/*

* Copyright (c) 2016-present, Yann Collet, Facebook, Inc.

* All rights reserved.

*

* This source code is licensed under both the BSD-style license (found in the

* LICENSE file in the root directory of this source tree) and the GPLv2 (found

* in the COPYING file in the root directory of this source tree).

* You may select, at your option, one of the above-listed licenses.

*/

/******************************************

* Includes

******************************************/

#include <stddef.h> /* size_t, ptrdiff_t */

#include "zstd_v01.h"

#include "error_private.h"

/******************************************

* Static allocation

******************************************/

/* You can statically allocate FSE CTable/DTable as a table of unsigned using below macro */

#define FSE_DTABLE_SIZE_U32(maxTableLog) (1 + (1<<maxTableLog))

/* You can statically allocate Huff0 DTable as a table of unsigned short using below macro */

#define HUF_DTABLE_SIZE_U16(maxTableLog) (1 + (1<<maxTableLog))

#define HUF_CREATE_STATIC_DTABLE(DTable, maxTableLog) \

unsigned short DTable[HUF_DTABLE_SIZE_U16(maxTableLog)] = { maxTableLog }

/******************************************

* Error Management

******************************************/

#define FSE_LIST_ERRORS(ITEM) \

ITEM(FSE_OK_NoError) ITEM(FSE_ERROR_GENERIC) \

ITEM(FSE_ERROR_tableLog_tooLarge) ITEM(FSE_ERROR_maxSymbolValue_tooLarge) ITEM(FSE_ERROR_maxSymbolValue_tooSmall) \

ITEM(FSE_ERROR_dstSize_tooSmall) ITEM(FSE_ERROR_srcSize_wrong)\

ITEM(FSE_ERROR_corruptionDetected) \

ITEM(FSE_ERROR_maxCode)

#define FSE_GENERATE_ENUM(ENUM) ENUM,

typedef enum { FSE_LIST_ERRORS(FSE_GENERATE_ENUM) } FSE_errorCodes; /* enum is exposed, to detect & handle specific errors; compare function result to -enum value */

/******************************************

* FSE symbol compression API

******************************************/

/*

This API consists of small unitary functions, which highly benefit from being inlined.

You will want to enable link-time-optimization to ensure these functions are properly inlined in your binary.

Visual seems to do it automatically.

For gcc or clang, you'll need to add -flto flag at compilation and linking stages.

If none of these solutions is applicable, include "fse.c" directly.

*/

typedef unsigned FSE_CTable; /* don't allocate that. It's just a way to be more restrictive than void* */

typedef unsigned FSE_DTable; /* don't allocate that. It's just a way to be more restrictive than void* */

typedef struct

{

size_t bitContainer;

int bitPos;

char* startPtr;

char* ptr;

char* endPtr;

} FSE_CStream_t;

typedef struct

{

ptrdiff_t value;

const void* stateTable;

const void* symbolTT;

unsigned stateLog;

} FSE_CState_t;

typedef struct

{

size_t bitContainer;

unsigned bitsConsumed;

const char* ptr;

const char* start;

} FSE_DStream_t;

typedef struct

{

size_t state;

const void* table; /* precise table may vary, depending on U16 */

} FSE_DState_t;

typedef enum { FSE_DStream_unfinished = 0,

FSE_DStream_endOfBuffer = 1,

FSE_DStream_completed = 2,

FSE_DStream_tooFar = 3 } FSE_DStream_status; /* result of FSE_reloadDStream() */

/* 1,2,4,8 would be better for bitmap combinations, but slows down performance a bit ... ?! */

/****************************************************************

* Tuning parameters

****************************************************************/

/* MEMORY_USAGE :

* Memory usage formula : N->2^N Bytes (examples : 10 -> 1KB; 12 -> 4KB ; 16 -> 64KB; 20 -> 1MB; etc.)

* Increasing memory usage improves compression ratio

* Reduced memory usage can improve speed, due to cache effect

* Recommended max value is 14, for 16KB, which nicely fits into Intel x86 L1 cache */

#define FSE_MAX_MEMORY_USAGE 14

#define FSE_DEFAULT_MEMORY_USAGE 13

/* FSE_MAX_SYMBOL_VALUE :

* Maximum symbol value authorized.

* Required for proper stack allocation */

#define FSE_MAX_SYMBOL_VALUE 255

/****************************************************************

* template functions type & suffix

****************************************************************/

#define FSE_FUNCTION_TYPE BYTE

#define FSE_FUNCTION_EXTENSION

