#include "fse.h"
#include "zstd_internal.h"

Include dependency graph for zstd_compress_sequences.h:

This graph shows which files directly or indirectly include this file:

Enumerations
enum	ZSTD_defaultPolicy_e { ZSTD_defaultDisallowed = 0 , ZSTD_defaultAllowed = 1 }

Functions
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)

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)

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)

size_t	ZSTD_fseBitCost (FSE_CTable const ctable, unsigned const count, unsigned const max)

size_t	ZSTD_crossEntropyCost (short const norm, unsigned accuracyLog, unsigned const count, unsigned const max)

Enumeration Type Documentation

◆ ZSTD_defaultPolicy_e

enum ZSTD_defaultPolicy_e

Enumerator
ZSTD_defaultDisallowed
ZSTD_defaultAllowed

Definition at line 17 of file zstd_compress_sequences.h.

             {
    ZSTD_defaultDisallowed = 0,
    ZSTD_defaultAllowed = 1
} ZSTD_defaultPolicy_e;

Function Documentation

◆ ZSTD_buildCTable()

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
	)

Definition at line 223 of file zstd_compress_sequences.c.

{
    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:
        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: {
        S16 norm[MaxSeq + 1];
        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);
        FORWARD_IF_ERROR(FSE_normalizeCount(norm, tableLog, count, nbSeq_1, max), "");
        {   size_t const NCountSize = FSE_writeNCount(op, oend - op, norm, max, tableLog);   /* overflow protected */
            FORWARD_IF_ERROR(NCountSize, "FSE_writeNCount failed");
            FORWARD_IF_ERROR(FSE_buildCTable_wksp(nextCTable, norm, max, tableLog, entropyWorkspace, entropyWorkspaceSize), "");
            return NCountSize;
        }
    }
    default: assert(0); RETURN_ERROR(GENERIC, "impossible to reach");
    }
}

Referenced by ZSTD_buildSuperBlockEntropy_sequences(), and ZSTD_compressSequences_internal().

◆ ZSTD_crossEntropyCost()

size_t ZSTD_crossEntropyCost	(	short const *	norm,
		unsigned	accuracyLog,
		unsigned const *	count,
		unsigned const	max
	)

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.

Definition at line 124 of file zstd_compress_sequences.c.

{
    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;
}

Referenced by ZSTD_estimateSubBlockSize_symbolType(), and ZSTD_selectEncodingType().

◆ ZSTD_encodeSequences()

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
	)

Definition at line 396 of file zstd_compress_sequences.c.

{
    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);
}

Referenced by ZSTD_compressSequences_internal(), and ZSTD_compressSubBlock_sequences().

◆ ZSTD_fseBitCost()

size_t ZSTD_fseBitCost	(	FSE_CTable const *	ctable,
		unsigned const *	count,
		unsigned const	max
	)

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.

Definition at line 89 of file zstd_compress_sequences.c.

{
    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;
}