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 */
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);
142             U32 const nextState = symbolNext[symbol]++;
143             tableDecode[u].nbBits = (BYTE) (tableLog - BIT_highbit32(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 *********************************************************/
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 
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 
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 */
310