1 /* ******************************************************************
2 FSE : Finite State Entropy decoder
3 Copyright (C) 2013-2015, Yann Collet.
5 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
7 Redistribution and use in source and binary forms, with or without
8 modification, are permitted provided that the following conditions are
11 * Redistributions of source code must retain the above copyright
12 notice, this list of conditions and the following disclaimer.
13 * Redistributions in binary form must reproduce the above
14 copyright notice, this list of conditions and the following disclaimer
15 in the documentation and/or other materials provided with the
18 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
19 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
20 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
21 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
22 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
23 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
24 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30 You can contact the author at :
31 - FSE source repository : https://github.com/Cyan4973/FiniteStateEntropy
32 - Public forum : https://groups.google.com/forum/#!forum/lz4c
33 ****************************************************************** */
36 /* **************************************************************
38 ****************************************************************/
39 #include <stdlib.h> /* malloc, free, qsort */
40 #include <string.h> /* memcpy, memset */
41 #include "bitstream.h"
43 #define FSE_STATIC_LINKING_ONLY
45 #include "error_private.h"
48 /* **************************************************************
50 ****************************************************************/
51 #define FSE_isError ERR_isError
52 #define FSE_STATIC_ASSERT(c) DEBUG_STATIC_ASSERT(c) /* use only *after* variable declarations */
54 /* check and forward error code */
55 #define CHECK_F(f) { size_t const e = f; if (FSE_isError(e)) return e; }
58 /* **************************************************************
60 ****************************************************************/
62 designed to be included
63 for type-specific functions (template emulation in C)
64 Objective is to write these functions only once, for improved maintenance
68 #ifndef FSE_FUNCTION_EXTENSION
69 # error "FSE_FUNCTION_EXTENSION must be defined"
71 #ifndef FSE_FUNCTION_TYPE
72 # error "FSE_FUNCTION_TYPE must be defined"
76 #define FSE_CAT(X,Y) X##Y
77 #define FSE_FUNCTION_NAME(X,Y) FSE_CAT(X,Y)
78 #define FSE_TYPE_NAME(X,Y) FSE_CAT(X,Y)
81 /* Function templates */
82 FSE_DTable* FSE_createDTable (unsigned tableLog)
84 if (tableLog > FSE_TABLELOG_ABSOLUTE_MAX) tableLog = FSE_TABLELOG_ABSOLUTE_MAX;
85 return (FSE_DTable*)malloc( FSE_DTABLE_SIZE_U32(tableLog) * sizeof (U32) );
88 void FSE_freeDTable (FSE_DTable* dt)
93 size_t FSE_buildDTable(FSE_DTable* dt, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog)
95 void* const tdPtr = dt+1; /* because *dt is unsigned, 32-bits aligned on 32-bits */
96 FSE_DECODE_TYPE* const tableDecode = (FSE_DECODE_TYPE*) (tdPtr);
97 U16 symbolNext[FSE_MAX_SYMBOL_VALUE+1];
99 U32 const maxSV1 = maxSymbolValue + 1;
100 U32 const tableSize = 1 << tableLog;
101 U32 highThreshold = tableSize-1;
104 if (maxSymbolValue > FSE_MAX_SYMBOL_VALUE) return ERROR(maxSymbolValue_tooLarge);
105 if (tableLog > FSE_MAX_TABLELOG) return ERROR(tableLog_tooLarge);
107 /* Init, lay down lowprob symbols */
108 { FSE_DTableHeader DTableH;
109 DTableH.tableLog = (U16)tableLog;
110 DTableH.fastMode = 1;
111 { S16 const largeLimit= (S16)(1 << (tableLog-1));
113 for (s=0; s<maxSV1; s++) {
114 if (normalizedCounter[s]==-1) {
115 tableDecode[highThreshold--].symbol = (FSE_FUNCTION_TYPE)s;
118 if (normalizedCounter[s] >= largeLimit) DTableH.fastMode=0;
119 symbolNext[s] = normalizedCounter[s];
121 memcpy(dt, &DTableH, sizeof(DTableH));
125 { U32 const tableMask = tableSize-1;
126 U32 const step = FSE_TABLESTEP(tableSize);
128 for (s=0; s<maxSV1; s++) {
130 for (i=0; i<normalizedCounter[s]; i++) {
131 tableDecode[position].symbol = (FSE_FUNCTION_TYPE)s;
132 position = (position + step) & tableMask;
133 while (position > highThreshold) position = (position + step) & tableMask; /* lowprob area */
135 if (position!=0) return ERROR(GENERIC); /* position must reach all cells once, otherwise normalizedCounter is incorrect */
138 /* Build Decoding table */
140 for (u=0; u<tableSize; u++) {
141 FSE_FUNCTION_TYPE const symbol = (FSE_FUNCTION_TYPE)(tableDecode[u].symbol);
142 U32 const nextState = symbolNext[symbol]++;
143 tableDecode[u].nbBits = (BYTE) (tableLog - BIT_highbit32(nextState) );
144 tableDecode[u].newState = (U16) ( (nextState << tableDecode[u].nbBits) - tableSize);
151 #ifndef FSE_COMMONDEFS_ONLY
153 /*-*******************************************************
154 * Decompression (Byte symbols)
155 *********************************************************/
156 size_t FSE_buildDTable_rle (FSE_DTable* dt, BYTE symbolValue)
159 FSE_DTableHeader* const DTableH = (FSE_DTableHeader*)ptr;
161 FSE_decode_t* const cell = (FSE_decode_t*)dPtr;
163 DTableH->tableLog = 0;
164 DTableH->fastMode = 0;
167 cell->symbol = symbolValue;
174 size_t FSE_buildDTable_raw (FSE_DTable* dt, unsigned nbBits)
177 FSE_DTableHeader* const DTableH = (FSE_DTableHeader*)ptr;
179 FSE_decode_t* const dinfo = (FSE_decode_t*)dPtr;
180 const unsigned tableSize = 1 << nbBits;
181 const unsigned tableMask = tableSize - 1;
182 const unsigned maxSV1 = tableMask+1;
186 if (nbBits < 1) return ERROR(GENERIC); /* min size */
188 /* Build Decoding Table */
189 DTableH->tableLog = (U16)nbBits;
190 DTableH->fastMode = 1;
191 for (s=0; s<maxSV1; s++) {
192 dinfo[s].newState = 0;
193 dinfo[s].symbol = (BYTE)s;
194 dinfo[s].nbBits = (BYTE)nbBits;
200 FORCE_INLINE_TEMPLATE size_t FSE_decompress_usingDTable_generic(
201 void* dst, size_t maxDstSize,
202 const void* cSrc, size_t cSrcSize,
203 const FSE_DTable* dt, const unsigned fast)
205 BYTE* const ostart = (BYTE*) dst;
207 BYTE* const omax = op + maxDstSize;
208 BYTE* const olimit = omax-3;
215 CHECK_F(BIT_initDStream(&bitD, cSrc, cSrcSize));
217 FSE_initDState(&state1, &bitD, dt);
218 FSE_initDState(&state2, &bitD, dt);
220 #define FSE_GETSYMBOL(statePtr) fast ? FSE_decodeSymbolFast(statePtr, &bitD) : FSE_decodeSymbol(statePtr, &bitD)
222 /* 4 symbols per loop */
223 for ( ; (BIT_reloadDStream(&bitD)==BIT_DStream_unfinished) & (op<olimit) ; op+=4) {
224 op[0] = FSE_GETSYMBOL(&state1);
226 if (FSE_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */
227 BIT_reloadDStream(&bitD);
229 op[1] = FSE_GETSYMBOL(&state2);
231 if (FSE_MAX_TABLELOG*4+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */
232 { if (BIT_reloadDStream(&bitD) > BIT_DStream_unfinished) { op+=2; break; } }
234 op[2] = FSE_GETSYMBOL(&state1);
236 if (FSE_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */
237 BIT_reloadDStream(&bitD);
239 op[3] = FSE_GETSYMBOL(&state2);
243 /* note : BIT_reloadDStream(&bitD) >= FSE_DStream_partiallyFilled; Ends at exactly BIT_DStream_completed */
245 if (op>(omax-2)) return ERROR(dstSize_tooSmall);
246 *op++ = FSE_GETSYMBOL(&state1);
247 if (BIT_reloadDStream(&bitD)==BIT_DStream_overflow) {
248 *op++ = FSE_GETSYMBOL(&state2);
252 if (op>(omax-2)) return ERROR(dstSize_tooSmall);
253 *op++ = FSE_GETSYMBOL(&state2);
254 if (BIT_reloadDStream(&bitD)==BIT_DStream_overflow) {
255 *op++ = FSE_GETSYMBOL(&state1);
263 size_t FSE_decompress_usingDTable(void* dst, size_t originalSize,
264 const void* cSrc, size_t cSrcSize,
265 const FSE_DTable* dt)
267 const void* ptr = dt;
268 const FSE_DTableHeader* DTableH = (const FSE_DTableHeader*)ptr;
269 const U32 fastMode = DTableH->fastMode;
271 /* select fast mode (static) */
272 if (fastMode) return FSE_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 1);
273 return FSE_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 0);
277 size_t FSE_decompress_wksp(void* dst, size_t dstCapacity, const void* cSrc, size_t cSrcSize, FSE_DTable* workSpace, unsigned maxLog)
279 const BYTE* const istart = (const BYTE*)cSrc;
280 const BYTE* ip = istart;
281 short counting[FSE_MAX_SYMBOL_VALUE+1];
283 unsigned maxSymbolValue = FSE_MAX_SYMBOL_VALUE;
285 /* normal FSE decoding mode */
286 size_t const NCountLength = FSE_readNCount (counting, &maxSymbolValue, &tableLog, istart, cSrcSize);
287 if (FSE_isError(NCountLength)) return NCountLength;
288 //if (NCountLength >= cSrcSize) return ERROR(srcSize_wrong); /* too small input size; supposed to be already checked in NCountLength, only remaining case : NCountLength==cSrcSize */
289 if (tableLog > maxLog) return ERROR(tableLog_tooLarge);
291 cSrcSize -= NCountLength;
293 CHECK_F( FSE_buildDTable (workSpace, counting, maxSymbolValue, tableLog) );
295 return FSE_decompress_usingDTable (dst, dstCapacity, ip, cSrcSize, workSpace); /* always return, even if it is an error code */
299 typedef FSE_DTable DTable_max_t[FSE_DTABLE_SIZE_U32(FSE_MAX_TABLELOG)];
301 size_t FSE_decompress(void* dst, size_t dstCapacity, const void* cSrc, size_t cSrcSize)
303 DTable_max_t dt; /* Static analyzer seems unable to understand this table will be properly initialized later */
304 return FSE_decompress_wksp(dst, dstCapacity, cSrc, cSrcSize, dt, FSE_MAX_TABLELOG);
309 #endif /* FSE_COMMONDEFS_ONLY */