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

   huff0 huffman decoder,

   part of Finite State Entropy library

   Copyright (C) 2013-present, Yann Collet.

   BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)

   Redistribution and use in source and binary forms, with or without

   modification, are permitted provided that the following conditions are

   met:

       * Redistributions of source code must retain the above copyright

   notice, this list of conditions and the following disclaimer.

       * Redistributions in binary form must reproduce the above

   copyright notice, this list of conditions and the following disclaimer

   in the documentation and/or other materials provided with the

   distribution.

   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS

   "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT

   LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR

   A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT

   OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,

   SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT

   LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,

   DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY

   THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT

   (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE

   OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

    You can contact the author at :

    - FSE+HUF source repository : https://github.com/Cyan4973/FiniteStateEntropy

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

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

*  Dependencies

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

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

#include "compiler.h"

#include "bitstream.h"  /* BIT_* */

#include "fse.h"        /* to compress headers */

#define HUF_STATIC_LINKING_ONLY

#include "huf.h"

#include "error_private.h"

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

*  Macros

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

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

 * Huffman decompression implementations. You can't force in both directions

 * at the same time.

 */

#if defined(HUF_FORCE_DECOMPRESS_X1) && \

    defined(HUF_FORCE_DECOMPRESS_X2)

#error "Cannot force the use of the X1 and X2 decoders at the same time!"

#endif

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

*  Error Management

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

#define HUF_isError ERR_isError

#define CHECK_F(f) { size_t const err_ = (f); if (HUF_isError(err_)) return err_; }

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

*  Byte alignment for workSpace management

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

#define HUF_ALIGN(x, a)         HUF_ALIGN_MASK((x), (a) - 1)

#define HUF_ALIGN_MASK(x, mask) (((x) + (mask)) & ~(mask))

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

*  BMI2 Variant Wrappers

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

#if DYNAMIC_BMI2

#define HUF_DGEN(fn)                                                        \

                                                                            \

    static size_t fn##_default(                                             \

                  void* dst,  size_t dstSize,                               \

            const void* cSrc, size_t cSrcSize,                              \

            const HUF_DTable* DTable)                                       \

    {                                                                       \

        return fn##_body(dst, dstSize, cSrc, cSrcSize, DTable);             \

    }                                                                       \

                                                                            \

    static TARGET_ATTRIBUTE("bmi2") size_t fn##_bmi2(                       \

                  void* dst,  size_t dstSize,                               \

            const void* cSrc, size_t cSrcSize,                              \

            const HUF_DTable* DTable)                                       \

    {                                                                       \

        return fn##_body(dst, dstSize, cSrc, cSrcSize, DTable);             \

    }                                                                       \

                                                                            \

    static size_t fn(void* dst, size_t dstSize, void const* cSrc,           \

                     size_t cSrcSize, HUF_DTable const* DTable, int bmi2)   \

    {                                                                       \

        if (bmi2) {                                                         \

            return fn##_bmi2(dst, dstSize, cSrc, cSrcSize, DTable);         \

        }                                                                   \

        return fn##_default(dst, dstSize, cSrc, cSrcSize, DTable);          \

    }

#else

#define HUF_DGEN(fn)                                                        \

    static size_t fn(void* dst, size_t dstSize, void const* cSrc,           \

                     size_t cSrcSize, HUF_DTable const* DTable, int bmi2)   \

    {                                                                       \

        (void)bmi2;                                                         \

        return fn##_body(dst, dstSize, cSrc, cSrcSize, DTable);             \

    }

#endif

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

/*  generic DTableDesc       */

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

typedef struct { BYTE maxTableLog; BYTE tableType; BYTE tableLog; BYTE reserved; } DTableDesc;

static DTableDesc HUF_getDTableDesc(const HUF_DTable* table)

{

    DTableDesc dtd;

    memcpy(&dtd, table, sizeof(dtd));

    return dtd;

}

#ifndef HUF_FORCE_DECOMPRESS_X2

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

/*  single-symbol decoding   */

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

typedef struct { BYTE byte; BYTE nbBits; } HUF_DEltX1;   /* single-symbol decoding */

size_t HUF_readDTableX1_wksp(HUF_DTable* DTable, const void* src, size_t srcSize, void* workSpace, size_t wkspSize)

