huf_compress.c File Reference

#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"

Data Structures
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)
#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

Enumerations
enum	HUF_nbStreams_e { HUF_singleStream , HUF_fourStreams }

Functions
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 */

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:

1. 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
2. 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.
3. The bitstream has two bit containers. You can add bits to the second container and merge them into the first container.

HUF_isError

#define HUF_isError   ERR_isError

HUF_STATIC_ASSERT

#define HUF_STATIC_ASSERT

(

c

)

Value:

DEBUG_STATIC_ASSERT(c)   /* use only *after* variable declarations */

HUF_WORKSPACE_MAX_ALIGNMENT

#define HUF_WORKSPACE_MAX_ALIGNMENT   8

MAX_FSE_TABLELOG_FOR_HUFF_HEADER

#define MAX_FSE_TABLELOG_FOR_HUFF_HEADER   6

RANK_POSITION_DISTINCT_COUNT_CUTOFF

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

RANK_POSITION_LOG_BUCKETS_BEGIN

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

RANK_POSITION_MAX_COUNT_LOG

#define RANK_POSITION_MAX_COUNT_LOG   32

RANK_POSITION_TABLE_SIZE

#define RANK_POSITION_TABLE_SIZE   192

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

SUSPECT_INCOMPRESSIBLE_SAMPLE_RATIO

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

SUSPECT_INCOMPRESSIBLE_SAMPLE_SIZE

#define SUSPECT_INCOMPRESSIBLE_SAMPLE_SIZE   4096

Typedef Documentation

nodeElt

typedef struct nodeElt_s nodeElt

Enumeration Type Documentation

HUF_nbStreams_e

enum HUF_nbStreams_e

Enumerator
HUF_singleStream
HUF_fourStreams

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.

HUF_buildCTable_wksp()

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

HUF_cardinality()

unsigned HUF_cardinality	(	const unsigned *	count,
		unsigned	maxSymbolValue )

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

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 )

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 )

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 )

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

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 )

HUF_compressBound()

size_t HUF_compressBound

(

size_t

size

)

maximum compressed size (worst case)

HUF_encodeSymbol()

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

HUF_estimateCompressedSize()

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

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.

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 : is not inlined, as HUF_CElt definition is private

HUF_insertionSort()

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

HUF_isSorted()

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

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.

HUF_minTableLog()

unsigned HUF_minTableLog

(

unsigned

symbolCardinality

)

HUF_compress() does the following:

1. count symbol occurrence from source[] into table count[] using FSE_count() (exposed within "fse.h")
2. (optional) refine tableLog using HUF_optimalTableLog()
3. build Huffman table from count using HUF_buildCTable()
4. save Huffman table to memory buffer using HUF_writeCTable()
5. 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.

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 )

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

HUF_validateCTable()

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

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 )

HUF_zeroIndex1()

FORCE_INLINE_TEMPLATE void HUF_zeroIndex1

(

HUF_CStream_t *

bitC

)