]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 | ||
7c673cae FG |
36 | /* ************************************************************** |
37 | * Includes | |
38 | ****************************************************************/ | |
39 | #include <stdlib.h> /* malloc, free, qsort */ | |
40 | #include <string.h> /* memcpy, memset */ | |
7c673cae | 41 | #include "bitstream.h" |
11fdf7f2 | 42 | #include "compiler.h" |
7c673cae FG |
43 | #define FSE_STATIC_LINKING_ONLY |
44 | #include "fse.h" | |
11fdf7f2 | 45 | #include "error_private.h" |
7c673cae FG |
46 | |
47 | ||
48 | /* ************************************************************** | |
49 | * Error Management | |
50 | ****************************************************************/ | |
51 | #define FSE_isError ERR_isError | |
9f95a23c | 52 | #define FSE_STATIC_ASSERT(c) DEBUG_STATIC_ASSERT(c) /* use only *after* variable declarations */ |
7c673cae FG |
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 */ | |
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 | ||
88 | void FSE_freeDTable (FSE_DTable* dt) | |
89 | { | |
90 | free(dt); | |
91 | } | |
92 | ||
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); | |
9f95a23c TL |
142 | U32 const nextState = symbolNext[symbol]++; |
143 | tableDecode[u].nbBits = (BYTE) (tableLog - BIT_highbit32(nextState) ); | |
7c673cae FG |
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 | *********************************************************/ | |
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 | ||
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 | ||
11fdf7f2 | 200 | FORCE_INLINE_TEMPLATE size_t FSE_decompress_usingDTable_generic( |
7c673cae FG |
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 | ||
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 | ||
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 | ||
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 */ |