#include "../common/zstd_deps.h"
#include "../common/compiler.h"
#include "../common/bitstream.h"
#include "hist.h"
#include "../common/fse.h"
#include "../common/huf.h"
#include "../common/error_private.h"
#include "../common/bits.h"

Include dependency graph for huf_compress.c:

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

Go to the source code of this file.

Classes
struct	nodeElt_s

struct	HUF_CompressWeightsWksp

struct	HUF_WriteCTableWksp

struct	rankPos

struct	HUF_buildCTable_wksp_tables

struct	HUF_CStream_t

struct	HUF_compress_tables_t

Macros
#define	FSE_STATIC_LINKING_ONLY /* FSE_optimalTableLog_internal */

#define	HUF_isError ERR_isError

#define	HUF_STATIC_ASSERT(c) DEBUG_STATIC_ASSERT(c) /* use only after variable declarations */

#define	HUF_WORKSPACE_MAX_ALIGNMENT 8

#define	MAX_FSE_TABLELOG_FOR_HUFF_HEADER 6

#define	RANK_POSITION_TABLE_SIZE 192

#define	RANK_POSITION_MAX_COUNT_LOG 32

#define	RANK_POSITION_LOG_BUCKETS_BEGIN ((RANK_POSITION_TABLE_SIZE - 1) - RANK_POSITION_MAX_COUNT_LOG - 1 /* == 158 */)

#define	RANK_POSITION_DISTINCT_COUNT_CUTOFF (RANK_POSITION_LOG_BUCKETS_BEGIN + ZSTD_highbit32(RANK_POSITION_LOG_BUCKETS_BEGIN) /* == 166 */)

#define	STARTNODE (HUF_SYMBOLVALUE_MAX+1)

#define	HUF_BITS_IN_CONTAINER (sizeof(size_t) * 8)

#define	SUSPECT_INCOMPRESSIBLE_SAMPLE_SIZE 4096

#define	SUSPECT_INCOMPRESSIBLE_SAMPLE_RATIO 10 /* Must be >= 2 */

Typedefs
typedef struct nodeElt_s	nodeElt

typedef nodeElt	huffNodeTable[2 *(HUF_SYMBOLVALUE_MAX+1)]

Enumerations
enum	HUF_nbStreams_e { HUF_singleStream , HUF_fourStreams }

Functions
HUF_CTableHeader	HUF_readCTableHeader (HUF_CElt const *ctable)

size_t	HUF_writeCTable_wksp (void dst, size_t maxDstSize, const HUF_CElt CTable, unsigned maxSymbolValue, unsigned huffLog, void *workspace, size_t workspaceSize)

size_t	HUF_readCTable (HUF_CElt CTable, unsigned maxSymbolValuePtr, const void src, size_t srcSize, unsigned hasZeroWeights)

U32	HUF_getNbBitsFromCTable (HUF_CElt const *CTable, U32 symbolValue)

MEM_STATIC int	HUF_isSorted (nodeElt huffNode[], U32 const maxSymbolValue1)

HINT_INLINE void	HUF_insertionSort (nodeElt huffNode[], int const low, int const high)

size_t	HUF_buildCTable_wksp (HUF_CElt CTable, const unsigned count, U32 maxSymbolValue, U32 maxNbBits, void *workSpace, size_t wkspSize)

size_t	HUF_estimateCompressedSize (const HUF_CElt CTable, const unsigned count, unsigned maxSymbolValue)

int	HUF_validateCTable (const HUF_CElt CTable, const unsigned count, unsigned maxSymbolValue)

size_t	HUF_compressBound (size_t size)

FORCE_INLINE_TEMPLATE void	HUF_addBits (HUF_CStream_t *bitC, HUF_CElt elt, int idx, int kFast)

FORCE_INLINE_TEMPLATE void	HUF_zeroIndex1 (HUF_CStream_t *bitC)

FORCE_INLINE_TEMPLATE void	HUF_mergeIndex1 (HUF_CStream_t *bitC)

FORCE_INLINE_TEMPLATE void	HUF_flushBits (HUF_CStream_t *bitC, int kFast)

FORCE_INLINE_TEMPLATE void	HUF_encodeSymbol (HUF_CStream_t bitCPtr, U32 symbol, const HUF_CElt CTable, int idx, int fast)

FORCE_INLINE_TEMPLATE void	HUF_compress1X_usingCTable_internal_body_loop (HUF_CStream_t bitC, const BYTE ip, size_t srcSize, const HUF_CElt *ct, int kUnroll, int kFastFlush, int kLastFast)

