ReactOS  0.4.15-dev-1150-g593bcce
fse_decompress.c File Reference
#include <stdlib.h>
#include <string.h>
#include "bitstream.h"
#include "compiler.h"
#include "fse.h"
#include "error_private.h"
#include <ntifs.h>
#include <ntddk.h>
Include dependency graph for fse_decompress.c:

Go to the source code of this file.

Macros

#define FSE_STATIC_LINKING_ONLY
 
#define FSE_isError   ERR_isError
 
#define FSE_STATIC_ASSERT(c)   DEBUG_STATIC_ASSERT(c) /* use only *after* variable declarations */
 
#define CHECK_F(f)   { size_t const e = f; if (FSE_isError(e)) return e; }
 
#define FSE_CAT(X, Y)   X##Y
 
#define FSE_FUNCTION_NAME(X, Y)   FSE_CAT(X,Y)
 
#define FSE_TYPE_NAME(X, Y)   FSE_CAT(X,Y)
 
#define FSED_ALLOC_TAG   0x64455346
 
#define FSE_GETSYMBOL(statePtr)   fast ? FSE_decodeSymbolFast(statePtr, &bitD) : FSE_decodeSymbol(statePtr, &bitD)
 

Typedefs

typedef FSE_DTable DTable_max_t[FSE_DTABLE_SIZE_U32(FSE_MAX_TABLELOG)]
 

Functions

FSE_DTableFSE_createDTable (unsigned tableLog)
 
void FSE_freeDTable (FSE_DTable *dt)
 
size_t FSE_buildDTable (FSE_DTable *dt, const short *normalizedCounter, unsigned maxSymbolValue, unsigned tableLog)
 
size_t FSE_buildDTable_rle (FSE_DTable *dt, BYTE symbolValue)
 
size_t FSE_buildDTable_raw (FSE_DTable *dt, unsigned nbBits)
 
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_decompress_usingDTable (void *dst, size_t originalSize, const void *cSrc, size_t cSrcSize, const FSE_DTable *dt)
 
size_t FSE_decompress_wksp (void *dst, size_t dstCapacity, const void *cSrc, size_t cSrcSize, FSE_DTable *workSpace, unsigned maxLog)
 
size_t FSE_decompress (void *dst, size_t dstCapacity, const void *cSrc, size_t cSrcSize)
 

Macro Definition Documentation

◆ CHECK_F

#define CHECK_F (   f)    { size_t const e = f; if (FSE_isError(e)) return e; }

Definition at line 57 of file fse_decompress.c.

◆ FSE_CAT

#define FSE_CAT (   X,
  Y 
)    X##Y

Definition at line 78 of file fse_decompress.c.

◆ FSE_FUNCTION_NAME

#define FSE_FUNCTION_NAME (   X,
  Y 
)    FSE_CAT(X,Y)

Definition at line 79 of file fse_decompress.c.

◆ FSE_GETSYMBOL

#define FSE_GETSYMBOL (   statePtr)    fast ? FSE_decodeSymbolFast(statePtr, &bitD) : FSE_decodeSymbol(statePtr, &bitD)

◆ FSE_isError

#define FSE_isError   ERR_isError

Definition at line 53 of file fse_decompress.c.

◆ FSE_STATIC_ASSERT

#define FSE_STATIC_ASSERT (   c)    DEBUG_STATIC_ASSERT(c) /* use only *after* variable declarations */

Definition at line 54 of file fse_decompress.c.

◆ FSE_STATIC_LINKING_ONLY

#define FSE_STATIC_LINKING_ONLY

Definition at line 43 of file fse_decompress.c.

◆ FSE_TYPE_NAME

#define FSE_TYPE_NAME (   X,
  Y 
)    FSE_CAT(X,Y)

Definition at line 80 of file fse_decompress.c.

◆ FSED_ALLOC_TAG

#define FSED_ALLOC_TAG   0x64455346

Definition at line 82 of file fse_decompress.c.

Typedef Documentation

◆ DTable_max_t

typedef FSE_DTable DTable_max_t[FSE_DTABLE_SIZE_U32(FSE_MAX_TABLELOG)]

Definition at line 303 of file fse_decompress.c.

Function Documentation

◆ FSE_buildDTable()

size_t FSE_buildDTable ( FSE_DTable dt,
const short normalizedCounter,
unsigned  maxSymbolValue,
unsigned  tableLog 
)

FSE_buildDTable(): Builds 'dt', which must be already allocated, using FSE_createDTable(). return : 0, or an errorCode, which can be tested using FSE_isError()

