lib/zstd/zstd_opt.h

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