// SPDX-License-Identifier: GPL-2.0+ OR BSD-3-Clause/* * Copyright (c) Meta Platforms, Inc. and affiliates. * All rights reserved. * * This source code is licensed under both the BSD-style license (found in the * LICENSE file in the root directory of this source tree) and the GPLv2 (found * in the COPYING file in the root directory of this source tree). * You may select, at your option, one of the above-listed licenses. */ #include "zstd_compress_internal.h"#include "hist.h"#include "zstd_opt.h" #if !defined(ZSTD_EXCLUDE_BTLAZY2_BLOCK_COMPRESSOR) \ || !defined(ZSTD_EXCLUDE_BTOPT_BLOCK_COMPRESSOR) \ || !defined(ZSTD_EXCLUDE_BTULTRA_BLOCK_COMPRESSOR) #define ZSTD_LITFREQ_ADD 2 /* scaling factor for litFreq, so that frequencies adapt faster to new stats */#define ZSTD_MAX_PRICE (1<<30) #define ZSTD_PREDEF_THRESHOLD 8 /* if srcSize < ZSTD_PREDEF_THRESHOLD, symbols' cost is assumed static, directly determined by pre-defined distributions */ /*-************************************** Price functions for optimal parser***************************************/ #if 0 /* approximation at bit level (for tests) */# define BITCOST_ACCURACY 0# define BITCOST_MULTIPLIER (1 << BITCOST_ACCURACY)# define WEIGHT(stat, opt) ((void)(opt), ZSTD_bitWeight(stat))#elif 0 /* fractional bit accuracy (for tests) */# define BITCOST_ACCURACY 8# define BITCOST_MULTIPLIER (1 << BITCOST_ACCURACY)# define WEIGHT(stat,opt) ((void)(opt), ZSTD_fracWeight(stat))#else /* opt==approx, ultra==accurate */# define BITCOST_ACCURACY 8# define BITCOST_MULTIPLIER (1 << BITCOST_ACCURACY)# define WEIGHT(stat,opt) ((opt) ? ZSTD_fracWeight(stat) : ZSTD_bitWeight(stat))#endif /* ZSTD_bitWeight() : * provide estimated "cost" of a stat in full bits only */MEM_STATIC U32 ZSTD_bitWeight(U32 stat){ return (ZSTD_highbit32(stat+1) * BITCOST_MULTIPLIER);} /* ZSTD_fracWeight() : * provide fractional-bit "cost" of a stat, * using linear interpolation approximation */MEM_STATIC U32 ZSTD_fracWeight(U32 rawStat){ U32 const stat = rawStat + 1; U32 const hb = ZSTD_highbit32(stat); U32 const BWeight = hb * BITCOST_MULTIPLIER; /* Fweight was meant for "Fractional weight" * but it's effectively a value between 1 and 2 * using fixed point arithmetic */ U32 const FWeight = (stat << BITCOST_ACCURACY) >> hb; U32 const weight = BWeight + FWeight; assert(hb + BITCOST_ACCURACY < 31); return weight;} #if (DEBUGLEVEL>=2)/* debugging function, * @return price in bytes as fractional value * for debug messages only */MEM_STATIC double ZSTD_fCost(int price){ return (double)price / (BITCOST_MULTIPLIER*8);}#endif static int ZSTD_compressedLiterals(optState_t const* const optPtr){ return optPtr->literalCompressionMode != ZSTD_ps_disable;} static void ZSTD_setBasePrices(optState_t* optPtr, int optLevel){ if (ZSTD_compressedLiterals(optPtr)) optPtr->litSumBasePrice = WEIGHT(optPtr->litSum, optLevel); optPtr->litLengthSumBasePrice = WEIGHT(optPtr->litLengthSum, optLevel); optPtr->matchLengthSumBasePrice = WEIGHT(optPtr->matchLengthSum, optLevel); optPtr->offCodeSumBasePrice = WEIGHT(optPtr->offCodeSum, optLevel);} static U32 sum_u32(const unsigned table[], size_t nbElts){ size_t n; U32 total = 0; for (n=0; n<nbElts; n++) { total += table[n]; } return total;} typedef enum { base_0possible=0, base_1guaranteed=1 } base_directive_e; static U32ZSTD_downscaleStats(unsigned* table, U32 lastEltIndex, U32 shift, base_directive_e base1){ U32 s, sum=0; DEBUGLOG(5, "ZSTD_downscaleStats (nbElts=%u, shift=%u)", (unsigned)lastEltIndex+1, (unsigned)shift ); assert(shift < 30); for (s=0; s<lastEltIndex+1; s++) { unsigned const base = base1 ? 1 : (table[s]>0); unsigned const newStat = base + (table[s] >> shift); sum += newStat; table[s] = newStat; } return sum;} /* ZSTD_scaleStats() : * reduce all elt frequencies in table if sum too large * return the resulting sum of elements */static U32 ZSTD_scaleStats(unsigned* table, U32 lastEltIndex, U32 logTarget){ U32 const prevsum = sum_u32(table, lastEltIndex+1); U32 const factor = prevsum >> logTarget; DEBUGLOG(5, "ZSTD_scaleStats (nbElts=%u, target=%u)", (unsigned)lastEltIndex+1, (unsigned)logTarget); assert(logTarget < 30); if (factor <= 1) return prevsum; return ZSTD_downscaleStats(table, lastEltIndex, ZSTD_highbit32(factor), base_1guaranteed);} /* ZSTD_rescaleFreqs() : * if first block (detected by optPtr->litLengthSum == 0) : init statistics * take hints from dictionary if there is one * and init from zero if there is none, * using src for literals stats, and baseline stats for sequence symbols * otherwise downscale existing stats, to be used as seed for next block. */static voidZSTD_rescaleFreqs(optState_t* const optPtr, const BYTE* const src, size_t const srcSize, int const optLevel){ int const compressedLiterals = ZSTD_compressedLiterals(optPtr); DEBUGLOG(5, "ZSTD_rescaleFreqs (srcSize=%u)", (unsigned)srcSize); optPtr->priceType = zop_dynamic; if (optPtr->litLengthSum == 0) { /* no literals stats collected -> first block assumed -> init */ /* heuristic: use pre-defined stats for too small inputs */ if (srcSize <= ZSTD_PREDEF_THRESHOLD) { DEBUGLOG(5, "srcSize <= %i : use predefined stats", ZSTD_PREDEF_THRESHOLD); optPtr->priceType = zop_predef; } assert(optPtr->symbolCosts != NULL); if (optPtr->symbolCosts->huf.repeatMode == HUF_repeat_valid) { /* huffman stats covering the full value set : table presumed generated by dictionary */ optPtr->priceType = zop_dynamic; if (compressedLiterals) { /* generate literals statistics from huffman table */ unsigned lit; assert(optPtr->litFreq != NULL); optPtr->litSum = 0; for (lit=0; lit<=MaxLit; lit++) { U32 const scaleLog = 11; /* scale to 2K */ U32 const bitCost = HUF_getNbBitsFromCTable(optPtr->symbolCosts->huf.CTable, lit); assert(bitCost <= scaleLog); optPtr->litFreq[lit] = bitCost ? 1 << (scaleLog-bitCost) : 1 /*minimum to calculate cost*/; optPtr->litSum += optPtr->litFreq[lit]; } } { unsigned ll; FSE_CState_t llstate; FSE_initCState(&llstate, optPtr->symbolCosts->fse.litlengthCTable); optPtr->litLengthSum = 0; for (ll=0; ll<=MaxLL; ll++) { U32 const scaleLog = 10; /* scale to 1K */ U32 const bitCost = FSE_getMaxNbBits(llstate.symbolTT, ll); assert(bitCost < scaleLog); optPtr->litLengthFreq[ll] = bitCost ? 1 << (scaleLog-bitCost) : 1 /*minimum to calculate cost*/; optPtr->litLengthSum += optPtr->litLengthFreq[ll]; } } { unsigned ml; FSE_CState_t mlstate; FSE_initCState(&mlstate, optPtr->symbolCosts->fse.matchlengthCTable); optPtr->matchLengthSum = 0; for (ml=0; ml<=MaxML; ml++) { U32 const scaleLog = 10; U32 const bitCost = FSE_getMaxNbBits(mlstate.symbolTT, ml); assert(bitCost < scaleLog); optPtr->matchLengthFreq[ml] = bitCost ? 1 << (scaleLog-bitCost) : 1 /*minimum to calculate cost*/; optPtr->matchLengthSum += optPtr->matchLengthFreq[ml]; } } { unsigned of; FSE_CState_t ofstate; FSE_initCState(&ofstate, optPtr->symbolCosts->fse.offcodeCTable); optPtr->offCodeSum = 0; for (of=0; of<=MaxOff; of++) { U32 const scaleLog = 10; U32 const bitCost = FSE_getMaxNbBits(ofstate.symbolTT, of); assert(bitCost < scaleLog); optPtr->offCodeFreq[of] = bitCost ? 1 << (scaleLog-bitCost) : 1 /*minimum to calculate cost*/; optPtr->offCodeSum += optPtr->offCodeFreq[of]; } } } else { /* first block, no dictionary */ assert(optPtr->litFreq != NULL); if (compressedLiterals) { /* base initial cost of literals on direct frequency within src */ unsigned lit = MaxLit; HIST_count_simple(optPtr->litFreq, &lit, src, srcSize); /* use raw first block to init statistics */ optPtr->litSum = ZSTD_downscaleStats(optPtr->litFreq, MaxLit, 8, base_0possible); } { unsigned const baseLLfreqs[MaxLL+1] = { 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }; ZSTD_memcpy(optPtr->litLengthFreq, baseLLfreqs, sizeof(baseLLfreqs)); optPtr->litLengthSum = sum_u32(baseLLfreqs, MaxLL+1); } { unsigned ml; for (ml=0; ml<=MaxML; ml++) optPtr->matchLengthFreq[ml] = 1; } optPtr->matchLengthSum = MaxML+1; { unsigned const baseOFCfreqs[MaxOff+1] = { 6, 2, 1, 1, 2, 3, 4, 4, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }; ZSTD_memcpy(optPtr->offCodeFreq, baseOFCfreqs, sizeof(baseOFCfreqs)); optPtr->offCodeSum = sum_u32(baseOFCfreqs, MaxOff+1); } } } else { /* new block : scale down accumulated statistics */ if (compressedLiterals) optPtr->litSum = ZSTD_scaleStats(optPtr->litFreq, MaxLit, 12); optPtr->litLengthSum = ZSTD_scaleStats(optPtr->litLengthFreq, MaxLL, 11); optPtr->matchLengthSum = ZSTD_scaleStats(optPtr->matchLengthFreq, MaxML, 11); optPtr->offCodeSum = ZSTD_scaleStats(optPtr->offCodeFreq, MaxOff, 11); } ZSTD_setBasePrices(optPtr, optLevel);} /* ZSTD_rawLiteralsCost() : * price of literals (only) in specified segment (which length can be 0). * does not include price of literalLength symbol */static U32 ZSTD_rawLiteralsCost(const BYTE* const literals, U32 const litLength, const optState_t* const optPtr, int optLevel){ DEBUGLOG(8, "ZSTD_rawLiteralsCost (%u literals)", litLength); if (litLength == 0) return 0; if (!ZSTD_compressedLiterals(optPtr)) return (litLength << 3) * BITCOST_MULTIPLIER; /* Uncompressed - 8 bytes per literal. */ if (optPtr->priceType == zop_predef) return (litLength*6) * BITCOST_MULTIPLIER; /* 6 bit per literal - no statistic used */ /* dynamic statistics */ { U32 price = optPtr->litSumBasePrice * litLength; U32 const litPriceMax = optPtr->litSumBasePrice - BITCOST_MULTIPLIER; U32 u; assert(optPtr->litSumBasePrice >= BITCOST_MULTIPLIER); for (u=0; u < litLength; u++) { U32 litPrice = WEIGHT(optPtr->litFreq[literals[u]], optLevel); if (UNLIKELY(litPrice > litPriceMax)) litPrice = litPriceMax; price -= litPrice; } return price; }} /* ZSTD_litLengthPrice() : * cost of literalLength symbol */static U32 ZSTD_litLengthPrice(U32 const litLength, const optState_t* const optPtr, int optLevel){ assert(litLength <= ZSTD_BLOCKSIZE_MAX); if (optPtr->priceType == zop_predef) return WEIGHT(litLength, optLevel); /* ZSTD_LLcode() can't compute litLength price for sizes >= ZSTD_BLOCKSIZE_MAX * because it isn't representable in the zstd format. * So instead just pretend it would cost 1 bit more than ZSTD_BLOCKSIZE_MAX - 1. * In such a case, the block would be all literals. */ if (litLength == ZSTD_BLOCKSIZE_MAX) return BITCOST_MULTIPLIER + ZSTD_litLengthPrice(ZSTD_BLOCKSIZE_MAX - 1, optPtr, optLevel); /* dynamic statistics */ { U32 const llCode = ZSTD_LLcode(litLength); return (LL_bits[llCode] * BITCOST_MULTIPLIER) + optPtr->litLengthSumBasePrice - WEIGHT(optPtr->litLengthFreq[llCode], optLevel); }} /* ZSTD_getMatchPrice() : * Provides the cost of the match part (offset + matchLength) of a sequence. * Must be combined with ZSTD_fullLiteralsCost() to get the full cost of a sequence. * @offBase : sumtype, representing an offset or a repcode, and using numeric representation of ZSTD_storeSeq() * @optLevel: when <2, favors small offset for decompression speed (improved cache efficiency) */FORCE_INLINE_TEMPLATE U32ZSTD_getMatchPrice(U32 const offBase, U32 const matchLength, const optState_t* const optPtr, int const optLevel){ U32 price; U32 const offCode = ZSTD_highbit32(offBase); U32 const mlBase = matchLength - MINMATCH; assert(matchLength >= MINMATCH); if (optPtr->priceType == zop_predef) /* fixed scheme, does not use statistics */ return WEIGHT(mlBase, optLevel) + ((16 + offCode) * BITCOST_MULTIPLIER); /* emulated offset cost */ /* dynamic statistics */ price = (offCode * BITCOST_MULTIPLIER) + (optPtr->offCodeSumBasePrice - WEIGHT(optPtr->offCodeFreq[offCode], optLevel)); if ((optLevel<2) /*static*/ && offCode >= 20) price += (offCode-19)*2 * BITCOST_MULTIPLIER; /* handicap for long distance offsets, favor decompression speed */ /* match Length */ { U32 const mlCode = ZSTD_MLcode(mlBase); price += (ML_bits[mlCode] * BITCOST_MULTIPLIER) + (optPtr->matchLengthSumBasePrice - WEIGHT(optPtr->matchLengthFreq[mlCode], optLevel)); } price += BITCOST_MULTIPLIER / 5; /* heuristic : make matches a bit more costly to favor less sequences -> faster decompression speed */ DEBUGLOG(8, "ZSTD_getMatchPrice(ml:%u) = %u", matchLength, price); return price;} /* ZSTD_updateStats() : * assumption : literals + litLength <= iend */static void ZSTD_updateStats(optState_t* const optPtr, U32 litLength, const BYTE* literals, U32 offBase, U32 matchLength){ /* literals */ if (ZSTD_compressedLiterals(optPtr)) { U32 u; for (u=0; u < litLength; u++) optPtr->litFreq[literals[u]] += ZSTD_LITFREQ_ADD; optPtr->litSum += litLength*ZSTD_LITFREQ_ADD; } /* literal Length */ { U32 const llCode = ZSTD_LLcode(litLength); optPtr->litLengthFreq[llCode]++; optPtr->litLengthSum++; } /* offset code : follows storeSeq() numeric representation */ { U32 const offCode = ZSTD_highbit32(offBase); assert(offCode <= MaxOff); optPtr->offCodeFreq[offCode]++; optPtr->offCodeSum++; } /* match Length */ { U32 const mlBase = matchLength - MINMATCH; U32 const mlCode = ZSTD_MLcode(mlBase); optPtr->matchLengthFreq[mlCode]++; optPtr->matchLengthSum++; }} /* ZSTD_readMINMATCH() : * function safe only for comparisons * assumption : memPtr must be at least 4 bytes before end of buffer */MEM_STATIC U32 ZSTD_readMINMATCH(const void* memPtr, U32 length){ switch (length) { default : case 4 : return MEM_read32(memPtr); case 3 : if (MEM_isLittleEndian()) return MEM_read32(memPtr)<<8; else return MEM_read32(memPtr)>>8; }} /* Update hashTable3 up to ip (excluded) Assumption : always within prefix (i.e. not within extDict) */staticZSTD_ALLOW_POINTER_OVERFLOW_ATTRU32 ZSTD_insertAndFindFirstIndexHash3 (const ZSTD_MatchState_t* ms, U32* nextToUpdate3, const BYTE* const ip){ U32* const hashTable3 = ms->hashTable3; U32 const hashLog3 = ms->hashLog3; const BYTE* const base = ms->window.base; U32 idx = *nextToUpdate3; U32 const target = (U32)(ip - base); size_t const hash3 = ZSTD_hash3Ptr(ip, hashLog3); assert(hashLog3 > 0); while(idx < target) { hashTable3[ZSTD_hash3Ptr(base+idx, hashLog3)] = idx; idx++; } *nextToUpdate3 = target; return hashTable3[hash3];} /*-************************************** Binary Tree search***************************************//* ZSTD_insertBt1() : add one or multiple positions to tree. * @param ip assumed <= iend-8 . * @param target The target of ZSTD_updateTree_internal() - we are filling to this position * @return : nb of positions added */staticZSTD_ALLOW_POINTER_OVERFLOW_ATTRU32 ZSTD_insertBt1( const ZSTD_MatchState_t* ms, const BYTE* const ip, const BYTE* const iend, U32 const target, U32 const mls, const int extDict){ const ZSTD_compressionParameters* const cParams = &ms->cParams; U32* const hashTable = ms->hashTable; U32 const hashLog = cParams->hashLog; size_t const h = ZSTD_hashPtr(ip, hashLog, mls); U32* const bt = ms->chainTable; U32 const btLog = cParams->chainLog - 1; U32 const btMask = (1 << btLog) - 1; U32 matchIndex = hashTable[h]; size_t commonLengthSmaller=0, commonLengthLarger=0; const BYTE* const base = ms->window.base; const BYTE* const dictBase = ms->window.dictBase; const U32 dictLimit = ms->window.dictLimit; const BYTE* const dictEnd = dictBase + dictLimit; const BYTE* const prefixStart = base + dictLimit; const BYTE* match; const U32 curr = (U32)(ip-base); const U32 btLow = btMask >= curr ? 0 : curr - btMask; U32* smallerPtr = bt + 2*(curr&btMask); U32* largerPtr = smallerPtr + 1; U32 dummy32; /* to be nullified at the end */ /* windowLow is based on target because * we only need positions that will be in the window at the end of the tree update. */ U32 const windowLow = ZSTD_getLowestMatchIndex(ms, target, cParams->windowLog); U32 matchEndIdx = curr+8+1; size_t bestLength = 8; U32 nbCompares = 1U << cParams->searchLog;#ifdef ZSTD_C_PREDICT U32 predictedSmall = *(bt + 2*((curr-1)&btMask) + 0); U32 predictedLarge = *(bt + 2*((curr-1)&btMask) + 1); predictedSmall += (predictedSmall>0); predictedLarge += (predictedLarge>0);#endif /* ZSTD_C_PREDICT */ DEBUGLOG(8, "ZSTD_insertBt1 (%u)", curr); assert(curr <= target); assert(ip <= iend-8); /* required for h calculation */ hashTable[h] = curr; /* Update Hash Table */ assert(windowLow > 0); for (; nbCompares && (matchIndex >= windowLow); --nbCompares) { U32* const nextPtr = bt + 2*(matchIndex & btMask); size_t matchLength = MIN(commonLengthSmaller, commonLengthLarger); /* guaranteed minimum nb of common bytes */ assert(matchIndex < curr); #ifdef ZSTD_C_PREDICT /* note : can create issues when hlog small <= 11 */ const U32* predictPtr = bt + 2*((matchIndex-1) & btMask); /* written this way, as bt is a roll buffer */ if (matchIndex == predictedSmall) { /* no need to check length, result known */ *smallerPtr = matchIndex; if (matchIndex <= btLow) { smallerPtr=&dummy32; break; } /* beyond tree size, stop the search */Lines 1–500 of 1581. Load more
// SPDX-License-Identifier: GPL-2.0+ OR BSD-3-Clause /* * Copyright (c) Meta Platforms, Inc. and affiliates. * All rights reserved. * * This source code is licensed under both the BSD-style license (found in the * LICENSE file in the root directory of this source tree) and the GPLv2 (found * in the COPYING file in the root directory of this source tree). * You may select, at your option, one of the above-listed licenses. */ #include "zstd_compress_internal.h" #include "hist.h" #include "zstd_opt.h" #if !defined(ZSTD_EXCLUDE_BTLAZY2_BLOCK_COMPRESSOR) \ || !defined(ZSTD_EXCLUDE_BTOPT_BLOCK_COMPRESSOR) \ || !defined(ZSTD_EXCLUDE_BTULTRA_BLOCK_COMPRESSOR) #define ZSTD_LITFREQ_ADD 2 /* scaling factor for litFreq, so that frequencies adapt faster to new stats */ #define ZSTD_MAX_PRICE (1<<30) #define ZSTD_PREDEF_THRESHOLD 8 /* if srcSize < ZSTD_PREDEF_THRESHOLD, symbols' cost is assumed static, directly determined by pre-defined distributions */ /*-************************************* * Price functions for optimal parser ***************************************/ #if 0 /* approximation at bit level (for tests) */ # define BITCOST_ACCURACY 0 # define BITCOST_MULTIPLIER (1 << BITCOST_ACCURACY) # define WEIGHT(stat, opt) ((void)(opt), ZSTD_bitWeight(stat)) #elif 0 /* fractional bit accuracy (for tests) */ # define BITCOST_ACCURACY 8 # define BITCOST_MULTIPLIER (1 << BITCOST_ACCURACY) # define WEIGHT(stat,opt) ((void)(opt), ZSTD_fracWeight(stat)) #else /* opt==approx, ultra==accurate */ # define BITCOST_ACCURACY 8 # define BITCOST_MULTIPLIER (1 << BITCOST_ACCURACY) # define WEIGHT(stat,opt) ((opt) ? ZSTD_fracWeight(stat) : ZSTD_bitWeight(stat)) #endif /* ZSTD_bitWeight() : * provide estimated "cost" of a stat in full bits only */ MEM_STATIC U32 ZSTD_bitWeight(U32 stat) { return (ZSTD_highbit32(stat+1) * BITCOST_MULTIPLIER); } /* ZSTD_fracWeight() : * provide fractional-bit "cost" of a stat, * using linear interpolation approximation */ MEM_STATIC U32 ZSTD_fracWeight(U32 rawStat) { U32 const stat = rawStat + 1; U32 const hb = ZSTD_highbit32(stat); U32 const BWeight = hb * BITCOST_MULTIPLIER; /* Fweight was meant for "Fractional weight" * but it's effectively a value between 1 and 2 * using fixed point arithmetic */ U32 const FWeight = (stat << BITCOST_ACCURACY) >> hb; U32 const weight = BWeight + FWeight; assert(hb + BITCOST_ACCURACY < 31); return weight; } #if (DEBUGLEVEL>=2) /* debugging function, * @return price in bytes as fractional value * for debug messages only */ MEM_STATIC double ZSTD_fCost(int price) { return (double)price / (BITCOST_MULTIPLIER*8); } #endif static int ZSTD_compressedLiterals(optState_t const* const optPtr) { return optPtr->literalCompressionMode != ZSTD_ps_disable; } static void ZSTD_setBasePrices(optState_t* optPtr, int optLevel) { if (ZSTD_compressedLiterals(optPtr)) optPtr->litSumBasePrice = WEIGHT(optPtr->litSum, optLevel); optPtr->litLengthSumBasePrice = WEIGHT(optPtr->litLengthSum, optLevel); optPtr->matchLengthSumBasePrice = WEIGHT(optPtr->matchLengthSum, optLevel); optPtr->offCodeSumBasePrice = WEIGHT(optPtr->offCodeSum, optLevel); } static U32 sum_u32(const unsigned table[], size_t nbElts) { size_t n; U32 total = 0; for (n=0; n<nbElts; n++) { total += table[n]; } return total; } typedef enum { base_0possible=0, base_1guaranteed=1 } base_directive_e; static U32 ZSTD_downscaleStats(unsigned* table, U32 lastEltIndex, U32 shift, base_directive_e base1) { U32 s, sum=0; DEBUGLOG(5, "ZSTD_downscaleStats (nbElts=%u, shift=%u)", (unsigned)lastEltIndex+1, (unsigned)shift ); assert(shift < 30); for (s=0; s<lastEltIndex+1; s++) { unsigned const base = base1 ? 1 : (table[s]>0); unsigned const newStat = base + (table[s] >> shift); sum += newStat; table[s] = newStat; } return sum; } /* ZSTD_scaleStats() : * reduce all elt frequencies in table if sum too large * return the resulting sum of elements */ static U32 ZSTD_scaleStats(unsigned* table, U32 lastEltIndex, U32 logTarget) { U32 const prevsum = sum_u32(table, lastEltIndex+1); U32 const factor = prevsum >> logTarget; DEBUGLOG(5, "ZSTD_scaleStats (nbElts=%u, target=%u)", (unsigned)lastEltIndex+1, (unsigned)logTarget); assert(logTarget < 30); if (factor <= 1) return prevsum; return ZSTD_downscaleStats(table, lastEltIndex, ZSTD_highbit32(factor), base_1guaranteed); } /* ZSTD_rescaleFreqs() : * if first block (detected by optPtr->litLengthSum == 0) : init statistics * take hints from dictionary if there is one * and init from zero if there is none, * using src for literals stats, and baseline stats for sequence symbols * otherwise downscale existing stats, to be used as seed for next block. */ static void ZSTD_rescaleFreqs(optState_t* const optPtr, const BYTE* const src, size_t const srcSize, int const optLevel) { int const compressedLiterals = ZSTD_compressedLiterals(optPtr); DEBUGLOG(5, "ZSTD_rescaleFreqs (srcSize=%u)", (unsigned)srcSize); optPtr->priceType = zop_dynamic; if (optPtr->litLengthSum == 0) { /* no literals stats collected -> first block assumed -> init */ /* heuristic: use pre-defined stats for too small inputs */ if (srcSize <= ZSTD_PREDEF_THRESHOLD) { DEBUGLOG(5, "srcSize <= %i : use predefined stats", ZSTD_PREDEF_THRESHOLD); optPtr->priceType = zop_predef; } assert(optPtr->symbolCosts != NULL); if (optPtr->symbolCosts->huf.repeatMode == HUF_repeat_valid) { /* huffman stats covering the full value set : table presumed generated by dictionary */ optPtr->priceType = zop_dynamic; if (compressedLiterals) { /* generate literals statistics from huffman table */ unsigned lit; assert(optPtr->litFreq != NULL); optPtr->litSum = 0; for (lit=0; lit<=MaxLit; lit++) { U32 const scaleLog = 11; /* scale to 2K */ U32 const bitCost = HUF_getNbBitsFromCTable(optPtr->symbolCosts->huf.CTable, lit); assert(bitCost <= scaleLog); optPtr->litFreq[lit] = bitCost ? 1 << (scaleLog-bitCost) : 1 /*minimum to calculate cost*/; optPtr->litSum += optPtr->litFreq[lit]; } } { unsigned ll; FSE_CState_t llstate; FSE_initCState(&llstate, optPtr->symbolCosts->fse.litlengthCTable); optPtr->litLengthSum = 0; for (ll=0; ll<=MaxLL; ll++) { U32 const scaleLog = 10; /* scale to 1K */ U32 const bitCost = FSE_getMaxNbBits(llstate.symbolTT, ll); assert(bitCost < scaleLog); optPtr->litLengthFreq[ll] = bitCost ? 1 << (scaleLog-bitCost) : 1 /*minimum to calculate cost*/; optPtr->litLengthSum += optPtr->litLengthFreq[ll]; } } { unsigned ml; FSE_CState_t mlstate; FSE_initCState(&mlstate, optPtr->symbolCosts->fse.matchlengthCTable); optPtr->matchLengthSum = 0; for (ml=0; ml<=MaxML; ml++) { U32 const scaleLog = 10; U32 const bitCost = FSE_getMaxNbBits(mlstate.symbolTT, ml); assert(bitCost < scaleLog); optPtr->matchLengthFreq[ml] = bitCost ? 1 << (scaleLog-bitCost) : 1 /*minimum to calculate cost*/; optPtr->matchLengthSum += optPtr->matchLengthFreq[ml]; } } { unsigned of; FSE_CState_t ofstate; FSE_initCState(&ofstate, optPtr->symbolCosts->fse.offcodeCTable); optPtr->offCodeSum = 0; for (of=0; of<=MaxOff; of++) { U32 const scaleLog = 10; U32 const bitCost = FSE_getMaxNbBits(ofstate.symbolTT, of); assert(bitCost < scaleLog); optPtr->offCodeFreq[of] = bitCost ? 1 << (scaleLog-bitCost) : 1 /*minimum to calculate cost*/; optPtr->offCodeSum += optPtr->offCodeFreq[of]; } } } else { /* first block, no dictionary */ assert(optPtr->litFreq != NULL); if (compressedLiterals) { /* base initial cost of literals on direct frequency within src */ unsigned lit = MaxLit; HIST_count_simple(optPtr->litFreq, &lit, src, srcSize); /* use raw first block to init statistics */ optPtr->litSum = ZSTD_downscaleStats(optPtr->litFreq, MaxLit, 8, base_0possible); } { unsigned const baseLLfreqs[MaxLL+1] = { 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }; ZSTD_memcpy(optPtr->litLengthFreq, baseLLfreqs, sizeof(baseLLfreqs)); optPtr->litLengthSum = sum_u32(baseLLfreqs, MaxLL+1); } { unsigned ml; for (ml=0; ml<=MaxML; ml++) optPtr->matchLengthFreq[ml] = 1; } optPtr->matchLengthSum = MaxML+1; { unsigned const baseOFCfreqs[MaxOff+1] = { 6, 2, 1, 1, 2, 3, 4, 4, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }; ZSTD_memcpy(optPtr->offCodeFreq, baseOFCfreqs, sizeof(baseOFCfreqs)); optPtr->offCodeSum = sum_u32(baseOFCfreqs, MaxOff+1); } } } else { /* new block : scale down accumulated statistics */ if (compressedLiterals) optPtr->litSum = ZSTD_scaleStats(optPtr->litFreq, MaxLit, 12); optPtr->litLengthSum = ZSTD_scaleStats(optPtr->litLengthFreq, MaxLL, 11); optPtr->matchLengthSum = ZSTD_scaleStats(optPtr->matchLengthFreq, MaxML, 11); optPtr->offCodeSum = ZSTD_scaleStats(optPtr->offCodeFreq, MaxOff, 11); } ZSTD_setBasePrices(optPtr, optLevel); } /* ZSTD_rawLiteralsCost() : * price of literals (only) in specified segment (which length can be 0). * does not include price of literalLength symbol */ static U32 ZSTD_rawLiteralsCost(const BYTE* const literals, U32 const litLength, const optState_t* const optPtr, int optLevel) { DEBUGLOG(8, "ZSTD_rawLiteralsCost (%u literals)", litLength); if (litLength == 0) return 0; if (!ZSTD_compressedLiterals(optPtr)) return (litLength << 3) * BITCOST_MULTIPLIER; /* Uncompressed - 8 bytes per literal. */ if (optPtr->priceType == zop_predef) return (litLength*6) * BITCOST_MULTIPLIER; /* 6 bit per literal - no statistic used */ /* dynamic statistics */ { U32 price = optPtr->litSumBasePrice * litLength; U32 const litPriceMax = optPtr->litSumBasePrice - BITCOST_MULTIPLIER; U32 u; assert(optPtr->litSumBasePrice >= BITCOST_MULTIPLIER); for (u=0; u < litLength; u++) { U32 litPrice = WEIGHT(optPtr->litFreq[literals[u]], optLevel); if (UNLIKELY(litPrice > litPriceMax)) litPrice = litPriceMax; price -= litPrice; } return price; } } /* ZSTD_litLengthPrice() : * cost of literalLength symbol */ static U32 ZSTD_litLengthPrice(U32 const litLength, const optState_t* const optPtr, int optLevel) { assert(litLength <= ZSTD_BLOCKSIZE_MAX); if (optPtr->priceType == zop_predef) return WEIGHT(litLength, optLevel); /* ZSTD_LLcode() can't compute litLength price for sizes >= ZSTD_BLOCKSIZE_MAX * because it isn't representable in the zstd format. * So instead just pretend it would cost 1 bit more than ZSTD_BLOCKSIZE_MAX - 1. * In such a case, the block would be all literals. */ if (litLength == ZSTD_BLOCKSIZE_MAX) return BITCOST_MULTIPLIER + ZSTD_litLengthPrice(ZSTD_BLOCKSIZE_MAX - 1, optPtr, optLevel); /* dynamic statistics */ { U32 const llCode = ZSTD_LLcode(litLength); return (LL_bits[llCode] * BITCOST_MULTIPLIER) + optPtr->litLengthSumBasePrice - WEIGHT(optPtr->litLengthFreq[llCode], optLevel); } } /* ZSTD_getMatchPrice() : * Provides the cost of the match part (offset + matchLength) of a sequence. * Must be combined with ZSTD_fullLiteralsCost() to get the full cost of a sequence. * @offBase : sumtype, representing an offset or a repcode, and using numeric representation of ZSTD_storeSeq() * @optLevel: when <2, favors small offset for decompression speed (improved cache efficiency) */ FORCE_INLINE_TEMPLATE U32 ZSTD_getMatchPrice(U32 const offBase, U32 const matchLength, const optState_t* const optPtr, int const optLevel) { U32 price; U32 const offCode = ZSTD_highbit32(offBase); U32 const mlBase = matchLength - MINMATCH; assert(matchLength >= MINMATCH); if (optPtr->priceType == zop_predef) /* fixed scheme, does not use statistics */ return WEIGHT(mlBase, optLevel) + ((16 + offCode) * BITCOST_MULTIPLIER); /* emulated offset cost */ /* dynamic statistics */ price = (offCode * BITCOST_MULTIPLIER) + (optPtr->offCodeSumBasePrice - WEIGHT(optPtr->offCodeFreq[offCode], optLevel)); if ((optLevel<2) /*static*/ && offCode >= 20) price += (offCode-19)*2 * BITCOST_MULTIPLIER; /* handicap for long distance offsets, favor decompression speed */ /* match Length */ { U32 const mlCode = ZSTD_MLcode(mlBase); price += (ML_bits[mlCode] * BITCOST_MULTIPLIER) + (optPtr->matchLengthSumBasePrice - WEIGHT(optPtr->matchLengthFreq[mlCode], optLevel)); } price += BITCOST_MULTIPLIER / 5; /* heuristic : make matches a bit more costly to favor less sequences -> faster decompression speed */ DEBUGLOG(8, "ZSTD_getMatchPrice(ml:%u) = %u", matchLength, price); return price; } /* ZSTD_updateStats() : * assumption : literals + litLength <= iend */ static void ZSTD_updateStats(optState_t* const optPtr, U32 litLength, const BYTE* literals, U32 offBase, U32 matchLength) { /* literals */ if (ZSTD_compressedLiterals(optPtr)) { U32 u; for (u=0; u < litLength; u++) optPtr->litFreq[literals[u]] += ZSTD_LITFREQ_ADD; optPtr->litSum += litLength*ZSTD_LITFREQ_ADD; } /* literal Length */ { U32 const llCode = ZSTD_LLcode(litLength); optPtr->litLengthFreq[llCode]++; optPtr->litLengthSum++; } /* offset code : follows storeSeq() numeric representation */ { U32 const offCode = ZSTD_highbit32(offBase); assert(offCode <= MaxOff); optPtr->offCodeFreq[offCode]++; optPtr->offCodeSum++; } /* match Length */ { U32 const mlBase = matchLength - MINMATCH; U32 const mlCode = ZSTD_MLcode(mlBase); optPtr->matchLengthFreq[mlCode]++; optPtr->matchLengthSum++; } } /* ZSTD_readMINMATCH() : * function safe only for comparisons * assumption : memPtr must be at least 4 bytes before end of buffer */ MEM_STATIC U32 ZSTD_readMINMATCH(const void* memPtr, U32 length) { switch (length) { default : case 4 : return MEM_read32(memPtr); case 3 : if (MEM_isLittleEndian()) return MEM_read32(memPtr)<<8; else return MEM_read32(memPtr)>>8; } } /* Update hashTable3 up to ip (excluded) Assumption : always within prefix (i.e. not within extDict) */ static ZSTD_ALLOW_POINTER_OVERFLOW_ATTR U32 ZSTD_insertAndFindFirstIndexHash3 (const ZSTD_MatchState_t* ms, U32* nextToUpdate3, const BYTE* const ip) { U32* const hashTable3 = ms->hashTable3; U32 const hashLog3 = ms->hashLog3; const BYTE* const base = ms->window.base; U32 idx = *nextToUpdate3; U32 const target = (U32)(ip - base); size_t const hash3 = ZSTD_hash3Ptr(ip, hashLog3); assert(hashLog3 > 0); while(idx < target) { hashTable3[ZSTD_hash3Ptr(base+idx, hashLog3)] = idx; idx++; } *nextToUpdate3 = target; return hashTable3[hash3]; } /*-************************************* * Binary Tree search ***************************************/ /* ZSTD_insertBt1() : add one or multiple positions to tree. * @param ip assumed <= iend-8 . * @param target The target of ZSTD_updateTree_internal() - we are filling to this position * @return : nb of positions added */ static ZSTD_ALLOW_POINTER_OVERFLOW_ATTR U32 ZSTD_insertBt1( const ZSTD_MatchState_t* ms, const BYTE* const ip, const BYTE* const iend, U32 const target, U32 const mls, const int extDict) { const ZSTD_compressionParameters* const cParams = &ms->cParams; U32* const hashTable = ms->hashTable; U32 const hashLog = cParams->hashLog; size_t const h = ZSTD_hashPtr(ip, hashLog, mls); U32* const bt = ms->chainTable; U32 const btLog = cParams->chainLog - 1; U32 const btMask = (1 << btLog) - 1; U32 matchIndex = hashTable[h]; size_t commonLengthSmaller=0, commonLengthLarger=0; const BYTE* const base = ms->window.base; const BYTE* const dictBase = ms->window.dictBase; const U32 dictLimit = ms->window.dictLimit; const BYTE* const dictEnd = dictBase + dictLimit; const BYTE* const prefixStart = base + dictLimit; const BYTE* match; const U32 curr = (U32)(ip-base); const U32 btLow = btMask >= curr ? 0 : curr - btMask; U32* smallerPtr = bt + 2*(curr&btMask); U32* largerPtr = smallerPtr + 1; U32 dummy32; /* to be nullified at the end */ /* windowLow is based on target because * we only need positions that will be in the window at the end of the tree update. */ U32 const windowLow = ZSTD_getLowestMatchIndex(ms, target, cParams->windowLog); U32 matchEndIdx = curr+8+1; size_t bestLength = 8; U32 nbCompares = 1U << cParams->searchLog; #ifdef ZSTD_C_PREDICT U32 predictedSmall = *(bt + 2*((curr-1)&btMask) + 0); U32 predictedLarge = *(bt + 2*((curr-1)&btMask) + 1); predictedSmall += (predictedSmall>0); predictedLarge += (predictedLarge>0); #endif /* ZSTD_C_PREDICT */ DEBUGLOG(8, "ZSTD_insertBt1 (%u)", curr); assert(curr <= target); assert(ip <= iend-8); /* required for h calculation */ hashTable[h] = curr; /* Update Hash Table */ assert(windowLow > 0); for (; nbCompares && (matchIndex >= windowLow); --nbCompares) { U32* const nextPtr = bt + 2*(matchIndex & btMask); size_t matchLength = MIN(commonLengthSmaller, commonLengthLarger); /* guaranteed minimum nb of common bytes */ assert(matchIndex < curr); #ifdef ZSTD_C_PREDICT /* note : can create issues when hlog small <= 11 */ const U32* predictPtr = bt + 2*((matchIndex-1) & btMask); /* written this way, as bt is a roll buffer */ if (matchIndex == predictedSmall) { /* no need to check length, result known */ *smallerPtr = matchIndex; if (matchIndex <= btLow) { smallerPtr=&dummy32; break; } /* beyond tree size, stop the search */