/*

* 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 "zstd_v05.h"

#include "error_private.h"

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

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 :

- FSEv05 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

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

* Dependencies

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

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

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

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

* Compiler specifics

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

#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 (__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(void*)==4; }

MEM_STATIC unsigned MEM_64bits(void) { return sizeof(void*)==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; }

MEM_STATIC void MEM_write32(void* memPtr, U32 value) { *(U32*)memPtr = value; }

MEM_STATIC void MEM_write64(void* memPtr, U64 value) { *(U64*)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; }

MEM_STATIC void MEM_write32(void* memPtr, U32 value) { ((unalign*)memPtr)->u32 = value; }

MEM_STATIC void MEM_write64(void* memPtr, U64 value) { ((unalign*)memPtr)->u64 = 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));

}

MEM_STATIC void MEM_write32(void* memPtr, U32 value)

{

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

}

MEM_STATIC void MEM_write64(void* memPtr, U64 value)

{

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

}

#endif /* MEM_FORCE_MEMORY_ACCESS */

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 {

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

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

}

}

MEM_STATIC U64 MEM_readLE64(const void* memPtr)

{

if (MEM_isLittleEndian())

return MEM_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));

}

}

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

/*

zstd - standard compression library

Header File for static linking only

Copyright (C) 2014-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 :

- zstd homepage : http://www.zstd.net

*/

#ifndef ZSTD_STATIC_H

#define ZSTD_STATIC_H

/* The prototypes defined within this file are considered experimental.

* They should not be used in the context DLL as they may change in the future.

* Prefer static linking if you need them, to control breaking version changes issues.

*/

#if defined (__cplusplus)

extern "C" {

#endif

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

* Types

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

#define ZSTDv05_WINDOWLOG_ABSOLUTEMIN 11

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

* Advanced functions

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

/*- Advanced Decompression functions -*/

/*! ZSTDv05_decompress_usingPreparedDCtx() :

* Same as ZSTDv05_decompress_usingDict, but using a reference context `preparedDCtx`, where dictionary has been loaded.

* It avoids reloading the dictionary each time.

* `preparedDCtx` must have been properly initialized using ZSTDv05_decompressBegin_usingDict().

* Requires 2 contexts : 1 for reference, which will not be modified, and 1 to run the decompression operation */

size_t ZSTDv05_decompress_usingPreparedDCtx(

ZSTDv05_DCtx* dctx, const ZSTDv05_DCtx* preparedDCtx,

void* dst, size_t dstCapacity,

const void* src, size_t srcSize);

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

* Streaming functions (direct mode)

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

size_t ZSTDv05_decompressBegin(ZSTDv05_DCtx* dctx);

/*

Streaming decompression, direct mode (bufferless)

A ZSTDv05_DCtx object is required to track streaming operations.

Use ZSTDv05_createDCtx() / ZSTDv05_freeDCtx() to manage it.

A ZSTDv05_DCtx object can be re-used multiple times.

First typical operation is to retrieve frame parameters, using ZSTDv05_getFrameParams().

This operation is independent, and just needs enough input data to properly decode the frame header.

Objective is to retrieve *params.windowlog, to know minimum amount of memory required during decoding.

Result : 0 when successful, it means the ZSTDv05_parameters 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 ZSTDv05_isError()

Start decompression, with ZSTDv05_decompressBegin() or ZSTDv05_decompressBegin_usingDict()

Alternatively, you can copy a prepared context, using ZSTDv05_copyDCtx()

Then use ZSTDv05_nextSrcSizeToDecompress() and ZSTDv05_decompressContinue() alternatively.

ZSTDv05_nextSrcSizeToDecompress() tells how much bytes to provide as 'srcSize' to ZSTDv05_decompressContinue().

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

ZSTDv05_decompressContinue() needs previous data blocks during decompression, up to (1 << windowlog).

They should preferably be located contiguously, prior to current block. Alternatively, a round buffer is also possible.

@result of ZSTDv05_decompressContinue() is the number of bytes regenerated within 'dst'.

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

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

Context can then be reset to start a new decompression.

*/

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

* Block functions

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

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

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

A few rules to respect :

- Uncompressed block size must be <= 128 KB

- Compressing or decompressing requires a context structure

+ Use ZSTDv05_createCCtx() and ZSTDv05_createDCtx()

- It is necessary to init context before starting

+ compression : ZSTDv05_compressBegin()

+ decompression : ZSTDv05_decompressBegin()

+ variants _usingDict() are also allowed

+ copyCCtx() and copyDCtx() work too

- When a block is considered not compressible enough, ZSTDv05_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

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

*/

size_t ZSTDv05_decompressBlock(ZSTDv05_DCtx* dctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize);

#if defined (__cplusplus)

}

