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