/src/zstd/lib/compress/zstd_compress_sequences.c

Source (jump to first uncovered line)
/*
 * 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.
 */

 /*-*************************************
 *  Dependencies
 ***************************************/
#include "zstd_compress_sequences.h"

/**
 * -log2(x / 256) lookup table for x in [0, 256).
 * If x == 0: Return 0
 * Else: Return floor(-log2(x / 256) * 256)
 */
static unsigned const kInverseProbabilityLog256[256] = {
    0,    2048, 1792, 1642, 1536, 1453, 1386, 1329, 1280, 1236, 1197, 1162,
    1130, 1100, 1073, 1047, 1024, 1001, 980,  960,  941,  923,  906,  889,
    874,  859,  844,  830,  817,  804,  791,  779,  768,  756,  745,  734,
    724,  714,  704,  694,  685,  676,  667,  658,  650,  642,  633,  626,
    618,  610,  603,  595,  588,  581,  574,  567,  561,  554,  548,  542,
    535,  529,  523,  517,  512,  506,  500,  495,  489,  484,  478,  473,
    468,  463,  458,  453,  448,  443,  438,  434,  429,  424,  420,  415,
    411,  407,  402,  398,  394,  390,  386,  382,  377,  373,  370,  366,
    362,  358,  354,  350,  347,  343,  339,  336,  332,  329,  325,  322,
    318,  315,  311,  308,  305,  302,  298,  295,  292,  289,  286,  282,
    279,  276,  273,  270,  267,  264,  261,  258,  256,  253,  250,  247,
    244,  241,  239,  236,  233,  230,  228,  225,  222,  220,  217,  215,
    212,  209,  207,  204,  202,  199,  197,  194,  192,  190,  187,  185,
    182,  180,  178,  175,  173,  171,  168,  166,  164,  162,  159,  157,
    155,  153,  151,  149,  146,  144,  142,  140,  138,  136,  134,  132,
    130,  128,  126,  123,  121,  119,  117,  115,  114,  112,  110,  108,
    106,  104,  102,  100,  98,   96,   94,   93,   91,   89,   87,   85,
    83,   82,   80,   78,   76,   74,   73,   71,   69,   67,   66,   64,
    62,   61,   59,   57,   55,   54,   52,   50,   49,   47,   46,   44,
    42,   41,   39,   37,   36,   34,   33,   31,   30,   28,   26,   25,
    23,   22,   20,   19,   17,   16,   14,   13,   11,   10,   8,    7,
    5,    4,    2,    1,
};

static unsigned ZSTD_getFSEMaxSymbolValue(FSE_CTable const* ctable) {
  void const* ptr = ctable;
  U16 const* u16ptr = (U16 const*)ptr;
  U32 const maxSymbolValue = MEM_read16(u16ptr + 1);
  return maxSymbolValue;
}

/**
 * Returns true if we should use ncount=-1 else we should
 * use ncount=1 for low probability symbols instead.
 */
static unsigned ZSTD_useLowProbCount(size_t const nbSeq)
{
    /* Heuristic: This should cover most blocks <= 16K and
     * start to fade out after 16K to about 32K depending on
     * compressibility.
     */
    return nbSeq >= 2048;
}

/**
 * Returns the cost in bytes of encoding the normalized count header.
 * Returns an error if any of the helper functions return an error.
 */
static size_t ZSTD_NCountCost(unsigned const* count, unsigned const max,
                              size_t const nbSeq, unsigned const FSELog)
{
    BYTE wksp[FSE_NCOUNTBOUND];
    S16 norm[MaxSeq + 1];
    const U32 tableLog = FSE_optimalTableLog(FSELog, nbSeq, max);
    FORWARD_IF_ERROR(FSE_normalizeCount(norm, tableLog, count, nbSeq, max, ZSTD_useLowProbCount(nbSeq)), "");
    return FSE_writeNCount(wksp, sizeof(wksp), norm, max, tableLog);
}

/**
 * Returns the cost in bits of encoding the distribution described by count
 * using the entropy bound.
 */
static size_t ZSTD_entropyCost(unsigned const* count, unsigned const max, size_t const total)
{
    unsigned cost = 0;
    unsigned s;

    assert(total > 0);
    for (s = 0; s <= max; ++s) {
        unsigned norm = (unsigned)((256 * count[s]) / total);
        if (count[s] != 0 && norm == 0)
            norm = 1;
        assert(count[s] < total);
        cost += count[s] * kInverseProbabilityLog256[norm];
    }
    return cost >> 8;
}

/**
 * Returns the cost in bits of encoding the distribution in count using ctable.
 * Returns an error if ctable cannot represent all the symbols in count.
 */
size_t ZSTD_fseBitCost(
    FSE_CTable const* ctable,
    unsigned const* count,
    unsigned const max)
{
    unsigned const kAccuracyLog = 8;
    size_t cost = 0;
    unsigned s;
    FSE_CState_t cstate;
    FSE_initCState(&cstate, ctable);
    if (ZSTD_getFSEMaxSymbolValue(ctable) < max) {
        DEBUGLOG(5, "Repeat FSE_CTable has maxSymbolValue %u < %u",
                    ZSTD_getFSEMaxSymbolValue(ctable), max);
        return ERROR(GENERIC);
    }
    for (s = 0; s <= max; ++s) {
        unsigned const tableLog = cstate.stateLog;
        unsigned const badCost = (tableLog + 1) << kAccuracyLog;
        unsigned const bitCost = FSE_bitCost(cstate.symbolTT, tableLog, s, kAccuracyLog);
        if (count[s] == 0)
            continue;
        if (bitCost >= badCost) {
            DEBUGLOG(5, "Repeat FSE_CTable has Prob[%u] == 0", s);
            return ERROR(GENERIC);
        }
        cost += (size_t)count[s] * bitCost;
    }
    return cost >> kAccuracyLog;
}

/**
 * Returns the cost in bits of encoding the distribution in count using the
 * table described by norm. The max symbol support by norm is assumed >= max.
 * norm must be valid for every symbol with non-zero probability in count.
 */
