ReactOS 0.4.15-dev-7654-g6bc40d3
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 */
62FSE_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
73size_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*********************************************************/
136size_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
154size_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
243size_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
257size_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
279typedef FSE_DTable DTable_max_t[FSE_DTABLE_SIZE_U32(FSE_MAX_TABLELOG)];
280
281size_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 */
MEM_STATIC size_t BIT_initDStream(BIT_DStream_t *bitD, const void *srcBuffer, size_t srcSize)
Definition: bitstream.h:272
MEM_STATIC unsigned BIT_highbit32(U32 val)
Definition: bitstream.h:139
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
signed short S16
Definition: mem.h:146
size_t FSE_readNCount(short *normalizedCounter, unsigned *maxSVPtr, unsigned *tableLogPtr, const void *headerBuffer, size_t hbSize)
#define ExAllocatePoolWithTag(hernya, size, tag)
Definition: env_spec_w32.h:350
#define ExFreePool(addr)
Definition: env_spec_w32.h:352
#define PagedPool
Definition: env_spec_w32.h:308
#define CHECK_F(f)
Definition: error_private.h:62
#define ERROR(name)
Definition: error_private.h:53
unsigned FSE_DTable
Definition: fse.h:233
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)]
size_t FSE_buildDTable_rle(FSE_DTable *dt, BYTE symbolValue)
size_t FSE_decompress_usingDTable(void *dst, size_t originalSize, const void *cSrc, size_t cSrcSize, const FSE_DTable *dt)
#define FSE_GETSYMBOL(statePtr)
size_t FSE_buildDTable(FSE_DTable *dt, const short *normalizedCounter, unsigned maxSymbolValue, unsigned tableLog)
void FSE_freeDTable(FSE_DTable *dt)
#define FSE_isError
size_t FSE_buildDTable_raw(FSE_DTable *dt, unsigned nbBits)
FSE_DTable * FSE_createDTable(unsigned tableLog)
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(void *dst, size_t dstCapacity, const void *cSrc, size_t cSrcSize)
#define FSED_ALLOC_TAG
GLdouble s
Definition: gl.h:2039
GLenum GLenum dst
Definition: glext.h:6340
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
static PVOID ptr
Definition: dispmode.c:27
size_t bitContainer
Definition: bitstream.h:92
Definition: dhcpd.h:62
unsigned char BYTE
Definition: xxhash.c:193
#define FORCE_INLINE_TEMPLATE
Definition: xxhash.c:172
unsigned int U32
Definition: xxhash.c:195
unsigned short U16
Definition: xxhash.c:194