ceph/src/zstd/lib/compress/zstd_opt.h

   1 /**
   2  * Copyright (c) 2016-present, Przemyslaw Skibinski, Yann Collet, Facebook, Inc.
   3  * All rights reserved.
   4  *
   5  * This source code is licensed under the BSD-style license found in the
   6  * LICENSE file in the root directory of this source tree. An additional grant
   7  * of patent rights can be found in the PATENTS file in the same directory.
   8  */
   9
  10
  11 /* Note : this file is intended to be included within zstd_compress.c */
  12
  13
  14 #ifndef ZSTD_OPT_H_91842398743
  15 #define ZSTD_OPT_H_91842398743
  16
  17
  18 #define ZSTD_LITFREQ_ADD    2
  19 #define ZSTD_FREQ_DIV       4
  20 #define ZSTD_MAX_PRICE      (1<<30)
  21
  22 /*-*************************************
  23 *  Price functions for optimal parser
  24 ***************************************/
  25 FORCE_INLINE void ZSTD_setLog2Prices(seqStore_t* ssPtr)
  26 {
  27     ssPtr->log2matchLengthSum = ZSTD_highbit32(ssPtr->matchLengthSum+1);
  28     ssPtr->log2litLengthSum = ZSTD_highbit32(ssPtr->litLengthSum+1);
  29     ssPtr->log2litSum = ZSTD_highbit32(ssPtr->litSum+1);
  30     ssPtr->log2offCodeSum = ZSTD_highbit32(ssPtr->offCodeSum+1);
  31     ssPtr->factor = 1 + ((ssPtr->litSum>>5) / ssPtr->litLengthSum) + ((ssPtr->litSum<<1) / (ssPtr->litSum + ssPtr->matchSum));
  32 }
  33
  34
  35 MEM_STATIC void ZSTD_rescaleFreqs(seqStore_t* ssPtr, const BYTE* src, size_t srcSize)
  36 {
  37     unsigned u;
  38
  39     ssPtr->cachedLiterals = NULL;
  40     ssPtr->cachedPrice = ssPtr->cachedLitLength = 0;
  41     ssPtr->staticPrices = 0;
  42
  43     if (ssPtr->litLengthSum == 0) {
  44         if (srcSize <= 1024) ssPtr->staticPrices = 1;
  45
  46         for (u=0; u<=MaxLit; u++)
  47             ssPtr->litFreq[u] = 0;
  48         for (u=0; u<srcSize; u++)
  49             ssPtr->litFreq[src[u]]++;
  50
  51         ssPtr->litSum = 0;
  52         ssPtr->litLengthSum = MaxLL+1;
  53         ssPtr->matchLengthSum = MaxML+1;
  54         ssPtr->offCodeSum = (MaxOff+1);
  55         ssPtr->matchSum = (ZSTD_LITFREQ_ADD<<Litbits);
  56
  57         for (u=0; u<=MaxLit; u++) {
  58             ssPtr->litFreq[u] = 1 + (ssPtr->litFreq[u]>>ZSTD_FREQ_DIV);
  59             ssPtr->litSum += ssPtr->litFreq[u];
  60         }
  61         for (u=0; u<=MaxLL; u++)
  62             ssPtr->litLengthFreq[u] = 1;
  63         for (u=0; u<=MaxML; u++)
  64             ssPtr->matchLengthFreq[u] = 1;
  65         for (u=0; u<=MaxOff; u++)
  66             ssPtr->offCodeFreq[u] = 1;
  67     } else {
  68         ssPtr->matchLengthSum = 0;
  69         ssPtr->litLengthSum = 0;
  70         ssPtr->offCodeSum = 0;
  71         ssPtr->matchSum = 0;
  72         ssPtr->litSum = 0;
  73
  74         for (u=0; u<=MaxLit; u++) {
  75             ssPtr->litFreq[u] = 1 + (ssPtr->litFreq[u]>>(ZSTD_FREQ_DIV+1));
  76             ssPtr->litSum += ssPtr->litFreq[u];
  77         }
  78         for (u=0; u<=MaxLL; u++) {
  79             ssPtr->litLengthFreq[u] = 1 + (ssPtr->litLengthFreq[u]>>(ZSTD_FREQ_DIV+1));
  80             ssPtr->litLengthSum += ssPtr->litLengthFreq[u];
  81         }
  82         for (u=0; u<=MaxML; u++) {
  83             ssPtr->matchLengthFreq[u] = 1 + (ssPtr->matchLengthFreq[u]>>ZSTD_FREQ_DIV);
  84             ssPtr->matchLengthSum += ssPtr->matchLengthFreq[u];
  85             ssPtr->matchSum += ssPtr->matchLengthFreq[u] * (u + 3);
  86         }
  87         ssPtr->matchSum *= ZSTD_LITFREQ_ADD;
  88         for (u=0; u<=MaxOff; u++) {
  89             ssPtr->offCodeFreq[u] = 1 + (ssPtr->offCodeFreq[u]>>ZSTD_FREQ_DIV);
  90             ssPtr->offCodeSum += ssPtr->offCodeFreq[u];
  91         }
  92     }
  93
  94     ZSTD_setLog2Prices(ssPtr);
  95 }
  96
  97
  98 FORCE_INLINE U32 ZSTD_getLiteralPrice(seqStore_t* ssPtr, U32 litLength, const BYTE* literals)
  99 {
 100     U32 price, u;
 101
 102     if (ssPtr->staticPrices)
 103         return ZSTD_highbit32((U32)litLength+1) + (litLength*6);
 104
 105     if (litLength == 0)
 106         return ssPtr->log2litLengthSum - ZSTD_highbit32(ssPtr->litLengthFreq[0]+1);
 107
 108     /* literals */
 109     if (ssPtr->cachedLiterals == literals) {
 110         U32 const additional = litLength - ssPtr->cachedLitLength;
 111         const BYTE* literals2 = ssPtr->cachedLiterals + ssPtr->cachedLitLength;
 112         price = ssPtr->cachedPrice + additional * ssPtr->log2litSum;
 113         for (u=0; u < additional; u++)
 114             price -= ZSTD_highbit32(ssPtr->litFreq[literals2[u]]+1);
 115         ssPtr->cachedPrice = price;
 116         ssPtr->cachedLitLength = litLength;
 117     } else {
 118         price = litLength * ssPtr->log2litSum;
 119         for (u=0; u < litLength; u++)
 120             price -= ZSTD_highbit32(ssPtr->litFreq[literals[u]]+1);
 121
 122         if (litLength >= 12) {
 123             ssPtr->cachedLiterals = literals;
 124             ssPtr->cachedPrice = price;
 125             ssPtr->cachedLitLength = litLength;
 126         }
 127     }
 128
 129     /* literal Length */
 130     {   const BYTE LL_deltaCode = 19;
 131         const BYTE llCode = (litLength>63) ? (BYTE)ZSTD_highbit32(litLength) + LL_deltaCode : LL_Code[litLength];
 132         price += LL_bits[llCode] + ssPtr->log2litLengthSum - ZSTD_highbit32(ssPtr->litLengthFreq[llCode]+1);
 133     }
 134
 135     return price;
 136 }
 137
 138
 139 FORCE_INLINE U32 ZSTD_getPrice(seqStore_t* seqStorePtr, U32 litLength, const BYTE* literals, U32 offset, U32 matchLength, const int ultra)
 140 {
 141     /* offset */
 142     U32 price;
 143     BYTE const offCode = (BYTE)ZSTD_highbit32(offset+1);
 144
 145     if (seqStorePtr->staticPrices)
 146         return ZSTD_getLiteralPrice(seqStorePtr, litLength, literals) + ZSTD_highbit32((U32)matchLength+1) + 16 + offCode;
 147
 148     price = offCode + seqStorePtr->log2offCodeSum - ZSTD_highbit32(seqStorePtr->offCodeFreq[offCode]+1);
 149     if (!ultra && offCode >= 20) price += (offCode-19)*2;
 150
 151     /* match Length */
 152     {   const BYTE ML_deltaCode = 36;
 153         const BYTE mlCode = (matchLength>127) ? (BYTE)ZSTD_highbit32(matchLength) + ML_deltaCode : ML_Code[matchLength];
 154         price += ML_bits[mlCode] + seqStorePtr->log2matchLengthSum - ZSTD_highbit32(seqStorePtr->matchLengthFreq[mlCode]+1);
 155     }
 156
 157     return price + ZSTD_getLiteralPrice(seqStorePtr, litLength, literals) + seqStorePtr->factor;
 158 }
 159
 160
 161 MEM_STATIC void ZSTD_updatePrice(seqStore_t* seqStorePtr, U32 litLength, const BYTE* literals, U32 offset, U32 matchLength)
 162 {
 163     U32 u;
 164
 165     /* literals */
 166     seqStorePtr->litSum += litLength*ZSTD_LITFREQ_ADD;
 167     for (u=0; u < litLength; u++)
 168         seqStorePtr->litFreq[literals[u]] += ZSTD_LITFREQ_ADD;
 169
 170     /* literal Length */
 171     {   const BYTE LL_deltaCode = 19;
 172         const BYTE llCode = (litLength>63) ? (BYTE)ZSTD_highbit32(litLength) + LL_deltaCode : LL_Code[litLength];
 173         seqStorePtr->litLengthFreq[llCode]++;
 174         seqStorePtr->litLengthSum++;
 175     }
 176
 177     /* match offset */
 178         {   BYTE const offCode = (BYTE)ZSTD_highbit32(offset+1);
 179                 seqStorePtr->offCodeSum++;
 180                 seqStorePtr->offCodeFreq[offCode]++;
 181         }
 182
 183     /* match Length */
 184     {   const BYTE ML_deltaCode = 36;
 185         const BYTE mlCode = (matchLength>127) ? (BYTE)ZSTD_highbit32(matchLength) + ML_deltaCode : ML_Code[matchLength];
 186         seqStorePtr->matchLengthFreq[mlCode]++;
 187         seqStorePtr->matchLengthSum++;
 188     }
 189
 190     ZSTD_setLog2Prices(seqStorePtr);
 191 }
 192
 193
 194 #define SET_PRICE(pos, mlen_, offset_, litlen_, price_)   \
 195     {                                                 \
 196         while (last_pos < pos)  { opt[last_pos+1].price = ZSTD_MAX_PRICE; last_pos++; } \
 197         opt[pos].mlen = mlen_;                         \
 198         opt[pos].off = offset_;                        \
 199         opt[pos].litlen = litlen_;                     \
 200         opt[pos].price = price_;                       \
 201     }
 202
 203
 204
 205 /* Update hashTable3 up to ip (excluded)
 206    Assumption : always within prefix (ie. not within extDict) */
 207 FORCE_INLINE
 208 U32 ZSTD_insertAndFindFirstIndexHash3 (ZSTD_CCtx* zc, const BYTE* ip)
 209 {
 210     U32* const hashTable3  = zc->hashTable3;
 211     U32 const hashLog3  = zc->hashLog3;
 212     const BYTE* const base = zc->base;
 213     U32 idx = zc->nextToUpdate3;
 214     const U32 target = zc->nextToUpdate3 = (U32)(ip - base);
 215     const size_t hash3 = ZSTD_hash3Ptr(ip, hashLog3);
 216
 217     while(idx < target) {
 218         hashTable3[ZSTD_hash3Ptr(base+idx, hashLog3)] = idx;
 219         idx++;
 220     }
 221
 222     return hashTable3[hash3];
 223 }
 224
 225
 226 /*-*************************************
 227 *  Binary Tree search
 228 ***************************************/
 229 static U32 ZSTD_insertBtAndGetAllMatches (
 230                         ZSTD_CCtx* zc,
 231                         const BYTE* const ip, const BYTE* const iLimit,
 232                         U32 nbCompares, const U32 mls,
 233                         U32 extDict, ZSTD_match_t* matches, const U32 minMatchLen)
 234 {
 235     const BYTE* const base = zc->base;
 236     const U32 current = (U32)(ip-base);
 237     const U32 hashLog = zc->params.cParams.hashLog;
 238     const size_t h  = ZSTD_hashPtr(ip, hashLog, mls);
 239     U32* const hashTable = zc->hashTable;
 240     U32 matchIndex  = hashTable[h];
 241     U32* const bt   = zc->chainTable;
 242     const U32 btLog = zc->params.cParams.chainLog - 1;
 243     const U32 btMask= (1U << btLog) - 1;
 244     size_t commonLengthSmaller=0, commonLengthLarger=0;
 245     const BYTE* const dictBase = zc->dictBase;
 246     const U32 dictLimit = zc->dictLimit;
 247     const BYTE* const dictEnd = dictBase + dictLimit;
 248     const BYTE* const prefixStart = base + dictLimit;
 249     const U32 btLow = btMask >= current ? 0 : current - btMask;
 250     const U32 windowLow = zc->lowLimit;
 251     U32* smallerPtr = bt + 2*(current&btMask);
 252     U32* largerPtr  = bt + 2*(current&btMask) + 1;
 253     U32 matchEndIdx = current+8;
 254     U32 dummy32;   /* to be nullified at the end */
 255     U32 mnum = 0;
 256
 257     const U32 minMatch = (mls == 3) ? 3 : 4;
 258     size_t bestLength = minMatchLen-1;
 259
 260     if (minMatch == 3) { /* HC3 match finder */
 261         U32 const matchIndex3 = ZSTD_insertAndFindFirstIndexHash3 (zc, ip);
 262         if (matchIndex3>windowLow && (current - matchIndex3 < (1<<18))) {
 263             const BYTE* match;
 264             size_t currentMl=0;
 265             if ((!extDict) || matchIndex3 >= dictLimit) {
 266                 match = base + matchIndex3;
 267                 if (match[bestLength] == ip[bestLength]) currentMl = ZSTD_count(ip, match, iLimit);
 268             } else {
 269                 match = dictBase + matchIndex3;
 270                 if (MEM_readMINMATCH(match, MINMATCH) == MEM_readMINMATCH(ip, MINMATCH))    /* assumption : matchIndex3 <= dictLimit-4 (by table construction) */
 271                     currentMl = ZSTD_count_2segments(ip+MINMATCH, match+MINMATCH, iLimit, dictEnd, prefixStart) + MINMATCH;
 272             }
 273
 274             /* save best solution */
 275             if (currentMl > bestLength) {
 276                 bestLength = currentMl;
 277                 matches[mnum].off = ZSTD_REP_MOVE_OPT + current - matchIndex3;
 278                 matches[mnum].len = (U32)currentMl;
 279                 mnum++;
 280                 if (currentMl > ZSTD_OPT_NUM) goto update;
 281                 if (ip+currentMl == iLimit) goto update; /* best possible, and avoid read overflow*/
 282             }
 283         }
 284     }
 285
 286     hashTable[h] = current;   /* Update Hash Table */
 287
 288     while (nbCompares-- && (matchIndex > windowLow)) {
 289         U32* nextPtr = bt + 2*(matchIndex & btMask);
 290         size_t matchLength = MIN(commonLengthSmaller, commonLengthLarger);   /* guaranteed minimum nb of common bytes */
 291         const BYTE* match;
 292
 293         if ((!extDict) || (matchIndex+matchLength >= dictLimit)) {
 294             match = base + matchIndex;
 295             if (match[matchLength] == ip[matchLength]) {
 296                 matchLength += ZSTD_count(ip+matchLength+1, match+matchLength+1, iLimit) +1;
 297             }
 298         } else {
 299             match = dictBase + matchIndex;
 300             matchLength += ZSTD_count_2segments(ip+matchLength, match+matchLength, iLimit, dictEnd, prefixStart);
 301             if (matchIndex+matchLength >= dictLimit)
 302                 match = base + matchIndex;   /* to prepare for next usage of match[matchLength] */
 303         }
 304
 305         if (matchLength > bestLength) {
 306             if (matchLength > matchEndIdx - matchIndex) matchEndIdx = matchIndex + (U32)matchLength;
 307             bestLength = matchLength;
 308             matches[mnum].off = ZSTD_REP_MOVE_OPT + current - matchIndex;
 309             matches[mnum].len = (U32)matchLength;
 310             mnum++;
 311             if (matchLength > ZSTD_OPT_NUM) break;
 312             if (ip+matchLength == iLimit)   /* equal : no way to know if inf or sup */
 313                 break;   /* drop, to guarantee consistency (miss a little bit of compression) */
 314         }
 315
 316         if (match[matchLength] < ip[matchLength]) {
 317             /* match is smaller than current */
 318             *smallerPtr = matchIndex;             /* update smaller idx */
 319             commonLengthSmaller = matchLength;    /* all smaller will now have at least this guaranteed common length */
 320             if (matchIndex <= btLow) { smallerPtr=&dummy32; break; }   /* beyond tree size, stop the search */
 321             smallerPtr = nextPtr+1;               /* new "smaller" => larger of match */
 322             matchIndex = nextPtr[1];              /* new matchIndex larger than previous (closer to current) */
 323         } else {
 324             /* match is larger than current */
 325             *largerPtr = matchIndex;
 326             commonLengthLarger = matchLength;
 327             if (matchIndex <= btLow) { largerPtr=&dummy32; break; }   /* beyond tree size, stop the search */
 328             largerPtr = nextPtr;
 329             matchIndex = nextPtr[0];
 330     }   }
 331
 332     *smallerPtr = *largerPtr = 0;
 333
 334 update:
 335     zc->nextToUpdate = (matchEndIdx > current + 8) ? matchEndIdx - 8 : current+1;
 336     return mnum;
 337 }
 338
 339
 340 /** Tree updater, providing best match */
 341 static U32 ZSTD_BtGetAllMatches (
 342                         ZSTD_CCtx* zc,
 343                         const BYTE* const ip, const BYTE* const iLimit,
 344                         const U32 maxNbAttempts, const U32 mls, ZSTD_match_t* matches, const U32 minMatchLen)
 345 {
 346     if (ip < zc->base + zc->nextToUpdate) return 0;   /* skipped area */
 347     ZSTD_updateTree(zc, ip, iLimit, maxNbAttempts, mls);
 348     return ZSTD_insertBtAndGetAllMatches(zc, ip, iLimit, maxNbAttempts, mls, 0, matches, minMatchLen);
 349 }
 350
 351
 352 static U32 ZSTD_BtGetAllMatches_selectMLS (
 353                         ZSTD_CCtx* zc,   /* Index table will be updated */
 354                         const BYTE* ip, const BYTE* const iHighLimit,
 355                         const U32 maxNbAttempts, const U32 matchLengthSearch, ZSTD_match_t* matches, const U32 minMatchLen)
 356 {
 357     switch(matchLengthSearch)
 358     {
 359     case 3 : return ZSTD_BtGetAllMatches(zc, ip, iHighLimit, maxNbAttempts, 3, matches, minMatchLen);
 360     default :
 361     case 4 : return ZSTD_BtGetAllMatches(zc, ip, iHighLimit, maxNbAttempts, 4, matches, minMatchLen);
 362     case 5 : return ZSTD_BtGetAllMatches(zc, ip, iHighLimit, maxNbAttempts, 5, matches, minMatchLen);
 363     case 6 : return ZSTD_BtGetAllMatches(zc, ip, iHighLimit, maxNbAttempts, 6, matches, minMatchLen);
 364     }
 365 }
 366
 367 /** Tree updater, providing best match */
 368 static U32 ZSTD_BtGetAllMatches_extDict (
 369                         ZSTD_CCtx* zc,
 370                         const BYTE* const ip, const BYTE* const iLimit,
 371                         const U32 maxNbAttempts, const U32 mls, ZSTD_match_t* matches, const U32 minMatchLen)
 372 {
 373     if (ip < zc->base + zc->nextToUpdate) return 0;   /* skipped area */
 374     ZSTD_updateTree_extDict(zc, ip, iLimit, maxNbAttempts, mls);
 375     return ZSTD_insertBtAndGetAllMatches(zc, ip, iLimit, maxNbAttempts, mls, 1, matches, minMatchLen);
 376 }
 377
 378
 379 static U32 ZSTD_BtGetAllMatches_selectMLS_extDict (
 380                         ZSTD_CCtx* zc,   /* Index table will be updated */
 381                         const BYTE* ip, const BYTE* const iHighLimit,
 382                         const U32 maxNbAttempts, const U32 matchLengthSearch, ZSTD_match_t* matches, const U32 minMatchLen)
 383 {
 384     switch(matchLengthSearch)
 385     {
 386     case 3 : return ZSTD_BtGetAllMatches_extDict(zc, ip, iHighLimit, maxNbAttempts, 3, matches, minMatchLen);
 387     default :
 388     case 4 : return ZSTD_BtGetAllMatches_extDict(zc, ip, iHighLimit, maxNbAttempts, 4, matches, minMatchLen);
 389     case 5 : return ZSTD_BtGetAllMatches_extDict(zc, ip, iHighLimit, maxNbAttempts, 5, matches, minMatchLen);
 390     case 6 : return ZSTD_BtGetAllMatches_extDict(zc, ip, iHighLimit, maxNbAttempts, 6, matches, minMatchLen);
 391     }
 392 }
 393
 394
 395 /*-*******************************
 396 *  Optimal parser
 397 *********************************/
 398 FORCE_INLINE
 399 void ZSTD_compressBlock_opt_generic(ZSTD_CCtx* ctx,
 400                                     const void* src, size_t srcSize, const int ultra)
 401 {
 402     seqStore_t* seqStorePtr = &(ctx->seqStore);
 403     const BYTE* const istart = (const BYTE*)src;
 404     const BYTE* ip = istart;
 405     const BYTE* anchor = istart;
 406     const BYTE* const iend = istart + srcSize;
 407     const BYTE* const ilimit = iend - 8;
 408     const BYTE* const base = ctx->base;
 409     const BYTE* const prefixStart = base + ctx->dictLimit;
 410
 411     const U32 maxSearches = 1U << ctx->params.cParams.searchLog;
 412     const U32 sufficient_len = ctx->params.cParams.targetLength;
 413     const U32 mls = ctx->params.cParams.searchLength;
 414     const U32 minMatch = (ctx->params.cParams.searchLength == 3) ? 3 : 4;
 415
 416     ZSTD_optimal_t* opt = seqStorePtr->priceTable;
 417     ZSTD_match_t* matches = seqStorePtr->matchTable;
 418     const BYTE* inr;
 419     U32 offset, rep[ZSTD_REP_NUM];
 420
 421     /* init */
 422     ctx->nextToUpdate3 = ctx->nextToUpdate;
 423     ZSTD_rescaleFreqs(seqStorePtr, (const BYTE*)src, srcSize);
 424     ip += (ip==prefixStart);
 425     { U32 i; for (i=0; i<ZSTD_REP_NUM; i++) rep[i]=ctx->rep[i]; }
 426
 427     /* Match Loop */
 428     while (ip < ilimit) {
 429         U32 cur, match_num, last_pos, litlen, price;
 430         U32 u, mlen, best_mlen, best_off, litLength;
 431         memset(opt, 0, sizeof(ZSTD_optimal_t));
 432         last_pos = 0;
 433         litlen = (U32)(ip - anchor);
 434
 435         /* check repCode */
 436         {   U32 i, last_i = ZSTD_REP_CHECK + (ip==anchor);
 437             for (i=(ip == anchor); i<last_i; i++) {
 438                 const S32 repCur = (i==ZSTD_REP_MOVE_OPT) ? (rep[0] - 1) : rep[i];
 439                 if ( (repCur > 0) && (repCur < (S32)(ip-prefixStart))
 440                     && (MEM_readMINMATCH(ip, minMatch) == MEM_readMINMATCH(ip - repCur, minMatch))) {
 441                     mlen = (U32)ZSTD_count(ip+minMatch, ip+minMatch-repCur, iend) + minMatch;
 442                     if (mlen > sufficient_len || mlen >= ZSTD_OPT_NUM) {
 443                         best_mlen = mlen; best_off = i; cur = 0; last_pos = 1;
 444                         goto _storeSequence;
 445                     }
 446                     best_off = i - (ip == anchor);
 447                     do {
 448                         price = ZSTD_getPrice(seqStorePtr, litlen, anchor, best_off, mlen - MINMATCH, ultra);
 449                         if (mlen > last_pos || price < opt[mlen].price)
 450                             SET_PRICE(mlen, mlen, i, litlen, price);   /* note : macro modifies last_pos */
 451                         mlen--;
 452                     } while (mlen >= minMatch);
 453         }   }   }
 454
 455         match_num = ZSTD_BtGetAllMatches_selectMLS(ctx, ip, iend, maxSearches, mls, matches, minMatch);
 456
 457         if (!last_pos && !match_num) { ip++; continue; }
 458
 459         if (match_num && (matches[match_num-1].len > sufficient_len || matches[match_num-1].len >= ZSTD_OPT_NUM)) {
 460             best_mlen = matches[match_num-1].len;
 461             best_off = matches[match_num-1].off;
 462             cur = 0;
 463             last_pos = 1;
 464             goto _storeSequence;
 465         }
 466
 467         /* set prices using matches at position = 0 */
 468         best_mlen = (last_pos) ? last_pos : minMatch;
 469         for (u = 0; u < match_num; u++) {
 470             mlen = (u>0) ? matches[u-1].len+1 : best_mlen;
 471             best_mlen = matches[u].len;
 472             while (mlen <= best_mlen) {
 473                 price = ZSTD_getPrice(seqStorePtr, litlen, anchor, matches[u].off-1, mlen - MINMATCH, ultra);
 474                 if (mlen > last_pos || price < opt[mlen].price)
 475                     SET_PRICE(mlen, mlen, matches[u].off, litlen, price);   /* note : macro modifies last_pos */
 476                 mlen++;
 477         }   }
 478
 479         if (last_pos < minMatch) { ip++; continue; }
 480
 481         /* initialize opt[0] */
 482         { U32 i ; for (i=0; i<ZSTD_REP_NUM; i++) opt[0].rep[i] = rep[i]; }
 483         opt[0].mlen = 1;
 484         opt[0].litlen = litlen;
 485
 486          /* check further positions */
 487         for (cur = 1; cur <= last_pos; cur++) {
 488            inr = ip + cur;
 489
 490            if (opt[cur-1].mlen == 1) {
 491                 litlen = opt[cur-1].litlen + 1;
 492                 if (cur > litlen) {
 493                     price = opt[cur - litlen].price + ZSTD_getLiteralPrice(seqStorePtr, litlen, inr-litlen);
 494                 } else
 495                     price = ZSTD_getLiteralPrice(seqStorePtr, litlen, anchor);
 496            } else {
 497                 litlen = 1;
 498                 price = opt[cur - 1].price + ZSTD_getLiteralPrice(seqStorePtr, litlen, inr-1);
 499            }
 500
 501            if (cur > last_pos || price <= opt[cur].price)
 502                 SET_PRICE(cur, 1, 0, litlen, price);
 503
 504            if (cur == last_pos) break;
 505
 506            if (inr > ilimit)  /* last match must start at a minimum distance of 8 from oend */
 507                continue;
 508
 509            mlen = opt[cur].mlen;
 510            if (opt[cur].off > ZSTD_REP_MOVE_OPT) {
 511                 opt[cur].rep[2] = opt[cur-mlen].rep[1];
 512                 opt[cur].rep[1] = opt[cur-mlen].rep[0];
 513                 opt[cur].rep[0] = opt[cur].off - ZSTD_REP_MOVE_OPT;
 514            } else {
 515                 opt[cur].rep[2] = (opt[cur].off > 1) ? opt[cur-mlen].rep[1] : opt[cur-mlen].rep[2];
 516                 opt[cur].rep[1] = (opt[cur].off > 0) ? opt[cur-mlen].rep[0] : opt[cur-mlen].rep[1];
 517                 opt[cur].rep[0] = ((opt[cur].off==ZSTD_REP_MOVE_OPT) && (mlen != 1)) ? (opt[cur-mlen].rep[0] - 1) : (opt[cur-mlen].rep[opt[cur].off]);
 518            }
 519
 520             best_mlen = minMatch;
 521             {   U32 i, last_i = ZSTD_REP_CHECK + (mlen != 1);
 522                 for (i=(opt[cur].mlen != 1); i<last_i; i++) {  /* check rep */
 523                     const S32 repCur = (i==ZSTD_REP_MOVE_OPT) ? (opt[cur].rep[0] - 1) : opt[cur].rep[i];
 524                     if ( (repCur > 0) && (repCur < (S32)(inr-prefixStart))
 525                        && (MEM_readMINMATCH(inr, minMatch) == MEM_readMINMATCH(inr - repCur, minMatch))) {
 526                        mlen = (U32)ZSTD_count(inr+minMatch, inr+minMatch - repCur, iend) + minMatch;
 527
 528                        if (mlen > sufficient_len || cur + mlen >= ZSTD_OPT_NUM) {
 529                             best_mlen = mlen; best_off = i; last_pos = cur + 1;
 530                             goto _storeSequence;
 531                        }
 532
 533                        best_off = i - (opt[cur].mlen != 1);
 534                        if (mlen > best_mlen) best_mlen = mlen;
 535
 536                        do {
 537                            if (opt[cur].mlen == 1) {
 538                                 litlen = opt[cur].litlen;
 539                                 if (cur > litlen) {
 540                                     price = opt[cur - litlen].price + ZSTD_getPrice(seqStorePtr, litlen, inr-litlen, best_off, mlen - MINMATCH, ultra);
 541                                 } else
 542                                     price = ZSTD_getPrice(seqStorePtr, litlen, anchor, best_off, mlen - MINMATCH, ultra);
 543                             } else {
 544                                 litlen = 0;
 545                                 price = opt[cur].price + ZSTD_getPrice(seqStorePtr, 0, NULL, best_off, mlen - MINMATCH, ultra);
 546                             }
 547
 548                             if (cur + mlen > last_pos || price <= opt[cur + mlen].price)
 549                                 SET_PRICE(cur + mlen, mlen, i, litlen, price);
 550                             mlen--;
 551                         } while (mlen >= minMatch);
 552             }   }   }
 553
 554             match_num = ZSTD_BtGetAllMatches_selectMLS(ctx, inr, iend, maxSearches, mls, matches, best_mlen);
 555
 556             if (match_num > 0 && (matches[match_num-1].len > sufficient_len || cur + matches[match_num-1].len >= ZSTD_OPT_NUM)) {
 557                 best_mlen = matches[match_num-1].len;
 558                 best_off = matches[match_num-1].off;
 559                 last_pos = cur + 1;
 560                 goto _storeSequence;
 561             }
 562
 563             /* set prices using matches at position = cur */
 564             for (u = 0; u < match_num; u++) {
 565                 mlen = (u>0) ? matches[u-1].len+1 : best_mlen;
 566                 best_mlen = matches[u].len;
 567
 568                 while (mlen <= best_mlen) {
 569                     if (opt[cur].mlen == 1) {
 570                         litlen = opt[cur].litlen;
 571                         if (cur > litlen)
 572                             price = opt[cur - litlen].price + ZSTD_getPrice(seqStorePtr, litlen, ip+cur-litlen, matches[u].off-1, mlen - MINMATCH, ultra);
 573                         else
 574                             price = ZSTD_getPrice(seqStorePtr, litlen, anchor, matches[u].off-1, mlen - MINMATCH, ultra);
 575                     } else {
 576                         litlen = 0;
 577                         price = opt[cur].price + ZSTD_getPrice(seqStorePtr, 0, NULL, matches[u].off-1, mlen - MINMATCH, ultra);
 578                     }
 579
 580                     if (cur + mlen > last_pos || (price < opt[cur + mlen].price))
 581                         SET_PRICE(cur + mlen, mlen, matches[u].off, litlen, price);
 582
 583                     mlen++;
 584         }   }   }
 585
 586         best_mlen = opt[last_pos].mlen;
 587         best_off = opt[last_pos].off;
 588         cur = last_pos - best_mlen;
 589
 590         /* store sequence */
 591 _storeSequence:   /* cur, last_pos, best_mlen, best_off have to be set */
 592         opt[0].mlen = 1;
 593
 594         while (1) {
 595             mlen = opt[cur].mlen;
 596             offset = opt[cur].off;
 597             opt[cur].mlen = best_mlen;
 598             opt[cur].off = best_off;
 599             best_mlen = mlen;
 600             best_off = offset;
 601             if (mlen > cur) break;
 602             cur -= mlen;
 603         }
 604
 605         for (u = 0; u <= last_pos;) {
 606             u += opt[u].mlen;
 607         }
 608
 609         for (cur=0; cur < last_pos; ) {
 610             mlen = opt[cur].mlen;
 611             if (mlen == 1) { ip++; cur++; continue; }
 612             offset = opt[cur].off;
 613             cur += mlen;
 614             litLength = (U32)(ip - anchor);
 615
 616             if (offset > ZSTD_REP_MOVE_OPT) {
 617                 rep[2] = rep[1];
 618                 rep[1] = rep[0];
 619                 rep[0] = offset - ZSTD_REP_MOVE_OPT;
 620                 offset--;
 621             } else {
 622                 if (offset != 0) {
 623                     best_off = (offset==ZSTD_REP_MOVE_OPT) ? (rep[0] - 1) : (rep[offset]);
 624                     if (offset != 1) rep[2] = rep[1];
 625                     rep[1] = rep[0];
 626                     rep[0] = best_off;
 627                 }
 628                 if (litLength==0) offset--;
 629             }
 630
 631             ZSTD_updatePrice(seqStorePtr, litLength, anchor, offset, mlen-MINMATCH);
 632             ZSTD_storeSeq(seqStorePtr, litLength, anchor, offset, mlen-MINMATCH);
 633             anchor = ip = ip + mlen;
 634     }    }   /* for (cur=0; cur < last_pos; ) */
 635
 636     /* Save reps for next block */
 637     { int i; for (i=0; i<ZSTD_REP_NUM; i++) ctx->savedRep[i] = rep[i]; }
 638
 639     /* Last Literals */
 640     {   size_t const lastLLSize = iend - anchor;
 641         memcpy(seqStorePtr->lit, anchor, lastLLSize);
 642         seqStorePtr->lit += lastLLSize;
 643     }
 644 }
 645
 646
 647 FORCE_INLINE
 648 void ZSTD_compressBlock_opt_extDict_generic(ZSTD_CCtx* ctx,
 649                                      const void* src, size_t srcSize, const int ultra)
 650 {
 651     seqStore_t* seqStorePtr = &(ctx->seqStore);
 652     const BYTE* const istart = (const BYTE*)src;
 653     const BYTE* ip = istart;
 654     const BYTE* anchor = istart;
 655     const BYTE* const iend = istart + srcSize;
 656     const BYTE* const ilimit = iend - 8;
 657     const BYTE* const base = ctx->base;
 658     const U32 lowestIndex = ctx->lowLimit;
 659     const U32 dictLimit = ctx->dictLimit;
 660     const BYTE* const prefixStart = base + dictLimit;
 661     const BYTE* const dictBase = ctx->dictBase;
 662     const BYTE* const dictEnd  = dictBase + dictLimit;
 663
 664     const U32 maxSearches = 1U << ctx->params.cParams.searchLog;
 665     const U32 sufficient_len = ctx->params.cParams.targetLength;
 666     const U32 mls = ctx->params.cParams.searchLength;
 667     const U32 minMatch = (ctx->params.cParams.searchLength == 3) ? 3 : 4;
 668
 669     ZSTD_optimal_t* opt = seqStorePtr->priceTable;
 670     ZSTD_match_t* matches = seqStorePtr->matchTable;
 671     const BYTE* inr;
 672
 673     /* init */
 674     U32 offset, rep[ZSTD_REP_NUM];
 675     { U32 i; for (i=0; i<ZSTD_REP_NUM; i++) rep[i]=ctx->rep[i]; }
 676
 677     ctx->nextToUpdate3 = ctx->nextToUpdate;
 678     ZSTD_rescaleFreqs(seqStorePtr, (const BYTE*)src, srcSize);
 679     ip += (ip==prefixStart);
 680
 681     /* Match Loop */
 682     while (ip < ilimit) {
 683         U32 cur, match_num, last_pos, litlen, price;
 684         U32 u, mlen, best_mlen, best_off, litLength;
 685         U32 current = (U32)(ip-base);
 686         memset(opt, 0, sizeof(ZSTD_optimal_t));
 687         last_pos = 0;
 688         opt[0].litlen = (U32)(ip - anchor);
 689
 690         /* check repCode */
 691         {   U32 i, last_i = ZSTD_REP_CHECK + (ip==anchor);
 692             for (i = (ip==anchor); i<last_i; i++) {
 693                 const S32 repCur = (i==ZSTD_REP_MOVE_OPT) ? (rep[0] - 1) : rep[i];
 694                 const U32 repIndex = (U32)(current - repCur);
 695                 const BYTE* const repBase = repIndex < dictLimit ? dictBase : base;
 696                 const BYTE* const repMatch = repBase + repIndex;
 697                 if ( (repCur > 0 && repCur <= (S32)current)
 698                    && (((U32)((dictLimit-1) - repIndex) >= 3) & (repIndex>lowestIndex))  /* intentional overflow */
 699                    && (MEM_readMINMATCH(ip, minMatch) == MEM_readMINMATCH(repMatch, minMatch)) ) {
 700                     /* repcode detected we should take it */
 701                     const BYTE* const repEnd = repIndex < dictLimit ? dictEnd : iend;
 702                     mlen = (U32)ZSTD_count_2segments(ip+minMatch, repMatch+minMatch, iend, repEnd, prefixStart) + minMatch;
 703
 704                     if (mlen > sufficient_len || mlen >= ZSTD_OPT_NUM) {
 705                         best_mlen = mlen; best_off = i; cur = 0; last_pos = 1;
 706                         goto _storeSequence;
 707                     }
 708
 709                     best_off = i - (ip==anchor);
 710                     litlen = opt[0].litlen;
 711                     do {
 712                         price = ZSTD_getPrice(seqStorePtr, litlen, anchor, best_off, mlen - MINMATCH, ultra);
 713                         if (mlen > last_pos || price < opt[mlen].price)
 714                             SET_PRICE(mlen, mlen, i, litlen, price);   /* note : macro modifies last_pos */
 715                         mlen--;
 716                     } while (mlen >= minMatch);
 717         }   }   }
 718
 719         match_num = ZSTD_BtGetAllMatches_selectMLS_extDict(ctx, ip, iend, maxSearches, mls, matches, minMatch);  /* first search (depth 0) */
 720
 721         if (!last_pos && !match_num) { ip++; continue; }
 722
 723         { U32 i; for (i=0; i<ZSTD_REP_NUM; i++) opt[0].rep[i] = rep[i]; }
 724         opt[0].mlen = 1;
 725
 726         if (match_num && (matches[match_num-1].len > sufficient_len || matches[match_num-1].len >= ZSTD_OPT_NUM)) {
 727             best_mlen = matches[match_num-1].len;
 728             best_off = matches[match_num-1].off;
 729             cur = 0;
 730             last_pos = 1;
 731             goto _storeSequence;
 732         }
 733
 734         best_mlen = (last_pos) ? last_pos : minMatch;
 735
 736         /* set prices using matches at position = 0 */
 737         for (u = 0; u < match_num; u++) {
 738             mlen = (u>0) ? matches[u-1].len+1 : best_mlen;
 739             best_mlen = matches[u].len;
 740             litlen = opt[0].litlen;
 741             while (mlen <= best_mlen) {
 742                 price = ZSTD_getPrice(seqStorePtr, litlen, anchor, matches[u].off-1, mlen - MINMATCH, ultra);
 743                 if (mlen > last_pos || price < opt[mlen].price)
 744                     SET_PRICE(mlen, mlen, matches[u].off, litlen, price);
 745                 mlen++;
 746         }   }
 747
 748         if (last_pos < minMatch) {
 749             ip++; continue;
 750         }
 751
 752         /* check further positions */
 753         for (cur = 1; cur <= last_pos; cur++) {
 754             inr = ip + cur;
 755
 756             if (opt[cur-1].mlen == 1) {
 757                 litlen = opt[cur-1].litlen + 1;
 758                 if (cur > litlen) {
 759                     price = opt[cur - litlen].price + ZSTD_getLiteralPrice(seqStorePtr, litlen, inr-litlen);
 760                 } else
 761                     price = ZSTD_getLiteralPrice(seqStorePtr, litlen, anchor);
 762             } else {
 763                 litlen = 1;
 764                 price = opt[cur - 1].price + ZSTD_getLiteralPrice(seqStorePtr, litlen, inr-1);
 765             }
 766
 767             if (cur > last_pos || price <= opt[cur].price)
 768                 SET_PRICE(cur, 1, 0, litlen, price);
 769
 770             if (cur == last_pos) break;
 771
 772             if (inr > ilimit)  /* last match must start at a minimum distance of 8 from oend */
 773                 continue;
 774
 775             mlen = opt[cur].mlen;
 776             if (opt[cur].off > ZSTD_REP_MOVE_OPT) {
 777                 opt[cur].rep[2] = opt[cur-mlen].rep[1];
 778                 opt[cur].rep[1] = opt[cur-mlen].rep[0];
 779                 opt[cur].rep[0] = opt[cur].off - ZSTD_REP_MOVE_OPT;
 780             } else {
 781                 opt[cur].rep[2] = (opt[cur].off > 1) ? opt[cur-mlen].rep[1] : opt[cur-mlen].rep[2];
 782                 opt[cur].rep[1] = (opt[cur].off > 0) ? opt[cur-mlen].rep[0] : opt[cur-mlen].rep[1];
 783                 opt[cur].rep[0] = ((opt[cur].off==ZSTD_REP_MOVE_OPT) && (mlen != 1)) ? (opt[cur-mlen].rep[0] - 1) : (opt[cur-mlen].rep[opt[cur].off]);
 784             }
 785
 786             best_mlen = minMatch;
 787             {   U32 i, last_i = ZSTD_REP_CHECK + (mlen != 1);
 788                 for (i = (mlen != 1); i<last_i; i++) {
 789                     const S32 repCur = (i==ZSTD_REP_MOVE_OPT) ? (opt[cur].rep[0] - 1) : opt[cur].rep[i];
 790                     const U32 repIndex = (U32)(current+cur - repCur);
 791                     const BYTE* const repBase = repIndex < dictLimit ? dictBase : base;
 792                     const BYTE* const repMatch = repBase + repIndex;
 793                     if ( (repCur > 0 && repCur <= (S32)(current+cur))
 794                       && (((U32)((dictLimit-1) - repIndex) >= 3) & (repIndex>lowestIndex))  /* intentional overflow */
 795                       && (MEM_readMINMATCH(inr, minMatch) == MEM_readMINMATCH(repMatch, minMatch)) ) {
 796                         /* repcode detected */
 797                         const BYTE* const repEnd = repIndex < dictLimit ? dictEnd : iend;
 798                         mlen = (U32)ZSTD_count_2segments(inr+minMatch, repMatch+minMatch, iend, repEnd, prefixStart) + minMatch;
 799
 800                         if (mlen > sufficient_len || cur + mlen >= ZSTD_OPT_NUM) {
 801                             best_mlen = mlen; best_off = i; last_pos = cur + 1;
 802                             goto _storeSequence;
 803                         }
 804
 805                         best_off = i - (opt[cur].mlen != 1);
 806                         if (mlen > best_mlen) best_mlen = mlen;
 807
 808                         do {
 809                             if (opt[cur].mlen == 1) {
 810                                 litlen = opt[cur].litlen;
 811                                 if (cur > litlen) {
 812                                     price = opt[cur - litlen].price + ZSTD_getPrice(seqStorePtr, litlen, inr-litlen, best_off, mlen - MINMATCH, ultra);
 813                                 } else
 814                                     price = ZSTD_getPrice(seqStorePtr, litlen, anchor, best_off, mlen - MINMATCH, ultra);
 815                             } else {
 816                                 litlen = 0;
 817                                 price = opt[cur].price + ZSTD_getPrice(seqStorePtr, 0, NULL, best_off, mlen - MINMATCH, ultra);
 818                             }
 819
 820                             if (cur + mlen > last_pos || price <= opt[cur + mlen].price)
 821                                 SET_PRICE(cur + mlen, mlen, i, litlen, price);
 822                             mlen--;
 823                         } while (mlen >= minMatch);
 824             }   }   }
 825
 826             match_num = ZSTD_BtGetAllMatches_selectMLS_extDict(ctx, inr, iend, maxSearches, mls, matches, minMatch);
 827
 828             if (match_num > 0 && matches[match_num-1].len > sufficient_len) {
 829                 best_mlen = matches[match_num-1].len;
 830                 best_off = matches[match_num-1].off;
 831                 last_pos = cur + 1;
 832                 goto _storeSequence;
 833             }
 834
 835             /* set prices using matches at position = cur */
 836             for (u = 0; u < match_num; u++) {
 837                 mlen = (u>0) ? matches[u-1].len+1 : best_mlen;
 838                 best_mlen = (cur + matches[u].len < ZSTD_OPT_NUM) ? matches[u].len : ZSTD_OPT_NUM - cur;
 839
 840                 while (mlen <= best_mlen) {
 841                     if (opt[cur].mlen == 1) {
 842                         litlen = opt[cur].litlen;
 843                         if (cur > litlen)
 844                             price = opt[cur - litlen].price + ZSTD_getPrice(seqStorePtr, litlen, ip+cur-litlen, matches[u].off-1, mlen - MINMATCH, ultra);
 845                         else
 846                             price = ZSTD_getPrice(seqStorePtr, litlen, anchor, matches[u].off-1, mlen - MINMATCH, ultra);
 847                     } else {
 848                         litlen = 0;
 849                         price = opt[cur].price + ZSTD_getPrice(seqStorePtr, 0, NULL, matches[u].off-1, mlen - MINMATCH, ultra);
 850                     }
 851
 852                     if (cur + mlen > last_pos || (price < opt[cur + mlen].price))
 853                         SET_PRICE(cur + mlen, mlen, matches[u].off, litlen, price);
 854
 855                     mlen++;
 856         }   }   }   /* for (cur = 1; cur <= last_pos; cur++) */
 857
 858         best_mlen = opt[last_pos].mlen;
 859         best_off = opt[last_pos].off;
 860         cur = last_pos - best_mlen;
 861
 862         /* store sequence */
 863 _storeSequence:   /* cur, last_pos, best_mlen, best_off have to be set */
 864         opt[0].mlen = 1;
 865
 866         while (1) {
 867             mlen = opt[cur].mlen;
 868             offset = opt[cur].off;
 869             opt[cur].mlen = best_mlen;
 870             opt[cur].off = best_off;
 871             best_mlen = mlen;
 872             best_off = offset;
 873             if (mlen > cur) break;
 874             cur -= mlen;
 875         }
 876
 877         for (u = 0; u <= last_pos; ) {
 878             u += opt[u].mlen;
 879         }
 880
 881         for (cur=0; cur < last_pos; ) {
 882             mlen = opt[cur].mlen;
 883             if (mlen == 1) { ip++; cur++; continue; }
 884             offset = opt[cur].off;
 885             cur += mlen;
 886             litLength = (U32)(ip - anchor);
 887
 888             if (offset > ZSTD_REP_MOVE_OPT) {
 889                 rep[2] = rep[1];
 890                 rep[1] = rep[0];
 891                 rep[0] = offset - ZSTD_REP_MOVE_OPT;
 892                 offset--;
 893             } else {
 894                 if (offset != 0) {
 895                     best_off = (offset==ZSTD_REP_MOVE_OPT) ? (rep[0] - 1) : (rep[offset]);
 896                     if (offset != 1) rep[2] = rep[1];
 897                     rep[1] = rep[0];
 898                     rep[0] = best_off;
 899                 }
 900
 901                 if (litLength==0) offset--;
 902             }
 903
 904             ZSTD_updatePrice(seqStorePtr, litLength, anchor, offset, mlen-MINMATCH);
 905             ZSTD_storeSeq(seqStorePtr, litLength, anchor, offset, mlen-MINMATCH);
 906             anchor = ip = ip + mlen;
 907     }    }   /* for (cur=0; cur < last_pos; ) */
 908
 909     /* Save reps for next block */
 910     { int i; for (i=0; i<ZSTD_REP_NUM; i++) ctx->savedRep[i] = rep[i]; }
 911
 912     /* Last Literals */
 913     {   size_t lastLLSize = iend - anchor;
 914         memcpy(seqStorePtr->lit, anchor, lastLLSize);
 915         seqStorePtr->lit += lastLLSize;
 916     }
 917 }
 918
 919 #endif  /* ZSTD_OPT_H_91842398743 */