xref: /freebsd/sys/contrib/zstd/lib/legacy/zstd_v04.c (revision 2b9c00cb6bd9392645dc8afca59cf57c42df4e2d)
10c16b537SWarner Losh /*
20c16b537SWarner Losh  * Copyright (c) 2016-present, Yann Collet, Facebook, Inc.
30c16b537SWarner Losh  * All rights reserved.
40c16b537SWarner Losh  *
50c16b537SWarner Losh  * This source code is licensed under both the BSD-style license (found in the
60c16b537SWarner Losh  * LICENSE file in the root directory of this source tree) and the GPLv2 (found
70c16b537SWarner Losh  * in the COPYING file in the root directory of this source tree).
80c16b537SWarner Losh  * You may select, at your option, one of the above-listed licenses.
90c16b537SWarner Losh  */
100c16b537SWarner Losh 
110c16b537SWarner Losh 
120f743729SConrad Meyer  /******************************************
130f743729SConrad Meyer  *  Includes
140f743729SConrad Meyer  ******************************************/
150f743729SConrad Meyer #include <stddef.h>    /* size_t, ptrdiff_t */
160f743729SConrad Meyer #include <string.h>    /* memcpy */
170f743729SConrad Meyer 
180c16b537SWarner Losh #include "zstd_v04.h"
190c16b537SWarner Losh #include "error_private.h"
200c16b537SWarner Losh 
210c16b537SWarner Losh 
220c16b537SWarner Losh /* ******************************************************************
230f743729SConrad Meyer  *   mem.h
240c16b537SWarner Losh  *******************************************************************/
250c16b537SWarner Losh #ifndef MEM_H_MODULE
260c16b537SWarner Losh #define MEM_H_MODULE
270c16b537SWarner Losh 
280c16b537SWarner Losh #if defined (__cplusplus)
290c16b537SWarner Losh extern "C" {
300c16b537SWarner Losh #endif
310c16b537SWarner Losh 
320c16b537SWarner Losh 
330c16b537SWarner Losh /******************************************
340c16b537SWarner Losh *  Compiler-specific
350c16b537SWarner Losh ******************************************/
360c16b537SWarner Losh #if defined(_MSC_VER)   /* Visual Studio */
370c16b537SWarner Losh #   include <stdlib.h>  /* _byteswap_ulong */
380c16b537SWarner Losh #   include <intrin.h>  /* _byteswap_* */
390c16b537SWarner Losh #endif
400c16b537SWarner Losh #if defined(__GNUC__)
410c16b537SWarner Losh #  define MEM_STATIC static __attribute__((unused))
420c16b537SWarner Losh #elif defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */)
430c16b537SWarner Losh #  define MEM_STATIC static inline
440c16b537SWarner Losh #elif defined(_MSC_VER)
450c16b537SWarner Losh #  define MEM_STATIC static __inline
460c16b537SWarner Losh #else
470c16b537SWarner Losh #  define MEM_STATIC static  /* this version may generate warnings for unused static functions; disable the relevant warning */
480c16b537SWarner Losh #endif
490c16b537SWarner Losh 
500c16b537SWarner Losh 
510c16b537SWarner Losh /****************************************************************
520c16b537SWarner Losh *  Basic Types
530c16b537SWarner Losh *****************************************************************/
540c16b537SWarner Losh #if defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */)
550c16b537SWarner Losh # include <stdint.h>
560c16b537SWarner Losh   typedef  uint8_t BYTE;
570c16b537SWarner Losh   typedef uint16_t U16;
580c16b537SWarner Losh   typedef  int16_t S16;
590c16b537SWarner Losh   typedef uint32_t U32;
600c16b537SWarner Losh   typedef  int32_t S32;
610c16b537SWarner Losh   typedef uint64_t U64;
620c16b537SWarner Losh   typedef  int64_t S64;
630c16b537SWarner Losh #else
640c16b537SWarner Losh   typedef unsigned char       BYTE;
650c16b537SWarner Losh   typedef unsigned short      U16;
660c16b537SWarner Losh   typedef   signed short      S16;
670c16b537SWarner Losh   typedef unsigned int        U32;
680c16b537SWarner Losh   typedef   signed int        S32;
690c16b537SWarner Losh   typedef unsigned long long  U64;
700c16b537SWarner Losh   typedef   signed long long  S64;
710c16b537SWarner Losh #endif
720c16b537SWarner Losh 
730c16b537SWarner Losh 
7419fcbaf1SConrad Meyer /*-*************************************
7519fcbaf1SConrad Meyer *  Debug
7619fcbaf1SConrad Meyer ***************************************/
770f743729SConrad Meyer #include "debug.h"
7819fcbaf1SConrad Meyer #ifndef assert
7919fcbaf1SConrad Meyer #  define assert(condition) ((void)0)
8019fcbaf1SConrad Meyer #endif
8119fcbaf1SConrad Meyer 
8219fcbaf1SConrad Meyer 
830c16b537SWarner Losh /****************************************************************
840c16b537SWarner Losh *  Memory I/O
850c16b537SWarner Losh *****************************************************************/
860c16b537SWarner Losh /* MEM_FORCE_MEMORY_ACCESS
870c16b537SWarner Losh  * By default, access to unaligned memory is controlled by `memcpy()`, which is safe and portable.
880c16b537SWarner Losh  * Unfortunately, on some target/compiler combinations, the generated assembly is sub-optimal.
890c16b537SWarner Losh  * The below switch allow to select different access method for improved performance.
900c16b537SWarner Losh  * Method 0 (default) : use `memcpy()`. Safe and portable.
910c16b537SWarner Losh  * Method 1 : `__packed` statement. It depends on compiler extension (ie, not portable).
920c16b537SWarner Losh  *            This method is safe if your compiler supports it, and *generally* as fast or faster than `memcpy`.
930c16b537SWarner Losh  * Method 2 : direct access. This method is portable but violate C standard.
940c16b537SWarner Losh  *            It can generate buggy code on targets generating assembly depending on alignment.
950c16b537SWarner Losh  *            But in some circumstances, it's the only known way to get the most performance (ie GCC + ARMv6)
960c16b537SWarner Losh  * See http://fastcompression.blogspot.fr/2015/08/accessing-unaligned-memory.html for details.
970c16b537SWarner Losh  * Prefer these methods in priority order (0 > 1 > 2)
980c16b537SWarner Losh  */
990c16b537SWarner Losh #ifndef MEM_FORCE_MEMORY_ACCESS   /* can be defined externally, on command line for example */
1000c16b537SWarner Losh #  if defined(__GNUC__) && ( defined(__ARM_ARCH_6__) || defined(__ARM_ARCH_6J__) || defined(__ARM_ARCH_6K__) || defined(__ARM_ARCH_6Z__) || defined(__ARM_ARCH_6ZK__) || defined(__ARM_ARCH_6T2__) )
1010c16b537SWarner Losh #    define MEM_FORCE_MEMORY_ACCESS 2
1020c16b537SWarner Losh #  elif (defined(__INTEL_COMPILER) && !defined(WIN32)) || \
1030c16b537SWarner Losh   (defined(__GNUC__) && ( defined(__ARM_ARCH_7__) || defined(__ARM_ARCH_7A__) || defined(__ARM_ARCH_7R__) || defined(__ARM_ARCH_7M__) || defined(__ARM_ARCH_7S__) ))
1040c16b537SWarner Losh #    define MEM_FORCE_MEMORY_ACCESS 1
1050c16b537SWarner Losh #  endif
1060c16b537SWarner Losh #endif
1070c16b537SWarner Losh 
1080c16b537SWarner Losh MEM_STATIC unsigned MEM_32bits(void) { return sizeof(void*)==4; }
1090c16b537SWarner Losh MEM_STATIC unsigned MEM_64bits(void) { return sizeof(void*)==8; }
1100c16b537SWarner Losh 
1110c16b537SWarner Losh MEM_STATIC unsigned MEM_isLittleEndian(void)
1120c16b537SWarner Losh {
1130c16b537SWarner Losh     const union { U32 u; BYTE c[4]; } one = { 1 };   /* don't use static : performance detrimental  */
1140c16b537SWarner Losh     return one.c[0];
1150c16b537SWarner Losh }
1160c16b537SWarner Losh 
1170c16b537SWarner Losh #if defined(MEM_FORCE_MEMORY_ACCESS) && (MEM_FORCE_MEMORY_ACCESS==2)
1180c16b537SWarner Losh 
1190c16b537SWarner Losh /* violates C standard on structure alignment.
1200c16b537SWarner Losh Only use if no other choice to achieve best performance on target platform */
1210c16b537SWarner Losh MEM_STATIC U16 MEM_read16(const void* memPtr) { return *(const U16*) memPtr; }
1220c16b537SWarner Losh MEM_STATIC U32 MEM_read32(const void* memPtr) { return *(const U32*) memPtr; }
1230c16b537SWarner Losh MEM_STATIC U64 MEM_read64(const void* memPtr) { return *(const U64*) memPtr; }
1240c16b537SWarner Losh 
1250c16b537SWarner Losh MEM_STATIC void MEM_write16(void* memPtr, U16 value) { *(U16*)memPtr = value; }
1260c16b537SWarner Losh 
1270c16b537SWarner Losh #elif defined(MEM_FORCE_MEMORY_ACCESS) && (MEM_FORCE_MEMORY_ACCESS==1)
1280c16b537SWarner Losh 
1290c16b537SWarner Losh /* __pack instructions are safer, but compiler specific, hence potentially problematic for some compilers */
1300c16b537SWarner Losh /* currently only defined for gcc and icc */
1310c16b537SWarner Losh typedef union { U16 u16; U32 u32; U64 u64; } __attribute__((packed)) unalign;
1320c16b537SWarner Losh 
1330c16b537SWarner Losh MEM_STATIC U16 MEM_read16(const void* ptr) { return ((const unalign*)ptr)->u16; }
1340c16b537SWarner Losh MEM_STATIC U32 MEM_read32(const void* ptr) { return ((const unalign*)ptr)->u32; }
1350c16b537SWarner Losh MEM_STATIC U64 MEM_read64(const void* ptr) { return ((const unalign*)ptr)->u64; }
1360c16b537SWarner Losh 
1370c16b537SWarner Losh MEM_STATIC void MEM_write16(void* memPtr, U16 value) { ((unalign*)memPtr)->u16 = value; }
1380c16b537SWarner Losh 
1390c16b537SWarner Losh #else
1400c16b537SWarner Losh 
1410c16b537SWarner Losh /* default method, safe and standard.
1420c16b537SWarner Losh    can sometimes prove slower */
1430c16b537SWarner Losh 
1440c16b537SWarner Losh MEM_STATIC U16 MEM_read16(const void* memPtr)
1450c16b537SWarner Losh {
1460c16b537SWarner Losh     U16 val; memcpy(&val, memPtr, sizeof(val)); return val;
1470c16b537SWarner Losh }
1480c16b537SWarner Losh 
1490c16b537SWarner Losh MEM_STATIC U32 MEM_read32(const void* memPtr)
1500c16b537SWarner Losh {
1510c16b537SWarner Losh     U32 val; memcpy(&val, memPtr, sizeof(val)); return val;
1520c16b537SWarner Losh }
1530c16b537SWarner Losh 
1540c16b537SWarner Losh MEM_STATIC U64 MEM_read64(const void* memPtr)
1550c16b537SWarner Losh {
1560c16b537SWarner Losh     U64 val; memcpy(&val, memPtr, sizeof(val)); return val;
1570c16b537SWarner Losh }
1580c16b537SWarner Losh 
1590c16b537SWarner Losh MEM_STATIC void MEM_write16(void* memPtr, U16 value)
1600c16b537SWarner Losh {
1610c16b537SWarner Losh     memcpy(memPtr, &value, sizeof(value));
1620c16b537SWarner Losh }
1630c16b537SWarner Losh 
1640c16b537SWarner Losh #endif // MEM_FORCE_MEMORY_ACCESS
1650c16b537SWarner Losh 
1660c16b537SWarner Losh 
1670c16b537SWarner Losh MEM_STATIC U16 MEM_readLE16(const void* memPtr)
1680c16b537SWarner Losh {
1690c16b537SWarner Losh     if (MEM_isLittleEndian())
1700c16b537SWarner Losh         return MEM_read16(memPtr);
1710c16b537SWarner Losh     else
1720c16b537SWarner Losh     {
1730c16b537SWarner Losh         const BYTE* p = (const BYTE*)memPtr;
1740c16b537SWarner Losh         return (U16)(p[0] + (p[1]<<8));
1750c16b537SWarner Losh     }
1760c16b537SWarner Losh }
1770c16b537SWarner Losh 
1780c16b537SWarner Losh MEM_STATIC void MEM_writeLE16(void* memPtr, U16 val)
1790c16b537SWarner Losh {
1800c16b537SWarner Losh     if (MEM_isLittleEndian())
1810c16b537SWarner Losh     {
1820c16b537SWarner Losh         MEM_write16(memPtr, val);
1830c16b537SWarner Losh     }
1840c16b537SWarner Losh     else
1850c16b537SWarner Losh     {
1860c16b537SWarner Losh         BYTE* p = (BYTE*)memPtr;
1870c16b537SWarner Losh         p[0] = (BYTE)val;
1880c16b537SWarner Losh         p[1] = (BYTE)(val>>8);
1890c16b537SWarner Losh     }
1900c16b537SWarner Losh }
1910c16b537SWarner Losh 
1920c16b537SWarner Losh MEM_STATIC U32 MEM_readLE32(const void* memPtr)
1930c16b537SWarner Losh {
1940c16b537SWarner Losh     if (MEM_isLittleEndian())
1950c16b537SWarner Losh         return MEM_read32(memPtr);
1960c16b537SWarner Losh     else
1970c16b537SWarner Losh     {
1980c16b537SWarner Losh         const BYTE* p = (const BYTE*)memPtr;
1990c16b537SWarner Losh         return (U32)((U32)p[0] + ((U32)p[1]<<8) + ((U32)p[2]<<16) + ((U32)p[3]<<24));
2000c16b537SWarner Losh     }
2010c16b537SWarner Losh }
2020c16b537SWarner Losh 
2030c16b537SWarner Losh 
2040c16b537SWarner Losh MEM_STATIC U64 MEM_readLE64(const void* memPtr)
2050c16b537SWarner Losh {
2060c16b537SWarner Losh     if (MEM_isLittleEndian())
2070c16b537SWarner Losh         return MEM_read64(memPtr);
2080c16b537SWarner Losh     else
2090c16b537SWarner Losh     {
2100c16b537SWarner Losh         const BYTE* p = (const BYTE*)memPtr;
2110c16b537SWarner Losh         return (U64)((U64)p[0] + ((U64)p[1]<<8) + ((U64)p[2]<<16) + ((U64)p[3]<<24)
2120c16b537SWarner Losh                      + ((U64)p[4]<<32) + ((U64)p[5]<<40) + ((U64)p[6]<<48) + ((U64)p[7]<<56));
2130c16b537SWarner Losh     }
2140c16b537SWarner Losh }
2150c16b537SWarner Losh 
2160c16b537SWarner Losh 
2170c16b537SWarner Losh MEM_STATIC size_t MEM_readLEST(const void* memPtr)
2180c16b537SWarner Losh {
2190c16b537SWarner Losh     if (MEM_32bits())
2200c16b537SWarner Losh         return (size_t)MEM_readLE32(memPtr);
2210c16b537SWarner Losh     else
2220c16b537SWarner Losh         return (size_t)MEM_readLE64(memPtr);
2230c16b537SWarner Losh }
2240c16b537SWarner Losh 
2250c16b537SWarner Losh 
2260c16b537SWarner Losh #if defined (__cplusplus)
2270c16b537SWarner Losh }
2280c16b537SWarner Losh #endif
2290c16b537SWarner Losh 
2300c16b537SWarner Losh #endif /* MEM_H_MODULE */
2310c16b537SWarner Losh 
2320c16b537SWarner Losh /*
2330c16b537SWarner Losh     zstd - standard compression library
2340c16b537SWarner Losh     Header File for static linking only
2350c16b537SWarner Losh */
2360c16b537SWarner Losh #ifndef ZSTD_STATIC_H
2370c16b537SWarner Losh #define ZSTD_STATIC_H
2380c16b537SWarner Losh 
2390c16b537SWarner Losh 
2400c16b537SWarner Losh /* *************************************
2410c16b537SWarner Losh *  Types
2420c16b537SWarner Losh ***************************************/
2430c16b537SWarner Losh #define ZSTD_WINDOWLOG_ABSOLUTEMIN 11
2440c16b537SWarner Losh 
2450c16b537SWarner Losh /** from faster to stronger */
2460c16b537SWarner Losh typedef enum { ZSTD_fast, ZSTD_greedy, ZSTD_lazy, ZSTD_lazy2, ZSTD_btlazy2 } ZSTD_strategy;
2470c16b537SWarner Losh 
2480c16b537SWarner Losh typedef struct
2490c16b537SWarner Losh {
2500c16b537SWarner Losh     U64 srcSize;       /* optional : tells how much bytes are present in the frame. Use 0 if not known. */
2510c16b537SWarner Losh     U32 windowLog;     /* largest match distance : larger == more compression, more memory needed during decompression */
2520c16b537SWarner Losh     U32 contentLog;    /* full search segment : larger == more compression, slower, more memory (useless for fast) */
2530c16b537SWarner Losh     U32 hashLog;       /* dispatch table : larger == more memory, faster */
2540c16b537SWarner Losh     U32 searchLog;     /* nb of searches : larger == more compression, slower */
2550c16b537SWarner Losh     U32 searchLength;  /* size of matches : larger == faster decompression, sometimes less compression */
2560c16b537SWarner Losh     ZSTD_strategy strategy;
2570c16b537SWarner Losh } ZSTD_parameters;
2580c16b537SWarner Losh 
2590c16b537SWarner Losh typedef ZSTDv04_Dctx ZSTD_DCtx;
2600c16b537SWarner Losh 
2610c16b537SWarner Losh /* *************************************
2620c16b537SWarner Losh *  Advanced functions
2630c16b537SWarner Losh ***************************************/
2640c16b537SWarner Losh /** ZSTD_decompress_usingDict
2650c16b537SWarner Losh *   Same as ZSTD_decompressDCtx, using a Dictionary content as prefix
2660c16b537SWarner Losh *   Note : dict can be NULL, in which case, it's equivalent to ZSTD_decompressDCtx() */
2670c16b537SWarner Losh static size_t ZSTD_decompress_usingDict(ZSTD_DCtx* ctx,
2680c16b537SWarner Losh                                              void* dst, size_t maxDstSize,
2690c16b537SWarner Losh                                        const void* src, size_t srcSize,
2700c16b537SWarner Losh                                        const void* dict,size_t dictSize);
2710c16b537SWarner Losh 
2720c16b537SWarner Losh 
2730c16b537SWarner Losh /* **************************************
2740c16b537SWarner Losh *  Streaming functions (direct mode)
2750c16b537SWarner Losh ****************************************/
2760c16b537SWarner Losh static size_t ZSTD_resetDCtx(ZSTD_DCtx* dctx);
2770c16b537SWarner Losh static size_t ZSTD_getFrameParams(ZSTD_parameters* params, const void* src, size_t srcSize);
2780c16b537SWarner Losh static void   ZSTD_decompress_insertDictionary(ZSTD_DCtx* ctx, const void* src, size_t srcSize);
2790c16b537SWarner Losh 
2800c16b537SWarner Losh static size_t ZSTD_nextSrcSizeToDecompress(ZSTD_DCtx* dctx);
2810c16b537SWarner Losh static size_t ZSTD_decompressContinue(ZSTD_DCtx* dctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize);
2820c16b537SWarner Losh 
2830c16b537SWarner Losh /**
2840c16b537SWarner Losh   Streaming decompression, bufferless mode
2850c16b537SWarner Losh 
2860c16b537SWarner Losh   A ZSTD_DCtx object is required to track streaming operations.
2870c16b537SWarner Losh   Use ZSTD_createDCtx() / ZSTD_freeDCtx() to manage it.
2880c16b537SWarner Losh   A ZSTD_DCtx object can be re-used multiple times. Use ZSTD_resetDCtx() to return to fresh status.
2890c16b537SWarner Losh 
2900c16b537SWarner Losh   First operation is to retrieve frame parameters, using ZSTD_getFrameParams().
2910c16b537SWarner Losh   This function doesn't consume its input. It needs enough input data to properly decode the frame header.
2920c16b537SWarner Losh   Objective is to retrieve *params.windowlog, to know minimum amount of memory required during decoding.
2930c16b537SWarner Losh   Result : 0 when successful, it means the ZSTD_parameters structure has been filled.
2940c16b537SWarner Losh            >0 : means there is not enough data into src. Provides the expected size to successfully decode header.
2950c16b537SWarner Losh            errorCode, which can be tested using ZSTD_isError() (For example, if it's not a ZSTD header)
2960c16b537SWarner Losh 
2970c16b537SWarner Losh   Then, you can optionally insert a dictionary.
2980c16b537SWarner Losh   This operation must mimic the compressor behavior, otherwise decompression will fail or be corrupted.
2990c16b537SWarner Losh 
3000c16b537SWarner Losh   Then it's possible to start decompression.
3010c16b537SWarner Losh   Use ZSTD_nextSrcSizeToDecompress() and ZSTD_decompressContinue() alternatively.
3020c16b537SWarner Losh   ZSTD_nextSrcSizeToDecompress() tells how much bytes to provide as 'srcSize' to ZSTD_decompressContinue().
3030c16b537SWarner Losh   ZSTD_decompressContinue() requires this exact amount of bytes, or it will fail.
3040c16b537SWarner Losh   ZSTD_decompressContinue() needs previous data blocks during decompression, up to (1 << windowlog).
3050c16b537SWarner Losh   They should preferably be located contiguously, prior to current block. Alternatively, a round buffer is also possible.
3060c16b537SWarner Losh 
3070c16b537SWarner Losh   @result of ZSTD_decompressContinue() is the number of bytes regenerated within 'dst'.
3080c16b537SWarner Losh   It can be zero, which is not an error; it just means ZSTD_decompressContinue() has decoded some header.
3090c16b537SWarner Losh 
3100c16b537SWarner Losh   A frame is fully decoded when ZSTD_nextSrcSizeToDecompress() returns zero.
3110c16b537SWarner Losh   Context can then be reset to start a new decompression.
3120c16b537SWarner Losh */
3130c16b537SWarner Losh 
3140c16b537SWarner Losh 
3150c16b537SWarner Losh 
3160c16b537SWarner Losh 
3170c16b537SWarner Losh #endif  /* ZSTD_STATIC_H */
3180c16b537SWarner Losh 
3190c16b537SWarner Losh 
3200c16b537SWarner Losh /*
3210c16b537SWarner Losh     zstd_internal - common functions to include
3220c16b537SWarner Losh     Header File for include
3230c16b537SWarner Losh */
3240c16b537SWarner Losh #ifndef ZSTD_CCOMMON_H_MODULE
3250c16b537SWarner Losh #define ZSTD_CCOMMON_H_MODULE
3260c16b537SWarner Losh 
3270c16b537SWarner Losh /* *************************************
3280c16b537SWarner Losh *  Common macros
3290c16b537SWarner Losh ***************************************/
3300c16b537SWarner Losh #define MIN(a,b) ((a)<(b) ? (a) : (b))
3310c16b537SWarner Losh #define MAX(a,b) ((a)>(b) ? (a) : (b))
3320c16b537SWarner Losh 
3330c16b537SWarner Losh 
3340c16b537SWarner Losh /* *************************************
3350c16b537SWarner Losh *  Common constants
3360c16b537SWarner Losh ***************************************/
3370c16b537SWarner Losh #define ZSTD_MAGICNUMBER 0xFD2FB524   /* v0.4 */
3380c16b537SWarner Losh 
3390c16b537SWarner Losh #define KB *(1 <<10)
3400c16b537SWarner Losh #define MB *(1 <<20)
3410c16b537SWarner Losh #define GB *(1U<<30)
3420c16b537SWarner Losh 
3430c16b537SWarner Losh #define BLOCKSIZE (128 KB)                 /* define, for static allocation */
3440c16b537SWarner Losh 
3450c16b537SWarner Losh static const size_t ZSTD_blockHeaderSize = 3;
3460c16b537SWarner Losh static const size_t ZSTD_frameHeaderSize_min = 5;
3470c16b537SWarner Losh #define ZSTD_frameHeaderSize_max 5         /* define, for static allocation */
3480c16b537SWarner Losh 
3490c16b537SWarner Losh #define BIT7 128
3500c16b537SWarner Losh #define BIT6  64
3510c16b537SWarner Losh #define BIT5  32
3520c16b537SWarner Losh #define BIT4  16
3530c16b537SWarner Losh #define BIT1   2
3540c16b537SWarner Losh #define BIT0   1
3550c16b537SWarner Losh 
3560c16b537SWarner Losh #define IS_RAW BIT0
3570c16b537SWarner Losh #define IS_RLE BIT1
3580c16b537SWarner Losh 
3590c16b537SWarner Losh #define MINMATCH 4
3600c16b537SWarner Losh #define REPCODE_STARTVALUE 4
3610c16b537SWarner Losh 
3620c16b537SWarner Losh #define MLbits   7
3630c16b537SWarner Losh #define LLbits   6
3640c16b537SWarner Losh #define Offbits  5
3650c16b537SWarner Losh #define MaxML  ((1<<MLbits) - 1)
3660c16b537SWarner Losh #define MaxLL  ((1<<LLbits) - 1)
3670c16b537SWarner Losh #define MaxOff ((1<<Offbits)- 1)
3680c16b537SWarner Losh #define MLFSELog   10
3690c16b537SWarner Losh #define LLFSELog   10
3700c16b537SWarner Losh #define OffFSELog   9
3710c16b537SWarner Losh #define MaxSeq MAX(MaxLL, MaxML)
3720c16b537SWarner Losh 
3730c16b537SWarner Losh #define MIN_SEQUENCES_SIZE (2 /*seqNb*/ + 2 /*dumps*/ + 3 /*seqTables*/ + 1 /*bitStream*/)
3740c16b537SWarner Losh #define MIN_CBLOCK_SIZE (3 /*litCSize*/ + MIN_SEQUENCES_SIZE)
3750c16b537SWarner Losh 
376*2b9c00cbSConrad Meyer #define ZSTD_CONTENTSIZE_ERROR   (0ULL - 2)
377*2b9c00cbSConrad Meyer 
3780c16b537SWarner Losh typedef enum { bt_compressed, bt_raw, bt_rle, bt_end } blockType_t;
3790c16b537SWarner Losh 
3800c16b537SWarner Losh 
3810c16b537SWarner Losh /* ******************************************
3820c16b537SWarner Losh *  Shared functions to include for inlining
3830c16b537SWarner Losh ********************************************/
3840c16b537SWarner Losh static void ZSTD_copy8(void* dst, const void* src) { memcpy(dst, src, 8); }
3850c16b537SWarner Losh 
3860c16b537SWarner Losh #define COPY8(d,s) { ZSTD_copy8(d,s); d+=8; s+=8; }
3870c16b537SWarner Losh 
3880c16b537SWarner Losh /*! ZSTD_wildcopy : custom version of memcpy(), can copy up to 7-8 bytes too many */
3890c16b537SWarner Losh static void ZSTD_wildcopy(void* dst, const void* src, ptrdiff_t length)
3900c16b537SWarner Losh {
3910c16b537SWarner Losh     const BYTE* ip = (const BYTE*)src;
3920c16b537SWarner Losh     BYTE* op = (BYTE*)dst;
3930c16b537SWarner Losh     BYTE* const oend = op + length;
3940c16b537SWarner Losh     do
3950c16b537SWarner Losh         COPY8(op, ip)
3960c16b537SWarner Losh     while (op < oend);
3970c16b537SWarner Losh }
3980c16b537SWarner Losh 
3990c16b537SWarner Losh 
4000c16b537SWarner Losh 
4010c16b537SWarner Losh /* ******************************************************************
4020c16b537SWarner Losh    FSE : Finite State Entropy coder
4030c16b537SWarner Losh    header file
4040c16b537SWarner Losh ****************************************************************** */
4050c16b537SWarner Losh #ifndef FSE_H
4060c16b537SWarner Losh #define FSE_H
4070c16b537SWarner Losh 
4080c16b537SWarner Losh #if defined (__cplusplus)
4090c16b537SWarner Losh extern "C" {
4100c16b537SWarner Losh #endif
4110c16b537SWarner Losh 
4120c16b537SWarner Losh 
4130c16b537SWarner Losh /* *****************************************
4140c16b537SWarner Losh *  Includes
4150c16b537SWarner Losh ******************************************/
4160c16b537SWarner Losh #include <stddef.h>    /* size_t, ptrdiff_t */
4170c16b537SWarner Losh 
4180c16b537SWarner Losh 
4190c16b537SWarner Losh /* *****************************************
4200c16b537SWarner Losh *  FSE simple functions
4210c16b537SWarner Losh ******************************************/
4220c16b537SWarner Losh static size_t FSE_decompress(void* dst,  size_t maxDstSize,
4230c16b537SWarner Losh                 const void* cSrc, size_t cSrcSize);
4240c16b537SWarner Losh /*!
4250c16b537SWarner Losh FSE_decompress():
4260c16b537SWarner Losh     Decompress FSE data from buffer 'cSrc', of size 'cSrcSize',
4270c16b537SWarner Losh     into already allocated destination buffer 'dst', of size 'maxDstSize'.
4280c16b537SWarner Losh     return : size of regenerated data (<= maxDstSize)
4290c16b537SWarner Losh              or an error code, which can be tested using FSE_isError()
4300c16b537SWarner Losh 
4310c16b537SWarner Losh     ** Important ** : FSE_decompress() doesn't decompress non-compressible nor RLE data !!!
4320c16b537SWarner Losh     Why ? : making this distinction requires a header.
4330c16b537SWarner Losh     Header management is intentionally delegated to the user layer, which can better manage special cases.
4340c16b537SWarner Losh */
4350c16b537SWarner Losh 
4360c16b537SWarner Losh 
4370c16b537SWarner Losh /* *****************************************
4380c16b537SWarner Losh *  Tool functions
4390c16b537SWarner Losh ******************************************/
4400c16b537SWarner Losh /* Error Management */
4410c16b537SWarner Losh static unsigned    FSE_isError(size_t code);        /* tells if a return value is an error code */
4420c16b537SWarner Losh 
4430c16b537SWarner Losh 
4440c16b537SWarner Losh 
4450c16b537SWarner Losh /* *****************************************
4460c16b537SWarner Losh *  FSE detailed API
4470c16b537SWarner Losh ******************************************/
4480c16b537SWarner Losh /*!
4490c16b537SWarner Losh FSE_compress() does the following:
4500c16b537SWarner Losh 1. count symbol occurrence from source[] into table count[]
4510c16b537SWarner Losh 2. normalize counters so that sum(count[]) == Power_of_2 (2^tableLog)
4520c16b537SWarner Losh 3. save normalized counters to memory buffer using writeNCount()
4530c16b537SWarner Losh 4. build encoding table 'CTable' from normalized counters
4540c16b537SWarner Losh 5. encode the data stream using encoding table 'CTable'
4550c16b537SWarner Losh 
4560c16b537SWarner Losh FSE_decompress() does the following:
4570c16b537SWarner Losh 1. read normalized counters with readNCount()
4580c16b537SWarner Losh 2. build decoding table 'DTable' from normalized counters
4590c16b537SWarner Losh 3. decode the data stream using decoding table 'DTable'
4600c16b537SWarner Losh 
4610c16b537SWarner Losh The following API allows targeting specific sub-functions for advanced tasks.
4620c16b537SWarner Losh For example, it's possible to compress several blocks using the same 'CTable',
4630c16b537SWarner Losh or to save and provide normalized distribution using external method.
4640c16b537SWarner Losh */
4650c16b537SWarner Losh 
4660c16b537SWarner Losh 
4670c16b537SWarner Losh /* *** DECOMPRESSION *** */
4680c16b537SWarner Losh 
4690c16b537SWarner Losh /*!
4700c16b537SWarner Losh FSE_readNCount():
4710c16b537SWarner Losh    Read compactly saved 'normalizedCounter' from 'rBuffer'.
4720c16b537SWarner Losh    return : size read from 'rBuffer'
4730c16b537SWarner Losh             or an errorCode, which can be tested using FSE_isError()
4740c16b537SWarner Losh             maxSymbolValuePtr[0] and tableLogPtr[0] will also be updated with their respective values */
4750c16b537SWarner Losh static  size_t FSE_readNCount (short* normalizedCounter, unsigned* maxSymbolValuePtr, unsigned* tableLogPtr, const void* rBuffer, size_t rBuffSize);
4760c16b537SWarner Losh 
4770c16b537SWarner Losh /*!
4780c16b537SWarner Losh Constructor and Destructor of type FSE_DTable
4790c16b537SWarner Losh     Note that its size depends on 'tableLog' */
4800c16b537SWarner Losh typedef unsigned FSE_DTable;   /* don't allocate that. It's just a way to be more restrictive than void* */
4810c16b537SWarner Losh 
4820c16b537SWarner Losh /*!
4830c16b537SWarner Losh FSE_buildDTable():
4840c16b537SWarner Losh    Builds 'dt', which must be already allocated, using FSE_createDTable()
4850c16b537SWarner Losh    return : 0,
4860c16b537SWarner Losh             or an errorCode, which can be tested using FSE_isError() */
4870c16b537SWarner Losh static size_t FSE_buildDTable ( FSE_DTable* dt, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog);
4880c16b537SWarner Losh 
4890c16b537SWarner Losh /*!
4900c16b537SWarner Losh FSE_decompress_usingDTable():
4910c16b537SWarner Losh    Decompress compressed source 'cSrc' of size 'cSrcSize' using 'dt'
4920c16b537SWarner Losh    into 'dst' which must be already allocated.
4930c16b537SWarner Losh    return : size of regenerated data (necessarily <= maxDstSize)
4940c16b537SWarner Losh             or an errorCode, which can be tested using FSE_isError() */
4950c16b537SWarner Losh static  size_t FSE_decompress_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const FSE_DTable* dt);
4960c16b537SWarner Losh 
4970c16b537SWarner Losh /*!
4980c16b537SWarner Losh Tutorial :
4990c16b537SWarner Losh ----------
5000c16b537SWarner Losh (Note : these functions only decompress FSE-compressed blocks.
5010c16b537SWarner Losh  If block is uncompressed, use memcpy() instead
5020c16b537SWarner Losh  If block is a single repeated byte, use memset() instead )
5030c16b537SWarner Losh 
5040c16b537SWarner Losh The first step is to obtain the normalized frequencies of symbols.
5050c16b537SWarner Losh This can be performed by FSE_readNCount() if it was saved using FSE_writeNCount().
5060c16b537SWarner Losh 'normalizedCounter' must be already allocated, and have at least 'maxSymbolValuePtr[0]+1' cells of signed short.
5070c16b537SWarner Losh In practice, that means it's necessary to know 'maxSymbolValue' beforehand,
5080c16b537SWarner Losh or size the table to handle worst case situations (typically 256).
5090c16b537SWarner Losh FSE_readNCount() will provide 'tableLog' and 'maxSymbolValue'.
5100c16b537SWarner Losh The result of FSE_readNCount() is the number of bytes read from 'rBuffer'.
5110c16b537SWarner Losh Note that 'rBufferSize' must be at least 4 bytes, even if useful information is less than that.
5120c16b537SWarner Losh If there is an error, the function will return an error code, which can be tested using FSE_isError().
5130c16b537SWarner Losh 
5140c16b537SWarner Losh The next step is to build the decompression tables 'FSE_DTable' from 'normalizedCounter'.
5150c16b537SWarner Losh This is performed by the function FSE_buildDTable().
5160c16b537SWarner Losh The space required by 'FSE_DTable' must be already allocated using FSE_createDTable().
5170c16b537SWarner Losh If there is an error, the function will return an error code, which can be tested using FSE_isError().
5180c16b537SWarner Losh 
5190c16b537SWarner Losh 'FSE_DTable' can then be used to decompress 'cSrc', with FSE_decompress_usingDTable().
5200c16b537SWarner Losh 'cSrcSize' must be strictly correct, otherwise decompression will fail.
5210c16b537SWarner Losh FSE_decompress_usingDTable() result will tell how many bytes were regenerated (<=maxDstSize).
5220c16b537SWarner Losh If there is an error, the function will return an error code, which can be tested using FSE_isError(). (ex: dst buffer too small)
5230c16b537SWarner Losh */
5240c16b537SWarner Losh 
5250c16b537SWarner Losh 
5260c16b537SWarner Losh #if defined (__cplusplus)
5270c16b537SWarner Losh }
5280c16b537SWarner Losh #endif
5290c16b537SWarner Losh 
5300c16b537SWarner Losh #endif  /* FSE_H */
5310c16b537SWarner Losh 
5320c16b537SWarner Losh 
5330c16b537SWarner Losh /* ******************************************************************
5340c16b537SWarner Losh    bitstream
5350c16b537SWarner Losh    Part of NewGen Entropy library
5360c16b537SWarner Losh    header file (to include)
5370c16b537SWarner Losh    Copyright (C) 2013-2015, Yann Collet.
5380c16b537SWarner Losh 
5390c16b537SWarner Losh    BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
5400c16b537SWarner Losh 
5410c16b537SWarner Losh    Redistribution and use in source and binary forms, with or without
5420c16b537SWarner Losh    modification, are permitted provided that the following conditions are
5430c16b537SWarner Losh    met:
5440c16b537SWarner Losh 
5450c16b537SWarner Losh        * Redistributions of source code must retain the above copyright
5460c16b537SWarner Losh    notice, this list of conditions and the following disclaimer.
5470c16b537SWarner Losh        * Redistributions in binary form must reproduce the above
5480c16b537SWarner Losh    copyright notice, this list of conditions and the following disclaimer
5490c16b537SWarner Losh    in the documentation and/or other materials provided with the
5500c16b537SWarner Losh    distribution.
5510c16b537SWarner Losh 
5520c16b537SWarner Losh    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
5530c16b537SWarner Losh    "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
5540c16b537SWarner Losh    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
5550c16b537SWarner Losh    A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
5560c16b537SWarner Losh    OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
5570c16b537SWarner Losh    SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
5580c16b537SWarner Losh    LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
5590c16b537SWarner Losh    DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
5600c16b537SWarner Losh    THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
5610c16b537SWarner Losh    (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
5620c16b537SWarner Losh    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
5630c16b537SWarner Losh 
5640c16b537SWarner Losh    You can contact the author at :
5650c16b537SWarner Losh    - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
5660c16b537SWarner Losh    - Public forum : https://groups.google.com/forum/#!forum/lz4c
5670c16b537SWarner Losh ****************************************************************** */
5680c16b537SWarner Losh #ifndef BITSTREAM_H_MODULE
5690c16b537SWarner Losh #define BITSTREAM_H_MODULE
5700c16b537SWarner Losh 
5710c16b537SWarner Losh #if defined (__cplusplus)
5720c16b537SWarner Losh extern "C" {
5730c16b537SWarner Losh #endif
5740c16b537SWarner Losh 
5750c16b537SWarner Losh 
5760c16b537SWarner Losh /*
5770c16b537SWarner Losh *  This API consists of small unitary functions, which highly benefit from being inlined.
5780c16b537SWarner Losh *  Since link-time-optimization is not available for all compilers,
5790c16b537SWarner Losh *  these functions are defined into a .h to be included.
5800c16b537SWarner Losh */
5810c16b537SWarner Losh 
5820c16b537SWarner Losh /**********************************************
5830c16b537SWarner Losh *  bitStream decompression API (read backward)
5840c16b537SWarner Losh **********************************************/
5850c16b537SWarner Losh typedef struct
5860c16b537SWarner Losh {
5870c16b537SWarner Losh     size_t   bitContainer;
5880c16b537SWarner Losh     unsigned bitsConsumed;
5890c16b537SWarner Losh     const char* ptr;
5900c16b537SWarner Losh     const char* start;
5910c16b537SWarner Losh } BIT_DStream_t;
5920c16b537SWarner Losh 
5930c16b537SWarner Losh typedef enum { BIT_DStream_unfinished = 0,
5940c16b537SWarner Losh                BIT_DStream_endOfBuffer = 1,
5950c16b537SWarner Losh                BIT_DStream_completed = 2,
5960c16b537SWarner Losh                BIT_DStream_overflow = 3 } BIT_DStream_status;  /* result of BIT_reloadDStream() */
5970c16b537SWarner Losh                /* 1,2,4,8 would be better for bitmap combinations, but slows down performance a bit ... :( */
5980c16b537SWarner Losh 
5990c16b537SWarner Losh MEM_STATIC size_t   BIT_initDStream(BIT_DStream_t* bitD, const void* srcBuffer, size_t srcSize);
6000c16b537SWarner Losh MEM_STATIC size_t   BIT_readBits(BIT_DStream_t* bitD, unsigned nbBits);
6010c16b537SWarner Losh MEM_STATIC BIT_DStream_status BIT_reloadDStream(BIT_DStream_t* bitD);
6020c16b537SWarner Losh MEM_STATIC unsigned BIT_endOfDStream(const BIT_DStream_t* bitD);
6030c16b537SWarner Losh 
6040c16b537SWarner Losh 
6050c16b537SWarner Losh 
6060c16b537SWarner Losh 
6070c16b537SWarner Losh /******************************************
6080c16b537SWarner Losh *  unsafe API
6090c16b537SWarner Losh ******************************************/
6100c16b537SWarner Losh MEM_STATIC size_t BIT_readBitsFast(BIT_DStream_t* bitD, unsigned nbBits);
6110c16b537SWarner Losh /* faster, but works only if nbBits >= 1 */
6120c16b537SWarner Losh 
6130c16b537SWarner Losh 
6140c16b537SWarner Losh 
6150c16b537SWarner Losh /****************************************************************
6160c16b537SWarner Losh *  Helper functions
6170c16b537SWarner Losh ****************************************************************/
618052d3c12SConrad Meyer MEM_STATIC unsigned BIT_highbit32 (U32 val)
6190c16b537SWarner Losh {
6200c16b537SWarner Losh #   if defined(_MSC_VER)   /* Visual */
6210c16b537SWarner Losh     unsigned long r=0;
6220c16b537SWarner Losh     _BitScanReverse ( &r, val );
6230c16b537SWarner Losh     return (unsigned) r;
6240c16b537SWarner Losh #   elif defined(__GNUC__) && (__GNUC__ >= 3)   /* Use GCC Intrinsic */
6250c16b537SWarner Losh     return 31 - __builtin_clz (val);
6260c16b537SWarner Losh #   else   /* Software version */
6270c16b537SWarner Losh     static const unsigned DeBruijnClz[32] = { 0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30, 8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31 };
6280c16b537SWarner Losh     U32 v = val;
6290c16b537SWarner Losh     unsigned r;
6300c16b537SWarner Losh     v |= v >> 1;
6310c16b537SWarner Losh     v |= v >> 2;
6320c16b537SWarner Losh     v |= v >> 4;
6330c16b537SWarner Losh     v |= v >> 8;
6340c16b537SWarner Losh     v |= v >> 16;
6350c16b537SWarner Losh     r = DeBruijnClz[ (U32) (v * 0x07C4ACDDU) >> 27];
6360c16b537SWarner Losh     return r;
6370c16b537SWarner Losh #   endif
6380c16b537SWarner Losh }
6390c16b537SWarner Losh 
6400c16b537SWarner Losh 
6410c16b537SWarner Losh /**********************************************************
6420c16b537SWarner Losh * bitStream decoding
6430c16b537SWarner Losh **********************************************************/
6440c16b537SWarner Losh 
6450c16b537SWarner Losh /*!BIT_initDStream
6460c16b537SWarner Losh *  Initialize a BIT_DStream_t.
6470c16b537SWarner Losh *  @bitD : a pointer to an already allocated BIT_DStream_t structure
6480c16b537SWarner Losh *  @srcBuffer must point at the beginning of a bitStream
6490c16b537SWarner Losh *  @srcSize must be the exact size of the bitStream
6500c16b537SWarner Losh *  @result : size of stream (== srcSize) or an errorCode if a problem is detected
6510c16b537SWarner Losh */
6520c16b537SWarner Losh MEM_STATIC size_t BIT_initDStream(BIT_DStream_t* bitD, const void* srcBuffer, size_t srcSize)
6530c16b537SWarner Losh {
6540c16b537SWarner Losh     if (srcSize < 1) { memset(bitD, 0, sizeof(*bitD)); return ERROR(srcSize_wrong); }
6550c16b537SWarner Losh 
6560c16b537SWarner Losh     if (srcSize >=  sizeof(size_t))   /* normal case */
6570c16b537SWarner Losh     {
6580c16b537SWarner Losh         U32 contain32;
6590c16b537SWarner Losh         bitD->start = (const char*)srcBuffer;
6600c16b537SWarner Losh         bitD->ptr   = (const char*)srcBuffer + srcSize - sizeof(size_t);
6610c16b537SWarner Losh         bitD->bitContainer = MEM_readLEST(bitD->ptr);
6620c16b537SWarner Losh         contain32 = ((const BYTE*)srcBuffer)[srcSize-1];
6630c16b537SWarner Losh         if (contain32 == 0) return ERROR(GENERIC);   /* endMark not present */
6640c16b537SWarner Losh         bitD->bitsConsumed = 8 - BIT_highbit32(contain32);
6650c16b537SWarner Losh     }
6660c16b537SWarner Losh     else
6670c16b537SWarner Losh     {
6680c16b537SWarner Losh         U32 contain32;
6690c16b537SWarner Losh         bitD->start = (const char*)srcBuffer;
6700c16b537SWarner Losh         bitD->ptr   = bitD->start;
6710c16b537SWarner Losh         bitD->bitContainer = *(const BYTE*)(bitD->start);
6720c16b537SWarner Losh         switch(srcSize)
6730c16b537SWarner Losh         {
6740c16b537SWarner Losh             case 7: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[6]) << (sizeof(size_t)*8 - 16);/* fall-through */
6750c16b537SWarner Losh             case 6: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[5]) << (sizeof(size_t)*8 - 24);/* fall-through */
6760c16b537SWarner Losh             case 5: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[4]) << (sizeof(size_t)*8 - 32);/* fall-through */
6770c16b537SWarner Losh             case 4: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[3]) << 24; /* fall-through */
6780c16b537SWarner Losh             case 3: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[2]) << 16; /* fall-through */
6790c16b537SWarner Losh             case 2: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[1]) <<  8; /* fall-through */
6800c16b537SWarner Losh             default: break;
6810c16b537SWarner Losh         }
6820c16b537SWarner Losh         contain32 = ((const BYTE*)srcBuffer)[srcSize-1];
6830c16b537SWarner Losh         if (contain32 == 0) return ERROR(GENERIC);   /* endMark not present */
6840c16b537SWarner Losh         bitD->bitsConsumed = 8 - BIT_highbit32(contain32);
6850c16b537SWarner Losh         bitD->bitsConsumed += (U32)(sizeof(size_t) - srcSize)*8;
6860c16b537SWarner Losh     }
6870c16b537SWarner Losh 
6880c16b537SWarner Losh     return srcSize;
6890c16b537SWarner Losh }
6900c16b537SWarner Losh 
6910c16b537SWarner Losh MEM_STATIC size_t BIT_lookBits(BIT_DStream_t* bitD, U32 nbBits)
6920c16b537SWarner Losh {
6930c16b537SWarner Losh     const U32 bitMask = sizeof(bitD->bitContainer)*8 - 1;
6940c16b537SWarner Losh     return ((bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> 1) >> ((bitMask-nbBits) & bitMask);
6950c16b537SWarner Losh }
6960c16b537SWarner Losh 
6970c16b537SWarner Losh /*! BIT_lookBitsFast :
6980c16b537SWarner Losh *   unsafe version; only works only if nbBits >= 1 */
6990c16b537SWarner Losh MEM_STATIC size_t BIT_lookBitsFast(BIT_DStream_t* bitD, U32 nbBits)
7000c16b537SWarner Losh {
7010c16b537SWarner Losh     const U32 bitMask = sizeof(bitD->bitContainer)*8 - 1;
7020c16b537SWarner Losh     return (bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> (((bitMask+1)-nbBits) & bitMask);
7030c16b537SWarner Losh }
7040c16b537SWarner Losh 
7050c16b537SWarner Losh MEM_STATIC void BIT_skipBits(BIT_DStream_t* bitD, U32 nbBits)
7060c16b537SWarner Losh {
7070c16b537SWarner Losh     bitD->bitsConsumed += nbBits;
7080c16b537SWarner Losh }
7090c16b537SWarner Losh 
7100c16b537SWarner Losh MEM_STATIC size_t BIT_readBits(BIT_DStream_t* bitD, U32 nbBits)
7110c16b537SWarner Losh {
7120c16b537SWarner Losh     size_t value = BIT_lookBits(bitD, nbBits);
7130c16b537SWarner Losh     BIT_skipBits(bitD, nbBits);
7140c16b537SWarner Losh     return value;
7150c16b537SWarner Losh }
7160c16b537SWarner Losh 
7170c16b537SWarner Losh /*!BIT_readBitsFast :
7180c16b537SWarner Losh *  unsafe version; only works only if nbBits >= 1 */
7190c16b537SWarner Losh MEM_STATIC size_t BIT_readBitsFast(BIT_DStream_t* bitD, U32 nbBits)
7200c16b537SWarner Losh {
7210c16b537SWarner Losh     size_t value = BIT_lookBitsFast(bitD, nbBits);
7220c16b537SWarner Losh     BIT_skipBits(bitD, nbBits);
7230c16b537SWarner Losh     return value;
7240c16b537SWarner Losh }
7250c16b537SWarner Losh 
7260c16b537SWarner Losh MEM_STATIC BIT_DStream_status BIT_reloadDStream(BIT_DStream_t* bitD)
7270c16b537SWarner Losh {
7280c16b537SWarner Losh     if (bitD->bitsConsumed > (sizeof(bitD->bitContainer)*8))  /* should never happen */
7290c16b537SWarner Losh         return BIT_DStream_overflow;
7300c16b537SWarner Losh 
7310c16b537SWarner Losh     if (bitD->ptr >= bitD->start + sizeof(bitD->bitContainer))
7320c16b537SWarner Losh     {
7330c16b537SWarner Losh         bitD->ptr -= bitD->bitsConsumed >> 3;
7340c16b537SWarner Losh         bitD->bitsConsumed &= 7;
7350c16b537SWarner Losh         bitD->bitContainer = MEM_readLEST(bitD->ptr);
7360c16b537SWarner Losh         return BIT_DStream_unfinished;
7370c16b537SWarner Losh     }
7380c16b537SWarner Losh     if (bitD->ptr == bitD->start)
7390c16b537SWarner Losh     {
7400c16b537SWarner Losh         if (bitD->bitsConsumed < sizeof(bitD->bitContainer)*8) return BIT_DStream_endOfBuffer;
7410c16b537SWarner Losh         return BIT_DStream_completed;
7420c16b537SWarner Losh     }
7430c16b537SWarner Losh     {
7440c16b537SWarner Losh         U32 nbBytes = bitD->bitsConsumed >> 3;
7450c16b537SWarner Losh         BIT_DStream_status result = BIT_DStream_unfinished;
7460c16b537SWarner Losh         if (bitD->ptr - nbBytes < bitD->start)
7470c16b537SWarner Losh         {
7480c16b537SWarner Losh             nbBytes = (U32)(bitD->ptr - bitD->start);  /* ptr > start */
7490c16b537SWarner Losh             result = BIT_DStream_endOfBuffer;
7500c16b537SWarner Losh         }
7510c16b537SWarner Losh         bitD->ptr -= nbBytes;
7520c16b537SWarner Losh         bitD->bitsConsumed -= nbBytes*8;
7530c16b537SWarner Losh         bitD->bitContainer = MEM_readLEST(bitD->ptr);   /* reminder : srcSize > sizeof(bitD) */
7540c16b537SWarner Losh         return result;
7550c16b537SWarner Losh     }
7560c16b537SWarner Losh }
7570c16b537SWarner Losh 
7580c16b537SWarner Losh /*! BIT_endOfDStream
7590c16b537SWarner Losh *   @return Tells if DStream has reached its exact end
7600c16b537SWarner Losh */
7610c16b537SWarner Losh MEM_STATIC unsigned BIT_endOfDStream(const BIT_DStream_t* DStream)
7620c16b537SWarner Losh {
7630c16b537SWarner Losh     return ((DStream->ptr == DStream->start) && (DStream->bitsConsumed == sizeof(DStream->bitContainer)*8));
7640c16b537SWarner Losh }
7650c16b537SWarner Losh 
7660c16b537SWarner Losh #if defined (__cplusplus)
7670c16b537SWarner Losh }
7680c16b537SWarner Losh #endif
7690c16b537SWarner Losh 
7700c16b537SWarner Losh #endif /* BITSTREAM_H_MODULE */
7710c16b537SWarner Losh 
7720c16b537SWarner Losh 
7730c16b537SWarner Losh 
7740c16b537SWarner Losh /* ******************************************************************
7750c16b537SWarner Losh    FSE : Finite State Entropy coder
7760c16b537SWarner Losh    header file for static linking (only)
7770c16b537SWarner Losh    Copyright (C) 2013-2015, Yann Collet
7780c16b537SWarner Losh 
7790c16b537SWarner Losh    BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
7800c16b537SWarner Losh 
7810c16b537SWarner Losh    Redistribution and use in source and binary forms, with or without
7820c16b537SWarner Losh    modification, are permitted provided that the following conditions are
7830c16b537SWarner Losh    met:
7840c16b537SWarner Losh 
7850c16b537SWarner Losh        * Redistributions of source code must retain the above copyright
7860c16b537SWarner Losh    notice, this list of conditions and the following disclaimer.
7870c16b537SWarner Losh        * Redistributions in binary form must reproduce the above
7880c16b537SWarner Losh    copyright notice, this list of conditions and the following disclaimer
7890c16b537SWarner Losh    in the documentation and/or other materials provided with the
7900c16b537SWarner Losh    distribution.
7910c16b537SWarner Losh 
7920c16b537SWarner Losh    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
7930c16b537SWarner Losh    "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
7940c16b537SWarner Losh    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
7950c16b537SWarner Losh    A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
7960c16b537SWarner Losh    OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
7970c16b537SWarner Losh    SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
7980c16b537SWarner Losh    LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
7990c16b537SWarner Losh    DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
8000c16b537SWarner Losh    THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
8010c16b537SWarner Losh    (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
8020c16b537SWarner Losh    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
8030c16b537SWarner Losh 
8040c16b537SWarner Losh    You can contact the author at :
8050c16b537SWarner Losh    - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
8060c16b537SWarner Losh    - Public forum : https://groups.google.com/forum/#!forum/lz4c
8070c16b537SWarner Losh ****************************************************************** */
8080c16b537SWarner Losh #ifndef FSE_STATIC_H
8090c16b537SWarner Losh #define FSE_STATIC_H
8100c16b537SWarner Losh 
8110c16b537SWarner Losh #if defined (__cplusplus)
8120c16b537SWarner Losh extern "C" {
8130c16b537SWarner Losh #endif
8140c16b537SWarner Losh 
8150c16b537SWarner Losh 
8160c16b537SWarner Losh /* *****************************************
8170c16b537SWarner Losh *  Static allocation
8180c16b537SWarner Losh *******************************************/
8190c16b537SWarner Losh /* FSE buffer bounds */
8200c16b537SWarner Losh #define FSE_NCOUNTBOUND 512
8210c16b537SWarner Losh #define FSE_BLOCKBOUND(size) (size + (size>>7))
8220c16b537SWarner Losh #define FSE_COMPRESSBOUND(size) (FSE_NCOUNTBOUND + FSE_BLOCKBOUND(size))   /* Macro version, useful for static allocation */
8230c16b537SWarner Losh 
8240c16b537SWarner Losh /* It is possible to statically allocate FSE CTable/DTable as a table of unsigned using below macros */
8250c16b537SWarner Losh #define FSE_CTABLE_SIZE_U32(maxTableLog, maxSymbolValue)   (1 + (1<<(maxTableLog-1)) + ((maxSymbolValue+1)*2))
8260c16b537SWarner Losh #define FSE_DTABLE_SIZE_U32(maxTableLog)                   (1 + (1<<maxTableLog))
8270c16b537SWarner Losh 
8280c16b537SWarner Losh 
8290c16b537SWarner Losh /* *****************************************
8300c16b537SWarner Losh *  FSE advanced API
8310c16b537SWarner Losh *******************************************/
8320c16b537SWarner Losh static size_t FSE_buildDTable_raw (FSE_DTable* dt, unsigned nbBits);
8330c16b537SWarner Losh /* build a fake FSE_DTable, designed to read an uncompressed bitstream where each symbol uses nbBits */
8340c16b537SWarner Losh 
8350c16b537SWarner Losh static size_t FSE_buildDTable_rle (FSE_DTable* dt, unsigned char symbolValue);
8360c16b537SWarner Losh /* build a fake FSE_DTable, designed to always generate the same symbolValue */
8370c16b537SWarner Losh 
8380c16b537SWarner Losh 
8390c16b537SWarner Losh 
8400c16b537SWarner Losh /* *****************************************
8410c16b537SWarner Losh *  FSE symbol decompression API
8420c16b537SWarner Losh *******************************************/
8430c16b537SWarner Losh typedef struct
8440c16b537SWarner Losh {
8450c16b537SWarner Losh     size_t      state;
8460c16b537SWarner Losh     const void* table;   /* precise table may vary, depending on U16 */
8470c16b537SWarner Losh } FSE_DState_t;
8480c16b537SWarner Losh 
8490c16b537SWarner Losh 
8500c16b537SWarner Losh static void     FSE_initDState(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD, const FSE_DTable* dt);
8510c16b537SWarner Losh 
8520c16b537SWarner Losh static unsigned char FSE_decodeSymbol(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD);
8530c16b537SWarner Losh 
8540c16b537SWarner Losh static unsigned FSE_endOfDState(const FSE_DState_t* DStatePtr);
8550c16b537SWarner Losh 
8560c16b537SWarner Losh 
8570c16b537SWarner Losh /* *****************************************
8580c16b537SWarner Losh *  FSE unsafe API
8590c16b537SWarner Losh *******************************************/
8600c16b537SWarner Losh static unsigned char FSE_decodeSymbolFast(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD);
8610c16b537SWarner Losh /* faster, but works only if nbBits is always >= 1 (otherwise, result will be corrupted) */
8620c16b537SWarner Losh 
8630c16b537SWarner Losh 
8640c16b537SWarner Losh /* *****************************************
8650c16b537SWarner Losh *  Implementation of inlined functions
8660c16b537SWarner Losh *******************************************/
8670c16b537SWarner Losh /* decompression */
8680c16b537SWarner Losh 
8690c16b537SWarner Losh typedef struct {
8700c16b537SWarner Losh     U16 tableLog;
8710c16b537SWarner Losh     U16 fastMode;
8720c16b537SWarner Losh } FSE_DTableHeader;   /* sizeof U32 */
8730c16b537SWarner Losh 
8740c16b537SWarner Losh typedef struct
8750c16b537SWarner Losh {
8760c16b537SWarner Losh     unsigned short newState;
8770c16b537SWarner Losh     unsigned char  symbol;
8780c16b537SWarner Losh     unsigned char  nbBits;
8790c16b537SWarner Losh } FSE_decode_t;   /* size == U32 */
8800c16b537SWarner Losh 
8810c16b537SWarner Losh MEM_STATIC void FSE_initDState(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD, const FSE_DTable* dt)
8820c16b537SWarner Losh {
8830c16b537SWarner Losh     FSE_DTableHeader DTableH;
8840c16b537SWarner Losh     memcpy(&DTableH, dt, sizeof(DTableH));
8850c16b537SWarner Losh     DStatePtr->state = BIT_readBits(bitD, DTableH.tableLog);
8860c16b537SWarner Losh     BIT_reloadDStream(bitD);
8870c16b537SWarner Losh     DStatePtr->table = dt + 1;
8880c16b537SWarner Losh }
8890c16b537SWarner Losh 
8900c16b537SWarner Losh MEM_STATIC BYTE FSE_decodeSymbol(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD)
8910c16b537SWarner Losh {
8920c16b537SWarner Losh     const FSE_decode_t DInfo = ((const FSE_decode_t*)(DStatePtr->table))[DStatePtr->state];
8930c16b537SWarner Losh     const U32  nbBits = DInfo.nbBits;
8940c16b537SWarner Losh     BYTE symbol = DInfo.symbol;
8950c16b537SWarner Losh     size_t lowBits = BIT_readBits(bitD, nbBits);
8960c16b537SWarner Losh 
8970c16b537SWarner Losh     DStatePtr->state = DInfo.newState + lowBits;
8980c16b537SWarner Losh     return symbol;
8990c16b537SWarner Losh }
9000c16b537SWarner Losh 
9010c16b537SWarner Losh MEM_STATIC BYTE FSE_decodeSymbolFast(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD)
9020c16b537SWarner Losh {
9030c16b537SWarner Losh     const FSE_decode_t DInfo = ((const FSE_decode_t*)(DStatePtr->table))[DStatePtr->state];
9040c16b537SWarner Losh     const U32 nbBits = DInfo.nbBits;
9050c16b537SWarner Losh     BYTE symbol = DInfo.symbol;
9060c16b537SWarner Losh     size_t lowBits = BIT_readBitsFast(bitD, nbBits);
9070c16b537SWarner Losh 
9080c16b537SWarner Losh     DStatePtr->state = DInfo.newState + lowBits;
9090c16b537SWarner Losh     return symbol;
9100c16b537SWarner Losh }
9110c16b537SWarner Losh 
9120c16b537SWarner Losh MEM_STATIC unsigned FSE_endOfDState(const FSE_DState_t* DStatePtr)
9130c16b537SWarner Losh {
9140c16b537SWarner Losh     return DStatePtr->state == 0;
9150c16b537SWarner Losh }
9160c16b537SWarner Losh 
9170c16b537SWarner Losh 
9180c16b537SWarner Losh #if defined (__cplusplus)
9190c16b537SWarner Losh }
9200c16b537SWarner Losh #endif
9210c16b537SWarner Losh 
9220c16b537SWarner Losh #endif  /* FSE_STATIC_H */
9230c16b537SWarner Losh 
9240c16b537SWarner Losh /* ******************************************************************
9250c16b537SWarner Losh    FSE : Finite State Entropy coder
9260c16b537SWarner Losh    Copyright (C) 2013-2015, Yann Collet.
9270c16b537SWarner Losh 
9280c16b537SWarner Losh    BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
9290c16b537SWarner Losh 
9300c16b537SWarner Losh    Redistribution and use in source and binary forms, with or without
9310c16b537SWarner Losh    modification, are permitted provided that the following conditions are
9320c16b537SWarner Losh    met:
9330c16b537SWarner Losh 
9340c16b537SWarner Losh        * Redistributions of source code must retain the above copyright
9350c16b537SWarner Losh    notice, this list of conditions and the following disclaimer.
9360c16b537SWarner Losh        * Redistributions in binary form must reproduce the above
9370c16b537SWarner Losh    copyright notice, this list of conditions and the following disclaimer
9380c16b537SWarner Losh    in the documentation and/or other materials provided with the
9390c16b537SWarner Losh    distribution.
9400c16b537SWarner Losh 
9410c16b537SWarner Losh    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
9420c16b537SWarner Losh    "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
9430c16b537SWarner Losh    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
9440c16b537SWarner Losh    A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
9450c16b537SWarner Losh    OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
9460c16b537SWarner Losh    SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
9470c16b537SWarner Losh    LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
9480c16b537SWarner Losh    DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
9490c16b537SWarner Losh    THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
9500c16b537SWarner Losh    (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
9510c16b537SWarner Losh    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
9520c16b537SWarner Losh 
9530c16b537SWarner Losh     You can contact the author at :
9540c16b537SWarner Losh     - FSE source repository : https://github.com/Cyan4973/FiniteStateEntropy
9550c16b537SWarner Losh     - Public forum : https://groups.google.com/forum/#!forum/lz4c
9560c16b537SWarner Losh ****************************************************************** */
9570c16b537SWarner Losh 
9580c16b537SWarner Losh #ifndef FSE_COMMONDEFS_ONLY
9590c16b537SWarner Losh 
9600c16b537SWarner Losh /* **************************************************************
9610c16b537SWarner Losh *  Tuning parameters
9620c16b537SWarner Losh ****************************************************************/
9630c16b537SWarner Losh /*!MEMORY_USAGE :
9640c16b537SWarner Losh *  Memory usage formula : N->2^N Bytes (examples : 10 -> 1KB; 12 -> 4KB ; 16 -> 64KB; 20 -> 1MB; etc.)
9650c16b537SWarner Losh *  Increasing memory usage improves compression ratio
9660c16b537SWarner Losh *  Reduced memory usage can improve speed, due to cache effect
9670c16b537SWarner Losh *  Recommended max value is 14, for 16KB, which nicely fits into Intel x86 L1 cache */
9680c16b537SWarner Losh #define FSE_MAX_MEMORY_USAGE 14
9690c16b537SWarner Losh #define FSE_DEFAULT_MEMORY_USAGE 13
9700c16b537SWarner Losh 
9710c16b537SWarner Losh /*!FSE_MAX_SYMBOL_VALUE :
9720c16b537SWarner Losh *  Maximum symbol value authorized.
9730c16b537SWarner Losh *  Required for proper stack allocation */
9740c16b537SWarner Losh #define FSE_MAX_SYMBOL_VALUE 255
9750c16b537SWarner Losh 
9760c16b537SWarner Losh 
9770c16b537SWarner Losh /* **************************************************************
9780c16b537SWarner Losh *  template functions type & suffix
9790c16b537SWarner Losh ****************************************************************/
9800c16b537SWarner Losh #define FSE_FUNCTION_TYPE BYTE
9810c16b537SWarner Losh #define FSE_FUNCTION_EXTENSION
9820c16b537SWarner Losh #define FSE_DECODE_TYPE FSE_decode_t
9830c16b537SWarner Losh 
9840c16b537SWarner Losh 
9850c16b537SWarner Losh #endif   /* !FSE_COMMONDEFS_ONLY */
9860c16b537SWarner Losh 
9870c16b537SWarner Losh /* **************************************************************
9880c16b537SWarner Losh *  Compiler specifics
9890c16b537SWarner Losh ****************************************************************/
9900c16b537SWarner Losh #ifdef _MSC_VER    /* Visual Studio */
9910c16b537SWarner Losh #  define FORCE_INLINE static __forceinline
9920c16b537SWarner Losh #  include <intrin.h>                    /* For Visual 2005 */
9930c16b537SWarner Losh #  pragma warning(disable : 4127)        /* disable: C4127: conditional expression is constant */
9940c16b537SWarner Losh #  pragma warning(disable : 4214)        /* disable: C4214: non-int bitfields */
9950c16b537SWarner Losh #else
9960c16b537SWarner Losh #  if defined (__cplusplus) || defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L   /* C99 */
9970c16b537SWarner Losh #    ifdef __GNUC__
9980c16b537SWarner Losh #      define FORCE_INLINE static inline __attribute__((always_inline))
9990c16b537SWarner Losh #    else
10000c16b537SWarner Losh #      define FORCE_INLINE static inline
10010c16b537SWarner Losh #    endif
10020c16b537SWarner Losh #  else
10030c16b537SWarner Losh #    define FORCE_INLINE static
10040c16b537SWarner Losh #  endif /* __STDC_VERSION__ */
10050c16b537SWarner Losh #endif
10060c16b537SWarner Losh 
10070c16b537SWarner Losh 
10080c16b537SWarner Losh /* **************************************************************
10090c16b537SWarner Losh *  Dependencies
10100c16b537SWarner Losh ****************************************************************/
10110c16b537SWarner Losh #include <stdlib.h>     /* malloc, free, qsort */
10120c16b537SWarner Losh #include <string.h>     /* memcpy, memset */
10130c16b537SWarner Losh #include <stdio.h>      /* printf (debug) */
10140c16b537SWarner Losh 
10150c16b537SWarner Losh 
10160c16b537SWarner Losh /* ***************************************************************
10170c16b537SWarner Losh *  Constants
10180c16b537SWarner Losh *****************************************************************/
10190c16b537SWarner Losh #define FSE_MAX_TABLELOG  (FSE_MAX_MEMORY_USAGE-2)
10200c16b537SWarner Losh #define FSE_MAX_TABLESIZE (1U<<FSE_MAX_TABLELOG)
10210c16b537SWarner Losh #define FSE_MAXTABLESIZE_MASK (FSE_MAX_TABLESIZE-1)
10220c16b537SWarner Losh #define FSE_DEFAULT_TABLELOG (FSE_DEFAULT_MEMORY_USAGE-2)
10230c16b537SWarner Losh #define FSE_MIN_TABLELOG 5
10240c16b537SWarner Losh 
10250c16b537SWarner Losh #define FSE_TABLELOG_ABSOLUTE_MAX 15
10260c16b537SWarner Losh #if FSE_MAX_TABLELOG > FSE_TABLELOG_ABSOLUTE_MAX
10270c16b537SWarner Losh #error "FSE_MAX_TABLELOG > FSE_TABLELOG_ABSOLUTE_MAX is not supported"
10280c16b537SWarner Losh #endif
10290c16b537SWarner Losh 
10300c16b537SWarner Losh 
10310c16b537SWarner Losh /* **************************************************************
10320c16b537SWarner Losh *  Error Management
10330c16b537SWarner Losh ****************************************************************/
10340c16b537SWarner Losh #define FSE_STATIC_ASSERT(c) { enum { FSE_static_assert = 1/(int)(!!(c)) }; }   /* use only *after* variable declarations */
10350c16b537SWarner Losh 
10360c16b537SWarner Losh 
10370c16b537SWarner Losh /* **************************************************************
10380c16b537SWarner Losh *  Complex types
10390c16b537SWarner Losh ****************************************************************/
10400c16b537SWarner Losh typedef U32 DTable_max_t[FSE_DTABLE_SIZE_U32(FSE_MAX_TABLELOG)];
10410c16b537SWarner Losh 
10420c16b537SWarner Losh 
10430c16b537SWarner Losh /*-**************************************************************
10440c16b537SWarner Losh *  Templates
10450c16b537SWarner Losh ****************************************************************/
10460c16b537SWarner Losh /*
10470c16b537SWarner Losh   designed to be included
10480c16b537SWarner Losh   for type-specific functions (template emulation in C)
10490c16b537SWarner Losh   Objective is to write these functions only once, for improved maintenance
10500c16b537SWarner Losh */
10510c16b537SWarner Losh 
10520c16b537SWarner Losh /* safety checks */
10530c16b537SWarner Losh #ifndef FSE_FUNCTION_EXTENSION
10540c16b537SWarner Losh #  error "FSE_FUNCTION_EXTENSION must be defined"
10550c16b537SWarner Losh #endif
10560c16b537SWarner Losh #ifndef FSE_FUNCTION_TYPE
10570c16b537SWarner Losh #  error "FSE_FUNCTION_TYPE must be defined"
10580c16b537SWarner Losh #endif
10590c16b537SWarner Losh 
10600c16b537SWarner Losh /* Function names */
10610c16b537SWarner Losh #define FSE_CAT(X,Y) X##Y
10620c16b537SWarner Losh #define FSE_FUNCTION_NAME(X,Y) FSE_CAT(X,Y)
10630c16b537SWarner Losh #define FSE_TYPE_NAME(X,Y) FSE_CAT(X,Y)
10640c16b537SWarner Losh 
10650c16b537SWarner Losh static U32 FSE_tableStep(U32 tableSize) { return (tableSize>>1) + (tableSize>>3) + 3; }
10660c16b537SWarner Losh 
10670c16b537SWarner Losh 
10680c16b537SWarner Losh static size_t FSE_buildDTable(FSE_DTable* dt, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog)
10690c16b537SWarner Losh {
10700c16b537SWarner Losh     FSE_DTableHeader DTableH;
10710c16b537SWarner Losh     void* const tdPtr = dt+1;   /* because dt is unsigned, 32-bits aligned on 32-bits */
10720c16b537SWarner Losh     FSE_DECODE_TYPE* const tableDecode = (FSE_DECODE_TYPE*) (tdPtr);
10730c16b537SWarner Losh     const U32 tableSize = 1 << tableLog;
10740c16b537SWarner Losh     const U32 tableMask = tableSize-1;
10750c16b537SWarner Losh     const U32 step = FSE_tableStep(tableSize);
10760c16b537SWarner Losh     U16 symbolNext[FSE_MAX_SYMBOL_VALUE+1];
10770c16b537SWarner Losh     U32 position = 0;
10780c16b537SWarner Losh     U32 highThreshold = tableSize-1;
10790c16b537SWarner Losh     const S16 largeLimit= (S16)(1 << (tableLog-1));
10800c16b537SWarner Losh     U32 noLarge = 1;
10810c16b537SWarner Losh     U32 s;
10820c16b537SWarner Losh 
10830c16b537SWarner Losh     /* Sanity Checks */
10840c16b537SWarner Losh     if (maxSymbolValue > FSE_MAX_SYMBOL_VALUE) return ERROR(maxSymbolValue_tooLarge);
10850c16b537SWarner Losh     if (tableLog > FSE_MAX_TABLELOG) return ERROR(tableLog_tooLarge);
10860c16b537SWarner Losh 
10870c16b537SWarner Losh     /* Init, lay down lowprob symbols */
10880f743729SConrad Meyer     memset(tableDecode, 0, sizeof(FSE_DECODE_TYPE) * (maxSymbolValue+1) );   /* useless init, but keep static analyzer happy, and we don't need to performance optimize legacy decoders */
10890c16b537SWarner Losh     DTableH.tableLog = (U16)tableLog;
10900c16b537SWarner Losh     for (s=0; s<=maxSymbolValue; s++)
10910c16b537SWarner Losh     {
10920c16b537SWarner Losh         if (normalizedCounter[s]==-1)
10930c16b537SWarner Losh         {
10940c16b537SWarner Losh             tableDecode[highThreshold--].symbol = (FSE_FUNCTION_TYPE)s;
10950c16b537SWarner Losh             symbolNext[s] = 1;
10960c16b537SWarner Losh         }
10970c16b537SWarner Losh         else
10980c16b537SWarner Losh         {
10990c16b537SWarner Losh             if (normalizedCounter[s] >= largeLimit) noLarge=0;
11000c16b537SWarner Losh             symbolNext[s] = normalizedCounter[s];
11010c16b537SWarner Losh         }
11020c16b537SWarner Losh     }
11030c16b537SWarner Losh 
11040c16b537SWarner Losh     /* Spread symbols */
11050c16b537SWarner Losh     for (s=0; s<=maxSymbolValue; s++)
11060c16b537SWarner Losh     {
11070c16b537SWarner Losh         int i;
11080c16b537SWarner Losh         for (i=0; i<normalizedCounter[s]; i++)
11090c16b537SWarner Losh         {
11100c16b537SWarner Losh             tableDecode[position].symbol = (FSE_FUNCTION_TYPE)s;
11110c16b537SWarner Losh             position = (position + step) & tableMask;
11120c16b537SWarner Losh             while (position > highThreshold) position = (position + step) & tableMask;   /* lowprob area */
11130c16b537SWarner Losh         }
11140c16b537SWarner Losh     }
11150c16b537SWarner Losh 
11160c16b537SWarner Losh     if (position!=0) return ERROR(GENERIC);   /* position must reach all cells once, otherwise normalizedCounter is incorrect */
11170c16b537SWarner Losh 
11180c16b537SWarner Losh     /* Build Decoding table */
11190c16b537SWarner Losh     {
11200c16b537SWarner Losh         U32 i;
11210c16b537SWarner Losh         for (i=0; i<tableSize; i++)
11220c16b537SWarner Losh         {
11230c16b537SWarner Losh             FSE_FUNCTION_TYPE symbol = (FSE_FUNCTION_TYPE)(tableDecode[i].symbol);
11240c16b537SWarner Losh             U16 nextState = symbolNext[symbol]++;
11250c16b537SWarner Losh             tableDecode[i].nbBits = (BYTE) (tableLog - BIT_highbit32 ((U32)nextState) );
11260c16b537SWarner Losh             tableDecode[i].newState = (U16) ( (nextState << tableDecode[i].nbBits) - tableSize);
11270c16b537SWarner Losh         }
11280c16b537SWarner Losh     }
11290c16b537SWarner Losh 
11300c16b537SWarner Losh     DTableH.fastMode = (U16)noLarge;
11310c16b537SWarner Losh     memcpy(dt, &DTableH, sizeof(DTableH));
11320c16b537SWarner Losh     return 0;
11330c16b537SWarner Losh }
11340c16b537SWarner Losh 
11350c16b537SWarner Losh 
11360c16b537SWarner Losh #ifndef FSE_COMMONDEFS_ONLY
11370c16b537SWarner Losh /******************************************
11380c16b537SWarner Losh *  FSE helper functions
11390c16b537SWarner Losh ******************************************/
11400c16b537SWarner Losh static unsigned FSE_isError(size_t code) { return ERR_isError(code); }
11410c16b537SWarner Losh 
11420c16b537SWarner Losh 
11430c16b537SWarner Losh /****************************************************************
11440c16b537SWarner Losh *  FSE NCount encoding-decoding
11450c16b537SWarner Losh ****************************************************************/
11460c16b537SWarner Losh static short FSE_abs(short a)
11470c16b537SWarner Losh {
11480c16b537SWarner Losh     return a<0 ? -a : a;
11490c16b537SWarner Losh }
11500c16b537SWarner Losh 
11510c16b537SWarner Losh static size_t FSE_readNCount (short* normalizedCounter, unsigned* maxSVPtr, unsigned* tableLogPtr,
11520c16b537SWarner Losh                  const void* headerBuffer, size_t hbSize)
11530c16b537SWarner Losh {
11540c16b537SWarner Losh     const BYTE* const istart = (const BYTE*) headerBuffer;
11550c16b537SWarner Losh     const BYTE* const iend = istart + hbSize;
11560c16b537SWarner Losh     const BYTE* ip = istart;
11570c16b537SWarner Losh     int nbBits;
11580c16b537SWarner Losh     int remaining;
11590c16b537SWarner Losh     int threshold;
11600c16b537SWarner Losh     U32 bitStream;
11610c16b537SWarner Losh     int bitCount;
11620c16b537SWarner Losh     unsigned charnum = 0;
11630c16b537SWarner Losh     int previous0 = 0;
11640c16b537SWarner Losh 
11650c16b537SWarner Losh     if (hbSize < 4) return ERROR(srcSize_wrong);
11660c16b537SWarner Losh     bitStream = MEM_readLE32(ip);
11670c16b537SWarner Losh     nbBits = (bitStream & 0xF) + FSE_MIN_TABLELOG;   /* extract tableLog */
11680c16b537SWarner Losh     if (nbBits > FSE_TABLELOG_ABSOLUTE_MAX) return ERROR(tableLog_tooLarge);
11690c16b537SWarner Losh     bitStream >>= 4;
11700c16b537SWarner Losh     bitCount = 4;
11710c16b537SWarner Losh     *tableLogPtr = nbBits;
11720c16b537SWarner Losh     remaining = (1<<nbBits)+1;
11730c16b537SWarner Losh     threshold = 1<<nbBits;
11740c16b537SWarner Losh     nbBits++;
11750c16b537SWarner Losh 
11760c16b537SWarner Losh     while ((remaining>1) && (charnum<=*maxSVPtr))
11770c16b537SWarner Losh     {
11780c16b537SWarner Losh         if (previous0)
11790c16b537SWarner Losh         {
11800c16b537SWarner Losh             unsigned n0 = charnum;
11810c16b537SWarner Losh             while ((bitStream & 0xFFFF) == 0xFFFF)
11820c16b537SWarner Losh             {
11830c16b537SWarner Losh                 n0+=24;
11840c16b537SWarner Losh                 if (ip < iend-5)
11850c16b537SWarner Losh                 {
11860c16b537SWarner Losh                     ip+=2;
11870c16b537SWarner Losh                     bitStream = MEM_readLE32(ip) >> bitCount;
11880c16b537SWarner Losh                 }
11890c16b537SWarner Losh                 else
11900c16b537SWarner Losh                 {
11910c16b537SWarner Losh                     bitStream >>= 16;
11920c16b537SWarner Losh                     bitCount+=16;
11930c16b537SWarner Losh                 }
11940c16b537SWarner Losh             }
11950c16b537SWarner Losh             while ((bitStream & 3) == 3)
11960c16b537SWarner Losh             {
11970c16b537SWarner Losh                 n0+=3;
11980c16b537SWarner Losh                 bitStream>>=2;
11990c16b537SWarner Losh                 bitCount+=2;
12000c16b537SWarner Losh             }
12010c16b537SWarner Losh             n0 += bitStream & 3;
12020c16b537SWarner Losh             bitCount += 2;
12030c16b537SWarner Losh             if (n0 > *maxSVPtr) return ERROR(maxSymbolValue_tooSmall);
12040c16b537SWarner Losh             while (charnum < n0) normalizedCounter[charnum++] = 0;
12050c16b537SWarner Losh             if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4))
12060c16b537SWarner Losh             {
12070c16b537SWarner Losh                 ip += bitCount>>3;
12080c16b537SWarner Losh                 bitCount &= 7;
12090c16b537SWarner Losh                 bitStream = MEM_readLE32(ip) >> bitCount;
12100c16b537SWarner Losh             }
12110c16b537SWarner Losh             else
12120c16b537SWarner Losh                 bitStream >>= 2;
12130c16b537SWarner Losh         }
12140c16b537SWarner Losh         {
12150c16b537SWarner Losh             const short max = (short)((2*threshold-1)-remaining);
12160c16b537SWarner Losh             short count;
12170c16b537SWarner Losh 
12180c16b537SWarner Losh             if ((bitStream & (threshold-1)) < (U32)max)
12190c16b537SWarner Losh             {
12200c16b537SWarner Losh                 count = (short)(bitStream & (threshold-1));
12210c16b537SWarner Losh                 bitCount   += nbBits-1;
12220c16b537SWarner Losh             }
12230c16b537SWarner Losh             else
12240c16b537SWarner Losh             {
12250c16b537SWarner Losh                 count = (short)(bitStream & (2*threshold-1));
12260c16b537SWarner Losh                 if (count >= threshold) count -= max;
12270c16b537SWarner Losh                 bitCount   += nbBits;
12280c16b537SWarner Losh             }
12290c16b537SWarner Losh 
12300c16b537SWarner Losh             count--;   /* extra accuracy */
12310c16b537SWarner Losh             remaining -= FSE_abs(count);
12320c16b537SWarner Losh             normalizedCounter[charnum++] = count;
12330c16b537SWarner Losh             previous0 = !count;
12340c16b537SWarner Losh             while (remaining < threshold)
12350c16b537SWarner Losh             {
12360c16b537SWarner Losh                 nbBits--;
12370c16b537SWarner Losh                 threshold >>= 1;
12380c16b537SWarner Losh             }
12390c16b537SWarner Losh 
12400c16b537SWarner Losh             {
12410c16b537SWarner Losh                 if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4))
12420c16b537SWarner Losh                 {
12430c16b537SWarner Losh                     ip += bitCount>>3;
12440c16b537SWarner Losh                     bitCount &= 7;
12450c16b537SWarner Losh                 }
12460c16b537SWarner Losh                 else
12470c16b537SWarner Losh                 {
12480c16b537SWarner Losh                     bitCount -= (int)(8 * (iend - 4 - ip));
12490c16b537SWarner Losh                     ip = iend - 4;
12500c16b537SWarner Losh                 }
12510c16b537SWarner Losh                 bitStream = MEM_readLE32(ip) >> (bitCount & 31);
12520c16b537SWarner Losh             }
12530c16b537SWarner Losh         }
12540c16b537SWarner Losh     }
12550c16b537SWarner Losh     if (remaining != 1) return ERROR(GENERIC);
12560c16b537SWarner Losh     *maxSVPtr = charnum-1;
12570c16b537SWarner Losh 
12580c16b537SWarner Losh     ip += (bitCount+7)>>3;
12590c16b537SWarner Losh     if ((size_t)(ip-istart) > hbSize) return ERROR(srcSize_wrong);
12600c16b537SWarner Losh     return ip-istart;
12610c16b537SWarner Losh }
12620c16b537SWarner Losh 
12630c16b537SWarner Losh 
12640c16b537SWarner Losh /*********************************************************
12650c16b537SWarner Losh *  Decompression (Byte symbols)
12660c16b537SWarner Losh *********************************************************/
12670c16b537SWarner Losh static size_t FSE_buildDTable_rle (FSE_DTable* dt, BYTE symbolValue)
12680c16b537SWarner Losh {
12690c16b537SWarner Losh     void* ptr = dt;
12700c16b537SWarner Losh     FSE_DTableHeader* const DTableH = (FSE_DTableHeader*)ptr;
12710c16b537SWarner Losh     void* dPtr = dt + 1;
12720c16b537SWarner Losh     FSE_decode_t* const cell = (FSE_decode_t*)dPtr;
12730c16b537SWarner Losh 
12740c16b537SWarner Losh     DTableH->tableLog = 0;
12750c16b537SWarner Losh     DTableH->fastMode = 0;
12760c16b537SWarner Losh 
12770c16b537SWarner Losh     cell->newState = 0;
12780c16b537SWarner Losh     cell->symbol = symbolValue;
12790c16b537SWarner Losh     cell->nbBits = 0;
12800c16b537SWarner Losh 
12810c16b537SWarner Losh     return 0;
12820c16b537SWarner Losh }
12830c16b537SWarner Losh 
12840c16b537SWarner Losh 
12850c16b537SWarner Losh static size_t FSE_buildDTable_raw (FSE_DTable* dt, unsigned nbBits)
12860c16b537SWarner Losh {
12870c16b537SWarner Losh     void* ptr = dt;
12880c16b537SWarner Losh     FSE_DTableHeader* const DTableH = (FSE_DTableHeader*)ptr;
12890c16b537SWarner Losh     void* dPtr = dt + 1;
12900c16b537SWarner Losh     FSE_decode_t* const dinfo = (FSE_decode_t*)dPtr;
12910c16b537SWarner Losh     const unsigned tableSize = 1 << nbBits;
12920c16b537SWarner Losh     const unsigned tableMask = tableSize - 1;
12930c16b537SWarner Losh     const unsigned maxSymbolValue = tableMask;
12940c16b537SWarner Losh     unsigned s;
12950c16b537SWarner Losh 
12960c16b537SWarner Losh     /* Sanity checks */
12970c16b537SWarner Losh     if (nbBits < 1) return ERROR(GENERIC);         /* min size */
12980c16b537SWarner Losh 
12990c16b537SWarner Losh     /* Build Decoding Table */
13000c16b537SWarner Losh     DTableH->tableLog = (U16)nbBits;
13010c16b537SWarner Losh     DTableH->fastMode = 1;
13020c16b537SWarner Losh     for (s=0; s<=maxSymbolValue; s++)
13030c16b537SWarner Losh     {
13040c16b537SWarner Losh         dinfo[s].newState = 0;
13050c16b537SWarner Losh         dinfo[s].symbol = (BYTE)s;
13060c16b537SWarner Losh         dinfo[s].nbBits = (BYTE)nbBits;
13070c16b537SWarner Losh     }
13080c16b537SWarner Losh 
13090c16b537SWarner Losh     return 0;
13100c16b537SWarner Losh }
13110c16b537SWarner Losh 
13120c16b537SWarner Losh FORCE_INLINE size_t FSE_decompress_usingDTable_generic(
13130c16b537SWarner Losh           void* dst, size_t maxDstSize,
13140c16b537SWarner Losh     const void* cSrc, size_t cSrcSize,
13150c16b537SWarner Losh     const FSE_DTable* dt, const unsigned fast)
13160c16b537SWarner Losh {
13170c16b537SWarner Losh     BYTE* const ostart = (BYTE*) dst;
13180c16b537SWarner Losh     BYTE* op = ostart;
13190c16b537SWarner Losh     BYTE* const omax = op + maxDstSize;
13200c16b537SWarner Losh     BYTE* const olimit = omax-3;
13210c16b537SWarner Losh 
13220c16b537SWarner Losh     BIT_DStream_t bitD;
13230c16b537SWarner Losh     FSE_DState_t state1;
13240c16b537SWarner Losh     FSE_DState_t state2;
13250c16b537SWarner Losh     size_t errorCode;
13260c16b537SWarner Losh 
13270c16b537SWarner Losh     /* Init */
13280c16b537SWarner Losh     errorCode = BIT_initDStream(&bitD, cSrc, cSrcSize);   /* replaced last arg by maxCompressed Size */
13290c16b537SWarner Losh     if (FSE_isError(errorCode)) return errorCode;
13300c16b537SWarner Losh 
13310c16b537SWarner Losh     FSE_initDState(&state1, &bitD, dt);
13320c16b537SWarner Losh     FSE_initDState(&state2, &bitD, dt);
13330c16b537SWarner Losh 
13340c16b537SWarner Losh #define FSE_GETSYMBOL(statePtr) fast ? FSE_decodeSymbolFast(statePtr, &bitD) : FSE_decodeSymbol(statePtr, &bitD)
13350c16b537SWarner Losh 
13360c16b537SWarner Losh     /* 4 symbols per loop */
13370c16b537SWarner Losh     for ( ; (BIT_reloadDStream(&bitD)==BIT_DStream_unfinished) && (op<olimit) ; op+=4)
13380c16b537SWarner Losh     {
13390c16b537SWarner Losh         op[0] = FSE_GETSYMBOL(&state1);
13400c16b537SWarner Losh 
13410c16b537SWarner Losh         if (FSE_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8)    /* This test must be static */
13420c16b537SWarner Losh             BIT_reloadDStream(&bitD);
13430c16b537SWarner Losh 
13440c16b537SWarner Losh         op[1] = FSE_GETSYMBOL(&state2);
13450c16b537SWarner Losh 
13460c16b537SWarner Losh         if (FSE_MAX_TABLELOG*4+7 > sizeof(bitD.bitContainer)*8)    /* This test must be static */
13470c16b537SWarner Losh             { if (BIT_reloadDStream(&bitD) > BIT_DStream_unfinished) { op+=2; break; } }
13480c16b537SWarner Losh 
13490c16b537SWarner Losh         op[2] = FSE_GETSYMBOL(&state1);
13500c16b537SWarner Losh 
13510c16b537SWarner Losh         if (FSE_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8)    /* This test must be static */
13520c16b537SWarner Losh             BIT_reloadDStream(&bitD);
13530c16b537SWarner Losh 
13540c16b537SWarner Losh         op[3] = FSE_GETSYMBOL(&state2);
13550c16b537SWarner Losh     }
13560c16b537SWarner Losh 
13570c16b537SWarner Losh     /* tail */
13580c16b537SWarner Losh     /* note : BIT_reloadDStream(&bitD) >= FSE_DStream_partiallyFilled; Ends at exactly BIT_DStream_completed */
13590c16b537SWarner Losh     while (1)
13600c16b537SWarner Losh     {
13610c16b537SWarner Losh         if ( (BIT_reloadDStream(&bitD)>BIT_DStream_completed) || (op==omax) || (BIT_endOfDStream(&bitD) && (fast || FSE_endOfDState(&state1))) )
13620c16b537SWarner Losh             break;
13630c16b537SWarner Losh 
13640c16b537SWarner Losh         *op++ = FSE_GETSYMBOL(&state1);
13650c16b537SWarner Losh 
13660c16b537SWarner Losh         if ( (BIT_reloadDStream(&bitD)>BIT_DStream_completed) || (op==omax) || (BIT_endOfDStream(&bitD) && (fast || FSE_endOfDState(&state2))) )
13670c16b537SWarner Losh             break;
13680c16b537SWarner Losh 
13690c16b537SWarner Losh         *op++ = FSE_GETSYMBOL(&state2);
13700c16b537SWarner Losh     }
13710c16b537SWarner Losh 
13720c16b537SWarner Losh     /* end ? */
13730c16b537SWarner Losh     if (BIT_endOfDStream(&bitD) && FSE_endOfDState(&state1) && FSE_endOfDState(&state2))
13740c16b537SWarner Losh         return op-ostart;
13750c16b537SWarner Losh 
13760c16b537SWarner Losh     if (op==omax) return ERROR(dstSize_tooSmall);   /* dst buffer is full, but cSrc unfinished */
13770c16b537SWarner Losh 
13780c16b537SWarner Losh     return ERROR(corruption_detected);
13790c16b537SWarner Losh }
13800c16b537SWarner Losh 
13810c16b537SWarner Losh 
13820c16b537SWarner Losh static size_t FSE_decompress_usingDTable(void* dst, size_t originalSize,
13830c16b537SWarner Losh                             const void* cSrc, size_t cSrcSize,
13840c16b537SWarner Losh                             const FSE_DTable* dt)
13850c16b537SWarner Losh {
13860c16b537SWarner Losh     FSE_DTableHeader DTableH;
13870c16b537SWarner Losh     U32 fastMode;
13880c16b537SWarner Losh 
13890c16b537SWarner Losh     memcpy(&DTableH, dt, sizeof(DTableH));
13900c16b537SWarner Losh     fastMode = DTableH.fastMode;
13910c16b537SWarner Losh 
13920c16b537SWarner Losh     /* select fast mode (static) */
13930c16b537SWarner Losh     if (fastMode) return FSE_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 1);
13940c16b537SWarner Losh     return FSE_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 0);
13950c16b537SWarner Losh }
13960c16b537SWarner Losh 
13970c16b537SWarner Losh 
13980c16b537SWarner Losh static size_t FSE_decompress(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize)
13990c16b537SWarner Losh {
14000c16b537SWarner Losh     const BYTE* const istart = (const BYTE*)cSrc;
14010c16b537SWarner Losh     const BYTE* ip = istart;
14020c16b537SWarner Losh     short counting[FSE_MAX_SYMBOL_VALUE+1];
14030c16b537SWarner Losh     DTable_max_t dt;   /* Static analyzer seems unable to understand this table will be properly initialized later */
14040c16b537SWarner Losh     unsigned tableLog;
14050c16b537SWarner Losh     unsigned maxSymbolValue = FSE_MAX_SYMBOL_VALUE;
14060c16b537SWarner Losh     size_t errorCode;
14070c16b537SWarner Losh 
14080c16b537SWarner Losh     if (cSrcSize<2) return ERROR(srcSize_wrong);   /* too small input size */
14090c16b537SWarner Losh 
14100c16b537SWarner Losh     /* normal FSE decoding mode */
14110c16b537SWarner Losh     errorCode = FSE_readNCount (counting, &maxSymbolValue, &tableLog, istart, cSrcSize);
14120c16b537SWarner Losh     if (FSE_isError(errorCode)) return errorCode;
14130c16b537SWarner Losh     if (errorCode >= cSrcSize) return ERROR(srcSize_wrong);   /* too small input size */
14140c16b537SWarner Losh     ip += errorCode;
14150c16b537SWarner Losh     cSrcSize -= errorCode;
14160c16b537SWarner Losh 
14170c16b537SWarner Losh     errorCode = FSE_buildDTable (dt, counting, maxSymbolValue, tableLog);
14180c16b537SWarner Losh     if (FSE_isError(errorCode)) return errorCode;
14190c16b537SWarner Losh 
14200c16b537SWarner Losh     /* always return, even if it is an error code */
14210c16b537SWarner Losh     return FSE_decompress_usingDTable (dst, maxDstSize, ip, cSrcSize, dt);
14220c16b537SWarner Losh }
14230c16b537SWarner Losh 
14240c16b537SWarner Losh 
14250c16b537SWarner Losh 
14260c16b537SWarner Losh #endif   /* FSE_COMMONDEFS_ONLY */
14270c16b537SWarner Losh 
14280c16b537SWarner Losh 
14290c16b537SWarner Losh /* ******************************************************************
14300c16b537SWarner Losh    Huff0 : Huffman coder, part of New Generation Entropy library
14310c16b537SWarner Losh    header file
14320c16b537SWarner Losh    Copyright (C) 2013-2015, Yann Collet.
14330c16b537SWarner Losh 
14340c16b537SWarner Losh    BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
14350c16b537SWarner Losh 
14360c16b537SWarner Losh    Redistribution and use in source and binary forms, with or without
14370c16b537SWarner Losh    modification, are permitted provided that the following conditions are
14380c16b537SWarner Losh    met:
14390c16b537SWarner Losh 
14400c16b537SWarner Losh        * Redistributions of source code must retain the above copyright
14410c16b537SWarner Losh    notice, this list of conditions and the following disclaimer.
14420c16b537SWarner Losh        * Redistributions in binary form must reproduce the above
14430c16b537SWarner Losh    copyright notice, this list of conditions and the following disclaimer
14440c16b537SWarner Losh    in the documentation and/or other materials provided with the
14450c16b537SWarner Losh    distribution.
14460c16b537SWarner Losh 
14470c16b537SWarner Losh    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
14480c16b537SWarner Losh    "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
14490c16b537SWarner Losh    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
14500c16b537SWarner Losh    A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
14510c16b537SWarner Losh    OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
14520c16b537SWarner Losh    SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
14530c16b537SWarner Losh    LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
14540c16b537SWarner Losh    DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
14550c16b537SWarner Losh    THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
14560c16b537SWarner Losh    (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
14570c16b537SWarner Losh    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
14580c16b537SWarner Losh 
14590c16b537SWarner Losh    You can contact the author at :
14600c16b537SWarner Losh    - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
14610c16b537SWarner Losh    - Public forum : https://groups.google.com/forum/#!forum/lz4c
14620c16b537SWarner Losh ****************************************************************** */
14630c16b537SWarner Losh #ifndef HUFF0_H
14640c16b537SWarner Losh #define HUFF0_H
14650c16b537SWarner Losh 
14660c16b537SWarner Losh #if defined (__cplusplus)
14670c16b537SWarner Losh extern "C" {
14680c16b537SWarner Losh #endif
14690c16b537SWarner Losh 
14700c16b537SWarner Losh 
14710c16b537SWarner Losh /* ****************************************
14720c16b537SWarner Losh *  Dependency
14730c16b537SWarner Losh ******************************************/
14740c16b537SWarner Losh #include <stddef.h>    /* size_t */
14750c16b537SWarner Losh 
14760c16b537SWarner Losh 
14770c16b537SWarner Losh /* ****************************************
14780c16b537SWarner Losh *  Huff0 simple functions
14790c16b537SWarner Losh ******************************************/
14800c16b537SWarner Losh static size_t HUF_decompress(void* dst,  size_t dstSize,
14810c16b537SWarner Losh                 const void* cSrc, size_t cSrcSize);
14820c16b537SWarner Losh /*!
14830c16b537SWarner Losh HUF_decompress():
14840c16b537SWarner Losh     Decompress Huff0 data from buffer 'cSrc', of size 'cSrcSize',
14850c16b537SWarner Losh     into already allocated destination buffer 'dst', of size 'dstSize'.
14860c16b537SWarner Losh     'dstSize' must be the exact size of original (uncompressed) data.
14870c16b537SWarner Losh     Note : in contrast with FSE, HUF_decompress can regenerate RLE (cSrcSize==1) and uncompressed (cSrcSize==dstSize) data, because it knows size to regenerate.
14880c16b537SWarner Losh     @return : size of regenerated data (== dstSize)
14890c16b537SWarner Losh               or an error code, which can be tested using HUF_isError()
14900c16b537SWarner Losh */
14910c16b537SWarner Losh 
14920c16b537SWarner Losh 
14930c16b537SWarner Losh /* ****************************************
14940c16b537SWarner Losh *  Tool functions
14950c16b537SWarner Losh ******************************************/
14960c16b537SWarner Losh /* Error Management */
14970c16b537SWarner Losh static unsigned    HUF_isError(size_t code);        /* tells if a return value is an error code */
14980c16b537SWarner Losh 
14990c16b537SWarner Losh 
15000c16b537SWarner Losh #if defined (__cplusplus)
15010c16b537SWarner Losh }
15020c16b537SWarner Losh #endif
15030c16b537SWarner Losh 
15040c16b537SWarner Losh #endif   /* HUFF0_H */
15050c16b537SWarner Losh 
15060c16b537SWarner Losh 
15070c16b537SWarner Losh /* ******************************************************************
15080c16b537SWarner Losh    Huff0 : Huffman coder, part of New Generation Entropy library
15090c16b537SWarner Losh    header file for static linking (only)
15100c16b537SWarner Losh    Copyright (C) 2013-2015, Yann Collet
15110c16b537SWarner Losh 
15120c16b537SWarner Losh    BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
15130c16b537SWarner Losh 
15140c16b537SWarner Losh    Redistribution and use in source and binary forms, with or without
15150c16b537SWarner Losh    modification, are permitted provided that the following conditions are
15160c16b537SWarner Losh    met:
15170c16b537SWarner Losh 
15180c16b537SWarner Losh        * Redistributions of source code must retain the above copyright
15190c16b537SWarner Losh    notice, this list of conditions and the following disclaimer.
15200c16b537SWarner Losh        * Redistributions in binary form must reproduce the above
15210c16b537SWarner Losh    copyright notice, this list of conditions and the following disclaimer
15220c16b537SWarner Losh    in the documentation and/or other materials provided with the
15230c16b537SWarner Losh    distribution.
15240c16b537SWarner Losh 
15250c16b537SWarner Losh    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
15260c16b537SWarner Losh    "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
15270c16b537SWarner Losh    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
15280c16b537SWarner Losh    A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
15290c16b537SWarner Losh    OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
15300c16b537SWarner Losh    SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
15310c16b537SWarner Losh    LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
15320c16b537SWarner Losh    DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
15330c16b537SWarner Losh    THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
15340c16b537SWarner Losh    (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
15350c16b537SWarner Losh    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
15360c16b537SWarner Losh 
15370c16b537SWarner Losh    You can contact the author at :
15380c16b537SWarner Losh    - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
15390c16b537SWarner Losh    - Public forum : https://groups.google.com/forum/#!forum/lz4c
15400c16b537SWarner Losh ****************************************************************** */
15410c16b537SWarner Losh #ifndef HUFF0_STATIC_H
15420c16b537SWarner Losh #define HUFF0_STATIC_H
15430c16b537SWarner Losh 
15440c16b537SWarner Losh #if defined (__cplusplus)
15450c16b537SWarner Losh extern "C" {
15460c16b537SWarner Losh #endif
15470c16b537SWarner Losh 
15480c16b537SWarner Losh 
15490c16b537SWarner Losh 
15500c16b537SWarner Losh /* ****************************************
15510c16b537SWarner Losh *  Static allocation macros
15520c16b537SWarner Losh ******************************************/
15530c16b537SWarner Losh /* static allocation of Huff0's DTable */
15540c16b537SWarner Losh #define HUF_DTABLE_SIZE(maxTableLog)   (1 + (1<<maxTableLog))  /* nb Cells; use unsigned short for X2, unsigned int for X4 */
15550c16b537SWarner Losh #define HUF_CREATE_STATIC_DTABLEX2(DTable, maxTableLog) \
15560c16b537SWarner Losh         unsigned short DTable[HUF_DTABLE_SIZE(maxTableLog)] = { maxTableLog }
15570c16b537SWarner Losh #define HUF_CREATE_STATIC_DTABLEX4(DTable, maxTableLog) \
15580c16b537SWarner Losh         unsigned int DTable[HUF_DTABLE_SIZE(maxTableLog)] = { maxTableLog }
15590c16b537SWarner Losh #define HUF_CREATE_STATIC_DTABLEX6(DTable, maxTableLog) \
15600c16b537SWarner Losh         unsigned int DTable[HUF_DTABLE_SIZE(maxTableLog) * 3 / 2] = { maxTableLog }
15610c16b537SWarner Losh 
15620c16b537SWarner Losh 
15630c16b537SWarner Losh /* ****************************************
15640c16b537SWarner Losh *  Advanced decompression functions
15650c16b537SWarner Losh ******************************************/
15660c16b537SWarner Losh static size_t HUF_decompress4X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize);   /* single-symbol decoder */
15670c16b537SWarner Losh static size_t HUF_decompress4X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize);   /* double-symbols decoder */
15680c16b537SWarner Losh 
15690c16b537SWarner Losh 
15700c16b537SWarner Losh /* ****************************************
15710c16b537SWarner Losh *  Huff0 detailed API
15720c16b537SWarner Losh ******************************************/
15730c16b537SWarner Losh /*!
15740c16b537SWarner Losh HUF_decompress() does the following:
15750c16b537SWarner Losh 1. select the decompression algorithm (X2, X4, X6) based on pre-computed heuristics
15760c16b537SWarner Losh 2. build Huffman table from save, using HUF_readDTableXn()
15770c16b537SWarner Losh 3. decode 1 or 4 segments in parallel using HUF_decompressSXn_usingDTable
15780c16b537SWarner Losh 
15790c16b537SWarner Losh */
15800c16b537SWarner Losh static size_t HUF_readDTableX2 (unsigned short* DTable, const void* src, size_t srcSize);
15810c16b537SWarner Losh static size_t HUF_readDTableX4 (unsigned* DTable, const void* src, size_t srcSize);
15820c16b537SWarner Losh 
15830c16b537SWarner Losh static size_t HUF_decompress4X2_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const unsigned short* DTable);
15840c16b537SWarner Losh static size_t HUF_decompress4X4_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const unsigned* DTable);
15850c16b537SWarner Losh 
15860c16b537SWarner Losh 
15870c16b537SWarner Losh #if defined (__cplusplus)
15880c16b537SWarner Losh }
15890c16b537SWarner Losh #endif
15900c16b537SWarner Losh 
15910c16b537SWarner Losh #endif /* HUFF0_STATIC_H */
15920c16b537SWarner Losh 
15930c16b537SWarner Losh 
15940c16b537SWarner Losh 
15950c16b537SWarner Losh /* ******************************************************************
15960c16b537SWarner Losh    Huff0 : Huffman coder, part of New Generation Entropy library
15970c16b537SWarner Losh    Copyright (C) 2013-2015, Yann Collet.
15980c16b537SWarner Losh 
15990c16b537SWarner Losh    BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
16000c16b537SWarner Losh 
16010c16b537SWarner Losh    Redistribution and use in source and binary forms, with or without
16020c16b537SWarner Losh    modification, are permitted provided that the following conditions are
16030c16b537SWarner Losh    met:
16040c16b537SWarner Losh 
16050c16b537SWarner Losh        * Redistributions of source code must retain the above copyright
16060c16b537SWarner Losh    notice, this list of conditions and the following disclaimer.
16070c16b537SWarner Losh        * Redistributions in binary form must reproduce the above
16080c16b537SWarner Losh    copyright notice, this list of conditions and the following disclaimer
16090c16b537SWarner Losh    in the documentation and/or other materials provided with the
16100c16b537SWarner Losh    distribution.
16110c16b537SWarner Losh 
16120c16b537SWarner Losh    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
16130c16b537SWarner Losh    "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
16140c16b537SWarner Losh    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
16150c16b537SWarner Losh    A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
16160c16b537SWarner Losh    OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
16170c16b537SWarner Losh    SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
16180c16b537SWarner Losh    LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
16190c16b537SWarner Losh    DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
16200c16b537SWarner Losh    THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
16210c16b537SWarner Losh    (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
16220c16b537SWarner Losh    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
16230c16b537SWarner Losh 
16240c16b537SWarner Losh     You can contact the author at :
16250c16b537SWarner Losh     - FSE+Huff0 source repository : https://github.com/Cyan4973/FiniteStateEntropy
16260c16b537SWarner Losh ****************************************************************** */
16270c16b537SWarner Losh 
16280c16b537SWarner Losh /* **************************************************************
16290c16b537SWarner Losh *  Compiler specifics
16300c16b537SWarner Losh ****************************************************************/
16310c16b537SWarner Losh #if defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */)
16320c16b537SWarner Losh /* inline is defined */
16330c16b537SWarner Losh #elif defined(_MSC_VER)
16340c16b537SWarner Losh #  define inline __inline
16350c16b537SWarner Losh #else
16360c16b537SWarner Losh #  define inline /* disable inline */
16370c16b537SWarner Losh #endif
16380c16b537SWarner Losh 
16390c16b537SWarner Losh 
16400c16b537SWarner Losh #ifdef _MSC_VER    /* Visual Studio */
16410c16b537SWarner Losh #  pragma warning(disable : 4127)        /* disable: C4127: conditional expression is constant */
16420c16b537SWarner Losh #endif
16430c16b537SWarner Losh 
16440c16b537SWarner Losh 
16450c16b537SWarner Losh /* **************************************************************
16460c16b537SWarner Losh *  Includes
16470c16b537SWarner Losh ****************************************************************/
16480c16b537SWarner Losh #include <stdlib.h>     /* malloc, free, qsort */
16490c16b537SWarner Losh #include <string.h>     /* memcpy, memset */
16500c16b537SWarner Losh #include <stdio.h>      /* printf (debug) */
16510c16b537SWarner Losh 
16520c16b537SWarner Losh 
16530c16b537SWarner Losh /* **************************************************************
16540c16b537SWarner Losh *  Constants
16550c16b537SWarner Losh ****************************************************************/
16560c16b537SWarner Losh #define HUF_ABSOLUTEMAX_TABLELOG  16   /* absolute limit of HUF_MAX_TABLELOG. Beyond that value, code does not work */
16570c16b537SWarner Losh #define HUF_MAX_TABLELOG  12           /* max configured tableLog (for static allocation); can be modified up to HUF_ABSOLUTEMAX_TABLELOG */
16580c16b537SWarner Losh #define HUF_DEFAULT_TABLELOG  HUF_MAX_TABLELOG   /* tableLog by default, when not specified */
16590c16b537SWarner Losh #define HUF_MAX_SYMBOL_VALUE 255
16600c16b537SWarner Losh #if (HUF_MAX_TABLELOG > HUF_ABSOLUTEMAX_TABLELOG)
16610c16b537SWarner Losh #  error "HUF_MAX_TABLELOG is too large !"
16620c16b537SWarner Losh #endif
16630c16b537SWarner Losh 
16640c16b537SWarner Losh 
16650c16b537SWarner Losh /* **************************************************************
16660c16b537SWarner Losh *  Error Management
16670c16b537SWarner Losh ****************************************************************/
16680c16b537SWarner Losh static unsigned HUF_isError(size_t code) { return ERR_isError(code); }
16690c16b537SWarner Losh #define HUF_STATIC_ASSERT(c) { enum { HUF_static_assert = 1/(int)(!!(c)) }; }   /* use only *after* variable declarations */
16700c16b537SWarner Losh 
16710c16b537SWarner Losh 
16720c16b537SWarner Losh 
16730c16b537SWarner Losh /*-*******************************************************
16740c16b537SWarner Losh *  Huff0 : Huffman block decompression
16750c16b537SWarner Losh *********************************************************/
16760c16b537SWarner Losh typedef struct { BYTE byte; BYTE nbBits; } HUF_DEltX2;   /* single-symbol decoding */
16770c16b537SWarner Losh 
16780c16b537SWarner Losh typedef struct { U16 sequence; BYTE nbBits; BYTE length; } HUF_DEltX4;  /* double-symbols decoding */
16790c16b537SWarner Losh 
16800c16b537SWarner Losh typedef struct { BYTE symbol; BYTE weight; } sortedSymbol_t;
16810c16b537SWarner Losh 
16820c16b537SWarner Losh /*! HUF_readStats
16830c16b537SWarner Losh     Read compact Huffman tree, saved by HUF_writeCTable
16840c16b537SWarner Losh     @huffWeight : destination buffer
16850c16b537SWarner Losh     @return : size read from `src`
16860c16b537SWarner Losh */
16870c16b537SWarner Losh static size_t HUF_readStats(BYTE* huffWeight, size_t hwSize, U32* rankStats,
16880c16b537SWarner Losh                             U32* nbSymbolsPtr, U32* tableLogPtr,
16890c16b537SWarner Losh                             const void* src, size_t srcSize)
16900c16b537SWarner Losh {
16910c16b537SWarner Losh     U32 weightTotal;
16920c16b537SWarner Losh     U32 tableLog;
16930c16b537SWarner Losh     const BYTE* ip = (const BYTE*) src;
16940c16b537SWarner Losh     size_t iSize;
16950c16b537SWarner Losh     size_t oSize;
16960c16b537SWarner Losh     U32 n;
16970c16b537SWarner Losh 
16980c16b537SWarner Losh     if (!srcSize) return ERROR(srcSize_wrong);
16990c16b537SWarner Losh     iSize = ip[0];
17000c16b537SWarner Losh     //memset(huffWeight, 0, hwSize);   /* is not necessary, even though some analyzer complain ... */
17010c16b537SWarner Losh 
17020c16b537SWarner Losh     if (iSize >= 128)  /* special header */
17030c16b537SWarner Losh     {
17040c16b537SWarner Losh         if (iSize >= (242))   /* RLE */
17050c16b537SWarner Losh         {
17060c16b537SWarner Losh             static int l[14] = { 1, 2, 3, 4, 7, 8, 15, 16, 31, 32, 63, 64, 127, 128 };
17070c16b537SWarner Losh             oSize = l[iSize-242];
17080c16b537SWarner Losh             memset(huffWeight, 1, hwSize);
17090c16b537SWarner Losh             iSize = 0;
17100c16b537SWarner Losh         }
17110c16b537SWarner Losh         else   /* Incompressible */
17120c16b537SWarner Losh         {
17130c16b537SWarner Losh             oSize = iSize - 127;
17140c16b537SWarner Losh             iSize = ((oSize+1)/2);
17150c16b537SWarner Losh             if (iSize+1 > srcSize) return ERROR(srcSize_wrong);
17160c16b537SWarner Losh             if (oSize >= hwSize) return ERROR(corruption_detected);
17170c16b537SWarner Losh             ip += 1;
17180c16b537SWarner Losh             for (n=0; n<oSize; n+=2)
17190c16b537SWarner Losh             {
17200c16b537SWarner Losh                 huffWeight[n]   = ip[n/2] >> 4;
17210c16b537SWarner Losh                 huffWeight[n+1] = ip[n/2] & 15;
17220c16b537SWarner Losh             }
17230c16b537SWarner Losh         }
17240c16b537SWarner Losh     }
17250c16b537SWarner Losh     else  /* header compressed with FSE (normal case) */
17260c16b537SWarner Losh     {
17270c16b537SWarner Losh         if (iSize+1 > srcSize) return ERROR(srcSize_wrong);
17280c16b537SWarner Losh         oSize = FSE_decompress(huffWeight, hwSize-1, ip+1, iSize);   /* max (hwSize-1) values decoded, as last one is implied */
17290c16b537SWarner Losh         if (FSE_isError(oSize)) return oSize;
17300c16b537SWarner Losh     }
17310c16b537SWarner Losh 
17320c16b537SWarner Losh     /* collect weight stats */
17330c16b537SWarner Losh     memset(rankStats, 0, (HUF_ABSOLUTEMAX_TABLELOG + 1) * sizeof(U32));
17340c16b537SWarner Losh     weightTotal = 0;
17350c16b537SWarner Losh     for (n=0; n<oSize; n++)
17360c16b537SWarner Losh     {
17370c16b537SWarner Losh         if (huffWeight[n] >= HUF_ABSOLUTEMAX_TABLELOG) return ERROR(corruption_detected);
17380c16b537SWarner Losh         rankStats[huffWeight[n]]++;
17390c16b537SWarner Losh         weightTotal += (1 << huffWeight[n]) >> 1;
17400c16b537SWarner Losh     }
17410c16b537SWarner Losh     if (weightTotal == 0) return ERROR(corruption_detected);
17420c16b537SWarner Losh 
17430c16b537SWarner Losh     /* get last non-null symbol weight (implied, total must be 2^n) */
17440c16b537SWarner Losh     tableLog = BIT_highbit32(weightTotal) + 1;
17450c16b537SWarner Losh     if (tableLog > HUF_ABSOLUTEMAX_TABLELOG) return ERROR(corruption_detected);
17460c16b537SWarner Losh     {
17470c16b537SWarner Losh         U32 total = 1 << tableLog;
17480c16b537SWarner Losh         U32 rest = total - weightTotal;
17490c16b537SWarner Losh         U32 verif = 1 << BIT_highbit32(rest);
17500c16b537SWarner Losh         U32 lastWeight = BIT_highbit32(rest) + 1;
17510c16b537SWarner Losh         if (verif != rest) return ERROR(corruption_detected);    /* last value must be a clean power of 2 */
17520c16b537SWarner Losh         huffWeight[oSize] = (BYTE)lastWeight;
17530c16b537SWarner Losh         rankStats[lastWeight]++;
17540c16b537SWarner Losh     }
17550c16b537SWarner Losh 
17560c16b537SWarner Losh     /* check tree construction validity */
17570c16b537SWarner Losh     if ((rankStats[1] < 2) || (rankStats[1] & 1)) return ERROR(corruption_detected);   /* by construction : at least 2 elts of rank 1, must be even */
17580c16b537SWarner Losh 
17590c16b537SWarner Losh     /* results */
17600c16b537SWarner Losh     *nbSymbolsPtr = (U32)(oSize+1);
17610c16b537SWarner Losh     *tableLogPtr = tableLog;
17620c16b537SWarner Losh     return iSize+1;
17630c16b537SWarner Losh }
17640c16b537SWarner Losh 
17650c16b537SWarner Losh 
17660c16b537SWarner Losh /**************************/
17670c16b537SWarner Losh /* single-symbol decoding */
17680c16b537SWarner Losh /**************************/
17690c16b537SWarner Losh 
17700c16b537SWarner Losh static size_t HUF_readDTableX2 (U16* DTable, const void* src, size_t srcSize)
17710c16b537SWarner Losh {
17720c16b537SWarner Losh     BYTE huffWeight[HUF_MAX_SYMBOL_VALUE + 1];
17730c16b537SWarner Losh     U32 rankVal[HUF_ABSOLUTEMAX_TABLELOG + 1];   /* large enough for values from 0 to 16 */
17740c16b537SWarner Losh     U32 tableLog = 0;
17750c16b537SWarner Losh     size_t iSize;
17760c16b537SWarner Losh     U32 nbSymbols = 0;
17770c16b537SWarner Losh     U32 n;
17780c16b537SWarner Losh     U32 nextRankStart;
17790c16b537SWarner Losh     void* const dtPtr = DTable + 1;
17800c16b537SWarner Losh     HUF_DEltX2* const dt = (HUF_DEltX2*)dtPtr;
17810c16b537SWarner Losh 
17820c16b537SWarner Losh     HUF_STATIC_ASSERT(sizeof(HUF_DEltX2) == sizeof(U16));   /* if compilation fails here, assertion is false */
17830c16b537SWarner Losh     //memset(huffWeight, 0, sizeof(huffWeight));   /* is not necessary, even though some analyzer complain ... */
17840c16b537SWarner Losh 
17850c16b537SWarner Losh     iSize = HUF_readStats(huffWeight, HUF_MAX_SYMBOL_VALUE + 1, rankVal, &nbSymbols, &tableLog, src, srcSize);
17860c16b537SWarner Losh     if (HUF_isError(iSize)) return iSize;
17870c16b537SWarner Losh 
17880c16b537SWarner Losh     /* check result */
17890c16b537SWarner Losh     if (tableLog > DTable[0]) return ERROR(tableLog_tooLarge);   /* DTable is too small */
17900c16b537SWarner Losh     DTable[0] = (U16)tableLog;   /* maybe should separate sizeof DTable, as allocated, from used size of DTable, in case of DTable re-use */
17910c16b537SWarner Losh 
17920c16b537SWarner Losh     /* Prepare ranks */
17930c16b537SWarner Losh     nextRankStart = 0;
17940c16b537SWarner Losh     for (n=1; n<=tableLog; n++)
17950c16b537SWarner Losh     {
17960c16b537SWarner Losh         U32 current = nextRankStart;
17970c16b537SWarner Losh         nextRankStart += (rankVal[n] << (n-1));
17980c16b537SWarner Losh         rankVal[n] = current;
17990c16b537SWarner Losh     }
18000c16b537SWarner Losh 
18010c16b537SWarner Losh     /* fill DTable */
18020c16b537SWarner Losh     for (n=0; n<nbSymbols; n++)
18030c16b537SWarner Losh     {
18040c16b537SWarner Losh         const U32 w = huffWeight[n];
18050c16b537SWarner Losh         const U32 length = (1 << w) >> 1;
18060c16b537SWarner Losh         U32 i;
18070c16b537SWarner Losh         HUF_DEltX2 D;
18080c16b537SWarner Losh         D.byte = (BYTE)n; D.nbBits = (BYTE)(tableLog + 1 - w);
18090c16b537SWarner Losh         for (i = rankVal[w]; i < rankVal[w] + length; i++)
18100c16b537SWarner Losh             dt[i] = D;
18110c16b537SWarner Losh         rankVal[w] += length;
18120c16b537SWarner Losh     }
18130c16b537SWarner Losh 
18140c16b537SWarner Losh     return iSize;
18150c16b537SWarner Losh }
18160c16b537SWarner Losh 
18170c16b537SWarner Losh static BYTE HUF_decodeSymbolX2(BIT_DStream_t* Dstream, const HUF_DEltX2* dt, const U32 dtLog)
18180c16b537SWarner Losh {
18190c16b537SWarner Losh         const size_t val = BIT_lookBitsFast(Dstream, dtLog); /* note : dtLog >= 1 */
18200c16b537SWarner Losh         const BYTE c = dt[val].byte;
18210c16b537SWarner Losh         BIT_skipBits(Dstream, dt[val].nbBits);
18220c16b537SWarner Losh         return c;
18230c16b537SWarner Losh }
18240c16b537SWarner Losh 
18250c16b537SWarner Losh #define HUF_DECODE_SYMBOLX2_0(ptr, DStreamPtr) \
18260c16b537SWarner Losh     *ptr++ = HUF_decodeSymbolX2(DStreamPtr, dt, dtLog)
18270c16b537SWarner Losh 
18280c16b537SWarner Losh #define HUF_DECODE_SYMBOLX2_1(ptr, DStreamPtr) \
18290c16b537SWarner Losh     if (MEM_64bits() || (HUF_MAX_TABLELOG<=12)) \
18300c16b537SWarner Losh         HUF_DECODE_SYMBOLX2_0(ptr, DStreamPtr)
18310c16b537SWarner Losh 
18320c16b537SWarner Losh #define HUF_DECODE_SYMBOLX2_2(ptr, DStreamPtr) \
18330c16b537SWarner Losh     if (MEM_64bits()) \
18340c16b537SWarner Losh         HUF_DECODE_SYMBOLX2_0(ptr, DStreamPtr)
18350c16b537SWarner Losh 
18360c16b537SWarner Losh static inline size_t HUF_decodeStreamX2(BYTE* p, BIT_DStream_t* const bitDPtr, BYTE* const pEnd, const HUF_DEltX2* const dt, const U32 dtLog)
18370c16b537SWarner Losh {
18380c16b537SWarner Losh     BYTE* const pStart = p;
18390c16b537SWarner Losh 
18400c16b537SWarner Losh     /* up to 4 symbols at a time */
18410c16b537SWarner Losh     while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p <= pEnd-4))
18420c16b537SWarner Losh     {
18430c16b537SWarner Losh         HUF_DECODE_SYMBOLX2_2(p, bitDPtr);
18440c16b537SWarner Losh         HUF_DECODE_SYMBOLX2_1(p, bitDPtr);
18450c16b537SWarner Losh         HUF_DECODE_SYMBOLX2_2(p, bitDPtr);
18460c16b537SWarner Losh         HUF_DECODE_SYMBOLX2_0(p, bitDPtr);
18470c16b537SWarner Losh     }
18480c16b537SWarner Losh 
18490c16b537SWarner Losh     /* closer to the end */
18500c16b537SWarner Losh     while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p < pEnd))
18510c16b537SWarner Losh         HUF_DECODE_SYMBOLX2_0(p, bitDPtr);
18520c16b537SWarner Losh 
18530c16b537SWarner Losh     /* no more data to retrieve from bitstream, hence no need to reload */
18540c16b537SWarner Losh     while (p < pEnd)
18550c16b537SWarner Losh         HUF_DECODE_SYMBOLX2_0(p, bitDPtr);
18560c16b537SWarner Losh 
18570c16b537SWarner Losh     return pEnd-pStart;
18580c16b537SWarner Losh }
18590c16b537SWarner Losh 
18600c16b537SWarner Losh 
18610c16b537SWarner Losh static size_t HUF_decompress4X2_usingDTable(
18620c16b537SWarner Losh           void* dst,  size_t dstSize,
18630c16b537SWarner Losh     const void* cSrc, size_t cSrcSize,
18640c16b537SWarner Losh     const U16* DTable)
18650c16b537SWarner Losh {
18660c16b537SWarner Losh     if (cSrcSize < 10) return ERROR(corruption_detected);   /* strict minimum : jump table + 1 byte per stream */
18670c16b537SWarner Losh 
18680c16b537SWarner Losh     {
18690c16b537SWarner Losh         const BYTE* const istart = (const BYTE*) cSrc;
18700c16b537SWarner Losh         BYTE* const ostart = (BYTE*) dst;
18710c16b537SWarner Losh         BYTE* const oend = ostart + dstSize;
18720c16b537SWarner Losh         const void* const dtPtr = DTable;
18730c16b537SWarner Losh         const HUF_DEltX2* const dt = ((const HUF_DEltX2*)dtPtr) +1;
18740c16b537SWarner Losh         const U32 dtLog = DTable[0];
18750c16b537SWarner Losh         size_t errorCode;
18760c16b537SWarner Losh 
18770c16b537SWarner Losh         /* Init */
18780c16b537SWarner Losh         BIT_DStream_t bitD1;
18790c16b537SWarner Losh         BIT_DStream_t bitD2;
18800c16b537SWarner Losh         BIT_DStream_t bitD3;
18810c16b537SWarner Losh         BIT_DStream_t bitD4;
18820c16b537SWarner Losh         const size_t length1 = MEM_readLE16(istart);
18830c16b537SWarner Losh         const size_t length2 = MEM_readLE16(istart+2);
18840c16b537SWarner Losh         const size_t length3 = MEM_readLE16(istart+4);
18850c16b537SWarner Losh         size_t length4;
18860c16b537SWarner Losh         const BYTE* const istart1 = istart + 6;  /* jumpTable */
18870c16b537SWarner Losh         const BYTE* const istart2 = istart1 + length1;
18880c16b537SWarner Losh         const BYTE* const istart3 = istart2 + length2;
18890c16b537SWarner Losh         const BYTE* const istart4 = istart3 + length3;
18900c16b537SWarner Losh         const size_t segmentSize = (dstSize+3) / 4;
18910c16b537SWarner Losh         BYTE* const opStart2 = ostart + segmentSize;
18920c16b537SWarner Losh         BYTE* const opStart3 = opStart2 + segmentSize;
18930c16b537SWarner Losh         BYTE* const opStart4 = opStart3 + segmentSize;
18940c16b537SWarner Losh         BYTE* op1 = ostart;
18950c16b537SWarner Losh         BYTE* op2 = opStart2;
18960c16b537SWarner Losh         BYTE* op3 = opStart3;
18970c16b537SWarner Losh         BYTE* op4 = opStart4;
18980c16b537SWarner Losh         U32 endSignal;
18990c16b537SWarner Losh 
19000c16b537SWarner Losh         length4 = cSrcSize - (length1 + length2 + length3 + 6);
19010c16b537SWarner Losh         if (length4 > cSrcSize) return ERROR(corruption_detected);   /* overflow */
19020c16b537SWarner Losh         errorCode = BIT_initDStream(&bitD1, istart1, length1);
19030c16b537SWarner Losh         if (HUF_isError(errorCode)) return errorCode;
19040c16b537SWarner Losh         errorCode = BIT_initDStream(&bitD2, istart2, length2);
19050c16b537SWarner Losh         if (HUF_isError(errorCode)) return errorCode;
19060c16b537SWarner Losh         errorCode = BIT_initDStream(&bitD3, istart3, length3);
19070c16b537SWarner Losh         if (HUF_isError(errorCode)) return errorCode;
19080c16b537SWarner Losh         errorCode = BIT_initDStream(&bitD4, istart4, length4);
19090c16b537SWarner Losh         if (HUF_isError(errorCode)) return errorCode;
19100c16b537SWarner Losh 
19110c16b537SWarner Losh         /* 16-32 symbols per loop (4-8 symbols per stream) */
19120c16b537SWarner Losh         endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4);
19130c16b537SWarner Losh         for ( ; (endSignal==BIT_DStream_unfinished) && (op4<(oend-7)) ; )
19140c16b537SWarner Losh         {
19150c16b537SWarner Losh             HUF_DECODE_SYMBOLX2_2(op1, &bitD1);
19160c16b537SWarner Losh             HUF_DECODE_SYMBOLX2_2(op2, &bitD2);
19170c16b537SWarner Losh             HUF_DECODE_SYMBOLX2_2(op3, &bitD3);
19180c16b537SWarner Losh             HUF_DECODE_SYMBOLX2_2(op4, &bitD4);
19190c16b537SWarner Losh             HUF_DECODE_SYMBOLX2_1(op1, &bitD1);
19200c16b537SWarner Losh             HUF_DECODE_SYMBOLX2_1(op2, &bitD2);
19210c16b537SWarner Losh             HUF_DECODE_SYMBOLX2_1(op3, &bitD3);
19220c16b537SWarner Losh             HUF_DECODE_SYMBOLX2_1(op4, &bitD4);
19230c16b537SWarner Losh             HUF_DECODE_SYMBOLX2_2(op1, &bitD1);
19240c16b537SWarner Losh             HUF_DECODE_SYMBOLX2_2(op2, &bitD2);
19250c16b537SWarner Losh             HUF_DECODE_SYMBOLX2_2(op3, &bitD3);
19260c16b537SWarner Losh             HUF_DECODE_SYMBOLX2_2(op4, &bitD4);
19270c16b537SWarner Losh             HUF_DECODE_SYMBOLX2_0(op1, &bitD1);
19280c16b537SWarner Losh             HUF_DECODE_SYMBOLX2_0(op2, &bitD2);
19290c16b537SWarner Losh             HUF_DECODE_SYMBOLX2_0(op3, &bitD3);
19300c16b537SWarner Losh             HUF_DECODE_SYMBOLX2_0(op4, &bitD4);
19310c16b537SWarner Losh 
19320c16b537SWarner Losh             endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4);
19330c16b537SWarner Losh         }
19340c16b537SWarner Losh 
19350c16b537SWarner Losh         /* check corruption */
19360c16b537SWarner Losh         if (op1 > opStart2) return ERROR(corruption_detected);
19370c16b537SWarner Losh         if (op2 > opStart3) return ERROR(corruption_detected);
19380c16b537SWarner Losh         if (op3 > opStart4) return ERROR(corruption_detected);
19390c16b537SWarner Losh         /* note : op4 supposed already verified within main loop */
19400c16b537SWarner Losh 
19410c16b537SWarner Losh         /* finish bitStreams one by one */
19420c16b537SWarner Losh         HUF_decodeStreamX2(op1, &bitD1, opStart2, dt, dtLog);
19430c16b537SWarner Losh         HUF_decodeStreamX2(op2, &bitD2, opStart3, dt, dtLog);
19440c16b537SWarner Losh         HUF_decodeStreamX2(op3, &bitD3, opStart4, dt, dtLog);
19450c16b537SWarner Losh         HUF_decodeStreamX2(op4, &bitD4, oend,     dt, dtLog);
19460c16b537SWarner Losh 
19470c16b537SWarner Losh         /* check */
19480c16b537SWarner Losh         endSignal = BIT_endOfDStream(&bitD1) & BIT_endOfDStream(&bitD2) & BIT_endOfDStream(&bitD3) & BIT_endOfDStream(&bitD4);
19490c16b537SWarner Losh         if (!endSignal) return ERROR(corruption_detected);
19500c16b537SWarner Losh 
19510c16b537SWarner Losh         /* decoded size */
19520c16b537SWarner Losh         return dstSize;
19530c16b537SWarner Losh     }
19540c16b537SWarner Losh }
19550c16b537SWarner Losh 
19560c16b537SWarner Losh 
19570c16b537SWarner Losh static size_t HUF_decompress4X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
19580c16b537SWarner Losh {
19590c16b537SWarner Losh     HUF_CREATE_STATIC_DTABLEX2(DTable, HUF_MAX_TABLELOG);
19600c16b537SWarner Losh     const BYTE* ip = (const BYTE*) cSrc;
19610c16b537SWarner Losh     size_t errorCode;
19620c16b537SWarner Losh 
19630c16b537SWarner Losh     errorCode = HUF_readDTableX2 (DTable, cSrc, cSrcSize);
19640c16b537SWarner Losh     if (HUF_isError(errorCode)) return errorCode;
19650c16b537SWarner Losh     if (errorCode >= cSrcSize) return ERROR(srcSize_wrong);
19660c16b537SWarner Losh     ip += errorCode;
19670c16b537SWarner Losh     cSrcSize -= errorCode;
19680c16b537SWarner Losh 
19690c16b537SWarner Losh     return HUF_decompress4X2_usingDTable (dst, dstSize, ip, cSrcSize, DTable);
19700c16b537SWarner Losh }
19710c16b537SWarner Losh 
19720c16b537SWarner Losh 
19730c16b537SWarner Losh /***************************/
19740c16b537SWarner Losh /* double-symbols decoding */
19750c16b537SWarner Losh /***************************/
19760c16b537SWarner Losh 
19770c16b537SWarner Losh static void HUF_fillDTableX4Level2(HUF_DEltX4* DTable, U32 sizeLog, const U32 consumed,
19780c16b537SWarner Losh                            const U32* rankValOrigin, const int minWeight,
19790c16b537SWarner Losh                            const sortedSymbol_t* sortedSymbols, const U32 sortedListSize,
19800c16b537SWarner Losh                            U32 nbBitsBaseline, U16 baseSeq)
19810c16b537SWarner Losh {
19820c16b537SWarner Losh     HUF_DEltX4 DElt;
19830c16b537SWarner Losh     U32 rankVal[HUF_ABSOLUTEMAX_TABLELOG + 1];
19840c16b537SWarner Losh     U32 s;
19850c16b537SWarner Losh 
19860c16b537SWarner Losh     /* get pre-calculated rankVal */
19870c16b537SWarner Losh     memcpy(rankVal, rankValOrigin, sizeof(rankVal));
19880c16b537SWarner Losh 
19890c16b537SWarner Losh     /* fill skipped values */
19900c16b537SWarner Losh     if (minWeight>1)
19910c16b537SWarner Losh     {
19920c16b537SWarner Losh         U32 i, skipSize = rankVal[minWeight];
19930c16b537SWarner Losh         MEM_writeLE16(&(DElt.sequence), baseSeq);
19940c16b537SWarner Losh         DElt.nbBits   = (BYTE)(consumed);
19950c16b537SWarner Losh         DElt.length   = 1;
19960c16b537SWarner Losh         for (i = 0; i < skipSize; i++)
19970c16b537SWarner Losh             DTable[i] = DElt;
19980c16b537SWarner Losh     }
19990c16b537SWarner Losh 
20000c16b537SWarner Losh     /* fill DTable */
20010c16b537SWarner Losh     for (s=0; s<sortedListSize; s++)   /* note : sortedSymbols already skipped */
20020c16b537SWarner Losh     {
20030c16b537SWarner Losh         const U32 symbol = sortedSymbols[s].symbol;
20040c16b537SWarner Losh         const U32 weight = sortedSymbols[s].weight;
20050c16b537SWarner Losh         const U32 nbBits = nbBitsBaseline - weight;
20060c16b537SWarner Losh         const U32 length = 1 << (sizeLog-nbBits);
20070c16b537SWarner Losh         const U32 start = rankVal[weight];
20080c16b537SWarner Losh         U32 i = start;
20090c16b537SWarner Losh         const U32 end = start + length;
20100c16b537SWarner Losh 
20110c16b537SWarner Losh         MEM_writeLE16(&(DElt.sequence), (U16)(baseSeq + (symbol << 8)));
20120c16b537SWarner Losh         DElt.nbBits = (BYTE)(nbBits + consumed);
20130c16b537SWarner Losh         DElt.length = 2;
20140c16b537SWarner Losh         do { DTable[i++] = DElt; } while (i<end);   /* since length >= 1 */
20150c16b537SWarner Losh 
20160c16b537SWarner Losh         rankVal[weight] += length;
20170c16b537SWarner Losh     }
20180c16b537SWarner Losh }
20190c16b537SWarner Losh 
20200c16b537SWarner Losh typedef U32 rankVal_t[HUF_ABSOLUTEMAX_TABLELOG][HUF_ABSOLUTEMAX_TABLELOG + 1];
20210c16b537SWarner Losh 
20220c16b537SWarner Losh static void HUF_fillDTableX4(HUF_DEltX4* DTable, const U32 targetLog,
20230c16b537SWarner Losh                            const sortedSymbol_t* sortedList, const U32 sortedListSize,
20240c16b537SWarner Losh                            const U32* rankStart, rankVal_t rankValOrigin, const U32 maxWeight,
20250c16b537SWarner Losh                            const U32 nbBitsBaseline)
20260c16b537SWarner Losh {
20270c16b537SWarner Losh     U32 rankVal[HUF_ABSOLUTEMAX_TABLELOG + 1];
20280c16b537SWarner Losh     const int scaleLog = nbBitsBaseline - targetLog;   /* note : targetLog >= srcLog, hence scaleLog <= 1 */
20290c16b537SWarner Losh     const U32 minBits  = nbBitsBaseline - maxWeight;
20300c16b537SWarner Losh     U32 s;
20310c16b537SWarner Losh 
20320c16b537SWarner Losh     memcpy(rankVal, rankValOrigin, sizeof(rankVal));
20330c16b537SWarner Losh 
20340c16b537SWarner Losh     /* fill DTable */
20350c16b537SWarner Losh     for (s=0; s<sortedListSize; s++)
20360c16b537SWarner Losh     {
20370c16b537SWarner Losh         const U16 symbol = sortedList[s].symbol;
20380c16b537SWarner Losh         const U32 weight = sortedList[s].weight;
20390c16b537SWarner Losh         const U32 nbBits = nbBitsBaseline - weight;
20400c16b537SWarner Losh         const U32 start = rankVal[weight];
20410c16b537SWarner Losh         const U32 length = 1 << (targetLog-nbBits);
20420c16b537SWarner Losh 
20430c16b537SWarner Losh         if (targetLog-nbBits >= minBits)   /* enough room for a second symbol */
20440c16b537SWarner Losh         {
20450c16b537SWarner Losh             U32 sortedRank;
20460c16b537SWarner Losh             int minWeight = nbBits + scaleLog;
20470c16b537SWarner Losh             if (minWeight < 1) minWeight = 1;
20480c16b537SWarner Losh             sortedRank = rankStart[minWeight];
20490c16b537SWarner Losh             HUF_fillDTableX4Level2(DTable+start, targetLog-nbBits, nbBits,
20500c16b537SWarner Losh                            rankValOrigin[nbBits], minWeight,
20510c16b537SWarner Losh                            sortedList+sortedRank, sortedListSize-sortedRank,
20520c16b537SWarner Losh                            nbBitsBaseline, symbol);
20530c16b537SWarner Losh         }
20540c16b537SWarner Losh         else
20550c16b537SWarner Losh         {
20560c16b537SWarner Losh             U32 i;
20570c16b537SWarner Losh             const U32 end = start + length;
20580c16b537SWarner Losh             HUF_DEltX4 DElt;
20590c16b537SWarner Losh 
20600c16b537SWarner Losh             MEM_writeLE16(&(DElt.sequence), symbol);
20610c16b537SWarner Losh             DElt.nbBits   = (BYTE)(nbBits);
20620c16b537SWarner Losh             DElt.length   = 1;
20630c16b537SWarner Losh             for (i = start; i < end; i++)
20640c16b537SWarner Losh                 DTable[i] = DElt;
20650c16b537SWarner Losh         }
20660c16b537SWarner Losh         rankVal[weight] += length;
20670c16b537SWarner Losh     }
20680c16b537SWarner Losh }
20690c16b537SWarner Losh 
20700c16b537SWarner Losh static size_t HUF_readDTableX4 (U32* DTable, const void* src, size_t srcSize)
20710c16b537SWarner Losh {
20720c16b537SWarner Losh     BYTE weightList[HUF_MAX_SYMBOL_VALUE + 1];
20730c16b537SWarner Losh     sortedSymbol_t sortedSymbol[HUF_MAX_SYMBOL_VALUE + 1];
20740c16b537SWarner Losh     U32 rankStats[HUF_ABSOLUTEMAX_TABLELOG + 1] = { 0 };
20750c16b537SWarner Losh     U32 rankStart0[HUF_ABSOLUTEMAX_TABLELOG + 2] = { 0 };
20760c16b537SWarner Losh     U32* const rankStart = rankStart0+1;
20770c16b537SWarner Losh     rankVal_t rankVal;
20780c16b537SWarner Losh     U32 tableLog, maxW, sizeOfSort, nbSymbols;
20790c16b537SWarner Losh     const U32 memLog = DTable[0];
20800c16b537SWarner Losh     size_t iSize;
20810c16b537SWarner Losh     void* dtPtr = DTable;
20820c16b537SWarner Losh     HUF_DEltX4* const dt = ((HUF_DEltX4*)dtPtr) + 1;
20830c16b537SWarner Losh 
20840c16b537SWarner Losh     HUF_STATIC_ASSERT(sizeof(HUF_DEltX4) == sizeof(U32));   /* if compilation fails here, assertion is false */
20850c16b537SWarner Losh     if (memLog > HUF_ABSOLUTEMAX_TABLELOG) return ERROR(tableLog_tooLarge);
20860c16b537SWarner Losh     //memset(weightList, 0, sizeof(weightList));   /* is not necessary, even though some analyzer complain ... */
20870c16b537SWarner Losh 
20880c16b537SWarner Losh     iSize = HUF_readStats(weightList, HUF_MAX_SYMBOL_VALUE + 1, rankStats, &nbSymbols, &tableLog, src, srcSize);
20890c16b537SWarner Losh     if (HUF_isError(iSize)) return iSize;
20900c16b537SWarner Losh 
20910c16b537SWarner Losh     /* check result */
20920c16b537SWarner Losh     if (tableLog > memLog) return ERROR(tableLog_tooLarge);   /* DTable can't fit code depth */
20930c16b537SWarner Losh 
20940c16b537SWarner Losh     /* find maxWeight */
20950c16b537SWarner Losh     for (maxW = tableLog; rankStats[maxW]==0; maxW--)
20960c16b537SWarner Losh         { if (!maxW) return ERROR(GENERIC); }  /* necessarily finds a solution before maxW==0 */
20970c16b537SWarner Losh 
20980c16b537SWarner Losh     /* Get start index of each weight */
20990c16b537SWarner Losh     {
21000c16b537SWarner Losh         U32 w, nextRankStart = 0;
21010c16b537SWarner Losh         for (w=1; w<=maxW; w++)
21020c16b537SWarner Losh         {
21030c16b537SWarner Losh             U32 current = nextRankStart;
21040c16b537SWarner Losh             nextRankStart += rankStats[w];
21050c16b537SWarner Losh             rankStart[w] = current;
21060c16b537SWarner Losh         }
21070c16b537SWarner Losh         rankStart[0] = nextRankStart;   /* put all 0w symbols at the end of sorted list*/
21080c16b537SWarner Losh         sizeOfSort = nextRankStart;
21090c16b537SWarner Losh     }
21100c16b537SWarner Losh 
21110c16b537SWarner Losh     /* sort symbols by weight */
21120c16b537SWarner Losh     {
21130c16b537SWarner Losh         U32 s;
21140c16b537SWarner Losh         for (s=0; s<nbSymbols; s++)
21150c16b537SWarner Losh         {
21160c16b537SWarner Losh             U32 w = weightList[s];
21170c16b537SWarner Losh             U32 r = rankStart[w]++;
21180c16b537SWarner Losh             sortedSymbol[r].symbol = (BYTE)s;
21190c16b537SWarner Losh             sortedSymbol[r].weight = (BYTE)w;
21200c16b537SWarner Losh         }
21210c16b537SWarner Losh         rankStart[0] = 0;   /* forget 0w symbols; this is beginning of weight(1) */
21220c16b537SWarner Losh     }
21230c16b537SWarner Losh 
21240c16b537SWarner Losh     /* Build rankVal */
21250c16b537SWarner Losh     {
21260c16b537SWarner Losh         const U32 minBits = tableLog+1 - maxW;
21270c16b537SWarner Losh         U32 nextRankVal = 0;
21280c16b537SWarner Losh         U32 w, consumed;
21290c16b537SWarner Losh         const int rescale = (memLog-tableLog) - 1;   /* tableLog <= memLog */
21300c16b537SWarner Losh         U32* rankVal0 = rankVal[0];
21310c16b537SWarner Losh         for (w=1; w<=maxW; w++)
21320c16b537SWarner Losh         {
21330c16b537SWarner Losh             U32 current = nextRankVal;
21340c16b537SWarner Losh             nextRankVal += rankStats[w] << (w+rescale);
21350c16b537SWarner Losh             rankVal0[w] = current;
21360c16b537SWarner Losh         }
21370c16b537SWarner Losh         for (consumed = minBits; consumed <= memLog - minBits; consumed++)
21380c16b537SWarner Losh         {
21390c16b537SWarner Losh             U32* rankValPtr = rankVal[consumed];
21400c16b537SWarner Losh             for (w = 1; w <= maxW; w++)
21410c16b537SWarner Losh             {
21420c16b537SWarner Losh                 rankValPtr[w] = rankVal0[w] >> consumed;
21430c16b537SWarner Losh             }
21440c16b537SWarner Losh         }
21450c16b537SWarner Losh     }
21460c16b537SWarner Losh 
21470c16b537SWarner Losh     HUF_fillDTableX4(dt, memLog,
21480c16b537SWarner Losh                    sortedSymbol, sizeOfSort,
21490c16b537SWarner Losh                    rankStart0, rankVal, maxW,
21500c16b537SWarner Losh                    tableLog+1);
21510c16b537SWarner Losh 
21520c16b537SWarner Losh     return iSize;
21530c16b537SWarner Losh }
21540c16b537SWarner Losh 
21550c16b537SWarner Losh 
21560c16b537SWarner Losh static U32 HUF_decodeSymbolX4(void* op, BIT_DStream_t* DStream, const HUF_DEltX4* dt, const U32 dtLog)
21570c16b537SWarner Losh {
21580c16b537SWarner Losh     const size_t val = BIT_lookBitsFast(DStream, dtLog);   /* note : dtLog >= 1 */
21590c16b537SWarner Losh     memcpy(op, dt+val, 2);
21600c16b537SWarner Losh     BIT_skipBits(DStream, dt[val].nbBits);
21610c16b537SWarner Losh     return dt[val].length;
21620c16b537SWarner Losh }
21630c16b537SWarner Losh 
21640c16b537SWarner Losh static U32 HUF_decodeLastSymbolX4(void* op, BIT_DStream_t* DStream, const HUF_DEltX4* dt, const U32 dtLog)
21650c16b537SWarner Losh {
21660c16b537SWarner Losh     const size_t val = BIT_lookBitsFast(DStream, dtLog);   /* note : dtLog >= 1 */
21670c16b537SWarner Losh     memcpy(op, dt+val, 1);
21680c16b537SWarner Losh     if (dt[val].length==1) BIT_skipBits(DStream, dt[val].nbBits);
21690c16b537SWarner Losh     else
21700c16b537SWarner Losh     {
21710c16b537SWarner Losh         if (DStream->bitsConsumed < (sizeof(DStream->bitContainer)*8))
21720c16b537SWarner Losh         {
21730c16b537SWarner Losh             BIT_skipBits(DStream, dt[val].nbBits);
21740c16b537SWarner Losh             if (DStream->bitsConsumed > (sizeof(DStream->bitContainer)*8))
21750c16b537SWarner Losh                 DStream->bitsConsumed = (sizeof(DStream->bitContainer)*8);   /* ugly hack; works only because it's the last symbol. Note : can't easily extract nbBits from just this symbol */
21760c16b537SWarner Losh         }
21770c16b537SWarner Losh     }
21780c16b537SWarner Losh     return 1;
21790c16b537SWarner Losh }
21800c16b537SWarner Losh 
21810c16b537SWarner Losh 
21820c16b537SWarner Losh #define HUF_DECODE_SYMBOLX4_0(ptr, DStreamPtr) \
21830c16b537SWarner Losh     ptr += HUF_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
21840c16b537SWarner Losh 
21850c16b537SWarner Losh #define HUF_DECODE_SYMBOLX4_1(ptr, DStreamPtr) \
21860c16b537SWarner Losh     if (MEM_64bits() || (HUF_MAX_TABLELOG<=12)) \
21870c16b537SWarner Losh         ptr += HUF_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
21880c16b537SWarner Losh 
21890c16b537SWarner Losh #define HUF_DECODE_SYMBOLX4_2(ptr, DStreamPtr) \
21900c16b537SWarner Losh     if (MEM_64bits()) \
21910c16b537SWarner Losh         ptr += HUF_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
21920c16b537SWarner Losh 
21930c16b537SWarner Losh static inline size_t HUF_decodeStreamX4(BYTE* p, BIT_DStream_t* bitDPtr, BYTE* const pEnd, const HUF_DEltX4* const dt, const U32 dtLog)
21940c16b537SWarner Losh {
21950c16b537SWarner Losh     BYTE* const pStart = p;
21960c16b537SWarner Losh 
21970c16b537SWarner Losh     /* up to 8 symbols at a time */
21980c16b537SWarner Losh     while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p < pEnd-7))
21990c16b537SWarner Losh     {
22000c16b537SWarner Losh         HUF_DECODE_SYMBOLX4_2(p, bitDPtr);
22010c16b537SWarner Losh         HUF_DECODE_SYMBOLX4_1(p, bitDPtr);
22020c16b537SWarner Losh         HUF_DECODE_SYMBOLX4_2(p, bitDPtr);
22030c16b537SWarner Losh         HUF_DECODE_SYMBOLX4_0(p, bitDPtr);
22040c16b537SWarner Losh     }
22050c16b537SWarner Losh 
22060c16b537SWarner Losh     /* closer to the end */
22070c16b537SWarner Losh     while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p <= pEnd-2))
22080c16b537SWarner Losh         HUF_DECODE_SYMBOLX4_0(p, bitDPtr);
22090c16b537SWarner Losh 
22100c16b537SWarner Losh     while (p <= pEnd-2)
22110c16b537SWarner Losh         HUF_DECODE_SYMBOLX4_0(p, bitDPtr);   /* no need to reload : reached the end of DStream */
22120c16b537SWarner Losh 
22130c16b537SWarner Losh     if (p < pEnd)
22140c16b537SWarner Losh         p += HUF_decodeLastSymbolX4(p, bitDPtr, dt, dtLog);
22150c16b537SWarner Losh 
22160c16b537SWarner Losh     return p-pStart;
22170c16b537SWarner Losh }
22180c16b537SWarner Losh 
22190c16b537SWarner Losh static size_t HUF_decompress4X4_usingDTable(
22200c16b537SWarner Losh           void* dst,  size_t dstSize,
22210c16b537SWarner Losh     const void* cSrc, size_t cSrcSize,
22220c16b537SWarner Losh     const U32* DTable)
22230c16b537SWarner Losh {
22240c16b537SWarner Losh     if (cSrcSize < 10) return ERROR(corruption_detected);   /* strict minimum : jump table + 1 byte per stream */
22250c16b537SWarner Losh 
22260c16b537SWarner Losh     {
22270c16b537SWarner Losh         const BYTE* const istart = (const BYTE*) cSrc;
22280c16b537SWarner Losh         BYTE* const ostart = (BYTE*) dst;
22290c16b537SWarner Losh         BYTE* const oend = ostart + dstSize;
22300c16b537SWarner Losh         const void* const dtPtr = DTable;
22310c16b537SWarner Losh         const HUF_DEltX4* const dt = ((const HUF_DEltX4*)dtPtr) +1;
22320c16b537SWarner Losh         const U32 dtLog = DTable[0];
22330c16b537SWarner Losh         size_t errorCode;
22340c16b537SWarner Losh 
22350c16b537SWarner Losh         /* Init */
22360c16b537SWarner Losh         BIT_DStream_t bitD1;
22370c16b537SWarner Losh         BIT_DStream_t bitD2;
22380c16b537SWarner Losh         BIT_DStream_t bitD3;
22390c16b537SWarner Losh         BIT_DStream_t bitD4;
22400c16b537SWarner Losh         const size_t length1 = MEM_readLE16(istart);
22410c16b537SWarner Losh         const size_t length2 = MEM_readLE16(istart+2);
22420c16b537SWarner Losh         const size_t length3 = MEM_readLE16(istart+4);
22430c16b537SWarner Losh         size_t length4;
22440c16b537SWarner Losh         const BYTE* const istart1 = istart + 6;  /* jumpTable */
22450c16b537SWarner Losh         const BYTE* const istart2 = istart1 + length1;
22460c16b537SWarner Losh         const BYTE* const istart3 = istart2 + length2;
22470c16b537SWarner Losh         const BYTE* const istart4 = istart3 + length3;
22480c16b537SWarner Losh         const size_t segmentSize = (dstSize+3) / 4;
22490c16b537SWarner Losh         BYTE* const opStart2 = ostart + segmentSize;
22500c16b537SWarner Losh         BYTE* const opStart3 = opStart2 + segmentSize;
22510c16b537SWarner Losh         BYTE* const opStart4 = opStart3 + segmentSize;
22520c16b537SWarner Losh         BYTE* op1 = ostart;
22530c16b537SWarner Losh         BYTE* op2 = opStart2;
22540c16b537SWarner Losh         BYTE* op3 = opStart3;
22550c16b537SWarner Losh         BYTE* op4 = opStart4;
22560c16b537SWarner Losh         U32 endSignal;
22570c16b537SWarner Losh 
22580c16b537SWarner Losh         length4 = cSrcSize - (length1 + length2 + length3 + 6);
22590c16b537SWarner Losh         if (length4 > cSrcSize) return ERROR(corruption_detected);   /* overflow */
22600c16b537SWarner Losh         errorCode = BIT_initDStream(&bitD1, istart1, length1);
22610c16b537SWarner Losh         if (HUF_isError(errorCode)) return errorCode;
22620c16b537SWarner Losh         errorCode = BIT_initDStream(&bitD2, istart2, length2);
22630c16b537SWarner Losh         if (HUF_isError(errorCode)) return errorCode;
22640c16b537SWarner Losh         errorCode = BIT_initDStream(&bitD3, istart3, length3);
22650c16b537SWarner Losh         if (HUF_isError(errorCode)) return errorCode;
22660c16b537SWarner Losh         errorCode = BIT_initDStream(&bitD4, istart4, length4);
22670c16b537SWarner Losh         if (HUF_isError(errorCode)) return errorCode;
22680c16b537SWarner Losh 
22690c16b537SWarner Losh         /* 16-32 symbols per loop (4-8 symbols per stream) */
22700c16b537SWarner Losh         endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4);
22710c16b537SWarner Losh         for ( ; (endSignal==BIT_DStream_unfinished) && (op4<(oend-7)) ; )
22720c16b537SWarner Losh         {
22730c16b537SWarner Losh             HUF_DECODE_SYMBOLX4_2(op1, &bitD1);
22740c16b537SWarner Losh             HUF_DECODE_SYMBOLX4_2(op2, &bitD2);
22750c16b537SWarner Losh             HUF_DECODE_SYMBOLX4_2(op3, &bitD3);
22760c16b537SWarner Losh             HUF_DECODE_SYMBOLX4_2(op4, &bitD4);
22770c16b537SWarner Losh             HUF_DECODE_SYMBOLX4_1(op1, &bitD1);
22780c16b537SWarner Losh             HUF_DECODE_SYMBOLX4_1(op2, &bitD2);
22790c16b537SWarner Losh             HUF_DECODE_SYMBOLX4_1(op3, &bitD3);
22800c16b537SWarner Losh             HUF_DECODE_SYMBOLX4_1(op4, &bitD4);
22810c16b537SWarner Losh             HUF_DECODE_SYMBOLX4_2(op1, &bitD1);
22820c16b537SWarner Losh             HUF_DECODE_SYMBOLX4_2(op2, &bitD2);
22830c16b537SWarner Losh             HUF_DECODE_SYMBOLX4_2(op3, &bitD3);
22840c16b537SWarner Losh             HUF_DECODE_SYMBOLX4_2(op4, &bitD4);
22850c16b537SWarner Losh             HUF_DECODE_SYMBOLX4_0(op1, &bitD1);
22860c16b537SWarner Losh             HUF_DECODE_SYMBOLX4_0(op2, &bitD2);
22870c16b537SWarner Losh             HUF_DECODE_SYMBOLX4_0(op3, &bitD3);
22880c16b537SWarner Losh             HUF_DECODE_SYMBOLX4_0(op4, &bitD4);
22890c16b537SWarner Losh 
22900c16b537SWarner Losh             endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4);
22910c16b537SWarner Losh         }
22920c16b537SWarner Losh 
22930c16b537SWarner Losh         /* check corruption */
22940c16b537SWarner Losh         if (op1 > opStart2) return ERROR(corruption_detected);
22950c16b537SWarner Losh         if (op2 > opStart3) return ERROR(corruption_detected);
22960c16b537SWarner Losh         if (op3 > opStart4) return ERROR(corruption_detected);
22970c16b537SWarner Losh         /* note : op4 supposed already verified within main loop */
22980c16b537SWarner Losh 
22990c16b537SWarner Losh         /* finish bitStreams one by one */
23000c16b537SWarner Losh         HUF_decodeStreamX4(op1, &bitD1, opStart2, dt, dtLog);
23010c16b537SWarner Losh         HUF_decodeStreamX4(op2, &bitD2, opStart3, dt, dtLog);
23020c16b537SWarner Losh         HUF_decodeStreamX4(op3, &bitD3, opStart4, dt, dtLog);
23030c16b537SWarner Losh         HUF_decodeStreamX4(op4, &bitD4, oend,     dt, dtLog);
23040c16b537SWarner Losh 
23050c16b537SWarner Losh         /* check */
23060c16b537SWarner Losh         endSignal = BIT_endOfDStream(&bitD1) & BIT_endOfDStream(&bitD2) & BIT_endOfDStream(&bitD3) & BIT_endOfDStream(&bitD4);
23070c16b537SWarner Losh         if (!endSignal) return ERROR(corruption_detected);
23080c16b537SWarner Losh 
23090c16b537SWarner Losh         /* decoded size */
23100c16b537SWarner Losh         return dstSize;
23110c16b537SWarner Losh     }
23120c16b537SWarner Losh }
23130c16b537SWarner Losh 
23140c16b537SWarner Losh 
23150c16b537SWarner Losh static size_t HUF_decompress4X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
23160c16b537SWarner Losh {
23170c16b537SWarner Losh     HUF_CREATE_STATIC_DTABLEX4(DTable, HUF_MAX_TABLELOG);
23180c16b537SWarner Losh     const BYTE* ip = (const BYTE*) cSrc;
23190c16b537SWarner Losh 
23200c16b537SWarner Losh     size_t hSize = HUF_readDTableX4 (DTable, cSrc, cSrcSize);
23210c16b537SWarner Losh     if (HUF_isError(hSize)) return hSize;
23220c16b537SWarner Losh     if (hSize >= cSrcSize) return ERROR(srcSize_wrong);
23230c16b537SWarner Losh     ip += hSize;
23240c16b537SWarner Losh     cSrcSize -= hSize;
23250c16b537SWarner Losh 
23260c16b537SWarner Losh     return HUF_decompress4X4_usingDTable (dst, dstSize, ip, cSrcSize, DTable);
23270c16b537SWarner Losh }
23280c16b537SWarner Losh 
23290c16b537SWarner Losh 
23300c16b537SWarner Losh /**********************************/
23310c16b537SWarner Losh /* Generic decompression selector */
23320c16b537SWarner Losh /**********************************/
23330c16b537SWarner Losh 
23340c16b537SWarner Losh typedef struct { U32 tableTime; U32 decode256Time; } algo_time_t;
23350c16b537SWarner Losh static const algo_time_t algoTime[16 /* Quantization */][3 /* single, double, quad */] =
23360c16b537SWarner Losh {
23370c16b537SWarner Losh     /* single, double, quad */
23380c16b537SWarner Losh     {{0,0}, {1,1}, {2,2}},  /* Q==0 : impossible */
23390c16b537SWarner Losh     {{0,0}, {1,1}, {2,2}},  /* Q==1 : impossible */
23400c16b537SWarner Losh     {{  38,130}, {1313, 74}, {2151, 38}},   /* Q == 2 : 12-18% */
23410c16b537SWarner Losh     {{ 448,128}, {1353, 74}, {2238, 41}},   /* Q == 3 : 18-25% */
23420c16b537SWarner Losh     {{ 556,128}, {1353, 74}, {2238, 47}},   /* Q == 4 : 25-32% */
23430c16b537SWarner Losh     {{ 714,128}, {1418, 74}, {2436, 53}},   /* Q == 5 : 32-38% */
23440c16b537SWarner Losh     {{ 883,128}, {1437, 74}, {2464, 61}},   /* Q == 6 : 38-44% */
23450c16b537SWarner Losh     {{ 897,128}, {1515, 75}, {2622, 68}},   /* Q == 7 : 44-50% */
23460c16b537SWarner Losh     {{ 926,128}, {1613, 75}, {2730, 75}},   /* Q == 8 : 50-56% */
23470c16b537SWarner Losh     {{ 947,128}, {1729, 77}, {3359, 77}},   /* Q == 9 : 56-62% */
23480c16b537SWarner Losh     {{1107,128}, {2083, 81}, {4006, 84}},   /* Q ==10 : 62-69% */
23490c16b537SWarner Losh     {{1177,128}, {2379, 87}, {4785, 88}},   /* Q ==11 : 69-75% */
23500c16b537SWarner Losh     {{1242,128}, {2415, 93}, {5155, 84}},   /* Q ==12 : 75-81% */
23510c16b537SWarner Losh     {{1349,128}, {2644,106}, {5260,106}},   /* Q ==13 : 81-87% */
23520c16b537SWarner Losh     {{1455,128}, {2422,124}, {4174,124}},   /* Q ==14 : 87-93% */
23530c16b537SWarner Losh     {{ 722,128}, {1891,145}, {1936,146}},   /* Q ==15 : 93-99% */
23540c16b537SWarner Losh };
23550c16b537SWarner Losh 
23560c16b537SWarner Losh typedef size_t (*decompressionAlgo)(void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize);
23570c16b537SWarner Losh 
23580c16b537SWarner Losh static size_t HUF_decompress (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
23590c16b537SWarner Losh {
23600c16b537SWarner Losh     static const decompressionAlgo decompress[3] = { HUF_decompress4X2, HUF_decompress4X4, NULL };
23610c16b537SWarner Losh     /* estimate decompression time */
23620c16b537SWarner Losh     U32 Q;
23630c16b537SWarner Losh     const U32 D256 = (U32)(dstSize >> 8);
23640c16b537SWarner Losh     U32 Dtime[3];
23650c16b537SWarner Losh     U32 algoNb = 0;
23660c16b537SWarner Losh     int n;
23670c16b537SWarner Losh 
23680c16b537SWarner Losh     /* validation checks */
23690c16b537SWarner Losh     if (dstSize == 0) return ERROR(dstSize_tooSmall);
23700c16b537SWarner Losh     if (cSrcSize > dstSize) return ERROR(corruption_detected);   /* invalid */
23710c16b537SWarner Losh     if (cSrcSize == dstSize) { memcpy(dst, cSrc, dstSize); return dstSize; }   /* not compressed */
23720c16b537SWarner Losh     if (cSrcSize == 1) { memset(dst, *(const BYTE*)cSrc, dstSize); return dstSize; }   /* RLE */
23730c16b537SWarner Losh 
23740c16b537SWarner Losh     /* decoder timing evaluation */
23750c16b537SWarner Losh     Q = (U32)(cSrcSize * 16 / dstSize);   /* Q < 16 since dstSize > cSrcSize */
23760c16b537SWarner Losh     for (n=0; n<3; n++)
23770c16b537SWarner Losh         Dtime[n] = algoTime[Q][n].tableTime + (algoTime[Q][n].decode256Time * D256);
23780c16b537SWarner Losh 
23790c16b537SWarner Losh     Dtime[1] += Dtime[1] >> 4; Dtime[2] += Dtime[2] >> 3; /* advantage to algorithms using less memory, for cache eviction */
23800c16b537SWarner Losh 
23810c16b537SWarner Losh     if (Dtime[1] < Dtime[0]) algoNb = 1;
23820c16b537SWarner Losh 
23830c16b537SWarner Losh     return decompress[algoNb](dst, dstSize, cSrc, cSrcSize);
23840c16b537SWarner Losh 
23850c16b537SWarner Losh     //return HUF_decompress4X2(dst, dstSize, cSrc, cSrcSize);   /* multi-streams single-symbol decoding */
23860c16b537SWarner Losh     //return HUF_decompress4X4(dst, dstSize, cSrc, cSrcSize);   /* multi-streams double-symbols decoding */
23870c16b537SWarner Losh     //return HUF_decompress4X6(dst, dstSize, cSrc, cSrcSize);   /* multi-streams quad-symbols decoding */
23880c16b537SWarner Losh }
23890c16b537SWarner Losh 
23900c16b537SWarner Losh 
23910c16b537SWarner Losh 
23920c16b537SWarner Losh #endif   /* ZSTD_CCOMMON_H_MODULE */
23930c16b537SWarner Losh 
23940c16b537SWarner Losh 
23950c16b537SWarner Losh /*
23960c16b537SWarner Losh     zstd - decompression module fo v0.4 legacy format
23970c16b537SWarner Losh     Copyright (C) 2015-2016, Yann Collet.
23980c16b537SWarner Losh 
23990c16b537SWarner Losh     BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
24000c16b537SWarner Losh 
24010c16b537SWarner Losh     Redistribution and use in source and binary forms, with or without
24020c16b537SWarner Losh     modification, are permitted provided that the following conditions are
24030c16b537SWarner Losh     met:
24040c16b537SWarner Losh     * Redistributions of source code must retain the above copyright
24050c16b537SWarner Losh     notice, this list of conditions and the following disclaimer.
24060c16b537SWarner Losh     * Redistributions in binary form must reproduce the above
24070c16b537SWarner Losh     copyright notice, this list of conditions and the following disclaimer
24080c16b537SWarner Losh     in the documentation and/or other materials provided with the
24090c16b537SWarner Losh     distribution.
24100c16b537SWarner Losh     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
24110c16b537SWarner Losh     "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
24120c16b537SWarner Losh     LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
24130c16b537SWarner Losh     A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
24140c16b537SWarner Losh     OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
24150c16b537SWarner Losh     SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
24160c16b537SWarner Losh     LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
24170c16b537SWarner Losh     DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24180c16b537SWarner Losh     THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24190c16b537SWarner Losh     (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
24200c16b537SWarner Losh     OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24210c16b537SWarner Losh 
24220c16b537SWarner Losh     You can contact the author at :
24230c16b537SWarner Losh     - zstd source repository : https://github.com/Cyan4973/zstd
24240c16b537SWarner Losh     - ztsd public forum : https://groups.google.com/forum/#!forum/lz4c
24250c16b537SWarner Losh */
24260c16b537SWarner Losh 
24270c16b537SWarner Losh /* ***************************************************************
24280c16b537SWarner Losh *  Tuning parameters
24290c16b537SWarner Losh *****************************************************************/
24300c16b537SWarner Losh /*!
24310c16b537SWarner Losh  * HEAPMODE :
24320c16b537SWarner Losh  * Select how default decompression function ZSTD_decompress() will allocate memory,
24330c16b537SWarner Losh  * in memory stack (0), or in memory heap (1, requires malloc())
24340c16b537SWarner Losh  */
24350c16b537SWarner Losh #ifndef ZSTD_HEAPMODE
24360c16b537SWarner Losh #  define ZSTD_HEAPMODE 1
24370c16b537SWarner Losh #endif
24380c16b537SWarner Losh 
24390c16b537SWarner Losh 
24400c16b537SWarner Losh /* *******************************************************
24410c16b537SWarner Losh *  Includes
24420c16b537SWarner Losh *********************************************************/
24430c16b537SWarner Losh #include <stdlib.h>      /* calloc */
24440c16b537SWarner Losh #include <string.h>      /* memcpy, memmove */
24450c16b537SWarner Losh #include <stdio.h>       /* debug : printf */
24460c16b537SWarner Losh 
24470c16b537SWarner Losh 
24480c16b537SWarner Losh /* *******************************************************
24490c16b537SWarner Losh *  Compiler specifics
24500c16b537SWarner Losh *********************************************************/
24510c16b537SWarner Losh #ifdef _MSC_VER    /* Visual Studio */
24520c16b537SWarner Losh #  include <intrin.h>                    /* For Visual 2005 */
24530c16b537SWarner Losh #  pragma warning(disable : 4127)        /* disable: C4127: conditional expression is constant */
24540c16b537SWarner Losh #  pragma warning(disable : 4324)        /* disable: C4324: padded structure */
24550c16b537SWarner Losh #endif
24560c16b537SWarner Losh 
24570c16b537SWarner Losh 
24580c16b537SWarner Losh /* *************************************
24590c16b537SWarner Losh *  Local types
24600c16b537SWarner Losh ***************************************/
24610c16b537SWarner Losh typedef struct
24620c16b537SWarner Losh {
24630c16b537SWarner Losh     blockType_t blockType;
24640c16b537SWarner Losh     U32 origSize;
24650c16b537SWarner Losh } blockProperties_t;
24660c16b537SWarner Losh 
24670c16b537SWarner Losh 
24680c16b537SWarner Losh /* *******************************************************
24690c16b537SWarner Losh *  Memory operations
24700c16b537SWarner Losh **********************************************************/
24710c16b537SWarner Losh static void ZSTD_copy4(void* dst, const void* src) { memcpy(dst, src, 4); }
24720c16b537SWarner Losh 
24730c16b537SWarner Losh 
24740c16b537SWarner Losh /* *************************************
24750c16b537SWarner Losh *  Error Management
24760c16b537SWarner Losh ***************************************/
24770c16b537SWarner Losh 
24780c16b537SWarner Losh /*! ZSTD_isError
24790c16b537SWarner Losh *   tells if a return value is an error code */
24800c16b537SWarner Losh static unsigned ZSTD_isError(size_t code) { return ERR_isError(code); }
24810c16b537SWarner Losh 
24820c16b537SWarner Losh 
24830c16b537SWarner Losh /* *************************************************************
24840c16b537SWarner Losh *   Context management
24850c16b537SWarner Losh ***************************************************************/
24860c16b537SWarner Losh typedef enum { ZSTDds_getFrameHeaderSize, ZSTDds_decodeFrameHeader,
24870c16b537SWarner Losh                ZSTDds_decodeBlockHeader, ZSTDds_decompressBlock } ZSTD_dStage;
24880c16b537SWarner Losh 
24890c16b537SWarner Losh struct ZSTDv04_Dctx_s
24900c16b537SWarner Losh {
24910c16b537SWarner Losh     U32 LLTable[FSE_DTABLE_SIZE_U32(LLFSELog)];
24920c16b537SWarner Losh     U32 OffTable[FSE_DTABLE_SIZE_U32(OffFSELog)];
24930c16b537SWarner Losh     U32 MLTable[FSE_DTABLE_SIZE_U32(MLFSELog)];
24940c16b537SWarner Losh     const void* previousDstEnd;
24950c16b537SWarner Losh     const void* base;
24960c16b537SWarner Losh     const void* vBase;
24970c16b537SWarner Losh     const void* dictEnd;
24980c16b537SWarner Losh     size_t expected;
24990c16b537SWarner Losh     size_t headerSize;
25000c16b537SWarner Losh     ZSTD_parameters params;
25010c16b537SWarner Losh     blockType_t bType;
25020c16b537SWarner Losh     ZSTD_dStage stage;
25030c16b537SWarner Losh     const BYTE* litPtr;
25040c16b537SWarner Losh     size_t litSize;
25050c16b537SWarner Losh     BYTE litBuffer[BLOCKSIZE + 8 /* margin for wildcopy */];
25060c16b537SWarner Losh     BYTE headerBuffer[ZSTD_frameHeaderSize_max];
25070c16b537SWarner Losh };  /* typedef'd to ZSTD_DCtx within "zstd_static.h" */
25080c16b537SWarner Losh 
25090c16b537SWarner Losh static size_t ZSTD_resetDCtx(ZSTD_DCtx* dctx)
25100c16b537SWarner Losh {
25110c16b537SWarner Losh     dctx->expected = ZSTD_frameHeaderSize_min;
25120c16b537SWarner Losh     dctx->stage = ZSTDds_getFrameHeaderSize;
25130c16b537SWarner Losh     dctx->previousDstEnd = NULL;
25140c16b537SWarner Losh     dctx->base = NULL;
25150c16b537SWarner Losh     dctx->vBase = NULL;
25160c16b537SWarner Losh     dctx->dictEnd = NULL;
25170c16b537SWarner Losh     return 0;
25180c16b537SWarner Losh }
25190c16b537SWarner Losh 
25200c16b537SWarner Losh static ZSTD_DCtx* ZSTD_createDCtx(void)
25210c16b537SWarner Losh {
25220c16b537SWarner Losh     ZSTD_DCtx* dctx = (ZSTD_DCtx*)malloc(sizeof(ZSTD_DCtx));
25230c16b537SWarner Losh     if (dctx==NULL) return NULL;
25240c16b537SWarner Losh     ZSTD_resetDCtx(dctx);
25250c16b537SWarner Losh     return dctx;
25260c16b537SWarner Losh }
25270c16b537SWarner Losh 
25280c16b537SWarner Losh static size_t ZSTD_freeDCtx(ZSTD_DCtx* dctx)
25290c16b537SWarner Losh {
25300c16b537SWarner Losh     free(dctx);
25310c16b537SWarner Losh     return 0;
25320c16b537SWarner Losh }
25330c16b537SWarner Losh 
25340c16b537SWarner Losh 
25350c16b537SWarner Losh /* *************************************************************
25360c16b537SWarner Losh *   Decompression section
25370c16b537SWarner Losh ***************************************************************/
25380c16b537SWarner Losh /** ZSTD_decodeFrameHeader_Part1
25390c16b537SWarner Losh *   decode the 1st part of the Frame Header, which tells Frame Header size.
25400c16b537SWarner Losh *   srcSize must be == ZSTD_frameHeaderSize_min
25410c16b537SWarner Losh *   @return : the full size of the Frame Header */
25420c16b537SWarner Losh static size_t ZSTD_decodeFrameHeader_Part1(ZSTD_DCtx* zc, const void* src, size_t srcSize)
25430c16b537SWarner Losh {
25440c16b537SWarner Losh     U32 magicNumber;
25450c16b537SWarner Losh     if (srcSize != ZSTD_frameHeaderSize_min) return ERROR(srcSize_wrong);
25460c16b537SWarner Losh     magicNumber = MEM_readLE32(src);
25470c16b537SWarner Losh     if (magicNumber != ZSTD_MAGICNUMBER) return ERROR(prefix_unknown);
25480c16b537SWarner Losh     zc->headerSize = ZSTD_frameHeaderSize_min;
25490c16b537SWarner Losh     return zc->headerSize;
25500c16b537SWarner Losh }
25510c16b537SWarner Losh 
25520c16b537SWarner Losh 
25530c16b537SWarner Losh static size_t ZSTD_getFrameParams(ZSTD_parameters* params, const void* src, size_t srcSize)
25540c16b537SWarner Losh {
25550c16b537SWarner Losh     U32 magicNumber;
25560c16b537SWarner Losh     if (srcSize < ZSTD_frameHeaderSize_min) return ZSTD_frameHeaderSize_max;
25570c16b537SWarner Losh     magicNumber = MEM_readLE32(src);
25580c16b537SWarner Losh     if (magicNumber != ZSTD_MAGICNUMBER) return ERROR(prefix_unknown);
25590c16b537SWarner Losh     memset(params, 0, sizeof(*params));
25600c16b537SWarner Losh     params->windowLog = (((const BYTE*)src)[4] & 15) + ZSTD_WINDOWLOG_ABSOLUTEMIN;
25610c16b537SWarner Losh     if ((((const BYTE*)src)[4] >> 4) != 0) return ERROR(frameParameter_unsupported);   /* reserved bits */
25620c16b537SWarner Losh     return 0;
25630c16b537SWarner Losh }
25640c16b537SWarner Losh 
25650c16b537SWarner Losh /** ZSTD_decodeFrameHeader_Part2
25660c16b537SWarner Losh *   decode the full Frame Header
25670c16b537SWarner Losh *   srcSize must be the size provided by ZSTD_decodeFrameHeader_Part1
25680c16b537SWarner Losh *   @return : 0, or an error code, which can be tested using ZSTD_isError() */
25690c16b537SWarner Losh static size_t ZSTD_decodeFrameHeader_Part2(ZSTD_DCtx* zc, const void* src, size_t srcSize)
25700c16b537SWarner Losh {
25710c16b537SWarner Losh     size_t result;
25720c16b537SWarner Losh     if (srcSize != zc->headerSize) return ERROR(srcSize_wrong);
25730c16b537SWarner Losh     result = ZSTD_getFrameParams(&(zc->params), src, srcSize);
25740c16b537SWarner Losh     if ((MEM_32bits()) && (zc->params.windowLog > 25)) return ERROR(frameParameter_unsupported);
25750c16b537SWarner Losh     return result;
25760c16b537SWarner Losh }
25770c16b537SWarner Losh 
25780c16b537SWarner Losh 
25790c16b537SWarner Losh static size_t ZSTD_getcBlockSize(const void* src, size_t srcSize, blockProperties_t* bpPtr)
25800c16b537SWarner Losh {
25810c16b537SWarner Losh     const BYTE* const in = (const BYTE* const)src;
25820c16b537SWarner Losh     BYTE headerFlags;
25830c16b537SWarner Losh     U32 cSize;
25840c16b537SWarner Losh 
25850c16b537SWarner Losh     if (srcSize < 3) return ERROR(srcSize_wrong);
25860c16b537SWarner Losh 
25870c16b537SWarner Losh     headerFlags = *in;
25880c16b537SWarner Losh     cSize = in[2] + (in[1]<<8) + ((in[0] & 7)<<16);
25890c16b537SWarner Losh 
25900c16b537SWarner Losh     bpPtr->blockType = (blockType_t)(headerFlags >> 6);
25910c16b537SWarner Losh     bpPtr->origSize = (bpPtr->blockType == bt_rle) ? cSize : 0;
25920c16b537SWarner Losh 
25930c16b537SWarner Losh     if (bpPtr->blockType == bt_end) return 0;
25940c16b537SWarner Losh     if (bpPtr->blockType == bt_rle) return 1;
25950c16b537SWarner Losh     return cSize;
25960c16b537SWarner Losh }
25970c16b537SWarner Losh 
25980c16b537SWarner Losh static size_t ZSTD_copyRawBlock(void* dst, size_t maxDstSize, const void* src, size_t srcSize)
25990c16b537SWarner Losh {
26000c16b537SWarner Losh     if (srcSize > maxDstSize) return ERROR(dstSize_tooSmall);
26010c16b537SWarner Losh     memcpy(dst, src, srcSize);
26020c16b537SWarner Losh     return srcSize;
26030c16b537SWarner Losh }
26040c16b537SWarner Losh 
26050c16b537SWarner Losh 
26060c16b537SWarner Losh /** ZSTD_decompressLiterals
26070c16b537SWarner Losh     @return : nb of bytes read from src, or an error code*/
26080c16b537SWarner Losh static size_t ZSTD_decompressLiterals(void* dst, size_t* maxDstSizePtr,
26090c16b537SWarner Losh                                 const void* src, size_t srcSize)
26100c16b537SWarner Losh {
26110c16b537SWarner Losh     const BYTE* ip = (const BYTE*)src;
26120c16b537SWarner Losh 
26130c16b537SWarner Losh     const size_t litSize = (MEM_readLE32(src) & 0x1FFFFF) >> 2;   /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */
26140c16b537SWarner Losh     const size_t litCSize = (MEM_readLE32(ip+2) & 0xFFFFFF) >> 5;   /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */
26150c16b537SWarner Losh 
26160c16b537SWarner Losh     if (litSize > *maxDstSizePtr) return ERROR(corruption_detected);
26170c16b537SWarner Losh     if (litCSize + 5 > srcSize) return ERROR(corruption_detected);
26180c16b537SWarner Losh 
26190c16b537SWarner Losh     if (HUF_isError(HUF_decompress(dst, litSize, ip+5, litCSize))) return ERROR(corruption_detected);
26200c16b537SWarner Losh 
26210c16b537SWarner Losh     *maxDstSizePtr = litSize;
26220c16b537SWarner Losh     return litCSize + 5;
26230c16b537SWarner Losh }
26240c16b537SWarner Losh 
26250c16b537SWarner Losh 
26260c16b537SWarner Losh /** ZSTD_decodeLiteralsBlock
26270c16b537SWarner Losh     @return : nb of bytes read from src (< srcSize ) */
26280c16b537SWarner Losh static size_t ZSTD_decodeLiteralsBlock(ZSTD_DCtx* dctx,
26290c16b537SWarner Losh                           const void* src, size_t srcSize)   /* note : srcSize < BLOCKSIZE */
26300c16b537SWarner Losh {
26310c16b537SWarner Losh     const BYTE* const istart = (const BYTE*) src;
26320c16b537SWarner Losh 
26330c16b537SWarner Losh     /* any compressed block with literals segment must be at least this size */
26340c16b537SWarner Losh     if (srcSize < MIN_CBLOCK_SIZE) return ERROR(corruption_detected);
26350c16b537SWarner Losh 
26360c16b537SWarner Losh     switch(*istart & 3)
26370c16b537SWarner Losh     {
26380c16b537SWarner Losh     /* compressed */
26390c16b537SWarner Losh     case 0:
26400c16b537SWarner Losh         {
26410c16b537SWarner Losh             size_t litSize = BLOCKSIZE;
26420c16b537SWarner Losh             const size_t readSize = ZSTD_decompressLiterals(dctx->litBuffer, &litSize, src, srcSize);
26430c16b537SWarner Losh             dctx->litPtr = dctx->litBuffer;
26440c16b537SWarner Losh             dctx->litSize = litSize;
26450c16b537SWarner Losh             memset(dctx->litBuffer + dctx->litSize, 0, 8);
26460c16b537SWarner Losh             return readSize;   /* works if it's an error too */
26470c16b537SWarner Losh         }
26480c16b537SWarner Losh     case IS_RAW:
26490c16b537SWarner Losh         {
26500c16b537SWarner Losh             const size_t litSize = (MEM_readLE32(istart) & 0xFFFFFF) >> 2;   /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */
26510c16b537SWarner Losh             if (litSize > srcSize-11)   /* risk of reading too far with wildcopy */
26520c16b537SWarner Losh             {
26530c16b537SWarner Losh                 if (litSize > srcSize-3) return ERROR(corruption_detected);
26540c16b537SWarner Losh                 memcpy(dctx->litBuffer, istart, litSize);
26550c16b537SWarner Losh                 dctx->litPtr = dctx->litBuffer;
26560c16b537SWarner Losh                 dctx->litSize = litSize;
26570c16b537SWarner Losh                 memset(dctx->litBuffer + dctx->litSize, 0, 8);
26580c16b537SWarner Losh                 return litSize+3;
26590c16b537SWarner Losh             }
26600c16b537SWarner Losh             /* direct reference into compressed stream */
26610c16b537SWarner Losh             dctx->litPtr = istart+3;
26620c16b537SWarner Losh             dctx->litSize = litSize;
26630c16b537SWarner Losh             return litSize+3;        }
26640c16b537SWarner Losh     case IS_RLE:
26650c16b537SWarner Losh         {
26660c16b537SWarner Losh             const size_t litSize = (MEM_readLE32(istart) & 0xFFFFFF) >> 2;   /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */
26670c16b537SWarner Losh             if (litSize > BLOCKSIZE) return ERROR(corruption_detected);
26680c16b537SWarner Losh             memset(dctx->litBuffer, istart[3], litSize + 8);
26690c16b537SWarner Losh             dctx->litPtr = dctx->litBuffer;
26700c16b537SWarner Losh             dctx->litSize = litSize;
26710c16b537SWarner Losh             return 4;
26720c16b537SWarner Losh         }
26730c16b537SWarner Losh     default:
26740c16b537SWarner Losh         return ERROR(corruption_detected);   /* forbidden nominal case */
26750c16b537SWarner Losh     }
26760c16b537SWarner Losh }
26770c16b537SWarner Losh 
26780c16b537SWarner Losh 
26790c16b537SWarner Losh static size_t ZSTD_decodeSeqHeaders(int* nbSeq, const BYTE** dumpsPtr, size_t* dumpsLengthPtr,
26800c16b537SWarner Losh                          FSE_DTable* DTableLL, FSE_DTable* DTableML, FSE_DTable* DTableOffb,
26810c16b537SWarner Losh                          const void* src, size_t srcSize)
26820c16b537SWarner Losh {
26830c16b537SWarner Losh     const BYTE* const istart = (const BYTE* const)src;
26840c16b537SWarner Losh     const BYTE* ip = istart;
26850c16b537SWarner Losh     const BYTE* const iend = istart + srcSize;
26860c16b537SWarner Losh     U32 LLtype, Offtype, MLtype;
26870c16b537SWarner Losh     U32 LLlog, Offlog, MLlog;
26880c16b537SWarner Losh     size_t dumpsLength;
26890c16b537SWarner Losh 
26900c16b537SWarner Losh     /* check */
26910c16b537SWarner Losh     if (srcSize < 5) return ERROR(srcSize_wrong);
26920c16b537SWarner Losh 
26930c16b537SWarner Losh     /* SeqHead */
26940c16b537SWarner Losh     *nbSeq = MEM_readLE16(ip); ip+=2;
26950c16b537SWarner Losh     LLtype  = *ip >> 6;
26960c16b537SWarner Losh     Offtype = (*ip >> 4) & 3;
26970c16b537SWarner Losh     MLtype  = (*ip >> 2) & 3;
26980c16b537SWarner Losh     if (*ip & 2)
26990c16b537SWarner Losh     {
27000c16b537SWarner Losh         dumpsLength  = ip[2];
27010c16b537SWarner Losh         dumpsLength += ip[1] << 8;
27020c16b537SWarner Losh         ip += 3;
27030c16b537SWarner Losh     }
27040c16b537SWarner Losh     else
27050c16b537SWarner Losh     {
27060c16b537SWarner Losh         dumpsLength  = ip[1];
27070c16b537SWarner Losh         dumpsLength += (ip[0] & 1) << 8;
27080c16b537SWarner Losh         ip += 2;
27090c16b537SWarner Losh     }
27100c16b537SWarner Losh     *dumpsPtr = ip;
27110c16b537SWarner Losh     ip += dumpsLength;
27120c16b537SWarner Losh     *dumpsLengthPtr = dumpsLength;
27130c16b537SWarner Losh 
27140c16b537SWarner Losh     /* check */
27150c16b537SWarner Losh     if (ip > iend-3) return ERROR(srcSize_wrong); /* min : all 3 are "raw", hence no header, but at least xxLog bits per type */
27160c16b537SWarner Losh 
27170c16b537SWarner Losh     /* sequences */
27180c16b537SWarner Losh     {
27190c16b537SWarner Losh         S16 norm[MaxML+1];    /* assumption : MaxML >= MaxLL >= MaxOff */
27200c16b537SWarner Losh         size_t headerSize;
27210c16b537SWarner Losh 
27220c16b537SWarner Losh         /* Build DTables */
27230c16b537SWarner Losh         switch(LLtype)
27240c16b537SWarner Losh         {
27250c16b537SWarner Losh         case bt_rle :
27260c16b537SWarner Losh             LLlog = 0;
27270c16b537SWarner Losh             FSE_buildDTable_rle(DTableLL, *ip++); break;
27280c16b537SWarner Losh         case bt_raw :
27290c16b537SWarner Losh             LLlog = LLbits;
27300c16b537SWarner Losh             FSE_buildDTable_raw(DTableLL, LLbits); break;
27310c16b537SWarner Losh         default :
27320c16b537SWarner Losh             {   U32 max = MaxLL;
27330c16b537SWarner Losh                 headerSize = FSE_readNCount(norm, &max, &LLlog, ip, iend-ip);
27340c16b537SWarner Losh                 if (FSE_isError(headerSize)) return ERROR(GENERIC);
27350c16b537SWarner Losh                 if (LLlog > LLFSELog) return ERROR(corruption_detected);
27360c16b537SWarner Losh                 ip += headerSize;
27370c16b537SWarner Losh                 FSE_buildDTable(DTableLL, norm, max, LLlog);
27380c16b537SWarner Losh         }   }
27390c16b537SWarner Losh 
27400c16b537SWarner Losh         switch(Offtype)
27410c16b537SWarner Losh         {
27420c16b537SWarner Losh         case bt_rle :
27430c16b537SWarner Losh             Offlog = 0;
27440c16b537SWarner Losh             if (ip > iend-2) return ERROR(srcSize_wrong);   /* min : "raw", hence no header, but at least xxLog bits */
27450c16b537SWarner Losh             FSE_buildDTable_rle(DTableOffb, *ip++ & MaxOff); /* if *ip > MaxOff, data is corrupted */
27460c16b537SWarner Losh             break;
27470c16b537SWarner Losh         case bt_raw :
27480c16b537SWarner Losh             Offlog = Offbits;
27490c16b537SWarner Losh             FSE_buildDTable_raw(DTableOffb, Offbits); break;
27500c16b537SWarner Losh         default :
27510c16b537SWarner Losh             {   U32 max = MaxOff;
27520c16b537SWarner Losh                 headerSize = FSE_readNCount(norm, &max, &Offlog, ip, iend-ip);
27530c16b537SWarner Losh                 if (FSE_isError(headerSize)) return ERROR(GENERIC);
27540c16b537SWarner Losh                 if (Offlog > OffFSELog) return ERROR(corruption_detected);
27550c16b537SWarner Losh                 ip += headerSize;
27560c16b537SWarner Losh                 FSE_buildDTable(DTableOffb, norm, max, Offlog);
27570c16b537SWarner Losh         }   }
27580c16b537SWarner Losh 
27590c16b537SWarner Losh         switch(MLtype)
27600c16b537SWarner Losh         {
27610c16b537SWarner Losh         case bt_rle :
27620c16b537SWarner Losh             MLlog = 0;
27630c16b537SWarner Losh             if (ip > iend-2) return ERROR(srcSize_wrong); /* min : "raw", hence no header, but at least xxLog bits */
27640c16b537SWarner Losh             FSE_buildDTable_rle(DTableML, *ip++); break;
27650c16b537SWarner Losh         case bt_raw :
27660c16b537SWarner Losh             MLlog = MLbits;
27670c16b537SWarner Losh             FSE_buildDTable_raw(DTableML, MLbits); break;
27680c16b537SWarner Losh         default :
27690c16b537SWarner Losh             {   U32 max = MaxML;
27700c16b537SWarner Losh                 headerSize = FSE_readNCount(norm, &max, &MLlog, ip, iend-ip);
27710c16b537SWarner Losh                 if (FSE_isError(headerSize)) return ERROR(GENERIC);
27720c16b537SWarner Losh                 if (MLlog > MLFSELog) return ERROR(corruption_detected);
27730c16b537SWarner Losh                 ip += headerSize;
27740c16b537SWarner Losh                 FSE_buildDTable(DTableML, norm, max, MLlog);
27750c16b537SWarner Losh     }   }   }
27760c16b537SWarner Losh 
27770c16b537SWarner Losh     return ip-istart;
27780c16b537SWarner Losh }
27790c16b537SWarner Losh 
27800c16b537SWarner Losh 
27810c16b537SWarner Losh typedef struct {
27820c16b537SWarner Losh     size_t litLength;
27830c16b537SWarner Losh     size_t offset;
27840c16b537SWarner Losh     size_t matchLength;
27850c16b537SWarner Losh } seq_t;
27860c16b537SWarner Losh 
27870c16b537SWarner Losh typedef struct {
27880c16b537SWarner Losh     BIT_DStream_t DStream;
27890c16b537SWarner Losh     FSE_DState_t stateLL;
27900c16b537SWarner Losh     FSE_DState_t stateOffb;
27910c16b537SWarner Losh     FSE_DState_t stateML;
27920c16b537SWarner Losh     size_t prevOffset;
27930c16b537SWarner Losh     const BYTE* dumps;
27940c16b537SWarner Losh     const BYTE* dumpsEnd;
27950c16b537SWarner Losh } seqState_t;
27960c16b537SWarner Losh 
27970c16b537SWarner Losh 
27980c16b537SWarner Losh static void ZSTD_decodeSequence(seq_t* seq, seqState_t* seqState)
27990c16b537SWarner Losh {
28000c16b537SWarner Losh     size_t litLength;
28010c16b537SWarner Losh     size_t prevOffset;
28020c16b537SWarner Losh     size_t offset;
28030c16b537SWarner Losh     size_t matchLength;
28040c16b537SWarner Losh     const BYTE* dumps = seqState->dumps;
28050c16b537SWarner Losh     const BYTE* const de = seqState->dumpsEnd;
28060c16b537SWarner Losh 
28070c16b537SWarner Losh     /* Literal length */
28080c16b537SWarner Losh     litLength = FSE_decodeSymbol(&(seqState->stateLL), &(seqState->DStream));
28090c16b537SWarner Losh     prevOffset = litLength ? seq->offset : seqState->prevOffset;
28100c16b537SWarner Losh     if (litLength == MaxLL) {
28110c16b537SWarner Losh         U32 add = *dumps++;
28120c16b537SWarner Losh         if (add < 255) litLength += add;
28130c16b537SWarner Losh         else {
28140c16b537SWarner Losh             litLength = dumps[0] + (dumps[1]<<8) + (dumps[2]<<16);
28150c16b537SWarner Losh             dumps += 3;
28160c16b537SWarner Losh         }
28170c16b537SWarner Losh         if (dumps > de) { litLength = MaxLL+255; }  /* late correction, to avoid using uninitialized memory */
28180c16b537SWarner Losh         if (dumps >= de) { dumps = de-1; }  /* late correction, to avoid read overflow (data is now corrupted anyway) */
28190c16b537SWarner Losh     }
28200c16b537SWarner Losh 
28210c16b537SWarner Losh     /* Offset */
28220c16b537SWarner Losh     {   static const U32 offsetPrefix[MaxOff+1] = {
28230c16b537SWarner Losh                 1 /*fake*/, 1, 2, 4, 8, 16, 32, 64, 128, 256,
28240c16b537SWarner Losh                 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144,
28250c16b537SWarner Losh                 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, /*fake*/ 1, 1, 1, 1, 1 };
28260c16b537SWarner Losh         U32 offsetCode, nbBits;
28270c16b537SWarner Losh         offsetCode = FSE_decodeSymbol(&(seqState->stateOffb), &(seqState->DStream));   /* <= maxOff, by table construction */
28280c16b537SWarner Losh         if (MEM_32bits()) BIT_reloadDStream(&(seqState->DStream));
28290c16b537SWarner Losh         nbBits = offsetCode - 1;
28300c16b537SWarner Losh         if (offsetCode==0) nbBits = 0;   /* cmove */
28310c16b537SWarner Losh         offset = offsetPrefix[offsetCode] + BIT_readBits(&(seqState->DStream), nbBits);
28320c16b537SWarner Losh         if (MEM_32bits()) BIT_reloadDStream(&(seqState->DStream));
28330c16b537SWarner Losh         if (offsetCode==0) offset = prevOffset;   /* cmove */
28340c16b537SWarner Losh         if (offsetCode | !litLength) seqState->prevOffset = seq->offset;   /* cmove */
28350c16b537SWarner Losh     }
28360c16b537SWarner Losh 
28370c16b537SWarner Losh     /* MatchLength */
28380c16b537SWarner Losh     matchLength = FSE_decodeSymbol(&(seqState->stateML), &(seqState->DStream));
28390c16b537SWarner Losh     if (matchLength == MaxML) {
28400c16b537SWarner Losh         U32 add = *dumps++;
28410c16b537SWarner Losh         if (add < 255) matchLength += add;
28420c16b537SWarner Losh         else {
28430c16b537SWarner Losh             matchLength = dumps[0] + (dumps[1]<<8) + (dumps[2]<<16);
28440c16b537SWarner Losh             dumps += 3;
28450c16b537SWarner Losh         }
28460c16b537SWarner Losh         if (dumps > de) { matchLength = MaxML+255; }  /* late correction, to avoid using uninitialized memory */
28470c16b537SWarner Losh         if (dumps >= de) { dumps = de-1; }  /* late correction, to avoid read overflow (data is now corrupted anyway) */
28480c16b537SWarner Losh     }
28490c16b537SWarner Losh     matchLength += MINMATCH;
28500c16b537SWarner Losh 
28510c16b537SWarner Losh     /* save result */
28520c16b537SWarner Losh     seq->litLength = litLength;
28530c16b537SWarner Losh     seq->offset = offset;
28540c16b537SWarner Losh     seq->matchLength = matchLength;
28550c16b537SWarner Losh     seqState->dumps = dumps;
28560c16b537SWarner Losh }
28570c16b537SWarner Losh 
28580c16b537SWarner Losh 
28590c16b537SWarner Losh static size_t ZSTD_execSequence(BYTE* op,
28600c16b537SWarner Losh                                 BYTE* const oend, seq_t sequence,
28610c16b537SWarner Losh                                 const BYTE** litPtr, const BYTE* const litLimit,
28620c16b537SWarner Losh                                 const BYTE* const base, const BYTE* const vBase, const BYTE* const dictEnd)
28630c16b537SWarner Losh {
28640c16b537SWarner Losh     static const int dec32table[] = { 0, 1, 2, 1, 4, 4, 4, 4 };   /* added */
2865*2b9c00cbSConrad Meyer     static const int dec64table[] = { 8, 8, 8, 7, 8, 9,10,11 };   /* subtracted */
28660c16b537SWarner Losh     BYTE* const oLitEnd = op + sequence.litLength;
28670c16b537SWarner Losh     const size_t sequenceLength = sequence.litLength + sequence.matchLength;
28680c16b537SWarner Losh     BYTE* const oMatchEnd = op + sequenceLength;   /* risk : address space overflow (32-bits) */
28690c16b537SWarner Losh     BYTE* const oend_8 = oend-8;
28700c16b537SWarner Losh     const BYTE* const litEnd = *litPtr + sequence.litLength;
28710c16b537SWarner Losh     const BYTE* match = oLitEnd - sequence.offset;
28720c16b537SWarner Losh 
28730c16b537SWarner Losh     /* check */
28740c16b537SWarner Losh     if (oLitEnd > oend_8) return ERROR(dstSize_tooSmall);   /* last match must start at a minimum distance of 8 from oend */
28750c16b537SWarner Losh     if (oMatchEnd > oend) return ERROR(dstSize_tooSmall);   /* overwrite beyond dst buffer */
28760c16b537SWarner Losh     if (litEnd > litLimit) return ERROR(corruption_detected);   /* risk read beyond lit buffer */
28770c16b537SWarner Losh 
28780c16b537SWarner Losh     /* copy Literals */
28790c16b537SWarner Losh     ZSTD_wildcopy(op, *litPtr, sequence.litLength);   /* note : oLitEnd <= oend-8 : no risk of overwrite beyond oend */
28800c16b537SWarner Losh     op = oLitEnd;
28810c16b537SWarner Losh     *litPtr = litEnd;   /* update for next sequence */
28820c16b537SWarner Losh 
28830c16b537SWarner Losh     /* copy Match */
28840c16b537SWarner Losh     if (sequence.offset > (size_t)(oLitEnd - base))
28850c16b537SWarner Losh     {
28860c16b537SWarner Losh         /* offset beyond prefix */
28870c16b537SWarner Losh         if (sequence.offset > (size_t)(oLitEnd - vBase))
28880c16b537SWarner Losh             return ERROR(corruption_detected);
28890c16b537SWarner Losh         match = dictEnd - (base-match);
28900c16b537SWarner Losh         if (match + sequence.matchLength <= dictEnd)
28910c16b537SWarner Losh         {
28920c16b537SWarner Losh             memmove(oLitEnd, match, sequence.matchLength);
28930c16b537SWarner Losh             return sequenceLength;
28940c16b537SWarner Losh         }
28950c16b537SWarner Losh         /* span extDict & currentPrefixSegment */
28960c16b537SWarner Losh         {
28970c16b537SWarner Losh             size_t length1 = dictEnd - match;
28980c16b537SWarner Losh             memmove(oLitEnd, match, length1);
28990c16b537SWarner Losh             op = oLitEnd + length1;
29000c16b537SWarner Losh             sequence.matchLength -= length1;
29010c16b537SWarner Losh             match = base;
29020c16b537SWarner Losh             if (op > oend_8 || sequence.matchLength < MINMATCH) {
29030c16b537SWarner Losh               while (op < oMatchEnd) *op++ = *match++;
29040c16b537SWarner Losh               return sequenceLength;
29050c16b537SWarner Losh             }
29060c16b537SWarner Losh         }
29070c16b537SWarner Losh     }
29080c16b537SWarner Losh     /* Requirement: op <= oend_8 */
29090c16b537SWarner Losh 
29100c16b537SWarner Losh     /* match within prefix */
29110c16b537SWarner Losh     if (sequence.offset < 8) {
29120c16b537SWarner Losh         /* close range match, overlap */
29130c16b537SWarner Losh         const int sub2 = dec64table[sequence.offset];
29140c16b537SWarner Losh         op[0] = match[0];
29150c16b537SWarner Losh         op[1] = match[1];
29160c16b537SWarner Losh         op[2] = match[2];
29170c16b537SWarner Losh         op[3] = match[3];
29180c16b537SWarner Losh         match += dec32table[sequence.offset];
29190c16b537SWarner Losh         ZSTD_copy4(op+4, match);
29200c16b537SWarner Losh         match -= sub2;
29210c16b537SWarner Losh     } else {
29220c16b537SWarner Losh         ZSTD_copy8(op, match);
29230c16b537SWarner Losh     }
29240c16b537SWarner Losh     op += 8; match += 8;
29250c16b537SWarner Losh 
29260c16b537SWarner Losh     if (oMatchEnd > oend-(16-MINMATCH))
29270c16b537SWarner Losh     {
29280c16b537SWarner Losh         if (op < oend_8)
29290c16b537SWarner Losh         {
29300c16b537SWarner Losh             ZSTD_wildcopy(op, match, oend_8 - op);
29310c16b537SWarner Losh             match += oend_8 - op;
29320c16b537SWarner Losh             op = oend_8;
29330c16b537SWarner Losh         }
29340c16b537SWarner Losh         while (op < oMatchEnd) *op++ = *match++;
29350c16b537SWarner Losh     }
29360c16b537SWarner Losh     else
29370c16b537SWarner Losh     {
29380f743729SConrad Meyer         ZSTD_wildcopy(op, match, (ptrdiff_t)sequence.matchLength-8);   /* works even if matchLength < 8, but must be signed */
29390c16b537SWarner Losh     }
29400c16b537SWarner Losh     return sequenceLength;
29410c16b537SWarner Losh }
29420c16b537SWarner Losh 
29430c16b537SWarner Losh 
29440c16b537SWarner Losh static size_t ZSTD_decompressSequences(
29450c16b537SWarner Losh                                ZSTD_DCtx* dctx,
29460c16b537SWarner Losh                                void* dst, size_t maxDstSize,
29470c16b537SWarner Losh                          const void* seqStart, size_t seqSize)
29480c16b537SWarner Losh {
29490c16b537SWarner Losh     const BYTE* ip = (const BYTE*)seqStart;
29500c16b537SWarner Losh     const BYTE* const iend = ip + seqSize;
29510c16b537SWarner Losh     BYTE* const ostart = (BYTE* const)dst;
29520c16b537SWarner Losh     BYTE* op = ostart;
29530c16b537SWarner Losh     BYTE* const oend = ostart + maxDstSize;
29540c16b537SWarner Losh     size_t errorCode, dumpsLength;
29550c16b537SWarner Losh     const BYTE* litPtr = dctx->litPtr;
29560c16b537SWarner Losh     const BYTE* const litEnd = litPtr + dctx->litSize;
29570c16b537SWarner Losh     int nbSeq;
29580c16b537SWarner Losh     const BYTE* dumps;
29590c16b537SWarner Losh     U32* DTableLL = dctx->LLTable;
29600c16b537SWarner Losh     U32* DTableML = dctx->MLTable;
29610c16b537SWarner Losh     U32* DTableOffb = dctx->OffTable;
29620c16b537SWarner Losh     const BYTE* const base = (const BYTE*) (dctx->base);
29630c16b537SWarner Losh     const BYTE* const vBase = (const BYTE*) (dctx->vBase);
29640c16b537SWarner Losh     const BYTE* const dictEnd = (const BYTE*) (dctx->dictEnd);
29650c16b537SWarner Losh 
29660c16b537SWarner Losh     /* Build Decoding Tables */
29670c16b537SWarner Losh     errorCode = ZSTD_decodeSeqHeaders(&nbSeq, &dumps, &dumpsLength,
29680c16b537SWarner Losh                                       DTableLL, DTableML, DTableOffb,
29690c16b537SWarner Losh                                       ip, iend-ip);
29700c16b537SWarner Losh     if (ZSTD_isError(errorCode)) return errorCode;
29710c16b537SWarner Losh     ip += errorCode;
29720c16b537SWarner Losh 
29730c16b537SWarner Losh     /* Regen sequences */
29740c16b537SWarner Losh     {
29750c16b537SWarner Losh         seq_t sequence;
29760c16b537SWarner Losh         seqState_t seqState;
29770c16b537SWarner Losh 
29780c16b537SWarner Losh         memset(&sequence, 0, sizeof(sequence));
29790c16b537SWarner Losh         sequence.offset = 4;
29800c16b537SWarner Losh         seqState.dumps = dumps;
29810c16b537SWarner Losh         seqState.dumpsEnd = dumps + dumpsLength;
29820c16b537SWarner Losh         seqState.prevOffset = 4;
29830c16b537SWarner Losh         errorCode = BIT_initDStream(&(seqState.DStream), ip, iend-ip);
29840c16b537SWarner Losh         if (ERR_isError(errorCode)) return ERROR(corruption_detected);
29850c16b537SWarner Losh         FSE_initDState(&(seqState.stateLL), &(seqState.DStream), DTableLL);
29860c16b537SWarner Losh         FSE_initDState(&(seqState.stateOffb), &(seqState.DStream), DTableOffb);
29870c16b537SWarner Losh         FSE_initDState(&(seqState.stateML), &(seqState.DStream), DTableML);
29880c16b537SWarner Losh 
29890c16b537SWarner Losh         for ( ; (BIT_reloadDStream(&(seqState.DStream)) <= BIT_DStream_completed) && nbSeq ; )
29900c16b537SWarner Losh         {
29910c16b537SWarner Losh             size_t oneSeqSize;
29920c16b537SWarner Losh             nbSeq--;
29930c16b537SWarner Losh             ZSTD_decodeSequence(&sequence, &seqState);
29940c16b537SWarner Losh             oneSeqSize = ZSTD_execSequence(op, oend, sequence, &litPtr, litEnd, base, vBase, dictEnd);
29950c16b537SWarner Losh             if (ZSTD_isError(oneSeqSize)) return oneSeqSize;
29960c16b537SWarner Losh             op += oneSeqSize;
29970c16b537SWarner Losh         }
29980c16b537SWarner Losh 
29990c16b537SWarner Losh         /* check if reached exact end */
30000c16b537SWarner Losh         if ( !BIT_endOfDStream(&(seqState.DStream)) ) return ERROR(corruption_detected);   /* DStream should be entirely and exactly consumed; otherwise data is corrupted */
30010c16b537SWarner Losh 
30020c16b537SWarner Losh         /* last literal segment */
30030c16b537SWarner Losh         {
30040c16b537SWarner Losh             size_t lastLLSize = litEnd - litPtr;
30050c16b537SWarner Losh             if (litPtr > litEnd) return ERROR(corruption_detected);
30060c16b537SWarner Losh             if (op+lastLLSize > oend) return ERROR(dstSize_tooSmall);
30070c16b537SWarner Losh             if (op != litPtr) memcpy(op, litPtr, lastLLSize);
30080c16b537SWarner Losh             op += lastLLSize;
30090c16b537SWarner Losh         }
30100c16b537SWarner Losh     }
30110c16b537SWarner Losh 
30120c16b537SWarner Losh     return op-ostart;
30130c16b537SWarner Losh }
30140c16b537SWarner Losh 
30150c16b537SWarner Losh 
30160c16b537SWarner Losh static void ZSTD_checkContinuity(ZSTD_DCtx* dctx, const void* dst)
30170c16b537SWarner Losh {
30180c16b537SWarner Losh     if (dst != dctx->previousDstEnd)   /* not contiguous */
30190c16b537SWarner Losh     {
30200c16b537SWarner Losh         dctx->dictEnd = dctx->previousDstEnd;
30210c16b537SWarner Losh         dctx->vBase = (const char*)dst - ((const char*)(dctx->previousDstEnd) - (const char*)(dctx->base));
30220c16b537SWarner Losh         dctx->base = dst;
30230c16b537SWarner Losh         dctx->previousDstEnd = dst;
30240c16b537SWarner Losh     }
30250c16b537SWarner Losh }
30260c16b537SWarner Losh 
30270c16b537SWarner Losh 
30280c16b537SWarner Losh static size_t ZSTD_decompressBlock_internal(ZSTD_DCtx* dctx,
30290c16b537SWarner Losh                             void* dst, size_t maxDstSize,
30300c16b537SWarner Losh                       const void* src, size_t srcSize)
30310c16b537SWarner Losh {
30320c16b537SWarner Losh     /* blockType == blockCompressed */
30330c16b537SWarner Losh     const BYTE* ip = (const BYTE*)src;
30340c16b537SWarner Losh 
30350c16b537SWarner Losh     /* Decode literals sub-block */
30360c16b537SWarner Losh     size_t litCSize = ZSTD_decodeLiteralsBlock(dctx, src, srcSize);
30370c16b537SWarner Losh     if (ZSTD_isError(litCSize)) return litCSize;
30380c16b537SWarner Losh     ip += litCSize;
30390c16b537SWarner Losh     srcSize -= litCSize;
30400c16b537SWarner Losh 
30410c16b537SWarner Losh     return ZSTD_decompressSequences(dctx, dst, maxDstSize, ip, srcSize);
30420c16b537SWarner Losh }
30430c16b537SWarner Losh 
30440c16b537SWarner Losh 
30450c16b537SWarner Losh static size_t ZSTD_decompress_usingDict(ZSTD_DCtx* ctx,
30460c16b537SWarner Losh                                  void* dst, size_t maxDstSize,
30470c16b537SWarner Losh                                  const void* src, size_t srcSize,
30480c16b537SWarner Losh                                  const void* dict, size_t dictSize)
30490c16b537SWarner Losh {
30500c16b537SWarner Losh     const BYTE* ip = (const BYTE*)src;
30510c16b537SWarner Losh     const BYTE* iend = ip + srcSize;
30520c16b537SWarner Losh     BYTE* const ostart = (BYTE* const)dst;
30530c16b537SWarner Losh     BYTE* op = ostart;
30540c16b537SWarner Losh     BYTE* const oend = ostart + maxDstSize;
30550c16b537SWarner Losh     size_t remainingSize = srcSize;
30560c16b537SWarner Losh     blockProperties_t blockProperties;
30570c16b537SWarner Losh 
30580c16b537SWarner Losh     /* init */
30590c16b537SWarner Losh     ZSTD_resetDCtx(ctx);
30600c16b537SWarner Losh     if (dict)
30610c16b537SWarner Losh     {
30620c16b537SWarner Losh         ZSTD_decompress_insertDictionary(ctx, dict, dictSize);
30630c16b537SWarner Losh         ctx->dictEnd = ctx->previousDstEnd;
30640c16b537SWarner Losh         ctx->vBase = (const char*)dst - ((const char*)(ctx->previousDstEnd) - (const char*)(ctx->base));
30650c16b537SWarner Losh         ctx->base = dst;
30660c16b537SWarner Losh     }
30670c16b537SWarner Losh     else
30680c16b537SWarner Losh     {
30690c16b537SWarner Losh         ctx->vBase = ctx->base = ctx->dictEnd = dst;
30700c16b537SWarner Losh     }
30710c16b537SWarner Losh 
30720c16b537SWarner Losh     /* Frame Header */
30730c16b537SWarner Losh     {
30740c16b537SWarner Losh         size_t frameHeaderSize;
30750c16b537SWarner Losh         if (srcSize < ZSTD_frameHeaderSize_min+ZSTD_blockHeaderSize) return ERROR(srcSize_wrong);
30760c16b537SWarner Losh         frameHeaderSize = ZSTD_decodeFrameHeader_Part1(ctx, src, ZSTD_frameHeaderSize_min);
30770c16b537SWarner Losh         if (ZSTD_isError(frameHeaderSize)) return frameHeaderSize;
30780c16b537SWarner Losh         if (srcSize < frameHeaderSize+ZSTD_blockHeaderSize) return ERROR(srcSize_wrong);
30790c16b537SWarner Losh         ip += frameHeaderSize; remainingSize -= frameHeaderSize;
30800c16b537SWarner Losh         frameHeaderSize = ZSTD_decodeFrameHeader_Part2(ctx, src, frameHeaderSize);
30810c16b537SWarner Losh         if (ZSTD_isError(frameHeaderSize)) return frameHeaderSize;
30820c16b537SWarner Losh     }
30830c16b537SWarner Losh 
30840c16b537SWarner Losh     /* Loop on each block */
30850c16b537SWarner Losh     while (1)
30860c16b537SWarner Losh     {
30870c16b537SWarner Losh         size_t decodedSize=0;
30880c16b537SWarner Losh         size_t cBlockSize = ZSTD_getcBlockSize(ip, iend-ip, &blockProperties);
30890c16b537SWarner Losh         if (ZSTD_isError(cBlockSize)) return cBlockSize;
30900c16b537SWarner Losh 
30910c16b537SWarner Losh         ip += ZSTD_blockHeaderSize;
30920c16b537SWarner Losh         remainingSize -= ZSTD_blockHeaderSize;
30930c16b537SWarner Losh         if (cBlockSize > remainingSize) return ERROR(srcSize_wrong);
30940c16b537SWarner Losh 
30950c16b537SWarner Losh         switch(blockProperties.blockType)
30960c16b537SWarner Losh         {
30970c16b537SWarner Losh         case bt_compressed:
30980c16b537SWarner Losh             decodedSize = ZSTD_decompressBlock_internal(ctx, op, oend-op, ip, cBlockSize);
30990c16b537SWarner Losh             break;
31000c16b537SWarner Losh         case bt_raw :
31010c16b537SWarner Losh             decodedSize = ZSTD_copyRawBlock(op, oend-op, ip, cBlockSize);
31020c16b537SWarner Losh             break;
31030c16b537SWarner Losh         case bt_rle :
31040c16b537SWarner Losh             return ERROR(GENERIC);   /* not yet supported */
31050c16b537SWarner Losh             break;
31060c16b537SWarner Losh         case bt_end :
31070c16b537SWarner Losh             /* end of frame */
31080c16b537SWarner Losh             if (remainingSize) return ERROR(srcSize_wrong);
31090c16b537SWarner Losh             break;
31100c16b537SWarner Losh         default:
31110c16b537SWarner Losh             return ERROR(GENERIC);   /* impossible */
31120c16b537SWarner Losh         }
31130c16b537SWarner Losh         if (cBlockSize == 0) break;   /* bt_end */
31140c16b537SWarner Losh 
31150c16b537SWarner Losh         if (ZSTD_isError(decodedSize)) return decodedSize;
31160c16b537SWarner Losh         op += decodedSize;
31170c16b537SWarner Losh         ip += cBlockSize;
31180c16b537SWarner Losh         remainingSize -= cBlockSize;
31190c16b537SWarner Losh     }
31200c16b537SWarner Losh 
31210c16b537SWarner Losh     return op-ostart;
31220c16b537SWarner Losh }
31230c16b537SWarner Losh 
3124*2b9c00cbSConrad Meyer /* ZSTD_errorFrameSizeInfoLegacy() :
3125*2b9c00cbSConrad Meyer    assumes `cSize` and `dBound` are _not_ NULL */
3126*2b9c00cbSConrad Meyer static void ZSTD_errorFrameSizeInfoLegacy(size_t* cSize, unsigned long long* dBound, size_t ret)
3127*2b9c00cbSConrad Meyer {
3128*2b9c00cbSConrad Meyer     *cSize = ret;
3129*2b9c00cbSConrad Meyer     *dBound = ZSTD_CONTENTSIZE_ERROR;
3130*2b9c00cbSConrad Meyer }
3131*2b9c00cbSConrad Meyer 
3132*2b9c00cbSConrad Meyer void ZSTDv04_findFrameSizeInfoLegacy(const void *src, size_t srcSize, size_t* cSize, unsigned long long* dBound)
31330c16b537SWarner Losh {
31340c16b537SWarner Losh     const BYTE* ip = (const BYTE*)src;
31350c16b537SWarner Losh     size_t remainingSize = srcSize;
3136*2b9c00cbSConrad Meyer     size_t nbBlocks = 0;
31370c16b537SWarner Losh     blockProperties_t blockProperties;
31380c16b537SWarner Losh 
31390c16b537SWarner Losh     /* Frame Header */
3140*2b9c00cbSConrad Meyer     if (srcSize < ZSTD_frameHeaderSize_min) {
3141*2b9c00cbSConrad Meyer         ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(srcSize_wrong));
3142*2b9c00cbSConrad Meyer         return;
3143*2b9c00cbSConrad Meyer     }
3144*2b9c00cbSConrad Meyer     if (MEM_readLE32(src) != ZSTD_MAGICNUMBER) {
3145*2b9c00cbSConrad Meyer         ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(prefix_unknown));
3146*2b9c00cbSConrad Meyer         return;
3147*2b9c00cbSConrad Meyer     }
31480c16b537SWarner Losh     ip += ZSTD_frameHeaderSize_min; remainingSize -= ZSTD_frameHeaderSize_min;
31490c16b537SWarner Losh 
31500c16b537SWarner Losh     /* Loop on each block */
31510c16b537SWarner Losh     while (1)
31520c16b537SWarner Losh     {
31530c16b537SWarner Losh         size_t cBlockSize = ZSTD_getcBlockSize(ip, remainingSize, &blockProperties);
3154*2b9c00cbSConrad Meyer         if (ZSTD_isError(cBlockSize)) {
3155*2b9c00cbSConrad Meyer             ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, cBlockSize);
3156*2b9c00cbSConrad Meyer             return;
3157*2b9c00cbSConrad Meyer         }
31580c16b537SWarner Losh 
31590c16b537SWarner Losh         ip += ZSTD_blockHeaderSize;
31600c16b537SWarner Losh         remainingSize -= ZSTD_blockHeaderSize;
3161*2b9c00cbSConrad Meyer         if (cBlockSize > remainingSize) {
3162*2b9c00cbSConrad Meyer             ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(srcSize_wrong));
3163*2b9c00cbSConrad Meyer             return;
3164*2b9c00cbSConrad Meyer         }
31650c16b537SWarner Losh 
31660c16b537SWarner Losh         if (cBlockSize == 0) break;   /* bt_end */
31670c16b537SWarner Losh 
31680c16b537SWarner Losh         ip += cBlockSize;
31690c16b537SWarner Losh         remainingSize -= cBlockSize;
3170*2b9c00cbSConrad Meyer         nbBlocks++;
31710c16b537SWarner Losh     }
31720c16b537SWarner Losh 
3173*2b9c00cbSConrad Meyer     *cSize = ip - (const BYTE*)src;
3174*2b9c00cbSConrad Meyer     *dBound = nbBlocks * BLOCKSIZE;
31750c16b537SWarner Losh }
31760c16b537SWarner Losh 
31770c16b537SWarner Losh /* ******************************
31780c16b537SWarner Losh *  Streaming Decompression API
31790c16b537SWarner Losh ********************************/
31800c16b537SWarner Losh static size_t ZSTD_nextSrcSizeToDecompress(ZSTD_DCtx* dctx)
31810c16b537SWarner Losh {
31820c16b537SWarner Losh     return dctx->expected;
31830c16b537SWarner Losh }
31840c16b537SWarner Losh 
31850c16b537SWarner Losh static size_t ZSTD_decompressContinue(ZSTD_DCtx* ctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize)
31860c16b537SWarner Losh {
31870c16b537SWarner Losh     /* Sanity check */
31880c16b537SWarner Losh     if (srcSize != ctx->expected) return ERROR(srcSize_wrong);
31890c16b537SWarner Losh     ZSTD_checkContinuity(ctx, dst);
31900c16b537SWarner Losh 
31910c16b537SWarner Losh     /* Decompress : frame header; part 1 */
31920c16b537SWarner Losh     switch (ctx->stage)
31930c16b537SWarner Losh     {
31940c16b537SWarner Losh     case ZSTDds_getFrameHeaderSize :
31950c16b537SWarner Losh         /* get frame header size */
31960c16b537SWarner Losh         if (srcSize != ZSTD_frameHeaderSize_min) return ERROR(srcSize_wrong);   /* impossible */
31970c16b537SWarner Losh         ctx->headerSize = ZSTD_decodeFrameHeader_Part1(ctx, src, ZSTD_frameHeaderSize_min);
31980c16b537SWarner Losh         if (ZSTD_isError(ctx->headerSize)) return ctx->headerSize;
31990c16b537SWarner Losh         memcpy(ctx->headerBuffer, src, ZSTD_frameHeaderSize_min);
32000c16b537SWarner Losh         if (ctx->headerSize > ZSTD_frameHeaderSize_min) return ERROR(GENERIC);   /* impossible */
32010c16b537SWarner Losh         ctx->expected = 0;   /* not necessary to copy more */
32020c16b537SWarner Losh         /* fallthrough */
32030c16b537SWarner Losh     case ZSTDds_decodeFrameHeader:
32040c16b537SWarner Losh         /* get frame header */
32050c16b537SWarner Losh         {   size_t const result = ZSTD_decodeFrameHeader_Part2(ctx, ctx->headerBuffer, ctx->headerSize);
32060c16b537SWarner Losh             if (ZSTD_isError(result)) return result;
32070c16b537SWarner Losh             ctx->expected = ZSTD_blockHeaderSize;
32080c16b537SWarner Losh             ctx->stage = ZSTDds_decodeBlockHeader;
32090c16b537SWarner Losh             return 0;
32100c16b537SWarner Losh         }
32110c16b537SWarner Losh     case ZSTDds_decodeBlockHeader:
32120c16b537SWarner Losh         /* Decode block header */
32130c16b537SWarner Losh         {   blockProperties_t bp;
32140c16b537SWarner Losh             size_t const blockSize = ZSTD_getcBlockSize(src, ZSTD_blockHeaderSize, &bp);
32150c16b537SWarner Losh             if (ZSTD_isError(blockSize)) return blockSize;
32160c16b537SWarner Losh             if (bp.blockType == bt_end)
32170c16b537SWarner Losh             {
32180c16b537SWarner Losh                 ctx->expected = 0;
32190c16b537SWarner Losh                 ctx->stage = ZSTDds_getFrameHeaderSize;
32200c16b537SWarner Losh             }
32210c16b537SWarner Losh             else
32220c16b537SWarner Losh             {
32230c16b537SWarner Losh                 ctx->expected = blockSize;
32240c16b537SWarner Losh                 ctx->bType = bp.blockType;
32250c16b537SWarner Losh                 ctx->stage = ZSTDds_decompressBlock;
32260c16b537SWarner Losh             }
32270c16b537SWarner Losh             return 0;
32280c16b537SWarner Losh         }
32290c16b537SWarner Losh     case ZSTDds_decompressBlock:
32300c16b537SWarner Losh         {
32310c16b537SWarner Losh             /* Decompress : block content */
32320c16b537SWarner Losh             size_t rSize;
32330c16b537SWarner Losh             switch(ctx->bType)
32340c16b537SWarner Losh             {
32350c16b537SWarner Losh             case bt_compressed:
32360c16b537SWarner Losh                 rSize = ZSTD_decompressBlock_internal(ctx, dst, maxDstSize, src, srcSize);
32370c16b537SWarner Losh                 break;
32380c16b537SWarner Losh             case bt_raw :
32390c16b537SWarner Losh                 rSize = ZSTD_copyRawBlock(dst, maxDstSize, src, srcSize);
32400c16b537SWarner Losh                 break;
32410c16b537SWarner Losh             case bt_rle :
32420c16b537SWarner Losh                 return ERROR(GENERIC);   /* not yet handled */
32430c16b537SWarner Losh                 break;
32440c16b537SWarner Losh             case bt_end :   /* should never happen (filtered at phase 1) */
32450c16b537SWarner Losh                 rSize = 0;
32460c16b537SWarner Losh                 break;
32470c16b537SWarner Losh             default:
32480c16b537SWarner Losh                 return ERROR(GENERIC);
32490c16b537SWarner Losh             }
32500c16b537SWarner Losh             ctx->stage = ZSTDds_decodeBlockHeader;
32510c16b537SWarner Losh             ctx->expected = ZSTD_blockHeaderSize;
32520c16b537SWarner Losh             ctx->previousDstEnd = (char*)dst + rSize;
32530c16b537SWarner Losh             return rSize;
32540c16b537SWarner Losh         }
32550c16b537SWarner Losh     default:
32560c16b537SWarner Losh         return ERROR(GENERIC);   /* impossible */
32570c16b537SWarner Losh     }
32580c16b537SWarner Losh }
32590c16b537SWarner Losh 
32600c16b537SWarner Losh 
32610c16b537SWarner Losh static void ZSTD_decompress_insertDictionary(ZSTD_DCtx* ctx, const void* dict, size_t dictSize)
32620c16b537SWarner Losh {
32630c16b537SWarner Losh     ctx->dictEnd = ctx->previousDstEnd;
32640c16b537SWarner Losh     ctx->vBase = (const char*)dict - ((const char*)(ctx->previousDstEnd) - (const char*)(ctx->base));
32650c16b537SWarner Losh     ctx->base = dict;
32660c16b537SWarner Losh     ctx->previousDstEnd = (const char*)dict + dictSize;
32670c16b537SWarner Losh }
32680c16b537SWarner Losh 
32690c16b537SWarner Losh 
32700c16b537SWarner Losh 
32710c16b537SWarner Losh /*
32720c16b537SWarner Losh     Buffered version of Zstd compression library
32730c16b537SWarner Losh     Copyright (C) 2015, Yann Collet.
32740c16b537SWarner Losh 
32750c16b537SWarner Losh     BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
32760c16b537SWarner Losh 
32770c16b537SWarner Losh     Redistribution and use in source and binary forms, with or without
32780c16b537SWarner Losh     modification, are permitted provided that the following conditions are
32790c16b537SWarner Losh     met:
32800c16b537SWarner Losh     * Redistributions of source code must retain the above copyright
32810c16b537SWarner Losh     notice, this list of conditions and the following disclaimer.
32820c16b537SWarner Losh     * Redistributions in binary form must reproduce the above
32830c16b537SWarner Losh     copyright notice, this list of conditions and the following disclaimer
32840c16b537SWarner Losh     in the documentation and/or other materials provided with the
32850c16b537SWarner Losh     distribution.
32860c16b537SWarner Losh     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
32870c16b537SWarner Losh     "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
32880c16b537SWarner Losh     LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
32890c16b537SWarner Losh     A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
32900c16b537SWarner Losh     OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
32910c16b537SWarner Losh     SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
32920c16b537SWarner Losh     LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
32930c16b537SWarner Losh     DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
32940c16b537SWarner Losh     THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
32950c16b537SWarner Losh     (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
32960c16b537SWarner Losh     OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32970c16b537SWarner Losh 
32980c16b537SWarner Losh     You can contact the author at :
32990c16b537SWarner Losh     - zstd source repository : https://github.com/Cyan4973/zstd
33000c16b537SWarner Losh     - ztsd public forum : https://groups.google.com/forum/#!forum/lz4c
33010c16b537SWarner Losh */
33020c16b537SWarner Losh 
33030c16b537SWarner Losh /* The objects defined into this file should be considered experimental.
33040c16b537SWarner Losh  * They are not labelled stable, as their prototype may change in the future.
33050c16b537SWarner Losh  * You can use them for tests, provide feedback, or if you can endure risk of future changes.
33060c16b537SWarner Losh  */
33070c16b537SWarner Losh 
33080c16b537SWarner Losh /* *************************************
33090c16b537SWarner Losh *  Includes
33100c16b537SWarner Losh ***************************************/
33110c16b537SWarner Losh #include <stdlib.h>
33120c16b537SWarner Losh 
33130c16b537SWarner Losh 
33140c16b537SWarner Losh /** ************************************************
33150c16b537SWarner Losh *  Streaming decompression
33160c16b537SWarner Losh *
33170c16b537SWarner Losh *  A ZBUFF_DCtx object is required to track streaming operation.
33180c16b537SWarner Losh *  Use ZBUFF_createDCtx() and ZBUFF_freeDCtx() to create/release resources.
33190c16b537SWarner Losh *  Use ZBUFF_decompressInit() to start a new decompression operation.
33200c16b537SWarner Losh *  ZBUFF_DCtx objects can be reused multiple times.
33210c16b537SWarner Losh *
33220c16b537SWarner Losh *  Use ZBUFF_decompressContinue() repetitively to consume your input.
33230c16b537SWarner Losh *  *srcSizePtr and *maxDstSizePtr can be any size.
33240c16b537SWarner Losh *  The function will report how many bytes were read or written by modifying *srcSizePtr and *maxDstSizePtr.
33250c16b537SWarner Losh *  Note that it may not consume the entire input, in which case it's up to the caller to call again the function with remaining input.
33260c16b537SWarner Losh *  The content of dst will be overwritten (up to *maxDstSizePtr) at each function call, so save its content if it matters or change dst .
33270c16b537SWarner Losh *  return : a hint to preferred nb of bytes to use as input for next function call (it's only a hint, to improve latency)
33280c16b537SWarner Losh *            or 0 when a frame is completely decoded
33290c16b537SWarner Losh *            or an error code, which can be tested using ZBUFF_isError().
33300c16b537SWarner Losh *
33310c16b537SWarner Losh *  Hint : recommended buffer sizes (not compulsory)
33320c16b537SWarner Losh *  output : 128 KB block size is the internal unit, it ensures it's always possible to write a full block when it's decoded.
33330c16b537SWarner Losh *  input : just follow indications from ZBUFF_decompressContinue() to minimize latency. It should always be <= 128 KB + 3 .
33340c16b537SWarner Losh * **************************************************/
33350c16b537SWarner Losh 
33360c16b537SWarner Losh typedef enum { ZBUFFds_init, ZBUFFds_readHeader, ZBUFFds_loadHeader, ZBUFFds_decodeHeader,
33370c16b537SWarner Losh                ZBUFFds_read, ZBUFFds_load, ZBUFFds_flush } ZBUFF_dStage;
33380c16b537SWarner Losh 
33390c16b537SWarner Losh /* *** Resource management *** */
33400c16b537SWarner Losh 
33410c16b537SWarner Losh #define ZSTD_frameHeaderSize_max 5   /* too magical, should come from reference */
33420c16b537SWarner Losh struct ZBUFFv04_DCtx_s {
33430c16b537SWarner Losh     ZSTD_DCtx* zc;
33440c16b537SWarner Losh     ZSTD_parameters params;
33450c16b537SWarner Losh     char* inBuff;
33460c16b537SWarner Losh     size_t inBuffSize;
33470c16b537SWarner Losh     size_t inPos;
33480c16b537SWarner Losh     char* outBuff;
33490c16b537SWarner Losh     size_t outBuffSize;
33500c16b537SWarner Losh     size_t outStart;
33510c16b537SWarner Losh     size_t outEnd;
33520c16b537SWarner Losh     size_t hPos;
33530c16b537SWarner Losh     const char* dict;
33540c16b537SWarner Losh     size_t dictSize;
33550c16b537SWarner Losh     ZBUFF_dStage stage;
33560c16b537SWarner Losh     unsigned char headerBuffer[ZSTD_frameHeaderSize_max];
33570c16b537SWarner Losh };   /* typedef'd to ZBUFF_DCtx within "zstd_buffered.h" */
33580c16b537SWarner Losh 
33590c16b537SWarner Losh typedef ZBUFFv04_DCtx ZBUFF_DCtx;
33600c16b537SWarner Losh 
33610c16b537SWarner Losh 
33620c16b537SWarner Losh static ZBUFF_DCtx* ZBUFF_createDCtx(void)
33630c16b537SWarner Losh {
33640c16b537SWarner Losh     ZBUFF_DCtx* zbc = (ZBUFF_DCtx*)malloc(sizeof(ZBUFF_DCtx));
33650c16b537SWarner Losh     if (zbc==NULL) return NULL;
33660c16b537SWarner Losh     memset(zbc, 0, sizeof(*zbc));
33670c16b537SWarner Losh     zbc->zc = ZSTD_createDCtx();
33680c16b537SWarner Losh     zbc->stage = ZBUFFds_init;
33690c16b537SWarner Losh     return zbc;
33700c16b537SWarner Losh }
33710c16b537SWarner Losh 
33720c16b537SWarner Losh static size_t ZBUFF_freeDCtx(ZBUFF_DCtx* zbc)
33730c16b537SWarner Losh {
33740c16b537SWarner Losh     if (zbc==NULL) return 0;   /* support free on null */
33750c16b537SWarner Losh     ZSTD_freeDCtx(zbc->zc);
33760c16b537SWarner Losh     free(zbc->inBuff);
33770c16b537SWarner Losh     free(zbc->outBuff);
33780c16b537SWarner Losh     free(zbc);
33790c16b537SWarner Losh     return 0;
33800c16b537SWarner Losh }
33810c16b537SWarner Losh 
33820c16b537SWarner Losh 
33830c16b537SWarner Losh /* *** Initialization *** */
33840c16b537SWarner Losh 
33850c16b537SWarner Losh static size_t ZBUFF_decompressInit(ZBUFF_DCtx* zbc)
33860c16b537SWarner Losh {
33870c16b537SWarner Losh     zbc->stage = ZBUFFds_readHeader;
33880c16b537SWarner Losh     zbc->hPos = zbc->inPos = zbc->outStart = zbc->outEnd = zbc->dictSize = 0;
33890c16b537SWarner Losh     return ZSTD_resetDCtx(zbc->zc);
33900c16b537SWarner Losh }
33910c16b537SWarner Losh 
33920c16b537SWarner Losh 
33930c16b537SWarner Losh static size_t ZBUFF_decompressWithDictionary(ZBUFF_DCtx* zbc, const void* src, size_t srcSize)
33940c16b537SWarner Losh {
33950c16b537SWarner Losh     zbc->dict = (const char*)src;
33960c16b537SWarner Losh     zbc->dictSize = srcSize;
33970c16b537SWarner Losh     return 0;
33980c16b537SWarner Losh }
33990c16b537SWarner Losh 
34000c16b537SWarner Losh static size_t ZBUFF_limitCopy(void* dst, size_t maxDstSize, const void* src, size_t srcSize)
34010c16b537SWarner Losh {
34020c16b537SWarner Losh     size_t length = MIN(maxDstSize, srcSize);
34030c16b537SWarner Losh     memcpy(dst, src, length);
34040c16b537SWarner Losh     return length;
34050c16b537SWarner Losh }
34060c16b537SWarner Losh 
34070c16b537SWarner Losh /* *** Decompression *** */
34080c16b537SWarner Losh 
34090c16b537SWarner Losh static size_t ZBUFF_decompressContinue(ZBUFF_DCtx* zbc, void* dst, size_t* maxDstSizePtr, const void* src, size_t* srcSizePtr)
34100c16b537SWarner Losh {
34110c16b537SWarner Losh     const char* const istart = (const char*)src;
34120c16b537SWarner Losh     const char* ip = istart;
34130c16b537SWarner Losh     const char* const iend = istart + *srcSizePtr;
34140c16b537SWarner Losh     char* const ostart = (char*)dst;
34150c16b537SWarner Losh     char* op = ostart;
34160c16b537SWarner Losh     char* const oend = ostart + *maxDstSizePtr;
34170c16b537SWarner Losh     U32 notDone = 1;
34180c16b537SWarner Losh 
341919fcbaf1SConrad Meyer     DEBUGLOG(5, "ZBUFF_decompressContinue");
34200c16b537SWarner Losh     while (notDone)
34210c16b537SWarner Losh     {
34220c16b537SWarner Losh         switch(zbc->stage)
34230c16b537SWarner Losh         {
34240c16b537SWarner Losh 
34250c16b537SWarner Losh         case ZBUFFds_init :
342619fcbaf1SConrad Meyer             DEBUGLOG(5, "ZBUFF_decompressContinue: stage==ZBUFFds_init => ERROR(init_missing)");
34270c16b537SWarner Losh             return ERROR(init_missing);
34280c16b537SWarner Losh 
34290c16b537SWarner Losh         case ZBUFFds_readHeader :
34300c16b537SWarner Losh             /* read header from src */
34310c16b537SWarner Losh             {   size_t const headerSize = ZSTD_getFrameParams(&(zbc->params), src, *srcSizePtr);
34320c16b537SWarner Losh                 if (ZSTD_isError(headerSize)) return headerSize;
34330c16b537SWarner Losh                 if (headerSize) {
34340c16b537SWarner Losh                     /* not enough input to decode header : tell how many bytes would be necessary */
34350c16b537SWarner Losh                     memcpy(zbc->headerBuffer+zbc->hPos, src, *srcSizePtr);
34360c16b537SWarner Losh                     zbc->hPos += *srcSizePtr;
34370c16b537SWarner Losh                     *maxDstSizePtr = 0;
34380c16b537SWarner Losh                     zbc->stage = ZBUFFds_loadHeader;
34390c16b537SWarner Losh                     return headerSize - zbc->hPos;
34400c16b537SWarner Losh                 }
34410c16b537SWarner Losh                 zbc->stage = ZBUFFds_decodeHeader;
34420c16b537SWarner Losh                 break;
34430c16b537SWarner Losh             }
34440c16b537SWarner Losh 
34450c16b537SWarner Losh         case ZBUFFds_loadHeader:
34460c16b537SWarner Losh             /* complete header from src */
34470c16b537SWarner Losh             {   size_t headerSize = ZBUFF_limitCopy(
34480c16b537SWarner Losh                     zbc->headerBuffer + zbc->hPos, ZSTD_frameHeaderSize_max - zbc->hPos,
34490c16b537SWarner Losh                     src, *srcSizePtr);
34500c16b537SWarner Losh                 zbc->hPos += headerSize;
34510c16b537SWarner Losh                 ip += headerSize;
34520c16b537SWarner Losh                 headerSize = ZSTD_getFrameParams(&(zbc->params), zbc->headerBuffer, zbc->hPos);
34530c16b537SWarner Losh                 if (ZSTD_isError(headerSize)) return headerSize;
34540c16b537SWarner Losh                 if (headerSize) {
34550c16b537SWarner Losh                     /* not enough input to decode header : tell how many bytes would be necessary */
34560c16b537SWarner Losh                     *maxDstSizePtr = 0;
34570c16b537SWarner Losh                     return headerSize - zbc->hPos;
34580c16b537SWarner Losh             }   }
34590c16b537SWarner Losh             /* intentional fallthrough */
34600c16b537SWarner Losh 
34610c16b537SWarner Losh         case ZBUFFds_decodeHeader:
34620c16b537SWarner Losh                 /* apply header to create / resize buffers */
34630c16b537SWarner Losh                 {   size_t const neededOutSize = (size_t)1 << zbc->params.windowLog;
34640c16b537SWarner Losh                     size_t const neededInSize = BLOCKSIZE;   /* a block is never > BLOCKSIZE */
34650c16b537SWarner Losh                     if (zbc->inBuffSize < neededInSize) {
34660c16b537SWarner Losh                         free(zbc->inBuff);
34670c16b537SWarner Losh                         zbc->inBuffSize = neededInSize;
34680c16b537SWarner Losh                         zbc->inBuff = (char*)malloc(neededInSize);
34690c16b537SWarner Losh                         if (zbc->inBuff == NULL) return ERROR(memory_allocation);
34700c16b537SWarner Losh                     }
34710c16b537SWarner Losh                     if (zbc->outBuffSize < neededOutSize) {
34720c16b537SWarner Losh                         free(zbc->outBuff);
34730c16b537SWarner Losh                         zbc->outBuffSize = neededOutSize;
34740c16b537SWarner Losh                         zbc->outBuff = (char*)malloc(neededOutSize);
34750c16b537SWarner Losh                         if (zbc->outBuff == NULL) return ERROR(memory_allocation);
34760c16b537SWarner Losh                 }   }
34770c16b537SWarner Losh                 if (zbc->dictSize)
34780c16b537SWarner Losh                     ZSTD_decompress_insertDictionary(zbc->zc, zbc->dict, zbc->dictSize);
34790c16b537SWarner Losh                 if (zbc->hPos) {
34800c16b537SWarner Losh                     /* some data already loaded into headerBuffer : transfer into inBuff */
34810c16b537SWarner Losh                     memcpy(zbc->inBuff, zbc->headerBuffer, zbc->hPos);
34820c16b537SWarner Losh                     zbc->inPos = zbc->hPos;
34830c16b537SWarner Losh                     zbc->hPos = 0;
34840c16b537SWarner Losh                     zbc->stage = ZBUFFds_load;
34850c16b537SWarner Losh                     break;
34860c16b537SWarner Losh                 }
34870c16b537SWarner Losh                 zbc->stage = ZBUFFds_read;
34880c16b537SWarner Losh 		/* fall-through */
34890c16b537SWarner Losh         case ZBUFFds_read:
34900c16b537SWarner Losh             {
34910c16b537SWarner Losh                 size_t neededInSize = ZSTD_nextSrcSizeToDecompress(zbc->zc);
34920c16b537SWarner Losh                 if (neededInSize==0)   /* end of frame */
34930c16b537SWarner Losh                 {
34940c16b537SWarner Losh                     zbc->stage = ZBUFFds_init;
34950c16b537SWarner Losh                     notDone = 0;
34960c16b537SWarner Losh                     break;
34970c16b537SWarner Losh                 }
34980c16b537SWarner Losh                 if ((size_t)(iend-ip) >= neededInSize)
34990c16b537SWarner Losh                 {
35000c16b537SWarner Losh                     /* directly decode from src */
35010c16b537SWarner Losh                     size_t decodedSize = ZSTD_decompressContinue(zbc->zc,
35020c16b537SWarner Losh                         zbc->outBuff + zbc->outStart, zbc->outBuffSize - zbc->outStart,
35030c16b537SWarner Losh                         ip, neededInSize);
35040c16b537SWarner Losh                     if (ZSTD_isError(decodedSize)) return decodedSize;
35050c16b537SWarner Losh                     ip += neededInSize;
35060c16b537SWarner Losh                     if (!decodedSize) break;   /* this was just a header */
35070c16b537SWarner Losh                     zbc->outEnd = zbc->outStart +  decodedSize;
35080c16b537SWarner Losh                     zbc->stage = ZBUFFds_flush;
35090c16b537SWarner Losh                     break;
35100c16b537SWarner Losh                 }
35110c16b537SWarner Losh                 if (ip==iend) { notDone = 0; break; }   /* no more input */
35120c16b537SWarner Losh                 zbc->stage = ZBUFFds_load;
35130c16b537SWarner Losh             }
35140c16b537SWarner Losh 	    /* fall-through */
35150c16b537SWarner Losh         case ZBUFFds_load:
35160c16b537SWarner Losh             {
35170c16b537SWarner Losh                 size_t neededInSize = ZSTD_nextSrcSizeToDecompress(zbc->zc);
35180c16b537SWarner Losh                 size_t toLoad = neededInSize - zbc->inPos;   /* should always be <= remaining space within inBuff */
35190c16b537SWarner Losh                 size_t loadedSize;
35200c16b537SWarner Losh                 if (toLoad > zbc->inBuffSize - zbc->inPos) return ERROR(corruption_detected);   /* should never happen */
35210c16b537SWarner Losh                 loadedSize = ZBUFF_limitCopy(zbc->inBuff + zbc->inPos, toLoad, ip, iend-ip);
35220c16b537SWarner Losh                 ip += loadedSize;
35230c16b537SWarner Losh                 zbc->inPos += loadedSize;
35240c16b537SWarner Losh                 if (loadedSize < toLoad) { notDone = 0; break; }   /* not enough input, wait for more */
35250c16b537SWarner Losh                 {
35260c16b537SWarner Losh                     size_t decodedSize = ZSTD_decompressContinue(zbc->zc,
35270c16b537SWarner Losh                         zbc->outBuff + zbc->outStart, zbc->outBuffSize - zbc->outStart,
35280c16b537SWarner Losh                         zbc->inBuff, neededInSize);
35290c16b537SWarner Losh                     if (ZSTD_isError(decodedSize)) return decodedSize;
35300c16b537SWarner Losh                     zbc->inPos = 0;   /* input is consumed */
35310c16b537SWarner Losh                     if (!decodedSize) { zbc->stage = ZBUFFds_read; break; }   /* this was just a header */
35320c16b537SWarner Losh                     zbc->outEnd = zbc->outStart +  decodedSize;
35330c16b537SWarner Losh                     zbc->stage = ZBUFFds_flush;
35340c16b537SWarner Losh                     /* ZBUFFds_flush follows */
35350c16b537SWarner Losh                 }
35360c16b537SWarner Losh             }
35370c16b537SWarner Losh 	    /* fall-through */
35380c16b537SWarner Losh         case ZBUFFds_flush:
35390c16b537SWarner Losh             {
35400c16b537SWarner Losh                 size_t toFlushSize = zbc->outEnd - zbc->outStart;
35410c16b537SWarner Losh                 size_t flushedSize = ZBUFF_limitCopy(op, oend-op, zbc->outBuff + zbc->outStart, toFlushSize);
35420c16b537SWarner Losh                 op += flushedSize;
35430c16b537SWarner Losh                 zbc->outStart += flushedSize;
35440c16b537SWarner Losh                 if (flushedSize == toFlushSize)
35450c16b537SWarner Losh                 {
35460c16b537SWarner Losh                     zbc->stage = ZBUFFds_read;
35470c16b537SWarner Losh                     if (zbc->outStart + BLOCKSIZE > zbc->outBuffSize)
35480c16b537SWarner Losh                         zbc->outStart = zbc->outEnd = 0;
35490c16b537SWarner Losh                     break;
35500c16b537SWarner Losh                 }
35510c16b537SWarner Losh                 /* cannot flush everything */
35520c16b537SWarner Losh                 notDone = 0;
35530c16b537SWarner Losh                 break;
35540c16b537SWarner Losh             }
35550c16b537SWarner Losh         default: return ERROR(GENERIC);   /* impossible */
35560c16b537SWarner Losh         }
35570c16b537SWarner Losh     }
35580c16b537SWarner Losh 
35590c16b537SWarner Losh     *srcSizePtr = ip-istart;
35600c16b537SWarner Losh     *maxDstSizePtr = op-ostart;
35610c16b537SWarner Losh 
35620c16b537SWarner Losh     {
35630c16b537SWarner Losh         size_t nextSrcSizeHint = ZSTD_nextSrcSizeToDecompress(zbc->zc);
35640c16b537SWarner Losh         if (nextSrcSizeHint > 3) nextSrcSizeHint+= 3;   /* get the next block header while at it */
35650c16b537SWarner Losh         nextSrcSizeHint -= zbc->inPos;   /* already loaded*/
35660c16b537SWarner Losh         return nextSrcSizeHint;
35670c16b537SWarner Losh     }
35680c16b537SWarner Losh }
35690c16b537SWarner Losh 
35700c16b537SWarner Losh 
35710c16b537SWarner Losh /* *************************************
35720c16b537SWarner Losh *  Tool functions
35730c16b537SWarner Losh ***************************************/
35740c16b537SWarner Losh unsigned ZBUFFv04_isError(size_t errorCode) { return ERR_isError(errorCode); }
35750c16b537SWarner Losh const char* ZBUFFv04_getErrorName(size_t errorCode) { return ERR_getErrorName(errorCode); }
35760c16b537SWarner Losh 
35770c16b537SWarner Losh size_t ZBUFFv04_recommendedDInSize()  { return BLOCKSIZE + 3; }
35780c16b537SWarner Losh size_t ZBUFFv04_recommendedDOutSize() { return BLOCKSIZE; }
35790c16b537SWarner Losh 
35800c16b537SWarner Losh 
35810c16b537SWarner Losh 
35820c16b537SWarner Losh /*- ========================================================================= -*/
35830c16b537SWarner Losh 
35840c16b537SWarner Losh /* final wrapping stage */
35850c16b537SWarner Losh 
35860c16b537SWarner Losh size_t ZSTDv04_decompressDCtx(ZSTD_DCtx* dctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize)
35870c16b537SWarner Losh {
35880c16b537SWarner Losh     return ZSTD_decompress_usingDict(dctx, dst, maxDstSize, src, srcSize, NULL, 0);
35890c16b537SWarner Losh }
35900c16b537SWarner Losh 
35910c16b537SWarner Losh size_t ZSTDv04_decompress(void* dst, size_t maxDstSize, const void* src, size_t srcSize)
35920c16b537SWarner Losh {
35930c16b537SWarner Losh #if defined(ZSTD_HEAPMODE) && (ZSTD_HEAPMODE==1)
35940c16b537SWarner Losh     size_t regenSize;
35950c16b537SWarner Losh     ZSTD_DCtx* dctx = ZSTD_createDCtx();
35960c16b537SWarner Losh     if (dctx==NULL) return ERROR(memory_allocation);
35970c16b537SWarner Losh     regenSize = ZSTDv04_decompressDCtx(dctx, dst, maxDstSize, src, srcSize);
35980c16b537SWarner Losh     ZSTD_freeDCtx(dctx);
35990c16b537SWarner Losh     return regenSize;
36000c16b537SWarner Losh #else
36010c16b537SWarner Losh     ZSTD_DCtx dctx;
36020c16b537SWarner Losh     return ZSTDv04_decompressDCtx(&dctx, dst, maxDstSize, src, srcSize);
36030c16b537SWarner Losh #endif
36040c16b537SWarner Losh }
36050c16b537SWarner Losh 
36060c16b537SWarner Losh size_t ZSTDv04_resetDCtx(ZSTDv04_Dctx* dctx) { return ZSTD_resetDCtx(dctx); }
36070c16b537SWarner Losh 
36080c16b537SWarner Losh size_t ZSTDv04_nextSrcSizeToDecompress(ZSTDv04_Dctx* dctx)
36090c16b537SWarner Losh {
36100c16b537SWarner Losh     return ZSTD_nextSrcSizeToDecompress(dctx);
36110c16b537SWarner Losh }
36120c16b537SWarner Losh 
36130c16b537SWarner Losh size_t ZSTDv04_decompressContinue(ZSTDv04_Dctx* dctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize)
36140c16b537SWarner Losh {
36150c16b537SWarner Losh     return ZSTD_decompressContinue(dctx, dst, maxDstSize, src, srcSize);
36160c16b537SWarner Losh }
36170c16b537SWarner Losh 
36180c16b537SWarner Losh 
36190c16b537SWarner Losh 
36200c16b537SWarner Losh ZBUFFv04_DCtx* ZBUFFv04_createDCtx(void) { return ZBUFF_createDCtx(); }
36210c16b537SWarner Losh size_t ZBUFFv04_freeDCtx(ZBUFFv04_DCtx* dctx) { return ZBUFF_freeDCtx(dctx); }
36220c16b537SWarner Losh 
36230c16b537SWarner Losh size_t ZBUFFv04_decompressInit(ZBUFFv04_DCtx* dctx) { return ZBUFF_decompressInit(dctx); }
36240c16b537SWarner Losh size_t ZBUFFv04_decompressWithDictionary(ZBUFFv04_DCtx* dctx, const void* src, size_t srcSize)
36250c16b537SWarner Losh { return ZBUFF_decompressWithDictionary(dctx, src, srcSize); }
36260c16b537SWarner Losh 
36270c16b537SWarner Losh size_t ZBUFFv04_decompressContinue(ZBUFFv04_DCtx* dctx, void* dst, size_t* maxDstSizePtr, const void* src, size_t* srcSizePtr)
36280c16b537SWarner Losh {
362919fcbaf1SConrad Meyer     DEBUGLOG(5, "ZBUFFv04_decompressContinue");
36300c16b537SWarner Losh     return ZBUFF_decompressContinue(dctx, dst, maxDstSizePtr, src, srcSizePtr);
36310c16b537SWarner Losh }
36320c16b537SWarner Losh 
36330c16b537SWarner Losh ZSTD_DCtx* ZSTDv04_createDCtx(void) { return ZSTD_createDCtx(); }
36340c16b537SWarner Losh size_t ZSTDv04_freeDCtx(ZSTD_DCtx* dctx) { return ZSTD_freeDCtx(dctx); }
3635