LXR linux/lib/zstd/zstd

   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***************************************/
  29FORCE_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
  38ZSTD_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
 101FORCE_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
 142FORCE_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
 165ZSTD_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) */
 214FORCE_INLINE
 215U32 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***************************************/
 235static 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
 350update:
 351        zc->nextToUpdate = (matchEndIdx > curr + 8) ? matchEndIdx - 8 : curr + 1;
 352        return mnum;
 353}
 354
 355/** Tree updater, providing best match */
 356static 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
 365static 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 */
 380static 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
 389static 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*********************************/
 406FORCE_INLINE
 407void 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
 699FORCE_INLINE
 700void 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 */
1015