deps/libchdr/deps/zstd-1.5.5/lib/compress/zstd_double_fast.c

   1 /*
   2  * Copyright (c) Meta Platforms, Inc. and affiliates.
   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_compress_internal.h"
  12 #include "zstd_double_fast.h"
  13
  14 static void ZSTD_fillDoubleHashTableForCDict(ZSTD_matchState_t* ms,
  15                               void const* end, ZSTD_dictTableLoadMethod_e dtlm)
  16 {
  17     const ZSTD_compressionParameters* const cParams = &ms->cParams;
  18     U32* const hashLarge = ms->hashTable;
  19     U32  const hBitsL = cParams->hashLog + ZSTD_SHORT_CACHE_TAG_BITS;
  20     U32  const mls = cParams->minMatch;
  21     U32* const hashSmall = ms->chainTable;
  22     U32  const hBitsS = cParams->chainLog + ZSTD_SHORT_CACHE_TAG_BITS;
  23     const BYTE* const base = ms->window.base;
  24     const BYTE* ip = base + ms->nextToUpdate;
  25     const BYTE* const iend = ((const BYTE*)end) - HASH_READ_SIZE;
  26     const U32 fastHashFillStep = 3;
  27
  28     /* Always insert every fastHashFillStep position into the hash tables.
  29      * Insert the other positions into the large hash table if their entry
  30      * is empty.
  31      */
  32     for (; ip + fastHashFillStep - 1 <= iend; ip += fastHashFillStep) {
  33         U32 const curr = (U32)(ip - base);
  34         U32 i;
  35         for (i = 0; i < fastHashFillStep; ++i) {
  36             size_t const smHashAndTag = ZSTD_hashPtr(ip + i, hBitsS, mls);
  37             size_t const lgHashAndTag = ZSTD_hashPtr(ip + i, hBitsL, 8);
  38             if (i == 0) {
  39                 ZSTD_writeTaggedIndex(hashSmall, smHashAndTag, curr + i);
  40             }
  41             if (i == 0 || hashLarge[lgHashAndTag >> ZSTD_SHORT_CACHE_TAG_BITS] == 0) {
  42                 ZSTD_writeTaggedIndex(hashLarge, lgHashAndTag, curr + i);
  43             }
  44             /* Only load extra positions for ZSTD_dtlm_full */
  45             if (dtlm == ZSTD_dtlm_fast)
  46                 break;
  47     }   }
  48 }
  49
  50 static void ZSTD_fillDoubleHashTableForCCtx(ZSTD_matchState_t* ms,
  51                               void const* end, ZSTD_dictTableLoadMethod_e dtlm)
  52 {
  53     const ZSTD_compressionParameters* const cParams = &ms->cParams;
  54     U32* const hashLarge = ms->hashTable;
  55     U32  const hBitsL = cParams->hashLog;
  56     U32  const mls = cParams->minMatch;
  57     U32* const hashSmall = ms->chainTable;
  58     U32  const hBitsS = cParams->chainLog;
  59     const BYTE* const base = ms->window.base;
  60     const BYTE* ip = base + ms->nextToUpdate;
  61     const BYTE* const iend = ((const BYTE*)end) - HASH_READ_SIZE;
  62     const U32 fastHashFillStep = 3;
  63
  64     /* Always insert every fastHashFillStep position into the hash tables.
  65      * Insert the other positions into the large hash table if their entry
  66      * is empty.
  67      */
  68     for (; ip + fastHashFillStep - 1 <= iend; ip += fastHashFillStep) {
  69         U32 const curr = (U32)(ip - base);
  70         U32 i;
  71         for (i = 0; i < fastHashFillStep; ++i) {
  72             size_t const smHash = ZSTD_hashPtr(ip + i, hBitsS, mls);
  73             size_t const lgHash = ZSTD_hashPtr(ip + i, hBitsL, 8);
  74             if (i == 0)
  75                 hashSmall[smHash] = curr + i;
  76             if (i == 0 || hashLarge[lgHash] == 0)
  77                 hashLarge[lgHash] = curr + i;
  78             /* Only load extra positions for ZSTD_dtlm_full */
  79             if (dtlm == ZSTD_dtlm_fast)
  80                 break;
  81         }   }
  82 }
  83
  84 void ZSTD_fillDoubleHashTable(ZSTD_matchState_t* ms,
  85                         const void* const end,
  86                         ZSTD_dictTableLoadMethod_e dtlm,
  87                         ZSTD_tableFillPurpose_e tfp)
  88 {
  89     if (tfp == ZSTD_tfp_forCDict) {
  90         ZSTD_fillDoubleHashTableForCDict(ms, end, dtlm);
  91     } else {
  92         ZSTD_fillDoubleHashTableForCCtx(ms, end, dtlm);
  93     }
  94 }
  95
  96
  97 FORCE_INLINE_TEMPLATE
  98 size_t ZSTD_compressBlock_doubleFast_noDict_generic(
  99         ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],
 100         void const* src, size_t srcSize, U32 const mls /* template */)
 101 {
 102     ZSTD_compressionParameters const* cParams = &ms->cParams;
 103     U32* const hashLong = ms->hashTable;
 104     const U32 hBitsL = cParams->hashLog;
 105     U32* const hashSmall = ms->chainTable;
 106     const U32 hBitsS = cParams->chainLog;
 107     const BYTE* const base = ms->window.base;
 108     const BYTE* const istart = (const BYTE*)src;
 109     const BYTE* anchor = istart;
 110     const U32 endIndex = (U32)((size_t)(istart - base) + srcSize);
 111     /* presumes that, if there is a dictionary, it must be using Attach mode */
 112     const U32 prefixLowestIndex = ZSTD_getLowestPrefixIndex(ms, endIndex, cParams->windowLog);
 113     const BYTE* const prefixLowest = base + prefixLowestIndex;
 114     const BYTE* const iend = istart + srcSize;
 115     const BYTE* const ilimit = iend - HASH_READ_SIZE;
 116     U32 offset_1=rep[0], offset_2=rep[1];
 117     U32 offsetSaved1 = 0, offsetSaved2 = 0;
 118
 119     size_t mLength;
 120     U32 offset;
 121     U32 curr;
 122
 123     /* how many positions to search before increasing step size */
 124     const size_t kStepIncr = 1 << kSearchStrength;
 125     /* the position at which to increment the step size if no match is found */
 126     const BYTE* nextStep;
 127     size_t step; /* the current step size */
 128
 129     size_t hl0; /* the long hash at ip */
 130     size_t hl1; /* the long hash at ip1 */
 131
 132     U32 idxl0; /* the long match index for ip */
 133     U32 idxl1; /* the long match index for ip1 */
 134
 135     const BYTE* matchl0; /* the long match for ip */
 136     const BYTE* matchs0; /* the short match for ip */
 137     const BYTE* matchl1; /* the long match for ip1 */
 138
 139     const BYTE* ip = istart; /* the current position */
 140     const BYTE* ip1; /* the next position */
 141
 142     DEBUGLOG(5, "ZSTD_compressBlock_doubleFast_noDict_generic");
 143
 144     /* init */
 145     ip += ((ip - prefixLowest) == 0);
 146     {
 147         U32 const current = (U32)(ip - base);
 148         U32 const windowLow = ZSTD_getLowestPrefixIndex(ms, current, cParams->windowLog);
 149         U32 const maxRep = current - windowLow;
 150         if (offset_2 > maxRep) offsetSaved2 = offset_2, offset_2 = 0;
 151         if (offset_1 > maxRep) offsetSaved1 = offset_1, offset_1 = 0;
 152     }
 153
 154     /* Outer Loop: one iteration per match found and stored */
 155     while (1) {
 156         step = 1;
 157         nextStep = ip + kStepIncr;
 158         ip1 = ip + step;
 159
 160         if (ip1 > ilimit) {
 161             goto _cleanup;
 162         }
 163
 164         hl0 = ZSTD_hashPtr(ip, hBitsL, 8);
 165         idxl0 = hashLong[hl0];
 166         matchl0 = base + idxl0;
 167
 168         /* Inner Loop: one iteration per search / position */
 169         do {
 170             const size_t hs0 = ZSTD_hashPtr(ip, hBitsS, mls);
 171             const U32 idxs0 = hashSmall[hs0];
 172             curr = (U32)(ip-base);
 173             matchs0 = base + idxs0;
 174
 175             hashLong[hl0] = hashSmall[hs0] = curr;   /* update hash tables */
 176
 177             /* check noDict repcode */
 178             if ((offset_1 > 0) & (MEM_read32(ip+1-offset_1) == MEM_read32(ip+1))) {
 179                 mLength = ZSTD_count(ip+1+4, ip+1+4-offset_1, iend) + 4;
 180                 ip++;
 181                 ZSTD_storeSeq(seqStore, (size_t)(ip-anchor), anchor, iend, REPCODE1_TO_OFFBASE, mLength);
 182                 goto _match_stored;
 183             }
 184
 185             hl1 = ZSTD_hashPtr(ip1, hBitsL, 8);
 186
 187             if (idxl0 > prefixLowestIndex) {
 188                 /* check prefix long match */
 189                 if (MEM_read64(matchl0) == MEM_read64(ip)) {
 190                     mLength = ZSTD_count(ip+8, matchl0+8, iend) + 8;
 191                     offset = (U32)(ip-matchl0);
 192                     while (((ip>anchor) & (matchl0>prefixLowest)) && (ip[-1] == matchl0[-1])) { ip--; matchl0--; mLength++; } /* catch up */
 193                     goto _match_found;
 194                 }
 195             }
 196
 197             idxl1 = hashLong[hl1];
 198             matchl1 = base + idxl1;
 199
 200             if (idxs0 > prefixLowestIndex) {
 201                 /* check prefix short match */
 202                 if (MEM_read32(matchs0) == MEM_read32(ip)) {
 203                     goto _search_next_long;
 204                 }
 205             }
 206
 207             if (ip1 >= nextStep) {
 208                 PREFETCH_L1(ip1 + 64);
 209                 PREFETCH_L1(ip1 + 128);
 210                 step++;
 211                 nextStep += kStepIncr;
 212             }
 213             ip = ip1;
 214             ip1 += step;
 215
 216             hl0 = hl1;
 217             idxl0 = idxl1;
 218             matchl0 = matchl1;
 219     #if defined(__aarch64__)
 220             PREFETCH_L1(ip+256);
 221     #endif
 222         } while (ip1 <= ilimit);
 223
 224 _cleanup:
 225         /* If offset_1 started invalid (offsetSaved1 != 0) and became valid (offset_1 != 0),
 226          * rotate saved offsets. See comment in ZSTD_compressBlock_fast_noDict for more context. */
 227         offsetSaved2 = ((offsetSaved1 != 0) && (offset_1 != 0)) ? offsetSaved1 : offsetSaved2;
 228
 229         /* save reps for next block */
 230         rep[0] = offset_1 ? offset_1 : offsetSaved1;
 231         rep[1] = offset_2 ? offset_2 : offsetSaved2;
 232
 233         /* Return the last literals size */
 234         return (size_t)(iend - anchor);
 235
 236 _search_next_long:
 237
 238         /* check prefix long +1 match */
 239         if (idxl1 > prefixLowestIndex) {
 240             if (MEM_read64(matchl1) == MEM_read64(ip1)) {
 241                 ip = ip1;
 242                 mLength = ZSTD_count(ip+8, matchl1+8, iend) + 8;
 243                 offset = (U32)(ip-matchl1);
 244                 while (((ip>anchor) & (matchl1>prefixLowest)) && (ip[-1] == matchl1[-1])) { ip--; matchl1--; mLength++; } /* catch up */
 245                 goto _match_found;
 246             }
 247         }
 248
 249         /* if no long +1 match, explore the short match we found */
 250         mLength = ZSTD_count(ip+4, matchs0+4, iend) + 4;
 251         offset = (U32)(ip - matchs0);
 252         while (((ip>anchor) & (matchs0>prefixLowest)) && (ip[-1] == matchs0[-1])) { ip--; matchs0--; mLength++; } /* catch up */
 253
 254         /* fall-through */
 255
 256 _match_found: /* requires ip, offset, mLength */
 257         offset_2 = offset_1;
 258         offset_1 = offset;
 259
 260         if (step < 4) {
 261             /* It is unsafe to write this value back to the hashtable when ip1 is
 262              * greater than or equal to the new ip we will have after we're done
 263              * processing this match. Rather than perform that test directly
 264              * (ip1 >= ip + mLength), which costs speed in practice, we do a simpler
 265              * more predictable test. The minmatch even if we take a short match is
 266              * 4 bytes, so as long as step, the distance between ip and ip1
 267              * (initially) is less than 4, we know ip1 < new ip. */
 268             hashLong[hl1] = (U32)(ip1 - base);
 269         }
 270
 271         ZSTD_storeSeq(seqStore, (size_t)(ip-anchor), anchor, iend, OFFSET_TO_OFFBASE(offset), mLength);
 272
 273 _match_stored:
 274         /* match found */
 275         ip += mLength;
 276         anchor = ip;
 277
 278         if (ip <= ilimit) {
 279             /* Complementary insertion */
 280             /* done after iLimit test, as candidates could be > iend-8 */
 281             {   U32 const indexToInsert = curr+2;
 282                 hashLong[ZSTD_hashPtr(base+indexToInsert, hBitsL, 8)] = indexToInsert;
 283                 hashLong[ZSTD_hashPtr(ip-2, hBitsL, 8)] = (U32)(ip-2-base);
 284                 hashSmall[ZSTD_hashPtr(base+indexToInsert, hBitsS, mls)] = indexToInsert;
 285                 hashSmall[ZSTD_hashPtr(ip-1, hBitsS, mls)] = (U32)(ip-1-base);
 286             }
 287
 288             /* check immediate repcode */
 289             while ( (ip <= ilimit)
 290                  && ( (offset_2>0)
 291                     & (MEM_read32(ip) == MEM_read32(ip - offset_2)) )) {
 292                 /* store sequence */
 293                 size_t const rLength = ZSTD_count(ip+4, ip+4-offset_2, iend) + 4;
 294                 U32 const tmpOff = offset_2; offset_2 = offset_1; offset_1 = tmpOff;  /* swap offset_2 <=> offset_1 */
 295                 hashSmall[ZSTD_hashPtr(ip, hBitsS, mls)] = (U32)(ip-base);
 296                 hashLong[ZSTD_hashPtr(ip, hBitsL, 8)] = (U32)(ip-base);
 297                 ZSTD_storeSeq(seqStore, 0, anchor, iend, REPCODE1_TO_OFFBASE, rLength);
 298                 ip += rLength;
 299                 anchor = ip;
 300                 continue;   /* faster when present ... (?) */
 301             }
 302         }
 303     }
 304 }
 305
 306
 307 FORCE_INLINE_TEMPLATE
 308 size_t ZSTD_compressBlock_doubleFast_dictMatchState_generic(
 309         ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],
 310         void const* src, size_t srcSize,
 311         U32 const mls /* template */)
 312 {
 313     ZSTD_compressionParameters const* cParams = &ms->cParams;
 314     U32* const hashLong = ms->hashTable;
 315     const U32 hBitsL = cParams->hashLog;
 316     U32* const hashSmall = ms->chainTable;
 317     const U32 hBitsS = cParams->chainLog;
 318     const BYTE* const base = ms->window.base;
 319     const BYTE* const istart = (const BYTE*)src;
 320     const BYTE* ip = istart;
 321     const BYTE* anchor = istart;
 322     const U32 endIndex = (U32)((size_t)(istart - base) + srcSize);
 323     /* presumes that, if there is a dictionary, it must be using Attach mode */
 324     const U32 prefixLowestIndex = ZSTD_getLowestPrefixIndex(ms, endIndex, cParams->windowLog);
 325     const BYTE* const prefixLowest = base + prefixLowestIndex;
 326     const BYTE* const iend = istart + srcSize;
 327     const BYTE* const ilimit = iend - HASH_READ_SIZE;
 328     U32 offset_1=rep[0], offset_2=rep[1];
 329
 330     const ZSTD_matchState_t* const dms = ms->dictMatchState;
 331     const ZSTD_compressionParameters* const dictCParams = &dms->cParams;
 332     const U32* const dictHashLong  = dms->hashTable;
 333     const U32* const dictHashSmall = dms->chainTable;
 334     const U32 dictStartIndex       = dms->window.dictLimit;
 335     const BYTE* const dictBase     = dms->window.base;
 336     const BYTE* const dictStart    = dictBase + dictStartIndex;
 337     const BYTE* const dictEnd      = dms->window.nextSrc;
 338     const U32 dictIndexDelta       = prefixLowestIndex - (U32)(dictEnd - dictBase);
 339     const U32 dictHBitsL           = dictCParams->hashLog + ZSTD_SHORT_CACHE_TAG_BITS;
 340     const U32 dictHBitsS           = dictCParams->chainLog + ZSTD_SHORT_CACHE_TAG_BITS;
 341     const U32 dictAndPrefixLength  = (U32)((ip - prefixLowest) + (dictEnd - dictStart));
 342
 343     DEBUGLOG(5, "ZSTD_compressBlock_doubleFast_dictMatchState_generic");
 344
 345     /* if a dictionary is attached, it must be within window range */
 346     assert(ms->window.dictLimit + (1U << cParams->windowLog) >= endIndex);
 347
 348     if (ms->prefetchCDictTables) {
 349         size_t const hashTableBytes = (((size_t)1) << dictCParams->hashLog) * sizeof(U32);
 350         size_t const chainTableBytes = (((size_t)1) << dictCParams->chainLog) * sizeof(U32);
 351         PREFETCH_AREA(dictHashLong, hashTableBytes)
 352         PREFETCH_AREA(dictHashSmall, chainTableBytes)
 353     }
 354
 355     /* init */
 356     ip += (dictAndPrefixLength == 0);
 357
 358     /* dictMatchState repCode checks don't currently handle repCode == 0
 359      * disabling. */
 360     assert(offset_1 <= dictAndPrefixLength);
 361     assert(offset_2 <= dictAndPrefixLength);
 362
 363     /* Main Search Loop */
 364     while (ip < ilimit) {   /* < instead of <=, because repcode check at (ip+1) */
 365         size_t mLength;
 366         U32 offset;
 367         size_t const h2 = ZSTD_hashPtr(ip, hBitsL, 8);
 368         size_t const h = ZSTD_hashPtr(ip, hBitsS, mls);
 369         size_t const dictHashAndTagL = ZSTD_hashPtr(ip, dictHBitsL, 8);
 370         size_t const dictHashAndTagS = ZSTD_hashPtr(ip, dictHBitsS, mls);
 371         U32 const dictMatchIndexAndTagL = dictHashLong[dictHashAndTagL >> ZSTD_SHORT_CACHE_TAG_BITS];
 372         U32 const dictMatchIndexAndTagS = dictHashSmall[dictHashAndTagS >> ZSTD_SHORT_CACHE_TAG_BITS];
 373         int const dictTagsMatchL = ZSTD_comparePackedTags(dictMatchIndexAndTagL, dictHashAndTagL);
 374         int const dictTagsMatchS = ZSTD_comparePackedTags(dictMatchIndexAndTagS, dictHashAndTagS);
 375         U32 const curr = (U32)(ip-base);
 376         U32 const matchIndexL = hashLong[h2];
 377         U32 matchIndexS = hashSmall[h];
 378         const BYTE* matchLong = base + matchIndexL;
 379         const BYTE* match = base + matchIndexS;
 380         const U32 repIndex = curr + 1 - offset_1;
 381         const BYTE* repMatch = (repIndex < prefixLowestIndex) ?
 382                                dictBase + (repIndex - dictIndexDelta) :
 383                                base + repIndex;
 384         hashLong[h2] = hashSmall[h] = curr;   /* update hash tables */
 385
 386         /* check repcode */
 387         if (((U32)((prefixLowestIndex-1) - repIndex) >= 3 /* intentional underflow */)
 388             && (MEM_read32(repMatch) == MEM_read32(ip+1)) ) {
 389             const BYTE* repMatchEnd = repIndex < prefixLowestIndex ? dictEnd : iend;
 390             mLength = ZSTD_count_2segments(ip+1+4, repMatch+4, iend, repMatchEnd, prefixLowest) + 4;
 391             ip++;
 392             ZSTD_storeSeq(seqStore, (size_t)(ip-anchor), anchor, iend, REPCODE1_TO_OFFBASE, mLength);
 393             goto _match_stored;
 394         }
 395
 396         if (matchIndexL > prefixLowestIndex) {
 397             /* check prefix long match */
 398             if (MEM_read64(matchLong) == MEM_read64(ip)) {
 399                 mLength = ZSTD_count(ip+8, matchLong+8, iend) + 8;
 400                 offset = (U32)(ip-matchLong);
 401                 while (((ip>anchor) & (matchLong>prefixLowest)) && (ip[-1] == matchLong[-1])) { ip--; matchLong--; mLength++; } /* catch up */
 402                 goto _match_found;
 403             }
 404         } else if (dictTagsMatchL) {
 405             /* check dictMatchState long match */
 406             U32 const dictMatchIndexL = dictMatchIndexAndTagL >> ZSTD_SHORT_CACHE_TAG_BITS;
 407             const BYTE* dictMatchL = dictBase + dictMatchIndexL;
 408             assert(dictMatchL < dictEnd);
 409
 410             if (dictMatchL > dictStart && MEM_read64(dictMatchL) == MEM_read64(ip)) {
 411                 mLength = ZSTD_count_2segments(ip+8, dictMatchL+8, iend, dictEnd, prefixLowest) + 8;
 412                 offset = (U32)(curr - dictMatchIndexL - dictIndexDelta);
 413                 while (((ip>anchor) & (dictMatchL>dictStart)) && (ip[-1] == dictMatchL[-1])) { ip--; dictMatchL--; mLength++; } /* catch up */
 414                 goto _match_found;
 415         }   }
 416
 417         if (matchIndexS > prefixLowestIndex) {
 418             /* check prefix short match */
 419             if (MEM_read32(match) == MEM_read32(ip)) {
 420                 goto _search_next_long;
 421             }
 422         } else if (dictTagsMatchS) {
 423             /* check dictMatchState short match */
 424             U32 const dictMatchIndexS = dictMatchIndexAndTagS >> ZSTD_SHORT_CACHE_TAG_BITS;
 425             match = dictBase + dictMatchIndexS;
 426             matchIndexS = dictMatchIndexS + dictIndexDelta;
 427
 428             if (match > dictStart && MEM_read32(match) == MEM_read32(ip)) {
 429                 goto _search_next_long;
 430         }   }
 431
 432         ip += ((ip-anchor) >> kSearchStrength) + 1;
 433 #if defined(__aarch64__)
 434         PREFETCH_L1(ip+256);
 435 #endif
 436         continue;
 437
 438 _search_next_long:
 439         {   size_t const hl3 = ZSTD_hashPtr(ip+1, hBitsL, 8);
 440             size_t const dictHashAndTagL3 = ZSTD_hashPtr(ip+1, dictHBitsL, 8);
 441             U32 const matchIndexL3 = hashLong[hl3];
 442             U32 const dictMatchIndexAndTagL3 = dictHashLong[dictHashAndTagL3 >> ZSTD_SHORT_CACHE_TAG_BITS];
 443             int const dictTagsMatchL3 = ZSTD_comparePackedTags(dictMatchIndexAndTagL3, dictHashAndTagL3);
 444             const BYTE* matchL3 = base + matchIndexL3;
 445             hashLong[hl3] = curr + 1;
 446
 447             /* check prefix long +1 match */
 448             if (matchIndexL3 > prefixLowestIndex) {
 449                 if (MEM_read64(matchL3) == MEM_read64(ip+1)) {
 450                     mLength = ZSTD_count(ip+9, matchL3+8, iend) + 8;
 451                     ip++;
 452                     offset = (U32)(ip-matchL3);
 453                     while (((ip>anchor) & (matchL3>prefixLowest)) && (ip[-1] == matchL3[-1])) { ip--; matchL3--; mLength++; } /* catch up */
 454                     goto _match_found;
 455                 }
 456             } else if (dictTagsMatchL3) {
 457                 /* check dict long +1 match */
 458                 U32 const dictMatchIndexL3 = dictMatchIndexAndTagL3 >> ZSTD_SHORT_CACHE_TAG_BITS;
 459                 const BYTE* dictMatchL3 = dictBase + dictMatchIndexL3;
 460                 assert(dictMatchL3 < dictEnd);
 461                 if (dictMatchL3 > dictStart && MEM_read64(dictMatchL3) == MEM_read64(ip+1)) {
 462                     mLength = ZSTD_count_2segments(ip+1+8, dictMatchL3+8, iend, dictEnd, prefixLowest) + 8;
 463                     ip++;
 464                     offset = (U32)(curr + 1 - dictMatchIndexL3 - dictIndexDelta);
 465                     while (((ip>anchor) & (dictMatchL3>dictStart)) && (ip[-1] == dictMatchL3[-1])) { ip--; dictMatchL3--; mLength++; } /* catch up */
 466                     goto _match_found;
 467         }   }   }
 468
 469         /* if no long +1 match, explore the short match we found */
 470         if (matchIndexS < prefixLowestIndex) {
 471             mLength = ZSTD_count_2segments(ip+4, match+4, iend, dictEnd, prefixLowest) + 4;
 472             offset = (U32)(curr - matchIndexS);
 473             while (((ip>anchor) & (match>dictStart)) && (ip[-1] == match[-1])) { ip--; match--; mLength++; } /* catch up */
 474         } else {
 475             mLength = ZSTD_count(ip+4, match+4, iend) + 4;
 476             offset = (U32)(ip - match);
 477             while (((ip>anchor) & (match>prefixLowest)) && (ip[-1] == match[-1])) { ip--; match--; mLength++; } /* catch up */
 478         }
 479
 480 _match_found:
 481         offset_2 = offset_1;
 482         offset_1 = offset;
 483
 484         ZSTD_storeSeq(seqStore, (size_t)(ip-anchor), anchor, iend, OFFSET_TO_OFFBASE(offset), mLength);
 485
 486 _match_stored:
 487         /* match found */
 488         ip += mLength;
 489         anchor = ip;
 490
 491         if (ip <= ilimit) {
 492             /* Complementary insertion */
 493             /* done after iLimit test, as candidates could be > iend-8 */
 494             {   U32 const indexToInsert = curr+2;
 495                 hashLong[ZSTD_hashPtr(base+indexToInsert, hBitsL, 8)] = indexToInsert;
 496                 hashLong[ZSTD_hashPtr(ip-2, hBitsL, 8)] = (U32)(ip-2-base);
 497                 hashSmall[ZSTD_hashPtr(base+indexToInsert, hBitsS, mls)] = indexToInsert;
 498                 hashSmall[ZSTD_hashPtr(ip-1, hBitsS, mls)] = (U32)(ip-1-base);
 499             }
 500
 501             /* check immediate repcode */
 502             while (ip <= ilimit) {
 503                 U32 const current2 = (U32)(ip-base);
 504                 U32 const repIndex2 = current2 - offset_2;
 505                 const BYTE* repMatch2 = repIndex2 < prefixLowestIndex ?
 506                         dictBase + repIndex2 - dictIndexDelta :
 507                         base + repIndex2;
 508                 if ( ((U32)((prefixLowestIndex-1) - (U32)repIndex2) >= 3 /* intentional overflow */)
 509                    && (MEM_read32(repMatch2) == MEM_read32(ip)) ) {
 510                     const BYTE* const repEnd2 = repIndex2 < prefixLowestIndex ? dictEnd : iend;
 511                     size_t const repLength2 = ZSTD_count_2segments(ip+4, repMatch2+4, iend, repEnd2, prefixLowest) + 4;
 512                     U32 tmpOffset = offset_2; offset_2 = offset_1; offset_1 = tmpOffset;   /* swap offset_2 <=> offset_1 */
 513                     ZSTD_storeSeq(seqStore, 0, anchor, iend, REPCODE1_TO_OFFBASE, repLength2);
 514                     hashSmall[ZSTD_hashPtr(ip, hBitsS, mls)] = current2;
 515                     hashLong[ZSTD_hashPtr(ip, hBitsL, 8)] = current2;
 516                     ip += repLength2;
 517                     anchor = ip;
 518                     continue;
 519                 }
 520                 break;
 521             }
 522         }
 523     }   /* while (ip < ilimit) */
 524
 525     /* save reps for next block */
 526     rep[0] = offset_1;
 527     rep[1] = offset_2;
 528
 529     /* Return the last literals size */
 530     return (size_t)(iend - anchor);
 531 }
 532
 533 #define ZSTD_GEN_DFAST_FN(dictMode, mls)                                                                 \
 534     static size_t ZSTD_compressBlock_doubleFast_##dictMode##_##mls(                                      \
 535             ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],                          \
 536             void const* src, size_t srcSize)                                                             \
 537     {                                                                                                    \
 538         return ZSTD_compressBlock_doubleFast_##dictMode##_generic(ms, seqStore, rep, src, srcSize, mls); \
 539     }
 540
 541 ZSTD_GEN_DFAST_FN(noDict, 4)
 542 ZSTD_GEN_DFAST_FN(noDict, 5)
 543 ZSTD_GEN_DFAST_FN(noDict, 6)
 544 ZSTD_GEN_DFAST_FN(noDict, 7)
 545
 546 ZSTD_GEN_DFAST_FN(dictMatchState, 4)
 547 ZSTD_GEN_DFAST_FN(dictMatchState, 5)
 548 ZSTD_GEN_DFAST_FN(dictMatchState, 6)
 549 ZSTD_GEN_DFAST_FN(dictMatchState, 7)
 550
 551
 552 size_t ZSTD_compressBlock_doubleFast(
 553         ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],
 554         void const* src, size_t srcSize)
 555 {
 556     const U32 mls = ms->cParams.minMatch;
 557     switch(mls)
 558     {
 559     default: /* includes case 3 */
 560     case 4 :
 561         return ZSTD_compressBlock_doubleFast_noDict_4(ms, seqStore, rep, src, srcSize);
 562     case 5 :
 563         return ZSTD_compressBlock_doubleFast_noDict_5(ms, seqStore, rep, src, srcSize);
 564     case 6 :
 565         return ZSTD_compressBlock_doubleFast_noDict_6(ms, seqStore, rep, src, srcSize);
 566     case 7 :
 567         return ZSTD_compressBlock_doubleFast_noDict_7(ms, seqStore, rep, src, srcSize);
 568     }
 569 }
 570
 571
 572 size_t ZSTD_compressBlock_doubleFast_dictMatchState(
 573         ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],
 574         void const* src, size_t srcSize)
 575 {
 576     const U32 mls = ms->cParams.minMatch;
 577     switch(mls)
 578     {
 579     default: /* includes case 3 */
 580     case 4 :
 581         return ZSTD_compressBlock_doubleFast_dictMatchState_4(ms, seqStore, rep, src, srcSize);
 582     case 5 :
 583         return ZSTD_compressBlock_doubleFast_dictMatchState_5(ms, seqStore, rep, src, srcSize);
 584     case 6 :
 585         return ZSTD_compressBlock_doubleFast_dictMatchState_6(ms, seqStore, rep, src, srcSize);
 586     case 7 :
 587         return ZSTD_compressBlock_doubleFast_dictMatchState_7(ms, seqStore, rep, src, srcSize);
 588     }
 589 }
 590
 591
 592 static size_t ZSTD_compressBlock_doubleFast_extDict_generic(
 593         ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],
 594         void const* src, size_t srcSize,
 595         U32 const mls /* template */)
 596 {
 597     ZSTD_compressionParameters const* cParams = &ms->cParams;
 598     U32* const hashLong = ms->hashTable;
 599     U32  const hBitsL = cParams->hashLog;
 600     U32* const hashSmall = ms->chainTable;
 601     U32  const hBitsS = cParams->chainLog;
 602     const BYTE* const istart = (const BYTE*)src;
 603     const BYTE* ip = istart;
 604     const BYTE* anchor = istart;
 605     const BYTE* const iend = istart + srcSize;
 606     const BYTE* const ilimit = iend - 8;
 607     const BYTE* const base = ms->window.base;
 608     const U32   endIndex = (U32)((size_t)(istart - base) + srcSize);
 609     const U32   lowLimit = ZSTD_getLowestMatchIndex(ms, endIndex, cParams->windowLog);
 610     const U32   dictStartIndex = lowLimit;
 611     const U32   dictLimit = ms->window.dictLimit;
 612     const U32   prefixStartIndex = (dictLimit > lowLimit) ? dictLimit : lowLimit;
 613     const BYTE* const prefixStart = base + prefixStartIndex;
 614     const BYTE* const dictBase = ms->window.dictBase;
 615     const BYTE* const dictStart = dictBase + dictStartIndex;
 616     const BYTE* const dictEnd = dictBase + prefixStartIndex;
 617     U32 offset_1=rep[0], offset_2=rep[1];
 618
 619     DEBUGLOG(5, "ZSTD_compressBlock_doubleFast_extDict_generic (srcSize=%zu)", srcSize);
 620
 621     /* if extDict is invalidated due to maxDistance, switch to "regular" variant */
 622     if (prefixStartIndex == dictStartIndex)
 623         return ZSTD_compressBlock_doubleFast(ms, seqStore, rep, src, srcSize);
 624
 625     /* Search Loop */
 626     while (ip < ilimit) {  /* < instead of <=, because (ip+1) */
 627         const size_t hSmall = ZSTD_hashPtr(ip, hBitsS, mls);
 628         const U32 matchIndex = hashSmall[hSmall];
 629         const BYTE* const matchBase = matchIndex < prefixStartIndex ? dictBase : base;
 630         const BYTE* match = matchBase + matchIndex;
 631
 632         const size_t hLong = ZSTD_hashPtr(ip, hBitsL, 8);
 633         const U32 matchLongIndex = hashLong[hLong];
 634         const BYTE* const matchLongBase = matchLongIndex < prefixStartIndex ? dictBase : base;
 635         const BYTE* matchLong = matchLongBase + matchLongIndex;
 636
 637         const U32 curr = (U32)(ip-base);
 638         const U32 repIndex = curr + 1 - offset_1;   /* offset_1 expected <= curr +1 */
 639         const BYTE* const repBase = repIndex < prefixStartIndex ? dictBase : base;
 640         const BYTE* const repMatch = repBase + repIndex;
 641         size_t mLength;
 642         hashSmall[hSmall] = hashLong[hLong] = curr;   /* update hash table */
 643
 644         if ((((U32)((prefixStartIndex-1) - repIndex) >= 3) /* intentional underflow : ensure repIndex doesn't overlap dict + prefix */
 645             & (offset_1 <= curr+1 - dictStartIndex)) /* note: we are searching at curr+1 */
 646           && (MEM_read32(repMatch) == MEM_read32(ip+1)) ) {
 647             const BYTE* repMatchEnd = repIndex < prefixStartIndex ? dictEnd : iend;
 648             mLength = ZSTD_count_2segments(ip+1+4, repMatch+4, iend, repMatchEnd, prefixStart) + 4;
 649             ip++;
 650             ZSTD_storeSeq(seqStore, (size_t)(ip-anchor), anchor, iend, REPCODE1_TO_OFFBASE, mLength);
 651         } else {
 652             if ((matchLongIndex > dictStartIndex) && (MEM_read64(matchLong) == MEM_read64(ip))) {
 653                 const BYTE* const matchEnd = matchLongIndex < prefixStartIndex ? dictEnd : iend;
 654                 const BYTE* const lowMatchPtr = matchLongIndex < prefixStartIndex ? dictStart : prefixStart;
 655                 U32 offset;
 656                 mLength = ZSTD_count_2segments(ip+8, matchLong+8, iend, matchEnd, prefixStart) + 8;
 657                 offset = curr - matchLongIndex;
 658                 while (((ip>anchor) & (matchLong>lowMatchPtr)) && (ip[-1] == matchLong[-1])) { ip--; matchLong--; mLength++; }   /* catch up */
 659                 offset_2 = offset_1;
 660                 offset_1 = offset;
 661                 ZSTD_storeSeq(seqStore, (size_t)(ip-anchor), anchor, iend, OFFSET_TO_OFFBASE(offset), mLength);
 662
 663             } else if ((matchIndex > dictStartIndex) && (MEM_read32(match) == MEM_read32(ip))) {
 664                 size_t const h3 = ZSTD_hashPtr(ip+1, hBitsL, 8);
 665                 U32 const matchIndex3 = hashLong[h3];
 666                 const BYTE* const match3Base = matchIndex3 < prefixStartIndex ? dictBase : base;
 667                 const BYTE* match3 = match3Base + matchIndex3;
 668                 U32 offset;
 669                 hashLong[h3] = curr + 1;
 670                 if ( (matchIndex3 > dictStartIndex) && (MEM_read64(match3) == MEM_read64(ip+1)) ) {
 671                     const BYTE* const matchEnd = matchIndex3 < prefixStartIndex ? dictEnd : iend;
 672                     const BYTE* const lowMatchPtr = matchIndex3 < prefixStartIndex ? dictStart : prefixStart;
 673                     mLength = ZSTD_count_2segments(ip+9, match3+8, iend, matchEnd, prefixStart) + 8;
 674                     ip++;
 675                     offset = curr+1 - matchIndex3;
 676                     while (((ip>anchor) & (match3>lowMatchPtr)) && (ip[-1] == match3[-1])) { ip--; match3--; mLength++; } /* catch up */
 677                 } else {
 678                     const BYTE* const matchEnd = matchIndex < prefixStartIndex ? dictEnd : iend;
 679                     const BYTE* const lowMatchPtr = matchIndex < prefixStartIndex ? dictStart : prefixStart;
 680                     mLength = ZSTD_count_2segments(ip+4, match+4, iend, matchEnd, prefixStart) + 4;
 681                     offset = curr - matchIndex;
 682                     while (((ip>anchor) & (match>lowMatchPtr)) && (ip[-1] == match[-1])) { ip--; match--; mLength++; }   /* catch up */
 683                 }
 684                 offset_2 = offset_1;
 685                 offset_1 = offset;
 686                 ZSTD_storeSeq(seqStore, (size_t)(ip-anchor), anchor, iend, OFFSET_TO_OFFBASE(offset), mLength);
 687
 688             } else {
 689                 ip += ((ip-anchor) >> kSearchStrength) + 1;
 690                 continue;
 691         }   }
 692
 693         /* move to next sequence start */
 694         ip += mLength;
 695         anchor = ip;
 696
 697         if (ip <= ilimit) {
 698             /* Complementary insertion */
 699             /* done after iLimit test, as candidates could be > iend-8 */
 700             {   U32 const indexToInsert = curr+2;
 701                 hashLong[ZSTD_hashPtr(base+indexToInsert, hBitsL, 8)] = indexToInsert;
 702                 hashLong[ZSTD_hashPtr(ip-2, hBitsL, 8)] = (U32)(ip-2-base);
 703                 hashSmall[ZSTD_hashPtr(base+indexToInsert, hBitsS, mls)] = indexToInsert;
 704                 hashSmall[ZSTD_hashPtr(ip-1, hBitsS, mls)] = (U32)(ip-1-base);
 705             }
 706
 707             /* check immediate repcode */
 708             while (ip <= ilimit) {
 709                 U32 const current2 = (U32)(ip-base);
 710                 U32 const repIndex2 = current2 - offset_2;
 711                 const BYTE* repMatch2 = repIndex2 < prefixStartIndex ? dictBase + repIndex2 : base + repIndex2;
 712                 if ( (((U32)((prefixStartIndex-1) - repIndex2) >= 3)   /* intentional overflow : ensure repIndex2 doesn't overlap dict + prefix */
 713                     & (offset_2 <= current2 - dictStartIndex))
 714                   && (MEM_read32(repMatch2) == MEM_read32(ip)) ) {
 715                     const BYTE* const repEnd2 = repIndex2 < prefixStartIndex ? dictEnd : iend;
 716                     size_t const repLength2 = ZSTD_count_2segments(ip+4, repMatch2+4, iend, repEnd2, prefixStart) + 4;
 717                     U32 const tmpOffset = offset_2; offset_2 = offset_1; offset_1 = tmpOffset;   /* swap offset_2 <=> offset_1 */
 718                     ZSTD_storeSeq(seqStore, 0, anchor, iend, REPCODE1_TO_OFFBASE, repLength2);
 719                     hashSmall[ZSTD_hashPtr(ip, hBitsS, mls)] = current2;
 720                     hashLong[ZSTD_hashPtr(ip, hBitsL, 8)] = current2;
 721                     ip += repLength2;
 722                     anchor = ip;
 723                     continue;
 724                 }
 725                 break;
 726     }   }   }
 727
 728     /* save reps for next block */
 729     rep[0] = offset_1;
 730     rep[1] = offset_2;
 731
 732     /* Return the last literals size */
 733     return (size_t)(iend - anchor);
 734 }
 735
 736 ZSTD_GEN_DFAST_FN(extDict, 4)
 737 ZSTD_GEN_DFAST_FN(extDict, 5)
 738 ZSTD_GEN_DFAST_FN(extDict, 6)
 739 ZSTD_GEN_DFAST_FN(extDict, 7)
 740
 741 size_t ZSTD_compressBlock_doubleFast_extDict(
 742         ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],
 743         void const* src, size_t srcSize)
 744 {
 745     U32 const mls = ms->cParams.minMatch;
 746     switch(mls)
 747     {
 748     default: /* includes case 3 */
 749     case 4 :
 750         return ZSTD_compressBlock_doubleFast_extDict_4(ms, seqStore, rep, src, srcSize);
 751     case 5 :
 752         return ZSTD_compressBlock_doubleFast_extDict_5(ms, seqStore, rep, src, srcSize);
 753     case 6 :
 754         return ZSTD_compressBlock_doubleFast_extDict_6(ms, seqStore, rep, src, srcSize);
 755     case 7 :
 756         return ZSTD_compressBlock_doubleFast_extDict_7(ms, seqStore, rep, src, srcSize);
 757     }
 758 }