FORCE_INLINE_TEMPLATE size_t	HUF_compress1X_usingCTable_internal_body (void dst, size_t dstSize, const void src, size_t srcSize, const HUF_CElt *CTable)

size_t	HUF_compress1X_usingCTable (void dst, size_t dstSize, const void src, size_t srcSize, const HUF_CElt *CTable, int flags)

size_t	HUF_compress4X_usingCTable (void dst, size_t dstSize, const void src, size_t srcSize, const HUF_CElt *CTable, int flags)

unsigned	HUF_cardinality (const unsigned *count, unsigned maxSymbolValue)

unsigned	HUF_minTableLog (unsigned symbolCardinality)

unsigned	HUF_optimalTableLog (unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue, void workSpace, size_t wkspSize, HUF_CElt table, const unsigned *count, int flags)

size_t	HUF_compress1X_repeat (void dst, size_t dstSize, const void src, size_t srcSize, unsigned maxSymbolValue, unsigned huffLog, void workSpace, size_t wkspSize, HUF_CElt hufTable, HUF_repeat *repeat, int flags)

size_t	HUF_compress4X_repeat (void dst, size_t dstSize, const void src, size_t srcSize, unsigned maxSymbolValue, unsigned huffLog, void workSpace, size_t wkspSize, HUF_CElt hufTable, HUF_repeat *repeat, int flags)

Macro Definition Documentation

◆ FSE_STATIC_LINKING_ONLY

#define FSE_STATIC_LINKING_ONLY /* FSE_optimalTableLog_internal */

Definition at line 30 of file huf_compress.c.

◆ HUF_BITS_IN_CONTAINER

#define HUF_BITS_IN_CONTAINER (sizeof(size_t) * 8)

HUF_CStream_t: Huffman uses its own BIT_CStream_t implementation. There are three major differences from BIT_CStream_t:

HUF_addBits() takes a HUF_CElt (size_t) which is the pair (nbBits, value) in the format: format:
- Bits [0, 4) = nbBits
- Bits [4, 64 - nbBits) = 0
- Bits [64 - nbBits, 64) = value
The bitContainer is built from the upper bits and right shifted. E.g. to add a new value of N bits you right shift the bitContainer by N, then or in the new value into the N upper bits.
The bitstream has two bit containers. You can add bits to the second container and merge them into the first container.

Definition at line 841 of file huf_compress.c.

◆ HUF_isError

#define HUF_isError ERR_isError

Definition at line 40 of file huf_compress.c.

◆ HUF_STATIC_ASSERT

#define HUF_STATIC_ASSERT ( c ) DEBUG_STATIC_ASSERT(c) /* use only *after* variable declarations */

Definition at line 41 of file huf_compress.c.

◆ HUF_WORKSPACE_MAX_ALIGNMENT

#define HUF_WORKSPACE_MAX_ALIGNMENT 8

Definition at line 110 of file huf_compress.c.

◆ MAX_FSE_TABLELOG_FOR_HUFF_HEADER

#define MAX_FSE_TABLELOG_FOR_HUFF_HEADER 6

Definition at line 137 of file huf_compress.c.

◆ RANK_POSITION_DISTINCT_COUNT_CUTOFF

#define RANK_POSITION_DISTINCT_COUNT_CUTOFF (RANK_POSITION_LOG_BUCKETS_BEGIN + ZSTD_highbit32(RANK_POSITION_LOG_BUCKETS_BEGIN) /* == 166 */)

Definition at line 525 of file huf_compress.c.

◆ RANK_POSITION_LOG_BUCKETS_BEGIN

#define RANK_POSITION_LOG_BUCKETS_BEGIN ((RANK_POSITION_TABLE_SIZE - 1) - RANK_POSITION_MAX_COUNT_LOG - 1 /* == 158 */)

Definition at line 524 of file huf_compress.c.

◆ RANK_POSITION_MAX_COUNT_LOG

#define RANK_POSITION_MAX_COUNT_LOG 32

Definition at line 523 of file huf_compress.c.

◆ RANK_POSITION_TABLE_SIZE

#define RANK_POSITION_TABLE_SIZE 192

Definition at line 508 of file huf_compress.c.

◆ STARTNODE

#define STARTNODE (HUF_SYMBOLVALUE_MAX+1)