{

    U32 tableLog = 0;

    U32 nbSymbols = 0;

    size_t iSize;

    void* const dtPtr = DTable + 1;

    HUF_DEltX1* const dt = (HUF_DEltX1*)dtPtr;

    U32* rankVal;

    BYTE* huffWeight;

    size_t spaceUsed32 = 0;

    rankVal = (U32 *)workSpace + spaceUsed32;

    spaceUsed32 += HUF_TABLELOG_ABSOLUTEMAX + 1;

    huffWeight = (BYTE *)((U32 *)workSpace + spaceUsed32);

    spaceUsed32 += HUF_ALIGN(HUF_SYMBOLVALUE_MAX + 1, sizeof(U32)) >> 2;

    if ((spaceUsed32 << 2) > wkspSize) return ERROR(tableLog_tooLarge);

    DEBUG_STATIC_ASSERT(sizeof(DTableDesc) == sizeof(HUF_DTable));

    /* memset(huffWeight, 0, sizeof(huffWeight)); */   /* is not necessary, even though some analyzer complain ... */

    iSize = HUF_readStats(huffWeight, HUF_SYMBOLVALUE_MAX + 1, rankVal, &nbSymbols, &tableLog, src, srcSize);

    if (HUF_isError(iSize)) return iSize;

    /* Table header */

    {   DTableDesc dtd = HUF_getDTableDesc(DTable);

        if (tableLog > (U32)(dtd.maxTableLog+1)) return ERROR(tableLog_tooLarge);   /* DTable too small, Huffman tree cannot fit in */

        dtd.tableType = 0;

        dtd.tableLog = (BYTE)tableLog;

        memcpy(DTable, &dtd, sizeof(dtd));

    }

    /* Calculate starting value for each rank */

    {   U32 n, nextRankStart = 0;

        for (n=1; n<tableLog+1; n++) {

            U32 const current = nextRankStart;

            nextRankStart += (rankVal[n] << (n-1));

            rankVal[n] = current;

    }   }

    /* fill DTable */

    {   U32 n;

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

            U32 const w = huffWeight[n];

            U32 const length = (1 << w) >> 1;

            U32 u;

            HUF_DEltX1 D;

            D.byte = (BYTE)n; D.nbBits = (BYTE)(tableLog + 1 - w);

            for (u = rankVal[w]; u < rankVal[w] + length; u++)

                dt[u] = D;

            rankVal[w] += length;

    }   }

    return iSize;

}

size_t HUF_readDTableX1(HUF_DTable* DTable, const void* src, size_t srcSize)

{

    U32 workSpace[HUF_DECOMPRESS_WORKSPACE_SIZE_U32];

    return HUF_readDTableX1_wksp(DTable, src, srcSize,

                                 workSpace, sizeof(workSpace));

}

FORCE_INLINE_TEMPLATE BYTE

HUF_decodeSymbolX1(BIT_DStream_t* Dstream, const HUF_DEltX1* dt, const U32 dtLog)

{

    size_t const val = BIT_lookBitsFast(Dstream, dtLog); /* note : dtLog >= 1 */

    BYTE const c = dt[val].byte;

    BIT_skipBits(Dstream, dt[val].nbBits);

    return c;

}

#define HUF_DECODE_SYMBOLX1_0(ptr, DStreamPtr) \

    *ptr++ = HUF_decodeSymbolX1(DStreamPtr, dt, dtLog)

#define HUF_DECODE_SYMBOLX1_1(ptr, DStreamPtr)  \

    if (MEM_64bits() || (HUF_TABLELOG_MAX<=12)) \

        HUF_DECODE_SYMBOLX1_0(ptr, DStreamPtr)

#define HUF_DECODE_SYMBOLX1_2(ptr, DStreamPtr) \

    if (MEM_64bits()) \

        HUF_DECODE_SYMBOLX1_0(ptr, DStreamPtr)

HINT_INLINE size_t

HUF_decodeStreamX1(BYTE* p, BIT_DStream_t* const bitDPtr, BYTE* const pEnd, const HUF_DEltX1* const dt, const U32 dtLog)