#endif

#endif /* ZSTDv05_STATIC_H */

/*

zstd_internal - common functions to include

Header File for include

Copyright (C) 2014-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 :

- zstd source repository : https://github.com/Cyan4973/zstd

*/

#ifndef ZSTD_CCOMMON_H_MODULE

#define ZSTD_CCOMMON_H_MODULE

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

* Common macros

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

#define MIN(a,b) ((a)<(b) ? (a) : (b))

#define MAX(a,b) ((a)>(b) ? (a) : (b))

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

* Common constants

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

#define ZSTDv05_DICT_MAGIC 0xEC30A435

#define KB *(1 <<10)

#define MB *(1 <<20)

#define GB *(1U<<30)

#define BLOCKSIZE (128 KB) /* define, for static allocation */

static const size_t ZSTDv05_blockHeaderSize = 3;

static const size_t ZSTDv05_frameHeaderSize_min = 5;

#define ZSTDv05_frameHeaderSize_max 5 /* define, for static allocation */

#define BITv057 128

#define BITv056 64

#define BITv055 32

#define BITv054 16

#define BITv051 2

#define BITv050 1

#define IS_HUFv05 0

#define IS_PCH 1

#define IS_RAW 2

#define IS_RLE 3

#define MINMATCH 4

#define REPCODE_STARTVALUE 1

#define Litbits 8

#define MLbits 7

#define LLbits 6

#define Offbits 5

#define MaxLit ((1<<Litbits) - 1)

#define MaxML ((1<<MLbits) - 1)

#define MaxLL ((1<<LLbits) - 1)

#define MaxOff ((1<<Offbits)- 1)

#define MLFSEv05Log 10

#define LLFSEv05Log 10

#define OffFSEv05Log 9

#define MaxSeq MAX(MaxLL, MaxML)

#define FSEv05_ENCODING_RAW 0

#define FSEv05_ENCODING_RLE 1

#define FSEv05_ENCODING_STATIC 2

#define FSEv05_ENCODING_DYNAMIC 3

#define HufLog 12

#define MIN_SEQUENCES_SIZE 1 /* nbSeq==0 */

#define MIN_CBLOCK_SIZE (1 /*litCSize*/ + 1 /* RLE or RAW */ + MIN_SEQUENCES_SIZE /* nbSeq==0 */) /* for a non-null block */

#define WILDCOPY_OVERLENGTH 8

typedef enum { bt_compressed, bt_raw, bt_rle, bt_end } blockType_t;

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

* Shared functions to include for inlining

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

static void ZSTDv05_copy8(void* dst, const void* src) { memcpy(dst, src, 8); }

#define COPY8(d,s) { ZSTDv05_copy8(d,s); d+=8; s+=8; }

/*! ZSTDv05_wildcopy() :

* custom version of memcpy(), can copy up to 7 bytes too many (8 bytes if length==0) */

MEM_STATIC void ZSTDv05_wildcopy(void* dst, const void* src, ptrdiff_t length)

{

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

BYTE* op = (BYTE*)dst;

BYTE* const oend = op + length;

do

COPY8(op, ip)

while (op < oend);

}

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

* Private interfaces

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

