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