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) { enum { FSE_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */ 53 54 /* check and forward error code */ 55 #define CHECK_F(f) { size_t const e = f; if (FSE_isError(e)) return e; } 56 57 58 /* ************************************************************** 59 * Templates 60 ****************************************************************/ 61 /* 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 65 */ 66 67 /* safety checks */ 68 #ifndef FSE_FUNCTION_EXTENSION 69 # error "FSE_FUNCTION_EXTENSION must be defined" 70 #endif 71 #ifndef FSE_FUNCTION_TYPE 72 # error "FSE_FUNCTION_TYPE must be defined" 73 #endif 74 75 /* Function names */ 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) 79 80 81 /* Function templates */ 82 FSE_DTable* FSE_createDTable (unsigned tableLog) 83 { 84 if (tableLog > FSE_TABLELOG_ABSOLUTE_MAX) tableLog = FSE_TABLELOG_ABSOLUTE_MAX; 85 return (FSE_DTable*)malloc( FSE_DTABLE_SIZE_U32(tableLog) * sizeof (U32) ); 86 } 87 88 void FSE_freeDTable (FSE_DTable* dt) 89 { 90 free(dt); 91 } 92 93 size_t FSE_buildDTable(FSE_DTable* dt, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog) 94 { 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]; 98 99 U32 const maxSV1 = maxSymbolValue + 1; 100 U32 const tableSize = 1 << tableLog; 101 U32 highThreshold = tableSize-1; 102 103 /* Sanity Checks */ 104 if (maxSymbolValue > FSE_MAX_SYMBOL_VALUE) return ERROR(maxSymbolValue_tooLarge); 105 if (tableLog > FSE_MAX_TABLELOG) return ERROR(tableLog_tooLarge); 106 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)); 112 U32 s; 113 for (s=0; s<maxSV1; s++) { 114 if (normalizedCounter[s]==-1) { 115 tableDecode[highThreshold--].symbol = (FSE_FUNCTION_TYPE)s; 116 symbolNext[s] = 1; 117 } else { 118 if (normalizedCounter[s] >= largeLimit) DTableH.fastMode=0; 119 symbolNext[s] = normalizedCounter[s]; 120 } } } 121 memcpy(dt, &DTableH, sizeof(DTableH)); 122 } 123 124 /* Spread symbols */ 125 { U32 const tableMask = tableSize-1; 126 U32 const step = FSE_TABLESTEP(tableSize); 127 U32 s, position = 0; 128 for (s=0; s<maxSV1; s++) { 129 int i; 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 */ 134 } } 135 if (position!=0) return ERROR(GENERIC); /* position must reach all cells once, otherwise normalizedCounter is incorrect */ 136 } 137 138 /* Build Decoding table */ 139 { U32 u; 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); 145 } } 146 147 return 0; 148 } 149 150 151 #ifndef FSE_COMMONDEFS_ONLY 152 153 /*-******************************************************* 154 * Decompression (Byte symbols) 155 *********************************************************/ 156 size_t FSE_buildDTable_rle (FSE_DTable* dt, BYTE symbolValue) 157 { 158 void* ptr = dt; 159 FSE_DTableHeader* const DTableH = (FSE_DTableHeader*)ptr; 160 void* dPtr = dt + 1; 161 FSE_decode_t* const cell = (FSE_decode_t*)dPtr; 162 163 DTableH->tableLog = 0; 164 DTableH->fastMode = 0; 165 166 cell->newState = 0; 167 cell->symbol = symbolValue; 168 cell->nbBits = 0; 169 170 return 0; 171 } 172 173 174 size_t FSE_buildDTable_raw (FSE_DTable* dt, unsigned nbBits) 175 { 176 void* ptr = dt; 177 FSE_DTableHeader* const DTableH = (FSE_DTableHeader*)ptr; 178 void* dPtr = dt + 1; 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; 183 unsigned s; 184 185 /* Sanity checks */ 186 if (nbBits < 1) return ERROR(GENERIC); /* min size */ 187 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; 195 } 196 197 return 0; 198 } 199 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) 204 { 205 BYTE* const ostart = (BYTE*) dst; 206 BYTE* op = ostart; 207 BYTE* const omax = op + maxDstSize; 208 BYTE* const olimit = omax-3; 209 210 BIT_DStream_t bitD; 211 FSE_DState_t state1; 212 FSE_DState_t state2; 213 214 /* Init */ 215 CHECK_F(BIT_initDStream(&bitD, cSrc, cSrcSize)); 216 217 FSE_initDState(&state1, &bitD, dt); 218 FSE_initDState(&state2, &bitD, dt); 219 220 #define FSE_GETSYMBOL(statePtr) fast ? FSE_decodeSymbolFast(statePtr, &bitD) : FSE_decodeSymbol(statePtr, &bitD) 221 222 /* 4 symbols per loop */ 223 for ( ; (BIT_reloadDStream(&bitD)==BIT_DStream_unfinished) & (op<olimit) ; op+=4) { 224 op[0] = FSE_GETSYMBOL(&state1); 225 226 if (FSE_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */ 227 BIT_reloadDStream(&bitD); 228 229 op[1] = FSE_GETSYMBOL(&state2); 230 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; } } 233 234 op[2] = FSE_GETSYMBOL(&state1); 235 236 if (FSE_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */ 237 BIT_reloadDStream(&bitD); 238 239 op[3] = FSE_GETSYMBOL(&state2); 240 } 241 242 /* tail */ 243 /* note : BIT_reloadDStream(&bitD) >= FSE_DStream_partiallyFilled; Ends at exactly BIT_DStream_completed */ 244 while (1) { 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); 249 break; 250 } 251 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); 256 break; 257 } } 258 259 return op-ostart; 260 } 261 262 263 size_t FSE_decompress_usingDTable(void* dst, size_t originalSize, 264 const void* cSrc, size_t cSrcSize, 265 const FSE_DTable* dt) 266 { 267 const void* ptr = dt; 268 const FSE_DTableHeader* DTableH = (const FSE_DTableHeader*)ptr; 269 const U32 fastMode = DTableH->fastMode; 270 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); 274 } 275 276 277 size_t FSE_decompress_wksp(void* dst, size_t dstCapacity, const void* cSrc, size_t cSrcSize, FSE_DTable* workSpace, unsigned maxLog) 278 { 279 const BYTE* const istart = (const BYTE*)cSrc; 280 const BYTE* ip = istart; 281 short counting[FSE_MAX_SYMBOL_VALUE+1]; 282 unsigned tableLog; 283 unsigned maxSymbolValue = FSE_MAX_SYMBOL_VALUE; 284 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); 290 ip += NCountLength; 291 cSrcSize -= NCountLength; 292 293 CHECK_F( FSE_buildDTable (workSpace, counting, maxSymbolValue, tableLog) ); 294 295 return FSE_decompress_usingDTable (dst, dstCapacity, ip, cSrcSize, workSpace); /* always return, even if it is an error code */ 296 } 297 298 299 typedef FSE_DTable DTable_max_t[FSE_DTABLE_SIZE_U32(FSE_MAX_TABLELOG)]; 300 301 size_t FSE_decompress(void* dst, size_t dstCapacity, const void* cSrc, size_t cSrcSize) 302 { 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); 305 } 306 307 308 309 #endif /* FSE_COMMONDEFS_ONLY */ 310