sys/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 *  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 */