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