/*

 * Copyright (c) Meta Platforms, Inc. and affiliates.

 * 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 "../common/zstd_deps.h"   /* ZSTD_memcpy, ZSTD_memmove, ZSTD_memset */

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

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

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

#define FSE_STATIC_LINKING_ONLY

#include "../common/fse.h"

#include "../common/huf.h"

#include "../common/zstd_internal.h"

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

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

#include "zstd_decompress_block.h"

#include "../common/bits.h"  /* ZSTD_highbit32 */

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

*  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) { ZSTD_memcpy(dst, src, 4); }

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

 *   Block decoding

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

static size_t ZSTD_blockSizeMax(ZSTD_DCtx const* dctx)

{

    size_t const blockSizeMax = dctx->isFrameDecompression ? dctx->fParams.blockSizeMax : ZSTD_BLOCKSIZE_MAX;

    assert(blockSizeMax <= ZSTD_BLOCKSIZE_MAX);

    return blockSizeMax;

}

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

    }

}

/* Allocate buffer for literals, either overlapping current dst, or split between dst and litExtraBuffer, or stored entirely within litExtraBuffer */

static void ZSTD_allocateLiteralsBuffer(ZSTD_DCtx* dctx, void* const dst, const size_t dstCapacity, const size_t litSize,

    const streaming_operation streaming, const size_t expectedWriteSize, const unsigned splitImmediately)

{

    size_t const blockSizeMax = ZSTD_blockSizeMax(dctx);

    assert(litSize <= blockSizeMax);

    assert(dctx->isFrameDecompression || streaming == not_streaming);

    assert(expectedWriteSize <= blockSizeMax);

    if (streaming == not_streaming && dstCapacity > blockSizeMax + WILDCOPY_OVERLENGTH + litSize + WILDCOPY_OVERLENGTH) {

        /* If we aren't streaming, we can just put the literals after the output

         * of the current block. We don't need to worry about overwriting the

         * extDict of our window, because it doesn't exist.

         * So if we have space after the end of the block, just put it there.

         */

        dctx->litBuffer = (BYTE*)dst + blockSizeMax + WILDCOPY_OVERLENGTH;

        dctx->litBufferEnd = dctx->litBuffer + litSize;

        dctx->litBufferLocation = ZSTD_in_dst;

    } else if (litSize <= ZSTD_LITBUFFEREXTRASIZE) {

        /* Literals fit entirely within the extra buffer, put them there to avoid

         * having to split the literals.

         */

        dctx->litBuffer = dctx->litExtraBuffer;

        dctx->litBufferEnd = dctx->litBuffer + litSize;

        dctx->litBufferLocation = ZSTD_not_in_dst;

    } else {

        assert(blockSizeMax > ZSTD_LITBUFFEREXTRASIZE);

        /* Literals must be split between the output block and the extra lit

         * buffer. We fill the extra lit buffer with the tail of the literals,

         * and put the rest of the literals at the end of the block, with

         * WILDCOPY_OVERLENGTH of buffer room to allow for overreads.

         * This MUST not write more than our maxBlockSize beyond dst, because in

         * streaming mode, that could overwrite part of our extDict window.

         */

        if (splitImmediately) {

            /* won't fit in litExtraBuffer, so it will be split between end of dst and extra buffer */

            dctx->litBuffer = (BYTE*)dst + expectedWriteSize - litSize + ZSTD_LITBUFFEREXTRASIZE - WILDCOPY_OVERLENGTH;

            dctx->litBufferEnd = dctx->litBuffer + litSize - ZSTD_LITBUFFEREXTRASIZE;

        } else {

            /* initially this will be stored entirely in dst during huffman decoding, it will partially be shifted to litExtraBuffer after */

            dctx->litBuffer = (BYTE*)dst + expectedWriteSize - litSize;

            dctx->litBufferEnd = (BYTE*)dst + expectedWriteSize;

        }

        dctx->litBufferLocation = ZSTD_split;

        assert(dctx->litBufferEnd <= (BYTE*)dst + expectedWriteSize);

    }

}