{

    BYTE* const pStart = p;

    /* up to 4 symbols at a time */

    while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) & (p < pEnd-3)) {

        HUF_DECODE_SYMBOLX1_2(p, bitDPtr);

        HUF_DECODE_SYMBOLX1_1(p, bitDPtr);

        HUF_DECODE_SYMBOLX1_2(p, bitDPtr);

        HUF_DECODE_SYMBOLX1_0(p, bitDPtr);

    }

    /* [0-3] symbols remaining */

    if (MEM_32bits())

        while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) & (p < pEnd))

            HUF_DECODE_SYMBOLX1_0(p, bitDPtr);

    /* no more data to retrieve from bitstream, no need to reload */

    while (p < pEnd)

        HUF_DECODE_SYMBOLX1_0(p, bitDPtr);

    return pEnd-pStart;

}

FORCE_INLINE_TEMPLATE size_t

HUF_decompress1X1_usingDTable_internal_body(

          void* dst,  size_t dstSize,

    const void* cSrc, size_t cSrcSize,

    const HUF_DTable* DTable)

{

    BYTE* op = (BYTE*)dst;

    BYTE* const oend = op + dstSize;

    const void* dtPtr = DTable + 1;

    const HUF_DEltX1* const dt = (const HUF_DEltX1*)dtPtr;

    BIT_DStream_t bitD;

    DTableDesc const dtd = HUF_getDTableDesc(DTable);

    U32 const dtLog = dtd.tableLog;

    CHECK_F( BIT_initDStream(&bitD, cSrc, cSrcSize) );

    HUF_decodeStreamX1(op, &bitD, oend, dt, dtLog);

    if (!BIT_endOfDStream(&bitD)) return ERROR(corruption_detected);

    return dstSize;

}

FORCE_INLINE_TEMPLATE size_t

HUF_decompress4X1_usingDTable_internal_body(

          void* dst,  size_t dstSize,

    const void* cSrc, size_t cSrcSize,

    const HUF_DTable* DTable)

{

    /* Check */

    if (cSrcSize < 10) return ERROR(corruption_detected);  /* strict minimum : jump table + 1 byte per stream */

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

        BYTE* const ostart = (BYTE*) dst;

        BYTE* const oend = ostart + dstSize;

        const void* const dtPtr = DTable + 1;

        const HUF_DEltX1* const dt = (const HUF_DEltX1*)dtPtr;

        /* Init */

        BIT_DStream_t bitD1;

        BIT_DStream_t bitD2;

        BIT_DStream_t bitD3;

        BIT_DStream_t bitD4;

        size_t const length1 = MEM_readLE16(istart);

        size_t const length2 = MEM_readLE16(istart+2);

        size_t const length3 = MEM_readLE16(istart+4);

        size_t const length4 = cSrcSize - (length1 + length2 + length3 + 6);

        const BYTE* const istart1 = istart + 6;  /* jumpTable */

        const BYTE* const istart2 = istart1 + length1;

        const BYTE* const istart3 = istart2 + length2;

        const BYTE* const istart4 = istart3 + length3;

        const size_t segmentSize = (dstSize+3) / 4;

        BYTE* const opStart2 = ostart + segmentSize;

        BYTE* const opStart3 = opStart2 + segmentSize;

        BYTE* const opStart4 = opStart3 + segmentSize;

        BYTE* op1 = ostart;

        BYTE* op2 = opStart2;

        BYTE* op3 = opStart3;

        BYTE* op4 = opStart4;

        U32 endSignal = BIT_DStream_unfinished;

        DTableDesc const dtd = HUF_getDTableDesc(DTable);

        U32 const dtLog = dtd.tableLog;

        if (length4 > cSrcSize) return ERROR(corruption_detected);   /* overflow */

        CHECK_F( BIT_initDStream(&bitD1, istart1, length1) );

        CHECK_F( BIT_initDStream(&bitD2, istart2, length2) );

        CHECK_F( BIT_initDStream(&bitD3, istart3, length3) );

        CHECK_F( BIT_initDStream(&bitD4, istart4, length4) );

        /* up to 16 symbols per loop (4 symbols per stream) in 64-bit mode */

        endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4);

        while ( (endSignal==BIT_DStream_unfinished) && (op4<(oend-3)) ) {

            HUF_DECODE_SYMBOLX1_2(op1, &bitD1);

            HUF_DECODE_SYMBOLX1_2(op2, &bitD2);

            HUF_DECODE_SYMBOLX1_2(op3, &bitD3);

            HUF_DECODE_SYMBOLX1_2(op4, &bitD4);

            HUF_DECODE_SYMBOLX1_1(op1, &bitD1);

            HUF_DECODE_SYMBOLX1_1(op2, &bitD2);

            HUF_DECODE_SYMBOLX1_1(op3, &bitD3);

            HUF_DECODE_SYMBOLX1_1(op4, &bitD4);

            HUF_DECODE_SYMBOLX1_2(op1, &bitD1);

            HUF_DECODE_SYMBOLX1_2(op2, &bitD2);

            HUF_DECODE_SYMBOLX1_2(op3, &bitD3);

            HUF_DECODE_SYMBOLX1_2(op4, &bitD4);

            HUF_DECODE_SYMBOLX1_0(op1, &bitD1);

            HUF_DECODE_SYMBOLX1_0(op2, &bitD2);

            HUF_DECODE_SYMBOLX1_0(op3, &bitD3);

            HUF_DECODE_SYMBOLX1_0(op4, &bitD4);

            BIT_reloadDStream(&bitD1);

            BIT_reloadDStream(&bitD2);

            BIT_reloadDStream(&bitD3);

            BIT_reloadDStream(&bitD4);

        }

        /* check corruption */

        /* note : should not be necessary : op# advance in lock step, and we control op4.

         *        but curiously, binary generated by gcc 7.2 & 7.3 with -mbmi2 runs faster when >=1 test is present */

        if (op1 > opStart2) return ERROR(corruption_detected);

        if (op2 > opStart3) return ERROR(corruption_detected);

        if (op3 > opStart4) return ERROR(corruption_detected);

        /* note : op4 supposed already verified within main loop */

        /* finish bitStreams one by one */

        HUF_decodeStreamX1(op1, &bitD1, opStart2, dt, dtLog);

        HUF_decodeStreamX1(op2, &bitD2, opStart3, dt, dtLog);

        HUF_decodeStreamX1(op3, &bitD3, opStart4, dt, dtLog);

        HUF_decodeStreamX1(op4, &bitD4, oend,     dt, dtLog);

        /* check */

        { U32 const endCheck = BIT_endOfDStream(&bitD1) & BIT_endOfDStream(&bitD2) & BIT_endOfDStream(&bitD3) & BIT_endOfDStream(&bitD4);

          if (!endCheck) return ERROR(corruption_detected); }

        /* decoded size */

        return dstSize;

    }

}

