/*

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

 */

/* zstd_decompress_block :

 * this module takes care of decompressing _compressed_ block */

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

*  Dependencies

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

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

#include "compiler.h"    /* prefetch */

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

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

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

#include "zstd_decompress_block.h"

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

*  Macros

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

/* These two optional macros force the use one way or another of the two

 * ZSTD_decompressSequences implementations. You can't force in both directions

 * at the same time.

 */

#if defined(ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT) && \

    defined(ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG)

#error "Cannot force the use of the short and the long ZSTD_decompressSequences variants!"

#endif

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

*  Memory operations

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

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

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

 *   Block decoding

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

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

{

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

        RETURN_ERROR_IF(bpPtr->blockType == bt_reserved, corruption_detected);

        return cSize;

    }

}

/* Hidden declaration for fullbench */

size_t ZSTD_decodeLiteralsBlock(ZSTD_DCtx* dctx,

                          const void* src, size_t srcSize);

/*! ZSTD_decodeLiteralsBlock() :

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

 *  note : symbol not declared but exposed for fullbench */

size_t ZSTD_decodeLiteralsBlock(ZSTD_DCtx* dctx,

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

{

    DEBUGLOG(5, "ZSTD_decodeLiteralsBlock");

    RETURN_ERROR_IF(srcSize < MIN_CBLOCK_SIZE, corruption_detected);

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

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

        switch(litEncType)

        {

        case set_repeat:

            DEBUGLOG(5, "set_repeat flag : re-using stats from previous compressed literals block");

            RETURN_ERROR_IF(dctx->litEntropy==0, dictionary_corrupted);

            /* fall-through */

        case set_compressed:

            RETURN_ERROR_IF(srcSize < 5, 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);

                size_t hufSuccess;

                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) + ((size_t)istart[4] << 10);

                    break;

                }

                RETURN_ERROR_IF(litSize > ZSTD_BLOCKSIZE_MAX, corruption_detected);

                RETURN_ERROR_IF(litCSize + lhSize > srcSize, corruption_detected);

                /* prefetch huffman table if cold */

                if (dctx->ddictIsCold && (litSize > 768 /* heuristic */)) {

                    PREFETCH_AREA(dctx->HUFptr, sizeof(dctx->entropy.hufTable));

                }

                if (litEncType==set_repeat) {

                    if (singleStream) {

                        hufSuccess = HUF_decompress1X_usingDTable_bmi2(

                            dctx->litBuffer, litSize, istart+lhSize, litCSize,

                            dctx->HUFptr, dctx->bmi2);

                    } else {

                        hufSuccess = HUF_decompress4X_usingDTable_bmi2(

                            dctx->litBuffer, litSize, istart+lhSize, litCSize,

                            dctx->HUFptr, dctx->bmi2);

                    }

                } else {

                    if (singleStream) {

#if defined(HUF_FORCE_DECOMPRESS_X2)

                        hufSuccess = HUF_decompress1X_DCtx_wksp(

                            dctx->entropy.hufTable, dctx->litBuffer, litSize,

                            istart+lhSize, litCSize, dctx->workspace,

                            sizeof(dctx->workspace));

#else

                        hufSuccess = HUF_decompress1X1_DCtx_wksp_bmi2(

                            dctx->entropy.hufTable, dctx->litBuffer, litSize,

                            istart+lhSize, litCSize, dctx->workspace,

                            sizeof(dctx->workspace), dctx->bmi2);

#endif

                    } else {

                        hufSuccess = HUF_decompress4X_hufOnly_wksp_bmi2(

                            dctx->entropy.hufTable, dctx->litBuffer, litSize,

                            istart+lhSize, litCSize, dctx->workspace,

                            sizeof(dctx->workspace), dctx->bmi2);

                    }

                }

                RETURN_ERROR_IF(HUF_isError(hufSuccess), corruption_detected);

                dctx->litPtr = dctx->litBuffer;

                dctx->litSize = litSize;

                dctx->litEntropy = 1;

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

                memset(dctx->litBuffer + dctx->litSize, 0, WILDCOPY_OVERLENGTH);

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

                    RETURN_ERROR_IF(litSize+lhSize > srcSize, corruption_detected);

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

                    dctx->litPtr = dctx->litBuffer;

                    dctx->litSize = litSize;

                    memset(dctx->litBuffer + dctx->litSize, 0, WILDCOPY_OVERLENGTH);

                    return lhSize+litSize;

                }

                /* direct reference into compressed stream */

                dctx->litPtr = istart+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;

                    RETURN_ERROR_IF(srcSize<4, corruption_detected, "srcSize >= MIN_CBLOCK_SIZE == 3; here we need lhSize+1 = 4");

                    break;

                }

                RETURN_ERROR_IF(litSize > ZSTD_BLOCKSIZE_MAX, corruption_detected);

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

                dctx->litPtr = dctx->litBuffer;

                dctx->litSize = litSize;

                return lhSize+1;

            }

        default:

            RETURN_ERROR(corruption_detected, "impossible");

        }

    }

}

/* Default FSE distribution tables.

 * These are pre-calculated FSE decoding tables using default distributions as defined in specification :

 * https://github.com/facebook/zstd/blob/master/doc/zstd_compression_format.md#default-distributions

 * They were generated programmatically with following method :

 * - start from default distributions, present in /lib/common/zstd_internal.h

 * - generate tables normally, using ZSTD_buildFSETable()

 * - printout the content of tables

 * - pretify output, report below, test with fuzzer to ensure it's correct */

/* Default FSE distribution table for Literal Lengths */

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

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

     /* nextState, nbAddBits, nbBits, baseVal */

     {  0,  0,  4,    0},  { 16,  0,  4,    0},

     { 32,  0,  5,    1},  {  0,  0,  5,    3},

     {  0,  0,  5,    4},  {  0,  0,  5,    6},

     {  0,  0,  5,    7},  {  0,  0,  5,    9},

     {  0,  0,  5,   10},  {  0,  0,  5,   12},

     {  0,  0,  6,   14},  {  0,  1,  5,   16},

     {  0,  1,  5,   20},  {  0,  1,  5,   22},

     {  0,  2,  5,   28},  {  0,  3,  5,   32},

     {  0,  4,  5,   48},  { 32,  6,  5,   64},

     {  0,  7,  5,  128},  {  0,  8,  6,  256},

     {  0, 10,  6, 1024},  {  0, 12,  6, 4096},

     { 32,  0,  4,    0},  {  0,  0,  4,    1},

     {  0,  0,  5,    2},  { 32,  0,  5,    4},

     {  0,  0,  5,    5},  { 32,  0,  5,    7},

     {  0,  0,  5,    8},  { 32,  0,  5,   10},

     {  0,  0,  5,   11},  {  0,  0,  6,   13},

     { 32,  1,  5,   16},  {  0,  1,  5,   18},

     { 32,  1,  5,   22},  {  0,  2,  5,   24},

     { 32,  3,  5,   32},  {  0,  3,  5,   40},

     {  0,  6,  4,   64},  { 16,  6,  4,   64},

     { 32,  7,  5,  128},  {  0,  9,  6,  512},

     {  0, 11,  6, 2048},  { 48,  0,  4,    0},

     { 16,  0,  4,    1},  { 32,  0,  5,    2},

     { 32,  0,  5,    3},  { 32,  0,  5,    5},

     { 32,  0,  5,    6},  { 32,  0,  5,    8},

     { 32,  0,  5,    9},  { 32,  0,  5,   11},

     { 32,  0,  5,   12},  {  0,  0,  6,   15},

     { 32,  1,  5,   18},  { 32,  1,  5,   20},

     { 32,  2,  5,   24},  { 32,  2,  5,   28},

     { 32,  3,  5,   40},  { 32,  4,  5,   48},

     {  0, 16,  6,65536},  {  0, 15,  6,32768},

     {  0, 14,  6,16384},  {  0, 13,  6, 8192},

};   /* LL_defaultDTable */

