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