/****************************************************************

* Byte symbol type

****************************************************************/

typedef struct

{

unsigned short newState;

unsigned char symbol;

unsigned char nbBits;

} FSE_decode_t; /* size == U32 */

/****************************************************************

* Compiler specifics

****************************************************************/

#ifdef _MSC_VER /* Visual Studio */

# define FORCE_INLINE static __forceinline

# include <intrin.h> /* For Visual 2005 */

# pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */

# pragma warning(disable : 4214) /* disable: C4214: non-int bitfields */

#else

# define GCC_VERSION (__GNUC__ * 100 + __GNUC_MINOR__)

# if defined (__cplusplus) || defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L /* C99 */

# ifdef __GNUC__

# define FORCE_INLINE static inline __attribute__((always_inline))

# else

# define FORCE_INLINE static inline

# endif

# else

# define FORCE_INLINE static

# endif /* __STDC_VERSION__ */

#endif

/****************************************************************

* Includes

****************************************************************/

#include <stdlib.h> /* malloc, free, qsort */

#include <string.h> /* memcpy, memset */

#include <stdio.h> /* printf (debug) */

#ifndef MEM_ACCESS_MODULE

#define MEM_ACCESS_MODULE

/****************************************************************

* Basic Types

*****************************************************************/

#if defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L /* C99 */

# include <stdint.h>

typedef uint8_t BYTE;

typedef uint16_t U16;

typedef int16_t S16;

typedef uint32_t U32;

typedef int32_t S32;

typedef uint64_t U64;

typedef int64_t S64;

#else

typedef unsigned char BYTE;

typedef unsigned short U16;

typedef signed short S16;

typedef unsigned int U32;

typedef signed int S32;

typedef unsigned long long U64;

typedef signed long long S64;

#endif

#endif /* MEM_ACCESS_MODULE */

/****************************************************************

* Memory I/O

*****************************************************************/

/* FSE_FORCE_MEMORY_ACCESS

* By default, access to unaligned memory is controlled by `memcpy()`, which is safe and portable.

* Unfortunately, on some target/compiler combinations, the generated assembly is sub-optimal.

* The below switch allow to select different access method for improved performance.

* Method 0 (default) : use `memcpy()`. Safe and portable.

* Method 1 : `__packed` statement. It depends on compiler extension (ie, not portable).

* This method is safe if your compiler supports it, and *generally* as fast or faster than `memcpy`.

* Method 2 : direct access. This method is portable but violate C standard.

* It can generate buggy code on targets generating assembly depending on alignment.

* But in some circumstances, it's the only known way to get the most performance (ie GCC + ARMv6)

* See http://fastcompression.blogspot.fr/2015/08/accessing-unaligned-memory.html for details.

* Prefer these methods in priority order (0 > 1 > 2)

*/

#ifndef FSE_FORCE_MEMORY_ACCESS /* can be defined externally, on command line for example */

# 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__) )

# define FSE_FORCE_MEMORY_ACCESS 2

# elif (defined(__INTEL_COMPILER) && !defined(WIN32)) || \

(defined(__GNUC__) && ( defined(__ARM_ARCH_7__) || defined(__ARM_ARCH_7A__) || defined(__ARM_ARCH_7R__) || defined(__ARM_ARCH_7M__) || defined(__ARM_ARCH_7S__) ))

# define FSE_FORCE_MEMORY_ACCESS 1

# endif

#endif

static unsigned FSE_32bits(void)

{

return sizeof(void*)==4;

}

static unsigned FSE_isLittleEndian(void)

{

const union { U32 i; BYTE c[4]; } one = { 1 }; /* don't use static : performance detrimental */

return one.c[0];

}

#if defined(FSE_FORCE_MEMORY_ACCESS) && (FSE_FORCE_MEMORY_ACCESS==2)

static U16 FSE_read16(const void* memPtr) { return *(const U16*) memPtr; }

static U32 FSE_read32(const void* memPtr) { return *(const U32*) memPtr; }

static U64 FSE_read64(const void* memPtr) { return *(const U64*) memPtr; }

#elif defined(FSE_FORCE_MEMORY_ACCESS) && (FSE_FORCE_MEMORY_ACCESS==1)

/* __pack instructions are safer, but compiler specific, hence potentially problematic for some compilers */

/* currently only defined for gcc and icc */

typedef union { U16 u16; U32 u32; U64 u64; } __attribute__((packed)) unalign;

static U16 FSE_read16(const void* ptr) { return ((const unalign*)ptr)->u16; }

