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

   Huffman decoder, part of New Generation Entropy library

   Copyright (C) 2013-2016, 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

    - Public forum : https://groups.google.com/forum/#!forum/lz4c

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

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

*  Dependencies

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

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

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

#include "fse.h"        /* header compression */

#define HUF_STATIC_LINKING_ONLY

#include "huf.h"

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

*  Error Management

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

#define HUF_STATIC_ASSERT(c) { enum { HUF_static_assert = 1/(int)(!!(c)) }; }   /* use only *after* variable declarations */

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

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

}

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

/*  single-symbol decoding   */

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

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

{

    U32 tableLog = 0;

    U32 nbSymbols = 0;

    size_t iSize;

    void* const dtPtr = DTable + 1;

    HUF_DEltX2* const dt = (HUF_DEltX2*)dtPtr;

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

        dtd.tableType = 0;

        dtd.tableLog = (BYTE)tableLog;

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

    }

    {   U32 n, nextRankStart = 0;

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

            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;

            HUF_DEltX2 D;

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

            rankVal[w] += length;

    }   }

    return iSize;

}

{

    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_SYMBOLX2_0(ptr, DStreamPtr) \

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

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

        HUF_DECODE_SYMBOLX2_0(ptr, DStreamPtr)

#define HUF_DECODE_SYMBOLX2_2(ptr, DStreamPtr) \

    if (MEM_64bits()) \

        HUF_DECODE_SYMBOLX2_0(ptr, DStreamPtr)

{

    BYTE* const pStart = p;

    /* up to 4 symbols at a time */

        HUF_DECODE_SYMBOLX2_2(p, bitDPtr);

        HUF_DECODE_SYMBOLX2_1(p, bitDPtr);

        HUF_DECODE_SYMBOLX2_2(p, bitDPtr);

        HUF_DECODE_SYMBOLX2_0(p, bitDPtr);

    }

    while (p < pEnd)

        HUF_DECODE_SYMBOLX2_0(p, bitDPtr);

    return pEnd-pStart;

}

          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_DEltX2* const dt = (const HUF_DEltX2*)dtPtr;

    BIT_DStream_t bitD;

    DTableDesc const dtd = HUF_getDTableDesc(DTable);

    U32 const dtLog = dtd.tableLog;

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

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

    return dstSize;

}

          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_DEltX2* const dt = (const HUF_DEltX2*)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;

        DTableDesc const dtd = HUF_getDTableDesc(DTable);

        U32 const dtLog = dtd.tableLog;

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

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

            HUF_DECODE_SYMBOLX2_2(op1, &bitD1);

            HUF_DECODE_SYMBOLX2_2(op2, &bitD2);

            HUF_DECODE_SYMBOLX2_2(op3, &bitD3);

            HUF_DECODE_SYMBOLX2_2(op4, &bitD4);

            HUF_DECODE_SYMBOLX2_1(op1, &bitD1);

            HUF_DECODE_SYMBOLX2_1(op2, &bitD2);

            HUF_DECODE_SYMBOLX2_1(op3, &bitD3);

            HUF_DECODE_SYMBOLX2_1(op4, &bitD4);

            HUF_DECODE_SYMBOLX2_2(op1, &bitD1);

            HUF_DECODE_SYMBOLX2_2(op2, &bitD2);

            HUF_DECODE_SYMBOLX2_2(op3, &bitD3);

            HUF_DECODE_SYMBOLX2_2(op4, &bitD4);

            HUF_DECODE_SYMBOLX2_0(op1, &bitD1);

            HUF_DECODE_SYMBOLX2_0(op2, &bitD2);

            HUF_DECODE_SYMBOLX2_0(op3, &bitD3);

            HUF_DECODE_SYMBOLX2_0(op4, &bitD4);

        }

        /* check corruption */

        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_decodeStreamX2(op1, &bitD1, opStart2, dt, dtLog);

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

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

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

        /* check */

        /* decoded size */

        return dstSize;

    }

}