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"

Data Structures
struct	fseWkspMax_t

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)
#define	FSE_FUNCTION_NAME(X, Y)
#define	FSE_TYPE_NAME(X, Y)
#define	FSE_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)
FSE_CTable *	FSE_createCTable (unsigned maxSymbolValue, unsigned tableLog)
void	FSE_freeCTable (FSE_CTable *ct)
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_raw (FSE_CTable *ct, unsigned nbBits)
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)
size_t	FSE_compress_wksp (void *dst, size_t dstSize, const void *src, size_t srcSize, unsigned maxSymbolValue, unsigned tableLog, void *workSpace, size_t wkspSize)
size_t	FSE_compress2 (void *dst, size_t dstCapacity, const void *src, size_t srcSize, unsigned maxSymbolValue, unsigned tableLog)
size_t	FSE_compress (void *dst, size_t dstCapacity, const void *src, size_t srcSize)

Macro Definition Documentation

FSE_CAT

#define FSE_CAT	(		X,
			Y )

Value:

X##Y

FSE_FLUSHBITS

#define FSE_FLUSHBITS

(

s

)

Value:

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

FSE_FUNCTION_NAME

#define FSE_FUNCTION_NAME	(		X,
			Y )

Value:

FSE_CAT(X,Y)

FSE_isError

#define FSE_isError   ERR_isError

FSE_STATIC_LINKING_ONLY

#define FSE_STATIC_LINKING_ONLY

FSE_TYPE_NAME

#define FSE_TYPE_NAME	(		X,
			Y )

Value:

FSE_CAT(X,Y)

ZSTD_DEPS_NEED_MALLOC

#define ZSTD_DEPS_NEED_MALLOC

ZSTD_DEPS_NEED_MATH64

#define ZSTD_DEPS_NEED_MATH64

Function Documentation

FSE_buildCTable_raw()

size_t FSE_buildCTable_raw	(	FSE_CTable *	ct,
		unsigned	nbBits )

FSE_buildCTable_rle()

size_t FSE_buildCTable_rle	(	FSE_CTable *	ct,
		BYTE	symbolValue )

FSE_buildCTable_wksp()

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

FSE_compress()

size_t FSE_compress	(	void *	dst,
		size_t	dstCapacity,
		const void *	src,
		size_t	srcSize )

FSE_compress() : Compress content of buffer 'src', of size 'srcSize', into destination buffer 'dst'. 'dst' buffer must be already allocated. Compression runs faster is dstCapacity >= FSE_compressBound(srcSize).

Returns

: size of compressed data (<= dstCapacity). Special values : if return == 0, srcData is not compressible => Nothing is stored within dst !!! if return == 1, srcData is a single byte symbol * srcSize times. Use RLE compression instead. if FSE_isError(return), compression failed (more details using FSE_getErrorName())

FSE_compress2()

size_t FSE_compress2	(	void *	dst,
		size_t	dstSize,
		const void *	src,
		size_t	srcSize,
		unsigned	maxSymbolValue,
		unsigned	tableLog )

FSE_compress2() : Same as FSE_compress(), but allows the selection of 'maxSymbolValue' and 'tableLog' Both parameters can be defined as '0' to mean : use default value

Returns

: size of compressed data Special values : if return == 0, srcData is not compressible => Nothing is stored within cSrc !!! if return == 1, srcData is a single byte symbol * srcSize times. Use RLE compression. if FSE_isError(return), it's an error code.

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

FSE_compress_wksp()

size_t FSE_compress_wksp	(	void *	dst,
		size_t	dstSize,
		const void *	src,
		size_t	srcSize,
		unsigned	maxSymbolValue,
		unsigned	tableLog,
		void *	workSpace,
		size_t	wkspSize )

FSE_compressBound()

size_t FSE_compressBound

(

size_t

size

)

FSE_createCTable()

FSE_CTable * FSE_createCTable	(	unsigned	maxSymbolValue,
		unsigned	tableLog )

FSE_freeCTable()

void FSE_freeCTable

(

FSE_CTable *

ct

)

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.

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

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

FSE_optimalTableLog_internal()

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

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