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_FREQ_DIV   5

    19 #define ZSTD_MAX_PRICE  (1<<30)

    20 

    21 /*-*************************************

    22 *  Price functions for optimal parser

    23 ***************************************/

    24 FORCE_INLINE void ZSTD_setLog2Prices(seqStore_t* ssPtr)

    25 {

    26     ssPtr->log2matchLengthSum = ZSTD_highbit32(ssPtr->matchLengthSum+1);

    27     ssPtr->log2litLengthSum = ZSTD_highbit32(ssPtr->litLengthSum+1);

    28     ssPtr->log2litSum = ZSTD_highbit32(ssPtr->litSum+1);

    29     ssPtr->log2offCodeSum = ZSTD_highbit32(ssPtr->offCodeSum+1);

    30     ssPtr->factor = 1 + ((ssPtr->litSum>>5) / ssPtr->litLengthSum) + ((ssPtr->litSum<<1) / (ssPtr->litSum + ssPtr->matchSum));

    31 }

    32 

    33 

    34 MEM_STATIC void ZSTD_rescaleFreqs(seqStore_t* ssPtr)

    35 {

    36     unsigned u;

    37 

    38     ssPtr->cachedLiterals = NULL;

    39     ssPtr->cachedPrice = ssPtr->cachedLitLength = 0;

    40 

    41     if (ssPtr->litLengthSum == 0) {

    42         ssPtr->litSum = (2<<Litbits);

    43         ssPtr->litLengthSum = MaxLL+1;

    44         ssPtr->matchLengthSum = MaxML+1;

    45         ssPtr->offCodeSum = (MaxOff+1);

    46         ssPtr->matchSum = (2<<Litbits);

    47 

    48         for (u=0; u<=MaxLit; u++)

    49             ssPtr->litFreq[u] = 2;

    50         for (u=0; u<=MaxLL; u++)

    51             ssPtr->litLengthFreq[u] = 1;

    52         for (u=0; u<=MaxML; u++)

    53             ssPtr->matchLengthFreq[u] = 1;

    54         for (u=0; u<=MaxOff; u++)

    55             ssPtr->offCodeFreq[u] = 1;

    56     } else {

    57         ssPtr->matchLengthSum = 0;

    58         ssPtr->litLengthSum = 0;

    59         ssPtr->offCodeSum = 0;

    60         ssPtr->matchSum = 0;

    61         ssPtr->litSum = 0;

    62 

    63         for (u=0; u<=MaxLit; u++) {

    64             ssPtr->litFreq[u] = 1 + (ssPtr->litFreq[u]>>ZSTD_FREQ_DIV);

    65             ssPtr->litSum += ssPtr->litFreq[u];

    66         }

    67         for (u=0; u<=MaxLL; u++) {

    68             ssPtr->litLengthFreq[u] = 1 + (ssPtr->litLengthFreq[u]>>ZSTD_FREQ_DIV);

    69             ssPtr->litLengthSum += ssPtr->litLengthFreq[u];

    70         }

    71         for (u=0; u<=MaxML; u++) {

    72             ssPtr->matchLengthFreq[u] = 1 + (ssPtr->matchLengthFreq[u]>>ZSTD_FREQ_DIV);

    73             ssPtr->matchLengthSum += ssPtr->matchLengthFreq[u];

    74             ssPtr->matchSum += ssPtr->matchLengthFreq[u] * (u + 3);

    75         }

    76         for (u=0; u<=MaxOff; u++) {

    77             ssPtr->offCodeFreq[u] = 1 + (ssPtr->offCodeFreq[u]>>ZSTD_FREQ_DIV);

    78             ssPtr->offCodeSum += ssPtr->offCodeFreq[u];

    79         }

    80     }

    81 

    82     ZSTD_setLog2Prices(ssPtr);

    83 }

    84 

    85 

    86 FORCE_INLINE U32 ZSTD_getLiteralPrice(seqStore_t* ssPtr, U32 litLength, const BYTE* literals)

    87 {

    88     U32 price, u;

    89 

    90     if (litLength == 0)

    91         return ssPtr->log2litLengthSum - ZSTD_highbit32(ssPtr->litLengthFreq[0]+1);

    92 

    93     /* literals */

    94     if (ssPtr->cachedLiterals == literals) {

    95         U32 const additional = litLength - ssPtr->cachedLitLength;

    96         const BYTE* literals2 = ssPtr->cachedLiterals + ssPtr->cachedLitLength;

    97         price = ssPtr->cachedPrice + additional * ssPtr->log2litSum;

    98         for (u=0; u < additional; u++)

    99             price -= ZSTD_highbit32(ssPtr->litFreq[literals2[u]]+1);

   100         ssPtr->cachedPrice = price;

   101         ssPtr->cachedLitLength = litLength;

   102     } else {

   103         price = litLength * ssPtr->log2litSum;

   104         for (u=0; u < litLength; u++)

   105             price -= ZSTD_highbit32(ssPtr->litFreq[literals[u]]+1);

   106 

   107         if (litLength >= 12) {

   108             ssPtr->cachedLiterals = literals;

   109             ssPtr->cachedPrice = price;

   110             ssPtr->cachedLitLength = litLength;

   111         }

   112     }

   113 

   114     /* literal Length */

   115     {   const BYTE LL_deltaCode = 19;

   116         const BYTE llCode = (litLength>63) ? (BYTE)ZSTD_highbit32(litLength) + LL_deltaCode : LL_Code[litLength];

   117         price += LL_bits[llCode] + ssPtr->log2litLengthSum - ZSTD_highbit32(ssPtr->litLengthFreq[llCode]+1);

   118     }

   119 

   120     return price;

   121 }

   122 

   123 

   124 FORCE_INLINE U32 ZSTD_getPrice(seqStore_t* seqStorePtr, U32 litLength, const BYTE* literals, U32 offset, U32 matchLength, const int ultra)

   125 {

   126     /* offset */

   127     BYTE const offCode = (BYTE)ZSTD_highbit32(offset+1);

   128     U32 price = offCode + seqStorePtr->log2offCodeSum - ZSTD_highbit32(seqStorePtr->offCodeFreq[offCode]+1);

   129 

   130     if (!ultra && offCode >= 20) price += (offCode-19)*2;

   131 

   132     /* match Length */

   133     {   const BYTE ML_deltaCode = 36;

   134         const BYTE mlCode = (matchLength>127) ? (BYTE)ZSTD_highbit32(matchLength) + ML_deltaCode : ML_Code[matchLength];

   135         price += ML_bits[mlCode] + seqStorePtr->log2matchLengthSum - ZSTD_highbit32(seqStorePtr->matchLengthFreq[mlCode]+1);

   136     }

   137 

   138     return price + ZSTD_getLiteralPrice(seqStorePtr, litLength, literals) + seqStorePtr->factor;

   139 }

   140 

   141 

   142 MEM_STATIC void ZSTD_updatePrice(seqStore_t* seqStorePtr, U32 litLength, const BYTE* literals, U32 offset, U32 matchLength)

   143 {

   144     U32 u;

   145 

   146     /* literals */

   147     seqStorePtr->litSum += litLength;

   148     for (u=0; u < litLength; u++)

   149         seqStorePtr->litFreq[literals[u]]++;

   150 

   151     /* literal Length */

   152     {   const BYTE LL_deltaCode = 19;

   153         const BYTE llCode = (litLength>63) ? (BYTE)ZSTD_highbit32(litLength) + LL_deltaCode : LL_Code[litLength];

   154         seqStorePtr->litLengthFreq[llCode]++;

   155         seqStorePtr->litLengthSum++;

   156     }

   157 

   158     /* match offset */

   159 	{   BYTE const offCode = (BYTE)ZSTD_highbit32(offset+1);

   160 		seqStorePtr->offCodeSum++;

   161 		seqStorePtr->offCodeFreq[offCode]++;

   162 	}

   163 

   164     /* match Length */

   165     {   const BYTE ML_deltaCode = 36;

   166         const BYTE mlCode = (matchLength>127) ? (BYTE)ZSTD_highbit32(matchLength) + ML_deltaCode : ML_Code[matchLength];

   167         seqStorePtr->matchLengthFreq[mlCode]++;

   168         seqStorePtr->matchLengthSum++;

   169     }

   170 

   171     ZSTD_setLog2Prices(seqStorePtr);

   172 }

   173 

   174 

   175 #define SET_PRICE(pos, mlen_, offset_, litlen_, price_)   \

   176     {                                                 \

   177         while (last_pos < pos)  { opt[last_pos+1].price = ZSTD_MAX_PRICE; last_pos++; } \

   178         opt[pos].mlen = mlen_;                         \

   179         opt[pos].off = offset_;                        \

   180         opt[pos].litlen = litlen_;                     \

   181         opt[pos].price = price_;                       \

   182     }

   183 

   184 

   185 

   186 /* Update hashTable3 up to ip (excluded)

   187    Assumption : always within prefix (ie. not within extDict) */

   188 FORCE_INLINE

   189 U32 ZSTD_insertAndFindFirstIndexHash3 (ZSTD_CCtx* zc, const BYTE* ip)

   190 {

   191     U32* const hashTable3  = zc->hashTable3;

   192     U32 const hashLog3  = zc->hashLog3;

   193     const BYTE* const base = zc->base;

   194     U32 idx = zc->nextToUpdate3;

   195     const U32 target = zc->nextToUpdate3 = (U32)(ip - base);

   196     const size_t hash3 = ZSTD_hash3Ptr(ip, hashLog3);

   197 

   198     while(idx < target) {

   199         hashTable3[ZSTD_hash3Ptr(base+idx, hashLog3)] = idx;

   200         idx++;

   201     }

   202 

   203     return hashTable3[hash3];

   204 }

   205 

   206 

   207 /*-*************************************

   208 *  Binary Tree search

   209 ***************************************/

   210 static U32 ZSTD_insertBtAndGetAllMatches (

   211                         ZSTD_CCtx* zc,

   212                         const BYTE* const ip, const BYTE* const iLimit,

   213                         U32 nbCompares, const U32 mls,

   214                         U32 extDict, ZSTD_match_t* matches, const U32 minMatchLen)

   215 {

   216     const BYTE* const base = zc->base;

   217     const U32 current = (U32)(ip-base);

   218     const U32 hashLog = zc->params.cParams.hashLog;

   219     const size_t h  = ZSTD_hashPtr(ip, hashLog, mls);

   220     U32* const hashTable = zc->hashTable;

   221     U32 matchIndex  = hashTable[h];

   222     U32* const bt   = zc->chainTable;

   223     const U32 btLog = zc->params.cParams.chainLog - 1;

   224     const U32 btMask= (1U << btLog) - 1;

   225     size_t commonLengthSmaller=0, commonLengthLarger=0;

   226     const BYTE* const dictBase = zc->dictBase;

   227     const U32 dictLimit = zc->dictLimit;

   228     const BYTE* const dictEnd = dictBase + dictLimit;

   229     const BYTE* const prefixStart = base + dictLimit;

   230     const U32 btLow = btMask >= current ? 0 : current - btMask;

   231     const U32 windowLow = zc->lowLimit;

   232     U32* smallerPtr = bt + 2*(current&btMask);

   233     U32* largerPtr  = bt + 2*(current&btMask) + 1;

   234     U32 matchEndIdx = current+8;

   235     U32 dummy32;   /* to be nullified at the end */

   236     U32 mnum = 0;

   237 

   238     const U32 minMatch = (mls == 3) ? 3 : 4;

   239     size_t bestLength = minMatchLen-1;

   240 

   241     if (minMatch == 3) { /* HC3 match finder */

   242         U32 const matchIndex3 = ZSTD_insertAndFindFirstIndexHash3 (zc, ip);

   243         if (matchIndex3>windowLow && (current - matchIndex3 < (1<<18))) {

   244             const BYTE* match;

   245             size_t currentMl=0;

   246             if ((!extDict) || matchIndex3 >= dictLimit) {

   247                 match = base + matchIndex3;

   248                 if (match[bestLength] == ip[bestLength]) currentMl = ZSTD_count(ip, match, iLimit);

   249             } else {

   250                 match = dictBase + matchIndex3;

   251                 if (MEM_readMINMATCH(match, MINMATCH) == MEM_readMINMATCH(ip, MINMATCH))    /* assumption : matchIndex3 <= dictLimit-4 (by table construction) */

   252                     currentMl = ZSTD_count_2segments(ip+MINMATCH, match+MINMATCH, iLimit, dictEnd, prefixStart) + MINMATCH;

   253             }

   254 

   255             /* save best solution */

   256             if (currentMl > bestLength) {

   257                 bestLength = currentMl;

   258                 matches[mnum].off = ZSTD_REP_MOVE_OPT + current - matchIndex3;

   259                 matches[mnum].len = (U32)currentMl;

   260                 mnum++;

   261                 if (currentMl > ZSTD_OPT_NUM) goto update;

   262                 if (ip+currentMl == iLimit) goto update; /* best possible, and avoid read overflow*/

   263             }

   264         }

   265     }

   266 

   267     hashTable[h] = current;   /* Update Hash Table */

   268 

   269     while (nbCompares-- && (matchIndex > windowLow)) {

   270         U32* nextPtr = bt + 2*(matchIndex & btMask);

   271         size_t matchLength = MIN(commonLengthSmaller, commonLengthLarger);   /* guaranteed minimum nb of common bytes */

   272         const BYTE* match;

   273 

   274         if ((!extDict) || (matchIndex+matchLength >= dictLimit)) {

   275             match = base + matchIndex;

   276             if (match[matchLength] == ip[matchLength]) {

   277                 matchLength += ZSTD_count(ip+matchLength+1, match+matchLength+1, iLimit) +1;

   278             }

   279         } else {

   280             match = dictBase + matchIndex;

   281             matchLength += ZSTD_count_2segments(ip+matchLength, match+matchLength, iLimit, dictEnd, prefixStart);

   282             if (matchIndex+matchLength >= dictLimit)

   283                 match = base + matchIndex;   /* to prepare for next usage of match[matchLength] */

   284         }

   285 

   286         if (matchLength > bestLength) {

   287             if (matchLength > matchEndIdx - matchIndex) matchEndIdx = matchIndex + (U32)matchLength;

   288             bestLength = matchLength;

   289             matches[mnum].off = ZSTD_REP_MOVE_OPT + current - matchIndex;

   290             matches[mnum].len = (U32)matchLength;

   291             mnum++;

   292             if (matchLength > ZSTD_OPT_NUM) break;

   293             if (ip+matchLength == iLimit)   /* equal : no way to know if inf or sup */

   294                 break;   /* drop, to guarantee consistency (miss a little bit of compression) */

   295         }

   296 

   297         if (match[matchLength] < ip[matchLength]) {

   298             /* match is smaller than current */

   299             *smallerPtr = matchIndex;             /* update smaller idx */

   300             commonLengthSmaller = matchLength;    /* all smaller will now have at least this guaranteed common length */

   301             if (matchIndex <= btLow) { smallerPtr=&dummy32; break; }   /* beyond tree size, stop the search */

   302             smallerPtr = nextPtr+1;               /* new "smaller" => larger of match */

   303             matchIndex = nextPtr[1];              /* new matchIndex larger than previous (closer to current) */

   304         } else {

   305             /* match is larger than current */

   306             *largerPtr = matchIndex;

   307             commonLengthLarger = matchLength;

   308             if (matchIndex <= btLow) { largerPtr=&dummy32; break; }   /* beyond tree size, stop the search */

   309             largerPtr = nextPtr;

   310             matchIndex = nextPtr[0];

   311     }   }

   312 

   313     *smallerPtr = *largerPtr = 0;

   314 

   315 update:

   316     zc->nextToUpdate = (matchEndIdx > current + 8) ? matchEndIdx - 8 : current+1;

   317     return mnum;

   318 }

   319 

   320 

   321 /** Tree updater, providing best match */

   322 static U32 ZSTD_BtGetAllMatches (

   323                         ZSTD_CCtx* zc,

   324                         const BYTE* const ip, const BYTE* const iLimit,

   325                         const U32 maxNbAttempts, const U32 mls, ZSTD_match_t* matches, const U32 minMatchLen)

   326 {

   327     if (ip < zc->base + zc->nextToUpdate) return 0;   /* skipped area */

   328     ZSTD_updateTree(zc, ip, iLimit, maxNbAttempts, mls);

   329     return ZSTD_insertBtAndGetAllMatches(zc, ip, iLimit, maxNbAttempts, mls, 0, matches, minMatchLen);

   330 }

   331 

   332 

   333 static U32 ZSTD_BtGetAllMatches_selectMLS (

   334                         ZSTD_CCtx* zc,   /* Index table will be updated */

   335                         const BYTE* ip, const BYTE* const iHighLimit,

   336                         const U32 maxNbAttempts, const U32 matchLengthSearch, ZSTD_match_t* matches, const U32 minMatchLen)

   337 {

   338     switch(matchLengthSearch)

   339     {

   340     case 3 : return ZSTD_BtGetAllMatches(zc, ip, iHighLimit, maxNbAttempts, 3, matches, minMatchLen);

   341     default :

   342     case 4 : return ZSTD_BtGetAllMatches(zc, ip, iHighLimit, maxNbAttempts, 4, matches, minMatchLen);

   343     case 5 : return ZSTD_BtGetAllMatches(zc, ip, iHighLimit, maxNbAttempts, 5, matches, minMatchLen);

   344     case 6 : return ZSTD_BtGetAllMatches(zc, ip, iHighLimit, maxNbAttempts, 6, matches, minMatchLen);

   345     }

   346 }

   347 

   348 /** Tree updater, providing best match */

   349 static U32 ZSTD_BtGetAllMatches_extDict (

   350                         ZSTD_CCtx* zc,

   351                         const BYTE* const ip, const BYTE* const iLimit,

   352                         const U32 maxNbAttempts, const U32 mls, ZSTD_match_t* matches, const U32 minMatchLen)

   353 {

   354     if (ip < zc->base + zc->nextToUpdate) return 0;   /* skipped area */

   355     ZSTD_updateTree_extDict(zc, ip, iLimit, maxNbAttempts, mls);

   356     return ZSTD_insertBtAndGetAllMatches(zc, ip, iLimit, maxNbAttempts, mls, 1, matches, minMatchLen);

   357 }

   358 

   359 

   360 static U32 ZSTD_BtGetAllMatches_selectMLS_extDict (

   361                         ZSTD_CCtx* zc,   /* Index table will be updated */

   362                         const BYTE* ip, const BYTE* const iHighLimit,

   363                         const U32 maxNbAttempts, const U32 matchLengthSearch, ZSTD_match_t* matches, const U32 minMatchLen)

   364 {

   365     switch(matchLengthSearch)

   366     {

   367     case 3 : return ZSTD_BtGetAllMatches_extDict(zc, ip, iHighLimit, maxNbAttempts, 3, matches, minMatchLen);

   368     default :

   369     case 4 : return ZSTD_BtGetAllMatches_extDict(zc, ip, iHighLimit, maxNbAttempts, 4, matches, minMatchLen);

   370     case 5 : return ZSTD_BtGetAllMatches_extDict(zc, ip, iHighLimit, maxNbAttempts, 5, matches, minMatchLen);

   371     case 6 : return ZSTD_BtGetAllMatches_extDict(zc, ip, iHighLimit, maxNbAttempts, 6, matches, minMatchLen);

   372     }

   373 }

   374 

   375 

   376 /*-*******************************

   377 *  Optimal parser

   378 *********************************/

   379 FORCE_INLINE

   380 void ZSTD_compressBlock_opt_generic(ZSTD_CCtx* ctx,

   381                                     const void* src, size_t srcSize, const int ultra)

   382 {

   383     seqStore_t* seqStorePtr = &(ctx->seqStore);

   384     const BYTE* const istart = (const BYTE*)src;

   385     const BYTE* ip = istart;

   386     const BYTE* anchor = istart;

   387     const BYTE* const iend = istart + srcSize;

   388     const BYTE* const ilimit = iend - 8;

   389     const BYTE* const base = ctx->base;

   390     const BYTE* const prefixStart = base + ctx->dictLimit;

   391 

   392     const U32 maxSearches = 1U << ctx->params.cParams.searchLog;

   393     const U32 sufficient_len = ctx->params.cParams.targetLength;

   394     const U32 mls = ctx->params.cParams.searchLength;

   395     const U32 minMatch = (ctx->params.cParams.searchLength == 3) ? 3 : 4;

   396 

   397     ZSTD_optimal_t* opt = seqStorePtr->priceTable;

   398     ZSTD_match_t* matches = seqStorePtr->matchTable;

   399     const BYTE* inr;

   400     U32 offset, rep[ZSTD_REP_NUM];

   401 

   402     /* init */

   403     ctx->nextToUpdate3 = ctx->nextToUpdate;

   404     ZSTD_rescaleFreqs(seqStorePtr);

   405     ip += (ip==prefixStart);

   406     { U32 i; for (i=0; i<ZSTD_REP_NUM; i++) rep[i]=ctx->rep[i]; }

   407 

   408     /* Match Loop */

   409     while (ip < ilimit) {

   410         U32 cur, match_num, last_pos, litlen, price;

   411         U32 u, mlen, best_mlen, best_off, litLength;

   412         memset(opt, 0, sizeof(ZSTD_optimal_t));

   413         last_pos = 0;

   414         litlen = (U32)(ip - anchor);

   415 

   416         /* check repCode */

   417         {   U32 i, last_i = ZSTD_REP_CHECK + (ip==anchor);

   418             for (i=(ip == anchor); i<last_i; i++) {

   419                 const S32 repCur = ((i==ZSTD_REP_MOVE_OPT) && (ip==anchor)) ? (rep[0] - 1) : rep[i];

   420                 if ( (repCur > 0) && (repCur < (S32)(ip-prefixStart))

   421                     && (MEM_readMINMATCH(ip, minMatch) == MEM_readMINMATCH(ip - repCur, minMatch))) {

   422                     mlen = (U32)ZSTD_count(ip+minMatch, ip+minMatch-repCur, iend) + minMatch;

   423                     if (mlen > sufficient_len || mlen >= ZSTD_OPT_NUM) {

   424                         best_mlen = mlen; best_off = i; cur = 0; last_pos = 1;

   425                         goto _storeSequence;

   426                     }

   427                     best_off = i - (ip == anchor);

   428                     do {

   429                         price = ZSTD_getPrice(seqStorePtr, litlen, anchor, best_off, mlen - MINMATCH, ultra);

   430                         if (mlen > last_pos || price < opt[mlen].price)

   431                             SET_PRICE(mlen, mlen, i, litlen, price);   /* note : macro modifies last_pos */

   432                         mlen--;

   433                     } while (mlen >= minMatch);

   434         }   }   }

   435 

   436         match_num = ZSTD_BtGetAllMatches_selectMLS(ctx, ip, iend, maxSearches, mls, matches, minMatch);

   437 

   438         if (!last_pos && !match_num) { ip++; continue; }

   439 

   440         if (match_num && (matches[match_num-1].len > sufficient_len || matches[match_num-1].len >= ZSTD_OPT_NUM)) {

   441             best_mlen = matches[match_num-1].len;

   442             best_off = matches[match_num-1].off;

   443             cur = 0;

   444             last_pos = 1;

   445             goto _storeSequence;

   446         }

   447 

   448         /* set prices using matches at position = 0 */

   449         best_mlen = (last_pos) ? last_pos : minMatch;

   450         for (u = 0; u < match_num; u++) {

   451             mlen = (u>0) ? matches[u-1].len+1 : best_mlen;

   452             best_mlen = matches[u].len;

   453             while (mlen <= best_mlen) {

   454                 price = ZSTD_getPrice(seqStorePtr, litlen, anchor, matches[u].off-1, mlen - MINMATCH, ultra);

   455                 if (mlen > last_pos || price < opt[mlen].price)

   456                     SET_PRICE(mlen, mlen, matches[u].off, litlen, price);   /* note : macro modifies last_pos */

   457                 mlen++;

   458         }   }

   459 

   460         if (last_pos < minMatch) { ip++; continue; }

   461 

   462         /* initialize opt[0] */

   463         { U32 i ; for (i=0; i<ZSTD_REP_NUM; i++) opt[0].rep[i] = rep[i]; }

   464         opt[0].mlen = 1;

   465         opt[0].litlen = litlen;

   466 

   467          /* check further positions */

   468         for (cur = 1; cur <= last_pos; cur++) {

   469            inr = ip + cur;

   470 

   471            if (opt[cur-1].mlen == 1) {

   472                 litlen = opt[cur-1].litlen + 1;

   473                 if (cur > litlen) {

   474                     price = opt[cur - litlen].price + ZSTD_getLiteralPrice(seqStorePtr, litlen, inr-litlen);

   475                 } else

   476                     price = ZSTD_getLiteralPrice(seqStorePtr, litlen, anchor);

   477            } else {

   478                 litlen = 1;

   479                 price = opt[cur - 1].price + ZSTD_getLiteralPrice(seqStorePtr, litlen, inr-1);

   480            }

   481 

   482            if (cur > last_pos || price <= opt[cur].price)

   483                 SET_PRICE(cur, 1, 0, litlen, price);

   484 

   485            if (cur == last_pos) break;

   486 

   487            if (inr > ilimit)  /* last match must start at a minimum distance of 8 from oend */

   488                continue;

   489 

   490            mlen = opt[cur].mlen;

   491            if (opt[cur].off > ZSTD_REP_MOVE_OPT) {

   492                 opt[cur].rep[2] = opt[cur-mlen].rep[1];

   493                 opt[cur].rep[1] = opt[cur-mlen].rep[0];

   494                 opt[cur].rep[0] = opt[cur].off - ZSTD_REP_MOVE_OPT;

   495            } else {

   496                 opt[cur].rep[2] = (opt[cur].off > 1) ? opt[cur-mlen].rep[1] : opt[cur-mlen].rep[2];

   497                 opt[cur].rep[1] = (opt[cur].off > 0) ? opt[cur-mlen].rep[0] : opt[cur-mlen].rep[1];

   498                 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]);

   499            }

   500 

   501             best_mlen = minMatch;

   502             {   U32 i, last_i = ZSTD_REP_CHECK + (mlen != 1);

   503                 for (i=(opt[cur].mlen != 1); i<last_i; i++) {  /* check rep */

   504                     const S32 repCur = ((i==ZSTD_REP_MOVE_OPT) && (opt[cur].mlen != 1)) ? (opt[cur].rep[0] - 1) : opt[cur].rep[i];

   505                     if ( (repCur > 0) && (repCur < (S32)(inr-prefixStart))

   506                        && (MEM_readMINMATCH(inr, minMatch) == MEM_readMINMATCH(inr - repCur, minMatch))) {

   507                        mlen = (U32)ZSTD_count(inr+minMatch, inr+minMatch - repCur, iend) + minMatch;

   508 

   509                        if (mlen > sufficient_len || cur + mlen >= ZSTD_OPT_NUM) {

   510                             best_mlen = mlen; best_off = i; last_pos = cur + 1;

   511                             goto _storeSequence;

   512                        }

   513 

   514                        best_off = i - (opt[cur].mlen != 1);

   515                        if (mlen > best_mlen) best_mlen = mlen;

   516 

   517                        do {

   518                            if (opt[cur].mlen == 1) {

   519                                 litlen = opt[cur].litlen;

   520                                 if (cur > litlen) {

   521                                     price = opt[cur - litlen].price + ZSTD_getPrice(seqStorePtr, litlen, inr-litlen, best_off, mlen - MINMATCH, ultra);

   522                                 } else

   523                                     price = ZSTD_getPrice(seqStorePtr, litlen, anchor, best_off, mlen - MINMATCH, ultra);

   524                             } else {

   525                                 litlen = 0;

   526                                 price = opt[cur].price + ZSTD_getPrice(seqStorePtr, 0, NULL, best_off, mlen - MINMATCH, ultra);

   527                             }

   528 

   529                             if (cur + mlen > last_pos || price <= opt[cur + mlen].price)

   530                                 SET_PRICE(cur + mlen, mlen, i, litlen, price);

   531                             mlen--;

   532                         } while (mlen >= minMatch);

   533             }   }   }

   534 

   535             match_num = ZSTD_BtGetAllMatches_selectMLS(ctx, inr, iend, maxSearches, mls, matches, best_mlen);

   536 

   537             if (match_num > 0 && (matches[match_num-1].len > sufficient_len || cur + matches[match_num-1].len >= ZSTD_OPT_NUM)) {

   538                 best_mlen = matches[match_num-1].len;

   539                 best_off = matches[match_num-1].off;

   540                 last_pos = cur + 1;

   541                 goto _storeSequence;

   542             }

   543 

   544             /* set prices using matches at position = cur */

   545             for (u = 0; u < match_num; u++) {

   546                 mlen = (u>0) ? matches[u-1].len+1 : best_mlen;

   547                 best_mlen = matches[u].len;

   548 

   549                 while (mlen <= best_mlen) {

   550                     if (opt[cur].mlen == 1) {

   551                         litlen = opt[cur].litlen;

   552                         if (cur > litlen)

   553                             price = opt[cur - litlen].price + ZSTD_getPrice(seqStorePtr, litlen, ip+cur-litlen, matches[u].off-1, mlen - MINMATCH, ultra);

   554                         else

   555                             price = ZSTD_getPrice(seqStorePtr, litlen, anchor, matches[u].off-1, mlen - MINMATCH, ultra);

   556                     } else {

   557                         litlen = 0;

   558                         price = opt[cur].price + ZSTD_getPrice(seqStorePtr, 0, NULL, matches[u].off-1, mlen - MINMATCH, ultra);

   559                     }

   560 

   561                     if (cur + mlen > last_pos || (price < opt[cur + mlen].price))

   562                         SET_PRICE(cur + mlen, mlen, matches[u].off, litlen, price);

   563 

   564                     mlen++;

   565         }   }   }

   566 

   567         best_mlen = opt[last_pos].mlen;

   568         best_off = opt[last_pos].off;

   569         cur = last_pos - best_mlen;

   570 

   571         /* store sequence */

   572 _storeSequence:   /* cur, last_pos, best_mlen, best_off have to be set */

   573         opt[0].mlen = 1;

   574 

   575         while (1) {

   576             mlen = opt[cur].mlen;

   577             offset = opt[cur].off;

   578             opt[cur].mlen = best_mlen;

   579             opt[cur].off = best_off;

   580             best_mlen = mlen;

   581             best_off = offset;

   582             if (mlen > cur) break;

   583             cur -= mlen;

   584         }

   585 

   586         for (u = 0; u <= last_pos;) {

   587             u += opt[u].mlen;

   588         }

   589 

   590         for (cur=0; cur < last_pos; ) {

   591             mlen = opt[cur].mlen;

   592             if (mlen == 1) { ip++; cur++; continue; }

   593             offset = opt[cur].off;

   594             cur += mlen;

   595             litLength = (U32)(ip - anchor);

   596 

   597             if (offset > ZSTD_REP_MOVE_OPT) {

   598                 rep[2] = rep[1];

   599                 rep[1] = rep[0];

   600                 rep[0] = offset - ZSTD_REP_MOVE_OPT;

   601                 offset--;

   602             } else {

   603                 if (offset != 0) {

   604                     best_off = ((offset==ZSTD_REP_MOVE_OPT) && (litLength==0)) ? (rep[0] - 1) : (rep[offset]);

   605                     if (offset != 1) rep[2] = rep[1];

   606                     rep[1] = rep[0];

   607                     rep[0] = best_off;

   608                 }

   609                 if (litLength==0) offset--;

   610             }

   611 

   612             ZSTD_updatePrice(seqStorePtr, litLength, anchor, offset, mlen-MINMATCH);

   613             ZSTD_storeSeq(seqStorePtr, litLength, anchor, offset, mlen-MINMATCH);

   614             anchor = ip = ip + mlen;

   615     }    }   /* for (cur=0; cur < last_pos; ) */

   616 

   617     /* Save reps for next block */

   618     { int i; for (i=0; i<ZSTD_REP_NUM; i++) ctx->savedRep[i] = rep[i]; }

   619 

   620     /* Last Literals */

   621     {   size_t const lastLLSize = iend - anchor;

   622         memcpy(seqStorePtr->lit, anchor, lastLLSize);

   623         seqStorePtr->lit += lastLLSize;

   624     }

   625 }

   626 

   627 

   628 FORCE_INLINE

   629 void ZSTD_compressBlock_opt_extDict_generic(ZSTD_CCtx* ctx,

   630                                      const void* src, size_t srcSize, const int ultra)

   631 {

   632     seqStore_t* seqStorePtr = &(ctx->seqStore);

   633     const BYTE* const istart = (const BYTE*)src;

   634     const BYTE* ip = istart;

   635     const BYTE* anchor = istart;

   636     const BYTE* const iend = istart + srcSize;

   637     const BYTE* const ilimit = iend - 8;

   638     const BYTE* const base = ctx->base;

   639     const U32 lowestIndex = ctx->lowLimit;

   640     const U32 dictLimit = ctx->dictLimit;

   641     const BYTE* const prefixStart = base + dictLimit;

   642     const BYTE* const dictBase = ctx->dictBase;

   643     const BYTE* const dictEnd  = dictBase + dictLimit;

   644 

   645     const U32 maxSearches = 1U << ctx->params.cParams.searchLog;

   646     const U32 sufficient_len = ctx->params.cParams.targetLength;

   647     const U32 mls = ctx->params.cParams.searchLength;

   648     const U32 minMatch = (ctx->params.cParams.searchLength == 3) ? 3 : 4;

   649 

   650     ZSTD_optimal_t* opt = seqStorePtr->priceTable;

   651     ZSTD_match_t* matches = seqStorePtr->matchTable;

   652     const BYTE* inr;

   653 

   654     /* init */

   655     U32 offset, rep[ZSTD_REP_NUM];

   656     { U32 i; for (i=0; i<ZSTD_REP_NUM; i++) rep[i]=ctx->rep[i]; }

   657 

   658     ctx->nextToUpdate3 = ctx->nextToUpdate;

   659     ZSTD_rescaleFreqs(seqStorePtr);

   660     ip += (ip==prefixStart);

   661 

   662     /* Match Loop */

   663     while (ip < ilimit) {

   664         U32 cur, match_num, last_pos, litlen, price;

   665         U32 u, mlen, best_mlen, best_off, litLength;

   666         U32 current = (U32)(ip-base);

   667         memset(opt, 0, sizeof(ZSTD_optimal_t));

   668         last_pos = 0;

   669         opt[0].litlen = (U32)(ip - anchor);

   670 

   671         /* check repCode */

   672         {   U32 i, last_i = ZSTD_REP_CHECK + (ip==anchor);

   673             for (i = (ip==anchor); i<last_i; i++) {

   674                 const S32 repCur = ((i==ZSTD_REP_MOVE_OPT) && (ip==anchor)) ? (rep[0] - 1) : rep[i];

   675                 const U32 repIndex = (U32)(current - repCur);

   676                 const BYTE* const repBase = repIndex < dictLimit ? dictBase : base;

   677                 const BYTE* const repMatch = repBase + repIndex;

   678                 if ( (repCur > 0 && repCur <= (S32)current)

   679                    && (((U32)((dictLimit-1) - repIndex) >= 3) & (repIndex>lowestIndex))  /* intentional overflow */

   680                    && (MEM_readMINMATCH(ip, minMatch) == MEM_readMINMATCH(repMatch, minMatch)) ) {

   681                     /* repcode detected we should take it */

   682                     const BYTE* const repEnd = repIndex < dictLimit ? dictEnd : iend;

   683                     mlen = (U32)ZSTD_count_2segments(ip+minMatch, repMatch+minMatch, iend, repEnd, prefixStart) + minMatch;

   684 

   685                     if (mlen > sufficient_len || mlen >= ZSTD_OPT_NUM) {

   686                         best_mlen = mlen; best_off = i; cur = 0; last_pos = 1;

   687                         goto _storeSequence;

   688                     }

   689 

   690                     best_off = i - (ip==anchor);

   691                     litlen = opt[0].litlen;

   692                     do {

   693                         price = ZSTD_getPrice(seqStorePtr, litlen, anchor, best_off, mlen - MINMATCH, ultra);

   694                         if (mlen > last_pos || price < opt[mlen].price)

   695                             SET_PRICE(mlen, mlen, i, litlen, price);   /* note : macro modifies last_pos */

   696                         mlen--;

   697                     } while (mlen >= minMatch);

   698         }   }   }

   699 

   700         match_num = ZSTD_BtGetAllMatches_selectMLS_extDict(ctx, ip, iend, maxSearches, mls, matches, minMatch);  /* first search (depth 0) */

   701 

   702         if (!last_pos && !match_num) { ip++; continue; }

   703 

   704         { U32 i; for (i=0; i<ZSTD_REP_NUM; i++) opt[0].rep[i] = rep[i]; }

   705         opt[0].mlen = 1;

   706 

   707         if (match_num && (matches[match_num-1].len > sufficient_len || matches[match_num-1].len >= ZSTD_OPT_NUM)) {

   708             best_mlen = matches[match_num-1].len;

   709             best_off = matches[match_num-1].off;

   710             cur = 0;

   711             last_pos = 1;

   712             goto _storeSequence;

   713         }

   714 

   715         best_mlen = (last_pos) ? last_pos : minMatch;

   716 

   717         /* set prices using matches at position = 0 */

   718         for (u = 0; u < match_num; u++) {

   719             mlen = (u>0) ? matches[u-1].len+1 : best_mlen;

   720             best_mlen = matches[u].len;

   721             litlen = opt[0].litlen;

   722             while (mlen <= best_mlen) {

   723                 price = ZSTD_getPrice(seqStorePtr, litlen, anchor, matches[u].off-1, mlen - MINMATCH, ultra);

   724                 if (mlen > last_pos || price < opt[mlen].price)

   725                     SET_PRICE(mlen, mlen, matches[u].off, litlen, price);

   726                 mlen++;

   727         }   }

   728 

   729         if (last_pos < minMatch) {

   730             ip++; continue;

   731         }

   732 

   733         /* check further positions */

   734         for (cur = 1; cur <= last_pos; cur++) {

   735             inr = ip + cur;

   736 

   737             if (opt[cur-1].mlen == 1) {

   738                 litlen = opt[cur-1].litlen + 1;

   739                 if (cur > litlen) {

   740                     price = opt[cur - litlen].price + ZSTD_getLiteralPrice(seqStorePtr, litlen, inr-litlen);

   741                 } else

   742                     price = ZSTD_getLiteralPrice(seqStorePtr, litlen, anchor);

   743             } else {

   744                 litlen = 1;

   745                 price = opt[cur - 1].price + ZSTD_getLiteralPrice(seqStorePtr, litlen, inr-1);

   746             }

   747 

   748             if (cur > last_pos || price <= opt[cur].price)

   749                 SET_PRICE(cur, 1, 0, litlen, price);

   750 

   751             if (cur == last_pos) break;

   752 

   753             if (inr > ilimit)  /* last match must start at a minimum distance of 8 from oend */

   754                 continue;

   755 

   756             mlen = opt[cur].mlen;

   757             if (opt[cur].off > ZSTD_REP_MOVE_OPT) {

   758                 opt[cur].rep[2] = opt[cur-mlen].rep[1];

   759                 opt[cur].rep[1] = opt[cur-mlen].rep[0];

   760                 opt[cur].rep[0] = opt[cur].off - ZSTD_REP_MOVE_OPT;

   761             } else {

   762                 opt[cur].rep[2] = (opt[cur].off > 1) ? opt[cur-mlen].rep[1] : opt[cur-mlen].rep[2];

   763                 opt[cur].rep[1] = (opt[cur].off > 0) ? opt[cur-mlen].rep[0] : opt[cur-mlen].rep[1];

   764                 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]);

   765             }

   766 

   767             best_mlen = minMatch;

   768             {   U32 i, last_i = ZSTD_REP_CHECK + (mlen != 1);

   769                 for (i = (mlen != 1); i<last_i; i++) {

   770                     const S32 repCur = ((i==ZSTD_REP_MOVE_OPT) && (opt[cur].mlen != 1)) ? (opt[cur].rep[0] - 1) : opt[cur].rep[i];

   771                     const U32 repIndex = (U32)(current+cur - repCur);

   772                     const BYTE* const repBase = repIndex < dictLimit ? dictBase : base;

   773                     const BYTE* const repMatch = repBase + repIndex;

   774                     if ( (repCur > 0 && repCur <= (S32)(current+cur))

   775                       && (((U32)((dictLimit-1) - repIndex) >= 3) & (repIndex>lowestIndex))  /* intentional overflow */

   776                       && (MEM_readMINMATCH(inr, minMatch) == MEM_readMINMATCH(repMatch, minMatch)) ) {

   777                         /* repcode detected */

   778                         const BYTE* const repEnd = repIndex < dictLimit ? dictEnd : iend;

   779                         mlen = (U32)ZSTD_count_2segments(inr+minMatch, repMatch+minMatch, iend, repEnd, prefixStart) + minMatch;

   780 

   781                         if (mlen > sufficient_len || cur + mlen >= ZSTD_OPT_NUM) {

   782                             best_mlen = mlen; best_off = i; last_pos = cur + 1;

   783                             goto _storeSequence;

   784                         }

   785 

   786                         best_off = i - (opt[cur].mlen != 1);

   787                         if (mlen > best_mlen) best_mlen = mlen;

   788 

   789                         do {

   790                             if (opt[cur].mlen == 1) {

   791                                 litlen = opt[cur].litlen;

   792                                 if (cur > litlen) {

   793                                     price = opt[cur - litlen].price + ZSTD_getPrice(seqStorePtr, litlen, inr-litlen, best_off, mlen - MINMATCH, ultra);

   794                                 } else

   795                                     price = ZSTD_getPrice(seqStorePtr, litlen, anchor, best_off, mlen - MINMATCH, ultra);

   796                             } else {

   797                                 litlen = 0;

   798                                 price = opt[cur].price + ZSTD_getPrice(seqStorePtr, 0, NULL, best_off, mlen - MINMATCH, ultra);

   799                             }

   800 

   801                             if (cur + mlen > last_pos || price <= opt[cur + mlen].price)

   802                                 SET_PRICE(cur + mlen, mlen, i, litlen, price);

   803                             mlen--;

   804                         } while (mlen >= minMatch);

   805             }   }   }

   806 

   807             match_num = ZSTD_BtGetAllMatches_selectMLS_extDict(ctx, inr, iend, maxSearches, mls, matches, minMatch);

   808 

   809             if (match_num > 0 && matches[match_num-1].len > sufficient_len) {

   810                 best_mlen = matches[match_num-1].len;

   811                 best_off = matches[match_num-1].off;

   812                 last_pos = cur + 1;

   813                 goto _storeSequence;

   814             }

   815 

   816             /* set prices using matches at position = cur */

   817             for (u = 0; u < match_num; u++) {

   818                 mlen = (u>0) ? matches[u-1].len+1 : best_mlen;

   819                 best_mlen = (cur + matches[u].len < ZSTD_OPT_NUM) ? matches[u].len : ZSTD_OPT_NUM - cur;

   820 

   821                 while (mlen <= best_mlen) {

   822                     if (opt[cur].mlen == 1) {

   823                         litlen = opt[cur].litlen;

   824                         if (cur > litlen)

   825                             price = opt[cur - litlen].price + ZSTD_getPrice(seqStorePtr, litlen, ip+cur-litlen, matches[u].off-1, mlen - MINMATCH, ultra);

   826                         else

   827                             price = ZSTD_getPrice(seqStorePtr, litlen, anchor, matches[u].off-1, mlen - MINMATCH, ultra);

   828                     } else {

   829                         litlen = 0;

   830                         price = opt[cur].price + ZSTD_getPrice(seqStorePtr, 0, NULL, matches[u].off-1, mlen - MINMATCH, ultra);

   831                     }

   832 

   833                     if (cur + mlen > last_pos || (price < opt[cur + mlen].price))

   834                         SET_PRICE(cur + mlen, mlen, matches[u].off, litlen, price);

   835 

   836                     mlen++;

   837         }   }   }   /* for (cur = 1; cur <= last_pos; cur++) */

   838 

   839         best_mlen = opt[last_pos].mlen;

   840         best_off = opt[last_pos].off;

   841         cur = last_pos - best_mlen;

   842 

   843         /* store sequence */

   844 _storeSequence:   /* cur, last_pos, best_mlen, best_off have to be set */

   845         opt[0].mlen = 1;

   846 

   847         while (1) {

   848             mlen = opt[cur].mlen;

   849             offset = opt[cur].off;

   850             opt[cur].mlen = best_mlen;

   851             opt[cur].off = best_off;

   852             best_mlen = mlen;

   853             best_off = offset;

   854             if (mlen > cur) break;

   855             cur -= mlen;

   856         }

   857 

   858         for (u = 0; u <= last_pos; ) {

   859             u += opt[u].mlen;

   860         }

   861 

   862         for (cur=0; cur < last_pos; ) {

   863             mlen = opt[cur].mlen;

   864             if (mlen == 1) { ip++; cur++; continue; }

   865             offset = opt[cur].off;

   866             cur += mlen;

   867             litLength = (U32)(ip - anchor);

   868 

   869             if (offset > ZSTD_REP_MOVE_OPT) {

   870                 rep[2] = rep[1];

   871                 rep[1] = rep[0];

   872                 rep[0] = offset - ZSTD_REP_MOVE_OPT;

   873                 offset--;

   874             } else {

   875                 if (offset != 0) {

   876                     best_off = ((offset==ZSTD_REP_MOVE_OPT) && (litLength==0)) ? (rep[0] - 1) : (rep[offset]);

   877                     if (offset != 1) rep[2] = rep[1];

   878                     rep[1] = rep[0];

   879                     rep[0] = best_off;

   880                 }

   881 

   882                 if (litLength==0) offset--;

   883             }

   884 

   885             ZSTD_updatePrice(seqStorePtr, litLength, anchor, offset, mlen-MINMATCH);

   886             ZSTD_storeSeq(seqStorePtr, litLength, anchor, offset, mlen-MINMATCH);

   887             anchor = ip = ip + mlen;

   888     }    }   /* for (cur=0; cur < last_pos; ) */

   889 

   890     /* Save reps for next block */

   891     { int i; for (i=0; i<ZSTD_REP_NUM; i++) ctx->savedRep[i] = rep[i]; }

   892 

   893     /* Last Literals */

   894     {   size_t lastLLSize = iend - anchor;

   895         memcpy(seqStorePtr->lit, anchor, lastLLSize);

   896         seqStorePtr->lit += lastLLSize;

   897     }

   898 }

   899 

   900 #endif  /* ZSTD_OPT_H_91842398743 */