HUF_buildCTable_wksp() : Same as HUF_buildCTable(), but using externally allocated scratch buffer. workSpace must be aligned on 4-bytes boundaries, and be at least as large as sizeof(HUF_buildCTable_wksp_tables).

Definition at line 672 of file huf_compress.c.

◆ SUSPECT_INCOMPRESSIBLE_SAMPLE_RATIO

#define SUSPECT_INCOMPRESSIBLE_SAMPLE_RATIO 10 /* Must be >= 2 */

Definition at line 1252 of file huf_compress.c.

◆ SUSPECT_INCOMPRESSIBLE_SAMPLE_SIZE

#define SUSPECT_INCOMPRESSIBLE_SAMPLE_SIZE 4096

Definition at line 1251 of file huf_compress.c.

Typedef Documentation

◆ huffNodeTable

typedef nodeElt huffNodeTable[2 *(HUF_SYMBOLVALUE_MAX+1)]

Definition at line 505 of file huf_compress.c.

◆ nodeElt

typedef struct nodeElt_s nodeElt

Enumeration Type Documentation

◆ HUF_nbStreams_e

enum HUF_nbStreams_e

Enumerator
HUF_singleStream
HUF_fourStreams

Definition at line 1222 of file huf_compress.c.

Function Documentation

◆ HUF_addBits()

FORCE_INLINE_TEMPLATE void HUF_addBits	(	HUF_CStream_t *	bitC,
		HUF_CElt	elt,
		int	idx,
		int	kFast
	)

HUF_addBits(): Adds the symbol stored in HUF_CElt elt to the bitstream.

Parameters

elt	The element we're adding. This is a (nbBits, value) pair. See the HUF_CStream_t docs for the format.
idx	Insert into the bitstream at this idx.
kFast	This is a template parameter. If the bitstream is guaranteed to have at least 4 unused bits after this call it may be 1, otherwise it must be 0. HUF_addBits() is faster when fast is set.

Definition at line 877 of file huf_compress.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ HUF_buildCTable_wksp()

size_t HUF_buildCTable_wksp	(	HUF_CElt *	CTable,
		const unsigned *	count,
		U32	maxSymbolValue,
		U32	maxNbBits,
		void *	workSpace,
		size_t	wkspSize
	)

Definition at line 756 of file huf_compress.c.

Here is the caller graph for this function:

◆ HUF_cardinality()

unsigned HUF_cardinality	(	const unsigned *	count,
		unsigned	maxSymbolValue
	)

Definition at line 1254 of file huf_compress.c.

Here is the caller graph for this function:

◆ HUF_compress1X_repeat()

size_t HUF_compress1X_repeat	(	void *	dst,
		size_t	dstSize,
		const void *	src,
		size_t	srcSize,
		unsigned	maxSymbolValue,
		unsigned	tableLog,
		void *	workSpace,
		size_t	wkspSize,
		HUF_CElt *	hufTable,
		HUF_repeat *	repeat,
		int	flags
	)

HUF_compress1X_repeat() : Same as HUF_compress1X_wksp(), but considers using hufTable if *repeat != HUF_repeat_none. If it uses hufTable it does not modify hufTable or repeat. If it doesn't, it sets *repeat = HUF_repeat_none, and it sets hufTable to the table used. If preferRepeat then the old table will always be used if valid. If suspectUncompressible then some sampling checks will be run to potentially skip huffman coding

Parameters

wkspSize workSpace must be aligned on 4-bytes boundaries, wkspSize must be >= HUF_WORKSPACE_SIZE

Definition at line 1436 of file huf_compress.c.

Here is the caller graph for this function:

◆ HUF_compress1X_usingCTable()

size_t HUF_compress1X_usingCTable	(	void *	dst,
		size_t	dstSize,
		const void *	src,
		size_t	srcSize,
		const HUF_CElt *	CTable,
		int	flags
	)

Definition at line 1162 of file huf_compress.c.

◆ HUF_compress1X_usingCTable_internal_body()

FORCE_INLINE_TEMPLATE size_t HUF_compress1X_usingCTable_internal_body	(	void *	dst,
		size_t	dstSize,
		const void *	src,
		size_t	srcSize,
		const HUF_CElt *	CTable
	)

Definition at line 1056 of file huf_compress.c.

Here is the call graph for this function:

◆ HUF_compress1X_usingCTable_internal_body_loop()

