1 // SPDX-License-Identifier: (GPL-2.0 or BSD-2-Clause)
2 /*
3 * FSE : Finite State Entropy decoder
4 * Copyright (C) 2013-2015, Yann Collet.
5 *
6 * You can contact the author at :
7 * - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
8 */
9
10 /* **************************************************************
11 * Compiler specifics
12 ****************************************************************/
13 #define FORCE_INLINE static __always_inline
14
15 /* **************************************************************
16 * Includes
17 ****************************************************************/
18 #include "bitstream.h"
19 #include "fse.h"
20 #include <linux/compiler.h>
21 #include <linux/kernel.h>
22 #include <linux/string.h> /* memcpy, memset */
23
24 /* **************************************************************
25 * Error Management
26 ****************************************************************/
27 #define FSE_isError ERR_isError
28 #define FSE_STATIC_ASSERT(c) \
29 { \
30 enum { FSE_static_assert = 1 / (int)(!!(c)) }; \
31 } /* use only *after* variable declarations */
32
33 /* check and forward error code */
34 #define CHECK_F(f) \
35 { \
36 size_t const e = f; \
37 if (FSE_isError(e)) \
38 return e; \
39 }
40
41 /* **************************************************************
42 * Templates
43 ****************************************************************/
44 /*
45 designed to be included
46 for type-specific functions (template emulation in C)
47 Objective is to write these functions only once, for improved maintenance
48 */
49
50 /* safety checks */
51 #ifndef FSE_FUNCTION_EXTENSION
52 #error "FSE_FUNCTION_EXTENSION must be defined"
53 #endif
54 #ifndef FSE_FUNCTION_TYPE
55 #error "FSE_FUNCTION_TYPE must be defined"
56 #endif
57
58 /* Function names */
59 #define FSE_CAT(X, Y) X##Y
60 #define FSE_FUNCTION_NAME(X, Y) FSE_CAT(X, Y)
61 #define FSE_TYPE_NAME(X, Y) FSE_CAT(X, Y)
62
63 /* Function templates */
64
FSE_buildDTable_wksp(FSE_DTable * dt,const short * normalizedCounter,unsigned maxSymbolValue,unsigned tableLog,void * workspace,size_t workspaceSize)65 size_t FSE_buildDTable_wksp(FSE_DTable *dt, const short *normalizedCounter, unsigned maxSymbolValue, unsigned tableLog, void *workspace, size_t workspaceSize)
66 {
67 void *const tdPtr = dt + 1; /* because *dt is unsigned, 32-bits aligned on 32-bits */
68 FSE_DECODE_TYPE *const tableDecode = (FSE_DECODE_TYPE *)(tdPtr);
69 U16 *symbolNext = (U16 *)workspace;
70
71 U32 const maxSV1 = maxSymbolValue + 1;
72 U32 const tableSize = 1 << tableLog;
73 U32 highThreshold = tableSize - 1;
74
75 /* Sanity Checks */
76 if (workspaceSize < sizeof(U16) * (FSE_MAX_SYMBOL_VALUE + 1))
77 return ERROR(tableLog_tooLarge);
78 if (maxSymbolValue > FSE_MAX_SYMBOL_VALUE)
79 return ERROR(maxSymbolValue_tooLarge);
80 if (tableLog > FSE_MAX_TABLELOG)
81 return ERROR(tableLog_tooLarge);
82
83 /* Init, lay down lowprob symbols */
84 {
85 FSE_DTableHeader DTableH;
86 DTableH.tableLog = (U16)tableLog;
87 DTableH.fastMode = 1;
88 {
89 S16 const largeLimit = (S16)(1 << (tableLog - 1));
90 U32 s;
91 for (s = 0; s < maxSV1; s++) {
92 if (normalizedCounter[s] == -1) {
93 tableDecode[highThreshold--].symbol = (FSE_FUNCTION_TYPE)s;
94 symbolNext[s] = 1;
95 } else {
96 if (normalizedCounter[s] >= largeLimit)
97 DTableH.fastMode = 0;
98 symbolNext[s] = normalizedCounter[s];
99 }
100 }
101 }
102 memcpy(dt, &DTableH, sizeof(DTableH));
103 }
104
105 /* Spread symbols */
106 {
107 U32 const tableMask = tableSize - 1;
108 U32 const step = FSE_TABLESTEP(tableSize);
109 U32 s, position = 0;
110 for (s = 0; s < maxSV1; s++) {
111 int i;
112 for (i = 0; i < normalizedCounter[s]; i++) {
113 tableDecode[position].symbol = (FSE_FUNCTION_TYPE)s;
114 position = (position + step) & tableMask;
115 while (position > highThreshold)
116 position = (position + step) & tableMask; /* lowprob area */
117 }
118 }
119 if (position != 0)
120 return ERROR(GENERIC); /* position must reach all cells once, otherwise normalizedCounter is incorrect */
121 }
122
123 /* Build Decoding table */
124 {
125 U32 u;
126 for (u = 0; u < tableSize; u++) {
127 FSE_FUNCTION_TYPE const symbol = (FSE_FUNCTION_TYPE)(tableDecode[u].symbol);
128 U16 nextState = symbolNext[symbol]++;
129 tableDecode[u].nbBits = (BYTE)(tableLog - BIT_highbit32((U32)nextState));
130 tableDecode[u].newState = (U16)((nextState << tableDecode[u].nbBits) - tableSize);
131 }
132 }
133
134 return 0;
135 }
136
137 /*-*******************************************************
138 * Decompression (Byte symbols)
139 *********************************************************/
FSE_buildDTable_rle(FSE_DTable * dt,BYTE symbolValue)140 size_t FSE_buildDTable_rle(FSE_DTable *dt, BYTE symbolValue)
141 {
142 void *ptr = dt;
143 FSE_DTableHeader *const DTableH = (FSE_DTableHeader *)ptr;
144 void *dPtr = dt + 1;
145 FSE_decode_t *const cell = (FSE_decode_t *)dPtr;
146
147 DTableH->tableLog = 0;
148 DTableH->fastMode = 0;
149
150 cell->newState = 0;
151 cell->symbol = symbolValue;
152 cell->nbBits = 0;
153
154 return 0;
155 }
156
FSE_buildDTable_raw(FSE_DTable * dt,unsigned nbBits)157 size_t FSE_buildDTable_raw(FSE_DTable *dt, unsigned nbBits)
158 {
159 void *ptr = dt;
160 FSE_DTableHeader *const DTableH = (FSE_DTableHeader *)ptr;
161 void *dPtr = dt + 1;
162 FSE_decode_t *const dinfo = (FSE_decode_t *)dPtr;
163 const unsigned tableSize = 1 << nbBits;
164 const unsigned tableMask = tableSize - 1;
165 const unsigned maxSV1 = tableMask + 1;
166 unsigned s;
167
168 /* Sanity checks */
169 if (nbBits < 1)
170 return ERROR(GENERIC); /* min size */
171
172 /* Build Decoding Table */
173 DTableH->tableLog = (U16)nbBits;
174 DTableH->fastMode = 1;
175 for (s = 0; s < maxSV1; s++) {
176 dinfo[s].newState = 0;
177 dinfo[s].symbol = (BYTE)s;
178 dinfo[s].nbBits = (BYTE)nbBits;
179 }
180
181 return 0;
182 }
183
FSE_decompress_usingDTable_generic(void * dst,size_t maxDstSize,const void * cSrc,size_t cSrcSize,const FSE_DTable * dt,const unsigned fast)184 FORCE_INLINE size_t FSE_decompress_usingDTable_generic(void *dst, size_t maxDstSize, const void *cSrc, size_t cSrcSize, const FSE_DTable *dt,
185 const unsigned fast)
186 {
187 BYTE *const ostart = (BYTE *)dst;
188 BYTE *op = ostart;
189 BYTE *const omax = op + maxDstSize;
190 BYTE *const olimit = omax - 3;
191
192 BIT_DStream_t bitD;
193 FSE_DState_t state1;
194 FSE_DState_t state2;
195
196 /* Init */
197 CHECK_F(BIT_initDStream(&bitD, cSrc, cSrcSize));
198
199 FSE_initDState(&state1, &bitD, dt);
200 FSE_initDState(&state2, &bitD, dt);
201
202 #define FSE_GETSYMBOL(statePtr) fast ? FSE_decodeSymbolFast(statePtr, &bitD) : FSE_decodeSymbol(statePtr, &bitD)
203
204 /* 4 symbols per loop */
205 for (; (BIT_reloadDStream(&bitD) == BIT_DStream_unfinished) & (op < olimit); op += 4) {
206 op[0] = FSE_GETSYMBOL(&state1);
207
208 if (FSE_MAX_TABLELOG * 2 + 7 > sizeof(bitD.bitContainer) * 8) /* This test must be static */
209 BIT_reloadDStream(&bitD);
210
211 op[1] = FSE_GETSYMBOL(&state2);
212
213 if (FSE_MAX_TABLELOG * 4 + 7 > sizeof(bitD.bitContainer) * 8) /* This test must be static */
214 {
215 if (BIT_reloadDStream(&bitD) > BIT_DStream_unfinished) {
216 op += 2;
217 break;
218 }
219 }
220
221 op[2] = FSE_GETSYMBOL(&state1);
222
223 if (FSE_MAX_TABLELOG * 2 + 7 > sizeof(bitD.bitContainer) * 8) /* This test must be static */
224 BIT_reloadDStream(&bitD);
225
226 op[3] = FSE_GETSYMBOL(&state2);
227 }
228
229 /* tail */
230 /* note : BIT_reloadDStream(&bitD) >= FSE_DStream_partiallyFilled; Ends at exactly BIT_DStream_completed */
231 while (1) {
232 if (op > (omax - 2))
233 return ERROR(dstSize_tooSmall);
234 *op++ = FSE_GETSYMBOL(&state1);
235 if (BIT_reloadDStream(&bitD) == BIT_DStream_overflow) {
236 *op++ = FSE_GETSYMBOL(&state2);
237 break;
238 }
239
240 if (op > (omax - 2))
241 return ERROR(dstSize_tooSmall);
242 *op++ = FSE_GETSYMBOL(&state2);
243 if (BIT_reloadDStream(&bitD) == BIT_DStream_overflow) {
244 *op++ = FSE_GETSYMBOL(&state1);
245 break;
246 }
247 }
248
249 return op - ostart;
250 }
251
FSE_decompress_usingDTable(void * dst,size_t originalSize,const void * cSrc,size_t cSrcSize,const FSE_DTable * dt)252 size_t FSE_decompress_usingDTable(void *dst, size_t originalSize, const void *cSrc, size_t cSrcSize, const FSE_DTable *dt)
253 {
254 const void *ptr = dt;
255 const FSE_DTableHeader *DTableH = (const FSE_DTableHeader *)ptr;
256 const U32 fastMode = DTableH->fastMode;
257
258 /* select fast mode (static) */
259 if (fastMode)
260 return FSE_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 1);
261 return FSE_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 0);
262 }
263
FSE_decompress_wksp(void * dst,size_t dstCapacity,const void * cSrc,size_t cSrcSize,unsigned maxLog,void * workspace,size_t workspaceSize)264 size_t FSE_decompress_wksp(void *dst, size_t dstCapacity, const void *cSrc, size_t cSrcSize, unsigned maxLog, void *workspace, size_t workspaceSize)
265 {
266 const BYTE *const istart = (const BYTE *)cSrc;
267 const BYTE *ip = istart;
268 unsigned tableLog;
269 unsigned maxSymbolValue = FSE_MAX_SYMBOL_VALUE;
270 size_t NCountLength;
271
272 FSE_DTable *dt;
273 short *counting;
274 size_t spaceUsed32 = 0;
275
276 FSE_STATIC_ASSERT(sizeof(FSE_DTable) == sizeof(U32));
277
278 dt = (FSE_DTable *)((U32 *)workspace + spaceUsed32);
279 spaceUsed32 += FSE_DTABLE_SIZE_U32(maxLog);
280 counting = (short *)((U32 *)workspace + spaceUsed32);
281 spaceUsed32 += ALIGN(sizeof(short) * (FSE_MAX_SYMBOL_VALUE + 1), sizeof(U32)) >> 2;
282
283 if ((spaceUsed32 << 2) > workspaceSize)
284 return ERROR(tableLog_tooLarge);
285 workspace = (U32 *)workspace + spaceUsed32;
286 workspaceSize -= (spaceUsed32 << 2);
287
288 /* normal FSE decoding mode */
289 NCountLength = FSE_readNCount(counting, &maxSymbolValue, &tableLog, istart, cSrcSize);
290 if (FSE_isError(NCountLength))
291 return NCountLength;
292 // if (NCountLength >= cSrcSize) return ERROR(srcSize_wrong); /* too small input size; supposed to be already checked in NCountLength, only remaining
293 // case : NCountLength==cSrcSize */
294 if (tableLog > maxLog)
295 return ERROR(tableLog_tooLarge);
296 ip += NCountLength;
297 cSrcSize -= NCountLength;
298
299 CHECK_F(FSE_buildDTable_wksp(dt, counting, maxSymbolValue, tableLog, workspace, workspaceSize));
300
301 return FSE_decompress_usingDTable(dst, dstCapacity, ip, cSrcSize, dt); /* always return, even if it is an error code */
302 }
303