projects/linux·blob master · refs

626 lines · 29.3 KiB

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