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