FORCE_INLINE_TEMPLATE void HUF_compress1X_usingCTable_internal_body_loop	(	HUF_CStream_t *	bitC,
		const BYTE *	ip,
		size_t	srcSize,
		const HUF_CElt *	ct,
		int	kUnroll,
		int	kFastFlush,
		int	kLastFast
	)

Definition at line 991 of file huf_compress.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ HUF_compress4X_repeat()

size_t HUF_compress4X_repeat	(	void *	dst,
		size_t	dstSize,
		const void *	src,
		size_t	srcSize,
		unsigned	maxSymbolValue,
		unsigned	tableLog,
		void *	workSpace,
		size_t	wkspSize,
		HUF_CElt *	hufTable,
		HUF_repeat *	repeat,
		int	flags
	)

HUF_compress4X_repeat() : Same as HUF_compress4X_wksp(), but considers using hufTable if *repeat != HUF_repeat_none. If it uses hufTable it does not modify hufTable or repeat. If it doesn't, it sets *repeat = HUF_repeat_none, and it sets hufTable to the table used. If preferRepeat then the old table will always be used if valid. If suspectUncompressible then some sampling checks will be run to potentially skip huffman coding

Parameters

wkspSize workSpace must be aligned on 4-bytes boundaries, wkspSize must be >= HUF_WORKSPACE_SIZE

Definition at line 1453 of file huf_compress.c.

Here is the caller graph for this function:

◆ HUF_compress4X_usingCTable()

size_t HUF_compress4X_usingCTable	(	void *	dst,
		size_t	dstSize,
		const void *	src,
		size_t	srcSize,
		const HUF_CElt *	CTable,
		int	flags
	)

Definition at line 1217 of file huf_compress.c.

◆ HUF_compressBound()

size_t HUF_compressBound ( size_t size )

maximum compressed size (worst case)

Definition at line 821 of file huf_compress.c.

◆ HUF_encodeSymbol()

FORCE_INLINE_TEMPLATE void HUF_encodeSymbol	(	HUF_CStream_t *	bitCPtr,
		U32	symbol,
		const HUF_CElt *	CTable,
		int	idx,
		int	fast
	)

Definition at line 985 of file huf_compress.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ HUF_estimateCompressedSize()

size_t HUF_estimateCompressedSize	(	const HUF_CElt *	CTable,
		const unsigned *	count,
		unsigned	maxSymbolValue
	)

Definition at line 793 of file huf_compress.c.

Here is the caller graph for this function:

◆ HUF_flushBits()

FORCE_INLINE_TEMPLATE void HUF_flushBits	(	HUF_CStream_t *	bitC,
		int	kFast
	)

HUF_flushBits() : Flushes the bits in the bit container @ index 0.

Postcondition: bitPos will be < 8.

Parameters

kFast If kFast is set then we must know a-priori that the bit container will not overflow.

Definition at line 937 of file huf_compress.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ HUF_getNbBitsFromCTable()

U32 HUF_getNbBitsFromCTable	(	const HUF_CElt *	symbolTable,
		U32	symbolValue
	)

HUF_getNbBitsFromCTable() : Read nbBits from CTable symbolTable, for symbol symbolValue presumed <= HUF_SYMBOLVALUE_MAX Note 1 : If symbolValue > HUF_readCTableHeader(symbolTable).maxSymbolValue, returns 0 Note 2 : is not inlined, as HUF_CElt definition is private

Definition at line 345 of file huf_compress.c.

Here is the call graph for this function:

◆ HUF_insertionSort()

HINT_INLINE void HUF_insertionSort	(	nodeElt	huffNode[],
		int const	low,
		int const	high
	)

Definition at line 555 of file huf_compress.c.

◆ HUF_isSorted()

MEM_STATIC int HUF_isSorted	(	nodeElt	huffNode[],
		U32 const	maxSymbolValue1
	)

Definition at line 544 of file huf_compress.c.

◆ HUF_mergeIndex1()

FORCE_INLINE_TEMPLATE void HUF_mergeIndex1 ( HUF_CStream_t * bitC )

HUF_mergeIndex1() : Merges the bit container @ index 1 into the bit container @ index 0 and zeros the bit container @ index 1.

Definition at line 921 of file huf_compress.c.

Here is the caller graph for this function:

◆ HUF_minTableLog()

unsigned HUF_minTableLog ( unsigned symbolCardinality )

HUF_compress() does the following:

