xref: /dflybsd-src/contrib/zstd/lib/common/fse_decompress.c (revision a28cd43d19e8b720a6c852a4bbc5ae147a26165a)
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