/* * Copyright (c) Przemyslaw Skibinski, Yann Collet, Facebook, Inc. * 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"  #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 1024   /* 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 MEM_STATIC U32 ZSTD_bitWeight(U32 stat){    return (ZSTD_highbit32(stat+1) * BITCOST_MULTIPLIER);} MEM_STATIC U32 ZSTD_fracWeight(U32 rawStat){    U32 const stat = rawStat + 1;    U32 const hb = ZSTD_highbit32(stat);    U32 const BWeight = hb * BITCOST_MULTIPLIER;    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(U32 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;} static U32 ZSTD_downscaleStats(unsigned* table, U32 lastEltIndex, U32 shift){    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++) {        table[s] = 1 + (table[s] >> shift);        sum += table[s];    }    return sum;} /* ZSTD_scaleStats() : * reduce all elements in table is 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));} /* 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) {  /* first block : init */        if (srcSize <= ZSTD_PREDEF_THRESHOLD) {  /* heuristic */            DEBUGLOG(5, "(srcSize <= ZSTD_PREDEF_THRESHOLD) => zop_predef");            optPtr->priceType = zop_predef;        }         assert(optPtr->symbolCosts != NULL);        if (optPtr->symbolCosts->huf.repeatMode == HUF_repeat_valid) {            /* huffman table presumed generated by dictionary */            optPtr->priceType = zop_dynamic;             if (compressedLiterals) {                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 {  /* not a dictionary */             assert(optPtr->litFreq != NULL);            if (compressedLiterals) {                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);            }             {   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 : re-use previous statistics, scaled down */         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){    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 = litLength * optPtr->litSumBasePrice;        U32 u;        for (u=0; u < litLength; u++) {            assert(WEIGHT(optPtr->litFreq[literals[u]], optLevel) <= optPtr->litSumBasePrice);   /* literal cost should never be negative */            price -= WEIGHT(optPtr->litFreq[literals[u]], optLevel);        }        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);    /* We can't compute the litLength price for sizes >= ZSTD_BLOCKSIZE_MAX     * because it isn't representable in the zstd format. So instead just     * call it 1 bit more than ZSTD_BLOCKSIZE_MAX - 1. In this 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. * @offcode : expects a scale where 0,1,2 are repcodes 1-3, and 3+ are real_offsets+2 * @optLevel: when <2, favors small offset for decompression speed (improved cache efficiency) */FORCE_INLINE_TEMPLATE U32ZSTD_getMatchPrice(U32 const offcode,                   U32 const matchLength,             const optState_t* const optPtr,                   int const optLevel){    U32 price;    U32 const offCode = ZSTD_highbit32(STORED_TO_OFFBASE(offcode));    U32 const mlBase = matchLength - MINMATCH;    assert(matchLength >= MINMATCH);     if (optPtr->priceType == zop_predef)  /* fixed scheme, do not use statistics */        return WEIGHT(mlBase, optLevel) + ((16 + offCode) * BITCOST_MULTIPLIER);     /* 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 + litLengtn <= iend */static void ZSTD_updateStats(optState_t* const optPtr,                             U32 litLength, const BYTE* literals,                             U32 offsetCode, 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 : expected to follow storeSeq() numeric representation */    {   U32 const offCode = ZSTD_highbit32(STORED_TO_OFFBASE(offsetCode));        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 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 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 */            smallerPtr = nextPtr+1;               /* new "smaller" => larger of match */            matchIndex = nextPtr[1];              /* new matchIndex larger than previous (closer to current) */            predictedSmall = predictPtr[1] + (predictPtr[1]>0);            continue;        }        if (matchIndex == predictedLarge) {            *largerPtr = matchIndex;            if (matchIndex <= btLow) { largerPtr=&dummy32; break; }   /* beyond tree size, stop the search */            largerPtr = nextPtr;            matchIndex = nextPtr[0];            predictedLarge = predictPtr[0] + (predictPtr[0]>0);            continue;        }#endif         if (!extDict || (matchIndex+matchLength >= dictLimit)) {            assert(matchIndex+matchLength >= dictLimit);   /* might be wrong if actually extDict */            match = base + matchIndex;            matchLength += ZSTD_count(ip+matchLength, match+matchLength, iend);        } else {            match = dictBase + matchIndex;            matchLength += ZSTD_count_2segments(ip+matchLength, match+matchLength, iend, dictEnd, prefixStart);            if (matchIndex+matchLength >= dictLimit)                match = base + matchIndex;   /* to prepare for next usage of match[matchLength] */        }         if (matchLength > bestLength) {            bestLength = matchLength;            if (matchLength > matchEndIdx - matchIndex)                matchEndIdx = matchIndex + (U32)matchLength;        } 

Lines 1–500 of 1446. Load more