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