static U32 FSE_read32(const void* ptr) { return ((const unalign*)ptr)->u32; }

static U64 FSE_read64(const void* ptr) { return ((const unalign*)ptr)->u64; }

#else

static U16 FSE_read16(const void* memPtr)

{

U16 val; memcpy(&val, memPtr, sizeof(val)); return val;

}

static U32 FSE_read32(const void* memPtr)

{

U32 val; memcpy(&val, memPtr, sizeof(val)); return val;

}

static U64 FSE_read64(const void* memPtr)

{

U64 val; memcpy(&val, memPtr, sizeof(val)); return val;

}

#endif // FSE_FORCE_MEMORY_ACCESS

static U16 FSE_readLE16(const void* memPtr)

{

if (FSE_isLittleEndian())

return FSE_read16(memPtr);

else

{

const BYTE* p = (const BYTE*)memPtr;

return (U16)(p[0] + (p[1]<<8));

}

}

static U32 FSE_readLE32(const void* memPtr)

{

if (FSE_isLittleEndian())

return FSE_read32(memPtr);

else

{

const BYTE* p = (const BYTE*)memPtr;

return (U32)((U32)p[0] + ((U32)p[1]<<8) + ((U32)p[2]<<16) + ((U32)p[3]<<24));

}

}

static U64 FSE_readLE64(const void* memPtr)

{

if (FSE_isLittleEndian())

return FSE_read64(memPtr);

else

{

const BYTE* p = (const BYTE*)memPtr;

return (U64)((U64)p[0] + ((U64)p[1]<<8) + ((U64)p[2]<<16) + ((U64)p[3]<<24)

+ ((U64)p[4]<<32) + ((U64)p[5]<<40) + ((U64)p[6]<<48) + ((U64)p[7]<<56));

}

}

static size_t FSE_readLEST(const void* memPtr)

{

if (FSE_32bits())

return (size_t)FSE_readLE32(memPtr);

else

return (size_t)FSE_readLE64(memPtr);

}

/****************************************************************

* Constants

*****************************************************************/

#define FSE_MAX_TABLELOG (FSE_MAX_MEMORY_USAGE-2)

#define FSE_MAX_TABLESIZE (1U<<FSE_MAX_TABLELOG)

#define FSE_MAXTABLESIZE_MASK (FSE_MAX_TABLESIZE-1)

#define FSE_DEFAULT_TABLELOG (FSE_DEFAULT_MEMORY_USAGE-2)

#define FSE_MIN_TABLELOG 5

#define FSE_TABLELOG_ABSOLUTE_MAX 15

#if FSE_MAX_TABLELOG > FSE_TABLELOG_ABSOLUTE_MAX

#error "FSE_MAX_TABLELOG > FSE_TABLELOG_ABSOLUTE_MAX is not supported"

#endif

/****************************************************************

* Error Management

****************************************************************/

#define FSE_STATIC_ASSERT(c) { enum { FSE_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */

/****************************************************************

* Complex types

****************************************************************/

typedef struct

{

int deltaFindState;

U32 deltaNbBits;

} FSE_symbolCompressionTransform; /* total 8 bytes */

typedef U32 DTable_max_t[FSE_DTABLE_SIZE_U32(FSE_MAX_TABLELOG)];

/****************************************************************

* Internal functions

****************************************************************/

FORCE_INLINE unsigned FSE_highbit32 (U32 val)

{

# if defined(_MSC_VER) /* Visual */

unsigned long r;

_BitScanReverse ( &r, val );

return (unsigned) r;

# elif defined(__GNUC__) && (GCC_VERSION >= 304) /* GCC Intrinsic */

return 31 - __builtin_clz (val);

# else /* Software version */

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 };

U32 v = val;

unsigned r;

v |= v >> 1;

v |= v >> 2;

v |= v >> 4;

v |= v >> 8;

v |= v >> 16;

r = DeBruijnClz[ (U32) (v * 0x07C4ACDDU) >> 27];

return r;

# endif

}

/****************************************************************

* Templates

****************************************************************/

/*

designed to be included

for type-specific functions (template emulation in C)

Objective is to write these functions only once, for improved maintenance

*/

/* safety checks */

#ifndef FSE_FUNCTION_EXTENSION

# error "FSE_FUNCTION_EXTENSION must be defined"

#endif

#ifndef FSE_FUNCTION_TYPE

# error "FSE_FUNCTION_TYPE must be defined"

#endif

/* Function names */

#define FSE_CAT(X,Y) X##Y

