LCOV - code coverage report
Current view: top level - pression/compressor/zstd/lib/common - fse_decompress.c (source / functions) Hit Total Coverage
Test: Pression Lines: 83 105 79.0 %
Date: 2016-12-06 05:44:58 Functions: 4 7 57.1 %

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

Generated by: LCOV version 1.11