1a28cd43dSSascha Wildner /* ******************************************************************
2a28cd43dSSascha Wildner * FSE : Finite State Entropy decoder
3a28cd43dSSascha Wildner * Copyright (c) 2013-2020, Yann Collet, Facebook, Inc.
4a28cd43dSSascha Wildner *
5a28cd43dSSascha Wildner * You can contact the author at :
6a28cd43dSSascha Wildner * - FSE source repository : https://github.com/Cyan4973/FiniteStateEntropy
7a28cd43dSSascha Wildner * - Public forum : https://groups.google.com/forum/#!forum/lz4c
8a28cd43dSSascha Wildner *
9a28cd43dSSascha Wildner * This source code is licensed under both the BSD-style license (found in the
10a28cd43dSSascha Wildner * LICENSE file in the root directory of this source tree) and the GPLv2 (found
11a28cd43dSSascha Wildner * in the COPYING file in the root directory of this source tree).
12a28cd43dSSascha Wildner * You may select, at your option, one of the above-listed licenses.
13a28cd43dSSascha Wildner ****************************************************************** */
14a28cd43dSSascha Wildner
15a28cd43dSSascha Wildner
16a28cd43dSSascha Wildner /* **************************************************************
17a28cd43dSSascha Wildner * Includes
18a28cd43dSSascha Wildner ****************************************************************/
19a28cd43dSSascha Wildner #include "debug.h" /* assert */
20a28cd43dSSascha Wildner #include "bitstream.h"
21a28cd43dSSascha Wildner #include "compiler.h"
22a28cd43dSSascha Wildner #define FSE_STATIC_LINKING_ONLY
23a28cd43dSSascha Wildner #include "fse.h"
24a28cd43dSSascha Wildner #include "error_private.h"
25a28cd43dSSascha Wildner #define ZSTD_DEPS_NEED_MALLOC
26a28cd43dSSascha Wildner #include "zstd_deps.h"
27a28cd43dSSascha Wildner
28a28cd43dSSascha Wildner
29a28cd43dSSascha Wildner /* **************************************************************
30a28cd43dSSascha Wildner * Error Management
31a28cd43dSSascha Wildner ****************************************************************/
32a28cd43dSSascha Wildner #define FSE_isError ERR_isError
33a28cd43dSSascha Wildner #define FSE_STATIC_ASSERT(c) DEBUG_STATIC_ASSERT(c) /* use only *after* variable declarations */
34a28cd43dSSascha Wildner
35a28cd43dSSascha Wildner
36a28cd43dSSascha Wildner /* **************************************************************
37a28cd43dSSascha Wildner * Templates
38a28cd43dSSascha Wildner ****************************************************************/
39a28cd43dSSascha Wildner /*
40a28cd43dSSascha Wildner designed to be included
41a28cd43dSSascha Wildner for type-specific functions (template emulation in C)
42a28cd43dSSascha Wildner Objective is to write these functions only once, for improved maintenance
43a28cd43dSSascha Wildner */
44a28cd43dSSascha Wildner
45a28cd43dSSascha Wildner /* safety checks */
46a28cd43dSSascha Wildner #ifndef FSE_FUNCTION_EXTENSION
47a28cd43dSSascha Wildner # error "FSE_FUNCTION_EXTENSION must be defined"
48a28cd43dSSascha Wildner #endif
49a28cd43dSSascha Wildner #ifndef FSE_FUNCTION_TYPE
50a28cd43dSSascha Wildner # error "FSE_FUNCTION_TYPE must be defined"
51a28cd43dSSascha Wildner #endif
52a28cd43dSSascha Wildner
53a28cd43dSSascha Wildner /* Function names */
54a28cd43dSSascha Wildner #define FSE_CAT(X,Y) X##Y
55a28cd43dSSascha Wildner #define FSE_FUNCTION_NAME(X,Y) FSE_CAT(X,Y)
56a28cd43dSSascha Wildner #define FSE_TYPE_NAME(X,Y) FSE_CAT(X,Y)
57a28cd43dSSascha Wildner
58a28cd43dSSascha Wildner
59a28cd43dSSascha Wildner /* Function templates */
FSE_createDTable(unsigned tableLog)60a28cd43dSSascha Wildner FSE_DTable* FSE_createDTable (unsigned tableLog)
61a28cd43dSSascha Wildner {
62a28cd43dSSascha Wildner if (tableLog > FSE_TABLELOG_ABSOLUTE_MAX) tableLog = FSE_TABLELOG_ABSOLUTE_MAX;
63a28cd43dSSascha Wildner return (FSE_DTable*)ZSTD_malloc( FSE_DTABLE_SIZE_U32(tableLog) * sizeof (U32) );
64a28cd43dSSascha Wildner }
65a28cd43dSSascha Wildner
FSE_freeDTable(FSE_DTable * dt)66a28cd43dSSascha Wildner void FSE_freeDTable (FSE_DTable* dt)
67a28cd43dSSascha Wildner {
68a28cd43dSSascha Wildner ZSTD_free(dt);
69a28cd43dSSascha Wildner }
70a28cd43dSSascha Wildner
FSE_buildDTable_internal(FSE_DTable * dt,const short * normalizedCounter,unsigned maxSymbolValue,unsigned tableLog,void * workSpace,size_t wkspSize)71a28cd43dSSascha Wildner static size_t FSE_buildDTable_internal(FSE_DTable* dt, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog, void* workSpace, size_t wkspSize)
72a28cd43dSSascha Wildner {
73a28cd43dSSascha Wildner void* const tdPtr = dt+1; /* because *dt is unsigned, 32-bits aligned on 32-bits */
74a28cd43dSSascha Wildner FSE_DECODE_TYPE* const tableDecode = (FSE_DECODE_TYPE*) (tdPtr);
75a28cd43dSSascha Wildner U16* symbolNext = (U16*)workSpace;
76a28cd43dSSascha Wildner BYTE* spread = (BYTE*)(symbolNext + maxSymbolValue + 1);
77a28cd43dSSascha Wildner
78a28cd43dSSascha Wildner U32 const maxSV1 = maxSymbolValue + 1;
79a28cd43dSSascha Wildner U32 const tableSize = 1 << tableLog;
80a28cd43dSSascha Wildner U32 highThreshold = tableSize-1;
81a28cd43dSSascha Wildner
82a28cd43dSSascha Wildner /* Sanity Checks */
83a28cd43dSSascha Wildner if (FSE_BUILD_DTABLE_WKSP_SIZE(tableLog, maxSymbolValue) > wkspSize) return ERROR(maxSymbolValue_tooLarge);
84a28cd43dSSascha Wildner if (maxSymbolValue > FSE_MAX_SYMBOL_VALUE) return ERROR(maxSymbolValue_tooLarge);
85a28cd43dSSascha Wildner if (tableLog > FSE_MAX_TABLELOG) return ERROR(tableLog_tooLarge);
86a28cd43dSSascha Wildner
87a28cd43dSSascha Wildner /* Init, lay down lowprob symbols */
88a28cd43dSSascha Wildner { FSE_DTableHeader DTableH;
89a28cd43dSSascha Wildner DTableH.tableLog = (U16)tableLog;
90a28cd43dSSascha Wildner DTableH.fastMode = 1;
91a28cd43dSSascha Wildner { S16 const largeLimit= (S16)(1 << (tableLog-1));
92a28cd43dSSascha Wildner U32 s;
93a28cd43dSSascha Wildner for (s=0; s<maxSV1; s++) {
94a28cd43dSSascha Wildner if (normalizedCounter[s]==-1) {
95a28cd43dSSascha Wildner tableDecode[highThreshold--].symbol = (FSE_FUNCTION_TYPE)s;
96a28cd43dSSascha Wildner symbolNext[s] = 1;
97a28cd43dSSascha Wildner } else {
98a28cd43dSSascha Wildner if (normalizedCounter[s] >= largeLimit) DTableH.fastMode=0;
99a28cd43dSSascha Wildner symbolNext[s] = normalizedCounter[s];
100a28cd43dSSascha Wildner } } }
101a28cd43dSSascha Wildner ZSTD_memcpy(dt, &DTableH, sizeof(DTableH));
102a28cd43dSSascha Wildner }
103a28cd43dSSascha Wildner
104a28cd43dSSascha Wildner /* Spread symbols */
105a28cd43dSSascha Wildner if (highThreshold == tableSize - 1) {
106a28cd43dSSascha Wildner size_t const tableMask = tableSize-1;
107a28cd43dSSascha Wildner size_t const step = FSE_TABLESTEP(tableSize);
108a28cd43dSSascha Wildner /* First lay down the symbols in order.
109a28cd43dSSascha Wildner * We use a uint64_t to lay down 8 bytes at a time. This reduces branch
110a28cd43dSSascha Wildner * misses since small blocks generally have small table logs, so nearly
111a28cd43dSSascha Wildner * all symbols have counts <= 8. We ensure we have 8 bytes at the end of
112a28cd43dSSascha Wildner * our buffer to handle the over-write.
113a28cd43dSSascha Wildner */
114a28cd43dSSascha Wildner {
115a28cd43dSSascha Wildner U64 const add = 0x0101010101010101ull;
116a28cd43dSSascha Wildner size_t pos = 0;
117a28cd43dSSascha Wildner U64 sv = 0;
118a28cd43dSSascha Wildner U32 s;
119a28cd43dSSascha Wildner for (s=0; s<maxSV1; ++s, sv += add) {
120a28cd43dSSascha Wildner int i;
121a28cd43dSSascha Wildner int const n = normalizedCounter[s];
122a28cd43dSSascha Wildner MEM_write64(spread + pos, sv);
123a28cd43dSSascha Wildner for (i = 8; i < n; i += 8) {
124a28cd43dSSascha Wildner MEM_write64(spread + pos + i, sv);
125a28cd43dSSascha Wildner }
126a28cd43dSSascha Wildner pos += n;
127a28cd43dSSascha Wildner }
128a28cd43dSSascha Wildner }
129a28cd43dSSascha Wildner /* Now we spread those positions across the table.
130a28cd43dSSascha Wildner * The benefit of doing it in two stages is that we avoid the the
131a28cd43dSSascha Wildner * variable size inner loop, which caused lots of branch misses.
132a28cd43dSSascha Wildner * Now we can run through all the positions without any branch misses.
133a28cd43dSSascha Wildner * We unroll the loop twice, since that is what emperically worked best.
134a28cd43dSSascha Wildner */
135a28cd43dSSascha Wildner {
136a28cd43dSSascha Wildner size_t position = 0;
137a28cd43dSSascha Wildner size_t s;
138a28cd43dSSascha Wildner size_t const unroll = 2;
139a28cd43dSSascha Wildner assert(tableSize % unroll == 0); /* FSE_MIN_TABLELOG is 5 */
140a28cd43dSSascha Wildner for (s = 0; s < (size_t)tableSize; s += unroll) {
141a28cd43dSSascha Wildner size_t u;
142a28cd43dSSascha Wildner for (u = 0; u < unroll; ++u) {
143a28cd43dSSascha Wildner size_t const uPosition = (position + (u * step)) & tableMask;
144a28cd43dSSascha Wildner tableDecode[uPosition].symbol = spread[s + u];
145a28cd43dSSascha Wildner }
146a28cd43dSSascha Wildner position = (position + (unroll * step)) & tableMask;
147a28cd43dSSascha Wildner }
148a28cd43dSSascha Wildner assert(position == 0);
149a28cd43dSSascha Wildner }
150a28cd43dSSascha Wildner } else {
151a28cd43dSSascha Wildner U32 const tableMask = tableSize-1;
152a28cd43dSSascha Wildner U32 const step = FSE_TABLESTEP(tableSize);
153a28cd43dSSascha Wildner U32 s, position = 0;
154a28cd43dSSascha Wildner for (s=0; s<maxSV1; s++) {
155a28cd43dSSascha Wildner int i;
156a28cd43dSSascha Wildner for (i=0; i<normalizedCounter[s]; i++) {
157a28cd43dSSascha Wildner tableDecode[position].symbol = (FSE_FUNCTION_TYPE)s;
158a28cd43dSSascha Wildner position = (position + step) & tableMask;
159a28cd43dSSascha Wildner while (position > highThreshold) position = (position + step) & tableMask; /* lowprob area */
160a28cd43dSSascha Wildner } }
161a28cd43dSSascha Wildner if (position!=0) return ERROR(GENERIC); /* position must reach all cells once, otherwise normalizedCounter is incorrect */
162a28cd43dSSascha Wildner }
163a28cd43dSSascha Wildner
164a28cd43dSSascha Wildner /* Build Decoding table */
165a28cd43dSSascha Wildner { U32 u;
166a28cd43dSSascha Wildner for (u=0; u<tableSize; u++) {
167a28cd43dSSascha Wildner FSE_FUNCTION_TYPE const symbol = (FSE_FUNCTION_TYPE)(tableDecode[u].symbol);
168a28cd43dSSascha Wildner U32 const nextState = symbolNext[symbol]++;
169a28cd43dSSascha Wildner tableDecode[u].nbBits = (BYTE) (tableLog - BIT_highbit32(nextState) );
170a28cd43dSSascha Wildner tableDecode[u].newState = (U16) ( (nextState << tableDecode[u].nbBits) - tableSize);
171a28cd43dSSascha Wildner } }
172a28cd43dSSascha Wildner
173a28cd43dSSascha Wildner return 0;
174a28cd43dSSascha Wildner }
175a28cd43dSSascha Wildner
FSE_buildDTable_wksp(FSE_DTable * dt,const short * normalizedCounter,unsigned maxSymbolValue,unsigned tableLog,void * workSpace,size_t wkspSize)176a28cd43dSSascha Wildner size_t FSE_buildDTable_wksp(FSE_DTable* dt, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog, void* workSpace, size_t wkspSize)
177a28cd43dSSascha Wildner {
178a28cd43dSSascha Wildner return FSE_buildDTable_internal(dt, normalizedCounter, maxSymbolValue, tableLog, workSpace, wkspSize);
179a28cd43dSSascha Wildner }
180a28cd43dSSascha Wildner
181a28cd43dSSascha Wildner
182a28cd43dSSascha Wildner #ifndef FSE_COMMONDEFS_ONLY
183a28cd43dSSascha Wildner
184a28cd43dSSascha Wildner /*-*******************************************************
185a28cd43dSSascha Wildner * Decompression (Byte symbols)
186a28cd43dSSascha Wildner *********************************************************/
FSE_buildDTable_rle(FSE_DTable * dt,BYTE symbolValue)187a28cd43dSSascha Wildner size_t FSE_buildDTable_rle (FSE_DTable* dt, BYTE symbolValue)
188a28cd43dSSascha Wildner {
189a28cd43dSSascha Wildner void* ptr = dt;
190a28cd43dSSascha Wildner FSE_DTableHeader* const DTableH = (FSE_DTableHeader*)ptr;
191a28cd43dSSascha Wildner void* dPtr = dt + 1;
192a28cd43dSSascha Wildner FSE_decode_t* const cell = (FSE_decode_t*)dPtr;
193a28cd43dSSascha Wildner
194a28cd43dSSascha Wildner DTableH->tableLog = 0;
195a28cd43dSSascha Wildner DTableH->fastMode = 0;
196a28cd43dSSascha Wildner
197a28cd43dSSascha Wildner cell->newState = 0;
198a28cd43dSSascha Wildner cell->symbol = symbolValue;
199a28cd43dSSascha Wildner cell->nbBits = 0;
200a28cd43dSSascha Wildner
201a28cd43dSSascha Wildner return 0;
202a28cd43dSSascha Wildner }
203a28cd43dSSascha Wildner
204a28cd43dSSascha Wildner
FSE_buildDTable_raw(FSE_DTable * dt,unsigned nbBits)205a28cd43dSSascha Wildner size_t FSE_buildDTable_raw (FSE_DTable* dt, unsigned nbBits)
206a28cd43dSSascha Wildner {
207a28cd43dSSascha Wildner void* ptr = dt;
208a28cd43dSSascha Wildner FSE_DTableHeader* const DTableH = (FSE_DTableHeader*)ptr;
209a28cd43dSSascha Wildner void* dPtr = dt + 1;
210a28cd43dSSascha Wildner FSE_decode_t* const dinfo = (FSE_decode_t*)dPtr;
211a28cd43dSSascha Wildner const unsigned tableSize = 1 << nbBits;
212a28cd43dSSascha Wildner const unsigned tableMask = tableSize - 1;
213a28cd43dSSascha Wildner const unsigned maxSV1 = tableMask+1;
214a28cd43dSSascha Wildner unsigned s;
215a28cd43dSSascha Wildner
216a28cd43dSSascha Wildner /* Sanity checks */
217a28cd43dSSascha Wildner if (nbBits < 1) return ERROR(GENERIC); /* min size */
218a28cd43dSSascha Wildner
219a28cd43dSSascha Wildner /* Build Decoding Table */
220a28cd43dSSascha Wildner DTableH->tableLog = (U16)nbBits;
221a28cd43dSSascha Wildner DTableH->fastMode = 1;
222a28cd43dSSascha Wildner for (s=0; s<maxSV1; s++) {
223a28cd43dSSascha Wildner dinfo[s].newState = 0;
224a28cd43dSSascha Wildner dinfo[s].symbol = (BYTE)s;
225a28cd43dSSascha Wildner dinfo[s].nbBits = (BYTE)nbBits;
226a28cd43dSSascha Wildner }
227a28cd43dSSascha Wildner
228a28cd43dSSascha Wildner return 0;
229a28cd43dSSascha Wildner }
230a28cd43dSSascha Wildner
FSE_decompress_usingDTable_generic(void * dst,size_t maxDstSize,const void * cSrc,size_t cSrcSize,const FSE_DTable * dt,const unsigned fast)231a28cd43dSSascha Wildner FORCE_INLINE_TEMPLATE size_t FSE_decompress_usingDTable_generic(
232a28cd43dSSascha Wildner void* dst, size_t maxDstSize,
233a28cd43dSSascha Wildner const void* cSrc, size_t cSrcSize,
234a28cd43dSSascha Wildner const FSE_DTable* dt, const unsigned fast)
235a28cd43dSSascha Wildner {
236a28cd43dSSascha Wildner BYTE* const ostart = (BYTE*) dst;
237a28cd43dSSascha Wildner BYTE* op = ostart;
238a28cd43dSSascha Wildner BYTE* const omax = op + maxDstSize;
239a28cd43dSSascha Wildner BYTE* const olimit = omax-3;
240a28cd43dSSascha Wildner
241a28cd43dSSascha Wildner BIT_DStream_t bitD;
242a28cd43dSSascha Wildner FSE_DState_t state1;
243a28cd43dSSascha Wildner FSE_DState_t state2;
244a28cd43dSSascha Wildner
245a28cd43dSSascha Wildner /* Init */
246a28cd43dSSascha Wildner CHECK_F(BIT_initDStream(&bitD, cSrc, cSrcSize));
247a28cd43dSSascha Wildner
248a28cd43dSSascha Wildner FSE_initDState(&state1, &bitD, dt);
249a28cd43dSSascha Wildner FSE_initDState(&state2, &bitD, dt);
250a28cd43dSSascha Wildner
251a28cd43dSSascha Wildner #define FSE_GETSYMBOL(statePtr) fast ? FSE_decodeSymbolFast(statePtr, &bitD) : FSE_decodeSymbol(statePtr, &bitD)
252a28cd43dSSascha Wildner
253a28cd43dSSascha Wildner /* 4 symbols per loop */
254a28cd43dSSascha Wildner for ( ; (BIT_reloadDStream(&bitD)==BIT_DStream_unfinished) & (op<olimit) ; op+=4) {
255a28cd43dSSascha Wildner op[0] = FSE_GETSYMBOL(&state1);
256a28cd43dSSascha Wildner
257a28cd43dSSascha Wildner if (FSE_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */
258a28cd43dSSascha Wildner BIT_reloadDStream(&bitD);
259a28cd43dSSascha Wildner
260a28cd43dSSascha Wildner op[1] = FSE_GETSYMBOL(&state2);
261a28cd43dSSascha Wildner
262a28cd43dSSascha Wildner if (FSE_MAX_TABLELOG*4+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */
263a28cd43dSSascha Wildner { if (BIT_reloadDStream(&bitD) > BIT_DStream_unfinished) { op+=2; break; } }
264a28cd43dSSascha Wildner
265a28cd43dSSascha Wildner op[2] = FSE_GETSYMBOL(&state1);
266a28cd43dSSascha Wildner
267a28cd43dSSascha Wildner if (FSE_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */
268a28cd43dSSascha Wildner BIT_reloadDStream(&bitD);
269a28cd43dSSascha Wildner
270a28cd43dSSascha Wildner op[3] = FSE_GETSYMBOL(&state2);
271a28cd43dSSascha Wildner }
272a28cd43dSSascha Wildner
273a28cd43dSSascha Wildner /* tail */
274a28cd43dSSascha Wildner /* note : BIT_reloadDStream(&bitD) >= FSE_DStream_partiallyFilled; Ends at exactly BIT_DStream_completed */
275a28cd43dSSascha Wildner while (1) {
276a28cd43dSSascha Wildner if (op>(omax-2)) return ERROR(dstSize_tooSmall);
277a28cd43dSSascha Wildner *op++ = FSE_GETSYMBOL(&state1);
278a28cd43dSSascha Wildner if (BIT_reloadDStream(&bitD)==BIT_DStream_overflow) {
279a28cd43dSSascha Wildner *op++ = FSE_GETSYMBOL(&state2);
280a28cd43dSSascha Wildner break;
281a28cd43dSSascha Wildner }
282a28cd43dSSascha Wildner
283a28cd43dSSascha Wildner if (op>(omax-2)) return ERROR(dstSize_tooSmall);
284a28cd43dSSascha Wildner *op++ = FSE_GETSYMBOL(&state2);
285a28cd43dSSascha Wildner if (BIT_reloadDStream(&bitD)==BIT_DStream_overflow) {
286a28cd43dSSascha Wildner *op++ = FSE_GETSYMBOL(&state1);
287a28cd43dSSascha Wildner break;
288a28cd43dSSascha Wildner } }
289a28cd43dSSascha Wildner
290a28cd43dSSascha Wildner return op-ostart;
291a28cd43dSSascha Wildner }
292a28cd43dSSascha Wildner
293a28cd43dSSascha Wildner
FSE_decompress_usingDTable(void * dst,size_t originalSize,const void * cSrc,size_t cSrcSize,const FSE_DTable * dt)294a28cd43dSSascha Wildner size_t FSE_decompress_usingDTable(void* dst, size_t originalSize,
295a28cd43dSSascha Wildner const void* cSrc, size_t cSrcSize,
296a28cd43dSSascha Wildner const FSE_DTable* dt)
297a28cd43dSSascha Wildner {
298a28cd43dSSascha Wildner const void* ptr = dt;
299a28cd43dSSascha Wildner const FSE_DTableHeader* DTableH = (const FSE_DTableHeader*)ptr;
300a28cd43dSSascha Wildner const U32 fastMode = DTableH->fastMode;
301a28cd43dSSascha Wildner
302a28cd43dSSascha Wildner /* select fast mode (static) */
303a28cd43dSSascha Wildner if (fastMode) return FSE_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 1);
304a28cd43dSSascha Wildner return FSE_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 0);
305a28cd43dSSascha Wildner }
306a28cd43dSSascha Wildner
307a28cd43dSSascha Wildner
FSE_decompress_wksp(void * dst,size_t dstCapacity,const void * cSrc,size_t cSrcSize,unsigned maxLog,void * workSpace,size_t wkspSize)308a28cd43dSSascha Wildner size_t FSE_decompress_wksp(void* dst, size_t dstCapacity, const void* cSrc, size_t cSrcSize, unsigned maxLog, void* workSpace, size_t wkspSize)
309a28cd43dSSascha Wildner {
310a28cd43dSSascha Wildner return FSE_decompress_wksp_bmi2(dst, dstCapacity, cSrc, cSrcSize, maxLog, workSpace, wkspSize, /* bmi2 */ 0);
311a28cd43dSSascha Wildner }
312a28cd43dSSascha Wildner
FSE_decompress_wksp_body(void * dst,size_t dstCapacity,const void * cSrc,size_t cSrcSize,unsigned maxLog,void * workSpace,size_t wkspSize,int bmi2)313a28cd43dSSascha Wildner FORCE_INLINE_TEMPLATE size_t FSE_decompress_wksp_body(
314a28cd43dSSascha Wildner void* dst, size_t dstCapacity,
315a28cd43dSSascha Wildner const void* cSrc, size_t cSrcSize,
316a28cd43dSSascha Wildner unsigned maxLog, void* workSpace, size_t wkspSize,
317a28cd43dSSascha Wildner int bmi2)
318a28cd43dSSascha Wildner {
319a28cd43dSSascha Wildner const BYTE* const istart = (const BYTE*)cSrc;
320a28cd43dSSascha Wildner const BYTE* ip = istart;
321a28cd43dSSascha Wildner short counting[FSE_MAX_SYMBOL_VALUE+1];
322a28cd43dSSascha Wildner unsigned tableLog;
323a28cd43dSSascha Wildner unsigned maxSymbolValue = FSE_MAX_SYMBOL_VALUE;
324a28cd43dSSascha Wildner FSE_DTable* const dtable = (FSE_DTable*)workSpace;
325a28cd43dSSascha Wildner
326a28cd43dSSascha Wildner /* normal FSE decoding mode */
327a28cd43dSSascha Wildner size_t const NCountLength = FSE_readNCount_bmi2(counting, &maxSymbolValue, &tableLog, istart, cSrcSize, bmi2);
328a28cd43dSSascha Wildner if (FSE_isError(NCountLength)) return NCountLength;
329a28cd43dSSascha Wildner if (tableLog > maxLog) return ERROR(tableLog_tooLarge);
330a28cd43dSSascha Wildner assert(NCountLength <= cSrcSize);
331a28cd43dSSascha Wildner ip += NCountLength;
332a28cd43dSSascha Wildner cSrcSize -= NCountLength;
333a28cd43dSSascha Wildner
334a28cd43dSSascha Wildner if (FSE_DECOMPRESS_WKSP_SIZE(tableLog, maxSymbolValue) > wkspSize) return ERROR(tableLog_tooLarge);
335a28cd43dSSascha Wildner workSpace = dtable + FSE_DTABLE_SIZE_U32(tableLog);
336a28cd43dSSascha Wildner wkspSize -= FSE_DTABLE_SIZE(tableLog);
337a28cd43dSSascha Wildner
338a28cd43dSSascha Wildner CHECK_F( FSE_buildDTable_internal(dtable, counting, maxSymbolValue, tableLog, workSpace, wkspSize) );
339a28cd43dSSascha Wildner
340a28cd43dSSascha Wildner {
341a28cd43dSSascha Wildner const void* ptr = dtable;
342a28cd43dSSascha Wildner const FSE_DTableHeader* DTableH = (const FSE_DTableHeader*)ptr;
343a28cd43dSSascha Wildner const U32 fastMode = DTableH->fastMode;
344a28cd43dSSascha Wildner
345a28cd43dSSascha Wildner /* select fast mode (static) */
346a28cd43dSSascha Wildner if (fastMode) return FSE_decompress_usingDTable_generic(dst, dstCapacity, ip, cSrcSize, dtable, 1);
347a28cd43dSSascha Wildner return FSE_decompress_usingDTable_generic(dst, dstCapacity, ip, cSrcSize, dtable, 0);
348a28cd43dSSascha Wildner }
349a28cd43dSSascha Wildner }
350a28cd43dSSascha Wildner
351a28cd43dSSascha Wildner /* Avoids the FORCE_INLINE of the _body() function. */
FSE_decompress_wksp_body_default(void * dst,size_t dstCapacity,const void * cSrc,size_t cSrcSize,unsigned maxLog,void * workSpace,size_t wkspSize)352a28cd43dSSascha Wildner static size_t FSE_decompress_wksp_body_default(void* dst, size_t dstCapacity, const void* cSrc, size_t cSrcSize, unsigned maxLog, void* workSpace, size_t wkspSize)
353a28cd43dSSascha Wildner {
354a28cd43dSSascha Wildner return FSE_decompress_wksp_body(dst, dstCapacity, cSrc, cSrcSize, maxLog, workSpace, wkspSize, 0);
355a28cd43dSSascha Wildner }
356a28cd43dSSascha Wildner
357a28cd43dSSascha Wildner #if DYNAMIC_BMI2
FSE_decompress_wksp_body_bmi2(void * dst,size_t dstCapacity,const void * cSrc,size_t cSrcSize,unsigned maxLog,void * workSpace,size_t wkspSize)358a28cd43dSSascha Wildner TARGET_ATTRIBUTE("bmi2") static size_t FSE_decompress_wksp_body_bmi2(void* dst, size_t dstCapacity, const void* cSrc, size_t cSrcSize, unsigned maxLog, void* workSpace, size_t wkspSize)
359a28cd43dSSascha Wildner {
360a28cd43dSSascha Wildner return FSE_decompress_wksp_body(dst, dstCapacity, cSrc, cSrcSize, maxLog, workSpace, wkspSize, 1);
361a28cd43dSSascha Wildner }
362a28cd43dSSascha Wildner #endif
363a28cd43dSSascha Wildner
FSE_decompress_wksp_bmi2(void * dst,size_t dstCapacity,const void * cSrc,size_t cSrcSize,unsigned maxLog,void * workSpace,size_t wkspSize,int bmi2)364a28cd43dSSascha Wildner size_t FSE_decompress_wksp_bmi2(void* dst, size_t dstCapacity, const void* cSrc, size_t cSrcSize, unsigned maxLog, void* workSpace, size_t wkspSize, int bmi2)
365a28cd43dSSascha Wildner {
366a28cd43dSSascha Wildner #if DYNAMIC_BMI2
367a28cd43dSSascha Wildner if (bmi2) {
368a28cd43dSSascha Wildner return FSE_decompress_wksp_body_bmi2(dst, dstCapacity, cSrc, cSrcSize, maxLog, workSpace, wkspSize);
369a28cd43dSSascha Wildner }
370a28cd43dSSascha Wildner #endif
371a28cd43dSSascha Wildner (void)bmi2;
372a28cd43dSSascha Wildner return FSE_decompress_wksp_body_default(dst, dstCapacity, cSrc, cSrcSize, maxLog, workSpace, wkspSize);
373a28cd43dSSascha Wildner }
374a28cd43dSSascha Wildner
375a28cd43dSSascha Wildner
376a28cd43dSSascha Wildner typedef FSE_DTable DTable_max_t[FSE_DTABLE_SIZE_U32(FSE_MAX_TABLELOG)];
377a28cd43dSSascha Wildner
378a28cd43dSSascha Wildner #ifndef ZSTD_NO_UNUSED_FUNCTIONS
FSE_buildDTable(FSE_DTable * dt,const short * normalizedCounter,unsigned maxSymbolValue,unsigned tableLog)379a28cd43dSSascha Wildner size_t FSE_buildDTable(FSE_DTable* dt, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog) {
380a28cd43dSSascha Wildner U32 wksp[FSE_BUILD_DTABLE_WKSP_SIZE_U32(FSE_TABLELOG_ABSOLUTE_MAX, FSE_MAX_SYMBOL_VALUE)];
381a28cd43dSSascha Wildner return FSE_buildDTable_wksp(dt, normalizedCounter, maxSymbolValue, tableLog, wksp, sizeof(wksp));
382a28cd43dSSascha Wildner }
383a28cd43dSSascha Wildner
FSE_decompress(void * dst,size_t dstCapacity,const void * cSrc,size_t cSrcSize)384a28cd43dSSascha Wildner size_t FSE_decompress(void* dst, size_t dstCapacity, const void* cSrc, size_t cSrcSize)
385a28cd43dSSascha Wildner {
386a28cd43dSSascha Wildner /* Static analyzer seems unable to understand this table will be properly initialized later */
387a28cd43dSSascha Wildner U32 wksp[FSE_DECOMPRESS_WKSP_SIZE_U32(FSE_MAX_TABLELOG, FSE_MAX_SYMBOL_VALUE)];
388a28cd43dSSascha Wildner return FSE_decompress_wksp(dst, dstCapacity, cSrc, cSrcSize, FSE_MAX_TABLELOG, wksp, sizeof(wksp));
389a28cd43dSSascha Wildner }
390a28cd43dSSascha Wildner #endif
391a28cd43dSSascha Wildner
392a28cd43dSSascha Wildner
393a28cd43dSSascha Wildner #endif /* FSE_COMMONDEFS_ONLY */
394