#define FSE_FUNCTION_NAME(X,Y) FSE_CAT(X,Y)

#define FSE_TYPE_NAME(X,Y) FSE_CAT(X,Y)

static U32 FSE_tableStep(U32 tableSize) { return (tableSize>>1) + (tableSize>>3) + 3; }

#define FSE_DECODE_TYPE FSE_decode_t

typedef struct {

U16 tableLog;

U16 fastMode;

} FSE_DTableHeader; /* sizeof U32 */

static size_t FSE_buildDTable

(FSE_DTable* dt, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog)

{

void* ptr = dt;

FSE_DTableHeader* const DTableH = (FSE_DTableHeader*)ptr;

FSE_DECODE_TYPE* const tableDecode = (FSE_DECODE_TYPE*)(ptr) + 1; /* because dt is unsigned, 32-bits aligned on 32-bits */

const U32 tableSize = 1 << tableLog;

const U32 tableMask = tableSize-1;

const U32 step = FSE_tableStep(tableSize);

U16 symbolNext[FSE_MAX_SYMBOL_VALUE+1];

U32 position = 0;

U32 highThreshold = tableSize-1;

const S16 largeLimit= (S16)(1 << (tableLog-1));

U32 noLarge = 1;

U32 s;

/* Sanity Checks */

if (maxSymbolValue > FSE_MAX_SYMBOL_VALUE) return (size_t)-FSE_ERROR_maxSymbolValue_tooLarge;

if (tableLog > FSE_MAX_TABLELOG) return (size_t)-FSE_ERROR_tableLog_tooLarge;

/* Init, lay down lowprob symbols */

DTableH[0].tableLog = (U16)tableLog;

for (s=0; s<=maxSymbolValue; s++)

{

if (normalizedCounter[s]==-1)

{

tableDecode[highThreshold--].symbol = (FSE_FUNCTION_TYPE)s;

symbolNext[s] = 1;

}

else

{

if (normalizedCounter[s] >= largeLimit) noLarge=0;

symbolNext[s] = normalizedCounter[s];

}

}

/* Spread symbols */

for (s=0; s<=maxSymbolValue; s++)

{

int i;

for (i=0; i<normalizedCounter[s]; i++)

{

tableDecode[position].symbol = (FSE_FUNCTION_TYPE)s;

position = (position + step) & tableMask;

while (position > highThreshold) position = (position + step) & tableMask; /* lowprob area */

}

}

if (position!=0) return (size_t)-FSE_ERROR_GENERIC; /* position must reach all cells once, otherwise normalizedCounter is incorrect */

/* Build Decoding table */

{

U32 i;

for (i=0; i<tableSize; i++)

{

FSE_FUNCTION_TYPE symbol = (FSE_FUNCTION_TYPE)(tableDecode[i].symbol);

U16 nextState = symbolNext[symbol]++;

tableDecode[i].nbBits = (BYTE) (tableLog - FSE_highbit32 ((U32)nextState) );

tableDecode[i].newState = (U16) ( (nextState << tableDecode[i].nbBits) - tableSize);

}

}

DTableH->fastMode = (U16)noLarge;

return 0;

}

/******************************************

* FSE byte symbol

******************************************/

#ifndef FSE_COMMONDEFS_ONLY

static unsigned FSE_isError(size_t code) { return (code > (size_t)(-FSE_ERROR_maxCode)); }

static short FSE_abs(short a)

{

return a<0? -a : a;

}

/****************************************************************

* Header bitstream management

****************************************************************/

static size_t FSE_readNCount (short* normalizedCounter, unsigned* maxSVPtr, unsigned* tableLogPtr,

const void* headerBuffer, size_t hbSize)