/*! ZSTD_decodeLiteralsBlock() :

 * Where it is possible to do so without being stomped by the output during decompression, the literals block will be stored

 * in the dstBuffer.  If there is room to do so, it will be stored in full in the excess dst space after where the current

 * block will be output.  Otherwise it will be stored at the end of the current dst blockspace, with a small portion being

 * stored in dctx->litExtraBuffer to help keep it "ahead" of the current output write.

 *

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

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

static size_t ZSTD_decodeLiteralsBlock(ZSTD_DCtx* dctx,

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

                          void* dst, size_t dstCapacity, const streaming_operation streaming)

{

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

        size_t const blockSizeMax = ZSTD_blockSizeMax(dctx);

        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, "");

            ZSTD_FALLTHROUGH;

        case set_compressed:

            RETURN_ERROR_IF(srcSize < 5, corruption_detected, "srcSize >= MIN_CBLOCK_SIZE == 2; 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;

                size_t expectedWriteSize = MIN(blockSizeMax, dstCapacity);

                int const flags = 0

                    | (ZSTD_DCtx_get_bmi2(dctx) ? HUF_flags_bmi2 : 0)

                    | (dctx->disableHufAsm ? HUF_flags_disableAsm : 0);

                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 > 0 && dst == NULL, dstSize_tooSmall, "NULL not handled");

                RETURN_ERROR_IF(litSize > blockSizeMax, corruption_detected, "");

                if (!singleStream)

                    RETURN_ERROR_IF(litSize < MIN_LITERALS_FOR_4_STREAMS, literals_headerWrong,

                        "Not enough literals (%zu) for the 4-streams mode (min %u)",

                        litSize, MIN_LITERALS_FOR_4_STREAMS);

                RETURN_ERROR_IF(litCSize + lhSize > srcSize, corruption_detected, "");

                RETURN_ERROR_IF(expectedWriteSize < litSize , dstSize_tooSmall, "");

                ZSTD_allocateLiteralsBuffer(dctx, dst, dstCapacity, litSize, streaming, expectedWriteSize, 0);

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

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

                            dctx->HUFptr, flags);

                    } else {

                        assert(litSize >= MIN_LITERALS_FOR_4_STREAMS);

                        hufSuccess = HUF_decompress4X_usingDTable(

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

                            dctx->HUFptr, flags);

                    }

                } 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), flags);

#else

                        hufSuccess = HUF_decompress1X1_DCtx_wksp(

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

                            istart+lhSize, litCSize, dctx->workspace,

                            sizeof(dctx->workspace), flags);

#endif

                    } else {

                        hufSuccess = HUF_decompress4X_hufOnly_wksp(

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

                            istart+lhSize, litCSize, dctx->workspace,

                            sizeof(dctx->workspace), flags);

                    }

                }

                if (dctx->litBufferLocation == ZSTD_split)

                {

                    assert(litSize > ZSTD_LITBUFFEREXTRASIZE);

                    ZSTD_memcpy(dctx->litExtraBuffer, dctx->litBufferEnd - ZSTD_LITBUFFEREXTRASIZE, ZSTD_LITBUFFEREXTRASIZE);

                    ZSTD_memmove(dctx->litBuffer + ZSTD_LITBUFFEREXTRASIZE - WILDCOPY_OVERLENGTH, dctx->litBuffer, litSize - ZSTD_LITBUFFEREXTRASIZE);

                    dctx->litBuffer += ZSTD_LITBUFFEREXTRASIZE - WILDCOPY_OVERLENGTH;

                    dctx->litBufferEnd -= WILDCOPY_OVERLENGTH;

                    assert(dctx->litBufferEnd <= (BYTE*)dst + blockSizeMax);

                }

                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;

                return litCSize + lhSize;

            }

        case set_basic:

            {   size_t litSize, lhSize;

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

                size_t expectedWriteSize = MIN(blockSizeMax, dstCapacity);

                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;

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

                    litSize = MEM_readLE24(istart) >> 4;

                    break;

                }

                RETURN_ERROR_IF(litSize > 0 && dst == NULL, dstSize_tooSmall, "NULL not handled");

                RETURN_ERROR_IF(litSize > blockSizeMax, corruption_detected, "");

                RETURN_ERROR_IF(expectedWriteSize < litSize, dstSize_tooSmall, "");

                ZSTD_allocateLiteralsBuffer(dctx, dst, dstCapacity, litSize, streaming, expectedWriteSize, 1);

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

                    RETURN_ERROR_IF(litSize+lhSize > srcSize, corruption_detected, "");

                    if (dctx->litBufferLocation == ZSTD_split)

                    {

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

                        ZSTD_memcpy(dctx->litExtraBuffer, istart + lhSize + litSize - ZSTD_LITBUFFEREXTRASIZE, ZSTD_LITBUFFEREXTRASIZE);

                    }

                    else

                    {

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

                    }

                    dctx->litPtr = dctx->litBuffer;

                    dctx->litSize = litSize;

                    return lhSize+litSize;

                }

                /* direct reference into compressed stream */

                dctx->litPtr = istart+lhSize;

                dctx->litSize = litSize;

                dctx->litBufferEnd = dctx->litPtr + litSize;

                dctx->litBufferLocation = ZSTD_not_in_dst;

                return lhSize+litSize;

            }

        case set_rle:

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

                size_t litSize, lhSize;

                size_t expectedWriteSize = MIN(blockSizeMax, dstCapacity);

                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;

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

                    litSize = MEM_readLE16(istart) >> 4;

                    break;

                case 3:

                    lhSize = 3;

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

                    litSize = MEM_readLE24(istart) >> 4;

                    break;

                }

                RETURN_ERROR_IF(litSize > 0 && dst == NULL, dstSize_tooSmall, "NULL not handled");

                RETURN_ERROR_IF(litSize > blockSizeMax, corruption_detected, "");

                RETURN_ERROR_IF(expectedWriteSize < litSize, dstSize_tooSmall, "");

                ZSTD_allocateLiteralsBuffer(dctx, dst, dstCapacity, litSize, streaming, expectedWriteSize, 1);

                if (dctx->litBufferLocation == ZSTD_split)

                {

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

                    ZSTD_memset(dctx->litExtraBuffer, istart[lhSize], ZSTD_LITBUFFEREXTRASIZE);

                }

                else

                {

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

                }

                dctx->litPtr = dctx->litBuffer;

                dctx->litSize = litSize;

                return lhSize+1;

            }

        default:

            RETURN_ERROR(corruption_detected, "impossible");

        }

    }

}

