/**

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

 * All rights reserved.

 *

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

 * LICENSE file in the root directory of this source tree. An additional grant

 * of patent rights can be found in the PATENTS file in the same directory.

 */

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

*  Tuning parameters

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

/*!

 * HEAPMODE :

 * Select how default decompression function ZSTD_decompress() will allocate memory,

 * in memory stack (0), or in memory heap (1, requires malloc())

 */

#ifndef ZSTD_HEAPMODE

#  define ZSTD_HEAPMODE 1

#endif

/*!

*  LEGACY_SUPPORT :

*  if set to 1, ZSTD_decompress() can decode older formats (v0.1+)

*/

#ifndef ZSTD_LEGACY_SUPPORT

#  define ZSTD_LEGACY_SUPPORT 0

#endif

/*!

*  MAXWINDOWSIZE_DEFAULT :

*  maximum window size accepted by DStream, by default.

*  Frames requiring more memory will be rejected.

*/

#ifndef ZSTD_MAXWINDOWSIZE_DEFAULT

#  define ZSTD_MAXWINDOWSIZE_DEFAULT ((1 << ZSTD_WINDOWLOG_MAX) + 1)   /* defined within zstd.h */

#endif

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

*  Dependencies

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

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

#include "mem.h"         /* low level memory routines */

#define XXH_STATIC_LINKING_ONLY   /* XXH64_state_t */

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

#define FSE_STATIC_LINKING_ONLY

#include "fse.h"

#define HUF_STATIC_LINKING_ONLY

#include "huf.h"

#include "zstd_internal.h"

#if defined(ZSTD_LEGACY_SUPPORT) && (ZSTD_LEGACY_SUPPORT>=1)

#  include "zstd_legacy.h"

#endif

#if defined(_MSC_VER)

#  include <mmintrin.h>   /* https://msdn.microsoft.com/fr-fr/library/84szxsww(v=vs.90).aspx */

#  define ZSTD_PREFETCH(ptr)   _mm_prefetch((const char*)ptr, _MM_HINT_T0)

#elif defined(__GNUC__)

#  define ZSTD_PREFETCH(ptr)   __builtin_prefetch(ptr, 0, 0)

#else

#  define ZSTD_PREFETCH(ptr)   /* disabled */

#endif

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

*  Macros

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

#define ZSTD_isError ERR_isError   /* for inlining */

#define FSE_isError  ERR_isError

#define HUF_isError  ERR_isError

/*_*******************************************************

*  Memory operations

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

static void ZSTD_copy4(void* dst, const void* src) { memcpy(dst, src, 4); }

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

*   Context management

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

typedef enum { ZSTDds_getFrameHeaderSize, ZSTDds_decodeFrameHeader,

               ZSTDds_decodeBlockHeader, ZSTDds_decompressBlock,

               ZSTDds_decompressLastBlock, ZSTDds_checkChecksum,

               ZSTDds_decodeSkippableHeader, ZSTDds_skipFrame } ZSTD_dStage;

struct ZSTD_DCtx_s

{

    const FSE_DTable* LLTptr;

    const FSE_DTable* MLTptr;

    const FSE_DTable* OFTptr;

    const HUF_DTable* HUFptr;

    FSE_DTable LLTable[FSE_DTABLE_SIZE_U32(LLFSELog)];

    FSE_DTable OFTable[FSE_DTABLE_SIZE_U32(OffFSELog)];

    FSE_DTable MLTable[FSE_DTABLE_SIZE_U32(MLFSELog)];

    HUF_DTable hufTable[HUF_DTABLE_SIZE(HufLog)];  /* can accommodate HUF_decompress4X */

    const void* previousDstEnd;

    const void* base;

    const void* vBase;

    const void* dictEnd;

    size_t expected;

    U32 rep[ZSTD_REP_NUM];

    ZSTD_frameParams fParams;

    blockType_e bType;   /* used in ZSTD_decompressContinue(), to transfer blockType between header decoding and block decoding stages */

    ZSTD_dStage stage;

    U32 litEntropy;

    U32 fseEntropy;

    XXH64_state_t xxhState;

    size_t headerSize;

    U32 dictID;

    const BYTE* litPtr;

    ZSTD_customMem customMem;

    size_t litSize;

    size_t rleSize;

    BYTE litBuffer[ZSTD_BLOCKSIZE_ABSOLUTEMAX + WILDCOPY_OVERLENGTH];

    BYTE headerBuffer[ZSTD_FRAMEHEADERSIZE_MAX];

};  /* typedef'd to ZSTD_DCtx within "zstd.h" */