typedef struct {

void* buffer;

U32* offsetStart;

U32* offset;

BYTE* offCodeStart;

BYTE* offCode;

BYTE* litStart;

BYTE* lit;

BYTE* litLengthStart;

BYTE* litLength;

BYTE* matchLengthStart;

BYTE* matchLength;

BYTE* dumpsStart;

BYTE* dumps;

/* opt */

U32* matchLengthFreq;

U32* litLengthFreq;

U32* litFreq;

U32* offCodeFreq;

U32 matchLengthSum;

U32 litLengthSum;

U32 litSum;

U32 offCodeSum;

} seqStore_t;

#endif /* ZSTDv05_CCOMMON_H_MODULE */

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

FSEv05 : Finite State Entropy coder

header file

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 :

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

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

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

#ifndef FSEv05_H

#define FSEv05_H

#if defined (__cplusplus)

extern "C" {

#endif

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

* Includes

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

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

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

* FSEv05 simple functions

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

size_t FSEv05_decompress(void* dst, size_t maxDstSize,

const void* cSrc, size_t cSrcSize);

/*!

FSEv05_decompress():

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

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

return : size of regenerated data (<= maxDstSize)

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

** Important ** : FSEv05_decompress() doesn't 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.

*/

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

* Tool functions

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

/* Error Management */

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

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

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

* FSEv05 detailed API

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

/* *** DECOMPRESSION *** */

/*!

FSEv05_readNCount():

Read compactly saved 'normalizedCounter' from 'rBuffer'.

return : size read from 'rBuffer'

or an errorCode, which can be tested using FSEv05_isError()

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

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

/*!

Constructor and Destructor of type FSEv05_DTable

Note that its size depends on 'tableLog' */

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

FSEv05_DTable* FSEv05_createDTable(unsigned tableLog);

void FSEv05_freeDTable(FSEv05_DTable* dt);

/*!

FSEv05_buildDTable():

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

@return : 0,

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

size_t FSEv05_buildDTable (FSEv05_DTable* dt, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog);

/*!

FSEv05_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 FSEv05_isError() */

size_t FSEv05_decompress_usingDTable(void* dst, size_t dstCapacity, const void* cSrc, size_t cSrcSize, const FSEv05_DTable* dt);

#if defined (__cplusplus)

}

#endif

#endif /* FSEv05_H */

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

bitstream

Part of FSEv05 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 BITv05STREAM_H_MODULE

#define BITv05STREAM_H_MODULE

#if defined (__cplusplus)

extern "C" {

#endif

/*

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

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

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

*/

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

* bitStream decoding API (read backward)

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

typedef struct

{

size_t bitContainer;

unsigned bitsConsumed;

const char* ptr;

const char* start;

} BITv05_DStream_t;

typedef enum { BITv05_DStream_unfinished = 0,

BITv05_DStream_endOfBuffer = 1,

BITv05_DStream_completed = 2,

BITv05_DStream_overflow = 3 } BITv05_DStream_status; /* result of BITv05_reloadDStream() */

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

MEM_STATIC size_t BITv05_initDStream(BITv05_DStream_t* bitD, const void* srcBuffer, size_t srcSize);

MEM_STATIC size_t BITv05_readBits(BITv05_DStream_t* bitD, unsigned nbBits);

MEM_STATIC BITv05_DStream_status BITv05_reloadDStream(BITv05_DStream_t* bitD);

MEM_STATIC unsigned BITv05_endOfDStream(const BITv05_DStream_t* bitD);

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

* unsafe API

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

MEM_STATIC size_t BITv05_readBitsFast(BITv05_DStream_t* bitD, unsigned nbBits);

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

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

* Helper functions

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

MEM_STATIC unsigned BITv05_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;

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

}

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

* bitStream decoding

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

/*!BITv05_initDStream

* Initialize a BITv05_DStream_t.

* @bitD : a pointer to an already allocated BITv05_DStream_t structure

* @srcBuffer must point at the beginning of a bitStream

* @srcSize must be the exact size of the bitStream

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

*/

MEM_STATIC size_t BITv05_initDStream(BITv05_DStream_t* bitD, const void* srcBuffer, size_t srcSize)