/* Hidden declaration for fullbench */

size_t ZSTD_decodeLiteralsBlock_wrapper(ZSTD_DCtx* dctx,

                          const void* src, size_t srcSize,

                          void* dst, size_t dstCapacity);

size_t ZSTD_decodeLiteralsBlock_wrapper(ZSTD_DCtx* dctx,

                          const void* src, size_t srcSize,

                          void* dst, size_t dstCapacity)

{

    dctx->isFrameDecompression = 0;

    return ZSTD_decodeLiteralsBlock(dctx, src, srcSize, dst, dstCapacity, not_streaming);

}

/* Default FSE distribution tables.

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

 * https://github.com/facebook/zstd/blob/release/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

 * - prettify 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, U8 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 = 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 */

FORCE_INLINE_TEMPLATE

void ZSTD_buildFSETable_body(ZSTD_seqSymbol* dt,

            const short* normalizedCounter, unsigned maxSymbolValue,

            const U32* baseValue, const U8* nbAdditionalBits,

            unsigned tableLog, void* wksp, size_t wkspSize)

{

    ZSTD_seqSymbol* const tableDecode = dt+1;

    U32 const maxSV1 = maxSymbolValue + 1;

    U32 const tableSize = 1 << tableLog;

    U16* symbolNext = (U16*)wksp;

    BYTE* spread = (BYTE*)(symbolNext + MaxSeq + 1);

    U32 highThreshold = tableSize - 1;

    /* Sanity Checks */

    assert(maxSymbolValue <= MaxSeq);

    assert(tableLog <= MaxFSELog);

    assert(wkspSize >= ZSTD_BUILD_FSE_TABLE_WKSP_SIZE);

    (void)wkspSize;

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

        }   }   }

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

    }

    /* Spread symbols */

    assert(tableSize <= 512);

    /* Specialized symbol spreading for the case when there are

     * no low probability (-1 count) symbols. When compressing

     * small blocks we avoid low probability symbols to hit this

     * case, since header decoding speed matters more.

     */

    if (highThreshold == tableSize - 1) {

        size_t const tableMask = tableSize-1;

        size_t const step = FSE_TABLESTEP(tableSize);

        /* First lay down the symbols in order.

         * We use a uint64_t to lay down 8 bytes at a time. This reduces branch

         * misses since small blocks generally have small table logs, so nearly

         * all symbols have counts <= 8. We ensure we have 8 bytes at the end of

         * our buffer to handle the over-write.

         */

        {

            U64 const add = 0x0101010101010101ull;

            size_t pos = 0;

            U64 sv = 0;

            U32 s;

            for (s=0; s<maxSV1; ++s, sv += add) {

                int i;

                int const n = normalizedCounter[s];

                MEM_write64(spread + pos, sv);

                for (i = 8; i < n; i += 8) {

                    MEM_write64(spread + pos + i, sv);

                }

                assert(n>=0);

                pos += (size_t)n;

            }

        }

        /* Now we spread those positions across the table.

         * The benefit of doing it in two stages is that we avoid the

         * variable size inner loop, which caused lots of branch misses.

         * Now we can run through all the positions without any branch misses.

         * We unroll the loop twice, since that is what empirically worked best.

         */

        {

            size_t position = 0;

            size_t s;

            size_t const unroll = 2;

            assert(tableSize % unroll == 0); /* FSE_MIN_TABLELOG is 5 */

            for (s = 0; s < (size_t)tableSize; s += unroll) {

                size_t u;

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

                    size_t const uPosition = (position + (u * step)) & tableMask;

                    tableDecode[uPosition].baseValue = spread[s + u];

                }

                position = (position + (unroll * step)) & tableMask;

            }

            assert(position == 0);

        }

    } else {

        U32 const tableMask = tableSize-1;

        U32 const step = FSE_TABLESTEP(tableSize);

        U32 s, position = 0;

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

            int i;

            int const n = normalizedCounter[s];

            for (i=0; i<n; i++) {

                tableDecode[position].baseValue = s;

                position = (position + step) & tableMask;

                while (UNLIKELY(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 - ZSTD_highbit32(nextState) );

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

            assert(nbAdditionalBits[symbol] < 255);

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

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

        }

    }

}