{

const BYTE* const istart = (const BYTE*) headerBuffer;

const BYTE* const iend = istart + hbSize;

const BYTE* ip = istart;

int nbBits;

int remaining;

int threshold;

U32 bitStream;

int bitCount;

unsigned charnum = 0;

int previous0 = 0;

if (hbSize < 4) return (size_t)-FSE_ERROR_srcSize_wrong;

bitStream = FSE_readLE32(ip);

nbBits = (bitStream & 0xF) + FSE_MIN_TABLELOG; /* extract tableLog */

if (nbBits > FSE_TABLELOG_ABSOLUTE_MAX) return (size_t)-FSE_ERROR_tableLog_tooLarge;

bitStream >>= 4;

bitCount = 4;

*tableLogPtr = nbBits;

remaining = (1<<nbBits)+1;

threshold = 1<<nbBits;

nbBits++;

while ((remaining>1) && (charnum<=*maxSVPtr))

{

if (previous0)

{

unsigned n0 = charnum;

while ((bitStream & 0xFFFF) == 0xFFFF)

{

n0+=24;

if (ip < iend-5)

{

ip+=2;

bitStream = FSE_readLE32(ip) >> bitCount;

}

else

{

bitStream >>= 16;

bitCount+=16;

}

}

while ((bitStream & 3) == 3)

{

n0+=3;

bitStream>>=2;

bitCount+=2;

}

n0 += bitStream & 3;

bitCount += 2;

if (n0 > *maxSVPtr) return (size_t)-FSE_ERROR_maxSymbolValue_tooSmall;

while (charnum < n0) normalizedCounter[charnum++] = 0;

if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4))

{

ip += bitCount>>3;

bitCount &= 7;

bitStream = FSE_readLE32(ip) >> bitCount;

}

else

bitStream >>= 2;

}

{

const short max = (short)((2*threshold-1)-remaining);

short count;

if ((bitStream & (threshold-1)) < (U32)max)

{

count = (short)(bitStream & (threshold-1));

bitCount += nbBits-1;

}

else

{

count = (short)(bitStream & (2*threshold-1));

if (count >= threshold) count -= max;

bitCount += nbBits;

}

count--; /* extra accuracy */

remaining -= FSE_abs(count);

normalizedCounter[charnum++] = count;

previous0 = !count;

while (remaining < threshold)

{

nbBits--;

threshold >>= 1;

}

{

if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4))

{

ip += bitCount>>3;

bitCount &= 7;

}

else

{

bitCount -= (int)(8 * (iend - 4 - ip));

ip = iend - 4;

}

bitStream = FSE_readLE32(ip) >> (bitCount & 31);

}

}

}

if (remaining != 1) return (size_t)-FSE_ERROR_GENERIC;

*maxSVPtr = charnum-1;

ip += (bitCount+7)>>3;

if ((size_t)(ip-istart) > hbSize) return (size_t)-FSE_ERROR_srcSize_wrong;

return ip-istart;

}

/*********************************************************

* Decompression (Byte symbols)

*********************************************************/

static size_t FSE_buildDTable_rle (FSE_DTable* dt, BYTE symbolValue)

{

void* ptr = dt;

FSE_DTableHeader* const DTableH = (FSE_DTableHeader*)ptr;

FSE_decode_t* const cell = (FSE_decode_t*)(ptr) + 1; /* because dt is unsigned */

DTableH->tableLog = 0;

DTableH->fastMode = 0;

cell->newState = 0;

cell->symbol = symbolValue;

cell->nbBits = 0;

return 0;

}

static size_t FSE_buildDTable_raw (FSE_DTable* dt, unsigned nbBits)

{

void* ptr = dt;

FSE_DTableHeader* const DTableH = (FSE_DTableHeader*)ptr;

FSE_decode_t* const dinfo = (FSE_decode_t*)(ptr) + 1; /* because dt is unsigned */

const unsigned tableSize = 1 << nbBits;

const unsigned tableMask = tableSize - 1;

const unsigned maxSymbolValue = tableMask;

unsigned s;

/* Sanity checks */

if (nbBits < 1) return (size_t)-FSE_ERROR_GENERIC; /* min size */

/* Build Decoding Table */

DTableH->tableLog = (U16)nbBits;

DTableH->fastMode = 1;

for (s=0; s<=maxSymbolValue; s++)

{

dinfo[s].newState = 0;

dinfo[s].symbol = (BYTE)s;

dinfo[s].nbBits = (BYTE)nbBits;

}

return 0;

}

/* FSE_initDStream

* Initialize a FSE_DStream_t.

* srcBuffer must point at the beginning of an FSE block.

* The function result is the size of the FSE_block (== srcSize).

* If srcSize is too small, the function will return an errorCode;

*/

static size_t FSE_initDStream(FSE_DStream_t* bitD, const void* srcBuffer, size_t srcSize)

