1*a28cd43dSSascha Wildner /* ******************************************************************
2*a28cd43dSSascha Wildner * FSE : Finite State Entropy codec
3*a28cd43dSSascha Wildner * Public Prototypes declaration
4*a28cd43dSSascha Wildner * Copyright (c) 2013-2020, Yann Collet, Facebook, Inc.
5*a28cd43dSSascha Wildner *
6*a28cd43dSSascha Wildner * You can contact the author at :
7*a28cd43dSSascha Wildner * - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
8*a28cd43dSSascha Wildner *
9*a28cd43dSSascha Wildner * This source code is licensed under both the BSD-style license (found in the
10*a28cd43dSSascha Wildner * LICENSE file in the root directory of this source tree) and the GPLv2 (found
11*a28cd43dSSascha Wildner * in the COPYING file in the root directory of this source tree).
12*a28cd43dSSascha Wildner * You may select, at your option, one of the above-listed licenses.
13*a28cd43dSSascha Wildner ****************************************************************** */
14*a28cd43dSSascha Wildner
15*a28cd43dSSascha Wildner #if defined (__cplusplus)
16*a28cd43dSSascha Wildner extern "C" {
17*a28cd43dSSascha Wildner #endif
18*a28cd43dSSascha Wildner
19*a28cd43dSSascha Wildner #ifndef FSE_H
20*a28cd43dSSascha Wildner #define FSE_H
21*a28cd43dSSascha Wildner
22*a28cd43dSSascha Wildner
23*a28cd43dSSascha Wildner /*-*****************************************
24*a28cd43dSSascha Wildner * Dependencies
25*a28cd43dSSascha Wildner ******************************************/
26*a28cd43dSSascha Wildner #include "zstd_deps.h" /* size_t, ptrdiff_t */
27*a28cd43dSSascha Wildner
28*a28cd43dSSascha Wildner
29*a28cd43dSSascha Wildner /*-*****************************************
30*a28cd43dSSascha Wildner * FSE_PUBLIC_API : control library symbols visibility
31*a28cd43dSSascha Wildner ******************************************/
32*a28cd43dSSascha Wildner #if defined(FSE_DLL_EXPORT) && (FSE_DLL_EXPORT==1) && defined(__GNUC__) && (__GNUC__ >= 4)
33*a28cd43dSSascha Wildner # define FSE_PUBLIC_API __attribute__ ((visibility ("default")))
34*a28cd43dSSascha Wildner #elif defined(FSE_DLL_EXPORT) && (FSE_DLL_EXPORT==1) /* Visual expected */
35*a28cd43dSSascha Wildner # define FSE_PUBLIC_API __declspec(dllexport)
36*a28cd43dSSascha Wildner #elif defined(FSE_DLL_IMPORT) && (FSE_DLL_IMPORT==1)
37*a28cd43dSSascha Wildner # 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.*/
38*a28cd43dSSascha Wildner #else
39*a28cd43dSSascha Wildner # define FSE_PUBLIC_API
40*a28cd43dSSascha Wildner #endif
41*a28cd43dSSascha Wildner
42*a28cd43dSSascha Wildner /*------ Version ------*/
43*a28cd43dSSascha Wildner #define FSE_VERSION_MAJOR 0
44*a28cd43dSSascha Wildner #define FSE_VERSION_MINOR 9
45*a28cd43dSSascha Wildner #define FSE_VERSION_RELEASE 0
46*a28cd43dSSascha Wildner
47*a28cd43dSSascha Wildner #define FSE_LIB_VERSION FSE_VERSION_MAJOR.FSE_VERSION_MINOR.FSE_VERSION_RELEASE
48*a28cd43dSSascha Wildner #define FSE_QUOTE(str) #str
49*a28cd43dSSascha Wildner #define FSE_EXPAND_AND_QUOTE(str) FSE_QUOTE(str)
50*a28cd43dSSascha Wildner #define FSE_VERSION_STRING FSE_EXPAND_AND_QUOTE(FSE_LIB_VERSION)
51*a28cd43dSSascha Wildner
52*a28cd43dSSascha Wildner #define FSE_VERSION_NUMBER (FSE_VERSION_MAJOR *100*100 + FSE_VERSION_MINOR *100 + FSE_VERSION_RELEASE)
53*a28cd43dSSascha Wildner FSE_PUBLIC_API unsigned FSE_versionNumber(void); /**< library version number; to be used when checking dll version */
54*a28cd43dSSascha Wildner
55*a28cd43dSSascha Wildner
56*a28cd43dSSascha Wildner /*-****************************************
57*a28cd43dSSascha Wildner * FSE simple functions
58*a28cd43dSSascha Wildner ******************************************/
59*a28cd43dSSascha Wildner /*! FSE_compress() :
60*a28cd43dSSascha Wildner Compress content of buffer 'src', of size 'srcSize', into destination buffer 'dst'.
61*a28cd43dSSascha Wildner 'dst' buffer must be already allocated. Compression runs faster is dstCapacity >= FSE_compressBound(srcSize).
62*a28cd43dSSascha Wildner @return : size of compressed data (<= dstCapacity).
63*a28cd43dSSascha Wildner Special values : if return == 0, srcData is not compressible => Nothing is stored within dst !!!
64*a28cd43dSSascha Wildner if return == 1, srcData is a single byte symbol * srcSize times. Use RLE compression instead.
65*a28cd43dSSascha Wildner if FSE_isError(return), compression failed (more details using FSE_getErrorName())
66*a28cd43dSSascha Wildner */
67*a28cd43dSSascha Wildner FSE_PUBLIC_API size_t FSE_compress(void* dst, size_t dstCapacity,
68*a28cd43dSSascha Wildner const void* src, size_t srcSize);
69*a28cd43dSSascha Wildner
70*a28cd43dSSascha Wildner /*! FSE_decompress():
71*a28cd43dSSascha Wildner Decompress FSE data from buffer 'cSrc', of size 'cSrcSize',
72*a28cd43dSSascha Wildner into already allocated destination buffer 'dst', of size 'dstCapacity'.
73*a28cd43dSSascha Wildner @return : size of regenerated data (<= maxDstSize),
74*a28cd43dSSascha Wildner or an error code, which can be tested using FSE_isError() .
75*a28cd43dSSascha Wildner
76*a28cd43dSSascha Wildner ** Important ** : FSE_decompress() does not decompress non-compressible nor RLE data !!!
77*a28cd43dSSascha Wildner Why ? : making this distinction requires a header.
78*a28cd43dSSascha Wildner Header management is intentionally delegated to the user layer, which can better manage special cases.
79*a28cd43dSSascha Wildner */
80*a28cd43dSSascha Wildner FSE_PUBLIC_API size_t FSE_decompress(void* dst, size_t dstCapacity,
81*a28cd43dSSascha Wildner const void* cSrc, size_t cSrcSize);
82*a28cd43dSSascha Wildner
83*a28cd43dSSascha Wildner
84*a28cd43dSSascha Wildner /*-*****************************************
85*a28cd43dSSascha Wildner * Tool functions
86*a28cd43dSSascha Wildner ******************************************/
87*a28cd43dSSascha Wildner FSE_PUBLIC_API size_t FSE_compressBound(size_t size); /* maximum compressed size */
88*a28cd43dSSascha Wildner
89*a28cd43dSSascha Wildner /* Error Management */
90*a28cd43dSSascha Wildner FSE_PUBLIC_API unsigned FSE_isError(size_t code); /* tells if a return value is an error code */
91*a28cd43dSSascha Wildner FSE_PUBLIC_API const char* FSE_getErrorName(size_t code); /* provides error code string (useful for debugging) */
92*a28cd43dSSascha Wildner
93*a28cd43dSSascha Wildner
94*a28cd43dSSascha Wildner /*-*****************************************
95*a28cd43dSSascha Wildner * FSE advanced functions
96*a28cd43dSSascha Wildner ******************************************/
97*a28cd43dSSascha Wildner /*! FSE_compress2() :
98*a28cd43dSSascha Wildner Same as FSE_compress(), but allows the selection of 'maxSymbolValue' and 'tableLog'
99*a28cd43dSSascha Wildner Both parameters can be defined as '0' to mean : use default value
100*a28cd43dSSascha Wildner @return : size of compressed data
101*a28cd43dSSascha Wildner Special values : if return == 0, srcData is not compressible => Nothing is stored within cSrc !!!
102*a28cd43dSSascha Wildner if return == 1, srcData is a single byte symbol * srcSize times. Use RLE compression.
103*a28cd43dSSascha Wildner if FSE_isError(return), it's an error code.
104*a28cd43dSSascha Wildner */
105*a28cd43dSSascha Wildner FSE_PUBLIC_API size_t FSE_compress2 (void* dst, size_t dstSize, const void* src, size_t srcSize, unsigned maxSymbolValue, unsigned tableLog);
106*a28cd43dSSascha Wildner
107*a28cd43dSSascha Wildner
108*a28cd43dSSascha Wildner /*-*****************************************
109*a28cd43dSSascha Wildner * FSE detailed API
110*a28cd43dSSascha Wildner ******************************************/
111*a28cd43dSSascha Wildner /*!
112*a28cd43dSSascha Wildner FSE_compress() does the following:
113*a28cd43dSSascha Wildner 1. count symbol occurrence from source[] into table count[] (see hist.h)
114*a28cd43dSSascha Wildner 2. normalize counters so that sum(count[]) == Power_of_2 (2^tableLog)
115*a28cd43dSSascha Wildner 3. save normalized counters to memory buffer using writeNCount()
116*a28cd43dSSascha Wildner 4. build encoding table 'CTable' from normalized counters
117*a28cd43dSSascha Wildner 5. encode the data stream using encoding table 'CTable'
118*a28cd43dSSascha Wildner
119*a28cd43dSSascha Wildner FSE_decompress() does the following:
120*a28cd43dSSascha Wildner 1. read normalized counters with readNCount()
121*a28cd43dSSascha Wildner 2. build decoding table 'DTable' from normalized counters
122*a28cd43dSSascha Wildner 3. decode the data stream using decoding table 'DTable'
123*a28cd43dSSascha Wildner
124*a28cd43dSSascha Wildner The following API allows targeting specific sub-functions for advanced tasks.
125*a28cd43dSSascha Wildner For example, it's possible to compress several blocks using the same 'CTable',
126*a28cd43dSSascha Wildner or to save and provide normalized distribution using external method.
127*a28cd43dSSascha Wildner */
128*a28cd43dSSascha Wildner
129*a28cd43dSSascha Wildner /* *** COMPRESSION *** */
130*a28cd43dSSascha Wildner
131*a28cd43dSSascha Wildner /*! FSE_optimalTableLog():
132*a28cd43dSSascha Wildner dynamically downsize 'tableLog' when conditions are met.
133*a28cd43dSSascha Wildner It saves CPU time, by using smaller tables, while preserving or even improving compression ratio.
134*a28cd43dSSascha Wildner @return : recommended tableLog (necessarily <= 'maxTableLog') */
135*a28cd43dSSascha Wildner FSE_PUBLIC_API unsigned FSE_optimalTableLog(unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue);
136*a28cd43dSSascha Wildner
137*a28cd43dSSascha Wildner /*! FSE_normalizeCount():
138*a28cd43dSSascha Wildner normalize counts so that sum(count[]) == Power_of_2 (2^tableLog)
139*a28cd43dSSascha Wildner 'normalizedCounter' is a table of short, of minimum size (maxSymbolValue+1).
140*a28cd43dSSascha Wildner useLowProbCount is a boolean parameter which trades off compressed size for
141*a28cd43dSSascha Wildner faster header decoding. When it is set to 1, the compressed data will be slightly
142*a28cd43dSSascha Wildner smaller. And when it is set to 0, FSE_readNCount() and FSE_buildDTable() will be
143*a28cd43dSSascha Wildner faster. If you are compressing a small amount of data (< 2 KB) then useLowProbCount=0
144*a28cd43dSSascha Wildner is a good default, since header deserialization makes a big speed difference.
145*a28cd43dSSascha Wildner Otherwise, useLowProbCount=1 is a good default, since the speed difference is small.
146*a28cd43dSSascha Wildner @return : tableLog,
147*a28cd43dSSascha Wildner or an errorCode, which can be tested using FSE_isError() */
148*a28cd43dSSascha Wildner FSE_PUBLIC_API size_t FSE_normalizeCount(short* normalizedCounter, unsigned tableLog,
149*a28cd43dSSascha Wildner const unsigned* count, size_t srcSize, unsigned maxSymbolValue, unsigned useLowProbCount);
150*a28cd43dSSascha Wildner
151*a28cd43dSSascha Wildner /*! FSE_NCountWriteBound():
152*a28cd43dSSascha Wildner Provides the maximum possible size of an FSE normalized table, given 'maxSymbolValue' and 'tableLog'.
153*a28cd43dSSascha Wildner Typically useful for allocation purpose. */
154*a28cd43dSSascha Wildner FSE_PUBLIC_API size_t FSE_NCountWriteBound(unsigned maxSymbolValue, unsigned tableLog);
155*a28cd43dSSascha Wildner
156*a28cd43dSSascha Wildner /*! FSE_writeNCount():
157*a28cd43dSSascha Wildner Compactly save 'normalizedCounter' into 'buffer'.
158*a28cd43dSSascha Wildner @return : size of the compressed table,
159*a28cd43dSSascha Wildner or an errorCode, which can be tested using FSE_isError(). */
160*a28cd43dSSascha Wildner FSE_PUBLIC_API size_t FSE_writeNCount (void* buffer, size_t bufferSize,
161*a28cd43dSSascha Wildner const short* normalizedCounter,
162*a28cd43dSSascha Wildner unsigned maxSymbolValue, unsigned tableLog);
163*a28cd43dSSascha Wildner
164*a28cd43dSSascha Wildner /*! Constructor and Destructor of FSE_CTable.
165*a28cd43dSSascha Wildner Note that FSE_CTable size depends on 'tableLog' and 'maxSymbolValue' */
166*a28cd43dSSascha Wildner typedef unsigned FSE_CTable; /* don't allocate that. It's only meant to be more restrictive than void* */
167*a28cd43dSSascha Wildner FSE_PUBLIC_API FSE_CTable* FSE_createCTable (unsigned maxSymbolValue, unsigned tableLog);
168*a28cd43dSSascha Wildner FSE_PUBLIC_API void FSE_freeCTable (FSE_CTable* ct);
169*a28cd43dSSascha Wildner
170*a28cd43dSSascha Wildner /*! FSE_buildCTable():
171*a28cd43dSSascha Wildner Builds `ct`, which must be already allocated, using FSE_createCTable().
172*a28cd43dSSascha Wildner @return : 0, or an errorCode, which can be tested using FSE_isError() */
173*a28cd43dSSascha Wildner FSE_PUBLIC_API size_t FSE_buildCTable(FSE_CTable* ct, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog);
174*a28cd43dSSascha Wildner
175*a28cd43dSSascha Wildner /*! FSE_compress_usingCTable():
176*a28cd43dSSascha Wildner Compress `src` using `ct` into `dst` which must be already allocated.
177*a28cd43dSSascha Wildner @return : size of compressed data (<= `dstCapacity`),
178*a28cd43dSSascha Wildner or 0 if compressed data could not fit into `dst`,
179*a28cd43dSSascha Wildner or an errorCode, which can be tested using FSE_isError() */
180*a28cd43dSSascha Wildner FSE_PUBLIC_API size_t FSE_compress_usingCTable (void* dst, size_t dstCapacity, const void* src, size_t srcSize, const FSE_CTable* ct);
181*a28cd43dSSascha Wildner
182*a28cd43dSSascha Wildner /*!
183*a28cd43dSSascha Wildner Tutorial :
184*a28cd43dSSascha Wildner ----------
185*a28cd43dSSascha Wildner The first step is to count all symbols. FSE_count() does this job very fast.
186*a28cd43dSSascha Wildner Result will be saved into 'count', a table of unsigned int, which must be already allocated, and have 'maxSymbolValuePtr[0]+1' cells.
187*a28cd43dSSascha Wildner 'src' is a table of bytes of size 'srcSize'. All values within 'src' MUST be <= maxSymbolValuePtr[0]
188*a28cd43dSSascha Wildner maxSymbolValuePtr[0] will be updated, with its real value (necessarily <= original value)
189*a28cd43dSSascha Wildner FSE_count() will return the number of occurrence of the most frequent symbol.
190*a28cd43dSSascha Wildner This can be used to know if there is a single symbol within 'src', and to quickly evaluate its compressibility.
191*a28cd43dSSascha Wildner If there is an error, the function will return an ErrorCode (which can be tested using FSE_isError()).
192*a28cd43dSSascha Wildner
193*a28cd43dSSascha Wildner The next step is to normalize the frequencies.
194*a28cd43dSSascha Wildner FSE_normalizeCount() will ensure that sum of frequencies is == 2 ^'tableLog'.
195*a28cd43dSSascha Wildner It also guarantees a minimum of 1 to any Symbol with frequency >= 1.
196*a28cd43dSSascha Wildner You can use 'tableLog'==0 to mean "use default tableLog value".
197*a28cd43dSSascha Wildner If you are unsure of which tableLog value to use, you can ask FSE_optimalTableLog(),
198*a28cd43dSSascha Wildner which will provide the optimal valid tableLog given sourceSize, maxSymbolValue, and a user-defined maximum (0 means "default").
199*a28cd43dSSascha Wildner
200*a28cd43dSSascha Wildner The result of FSE_normalizeCount() will be saved into a table,
201*a28cd43dSSascha Wildner called 'normalizedCounter', which is a table of signed short.
202*a28cd43dSSascha Wildner 'normalizedCounter' must be already allocated, and have at least 'maxSymbolValue+1' cells.
203*a28cd43dSSascha Wildner The return value is tableLog if everything proceeded as expected.
204*a28cd43dSSascha Wildner It is 0 if there is a single symbol within distribution.
205*a28cd43dSSascha Wildner If there is an error (ex: invalid tableLog value), the function will return an ErrorCode (which can be tested using FSE_isError()).
206*a28cd43dSSascha Wildner
207*a28cd43dSSascha Wildner 'normalizedCounter' can be saved in a compact manner to a memory area using FSE_writeNCount().
208*a28cd43dSSascha Wildner 'buffer' must be already allocated.
209*a28cd43dSSascha Wildner For guaranteed success, buffer size must be at least FSE_headerBound().
210*a28cd43dSSascha Wildner The result of the function is the number of bytes written into 'buffer'.
211*a28cd43dSSascha Wildner If there is an error, the function will return an ErrorCode (which can be tested using FSE_isError(); ex : buffer size too small).
212*a28cd43dSSascha Wildner
213*a28cd43dSSascha Wildner 'normalizedCounter' can then be used to create the compression table 'CTable'.
214*a28cd43dSSascha Wildner The space required by 'CTable' must be already allocated, using FSE_createCTable().
215*a28cd43dSSascha Wildner You can then use FSE_buildCTable() to fill 'CTable'.
216*a28cd43dSSascha Wildner If there is an error, both functions will return an ErrorCode (which can be tested using FSE_isError()).
217*a28cd43dSSascha Wildner
218*a28cd43dSSascha Wildner 'CTable' can then be used to compress 'src', with FSE_compress_usingCTable().
219*a28cd43dSSascha Wildner Similar to FSE_count(), the convention is that 'src' is assumed to be a table of char of size 'srcSize'
220*a28cd43dSSascha Wildner The function returns the size of compressed data (without header), necessarily <= `dstCapacity`.
221*a28cd43dSSascha Wildner If it returns '0', compressed data could not fit into 'dst'.
222*a28cd43dSSascha Wildner If there is an error, the function will return an ErrorCode (which can be tested using FSE_isError()).
223*a28cd43dSSascha Wildner */
224*a28cd43dSSascha Wildner
225*a28cd43dSSascha Wildner
226*a28cd43dSSascha Wildner /* *** DECOMPRESSION *** */
227*a28cd43dSSascha Wildner
228*a28cd43dSSascha Wildner /*! FSE_readNCount():
229*a28cd43dSSascha Wildner Read compactly saved 'normalizedCounter' from 'rBuffer'.
230*a28cd43dSSascha Wildner @return : size read from 'rBuffer',
231*a28cd43dSSascha Wildner or an errorCode, which can be tested using FSE_isError().
232*a28cd43dSSascha Wildner maxSymbolValuePtr[0] and tableLogPtr[0] will also be updated with their respective values */
233*a28cd43dSSascha Wildner FSE_PUBLIC_API size_t FSE_readNCount (short* normalizedCounter,
234*a28cd43dSSascha Wildner unsigned* maxSymbolValuePtr, unsigned* tableLogPtr,
235*a28cd43dSSascha Wildner const void* rBuffer, size_t rBuffSize);
236*a28cd43dSSascha Wildner
237*a28cd43dSSascha Wildner /*! FSE_readNCount_bmi2():
238*a28cd43dSSascha Wildner * Same as FSE_readNCount() but pass bmi2=1 when your CPU supports BMI2 and 0 otherwise.
239*a28cd43dSSascha Wildner */
240*a28cd43dSSascha Wildner FSE_PUBLIC_API size_t FSE_readNCount_bmi2(short* normalizedCounter,
241*a28cd43dSSascha Wildner unsigned* maxSymbolValuePtr, unsigned* tableLogPtr,
242*a28cd43dSSascha Wildner const void* rBuffer, size_t rBuffSize, int bmi2);
243*a28cd43dSSascha Wildner
244*a28cd43dSSascha Wildner /*! Constructor and Destructor of FSE_DTable.
245*a28cd43dSSascha Wildner Note that its size depends on 'tableLog' */
246*a28cd43dSSascha Wildner typedef unsigned FSE_DTable; /* don't allocate that. It's just a way to be more restrictive than void* */
247*a28cd43dSSascha Wildner FSE_PUBLIC_API FSE_DTable* FSE_createDTable(unsigned tableLog);
248*a28cd43dSSascha Wildner FSE_PUBLIC_API void FSE_freeDTable(FSE_DTable* dt);
249*a28cd43dSSascha Wildner
250*a28cd43dSSascha Wildner /*! FSE_buildDTable():
251*a28cd43dSSascha Wildner Builds 'dt', which must be already allocated, using FSE_createDTable().
252*a28cd43dSSascha Wildner return : 0, or an errorCode, which can be tested using FSE_isError() */
253*a28cd43dSSascha Wildner FSE_PUBLIC_API size_t FSE_buildDTable (FSE_DTable* dt, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog);
254*a28cd43dSSascha Wildner
255*a28cd43dSSascha Wildner /*! FSE_decompress_usingDTable():
256*a28cd43dSSascha Wildner Decompress compressed source `cSrc` of size `cSrcSize` using `dt`
257*a28cd43dSSascha Wildner into `dst` which must be already allocated.
258*a28cd43dSSascha Wildner @return : size of regenerated data (necessarily <= `dstCapacity`),
259*a28cd43dSSascha Wildner or an errorCode, which can be tested using FSE_isError() */
260*a28cd43dSSascha Wildner FSE_PUBLIC_API size_t FSE_decompress_usingDTable(void* dst, size_t dstCapacity, const void* cSrc, size_t cSrcSize, const FSE_DTable* dt);
261*a28cd43dSSascha Wildner
262*a28cd43dSSascha Wildner /*!
263*a28cd43dSSascha Wildner Tutorial :
264*a28cd43dSSascha Wildner ----------
265*a28cd43dSSascha Wildner (Note : these functions only decompress FSE-compressed blocks.
266*a28cd43dSSascha Wildner If block is uncompressed, use memcpy() instead
267*a28cd43dSSascha Wildner If block is a single repeated byte, use memset() instead )
268*a28cd43dSSascha Wildner
269*a28cd43dSSascha Wildner The first step is to obtain the normalized frequencies of symbols.
270*a28cd43dSSascha Wildner This can be performed by FSE_readNCount() if it was saved using FSE_writeNCount().
271*a28cd43dSSascha Wildner 'normalizedCounter' must be already allocated, and have at least 'maxSymbolValuePtr[0]+1' cells of signed short.
272*a28cd43dSSascha Wildner In practice, that means it's necessary to know 'maxSymbolValue' beforehand,
273*a28cd43dSSascha Wildner or size the table to handle worst case situations (typically 256).
274*a28cd43dSSascha Wildner FSE_readNCount() will provide 'tableLog' and 'maxSymbolValue'.
275*a28cd43dSSascha Wildner The result of FSE_readNCount() is the number of bytes read from 'rBuffer'.
276*a28cd43dSSascha Wildner Note that 'rBufferSize' must be at least 4 bytes, even if useful information is less than that.
277*a28cd43dSSascha Wildner If there is an error, the function will return an error code, which can be tested using FSE_isError().
278*a28cd43dSSascha Wildner
279*a28cd43dSSascha Wildner The next step is to build the decompression tables 'FSE_DTable' from 'normalizedCounter'.
280*a28cd43dSSascha Wildner This is performed by the function FSE_buildDTable().
281*a28cd43dSSascha Wildner The space required by 'FSE_DTable' must be already allocated using FSE_createDTable().
282*a28cd43dSSascha Wildner If there is an error, the function will return an error code, which can be tested using FSE_isError().
283*a28cd43dSSascha Wildner
284*a28cd43dSSascha Wildner `FSE_DTable` can then be used to decompress `cSrc`, with FSE_decompress_usingDTable().
285*a28cd43dSSascha Wildner `cSrcSize` must be strictly correct, otherwise decompression will fail.
286*a28cd43dSSascha Wildner FSE_decompress_usingDTable() result will tell how many bytes were regenerated (<=`dstCapacity`).
287*a28cd43dSSascha Wildner If there is an error, the function will return an error code, which can be tested using FSE_isError(). (ex: dst buffer too small)
288*a28cd43dSSascha Wildner */
289*a28cd43dSSascha Wildner
290*a28cd43dSSascha Wildner #endif /* FSE_H */
291*a28cd43dSSascha Wildner
292*a28cd43dSSascha Wildner #if defined(FSE_STATIC_LINKING_ONLY) && !defined(FSE_H_FSE_STATIC_LINKING_ONLY)
293*a28cd43dSSascha Wildner #define FSE_H_FSE_STATIC_LINKING_ONLY
294*a28cd43dSSascha Wildner
295*a28cd43dSSascha Wildner /* *** Dependency *** */
296*a28cd43dSSascha Wildner #include "bitstream.h"
297*a28cd43dSSascha Wildner
298*a28cd43dSSascha Wildner
299*a28cd43dSSascha Wildner /* *****************************************
300*a28cd43dSSascha Wildner * Static allocation
301*a28cd43dSSascha Wildner *******************************************/
302*a28cd43dSSascha Wildner /* FSE buffer bounds */
303*a28cd43dSSascha Wildner #define FSE_NCOUNTBOUND 512
304*a28cd43dSSascha Wildner #define FSE_BLOCKBOUND(size) ((size) + ((size)>>7) + 4 /* fse states */ + sizeof(size_t) /* bitContainer */)
305*a28cd43dSSascha Wildner #define FSE_COMPRESSBOUND(size) (FSE_NCOUNTBOUND + FSE_BLOCKBOUND(size)) /* Macro version, useful for static allocation */
306*a28cd43dSSascha Wildner
307*a28cd43dSSascha Wildner /* It is possible to statically allocate FSE CTable/DTable as a table of FSE_CTable/FSE_DTable using below macros */
308*a28cd43dSSascha Wildner #define FSE_CTABLE_SIZE_U32(maxTableLog, maxSymbolValue) (1 + (1<<((maxTableLog)-1)) + (((maxSymbolValue)+1)*2))
309*a28cd43dSSascha Wildner #define FSE_DTABLE_SIZE_U32(maxTableLog) (1 + (1<<(maxTableLog)))
310*a28cd43dSSascha Wildner
311*a28cd43dSSascha Wildner /* or use the size to malloc() space directly. Pay attention to alignment restrictions though */
312*a28cd43dSSascha Wildner #define FSE_CTABLE_SIZE(maxTableLog, maxSymbolValue) (FSE_CTABLE_SIZE_U32(maxTableLog, maxSymbolValue) * sizeof(FSE_CTable))
313*a28cd43dSSascha Wildner #define FSE_DTABLE_SIZE(maxTableLog) (FSE_DTABLE_SIZE_U32(maxTableLog) * sizeof(FSE_DTable))
314*a28cd43dSSascha Wildner
315*a28cd43dSSascha Wildner
316*a28cd43dSSascha Wildner /* *****************************************
317*a28cd43dSSascha Wildner * FSE advanced API
318*a28cd43dSSascha Wildner ***************************************** */
319*a28cd43dSSascha Wildner
320*a28cd43dSSascha Wildner unsigned FSE_optimalTableLog_internal(unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue, unsigned minus);
321*a28cd43dSSascha Wildner /**< same as FSE_optimalTableLog(), which used `minus==2` */
322*a28cd43dSSascha Wildner
323*a28cd43dSSascha Wildner /* FSE_compress_wksp() :
324*a28cd43dSSascha Wildner * Same as FSE_compress2(), but using an externally allocated scratch buffer (`workSpace`).
325*a28cd43dSSascha Wildner * FSE_COMPRESS_WKSP_SIZE_U32() provides the minimum size required for `workSpace` as a table of FSE_CTable.
326*a28cd43dSSascha Wildner */
327*a28cd43dSSascha Wildner #define FSE_COMPRESS_WKSP_SIZE_U32(maxTableLog, maxSymbolValue) ( FSE_CTABLE_SIZE_U32(maxTableLog, maxSymbolValue) + ((maxTableLog > 12) ? (1 << (maxTableLog - 2)) : 1024) )
328*a28cd43dSSascha Wildner 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);
329*a28cd43dSSascha Wildner
330*a28cd43dSSascha Wildner size_t FSE_buildCTable_raw (FSE_CTable* ct, unsigned nbBits);
331*a28cd43dSSascha Wildner /**< build a fake FSE_CTable, designed for a flat distribution, where each symbol uses nbBits */
332*a28cd43dSSascha Wildner
333*a28cd43dSSascha Wildner size_t FSE_buildCTable_rle (FSE_CTable* ct, unsigned char symbolValue);
334*a28cd43dSSascha Wildner /**< build a fake FSE_CTable, designed to compress always the same symbolValue */
335*a28cd43dSSascha Wildner
336*a28cd43dSSascha Wildner /* FSE_buildCTable_wksp() :
337*a28cd43dSSascha Wildner * Same as FSE_buildCTable(), but using an externally allocated scratch buffer (`workSpace`).
338*a28cd43dSSascha Wildner * `wkspSize` must be >= `FSE_BUILD_CTABLE_WORKSPACE_SIZE_U32(maxSymbolValue, tableLog)` of `unsigned`.
339*a28cd43dSSascha Wildner */
340*a28cd43dSSascha Wildner #define FSE_BUILD_CTABLE_WORKSPACE_SIZE_U32(maxSymbolValue, tableLog) (maxSymbolValue + 2 + (1ull << (tableLog - 2)))
341*a28cd43dSSascha Wildner #define FSE_BUILD_CTABLE_WORKSPACE_SIZE(maxSymbolValue, tableLog) (sizeof(unsigned) * FSE_BUILD_CTABLE_WORKSPACE_SIZE_U32(maxSymbolValue, tableLog))
342*a28cd43dSSascha Wildner size_t FSE_buildCTable_wksp(FSE_CTable* ct, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog, void* workSpace, size_t wkspSize);
343*a28cd43dSSascha Wildner
344*a28cd43dSSascha Wildner #define FSE_BUILD_DTABLE_WKSP_SIZE(maxTableLog, maxSymbolValue) (sizeof(short) * (maxSymbolValue + 1) + (1ULL << maxTableLog) + 8)
345*a28cd43dSSascha Wildner #define FSE_BUILD_DTABLE_WKSP_SIZE_U32(maxTableLog, maxSymbolValue) ((FSE_BUILD_DTABLE_WKSP_SIZE(maxTableLog, maxSymbolValue) + sizeof(unsigned) - 1) / sizeof(unsigned))
346*a28cd43dSSascha Wildner FSE_PUBLIC_API size_t FSE_buildDTable_wksp(FSE_DTable* dt, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog, void* workSpace, size_t wkspSize);
347*a28cd43dSSascha Wildner /**< Same as FSE_buildDTable(), using an externally allocated `workspace` produced with `FSE_BUILD_DTABLE_WKSP_SIZE_U32(maxSymbolValue)` */
348*a28cd43dSSascha Wildner
349*a28cd43dSSascha Wildner size_t FSE_buildDTable_raw (FSE_DTable* dt, unsigned nbBits);
350*a28cd43dSSascha Wildner /**< build a fake FSE_DTable, designed to read a flat distribution where each symbol uses nbBits */
351*a28cd43dSSascha Wildner
352*a28cd43dSSascha Wildner size_t FSE_buildDTable_rle (FSE_DTable* dt, unsigned char symbolValue);
353*a28cd43dSSascha Wildner /**< build a fake FSE_DTable, designed to always generate the same symbolValue */
354*a28cd43dSSascha Wildner
355*a28cd43dSSascha Wildner #define FSE_DECOMPRESS_WKSP_SIZE_U32(maxTableLog, maxSymbolValue) (FSE_DTABLE_SIZE_U32(maxTableLog) + FSE_BUILD_DTABLE_WKSP_SIZE_U32(maxTableLog, maxSymbolValue))
356*a28cd43dSSascha Wildner #define FSE_DECOMPRESS_WKSP_SIZE(maxTableLog, maxSymbolValue) (FSE_DECOMPRESS_WKSP_SIZE_U32(maxTableLog, maxSymbolValue) * sizeof(unsigned))
357*a28cd43dSSascha Wildner size_t FSE_decompress_wksp(void* dst, size_t dstCapacity, const void* cSrc, size_t cSrcSize, unsigned maxLog, void* workSpace, size_t wkspSize);
358*a28cd43dSSascha Wildner /**< same as FSE_decompress(), using an externally allocated `workSpace` produced with `FSE_DECOMPRESS_WKSP_SIZE_U32(maxLog, maxSymbolValue)` */
359*a28cd43dSSascha Wildner
360*a28cd43dSSascha Wildner size_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);
361*a28cd43dSSascha Wildner /**< Same as FSE_decompress_wksp() but with dynamic BMI2 support. Pass 1 if your CPU supports BMI2 or 0 if it doesn't. */
362*a28cd43dSSascha Wildner
363*a28cd43dSSascha Wildner typedef enum {
364*a28cd43dSSascha Wildner FSE_repeat_none, /**< Cannot use the previous table */
365*a28cd43dSSascha Wildner FSE_repeat_check, /**< Can use the previous table but it must be checked */
366*a28cd43dSSascha Wildner FSE_repeat_valid /**< Can use the previous table and it is assumed to be valid */
367*a28cd43dSSascha Wildner } FSE_repeat;
368*a28cd43dSSascha Wildner
369*a28cd43dSSascha Wildner /* *****************************************
370*a28cd43dSSascha Wildner * FSE symbol compression API
371*a28cd43dSSascha Wildner *******************************************/
372*a28cd43dSSascha Wildner /*!
373*a28cd43dSSascha Wildner This API consists of small unitary functions, which highly benefit from being inlined.
374*a28cd43dSSascha Wildner Hence their body are included in next section.
375*a28cd43dSSascha Wildner */
376*a28cd43dSSascha Wildner typedef struct {
377*a28cd43dSSascha Wildner ptrdiff_t value;
378*a28cd43dSSascha Wildner const void* stateTable;
379*a28cd43dSSascha Wildner const void* symbolTT;
380*a28cd43dSSascha Wildner unsigned stateLog;
381*a28cd43dSSascha Wildner } FSE_CState_t;
382*a28cd43dSSascha Wildner
383*a28cd43dSSascha Wildner static void FSE_initCState(FSE_CState_t* CStatePtr, const FSE_CTable* ct);
384*a28cd43dSSascha Wildner
385*a28cd43dSSascha Wildner static void FSE_encodeSymbol(BIT_CStream_t* bitC, FSE_CState_t* CStatePtr, unsigned symbol);
386*a28cd43dSSascha Wildner
387*a28cd43dSSascha Wildner static void FSE_flushCState(BIT_CStream_t* bitC, const FSE_CState_t* CStatePtr);
388*a28cd43dSSascha Wildner
389*a28cd43dSSascha Wildner /**<
390*a28cd43dSSascha Wildner These functions are inner components of FSE_compress_usingCTable().
391*a28cd43dSSascha Wildner They allow the creation of custom streams, mixing multiple tables and bit sources.
392*a28cd43dSSascha Wildner
393*a28cd43dSSascha Wildner A key property to keep in mind is that encoding and decoding are done **in reverse direction**.
394*a28cd43dSSascha Wildner So the first symbol you will encode is the last you will decode, like a LIFO stack.
395*a28cd43dSSascha Wildner
396*a28cd43dSSascha Wildner You will need a few variables to track your CStream. They are :
397*a28cd43dSSascha Wildner
398*a28cd43dSSascha Wildner FSE_CTable ct; // Provided by FSE_buildCTable()
399*a28cd43dSSascha Wildner BIT_CStream_t bitStream; // bitStream tracking structure
400*a28cd43dSSascha Wildner FSE_CState_t state; // State tracking structure (can have several)
401*a28cd43dSSascha Wildner
402*a28cd43dSSascha Wildner
403*a28cd43dSSascha Wildner The first thing to do is to init bitStream and state.
404*a28cd43dSSascha Wildner size_t errorCode = BIT_initCStream(&bitStream, dstBuffer, maxDstSize);
405*a28cd43dSSascha Wildner FSE_initCState(&state, ct);
406*a28cd43dSSascha Wildner
407*a28cd43dSSascha Wildner Note that BIT_initCStream() can produce an error code, so its result should be tested, using FSE_isError();
408*a28cd43dSSascha Wildner You can then encode your input data, byte after byte.
409*a28cd43dSSascha Wildner FSE_encodeSymbol() outputs a maximum of 'tableLog' bits at a time.
410*a28cd43dSSascha Wildner Remember decoding will be done in reverse direction.
411*a28cd43dSSascha Wildner FSE_encodeByte(&bitStream, &state, symbol);
412*a28cd43dSSascha Wildner
413*a28cd43dSSascha Wildner At any time, you can also add any bit sequence.
414*a28cd43dSSascha Wildner Note : maximum allowed nbBits is 25, for compatibility with 32-bits decoders
415*a28cd43dSSascha Wildner BIT_addBits(&bitStream, bitField, nbBits);
416*a28cd43dSSascha Wildner
417*a28cd43dSSascha Wildner The above methods don't commit data to memory, they just store it into local register, for speed.
418*a28cd43dSSascha Wildner Local register size is 64-bits on 64-bits systems, 32-bits on 32-bits systems (size_t).
419*a28cd43dSSascha Wildner Writing data to memory is a manual operation, performed by the flushBits function.
420*a28cd43dSSascha Wildner BIT_flushBits(&bitStream);
421*a28cd43dSSascha Wildner
422*a28cd43dSSascha Wildner Your last FSE encoding operation shall be to flush your last state value(s).
423*a28cd43dSSascha Wildner FSE_flushState(&bitStream, &state);
424*a28cd43dSSascha Wildner
425*a28cd43dSSascha Wildner Finally, you must close the bitStream.
426*a28cd43dSSascha Wildner The function returns the size of CStream in bytes.
427*a28cd43dSSascha Wildner If data couldn't fit into dstBuffer, it will return a 0 ( == not compressible)
428*a28cd43dSSascha Wildner If there is an error, it returns an errorCode (which can be tested using FSE_isError()).
429*a28cd43dSSascha Wildner size_t size = BIT_closeCStream(&bitStream);
430*a28cd43dSSascha Wildner */
431*a28cd43dSSascha Wildner
432*a28cd43dSSascha Wildner
433*a28cd43dSSascha Wildner /* *****************************************
434*a28cd43dSSascha Wildner * FSE symbol decompression API
435*a28cd43dSSascha Wildner *******************************************/
436*a28cd43dSSascha Wildner typedef struct {
437*a28cd43dSSascha Wildner size_t state;
438*a28cd43dSSascha Wildner const void* table; /* precise table may vary, depending on U16 */
439*a28cd43dSSascha Wildner } FSE_DState_t;
440*a28cd43dSSascha Wildner
441*a28cd43dSSascha Wildner
442*a28cd43dSSascha Wildner static void FSE_initDState(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD, const FSE_DTable* dt);
443*a28cd43dSSascha Wildner
444*a28cd43dSSascha Wildner static unsigned char FSE_decodeSymbol(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD);
445*a28cd43dSSascha Wildner
446*a28cd43dSSascha Wildner static unsigned FSE_endOfDState(const FSE_DState_t* DStatePtr);
447*a28cd43dSSascha Wildner
448*a28cd43dSSascha Wildner /**<
449*a28cd43dSSascha Wildner Let's now decompose FSE_decompress_usingDTable() into its unitary components.
450*a28cd43dSSascha Wildner You will decode FSE-encoded symbols from the bitStream,
451*a28cd43dSSascha Wildner and also any other bitFields you put in, **in reverse order**.
452*a28cd43dSSascha Wildner
453*a28cd43dSSascha Wildner You will need a few variables to track your bitStream. They are :
454*a28cd43dSSascha Wildner
455*a28cd43dSSascha Wildner BIT_DStream_t DStream; // Stream context
456*a28cd43dSSascha Wildner FSE_DState_t DState; // State context. Multiple ones are possible
457*a28cd43dSSascha Wildner FSE_DTable* DTablePtr; // Decoding table, provided by FSE_buildDTable()
458*a28cd43dSSascha Wildner
459*a28cd43dSSascha Wildner The first thing to do is to init the bitStream.
460*a28cd43dSSascha Wildner errorCode = BIT_initDStream(&DStream, srcBuffer, srcSize);
461*a28cd43dSSascha Wildner
462*a28cd43dSSascha Wildner You should then retrieve your initial state(s)
463*a28cd43dSSascha Wildner (in reverse flushing order if you have several ones) :
464*a28cd43dSSascha Wildner errorCode = FSE_initDState(&DState, &DStream, DTablePtr);
465*a28cd43dSSascha Wildner
466*a28cd43dSSascha Wildner You can then decode your data, symbol after symbol.
467*a28cd43dSSascha Wildner For information the maximum number of bits read by FSE_decodeSymbol() is 'tableLog'.
468*a28cd43dSSascha Wildner Keep in mind that symbols are decoded in reverse order, like a LIFO stack (last in, first out).
469*a28cd43dSSascha Wildner unsigned char symbol = FSE_decodeSymbol(&DState, &DStream);
470*a28cd43dSSascha Wildner
471*a28cd43dSSascha Wildner You can retrieve any bitfield you eventually stored into the bitStream (in reverse order)
472*a28cd43dSSascha Wildner Note : maximum allowed nbBits is 25, for 32-bits compatibility
473*a28cd43dSSascha Wildner size_t bitField = BIT_readBits(&DStream, nbBits);
474*a28cd43dSSascha Wildner
475*a28cd43dSSascha Wildner All above operations only read from local register (which size depends on size_t).
476*a28cd43dSSascha Wildner Refueling the register from memory is manually performed by the reload method.
477*a28cd43dSSascha Wildner endSignal = FSE_reloadDStream(&DStream);
478*a28cd43dSSascha Wildner
479*a28cd43dSSascha Wildner BIT_reloadDStream() result tells if there is still some more data to read from DStream.
480*a28cd43dSSascha Wildner BIT_DStream_unfinished : there is still some data left into the DStream.
481*a28cd43dSSascha Wildner BIT_DStream_endOfBuffer : Dstream reached end of buffer. Its container may no longer be completely filled.
482*a28cd43dSSascha Wildner BIT_DStream_completed : Dstream reached its exact end, corresponding in general to decompression completed.
483*a28cd43dSSascha Wildner BIT_DStream_tooFar : Dstream went too far. Decompression result is corrupted.
484*a28cd43dSSascha Wildner
485*a28cd43dSSascha Wildner When reaching end of buffer (BIT_DStream_endOfBuffer), progress slowly, notably if you decode multiple symbols per loop,
486*a28cd43dSSascha Wildner to properly detect the exact end of stream.
487*a28cd43dSSascha Wildner After each decoded symbol, check if DStream is fully consumed using this simple test :
488*a28cd43dSSascha Wildner BIT_reloadDStream(&DStream) >= BIT_DStream_completed
489*a28cd43dSSascha Wildner
490*a28cd43dSSascha Wildner When it's done, verify decompression is fully completed, by checking both DStream and the relevant states.
491*a28cd43dSSascha Wildner Checking if DStream has reached its end is performed by :
492*a28cd43dSSascha Wildner BIT_endOfDStream(&DStream);
493*a28cd43dSSascha Wildner Check also the states. There might be some symbols left there, if some high probability ones (>50%) are possible.
494*a28cd43dSSascha Wildner FSE_endOfDState(&DState);
495*a28cd43dSSascha Wildner */
496*a28cd43dSSascha Wildner
497*a28cd43dSSascha Wildner
498*a28cd43dSSascha Wildner /* *****************************************
499*a28cd43dSSascha Wildner * FSE unsafe API
500*a28cd43dSSascha Wildner *******************************************/
501*a28cd43dSSascha Wildner static unsigned char FSE_decodeSymbolFast(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD);
502*a28cd43dSSascha Wildner /* faster, but works only if nbBits is always >= 1 (otherwise, result will be corrupted) */
503*a28cd43dSSascha Wildner
504*a28cd43dSSascha Wildner
505*a28cd43dSSascha Wildner /* *****************************************
506*a28cd43dSSascha Wildner * Implementation of inlined functions
507*a28cd43dSSascha Wildner *******************************************/
508*a28cd43dSSascha Wildner typedef struct {
509*a28cd43dSSascha Wildner int deltaFindState;
510*a28cd43dSSascha Wildner U32 deltaNbBits;
511*a28cd43dSSascha Wildner } FSE_symbolCompressionTransform; /* total 8 bytes */
512*a28cd43dSSascha Wildner
FSE_initCState(FSE_CState_t * statePtr,const FSE_CTable * ct)513*a28cd43dSSascha Wildner MEM_STATIC void FSE_initCState(FSE_CState_t* statePtr, const FSE_CTable* ct)
514*a28cd43dSSascha Wildner {
515*a28cd43dSSascha Wildner const void* ptr = ct;
516*a28cd43dSSascha Wildner const U16* u16ptr = (const U16*) ptr;
517*a28cd43dSSascha Wildner const U32 tableLog = MEM_read16(ptr);
518*a28cd43dSSascha Wildner statePtr->value = (ptrdiff_t)1<<tableLog;
519*a28cd43dSSascha Wildner statePtr->stateTable = u16ptr+2;
520*a28cd43dSSascha Wildner statePtr->symbolTT = ct + 1 + (tableLog ? (1<<(tableLog-1)) : 1);
521*a28cd43dSSascha Wildner statePtr->stateLog = tableLog;
522*a28cd43dSSascha Wildner }
523*a28cd43dSSascha Wildner
524*a28cd43dSSascha Wildner
525*a28cd43dSSascha Wildner /*! FSE_initCState2() :
526*a28cd43dSSascha Wildner * Same as FSE_initCState(), but the first symbol to include (which will be the last to be read)
527*a28cd43dSSascha Wildner * uses the smallest state value possible, saving the cost of this symbol */
FSE_initCState2(FSE_CState_t * statePtr,const FSE_CTable * ct,U32 symbol)528*a28cd43dSSascha Wildner MEM_STATIC void FSE_initCState2(FSE_CState_t* statePtr, const FSE_CTable* ct, U32 symbol)
529*a28cd43dSSascha Wildner {
530*a28cd43dSSascha Wildner FSE_initCState(statePtr, ct);
531*a28cd43dSSascha Wildner { const FSE_symbolCompressionTransform symbolTT = ((const FSE_symbolCompressionTransform*)(statePtr->symbolTT))[symbol];
532*a28cd43dSSascha Wildner const U16* stateTable = (const U16*)(statePtr->stateTable);
533*a28cd43dSSascha Wildner U32 nbBitsOut = (U32)((symbolTT.deltaNbBits + (1<<15)) >> 16);
534*a28cd43dSSascha Wildner statePtr->value = (nbBitsOut << 16) - symbolTT.deltaNbBits;
535*a28cd43dSSascha Wildner statePtr->value = stateTable[(statePtr->value >> nbBitsOut) + symbolTT.deltaFindState];
536*a28cd43dSSascha Wildner }
537*a28cd43dSSascha Wildner }
538*a28cd43dSSascha Wildner
FSE_encodeSymbol(BIT_CStream_t * bitC,FSE_CState_t * statePtr,unsigned symbol)539*a28cd43dSSascha Wildner MEM_STATIC void FSE_encodeSymbol(BIT_CStream_t* bitC, FSE_CState_t* statePtr, unsigned symbol)
540*a28cd43dSSascha Wildner {
541*a28cd43dSSascha Wildner FSE_symbolCompressionTransform const symbolTT = ((const FSE_symbolCompressionTransform*)(statePtr->symbolTT))[symbol];
542*a28cd43dSSascha Wildner const U16* const stateTable = (const U16*)(statePtr->stateTable);
543*a28cd43dSSascha Wildner U32 const nbBitsOut = (U32)((statePtr->value + symbolTT.deltaNbBits) >> 16);
544*a28cd43dSSascha Wildner BIT_addBits(bitC, statePtr->value, nbBitsOut);
545*a28cd43dSSascha Wildner statePtr->value = stateTable[ (statePtr->value >> nbBitsOut) + symbolTT.deltaFindState];
546*a28cd43dSSascha Wildner }
547*a28cd43dSSascha Wildner
FSE_flushCState(BIT_CStream_t * bitC,const FSE_CState_t * statePtr)548*a28cd43dSSascha Wildner MEM_STATIC void FSE_flushCState(BIT_CStream_t* bitC, const FSE_CState_t* statePtr)
549*a28cd43dSSascha Wildner {
550*a28cd43dSSascha Wildner BIT_addBits(bitC, statePtr->value, statePtr->stateLog);
551*a28cd43dSSascha Wildner BIT_flushBits(bitC);
552*a28cd43dSSascha Wildner }
553*a28cd43dSSascha Wildner
554*a28cd43dSSascha Wildner
555*a28cd43dSSascha Wildner /* FSE_getMaxNbBits() :
556*a28cd43dSSascha Wildner * Approximate maximum cost of a symbol, in bits.
557*a28cd43dSSascha Wildner * Fractional get rounded up (i.e : a symbol with a normalized frequency of 3 gives the same result as a frequency of 2)
558*a28cd43dSSascha Wildner * note 1 : assume symbolValue is valid (<= maxSymbolValue)
559*a28cd43dSSascha Wildner * note 2 : if freq[symbolValue]==0, @return a fake cost of tableLog+1 bits */
FSE_getMaxNbBits(const void * symbolTTPtr,U32 symbolValue)560*a28cd43dSSascha Wildner MEM_STATIC U32 FSE_getMaxNbBits(const void* symbolTTPtr, U32 symbolValue)
561*a28cd43dSSascha Wildner {
562*a28cd43dSSascha Wildner const FSE_symbolCompressionTransform* symbolTT = (const FSE_symbolCompressionTransform*) symbolTTPtr;
563*a28cd43dSSascha Wildner return (symbolTT[symbolValue].deltaNbBits + ((1<<16)-1)) >> 16;
564*a28cd43dSSascha Wildner }
565*a28cd43dSSascha Wildner
566*a28cd43dSSascha Wildner /* FSE_bitCost() :
567*a28cd43dSSascha Wildner * Approximate symbol cost, as fractional value, using fixed-point format (accuracyLog fractional bits)
568*a28cd43dSSascha Wildner * note 1 : assume symbolValue is valid (<= maxSymbolValue)
569*a28cd43dSSascha Wildner * note 2 : if freq[symbolValue]==0, @return a fake cost of tableLog+1 bits */
FSE_bitCost(const void * symbolTTPtr,U32 tableLog,U32 symbolValue,U32 accuracyLog)570*a28cd43dSSascha Wildner MEM_STATIC U32 FSE_bitCost(const void* symbolTTPtr, U32 tableLog, U32 symbolValue, U32 accuracyLog)
571*a28cd43dSSascha Wildner {
572*a28cd43dSSascha Wildner const FSE_symbolCompressionTransform* symbolTT = (const FSE_symbolCompressionTransform*) symbolTTPtr;
573*a28cd43dSSascha Wildner U32 const minNbBits = symbolTT[symbolValue].deltaNbBits >> 16;
574*a28cd43dSSascha Wildner U32 const threshold = (minNbBits+1) << 16;
575*a28cd43dSSascha Wildner assert(tableLog < 16);
576*a28cd43dSSascha Wildner assert(accuracyLog < 31-tableLog); /* ensure enough room for renormalization double shift */
577*a28cd43dSSascha Wildner { U32 const tableSize = 1 << tableLog;
578*a28cd43dSSascha Wildner U32 const deltaFromThreshold = threshold - (symbolTT[symbolValue].deltaNbBits + tableSize);
579*a28cd43dSSascha Wildner U32 const normalizedDeltaFromThreshold = (deltaFromThreshold << accuracyLog) >> tableLog; /* linear interpolation (very approximate) */
580*a28cd43dSSascha Wildner U32 const bitMultiplier = 1 << accuracyLog;
581*a28cd43dSSascha Wildner assert(symbolTT[symbolValue].deltaNbBits + tableSize <= threshold);
582*a28cd43dSSascha Wildner assert(normalizedDeltaFromThreshold <= bitMultiplier);
583*a28cd43dSSascha Wildner return (minNbBits+1)*bitMultiplier - normalizedDeltaFromThreshold;
584*a28cd43dSSascha Wildner }
585*a28cd43dSSascha Wildner }
586*a28cd43dSSascha Wildner
587*a28cd43dSSascha Wildner
588*a28cd43dSSascha Wildner /* ====== Decompression ====== */
589*a28cd43dSSascha Wildner
590*a28cd43dSSascha Wildner typedef struct {
591*a28cd43dSSascha Wildner U16 tableLog;
592*a28cd43dSSascha Wildner U16 fastMode;
593*a28cd43dSSascha Wildner } FSE_DTableHeader; /* sizeof U32 */
594*a28cd43dSSascha Wildner
595*a28cd43dSSascha Wildner typedef struct
596*a28cd43dSSascha Wildner {
597*a28cd43dSSascha Wildner unsigned short newState;
598*a28cd43dSSascha Wildner unsigned char symbol;
599*a28cd43dSSascha Wildner unsigned char nbBits;
600*a28cd43dSSascha Wildner } FSE_decode_t; /* size == U32 */
601*a28cd43dSSascha Wildner
FSE_initDState(FSE_DState_t * DStatePtr,BIT_DStream_t * bitD,const FSE_DTable * dt)602*a28cd43dSSascha Wildner MEM_STATIC void FSE_initDState(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD, const FSE_DTable* dt)
603*a28cd43dSSascha Wildner {
604*a28cd43dSSascha Wildner const void* ptr = dt;
605*a28cd43dSSascha Wildner const FSE_DTableHeader* const DTableH = (const FSE_DTableHeader*)ptr;
606*a28cd43dSSascha Wildner DStatePtr->state = BIT_readBits(bitD, DTableH->tableLog);
607*a28cd43dSSascha Wildner BIT_reloadDStream(bitD);
608*a28cd43dSSascha Wildner DStatePtr->table = dt + 1;
609*a28cd43dSSascha Wildner }
610*a28cd43dSSascha Wildner
FSE_peekSymbol(const FSE_DState_t * DStatePtr)611*a28cd43dSSascha Wildner MEM_STATIC BYTE FSE_peekSymbol(const FSE_DState_t* DStatePtr)
612*a28cd43dSSascha Wildner {
613*a28cd43dSSascha Wildner FSE_decode_t const DInfo = ((const FSE_decode_t*)(DStatePtr->table))[DStatePtr->state];
614*a28cd43dSSascha Wildner return DInfo.symbol;
615*a28cd43dSSascha Wildner }
616*a28cd43dSSascha Wildner
FSE_updateState(FSE_DState_t * DStatePtr,BIT_DStream_t * bitD)617*a28cd43dSSascha Wildner MEM_STATIC void FSE_updateState(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD)
618*a28cd43dSSascha Wildner {
619*a28cd43dSSascha Wildner FSE_decode_t const DInfo = ((const FSE_decode_t*)(DStatePtr->table))[DStatePtr->state];
620*a28cd43dSSascha Wildner U32 const nbBits = DInfo.nbBits;
621*a28cd43dSSascha Wildner size_t const lowBits = BIT_readBits(bitD, nbBits);
622*a28cd43dSSascha Wildner DStatePtr->state = DInfo.newState + lowBits;
623*a28cd43dSSascha Wildner }
624*a28cd43dSSascha Wildner
FSE_decodeSymbol(FSE_DState_t * DStatePtr,BIT_DStream_t * bitD)625*a28cd43dSSascha Wildner MEM_STATIC BYTE FSE_decodeSymbol(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD)
626*a28cd43dSSascha Wildner {
627*a28cd43dSSascha Wildner FSE_decode_t const DInfo = ((const FSE_decode_t*)(DStatePtr->table))[DStatePtr->state];
628*a28cd43dSSascha Wildner U32 const nbBits = DInfo.nbBits;
629*a28cd43dSSascha Wildner BYTE const symbol = DInfo.symbol;
630*a28cd43dSSascha Wildner size_t const lowBits = BIT_readBits(bitD, nbBits);
631*a28cd43dSSascha Wildner
632*a28cd43dSSascha Wildner DStatePtr->state = DInfo.newState + lowBits;
633*a28cd43dSSascha Wildner return symbol;
634*a28cd43dSSascha Wildner }
635*a28cd43dSSascha Wildner
636*a28cd43dSSascha Wildner /*! FSE_decodeSymbolFast() :
637*a28cd43dSSascha Wildner unsafe, only works if no symbol has a probability > 50% */
FSE_decodeSymbolFast(FSE_DState_t * DStatePtr,BIT_DStream_t * bitD)638*a28cd43dSSascha Wildner MEM_STATIC BYTE FSE_decodeSymbolFast(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD)
639*a28cd43dSSascha Wildner {
640*a28cd43dSSascha Wildner FSE_decode_t const DInfo = ((const FSE_decode_t*)(DStatePtr->table))[DStatePtr->state];
641*a28cd43dSSascha Wildner U32 const nbBits = DInfo.nbBits;
642*a28cd43dSSascha Wildner BYTE const symbol = DInfo.symbol;
643*a28cd43dSSascha Wildner size_t const lowBits = BIT_readBitsFast(bitD, nbBits);
644*a28cd43dSSascha Wildner
645*a28cd43dSSascha Wildner DStatePtr->state = DInfo.newState + lowBits;
646*a28cd43dSSascha Wildner return symbol;
647*a28cd43dSSascha Wildner }
648*a28cd43dSSascha Wildner
FSE_endOfDState(const FSE_DState_t * DStatePtr)649*a28cd43dSSascha Wildner MEM_STATIC unsigned FSE_endOfDState(const FSE_DState_t* DStatePtr)
650*a28cd43dSSascha Wildner {
651*a28cd43dSSascha Wildner return DStatePtr->state == 0;
652*a28cd43dSSascha Wildner }
653*a28cd43dSSascha Wildner
654*a28cd43dSSascha Wildner
655*a28cd43dSSascha Wildner
656*a28cd43dSSascha Wildner #ifndef FSE_COMMONDEFS_ONLY
657*a28cd43dSSascha Wildner
658*a28cd43dSSascha Wildner /* **************************************************************
659*a28cd43dSSascha Wildner * Tuning parameters
660*a28cd43dSSascha Wildner ****************************************************************/
661*a28cd43dSSascha Wildner /*!MEMORY_USAGE :
662*a28cd43dSSascha Wildner * Memory usage formula : N->2^N Bytes (examples : 10 -> 1KB; 12 -> 4KB ; 16 -> 64KB; 20 -> 1MB; etc.)
663*a28cd43dSSascha Wildner * Increasing memory usage improves compression ratio
664*a28cd43dSSascha Wildner * Reduced memory usage can improve speed, due to cache effect
665*a28cd43dSSascha Wildner * Recommended max value is 14, for 16KB, which nicely fits into Intel x86 L1 cache */
666*a28cd43dSSascha Wildner #ifndef FSE_MAX_MEMORY_USAGE
667*a28cd43dSSascha Wildner # define FSE_MAX_MEMORY_USAGE 14
668*a28cd43dSSascha Wildner #endif
669*a28cd43dSSascha Wildner #ifndef FSE_DEFAULT_MEMORY_USAGE
670*a28cd43dSSascha Wildner # define FSE_DEFAULT_MEMORY_USAGE 13
671*a28cd43dSSascha Wildner #endif
672*a28cd43dSSascha Wildner #if (FSE_DEFAULT_MEMORY_USAGE > FSE_MAX_MEMORY_USAGE)
673*a28cd43dSSascha Wildner # error "FSE_DEFAULT_MEMORY_USAGE must be <= FSE_MAX_MEMORY_USAGE"
674*a28cd43dSSascha Wildner #endif
675*a28cd43dSSascha Wildner
676*a28cd43dSSascha Wildner /*!FSE_MAX_SYMBOL_VALUE :
677*a28cd43dSSascha Wildner * Maximum symbol value authorized.
678*a28cd43dSSascha Wildner * Required for proper stack allocation */
679*a28cd43dSSascha Wildner #ifndef FSE_MAX_SYMBOL_VALUE
680*a28cd43dSSascha Wildner # define FSE_MAX_SYMBOL_VALUE 255
681*a28cd43dSSascha Wildner #endif
682*a28cd43dSSascha Wildner
683*a28cd43dSSascha Wildner /* **************************************************************
684*a28cd43dSSascha Wildner * template functions type & suffix
685*a28cd43dSSascha Wildner ****************************************************************/
686*a28cd43dSSascha Wildner #define FSE_FUNCTION_TYPE BYTE
687*a28cd43dSSascha Wildner #define FSE_FUNCTION_EXTENSION
688*a28cd43dSSascha Wildner #define FSE_DECODE_TYPE FSE_decode_t
689*a28cd43dSSascha Wildner
690*a28cd43dSSascha Wildner
691*a28cd43dSSascha Wildner #endif /* !FSE_COMMONDEFS_ONLY */
692*a28cd43dSSascha Wildner
693*a28cd43dSSascha Wildner
694*a28cd43dSSascha Wildner /* ***************************************************************
695*a28cd43dSSascha Wildner * Constants
696*a28cd43dSSascha Wildner *****************************************************************/
697*a28cd43dSSascha Wildner #define FSE_MAX_TABLELOG (FSE_MAX_MEMORY_USAGE-2)
698*a28cd43dSSascha Wildner #define FSE_MAX_TABLESIZE (1U<<FSE_MAX_TABLELOG)
699*a28cd43dSSascha Wildner #define FSE_MAXTABLESIZE_MASK (FSE_MAX_TABLESIZE-1)
700*a28cd43dSSascha Wildner #define FSE_DEFAULT_TABLELOG (FSE_DEFAULT_MEMORY_USAGE-2)
701*a28cd43dSSascha Wildner #define FSE_MIN_TABLELOG 5
702*a28cd43dSSascha Wildner
703*a28cd43dSSascha Wildner #define FSE_TABLELOG_ABSOLUTE_MAX 15
704*a28cd43dSSascha Wildner #if FSE_MAX_TABLELOG > FSE_TABLELOG_ABSOLUTE_MAX
705*a28cd43dSSascha Wildner # error "FSE_MAX_TABLELOG > FSE_TABLELOG_ABSOLUTE_MAX is not supported"
706*a28cd43dSSascha Wildner #endif
707*a28cd43dSSascha Wildner
708*a28cd43dSSascha Wildner #define FSE_TABLESTEP(tableSize) (((tableSize)>>1) + ((tableSize)>>3) + 3)
709*a28cd43dSSascha Wildner
710*a28cd43dSSascha Wildner
711*a28cd43dSSascha Wildner #endif /* FSE_STATIC_LINKING_ONLY */
712*a28cd43dSSascha Wildner
713*a28cd43dSSascha Wildner
714*a28cd43dSSascha Wildner #if defined (__cplusplus)
715*a28cd43dSSascha Wildner }
716*a28cd43dSSascha Wildner #endif
717