sys/contrib/zstd/lib/compress/zstd_fast.c

   1 /*
   2  * Copyright (c) 2016-present, Yann Collet, Facebook, Inc.
   3  * All rights reserved.
   4  *
   5  * This source code is licensed under both the BSD-style license (found in the
   6  * LICENSE file in the root directory of this source tree) and the GPLv2 (found
   7  * in the COPYING file in the root directory of this source tree).
   8  * You may select, at your option, one of the above-listed licenses.
   9  */
  10
  11 #include "zstd_fast.h"
  12
  13
  14 void ZSTD_fillHashTable (ZSTD_CCtx* zc, const void* end, const U32 mls)
  15 {
  16     U32* const hashTable = zc->hashTable;
  17     U32  const hBits = zc->appliedParams.cParams.hashLog;
  18     const BYTE* const base = zc->base;
  19     const BYTE* ip = base + zc->nextToUpdate;
  20     const BYTE* const iend = ((const BYTE*)end) - HASH_READ_SIZE;
  21     const size_t fastHashFillStep = 3;
  22
  23     while(ip <= iend) {
  24         hashTable[ZSTD_hashPtr(ip, hBits, mls)] = (U32)(ip - base);
  25         ip += fastHashFillStep;
  26     }
  27 }
  28
  29
  30 FORCE_INLINE_TEMPLATE
  31 size_t ZSTD_compressBlock_fast_generic(ZSTD_CCtx* cctx,
  32                                  const void* src, size_t srcSize,
  33                                  const U32 mls)
  34 {
  35     U32* const hashTable = cctx->hashTable;
  36     U32  const hBits = cctx->appliedParams.cParams.hashLog;
  37     seqStore_t* seqStorePtr = &(cctx->seqStore);
  38     const BYTE* const base = cctx->base;
  39     const BYTE* const istart = (const BYTE*)src;
  40     const BYTE* ip = istart;
  41     const BYTE* anchor = istart;
  42     const U32   lowestIndex = cctx->dictLimit;
  43     const BYTE* const lowest = base + lowestIndex;
  44     const BYTE* const iend = istart + srcSize;
  45     const BYTE* const ilimit = iend - HASH_READ_SIZE;
  46     U32 offset_1=seqStorePtr->rep[0], offset_2=seqStorePtr->rep[1];
  47     U32 offsetSaved = 0;
  48
  49     /* init */
  50     ip += (ip==lowest);
  51     {   U32 const maxRep = (U32)(ip-lowest);
  52         if (offset_2 > maxRep) offsetSaved = offset_2, offset_2 = 0;
  53         if (offset_1 > maxRep) offsetSaved = offset_1, offset_1 = 0;
  54     }
  55
  56     /* Main Search Loop */
  57     while (ip < ilimit) {   /* < instead of <=, because repcode check at (ip+1) */
  58         size_t mLength;
  59         size_t const h = ZSTD_hashPtr(ip, hBits, mls);
  60         U32 const current = (U32)(ip-base);
  61         U32 const matchIndex = hashTable[h];
  62         const BYTE* match = base + matchIndex;
  63         hashTable[h] = current;   /* update hash table */
  64
  65         if ((offset_1 > 0) & (MEM_read32(ip+1-offset_1) == MEM_read32(ip+1))) {
  66             mLength = ZSTD_count(ip+1+4, ip+1+4-offset_1, iend) + 4;
  67             ip++;
  68             ZSTD_storeSeq(seqStorePtr, ip-anchor, anchor, 0, mLength-MINMATCH);
  69         } else {
  70             U32 offset;
  71             if ( (matchIndex <= lowestIndex) || (MEM_read32(match) != MEM_read32(ip)) ) {
  72                 ip += ((ip-anchor) >> g_searchStrength) + 1;
  73                 continue;
  74             }
  75             mLength = ZSTD_count(ip+4, match+4, iend) + 4;
  76             offset = (U32)(ip-match);
  77             while (((ip>anchor) & (match>lowest)) && (ip[-1] == match[-1])) { ip--; match--; mLength++; } /* catch up */
  78             offset_2 = offset_1;
  79             offset_1 = offset;
  80
  81             ZSTD_storeSeq(seqStorePtr, ip-anchor, anchor, offset + ZSTD_REP_MOVE, mLength-MINMATCH);
  82         }
  83
  84         /* match found */
  85         ip += mLength;
  86         anchor = ip;
  87
  88         if (ip <= ilimit) {
  89             /* Fill Table */
  90             hashTable[ZSTD_hashPtr(base+current+2, hBits, mls)] = current+2;  /* here because current+2 could be > iend-8 */
  91             hashTable[ZSTD_hashPtr(ip-2, hBits, mls)] = (U32)(ip-2-base);
  92             /* check immediate repcode */
  93             while ( (ip <= ilimit)
  94                  && ( (offset_2>0)
  95                  & (MEM_read32(ip) == MEM_read32(ip - offset_2)) )) {
  96                 /* store sequence */
  97                 size_t const rLength = ZSTD_count(ip+4, ip+4-offset_2, iend) + 4;
  98                 { U32 const tmpOff = offset_2; offset_2 = offset_1; offset_1 = tmpOff; }  /* swap offset_2 <=> offset_1 */
  99                 hashTable[ZSTD_hashPtr(ip, hBits, mls)] = (U32)(ip-base);
 100                 ZSTD_storeSeq(seqStorePtr, 0, anchor, 0, rLength-MINMATCH);
 101                 ip += rLength;
 102                 anchor = ip;
 103                 continue;   /* faster when present ... (?) */
 104     }   }   }
 105
 106     /* save reps for next block */
 107     seqStorePtr->repToConfirm[0] = offset_1 ? offset_1 : offsetSaved;
 108     seqStorePtr->repToConfirm[1] = offset_2 ? offset_2 : offsetSaved;
 109
 110     /* Return the last literals size */
 111     return iend - anchor;
 112 }
 113
 114
 115 size_t ZSTD_compressBlock_fast(ZSTD_CCtx* ctx,
 116                        const void* src, size_t srcSize)
 117 {
 118     const U32 mls = ctx->appliedParams.cParams.searchLength;
 119     switch(mls)
 120     {
 121     default: /* includes case 3 */
 122     case 4 :
 123         return ZSTD_compressBlock_fast_generic(ctx, src, srcSize, 4);
 124     case 5 :
 125         return ZSTD_compressBlock_fast_generic(ctx, src, srcSize, 5);
 126     case 6 :
 127         return ZSTD_compressBlock_fast_generic(ctx, src, srcSize, 6);
 128     case 7 :
 129         return ZSTD_compressBlock_fast_generic(ctx, src, srcSize, 7);
 130     }
 131 }
 132
 133
 134 static size_t ZSTD_compressBlock_fast_extDict_generic(ZSTD_CCtx* ctx,
 135                                  const void* src, size_t srcSize,
 136                                  const U32 mls)
 137 {
 138     U32* hashTable = ctx->hashTable;
 139     const U32 hBits = ctx->appliedParams.cParams.hashLog;
 140     seqStore_t* seqStorePtr = &(ctx->seqStore);
 141     const BYTE* const base = ctx->base;
 142     const BYTE* const dictBase = ctx->dictBase;
 143     const BYTE* const istart = (const BYTE*)src;
 144     const BYTE* ip = istart;
 145     const BYTE* anchor = istart;
 146     const U32   lowestIndex = ctx->lowLimit;
 147     const BYTE* const dictStart = dictBase + lowestIndex;
 148     const U32   dictLimit = ctx->dictLimit;
 149     const BYTE* const lowPrefixPtr = base + dictLimit;
 150     const BYTE* const dictEnd = dictBase + dictLimit;
 151     const BYTE* const iend = istart + srcSize;
 152     const BYTE* const ilimit = iend - 8;
 153     U32 offset_1=seqStorePtr->rep[0], offset_2=seqStorePtr->rep[1];
 154
 155     /* Search Loop */
 156     while (ip < ilimit) {  /* < instead of <=, because (ip+1) */
 157         const size_t h = ZSTD_hashPtr(ip, hBits, mls);
 158         const U32 matchIndex = hashTable[h];
 159         const BYTE* matchBase = matchIndex < dictLimit ? dictBase : base;
 160         const BYTE* match = matchBase + matchIndex;
 161         const U32 current = (U32)(ip-base);
 162         const U32 repIndex = current + 1 - offset_1;   /* offset_1 expected <= current +1 */
 163         const BYTE* repBase = repIndex < dictLimit ? dictBase : base;
 164         const BYTE* repMatch = repBase + repIndex;
 165         size_t mLength;
 166         hashTable[h] = current;   /* update hash table */
 167
 168         if ( (((U32)((dictLimit-1) - repIndex) >= 3) /* intentional underflow */ & (repIndex > lowestIndex))
 169            && (MEM_read32(repMatch) == MEM_read32(ip+1)) ) {
 170             const BYTE* repMatchEnd = repIndex < dictLimit ? dictEnd : iend;
 171             mLength = ZSTD_count_2segments(ip+1+4, repMatch+4, iend, repMatchEnd, lowPrefixPtr) + 4;
 172             ip++;
 173             ZSTD_storeSeq(seqStorePtr, ip-anchor, anchor, 0, mLength-MINMATCH);
 174         } else {
 175             if ( (matchIndex < lowestIndex) ||
 176                  (MEM_read32(match) != MEM_read32(ip)) ) {
 177                 ip += ((ip-anchor) >> g_searchStrength) + 1;
 178                 continue;
 179             }
 180             {   const BYTE* matchEnd = matchIndex < dictLimit ? dictEnd : iend;
 181                 const BYTE* lowMatchPtr = matchIndex < dictLimit ? dictStart : lowPrefixPtr;
 182                 U32 offset;
 183                 mLength = ZSTD_count_2segments(ip+4, match+4, iend, matchEnd, lowPrefixPtr) + 4;
 184                 while (((ip>anchor) & (match>lowMatchPtr)) && (ip[-1] == match[-1])) { ip--; match--; mLength++; }   /* catch up */
 185                 offset = current - matchIndex;
 186                 offset_2 = offset_1;
 187                 offset_1 = offset;
 188                 ZSTD_storeSeq(seqStorePtr, ip-anchor, anchor, offset + ZSTD_REP_MOVE, mLength-MINMATCH);
 189         }   }
 190
 191         /* found a match : store it */
 192         ip += mLength;
 193         anchor = ip;
 194
 195         if (ip <= ilimit) {
 196             /* Fill Table */
 197             hashTable[ZSTD_hashPtr(base+current+2, hBits, mls)] = current+2;
 198             hashTable[ZSTD_hashPtr(ip-2, hBits, mls)] = (U32)(ip-2-base);
 199             /* check immediate repcode */
 200             while (ip <= ilimit) {
 201                 U32 const current2 = (U32)(ip-base);
 202                 U32 const repIndex2 = current2 - offset_2;
 203                 const BYTE* repMatch2 = repIndex2 < dictLimit ? dictBase + repIndex2 : base + repIndex2;
 204                 if ( (((U32)((dictLimit-1) - repIndex2) >= 3) & (repIndex2 > lowestIndex))  /* intentional overflow */
 205                    && (MEM_read32(repMatch2) == MEM_read32(ip)) ) {
 206                     const BYTE* const repEnd2 = repIndex2 < dictLimit ? dictEnd : iend;
 207                     size_t const repLength2 = ZSTD_count_2segments(ip+4, repMatch2+4, iend, repEnd2, lowPrefixPtr) + 4;
 208                     U32 tmpOffset = offset_2; offset_2 = offset_1; offset_1 = tmpOffset;   /* swap offset_2 <=> offset_1 */
 209                     ZSTD_storeSeq(seqStorePtr, 0, anchor, 0, repLength2-MINMATCH);
 210                     hashTable[ZSTD_hashPtr(ip, hBits, mls)] = current2;
 211                     ip += repLength2;
 212                     anchor = ip;
 213                     continue;
 214                 }
 215                 break;
 216     }   }   }
 217
 218     /* save reps for next block */
 219     seqStorePtr->repToConfirm[0] = offset_1; seqStorePtr->repToConfirm[1] = offset_2;
 220
 221     /* Return the last literals size */
 222     return iend - anchor;
 223 }
 224
 225
 226 size_t ZSTD_compressBlock_fast_extDict(ZSTD_CCtx* ctx,
 227                          const void* src, size_t srcSize)
 228 {
 229     U32 const mls = ctx->appliedParams.cParams.searchLength;
 230     switch(mls)
 231     {
 232     default: /* includes case 3 */
 233     case 4 :
 234         return ZSTD_compressBlock_fast_extDict_generic(ctx, src, srcSize, 4);
 235     case 5 :
 236         return ZSTD_compressBlock_fast_extDict_generic(ctx, src, srcSize, 5);
 237     case 6 :
 238         return ZSTD_compressBlock_fast_extDict_generic(ctx, src, srcSize, 6);
 239     case 7 :
 240         return ZSTD_compressBlock_fast_extDict_generic(ctx, src, srcSize, 7);
 241     }
 242 }