/* Avoids the FORCE_INLINE of the _body() function. */

static void ZSTD_buildFSETable_body_default(ZSTD_seqSymbol* dt,

            const short* normalizedCounter, unsigned maxSymbolValue,

            const U32* baseValue, const U8* nbAdditionalBits,

            unsigned tableLog, void* wksp, size_t wkspSize)

{

    ZSTD_buildFSETable_body(dt, normalizedCounter, maxSymbolValue,

            baseValue, nbAdditionalBits, tableLog, wksp, wkspSize);

}

#if DYNAMIC_BMI2

BMI2_TARGET_ATTRIBUTE static void ZSTD_buildFSETable_body_bmi2(ZSTD_seqSymbol* dt,

            const short* normalizedCounter, unsigned maxSymbolValue,

            const U32* baseValue, const U8* nbAdditionalBits,

            unsigned tableLog, void* wksp, size_t wkspSize)

{

    ZSTD_buildFSETable_body(dt, normalizedCounter, maxSymbolValue,

            baseValue, nbAdditionalBits, tableLog, wksp, wkspSize);

}

#endif

void ZSTD_buildFSETable(ZSTD_seqSymbol* dt,

            const short* normalizedCounter, unsigned maxSymbolValue,

            const U32* baseValue, const U8* nbAdditionalBits,

            unsigned tableLog, void* wksp, size_t wkspSize, int bmi2)

{

#if DYNAMIC_BMI2

    if (bmi2) {

        ZSTD_buildFSETable_body_bmi2(dt, normalizedCounter, maxSymbolValue,

                baseValue, nbAdditionalBits, tableLog, wksp, wkspSize);

        return;

    }

#endif

    (void)bmi2;

    ZSTD_buildFSETable_body_default(dt, normalizedCounter, maxSymbolValue,

            baseValue, nbAdditionalBits, tableLog, wksp, wkspSize);

}

