ReactOS  0.4.14-dev-323-g6fe6a88
fse_decompress.c
Go to the documentation of this file.
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 
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 
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);
252  *op++ = FSE_GETSYMBOL(&state2);
253  break;
254  }
255 
256  if (op>(omax-2)) return ERROR(dstSize_tooSmall);
257  *op++ = FSE_GETSYMBOL(&state2);
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 */
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble * u
Definition: glfuncs.h:240
unsigned short U16
Definition: mem.h:72
FSE_DTable DTable_max_t[FSE_DTABLE_SIZE_U32(FSE_MAX_TABLELOG)]
#define FSE_isError
FORCE_INLINE_TEMPLATE size_t FSE_decompress_usingDTable_generic(void *dst, size_t maxDstSize, const void *cSrc, size_t cSrcSize, const FSE_DTable *dt, const unsigned fast)
size_t FSE_buildDTable(FSE_DTable *dt, const short *normalizedCounter, unsigned maxSymbolValue, unsigned tableLog)
#define ERROR(name)
Definition: error_private.h:53
size_t FSE_readNCount(short *normalizedCounter, unsigned *maxSVPtr, unsigned *tableLogPtr, const void *headerBuffer, size_t hbSize)
unsigned int U32
Definition: mem.h:77
MEM_STATIC size_t BIT_initDStream(BIT_DStream_t *bitD, const void *srcBuffer, size_t srcSize)
Definition: bitstream.h:287
MEM_STATIC BIT_DStream_status BIT_reloadDStream(BIT_DStream_t *bitD)
Definition: bitstream.h:414
unsigned FSE_DTable
Definition: fse.h:253
MEM_STATIC unsigned BIT_highbit32(U32 val)
Definition: bitstream.h:156
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint i
Definition: glfuncs.h:248
size_t FSE_decompress_usingDTable(void *dst, size_t originalSize, const void *cSrc, size_t cSrcSize, const FSE_DTable *dt)
static PVOID ptr
Definition: dispmode.c:27
#define FSE_GETSYMBOL(statePtr)
#define FSED_ALLOC_TAG
FSE_DTable * FSE_createDTable(unsigned tableLog)
size_t FSE_decompress(void *dst, size_t dstCapacity, const void *cSrc, size_t cSrcSize)
size_t bitContainer
Definition: bitstream.h:109
Definition: dhcpd.h:61
void FSE_freeDTable(FSE_DTable *dt)
#define ExAllocatePoolWithTag(hernya, size, tag)
Definition: env_spec_w32.h:350
#define FORCE_INLINE_TEMPLATE
Definition: compiler.h:37
#define memcpy(s1, s2, n)
Definition: mkisofs.h:878
unsigned char BYTE
Definition: mem.h:68
GLdouble s
Definition: gl.h:2039
#define CHECK_F(f)
size_t FSE_buildDTable_raw(FSE_DTable *dt, unsigned nbBits)
GLenum GLenum dst
Definition: glext.h:6340
size_t FSE_decompress_wksp(void *dst, size_t dstCapacity, const void *cSrc, size_t cSrcSize, FSE_DTable *workSpace, unsigned maxLog)
signed short S16
Definition: mem.h:73
UINT op
Definition: effect.c:223
size_t FSE_buildDTable_rle(FSE_DTable *dt, BYTE symbolValue)
#define ExFreePool(addr)
Definition: env_spec_w32.h:352