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