contrib/zstd/lib/common/fse_decompress.c

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