ReactOS  0.4.15-dev-5492-g47f3a4e
fse_decompress.c
Go to the documentation of this file.
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 #include <ntifs.h>
27 #include <ntddk.h>
28 
29 
30 /* **************************************************************
31 * Error Management
32 ****************************************************************/
33 #define FSE_isError ERR_isError
34 #define FSE_STATIC_ASSERT(c) DEBUG_STATIC_ASSERT(c) /* use only *after* variable declarations */
35 
36 
37 /* **************************************************************
38 * Templates
39 ****************************************************************/
40 /*
41  designed to be included
42  for type-specific functions (template emulation in C)
43  Objective is to write these functions only once, for improved maintenance
44 */
45 
46 /* safety checks */
47 #ifndef FSE_FUNCTION_EXTENSION
48 # error "FSE_FUNCTION_EXTENSION must be defined"
49 #endif
50 #ifndef FSE_FUNCTION_TYPE
51 # error "FSE_FUNCTION_TYPE must be defined"
52 #endif
53 
54 /* Function names */
55 #define FSE_CAT(X,Y) X##Y
56 #define FSE_FUNCTION_NAME(X,Y) FSE_CAT(X,Y)
57 #define FSE_TYPE_NAME(X,Y) FSE_CAT(X,Y)
58 
59 #define FSED_ALLOC_TAG 0x64455346 // "FSEd"
60 
61 /* Function templates */
62 FSE_DTable* FSE_createDTable (unsigned tableLog)
63 {
64  if (tableLog > FSE_TABLELOG_ABSOLUTE_MAX) tableLog = FSE_TABLELOG_ABSOLUTE_MAX;
65  return (FSE_DTable*)ExAllocatePoolWithTag(PagedPool, FSE_DTABLE_SIZE_U32(tableLog) * sizeof (U32), FSED_ALLOC_TAG);
66 }
67 
69 {
70  ExFreePool(dt);
71 }
72 
73 size_t FSE_buildDTable(FSE_DTable* dt, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog)
74 {
75  void* const tdPtr = dt+1; /* because *dt is unsigned, 32-bits aligned on 32-bits */
76  FSE_DECODE_TYPE* const tableDecode = (FSE_DECODE_TYPE*) (tdPtr);
77  U16 symbolNext[FSE_MAX_SYMBOL_VALUE+1];
78 
79  U32 const maxSV1 = maxSymbolValue + 1;
80  U32 const tableSize = 1 << tableLog;
81  U32 highThreshold = tableSize-1;
82 
83  /* Sanity Checks */
84  if (maxSymbolValue > FSE_MAX_SYMBOL_VALUE) return ERROR(maxSymbolValue_tooLarge);
85  if (tableLog > FSE_MAX_TABLELOG) return ERROR(tableLog_tooLarge);
86 
87  /* Init, lay down lowprob symbols */
88  { FSE_DTableHeader DTableH;
89  DTableH.tableLog = (U16)tableLog;
90  DTableH.fastMode = 1;
91  { S16 const largeLimit= (S16)(1 << (tableLog-1));
92  U32 s;
93  for (s=0; s<maxSV1; s++) {
94  if (normalizedCounter[s]==-1) {
95  tableDecode[highThreshold--].symbol = (FSE_FUNCTION_TYPE)s;
96  symbolNext[s] = 1;
97  } else {
98  if (normalizedCounter[s] >= largeLimit) DTableH.fastMode=0;
99  symbolNext[s] = normalizedCounter[s];
100  } } }
101  memcpy(dt, &DTableH, sizeof(DTableH));
102  }
103 
104  /* Spread symbols */
105  { U32 const tableMask = tableSize-1;
106  U32 const step = FSE_TABLESTEP(tableSize);
107  U32 s, position = 0;
108  for (s=0; s<maxSV1; s++) {
109  int i;
110  for (i=0; i<normalizedCounter[s]; i++) {
111  tableDecode[position].symbol = (FSE_FUNCTION_TYPE)s;
112  position = (position + step) & tableMask;
113  while (position > highThreshold) position = (position + step) & tableMask; /* lowprob area */
114  } }
115  if (position!=0) return ERROR(GENERIC); /* position must reach all cells once, otherwise normalizedCounter is incorrect */
116  }
117 
118  /* Build Decoding table */
119  { U32 u;
120  for (u=0; u<tableSize; u++) {
121  FSE_FUNCTION_TYPE const symbol = (FSE_FUNCTION_TYPE)(tableDecode[u].symbol);
122  U32 const nextState = symbolNext[symbol]++;
123  tableDecode[u].nbBits = (BYTE) (tableLog - BIT_highbit32(nextState) );
124  tableDecode[u].newState = (U16) ( (nextState << tableDecode[u].nbBits) - tableSize);
125  } }
126 
127  return 0;
128 }
129 
130 
131 #ifndef FSE_COMMONDEFS_ONLY
132 
133 /*-*******************************************************
134 * Decompression (Byte symbols)
135 *********************************************************/
136 size_t FSE_buildDTable_rle (FSE_DTable* dt, BYTE symbolValue)
137 {
138  void* ptr = dt;
139  FSE_DTableHeader* const DTableH = (FSE_DTableHeader*)ptr;
140  void* dPtr = dt + 1;
141  FSE_decode_t* const cell = (FSE_decode_t*)dPtr;
142 
143  DTableH->tableLog = 0;
144  DTableH->fastMode = 0;
145 
146  cell->newState = 0;
147  cell->symbol = symbolValue;
148  cell->nbBits = 0;
149 
150  return 0;
151 }
152 
153 
154 size_t FSE_buildDTable_raw (FSE_DTable* dt, unsigned nbBits)
155 {
156  void* ptr = dt;
157  FSE_DTableHeader* const DTableH = (FSE_DTableHeader*)ptr;
158  void* dPtr = dt + 1;
159  FSE_decode_t* const dinfo = (FSE_decode_t*)dPtr;
160  const unsigned tableSize = 1 << nbBits;
161  const unsigned tableMask = tableSize - 1;
162  const unsigned maxSV1 = tableMask+1;
163  unsigned s;
164 
165  /* Sanity checks */
166  if (nbBits < 1) return ERROR(GENERIC); /* min size */
167 
168  /* Build Decoding Table */
169  DTableH->tableLog = (U16)nbBits;
170  DTableH->fastMode = 1;
171  for (s=0; s<maxSV1; s++) {
172  dinfo[s].newState = 0;
173  dinfo[s].symbol = (BYTE)s;
174  dinfo[s].nbBits = (BYTE)nbBits;
175  }
176 
177  return 0;
178 }
179 
181  void* dst, size_t maxDstSize,
182  const void* cSrc, size_t cSrcSize,
183  const FSE_DTable* dt, const unsigned fast)
184 {
185  BYTE* const ostart = (BYTE*) dst;
186  BYTE* op = ostart;
187  BYTE* const omax = op + maxDstSize;
188  BYTE* const olimit = omax-3;
189 
190  BIT_DStream_t bitD;
191  FSE_DState_t state1;
192  FSE_DState_t state2;
193 
194  /* Init */
195  CHECK_F(BIT_initDStream(&bitD, cSrc, cSrcSize));
196 
197  FSE_initDState(&state1, &bitD, dt);
198  FSE_initDState(&state2, &bitD, dt);
199 
200 #define FSE_GETSYMBOL(statePtr) fast ? FSE_decodeSymbolFast(statePtr, &bitD) : FSE_decodeSymbol(statePtr, &bitD)
201 
202  /* 4 symbols per loop */
203  for ( ; (BIT_reloadDStream(&bitD)==BIT_DStream_unfinished) & (op<olimit) ; op+=4) {
204  op[0] = FSE_GETSYMBOL(&state1);
205 
206  if (FSE_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */
207  BIT_reloadDStream(&bitD);
208 
209  op[1] = FSE_GETSYMBOL(&state2);
210 
211  if (FSE_MAX_TABLELOG*4+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */
212  { if (BIT_reloadDStream(&bitD) > BIT_DStream_unfinished) { op+=2; break; } }
213 
214  op[2] = FSE_GETSYMBOL(&state1);
215 
216  if (FSE_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */
217  BIT_reloadDStream(&bitD);
218 
219  op[3] = FSE_GETSYMBOL(&state2);
220  }
221 
222  /* tail */
223  /* note : BIT_reloadDStream(&bitD) >= FSE_DStream_partiallyFilled; Ends at exactly BIT_DStream_completed */
224  while (1) {
225  if (op>(omax-2)) return ERROR(dstSize_tooSmall);
226  *op++ = FSE_GETSYMBOL(&state1);
228  *op++ = FSE_GETSYMBOL(&state2);
229  break;
230  }
231 
232  if (op>(omax-2)) return ERROR(dstSize_tooSmall);
233  *op++ = FSE_GETSYMBOL(&state2);
235  *op++ = FSE_GETSYMBOL(&state1);
236  break;
237  } }
238 
239  return op-ostart;
240 }
241 
242 
243 size_t FSE_decompress_usingDTable(void* dst, size_t originalSize,
244  const void* cSrc, size_t cSrcSize,
245  const FSE_DTable* dt)
246 {
247  const void* ptr = dt;
248  const FSE_DTableHeader* DTableH = (const FSE_DTableHeader*)ptr;
249  const U32 fastMode = DTableH->fastMode;
250 
251  /* select fast mode (static) */
252  if (fastMode) return FSE_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 1);
253  return FSE_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 0);
254 }
255 
256 
257 size_t FSE_decompress_wksp(void* dst, size_t dstCapacity, const void* cSrc, size_t cSrcSize, FSE_DTable* workSpace, unsigned maxLog)
258 {
259  const BYTE* const istart = (const BYTE*)cSrc;
260  const BYTE* ip = istart;
261  short counting[FSE_MAX_SYMBOL_VALUE+1];
262  unsigned tableLog;
263  unsigned maxSymbolValue = FSE_MAX_SYMBOL_VALUE;
264 
265  /* normal FSE decoding mode */
266  size_t const NCountLength = FSE_readNCount (counting, &maxSymbolValue, &tableLog, istart, cSrcSize);
267  if (FSE_isError(NCountLength)) return NCountLength;
268  /* if (NCountLength >= cSrcSize) return ERROR(srcSize_wrong); */ /* too small input size; supposed to be already checked in NCountLength, only remaining case : NCountLength==cSrcSize */
269  if (tableLog > maxLog) return ERROR(tableLog_tooLarge);
270  ip += NCountLength;
271  cSrcSize -= NCountLength;
272 
273  CHECK_F( FSE_buildDTable (workSpace, counting, maxSymbolValue, tableLog) );
274 
275  return FSE_decompress_usingDTable (dst, dstCapacity, ip, cSrcSize, workSpace); /* always return, even if it is an error code */
276 }
277 
278 
279 typedef FSE_DTable DTable_max_t[FSE_DTABLE_SIZE_U32(FSE_MAX_TABLELOG)];
280 
281 size_t FSE_decompress(void* dst, size_t dstCapacity, const void* cSrc, size_t cSrcSize)
282 {
283  DTable_max_t dt; /* Static analyzer seems unable to understand this table will be properly initialized later */
284  return FSE_decompress_wksp(dst, dstCapacity, cSrc, cSrcSize, dt, FSE_MAX_TABLELOG);
285 }
286 
287 
288 
289 #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
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)
#define CHECK_F(f)
Definition: error_private.h:62
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)
MEM_STATIC size_t BIT_initDStream(BIT_DStream_t *bitD, const void *srcBuffer, size_t srcSize)
Definition: bitstream.h:272
MEM_STATIC BIT_DStream_status BIT_reloadDStream(BIT_DStream_t *bitD)
Definition: bitstream.h:416
unsigned FSE_DTable
Definition: fse.h:233
MEM_STATIC unsigned BIT_highbit32(U32 val)
Definition: bitstream.h:139
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:92
Definition: dhcpd.h:61
UINT op
Definition: effect.c:236
void FSE_freeDTable(FSE_DTable *dt)
#define ExAllocatePoolWithTag(hernya, size, tag)
Definition: env_spec_w32.h:350
#define memcpy(s1, s2, n)
Definition: mkisofs.h:878
GLdouble s
Definition: gl.h:2039
size_t FSE_buildDTable_raw(FSE_DTable *dt, unsigned nbBits)
unsigned char BYTE
Definition: xxhash.c:193
unsigned short U16
Definition: xxhash.c:194
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
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:146
unsigned int U32
Definition: xxhash.c:195
size_t FSE_buildDTable_rle(FSE_DTable *dt, BYTE symbolValue)
#define ExFreePool(addr)
Definition: env_spec_w32.h:352
#define FORCE_INLINE_TEMPLATE
Definition: xxhash.c:172