count symbol occurrence from source[] into table count[] using FSE_count() (exposed within "fse.h")
(optional) refine tableLog using HUF_optimalTableLog()
build Huffman table from count using HUF_buildCTable()
save Huffman table to memory buffer using HUF_writeCTable()
encode the data stream using HUF_compress4X_usingCTable()

The following API allows targeting specific sub-functions for advanced tasks. For example, it's possible to compress several blocks using the same 'CTable', or to save and regenerate 'CTable' using external methods.

Definition at line 1266 of file huf_compress.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ HUF_optimalTableLog()

unsigned HUF_optimalTableLog	(	unsigned	maxTableLog,
		size_t	srcSize,
		unsigned	maxSymbolValue,
		void *	workSpace,
		size_t	wkspSize,
		HUF_CElt *	table,
		const unsigned *	count,
		int	flags
	)

Definition at line 1272 of file huf_compress.c.

Here is the call graph for this function:

◆ HUF_readCTable()

size_t HUF_readCTable	(	HUF_CElt *	CTable,
		unsigned *	maxSymbolValuePtr,
		const void *	src,
		size_t	srcSize,
		unsigned *	hasZeroWeights
	)

HUF_readCTable() : Loading a CTable saved with HUF_writeCTable()

Definition at line 292 of file huf_compress.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ HUF_readCTableHeader()

HUF_CTableHeader HUF_readCTableHeader ( HUF_CElt const * ctable )

HUF_readCTableHeader() :

Returns: The header from the CTable specifying the tableLog and the maxSymbolValue.

Definition at line 223 of file huf_compress.c.

Here is the caller graph for this function:

◆ HUF_validateCTable()

int HUF_validateCTable	(	const HUF_CElt *	CTable,
		const unsigned *	count,
		unsigned	maxSymbolValue
	)

Definition at line 804 of file huf_compress.c.

Here is the call graph for this function:

◆ HUF_writeCTable_wksp()

size_t HUF_writeCTable_wksp	(	void *	dst,
		size_t	maxDstSize,
		const HUF_CElt *	CTable,
		unsigned	maxSymbolValue,
		unsigned	huffLog,
		void *	workspace,
		size_t	workspaceSize
	)

Definition at line 248 of file huf_compress.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ HUF_zeroIndex1()

FORCE_INLINE_TEMPLATE void HUF_zeroIndex1 ( HUF_CStream_t * bitC )

Definition at line 911 of file huf_compress.c.

Here is the caller graph for this function:

Classes

Macros

Typedefs

Enumerations

Functions

Macro Definition Documentation

◆ FSE_STATIC_LINKING_ONLY

◆ HUF_BITS_IN_CONTAINER

◆ HUF_isError

◆ HUF_STATIC_ASSERT

◆ HUF_WORKSPACE_MAX_ALIGNMENT

◆ MAX_FSE_TABLELOG_FOR_HUFF_HEADER

◆ RANK_POSITION_DISTINCT_COUNT_CUTOFF

◆ RANK_POSITION_LOG_BUCKETS_BEGIN

◆ RANK_POSITION_MAX_COUNT_LOG

◆ RANK_POSITION_TABLE_SIZE

◆ STARTNODE

◆ SUSPECT_INCOMPRESSIBLE_SAMPLE_RATIO

◆ SUSPECT_INCOMPRESSIBLE_SAMPLE_SIZE

Typedef Documentation

◆ huffNodeTable

◆ nodeElt

Enumeration Type Documentation

◆ HUF_nbStreams_e

Function Documentation

◆ HUF_addBits()

◆ HUF_buildCTable_wksp()

◆ HUF_cardinality()

◆ HUF_compress1X_repeat()

◆ HUF_compress1X_usingCTable()

◆ HUF_compress1X_usingCTable_internal_body()

◆ HUF_compress1X_usingCTable_internal_body_loop()

◆ HUF_compress4X_repeat()

◆ HUF_compress4X_usingCTable()

◆ HUF_compressBound()

◆ HUF_encodeSymbol()

◆ HUF_estimateCompressedSize()

◆ HUF_flushBits()

◆ HUF_getNbBitsFromCTable()

◆ HUF_insertionSort()

◆ HUF_isSorted()

◆ HUF_mergeIndex1()

◆ HUF_minTableLog()

◆ HUF_optimalTableLog()

◆ HUF_readCTable()

◆ HUF_readCTableHeader()

◆ HUF_validateCTable()

◆ HUF_writeCTable_wksp()

◆ HUF_zeroIndex1()