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 27 28 /* ************************************************************** 29 * Error Management 30 ****************************************************************/ 31 #define FSE_isError ERR_isError 32 #define FSE_STATIC_ASSERT(c) DEBUG_STATIC_ASSERT(c) /* use only *after* variable declarations */ 33 34 35 /* ************************************************************** 36 * Templates 37 ****************************************************************/ 38 /* 39 designed to be included 40 for type-specific functions (template emulation in C) 41 Objective is to write these functions only once, for improved maintenance 42 */ 43 44 /* safety checks */ 45 #ifndef FSE_FUNCTION_EXTENSION 46 # error "FSE_FUNCTION_EXTENSION must be defined" 47 #endif 48 #ifndef FSE_FUNCTION_TYPE 49 # error "FSE_FUNCTION_TYPE must be defined" 50 #endif 51 52 /* Function names */ 53 #define FSE_CAT(X,Y) X##Y 54 #define FSE_FUNCTION_NAME(X,Y) FSE_CAT(X,Y) 55 #define FSE_TYPE_NAME(X,Y) FSE_CAT(X,Y) 56 57 58 /* Function templates */ 59 size_t FSE_buildDTable(FSE_DTable* dt, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog) 60 { 61 void* const tdPtr = dt+1; /* because *dt is unsigned, 32-bits aligned on 32-bits */ 62 FSE_DECODE_TYPE* const tableDecode = (FSE_DECODE_TYPE*) (tdPtr); 63 U16 symbolNext[FSE_MAX_SYMBOL_VALUE+1]; 64 65 U32 const maxSV1 = maxSymbolValue + 1; 66 U32 const tableSize = 1 << tableLog; 67 U32 highThreshold = tableSize-1; 68 69 /* Sanity Checks */ 70 if (maxSymbolValue > FSE_MAX_SYMBOL_VALUE) return ERROR(maxSymbolValue_tooLarge); 71 if (tableLog > FSE_MAX_TABLELOG) return ERROR(tableLog_tooLarge); 72 73 /* Init, lay down lowprob symbols */ 74 { FSE_DTableHeader DTableH; 75 DTableH.tableLog = (U16)tableLog; 76 DTableH.fastMode = 1; 77 { S16 const largeLimit= (S16)(1 << (tableLog-1)); 78 U32 s; 79 for (s=0; s<maxSV1; s++) { 80 if (normalizedCounter[s]==-1) { 81 tableDecode[highThreshold--].symbol = (FSE_FUNCTION_TYPE)s; 82 symbolNext[s] = 1; 83 } else { 84 if (normalizedCounter[s] >= largeLimit) DTableH.fastMode=0; 85 symbolNext[s] = normalizedCounter[s]; 86 } } } 87 memcpy(dt, &DTableH, sizeof(DTableH)); 88 } 89 90 /* Spread symbols */ 91 { U32 const tableMask = tableSize-1; 92 U32 const step = FSE_TABLESTEP(tableSize); 93 U32 s, position = 0; 94 for (s=0; s<maxSV1; s++) { 95 int i; 96 for (i=0; i<normalizedCounter[s]; i++) { 97 tableDecode[position].symbol = (FSE_FUNCTION_TYPE)s; 98 position = (position + step) & tableMask; 99 while (position > highThreshold) position = (position + step) & tableMask; /* lowprob area */ 100 } } 101 if (position!=0) return ERROR(GENERIC); /* position must reach all cells once, otherwise normalizedCounter is incorrect */ 102 } 103 104 /* Build Decoding table */ 105 { U32 u; 106 for (u=0; u<tableSize; u++) { 107 FSE_FUNCTION_TYPE const symbol = (FSE_FUNCTION_TYPE)(tableDecode[u].symbol); 108 U32 const nextState = symbolNext[symbol]++; 109 tableDecode[u].nbBits = (BYTE) (tableLog - BIT_highbit32(nextState) ); 110 tableDecode[u].newState = (U16) ( (nextState << tableDecode[u].nbBits) - tableSize); 111 } } 112 113 return 0; 114 } 115 116 117 #ifndef FSE_COMMONDEFS_ONLY 118 119 /*-******************************************************* 120 * Decompression (Byte symbols) 121 *********************************************************/ 122 size_t FSE_buildDTable_rle (FSE_DTable* dt, BYTE symbolValue) 123 { 124 void* ptr = dt; 125 FSE_DTableHeader* const DTableH = (FSE_DTableHeader*)ptr; 126 void* dPtr = dt + 1; 127 FSE_decode_t* const cell = (FSE_decode_t*)dPtr; 128 129 DTableH->tableLog = 0; 130 DTableH->fastMode = 0; 131 132 cell->newState = 0; 133 cell->symbol = symbolValue; 134 cell->nbBits = 0; 135 136 return 0; 137 } 138 139 140 size_t FSE_buildDTable_raw (FSE_DTable* dt, unsigned nbBits) 141 { 142 void* ptr = dt; 143 FSE_DTableHeader* const DTableH = (FSE_DTableHeader*)ptr; 144 void* dPtr = dt + 1; 145 FSE_decode_t* const dinfo = (FSE_decode_t*)dPtr; 146 const unsigned tableSize = 1 << nbBits; 147 const unsigned tableMask = tableSize - 1; 148 const unsigned maxSV1 = tableMask+1; 149 unsigned s; 150 151 /* Sanity checks */ 152 if (nbBits < 1) return ERROR(GENERIC); /* min size */ 153 154 /* Build Decoding Table */ 155 DTableH->tableLog = (U16)nbBits; 156 DTableH->fastMode = 1; 157 for (s=0; s<maxSV1; s++) { 158 dinfo[s].newState = 0; 159 dinfo[s].symbol = (BYTE)s; 160 dinfo[s].nbBits = (BYTE)nbBits; 161 } 162 163 return 0; 164 } 165 166 FORCE_INLINE_TEMPLATE size_t FSE_decompress_usingDTable_generic( 167 void* dst, size_t maxDstSize, 168 const void* cSrc, size_t cSrcSize, 169 const FSE_DTable* dt, const unsigned fast) 170 { 171 BYTE* const ostart = (BYTE*) dst; 172 BYTE* op = ostart; 173 BYTE* const omax = op + maxDstSize; 174 BYTE* const olimit = omax-3; 175 176 BIT_DStream_t bitD; 177 FSE_DState_t state1; 178 FSE_DState_t state2; 179 180 /* Init */ 181 CHECK_F(BIT_initDStream(&bitD, cSrc, cSrcSize)); 182 183 FSE_initDState(&state1, &bitD, dt); 184 FSE_initDState(&state2, &bitD, dt); 185 186 #define FSE_GETSYMBOL(statePtr) fast ? FSE_decodeSymbolFast(statePtr, &bitD) : FSE_decodeSymbol(statePtr, &bitD) 187 188 /* 4 symbols per loop */ 189 for ( ; (BIT_reloadDStream(&bitD)==BIT_DStream_unfinished) & (op<olimit) ; op+=4) { 190 op[0] = FSE_GETSYMBOL(&state1); 191 192 if (FSE_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */ 193 BIT_reloadDStream(&bitD); 194 195 op[1] = FSE_GETSYMBOL(&state2); 196 197 if (FSE_MAX_TABLELOG*4+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */ 198 { if (BIT_reloadDStream(&bitD) > BIT_DStream_unfinished) { op+=2; break; } } 199 200 op[2] = FSE_GETSYMBOL(&state1); 201 202 if (FSE_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */ 203 BIT_reloadDStream(&bitD); 204 205 op[3] = FSE_GETSYMBOL(&state2); 206 } 207 208 /* tail */ 209 /* note : BIT_reloadDStream(&bitD) >= FSE_DStream_partiallyFilled; Ends at exactly BIT_DStream_completed */ 210 while (1) { 211 if (op>(omax-2)) return ERROR(dstSize_tooSmall); 212 *op++ = FSE_GETSYMBOL(&state1); 213 if (BIT_reloadDStream(&bitD)==BIT_DStream_overflow) { 214 *op++ = FSE_GETSYMBOL(&state2); 215 break; 216 } 217 218 if (op>(omax-2)) return ERROR(dstSize_tooSmall); 219 *op++ = FSE_GETSYMBOL(&state2); 220 if (BIT_reloadDStream(&bitD)==BIT_DStream_overflow) { 221 *op++ = FSE_GETSYMBOL(&state1); 222 break; 223 } } 224 225 return op-ostart; 226 } 227 228 229 size_t FSE_decompress_usingDTable(void* dst, size_t originalSize, 230 const void* cSrc, size_t cSrcSize, 231 const FSE_DTable* dt) 232 { 233 const void* ptr = dt; 234 const FSE_DTableHeader* DTableH = (const FSE_DTableHeader*)ptr; 235 const U32 fastMode = DTableH->fastMode; 236 237 /* select fast mode (static) */ 238 if (fastMode) return FSE_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 1); 239 return FSE_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 0); 240 } 241 242 243 size_t FSE_decompress_wksp(void* dst, size_t dstCapacity, const void* cSrc, size_t cSrcSize, FSE_DTable* workSpace, unsigned maxLog) 244 { 245 const BYTE* const istart = (const BYTE*)cSrc; 246 const BYTE* ip = istart; 247 short counting[FSE_MAX_SYMBOL_VALUE+1]; 248 unsigned tableLog; 249 unsigned maxSymbolValue = FSE_MAX_SYMBOL_VALUE; 250 251 /* normal FSE decoding mode */ 252 size_t const NCountLength = FSE_readNCount (counting, &maxSymbolValue, &tableLog, istart, cSrcSize); 253 if (FSE_isError(NCountLength)) return NCountLength; 254 /* if (NCountLength >= cSrcSize) return ERROR(srcSize_wrong); */ /* too small input size; supposed to be already checked in NCountLength, only remaining case : NCountLength==cSrcSize */ 255 if (tableLog > maxLog) return ERROR(tableLog_tooLarge); 256 ip += NCountLength; 257 cSrcSize -= NCountLength; 258 259 CHECK_F( FSE_buildDTable (workSpace, counting, maxSymbolValue, tableLog) ); 260 261 return FSE_decompress_usingDTable (dst, dstCapacity, ip, cSrcSize, workSpace); /* always return, even if it is an error code */ 262 } 263 264 265 typedef FSE_DTable DTable_max_t[FSE_DTABLE_SIZE_U32(FSE_MAX_TABLELOG)]; 266 267 size_t FSE_decompress(void* dst, size_t dstCapacity, const void* cSrc, size_t cSrcSize) 268 { 269 DTable_max_t dt; /* Static analyzer seems unable to understand this table will be properly initialized later */ 270 return FSE_decompress_wksp(dst, dstCapacity, cSrc, cSrcSize, dt, FSE_MAX_TABLELOG); 271 } 272 273 274 275 #endif /* FSE_COMMONDEFS_ONLY */ 276