/*

* 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.

*/

/*- Dependencies -*/

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

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

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

#ifndef XXH_STATIC_LINKING_ONLY

# define XXH_STATIC_LINKING_ONLY /* XXH64_state_t */

#endif

#include "xxhash.h" /* XXH64_* */

#include "zstd_v07.h"

#define FSEv07_STATIC_LINKING_ONLY /* FSEv07_MIN_TABLELOG */

#define HUFv07_STATIC_LINKING_ONLY /* HUFv07_TABLELOG_ABSOLUTEMAX */

#define ZSTDv07_STATIC_LINKING_ONLY

#include "error_private.h"

#ifdef ZSTDv07_STATIC_LINKING_ONLY

/* ====================================================================================

* The definitions in this section are considered experimental.

* They should never be used with a dynamic library, as they may change in the future.

* They are provided for advanced usages.

* Use them only in association with static linking.

* ==================================================================================== */

/*--- Constants ---*/

#define ZSTDv07_MAGIC_SKIPPABLE_START 0x184D2A50U

#define ZSTDv07_WINDOWLOG_MAX_32 25

#define ZSTDv07_WINDOWLOG_MAX_64 27

#define ZSTDv07_WINDOWLOG_MAX ((U32)(MEM_32bits() ? ZSTDv07_WINDOWLOG_MAX_32 : ZSTDv07_WINDOWLOG_MAX_64))

#define ZSTDv07_WINDOWLOG_MIN 18

#define ZSTDv07_CHAINLOG_MAX (ZSTDv07_WINDOWLOG_MAX+1)

#define ZSTDv07_CHAINLOG_MIN 4

#define ZSTDv07_HASHLOG_MAX ZSTDv07_WINDOWLOG_MAX

#define ZSTDv07_HASHLOG_MIN 12

#define ZSTDv07_HASHLOG3_MAX 17

#define ZSTDv07_SEARCHLOG_MAX (ZSTDv07_WINDOWLOG_MAX-1)

#define ZSTDv07_SEARCHLOG_MIN 1

#define ZSTDv07_SEARCHLENGTH_MAX 7

#define ZSTDv07_SEARCHLENGTH_MIN 3

#define ZSTDv07_TARGETLENGTH_MIN 4

#define ZSTDv07_TARGETLENGTH_MAX 999

#define ZSTDv07_FRAMEHEADERSIZE_MAX 18 /* for static allocation */

static const size_t ZSTDv07_frameHeaderSize_min = 5;

static const size_t ZSTDv07_frameHeaderSize_max = ZSTDv07_FRAMEHEADERSIZE_MAX;

static const size_t ZSTDv07_skippableHeaderSize = 8; /* magic number + skippable frame length */

/* custom memory allocation functions */

typedef void* (*ZSTDv07_allocFunction) (void* opaque, size_t size);

typedef void (*ZSTDv07_freeFunction) (void* opaque, void* address);

typedef struct { ZSTDv07_allocFunction customAlloc; ZSTDv07_freeFunction customFree; void* opaque; } ZSTDv07_customMem;

/*--- Advanced Decompression functions ---*/

/*! ZSTDv07_estimateDCtxSize() :

* Gives the potential amount of memory allocated to create a ZSTDv07_DCtx */

ZSTDLIBv07_API size_t ZSTDv07_estimateDCtxSize(void);

/*! ZSTDv07_createDCtx_advanced() :

* Create a ZSTD decompression context using external alloc and free functions */

ZSTDLIBv07_API ZSTDv07_DCtx* ZSTDv07_createDCtx_advanced(ZSTDv07_customMem customMem);

/*! ZSTDv07_sizeofDCtx() :

* Gives the amount of memory used by a given ZSTDv07_DCtx */

ZSTDLIBv07_API size_t ZSTDv07_sizeofDCtx(const ZSTDv07_DCtx* dctx);

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

* Buffer-less streaming functions (synchronous mode)

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

ZSTDLIBv07_API size_t ZSTDv07_decompressBegin(ZSTDv07_DCtx* dctx);

ZSTDLIBv07_API size_t ZSTDv07_decompressBegin_usingDict(ZSTDv07_DCtx* dctx, const void* dict, size_t dictSize);

