fse_compress.c File Reference

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

Include dependency graph for fse_compress.c:

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

Go to the source code of this file.

Macros
#define	FSE_STATIC_LINKING_ONLY
#define	ZSTD_DEPS_NEED_MALLOC
#define	ZSTD_DEPS_NEED_MATH64
#define	FSE_isError   ERR_isError
#define	FSE_CAT(X, Y)   X##Y
#define	FSE_FUNCTION_NAME(X, Y)   FSE_CAT(X,Y)
#define	FSE_TYPE_NAME(X, Y)   FSE_CAT(X,Y)
#define	FSE_FLUSHBITS(s)   (fast ? BIT_flushBitsFast(s) : BIT_flushBits(s))

Functions
size_t	FSE_buildCTable_wksp (FSE_CTable *ct, const short *normalizedCounter, unsigned maxSymbolValue, unsigned tableLog, void *workSpace, size_t wkspSize)
size_t	FSE_NCountWriteBound (unsigned maxSymbolValue, unsigned tableLog)
size_t	FSE_writeNCount (void *buffer, size_t bufferSize, const short *normalizedCounter, unsigned maxSymbolValue, unsigned tableLog)
unsigned	FSE_optimalTableLog_internal (unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue, unsigned minus)
unsigned	FSE_optimalTableLog (unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue)
size_t	FSE_normalizeCount (short *normalizedCounter, unsigned tableLog, const unsigned *count, size_t total, unsigned maxSymbolValue, unsigned useLowProbCount)
size_t	FSE_buildCTable_rle (FSE_CTable *ct, BYTE symbolValue)
size_t	FSE_compress_usingCTable (void *dst, size_t dstSize, const void *src, size_t srcSize, const FSE_CTable *ct)
size_t	FSE_compressBound (size_t size)

Macro Definition Documentation

FSE_CAT

#define FSE_CAT	(		X,
			Y
	)		X##Y

Definition at line 56 of file fse_compress.c.

FSE_FLUSHBITS

#define FSE_FLUSHBITS

(

s

)

(fast ? BIT_flushBitsFast(s) : BIT_flushBits(s))

FSE_FUNCTION_NAME

#define FSE_FUNCTION_NAME	(		X,
			Y
	)		FSE_CAT(X,Y)

Definition at line 57 of file fse_compress.c.

FSE_isError

#define FSE_isError   ERR_isError

Definition at line 35 of file fse_compress.c.

FSE_STATIC_LINKING_ONLY

#define FSE_STATIC_LINKING_ONLY

Definition at line 23 of file fse_compress.c.

FSE_TYPE_NAME

#define FSE_TYPE_NAME	(		X,
			Y
	)		FSE_CAT(X,Y)

Definition at line 58 of file fse_compress.c.

ZSTD_DEPS_NEED_MALLOC

#define ZSTD_DEPS_NEED_MALLOC

Definition at line 26 of file fse_compress.c.

ZSTD_DEPS_NEED_MATH64

#define ZSTD_DEPS_NEED_MATH64

Definition at line 27 of file fse_compress.c.

Function Documentation

FSE_buildCTable_rle()

size_t FSE_buildCTable_rle	(	FSE_CTable *	ct,
		BYTE	symbolValue
	)

Definition at line 528 of file fse_compress.c.

Here is the caller graph for this function:

FSE_buildCTable_wksp()

size_t FSE_buildCTable_wksp	(	FSE_CTable *	ct,
		const short *	normalizedCounter,
		unsigned	maxSymbolValue,
		unsigned	tableLog,
		void *	workSpace,
		size_t	wkspSize
	)

Definition at line 68 of file fse_compress.c.

Here is the call graph for this function:

Here is the caller graph for this function:

FSE_compress_usingCTable()

size_t FSE_compress_usingCTable	(	void *	dst,
		size_t	dstCapacity,
		const void *	src,
		size_t	srcSize,
		const FSE_CTable *	ct
	)

FSE_compress_usingCTable(): Compress src using ct into dst which must be already allocated.

Returns

: size of compressed data (<= dstCapacity), or 0 if compressed data could not fit into dst, or an errorCode, which can be tested using FSE_isError()

Definition at line 610 of file fse_compress.c.

FSE_compressBound()

size_t FSE_compressBound

(

size_t

size

)

Definition at line 623 of file fse_compress.c.

FSE_NCountWriteBound()

size_t FSE_NCountWriteBound	(	unsigned	maxSymbolValue,
		unsigned	tableLog
	)

FSE_NCountWriteBound(): Provides the maximum possible size of an FSE normalized table, given 'maxSymbolValue' and 'tableLog'. Typically useful for allocation purpose.

Definition at line 223 of file fse_compress.c.

Here is the caller graph for this function:

FSE_normalizeCount()

size_t FSE_normalizeCount	(	short *	normalizedCounter,
		unsigned	tableLog,
		const unsigned *	count,
		size_t	srcSize,
		unsigned	maxSymbolValue,
		unsigned	useLowProbCount
	)

FSE_normalizeCount(): normalize counts so that sum(count[]) == Power_of_2 (2^tableLog) 'normalizedCounter' is a table of short, of minimum size (maxSymbolValue+1). useLowProbCount is a boolean parameter which trades off compressed size for faster header decoding. When it is set to 1, the compressed data will be slightly smaller. And when it is set to 0, FSE_readNCount() and FSE_buildDTable() will be faster. If you are compressing a small amount of data (< 2 KB) then useLowProbCount=0 is a good default, since header deserialization makes a big speed difference. Otherwise, useLowProbCount=1 is a good default, since the speed difference is small.

Returns

: tableLog, or an errorCode, which can be tested using FSE_isError()

Definition at line 465 of file fse_compress.c.

Here is the caller graph for this function:

FSE_optimalTableLog()

unsigned FSE_optimalTableLog	(	unsigned	maxTableLog,
		size_t	srcSize,
		unsigned	maxSymbolValue
	)

FSE_compress() does the following:

1. count symbol occurrence from source[] into table count[] (see hist.h)
2. normalize counters so that sum(count[]) == Power_of_2 (2^tableLog)
3. save normalized counters to memory buffer using writeNCount()
4. build encoding table 'CTable' from normalized counters
5. encode the data stream using encoding table 'CTable'

FSE_decompress() does the following:

1. read normalized counters with readNCount()
2. build decoding table 'DTable' from normalized counters
3. decode the data stream using decoding table 'DTable'

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 provide normalized distribution using external method.

FSE_optimalTableLog(): dynamically downsize 'tableLog' when conditions are met. It saves CPU time, by using smaller tables, while preserving or even improving compression ratio.

Returns

: recommended tableLog (necessarily <= 'maxTableLog')

Definition at line 371 of file fse_compress.c.

Here is the call graph for this function:

Here is the caller graph for this function:

FSE_optimalTableLog_internal()

unsigned FSE_optimalTableLog_internal	(	unsigned	maxTableLog,
		size_t	srcSize,
		unsigned	maxSymbolValue,
		unsigned	minus
	)

Definition at line 357 of file fse_compress.c.

Here is the call graph for this function:

Here is the caller graph for this function:

FSE_writeNCount()

size_t FSE_writeNCount	(	void *	buffer,
		size_t	bufferSize,
		const short *	normalizedCounter,
		unsigned	maxSymbolValue,
		unsigned	tableLog
	)

FSE_writeNCount(): Compactly save 'normalizedCounter' into 'buffer'.

Returns

: size of the compressed table, or an errorCode, which can be tested using FSE_isError().

Definition at line 330 of file fse_compress.c.

Here is the call graph for this function:

Here is the caller graph for this function: