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