21 #define ZSTD_NO_INLINE 1
30 #define ZSTD_MAX_PRICE     (1<<30)
41 #  define BITCOST_MULTIPLIER (1 << BITCOST_ACCURACY)
45 #  define BITCOST_MULTIPLIER (1 << BITCOST_ACCURACY)
49 #  define BITCOST_MULTIPLIER (1 << BITCOST_ACCURACY)
55     return (ZSTD_highbit32(stat+1) * BITCOST_MULTIPLIER);  in ZSTD_bitWeight()
60     U32 const stat = rawStat + 1;  in ZSTD_fracWeight()
100     DEBUGLOG(5, "ZSTD_downscaleStat (nbElts=%u)", (unsigned)lastEltIndex+1);  in ZSTD_downscaleStat()
102     for (s=0; s<lastEltIndex+1; s++) {  in ZSTD_downscaleStat()
103         table[s] = 1 + (table[s] >> (ZSTD_FREQ_DIV+malus));  in ZSTD_downscaleStat()
112  *    or init from zero, using src for literals stats, or flat 1 for match symbols
143 …        optPtr->litFreq[lit] = bitCost ? 1 << (scaleLog-bitCost) : 1 /*minimum to calculate cost*/;  in ZSTD_rescaleFreqs()
152                     U32 const scaleLog = 10;   /* scale to 1K */  in ZSTD_rescaleFreqs()
155 …   optPtr->litLengthFreq[ll] = bitCost ? 1 << (scaleLog-bitCost) : 1 /*minimum to calculate cost*/;  in ZSTD_rescaleFreqs()
167 … optPtr->matchLengthFreq[ml] = bitCost ? 1 << (scaleLog-bitCost) : 1 /*minimum to calculate cost*/;  in ZSTD_rescaleFreqs()
179 …     optPtr->offCodeFreq[of] = bitCost ? 1 << (scaleLog-bitCost) : 1 /*minimum to calculate cost*/;  in ZSTD_rescaleFreqs()
189                 optPtr->litSum = ZSTD_downscaleStat(optPtr->litFreq, MaxLit, 1);  in ZSTD_rescaleFreqs()
194                     optPtr->litLengthFreq[ll] = 1;  in ZSTD_rescaleFreqs()
196             optPtr->litLengthSum = MaxLL+1;  in ZSTD_rescaleFreqs()
200                     optPtr->matchLengthFreq[ml] = 1;  in ZSTD_rescaleFreqs()
202             optPtr->matchLengthSum = MaxML+1;  in ZSTD_rescaleFreqs()
206                     optPtr->offCodeFreq[of] = 1;  in ZSTD_rescaleFreqs()
208             optPtr->offCodeSum = MaxOff+1;  in ZSTD_rescaleFreqs()
215             optPtr->litSum = ZSTD_downscaleStat(optPtr->litFreq, MaxLit, 1);  in ZSTD_rescaleFreqs()
275     U32 const offCode = ZSTD_highbit32(offset+1);  in ZSTD_getMatchPrice()
319     {   U32 const offCode = ZSTD_highbit32(offsetCode+1);  in ZSTD_updateStats()
353 static U32 ZSTD_insertAndFindFirstIndexHash3 (ZSTD_matchState_t* ms,  in ZSTD_insertAndFindFirstIndexHash3()  argument
357     U32* const hashTable3 = ms->hashTable3;  in ZSTD_insertAndFindFirstIndexHash3()
358     U32 const hashLog3 = ms->hashLog3;  in ZSTD_insertAndFindFirstIndexHash3()
359     const BYTE* const base = ms->window.base;  in ZSTD_insertAndFindFirstIndexHash3()
382                 ZSTD_matchState_t* ms,  in ZSTD_insertBt1()  argument
386     const ZSTD_compressionParameters* const cParams = &ms->cParams;  in ZSTD_insertBt1()
387     U32*   const hashTable = ms->hashTable;  in ZSTD_insertBt1()
390     U32*   const bt = ms->chainTable;  in ZSTD_insertBt1()
391     U32    const btLog  = cParams->chainLog - 1;  in ZSTD_insertBt1()
392     U32    const btMask = (1 << btLog) - 1;  in ZSTD_insertBt1()
395     const BYTE* const base = ms->window.base;  in ZSTD_insertBt1()
396     const BYTE* const dictBase = ms->window.dictBase;  in ZSTD_insertBt1()
397     const U32 dictLimit = ms->window.dictLimit;  in ZSTD_insertBt1()
404     U32* largerPtr  = smallerPtr + 1;  in ZSTD_insertBt1()
406     U32 const windowLow = ms->window.lowLimit;  in ZSTD_insertBt1()
407     U32 matchEndIdx = curr+8+1;  in ZSTD_insertBt1()
409     U32 nbCompares = 1U << cParams->searchLog;  in ZSTD_insertBt1()
411     U32 predictedSmall = *(bt + 2*((curr-1)&btMask) + 0);  in ZSTD_insertBt1()
412     U32 predictedLarge = *(bt + 2*((curr-1)&btMask) + 1);  in ZSTD_insertBt1()
429 …const U32* predictPtr = bt + 2*((matchIndex-1) & btMask);   /* written this way, as bt is a roll b…  in ZSTD_insertBt1()
434             smallerPtr = nextPtr+1;               /* new "smaller" => larger of match */  in ZSTD_insertBt1()
435 …matchIndex = nextPtr[1];              /* new matchIndex larger than previous (closer to current) */  in ZSTD_insertBt1()
436             predictedSmall = predictPtr[1] + (predictPtr[1]>0);  in ZSTD_insertBt1()
475 …smallerPtr = nextPtr+1;               /* new "candidate" => larger than match, which was smaller t…  in ZSTD_insertBt1()
476 …matchIndex = nextPtr[1];              /* new matchIndex, larger than previous and closer to curren…  in ZSTD_insertBt1()
496                 ZSTD_matchState_t* ms,  in ZSTD_updateTree_internal()  argument
500     const BYTE* const base = ms->window.base;  in ZSTD_updateTree_internal()
502     U32 idx = ms->nextToUpdate;  in ZSTD_updateTree_internal()
507         U32 const forward = ZSTD_insertBt1(ms, base+idx, iend, mls, dictMode == ZSTD_extDict);  in ZSTD_updateTree_internal()
511     assert((size_t)(ip - base) <= (size_t)(U32)(-1));  in ZSTD_updateTree_internal()
512     assert((size_t)(iend - base) <= (size_t)(U32)(-1));  in ZSTD_updateTree_internal()
513     ms->nextToUpdate = target;  in ZSTD_updateTree_internal()
516 void ZSTD_updateTree(ZSTD_matchState_t* ms, const BYTE* ip, const BYTE* iend) {  in ZSTD_updateTree()  argument
517     ZSTD_updateTree_internal(ms, ip, iend, ms->cParams.minMatch, ZSTD_noDict);  in ZSTD_updateTree()
523                     ZSTD_matchState_t* ms,  in ZSTD_insertBtAndGetAllMatches()  argument
527 …   U32 const ll0,   /* tells if associated literal length is 0 or not. This value must be 0 or 1 */  in ZSTD_insertBtAndGetAllMatches()
531     const ZSTD_compressionParameters* const cParams = &ms->cParams;  in ZSTD_insertBtAndGetAllMatches()
532     U32 const sufficient_len = MIN(cParams->targetLength, ZSTD_OPT_NUM -1);  in ZSTD_insertBtAndGetAllMatches()
533     const BYTE* const base = ms->window.base;  in ZSTD_insertBtAndGetAllMatches()
537     U32* const hashTable = ms->hashTable;  in ZSTD_insertBtAndGetAllMatches()
540     U32* const bt   = ms->chainTable;  in ZSTD_insertBtAndGetAllMatches()
541     U32 const btLog = cParams->chainLog - 1;  in ZSTD_insertBtAndGetAllMatches()
542     U32 const btMask= (1U << btLog) - 1;  in ZSTD_insertBtAndGetAllMatches()
544     const BYTE* const dictBase = ms->window.dictBase;  in ZSTD_insertBtAndGetAllMatches()
545     U32 const dictLimit = ms->window.dictLimit;  in ZSTD_insertBtAndGetAllMatches()
549     U32 const windowLow = ZSTD_getLowestMatchIndex(ms, curr, cParams->windowLog);  in ZSTD_insertBtAndGetAllMatches()
550     U32 const matchLow = windowLow ? windowLow : 1;  in ZSTD_insertBtAndGetAllMatches()
552     U32* largerPtr  = bt + 2*(curr&btMask) + 1;  in ZSTD_insertBtAndGetAllMatches()
553 …U32 matchEndIdx = curr+8+1;   /* farthest referenced position of any match => detects repetitive p…  in ZSTD_insertBtAndGetAllMatches()
556     U32 nbCompares = 1U << cParams->searchLog;  in ZSTD_insertBtAndGetAllMatches()
558     const ZSTD_matchState_t* dms    = dictMode == ZSTD_dictMatchState ? ms->dictMatchState : NULL;  in ZSTD_insertBtAndGetAllMatches()
567 …U32         const dmsBtLog      = dictMode == ZSTD_dictMatchState ? dmsCParams->chainLog - 1 : btL…  in ZSTD_insertBtAndGetAllMatches()
568     U32         const dmsBtMask     = dictMode == ZSTD_dictMatchState ? (1U << dmsBtLog) - 1 : 0;  in ZSTD_insertBtAndGetAllMatches()
571     size_t bestLength = lengthToBeat-1;  in ZSTD_insertBtAndGetAllMatches()
575     assert(ll0 <= 1);   /* necessarily 1 or 0 */  in ZSTD_insertBtAndGetAllMatches()
579             U32 const repOffset = (repCode==ZSTD_REP_NUM) ? (rep[0] - 1) : rep[repCode];  in ZSTD_insertBtAndGetAllMatches()
583 …if (repOffset-1 /* intentional overflow, discards 0 and -1 */ < curr-dictLimit) {  /* equivalent t…  in ZSTD_insertBtAndGetAllMatches()
596 …&& ( ((repOffset-1) /*intentional overflow*/ < curr - windowLow)  /* equivalent to `curr > repInde…  in ZSTD_insertBtAndGetAllMatches()
597 …& (((U32)((dictLimit-1) - repIndex) >= 3) ) /* intentional overflow : do not test positions overla…  in ZSTD_insertBtAndGetAllMatches()
602 …&& ( ((repOffset-1) /*intentional overflow*/ < curr - (dmsLowLimit + dmsIndexDelta))  /* equivalen…  in ZSTD_insertBtAndGetAllMatches()
603 …& ((U32)((dictLimit-1) - repIndex) >= 3) ) /* intentional overflow : do not test positions overlap…  in ZSTD_insertBtAndGetAllMatches()
622         U32 const matchIndex3 = ZSTD_insertAndFindFirstIndexHash3(ms, nextToUpdate3, ip);  in ZSTD_insertBtAndGetAllMatches()
624           & (curr - matchIndex3 < (1<<18)) /*heuristic : longer distance likely too expensive*/ ) {  in ZSTD_insertBtAndGetAllMatches()
643                 mnum = 1;  in ZSTD_insertBtAndGetAllMatches()
646                     ms->nextToUpdate = curr+1;  /* skip insertion */  in ZSTD_insertBtAndGetAllMatches()
647                     return 1;  in ZSTD_insertBtAndGetAllMatches()
695 …smallerPtr = nextPtr+1;               /* new candidate => larger than match, which was smaller tha…  in ZSTD_insertBtAndGetAllMatches()
696 …matchIndex = nextPtr[1];              /* new matchIndex, larger than previous, closer to current */  in ZSTD_insertBtAndGetAllMatches()
707     assert(nbCompares <= (1U << ZSTD_SEARCHLOG_MAX)); /* Check we haven't underflowed. */  in ZSTD_insertBtAndGetAllMatches()
740 …dictMatchIndex = nextPtr[1];              /* new matchIndex larger than previous (closer to curren…  in ZSTD_insertBtAndGetAllMatches()
750     ms->nextToUpdate = matchEndIdx - 8;  /* skip repetitive patterns */  in ZSTD_insertBtAndGetAllMatches()
757                         ZSTD_matchState_t* ms,  in ZSTD_BtGetAllMatches()  argument
764     const ZSTD_compressionParameters* const cParams = &ms->cParams;  in ZSTD_BtGetAllMatches()
767     if (ip < ms->window.base + ms->nextToUpdate) return 0;   /* skipped area */  in ZSTD_BtGetAllMatches()
768     ZSTD_updateTree_internal(ms, ip, iHighLimit, matchLengthSearch, dictMode);  in ZSTD_BtGetAllMatches()
771 …case 3 : return ZSTD_insertBtAndGetAllMatches(matches, ms, nextToUpdate3, ip, iHighLimit, dictMode…  in ZSTD_BtGetAllMatches()
773 …case 4 : return ZSTD_insertBtAndGetAllMatches(matches, ms, nextToUpdate3, ip, iHighLimit, dictMode…  in ZSTD_BtGetAllMatches()
774 …case 5 : return ZSTD_insertBtAndGetAllMatches(matches, ms, nextToUpdate3, ip, iHighLimit, dictMode…  in ZSTD_BtGetAllMatches()
776 …case 6 : return ZSTD_insertBtAndGetAllMatches(matches, ms, nextToUpdate3, ip, iHighLimit, dictMode…  in ZSTD_BtGetAllMatches()
883 …if (*nbMatches == 0 || ((candidateMatchLength > matches[*nbMatches-1].len) && *nbMatches < ZSTD_OP…  in ZSTD_optLdm_maybeAddMatch()
930     int const nbElts = lastEltID + 1;
943 ZSTD_compressBlock_opt_generic(ZSTD_matchState_t* ms,  in ZSTD_compressBlock_opt_generic()  argument
950     optState_t* const optStatePtr = &ms->opt;  in ZSTD_compressBlock_opt_generic()
956     const BYTE* const base = ms->window.base;  in ZSTD_compressBlock_opt_generic()
957     const BYTE* const prefixStart = base + ms->window.dictLimit;  in ZSTD_compressBlock_opt_generic()
958     const ZSTD_compressionParameters* const cParams = &ms->cParams;  in ZSTD_compressBlock_opt_generic()
960     U32 const sufficient_len = MIN(cParams->targetLength, ZSTD_OPT_NUM -1);  in ZSTD_compressBlock_opt_generic()
962     U32 nextToUpdate3 = ms->nextToUpdate;  in ZSTD_compressBlock_opt_generic()
969     optLdm.seqStore = ms->ldmSeqStore ? *ms->ldmSeqStore : kNullRawSeqStore;  in ZSTD_compressBlock_opt_generic()
975                 (U32)(ip - base), ms->window.dictLimit, ms->nextToUpdate);  in ZSTD_compressBlock_opt_generic()
987 …U32 nbMatches = ZSTD_BtGetAllMatches(matches, ms, &nextToUpdate3, ip, iend, dictMode, rep, ll0, mi…  in ZSTD_compressBlock_opt_generic()
1004             {   U32 const maxML = matches[nbMatches-1].len;  in ZSTD_compressBlock_opt_generic()
1005                 U32 const maxOffset = matches[nbMatches-1].off;  in ZSTD_compressBlock_opt_generic()
1024                 for (pos = 1; pos < minMatch; pos++) {  in ZSTD_compressBlock_opt_generic()
1040                 last_pos = pos-1;  in ZSTD_compressBlock_opt_generic()
1045         for (cur = 1; cur <= last_pos; cur++) {  in ZSTD_compressBlock_opt_generic()
1051             {   U32 const litlen = (opt[cur-1].mlen == 0) ? opt[cur-1].litlen + 1 : 1;  in ZSTD_compressBlock_opt_generic()
1052                 int const price = opt[cur-1].price  in ZSTD_compressBlock_opt_generic()
1053                                 + ZSTD_rawLiteralsCost(ip+cur-1, 1, optStatePtr, optLevel)  in ZSTD_compressBlock_opt_generic()
1055                                 - ZSTD_litLengthPrice(litlen-1, optStatePtr, optLevel);  in ZSTD_compressBlock_opt_generic()
1060                                 opt[cur-1].rep[0], opt[cur-1].rep[1], opt[cur-1].rep[2]);  in ZSTD_compressBlock_opt_generic()
1068                                 opt[cur].rep[0], opt[cur].rep[1], opt[cur].rep[2]);  in ZSTD_compressBlock_opt_generic()
1084                 ZSTD_memcpy(opt[cur].rep, opt[cur - 1].rep, sizeof(repcodes_t));  in ZSTD_compressBlock_opt_generic()
1093               && (opt[cur+1].price <= opt[cur].price + (BITCOST_MULTIPLIER/2)) ) {  in ZSTD_compressBlock_opt_generic()
1094                 DEBUGLOG(7, "move to next rPos:%u : price is <=", cur+1);  in ZSTD_compressBlock_opt_generic()
1102 …U32 nbMatches = ZSTD_BtGetAllMatches(matches, ms, &nextToUpdate3, inr, iend, dictMode, opt[cur].re…  in ZSTD_compressBlock_opt_generic()
1113                 {   U32 const maxML = matches[nbMatches-1].len;  in ZSTD_compressBlock_opt_generic()
1120                         lastSequence.off = matches[nbMatches-1].off;  in ZSTD_compressBlock_opt_generic()
1132                     U32 const startML = (matchNb>0) ? matches[matchNb-1].len+1 : minMatch;  in ZSTD_compressBlock_opt_generic()
1145 …while (last_pos < pos) { opt[last_pos+1].price = ZSTD_MAX_PRICE; last_pos++; }   /* fill empty pos…  in ZSTD_compressBlock_opt_generic()
1156         }  /* for (cur = 1; cur <= last_pos; cur++) */  in ZSTD_compressBlock_opt_generic()
1176         {   U32 const storeEnd = cur + 1;  in ZSTD_compressBlock_opt_generic()
1228         ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],  in ZSTD_compressBlock_btopt()  argument
1232 …return ZSTD_compressBlock_opt_generic(ms, seqStore, rep, src, srcSize, 0 /*optLevel*/, ZSTD_noDict…  in ZSTD_compressBlock_btopt()
1241     for (s=0; s<lastEltIndex+1; s++) {  in ZSTD_upscaleStat()
1265 ZSTD_initStats_ultra(ZSTD_matchState_t* ms,  in ZSTD_initStats_ultra()  argument
1274     assert(ms->opt.litLengthSum == 0);    /* first block */  in ZSTD_initStats_ultra()
1276     assert(ms->window.dictLimit == ms->window.lowLimit);   /* no dictionary */  in ZSTD_initStats_ultra()
1277 …assert(ms->window.dictLimit - ms->nextToUpdate <= 1);  /* no prefix (note: intentional overflow, d…  in ZSTD_initStats_ultra()
1279 …STD_compressBlock_opt_generic(ms, seqStore, tmpRep, src, srcSize, 2 /*optLevel*/, ZSTD_noDict);   …  in ZSTD_initStats_ultra()
1283     ms->window.base -= srcSize;  in ZSTD_initStats_ultra()
1284     ms->window.dictLimit += (U32)srcSize;  in ZSTD_initStats_ultra()
1285     ms->window.lowLimit = ms->window.dictLimit;  in ZSTD_initStats_ultra()
1286     ms->nextToUpdate = ms->window.dictLimit;  in ZSTD_initStats_ultra()
1289     ZSTD_upscaleStats(&ms->opt);  in ZSTD_initStats_ultra()
1293         ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],  in ZSTD_compressBlock_btultra()  argument
1297 …return ZSTD_compressBlock_opt_generic(ms, seqStore, rep, src, srcSize, 2 /*optLevel*/, ZSTD_noDict…  in ZSTD_compressBlock_btultra()
1301         ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],  in ZSTD_compressBlock_btultra2()  argument
1304     U32 const curr = (U32)((const BYTE*)src - ms->window.base);  in ZSTD_compressBlock_btultra2()
1310      * After 1st pass, function forgets everything, and starts a new block.  in ZSTD_compressBlock_btultra2()
1316     if ( (ms->opt.litLengthSum==0)   /* first block */  in ZSTD_compressBlock_btultra2()
1318       && (ms->window.dictLimit == ms->window.lowLimit)   /* no dictionary */  in ZSTD_compressBlock_btultra2()
1319       && (curr == ms->window.dictLimit)   /* start of frame, nothing already loaded nor skipped */  in ZSTD_compressBlock_btultra2()
1322         ZSTD_initStats_ultra(ms, seqStore, rep, src, srcSize);  in ZSTD_compressBlock_btultra2()
1325 …return ZSTD_compressBlock_opt_generic(ms, seqStore, rep, src, srcSize, 2 /*optLevel*/, ZSTD_noDict…  in ZSTD_compressBlock_btultra2()
1329         ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],  in ZSTD_compressBlock_btopt_dictMatchState()  argument
1332 …return ZSTD_compressBlock_opt_generic(ms, seqStore, rep, src, srcSize, 0 /*optLevel*/, ZSTD_dictMa…  in ZSTD_compressBlock_btopt_dictMatchState()
1336         ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],  in ZSTD_compressBlock_btultra_dictMatchState()  argument
1339 …return ZSTD_compressBlock_opt_generic(ms, seqStore, rep, src, srcSize, 2 /*optLevel*/, ZSTD_dictMa…  in ZSTD_compressBlock_btultra_dictMatchState()
1343         ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],  in ZSTD_compressBlock_btopt_extDict()  argument
1346 …return ZSTD_compressBlock_opt_generic(ms, seqStore, rep, src, srcSize, 0 /*optLevel*/, ZSTD_extDic…  in ZSTD_compressBlock_btopt_extDict()
1350         ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],  in ZSTD_compressBlock_btultra_extDict()  argument
1353 …return ZSTD_compressBlock_opt_generic(ms, seqStore, rep, src, srcSize, 2 /*optLevel*/, ZSTD_extDic…  in ZSTD_compressBlock_btultra_extDict()