ReactOS 0.4.15-dev-5666-gc548b97
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}
MEM_STATIC unsigned BIT_highbit32(U32 val)
Definition: bitstream.h:139
signed short S16
Definition: mem.h:146
#define ERROR(name)
Definition: error_private.h:53
GLdouble s
Definition: gl.h:2039
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
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 memcpy(s1, s2, n)
Definition: mkisofs.h:878
unsigned char BYTE
Definition: xxhash.c:193
unsigned int U32
Definition: xxhash.c:195
unsigned short U16
Definition: xxhash.c:194

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

◆ 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}

◆ 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}
#define ExAllocatePoolWithTag(hernya, size, tag)
Definition: env_spec_w32.h:350
#define PagedPool
Definition: env_spec_w32.h:308
unsigned FSE_DTable
Definition: fse.h:233
#define FSED_ALLOC_TAG

◆ 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}
size_t FSE_decompress_wksp(void *dst, size_t dstCapacity, const void *cSrc, size_t cSrcSize, FSE_DTable *workSpace, unsigned maxLog)
FSE_DTable DTable_max_t[FSE_DTABLE_SIZE_U32(FSE_MAX_TABLELOG)]
GLenum GLenum dst
Definition: glext.h:6340

◆ 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)

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}
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
@ BIT_DStream_overflow
Definition: bitstream.h:102
@ BIT_DStream_unfinished
Definition: bitstream.h:99
UINT op
Definition: effect.c:236
#define CHECK_F(f)
Definition: error_private.h:62
#define FSE_GETSYMBOL(statePtr)
size_t bitContainer
Definition: bitstream.h:92

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}
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)
size_t FSE_buildDTable(FSE_DTable *dt, const short *normalizedCounter, unsigned maxSymbolValue, unsigned tableLog)
#define FSE_isError
Definition: dhcpd.h:62

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