size_t ZSTD_sizeof_DCtx (const ZSTD_DCtx* dctx) { return (dctx==NULL) ? 0 : sizeof(ZSTD_DCtx); }

size_t ZSTD_estimateDCtxSize(void) { return sizeof(ZSTD_DCtx); }

size_t ZSTD_decompressBegin(ZSTD_DCtx* dctx)

{

    dctx->expected = ZSTD_frameHeaderSize_prefix;

    dctx->stage = ZSTDds_getFrameHeaderSize;

    dctx->previousDstEnd = NULL;

    dctx->base = NULL;

    dctx->vBase = NULL;

    dctx->dictEnd = NULL;

    dctx->hufTable[0] = (HUF_DTable)((HufLog)*0x1000001);  /* cover both little and big endian */

    dctx->litEntropy = dctx->fseEntropy = 0;

    dctx->dictID = 0;

    MEM_STATIC_ASSERT(sizeof(dctx->rep) == sizeof(repStartValue));

    memcpy(dctx->rep, repStartValue, sizeof(repStartValue));  /* initial repcodes */

    dctx->LLTptr = dctx->LLTable;

    dctx->MLTptr = dctx->MLTable;

    dctx->OFTptr = dctx->OFTable;

    dctx->HUFptr = dctx->hufTable;

    return 0;

}

ZSTD_DCtx* ZSTD_createDCtx_advanced(ZSTD_customMem customMem)

{

    ZSTD_DCtx* dctx;

    if (!customMem.customAlloc && !customMem.customFree) customMem = defaultCustomMem;

    if (!customMem.customAlloc || !customMem.customFree) return NULL;

    dctx = (ZSTD_DCtx*)ZSTD_malloc(sizeof(ZSTD_DCtx), customMem);

    if (!dctx) return NULL;

    memcpy(&dctx->customMem, &customMem, sizeof(customMem));

    ZSTD_decompressBegin(dctx);

    return dctx;

}

ZSTD_DCtx* ZSTD_createDCtx(void)

{

    return ZSTD_createDCtx_advanced(defaultCustomMem);

}

size_t ZSTD_freeDCtx(ZSTD_DCtx* dctx)

{

    if (dctx==NULL) return 0;   /* support free on NULL */

    ZSTD_free(dctx, dctx->customMem);

    return 0;   /* reserved as a potential error code in the future */

}

void ZSTD_copyDCtx(ZSTD_DCtx* dstDCtx, const ZSTD_DCtx* srcDCtx)

{

    size_t const workSpaceSize = (ZSTD_BLOCKSIZE_ABSOLUTEMAX+WILDCOPY_OVERLENGTH) + ZSTD_frameHeaderSize_max;

    memcpy(dstDCtx, srcDCtx, sizeof(ZSTD_DCtx) - workSpaceSize);  /* no need to copy workspace */

}

static void ZSTD_refDCtx(ZSTD_DCtx* dstDCtx, const ZSTD_DCtx* srcDCtx)

{

    ZSTD_decompressBegin(dstDCtx);  /* init */

    if (srcDCtx) {   /* support refDCtx on NULL */

        dstDCtx->dictEnd = srcDCtx->dictEnd;

        dstDCtx->vBase = srcDCtx->vBase;

        dstDCtx->base = srcDCtx->base;

        dstDCtx->previousDstEnd = srcDCtx->previousDstEnd;

        dstDCtx->dictID = srcDCtx->dictID;

        dstDCtx->litEntropy = srcDCtx->litEntropy;

        dstDCtx->fseEntropy = srcDCtx->fseEntropy;

        dstDCtx->LLTptr = srcDCtx->LLTable;

        dstDCtx->MLTptr = srcDCtx->MLTable;

        dstDCtx->OFTptr = srcDCtx->OFTable;

        dstDCtx->HUFptr = srcDCtx->hufTable;

        dstDCtx->rep[0] = srcDCtx->rep[0];

        dstDCtx->rep[1] = srcDCtx->rep[1];

        dstDCtx->rep[2] = srcDCtx->rep[2];

    }

}

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

*   Decompression section

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

/*! ZSTD_isFrame() :

 *  Tells if the content of `buffer` starts with a valid Frame Identifier.

 *  Note : Frame Identifier is 4 bytes. If `size < 4`, @return will always be 0.

 *  Note 2 : Legacy Frame Identifiers are considered valid only if Legacy Support is enabled.

 *  Note 3 : Skippable Frame Identifiers are considered valid. */

unsigned ZSTD_isFrame(const void* buffer, size_t size)