{

if (srcSize < 1) return (size_t)-FSE_ERROR_srcSize_wrong;

if (srcSize >= sizeof(size_t))

{

U32 contain32;

bitD->start = (const char*)srcBuffer;

bitD->ptr = (const char*)srcBuffer + srcSize - sizeof(size_t);

bitD->bitContainer = FSE_readLEST(bitD->ptr);

contain32 = ((const BYTE*)srcBuffer)[srcSize-1];

if (contain32 == 0) return (size_t)-FSE_ERROR_GENERIC; /* stop bit not present */

bitD->bitsConsumed = 8 - FSE_highbit32(contain32);

}

else

{

U32 contain32;

bitD->start = (const char*)srcBuffer;

bitD->ptr = bitD->start;

bitD->bitContainer = *(const BYTE*)(bitD->start);

switch(srcSize)

{

case 7: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[6]) << (sizeof(size_t)*8 - 16);

case 6: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[5]) << (sizeof(size_t)*8 - 24);

case 5: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[4]) << (sizeof(size_t)*8 - 32);

case 4: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[3]) << 24;

case 3: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[2]) << 16;

case 2: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[1]) << 8;

default:;

}

contain32 = ((const BYTE*)srcBuffer)[srcSize-1];

if (contain32 == 0) return (size_t)-FSE_ERROR_GENERIC; /* stop bit not present */

bitD->bitsConsumed = 8 - FSE_highbit32(contain32);

bitD->bitsConsumed += (U32)(sizeof(size_t) - srcSize)*8;

}

return srcSize;

}

/*!FSE_lookBits

* Provides next n bits from the bitContainer.

* bitContainer is not modified (bits are still present for next read/look)

* On 32-bits, maxNbBits==25

* On 64-bits, maxNbBits==57

* return : value extracted.

*/

static size_t FSE_lookBits(FSE_DStream_t* bitD, U32 nbBits)

