ReactOS  0.4.15-dev-5112-g22d8c0f
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 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

◆ FSE_CAT

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

Definition at line 55 of file fse_decompress.c.

◆ FSE_FUNCTION_NAME

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

Definition at line 56 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 33 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 34 of file fse_decompress.c.

◆ FSE_STATIC_LINKING_ONLY

#define FSE_STATIC_LINKING_ONLY

Definition at line 23 of file fse_decompress.c.

◆ FSE_TYPE_NAME

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

Definition at line 57 of file fse_decompress.c.

◆ FSED_ALLOC_TAG

#define FSED_ALLOC_TAG   0x64455346

Definition at line 59 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 279 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 73 of file fse_decompress.c.

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 }
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:139
#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
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
signed short S16
Definition: mem.h:146
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 154 of file fse_decompress.c.

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 }
#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 136 of file fse_decompress.c.

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

◆ FSE_createDTable()

FSE_DTable* FSE_createDTable ( unsigned  tableLog)

Definition at line 62 of file fse_decompress.c.

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 }
unsigned FSE_DTable
Definition: fse.h:233
#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 281 of file fse_decompress.c.

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 }
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 243 of file fse_decompress.c.

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 }
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 180 of file fse_decompress.c.

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 }
#define CHECK_F(f)
Definition: error_private.h:62
#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:272
MEM_STATIC BIT_DStream_status BIT_reloadDStream(BIT_DStream_t *bitD)
Definition: bitstream.h:416
#define FSE_GETSYMBOL(statePtr)
size_t bitContainer
Definition: bitstream.h:92
UINT op
Definition: effect.c:236
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 257 of file fse_decompress.c.

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 }
#define FSE_isError
#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)
size_t FSE_decompress_usingDTable(void *dst, size_t originalSize, const void *cSrc, size_t cSrcSize, const FSE_DTable *dt)
Definition: dhcpd.h:61
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 68 of file fse_decompress.c.

69 {
70  ExFreePool(dt);
71 }
#define ExFreePool(addr)
Definition: env_spec_w32.h:352