{

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

if (srcSize >= sizeof(size_t)) { /* normal case */

U32 contain32;

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

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

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

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

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

bitD->bitsConsumed = 8 - BITv05_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);/* fall-through */

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

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

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

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

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

default: break;

}

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

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

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

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

}

return srcSize;

}

MEM_STATIC size_t BITv05_lookBits(BITv05_DStream_t* bitD, U32 nbBits)

{

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

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

}

/*! BITv05_lookBitsFast :

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

MEM_STATIC size_t BITv05_lookBitsFast(BITv05_DStream_t* bitD, U32 nbBits)

{

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

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

}

MEM_STATIC void BITv05_skipBits(BITv05_DStream_t* bitD, U32 nbBits)

{

bitD->bitsConsumed += nbBits;

}

MEM_STATIC size_t BITv05_readBits(BITv05_DStream_t* bitD, U32 nbBits)

{

size_t value = BITv05_lookBits(bitD, nbBits);

BITv05_skipBits(bitD, nbBits);

return value;

}

/*!BITv05_readBitsFast :

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

MEM_STATIC size_t BITv05_readBitsFast(BITv05_DStream_t* bitD, U32 nbBits)

{

size_t value = BITv05_lookBitsFast(bitD, nbBits);

BITv05_skipBits(bitD, nbBits);

return value;

}

MEM_STATIC BITv05_DStream_status BITv05_reloadDStream(BITv05_DStream_t* bitD)

{

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

return BITv05_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 BITv05_DStream_unfinished;

}

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

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

return BITv05_DStream_completed;

}

{

U32 nbBytes = bitD->bitsConsumed >> 3;

BITv05_DStream_status result = BITv05_DStream_unfinished;

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

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

result = BITv05_DStream_endOfBuffer;

}

bitD->ptr -= nbBytes;

bitD->bitsConsumed -= nbBytes*8;

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

return result;

}

}

/*! BITv05_endOfDStream

* @return Tells if DStream has reached its exact end

*/

MEM_STATIC unsigned BITv05_endOfDStream(const BITv05_DStream_t* DStream)

{

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

}

#if defined (__cplusplus)

}

#endif

#endif /* BITv05STREAM_H_MODULE */

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

FSEv05 : Finite State Entropy coder

header file for static linking (only)

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 :

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

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

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

#ifndef FSEv05_STATIC_H

#define FSEv05_STATIC_H

#if defined (__cplusplus)

extern "C" {

#endif

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

* Static allocation

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

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

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

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

* FSEv05 advanced API

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

size_t FSEv05_buildDTable_raw (FSEv05_DTable* dt, unsigned nbBits);

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

size_t FSEv05_buildDTable_rle (FSEv05_DTable* dt, unsigned char symbolValue);

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

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

* FSEv05 symbol decompression API

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

typedef struct

{

size_t state;

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

} FSEv05_DState_t;

static void FSEv05_initDState(FSEv05_DState_t* DStatePtr, BITv05_DStream_t* bitD, const FSEv05_DTable* dt);

static unsigned char FSEv05_decodeSymbol(FSEv05_DState_t* DStatePtr, BITv05_DStream_t* bitD);

static unsigned FSEv05_endOfDState(const FSEv05_DState_t* DStatePtr);

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

* FSEv05 unsafe API

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

static unsigned char FSEv05_decodeSymbolFast(FSEv05_DState_t* DStatePtr, BITv05_DStream_t* bitD);

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

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

* Implementation of inlined functions

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

/* decompression */

typedef struct {

U16 tableLog;

U16 fastMode;

} FSEv05_DTableHeader; /* sizeof U32 */

typedef struct

{

unsigned short newState;

unsigned char symbol;

unsigned char nbBits;

} FSEv05_decode_t; /* size == U32 */

MEM_STATIC void FSEv05_initDState(FSEv05_DState_t* DStatePtr, BITv05_DStream_t* bitD, const FSEv05_DTable* dt)