/*

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