/**

 * 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

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

*  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 litBufSize;

    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

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

/* See compression format details in : doc/zstd_compression_format.md */

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

            {   size_t lhSize, litSize, litCSize;

                U32 singleStream=0;

                U32 const lhlCode = (istart[0] >> 2) & 3;

                U32 const lhc = MEM_readLE32(istart);

                switch(lhlCode)

                {

                case 0: case 1: default:   /* note : default is impossible, since lhlCode into [0..3] */

                    /* 2 - 2 - 10 - 10 */

                    singleStream = !lhlCode;

                    lhSize = 3;

                    litSize  = (lhc >> 4) & 0x3FF;

                    litCSize = (lhc >> 14) & 0x3FF;

                    break;

                case 2:

                    /* 2 - 2 - 14 - 14 */

                    lhSize = 4;

                    litSize  = (lhc >> 4) & 0x3FFF;

                    litCSize = lhc >> 18;

                    break;

                case 3:

                    /* 2 - 2 - 18 - 18 */

                    lhSize = 5;

                    litSize  = (lhc >> 4) & 0x3FFFF;

                    litCSize = (lhc >> 22) + (istart[4] << 10);

                    break;

                }

                if (litSize > ZSTD_BLOCKSIZE_ABSOLUTEMAX) return ERROR(corruption_detected);

                if (litCSize + lhSize > srcSize) return ERROR(corruption_detected);

                if (HUF_isError((litEncType==set_repeat) ?

                                    ( singleStream ?

                                        HUF_decompress1X_usingDTable(dctx->litBuffer, litSize, istart+lhSize, litCSize, dctx->HUFptr) :

                                        HUF_decompress4X_usingDTable(dctx->litBuffer, litSize, istart+lhSize, litCSize, dctx->HUFptr) ) :

                                    ( singleStream ?

                                        HUF_decompress1X2_DCtx(dctx->hufTable, dctx->litBuffer, litSize, istart+lhSize, litCSize) :

                                        HUF_decompress4X_hufOnly (dctx->hufTable, dctx->litBuffer, litSize, istart+lhSize, litCSize)) ))

                    return ERROR(corruption_detected);

                dctx->litPtr = dctx->litBuffer;

                dctx->litBufSize = ZSTD_BLOCKSIZE_ABSOLUTEMAX+WILDCOPY_OVERLENGTH;

                dctx->litSize = litSize;

                dctx->litEntropy = 1;

                if (litEncType==set_compressed) dctx->HUFptr = dctx->hufTable;

                return litCSize + lhSize;

            }

        case set_basic:

            {   size_t litSize, lhSize;

                U32 const lhlCode = ((istart[0]) >> 2) & 3;

                switch(lhlCode)

                {

                case 0: case 2: default:   /* note : default is impossible, since lhlCode into [0..3] */

                    lhSize = 1;

                    litSize = istart[0] >> 3;

                    break;

                case 1:

                    lhSize = 2;

                    litSize = MEM_readLE16(istart) >> 4;

                    break;

                case 3:

                    lhSize = 3;

                    litSize = MEM_readLE24(istart) >> 4;

                    break;

                }

                if (lhSize+litSize+WILDCOPY_OVERLENGTH > srcSize) {  /* risk reading beyond src buffer with wildcopy */

                    if (litSize+lhSize > srcSize) return ERROR(corruption_detected);

                    memcpy(dctx->litBuffer, istart+lhSize, litSize);

                    dctx->litPtr = dctx->litBuffer;

                    dctx->litBufSize = ZSTD_BLOCKSIZE_ABSOLUTEMAX+8;

                    dctx->litSize = litSize;

                    return lhSize+litSize;

                }

                /* direct reference into compressed stream */

                dctx->litPtr = istart+lhSize;

                dctx->litBufSize = srcSize-lhSize;

                dctx->litSize = litSize;

                return lhSize+litSize;

            }

        case set_rle:

            {   U32 const lhlCode = ((istart[0]) >> 2) & 3;

                size_t litSize, lhSize;

                switch(lhlCode)

                {

                case 0: case 2: default:   /* note : default is impossible, since lhlCode into [0..3] */

                    lhSize = 1;

                    litSize = istart[0] >> 3;

                    break;

                case 1:

                    lhSize = 2;

                    litSize = MEM_readLE16(istart) >> 4;

                    break;

                case 3:

                    lhSize = 3;

                    litSize = MEM_readLE24(istart) >> 4;

                    if (srcSize<4) return ERROR(corruption_detected);   /* srcSize >= MIN_CBLOCK_SIZE == 3; here we need lhSize+1 = 4 */

                    break;

                }

                if (litSize > ZSTD_BLOCKSIZE_ABSOLUTEMAX) return ERROR(corruption_detected);

                memset(dctx->litBuffer, istart[lhSize], litSize);

                dctx->litPtr = dctx->litBuffer;

                dctx->litBufSize = ZSTD_BLOCKSIZE_ABSOLUTEMAX+WILDCOPY_OVERLENGTH;

                dctx->litSize = litSize;

                return lhSize+1;

            }

        default:

            return ERROR(corruption_detected);   /* impossible */

        }

    }

}

typedef union {

    FSE_decode_t realData;

    U32 alignedBy4;

} FSE_decode_t4;

static const FSE_decode_t4 LL_defaultDTable[(1<<LL_DEFAULTNORMLOG)+1] = {

    { { LL_DEFAULTNORMLOG, 1, 1 } }, /* header : tableLog, fastMode, fastMode */

    { {  0,  0,  4 } },              /* 0 : base, symbol, bits */

    { { 16,  0,  4 } },

    { { 32,  1,  5 } },

    { {  0,  3,  5 } },

    { {  0,  4,  5 } },

    { {  0,  6,  5 } },

    { {  0,  7,  5 } },

    { {  0,  9,  5 } },

    { {  0, 10,  5 } },

    { {  0, 12,  5 } },

    { {  0, 14,  6 } },

    { {  0, 16,  5 } },

    { {  0, 18,  5 } },

    { {  0, 19,  5 } },

    { {  0, 21,  5 } },

    { {  0, 22,  5 } },

    { {  0, 24,  5 } },

    { { 32, 25,  5 } },

    { {  0, 26,  5 } },

    { {  0, 27,  6 } },

    { {  0, 29,  6 } },

    { {  0, 31,  6 } },

    { { 32,  0,  4 } },

    { {  0,  1,  4 } },

    { {  0,  2,  5 } },

    { { 32,  4,  5 } },

    { {  0,  5,  5 } },

    { { 32,  7,  5 } },

    { {  0,  8,  5 } },

    { { 32, 10,  5 } },

    { {  0, 11,  5 } },

    { {  0, 13,  6 } },

    { { 32, 16,  5 } },

    { {  0, 17,  5 } },