/* Default FSE distribution table for Offset Codes */

static const ZSTD_seqSymbol OF_defaultDTable[(1<<OF_DEFAULTNORMLOG)+1] = {

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

    /* nextState, nbAddBits, nbBits, baseVal */

    {  0,  0,  5,    0},     {  0,  6,  4,   61},

    {  0,  9,  5,  509},     {  0, 15,  5,32765},

    {  0, 21,  5,2097149},   {  0,  3,  5,    5},

    {  0,  7,  4,  125},     {  0, 12,  5, 4093},

    {  0, 18,  5,262141},    {  0, 23,  5,8388605},

    {  0,  5,  5,   29},     {  0,  8,  4,  253},

    {  0, 14,  5,16381},     {  0, 20,  5,1048573},

    {  0,  2,  5,    1},     { 16,  7,  4,  125},

    {  0, 11,  5, 2045},     {  0, 17,  5,131069},

    {  0, 22,  5,4194301},   {  0,  4,  5,   13},

    { 16,  8,  4,  253},     {  0, 13,  5, 8189},

    {  0, 19,  5,524285},    {  0,  1,  5,    1},

    { 16,  6,  4,   61},     {  0, 10,  5, 1021},

    {  0, 16,  5,65533},     {  0, 28,  5,268435453},

    {  0, 27,  5,134217725}, {  0, 26,  5,67108861},

    {  0, 25,  5,33554429},  {  0, 24,  5,16777213},

};   /* OF_defaultDTable */

/* Default FSE distribution table for Match Lengths */

static const ZSTD_seqSymbol ML_defaultDTable[(1<<ML_DEFAULTNORMLOG)+1] = {

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

    /* nextState, nbAddBits, nbBits, baseVal */

    {  0,  0,  6,    3},  {  0,  0,  4,    4},

    { 32,  0,  5,    5},  {  0,  0,  5,    6},

    {  0,  0,  5,    8},  {  0,  0,  5,    9},

    {  0,  0,  5,   11},  {  0,  0,  6,   13},

    {  0,  0,  6,   16},  {  0,  0,  6,   19},

    {  0,  0,  6,   22},  {  0,  0,  6,   25},

    {  0,  0,  6,   28},  {  0,  0,  6,   31},

    {  0,  0,  6,   34},  {  0,  1,  6,   37},

    {  0,  1,  6,   41},  {  0,  2,  6,   47},

    {  0,  3,  6,   59},  {  0,  4,  6,   83},

    {  0,  7,  6,  131},  {  0,  9,  6,  515},

    { 16,  0,  4,    4},  {  0,  0,  4,    5},

    { 32,  0,  5,    6},  {  0,  0,  5,    7},

    { 32,  0,  5,    9},  {  0,  0,  5,   10},

    {  0,  0,  6,   12},  {  0,  0,  6,   15},

    {  0,  0,  6,   18},  {  0,  0,  6,   21},

    {  0,  0,  6,   24},  {  0,  0,  6,   27},

    {  0,  0,  6,   30},  {  0,  0,  6,   33},

    {  0,  1,  6,   35},  {  0,  1,  6,   39},

    {  0,  2,  6,   43},  {  0,  3,  6,   51},

    {  0,  4,  6,   67},  {  0,  5,  6,   99},

    {  0,  8,  6,  259},  { 32,  0,  4,    4},

    { 48,  0,  4,    4},  { 16,  0,  4,    5},

    { 32,  0,  5,    7},  { 32,  0,  5,    8},

    { 32,  0,  5,   10},  { 32,  0,  5,   11},

    {  0,  0,  6,   14},  {  0,  0,  6,   17},

    {  0,  0,  6,   20},  {  0,  0,  6,   23},

    {  0,  0,  6,   26},  {  0,  0,  6,   29},

    {  0,  0,  6,   32},  {  0, 16,  6,65539},

    {  0, 15,  6,32771},  {  0, 14,  6,16387},

    {  0, 13,  6, 8195},  {  0, 12,  6, 4099},

    {  0, 11,  6, 2051},  {  0, 10,  6, 1027},

};   /* ML_defaultDTable */

