1 /*
2 * FSE : Finite State Entropy decoder
3 * Copyright (C) 2013-2015, Yann Collet.
4 *
5 * BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions are
9 * met:
10 *
11 * * Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * * Redistributions in binary form must reproduce the above
14 * copyright notice, this list of conditions and the following disclaimer
15 * in the documentation and/or other materials provided with the
16 * distribution.
17 *
18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
19 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
20 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
21 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
22 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
23 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
24 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 *
30 * This program is free software; you can redistribute it and/or modify it under
31 * the terms of the GNU General Public License version 2 as published by the
32 * Free Software Foundation. This program is dual-licensed; you may select
33 * either version 2 of the GNU General Public License ("GPL") or BSD license
34 * ("BSD").
35 *
36 * You can contact the author at :
37 * - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
38 */
39
40 /* **************************************************************
41 * Compiler specifics
42 ****************************************************************/
43 #define FORCE_INLINE static always_inline
44
45 /* **************************************************************
46 * Includes
47 ****************************************************************/
48 #include "bitstream.h"
49 #include "fse.h"
50 #include "zstd_internal.h"
51
52 /* **************************************************************
53 * Error Management
54 ****************************************************************/
55 #define FSE_isError ERR_isError
56 #define FSE_STATIC_ASSERT(c) \
57 { \
58 enum { FSE_static_assert = 1 / (int)(!!(c)) }; \
59 } /* use only *after* variable declarations */
60
61 /* **************************************************************
62 * Templates
63 ****************************************************************/
64 /*
65 designed to be included
66 for type-specific functions (template emulation in C)
67 Objective is to write these functions only once, for improved maintenance
68 */
69
70 /* safety checks */
71 #ifndef FSE_FUNCTION_EXTENSION
72 #error "FSE_FUNCTION_EXTENSION must be defined"
73 #endif
74 #ifndef FSE_FUNCTION_TYPE
75 #error "FSE_FUNCTION_TYPE must be defined"
76 #endif
77
78 /* Function names */
79 #define FSE_CAT(X, Y) X##Y
80 #define FSE_FUNCTION_NAME(X, Y) FSE_CAT(X, Y)
81 #define FSE_TYPE_NAME(X, Y) FSE_CAT(X, Y)
82
83 /* Function templates */
84
FSE_buildDTable_wksp(FSE_DTable * dt,const short * normalizedCounter,unsigned maxSymbolValue,unsigned tableLog,void * workspace,size_t workspaceSize)85 size_t __init FSE_buildDTable_wksp(FSE_DTable *dt, const short *normalizedCounter, unsigned maxSymbolValue, unsigned tableLog, void *workspace, size_t workspaceSize)
86 {
87 void *const tdPtr = dt + 1; /* because *dt is unsigned, 32-bits aligned on 32-bits */
88 FSE_DECODE_TYPE *const tableDecode = (FSE_DECODE_TYPE *)(tdPtr);
89 U16 *symbolNext = (U16 *)workspace;
90
91 U32 const maxSV1 = maxSymbolValue + 1;
92 U32 const tableSize = 1 << tableLog;
93 U32 highThreshold = tableSize - 1;
94
95 /* Sanity Checks */
96 if (workspaceSize < sizeof(U16) * (FSE_MAX_SYMBOL_VALUE + 1))
97 return ERROR(tableLog_tooLarge);
98 if (maxSymbolValue > FSE_MAX_SYMBOL_VALUE)
99 return ERROR(maxSymbolValue_tooLarge);
100 if (tableLog > FSE_MAX_TABLELOG)
101 return ERROR(tableLog_tooLarge);
102
103 /* Init, lay down lowprob symbols */
104 {
105 FSE_DTableHeader DTableH;
106 DTableH.tableLog = (U16)tableLog;
107 DTableH.fastMode = 1;
108 {
109 S16 const largeLimit = (S16)(1 << (tableLog - 1));
110 U32 s;
111 for (s = 0; s < maxSV1; s++) {
112 if (normalizedCounter[s] == -1) {
113 tableDecode[highThreshold--].symbol = (FSE_FUNCTION_TYPE)s;
114 symbolNext[s] = 1;
115 } else {
116 if (normalizedCounter[s] >= largeLimit)
117 DTableH.fastMode = 0;
118 symbolNext[s] = normalizedCounter[s];
119 }
120 }
121 }
122 memcpy(dt, &DTableH, sizeof(DTableH));
123 }
124
125 /* Spread symbols */
126 {
127 U32 const tableMask = tableSize - 1;
128 U32 const step = FSE_TABLESTEP(tableSize);
129 U32 s, position = 0;
130 for (s = 0; s < maxSV1; s++) {
131 int i;
132 for (i = 0; i < normalizedCounter[s]; i++) {
133 tableDecode[position].symbol = (FSE_FUNCTION_TYPE)s;
134 position = (position + step) & tableMask;
135 while (position > highThreshold)
136 position = (position + step) & tableMask; /* lowprob area */
137 }
138 }
139 if (position != 0)
140 return ERROR(GENERIC); /* position must reach all cells once, otherwise normalizedCounter is incorrect */
141 }
142
143 /* Build Decoding table */
144 {
145 U32 u;
146 for (u = 0; u < tableSize; u++) {
147 FSE_FUNCTION_TYPE const symbol = (FSE_FUNCTION_TYPE)(tableDecode[u].symbol);
148 U16 nextState = symbolNext[symbol]++;
149 tableDecode[u].nbBits = (BYTE)(tableLog - BIT_highbit32((U32)nextState));
150 tableDecode[u].newState = (U16)((nextState << tableDecode[u].nbBits) - tableSize);
151 }
152 }
153
154 return 0;
155 }
156
157 /*-*******************************************************
158 * Decompression (Byte symbols)
159 *********************************************************/
FSE_buildDTable_rle(FSE_DTable * dt,BYTE symbolValue)160 size_t __init FSE_buildDTable_rle(FSE_DTable *dt, BYTE symbolValue)
161 {
162 void *ptr = dt;
163 FSE_DTableHeader *const DTableH = (FSE_DTableHeader *)ptr;
164 void *dPtr = dt + 1;
165 FSE_decode_t *const cell = (FSE_decode_t *)dPtr;
166
167 DTableH->tableLog = 0;
168 DTableH->fastMode = 0;
169
170 cell->newState = 0;
171 cell->symbol = symbolValue;
172 cell->nbBits = 0;
173
174 return 0;
175 }
176
FSE_buildDTable_raw(FSE_DTable * dt,unsigned nbBits)177 size_t __init FSE_buildDTable_raw(FSE_DTable *dt, unsigned nbBits)
178 {
179 void *ptr = dt;
180 FSE_DTableHeader *const DTableH = (FSE_DTableHeader *)ptr;
181 void *dPtr = dt + 1;
182 FSE_decode_t *const dinfo = (FSE_decode_t *)dPtr;
183 const unsigned tableSize = 1 << nbBits;
184 const unsigned tableMask = tableSize - 1;
185 const unsigned maxSV1 = tableMask + 1;
186 unsigned s;
187
188 /* Sanity checks */
189 if (nbBits < 1)
190 return ERROR(GENERIC); /* min size */
191
192 /* Build Decoding Table */
193 DTableH->tableLog = (U16)nbBits;
194 DTableH->fastMode = 1;
195 for (s = 0; s < maxSV1; s++) {
196 dinfo[s].newState = 0;
197 dinfo[s].symbol = (BYTE)s;
198 dinfo[s].nbBits = (BYTE)nbBits;
199 }
200
201 return 0;
202 }
203
FSE_decompress_usingDTable_generic(void * dst,size_t maxDstSize,const void * cSrc,size_t cSrcSize,const FSE_DTable * dt,const unsigned fast)204 FORCE_INLINE size_t FSE_decompress_usingDTable_generic(void *dst, size_t maxDstSize, const void *cSrc, size_t cSrcSize, const FSE_DTable *dt,
205 const unsigned fast)
206 {
207 BYTE *const ostart = (BYTE *)dst;
208 BYTE *op = ostart;
209 BYTE *const omax = op + maxDstSize;
210 BYTE *const olimit = omax - 3;
211
212 BIT_DStream_t bitD;
213 FSE_DState_t state1;
214 FSE_DState_t state2;
215
216 /* Init */
217 CHECK_F(BIT_initDStream(&bitD, cSrc, cSrcSize));
218
219 FSE_initDState(&state1, &bitD, dt);
220 FSE_initDState(&state2, &bitD, dt);
221
222 #define FSE_GETSYMBOL(statePtr) fast ? FSE_decodeSymbolFast(statePtr, &bitD) : FSE_decodeSymbol(statePtr, &bitD)
223
224 /* 4 symbols per loop */
225 for (; (BIT_reloadDStream(&bitD) == BIT_DStream_unfinished) & (op < olimit); op += 4) {
226 op[0] = FSE_GETSYMBOL(&state1);
227
228 if (FSE_MAX_TABLELOG * 2 + 7 > sizeof(bitD.bitContainer) * 8) /* This test must be static */
229 BIT_reloadDStream(&bitD);
230
231 op[1] = FSE_GETSYMBOL(&state2);
232
233 if (FSE_MAX_TABLELOG * 4 + 7 > sizeof(bitD.bitContainer) * 8) /* This test must be static */
234 {
235 if (BIT_reloadDStream(&bitD) > BIT_DStream_unfinished) {
236 op += 2;
237 break;
238 }
239 }
240
241 op[2] = FSE_GETSYMBOL(&state1);
242
243 if (FSE_MAX_TABLELOG * 2 + 7 > sizeof(bitD.bitContainer) * 8) /* This test must be static */
244 BIT_reloadDStream(&bitD);
245
246 op[3] = FSE_GETSYMBOL(&state2);
247 }
248
249 /* tail */
250 /* note : BIT_reloadDStream(&bitD) >= FSE_DStream_partiallyFilled; Ends at exactly BIT_DStream_completed */
251 while (1) {
252 if (op > (omax - 2))
253 return ERROR(dstSize_tooSmall);
254 *op++ = FSE_GETSYMBOL(&state1);
255 if (BIT_reloadDStream(&bitD) == BIT_DStream_overflow) {
256 *op++ = FSE_GETSYMBOL(&state2);
257 break;
258 }
259
260 if (op > (omax - 2))
261 return ERROR(dstSize_tooSmall);
262 *op++ = FSE_GETSYMBOL(&state2);
263 if (BIT_reloadDStream(&bitD) == BIT_DStream_overflow) {
264 *op++ = FSE_GETSYMBOL(&state1);
265 break;
266 }
267 }
268
269 return op - ostart;
270 }
271
FSE_decompress_usingDTable(void * dst,size_t originalSize,const void * cSrc,size_t cSrcSize,const FSE_DTable * dt)272 size_t __init FSE_decompress_usingDTable(void *dst, size_t originalSize, const void *cSrc, size_t cSrcSize, const FSE_DTable *dt)
273 {
274 const void *ptr = dt;
275 const FSE_DTableHeader *DTableH = (const FSE_DTableHeader *)ptr;
276 const U32 fastMode = DTableH->fastMode;
277
278 /* select fast mode (static) */
279 if (fastMode)
280 return FSE_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 1);
281 return FSE_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 0);
282 }
283
FSE_decompress_wksp(void * dst,size_t dstCapacity,const void * cSrc,size_t cSrcSize,unsigned maxLog,void * workspace,size_t workspaceSize)284 size_t __init FSE_decompress_wksp(void *dst, size_t dstCapacity, const void *cSrc, size_t cSrcSize, unsigned maxLog, void *workspace, size_t workspaceSize)
285 {
286 const BYTE *const istart = (const BYTE *)cSrc;
287 const BYTE *ip = istart;
288 unsigned tableLog;
289 unsigned maxSymbolValue = FSE_MAX_SYMBOL_VALUE;
290 size_t NCountLength;
291
292 FSE_DTable *dt;
293 short *counting;
294 size_t spaceUsed32 = 0;
295
296 FSE_STATIC_ASSERT(sizeof(FSE_DTable) == sizeof(U32));
297
298 dt = (FSE_DTable *)((U32 *)workspace + spaceUsed32);
299 spaceUsed32 += FSE_DTABLE_SIZE_U32(maxLog);
300 counting = (short *)((U32 *)workspace + spaceUsed32);
301 spaceUsed32 += ALIGN(sizeof(short) * (FSE_MAX_SYMBOL_VALUE + 1), sizeof(U32)) >> 2;
302
303 if ((spaceUsed32 << 2) > workspaceSize)
304 return ERROR(tableLog_tooLarge);
305 workspace = (U32 *)workspace + spaceUsed32;
306 workspaceSize -= (spaceUsed32 << 2);
307
308 /* normal FSE decoding mode */
309 NCountLength = FSE_readNCount(counting, &maxSymbolValue, &tableLog, istart, cSrcSize);
310 if (FSE_isError(NCountLength))
311 return NCountLength;
312 // if (NCountLength >= cSrcSize) return ERROR(srcSize_wrong); /* too small input size; supposed to be already checked in NCountLength, only remaining
313 // case : NCountLength==cSrcSize */
314 if (tableLog > maxLog)
315 return ERROR(tableLog_tooLarge);
316 ip += NCountLength;
317 cSrcSize -= NCountLength;
318
319 CHECK_F(FSE_buildDTable_wksp(dt, counting, maxSymbolValue, tableLog, workspace, workspaceSize));
320
321 return FSE_decompress_usingDTable(dst, dstCapacity, ip, cSrcSize, dt); /* always return, even if it is an error code */
322 }
323