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

Source
/*
 * 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 "../common/bmi2.h"
#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;

    assert(MEM_32bits() || !longOffsets);
    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 (MEM_32bits() && 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 (MEM_32bits() && 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);
}

#else

#define ZSTD_encodeSequences_bmi2 ZSTD_encodeSequences_default

#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 (ZSTD_USE_BMI2(bmi2)) {
        return ZSTD_encodeSequences_bmi2(dst, dstCapacity,
                                         CTable_MatchLength, mlCodeTable,
                                         CTable_OffsetBits, ofCodeTable,
                                         CTable_LitLength, llCodeTable,
                                         sequences, nbSeq, longOffsets);
    }
    (void)bmi2;
    return ZSTD_encodeSequences_default(dst, dstCapacity,
                                        CTable_MatchLength, mlCodeTable,
                                        CTable_OffsetBits, ofCodeTable,
                                        CTable_LitLength, llCodeTable,
                                        sequences, nbSeq, longOffsets);
}

Coverage Report

Created: 2026-10-28 07:09

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