static void ZSTD_buildSeqTable_rle(ZSTD_seqSymbol* dt, U32 baseValue, U32 nbAddBits)

{

    void* ptr = dt;

    ZSTD_seqSymbol_header* const DTableH = (ZSTD_seqSymbol_header*)ptr;

    ZSTD_seqSymbol* const cell = dt + 1;

    DTableH->tableLog = 0;

    DTableH->fastMode = 0;

    cell->nbBits = 0;

    cell->nextState = 0;

    assert(nbAddBits < 255);

    cell->nbAdditionalBits = (BYTE)nbAddBits;

    cell->baseValue = baseValue;

}

/* ZSTD_buildFSETable() :

 * generate FSE decoding table for one symbol (ll, ml or off)

 * cannot fail if input is valid =>

 * all inputs are presumed validated at this stage */

void

ZSTD_buildFSETable(ZSTD_seqSymbol* dt,

            const short* normalizedCounter, unsigned maxSymbolValue,

            const U32* baseValue, const U32* nbAdditionalBits,

            unsigned tableLog)

{

    ZSTD_seqSymbol* const tableDecode = dt+1;

    U16 symbolNext[MaxSeq+1];

    U32 const maxSV1 = maxSymbolValue + 1;

    U32 const tableSize = 1 << tableLog;

    U32 highThreshold = tableSize-1;

    /* Sanity Checks */

    assert(maxSymbolValue <= MaxSeq);

    assert(tableLog <= MaxFSELog);

    /* Init, lay down lowprob symbols */

    {   ZSTD_seqSymbol_header DTableH;

        DTableH.tableLog = tableLog;

        DTableH.fastMode = 1;

        {   S16 const largeLimit= (S16)(1 << (tableLog-1));

            U32 s;

            for (s=0; s<maxSV1; s++) {

                if (normalizedCounter[s]==-1) {

                    tableDecode[highThreshold--].baseValue = s;

                    symbolNext[s] = 1;

                } else {

                    if (normalizedCounter[s] >= largeLimit) DTableH.fastMode=0;

                    assert(normalizedCounter[s]>=0);

                    symbolNext[s] = (U16)normalizedCounter[s];

        }   }   }

        memcpy(dt, &DTableH, sizeof(DTableH));

    }

    /* Spread symbols */

    {   U32 const tableMask = tableSize-1;

        U32 const step = FSE_TABLESTEP(tableSize);

        U32 s, position = 0;

        for (s=0; s<maxSV1; s++) {

            int i;

            for (i=0; i<normalizedCounter[s]; i++) {

                tableDecode[position].baseValue = s;

                position = (position + step) & tableMask;

                while (position > highThreshold) position = (position + step) & tableMask;   /* lowprob area */

        }   }

        assert(position == 0); /* position must reach all cells once, otherwise normalizedCounter is incorrect */

    }

    /* Build Decoding table */

    {   U32 u;

        for (u=0; u<tableSize; u++) {

            U32 const symbol = tableDecode[u].baseValue;

            U32 const nextState = symbolNext[symbol]++;

            tableDecode[u].nbBits = (BYTE) (tableLog - BIT_highbit32(nextState) );

            tableDecode[u].nextState = (U16) ( (nextState << tableDecode[u].nbBits) - tableSize);

            assert(nbAdditionalBits[symbol] < 255);

            tableDecode[u].nbAdditionalBits = (BYTE)nbAdditionalBits[symbol];

            tableDecode[u].baseValue = baseValue[symbol];

    }   }

}

/*! ZSTD_buildSeqTable() :

 * @return : nb bytes read from src,

 *           or an error code if it fails */

static size_t ZSTD_buildSeqTable(ZSTD_seqSymbol* DTableSpace, const ZSTD_seqSymbol** DTablePtr,

                                 symbolEncodingType_e type, unsigned max, U32 maxLog,

                                 const void* src, size_t srcSize,

                                 const U32* baseValue, const U32* nbAdditionalBits,

                                 const ZSTD_seqSymbol* defaultTable, U32 flagRepeatTable,

                                 int ddictIsCold, int nbSeq)

