/*

 * 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_LIMIT_DEFAULT) + 1)

#endif

/*!

 *  NO_FORWARD_PROGRESS_MAX :

 *  maximum allowed nb of calls to ZSTD_decompressStream()

 *  without any forward progress

 *  (defined as: no byte read from input, and no byte flushed to output)

 *  before triggering an error.

 */

#ifndef ZSTD_NO_FORWARD_PROGRESS_MAX

#  define ZSTD_NO_FORWARD_PROGRESS_MAX 16

#endif

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

*  Dependencies

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

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

#include "cpu.h"         /* bmi2 */

#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"  /* blockProperties_t */

#include "zstd_decompress_internal.h"   /* ZSTD_DCtx */

#include "zstd_ddict.h"  /* ZSTD_DDictDictContent */

#include "zstd_decompress_block.h"   /* ZSTD_decompressBlock_internal */

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

#  include "zstd_legacy.h"

#endif

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

*   Context management

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

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 = ZSTD_FRAMEHEADERSIZE_PREFIX(format);

    /* 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->dictEnd     = NULL;

    dctx->ddictIsCold = 0;

    dctx->dictUses = ZSTD_dont_use;

    dctx->inBuff      = NULL;

    dctx->inBuffSize  = 0;

    dctx->outBuffSize = 0;

    dctx->streamStage = zdss_init;

    dctx->legacyContext = NULL;

    dctx->previousLegacyVersion = 0;

    dctx->noForwardProgress = 0;

    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;

        ZSTD_initDCtx_internal(dctx);

        return dctx;

    }

}

ZSTD_DCtx* ZSTD_createDCtx(void)

{

    DEBUGLOG(3, "ZSTD_createDCtx");

    return ZSTD_createDCtx_advanced(ZSTD_defaultCMem);

}

static void ZSTD_clearDict(ZSTD_DCtx* dctx)

{

    ZSTD_freeDDict(dctx->ddictLocal);

    dctx->ddictLocal = NULL;

    dctx->ddict = NULL;

    dctx->dictUses = ZSTD_dont_use;

}

size_t ZSTD_freeDCtx(ZSTD_DCtx* dctx)

{

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

    RETURN_ERROR_IF(dctx->staticSize, memory_allocation, "not compatible with static DCtx");

    {   ZSTD_customMem const cMem = dctx->customMem;

        ZSTD_clearDict(dctx);

        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 & ZSTD_MAGIC_SKIPPABLE_MASK) == 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);

    RETURN_ERROR_IF(srcSize < minInputSize, 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,

 *           or an error code (if srcSize is too small) */

size_t ZSTD_frameHeaderSize(const void* src, size_t srcSize)

{

    return ZSTD_frameHeaderSize_internal(src, srcSize, ZSTD_f_zstd1);

}

/** ZSTD_getFrameHeader_advanced() :

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

size_t ZSTD_getFrameHeader_advanced(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);

    memset(zfhPtr, 0, sizeof(*zfhPtr));   /* not strictly necessary, but static analyzer do not understand that zfhPtr is only going to be read only if return value is zero, since they are 2 different signals */

    if (srcSize < minInputSize) return minInputSize;

    RETURN_ERROR_IF(src==NULL, GENERIC, "invalid parameter");

    if ( (format != ZSTD_f_zstd1_magicless)

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

        if ((MEM_readLE32(src) & ZSTD_MAGIC_SKIPPABLE_MASK) == 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;

        RETURN_ERROR_IF((fhdByte & 0x08) != 0, frameParameter_unsupported,

                        "reserved bits, must be zero");

        if (!singleSegment) {

            BYTE const wlByte = ip[pos++];

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

            RETURN_ERROR_IF(windowLog > ZSTD_WINDOWLOG_MAX, 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_advanced(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;

    }   }

}

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

{

    size_t const skippableHeaderSize = ZSTD_SKIPPABLEHEADERSIZE;

    U32 sizeU32;

    RETURN_ERROR_IF(srcSize < ZSTD_SKIPPABLEHEADERSIZE, srcSize_wrong);

    sizeU32 = MEM_readLE32((BYTE const*)src + ZSTD_FRAMEIDSIZE);

    RETURN_ERROR_IF((U32)(sizeU32 + ZSTD_SKIPPABLEHEADERSIZE) < sizeU32,

                    frameParameter_unsupported);

    {

        size_t const skippableSize = skippableHeaderSize + sizeU32;

        RETURN_ERROR_IF(skippableSize > srcSize, srcSize_wrong);

        return skippableSize;

    }

}

/** 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_startingInputLength(ZSTD_f_zstd1)) {

        U32 const magicNumber = MEM_readLE32(src);

        if ((magicNumber & ZSTD_MAGIC_SKIPPABLE_MASK) == ZSTD_MAGIC_SKIPPABLE_START) {

            size_t const skippableSize = readSkippableFrameSize(src, srcSize);

            if (ZSTD_isError(skippableSize)) {

                return ZSTD_CONTENTSIZE_ERROR;

            }

            assert(skippableSize <= srcSize);

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

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

    RETURN_ERROR_IF(result>0, srcSize_wrong, "headerSize too small");

#ifndef FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION

    /* Skip the dictID check in fuzzing mode, because it makes the search

     * harder.

     */

    RETURN_ERROR_IF(dctx->fParams.dictID && (dctx->dictID != dctx->fParams.dictID),

                    dictionary_wrong);

#endif

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

    return 0;

}

static ZSTD_frameSizeInfo ZSTD_errorFrameSizeInfo(size_t ret)

{

    ZSTD_frameSizeInfo frameSizeInfo;

    frameSizeInfo.compressedSize = ret;

    frameSizeInfo.decompressedBound = ZSTD_CONTENTSIZE_ERROR;

    return frameSizeInfo;

}

static ZSTD_frameSizeInfo ZSTD_findFrameSizeInfo(const void* src, size_t srcSize)

{

    ZSTD_frameSizeInfo frameSizeInfo;

    memset(&frameSizeInfo, 0, sizeof(ZSTD_frameSizeInfo));

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

    if (ZSTD_isLegacy(src, srcSize))

        return ZSTD_findFrameSizeInfoLegacy(src, srcSize);

#endif

    if ((srcSize >= ZSTD_SKIPPABLEHEADERSIZE)

        && (MEM_readLE32(src) & ZSTD_MAGIC_SKIPPABLE_MASK) == ZSTD_MAGIC_SKIPPABLE_START) {

        frameSizeInfo.compressedSize = readSkippableFrameSize(src, srcSize);

        assert(ZSTD_isError(frameSizeInfo.compressedSize) ||

               frameSizeInfo.compressedSize <= srcSize);

        return frameSizeInfo;

    } else {

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

        const BYTE* const ipstart = ip;

        size_t remainingSize = srcSize;

        size_t nbBlocks = 0;

        ZSTD_frameHeader zfh;

        /* Extract Frame Header */

        {   size_t const ret = ZSTD_getFrameHeader(&zfh, src, srcSize);

            if (ZSTD_isError(ret))

                return ZSTD_errorFrameSizeInfo(ret);

            if (ret > 0)

                return ZSTD_errorFrameSizeInfo(ERROR(srcSize_wrong));

        }

        ip += zfh.headerSize;

        remainingSize -= zfh.headerSize;

        /* Iterate over each block */

        while (1) {

            blockProperties_t blockProperties;

            size_t const cBlockSize = ZSTD_getcBlockSize(ip, remainingSize, &blockProperties);

            if (ZSTD_isError(cBlockSize))

                return ZSTD_errorFrameSizeInfo(cBlockSize);