/*

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

 */

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

*  Tuning parameters

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

/*!

 * HEAPMODE :

 * Select how default decompression function ZSTD_decompress() allocates its context,

 * on stack (0), or into heap (1, default; requires malloc()).

 * Note that functions with explicit context such as ZSTD_decompressDCtx() are unaffected.

 */

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

 *  It's possible to set a different limit using ZSTD_DCtx_setMaxWindowSize().

 */

#ifndef ZSTD_MAXWINDOWSIZE_DEFAULT

#  define ZSTD_MAXWINDOWSIZE_DEFAULT (((U32)1 << ZSTD_WINDOWLOG_DEFAULTMAX) + 1)

#endif

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

*  Dependencies

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

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

#include "cpu.h"

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

#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

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

*  Errors

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

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

typedef enum { zdss_init=0, zdss_loadHeader,

               zdss_read, zdss_load, zdss_flush } ZSTD_dStreamStage;

typedef struct {

    U32 fastMode;

    U32 tableLog;

} ZSTD_seqSymbol_header;

typedef struct {

    U16  nextState;

    BYTE nbAdditionalBits;

    BYTE nbBits;

    U32  baseValue;

} ZSTD_seqSymbol;

#define SEQSYMBOL_TABLE_SIZE(log)   (1 + (1 << (log)))

typedef struct {

    ZSTD_seqSymbol LLTable[SEQSYMBOL_TABLE_SIZE(LLFSELog)];

    ZSTD_seqSymbol OFTable[SEQSYMBOL_TABLE_SIZE(OffFSELog)];

    ZSTD_seqSymbol MLTable[SEQSYMBOL_TABLE_SIZE(MLFSELog)];

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

    U32 workspace[HUF_DECOMPRESS_WORKSPACE_SIZE_U32];

    U32 rep[ZSTD_REP_NUM];

} ZSTD_entropyDTables_t;

struct ZSTD_DCtx_s

{

    const ZSTD_seqSymbol* LLTptr;

    const ZSTD_seqSymbol* MLTptr;

    const ZSTD_seqSymbol* OFTptr;

    const HUF_DTable* HUFptr;

    ZSTD_entropyDTables_t entropy;

    const void* previousDstEnd;   /* detect continuity */

    const void* base;             /* start of current segment */

    const void* vBase;            /* virtual start of previous segment if it was just before current one */

    const void* dictEnd;          /* end of previous segment */

    size_t expected;

    ZSTD_frameHeader fParams;

    U64 decodedSize;

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

    ZSTD_dStage stage;

    U32 litEntropy;

    U32 fseEntropy;

    XXH64_state_t xxhState;

    size_t headerSize;

    U32 dictID;

    ZSTD_format_e format;

    const BYTE* litPtr;

    ZSTD_customMem customMem;

    size_t litSize;

    size_t rleSize;

    size_t staticSize;

    int bmi2;                     /* == 1 if the CPU supports BMI2 and 0 otherwise. CPU support is determined dynamically once per context lifetime. */

    /* streaming */

    ZSTD_DDict* ddictLocal;

    const ZSTD_DDict* ddict;

    ZSTD_dStreamStage streamStage;

    char*  inBuff;

    size_t inBuffSize;

    size_t inPos;

    size_t maxWindowSize;

    char*  outBuff;

    size_t outBuffSize;

    size_t outStart;

    size_t outEnd;

    size_t lhSize;

    void* legacyContext;

    U32 previousLegacyVersion;

    U32 legacyVersion;

    U32 hostageByte;

    /* workspace */

    BYTE litBuffer[ZSTD_BLOCKSIZE_MAX + WILDCOPY_OVERLENGTH];

    BYTE headerBuffer[ZSTD_FRAMEHEADERSIZE_MAX];

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

size_t ZSTD_sizeof_DCtx (const ZSTD_DCtx* dctx)

{

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

    return sizeof(*dctx)

           + ZSTD_sizeof_DDict(dctx->ddictLocal)

           + dctx->inBuffSize + dctx->outBuffSize;

}

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

static size_t ZSTD_startingInputLength(ZSTD_format_e format)

{

    size_t const startingInputLength = (format==ZSTD_f_zstd1_magicless) ?

                    ZSTD_frameHeaderSize_prefix - ZSTD_frameIdSize :

                    ZSTD_frameHeaderSize_prefix;

    ZSTD_STATIC_ASSERT(ZSTD_FRAMEHEADERSIZE_PREFIX >= ZSTD_FRAMEIDSIZE);

    /* only supports formats ZSTD_f_zstd1 and ZSTD_f_zstd1_magicless */

    assert( (format == ZSTD_f_zstd1) || (format == ZSTD_f_zstd1_magicless) );

    return startingInputLength;

}

static void ZSTD_initDCtx_internal(ZSTD_DCtx* dctx)

{

    dctx->format = ZSTD_f_zstd1;  /* ZSTD_decompressBegin() invokes ZSTD_startingInputLength() with argument dctx->format */

    dctx->staticSize  = 0;

    dctx->maxWindowSize = ZSTD_MAXWINDOWSIZE_DEFAULT;

    dctx->ddict       = NULL;

    dctx->ddictLocal  = NULL;

    dctx->inBuff      = NULL;

    dctx->inBuffSize  = 0;

    dctx->outBuffSize = 0;

    dctx->streamStage = zdss_init;

    dctx->bmi2 = ZSTD_cpuid_bmi2(ZSTD_cpuid());

}

ZSTD_DCtx* ZSTD_initStaticDCtx(void *workspace, size_t workspaceSize)

{

    ZSTD_DCtx* const dctx = (ZSTD_DCtx*) workspace;

    if ((size_t)workspace & 7) return NULL;  /* 8-aligned */

    if (workspaceSize < sizeof(ZSTD_DCtx)) return NULL;  /* minimum size */

    ZSTD_initDCtx_internal(dctx);

    dctx->staticSize = workspaceSize;

    dctx->inBuff = (char*)(dctx+1);

    return dctx;

}

ZSTD_DCtx* ZSTD_createDCtx_advanced(ZSTD_customMem customMem)

{

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

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

        if (!dctx) return NULL;

        dctx->customMem = customMem;

        dctx->legacyContext = NULL;

        dctx->previousLegacyVersion = 0;

        ZSTD_initDCtx_internal(dctx);

        return dctx;

    }

}