/*! 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 U8* nbAdditionalBits,

                                 const ZSTD_seqSymbol* defaultTable, U32 flagRepeatTable,

                                 int ddictIsCold, int nbSeq, U32* wksp, size_t wkspSize,

                                 int bmi2)

{

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

            U8 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, wksp, wkspSize, bmi2);

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

    if (nbSeq == 0) {

        /* No sequence : section ends immediately */

        RETURN_ERROR_IF(ip != iend, corruption_detected,

            "extraneous data present in the Sequences section");

        return (size_t)(ip - istart);

    }

    /* FSE table descriptors */

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

    RETURN_ERROR_IF(*ip & 3, corruption_detected, ""); /* The last field, Reserved, must be all-zeroes. */

    {   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,

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

                                                      ZSTD_DCtx_get_bmi2(dctx));

            RETURN_ERROR_IF(ZSTD_isError(llhSize), corruption_detected, "ZSTD_buildSeqTable failed");

            ip += llhSize;

        }

        {   size_t const ofhSize = ZSTD_buildSeqTable(dctx->entropy.OFTable, &dctx->OFTptr,

                                                      OFtype, MaxOff, OffFSELog,

                                                      ip, iend-ip,

                                                      OF_base, OF_bits,

                                                      OF_defaultDTable, dctx->fseEntropy,

                                                      dctx->ddictIsCold, nbSeq,

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

                                                      ZSTD_DCtx_get_bmi2(dctx));

            RETURN_ERROR_IF(ZSTD_isError(ofhSize), corruption_detected, "ZSTD_buildSeqTable failed");

            ip += ofhSize;

        }

        {   size_t const mlhSize = ZSTD_buildSeqTable(dctx->entropy.MLTable, &dctx->MLTptr,

                                                      MLtype, MaxML, MLFSELog,

                                                      ip, iend-ip,

                                                      ML_base, ML_bits,

                                                      ML_defaultDTable, dctx->fseEntropy,

                                                      dctx->ddictIsCold, nbSeq,

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

                                                      ZSTD_DCtx_get_bmi2(dctx));

            RETURN_ERROR_IF(ZSTD_isError(mlhSize), corruption_detected, "ZSTD_buildSeqTable failed");

            ip += mlhSize;

        }

    }

    return ip-istart;

}

typedef struct {

    size_t litLength;

    size_t matchLength;

    size_t offset;

} seq_t;

typedef struct {

    size_t state;

    const ZSTD_seqSymbol* table;

} ZSTD_fseState;

typedef struct {

    BIT_DStream_t DStream;

    ZSTD_fseState stateLL;

    ZSTD_fseState stateOffb;

    ZSTD_fseState stateML;

    size_t prevOffset[ZSTD_REP_NUM];

} seqState_t;

/*! ZSTD_overlapCopy8() :

 *  Copies 8 bytes from ip to op and updates op and ip where ip <= op.

 *  If the offset is < 8 then the offset is spread to at least 8 bytes.

 *

 *  Precondition: *ip <= *op

 *  Postcondition: *op - *op >= 8

 */

HINT_INLINE void ZSTD_overlapCopy8(BYTE** op, BYTE const** ip, size_t offset) {

    assert(*ip <= *op);

    if (offset < 8) {

        /* close range match, overlap */

        static const U32 dec32table[] = { 0, 1, 2, 1, 4, 4, 4, 4 };   /* added */

        static const int dec64table[] = { 8, 8, 8, 7, 8, 9,10,11 };   /* subtracted */

        int const sub2 = dec64table[offset];

        (*op)[0] = (*ip)[0];

        (*op)[1] = (*ip)[1];

        (*op)[2] = (*ip)[2];

        (*op)[3] = (*ip)[3];

        *ip += dec32table[offset];

        ZSTD_copy4(*op+4, *ip);

        *ip -= sub2;

    } else {

        ZSTD_copy8(*op, *ip);

    }

    *ip += 8;

    *op += 8;

    assert(*op - *ip >= 8);

}