ZSTDLIBv07_API void ZSTDv07_copyDCtx(ZSTDv07_DCtx* dctx, const ZSTDv07_DCtx* preparedDCtx);

ZSTDLIBv07_API size_t ZSTDv07_nextSrcSizeToDecompress(ZSTDv07_DCtx* dctx);

ZSTDLIBv07_API size_t ZSTDv07_decompressContinue(ZSTDv07_DCtx* dctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize);

/*

Buffer-less streaming decompression (synchronous mode)

A ZSTDv07_DCtx object is required to track streaming operations.

Use ZSTDv07_createDCtx() / ZSTDv07_freeDCtx() to manage it.

A ZSTDv07_DCtx object can be re-used multiple times.

First optional operation is to retrieve frame parameters, using ZSTDv07_getFrameParams(), which doesn't consume the input.

It can provide the minimum size of rolling buffer required to properly decompress data (`windowSize`),

and optionally the final size of uncompressed content.

(Note : content size is an optional info that may not be present. 0 means : content size unknown)

Frame parameters are extracted from the beginning of compressed frame.

The amount of data to read is variable, from ZSTDv07_frameHeaderSize_min to ZSTDv07_frameHeaderSize_max (so if `srcSize` >= ZSTDv07_frameHeaderSize_max, it will always work)

If `srcSize` is too small for operation to succeed, function will return the minimum size it requires to produce a result.

Result : 0 when successful, it means the ZSTDv07_frameParams structure has been filled.

>0 : means there is not enough data into `src`. Provides the expected size to successfully decode header.

errorCode, which can be tested using ZSTDv07_isError()

Start decompression, with ZSTDv07_decompressBegin() or ZSTDv07_decompressBegin_usingDict().

Alternatively, you can copy a prepared context, using ZSTDv07_copyDCtx().

Then use ZSTDv07_nextSrcSizeToDecompress() and ZSTDv07_decompressContinue() alternatively.

ZSTDv07_nextSrcSizeToDecompress() tells how much bytes to provide as 'srcSize' to ZSTDv07_decompressContinue().

ZSTDv07_decompressContinue() requires this exact amount of bytes, or it will fail.

@result of ZSTDv07_decompressContinue() is the number of bytes regenerated within 'dst' (necessarily <= dstCapacity).

It can be zero, which is not an error; it just means ZSTDv07_decompressContinue() has decoded some header.

ZSTDv07_decompressContinue() needs previous data blocks during decompression, up to `windowSize`.

They should preferably be located contiguously, prior to current block.

Alternatively, a round buffer of sufficient size is also possible. Sufficient size is determined by frame parameters.

ZSTDv07_decompressContinue() is very sensitive to contiguity,

if 2 blocks don't follow each other, make sure that either the compressor breaks contiguity at the same place,

or that previous contiguous segment is large enough to properly handle maximum back-reference.

A frame is fully decoded when ZSTDv07_nextSrcSizeToDecompress() returns zero.

Context can then be reset to start a new decompression.

== Special case : skippable frames ==

Skippable frames allow the integration of user-defined data into a flow of concatenated frames.

Skippable frames will be ignored (skipped) by a decompressor. The format of skippable frame is following:

a) Skippable frame ID - 4 Bytes, Little endian format, any value from 0x184D2A50 to 0x184D2A5F

b) Frame Size - 4 Bytes, Little endian format, unsigned 32-bits

c) Frame Content - any content (User Data) of length equal to Frame Size

For skippable frames ZSTDv07_decompressContinue() always returns 0.

For skippable frames ZSTDv07_getFrameParams() returns fparamsPtr->windowLog==0 what means that a frame is skippable.

It also returns Frame Size as fparamsPtr->frameContentSize.

*/

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

* Block functions

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