size_t ZSTD_crossEntropyCost(short const* norm, unsigned accuracyLog,
                             unsigned const* count, unsigned const max)
{
    unsigned const shift = 8 - accuracyLog;
    size_t cost = 0;
    unsigned s;
    assert(accuracyLog <= 8);
    for (s = 0; s <= max; ++s) {
        unsigned const normAcc = (norm[s] != -1) ? (unsigned)norm[s] : 1;
        unsigned const norm256 = normAcc << shift;
        assert(norm256 > 0);
        assert(norm256 < 256);
        cost += count[s] * kInverseProbabilityLog256[norm256];
    }
    return cost >> 8;
}

SymbolEncodingType_e
ZSTD_selectEncodingType(
        FSE_repeat* repeatMode, unsigned const* count, unsigned const max,
        size_t const mostFrequent, size_t nbSeq, unsigned const FSELog,
        FSE_CTable const* prevCTable,
        short const* defaultNorm, U32 defaultNormLog,
        ZSTD_DefaultPolicy_e const isDefaultAllowed,
        ZSTD_strategy const strategy)
{
    ZSTD_STATIC_ASSERT(ZSTD_defaultDisallowed == 0 && ZSTD_defaultAllowed != 0);
    if (mostFrequent == nbSeq) {
        *repeatMode = FSE_repeat_none;
        if (isDefaultAllowed && nbSeq <= 2) {
            /* Prefer set_basic over set_rle when there are 2 or fewer symbols,
             * since RLE uses 1 byte, but set_basic uses 5-6 bits per symbol.
             * If basic encoding isn't possible, always choose RLE.
             */
            DEBUGLOG(5, "Selected set_basic");
            return set_basic;
        }
        DEBUGLOG(5, "Selected set_rle");
        return set_rle;
    }
    if (strategy < ZSTD_lazy) {
        if (isDefaultAllowed) {
            size_t const staticFse_nbSeq_max = 1000;
            size_t const mult = 10 - strategy;
            size_t const baseLog = 3;
            size_t const dynamicFse_nbSeq_min = (((size_t)1 << defaultNormLog) * mult) >> baseLog;  /* 28-36 for offset, 56-72 for lengths */
            assert(defaultNormLog >= 5 && defaultNormLog <= 6);  /* xx_DEFAULTNORMLOG */
            assert(mult <= 9 && mult >= 7);
            if ( (*repeatMode == FSE_repeat_valid)
              && (nbSeq < staticFse_nbSeq_max) ) {
                DEBUGLOG(5, "Selected set_repeat");
                return set_repeat;
            }
            if ( (nbSeq < dynamicFse_nbSeq_min)
              || (mostFrequent < (nbSeq >> (defaultNormLog-1))) ) {
                DEBUGLOG(5, "Selected set_basic");
                /* The format allows default tables to be repeated, but it isn't useful.
                 * When using simple heuristics to select encoding type, we don't want
                 * to confuse these tables with dictionaries. When running more careful
                 * analysis, we don't need to waste time checking both repeating tables
                 * and default tables.
                 */
                *repeatMode = FSE_repeat_none;
                return set_basic;
            }
        }
    } else {
        size_t const basicCost = isDefaultAllowed ? ZSTD_crossEntropyCost(defaultNorm, defaultNormLog, count, max) : ERROR(GENERIC);
        size_t const repeatCost = *repeatMode != FSE_repeat_none ? ZSTD_fseBitCost(prevCTable, count, max) : ERROR(GENERIC);
        size_t const NCountCost = ZSTD_NCountCost(count, max, nbSeq, FSELog);
        size_t const compressedCost = (NCountCost << 3) + ZSTD_entropyCost(count, max, nbSeq);

        if (isDefaultAllowed) {
            assert(!ZSTD_isError(basicCost));
            assert(!(*repeatMode == FSE_repeat_valid && ZSTD_isError(repeatCost)));
        }
        assert(!ZSTD_isError(NCountCost));
        assert(compressedCost < ERROR(maxCode));
        DEBUGLOG(5, "Estimated bit costs: basic=%u\trepeat=%u\tcompressed=%u",
                    (unsigned)basicCost, (unsigned)repeatCost, (unsigned)compressedCost);
        if (basicCost <= repeatCost && basicCost <= compressedCost) {
            DEBUGLOG(5, "Selected set_basic");
            assert(isDefaultAllowed);
            *repeatMode = FSE_repeat_none;
            return set_basic;
        }
        if (repeatCost <= compressedCost) {
            DEBUGLOG(5, "Selected set_repeat");
            assert(!ZSTD_isError(repeatCost));
            return set_repeat;
        }
        assert(compressedCost < basicCost && compressedCost < repeatCost);
    }
    DEBUGLOG(5, "Selected set_compressed");
    *repeatMode = FSE_repeat_check;
    return set_compressed;
}

typedef struct {
    S16 norm[MaxSeq + 1];
    U32 wksp[FSE_BUILD_CTABLE_WORKSPACE_SIZE_U32(MaxSeq, MaxFSELog)];
} ZSTD_BuildCTableWksp;