ZSTD_DCtx* ZSTD_createDCtx(void)

{

    DEBUGLOG(3, "ZSTD_createDCtx");

    return ZSTD_createDCtx_advanced(ZSTD_defaultCMem);

}

size_t ZSTD_freeDCtx(ZSTD_DCtx* dctx)

{

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

    if (dctx->staticSize) return ERROR(memory_allocation);   /* not compatible with static DCtx */

    {   ZSTD_customMem const cMem = dctx->customMem;

        ZSTD_freeDDict(dctx->ddictLocal);

        dctx->ddictLocal = NULL;

        ZSTD_free(dctx->inBuff, cMem);

        dctx->inBuff = NULL;

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

        if (dctx->legacyContext)

            ZSTD_freeLegacyStreamContext(dctx->legacyContext, dctx->previousLegacyVersion);

#endif

        ZSTD_free(dctx, cMem);

        return 0;

    }

}

/* no longer useful */

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

{

    size_t const toCopy = (size_t)((char*)(&dstDCtx->inBuff) - (char*)dstDCtx);

    memcpy(dstDCtx, srcDCtx, toCopy);  /* no need to copy workspace */

}

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

 *   Frame header decoding

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

/*! 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 < ZSTD_frameIdSize) 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_internal() :

 *  srcSize must be large enough to reach header size fields.

 *  note : only works for formats ZSTD_f_zstd1 and ZSTD_f_zstd1_magicless.

 * @return : size of the Frame Header

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

static size_t ZSTD_frameHeaderSize_internal(const void* src, size_t srcSize, ZSTD_format_e format)

{

    size_t const minInputSize = ZSTD_startingInputLength(format);

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

    {   BYTE const fhd = ((const BYTE*)src)[minInputSize-1];

        U32 const dictID= fhd & 3;

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

        U32 const fcsId = fhd >> 6;

        return minInputSize + !singleSegment

             + ZSTD_did_fieldSize[dictID] + ZSTD_fcs_fieldSize[fcsId]

             + (singleSegment && !fcsId);

    }

}

/** ZSTD_frameHeaderSize() :

 *  srcSize must be >= ZSTD_frameHeaderSize_prefix.

 * @return : size of the Frame Header */

size_t ZSTD_frameHeaderSize(const void* src, size_t srcSize)

{

    return ZSTD_frameHeaderSize_internal(src, srcSize, ZSTD_f_zstd1);

}