/*! Block functions produce and decode raw zstd blocks, without frame metadata.

Frame metadata cost is typically ~18 bytes, which can be non-negligible for very small blocks (< 100 bytes).

User will have to take in charge required information to regenerate data, such as compressed and content sizes.

A few rules to respect :

- Compressing and decompressing require a context structure

+ Use ZSTDv07_createCCtx() and ZSTDv07_createDCtx()

- It is necessary to init context before starting

+ compression : ZSTDv07_compressBegin()

+ decompression : ZSTDv07_decompressBegin()

+ variants _usingDict() are also allowed

+ copyCCtx() and copyDCtx() work too

- Block size is limited, it must be <= ZSTDv07_getBlockSizeMax()

+ If you need to compress more, cut data into multiple blocks

+ Consider using the regular ZSTDv07_compress() instead, as frame metadata costs become negligible when source size is large.

- When a block is considered not compressible enough, ZSTDv07_compressBlock() result will be zero.

In which case, nothing is produced into `dst`.

+ User must test for such outcome and deal directly with uncompressed data

+ ZSTDv07_decompressBlock() doesn't accept uncompressed data as input !!!

+ In case of multiple successive blocks, decoder must be informed of uncompressed block existence to follow proper history.

Use ZSTDv07_insertBlock() in such a case.

*/

#define ZSTDv07_BLOCKSIZE_ABSOLUTEMAX (128 * 1024) /* define, for static allocation */

ZSTDLIBv07_API size_t ZSTDv07_decompressBlock(ZSTDv07_DCtx* dctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize);

ZSTDLIBv07_API size_t ZSTDv07_insertBlock(ZSTDv07_DCtx* dctx, const void* blockStart, size_t blockSize); /**< insert block into `dctx` history. Useful for uncompressed blocks */

#endif /* ZSTDv07_STATIC_LINKING_ONLY */

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

mem.h

low-level memory access routines

Copyright (C) 2013-2015, Yann Collet.

BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)

Redistribution and use in source and binary forms, with or without

modification, are permitted provided that the following conditions are

met:

* Redistributions of source code must retain the above copyright

notice, this list of conditions and the following disclaimer.

* Redistributions in binary form must reproduce the above

copyright notice, this list of conditions and the following disclaimer

in the documentation and/or other materials provided with the

distribution.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS

"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT

LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR

A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT

OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,

SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT

LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,

DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY

THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT

(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE

OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

You can contact the author at :

- FSE source repository : https://github.com/Cyan4973/FiniteStateEntropy

- Public forum : https://groups.google.com/forum/#!forum/lz4c

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

#ifndef MEM_H_MODULE

#define MEM_H_MODULE

#if defined (__cplusplus)

extern "C" {

#endif

/*-****************************************

* Compiler specifics

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

#if defined(_MSC_VER) /* Visual Studio */

# include <stdlib.h> /* _byteswap_ulong */

# include <intrin.h> /* _byteswap_* */

#endif

#if defined(__GNUC__)

# define MEM_STATIC static __attribute__((unused))

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

# define MEM_STATIC static inline

#elif defined(_MSC_VER)

# define MEM_STATIC static __inline

#else

# define MEM_STATIC static /* this version may generate warnings for unused static functions; disable the relevant warning */

#endif

/*-**************************************************************

* Basic Types

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

#if !defined (__VMS) && (defined (__cplusplus) || (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

/*-**************************************************************

* Memory I/O

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

/* MEM_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 depending on alignment.

* 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 MEM_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 MEM_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 MEM_FORCE_MEMORY_ACCESS 1

# endif

#endif

MEM_STATIC unsigned MEM_32bits(void) { return sizeof(size_t)==4; }

MEM_STATIC unsigned MEM_64bits(void) { return sizeof(size_t)==8; }

MEM_STATIC unsigned MEM_isLittleEndian(void)

{

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

return one.c[0];

}

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

/* violates C standard, by lying on structure alignment.

Only use if no other choice to achieve best performance on target platform */

MEM_STATIC U16 MEM_read16(const void* memPtr) { return *(const U16*) memPtr; }

MEM_STATIC U32 MEM_read32(const void* memPtr) { return *(const U32*) memPtr; }

MEM_STATIC U64 MEM_read64(const void* memPtr) { return *(const U64*) memPtr; }

MEM_STATIC void MEM_write16(void* memPtr, U16 value) { *(U16*)memPtr = value; }

#elif defined(MEM_FORCE_MEMORY_ACCESS) && (MEM_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; size_t st; } __attribute__((packed)) unalign;

MEM_STATIC U16 MEM_read16(const void* ptr) { return ((const unalign*)ptr)->u16; }

MEM_STATIC U32 MEM_read32(const void* ptr) { return ((const unalign*)ptr)->u32; }

MEM_STATIC U64 MEM_read64(const void* ptr) { return ((const unalign*)ptr)->u64; }

MEM_STATIC void MEM_write16(void* memPtr, U16 value) { ((unalign*)memPtr)->u16 = value; }

#else

/* default method, safe and standard.

can sometimes prove slower */

MEM_STATIC U16 MEM_read16(const void* memPtr)

{

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

}

MEM_STATIC U32 MEM_read32(const void* memPtr)

{

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

}

MEM_STATIC U64 MEM_read64(const void* memPtr)

{

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

}

MEM_STATIC void MEM_write16(void* memPtr, U16 value)

{

memcpy(memPtr, &value, sizeof(value));

}

#endif /* MEM_FORCE_MEMORY_ACCESS */

MEM_STATIC U32 MEM_swap32(U32 in)

{

#if defined(_MSC_VER) /* Visual Studio */

return _byteswap_ulong(in);

#elif defined (__GNUC__) && (__GNUC__ * 100 + __GNUC_MINOR__ >= 403)

return __builtin_bswap32(in);

#else

return ((in << 24) & 0xff000000 ) |

((in << 8) & 0x00ff0000 ) |

((in >> 8) & 0x0000ff00 ) |

((in >> 24) & 0x000000ff );

#endif

}

MEM_STATIC U64 MEM_swap64(U64 in)

{

#if defined(_MSC_VER) /* Visual Studio */

return _byteswap_uint64(in);

#elif defined (__GNUC__) && (__GNUC__ * 100 + __GNUC_MINOR__ >= 403)

return __builtin_bswap64(in);

#else

return ((in << 56) & 0xff00000000000000ULL) |

((in << 40) & 0x00ff000000000000ULL) |

((in << 24) & 0x0000ff0000000000ULL) |

((in << 8) & 0x000000ff00000000ULL) |

((in >> 8) & 0x00000000ff000000ULL) |

((in >> 24) & 0x0000000000ff0000ULL) |

((in >> 40) & 0x000000000000ff00ULL) |

((in >> 56) & 0x00000000000000ffULL);

#endif

}

/*=== Little endian r/w ===*/

MEM_STATIC U16 MEM_readLE16(const void* memPtr)

{

if (MEM_isLittleEndian())

return MEM_read16(memPtr);

else {

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

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

}

}

MEM_STATIC void MEM_writeLE16(void* memPtr, U16 val)

{

if (MEM_isLittleEndian()) {

MEM_write16(memPtr, val);

} else {

BYTE* p = (BYTE*)memPtr;

p[0] = (BYTE)val;

p[1] = (BYTE)(val>>8);

}

}

MEM_STATIC U32 MEM_readLE32(const void* memPtr)

{

if (MEM_isLittleEndian())

return MEM_read32(memPtr);

else

return MEM_swap32(MEM_read32(memPtr));

}

MEM_STATIC U64 MEM_readLE64(const void* memPtr)

{

if (MEM_isLittleEndian())

return MEM_read64(memPtr);

else

return MEM_swap64(MEM_read64(memPtr));

}

MEM_STATIC size_t MEM_readLEST(const void* memPtr)

{

if (MEM_32bits())

return (size_t)MEM_readLE32(memPtr);

else

return (size_t)MEM_readLE64(memPtr);

}

#if defined (__cplusplus)

}

#endif

#endif /* MEM_H_MODULE */

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

bitstream

Part of FSE library

header file (to include)

Copyright (C) 2013-2016, Yann Collet.

BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)

Redistribution and use in source and binary forms, with or without

modification, are permitted provided that the following conditions are

met:

* Redistributions of source code must retain the above copyright

notice, this list of conditions and the following disclaimer.

* Redistributions in binary form must reproduce the above

copyright notice, this list of conditions and the following disclaimer

in the documentation and/or other materials provided with the

distribution.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS

"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT

LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR

A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT

OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,

SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT

LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,

DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY

THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT

(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE

OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

You can contact the author at :

- Source repository : https://github.com/Cyan4973/FiniteStateEntropy

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

#ifndef BITSTREAM_H_MODULE

#define BITSTREAM_H_MODULE

#if defined (__cplusplus)

extern "C" {

#endif

/*

* This API consists of small unitary functions, which must be inlined for best performance.

* Since link-time-optimization is not available for all compilers,

* these functions are defined into a .h to be included.

*/

/*=========================================

* Target specific

=========================================*/

#if defined(__BMI__) && defined(__GNUC__)

# include <immintrin.h> /* support for bextr (experimental) */

#endif

/*-********************************************

* bitStream decoding API (read backward)

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

typedef struct

{

size_t bitContainer;

unsigned bitsConsumed;

const char* ptr;

const char* start;

} BITv07_DStream_t;

typedef enum { BITv07_DStream_unfinished = 0,

BITv07_DStream_endOfBuffer = 1,

BITv07_DStream_completed = 2,

BITv07_DStream_overflow = 3 } BITv07_DStream_status; /* result of BITv07_reloadDStream() */

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

MEM_STATIC size_t BITv07_initDStream(BITv07_DStream_t* bitD, const void* srcBuffer, size_t srcSize);

MEM_STATIC size_t BITv07_readBits(BITv07_DStream_t* bitD, unsigned nbBits);

MEM_STATIC BITv07_DStream_status BITv07_reloadDStream(BITv07_DStream_t* bitD);

MEM_STATIC unsigned BITv07_endOfDStream(const BITv07_DStream_t* bitD);

/*-****************************************

* unsafe API

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

MEM_STATIC size_t BITv07_readBitsFast(BITv07_DStream_t* bitD, unsigned nbBits);

/* faster, but works only if nbBits >= 1 */

/*-**************************************************************

* Internal functions

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

MEM_STATIC unsigned BITv07_highbit32 (U32 val)

{

# if defined(_MSC_VER) /* Visual */

unsigned long r=0;

_BitScanReverse ( &r, val );

return (unsigned) r;

# elif defined(__GNUC__) && (__GNUC__ >= 3) /* Use 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;

v |= v >> 1;

v |= v >> 2;

v |= v >> 4;

v |= v >> 8;

v |= v >> 16;

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

# endif

}

/*-********************************************************

* bitStream decoding

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

/*! BITv07_initDStream() :

* Initialize a BITv07_DStream_t.

* `bitD` : a pointer to an already allocated BITv07_DStream_t structure.

* `srcSize` must be the *exact* size of the bitStream, in bytes.

* @return : size of stream (== srcSize) or an errorCode if a problem is detected

*/

MEM_STATIC size_t BITv07_initDStream(BITv07_DStream_t* bitD, const void* srcBuffer, size_t srcSize)

{

if (srcSize < 1) { memset(bitD, 0, sizeof(*bitD)); return ERROR(srcSize_wrong); }

if (srcSize >= sizeof(bitD->bitContainer)) { /* normal case */

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

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

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

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

bitD->bitsConsumed = lastByte ? 8 - BITv07_highbit32(lastByte) : 0;

if (lastByte == 0) return ERROR(GENERIC); /* endMark not present */ }

} else {

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*)(srcBuffer))[6]) << (sizeof(bitD->bitContainer)*8 - 16);/* fall-through */

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

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

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

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

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

default: break;

}

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

bitD->bitsConsumed = lastByte ? 8 - BITv07_highbit32(lastByte) : 0;

if (lastByte == 0) return ERROR(GENERIC); /* endMark not present */ }

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

}

return srcSize;

}

MEM_STATIC size_t BITv07_lookBits(const BITv07_DStream_t* bitD, U32 nbBits)

{

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

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

}

/*! BITv07_lookBitsFast() :

* unsafe version; only works only if nbBits >= 1 */

MEM_STATIC size_t BITv07_lookBitsFast(const BITv07_DStream_t* bitD, U32 nbBits)

{

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

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

}

MEM_STATIC void BITv07_skipBits(BITv07_DStream_t* bitD, U32 nbBits)

{

bitD->bitsConsumed += nbBits;

}

MEM_STATIC size_t BITv07_readBits(BITv07_DStream_t* bitD, U32 nbBits)

{

size_t const value = BITv07_lookBits(bitD, nbBits);

BITv07_skipBits(bitD, nbBits);

return value;

}

/*! BITv07_readBitsFast() :

* unsafe version; only works only if nbBits >= 1 */

MEM_STATIC size_t BITv07_readBitsFast(BITv07_DStream_t* bitD, U32 nbBits)