{

    if (size < 4) return 0;

    {   U32 const magic = MEM_readLE32(buffer);

        if (magic == ZSTD_MAGICNUMBER) return 1;

        if ((magic & 0xFFFFFFF0U) == ZSTD_MAGIC_SKIPPABLE_START) return 1;

    }

#if defined(ZSTD_LEGACY_SUPPORT) && (ZSTD_LEGACY_SUPPORT >= 1)

    if (ZSTD_isLegacy(buffer, size)) return 1;

#endif

    return 0;

}

/** ZSTD_frameHeaderSize() :

*   srcSize must be >= ZSTD_frameHeaderSize_prefix.

*   @return : size of the Frame Header */

static size_t ZSTD_frameHeaderSize(const void* src, size_t srcSize)

{

    if (srcSize < ZSTD_frameHeaderSize_prefix) return ERROR(srcSize_wrong);

    {   BYTE const fhd = ((const BYTE*)src)[4];

        U32 const dictID= fhd & 3;

        U32 const singleSegment = (fhd >> 5) & 1;

        U32 const fcsId = fhd >> 6;

        return ZSTD_frameHeaderSize_prefix + !singleSegment + ZSTD_did_fieldSize[dictID] + ZSTD_fcs_fieldSize[fcsId]

                + (singleSegment && !fcsId);

    }

}

/** ZSTD_getFrameParams() :

*   decode Frame Header, or require larger `srcSize`.

*   @return : 0, `fparamsPtr` is correctly filled,

*            >0, `srcSize` is too small, result is expected `srcSize`,

*             or an error code, which can be tested using ZSTD_isError() */

size_t ZSTD_getFrameParams(ZSTD_frameParams* fparamsPtr, const void* src, size_t srcSize)

{

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

    if (srcSize < ZSTD_frameHeaderSize_prefix) return ZSTD_frameHeaderSize_prefix;

    if (MEM_readLE32(src) != ZSTD_MAGICNUMBER) {

        if ((MEM_readLE32(src) & 0xFFFFFFF0U) == ZSTD_MAGIC_SKIPPABLE_START) {

            if (srcSize < ZSTD_skippableHeaderSize) return ZSTD_skippableHeaderSize; /* magic number + skippable frame length */

            memset(fparamsPtr, 0, sizeof(*fparamsPtr));

            fparamsPtr->frameContentSize = MEM_readLE32((const char *)src + 4);

            fparamsPtr->windowSize = 0; /* windowSize==0 means a frame is skippable */

            return 0;

        }

        return ERROR(prefix_unknown);

    }

    /* ensure there is enough `srcSize` to fully read/decode frame header */

    { size_t const fhsize = ZSTD_frameHeaderSize(src, srcSize);

      if (srcSize < fhsize) return fhsize; }

    {   BYTE const fhdByte = ip[4];

        size_t pos = 5;

        U32 const dictIDSizeCode = fhdByte&3;

        U32 const checksumFlag = (fhdByte>>2)&1;

        U32 const singleSegment = (fhdByte>>5)&1;

        U32 const fcsID = fhdByte>>6;

        U32 const windowSizeMax = 1U << ZSTD_WINDOWLOG_MAX;

        U32 windowSize = 0;

        U32 dictID = 0;

        U64 frameContentSize = 0;

        if ((fhdByte & 0x08) != 0) return ERROR(frameParameter_unsupported);   /* reserved bits, which must be zero */

        if (!singleSegment) {

            BYTE const wlByte = ip[pos++];

            U32 const windowLog = (wlByte >> 3) + ZSTD_WINDOWLOG_ABSOLUTEMIN;

            if (windowLog > ZSTD_WINDOWLOG_MAX) return ERROR(frameParameter_windowTooLarge);  /* avoids issue with 1 << windowLog */

            windowSize = (1U << windowLog);

            windowSize += (windowSize >> 3) * (wlByte&7);

        }

        switch(dictIDSizeCode)

        {

            default:   /* impossible */

            case 0 : break;

            case 1 : dictID = ip[pos]; pos++; break;

            case 2 : dictID = MEM_readLE16(ip+pos); pos+=2; break;

            case 3 : dictID = MEM_readLE32(ip+pos); pos+=4; break;

        }

        switch(fcsID)

        {

            default:   /* impossible */

            case 0 : if (singleSegment) frameContentSize = ip[pos]; break;

            case 1 : frameContentSize = MEM_readLE16(ip+pos)+256; break;

            case 2 : frameContentSize = MEM_readLE32(ip+pos); break;

            case 3 : frameContentSize = MEM_readLE64(ip+pos); break;

        }

        if (!windowSize) windowSize = (U32)frameContentSize;

        if (windowSize > windowSizeMax) return ERROR(frameParameter_windowTooLarge);

        fparamsPtr->frameContentSize = frameContentSize;

        fparamsPtr->windowSize = windowSize;

        fparamsPtr->dictID = dictID;

        fparamsPtr->checksumFlag = checksumFlag;

    }

    return 0;

}