Definition at line 97 of file fse_decompress.c.

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 }
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
#define ERROR(name)
Definition: error_private.h:53
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
#define memcpy(s1, s2, n)
Definition: mkisofs.h:878
GLdouble s
Definition: gl.h:2039
unsigned char BYTE
Definition: xxhash.c:193
unsigned short U16
Definition: xxhash.c:194
signed short S16
Definition: mem.h:73
unsigned int U32
Definition: xxhash.c:195

Referenced by FSE_decompress_wksp().

◆ FSE_buildDTable_raw()

size_t FSE_buildDTable_raw ( FSE_DTable dt,
unsigned  nbBits 
)

Definition at line 178 of file fse_decompress.c.

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 }
#define ERROR(name)
Definition: error_private.h:53
static PVOID ptr
Definition: dispmode.c:27
GLdouble s
Definition: gl.h:2039
unsigned char BYTE
Definition: xxhash.c:193
unsigned short U16
Definition: xxhash.c:194

◆ FSE_buildDTable_rle()

size_t FSE_buildDTable_rle ( FSE_DTable dt,
BYTE  symbolValue 
)

Definition at line 160 of file fse_decompress.c.

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 }
static PVOID ptr
Definition: dispmode.c:27

◆ FSE_createDTable()

FSE_DTable* FSE_createDTable ( unsigned  tableLog)

Definition at line 86 of file fse_decompress.c.

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 }
unsigned FSE_DTable
Definition: fse.h:253
#define FSED_ALLOC_TAG
#define ExAllocatePoolWithTag(hernya, size, tag)
Definition: env_spec_w32.h:350
unsigned int U32
Definition: xxhash.c:195

◆ FSE_decompress()

size_t FSE_decompress ( void dst,
size_t  dstCapacity,
const void cSrc,
size_t  cSrcSize 
)

FSE_decompress(): Decompress FSE data from buffer 'cSrc', of size 'cSrcSize', into already allocated destination buffer 'dst', of size 'dstCapacity'.

Returns
: size of regenerated data (<= maxDstSize), or an error code, which can be tested using FSE_isError() .

Important ** : FSE_decompress() does not decompress non-compressible nor RLE data !!! Why ? : making this distinction requires a header. Header management is intentionally delegated to the user layer, which can better manage special cases.

Definition at line 305 of file fse_decompress.c.

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 }
FSE_DTable DTable_max_t[FSE_DTABLE_SIZE_U32(FSE_MAX_TABLELOG)]
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)

◆ FSE_decompress_usingDTable()

size_t FSE_decompress_usingDTable ( void dst,
size_t  dstCapacity,
const void cSrc,
size_t  cSrcSize,
const FSE_DTable dt 
)

FSE_decompress_usingDTable(): Decompress compressed source cSrc of size cSrcSize using dt into dst which must be already allocated.

Returns
: size of regenerated data (necessarily <= dstCapacity), or an errorCode, which can be tested using FSE_isError()

Definition at line 267 of file fse_decompress.c.

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 }
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)
static PVOID ptr
Definition: dispmode.c:27
GLenum GLenum dst
Definition: glext.h:6340
unsigned int U32
Definition: xxhash.c:195

Referenced by FSE_decompress_wksp().

◆ FSE_decompress_usingDTable_generic()

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 
)

Definition at line 204 of file fse_decompress.c.

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 }
#define ERROR(name)
Definition: error_private.h:53
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
#define FSE_GETSYMBOL(statePtr)
size_t bitContainer
Definition: bitstream.h:109
UINT op
Definition: effect.c:224
#define CHECK_F(f)
unsigned char BYTE
Definition: xxhash.c:193
GLenum GLenum dst
Definition: glext.h:6340

Referenced by FSE_decompress_usingDTable().

◆ FSE_decompress_wksp()

size_t FSE_decompress_wksp ( void dst,
size_t  dstCapacity,
const void cSrc,
size_t  cSrcSize,
FSE_DTable workSpace,
unsigned  maxLog 
)

Definition at line 281 of file fse_decompress.c.

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 }
#define FSE_isError
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)
size_t FSE_decompress_usingDTable(void *dst, size_t originalSize, const void *cSrc, size_t cSrcSize, const FSE_DTable *dt)
Definition: dhcpd.h:61
#define CHECK_F(f)
unsigned char BYTE
Definition: xxhash.c:193
GLenum GLenum dst
Definition: glext.h:6340

Referenced by FSE_decompress(), and HUF_readStats().

◆ FSE_freeDTable()

void FSE_freeDTable ( FSE_DTable dt)

Definition at line 92 of file fse_decompress.c.

93 {
94  ExFreePool(dt);
95 }
#define ExFreePool(addr)
Definition: env_spec_w32.h:352