/*! ZSTD_safecopy() :

 *  Specialized version of memcpy() that is allowed to READ up to WILDCOPY_OVERLENGTH past the input buffer

 *  and write up to 16 bytes past oend_w (op >= oend_w is allowed).

 *  This function is only called in the uncommon case where the sequence is near the end of the block. It

 *  should be fast for a single long sequence, but can be slow for several short sequences.

 *

 *  @param ovtype controls the overlap detection

 *         - ZSTD_no_overlap: The source and destination are guaranteed to be at least WILDCOPY_VECLEN bytes apart.

 *         - ZSTD_overlap_src_before_dst: The src and dst may overlap and may be any distance apart.

 *           The src buffer must be before the dst buffer.

 */

static void ZSTD_safecopy(BYTE* op, const BYTE* const oend_w, BYTE const* ip, ptrdiff_t length, ZSTD_overlap_e ovtype) {

    ptrdiff_t const diff = op - ip;

    BYTE* const oend = op + length;

    assert((ovtype == ZSTD_no_overlap && (diff <= -8 || diff >= 8 || op >= oend_w)) ||

           (ovtype == ZSTD_overlap_src_before_dst && diff >= 0));

    if (length < 8) {

        /* Handle short lengths. */

        while (op < oend) *op++ = *ip++;

        return;

    }

    if (ovtype == ZSTD_overlap_src_before_dst) {

        /* Copy 8 bytes and ensure the offset >= 8 when there can be overlap. */

        assert(length >= 8);

        ZSTD_overlapCopy8(&op, &ip, diff);

        length -= 8;

        assert(op - ip >= 8);

        assert(op <= oend);

    }

    if (oend <= oend_w) {

        /* No risk of overwrite. */

        ZSTD_wildcopy(op, ip, length, ovtype);

        return;

    }

    if (op <= oend_w) {

        /* Wildcopy until we get close to the end. */

        assert(oend > oend_w);

        ZSTD_wildcopy(op, ip, oend_w - op, ovtype);

        ip += oend_w - op;

        op += oend_w - op;

    }

    /* Handle the leftovers. */

    while (op < oend) *op++ = *ip++;

}

/* ZSTD_safecopyDstBeforeSrc():

 * This version allows overlap with dst before src, or handles the non-overlap case with dst after src

 * Kept separate from more common ZSTD_safecopy case to avoid performance impact to the safecopy common case */

static void ZSTD_safecopyDstBeforeSrc(BYTE* op, const BYTE* ip, ptrdiff_t length) {

    ptrdiff_t const diff = op - ip;

    BYTE* const oend = op + length;

    if (length < 8 || diff > -8) {

        /* Handle short lengths, close overlaps, and dst not before src. */

        while (op < oend) *op++ = *ip++;

        return;

    }

    if (op <= oend - WILDCOPY_OVERLENGTH && diff < -WILDCOPY_VECLEN) {

        ZSTD_wildcopy(op, ip, oend - WILDCOPY_OVERLENGTH - op, ZSTD_no_overlap);

        ip += oend - WILDCOPY_OVERLENGTH - op;

        op += oend - WILDCOPY_OVERLENGTH - op;

    }

    /* Handle the leftovers. */

    while (op < oend) *op++ = *ip++;

}

/* ZSTD_execSequenceEnd():

 * This version handles cases that are near the end of the output buffer. It requires

 * more careful checks to make sure there is no overflow. By separating out these hard

 * and unlikely cases, we can speed up the common cases.

 *

 * NOTE: This function needs to be fast for a single long sequence, but doesn't need

 * to be optimized for many small sequences, since those fall into ZSTD_execSequence().

 */

FORCE_NOINLINE

ZSTD_ALLOW_POINTER_OVERFLOW_ATTR

size_t ZSTD_execSequenceEnd(BYTE* op,

    BYTE* const oend, seq_t sequence,

    const BYTE** litPtr, const BYTE* const litLimit,

    const BYTE* const prefixStart, const BYTE* const virtualStart, const BYTE* const dictEnd)

{

    BYTE* const oLitEnd = op + sequence.litLength;

    size_t const sequenceLength = sequence.litLength + sequence.matchLength;

    const BYTE* const iLitEnd = *litPtr + sequence.litLength;

    const BYTE* match = oLitEnd - sequence.offset;

    BYTE* const oend_w = oend - WILDCOPY_OVERLENGTH;

    /* bounds checks : careful of address space overflow in 32-bit mode */