size_t
ZSTD_buildCTable(void* dst, size_t dstCapacity,
                FSE_CTable* nextCTable, U32 FSELog, SymbolEncodingType_e type,
                unsigned* count, U32 max,
                const BYTE* codeTable, size_t nbSeq,
                const S16* defaultNorm, U32 defaultNormLog, U32 defaultMax,
                const FSE_CTable* prevCTable, size_t prevCTableSize,
                void* entropyWorkspace, size_t entropyWorkspaceSize)
{
    BYTE* op = (BYTE*)dst;
    const BYTE* const oend = op + dstCapacity;
    DEBUGLOG(6, "ZSTD_buildCTable (dstCapacity=%u)", (unsigned)dstCapacity);

    switch (type) {
    case set_rle:
        FORWARD_IF_ERROR(FSE_buildCTable_rle(nextCTable, (BYTE)max), "");
        RETURN_ERROR_IF(dstCapacity==0, dstSize_tooSmall, "not enough space");
        *op = codeTable[0];
        return 1;
    case set_repeat:
        ZSTD_memcpy(nextCTable, prevCTable, prevCTableSize);
        return 0;
    case set_basic:
        FORWARD_IF_ERROR(FSE_buildCTable_wksp(nextCTable, defaultNorm, defaultMax, defaultNormLog, entropyWorkspace, entropyWorkspaceSize), "");  /* note : could be pre-calculated */
        return 0;
    case set_compressed: {
        ZSTD_BuildCTableWksp* wksp = (ZSTD_BuildCTableWksp*)entropyWorkspace;
        size_t nbSeq_1 = nbSeq;
        const U32 tableLog = FSE_optimalTableLog(FSELog, nbSeq, max);
        if (count[codeTable[nbSeq-1]] > 1) {
            count[codeTable[nbSeq-1]]--;
            nbSeq_1--;
        }
        assert(nbSeq_1 > 1);
        assert(entropyWorkspaceSize >= sizeof(ZSTD_BuildCTableWksp));
        (void)entropyWorkspaceSize;
        FORWARD_IF_ERROR(FSE_normalizeCount(wksp->norm, tableLog, count, nbSeq_1, max, ZSTD_useLowProbCount(nbSeq_1)), "FSE_normalizeCount failed");
        assert(oend >= op);
        {   size_t const NCountSize = FSE_writeNCount(op, (size_t)(oend - op), wksp->norm, max, tableLog);   /* overflow protected */
            FORWARD_IF_ERROR(NCountSize, "FSE_writeNCount failed");
            FORWARD_IF_ERROR(FSE_buildCTable_wksp(nextCTable, wksp->norm, max, tableLog, wksp->wksp, sizeof(wksp->wksp)), "FSE_buildCTable_wksp failed");
            return NCountSize;
        }
    }
    default: assert(0); RETURN_ERROR(GENERIC, "impossible to reach");
    }
}

FORCE_INLINE_TEMPLATE size_t
ZSTD_encodeSequences_body(
            void* dst, size_t dstCapacity,
            FSE_CTable const* CTable_MatchLength, BYTE const* mlCodeTable,
            FSE_CTable const* CTable_OffsetBits, BYTE const* ofCodeTable,
            FSE_CTable const* CTable_LitLength, BYTE const* llCodeTable,
            SeqDef const* sequences, size_t nbSeq, int longOffsets)
{
    BIT_CStream_t blockStream;
    FSE_CState_t  stateMatchLength;
    FSE_CState_t  stateOffsetBits;
    FSE_CState_t  stateLitLength;

    RETURN_ERROR_IF(
        ERR_isError(BIT_initCStream(&blockStream, dst, dstCapacity)),
        dstSize_tooSmall, "not enough space remaining");
    DEBUGLOG(6, "available space for bitstream : %i  (dstCapacity=%u)",
                (int)(blockStream.endPtr - blockStream.startPtr),
                (unsigned)dstCapacity);

    /* first symbols */
    FSE_initCState2(&stateMatchLength, CTable_MatchLength, mlCodeTable[nbSeq-1]);
    FSE_initCState2(&stateOffsetBits,  CTable_OffsetBits,  ofCodeTable[nbSeq-1]);
    FSE_initCState2(&stateLitLength,   CTable_LitLength,   llCodeTable[nbSeq-1]);
    BIT_addBits(&blockStream, sequences[nbSeq-1].litLength, LL_bits[llCodeTable[nbSeq-1]]);
    if (MEM_32bits()) BIT_flushBits(&blockStream);
    BIT_addBits(&blockStream, sequences[nbSeq-1].mlBase, ML_bits[mlCodeTable[nbSeq-1]]);
    if (MEM_32bits()) BIT_flushBits(&blockStream);
    if (longOffsets) {
        U32 const ofBits = ofCodeTable[nbSeq-1];
        unsigned const extraBits = ofBits - MIN(ofBits, STREAM_ACCUMULATOR_MIN-1);
        if (extraBits) {
            BIT_addBits(&blockStream, sequences[nbSeq-1].offBase, extraBits);
            BIT_flushBits(&blockStream);
        }
        BIT_addBits(&blockStream, sequences[nbSeq-1].offBase >> extraBits,
                    ofBits - extraBits);
    } else {
        BIT_addBits(&blockStream, sequences[nbSeq-1].offBase, ofCodeTable[nbSeq-1]);
    }
    BIT_flushBits(&blockStream);

    {   size_t n;
        for (n=nbSeq-2 ; n<nbSeq ; n--) {      /* intentional underflow */
            BYTE const llCode = llCodeTable[n];
            BYTE const ofCode = ofCodeTable[n];
            BYTE const mlCode = mlCodeTable[n];
            U32  const llBits = LL_bits[llCode];
            U32  const ofBits = ofCode;
            U32  const mlBits = ML_bits[mlCode];
            DEBUGLOG(6, "encoding: litlen:%2u - matchlen:%2u - offCode:%7u",
                        (unsigned)sequences[n].litLength,
                        (unsigned)sequences[n].mlBase + MINMATCH,
                        (unsigned)sequences[n].offBase);
                                                                            /* 32b*/  /* 64b*/
                                                                            /* (7)*/  /* (7)*/
            FSE_encodeSymbol(&blockStream, &stateOffsetBits, ofCode);       /* 15 */  /* 15 */
            FSE_encodeSymbol(&blockStream, &stateMatchLength, mlCode);      /* 24 */  /* 24 */
            if (MEM_32bits()) BIT_flushBits(&blockStream);                  /* (7)*/
            FSE_encodeSymbol(&blockStream, &stateLitLength, llCode);        /* 16 */  /* 33 */
            if (MEM_32bits() || (ofBits+mlBits+llBits >= 64-7-(LLFSELog+MLFSELog+OffFSELog)))
                BIT_flushBits(&blockStream);                                /* (7)*/
            BIT_addBits(&blockStream, sequences[n].litLength, llBits);
            if (MEM_32bits() && ((llBits+mlBits)>24)) BIT_flushBits(&blockStream);
            BIT_addBits(&blockStream, sequences[n].mlBase, mlBits);
            if (MEM_32bits() || (ofBits+mlBits+llBits > 56)) BIT_flushBits(&blockStream);
            if (longOffsets) {
                unsigned const extraBits = ofBits - MIN(ofBits, STREAM_ACCUMULATOR_MIN-1);
                if (extraBits) {
                    BIT_addBits(&blockStream, sequences[n].offBase, extraBits);
                    BIT_flushBits(&blockStream);                            /* (7)*/
                }
                BIT_addBits(&blockStream, sequences[n].offBase >> extraBits,
                            ofBits - extraBits);                            /* 31 */
            } else {
                BIT_addBits(&blockStream, sequences[n].offBase, ofBits);     /* 31 */
            }
            BIT_flushBits(&blockStream);                                    /* (7)*/
            DEBUGLOG(7, "remaining space : %i", (int)(blockStream.endPtr - blockStream.ptr));
    }   }

    DEBUGLOG(6, "ZSTD_encodeSequences: flushing ML state with %u bits", stateMatchLength.stateLog);
    FSE_flushCState(&blockStream, &stateMatchLength);
    DEBUGLOG(6, "ZSTD_encodeSequences: flushing Off state with %u bits", stateOffsetBits.stateLog);
    FSE_flushCState(&blockStream, &stateOffsetBits);
    DEBUGLOG(6, "ZSTD_encodeSequences: flushing LL state with %u bits", stateLitLength.stateLog);
    FSE_flushCState(&blockStream, &stateLitLength);

    {   size_t const streamSize = BIT_closeCStream(&blockStream);
        RETURN_ERROR_IF(streamSize==0, dstSize_tooSmall, "not enough space");
        return streamSize;
    }
}