/** ZSTD_getFrameHeader_internal() :

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

 *  note : only works for formats ZSTD_f_zstd1 and ZSTD_f_zstd1_magicless

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

 *          >0, `srcSize` is too small, value is wanted `srcSize` amount,

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

static size_t ZSTD_getFrameHeader_internal(ZSTD_frameHeader* zfhPtr, const void* src, size_t srcSize, ZSTD_format_e format)

{

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

    size_t const minInputSize = ZSTD_startingInputLength(format);

    if (srcSize < minInputSize) return minInputSize;

    if ( (format != ZSTD_f_zstd1_magicless)

      && (MEM_readLE32(src) != ZSTD_MAGICNUMBER) ) {

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

            /* skippable frame */

            if (srcSize < ZSTD_skippableHeaderSize)

                return ZSTD_skippableHeaderSize; /* magic number + frame length */

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

            zfhPtr->frameContentSize = MEM_readLE32((const char *)src + ZSTD_frameIdSize);

            zfhPtr->frameType = ZSTD_skippableFrame;

            return 0;

        }

        return ERROR(prefix_unknown);

    }

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

    {   size_t const fhsize = ZSTD_frameHeaderSize_internal(src, srcSize, format);

        if (srcSize < fhsize) return fhsize;

        zfhPtr->headerSize = (U32)fhsize;

    }

    {   BYTE const fhdByte = ip[minInputSize-1];

        size_t pos = minInputSize;

        U32 const dictIDSizeCode = fhdByte&3;

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

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

        U32 const fcsID = fhdByte>>6;

        U64 windowSize = 0;

        U32 dictID = 0;

        U64 frameContentSize = ZSTD_CONTENTSIZE_UNKNOWN;

        if ((fhdByte & 0x08) != 0)

            return ERROR(frameParameter_unsupported); /* reserved bits, 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);

            windowSize = (1ULL << windowLog);

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

        }

        switch(dictIDSizeCode)

        {

            default: assert(0);  /* 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: assert(0);  /* 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 (singleSegment) windowSize = frameContentSize;

        zfhPtr->frameType = ZSTD_frame;

        zfhPtr->frameContentSize = frameContentSize;

        zfhPtr->windowSize = windowSize;

        zfhPtr->blockSizeMax = (unsigned) MIN(windowSize, ZSTD_BLOCKSIZE_MAX);

        zfhPtr->dictID = dictID;

        zfhPtr->checksumFlag = checksumFlag;

    }

    return 0;

}

/** ZSTD_getFrameHeader() :

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

 *  note : this function does not consume input, it only reads it.

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

 *          >0, `srcSize` is too small, value is wanted `srcSize` amount,

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

size_t ZSTD_getFrameHeader(ZSTD_frameHeader* zfhPtr, const void* src, size_t srcSize)

{

    return ZSTD_getFrameHeader_internal(zfhPtr, src, srcSize, ZSTD_f_zstd1);

}

/** ZSTD_getFrameContentSize() :

 *  compatible with legacy mode

 * @return : decompressed size of the single frame pointed to be `src` if known, otherwise

 *         - ZSTD_CONTENTSIZE_UNKNOWN if the size cannot be determined

 *         - ZSTD_CONTENTSIZE_ERROR if an error occurred (e.g. invalid magic number, srcSize too small) */

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

{

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

    if (ZSTD_isLegacy(src, srcSize)) {

        unsigned long long const ret = ZSTD_getDecompressedSize_legacy(src, srcSize);

        return ret == 0 ? ZSTD_CONTENTSIZE_UNKNOWN : ret;

    }

#endif

    {   ZSTD_frameHeader zfh;

        if (ZSTD_getFrameHeader(&zfh, src, srcSize) != 0)

            return ZSTD_CONTENTSIZE_ERROR;

        if (zfh.frameType == ZSTD_skippableFrame) {

            return 0;

        } else {

            return zfh.frameContentSize;

    }   }

}

/** ZSTD_findDecompressedSize() :

 *  compatible with legacy mode

 *  `srcSize` must be the exact length of some number of ZSTD compressed and/or

 *      skippable frames

 *  @return : decompressed size of the frames contained */

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

{

    unsigned long long totalDstSize = 0;

    while (srcSize >= ZSTD_frameHeaderSize_prefix) {

        U32 const magicNumber = MEM_readLE32(src);

        if ((magicNumber & 0xFFFFFFF0U) == ZSTD_MAGIC_SKIPPABLE_START) {

            size_t skippableSize;

            if (srcSize < ZSTD_skippableHeaderSize)

                return ERROR(srcSize_wrong);

            skippableSize = MEM_readLE32((const BYTE *)src + ZSTD_frameIdSize)

                          + ZSTD_skippableHeaderSize;

            if (srcSize < skippableSize) {

                return ZSTD_CONTENTSIZE_ERROR;

            }

            src = (const BYTE *)src + skippableSize;

            srcSize -= skippableSize;

            continue;

        }

        {   unsigned long long const ret = ZSTD_getFrameContentSize(src, srcSize);

            if (ret >= ZSTD_CONTENTSIZE_ERROR) return ret;

            /* check for overflow */

            if (totalDstSize + ret < totalDstSize) return ZSTD_CONTENTSIZE_ERROR;

            totalDstSize += ret;

        }

        {   size_t const frameSrcSize = ZSTD_findFrameCompressedSize(src, srcSize);

            if (ZSTD_isError(frameSrcSize)) {

                return ZSTD_CONTENTSIZE_ERROR;

            }

            src = (const BYTE *)src + frameSrcSize;

            srcSize -= frameSrcSize;

        }

    }  /* while (srcSize >= ZSTD_frameHeaderSize_prefix) */

    if (srcSize) return ZSTD_CONTENTSIZE_ERROR;

    return totalDstSize;

}

/** ZSTD_getDecompressedSize() :

*   compatible with legacy mode

*   @return : decompressed size if known, 0 otherwise

              note : 0 can mean any of the following :

                   - frame content is empty

                   - decompressed size field is not present in 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)

{

    unsigned long long const ret = ZSTD_getFrameContentSize(src, srcSize);

    ZSTD_STATIC_ASSERT(ZSTD_CONTENTSIZE_ERROR < ZSTD_CONTENTSIZE_UNKNOWN);

    return (ret >= ZSTD_CONTENTSIZE_ERROR) ? 0 : ret;

}

/** 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_getFrameHeader_internal(&(dctx->fParams), src, headerSize, dctx->format);

    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;

}