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