{

size_t const value = BITv07_lookBitsFast(bitD, nbBits);

BITv07_skipBits(bitD, nbBits);

return value;

}

MEM_STATIC BITv07_DStream_status BITv07_reloadDStream(BITv07_DStream_t* bitD)

{

if (bitD->bitsConsumed > (sizeof(bitD->bitContainer)*8)) /* should not happen => corruption detected */

return BITv07_DStream_overflow;

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

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

bitD->bitsConsumed &= 7;

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

return BITv07_DStream_unfinished;

}

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

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

return BITv07_DStream_completed;

}

{ U32 nbBytes = bitD->bitsConsumed >> 3;

BITv07_DStream_status result = BITv07_DStream_unfinished;

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

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

result = BITv07_DStream_endOfBuffer;

}

bitD->ptr -= nbBytes;

bitD->bitsConsumed -= nbBytes*8;

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

return result;

}

}

/*! BITv07_endOfDStream() :

* @return Tells if DStream has exactly reached its end (all bits consumed).

*/

MEM_STATIC unsigned BITv07_endOfDStream(const BITv07_DStream_t* DStream)

{

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

}

#if defined (__cplusplus)

}

#endif

#endif /* BITSTREAM_H_MODULE */

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

FSE : Finite State Entropy codec

Public Prototypes declaration

Copyright (C) 2013-2016, Yann Collet.

BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)

Redistribution and use in source and binary forms, with or without

modification, are permitted provided that the following conditions are

met:

* Redistributions of source code must retain the above copyright

notice, this list of conditions and the following disclaimer.

* Redistributions in binary form must reproduce the above

copyright notice, this list of conditions and the following disclaimer

in the documentation and/or other materials provided with the

distribution.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS

"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT

LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR

A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT

OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,

SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT

LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,

DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY

THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT

(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE

OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

You can contact the author at :

- Source repository : https://github.com/Cyan4973/FiniteStateEntropy

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

#ifndef FSEv07_H

#define FSEv07_H

#if defined (__cplusplus)

extern "C" {

#endif

/*-****************************************

* FSE simple functions

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

/*! FSEv07_decompress():

Decompress FSE data from buffer 'cSrc', of size 'cSrcSize',

into already allocated destination buffer 'dst', of size 'dstCapacity'.

@return : size of regenerated data (<= maxDstSize),

or an error code, which can be tested using FSEv07_isError() .

** Important ** : FSEv07_decompress() does not decompress non-compressible nor RLE data !!!

Why ? : making this distinction requires a header.

Header management is intentionally delegated to the user layer, which can better manage special cases.

*/

size_t FSEv07_decompress(void* dst, size_t dstCapacity,

const void* cSrc, size_t cSrcSize);

/* Error Management */

unsigned FSEv07_isError(size_t code); /* tells if a return value is an error code */

const char* FSEv07_getErrorName(size_t code); /* provides error code string (useful for debugging) */

/*-*****************************************

* FSE detailed API

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

/*!

FSEv07_decompress() does the following:

1. read normalized counters with readNCount()

2. build decoding table 'DTable' from normalized counters

3. decode the data stream using decoding table 'DTable'

The following API allows targeting specific sub-functions for advanced tasks.

For example, it's possible to compress several blocks using the same 'CTable',

or to save and provide normalized distribution using external method.

*/

/* *** DECOMPRESSION *** */

/*! FSEv07_readNCount():

Read compactly saved 'normalizedCounter' from 'rBuffer'.

@return : size read from 'rBuffer',

or an errorCode, which can be tested using FSEv07_isError().

maxSymbolValuePtr[0] and tableLogPtr[0] will also be updated with their respective values */

size_t FSEv07_readNCount (short* normalizedCounter, unsigned* maxSymbolValuePtr, unsigned* tableLogPtr, const void* rBuffer, size_t rBuffSize);

/*! Constructor and Destructor of FSEv07_DTable.

Note that its size depends on 'tableLog' */

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

FSEv07_DTable* FSEv07_createDTable(unsigned tableLog);

void FSEv07_freeDTable(FSEv07_DTable* dt);

/*! FSEv07_buildDTable():

Builds 'dt', which must be already allocated, using FSEv07_createDTable().

return : 0, or an errorCode, which can be tested using FSEv07_isError() */

size_t FSEv07_buildDTable (FSEv07_DTable* dt, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog);

/*! FSEv07_decompress_usingDTable():

Decompress compressed source `cSrc` of size `cSrcSize` using `dt`

into `dst` which must be already allocated.

@return : size of regenerated data (necessarily <= `dstCapacity`),

or an errorCode, which can be tested using FSEv07_isError() */

size_t FSEv07_decompress_usingDTable(void* dst, size_t dstCapacity, const void* cSrc, size_t cSrcSize, const FSEv07_DTable* dt);

/*!

Tutorial :

----------

(Note : these functions only decompress FSE-compressed blocks.

If block is uncompressed, use memcpy() instead

If block is a single repeated byte, use memset() instead )

The first step is to obtain the normalized frequencies of symbols.

This can be performed by FSEv07_readNCount() if it was saved using FSEv07_writeNCount().

'normalizedCounter' must be already allocated, and have at least 'maxSymbolValuePtr[0]+1' cells of signed short.

In practice, that means it's necessary to know 'maxSymbolValue' beforehand,

or size the table to handle worst case situations (typically 256).

FSEv07_readNCount() will provide 'tableLog' and 'maxSymbolValue'.

The result of FSEv07_readNCount() is the number of bytes read from 'rBuffer'.

Note that 'rBufferSize' must be at least 4 bytes, even if useful information is less than that.

If there is an error, the function will return an error code, which can be tested using FSEv07_isError().

The next step is to build the decompression tables 'FSEv07_DTable' from 'normalizedCounter'.

This is performed by the function FSEv07_buildDTable().

The space required by 'FSEv07_DTable' must be already allocated using FSEv07_createDTable().

If there is an error, the function will return an error code, which can be tested using FSEv07_isError().

`FSEv07_DTable` can then be used to decompress `cSrc`, with FSEv07_decompress_usingDTable().

`cSrcSize` must be strictly correct, otherwise decompression will fail.

FSEv07_decompress_usingDTable() result will tell how many bytes were regenerated (<=`dstCapacity`).

If there is an error, the function will return an error code, which can be tested using FSEv07_isError(). (ex: dst buffer too small)

*/

#ifdef FSEv07_STATIC_LINKING_ONLY

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

* Static allocation

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

/* FSE buffer bounds */

#define FSEv07_NCOUNTBOUND 512

#define FSEv07_BLOCKBOUND(size) (size + (size>>7))

/* It is possible to statically allocate FSE CTable/DTable as a table of unsigned using below macros */

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

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

* FSE advanced API

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

size_t FSEv07_countFast(unsigned* count, unsigned* maxSymbolValuePtr, const void* src, size_t srcSize);

/**< same as FSEv07_count(), but blindly trusts that all byte values within src are <= *maxSymbolValuePtr */

unsigned FSEv07_optimalTableLog_internal(unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue, unsigned minus);

/**< same as FSEv07_optimalTableLog(), which used `minus==2` */

size_t FSEv07_buildDTable_raw (FSEv07_DTable* dt, unsigned nbBits);

/**< build a fake FSEv07_DTable, designed to read an uncompressed bitstream where each symbol uses nbBits */

size_t FSEv07_buildDTable_rle (FSEv07_DTable* dt, unsigned char symbolValue);

/**< build a fake FSEv07_DTable, designed to always generate the same symbolValue */

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

* FSE symbol decompression API

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

typedef struct

{

size_t state;

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

} FSEv07_DState_t;

static void FSEv07_initDState(FSEv07_DState_t* DStatePtr, BITv07_DStream_t* bitD, const FSEv07_DTable* dt);

static unsigned char FSEv07_decodeSymbol(FSEv07_DState_t* DStatePtr, BITv07_DStream_t* bitD);

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

* FSE unsafe API

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

static unsigned char FSEv07_decodeSymbolFast(FSEv07_DState_t* DStatePtr, BITv07_DStream_t* bitD);

/* faster, but works only if nbBits is always >= 1 (otherwise, result will be corrupted) */

/* ====== Decompression ====== */

typedef struct {

U16 tableLog;

U16 fastMode;

} FSEv07_DTableHeader; /* sizeof U32 */

typedef struct

{

unsigned short newState;

unsigned char symbol;

unsigned char nbBits;

} FSEv07_decode_t; /* size == U32 */

MEM_STATIC void FSEv07_initDState(FSEv07_DState_t* DStatePtr, BITv07_DStream_t* bitD, const FSEv07_DTable* dt)

{

const void* ptr = dt;

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

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

BITv07_reloadDStream(bitD);

DStatePtr->table = dt + 1;

}

MEM_STATIC BYTE FSEv07_peekSymbol(const FSEv07_DState_t* DStatePtr)

{

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

return DInfo.symbol;

}

MEM_STATIC void FSEv07_updateState(FSEv07_DState_t* DStatePtr, BITv07_DStream_t* bitD)

{

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

U32 const nbBits = DInfo.nbBits;

size_t const lowBits = BITv07_readBits(bitD, nbBits);

DStatePtr->state = DInfo.newState + lowBits;

}

MEM_STATIC BYTE FSEv07_decodeSymbol(FSEv07_DState_t* DStatePtr, BITv07_DStream_t* bitD)

{

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

U32 const nbBits = DInfo.nbBits;

BYTE const symbol = DInfo.symbol;

size_t const lowBits = BITv07_readBits(bitD, nbBits);

DStatePtr->state = DInfo.newState + lowBits;

return symbol;

}

/*! FSEv07_decodeSymbolFast() :

unsafe, only works if no symbol has a probability > 50% */

MEM_STATIC BYTE FSEv07_decodeSymbolFast(FSEv07_DState_t* DStatePtr, BITv07_DStream_t* bitD)

{

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

U32 const nbBits = DInfo.nbBits;

BYTE const symbol = DInfo.symbol;

size_t const lowBits = BITv07_readBitsFast(bitD, nbBits);

DStatePtr->state = DInfo.newState + lowBits;

return symbol;

}

#ifndef FSEv07_COMMONDEFS_ONLY

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

* 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 FSEv07_MAX_MEMORY_USAGE 14

#define FSEv07_DEFAULT_MEMORY_USAGE 13

/*!FSEv07_MAX_SYMBOL_VALUE :

* Maximum symbol value authorized.

* Required for proper stack allocation */

#define FSEv07_MAX_SYMBOL_VALUE 255

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

* template functions type & suffix

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

#define FSEv07_FUNCTION_TYPE BYTE

#define FSEv07_FUNCTION_EXTENSION

#define FSEv07_DECODE_TYPE FSEv07_decode_t

#endif /* !FSEv07_COMMONDEFS_ONLY */

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

* Constants

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

#define FSEv07_MAX_TABLELOG (FSEv07_MAX_MEMORY_USAGE-2)

#define FSEv07_MAX_TABLESIZE (1U<<FSEv07_MAX_TABLELOG)

#define FSEv07_MAXTABLESIZE_MASK (FSEv07_MAX_TABLESIZE-1)

#define FSEv07_DEFAULT_TABLELOG (FSEv07_DEFAULT_MEMORY_USAGE-2)

#define FSEv07_MIN_TABLELOG 5

#define FSEv07_TABLELOG_ABSOLUTE_MAX 15

#if FSEv07_MAX_TABLELOG > FSEv07_TABLELOG_ABSOLUTE_MAX

# error "FSEv07_MAX_TABLELOG > FSEv07_TABLELOG_ABSOLUTE_MAX is not supported"

#endif

#define FSEv07_TABLESTEP(tableSize) ((tableSize>>1) + (tableSize>>3) + 3)

#endif /* FSEv07_STATIC_LINKING_ONLY */

#if defined (__cplusplus)

}

#endif

#endif /* FSEv07_H */

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

Huffman coder, part of New Generation Entropy library

header file

Copyright (C) 2013-2016, Yann Collet.

BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)

Redistribution and use in source and binary forms, with or without

modification, are permitted provided that the following conditions are

met:

* Redistributions of source code must retain the above copyright

notice, this list of conditions and the following disclaimer.

* Redistributions in binary form must reproduce the above

copyright notice, this list of conditions and the following disclaimer

in the documentation and/or other materials provided with the

distribution.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS

"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT

LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR

A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT

OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,

SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT

LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,