static size_t
ZSTD_encodeSequences_default(
            void* dst, size_t dstCapacity,
            FSE_CTable const* CTable_MatchLength, BYTE const* mlCodeTable,
            FSE_CTable const* CTable_OffsetBits, BYTE const* ofCodeTable,
            FSE_CTable const* CTable_LitLength, BYTE const* llCodeTable,
            SeqDef const* sequences, size_t nbSeq, int longOffsets)
{
    return ZSTD_encodeSequences_body(dst, dstCapacity,
                                    CTable_MatchLength, mlCodeTable,
                                    CTable_OffsetBits, ofCodeTable,
                                    CTable_LitLength, llCodeTable,
                                    sequences, nbSeq, longOffsets);
}


#if DYNAMIC_BMI2

static BMI2_TARGET_ATTRIBUTE size_t
ZSTD_encodeSequences_bmi2(
            void* dst, size_t dstCapacity,
            FSE_CTable const* CTable_MatchLength, BYTE const* mlCodeTable,
            FSE_CTable const* CTable_OffsetBits, BYTE const* ofCodeTable,
            FSE_CTable const* CTable_LitLength, BYTE const* llCodeTable,
            SeqDef const* sequences, size_t nbSeq, int longOffsets)
{
    return ZSTD_encodeSequences_body(dst, dstCapacity,
                                    CTable_MatchLength, mlCodeTable,
                                    CTable_OffsetBits, ofCodeTable,
                                    CTable_LitLength, llCodeTable,
                                    sequences, nbSeq, longOffsets);
}

#endif

size_t ZSTD_encodeSequences(
            void* dst, size_t dstCapacity,
            FSE_CTable const* CTable_MatchLength, BYTE const* mlCodeTable,
            FSE_CTable const* CTable_OffsetBits, BYTE const* ofCodeTable,
            FSE_CTable const* CTable_LitLength, BYTE const* llCodeTable,
            SeqDef const* sequences, size_t nbSeq, int longOffsets, int bmi2)
{
    DEBUGLOG(5, "ZSTD_encodeSequences: dstCapacity = %u", (unsigned)dstCapacity);
#if DYNAMIC_BMI2
    if (bmi2) {
        return ZSTD_encodeSequences_bmi2(dst, dstCapacity,
                                         CTable_MatchLength, mlCodeTable,
                                         CTable_OffsetBits, ofCodeTable,
                                         CTable_LitLength, llCodeTable,
                                         sequences, nbSeq, longOffsets);
    }
#endif
    (void)bmi2;
    return ZSTD_encodeSequences_default(dst, dstCapacity,
                                        CTable_MatchLength, mlCodeTable,
                                        CTable_OffsetBits, ofCodeTable,
                                        CTable_LitLength, llCodeTable,
                                        sequences, nbSeq, longOffsets);
}

Coverage Report

Created: 2025-03-15 06:58