{

const U32 bitMask = sizeof(bitD->bitContainer)*8 - 1;

return ((bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> 1) >> ((bitMask-nbBits) & bitMask);

}

static size_t FSE_lookBitsFast(FSE_DStream_t* bitD, U32 nbBits) /* only if nbBits >= 1 !! */

{

const U32 bitMask = sizeof(bitD->bitContainer)*8 - 1;

return (bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> (((bitMask+1)-nbBits) & bitMask);

}

static void FSE_skipBits(FSE_DStream_t* bitD, U32 nbBits)

{

bitD->bitsConsumed += nbBits;

}

/*!FSE_readBits

* Read next n bits from the bitContainer.

* On 32-bits, don't read more than maxNbBits==25

* On 64-bits, don't read more than maxNbBits==57

* Use the fast variant *only* if n >= 1.

* return : value extracted.

*/

static size_t FSE_readBits(FSE_DStream_t* bitD, U32 nbBits)

{

size_t value = FSE_lookBits(bitD, nbBits);

FSE_skipBits(bitD, nbBits);

return value;

}

static size_t FSE_readBitsFast(FSE_DStream_t* bitD, U32 nbBits) /* only if nbBits >= 1 !! */

{

size_t value = FSE_lookBitsFast(bitD, nbBits);

FSE_skipBits(bitD, nbBits);

return value;

}

static unsigned FSE_reloadDStream(FSE_DStream_t* bitD)

{

if (bitD->bitsConsumed > (sizeof(bitD->bitContainer)*8)) /* should never happen */

return FSE_DStream_tooFar;

if (bitD->ptr >= bitD->start + sizeof(bitD->bitContainer))

{

bitD->ptr -= bitD->bitsConsumed >> 3;

bitD->bitsConsumed &= 7;

bitD->bitContainer = FSE_readLEST(bitD->ptr);

return FSE_DStream_unfinished;

}

if (bitD->ptr == bitD->start)

{

if (bitD->bitsConsumed < sizeof(bitD->bitContainer)*8) return FSE_DStream_endOfBuffer;

return FSE_DStream_completed;

}

{

U32 nbBytes = bitD->bitsConsumed >> 3;

U32 result = FSE_DStream_unfinished;

if (bitD->ptr - nbBytes < bitD->start)

{

nbBytes = (U32)(bitD->ptr - bitD->start); /* ptr > start */

result = FSE_DStream_endOfBuffer;

}

bitD->ptr -= nbBytes;

bitD->bitsConsumed -= nbBytes*8;

bitD->bitContainer = FSE_readLEST(bitD->ptr); /* reminder : srcSize > sizeof(bitD) */

return result;

}

}

static void FSE_initDState(FSE_DState_t* DStatePtr, FSE_DStream_t* bitD, const FSE_DTable* dt)

{

const void* ptr = dt;

const FSE_DTableHeader* const DTableH = (const FSE_DTableHeader*)ptr;

DStatePtr->state = FSE_readBits(bitD, DTableH->tableLog);

FSE_reloadDStream(bitD);

DStatePtr->table = dt + 1;

}

static BYTE FSE_decodeSymbol(FSE_DState_t* DStatePtr, FSE_DStream_t* bitD)

{

const FSE_decode_t DInfo = ((const FSE_decode_t*)(DStatePtr->table))[DStatePtr->state];

const U32 nbBits = DInfo.nbBits;

BYTE symbol = DInfo.symbol;

size_t lowBits = FSE_readBits(bitD, nbBits);

DStatePtr->state = DInfo.newState + lowBits;

return symbol;

}

static BYTE FSE_decodeSymbolFast(FSE_DState_t* DStatePtr, FSE_DStream_t* bitD)

{

const FSE_decode_t DInfo = ((const FSE_decode_t*)(DStatePtr->table))[DStatePtr->state];

const U32 nbBits = DInfo.nbBits;

BYTE symbol = DInfo.symbol;

size_t lowBits = FSE_readBitsFast(bitD, nbBits);

DStatePtr->state = DInfo.newState + lowBits;

return symbol;

}

/* FSE_endOfDStream

Tells if bitD has reached end of bitStream or not */

static unsigned FSE_endOfDStream(const FSE_DStream_t* bitD)

{

return ((bitD->ptr == bitD->start) && (bitD->bitsConsumed == sizeof(bitD->bitContainer)*8));

}

static unsigned FSE_endOfDState(const FSE_DState_t* DStatePtr)

{

return DStatePtr->state == 0;

}

FORCE_INLINE size_t FSE_decompress_usingDTable_generic(

void* dst, size_t maxDstSize,

const void* cSrc, size_t cSrcSize,

const FSE_DTable* dt, const unsigned fast)

{

BYTE* const ostart = (BYTE*) dst;

BYTE* op = ostart;

BYTE* const omax = op + maxDstSize;

BYTE* const olimit = omax-3;

FSE_DStream_t bitD;

FSE_DState_t state1;

FSE_DState_t state2;

size_t errorCode;

/* Init */

errorCode = FSE_initDStream(&bitD, cSrc, cSrcSize); /* replaced last arg by maxCompressed Size */

if (FSE_isError(errorCode)) return errorCode;

FSE_initDState(&state1, &bitD, dt);

FSE_initDState(&state2, &bitD, dt);

#define FSE_GETSYMBOL(statePtr) fast ? FSE_decodeSymbolFast(statePtr, &bitD) : FSE_decodeSymbol(statePtr, &bitD)

/* 4 symbols per loop */

for ( ; (FSE_reloadDStream(&bitD)==FSE_DStream_unfinished) && (op<olimit) ; op+=4)

{

op[0] = FSE_GETSYMBOL(&state1);

if (FSE_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */

FSE_reloadDStream(&bitD);

op[1] = FSE_GETSYMBOL(&state2);

if (FSE_MAX_TABLELOG*4+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */

{ if (FSE_reloadDStream(&bitD) > FSE_DStream_unfinished) { op+=2; break; } }

op[2] = FSE_GETSYMBOL(&state1);

if (FSE_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */

FSE_reloadDStream(&bitD);

op[3] = FSE_GETSYMBOL(&state2);

}

/* tail */

/* note : FSE_reloadDStream(&bitD) >= FSE_DStream_partiallyFilled; Ends at exactly FSE_DStream_completed */

while (1)

{

if ( (FSE_reloadDStream(&bitD)>FSE_DStream_completed) || (op==omax) || (FSE_endOfDStream(&bitD) && (fast || FSE_endOfDState(&state1))) )

break;

*op++ = FSE_GETSYMBOL(&state1);

if ( (FSE_reloadDStream(&bitD)>FSE_DStream_completed) || (op==omax) || (FSE_endOfDStream(&bitD) && (fast || FSE_endOfDState(&state2))) )

break;

*op++ = FSE_GETSYMBOL(&state2);

}

/* end ? */

if (FSE_endOfDStream(&bitD) && FSE_endOfDState(&state1) && FSE_endOfDState(&state2))

return op-ostart;

if (op==omax) return (size_t)-FSE_ERROR_dstSize_tooSmall; /* dst buffer is full, but cSrc unfinished */

return (size_t)-FSE_ERROR_corruptionDetected;

}

static size_t FSE_decompress_usingDTable(void* dst, size_t originalSize,

const void* cSrc, size_t cSrcSize,

const FSE_DTable* dt)

{

FSE_DTableHeader DTableH;

memcpy(&DTableH, dt, sizeof(DTableH)); /* memcpy() into local variable, to avoid strict aliasing warning */

/* select fast mode (static) */

if (DTableH.fastMode) return FSE_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 1);

return FSE_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 0);

}

static size_t FSE_decompress(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize)

{

const BYTE* const istart = (const BYTE*)cSrc;

const BYTE* ip = istart;

short counting[FSE_MAX_SYMBOL_VALUE+1];

DTable_max_t dt; /* Static analyzer seems unable to understand this table will be properly initialized later */

unsigned tableLog;

unsigned maxSymbolValue = FSE_MAX_SYMBOL_VALUE;

size_t errorCode;

if (cSrcSize<2) return (size_t)-FSE_ERROR_srcSize_wrong; /* too small input size */

/* normal FSE decoding mode */

errorCode = FSE_readNCount (counting, &maxSymbolValue, &tableLog, istart, cSrcSize);

if (FSE_isError(errorCode)) return errorCode;

if (errorCode >= cSrcSize) return (size_t)-FSE_ERROR_srcSize_wrong; /* too small input size */

ip += errorCode;

cSrcSize -= errorCode;

errorCode = FSE_buildDTable (dt, counting, maxSymbolValue, tableLog);

if (FSE_isError(errorCode)) return errorCode;

/* always return, even if it is an error code */

return FSE_decompress_usingDTable (dst, maxDstSize, ip, cSrcSize, dt);

}

/* *******************************************************

* Huff0 : Huffman block compression

*********************************************************/

#define HUF_MAX_SYMBOL_VALUE 255

#define HUF_DEFAULT_TABLELOG 12 /* used by default, when not specified */

#define HUF_MAX_TABLELOG 12 /* max possible tableLog; for allocation purpose; can be modified */

#define HUF_ABSOLUTEMAX_TABLELOG 16 /* absolute limit of HUF_MAX_TABLELOG. Beyond that value, code does not work */

#if (HUF_MAX_TABLELOG > HUF_ABSOLUTEMAX_TABLELOG)

# error "HUF_MAX_TABLELOG is too large !"

#endif

typedef struct HUF_CElt_s {

U16 val;

BYTE nbBits;

} HUF_CElt ;

typedef struct nodeElt_s {

U32 count;

U16 parent;

BYTE byte;

BYTE nbBits;

} nodeElt;

/* *******************************************************

* Huff0 : Huffman block decompression

*********************************************************/

typedef struct {

BYTE byte;

BYTE nbBits;

} HUF_DElt;

static size_t HUF_readDTable (U16* DTable, const void* src, size_t srcSize)

{

BYTE huffWeight[HUF_MAX_SYMBOL_VALUE + 1];

U32 rankVal[HUF_ABSOLUTEMAX_TABLELOG + 1]; /* large enough for values from 0 to 16 */

U32 weightTotal;

U32 maxBits;

const BYTE* ip = (const BYTE*) src;

size_t iSize;

size_t oSize;

U32 n;

U32 nextRankStart;

void* ptr = DTable+1;

HUF_DElt* const dt = (HUF_DElt*)ptr;

if (!srcSize) return (size_t)-FSE_ERROR_srcSize_wrong;

iSize = ip[0];

FSE_STATIC_ASSERT(sizeof(HUF_DElt) == sizeof(U16)); /* if compilation fails here, assertion is false */

//memset(huffWeight, 0, sizeof(huffWeight)); /* should not be necessary, but some analyzer complain ... */

if (iSize >= 128) /* special header */

{

if (iSize >= (242)) /* RLE */

{

static int l[14] = { 1, 2, 3, 4, 7, 8, 15, 16, 31, 32, 63, 64, 127, 128 };

oSize = l[iSize-242];

memset(huffWeight, 1, sizeof(huffWeight));

iSize = 0;

}

else /* Incompressible */

{

oSize = iSize - 127;

iSize = ((oSize+1)/2);

if (iSize+1 > srcSize) return (size_t)-FSE_ERROR_srcSize_wrong;

ip += 1;

for (n=0; n<oSize; n+=2)

{

huffWeight[n] = ip[n/2] >> 4;

huffWeight[n+1] = ip[n/2] & 15;

}

}

}

else /* header compressed with FSE (normal case) */

{

if (iSize+1 > srcSize) return (size_t)-FSE_ERROR_srcSize_wrong;

oSize = FSE_decompress(huffWeight, HUF_MAX_SYMBOL_VALUE, ip+1, iSize); /* max 255 values decoded, last one is implied */

if (FSE_isError(oSize)) return oSize;