]>
Commit | Line | Data |
---|---|---|
73f3d1b4 NT |
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 | * This program is free software; you can redistribute it and/or modify it under | |
32 | * the terms of the GNU General Public License version 2 as published by the | |
33 | * Free Software Foundation. This program is dual-licensed; you may select | |
34 | * either version 2 of the GNU General Public License ("GPL") or BSD license | |
35 | * ("BSD"). | |
36 | * | |
37 | * You can contact the author at : | |
38 | * - Source repository : https://github.com/Cyan4973/FiniteStateEntropy | |
39 | */ | |
40 | #ifndef FSE_H | |
41 | #define FSE_H | |
42 | ||
43 | /*-***************************************** | |
44 | * Dependencies | |
45 | ******************************************/ | |
46 | #include <linux/types.h> /* size_t, ptrdiff_t */ | |
47 | ||
48 | /*-***************************************** | |
49 | * FSE_PUBLIC_API : control library symbols visibility | |
50 | ******************************************/ | |
51 | #define FSE_PUBLIC_API | |
52 | ||
53 | /*------ Version ------*/ | |
54 | #define FSE_VERSION_MAJOR 0 | |
55 | #define FSE_VERSION_MINOR 9 | |
56 | #define FSE_VERSION_RELEASE 0 | |
57 | ||
58 | #define FSE_LIB_VERSION FSE_VERSION_MAJOR.FSE_VERSION_MINOR.FSE_VERSION_RELEASE | |
59 | #define FSE_QUOTE(str) #str | |
60 | #define FSE_EXPAND_AND_QUOTE(str) FSE_QUOTE(str) | |
61 | #define FSE_VERSION_STRING FSE_EXPAND_AND_QUOTE(FSE_LIB_VERSION) | |
62 | ||
63 | #define FSE_VERSION_NUMBER (FSE_VERSION_MAJOR * 100 * 100 + FSE_VERSION_MINOR * 100 + FSE_VERSION_RELEASE) | |
64 | FSE_PUBLIC_API unsigned FSE_versionNumber(void); /**< library version number; to be used when checking dll version */ | |
65 | ||
66 | /*-***************************************** | |
67 | * Tool functions | |
68 | ******************************************/ | |
69 | FSE_PUBLIC_API size_t FSE_compressBound(size_t size); /* maximum compressed size */ | |
70 | ||
71 | /* Error Management */ | |
72 | FSE_PUBLIC_API unsigned FSE_isError(size_t code); /* tells if a return value is an error code */ | |
73 | ||
74 | /*-***************************************** | |
75 | * FSE detailed API | |
76 | ******************************************/ | |
77 | /*! | |
78 | FSE_compress() does the following: | |
79 | 1. count symbol occurrence from source[] into table count[] | |
80 | 2. normalize counters so that sum(count[]) == Power_of_2 (2^tableLog) | |
81 | 3. save normalized counters to memory buffer using writeNCount() | |
82 | 4. build encoding table 'CTable' from normalized counters | |
83 | 5. encode the data stream using encoding table 'CTable' | |
84 | ||
85 | FSE_decompress() does the following: | |
86 | 1. read normalized counters with readNCount() | |
87 | 2. build decoding table 'DTable' from normalized counters | |
88 | 3. decode the data stream using decoding table 'DTable' | |
89 | ||
90 | The following API allows targeting specific sub-functions for advanced tasks. | |
91 | For example, it's possible to compress several blocks using the same 'CTable', | |
92 | or to save and provide normalized distribution using external method. | |
93 | */ | |
94 | ||
95 | /* *** COMPRESSION *** */ | |
96 | /*! FSE_optimalTableLog(): | |
97 | dynamically downsize 'tableLog' when conditions are met. | |
98 | It saves CPU time, by using smaller tables, while preserving or even improving compression ratio. | |
99 | @return : recommended tableLog (necessarily <= 'maxTableLog') */ | |
100 | FSE_PUBLIC_API unsigned FSE_optimalTableLog(unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue); | |
101 | ||
102 | /*! FSE_normalizeCount(): | |
103 | normalize counts so that sum(count[]) == Power_of_2 (2^tableLog) | |
104 | 'normalizedCounter' is a table of short, of minimum size (maxSymbolValue+1). | |
105 | @return : tableLog, | |
106 | or an errorCode, which can be tested using FSE_isError() */ | |
107 | FSE_PUBLIC_API size_t FSE_normalizeCount(short *normalizedCounter, unsigned tableLog, const unsigned *count, size_t srcSize, unsigned maxSymbolValue); | |
108 | ||
109 | /*! FSE_NCountWriteBound(): | |
110 | Provides the maximum possible size of an FSE normalized table, given 'maxSymbolValue' and 'tableLog'. | |
111 | Typically useful for allocation purpose. */ | |
112 | FSE_PUBLIC_API size_t FSE_NCountWriteBound(unsigned maxSymbolValue, unsigned tableLog); | |
113 | ||
114 | /*! FSE_writeNCount(): | |
115 | Compactly save 'normalizedCounter' into 'buffer'. | |
116 | @return : size of the compressed table, | |
117 | or an errorCode, which can be tested using FSE_isError(). */ | |
118 | FSE_PUBLIC_API size_t FSE_writeNCount(void *buffer, size_t bufferSize, const short *normalizedCounter, unsigned maxSymbolValue, unsigned tableLog); | |
119 | ||
120 | /*! Constructor and Destructor of FSE_CTable. | |
121 | Note that FSE_CTable size depends on 'tableLog' and 'maxSymbolValue' */ | |
122 | typedef unsigned FSE_CTable; /* don't allocate that. It's only meant to be more restrictive than void* */ | |
123 | ||
124 | /*! FSE_compress_usingCTable(): | |
125 | Compress `src` using `ct` into `dst` which must be already allocated. | |
126 | @return : size of compressed data (<= `dstCapacity`), | |
127 | or 0 if compressed data could not fit into `dst`, | |
128 | or an errorCode, which can be tested using FSE_isError() */ | |
129 | FSE_PUBLIC_API size_t FSE_compress_usingCTable(void *dst, size_t dstCapacity, const void *src, size_t srcSize, const FSE_CTable *ct); | |
130 | ||
131 | /*! | |
132 | Tutorial : | |
133 | ---------- | |
134 | The first step is to count all symbols. FSE_count() does this job very fast. | |
135 | Result will be saved into 'count', a table of unsigned int, which must be already allocated, and have 'maxSymbolValuePtr[0]+1' cells. | |
136 | 'src' is a table of bytes of size 'srcSize'. All values within 'src' MUST be <= maxSymbolValuePtr[0] | |
137 | maxSymbolValuePtr[0] will be updated, with its real value (necessarily <= original value) | |
138 | FSE_count() will return the number of occurrence of the most frequent symbol. | |
139 | This can be used to know if there is a single symbol within 'src', and to quickly evaluate its compressibility. | |
140 | If there is an error, the function will return an ErrorCode (which can be tested using FSE_isError()). | |
141 | ||
142 | The next step is to normalize the frequencies. | |
143 | FSE_normalizeCount() will ensure that sum of frequencies is == 2 ^'tableLog'. | |
144 | It also guarantees a minimum of 1 to any Symbol with frequency >= 1. | |
145 | You can use 'tableLog'==0 to mean "use default tableLog value". | |
146 | If you are unsure of which tableLog value to use, you can ask FSE_optimalTableLog(), | |
147 | which will provide the optimal valid tableLog given sourceSize, maxSymbolValue, and a user-defined maximum (0 means "default"). | |
148 | ||
149 | The result of FSE_normalizeCount() will be saved into a table, | |
150 | called 'normalizedCounter', which is a table of signed short. | |
151 | 'normalizedCounter' must be already allocated, and have at least 'maxSymbolValue+1' cells. | |
152 | The return value is tableLog if everything proceeded as expected. | |
153 | It is 0 if there is a single symbol within distribution. | |
154 | If there is an error (ex: invalid tableLog value), the function will return an ErrorCode (which can be tested using FSE_isError()). | |
155 | ||
156 | 'normalizedCounter' can be saved in a compact manner to a memory area using FSE_writeNCount(). | |
157 | 'buffer' must be already allocated. | |
158 | For guaranteed success, buffer size must be at least FSE_headerBound(). | |
159 | The result of the function is the number of bytes written into 'buffer'. | |
160 | If there is an error, the function will return an ErrorCode (which can be tested using FSE_isError(); ex : buffer size too small). | |
161 | ||
162 | 'normalizedCounter' can then be used to create the compression table 'CTable'. | |
163 | The space required by 'CTable' must be already allocated, using FSE_createCTable(). | |
164 | You can then use FSE_buildCTable() to fill 'CTable'. | |
165 | If there is an error, both functions will return an ErrorCode (which can be tested using FSE_isError()). | |
166 | ||
167 | 'CTable' can then be used to compress 'src', with FSE_compress_usingCTable(). | |
168 | Similar to FSE_count(), the convention is that 'src' is assumed to be a table of char of size 'srcSize' | |
169 | The function returns the size of compressed data (without header), necessarily <= `dstCapacity`. | |
170 | If it returns '0', compressed data could not fit into 'dst'. | |
171 | If there is an error, the function will return an ErrorCode (which can be tested using FSE_isError()). | |
172 | */ | |
173 | ||
174 | /* *** DECOMPRESSION *** */ | |
175 | ||
176 | /*! FSE_readNCount(): | |
177 | Read compactly saved 'normalizedCounter' from 'rBuffer'. | |
178 | @return : size read from 'rBuffer', | |
179 | or an errorCode, which can be tested using FSE_isError(). | |
180 | maxSymbolValuePtr[0] and tableLogPtr[0] will also be updated with their respective values */ | |
181 | FSE_PUBLIC_API size_t FSE_readNCount(short *normalizedCounter, unsigned *maxSymbolValuePtr, unsigned *tableLogPtr, const void *rBuffer, size_t rBuffSize); | |
182 | ||
183 | /*! Constructor and Destructor of FSE_DTable. | |
184 | Note that its size depends on 'tableLog' */ | |
185 | typedef unsigned FSE_DTable; /* don't allocate that. It's just a way to be more restrictive than void* */ | |
186 | ||
187 | /*! FSE_buildDTable(): | |
188 | Builds 'dt', which must be already allocated, using FSE_createDTable(). | |
189 | return : 0, or an errorCode, which can be tested using FSE_isError() */ | |
190 | FSE_PUBLIC_API size_t FSE_buildDTable_wksp(FSE_DTable *dt, const short *normalizedCounter, unsigned maxSymbolValue, unsigned tableLog, void *workspace, size_t workspaceSize); | |
191 | ||
192 | /*! FSE_decompress_usingDTable(): | |
193 | Decompress compressed source `cSrc` of size `cSrcSize` using `dt` | |
194 | into `dst` which must be already allocated. | |
195 | @return : size of regenerated data (necessarily <= `dstCapacity`), | |
196 | or an errorCode, which can be tested using FSE_isError() */ | |
197 | FSE_PUBLIC_API size_t FSE_decompress_usingDTable(void *dst, size_t dstCapacity, const void *cSrc, size_t cSrcSize, const FSE_DTable *dt); | |
198 | ||
199 | /*! | |
200 | Tutorial : | |
201 | ---------- | |
202 | (Note : these functions only decompress FSE-compressed blocks. | |
203 | If block is uncompressed, use memcpy() instead | |
204 | If block is a single repeated byte, use memset() instead ) | |
205 | ||
206 | The first step is to obtain the normalized frequencies of symbols. | |
207 | This can be performed by FSE_readNCount() if it was saved using FSE_writeNCount(). | |
208 | 'normalizedCounter' must be already allocated, and have at least 'maxSymbolValuePtr[0]+1' cells of signed short. | |
209 | In practice, that means it's necessary to know 'maxSymbolValue' beforehand, | |
210 | or size the table to handle worst case situations (typically 256). | |
211 | FSE_readNCount() will provide 'tableLog' and 'maxSymbolValue'. | |
212 | The result of FSE_readNCount() is the number of bytes read from 'rBuffer'. | |
213 | Note that 'rBufferSize' must be at least 4 bytes, even if useful information is less than that. | |
214 | If there is an error, the function will return an error code, which can be tested using FSE_isError(). | |
215 | ||
216 | The next step is to build the decompression tables 'FSE_DTable' from 'normalizedCounter'. | |
217 | This is performed by the function FSE_buildDTable(). | |
218 | The space required by 'FSE_DTable' must be already allocated using FSE_createDTable(). | |
219 | If there is an error, the function will return an error code, which can be tested using FSE_isError(). | |
220 | ||
221 | `FSE_DTable` can then be used to decompress `cSrc`, with FSE_decompress_usingDTable(). | |
222 | `cSrcSize` must be strictly correct, otherwise decompression will fail. | |
223 | FSE_decompress_usingDTable() result will tell how many bytes were regenerated (<=`dstCapacity`). | |
224 | If there is an error, the function will return an error code, which can be tested using FSE_isError(). (ex: dst buffer too small) | |
225 | */ | |
226 | ||
227 | /* *** Dependency *** */ | |
228 | #include "bitstream.h" | |
229 | ||
230 | /* ***************************************** | |
231 | * Static allocation | |
232 | *******************************************/ | |
233 | /* FSE buffer bounds */ | |
234 | #define FSE_NCOUNTBOUND 512 | |
235 | #define FSE_BLOCKBOUND(size) (size + (size >> 7)) | |
236 | #define FSE_COMPRESSBOUND(size) (FSE_NCOUNTBOUND + FSE_BLOCKBOUND(size)) /* Macro version, useful for static allocation */ | |
237 | ||
238 | /* It is possible to statically allocate FSE CTable/DTable as a table of FSE_CTable/FSE_DTable using below macros */ | |
239 | #define FSE_CTABLE_SIZE_U32(maxTableLog, maxSymbolValue) (1 + (1 << (maxTableLog - 1)) + ((maxSymbolValue + 1) * 2)) | |
240 | #define FSE_DTABLE_SIZE_U32(maxTableLog) (1 + (1 << maxTableLog)) | |
241 | ||
242 | /* ***************************************** | |
243 | * FSE advanced API | |
244 | *******************************************/ | |
245 | /* FSE_count_wksp() : | |
246 | * Same as FSE_count(), but using an externally provided scratch buffer. | |
247 | * `workSpace` size must be table of >= `1024` unsigned | |
248 | */ | |
249 | size_t FSE_count_wksp(unsigned *count, unsigned *maxSymbolValuePtr, const void *source, size_t sourceSize, unsigned *workSpace); | |
250 | ||
251 | /* FSE_countFast_wksp() : | |
252 | * Same as FSE_countFast(), but using an externally provided scratch buffer. | |
253 | * `workSpace` must be a table of minimum `1024` unsigned | |
254 | */ | |
255 | size_t FSE_countFast_wksp(unsigned *count, unsigned *maxSymbolValuePtr, const void *src, size_t srcSize, unsigned *workSpace); | |
256 | ||
257 | /*! FSE_count_simple | |
258 | * Same as FSE_countFast(), but does not use any additional memory (not even on stack). | |
259 | * This function is unsafe, and will segfault if any value within `src` is `> *maxSymbolValuePtr` (presuming it's also the size of `count`). | |
260 | */ | |
261 | size_t FSE_count_simple(unsigned *count, unsigned *maxSymbolValuePtr, const void *src, size_t srcSize); | |
262 | ||
263 | unsigned FSE_optimalTableLog_internal(unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue, unsigned minus); | |
264 | /**< same as FSE_optimalTableLog(), which used `minus==2` */ | |
265 | ||
266 | size_t FSE_buildCTable_raw(FSE_CTable *ct, unsigned nbBits); | |
267 | /**< build a fake FSE_CTable, designed for a flat distribution, where each symbol uses nbBits */ | |
268 | ||
269 | size_t FSE_buildCTable_rle(FSE_CTable *ct, unsigned char symbolValue); | |
270 | /**< build a fake FSE_CTable, designed to compress always the same symbolValue */ | |
271 | ||
272 | /* FSE_buildCTable_wksp() : | |
273 | * Same as FSE_buildCTable(), but using an externally allocated scratch buffer (`workSpace`). | |
274 | * `wkspSize` must be >= `(1<<tableLog)`. | |
275 | */ | |
276 | size_t FSE_buildCTable_wksp(FSE_CTable *ct, const short *normalizedCounter, unsigned maxSymbolValue, unsigned tableLog, void *workSpace, size_t wkspSize); | |
277 | ||
278 | size_t FSE_buildDTable_raw(FSE_DTable *dt, unsigned nbBits); | |
279 | /**< build a fake FSE_DTable, designed to read a flat distribution where each symbol uses nbBits */ | |
280 | ||
281 | size_t FSE_buildDTable_rle(FSE_DTable *dt, unsigned char symbolValue); | |
282 | /**< build a fake FSE_DTable, designed to always generate the same symbolValue */ | |
283 | ||
284 | size_t FSE_decompress_wksp(void *dst, size_t dstCapacity, const void *cSrc, size_t cSrcSize, unsigned maxLog, void *workspace, size_t workspaceSize); | |
285 | /**< same as FSE_decompress(), using an externally allocated `workSpace` produced with `FSE_DTABLE_SIZE_U32(maxLog)` */ | |
286 | ||
287 | /* ***************************************** | |
288 | * FSE symbol compression API | |
289 | *******************************************/ | |
290 | /*! | |
291 | This API consists of small unitary functions, which highly benefit from being inlined. | |
292 | Hence their body are included in next section. | |
293 | */ | |
294 | typedef struct { | |
295 | ptrdiff_t value; | |
296 | const void *stateTable; | |
297 | const void *symbolTT; | |
298 | unsigned stateLog; | |
299 | } FSE_CState_t; | |
300 | ||
301 | static void FSE_initCState(FSE_CState_t *CStatePtr, const FSE_CTable *ct); | |
302 | ||
303 | static void FSE_encodeSymbol(BIT_CStream_t *bitC, FSE_CState_t *CStatePtr, unsigned symbol); | |
304 | ||
305 | static void FSE_flushCState(BIT_CStream_t *bitC, const FSE_CState_t *CStatePtr); | |
306 | ||
307 | /**< | |
308 | These functions are inner components of FSE_compress_usingCTable(). | |
309 | They allow the creation of custom streams, mixing multiple tables and bit sources. | |
310 | ||
311 | A key property to keep in mind is that encoding and decoding are done **in reverse direction**. | |
312 | So the first symbol you will encode is the last you will decode, like a LIFO stack. | |
313 | ||
314 | You will need a few variables to track your CStream. They are : | |
315 | ||
316 | FSE_CTable ct; // Provided by FSE_buildCTable() | |
317 | BIT_CStream_t bitStream; // bitStream tracking structure | |
318 | FSE_CState_t state; // State tracking structure (can have several) | |
319 | ||
320 | ||
321 | The first thing to do is to init bitStream and state. | |
322 | size_t errorCode = BIT_initCStream(&bitStream, dstBuffer, maxDstSize); | |
323 | FSE_initCState(&state, ct); | |
324 | ||
325 | Note that BIT_initCStream() can produce an error code, so its result should be tested, using FSE_isError(); | |
326 | You can then encode your input data, byte after byte. | |
327 | FSE_encodeSymbol() outputs a maximum of 'tableLog' bits at a time. | |
328 | Remember decoding will be done in reverse direction. | |
329 | FSE_encodeByte(&bitStream, &state, symbol); | |
330 | ||
331 | At any time, you can also add any bit sequence. | |
332 | Note : maximum allowed nbBits is 25, for compatibility with 32-bits decoders | |
333 | BIT_addBits(&bitStream, bitField, nbBits); | |
334 | ||
335 | The above methods don't commit data to memory, they just store it into local register, for speed. | |
336 | Local register size is 64-bits on 64-bits systems, 32-bits on 32-bits systems (size_t). | |
337 | Writing data to memory is a manual operation, performed by the flushBits function. | |
338 | BIT_flushBits(&bitStream); | |
339 | ||
340 | Your last FSE encoding operation shall be to flush your last state value(s). | |
341 | FSE_flushState(&bitStream, &state); | |
342 | ||
343 | Finally, you must close the bitStream. | |
344 | The function returns the size of CStream in bytes. | |
345 | If data couldn't fit into dstBuffer, it will return a 0 ( == not compressible) | |
346 | If there is an error, it returns an errorCode (which can be tested using FSE_isError()). | |
347 | size_t size = BIT_closeCStream(&bitStream); | |
348 | */ | |
349 | ||
350 | /* ***************************************** | |
351 | * FSE symbol decompression API | |
352 | *******************************************/ | |
353 | typedef struct { | |
354 | size_t state; | |
355 | const void *table; /* precise table may vary, depending on U16 */ | |
356 | } FSE_DState_t; | |
357 | ||
358 | static void FSE_initDState(FSE_DState_t *DStatePtr, BIT_DStream_t *bitD, const FSE_DTable *dt); | |
359 | ||
360 | static unsigned char FSE_decodeSymbol(FSE_DState_t *DStatePtr, BIT_DStream_t *bitD); | |
361 | ||
362 | static unsigned FSE_endOfDState(const FSE_DState_t *DStatePtr); | |
363 | ||
364 | /**< | |
365 | Let's now decompose FSE_decompress_usingDTable() into its unitary components. | |
366 | You will decode FSE-encoded symbols from the bitStream, | |
367 | and also any other bitFields you put in, **in reverse order**. | |
368 | ||
369 | You will need a few variables to track your bitStream. They are : | |
370 | ||
371 | BIT_DStream_t DStream; // Stream context | |
372 | FSE_DState_t DState; // State context. Multiple ones are possible | |
373 | FSE_DTable* DTablePtr; // Decoding table, provided by FSE_buildDTable() | |
374 | ||
375 | The first thing to do is to init the bitStream. | |
376 | errorCode = BIT_initDStream(&DStream, srcBuffer, srcSize); | |
377 | ||
378 | You should then retrieve your initial state(s) | |
379 | (in reverse flushing order if you have several ones) : | |
380 | errorCode = FSE_initDState(&DState, &DStream, DTablePtr); | |
381 | ||
382 | You can then decode your data, symbol after symbol. | |
383 | For information the maximum number of bits read by FSE_decodeSymbol() is 'tableLog'. | |
384 | Keep in mind that symbols are decoded in reverse order, like a LIFO stack (last in, first out). | |
385 | unsigned char symbol = FSE_decodeSymbol(&DState, &DStream); | |
386 | ||
387 | You can retrieve any bitfield you eventually stored into the bitStream (in reverse order) | |
388 | Note : maximum allowed nbBits is 25, for 32-bits compatibility | |
389 | size_t bitField = BIT_readBits(&DStream, nbBits); | |
390 | ||
391 | All above operations only read from local register (which size depends on size_t). | |
392 | Refueling the register from memory is manually performed by the reload method. | |
393 | endSignal = FSE_reloadDStream(&DStream); | |
394 | ||
395 | BIT_reloadDStream() result tells if there is still some more data to read from DStream. | |
396 | BIT_DStream_unfinished : there is still some data left into the DStream. | |
397 | BIT_DStream_endOfBuffer : Dstream reached end of buffer. Its container may no longer be completely filled. | |
398 | BIT_DStream_completed : Dstream reached its exact end, corresponding in general to decompression completed. | |
399 | BIT_DStream_tooFar : Dstream went too far. Decompression result is corrupted. | |
400 | ||
401 | When reaching end of buffer (BIT_DStream_endOfBuffer), progress slowly, notably if you decode multiple symbols per loop, | |
402 | to properly detect the exact end of stream. | |
403 | After each decoded symbol, check if DStream is fully consumed using this simple test : | |
404 | BIT_reloadDStream(&DStream) >= BIT_DStream_completed | |
405 | ||
406 | When it's done, verify decompression is fully completed, by checking both DStream and the relevant states. | |
407 | Checking if DStream has reached its end is performed by : | |
408 | BIT_endOfDStream(&DStream); | |
409 | Check also the states. There might be some symbols left there, if some high probability ones (>50%) are possible. | |
410 | FSE_endOfDState(&DState); | |
411 | */ | |
412 | ||
413 | /* ***************************************** | |
414 | * FSE unsafe API | |
415 | *******************************************/ | |
416 | static unsigned char FSE_decodeSymbolFast(FSE_DState_t *DStatePtr, BIT_DStream_t *bitD); | |
417 | /* faster, but works only if nbBits is always >= 1 (otherwise, result will be corrupted) */ | |
418 | ||
419 | /* ***************************************** | |
420 | * Implementation of inlined functions | |
421 | *******************************************/ | |
422 | typedef struct { | |
423 | int deltaFindState; | |
424 | U32 deltaNbBits; | |
425 | } FSE_symbolCompressionTransform; /* total 8 bytes */ | |
426 | ||
427 | ZSTD_STATIC void FSE_initCState(FSE_CState_t *statePtr, const FSE_CTable *ct) | |
428 | { | |
429 | const void *ptr = ct; | |
430 | const U16 *u16ptr = (const U16 *)ptr; | |
431 | const U32 tableLog = ZSTD_read16(ptr); | |
432 | statePtr->value = (ptrdiff_t)1 << tableLog; | |
433 | statePtr->stateTable = u16ptr + 2; | |
434 | statePtr->symbolTT = ((const U32 *)ct + 1 + (tableLog ? (1 << (tableLog - 1)) : 1)); | |
435 | statePtr->stateLog = tableLog; | |
436 | } | |
437 | ||
438 | /*! FSE_initCState2() : | |
439 | * Same as FSE_initCState(), but the first symbol to include (which will be the last to be read) | |
440 | * uses the smallest state value possible, saving the cost of this symbol */ | |
441 | ZSTD_STATIC void FSE_initCState2(FSE_CState_t *statePtr, const FSE_CTable *ct, U32 symbol) | |
442 | { | |
443 | FSE_initCState(statePtr, ct); | |
444 | { | |
445 | const FSE_symbolCompressionTransform symbolTT = ((const FSE_symbolCompressionTransform *)(statePtr->symbolTT))[symbol]; | |
446 | const U16 *stateTable = (const U16 *)(statePtr->stateTable); | |
447 | U32 nbBitsOut = (U32)((symbolTT.deltaNbBits + (1 << 15)) >> 16); | |
448 | statePtr->value = (nbBitsOut << 16) - symbolTT.deltaNbBits; | |
449 | statePtr->value = stateTable[(statePtr->value >> nbBitsOut) + symbolTT.deltaFindState]; | |
450 | } | |
451 | } | |
452 | ||
453 | ZSTD_STATIC void FSE_encodeSymbol(BIT_CStream_t *bitC, FSE_CState_t *statePtr, U32 symbol) | |
454 | { | |
455 | const FSE_symbolCompressionTransform symbolTT = ((const FSE_symbolCompressionTransform *)(statePtr->symbolTT))[symbol]; | |
456 | const U16 *const stateTable = (const U16 *)(statePtr->stateTable); | |
457 | U32 nbBitsOut = (U32)((statePtr->value + symbolTT.deltaNbBits) >> 16); | |
458 | BIT_addBits(bitC, statePtr->value, nbBitsOut); | |
459 | statePtr->value = stateTable[(statePtr->value >> nbBitsOut) + symbolTT.deltaFindState]; | |
460 | } | |
461 | ||
462 | ZSTD_STATIC void FSE_flushCState(BIT_CStream_t *bitC, const FSE_CState_t *statePtr) | |
463 | { | |
464 | BIT_addBits(bitC, statePtr->value, statePtr->stateLog); | |
465 | BIT_flushBits(bitC); | |
466 | } | |
467 | ||
468 | /* ====== Decompression ====== */ | |
469 | ||
470 | typedef struct { | |
471 | U16 tableLog; | |
472 | U16 fastMode; | |
473 | } FSE_DTableHeader; /* sizeof U32 */ | |
474 | ||
475 | typedef struct { | |
476 | unsigned short newState; | |
477 | unsigned char symbol; | |
478 | unsigned char nbBits; | |
479 | } FSE_decode_t; /* size == U32 */ | |
480 | ||
481 | ZSTD_STATIC void FSE_initDState(FSE_DState_t *DStatePtr, BIT_DStream_t *bitD, const FSE_DTable *dt) | |
482 | { | |
483 | const void *ptr = dt; | |
484 | const FSE_DTableHeader *const DTableH = (const FSE_DTableHeader *)ptr; | |
485 | DStatePtr->state = BIT_readBits(bitD, DTableH->tableLog); | |
486 | BIT_reloadDStream(bitD); | |
487 | DStatePtr->table = dt + 1; | |
488 | } | |
489 | ||
490 | ZSTD_STATIC BYTE FSE_peekSymbol(const FSE_DState_t *DStatePtr) | |
491 | { | |
492 | FSE_decode_t const DInfo = ((const FSE_decode_t *)(DStatePtr->table))[DStatePtr->state]; | |
493 | return DInfo.symbol; | |
494 | } | |
495 | ||
496 | ZSTD_STATIC void FSE_updateState(FSE_DState_t *DStatePtr, BIT_DStream_t *bitD) | |
497 | { | |
498 | FSE_decode_t const DInfo = ((const FSE_decode_t *)(DStatePtr->table))[DStatePtr->state]; | |
499 | U32 const nbBits = DInfo.nbBits; | |
500 | size_t const lowBits = BIT_readBits(bitD, nbBits); | |
501 | DStatePtr->state = DInfo.newState + lowBits; | |
502 | } | |
503 | ||
504 | ZSTD_STATIC BYTE FSE_decodeSymbol(FSE_DState_t *DStatePtr, BIT_DStream_t *bitD) | |
505 | { | |
506 | FSE_decode_t const DInfo = ((const FSE_decode_t *)(DStatePtr->table))[DStatePtr->state]; | |
507 | U32 const nbBits = DInfo.nbBits; | |
508 | BYTE const symbol = DInfo.symbol; | |
509 | size_t const lowBits = BIT_readBits(bitD, nbBits); | |
510 | ||
511 | DStatePtr->state = DInfo.newState + lowBits; | |
512 | return symbol; | |
513 | } | |
514 | ||
515 | /*! FSE_decodeSymbolFast() : | |
516 | unsafe, only works if no symbol has a probability > 50% */ | |
517 | ZSTD_STATIC BYTE FSE_decodeSymbolFast(FSE_DState_t *DStatePtr, BIT_DStream_t *bitD) | |
518 | { | |
519 | FSE_decode_t const DInfo = ((const FSE_decode_t *)(DStatePtr->table))[DStatePtr->state]; | |
520 | U32 const nbBits = DInfo.nbBits; | |
521 | BYTE const symbol = DInfo.symbol; | |
522 | size_t const lowBits = BIT_readBitsFast(bitD, nbBits); | |
523 | ||
524 | DStatePtr->state = DInfo.newState + lowBits; | |
525 | return symbol; | |
526 | } | |
527 | ||
528 | ZSTD_STATIC unsigned FSE_endOfDState(const FSE_DState_t *DStatePtr) { return DStatePtr->state == 0; } | |
529 | ||
530 | /* ************************************************************** | |
531 | * Tuning parameters | |
532 | ****************************************************************/ | |
533 | /*!MEMORY_USAGE : | |
534 | * Memory usage formula : N->2^N Bytes (examples : 10 -> 1KB; 12 -> 4KB ; 16 -> 64KB; 20 -> 1MB; etc.) | |
535 | * Increasing memory usage improves compression ratio | |
536 | * Reduced memory usage can improve speed, due to cache effect | |
537 | * Recommended max value is 14, for 16KB, which nicely fits into Intel x86 L1 cache */ | |
538 | #ifndef FSE_MAX_MEMORY_USAGE | |
539 | #define FSE_MAX_MEMORY_USAGE 14 | |
540 | #endif | |
541 | #ifndef FSE_DEFAULT_MEMORY_USAGE | |
542 | #define FSE_DEFAULT_MEMORY_USAGE 13 | |
543 | #endif | |
544 | ||
545 | /*!FSE_MAX_SYMBOL_VALUE : | |
546 | * Maximum symbol value authorized. | |
547 | * Required for proper stack allocation */ | |
548 | #ifndef FSE_MAX_SYMBOL_VALUE | |
549 | #define FSE_MAX_SYMBOL_VALUE 255 | |
550 | #endif | |
551 | ||
552 | /* ************************************************************** | |
553 | * template functions type & suffix | |
554 | ****************************************************************/ | |
555 | #define FSE_FUNCTION_TYPE BYTE | |
556 | #define FSE_FUNCTION_EXTENSION | |
557 | #define FSE_DECODE_TYPE FSE_decode_t | |
558 | ||
559 | /* *************************************************************** | |
560 | * Constants | |
561 | *****************************************************************/ | |
562 | #define FSE_MAX_TABLELOG (FSE_MAX_MEMORY_USAGE - 2) | |
563 | #define FSE_MAX_TABLESIZE (1U << FSE_MAX_TABLELOG) | |
564 | #define FSE_MAXTABLESIZE_MASK (FSE_MAX_TABLESIZE - 1) | |
565 | #define FSE_DEFAULT_TABLELOG (FSE_DEFAULT_MEMORY_USAGE - 2) | |
566 | #define FSE_MIN_TABLELOG 5 | |
567 | ||
568 | #define FSE_TABLELOG_ABSOLUTE_MAX 15 | |
569 | #if FSE_MAX_TABLELOG > FSE_TABLELOG_ABSOLUTE_MAX | |
570 | #error "FSE_MAX_TABLELOG > FSE_TABLELOG_ABSOLUTE_MAX is not supported" | |
571 | #endif | |
572 | ||
573 | #define FSE_TABLESTEP(tableSize) ((tableSize >> 1) + (tableSize >> 3) + 3) | |
574 | ||
575 | #endif /* FSE_H */ |