Line	Count	Source (jump to first uncovered line)
1		/*
2		* Copyright (c) Meta Platforms, Inc. and affiliates.
3		* All rights reserved.
4		*
5		* This source code is licensed under both the BSD-style license (found in the
6		* LICENSE file in the root directory of this source tree) and the GPLv2 (found
7		* in the COPYING file in the root directory of this source tree).
8		* You may select, at your option, one of the above-listed licenses.
9		*/
10
11		/-************************************
12		* Dependencies
13		***************************************/
14		#include "zstd_compress_sequences.h"
15
16		/**
17		* -log2(x / 256) lookup table for x in [0, 256).
18		* If x == 0: Return 0
19		* Else: Return floor(-log2(x / 256) * 256)
20		*/
21		static unsigned const kInverseProbabilityLog256[256] = {
22		0, 2048, 1792, 1642, 1536, 1453, 1386, 1329, 1280, 1236, 1197, 1162,
23		1130, 1100, 1073, 1047, 1024, 1001, 980, 960, 941, 923, 906, 889,
24		874, 859, 844, 830, 817, 804, 791, 779, 768, 756, 745, 734,
25		724, 714, 704, 694, 685, 676, 667, 658, 650, 642, 633, 626,
26		618, 610, 603, 595, 588, 581, 574, 567, 561, 554, 548, 542,
27		535, 529, 523, 517, 512, 506, 500, 495, 489, 484, 478, 473,
28		468, 463, 458, 453, 448, 443, 438, 434, 429, 424, 420, 415,
29		411, 407, 402, 398, 394, 390, 386, 382, 377, 373, 370, 366,
30		362, 358, 354, 350, 347, 343, 339, 336, 332, 329, 325, 322,
31		318, 315, 311, 308, 305, 302, 298, 295, 292, 289, 286, 282,
32		279, 276, 273, 270, 267, 264, 261, 258, 256, 253, 250, 247,
33		244, 241, 239, 236, 233, 230, 228, 225, 222, 220, 217, 215,
34		212, 209, 207, 204, 202, 199, 197, 194, 192, 190, 187, 185,
35		182, 180, 178, 175, 173, 171, 168, 166, 164, 162, 159, 157,
36		155, 153, 151, 149, 146, 144, 142, 140, 138, 136, 134, 132,
37		130, 128, 126, 123, 121, 119, 117, 115, 114, 112, 110, 108,
38		106, 104, 102, 100, 98, 96, 94, 93, 91, 89, 87, 85,
39		83, 82, 80, 78, 76, 74, 73, 71, 69, 67, 66, 64,
40		62, 61, 59, 57, 55, 54, 52, 50, 49, 47, 46, 44,
41		42, 41, 39, 37, 36, 34, 33, 31, 30, 28, 26, 25,
42		23, 22, 20, 19, 17, 16, 14, 13, 11, 10, 8, 7,
43		5, 4, 2, 1,
44		};
45
46	0	static unsigned ZSTD_getFSEMaxSymbolValue(FSE_CTable const* ctable) {
47	0	void const* ptr = ctable;
48	0	U16 const* u16ptr = (U16 const*)ptr;
49	0	U32 const maxSymbolValue = MEM_read16(u16ptr + 1);
50	0	return maxSymbolValue;
51	0	}
52
53		/**
54		* Returns true if we should use ncount=-1 else we should
55		* use ncount=1 for low probability symbols instead.
56		*/
57		static unsigned ZSTD_useLowProbCount(size_t const nbSeq)
58	0	{
59		/* Heuristic: This should cover most blocks <= 16K and
60		* start to fade out after 16K to about 32K depending on
61		* compressibility.
62		*/
63	0	return nbSeq >= 2048;
64	0	}
65
66		/**
67		* Returns the cost in bytes of encoding the normalized count header.
68		* Returns an error if any of the helper functions return an error.
69		*/
70		static size_t ZSTD_NCountCost(unsigned const* count, unsigned const max,
71		size_t const nbSeq, unsigned const FSELog)
72	0	{
73	0	BYTE wksp[FSE_NCOUNTBOUND];
74	0	S16 norm[MaxSeq + 1];
75	0	const U32 tableLog = FSE_optimalTableLog(FSELog, nbSeq, max);
76	0	FORWARD_IF_ERROR(FSE_normalizeCount(norm, tableLog, count, nbSeq, max, ZSTD_useLowProbCount(nbSeq)), "");
77	0	return FSE_writeNCount(wksp, sizeof(wksp), norm, max, tableLog);
78	0	}
79
80		/**
81		* Returns the cost in bits of encoding the distribution described by count
82		* using the entropy bound.
83		*/
84		static size_t ZSTD_entropyCost(unsigned const* count, unsigned const max, size_t const total)
85	0	{
86	0	unsigned cost = 0;
87	0	unsigned s;
88
89	0	assert(total > 0);
90	0	for (s = 0; s <= max; ++s) {
91	0	unsigned norm = (unsigned)((256 * count[s]) / total);
92	0	if (count[s] != 0 && norm == 0)
93	0	norm = 1;
94	0	assert(count[s] < total);
95	0	cost += count[s] * kInverseProbabilityLog256[norm];
96	0	}
97	0	return cost >> 8;
98	0	}
99
100		/**
101		* Returns the cost in bits of encoding the distribution in count using ctable.
102		* Returns an error if ctable cannot represent all the symbols in count.
103		*/
104		size_t ZSTD_fseBitCost(
105		FSE_CTable const* ctable,
106		unsigned const* count,
107		unsigned const max)
108	0	{
109	0	unsigned const kAccuracyLog = 8;
110	0	size_t cost = 0;
111	0	unsigned s;
112	0	FSE_CState_t cstate;
113	0	FSE_initCState(&cstate, ctable);
114	0	if (ZSTD_getFSEMaxSymbolValue(ctable) < max) {
115	0	DEBUGLOG(5, "Repeat FSE_CTable has maxSymbolValue %u < %u",
116	0	ZSTD_getFSEMaxSymbolValue(ctable), max);
117	0	return ERROR(GENERIC);
118	0	}
119	0	for (s = 0; s <= max; ++s) {
120	0	unsigned const tableLog = cstate.stateLog;
121	0	unsigned const badCost = (tableLog + 1) << kAccuracyLog;
122	0	unsigned const bitCost = FSE_bitCost(cstate.symbolTT, tableLog, s, kAccuracyLog);
123	0	if (count[s] == 0)
124	0	continue;
125	0	if (bitCost >= badCost) {
126	0	DEBUGLOG(5, "Repeat FSE_CTable has Prob[%u] == 0", s);
127	0	return ERROR(GENERIC);
128	0	}
129	0	cost += (size_t)count[s] * bitCost;
130	0	}
131	0	return cost >> kAccuracyLog;
132	0	}
133
134		/**
135		* Returns the cost in bits of encoding the distribution in count using the
136		* table described by norm. The max symbol support by norm is assumed >= max.
137		* norm must be valid for every symbol with non-zero probability in count.
138		*/
139		size_t ZSTD_crossEntropyCost(short const* norm, unsigned accuracyLog,
140		unsigned const* count, unsigned const max)
141	0	{
142	0	unsigned const shift = 8 - accuracyLog;
143	0	size_t cost = 0;
144	0	unsigned s;
145	0	assert(accuracyLog <= 8);
146	0	for (s = 0; s <= max; ++s) {
147	0	unsigned const normAcc = (norm[s] != -1) ? (unsigned)norm[s] : 1;
148	0	unsigned const norm256 = normAcc << shift;
149	0	assert(norm256 > 0);
150	0	assert(norm256 < 256);
151	0	cost += count[s] * kInverseProbabilityLog256[norm256];
152	0	}
153	0	return cost >> 8;
154	0	}
155
156		SymbolEncodingType_e
157		ZSTD_selectEncodingType(
158		FSE_repeat* repeatMode, unsigned const* count, unsigned const max,
159		size_t const mostFrequent, size_t nbSeq, unsigned const FSELog,
160		FSE_CTable const* prevCTable,
161		short const* defaultNorm, U32 defaultNormLog,
162		ZSTD_DefaultPolicy_e const isDefaultAllowed,
163		ZSTD_strategy const strategy)
164	0	{
165	0	ZSTD_STATIC_ASSERT(ZSTD_defaultDisallowed == 0 && ZSTD_defaultAllowed != 0);
166	0	if (mostFrequent == nbSeq) {
167	0	*repeatMode = FSE_repeat_none;
168	0	if (isDefaultAllowed && nbSeq <= 2) {
169		/* Prefer set_basic over set_rle when there are 2 or fewer symbols,
170		* since RLE uses 1 byte, but set_basic uses 5-6 bits per symbol.
171		* If basic encoding isn't possible, always choose RLE.
172		*/
173	0	DEBUGLOG(5, "Selected set_basic");
174	0	return set_basic;
175	0	}
176	0	DEBUGLOG(5, "Selected set_rle");
177	0	return set_rle;
178	0	}
179	0	if (strategy < ZSTD_lazy) {
180	0	if (isDefaultAllowed) {
181	0	size_t const staticFse_nbSeq_max = 1000;
182	0	size_t const mult = 10 - strategy;
183	0	size_t const baseLog = 3;
184	0	size_t const dynamicFse_nbSeq_min = (((size_t)1 << defaultNormLog) * mult) >> baseLog; /* 28-36 for offset, 56-72 for lengths */
185	0	assert(defaultNormLog >= 5 && defaultNormLog <= 6); /* xx_DEFAULTNORMLOG */
186	0	assert(mult <= 9 && mult >= 7);
187	0	if ( (*repeatMode == FSE_repeat_valid)
188	0	&& (nbSeq < staticFse_nbSeq_max) ) {
189	0	DEBUGLOG(5, "Selected set_repeat");
190	0	return set_repeat;
191	0	}
192	0	if ( (nbSeq < dynamicFse_nbSeq_min)
193	0	\|\| (mostFrequent < (nbSeq >> (defaultNormLog-1))) ) {
194	0	DEBUGLOG(5, "Selected set_basic");
195		/* The format allows default tables to be repeated, but it isn't useful.
196		* When using simple heuristics to select encoding type, we don't want
197		* to confuse these tables with dictionaries. When running more careful
198		* analysis, we don't need to waste time checking both repeating tables
199		* and default tables.
200		*/
201	0	*repeatMode = FSE_repeat_none;
202	0	return set_basic;
203	0	}
204	0	}
205	0	} else {
206	0	size_t const basicCost = isDefaultAllowed ? ZSTD_crossEntropyCost(defaultNorm, defaultNormLog, count, max) : ERROR(GENERIC);
207	0	size_t const repeatCost = *repeatMode != FSE_repeat_none ? ZSTD_fseBitCost(prevCTable, count, max) : ERROR(GENERIC);
208	0	size_t const NCountCost = ZSTD_NCountCost(count, max, nbSeq, FSELog);
209	0	size_t const compressedCost = (NCountCost << 3) + ZSTD_entropyCost(count, max, nbSeq);
210
211	0	if (isDefaultAllowed) {
212	0	assert(!ZSTD_isError(basicCost));
213	0	assert(!(*repeatMode == FSE_repeat_valid && ZSTD_isError(repeatCost)));
214	0	}
215	0	assert(!ZSTD_isError(NCountCost));
216	0	assert(compressedCost < ERROR(maxCode));
217	0	DEBUGLOG(5, "Estimated bit costs: basic=%u\trepeat=%u\tcompressed=%u",
218	0	(unsigned)basicCost, (unsigned)repeatCost, (unsigned)compressedCost);
219	0	if (basicCost <= repeatCost && basicCost <= compressedCost) {
220	0	DEBUGLOG(5, "Selected set_basic");
221	0	assert(isDefaultAllowed);
222	0	*repeatMode = FSE_repeat_none;
223	0	return set_basic;
224	0	}
225	0	if (repeatCost <= compressedCost) {
226	0	DEBUGLOG(5, "Selected set_repeat");
227	0	assert(!ZSTD_isError(repeatCost));
228	0	return set_repeat;
229	0	}
230	0	assert(compressedCost < basicCost && compressedCost < repeatCost);
231	0	}
232	0	DEBUGLOG(5, "Selected set_compressed");
233	0	*repeatMode = FSE_repeat_check;
234	0	return set_compressed;
235	0	}
236
237		typedef struct {
238		S16 norm[MaxSeq + 1];
239		U32 wksp[FSE_BUILD_CTABLE_WORKSPACE_SIZE_U32(MaxSeq, MaxFSELog)];
240		} ZSTD_BuildCTableWksp;
241
242		size_t
243		ZSTD_buildCTable(void* dst, size_t dstCapacity,
244		FSE_CTable* nextCTable, U32 FSELog, SymbolEncodingType_e type,
245		unsigned* count, U32 max,
246		const BYTE* codeTable, size_t nbSeq,
247		const S16* defaultNorm, U32 defaultNormLog, U32 defaultMax,
248		const FSE_CTable* prevCTable, size_t prevCTableSize,
249		void* entropyWorkspace, size_t entropyWorkspaceSize)
250	0	{
251	0	BYTE* op = (BYTE*)dst;
252	0	const BYTE* const oend = op + dstCapacity;
253	0	DEBUGLOG(6, "ZSTD_buildCTable (dstCapacity=%u)", (unsigned)dstCapacity);
254
255	0	switch (type) {
256	0	case set_rle:
257	0	FORWARD_IF_ERROR(FSE_buildCTable_rle(nextCTable, (BYTE)max), "");
258	0	RETURN_ERROR_IF(dstCapacity==0, dstSize_tooSmall, "not enough space");
259	0	*op = codeTable[0];
260	0	return 1;
261	0	case set_repeat:
262	0	ZSTD_memcpy(nextCTable, prevCTable, prevCTableSize);
263	0	return 0;
264	0	case set_basic:
265	0	FORWARD_IF_ERROR(FSE_buildCTable_wksp(nextCTable, defaultNorm, defaultMax, defaultNormLog, entropyWorkspace, entropyWorkspaceSize), ""); /* note : could be pre-calculated */
266	0	return 0;
267	0	case set_compressed: {
268	0	ZSTD_BuildCTableWksp* wksp = (ZSTD_BuildCTableWksp*)entropyWorkspace;
269	0	size_t nbSeq_1 = nbSeq;
270	0	const U32 tableLog = FSE_optimalTableLog(FSELog, nbSeq, max);
271	0	if (count[codeTable[nbSeq-1]] > 1) {
272	0	count[codeTable[nbSeq-1]]--;
273	0	nbSeq_1--;
274	0	}
275	0	assert(nbSeq_1 > 1);
276	0	assert(entropyWorkspaceSize >= sizeof(ZSTD_BuildCTableWksp));
277	0	(void)entropyWorkspaceSize;
278	0	FORWARD_IF_ERROR(FSE_normalizeCount(wksp->norm, tableLog, count, nbSeq_1, max, ZSTD_useLowProbCount(nbSeq_1)), "FSE_normalizeCount failed");
279	0	assert(oend >= op);
280	0	{ size_t const NCountSize = FSE_writeNCount(op, (size_t)(oend - op), wksp->norm, max, tableLog); /* overflow protected */
281	0	FORWARD_IF_ERROR(NCountSize, "FSE_writeNCount failed");
282	0	FORWARD_IF_ERROR(FSE_buildCTable_wksp(nextCTable, wksp->norm, max, tableLog, wksp->wksp, sizeof(wksp->wksp)), "FSE_buildCTable_wksp failed");
283	0	return NCountSize;
284	0	}
285	0	}
286	0	default: assert(0); RETURN_ERROR(GENERIC, "impossible to reach");
287	0	}
288	0	}
289
290		FORCE_INLINE_TEMPLATE size_t
291		ZSTD_encodeSequences_body(
292		void* dst, size_t dstCapacity,
293		FSE_CTable const* CTable_MatchLength, BYTE const* mlCodeTable,
294		FSE_CTable const* CTable_OffsetBits, BYTE const* ofCodeTable,
295		FSE_CTable const* CTable_LitLength, BYTE const* llCodeTable,
296		SeqDef const* sequences, size_t nbSeq, int longOffsets)
297	0	{
298	0	BIT_CStream_t blockStream;
299	0	FSE_CState_t stateMatchLength;
300	0	FSE_CState_t stateOffsetBits;
301	0	FSE_CState_t stateLitLength;
302
303	0	RETURN_ERROR_IF(
304	0	ERR_isError(BIT_initCStream(&blockStream, dst, dstCapacity)),
305	0	dstSize_tooSmall, "not enough space remaining");
306	0	DEBUGLOG(6, "available space for bitstream : %i (dstCapacity=%u)",
307	0	(int)(blockStream.endPtr - blockStream.startPtr),
308	0	(unsigned)dstCapacity);
309
310		/* first symbols */
311	0	FSE_initCState2(&stateMatchLength, CTable_MatchLength, mlCodeTable[nbSeq-1]);
312	0	FSE_initCState2(&stateOffsetBits, CTable_OffsetBits, ofCodeTable[nbSeq-1]);
313	0	FSE_initCState2(&stateLitLength, CTable_LitLength, llCodeTable[nbSeq-1]);
314	0	BIT_addBits(&blockStream, sequences[nbSeq-1].litLength, LL_bits[llCodeTable[nbSeq-1]]);
315	0	if (MEM_32bits()) BIT_flushBits(&blockStream);
316	0	BIT_addBits(&blockStream, sequences[nbSeq-1].mlBase, ML_bits[mlCodeTable[nbSeq-1]]);
317	0	if (MEM_32bits()) BIT_flushBits(&blockStream);
318	0	if (longOffsets) {
319	0	U32 const ofBits = ofCodeTable[nbSeq-1];
320	0	unsigned const extraBits = ofBits - MIN(ofBits, STREAM_ACCUMULATOR_MIN-1);
321	0	if (extraBits) {
322	0	BIT_addBits(&blockStream, sequences[nbSeq-1].offBase, extraBits);
323	0	BIT_flushBits(&blockStream);
324	0	}
325	0	BIT_addBits(&blockStream, sequences[nbSeq-1].offBase >> extraBits,
326	0	ofBits - extraBits);
327	0	} else {
328	0	BIT_addBits(&blockStream, sequences[nbSeq-1].offBase, ofCodeTable[nbSeq-1]);
329	0	}
330	0	BIT_flushBits(&blockStream);
331
332	0	{ size_t n;
333	0	for (n=nbSeq-2 ; n<nbSeq ; n--) { /* intentional underflow */
334	0	BYTE const llCode = llCodeTable[n];
335	0	BYTE const ofCode = ofCodeTable[n];
336	0	BYTE const mlCode = mlCodeTable[n];
337	0	U32 const llBits = LL_bits[llCode];
338	0	U32 const ofBits = ofCode;
339	0	U32 const mlBits = ML_bits[mlCode];
340	0	DEBUGLOG(6, "encoding: litlen:%2u - matchlen:%2u - offCode:%7u",
341	0	(unsigned)sequences[n].litLength,
342	0	(unsigned)sequences[n].mlBase + MINMATCH,
343	0	(unsigned)sequences[n].offBase);
344		/* 32b/ / 64b*/
345		/* (7)/ / (7)*/
346	0	FSE_encodeSymbol(&blockStream, &stateOffsetBits, ofCode); /* 15 / / 15 */
347	0	FSE_encodeSymbol(&blockStream, &stateMatchLength, mlCode); /* 24 / / 24 */
348	0	if (MEM_32bits()) BIT_flushBits(&blockStream); /* (7)*/
349	0	FSE_encodeSymbol(&blockStream, &stateLitLength, llCode); /* 16 / / 33 */
350	0	if (MEM_32bits() \|\| (ofBits+mlBits+llBits >= 64-7-(LLFSELog+MLFSELog+OffFSELog)))
351	0	BIT_flushBits(&blockStream); /* (7)*/
352	0	BIT_addBits(&blockStream, sequences[n].litLength, llBits);
353	0	if (MEM_32bits() && ((llBits+mlBits)>24)) BIT_flushBits(&blockStream);
354	0	BIT_addBits(&blockStream, sequences[n].mlBase, mlBits);
355	0	if (MEM_32bits() \|\| (ofBits+mlBits+llBits > 56)) BIT_flushBits(&blockStream);
356	0	if (longOffsets) {
357	0	unsigned const extraBits = ofBits - MIN(ofBits, STREAM_ACCUMULATOR_MIN-1);
358	0	if (extraBits) {
359	0	BIT_addBits(&blockStream, sequences[n].offBase, extraBits);
360	0	BIT_flushBits(&blockStream); /* (7)*/
361	0	}
362	0	BIT_addBits(&blockStream, sequences[n].offBase >> extraBits,
363	0	ofBits - extraBits); /* 31 */
364	0	} else {
365	0	BIT_addBits(&blockStream, sequences[n].offBase, ofBits); /* 31 */
366	0	}
367	0	BIT_flushBits(&blockStream); /* (7)*/
368	0	DEBUGLOG(7, "remaining space : %i", (int)(blockStream.endPtr - blockStream.ptr));
369	0	} }
370
371	0	DEBUGLOG(6, "ZSTD_encodeSequences: flushing ML state with %u bits", stateMatchLength.stateLog);
372	0	FSE_flushCState(&blockStream, &stateMatchLength);
373	0	DEBUGLOG(6, "ZSTD_encodeSequences: flushing Off state with %u bits", stateOffsetBits.stateLog);
374	0	FSE_flushCState(&blockStream, &stateOffsetBits);
375	0	DEBUGLOG(6, "ZSTD_encodeSequences: flushing LL state with %u bits", stateLitLength.stateLog);
376	0	FSE_flushCState(&blockStream, &stateLitLength);
377
378	0	{ size_t const streamSize = BIT_closeCStream(&blockStream);
379	0	RETURN_ERROR_IF(streamSize==0, dstSize_tooSmall, "not enough space");
380	0	return streamSize;
381	0	}
382	0	}
383
384		static size_t
385		ZSTD_encodeSequences_default(
386		void* dst, size_t dstCapacity,
387		FSE_CTable const* CTable_MatchLength, BYTE const* mlCodeTable,
388		FSE_CTable const* CTable_OffsetBits, BYTE const* ofCodeTable,
389		FSE_CTable const* CTable_LitLength, BYTE const* llCodeTable,
390		SeqDef const* sequences, size_t nbSeq, int longOffsets)
391	0	{
392	0	return ZSTD_encodeSequences_body(dst, dstCapacity,
393	0	CTable_MatchLength, mlCodeTable,
394	0	CTable_OffsetBits, ofCodeTable,
395	0	CTable_LitLength, llCodeTable,
396	0	sequences, nbSeq, longOffsets);
397	0	}
398
399
400		#if DYNAMIC_BMI2
401
402		static BMI2_TARGET_ATTRIBUTE size_t
403		ZSTD_encodeSequences_bmi2(
404		void* dst, size_t dstCapacity,
405		FSE_CTable const* CTable_MatchLength, BYTE const* mlCodeTable,
406		FSE_CTable const* CTable_OffsetBits, BYTE const* ofCodeTable,
407		FSE_CTable const* CTable_LitLength, BYTE const* llCodeTable,
408		SeqDef const* sequences, size_t nbSeq, int longOffsets)
409	0	{
410	0	return ZSTD_encodeSequences_body(dst, dstCapacity,
411	0	CTable_MatchLength, mlCodeTable,
412	0	CTable_OffsetBits, ofCodeTable,
413	0	CTable_LitLength, llCodeTable,
414	0	sequences, nbSeq, longOffsets);
415	0	}
416
417		#endif
418
419		size_t ZSTD_encodeSequences(
420		void* dst, size_t dstCapacity,
421		FSE_CTable const* CTable_MatchLength, BYTE const* mlCodeTable,
422		FSE_CTable const* CTable_OffsetBits, BYTE const* ofCodeTable,
423		FSE_CTable const* CTable_LitLength, BYTE const* llCodeTable,
424		SeqDef const* sequences, size_t nbSeq, int longOffsets, int bmi2)
425	0	{
426	0	DEBUGLOG(5, "ZSTD_encodeSequences: dstCapacity = %u", (unsigned)dstCapacity);
427	0	#if DYNAMIC_BMI2
428	0	if (bmi2) {
429	0	return ZSTD_encodeSequences_bmi2(dst, dstCapacity,
430	0	CTable_MatchLength, mlCodeTable,
431	0	CTable_OffsetBits, ofCodeTable,
432	0	CTable_LitLength, llCodeTable,
433	0	sequences, nbSeq, longOffsets);
434	0	}
435	0	#endif
436	0	(void)bmi2;
437	0	return ZSTD_encodeSequences_default(dst, dstCapacity,
438	0	CTable_MatchLength, mlCodeTable,
439	0	CTable_OffsetBits, ofCodeTable,
440	0	CTable_LitLength, llCodeTable,
441	0	sequences, nbSeq, longOffsets);
442	0	}