Back to home page

OSCL-LXR
 
 

     

0001 /*
0002  * Copyright (c) Przemyslaw Skibinski, Yann Collet, Facebook, Inc.
0003  * All rights reserved.
0004  *
0005  * This source code is licensed under both the BSD-style license (found in the
0006  * LICENSE file in the root directory of this source tree) and the GPLv2 (found
0007  * in the COPYING file in the root directory of this source tree).
0008  * You may select, at your option, one of the above-listed licenses.
0009  */
0010 
0011 /*
0012  * Disable inlining for the optimal parser for the kernel build.
0013  * It is unlikely to be used in the kernel, and where it is used
0014  * latency shouldn't matter because it is very slow to begin with.
0015  * We prefer a ~180KB binary size win over faster optimal parsing.
0016  *
0017  * TODO(https://github.com/facebook/zstd/issues/2862):
0018  * Improve the code size of the optimal parser in general, so we
0019  * don't need this hack for the kernel build.
0020  */
0021 #define ZSTD_NO_INLINE 1
0022 
0023 #include "zstd_compress_internal.h"
0024 #include "hist.h"
0025 #include "zstd_opt.h"
0026 
0027 
0028 #define ZSTD_LITFREQ_ADD    2   /* scaling factor for litFreq, so that frequencies adapt faster to new stats */
0029 #define ZSTD_FREQ_DIV       4   /* log factor when using previous stats to init next stats */
0030 #define ZSTD_MAX_PRICE     (1<<30)
0031 
0032 #define ZSTD_PREDEF_THRESHOLD 1024   /* if srcSize < ZSTD_PREDEF_THRESHOLD, symbols' cost is assumed static, directly determined by pre-defined distributions */
0033 
0034 
0035 /*-*************************************
0036 *  Price functions for optimal parser
0037 ***************************************/
0038 
0039 #if 0    /* approximation at bit level */
0040 #  define BITCOST_ACCURACY 0
0041 #  define BITCOST_MULTIPLIER (1 << BITCOST_ACCURACY)
0042 #  define WEIGHT(stat)  ((void)opt, ZSTD_bitWeight(stat))
0043 #elif 0  /* fractional bit accuracy */
0044 #  define BITCOST_ACCURACY 8
0045 #  define BITCOST_MULTIPLIER (1 << BITCOST_ACCURACY)
0046 #  define WEIGHT(stat,opt) ((void)opt, ZSTD_fracWeight(stat))
0047 #else    /* opt==approx, ultra==accurate */
0048 #  define BITCOST_ACCURACY 8
0049 #  define BITCOST_MULTIPLIER (1 << BITCOST_ACCURACY)
0050 #  define WEIGHT(stat,opt) (opt ? ZSTD_fracWeight(stat) : ZSTD_bitWeight(stat))
0051 #endif
0052 
0053 MEM_STATIC U32 ZSTD_bitWeight(U32 stat)
0054 {
0055     return (ZSTD_highbit32(stat+1) * BITCOST_MULTIPLIER);
0056 }
0057 
0058 MEM_STATIC U32 ZSTD_fracWeight(U32 rawStat)
0059 {
0060     U32 const stat = rawStat + 1;
0061     U32 const hb = ZSTD_highbit32(stat);
0062     U32 const BWeight = hb * BITCOST_MULTIPLIER;
0063     U32 const FWeight = (stat << BITCOST_ACCURACY) >> hb;
0064     U32 const weight = BWeight + FWeight;
0065     assert(hb + BITCOST_ACCURACY < 31);
0066     return weight;
0067 }
0068 
0069 #if (DEBUGLEVEL>=2)
0070 /* debugging function,
0071  * @return price in bytes as fractional value
0072  * for debug messages only */
0073 MEM_STATIC double ZSTD_fCost(U32 price)
0074 {
0075     return (double)price / (BITCOST_MULTIPLIER*8);
0076 }
0077 #endif
0078 
0079 static int ZSTD_compressedLiterals(optState_t const* const optPtr)
0080 {
0081     return optPtr->literalCompressionMode != ZSTD_lcm_uncompressed;
0082 }
0083 
0084 static void ZSTD_setBasePrices(optState_t* optPtr, int optLevel)
0085 {
0086     if (ZSTD_compressedLiterals(optPtr))
0087         optPtr->litSumBasePrice = WEIGHT(optPtr->litSum, optLevel);
0088     optPtr->litLengthSumBasePrice = WEIGHT(optPtr->litLengthSum, optLevel);
0089     optPtr->matchLengthSumBasePrice = WEIGHT(optPtr->matchLengthSum, optLevel);
0090     optPtr->offCodeSumBasePrice = WEIGHT(optPtr->offCodeSum, optLevel);
0091 }
0092 
0093 
0094 /* ZSTD_downscaleStat() :
0095  * reduce all elements in table by a factor 2^(ZSTD_FREQ_DIV+malus)
0096  * return the resulting sum of elements */
0097 static U32 ZSTD_downscaleStat(unsigned* table, U32 lastEltIndex, int malus)
0098 {
0099     U32 s, sum=0;
0100     DEBUGLOG(5, "ZSTD_downscaleStat (nbElts=%u)", (unsigned)lastEltIndex+1);
0101     assert(ZSTD_FREQ_DIV+malus > 0 && ZSTD_FREQ_DIV+malus < 31);
0102     for (s=0; s<lastEltIndex+1; s++) {
0103         table[s] = 1 + (table[s] >> (ZSTD_FREQ_DIV+malus));
0104         sum += table[s];
0105     }
0106     return sum;
0107 }
0108 
0109 /* ZSTD_rescaleFreqs() :
0110  * if first block (detected by optPtr->litLengthSum == 0) : init statistics
0111  *    take hints from dictionary if there is one
0112  *    or init from zero, using src for literals stats, or flat 1 for match symbols
0113  * otherwise downscale existing stats, to be used as seed for next block.
0114  */
0115 static void
0116 ZSTD_rescaleFreqs(optState_t* const optPtr,
0117             const BYTE* const src, size_t const srcSize,
0118                   int const optLevel)
0119 {
0120     int const compressedLiterals = ZSTD_compressedLiterals(optPtr);
0121     DEBUGLOG(5, "ZSTD_rescaleFreqs (srcSize=%u)", (unsigned)srcSize);
0122     optPtr->priceType = zop_dynamic;
0123 
0124     if (optPtr->litLengthSum == 0) {  /* first block : init */
0125         if (srcSize <= ZSTD_PREDEF_THRESHOLD) {  /* heuristic */
0126             DEBUGLOG(5, "(srcSize <= ZSTD_PREDEF_THRESHOLD) => zop_predef");
0127             optPtr->priceType = zop_predef;
0128         }
0129 
0130         assert(optPtr->symbolCosts != NULL);
0131         if (optPtr->symbolCosts->huf.repeatMode == HUF_repeat_valid) {
0132             /* huffman table presumed generated by dictionary */
0133             optPtr->priceType = zop_dynamic;
0134 
0135             if (compressedLiterals) {
0136                 unsigned lit;
0137                 assert(optPtr->litFreq != NULL);
0138                 optPtr->litSum = 0;
0139                 for (lit=0; lit<=MaxLit; lit++) {
0140                     U32 const scaleLog = 11;   /* scale to 2K */
0141                     U32 const bitCost = HUF_getNbBits(optPtr->symbolCosts->huf.CTable, lit);
0142                     assert(bitCost <= scaleLog);
0143                     optPtr->litFreq[lit] = bitCost ? 1 << (scaleLog-bitCost) : 1 /*minimum to calculate cost*/;
0144                     optPtr->litSum += optPtr->litFreq[lit];
0145             }   }
0146 
0147             {   unsigned ll;
0148                 FSE_CState_t llstate;
0149                 FSE_initCState(&llstate, optPtr->symbolCosts->fse.litlengthCTable);
0150                 optPtr->litLengthSum = 0;
0151                 for (ll=0; ll<=MaxLL; ll++) {
0152                     U32 const scaleLog = 10;   /* scale to 1K */
0153                     U32 const bitCost = FSE_getMaxNbBits(llstate.symbolTT, ll);
0154                     assert(bitCost < scaleLog);
0155                     optPtr->litLengthFreq[ll] = bitCost ? 1 << (scaleLog-bitCost) : 1 /*minimum to calculate cost*/;
0156                     optPtr->litLengthSum += optPtr->litLengthFreq[ll];
0157             }   }
0158 
0159             {   unsigned ml;
0160                 FSE_CState_t mlstate;
0161                 FSE_initCState(&mlstate, optPtr->symbolCosts->fse.matchlengthCTable);
0162                 optPtr->matchLengthSum = 0;
0163                 for (ml=0; ml<=MaxML; ml++) {
0164                     U32 const scaleLog = 10;
0165                     U32 const bitCost = FSE_getMaxNbBits(mlstate.symbolTT, ml);
0166                     assert(bitCost < scaleLog);
0167                     optPtr->matchLengthFreq[ml] = bitCost ? 1 << (scaleLog-bitCost) : 1 /*minimum to calculate cost*/;
0168                     optPtr->matchLengthSum += optPtr->matchLengthFreq[ml];
0169             }   }
0170 
0171             {   unsigned of;
0172                 FSE_CState_t ofstate;
0173                 FSE_initCState(&ofstate, optPtr->symbolCosts->fse.offcodeCTable);
0174                 optPtr->offCodeSum = 0;
0175                 for (of=0; of<=MaxOff; of++) {
0176                     U32 const scaleLog = 10;
0177                     U32 const bitCost = FSE_getMaxNbBits(ofstate.symbolTT, of);
0178                     assert(bitCost < scaleLog);
0179                     optPtr->offCodeFreq[of] = bitCost ? 1 << (scaleLog-bitCost) : 1 /*minimum to calculate cost*/;
0180                     optPtr->offCodeSum += optPtr->offCodeFreq[of];
0181             }   }
0182 
0183         } else {  /* not a dictionary */
0184 
0185             assert(optPtr->litFreq != NULL);
0186             if (compressedLiterals) {
0187                 unsigned lit = MaxLit;
0188                 HIST_count_simple(optPtr->litFreq, &lit, src, srcSize);   /* use raw first block to init statistics */
0189                 optPtr->litSum = ZSTD_downscaleStat(optPtr->litFreq, MaxLit, 1);
0190             }
0191 
0192             {   unsigned ll;
0193                 for (ll=0; ll<=MaxLL; ll++)
0194                     optPtr->litLengthFreq[ll] = 1;
0195             }
0196             optPtr->litLengthSum = MaxLL+1;
0197 
0198             {   unsigned ml;
0199                 for (ml=0; ml<=MaxML; ml++)
0200                     optPtr->matchLengthFreq[ml] = 1;
0201             }
0202             optPtr->matchLengthSum = MaxML+1;
0203 
0204             {   unsigned of;
0205                 for (of=0; of<=MaxOff; of++)
0206                     optPtr->offCodeFreq[of] = 1;
0207             }
0208             optPtr->offCodeSum = MaxOff+1;
0209 
0210         }
0211 
0212     } else {   /* new block : re-use previous statistics, scaled down */
0213 
0214         if (compressedLiterals)
0215             optPtr->litSum = ZSTD_downscaleStat(optPtr->litFreq, MaxLit, 1);
0216         optPtr->litLengthSum = ZSTD_downscaleStat(optPtr->litLengthFreq, MaxLL, 0);
0217         optPtr->matchLengthSum = ZSTD_downscaleStat(optPtr->matchLengthFreq, MaxML, 0);
0218         optPtr->offCodeSum = ZSTD_downscaleStat(optPtr->offCodeFreq, MaxOff, 0);
0219     }
0220 
0221     ZSTD_setBasePrices(optPtr, optLevel);
0222 }
0223 
0224 /* ZSTD_rawLiteralsCost() :
0225  * price of literals (only) in specified segment (which length can be 0).
0226  * does not include price of literalLength symbol */
0227 static U32 ZSTD_rawLiteralsCost(const BYTE* const literals, U32 const litLength,
0228                                 const optState_t* const optPtr,
0229                                 int optLevel)
0230 {
0231     if (litLength == 0) return 0;
0232 
0233     if (!ZSTD_compressedLiterals(optPtr))
0234         return (litLength << 3) * BITCOST_MULTIPLIER;  /* Uncompressed - 8 bytes per literal. */
0235 
0236     if (optPtr->priceType == zop_predef)
0237         return (litLength*6) * BITCOST_MULTIPLIER;  /* 6 bit per literal - no statistic used */
0238 
0239     /* dynamic statistics */
0240     {   U32 price = litLength * optPtr->litSumBasePrice;
0241         U32 u;
0242         for (u=0; u < litLength; u++) {
0243             assert(WEIGHT(optPtr->litFreq[literals[u]], optLevel) <= optPtr->litSumBasePrice);   /* literal cost should never be negative */
0244             price -= WEIGHT(optPtr->litFreq[literals[u]], optLevel);
0245         }
0246         return price;
0247     }
0248 }
0249 
0250 /* ZSTD_litLengthPrice() :
0251  * cost of literalLength symbol */
0252 static U32 ZSTD_litLengthPrice(U32 const litLength, const optState_t* const optPtr, int optLevel)
0253 {
0254     if (optPtr->priceType == zop_predef) return WEIGHT(litLength, optLevel);
0255 
0256     /* dynamic statistics */
0257     {   U32 const llCode = ZSTD_LLcode(litLength);
0258         return (LL_bits[llCode] * BITCOST_MULTIPLIER)
0259              + optPtr->litLengthSumBasePrice
0260              - WEIGHT(optPtr->litLengthFreq[llCode], optLevel);
0261     }
0262 }
0263 
0264 /* ZSTD_getMatchPrice() :
0265  * Provides the cost of the match part (offset + matchLength) of a sequence
0266  * Must be combined with ZSTD_fullLiteralsCost() to get the full cost of a sequence.
0267  * optLevel: when <2, favors small offset for decompression speed (improved cache efficiency) */
0268 FORCE_INLINE_TEMPLATE U32
0269 ZSTD_getMatchPrice(U32 const offset,
0270                    U32 const matchLength,
0271              const optState_t* const optPtr,
0272                    int const optLevel)
0273 {
0274     U32 price;
0275     U32 const offCode = ZSTD_highbit32(offset+1);
0276     U32 const mlBase = matchLength - MINMATCH;
0277     assert(matchLength >= MINMATCH);
0278 
0279     if (optPtr->priceType == zop_predef)  /* fixed scheme, do not use statistics */
0280         return WEIGHT(mlBase, optLevel) + ((16 + offCode) * BITCOST_MULTIPLIER);
0281 
0282     /* dynamic statistics */
0283     price = (offCode * BITCOST_MULTIPLIER) + (optPtr->offCodeSumBasePrice - WEIGHT(optPtr->offCodeFreq[offCode], optLevel));
0284     if ((optLevel<2) /*static*/ && offCode >= 20)
0285         price += (offCode-19)*2 * BITCOST_MULTIPLIER; /* handicap for long distance offsets, favor decompression speed */
0286 
0287     /* match Length */
0288     {   U32 const mlCode = ZSTD_MLcode(mlBase);
0289         price += (ML_bits[mlCode] * BITCOST_MULTIPLIER) + (optPtr->matchLengthSumBasePrice - WEIGHT(optPtr->matchLengthFreq[mlCode], optLevel));
0290     }
0291 
0292     price += BITCOST_MULTIPLIER / 5;   /* heuristic : make matches a bit more costly to favor less sequences -> faster decompression speed */
0293 
0294     DEBUGLOG(8, "ZSTD_getMatchPrice(ml:%u) = %u", matchLength, price);
0295     return price;
0296 }
0297 
0298 /* ZSTD_updateStats() :
0299  * assumption : literals + litLengtn <= iend */
0300 static void ZSTD_updateStats(optState_t* const optPtr,
0301                              U32 litLength, const BYTE* literals,
0302                              U32 offsetCode, U32 matchLength)
0303 {
0304     /* literals */
0305     if (ZSTD_compressedLiterals(optPtr)) {
0306         U32 u;
0307         for (u=0; u < litLength; u++)
0308             optPtr->litFreq[literals[u]] += ZSTD_LITFREQ_ADD;
0309         optPtr->litSum += litLength*ZSTD_LITFREQ_ADD;
0310     }
0311 
0312     /* literal Length */
0313     {   U32 const llCode = ZSTD_LLcode(litLength);
0314         optPtr->litLengthFreq[llCode]++;
0315         optPtr->litLengthSum++;
0316     }
0317 
0318     /* match offset code (0-2=>repCode; 3+=>offset+2) */
0319     {   U32 const offCode = ZSTD_highbit32(offsetCode+1);
0320         assert(offCode <= MaxOff);
0321         optPtr->offCodeFreq[offCode]++;
0322         optPtr->offCodeSum++;
0323     }
0324 
0325     /* match Length */
0326     {   U32 const mlBase = matchLength - MINMATCH;
0327         U32 const mlCode = ZSTD_MLcode(mlBase);
0328         optPtr->matchLengthFreq[mlCode]++;
0329         optPtr->matchLengthSum++;
0330     }
0331 }
0332 
0333 
0334 /* ZSTD_readMINMATCH() :
0335  * function safe only for comparisons
0336  * assumption : memPtr must be at least 4 bytes before end of buffer */
0337 MEM_STATIC U32 ZSTD_readMINMATCH(const void* memPtr, U32 length)
0338 {
0339     switch (length)
0340     {
0341     default :
0342     case 4 : return MEM_read32(memPtr);
0343     case 3 : if (MEM_isLittleEndian())
0344                 return MEM_read32(memPtr)<<8;
0345              else
0346                 return MEM_read32(memPtr)>>8;
0347     }
0348 }
0349 
0350 
0351 /* Update hashTable3 up to ip (excluded)
0352    Assumption : always within prefix (i.e. not within extDict) */
0353 static U32 ZSTD_insertAndFindFirstIndexHash3 (ZSTD_matchState_t* ms,
0354                                               U32* nextToUpdate3,
0355                                               const BYTE* const ip)
0356 {
0357     U32* const hashTable3 = ms->hashTable3;
0358     U32 const hashLog3 = ms->hashLog3;
0359     const BYTE* const base = ms->window.base;
0360     U32 idx = *nextToUpdate3;
0361     U32 const target = (U32)(ip - base);
0362     size_t const hash3 = ZSTD_hash3Ptr(ip, hashLog3);
0363     assert(hashLog3 > 0);
0364 
0365     while(idx < target) {
0366         hashTable3[ZSTD_hash3Ptr(base+idx, hashLog3)] = idx;
0367         idx++;
0368     }
0369 
0370     *nextToUpdate3 = target;
0371     return hashTable3[hash3];
0372 }
0373 
0374 
0375 /*-*************************************
0376 *  Binary Tree search
0377 ***************************************/
0378 /* ZSTD_insertBt1() : add one or multiple positions to tree.
0379  *  ip : assumed <= iend-8 .
0380  * @return : nb of positions added */
0381 static U32 ZSTD_insertBt1(
0382                 ZSTD_matchState_t* ms,
0383                 const BYTE* const ip, const BYTE* const iend,
0384                 U32 const mls, const int extDict)
0385 {
0386     const ZSTD_compressionParameters* const cParams = &ms->cParams;
0387     U32*   const hashTable = ms->hashTable;
0388     U32    const hashLog = cParams->hashLog;
0389     size_t const h  = ZSTD_hashPtr(ip, hashLog, mls);
0390     U32*   const bt = ms->chainTable;
0391     U32    const btLog  = cParams->chainLog - 1;
0392     U32    const btMask = (1 << btLog) - 1;
0393     U32 matchIndex = hashTable[h];
0394     size_t commonLengthSmaller=0, commonLengthLarger=0;
0395     const BYTE* const base = ms->window.base;
0396     const BYTE* const dictBase = ms->window.dictBase;
0397     const U32 dictLimit = ms->window.dictLimit;
0398     const BYTE* const dictEnd = dictBase + dictLimit;
0399     const BYTE* const prefixStart = base + dictLimit;
0400     const BYTE* match;
0401     const U32 curr = (U32)(ip-base);
0402     const U32 btLow = btMask >= curr ? 0 : curr - btMask;
0403     U32* smallerPtr = bt + 2*(curr&btMask);
0404     U32* largerPtr  = smallerPtr + 1;
0405     U32 dummy32;   /* to be nullified at the end */
0406     U32 const windowLow = ms->window.lowLimit;
0407     U32 matchEndIdx = curr+8+1;
0408     size_t bestLength = 8;
0409     U32 nbCompares = 1U << cParams->searchLog;
0410 #ifdef ZSTD_C_PREDICT
0411     U32 predictedSmall = *(bt + 2*((curr-1)&btMask) + 0);
0412     U32 predictedLarge = *(bt + 2*((curr-1)&btMask) + 1);
0413     predictedSmall += (predictedSmall>0);
0414     predictedLarge += (predictedLarge>0);
0415 #endif /* ZSTD_C_PREDICT */
0416 
0417     DEBUGLOG(8, "ZSTD_insertBt1 (%u)", curr);
0418 
0419     assert(ip <= iend-8);   /* required for h calculation */
0420     hashTable[h] = curr;   /* Update Hash Table */
0421 
0422     assert(windowLow > 0);
0423     for (; nbCompares && (matchIndex >= windowLow); --nbCompares) {
0424         U32* const nextPtr = bt + 2*(matchIndex & btMask);
0425         size_t matchLength = MIN(commonLengthSmaller, commonLengthLarger);   /* guaranteed minimum nb of common bytes */
0426         assert(matchIndex < curr);
0427 
0428 #ifdef ZSTD_C_PREDICT   /* note : can create issues when hlog small <= 11 */
0429         const U32* predictPtr = bt + 2*((matchIndex-1) & btMask);   /* written this way, as bt is a roll buffer */
0430         if (matchIndex == predictedSmall) {
0431             /* no need to check length, result known */
0432             *smallerPtr = matchIndex;
0433             if (matchIndex <= btLow) { smallerPtr=&dummy32; break; }   /* beyond tree size, stop the search */
0434             smallerPtr = nextPtr+1;               /* new "smaller" => larger of match */
0435             matchIndex = nextPtr[1];              /* new matchIndex larger than previous (closer to current) */
0436             predictedSmall = predictPtr[1] + (predictPtr[1]>0);
0437             continue;
0438         }
0439         if (matchIndex == predictedLarge) {
0440             *largerPtr = matchIndex;
0441             if (matchIndex <= btLow) { largerPtr=&dummy32; break; }   /* beyond tree size, stop the search */
0442             largerPtr = nextPtr;
0443             matchIndex = nextPtr[0];
0444             predictedLarge = predictPtr[0] + (predictPtr[0]>0);
0445             continue;
0446         }
0447 #endif
0448 
0449         if (!extDict || (matchIndex+matchLength >= dictLimit)) {
0450             assert(matchIndex+matchLength >= dictLimit);   /* might be wrong if actually extDict */
0451             match = base + matchIndex;
0452             matchLength += ZSTD_count(ip+matchLength, match+matchLength, iend);
0453         } else {
0454             match = dictBase + matchIndex;
0455             matchLength += ZSTD_count_2segments(ip+matchLength, match+matchLength, iend, dictEnd, prefixStart);
0456             if (matchIndex+matchLength >= dictLimit)
0457                 match = base + matchIndex;   /* to prepare for next usage of match[matchLength] */
0458         }
0459 
0460         if (matchLength > bestLength) {
0461             bestLength = matchLength;
0462             if (matchLength > matchEndIdx - matchIndex)
0463                 matchEndIdx = matchIndex + (U32)matchLength;
0464         }
0465 
0466         if (ip+matchLength == iend) {   /* equal : no way to know if inf or sup */
0467             break;   /* drop , to guarantee consistency ; miss a bit of compression, but other solutions can corrupt tree */
0468         }
0469 
0470         if (match[matchLength] < ip[matchLength]) {  /* necessarily within buffer */
0471             /* match is smaller than current */
0472             *smallerPtr = matchIndex;             /* update smaller idx */
0473             commonLengthSmaller = matchLength;    /* all smaller will now have at least this guaranteed common length */
0474             if (matchIndex <= btLow) { smallerPtr=&dummy32; break; }   /* beyond tree size, stop searching */
0475             smallerPtr = nextPtr+1;               /* new "candidate" => larger than match, which was smaller than target */
0476             matchIndex = nextPtr[1];              /* new matchIndex, larger than previous and closer to current */
0477         } else {
0478             /* match is larger than current */
0479             *largerPtr = matchIndex;
0480             commonLengthLarger = matchLength;
0481             if (matchIndex <= btLow) { largerPtr=&dummy32; break; }   /* beyond tree size, stop searching */
0482             largerPtr = nextPtr;
0483             matchIndex = nextPtr[0];
0484     }   }
0485 
0486     *smallerPtr = *largerPtr = 0;
0487     {   U32 positions = 0;
0488         if (bestLength > 384) positions = MIN(192, (U32)(bestLength - 384));   /* speed optimization */
0489         assert(matchEndIdx > curr + 8);
0490         return MAX(positions, matchEndIdx - (curr + 8));
0491     }
0492 }
0493 
0494 FORCE_INLINE_TEMPLATE
0495 void ZSTD_updateTree_internal(
0496                 ZSTD_matchState_t* ms,
0497                 const BYTE* const ip, const BYTE* const iend,
0498                 const U32 mls, const ZSTD_dictMode_e dictMode)
0499 {
0500     const BYTE* const base = ms->window.base;
0501     U32 const target = (U32)(ip - base);
0502     U32 idx = ms->nextToUpdate;
0503     DEBUGLOG(6, "ZSTD_updateTree_internal, from %u to %u  (dictMode:%u)",
0504                 idx, target, dictMode);
0505 
0506     while(idx < target) {
0507         U32 const forward = ZSTD_insertBt1(ms, base+idx, iend, mls, dictMode == ZSTD_extDict);
0508         assert(idx < (U32)(idx + forward));
0509         idx += forward;
0510     }
0511     assert((size_t)(ip - base) <= (size_t)(U32)(-1));
0512     assert((size_t)(iend - base) <= (size_t)(U32)(-1));
0513     ms->nextToUpdate = target;
0514 }
0515 
0516 void ZSTD_updateTree(ZSTD_matchState_t* ms, const BYTE* ip, const BYTE* iend) {
0517     ZSTD_updateTree_internal(ms, ip, iend, ms->cParams.minMatch, ZSTD_noDict);
0518 }
0519 
0520 FORCE_INLINE_TEMPLATE
0521 U32 ZSTD_insertBtAndGetAllMatches (
0522                     ZSTD_match_t* matches,   /* store result (found matches) in this table (presumed large enough) */
0523                     ZSTD_matchState_t* ms,
0524                     U32* nextToUpdate3,
0525                     const BYTE* const ip, const BYTE* const iLimit, const ZSTD_dictMode_e dictMode,
0526                     const U32 rep[ZSTD_REP_NUM],
0527                     U32 const ll0,   /* tells if associated literal length is 0 or not. This value must be 0 or 1 */
0528                     const U32 lengthToBeat,
0529                     U32 const mls /* template */)
0530 {
0531     const ZSTD_compressionParameters* const cParams = &ms->cParams;
0532     U32 const sufficient_len = MIN(cParams->targetLength, ZSTD_OPT_NUM -1);
0533     const BYTE* const base = ms->window.base;
0534     U32 const curr = (U32)(ip-base);
0535     U32 const hashLog = cParams->hashLog;
0536     U32 const minMatch = (mls==3) ? 3 : 4;
0537     U32* const hashTable = ms->hashTable;
0538     size_t const h  = ZSTD_hashPtr(ip, hashLog, mls);
0539     U32 matchIndex  = hashTable[h];
0540     U32* const bt   = ms->chainTable;
0541     U32 const btLog = cParams->chainLog - 1;
0542     U32 const btMask= (1U << btLog) - 1;
0543     size_t commonLengthSmaller=0, commonLengthLarger=0;
0544     const BYTE* const dictBase = ms->window.dictBase;
0545     U32 const dictLimit = ms->window.dictLimit;
0546     const BYTE* const dictEnd = dictBase + dictLimit;
0547     const BYTE* const prefixStart = base + dictLimit;
0548     U32 const btLow = (btMask >= curr) ? 0 : curr - btMask;
0549     U32 const windowLow = ZSTD_getLowestMatchIndex(ms, curr, cParams->windowLog);
0550     U32 const matchLow = windowLow ? windowLow : 1;
0551     U32* smallerPtr = bt + 2*(curr&btMask);
0552     U32* largerPtr  = bt + 2*(curr&btMask) + 1;
0553     U32 matchEndIdx = curr+8+1;   /* farthest referenced position of any match => detects repetitive patterns */
0554     U32 dummy32;   /* to be nullified at the end */
0555     U32 mnum = 0;
0556     U32 nbCompares = 1U << cParams->searchLog;
0557 
0558     const ZSTD_matchState_t* dms    = dictMode == ZSTD_dictMatchState ? ms->dictMatchState : NULL;
0559     const ZSTD_compressionParameters* const dmsCParams =
0560                                       dictMode == ZSTD_dictMatchState ? &dms->cParams : NULL;
0561     const BYTE* const dmsBase       = dictMode == ZSTD_dictMatchState ? dms->window.base : NULL;
0562     const BYTE* const dmsEnd        = dictMode == ZSTD_dictMatchState ? dms->window.nextSrc : NULL;
0563     U32         const dmsHighLimit  = dictMode == ZSTD_dictMatchState ? (U32)(dmsEnd - dmsBase) : 0;
0564     U32         const dmsLowLimit   = dictMode == ZSTD_dictMatchState ? dms->window.lowLimit : 0;
0565     U32         const dmsIndexDelta = dictMode == ZSTD_dictMatchState ? windowLow - dmsHighLimit : 0;
0566     U32         const dmsHashLog    = dictMode == ZSTD_dictMatchState ? dmsCParams->hashLog : hashLog;
0567     U32         const dmsBtLog      = dictMode == ZSTD_dictMatchState ? dmsCParams->chainLog - 1 : btLog;
0568     U32         const dmsBtMask     = dictMode == ZSTD_dictMatchState ? (1U << dmsBtLog) - 1 : 0;
0569     U32         const dmsBtLow      = dictMode == ZSTD_dictMatchState && dmsBtMask < dmsHighLimit - dmsLowLimit ? dmsHighLimit - dmsBtMask : dmsLowLimit;
0570 
0571     size_t bestLength = lengthToBeat-1;
0572     DEBUGLOG(8, "ZSTD_insertBtAndGetAllMatches: current=%u", curr);
0573 
0574     /* check repCode */
0575     assert(ll0 <= 1);   /* necessarily 1 or 0 */
0576     {   U32 const lastR = ZSTD_REP_NUM + ll0;
0577         U32 repCode;
0578         for (repCode = ll0; repCode < lastR; repCode++) {
0579             U32 const repOffset = (repCode==ZSTD_REP_NUM) ? (rep[0] - 1) : rep[repCode];
0580             U32 const repIndex = curr - repOffset;
0581             U32 repLen = 0;
0582             assert(curr >= dictLimit);
0583             if (repOffset-1 /* intentional overflow, discards 0 and -1 */ < curr-dictLimit) {  /* equivalent to `curr > repIndex >= dictLimit` */
0584                 /* We must validate the repcode offset because when we're using a dictionary the
0585                  * valid offset range shrinks when the dictionary goes out of bounds.
0586                  */
0587                 if ((repIndex >= windowLow) & (ZSTD_readMINMATCH(ip, minMatch) == ZSTD_readMINMATCH(ip - repOffset, minMatch))) {
0588                     repLen = (U32)ZSTD_count(ip+minMatch, ip+minMatch-repOffset, iLimit) + minMatch;
0589                 }
0590             } else {  /* repIndex < dictLimit || repIndex >= curr */
0591                 const BYTE* const repMatch = dictMode == ZSTD_dictMatchState ?
0592                                              dmsBase + repIndex - dmsIndexDelta :
0593                                              dictBase + repIndex;
0594                 assert(curr >= windowLow);
0595                 if ( dictMode == ZSTD_extDict
0596                   && ( ((repOffset-1) /*intentional overflow*/ < curr - windowLow)  /* equivalent to `curr > repIndex >= windowLow` */
0597                      & (((U32)((dictLimit-1) - repIndex) >= 3) ) /* intentional overflow : do not test positions overlapping 2 memory segments */)
0598                   && (ZSTD_readMINMATCH(ip, minMatch) == ZSTD_readMINMATCH(repMatch, minMatch)) ) {
0599                     repLen = (U32)ZSTD_count_2segments(ip+minMatch, repMatch+minMatch, iLimit, dictEnd, prefixStart) + minMatch;
0600                 }
0601                 if (dictMode == ZSTD_dictMatchState
0602                   && ( ((repOffset-1) /*intentional overflow*/ < curr - (dmsLowLimit + dmsIndexDelta))  /* equivalent to `curr > repIndex >= dmsLowLimit` */
0603                      & ((U32)((dictLimit-1) - repIndex) >= 3) ) /* intentional overflow : do not test positions overlapping 2 memory segments */
0604                   && (ZSTD_readMINMATCH(ip, minMatch) == ZSTD_readMINMATCH(repMatch, minMatch)) ) {
0605                     repLen = (U32)ZSTD_count_2segments(ip+minMatch, repMatch+minMatch, iLimit, dmsEnd, prefixStart) + minMatch;
0606             }   }
0607             /* save longer solution */
0608             if (repLen > bestLength) {
0609                 DEBUGLOG(8, "found repCode %u (ll0:%u, offset:%u) of length %u",
0610                             repCode, ll0, repOffset, repLen);
0611                 bestLength = repLen;
0612                 matches[mnum].off = repCode - ll0;
0613                 matches[mnum].len = (U32)repLen;
0614                 mnum++;
0615                 if ( (repLen > sufficient_len)
0616                    | (ip+repLen == iLimit) ) {  /* best possible */
0617                     return mnum;
0618     }   }   }   }
0619 
0620     /* HC3 match finder */
0621     if ((mls == 3) /*static*/ && (bestLength < mls)) {
0622         U32 const matchIndex3 = ZSTD_insertAndFindFirstIndexHash3(ms, nextToUpdate3, ip);
0623         if ((matchIndex3 >= matchLow)
0624           & (curr - matchIndex3 < (1<<18)) /*heuristic : longer distance likely too expensive*/ ) {
0625             size_t mlen;
0626             if ((dictMode == ZSTD_noDict) /*static*/ || (dictMode == ZSTD_dictMatchState) /*static*/ || (matchIndex3 >= dictLimit)) {
0627                 const BYTE* const match = base + matchIndex3;
0628                 mlen = ZSTD_count(ip, match, iLimit);
0629             } else {
0630                 const BYTE* const match = dictBase + matchIndex3;
0631                 mlen = ZSTD_count_2segments(ip, match, iLimit, dictEnd, prefixStart);
0632             }
0633 
0634             /* save best solution */
0635             if (mlen >= mls /* == 3 > bestLength */) {
0636                 DEBUGLOG(8, "found small match with hlog3, of length %u",
0637                             (U32)mlen);
0638                 bestLength = mlen;
0639                 assert(curr > matchIndex3);
0640                 assert(mnum==0);  /* no prior solution */
0641                 matches[0].off = (curr - matchIndex3) + ZSTD_REP_MOVE;
0642                 matches[0].len = (U32)mlen;
0643                 mnum = 1;
0644                 if ( (mlen > sufficient_len) |
0645                      (ip+mlen == iLimit) ) {  /* best possible length */
0646                     ms->nextToUpdate = curr+1;  /* skip insertion */
0647                     return 1;
0648         }   }   }
0649         /* no dictMatchState lookup: dicts don't have a populated HC3 table */
0650     }
0651 
0652     hashTable[h] = curr;   /* Update Hash Table */
0653 
0654     for (; nbCompares && (matchIndex >= matchLow); --nbCompares) {
0655         U32* const nextPtr = bt + 2*(matchIndex & btMask);
0656         const BYTE* match;
0657         size_t matchLength = MIN(commonLengthSmaller, commonLengthLarger);   /* guaranteed minimum nb of common bytes */
0658         assert(curr > matchIndex);
0659 
0660         if ((dictMode == ZSTD_noDict) || (dictMode == ZSTD_dictMatchState) || (matchIndex+matchLength >= dictLimit)) {
0661             assert(matchIndex+matchLength >= dictLimit);  /* ensure the condition is correct when !extDict */
0662             match = base + matchIndex;
0663             if (matchIndex >= dictLimit) assert(memcmp(match, ip, matchLength) == 0);  /* ensure early section of match is equal as expected */
0664             matchLength += ZSTD_count(ip+matchLength, match+matchLength, iLimit);
0665         } else {
0666             match = dictBase + matchIndex;
0667             assert(memcmp(match, ip, matchLength) == 0);  /* ensure early section of match is equal as expected */
0668             matchLength += ZSTD_count_2segments(ip+matchLength, match+matchLength, iLimit, dictEnd, prefixStart);
0669             if (matchIndex+matchLength >= dictLimit)
0670                 match = base + matchIndex;   /* prepare for match[matchLength] read */
0671         }
0672 
0673         if (matchLength > bestLength) {
0674             DEBUGLOG(8, "found match of length %u at distance %u (offCode=%u)",
0675                     (U32)matchLength, curr - matchIndex, curr - matchIndex + ZSTD_REP_MOVE);
0676             assert(matchEndIdx > matchIndex);
0677             if (matchLength > matchEndIdx - matchIndex)
0678                 matchEndIdx = matchIndex + (U32)matchLength;
0679             bestLength = matchLength;
0680             matches[mnum].off = (curr - matchIndex) + ZSTD_REP_MOVE;
0681             matches[mnum].len = (U32)matchLength;
0682             mnum++;
0683             if ( (matchLength > ZSTD_OPT_NUM)
0684                | (ip+matchLength == iLimit) /* equal : no way to know if inf or sup */) {
0685                 if (dictMode == ZSTD_dictMatchState) nbCompares = 0; /* break should also skip searching dms */
0686                 break; /* drop, to preserve bt consistency (miss a little bit of compression) */
0687             }
0688         }
0689 
0690         if (match[matchLength] < ip[matchLength]) {
0691             /* match smaller than current */
0692             *smallerPtr = matchIndex;             /* update smaller idx */
0693             commonLengthSmaller = matchLength;    /* all smaller will now have at least this guaranteed common length */
0694             if (matchIndex <= btLow) { smallerPtr=&dummy32; break; }   /* beyond tree size, stop the search */
0695             smallerPtr = nextPtr+1;               /* new candidate => larger than match, which was smaller than current */
0696             matchIndex = nextPtr[1];              /* new matchIndex, larger than previous, closer to current */
0697         } else {
0698             *largerPtr = matchIndex;
0699             commonLengthLarger = matchLength;
0700             if (matchIndex <= btLow) { largerPtr=&dummy32; break; }   /* beyond tree size, stop the search */
0701             largerPtr = nextPtr;
0702             matchIndex = nextPtr[0];
0703     }   }
0704 
0705     *smallerPtr = *largerPtr = 0;
0706 
0707     assert(nbCompares <= (1U << ZSTD_SEARCHLOG_MAX)); /* Check we haven't underflowed. */
0708     if (dictMode == ZSTD_dictMatchState && nbCompares) {
0709         size_t const dmsH = ZSTD_hashPtr(ip, dmsHashLog, mls);
0710         U32 dictMatchIndex = dms->hashTable[dmsH];
0711         const U32* const dmsBt = dms->chainTable;
0712         commonLengthSmaller = commonLengthLarger = 0;
0713         for (; nbCompares && (dictMatchIndex > dmsLowLimit); --nbCompares) {
0714             const U32* const nextPtr = dmsBt + 2*(dictMatchIndex & dmsBtMask);
0715             size_t matchLength = MIN(commonLengthSmaller, commonLengthLarger);   /* guaranteed minimum nb of common bytes */
0716             const BYTE* match = dmsBase + dictMatchIndex;
0717             matchLength += ZSTD_count_2segments(ip+matchLength, match+matchLength, iLimit, dmsEnd, prefixStart);
0718             if (dictMatchIndex+matchLength >= dmsHighLimit)
0719                 match = base + dictMatchIndex + dmsIndexDelta;   /* to prepare for next usage of match[matchLength] */
0720 
0721             if (matchLength > bestLength) {
0722                 matchIndex = dictMatchIndex + dmsIndexDelta;
0723                 DEBUGLOG(8, "found dms match of length %u at distance %u (offCode=%u)",
0724                         (U32)matchLength, curr - matchIndex, curr - matchIndex + ZSTD_REP_MOVE);
0725                 if (matchLength > matchEndIdx - matchIndex)
0726                     matchEndIdx = matchIndex + (U32)matchLength;
0727                 bestLength = matchLength;
0728                 matches[mnum].off = (curr - matchIndex) + ZSTD_REP_MOVE;
0729                 matches[mnum].len = (U32)matchLength;
0730                 mnum++;
0731                 if ( (matchLength > ZSTD_OPT_NUM)
0732                    | (ip+matchLength == iLimit) /* equal : no way to know if inf or sup */) {
0733                     break;   /* drop, to guarantee consistency (miss a little bit of compression) */
0734                 }
0735             }
0736 
0737             if (dictMatchIndex <= dmsBtLow) { break; }   /* beyond tree size, stop the search */
0738             if (match[matchLength] < ip[matchLength]) {
0739                 commonLengthSmaller = matchLength;    /* all smaller will now have at least this guaranteed common length */
0740                 dictMatchIndex = nextPtr[1];              /* new matchIndex larger than previous (closer to current) */
0741             } else {
0742                 /* match is larger than current */
0743                 commonLengthLarger = matchLength;
0744                 dictMatchIndex = nextPtr[0];
0745             }
0746         }
0747     }
0748 
0749     assert(matchEndIdx > curr+8);
0750     ms->nextToUpdate = matchEndIdx - 8;  /* skip repetitive patterns */
0751     return mnum;
0752 }
0753 
0754 
0755 FORCE_INLINE_TEMPLATE U32 ZSTD_BtGetAllMatches (
0756                         ZSTD_match_t* matches,   /* store result (match found, increasing size) in this table */
0757                         ZSTD_matchState_t* ms,
0758                         U32* nextToUpdate3,
0759                         const BYTE* ip, const BYTE* const iHighLimit, const ZSTD_dictMode_e dictMode,
0760                         const U32 rep[ZSTD_REP_NUM],
0761                         U32 const ll0,
0762                         U32 const lengthToBeat)
0763 {
0764     const ZSTD_compressionParameters* const cParams = &ms->cParams;
0765     U32 const matchLengthSearch = cParams->minMatch;
0766     DEBUGLOG(8, "ZSTD_BtGetAllMatches");
0767     if (ip < ms->window.base + ms->nextToUpdate) return 0;   /* skipped area */
0768     ZSTD_updateTree_internal(ms, ip, iHighLimit, matchLengthSearch, dictMode);
0769     switch(matchLengthSearch)
0770     {
0771     case 3 : return ZSTD_insertBtAndGetAllMatches(matches, ms, nextToUpdate3, ip, iHighLimit, dictMode, rep, ll0, lengthToBeat, 3);
0772     default :
0773     case 4 : return ZSTD_insertBtAndGetAllMatches(matches, ms, nextToUpdate3, ip, iHighLimit, dictMode, rep, ll0, lengthToBeat, 4);
0774     case 5 : return ZSTD_insertBtAndGetAllMatches(matches, ms, nextToUpdate3, ip, iHighLimit, dictMode, rep, ll0, lengthToBeat, 5);
0775     case 7 :
0776     case 6 : return ZSTD_insertBtAndGetAllMatches(matches, ms, nextToUpdate3, ip, iHighLimit, dictMode, rep, ll0, lengthToBeat, 6);
0777     }
0778 }
0779 
0780 /* ***********************
0781 *  LDM helper functions  *
0782 *************************/
0783 
0784 /* Struct containing info needed to make decision about ldm inclusion */
0785 typedef struct {
0786     rawSeqStore_t seqStore;         /* External match candidates store for this block */
0787     U32 startPosInBlock;            /* Start position of the current match candidate */
0788     U32 endPosInBlock;              /* End position of the current match candidate */
0789     U32 offset;                     /* Offset of the match candidate */
0790 } ZSTD_optLdm_t;
0791 
0792 /* ZSTD_optLdm_skipRawSeqStoreBytes():
0793  * Moves forward in rawSeqStore by nbBytes, which will update the fields 'pos' and 'posInSequence'.
0794  */
0795 static void ZSTD_optLdm_skipRawSeqStoreBytes(rawSeqStore_t* rawSeqStore, size_t nbBytes) {
0796     U32 currPos = (U32)(rawSeqStore->posInSequence + nbBytes);
0797     while (currPos && rawSeqStore->pos < rawSeqStore->size) {
0798         rawSeq currSeq = rawSeqStore->seq[rawSeqStore->pos];
0799         if (currPos >= currSeq.litLength + currSeq.matchLength) {
0800             currPos -= currSeq.litLength + currSeq.matchLength;
0801             rawSeqStore->pos++;
0802         } else {
0803             rawSeqStore->posInSequence = currPos;
0804             break;
0805         }
0806     }
0807     if (currPos == 0 || rawSeqStore->pos == rawSeqStore->size) {
0808         rawSeqStore->posInSequence = 0;
0809     }
0810 }
0811 
0812 /* ZSTD_opt_getNextMatchAndUpdateSeqStore():
0813  * Calculates the beginning and end of the next match in the current block.
0814  * Updates 'pos' and 'posInSequence' of the ldmSeqStore.
0815  */
0816 static void ZSTD_opt_getNextMatchAndUpdateSeqStore(ZSTD_optLdm_t* optLdm, U32 currPosInBlock,
0817                                                    U32 blockBytesRemaining) {
0818     rawSeq currSeq;
0819     U32 currBlockEndPos;
0820     U32 literalsBytesRemaining;
0821     U32 matchBytesRemaining;
0822 
0823     /* Setting match end position to MAX to ensure we never use an LDM during this block */
0824     if (optLdm->seqStore.size == 0 || optLdm->seqStore.pos >= optLdm->seqStore.size) {
0825         optLdm->startPosInBlock = UINT_MAX;
0826         optLdm->endPosInBlock = UINT_MAX;
0827         return;
0828     }
0829     /* Calculate appropriate bytes left in matchLength and litLength after adjusting
0830        based on ldmSeqStore->posInSequence */
0831     currSeq = optLdm->seqStore.seq[optLdm->seqStore.pos];
0832     assert(optLdm->seqStore.posInSequence <= currSeq.litLength + currSeq.matchLength);
0833     currBlockEndPos = currPosInBlock + blockBytesRemaining;
0834     literalsBytesRemaining = (optLdm->seqStore.posInSequence < currSeq.litLength) ?
0835             currSeq.litLength - (U32)optLdm->seqStore.posInSequence :
0836             0;
0837     matchBytesRemaining = (literalsBytesRemaining == 0) ?
0838             currSeq.matchLength - ((U32)optLdm->seqStore.posInSequence - currSeq.litLength) :
0839             currSeq.matchLength;
0840 
0841     /* If there are more literal bytes than bytes remaining in block, no ldm is possible */
0842     if (literalsBytesRemaining >= blockBytesRemaining) {
0843         optLdm->startPosInBlock = UINT_MAX;
0844         optLdm->endPosInBlock = UINT_MAX;
0845         ZSTD_optLdm_skipRawSeqStoreBytes(&optLdm->seqStore, blockBytesRemaining);
0846         return;
0847     }
0848 
0849     /* Matches may be < MINMATCH by this process. In that case, we will reject them
0850        when we are deciding whether or not to add the ldm */
0851     optLdm->startPosInBlock = currPosInBlock + literalsBytesRemaining;
0852     optLdm->endPosInBlock = optLdm->startPosInBlock + matchBytesRemaining;
0853     optLdm->offset = currSeq.offset;
0854 
0855     if (optLdm->endPosInBlock > currBlockEndPos) {
0856         /* Match ends after the block ends, we can't use the whole match */
0857         optLdm->endPosInBlock = currBlockEndPos;
0858         ZSTD_optLdm_skipRawSeqStoreBytes(&optLdm->seqStore, currBlockEndPos - currPosInBlock);
0859     } else {
0860         /* Consume nb of bytes equal to size of sequence left */
0861         ZSTD_optLdm_skipRawSeqStoreBytes(&optLdm->seqStore, literalsBytesRemaining + matchBytesRemaining);
0862     }
0863 }
0864 
0865 /* ZSTD_optLdm_maybeAddMatch():
0866  * Adds a match if it's long enough, based on it's 'matchStartPosInBlock'
0867  * and 'matchEndPosInBlock', into 'matches'. Maintains the correct ordering of 'matches'
0868  */
0869 static void ZSTD_optLdm_maybeAddMatch(ZSTD_match_t* matches, U32* nbMatches,
0870                                       ZSTD_optLdm_t* optLdm, U32 currPosInBlock) {
0871     U32 posDiff = currPosInBlock - optLdm->startPosInBlock;
0872     /* Note: ZSTD_match_t actually contains offCode and matchLength (before subtracting MINMATCH) */
0873     U32 candidateMatchLength = optLdm->endPosInBlock - optLdm->startPosInBlock - posDiff;
0874     U32 candidateOffCode = optLdm->offset + ZSTD_REP_MOVE;
0875 
0876     /* Ensure that current block position is not outside of the match */
0877     if (currPosInBlock < optLdm->startPosInBlock
0878       || currPosInBlock >= optLdm->endPosInBlock
0879       || candidateMatchLength < MINMATCH) {
0880         return;
0881     }
0882 
0883     if (*nbMatches == 0 || ((candidateMatchLength > matches[*nbMatches-1].len) && *nbMatches < ZSTD_OPT_NUM)) {
0884         DEBUGLOG(6, "ZSTD_optLdm_maybeAddMatch(): Adding ldm candidate match (offCode: %u matchLength %u) at block position=%u",
0885                  candidateOffCode, candidateMatchLength, currPosInBlock);
0886         matches[*nbMatches].len = candidateMatchLength;
0887         matches[*nbMatches].off = candidateOffCode;
0888         (*nbMatches)++;
0889     }
0890 }
0891 
0892 /* ZSTD_optLdm_processMatchCandidate():
0893  * Wrapper function to update ldm seq store and call ldm functions as necessary.
0894  */
0895 static void ZSTD_optLdm_processMatchCandidate(ZSTD_optLdm_t* optLdm, ZSTD_match_t* matches, U32* nbMatches,
0896                                               U32 currPosInBlock, U32 remainingBytes) {
0897     if (optLdm->seqStore.size == 0 || optLdm->seqStore.pos >= optLdm->seqStore.size) {
0898         return;
0899     }
0900 
0901     if (currPosInBlock >= optLdm->endPosInBlock) {
0902         if (currPosInBlock > optLdm->endPosInBlock) {
0903             /* The position at which ZSTD_optLdm_processMatchCandidate() is called is not necessarily
0904              * at the end of a match from the ldm seq store, and will often be some bytes
0905              * over beyond matchEndPosInBlock. As such, we need to correct for these "overshoots"
0906              */
0907             U32 posOvershoot = currPosInBlock - optLdm->endPosInBlock;
0908             ZSTD_optLdm_skipRawSeqStoreBytes(&optLdm->seqStore, posOvershoot);
0909         } 
0910         ZSTD_opt_getNextMatchAndUpdateSeqStore(optLdm, currPosInBlock, remainingBytes);
0911     }
0912     ZSTD_optLdm_maybeAddMatch(matches, nbMatches, optLdm, currPosInBlock);
0913 }
0914 
0915 /*-*******************************
0916 *  Optimal parser
0917 *********************************/
0918 
0919 
0920 static U32 ZSTD_totalLen(ZSTD_optimal_t sol)
0921 {
0922     return sol.litlen + sol.mlen;
0923 }
0924 
0925 #if 0 /* debug */
0926 
0927 static void
0928 listStats(const U32* table, int lastEltID)
0929 {
0930     int const nbElts = lastEltID + 1;
0931     int enb;
0932     for (enb=0; enb < nbElts; enb++) {
0933         (void)table;
0934         /* RAWLOG(2, "%3i:%3i,  ", enb, table[enb]); */
0935         RAWLOG(2, "%4i,", table[enb]);
0936     }
0937     RAWLOG(2, " \n");
0938 }
0939 
0940 #endif
0941 
0942 FORCE_INLINE_TEMPLATE size_t
0943 ZSTD_compressBlock_opt_generic(ZSTD_matchState_t* ms,
0944                                seqStore_t* seqStore,
0945                                U32 rep[ZSTD_REP_NUM],
0946                          const void* src, size_t srcSize,
0947                          const int optLevel,
0948                          const ZSTD_dictMode_e dictMode)
0949 {
0950     optState_t* const optStatePtr = &ms->opt;
0951     const BYTE* const istart = (const BYTE*)src;
0952     const BYTE* ip = istart;
0953     const BYTE* anchor = istart;
0954     const BYTE* const iend = istart + srcSize;
0955     const BYTE* const ilimit = iend - 8;
0956     const BYTE* const base = ms->window.base;
0957     const BYTE* const prefixStart = base + ms->window.dictLimit;
0958     const ZSTD_compressionParameters* const cParams = &ms->cParams;
0959 
0960     U32 const sufficient_len = MIN(cParams->targetLength, ZSTD_OPT_NUM -1);
0961     U32 const minMatch = (cParams->minMatch == 3) ? 3 : 4;
0962     U32 nextToUpdate3 = ms->nextToUpdate;
0963 
0964     ZSTD_optimal_t* const opt = optStatePtr->priceTable;
0965     ZSTD_match_t* const matches = optStatePtr->matchTable;
0966     ZSTD_optimal_t lastSequence;
0967     ZSTD_optLdm_t optLdm;
0968 
0969     optLdm.seqStore = ms->ldmSeqStore ? *ms->ldmSeqStore : kNullRawSeqStore;
0970     optLdm.endPosInBlock = optLdm.startPosInBlock = optLdm.offset = 0;
0971     ZSTD_opt_getNextMatchAndUpdateSeqStore(&optLdm, (U32)(ip-istart), (U32)(iend-ip));
0972 
0973     /* init */
0974     DEBUGLOG(5, "ZSTD_compressBlock_opt_generic: current=%u, prefix=%u, nextToUpdate=%u",
0975                 (U32)(ip - base), ms->window.dictLimit, ms->nextToUpdate);
0976     assert(optLevel <= 2);
0977     ZSTD_rescaleFreqs(optStatePtr, (const BYTE*)src, srcSize, optLevel);
0978     ip += (ip==prefixStart);
0979 
0980     /* Match Loop */
0981     while (ip < ilimit) {
0982         U32 cur, last_pos = 0;
0983 
0984         /* find first match */
0985         {   U32 const litlen = (U32)(ip - anchor);
0986             U32 const ll0 = !litlen;
0987             U32 nbMatches = ZSTD_BtGetAllMatches(matches, ms, &nextToUpdate3, ip, iend, dictMode, rep, ll0, minMatch);
0988             ZSTD_optLdm_processMatchCandidate(&optLdm, matches, &nbMatches,
0989                                               (U32)(ip-istart), (U32)(iend - ip));
0990             if (!nbMatches) { ip++; continue; }
0991 
0992             /* initialize opt[0] */
0993             { U32 i ; for (i=0; i<ZSTD_REP_NUM; i++) opt[0].rep[i] = rep[i]; }
0994             opt[0].mlen = 0;  /* means is_a_literal */
0995             opt[0].litlen = litlen;
0996             /* We don't need to include the actual price of the literals because
0997              * it is static for the duration of the forward pass, and is included
0998              * in every price. We include the literal length to avoid negative
0999              * prices when we subtract the previous literal length.
1000              */
1001             opt[0].price = ZSTD_litLengthPrice(litlen, optStatePtr, optLevel);
1002 
1003             /* large match -> immediate encoding */
1004             {   U32 const maxML = matches[nbMatches-1].len;
1005                 U32 const maxOffset = matches[nbMatches-1].off;
1006                 DEBUGLOG(6, "found %u matches of maxLength=%u and maxOffCode=%u at cPos=%u => start new series",
1007                             nbMatches, maxML, maxOffset, (U32)(ip-prefixStart));
1008 
1009                 if (maxML > sufficient_len) {
1010                     lastSequence.litlen = litlen;
1011                     lastSequence.mlen = maxML;
1012                     lastSequence.off = maxOffset;
1013                     DEBUGLOG(6, "large match (%u>%u), immediate encoding",
1014                                 maxML, sufficient_len);
1015                     cur = 0;
1016                     last_pos = ZSTD_totalLen(lastSequence);
1017                     goto _shortestPath;
1018             }   }
1019 
1020             /* set prices for first matches starting position == 0 */
1021             {   U32 const literalsPrice = opt[0].price + ZSTD_litLengthPrice(0, optStatePtr, optLevel);
1022                 U32 pos;
1023                 U32 matchNb;
1024                 for (pos = 1; pos < minMatch; pos++) {
1025                     opt[pos].price = ZSTD_MAX_PRICE;   /* mlen, litlen and price will be fixed during forward scanning */
1026                 }
1027                 for (matchNb = 0; matchNb < nbMatches; matchNb++) {
1028                     U32 const offset = matches[matchNb].off;
1029                     U32 const end = matches[matchNb].len;
1030                     for ( ; pos <= end ; pos++ ) {
1031                         U32 const matchPrice = ZSTD_getMatchPrice(offset, pos, optStatePtr, optLevel);
1032                         U32 const sequencePrice = literalsPrice + matchPrice;
1033                         DEBUGLOG(7, "rPos:%u => set initial price : %.2f",
1034                                     pos, ZSTD_fCost(sequencePrice));
1035                         opt[pos].mlen = pos;
1036                         opt[pos].off = offset;
1037                         opt[pos].litlen = litlen;
1038                         opt[pos].price = sequencePrice;
1039                 }   }
1040                 last_pos = pos-1;
1041             }
1042         }
1043 
1044         /* check further positions */
1045         for (cur = 1; cur <= last_pos; cur++) {
1046             const BYTE* const inr = ip + cur;
1047             assert(cur < ZSTD_OPT_NUM);
1048             DEBUGLOG(7, "cPos:%zi==rPos:%u", inr-istart, cur)
1049 
1050             /* Fix current position with one literal if cheaper */
1051             {   U32 const litlen = (opt[cur-1].mlen == 0) ? opt[cur-1].litlen + 1 : 1;
1052                 int const price = opt[cur-1].price
1053                                 + ZSTD_rawLiteralsCost(ip+cur-1, 1, optStatePtr, optLevel)
1054                                 + ZSTD_litLengthPrice(litlen, optStatePtr, optLevel)
1055                                 - ZSTD_litLengthPrice(litlen-1, optStatePtr, optLevel);
1056                 assert(price < 1000000000); /* overflow check */
1057                 if (price <= opt[cur].price) {
1058                     DEBUGLOG(7, "cPos:%zi==rPos:%u : better price (%.2f<=%.2f) using literal (ll==%u) (hist:%u,%u,%u)",
1059                                 inr-istart, cur, ZSTD_fCost(price), ZSTD_fCost(opt[cur].price), litlen,
1060                                 opt[cur-1].rep[0], opt[cur-1].rep[1], opt[cur-1].rep[2]);
1061                     opt[cur].mlen = 0;
1062                     opt[cur].off = 0;
1063                     opt[cur].litlen = litlen;
1064                     opt[cur].price = price;
1065                 } else {
1066                     DEBUGLOG(7, "cPos:%zi==rPos:%u : literal would cost more (%.2f>%.2f) (hist:%u,%u,%u)",
1067                                 inr-istart, cur, ZSTD_fCost(price), ZSTD_fCost(opt[cur].price),
1068                                 opt[cur].rep[0], opt[cur].rep[1], opt[cur].rep[2]);
1069                 }
1070             }
1071 
1072             /* Set the repcodes of the current position. We must do it here
1073              * because we rely on the repcodes of the 2nd to last sequence being
1074              * correct to set the next chunks repcodes during the backward
1075              * traversal.
1076              */
1077             ZSTD_STATIC_ASSERT(sizeof(opt[cur].rep) == sizeof(repcodes_t));
1078             assert(cur >= opt[cur].mlen);
1079             if (opt[cur].mlen != 0) {
1080                 U32 const prev = cur - opt[cur].mlen;
1081                 repcodes_t newReps = ZSTD_updateRep(opt[prev].rep, opt[cur].off, opt[cur].litlen==0);
1082                 ZSTD_memcpy(opt[cur].rep, &newReps, sizeof(repcodes_t));
1083             } else {
1084                 ZSTD_memcpy(opt[cur].rep, opt[cur - 1].rep, sizeof(repcodes_t));
1085             }
1086 
1087             /* last match must start at a minimum distance of 8 from oend */
1088             if (inr > ilimit) continue;
1089 
1090             if (cur == last_pos) break;
1091 
1092             if ( (optLevel==0) /*static_test*/
1093               && (opt[cur+1].price <= opt[cur].price + (BITCOST_MULTIPLIER/2)) ) {
1094                 DEBUGLOG(7, "move to next rPos:%u : price is <=", cur+1);
1095                 continue;  /* skip unpromising positions; about ~+6% speed, -0.01 ratio */
1096             }
1097 
1098             {   U32 const ll0 = (opt[cur].mlen != 0);
1099                 U32 const litlen = (opt[cur].mlen == 0) ? opt[cur].litlen : 0;
1100                 U32 const previousPrice = opt[cur].price;
1101                 U32 const basePrice = previousPrice + ZSTD_litLengthPrice(0, optStatePtr, optLevel);
1102                 U32 nbMatches = ZSTD_BtGetAllMatches(matches, ms, &nextToUpdate3, inr, iend, dictMode, opt[cur].rep, ll0, minMatch);
1103                 U32 matchNb;
1104 
1105                 ZSTD_optLdm_processMatchCandidate(&optLdm, matches, &nbMatches,
1106                                                   (U32)(inr-istart), (U32)(iend-inr));
1107 
1108                 if (!nbMatches) {
1109                     DEBUGLOG(7, "rPos:%u : no match found", cur);
1110                     continue;
1111                 }
1112 
1113                 {   U32 const maxML = matches[nbMatches-1].len;
1114                     DEBUGLOG(7, "cPos:%zi==rPos:%u, found %u matches, of maxLength=%u",
1115                                 inr-istart, cur, nbMatches, maxML);
1116 
1117                     if ( (maxML > sufficient_len)
1118                       || (cur + maxML >= ZSTD_OPT_NUM) ) {
1119                         lastSequence.mlen = maxML;
1120                         lastSequence.off = matches[nbMatches-1].off;
1121                         lastSequence.litlen = litlen;
1122                         cur -= (opt[cur].mlen==0) ? opt[cur].litlen : 0;  /* last sequence is actually only literals, fix cur to last match - note : may underflow, in which case, it's first sequence, and it's okay */
1123                         last_pos = cur + ZSTD_totalLen(lastSequence);
1124                         if (cur > ZSTD_OPT_NUM) cur = 0;   /* underflow => first match */
1125                         goto _shortestPath;
1126                 }   }
1127 
1128                 /* set prices using matches found at position == cur */
1129                 for (matchNb = 0; matchNb < nbMatches; matchNb++) {
1130                     U32 const offset = matches[matchNb].off;
1131                     U32 const lastML = matches[matchNb].len;
1132                     U32 const startML = (matchNb>0) ? matches[matchNb-1].len+1 : minMatch;
1133                     U32 mlen;
1134 
1135                     DEBUGLOG(7, "testing match %u => offCode=%4u, mlen=%2u, llen=%2u",
1136                                 matchNb, matches[matchNb].off, lastML, litlen);
1137 
1138                     for (mlen = lastML; mlen >= startML; mlen--) {  /* scan downward */
1139                         U32 const pos = cur + mlen;
1140                         int const price = basePrice + ZSTD_getMatchPrice(offset, mlen, optStatePtr, optLevel);
1141 
1142                         if ((pos > last_pos) || (price < opt[pos].price)) {
1143                             DEBUGLOG(7, "rPos:%u (ml=%2u) => new better price (%.2f<%.2f)",
1144                                         pos, mlen, ZSTD_fCost(price), ZSTD_fCost(opt[pos].price));
1145                             while (last_pos < pos) { opt[last_pos+1].price = ZSTD_MAX_PRICE; last_pos++; }   /* fill empty positions */
1146                             opt[pos].mlen = mlen;
1147                             opt[pos].off = offset;
1148                             opt[pos].litlen = litlen;
1149                             opt[pos].price = price;
1150                         } else {
1151                             DEBUGLOG(7, "rPos:%u (ml=%2u) => new price is worse (%.2f>=%.2f)",
1152                                         pos, mlen, ZSTD_fCost(price), ZSTD_fCost(opt[pos].price));
1153                             if (optLevel==0) break;  /* early update abort; gets ~+10% speed for about -0.01 ratio loss */
1154                         }
1155             }   }   }
1156         }  /* for (cur = 1; cur <= last_pos; cur++) */
1157 
1158         lastSequence = opt[last_pos];
1159         cur = last_pos > ZSTD_totalLen(lastSequence) ? last_pos - ZSTD_totalLen(lastSequence) : 0;  /* single sequence, and it starts before `ip` */
1160         assert(cur < ZSTD_OPT_NUM);  /* control overflow*/
1161 
1162 _shortestPath:   /* cur, last_pos, best_mlen, best_off have to be set */
1163         assert(opt[0].mlen == 0);
1164 
1165         /* Set the next chunk's repcodes based on the repcodes of the beginning
1166          * of the last match, and the last sequence. This avoids us having to
1167          * update them while traversing the sequences.
1168          */
1169         if (lastSequence.mlen != 0) {
1170             repcodes_t reps = ZSTD_updateRep(opt[cur].rep, lastSequence.off, lastSequence.litlen==0);
1171             ZSTD_memcpy(rep, &reps, sizeof(reps));
1172         } else {
1173             ZSTD_memcpy(rep, opt[cur].rep, sizeof(repcodes_t));
1174         }
1175 
1176         {   U32 const storeEnd = cur + 1;
1177             U32 storeStart = storeEnd;
1178             U32 seqPos = cur;
1179 
1180             DEBUGLOG(6, "start reverse traversal (last_pos:%u, cur:%u)",
1181                         last_pos, cur); (void)last_pos;
1182             assert(storeEnd < ZSTD_OPT_NUM);
1183             DEBUGLOG(6, "last sequence copied into pos=%u (llen=%u,mlen=%u,ofc=%u)",
1184                         storeEnd, lastSequence.litlen, lastSequence.mlen, lastSequence.off);
1185             opt[storeEnd] = lastSequence;
1186             while (seqPos > 0) {
1187                 U32 const backDist = ZSTD_totalLen(opt[seqPos]);
1188                 storeStart--;
1189                 DEBUGLOG(6, "sequence from rPos=%u copied into pos=%u (llen=%u,mlen=%u,ofc=%u)",
1190                             seqPos, storeStart, opt[seqPos].litlen, opt[seqPos].mlen, opt[seqPos].off);
1191                 opt[storeStart] = opt[seqPos];
1192                 seqPos = (seqPos > backDist) ? seqPos - backDist : 0;
1193             }
1194 
1195             /* save sequences */
1196             DEBUGLOG(6, "sending selected sequences into seqStore")
1197             {   U32 storePos;
1198                 for (storePos=storeStart; storePos <= storeEnd; storePos++) {
1199                     U32 const llen = opt[storePos].litlen;
1200                     U32 const mlen = opt[storePos].mlen;
1201                     U32 const offCode = opt[storePos].off;
1202                     U32 const advance = llen + mlen;
1203                     DEBUGLOG(6, "considering seq starting at %zi, llen=%u, mlen=%u",
1204                                 anchor - istart, (unsigned)llen, (unsigned)mlen);
1205 
1206                     if (mlen==0) {  /* only literals => must be last "sequence", actually starting a new stream of sequences */
1207                         assert(storePos == storeEnd);   /* must be last sequence */
1208                         ip = anchor + llen;     /* last "sequence" is a bunch of literals => don't progress anchor */
1209                         continue;   /* will finish */
1210                     }
1211 
1212                     assert(anchor + llen <= iend);
1213                     ZSTD_updateStats(optStatePtr, llen, anchor, offCode, mlen);
1214                     ZSTD_storeSeq(seqStore, llen, anchor, iend, offCode, mlen-MINMATCH);
1215                     anchor += advance;
1216                     ip = anchor;
1217             }   }
1218             ZSTD_setBasePrices(optStatePtr, optLevel);
1219         }
1220     }   /* while (ip < ilimit) */
1221 
1222     /* Return the last literals size */
1223     return (size_t)(iend - anchor);
1224 }
1225 
1226 
1227 size_t ZSTD_compressBlock_btopt(
1228         ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],
1229         const void* src, size_t srcSize)
1230 {
1231     DEBUGLOG(5, "ZSTD_compressBlock_btopt");
1232     return ZSTD_compressBlock_opt_generic(ms, seqStore, rep, src, srcSize, 0 /*optLevel*/, ZSTD_noDict);
1233 }
1234 
1235 
1236 /* used in 2-pass strategy */
1237 static U32 ZSTD_upscaleStat(unsigned* table, U32 lastEltIndex, int bonus)
1238 {
1239     U32 s, sum=0;
1240     assert(ZSTD_FREQ_DIV+bonus >= 0);
1241     for (s=0; s<lastEltIndex+1; s++) {
1242         table[s] <<= ZSTD_FREQ_DIV+bonus;
1243         table[s]--;
1244         sum += table[s];
1245     }
1246     return sum;
1247 }
1248 
1249 /* used in 2-pass strategy */
1250 MEM_STATIC void ZSTD_upscaleStats(optState_t* optPtr)
1251 {
1252     if (ZSTD_compressedLiterals(optPtr))
1253         optPtr->litSum = ZSTD_upscaleStat(optPtr->litFreq, MaxLit, 0);
1254     optPtr->litLengthSum = ZSTD_upscaleStat(optPtr->litLengthFreq, MaxLL, 0);
1255     optPtr->matchLengthSum = ZSTD_upscaleStat(optPtr->matchLengthFreq, MaxML, 0);
1256     optPtr->offCodeSum = ZSTD_upscaleStat(optPtr->offCodeFreq, MaxOff, 0);
1257 }
1258 
1259 /* ZSTD_initStats_ultra():
1260  * make a first compression pass, just to seed stats with more accurate starting values.
1261  * only works on first block, with no dictionary and no ldm.
1262  * this function cannot error, hence its contract must be respected.
1263  */
1264 static void
1265 ZSTD_initStats_ultra(ZSTD_matchState_t* ms,
1266                      seqStore_t* seqStore,
1267                      U32 rep[ZSTD_REP_NUM],
1268                const void* src, size_t srcSize)
1269 {
1270     U32 tmpRep[ZSTD_REP_NUM];  /* updated rep codes will sink here */
1271     ZSTD_memcpy(tmpRep, rep, sizeof(tmpRep));
1272 
1273     DEBUGLOG(4, "ZSTD_initStats_ultra (srcSize=%zu)", srcSize);
1274     assert(ms->opt.litLengthSum == 0);    /* first block */
1275     assert(seqStore->sequences == seqStore->sequencesStart);   /* no ldm */
1276     assert(ms->window.dictLimit == ms->window.lowLimit);   /* no dictionary */
1277     assert(ms->window.dictLimit - ms->nextToUpdate <= 1);  /* no prefix (note: intentional overflow, defined as 2-complement) */
1278 
1279     ZSTD_compressBlock_opt_generic(ms, seqStore, tmpRep, src, srcSize, 2 /*optLevel*/, ZSTD_noDict);   /* generate stats into ms->opt*/
1280 
1281     /* invalidate first scan from history */
1282     ZSTD_resetSeqStore(seqStore);
1283     ms->window.base -= srcSize;
1284     ms->window.dictLimit += (U32)srcSize;
1285     ms->window.lowLimit = ms->window.dictLimit;
1286     ms->nextToUpdate = ms->window.dictLimit;
1287 
1288     /* re-inforce weight of collected statistics */
1289     ZSTD_upscaleStats(&ms->opt);
1290 }
1291 
1292 size_t ZSTD_compressBlock_btultra(
1293         ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],
1294         const void* src, size_t srcSize)
1295 {
1296     DEBUGLOG(5, "ZSTD_compressBlock_btultra (srcSize=%zu)", srcSize);
1297     return ZSTD_compressBlock_opt_generic(ms, seqStore, rep, src, srcSize, 2 /*optLevel*/, ZSTD_noDict);
1298 }
1299 
1300 size_t ZSTD_compressBlock_btultra2(
1301         ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],
1302         const void* src, size_t srcSize)
1303 {
1304     U32 const curr = (U32)((const BYTE*)src - ms->window.base);
1305     DEBUGLOG(5, "ZSTD_compressBlock_btultra2 (srcSize=%zu)", srcSize);
1306 
1307     /* 2-pass strategy:
1308      * this strategy makes a first pass over first block to collect statistics
1309      * and seed next round's statistics with it.
1310      * After 1st pass, function forgets everything, and starts a new block.
1311      * Consequently, this can only work if no data has been previously loaded in tables,
1312      * aka, no dictionary, no prefix, no ldm preprocessing.
1313      * The compression ratio gain is generally small (~0.5% on first block),
1314      * the cost is 2x cpu time on first block. */
1315     assert(srcSize <= ZSTD_BLOCKSIZE_MAX);
1316     if ( (ms->opt.litLengthSum==0)   /* first block */
1317       && (seqStore->sequences == seqStore->sequencesStart)  /* no ldm */
1318       && (ms->window.dictLimit == ms->window.lowLimit)   /* no dictionary */
1319       && (curr == ms->window.dictLimit)   /* start of frame, nothing already loaded nor skipped */
1320       && (srcSize > ZSTD_PREDEF_THRESHOLD)
1321       ) {
1322         ZSTD_initStats_ultra(ms, seqStore, rep, src, srcSize);
1323     }
1324 
1325     return ZSTD_compressBlock_opt_generic(ms, seqStore, rep, src, srcSize, 2 /*optLevel*/, ZSTD_noDict);
1326 }
1327 
1328 size_t ZSTD_compressBlock_btopt_dictMatchState(
1329         ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],
1330         const void* src, size_t srcSize)
1331 {
1332     return ZSTD_compressBlock_opt_generic(ms, seqStore, rep, src, srcSize, 0 /*optLevel*/, ZSTD_dictMatchState);
1333 }
1334 
1335 size_t ZSTD_compressBlock_btultra_dictMatchState(
1336         ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],
1337         const void* src, size_t srcSize)
1338 {
1339     return ZSTD_compressBlock_opt_generic(ms, seqStore, rep, src, srcSize, 2 /*optLevel*/, ZSTD_dictMatchState);
1340 }
1341 
1342 size_t ZSTD_compressBlock_btopt_extDict(
1343         ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],
1344         const void* src, size_t srcSize)
1345 {
1346     return ZSTD_compressBlock_opt_generic(ms, seqStore, rep, src, srcSize, 0 /*optLevel*/, ZSTD_extDict);
1347 }
1348 
1349 size_t ZSTD_compressBlock_btultra_extDict(
1350         ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],
1351         const void* src, size_t srcSize)
1352 {
1353     return ZSTD_compressBlock_opt_generic(ms, seqStore, rep, src, srcSize, 2 /*optLevel*/, ZSTD_extDict);
1354 }
1355 
1356 /* note : no btultra2 variant for extDict nor dictMatchState,
1357  * because btultra2 is not meant to work with dictionaries
1358  * and is only specific for the first block (no prefix) */
[ Source navigation ] [ Diff markup ] [ Identifier search ] [ general search ]

This page was automatically generated by the 2.1.0 LXR engine.

The LXR team
Valid CSS 2.1! Valid HTML 4.01!