{

    switch(type)

    {

    case set_rle :

        RETURN_ERROR_IF(!srcSize, srcSize_wrong);

        RETURN_ERROR_IF((*(const BYTE*)src) > max, corruption_detected);

        {   U32 const symbol = *(const BYTE*)src;

            U32 const baseline = baseValue[symbol];

            U32 const nbBits = nbAdditionalBits[symbol];

            ZSTD_buildSeqTable_rle(DTableSpace, baseline, nbBits);

        }

        *DTablePtr = DTableSpace;

        return 1;

    case set_basic :

        *DTablePtr = defaultTable;

        return 0;

    case set_repeat:

        RETURN_ERROR_IF(!flagRepeatTable, corruption_detected);

        /* prefetch FSE table if used */

        if (ddictIsCold && (nbSeq > 24 /* heuristic */)) {

            const void* const pStart = *DTablePtr;

            size_t const pSize = sizeof(ZSTD_seqSymbol) * (SEQSYMBOL_TABLE_SIZE(maxLog));

            PREFETCH_AREA(pStart, pSize);

        }

        return 0;

    case set_compressed :

        {   unsigned tableLog;

            S16 norm[MaxSeq+1];

            size_t const headerSize = FSE_readNCount(norm, &max, &tableLog, src, srcSize);

            RETURN_ERROR_IF(FSE_isError(headerSize), corruption_detected);

            RETURN_ERROR_IF(tableLog > maxLog, corruption_detected);

            ZSTD_buildFSETable(DTableSpace, norm, max, baseValue, nbAdditionalBits, tableLog);

            *DTablePtr = DTableSpace;

            return headerSize;

        }

    default :

        assert(0);

        RETURN_ERROR(GENERIC, "impossible");

    }

}

size_t ZSTD_decodeSeqHeaders(ZSTD_DCtx* dctx, int* nbSeqPtr,

                             const void* src, size_t srcSize)

{

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

    const BYTE* const iend = istart + srcSize;

    const BYTE* ip = istart;

    int nbSeq;

    DEBUGLOG(5, "ZSTD_decodeSeqHeaders");

    /* check */

    RETURN_ERROR_IF(srcSize < MIN_SEQUENCES_SIZE, srcSize_wrong);

    /* SeqHead */

    nbSeq = *ip++;

    if (!nbSeq) {

        *nbSeqPtr=0;

        RETURN_ERROR_IF(srcSize != 1, srcSize_wrong);

        return 1;

    }

    if (nbSeq > 0x7F) {

        if (nbSeq == 0xFF) {

            RETURN_ERROR_IF(ip+2 > iend, srcSize_wrong);

            nbSeq = MEM_readLE16(ip) + LONGNBSEQ, ip+=2;

        } else {

            RETURN_ERROR_IF(ip >= iend, srcSize_wrong);

            nbSeq = ((nbSeq-0x80)<<8) + *ip++;

        }

    }

    *nbSeqPtr = nbSeq;

    /* FSE table descriptors */

    RETURN_ERROR_IF(ip+1 > iend, srcSize_wrong); /* minimum possible size: 1 byte for symbol encoding types */

    {   symbolEncodingType_e const LLtype = (symbolEncodingType_e)(*ip >> 6);

        symbolEncodingType_e const OFtype = (symbolEncodingType_e)((*ip >> 4) & 3);

        symbolEncodingType_e const MLtype = (symbolEncodingType_e)((*ip >> 2) & 3);

        ip++;

        /* Build DTables */

        {   size_t const llhSize = ZSTD_buildSeqTable(dctx->entropy.LLTable, &dctx->LLTptr,

                                                      LLtype, MaxLL, LLFSELog,

                                                      ip, iend-ip,

                                                      LL_base, LL_bits,

                                                      LL_defaultDTable, dctx->fseEntropy,

                                                      dctx->ddictIsCold, nbSeq);