lib/zstd/zstd_opt.h

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