typedef size_t (*HUF_decompress_usingDTable_t)(void *dst, size_t dstSize,

                                               const void *cSrc,

                                               size_t cSrcSize,

                                               const HUF_DTable *DTable);

HUF_DGEN(HUF_decompress1X1_usingDTable_internal)

HUF_DGEN(HUF_decompress4X1_usingDTable_internal)

size_t HUF_decompress1X1_usingDTable(

          void* dst,  size_t dstSize,

    const void* cSrc, size_t cSrcSize,

    const HUF_DTable* DTable)

{

    DTableDesc dtd = HUF_getDTableDesc(DTable);

    if (dtd.tableType != 0) return ERROR(GENERIC);

    return HUF_decompress1X1_usingDTable_internal(dst, dstSize, cSrc, cSrcSize, DTable, /* bmi2 */ 0);

}

size_t HUF_decompress1X1_DCtx_wksp(HUF_DTable* DCtx, void* dst, size_t dstSize,

                                   const void* cSrc, size_t cSrcSize,

                                   void* workSpace, size_t wkspSize)

{

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

    size_t const hSize = HUF_readDTableX1_wksp(DCtx, cSrc, cSrcSize, workSpace, wkspSize);

    if (HUF_isError(hSize)) return hSize;

    if (hSize >= cSrcSize) return ERROR(srcSize_wrong);

    ip += hSize; cSrcSize -= hSize;

    return HUF_decompress1X1_usingDTable_internal(dst, dstSize, ip, cSrcSize, DCtx, /* bmi2 */ 0);

}

size_t HUF_decompress1X1_DCtx(HUF_DTable* DCtx, void* dst, size_t dstSize,

                              const void* cSrc, size_t cSrcSize)

{

    U32 workSpace[HUF_DECOMPRESS_WORKSPACE_SIZE_U32];

    return HUF_decompress1X1_DCtx_wksp(DCtx, dst, dstSize, cSrc, cSrcSize,

                                       workSpace, sizeof(workSpace));

}

size_t HUF_decompress1X1 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)

