156337Skato/* ****************************************************************** 256337Skato * FSE : Finite State Entropy codec 356337Skato * Public Prototypes declaration 456337Skato * Copyright (c) Yann Collet, Facebook, Inc. 556337Skato * 656337Skato * You can contact the author at : 756337Skato * - Source repository : https://github.com/Cyan4973/FiniteStateEntropy 856337Skato * 956337Skato * This source code is licensed under both the BSD-style license (found in the 1056337Skato * LICENSE file in the root directory of this source tree) and the GPLv2 (found 1156337Skato * in the COPYING file in the root directory of this source tree). 1256337Skato * You may select, at your option, one of the above-listed licenses. 1356337Skato****************************************************************** */ 1456337Skato 1556337Skato 1656337Skato#ifndef FSE_H 1756337Skato#define FSE_H 1856337Skato 1956337Skato 2056337Skato/*-***************************************** 2156337Skato* Dependencies 2256337Skato******************************************/ 2356337Skato#include "zstd_deps.h" /* size_t, ptrdiff_t */ 2456337Skato 2556337Skato 2656337Skato/*-***************************************** 2756337Skato* FSE_PUBLIC_API : control library symbols visibility 2856337Skato******************************************/ 2956337Skato#if defined(FSE_DLL_EXPORT) && (FSE_DLL_EXPORT==1) && defined(__GNUC__) && (__GNUC__ >= 4) 3056337Skato# define FSE_PUBLIC_API __attribute__ ((visibility ("default"))) 3156337Skato#elif defined(FSE_DLL_EXPORT) && (FSE_DLL_EXPORT==1) /* Visual expected */ 3256337Skato# define FSE_PUBLIC_API __declspec(dllexport) 3356337Skato#elif defined(FSE_DLL_IMPORT) && (FSE_DLL_IMPORT==1) 34130070Sphk# define FSE_PUBLIC_API __declspec(dllimport) /* It isn't required but allows to generate better code, saving a function pointer load from the IAT and an indirect jump.*/ 3556337Skato#else 3656337Skato# define FSE_PUBLIC_API 3756337Skato#endif 3856337Skato 3956337Skato/*------ Version ------*/ 40186681Sed#define FSE_VERSION_MAJOR 0 4156337Skato#define FSE_VERSION_MINOR 9 4256337Skato#define FSE_VERSION_RELEASE 0 4356337Skato 4456337Skato#define FSE_LIB_VERSION FSE_VERSION_MAJOR.FSE_VERSION_MINOR.FSE_VERSION_RELEASE 4556337Skato#define FSE_QUOTE(str) #str 4656337Skato#define FSE_EXPAND_AND_QUOTE(str) FSE_QUOTE(str) 4756337Skato#define FSE_VERSION_STRING FSE_EXPAND_AND_QUOTE(FSE_LIB_VERSION) 4856337Skato 4956337Skato#define FSE_VERSION_NUMBER (FSE_VERSION_MAJOR *100*100 + FSE_VERSION_MINOR *100 + FSE_VERSION_RELEASE) 5056337SkatoFSE_PUBLIC_API unsigned FSE_versionNumber(void); /*< library version number; to be used when checking dll version */ 5156337Skato 5256337Skato 5356337Skato/*-**************************************** 5456337Skato* FSE simple functions 5556337Skato******************************************/ 5656337Skato/*! FSE_compress() : 5756337Skato Compress content of buffer 'src', of size 'srcSize', into destination buffer 'dst'. 5856337Skato 'dst' buffer must be already allocated. Compression runs faster is dstCapacity >= FSE_compressBound(srcSize). 5956337Skato @return : size of compressed data (<= dstCapacity). 6056337Skato Special values : if return == 0, srcData is not compressible => Nothing is stored within dst !!! 6156337Skato if return == 1, srcData is a single byte symbol * srcSize times. Use RLE compression instead. 6256337Skato if FSE_isError(return), compression failed (more details using FSE_getErrorName()) 6356337Skato*/ 6456337SkatoFSE_PUBLIC_API size_t FSE_compress(void* dst, size_t dstCapacity, 6556337Skato const void* src, size_t srcSize); 6656337Skato 6756337Skato/*! FSE_decompress(): 6856337Skato Decompress FSE data from buffer 'cSrc', of size 'cSrcSize', 6956337Skato into already allocated destination buffer 'dst', of size 'dstCapacity'. 7056337Skato @return : size of regenerated data (<= maxDstSize), 7156337Skato or an error code, which can be tested using FSE_isError() . 7256337Skato 7356337Skato ** Important ** : FSE_decompress() does not decompress non-compressible nor RLE data !!! 7456337Skato Why ? : making this distinction requires a header. 7556337Skato Header management is intentionally delegated to the user layer, which can better manage special cases. 7656337Skato*/ 7756337SkatoFSE_PUBLIC_API size_t FSE_decompress(void* dst, size_t dstCapacity, 7856337Skato const void* cSrc, size_t cSrcSize); 7956337Skato 8056337Skato 8156337Skato/*-***************************************** 8256337Skato* Tool functions 8356337Skato******************************************/ 8456337SkatoFSE_PUBLIC_API size_t FSE_compressBound(size_t size); /* maximum compressed size */ 8556337Skato 8656337Skato/* Error Management */ 8756337SkatoFSE_PUBLIC_API unsigned FSE_isError(size_t code); /* tells if a return value is an error code */ 8856337SkatoFSE_PUBLIC_API const char* FSE_getErrorName(size_t code); /* provides error code string (useful for debugging) */ 8956337Skato 9056337Skato 9156337Skato/*-***************************************** 9256337Skato* FSE advanced functions 9356337Skato******************************************/ 9456337Skato/*! FSE_compress2() : 9556337Skato Same as FSE_compress(), but allows the selection of 'maxSymbolValue' and 'tableLog' 9656337Skato Both parameters can be defined as '0' to mean : use default value 9756337Skato @return : size of compressed data 9856337Skato Special values : if return == 0, srcData is not compressible => Nothing is stored within cSrc !!! 9956337Skato if return == 1, srcData is a single byte symbol * srcSize times. Use RLE compression. 10056337Skato if FSE_isError(return), it's an error code. 10156337Skato*/ 10256337SkatoFSE_PUBLIC_API size_t FSE_compress2 (void* dst, size_t dstSize, const void* src, size_t srcSize, unsigned maxSymbolValue, unsigned tableLog); 10356337Skato 10456337Skato 10556337Skato/*-***************************************** 10656337Skato* FSE detailed API 10756337Skato******************************************/ 10856337Skato/*! 10958381SnyanFSE_compress() does the following: 11058381Snyan1. count symbol occurrence from source[] into table count[] (see hist.h) 11158381Snyan2. normalize counters so that sum(count[]) == Power_of_2 (2^tableLog) 11258381Snyan3. save normalized counters to memory buffer using writeNCount() 11356337Skato4. build encoding table 'CTable' from normalized counters 11456337Skato5. encode the data stream using encoding table 'CTable' 11556337Skato 11656337SkatoFSE_decompress() does the following: 11756337Skato1. read normalized counters with readNCount() 11856337Skato2. build decoding table 'DTable' from normalized counters 11956337Skato3. decode the data stream using decoding table 'DTable' 12056337Skato 12156337SkatoThe following API allows targeting specific sub-functions for advanced tasks. 12256337SkatoFor example, it's possible to compress several blocks using the same 'CTable', 12356337Skatoor to save and provide normalized distribution using external method. 12456337Skato*/ 12556337Skato 12656337Skato/* *** COMPRESSION *** */ 12756337Skato 12856337Skato/*! FSE_optimalTableLog(): 12956337Skato dynamically downsize 'tableLog' when conditions are met. 13056337Skato It saves CPU time, by using smaller tables, while preserving or even improving compression ratio. 13156337Skato @return : recommended tableLog (necessarily <= 'maxTableLog') */ 13256337SkatoFSE_PUBLIC_API unsigned FSE_optimalTableLog(unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue); 13390012Snyan 13490012Snyan/*! FSE_normalizeCount(): 13590012Snyan normalize counts so that sum(count[]) == Power_of_2 (2^tableLog) 13690012Snyan 'normalizedCounter' is a table of short, of minimum size (maxSymbolValue+1). 13790465Snyan useLowProbCount is a boolean parameter which trades off compressed size for 13890465Snyan faster header decoding. When it is set to 1, the compressed data will be slightly 13990465Snyan smaller. And when it is set to 0, FSE_readNCount() and FSE_buildDTable() will be 14090465Snyan faster. If you are compressing a small amount of data (< 2 KB) then useLowProbCount=0 14190465Snyan is a good default, since header deserialization makes a big speed difference. 14290465Snyan Otherwise, useLowProbCount=1 is a good default, since the speed difference is small. 14390465Snyan @return : tableLog, 14490465Snyan or an errorCode, which can be tested using FSE_isError() */ 14590465SnyanFSE_PUBLIC_API size_t FSE_normalizeCount(short* normalizedCounter, unsigned tableLog, 14690465Snyan const unsigned* count, size_t srcSize, unsigned maxSymbolValue, unsigned useLowProbCount); 14790465Snyan 14890012Snyan/*! FSE_NCountWriteBound(): 14990465Snyan Provides the maximum possible size of an FSE normalized table, given 'maxSymbolValue' and 'tableLog'. 15090465Snyan Typically useful for allocation purpose. */ 15190465SnyanFSE_PUBLIC_API size_t FSE_NCountWriteBound(unsigned maxSymbolValue, unsigned tableLog); 15290465Snyan 15390465Snyan/*! FSE_writeNCount(): 15490012Snyan Compactly save 'normalizedCounter' into 'buffer'. 15590465Snyan @return : size of the compressed table, 15690465Snyan or an errorCode, which can be tested using FSE_isError(). */ 15790465SnyanFSE_PUBLIC_API size_t FSE_writeNCount (void* buffer, size_t bufferSize, 15890465Snyan const short* normalizedCounter, 15990012Snyan unsigned maxSymbolValue, unsigned tableLog); 16090465Snyan 16190465Snyan/*! Constructor and Destructor of FSE_CTable. 16290465Snyan Note that FSE_CTable size depends on 'tableLog' and 'maxSymbolValue' */ 16390465Snyantypedef unsigned FSE_CTable; /* don't allocate that. It's only meant to be more restrictive than void* */ 16490012SnyanFSE_PUBLIC_API FSE_CTable* FSE_createCTable (unsigned maxSymbolValue, unsigned tableLog); 16590465SnyanFSE_PUBLIC_API void FSE_freeCTable (FSE_CTable* ct); 16690465Snyan 16790465Snyan/*! FSE_buildCTable(): 16890465Snyan Builds `ct`, which must be already allocated, using FSE_createCTable(). 16990465Snyan @return : 0, or an errorCode, which can be tested using FSE_isError() */ 17090465SnyanFSE_PUBLIC_API size_t FSE_buildCTable(FSE_CTable* ct, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog); 17190465Snyan 17290465Snyan/*! FSE_compress_usingCTable(): 17390465Snyan Compress `src` using `ct` into `dst` which must be already allocated. 17490465Snyan @return : size of compressed data (<= `dstCapacity`), 17590465Snyan or 0 if compressed data could not fit into `dst`, 17690012Snyan or an errorCode, which can be tested using FSE_isError() */ 17790465SnyanFSE_PUBLIC_API size_t FSE_compress_usingCTable (void* dst, size_t dstCapacity, const void* src, size_t srcSize, const FSE_CTable* ct); 17890465Snyan 17990465Snyan/*! 18090465SnyanTutorial : 18190465Snyan---------- 18290465SnyanThe first step is to count all symbols. FSE_count() does this job very fast. 18390012SnyanResult will be saved into 'count', a table of unsigned int, which must be already allocated, and have 'maxSymbolValuePtr[0]+1' cells. 18490465Snyan'src' is a table of bytes of size 'srcSize'. All values within 'src' MUST be <= maxSymbolValuePtr[0] 18590012SnyanmaxSymbolValuePtr[0] will be updated, with its real value (necessarily <= original value) 18690012SnyanFSE_count() will return the number of occurrence of the most frequent symbol. 18790012SnyanThis can be used to know if there is a single symbol within 'src', and to quickly evaluate its compressibility. 18890012SnyanIf there is an error, the function will return an ErrorCode (which can be tested using FSE_isError()). 18990012Snyan 19090467SnyanThe next step is to normalize the frequencies. 19190467SnyanFSE_normalizeCount() will ensure that sum of frequencies is == 2 ^'tableLog'. 19290467SnyanIt also guarantees a minimum of 1 to any Symbol with frequency >= 1. 19390467SnyanYou can use 'tableLog'==0 to mean "use default tableLog value". 19490467SnyanIf you are unsure of which tableLog value to use, you can ask FSE_optimalTableLog(), 19590467Snyanwhich will provide the optimal valid tableLog given sourceSize, maxSymbolValue, and a user-defined maximum (0 means "default"). 19690467Snyan 19790467SnyanThe result of FSE_normalizeCount() will be saved into a table, 19890467Snyancalled 'normalizedCounter', which is a table of signed short. 19990467Snyan'normalizedCounter' must be already allocated, and have at least 'maxSymbolValue+1' cells. 20090467SnyanThe return value is tableLog if everything proceeded as expected. 20190467SnyanIt is 0 if there is a single symbol within distribution. 20290467SnyanIf there is an error (ex: invalid tableLog value), the function will return an ErrorCode (which can be tested using FSE_isError()). 20390467Snyan 20490467Snyan'normalizedCounter' can be saved in a compact manner to a memory area using FSE_writeNCount(). 20590467Snyan'buffer' must be already allocated. 20690467SnyanFor guaranteed success, buffer size must be at least FSE_headerBound(). 20790467SnyanThe result of the function is the number of bytes written into 'buffer'. 20890467SnyanIf there is an error, the function will return an ErrorCode (which can be tested using FSE_isError(); ex : buffer size too small). 20990467Snyan 21090467Snyan'normalizedCounter' can then be used to create the compression table 'CTable'. 21190467SnyanThe space required by 'CTable' must be already allocated, using FSE_createCTable(). 21290467SnyanYou can then use FSE_buildCTable() to fill 'CTable'. 21390467SnyanIf there is an error, both functions will return an ErrorCode (which can be tested using FSE_isError()). 21490467Snyan 21590467Snyan'CTable' can then be used to compress 'src', with FSE_compress_usingCTable(). 21690467SnyanSimilar to FSE_count(), the convention is that 'src' is assumed to be a table of char of size 'srcSize' 21790467SnyanThe function returns the size of compressed data (without header), necessarily <= `dstCapacity`. 21890467SnyanIf it returns '0', compressed data could not fit into 'dst'. 21990467SnyanIf there is an error, the function will return an ErrorCode (which can be tested using FSE_isError()). 22090467Snyan*/ 22190467Snyan 22290467Snyan 22390467Snyan/* *** DECOMPRESSION *** */ 22490467Snyan 22590467Snyan/*! FSE_readNCount(): 22690467Snyan Read compactly saved 'normalizedCounter' from 'rBuffer'. 22790467Snyan @return : size read from 'rBuffer', 22890467Snyan or an errorCode, which can be tested using FSE_isError(). 22990467Snyan maxSymbolValuePtr[0] and tableLogPtr[0] will also be updated with their respective values */ 23090467SnyanFSE_PUBLIC_API size_t FSE_readNCount (short* normalizedCounter, 23190467Snyan unsigned* maxSymbolValuePtr, unsigned* tableLogPtr, 23290467Snyan const void* rBuffer, size_t rBuffSize); 23390467Snyan 23490467Snyan/*! FSE_readNCount_bmi2(): 23590467Snyan * Same as FSE_readNCount() but pass bmi2=1 when your CPU supports BMI2 and 0 otherwise. 23690467Snyan */ 23790467SnyanFSE_PUBLIC_API size_t FSE_readNCount_bmi2(short* normalizedCounter, 23890012Snyan unsigned* maxSymbolValuePtr, unsigned* tableLogPtr, 23990467Snyan const void* rBuffer, size_t rBuffSize, int bmi2); 24090467Snyan 24190012Snyan/*! Constructor and Destructor of FSE_DTable. 24290012Snyan Note that its size depends on 'tableLog' */ 24390012Snyantypedef unsigned FSE_DTable; /* don't allocate that. It's just a way to be more restrictive than void* */ 24490012SnyanFSE_PUBLIC_API FSE_DTable* FSE_createDTable(unsigned tableLog); 24590012SnyanFSE_PUBLIC_API void FSE_freeDTable(FSE_DTable* dt); 24690012Snyan 24790012Snyan/*! FSE_buildDTable(): 24890012Snyan Builds 'dt', which must be already allocated, using FSE_createDTable(). 24990012Snyan return : 0, or an errorCode, which can be tested using FSE_isError() */ 25090012SnyanFSE_PUBLIC_API size_t FSE_buildDTable (FSE_DTable* dt, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog); 25190012Snyan 25290012Snyan/*! FSE_decompress_usingDTable(): 25390012Snyan Decompress compressed source `cSrc` of size `cSrcSize` using `dt` 25490012Snyan into `dst` which must be already allocated. 25590012Snyan @return : size of regenerated data (necessarily <= `dstCapacity`), 25690467Snyan or an errorCode, which can be tested using FSE_isError() */ 25790012SnyanFSE_PUBLIC_API size_t FSE_decompress_usingDTable(void* dst, size_t dstCapacity, const void* cSrc, size_t cSrcSize, const FSE_DTable* dt); 25890467Snyan 25990467Snyan/*! 26090467SnyanTutorial : 26190467Snyan---------- 26290467Snyan(Note : these functions only decompress FSE-compressed blocks. 26390467Snyan If block is uncompressed, use memcpy() instead 26490467Snyan If block is a single repeated byte, use memset() instead ) 26590467Snyan 26690467SnyanThe first step is to obtain the normalized frequencies of symbols. 26790467SnyanThis can be performed by FSE_readNCount() if it was saved using FSE_writeNCount(). 26890467Snyan'normalizedCounter' must be already allocated, and have at least 'maxSymbolValuePtr[0]+1' cells of signed short. 26990467SnyanIn practice, that means it's necessary to know 'maxSymbolValue' beforehand, 27090467Snyanor size the table to handle worst case situations (typically 256). 27190467SnyanFSE_readNCount() will provide 'tableLog' and 'maxSymbolValue'. 27290467SnyanThe result of FSE_readNCount() is the number of bytes read from 'rBuffer'. 27390467SnyanNote that 'rBufferSize' must be at least 4 bytes, even if useful information is less than that. 27490467SnyanIf there is an error, the function will return an error code, which can be tested using FSE_isError(). 27590467Snyan 27690467SnyanThe next step is to build the decompression tables 'FSE_DTable' from 'normalizedCounter'. 27790467SnyanThis is performed by the function FSE_buildDTable(). 27890467SnyanThe space required by 'FSE_DTable' must be already allocated using FSE_createDTable(). 27990467SnyanIf there is an error, the function will return an error code, which can be tested using FSE_isError(). 28090467Snyan 28190467Snyan`FSE_DTable` can then be used to decompress `cSrc`, with FSE_decompress_usingDTable(). 28290467Snyan`cSrcSize` must be strictly correct, otherwise decompression will fail. 28390467SnyanFSE_decompress_usingDTable() result will tell how many bytes were regenerated (<=`dstCapacity`). 28490467SnyanIf there is an error, the function will return an error code, which can be tested using FSE_isError(). (ex: dst buffer too small) 28590467Snyan*/ 28690467Snyan 28790467Snyan#endif /* FSE_H */ 28890467Snyan 28990012Snyan#if !defined(FSE_H_FSE_STATIC_LINKING_ONLY) 29090012Snyan#define FSE_H_FSE_STATIC_LINKING_ONLY 29190467Snyan 29290467Snyan/* *** Dependency *** */ 29390467Snyan#include "bitstream.h" 29490467Snyan 29590467Snyan 29690012Snyan/* ***************************************** 29790467Snyan* Static allocation 29890012Snyan*******************************************/ 29990012Snyan/* FSE buffer bounds */ 30090012Snyan#define FSE_NCOUNTBOUND 512 30156337Skato#define FSE_BLOCKBOUND(size) ((size) + ((size)>>7) + 4 /* fse states */ + sizeof(size_t) /* bitContainer */) 30256337Skato#define FSE_COMPRESSBOUND(size) (FSE_NCOUNTBOUND + FSE_BLOCKBOUND(size)) /* Macro version, useful for static allocation */ 30356337Skato 30456337Skato/* It is possible to statically allocate FSE CTable/DTable as a table of FSE_CTable/FSE_DTable using below macros */ 30556337Skato#define FSE_CTABLE_SIZE_U32(maxTableLog, maxSymbolValue) (1 + (1<<((maxTableLog)-1)) + (((maxSymbolValue)+1)*2)) 30656337Skato#define FSE_DTABLE_SIZE_U32(maxTableLog) (1 + (1<<(maxTableLog))) 30756337Skato 30856337Skato/* or use the size to malloc() space directly. Pay attention to alignment restrictions though */ 30956337Skato#define FSE_CTABLE_SIZE(maxTableLog, maxSymbolValue) (FSE_CTABLE_SIZE_U32(maxTableLog, maxSymbolValue) * sizeof(FSE_CTable)) 31056337Skato#define FSE_DTABLE_SIZE(maxTableLog) (FSE_DTABLE_SIZE_U32(maxTableLog) * sizeof(FSE_DTable)) 31156337Skato 31256337Skato 31356337Skato/* ***************************************** 31456337Skato * FSE advanced API 31556337Skato ***************************************** */ 31656337Skato 31756337Skatounsigned FSE_optimalTableLog_internal(unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue, unsigned minus); 31856337Skato/*< same as FSE_optimalTableLog(), which used `minus==2` */ 31956337Skato 32056337Skato/* FSE_compress_wksp() : 32156337Skato * Same as FSE_compress2(), but using an externally allocated scratch buffer (`workSpace`). 32256337Skato * FSE_COMPRESS_WKSP_SIZE_U32() provides the minimum size required for `workSpace` as a table of FSE_CTable. 32356337Skato */ 32456337Skato#define FSE_COMPRESS_WKSP_SIZE_U32(maxTableLog, maxSymbolValue) ( FSE_CTABLE_SIZE_U32(maxTableLog, maxSymbolValue) + ((maxTableLog > 12) ? (1 << (maxTableLog - 2)) : 1024) ) 32556337Skatosize_t FSE_compress_wksp (void* dst, size_t dstSize, const void* src, size_t srcSize, unsigned maxSymbolValue, unsigned tableLog, void* workSpace, size_t wkspSize); 32656337Skato 32756337Skatosize_t FSE_buildCTable_raw (FSE_CTable* ct, unsigned nbBits); 32856337Skato/*< build a fake FSE_CTable, designed for a flat distribution, where each symbol uses nbBits */ 32956337Skato 33056337Skatosize_t FSE_buildCTable_rle (FSE_CTable* ct, unsigned char symbolValue); 33156337Skato/*< build a fake FSE_CTable, designed to compress always the same symbolValue */ 33256337Skato 33356337Skato/* FSE_buildCTable_wksp() : 33456337Skato * Same as FSE_buildCTable(), but using an externally allocated scratch buffer (`workSpace`). 33556337Skato * `wkspSize` must be >= `FSE_BUILD_CTABLE_WORKSPACE_SIZE_U32(maxSymbolValue, tableLog)` of `unsigned`. 33656337Skato * See FSE_buildCTable_wksp() for breakdown of workspace usage. 33756337Skato */ 33856337Skato#define FSE_BUILD_CTABLE_WORKSPACE_SIZE_U32(maxSymbolValue, tableLog) (((maxSymbolValue + 2) + (1ull << (tableLog)))/2 + sizeof(U64)/sizeof(U32) /* additional 8 bytes for potential table overwrite */) 33956337Skato#define FSE_BUILD_CTABLE_WORKSPACE_SIZE(maxSymbolValue, tableLog) (sizeof(unsigned) * FSE_BUILD_CTABLE_WORKSPACE_SIZE_U32(maxSymbolValue, tableLog)) 34056337Skatosize_t FSE_buildCTable_wksp(FSE_CTable* ct, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog, void* workSpace, size_t wkspSize); 34157136Skato 34256337Skato#define FSE_BUILD_DTABLE_WKSP_SIZE(maxTableLog, maxSymbolValue) (sizeof(short) * (maxSymbolValue + 1) + (1ULL << maxTableLog) + 8) 34356337Skato#define FSE_BUILD_DTABLE_WKSP_SIZE_U32(maxTableLog, maxSymbolValue) ((FSE_BUILD_DTABLE_WKSP_SIZE(maxTableLog, maxSymbolValue) + sizeof(unsigned) - 1) / sizeof(unsigned)) 34457136SkatoFSE_PUBLIC_API size_t FSE_buildDTable_wksp(FSE_DTable* dt, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog, void* workSpace, size_t wkspSize); 34556337Skato/*< Same as FSE_buildDTable(), using an externally allocated `workspace` produced with `FSE_BUILD_DTABLE_WKSP_SIZE_U32(maxSymbolValue)` */ 34656337Skato 34756337Skatosize_t FSE_buildDTable_raw (FSE_DTable* dt, unsigned nbBits); 34856337Skato/*< build a fake FSE_DTable, designed to read a flat distribution where each symbol uses nbBits */ 34956337Skato 35056337Skatosize_t FSE_buildDTable_rle (FSE_DTable* dt, unsigned char symbolValue); 35156337Skato/*< build a fake FSE_DTable, designed to always generate the same symbolValue */ 35256337Skato 35356337Skato#define FSE_DECOMPRESS_WKSP_SIZE_U32(maxTableLog, maxSymbolValue) (FSE_DTABLE_SIZE_U32(maxTableLog) + FSE_BUILD_DTABLE_WKSP_SIZE_U32(maxTableLog, maxSymbolValue) + (FSE_MAX_SYMBOL_VALUE + 1) / 2 + 1) 35456337Skato#define FSE_DECOMPRESS_WKSP_SIZE(maxTableLog, maxSymbolValue) (FSE_DECOMPRESS_WKSP_SIZE_U32(maxTableLog, maxSymbolValue) * sizeof(unsigned)) 35556337Skatosize_t FSE_decompress_wksp(void* dst, size_t dstCapacity, const void* cSrc, size_t cSrcSize, unsigned maxLog, void* workSpace, size_t wkspSize); 35656337Skato/*< same as FSE_decompress(), using an externally allocated `workSpace` produced with `FSE_DECOMPRESS_WKSP_SIZE_U32(maxLog, maxSymbolValue)` */ 35756337Skato 35856337Skatosize_t FSE_decompress_wksp_bmi2(void* dst, size_t dstCapacity, const void* cSrc, size_t cSrcSize, unsigned maxLog, void* workSpace, size_t wkspSize, int bmi2); 35956337Skato/*< Same as FSE_decompress_wksp() but with dynamic BMI2 support. Pass 1 if your CPU supports BMI2 or 0 if it doesn't. */ 36056337Skato 36156337Skatotypedef enum { 36256337Skato FSE_repeat_none, /*< Cannot use the previous table */ 36356337Skato FSE_repeat_check, /*< Can use the previous table but it must be checked */ 36456337Skato FSE_repeat_valid /*< Can use the previous table and it is assumed to be valid */ 36556337Skato } FSE_repeat; 36656337Skato 36756337Skato/* ***************************************** 36856337Skato* FSE symbol compression API 36956337Skato*******************************************/ 37056337Skato/*! 37156337Skato This API consists of small unitary functions, which highly benefit from being inlined. 37258381Snyan Hence their body are included in next section. 37381231Snyan*/ 37481231Snyantypedef struct { 37581231Snyan ptrdiff_t value; 37681231Snyan const void* stateTable; 37781231Snyan const void* symbolTT; 37881231Snyan unsigned stateLog; 37981231Snyan} FSE_CState_t; 38081231Snyan 38181231Snyanstatic void FSE_initCState(FSE_CState_t* CStatePtr, const FSE_CTable* ct); 38281231Snyan 38381231Snyanstatic void FSE_encodeSymbol(BIT_CStream_t* bitC, FSE_CState_t* CStatePtr, unsigned symbol); 38481231Snyan 38581231Snyanstatic void FSE_flushCState(BIT_CStream_t* bitC, const FSE_CState_t* CStatePtr); 38656337Skato 38781231Snyan/*< 38856337SkatoThese functions are inner components of FSE_compress_usingCTable(). 38956337SkatoThey allow the creation of custom streams, mixing multiple tables and bit sources. 39058381Snyan 39158381SnyanA key property to keep in mind is that encoding and decoding are done **in reverse direction**. 39258381SnyanSo the first symbol you will encode is the last you will decode, like a LIFO stack. 39359778Snyan 39459778SnyanYou will need a few variables to track your CStream. They are : 39559778Snyan 39659778SnyanFSE_CTable ct; // Provided by FSE_buildCTable() 39759778SnyanBIT_CStream_t bitStream; // bitStream tracking structure 39859778SnyanFSE_CState_t state; // State tracking structure (can have several) 39959778Snyan 40059778Snyan 40159778SnyanThe first thing to do is to init bitStream and state. 40259778Snyan size_t errorCode = BIT_initCStream(&bitStream, dstBuffer, maxDstSize); 40359778Snyan FSE_initCState(&state, ct); 40459778Snyan 40559778SnyanNote that BIT_initCStream() can produce an error code, so its result should be tested, using FSE_isError(); 40659778SnyanYou can then encode your input data, byte after byte. 40759778SnyanFSE_encodeSymbol() outputs a maximum of 'tableLog' bits at a time. 40859778SnyanRemember decoding will be done in reverse direction. 40959778Snyan FSE_encodeByte(&bitStream, &state, symbol); 41059778Snyan 41159778SnyanAt any time, you can also add any bit sequence. 41259778SnyanNote : maximum allowed nbBits is 25, for compatibility with 32-bits decoders 41359778Snyan BIT_addBits(&bitStream, bitField, nbBits); 41459778Snyan 41559778SnyanThe above methods don't commit data to memory, they just store it into local register, for speed. 41659778SnyanLocal register size is 64-bits on 64-bits systems, 32-bits on 32-bits systems (size_t). 41759778SnyanWriting data to memory is a manual operation, performed by the flushBits function. 41859778Snyan BIT_flushBits(&bitStream); 41959778Snyan 42059778SnyanYour last FSE encoding operation shall be to flush your last state value(s). 42159778Snyan FSE_flushState(&bitStream, &state); 42259778Snyan 42359778SnyanFinally, you must close the bitStream. 42459778SnyanThe function returns the size of CStream in bytes. 42559778SnyanIf data couldn't fit into dstBuffer, it will return a 0 ( == not compressible) 42659778SnyanIf there is an error, it returns an errorCode (which can be tested using FSE_isError()). 42759778Snyan size_t size = BIT_closeCStream(&bitStream); 42859778Snyan*/ 42959778Snyan 43059778Snyan 43159778Snyan/* ***************************************** 43259778Snyan* FSE symbol decompression API 43358381Snyan*******************************************/ 43456337Skatotypedef struct { 43558381Snyan size_t state; 43658381Snyan const void* table; /* precise table may vary, depending on U16 */ 43758381Snyan} FSE_DState_t; 43858381Snyan 43956337Skato 44058381Snyanstatic void FSE_initDState(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD, const FSE_DTable* dt); 44158381Snyan 44258381Snyanstatic unsigned char FSE_decodeSymbol(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD); 44358381Snyan 44458381Snyanstatic unsigned FSE_endOfDState(const FSE_DState_t* DStatePtr); 44556337Skato 44658381Snyan/*< 44758381SnyanLet's now decompose FSE_decompress_usingDTable() into its unitary components. 44858381SnyanYou will decode FSE-encoded symbols from the bitStream, 44958381Snyanand also any other bitFields you put in, **in reverse order**. 45058381Snyan 45158381SnyanYou will need a few variables to track your bitStream. They are : 45258381Snyan 45356337SkatoBIT_DStream_t DStream; // Stream context 45456337SkatoFSE_DState_t DState; // State context. Multiple ones are possible 45558381SnyanFSE_DTable* DTablePtr; // Decoding table, provided by FSE_buildDTable() 45658381Snyan 45758381SnyanThe first thing to do is to init the bitStream. 45856337Skato errorCode = BIT_initDStream(&DStream, srcBuffer, srcSize); 45956337Skato 46058381SnyanYou should then retrieve your initial state(s) 46158381Snyan(in reverse flushing order if you have several ones) : 46258381Snyan errorCode = FSE_initDState(&DState, &DStream, DTablePtr); 46358381Snyan 464153110SruYou can then decode your data, symbol after symbol. 46558381SnyanFor information the maximum number of bits read by FSE_decodeSymbol() is 'tableLog'. 46658381SnyanKeep in mind that symbols are decoded in reverse order, like a LIFO stack (last in, first out). 46758381Snyan unsigned char symbol = FSE_decodeSymbol(&DState, &DStream); 46856337Skato 46964021SnyanYou can retrieve any bitfield you eventually stored into the bitStream (in reverse order) 47064021SnyanNote : maximum allowed nbBits is 25, for 32-bits compatibility 47164021Snyan size_t bitField = BIT_readBits(&DStream, nbBits); 47264021Snyan 47364021SnyanAll above operations only read from local register (which size depends on size_t). 47464021SnyanRefueling the register from memory is manually performed by the reload method. 47581231Snyan endSignal = FSE_reloadDStream(&DStream); 47681231Snyan 47758381SnyanBIT_reloadDStream() result tells if there is still some more data to read from DStream. 47858381SnyanBIT_DStream_unfinished : there is still some data left into the DStream. 47956337SkatoBIT_DStream_endOfBuffer : Dstream reached end of buffer. Its container may no longer be completely filled. 48058381SnyanBIT_DStream_completed : Dstream reached its exact end, corresponding in general to decompression completed. 48156337SkatoBIT_DStream_tooFar : Dstream went too far. Decompression result is corrupted. 48258381Snyan 48356337SkatoWhen reaching end of buffer (BIT_DStream_endOfBuffer), progress slowly, notably if you decode multiple symbols per loop, 48458381Snyanto properly detect the exact end of stream. 48556337SkatoAfter each decoded symbol, check if DStream is fully consumed using this simple test : 48658381Snyan BIT_reloadDStream(&DStream) >= BIT_DStream_completed 48756337Skato 48858381SnyanWhen it's done, verify decompression is fully completed, by checking both DStream and the relevant states. 48958381SnyanChecking if DStream has reached its end is performed by : 49058381Snyan BIT_endOfDStream(&DStream); 49158381SnyanCheck also the states. There might be some symbols left there, if some high probability ones (>50%) are possible. 49258381Snyan FSE_endOfDState(&DState); 49358381Snyan*/ 49458381Snyan 49558381Snyan 49658381Snyan/* ***************************************** 49758381Snyan* FSE unsafe API 49858381Snyan*******************************************/ 49958381Snyanstatic unsigned char FSE_decodeSymbolFast(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD); 50058381Snyan/* faster, but works only if nbBits is always >= 1 (otherwise, result will be corrupted) */ 50158381Snyan 50258381Snyan 50356337Skato/* ***************************************** 50458381Snyan* Implementation of inlined functions 50558381Snyan*******************************************/ 50658381Snyantypedef struct { 50758381Snyan int deltaFindState; 50856337Skato U32 deltaNbBits; 50958381Snyan} FSE_symbolCompressionTransform; /* total 8 bytes */ 51058381Snyan 51158381SnyanMEM_STATIC void FSE_initCState(FSE_CState_t* statePtr, const FSE_CTable* ct) 51258381Snyan{ 51358381Snyan const void* ptr = ct; 51458381Snyan const U16* u16ptr = (const U16*) ptr; 51558381Snyan const U32 tableLog = MEM_read16(ptr); 51656337Skato statePtr->value = (ptrdiff_t)1<<tableLog; 51758381Snyan statePtr->stateTable = u16ptr+2; 51858381Snyan statePtr->symbolTT = ct + 1 + (tableLog ? (1<<(tableLog-1)) : 1); 51958381Snyan statePtr->stateLog = tableLog; 52056337Skato} 52158381Snyan 52258381Snyan 52358381Snyan/*! FSE_initCState2() : 52456337Skato* Same as FSE_initCState(), but the first symbol to include (which will be the last to be read) 52558381Snyan* uses the smallest state value possible, saving the cost of this symbol */ 52658381SnyanMEM_STATIC void FSE_initCState2(FSE_CState_t* statePtr, const FSE_CTable* ct, U32 symbol) 52758381Snyan{ 52856337Skato FSE_initCState(statePtr, ct); 52958381Snyan { const FSE_symbolCompressionTransform symbolTT = ((const FSE_symbolCompressionTransform*)(statePtr->symbolTT))[symbol]; 53058381Snyan const U16* stateTable = (const U16*)(statePtr->stateTable); 53158381Snyan U32 nbBitsOut = (U32)((symbolTT.deltaNbBits + (1<<15)) >> 16); 53256337Skato statePtr->value = (nbBitsOut << 16) - symbolTT.deltaNbBits; 53358381Snyan statePtr->value = stateTable[(statePtr->value >> nbBitsOut) + symbolTT.deltaFindState]; 53458381Snyan } 53558381Snyan} 53658381Snyan 53758381SnyanMEM_STATIC void FSE_encodeSymbol(BIT_CStream_t* bitC, FSE_CState_t* statePtr, unsigned symbol) 53858381Snyan{ 53956337Skato FSE_symbolCompressionTransform const symbolTT = ((const FSE_symbolCompressionTransform*)(statePtr->symbolTT))[symbol]; 54058381Snyan const U16* const stateTable = (const U16*)(statePtr->stateTable); 54158381Snyan U32 const nbBitsOut = (U32)((statePtr->value + symbolTT.deltaNbBits) >> 16); 54258381Snyan BIT_addBits(bitC, statePtr->value, nbBitsOut); 54358381Snyan statePtr->value = stateTable[ (statePtr->value >> nbBitsOut) + symbolTT.deltaFindState]; 54458381Snyan} 54558381Snyan 54656337SkatoMEM_STATIC void FSE_flushCState(BIT_CStream_t* bitC, const FSE_CState_t* statePtr) 54758381Snyan{ 54858381Snyan BIT_addBits(bitC, statePtr->value, statePtr->stateLog); 54958381Snyan BIT_flushBits(bitC); 55058381Snyan} 55158381Snyan 55258381Snyan 55358381Snyan/* FSE_getMaxNbBits() : 55458381Snyan * Approximate maximum cost of a symbol, in bits. 55556337Skato * Fractional get rounded up (i.e : a symbol with a normalized frequency of 3 gives the same result as a frequency of 2) 55658381Snyan * note 1 : assume symbolValue is valid (<= maxSymbolValue) 55758381Snyan * note 2 : if freq[symbolValue]==0, @return a fake cost of tableLog+1 bits */ 55858381SnyanMEM_STATIC U32 FSE_getMaxNbBits(const void* symbolTTPtr, U32 symbolValue) 55958381Snyan{ 56058381Snyan const FSE_symbolCompressionTransform* symbolTT = (const FSE_symbolCompressionTransform*) symbolTTPtr; 56158381Snyan return (symbolTT[symbolValue].deltaNbBits + ((1<<16)-1)) >> 16; 56258381Snyan} 56358381Snyan 56456337Skato/* FSE_bitCost() : 56558381Snyan * Approximate symbol cost, as fractional value, using fixed-point format (accuracyLog fractional bits) 56658381Snyan * note 1 : assume symbolValue is valid (<= maxSymbolValue) 56758381Snyan * note 2 : if freq[symbolValue]==0, @return a fake cost of tableLog+1 bits */ 56858381SnyanMEM_STATIC U32 FSE_bitCost(const void* symbolTTPtr, U32 tableLog, U32 symbolValue, U32 accuracyLog) 56958381Snyan{ 57058381Snyan const FSE_symbolCompressionTransform* symbolTT = (const FSE_symbolCompressionTransform*) symbolTTPtr; 57158381Snyan U32 const minNbBits = symbolTT[symbolValue].deltaNbBits >> 16; 57258381Snyan U32 const threshold = (minNbBits+1) << 16; 57356337Skato assert(tableLog < 16); 57458381Snyan assert(accuracyLog < 31-tableLog); /* ensure enough room for renormalization double shift */ 57558381Snyan { U32 const tableSize = 1 << tableLog; 57658381Snyan U32 const deltaFromThreshold = threshold - (symbolTT[symbolValue].deltaNbBits + tableSize); 57758381Snyan U32 const normalizedDeltaFromThreshold = (deltaFromThreshold << accuracyLog) >> tableLog; /* linear interpolation (very approximate) */ 57856337Skato U32 const bitMultiplier = 1 << accuracyLog; 57958381Snyan assert(symbolTT[symbolValue].deltaNbBits + tableSize <= threshold); 58058381Snyan assert(normalizedDeltaFromThreshold <= bitMultiplier); 58158381Snyan return (minNbBits+1)*bitMultiplier - normalizedDeltaFromThreshold; 58258381Snyan } 58356337Skato} 58458381Snyan 58558381Snyan 58658381Snyan/* ====== Decompression ====== */ 58758381Snyan 58856337Skatotypedef struct { 58958381Snyan U16 tableLog; 59058381Snyan U16 fastMode; 59158381Snyan} FSE_DTableHeader; /* sizeof U32 */ 59258381Snyan 59356337Skatotypedef struct 59458381Snyan{ 59558381Snyan unsigned short newState; 59658381Snyan unsigned char symbol; 59758381Snyan unsigned char nbBits; 59856337Skato} FSE_decode_t; /* size == U32 */ 59958381Snyan 60058381SnyanMEM_STATIC void FSE_initDState(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD, const FSE_DTable* dt) 60158381Snyan{ 60258381Snyan const void* ptr = dt; 60356337Skato const FSE_DTableHeader* const DTableH = (const FSE_DTableHeader*)ptr; 60458381Snyan DStatePtr->state = BIT_readBits(bitD, DTableH->tableLog); 60558381Snyan BIT_reloadDStream(bitD); 60658381Snyan DStatePtr->table = dt + 1; 60758381Snyan} 60858381Snyan 60958381SnyanMEM_STATIC BYTE FSE_peekSymbol(const FSE_DState_t* DStatePtr) 61058381Snyan{ 61158381Snyan FSE_decode_t const DInfo = ((const FSE_decode_t*)(DStatePtr->table))[DStatePtr->state]; 61258381Snyan return DInfo.symbol; 61358381Snyan} 61458381Snyan 61556337SkatoMEM_STATIC void FSE_updateState(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD) 61658381Snyan{ 61758381Snyan FSE_decode_t const DInfo = ((const FSE_decode_t*)(DStatePtr->table))[DStatePtr->state]; 61858381Snyan U32 const nbBits = DInfo.nbBits; 61956337Skato size_t const lowBits = BIT_readBits(bitD, nbBits); 62058381Snyan DStatePtr->state = DInfo.newState + lowBits; 62158381Snyan} 62258381Snyan 62356337SkatoMEM_STATIC BYTE FSE_decodeSymbol(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD) 62458381Snyan{ 62558381Snyan FSE_decode_t const DInfo = ((const FSE_decode_t*)(DStatePtr->table))[DStatePtr->state]; 62658381Snyan U32 const nbBits = DInfo.nbBits; 62756337Skato BYTE const symbol = DInfo.symbol; 62858381Snyan size_t const lowBits = BIT_readBits(bitD, nbBits); 62958381Snyan 63058381Snyan DStatePtr->state = DInfo.newState + lowBits; 63156337Skato return symbol; 63258381Snyan} 63358381Snyan 63458381Snyan/*! FSE_decodeSymbolFast() : 63556337Skato unsafe, only works if no symbol has a probability > 50% */ 63658381SnyanMEM_STATIC BYTE FSE_decodeSymbolFast(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD) 63758381Snyan{ 63858381Snyan FSE_decode_t const DInfo = ((const FSE_decode_t*)(DStatePtr->table))[DStatePtr->state]; 63958381Snyan U32 const nbBits = DInfo.nbBits; 64058381Snyan BYTE const symbol = DInfo.symbol; 64158381Snyan size_t const lowBits = BIT_readBitsFast(bitD, nbBits); 64258381Snyan 64358381Snyan DStatePtr->state = DInfo.newState + lowBits; 64458381Snyan return symbol; 64558381Snyan} 64658381Snyan 64758381SnyanMEM_STATIC unsigned FSE_endOfDState(const FSE_DState_t* DStatePtr) 64858381Snyan{ 64958381Snyan return DStatePtr->state == 0; 65058381Snyan} 65158381Snyan 65258381Snyan 65358381Snyan 65458381Snyan#ifndef FSE_COMMONDEFS_ONLY 65558381Snyan 65658381Snyan/* ************************************************************** 65758381Snyan* Tuning parameters 65858381Snyan****************************************************************/ 65958381Snyan/*!MEMORY_USAGE : 66058381Snyan* Memory usage formula : N->2^N Bytes (examples : 10 -> 1KB; 12 -> 4KB ; 16 -> 64KB; 20 -> 1MB; etc.) 66158381Snyan* Increasing memory usage improves compression ratio 66264021Snyan* Reduced memory usage can improve speed, due to cache effect 66358381Snyan* Recommended max value is 14, for 16KB, which nicely fits into Intel x86 L1 cache */ 66458381Snyan#ifndef FSE_MAX_MEMORY_USAGE 66558381Snyan# define FSE_MAX_MEMORY_USAGE 14 66664021Snyan#endif 66764021Snyan#ifndef FSE_DEFAULT_MEMORY_USAGE 66864021Snyan# define FSE_DEFAULT_MEMORY_USAGE 13 66964021Snyan#endif 67064021Snyan#if (FSE_DEFAULT_MEMORY_USAGE > FSE_MAX_MEMORY_USAGE) 67164021Snyan# error "FSE_DEFAULT_MEMORY_USAGE must be <= FSE_MAX_MEMORY_USAGE" 67264021Snyan#endif 67364021Snyan 67464021Snyan/*!FSE_MAX_SYMBOL_VALUE : 67564021Snyan* Maximum symbol value authorized. 67664021Snyan* Required for proper stack allocation */ 67764021Snyan#ifndef FSE_MAX_SYMBOL_VALUE 67864021Snyan# define FSE_MAX_SYMBOL_VALUE 255 67964021Snyan#endif 68064021Snyan 68164021Snyan/* ************************************************************** 68264021Snyan* template functions type & suffix 68358381Snyan****************************************************************/ 68458381Snyan#define FSE_FUNCTION_TYPE BYTE 68558381Snyan#define FSE_FUNCTION_EXTENSION 68658381Snyan#define FSE_DECODE_TYPE FSE_decode_t 68758381Snyan 68858381Snyan 68964021Snyan#endif /* !FSE_COMMONDEFS_ONLY */ 69064021Snyan 69161950Snyan 69261950Snyan/* *************************************************************** 69361950Snyan* Constants 69464021Snyan*****************************************************************/ 69558381Snyan#define FSE_MAX_TABLELOG (FSE_MAX_MEMORY_USAGE-2) 69658381Snyan#define FSE_MAX_TABLESIZE (1U<<FSE_MAX_TABLELOG) 69758381Snyan#define FSE_MAXTABLESIZE_MASK (FSE_MAX_TABLESIZE-1) 69858381Snyan#define FSE_DEFAULT_TABLELOG (FSE_DEFAULT_MEMORY_USAGE-2) 69958381Snyan#define FSE_MIN_TABLELOG 5 70058381Snyan 70164021Snyan#define FSE_TABLELOG_ABSOLUTE_MAX 15 70261950Snyan#if FSE_MAX_TABLELOG > FSE_TABLELOG_ABSOLUTE_MAX 70361950Snyan# error "FSE_MAX_TABLELOG > FSE_TABLELOG_ABSOLUTE_MAX is not supported" 70461950Snyan#endif 70561950Snyan 70658381Snyan#define FSE_TABLESTEP(tableSize) (((tableSize)>>1) + ((tableSize)>>3) + 3) 70758381Snyan 70858381Snyan 70956337Skato#endif /* FSE_STATIC_LINKING_ONLY */ 71058381Snyan 71158381Snyan 71258381Snyan