/** ZSTD_getDecompressedSize() :

*   compatible with legacy mode

*   @return : decompressed size if known, 0 otherwise

              note : 0 can mean any of the following :

                   - decompressed size is not present within frame header

                   - frame header unknown / not supported

                   - frame header not complete (`srcSize` too small) */

unsigned long long ZSTD_getDecompressedSize(const void* src, size_t srcSize)

{

#if defined(ZSTD_LEGACY_SUPPORT) && (ZSTD_LEGACY_SUPPORT==1)

    if (ZSTD_isLegacy(src, srcSize)) return ZSTD_getDecompressedSize_legacy(src, srcSize);

#endif

    {   ZSTD_frameParams fparams;

        size_t const frResult = ZSTD_getFrameParams(&fparams, src, srcSize);

        if (frResult!=0) return 0;

        return fparams.frameContentSize;

    }

}

/** ZSTD_decodeFrameHeader() :

*   `headerSize` must be the size provided by ZSTD_frameHeaderSize().

*   @return : 0 if success, or an error code, which can be tested using ZSTD_isError() */

static size_t ZSTD_decodeFrameHeader(ZSTD_DCtx* dctx, const void* src, size_t headerSize)

{

    size_t const result = ZSTD_getFrameParams(&(dctx->fParams), src, headerSize);

    if (ZSTD_isError(result)) return result;  /* invalid header */

    if (result>0) return ERROR(srcSize_wrong);   /* headerSize too small */

    if (dctx->fParams.dictID && (dctx->dictID != dctx->fParams.dictID)) return ERROR(dictionary_wrong);

    if (dctx->fParams.checksumFlag) XXH64_reset(&dctx->xxhState, 0);

    return 0;

}

typedef struct

{

    blockType_e blockType;

    U32 lastBlock;

    U32 origSize;

} blockProperties_t;

/*! ZSTD_getcBlockSize() :

*   Provides the size of compressed block from block header `src` */

size_t ZSTD_getcBlockSize(const void* src, size_t srcSize, blockProperties_t* bpPtr)

{

    if (srcSize < ZSTD_blockHeaderSize) return ERROR(srcSize_wrong);

    {   U32 const cBlockHeader = MEM_readLE24(src);

        U32 const cSize = cBlockHeader >> 3;

        bpPtr->lastBlock = cBlockHeader & 1;

        bpPtr->blockType = (blockType_e)((cBlockHeader >> 1) & 3);

        bpPtr->origSize = cSize;   /* only useful for RLE */

        if (bpPtr->blockType == bt_rle) return 1;

        if (bpPtr->blockType == bt_reserved) return ERROR(corruption_detected);

        return cSize;

    }

}

static size_t ZSTD_copyRawBlock(void* dst, size_t dstCapacity, const void* src, size_t srcSize)

{

    if (srcSize > dstCapacity) return ERROR(dstSize_tooSmall);

    memcpy(dst, src, srcSize);

    return srcSize;

}

static size_t ZSTD_setRleBlock(void* dst, size_t dstCapacity, const void* src, size_t srcSize, size_t regenSize)

{

    if (srcSize != 1) return ERROR(srcSize_wrong);

    if (regenSize > dstCapacity) return ERROR(dstSize_tooSmall);

    memset(dst, *(const BYTE*)src, regenSize);

    return regenSize;

}

/*! ZSTD_decodeLiteralsBlock() :

    @return : nb of bytes read from src (< srcSize ) */

size_t ZSTD_decodeLiteralsBlock(ZSTD_DCtx* dctx,

                          const void* src, size_t srcSize)   /* note : srcSize < BLOCKSIZE */

{

    if (srcSize < MIN_CBLOCK_SIZE) return ERROR(corruption_detected);

    {   const BYTE* const istart = (const BYTE*) src;

        symbolEncodingType_e const litEncType = (symbolEncodingType_e)(istart[0] & 3);

        switch(litEncType)

        {

        case set_repeat:

            if (dctx->litEntropy==0) return ERROR(dictionary_corrupted);

            /* fall-through */

        case set_compressed:

            if (srcSize < 5) return ERROR(corruption_detected);   /* srcSize >= MIN_CBLOCK_SIZE == 3; here we need up to 5 for case 3 */