{

    HUF_CREATE_STATIC_DTABLEX1(DTable, HUF_TABLELOG_MAX);

    return HUF_decompress1X1_DCtx (DTable, dst, dstSize, cSrc, cSrcSize);

}

size_t HUF_decompress4X1_usingDTable(

          void* dst,  size_t dstSize,

    const void* cSrc, size_t cSrcSize,

    const HUF_DTable* DTable)

{

    DTableDesc dtd = HUF_getDTableDesc(DTable);

    if (dtd.tableType != 0) return ERROR(GENERIC);

    return HUF_decompress4X1_usingDTable_internal(dst, dstSize, cSrc, cSrcSize, DTable, /* bmi2 */ 0);

}

static size_t HUF_decompress4X1_DCtx_wksp_bmi2(HUF_DTable* dctx, void* dst, size_t dstSize,

                                   const void* cSrc, size_t cSrcSize,

                                   void* workSpace, size_t wkspSize, int bmi2)

{

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

    size_t const hSize = HUF_readDTableX1_wksp (dctx, cSrc, cSrcSize,

                                                workSpace, wkspSize);

    if (HUF_isError(hSize)) return hSize;

    if (hSize >= cSrcSize) return ERROR(srcSize_wrong);

    ip += hSize; cSrcSize -= hSize;

    return HUF_decompress4X1_usingDTable_internal(dst, dstSize, ip, cSrcSize, dctx, bmi2);

}

size_t HUF_decompress4X1_DCtx_wksp(HUF_DTable* dctx, void* dst, size_t dstSize,

                                   const void* cSrc, size_t cSrcSize,

                                   void* workSpace, size_t wkspSize)

{

    return HUF_decompress4X1_DCtx_wksp_bmi2(dctx, dst, dstSize, cSrc, cSrcSize, workSpace, wkspSize, 0);

}

size_t HUF_decompress4X1_DCtx (HUF_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)

{

    U32 workSpace[HUF_DECOMPRESS_WORKSPACE_SIZE_U32];

    return HUF_decompress4X1_DCtx_wksp(dctx, dst, dstSize, cSrc, cSrcSize,

                                       workSpace, sizeof(workSpace));

}

size_t HUF_decompress4X1 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)

{

    HUF_CREATE_STATIC_DTABLEX1(DTable, HUF_TABLELOG_MAX);

    return HUF_decompress4X1_DCtx(DTable, dst, dstSize, cSrc, cSrcSize);

}

#endif /* HUF_FORCE_DECOMPRESS_X2 */

#ifndef HUF_FORCE_DECOMPRESS_X1

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

/* double-symbols decoding */

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

typedef struct { U16 sequence; BYTE nbBits; BYTE length; } HUF_DEltX2;  /* double-symbols decoding */

typedef struct { BYTE symbol; BYTE weight; } sortedSymbol_t;

typedef U32 rankValCol_t[HUF_TABLELOG_MAX + 1];

typedef rankValCol_t rankVal_t[HUF_TABLELOG_MAX];

/* HUF_fillDTableX2Level2() :

 * `rankValOrigin` must be a table of at least (HUF_TABLELOG_MAX + 1) U32 */

static void HUF_fillDTableX2Level2(HUF_DEltX2* DTable, U32 sizeLog, const U32 consumed,

                           const U32* rankValOrigin, const int minWeight,

                           const sortedSymbol_t* sortedSymbols, const U32 sortedListSize,

                           U32 nbBitsBaseline, U16 baseSeq)

{

    HUF_DEltX2 DElt;

    U32 rankVal[HUF_TABLELOG_MAX + 1];

    /* get pre-calculated rankVal */

    memcpy(rankVal, rankValOrigin, sizeof(rankVal));

    /* fill skipped values */

    if (minWeight>1) {

        U32 i, skipSize = rankVal[minWeight];

        MEM_writeLE16(&(DElt.sequence), baseSeq);

        DElt.nbBits   = (BYTE)(consumed);

        DElt.length   = 1;

        for (i = 0; i < skipSize; i++)

            DTable[i] = DElt;

    }

    /* fill DTable */

    {   U32 s; for (s=0; s<sortedListSize; s++) {   /* note : sortedSymbols already skipped */

            const U32 symbol = sortedSymbols[s].symbol;

            const U32 weight = sortedSymbols[s].weight;