ImfHuf.cpp

//
// SPDX-License-Identifier: BSD-3-Clause
// Copyright (c) Contributors to the OpenEXR Project.
//

//-----------------------------------------------------------------------------
//
//	16-bit Huffman compression and decompression.
//
//	The source code in this file is derived from the 8-bit
//	Huffman compression and decompression routines written
//	by Christian Rouet for his PIZ image file format.
//
//-----------------------------------------------------------------------------

#include "Iex.h"
#include "ImfAutoArray.h"
#include "ImfFastHuf.h"
#include <ImfHuf.h>
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <cstring>

using namespace std;
using namespace IEX_NAMESPACE;
#include "ImfNamespace.h"

OPENEXR_IMF_INTERNAL_NAMESPACE_SOURCE_ENTER

namespace
{

const int HUF_ENCBITS = 16; // literal (value) bit length
const int HUF_DECBITS = 14; // decoding bit size (>= 8)

const int HUF_ENCSIZE = (1 << HUF_ENCBITS) + 1; // encoding table size
const int HUF_DECSIZE = 1 << HUF_DECBITS;       // decoding table size
const int HUF_DECMASK = HUF_DECSIZE - 1;

struct HufDec
{ // short code		long code
    //-------------------------------
    int  len : 8;  // code length		0
    int  lit : 24; // lit			p size
    int* p;        // 0			lits
};

void
invalidNBits ()
{
    throw InputExc ("Error in header for Huffman-encoded data "
                    "(invalid number of bits).");
}

void
tooMuchData ()
{
    throw InputExc ("Error in Huffman-encoded data "
                    "(decoded data are longer than expected).");
}

void
notEnoughData ()
{
    throw InputExc ("Error in Huffman-encoded data "
                    "(decoded data are shorter than expected).");
}

void
invalidCode ()
{
    throw InputExc ("Error in Huffman-encoded data "
                    "(invalid code).");
}

void
invalidTableSize ()
{
    throw InputExc ("Error in Huffman-encoded data "
                    "(invalid code table size).");
}

void
unexpectedEndOfTable ()
{
    throw InputExc ("Error in Huffman-encoded data "
                    "(unexpected end of code table data).");
}

void
tableTooLong ()
{
    throw InputExc ("Error in Huffman-encoded data "
                    "(code table is longer than expected).");
}

void
invalidTableEntry ()
{
    throw InputExc ("Error in Huffman-encoded data "
                    "(invalid code table entry).");
}

inline uint64_t
hufLength (uint64_t code)
{
    return code & 63;
}

inline uint64_t
hufCode (uint64_t code)
{
    return code >> 6;
}

inline void
outputBits (int nBits, uint64_t bits, uint64_t& c, int& lc, char*& out)
{
    c <<= nBits;
    lc += nBits;

    c |= bits;

    while (lc >= 8)
        *out++ = (c >> (lc -= 8));
}

inline uint64_t
getBits (int nBits, uint64_t& c, int& lc, const char*& in)
{
    while (lc < nBits)
    {
        c = (c << 8) | *(unsigned char*) (in++);
        lc += 8;
    }

    lc -= nBits;
    return (c >> lc) & ((1 << nBits) - 1);
}

//
// ENCODING TABLE BUILDING & (UN)PACKING
//

//
// Build a "canonical" Huffman code table:
//	- for each (uncompressed) symbol, hcode contains the length
//	  of the corresponding code (in the compressed data)
//	- canonical codes are computed and stored in hcode
//	- the rules for constructing canonical codes are as follows:
//	  * shorter codes (if filled with zeroes to the right)
//	    have a numerically higher value than longer codes
//	  * for codes with the same length, numerical values
//	    increase with numerical symbol values
//	- because the canonical code table can be constructed from
//	  symbol lengths alone, the code table can be transmitted
//	  without sending the actual code values
//	- see http://www.compressconsult.com/huffman/
//

#if !defined(OPENEXR_IMF_HAVE_LARGE_STACK)
void
hufCanonicalCodeTable (uint64_t* hcode)
#else
void
hufCanonicalCodeTable (uint64_t hcode[HUF_ENCSIZE])
#endif
{
    uint64_t n[59];

    //
    // For each i from 0 through 58, count the
    // number of different codes of length i, and
    // store the count in n[i].
    //

    for (int i = 0; i <= 58; ++i)
        n[i] = 0;

    for (int i = 0; i < HUF_ENCSIZE; ++i)
        n[hcode[i]] += 1;

    //
    // For each i from 58 through 1, compute the
    // numerically lowest code with length i, and
    // store that code in n[i].
    //

    uint64_t c = 0;

    for (int i = 58; i > 0; --i)
    {
        uint64_t nc = ((c + n[i]) >> 1);
        n[i]        = c;
        c           = nc;
    }

    //
    // hcode[i] contains the length, l, of the
    // code for symbol i.  Assign the next available
    // code of length l to the symbol and store both
    // l and the code in hcode[i].
    //

    for (int i = 0; i < HUF_ENCSIZE; ++i)
    {
        int l = hcode[i];

        if (l > 0) hcode[i] = l | (n[l]++ << 6);
    }
}

//
// Compute Huffman codes (based on frq input) and store them in frq:
//	- code structure is : [63:lsb - 6:msb] | [5-0: bit length];
//	- max code length is 58 bits;
//	- codes outside the range [im-iM] have a null length (unused values);
//	- original frequencies are destroyed;
//	- encoding tables are used by hufEncode() and hufBuildDecTable();
//
// NB: The following code "(*a == *b) && (a > b))" was added to ensure
//     elements in the heap with the same value are sorted by index.
//     This is to ensure, the STL make_heap()/pop_heap()/push_heap() methods
//     produced a resultant sorted heap that is identical across OSes.
//

struct FHeapCompare
{
    bool operator() (uint64_t* a, uint64_t* b)
    {
        return ((*a > *b) || ((*a == *b) && (a > b)));
    }
};

void
hufBuildEncTable (
    uint64_t* frq, // io: input frequencies [HUF_ENCSIZE], output table
    int*      im,  //  o: min frq index
    int*      iM)       //  o: max frq index
{
    //
    // This function assumes that when it is called, array frq
    // indicates the frequency of all possible symbols in the data
    // that are to be Huffman-encoded.  (frq[i] contains the number
    // of occurrences of symbol i in the data.)
    //
    // The loop below does three things:
    //
    // 1) Finds the minimum and maximum indices that point
    //    to non-zero entries in frq:
    //
    //     frq[im] != 0, and frq[i] == 0 for all i < im
    //     frq[iM] != 0, and frq[i] == 0 for all i > iM
    //
    // 2) Fills array fHeap with pointers to all non-zero
    //    entries in frq.
    //
    // 3) Initializes array hlink such that hlink[i] == i
    //    for all array entries.
    //

    AutoArray<int, HUF_ENCSIZE>       hlink;
    AutoArray<uint64_t*, HUF_ENCSIZE> fHeap;

    *im = 0;

    while (!frq[*im])
        (*im)++;

    int nf = 0;

    for (int i = *im; i < HUF_ENCSIZE; i++)
    {
        hlink[i] = i;

        if (frq[i])
        {
            fHeap[nf] = &frq[i];
            nf++;
            *iM = i;
        }
    }

    //
    // Add a pseudo-symbol, with a frequency count of 1, to frq;
    // adjust the fHeap and hlink array accordingly.  Function
    // hufEncode() uses the pseudo-symbol for run-length encoding.
    //

    (*iM)++;
    frq[*iM]  = 1;
    fHeap[nf] = &frq[*iM];
    nf++;

    //
    // Build an array, scode, such that scode[i] contains the number
    // of bits assigned to symbol i.  Conceptually this is done by
    // constructing a tree whose leaves are the symbols with non-zero
    // frequency:
    //
    //     Make a heap that contains all symbols with a non-zero frequency,
    //     with the least frequent symbol on top.
    //
    //     Repeat until only one symbol is left on the heap:
    //
    //         Take the two least frequent symbols off the top of the heap.
    //         Create a new node that has first two nodes as children, and
    //         whose frequency is the sum of the frequencies of the first
    //         two nodes.  Put the new node back into the heap.
    //
    // The last node left on the heap is the root of the tree.  For each
    // leaf node, the distance between the root and the leaf is the length
    // of the code for the corresponding symbol.
    //
    // The loop below doesn't actually build the tree; instead we compute
    // the distances of the leaves from the root on the fly.  When a new
    // node is added to the heap, then that node's descendants are linked
    // into a single linear list that starts at the new node, and the code
    // lengths of the descendants (that is, their distance from the root
    // of the tree) are incremented by one.
    //

    make_heap (&fHeap[0], &fHeap[nf], FHeapCompare ());

    AutoArray<uint64_t, HUF_ENCSIZE> scode;
    memset (scode, 0, sizeof (uint64_t) * HUF_ENCSIZE);

    while (nf > 1)
    {
        //
        // Find the indices, mm and m, of the two smallest non-zero frq
        // values in fHeap, add the smallest frq to the second-smallest
        // frq, and remove the smallest frq value from fHeap.
        //

        int mm = fHeap[0] - frq;
        pop_heap (&fHeap[0], &fHeap[nf], FHeapCompare ());
        --nf;

        int m = fHeap[0] - frq;
        pop_heap (&fHeap[0], &fHeap[nf], FHeapCompare ());

        frq[m] += frq[mm];
        push_heap (&fHeap[0], &fHeap[nf], FHeapCompare ());

        //
        // The entries in scode are linked into lists with the
        // entries in hlink serving as "next" pointers and with
        // the end of a list marked by hlink[j] == j.
        //
        // Traverse the lists that start at scode[m] and scode[mm].
        // For each element visited, increment the length of the
        // corresponding code by one bit. (If we visit scode[j]
        // during the traversal, then the code for symbol j becomes
        // one bit longer.)
        //
        // Merge the lists that start at scode[m] and scode[mm]
        // into a single list that starts at scode[m].
        //

        //
        // Add a bit to all codes in the first list.
        //

        for (int j = m; true; j = hlink[j])
        {
            scode[j]++;

            assert (scode[j] <= 58);

            if (hlink[j] == j)
            {
                //
                // Merge the two lists.
                //

                hlink[j] = mm;
                break;
            }
        }

        //
        // Add a bit to all codes in the second list
        //

        for (int j = mm; true; j = hlink[j])
        {
            scode[j]++;

            assert (scode[j] <= 58);

            if (hlink[j] == j) break;
        }
    }

    //
    // Build a canonical Huffman code table, replacing the code
    // lengths in scode with (code, code length) pairs.  Copy the
    // code table from scode into frq.
    //

    hufCanonicalCodeTable (scode);
    memcpy (frq, scode, sizeof (uint64_t) * HUF_ENCSIZE);
}

//
// Pack an encoding table:
//	- only code lengths, not actual codes, are stored
//	- runs of zeroes are compressed as follows:
//
//	  unpacked		packed
//	  --------------------------------
//	  1 zero		0	(6 bits)
//	  2 zeroes		59
//	  3 zeroes		60
//	  4 zeroes		61
//	  5 zeroes		62
//	  n zeroes (6 or more)	63 n-6	(6 + 8 bits)
//

const int SHORT_ZEROCODE_RUN = 59;
const int LONG_ZEROCODE_RUN  = 63;
const int SHORTEST_LONG_RUN  = 2 + LONG_ZEROCODE_RUN - SHORT_ZEROCODE_RUN;
const int LONGEST_LONG_RUN   = 255 + SHORTEST_LONG_RUN;

void
hufPackEncTable (
    const uint64_t* hcode, // i : encoding table [HUF_ENCSIZE]
    int             im,    // i : min hcode index
    int             iM,    // i : max hcode index
    char**          pcode)          //  o: ptr to packed table (updated)
{
    char*    p  = *pcode;
    uint64_t c  = 0;
    int      lc = 0;

    for (; im <= iM; im++)
    {
        int l = hufLength (hcode[im]);

        if (l == 0)
        {
            int zerun = 1;

            while ((im < iM) && (zerun < LONGEST_LONG_RUN))
            {
                if (hufLength (hcode[im + 1]) > 0) break;
                im++;
                zerun++;
            }

            if (zerun >= 2)
            {
                if (zerun >= SHORTEST_LONG_RUN)
                {
                    outputBits (6, LONG_ZEROCODE_RUN, c, lc, p);
                    outputBits (8, zerun - SHORTEST_LONG_RUN, c, lc, p);
                }
                else
                {
                    outputBits (6, SHORT_ZEROCODE_RUN + zerun - 2, c, lc, p);
                }
                continue;
            }
        }

        outputBits (6, l, c, lc, p);
    }

    if (lc > 0) *p++ = (unsigned char) (c << (8 - lc));

    *pcode = p;
}

//
// Unpack an encoding table packed by hufPackEncTable():
//

void
hufUnpackEncTable (
    const char** pcode, // io: ptr to packed table (updated)
    int          ni,    // i : input size (in bytes)
    int          im,    // i : min hcode index
    int          iM,    // i : max hcode index
    uint64_t*    hcode)    //  o: encoding table [HUF_ENCSIZE]
{
    memset (hcode, 0, sizeof (uint64_t) * HUF_ENCSIZE);

    const char* p  = *pcode;
    uint64_t    c  = 0;
    int         lc = 0;

    for (; im <= iM; im++)
    {
        if (p - *pcode > ni) unexpectedEndOfTable ();

        uint64_t l = hcode[im] = getBits (6, c, lc, p); // code length

        if (l == (uint64_t) LONG_ZEROCODE_RUN)
        {
            if (p - *pcode > ni) unexpectedEndOfTable ();

            int zerun = getBits (8, c, lc, p) + SHORTEST_LONG_RUN;

            if (im + zerun > iM + 1) tableTooLong ();

            while (zerun--)
                hcode[im++] = 0;

            im--;
        }
        else if (l >= (uint64_t) SHORT_ZEROCODE_RUN)
        {
            int zerun = l - SHORT_ZEROCODE_RUN + 2;

            if (im + zerun > iM + 1) tableTooLong ();

            while (zerun--)
                hcode[im++] = 0;

            im--;
        }
    }

    *pcode = const_cast<char*> (p);

    hufCanonicalCodeTable (hcode);
}

//
// DECODING TABLE BUILDING
//

//
// Clear a newly allocated decoding table so that it contains only zeroes.
//

void
hufClearDecTable (HufDec* hdecod) // io: (allocated by caller)
                                  //     decoding table [HUF_DECSIZE]
{
    memset (hdecod, 0, sizeof (HufDec) * HUF_DECSIZE);
}

//
// Build a decoding hash table based on the encoding table hcode:
//	- short codes (<= HUF_DECBITS) are resolved with a single table access;
//	- long code entry allocations are not optimized, because long codes are
//	  unfrequent;
//	- decoding tables are used by hufDecode();
//

void
hufBuildDecTable (
    const uint64_t* hcode, // i : encoding table
    int             im,    // i : min index in hcode
    int             iM,    // i : max index in hcode
    HufDec*         hdecod)        //  o: (allocated by caller)
                           //     decoding table [HUF_DECSIZE]
{
    //
    // Init hashtable & loop on all codes.
    // Assumes that hufClearDecTable(hdecod) has already been called.
    //

    for (; im <= iM; im++)
    {
        uint64_t c = hufCode (hcode[im]);
        int      l = hufLength (hcode[im]);

        if (c >> l)
        {
            //
            // Error: c is supposed to be an l-bit code,
            // but c contains a value that is greater
            // than the largest l-bit number.
            //

            invalidTableEntry ();
        }

        if (l > HUF_DECBITS)
        {
            //
            // Long code: add a secondary entry
            //

            HufDec* pl = hdecod + (c >> (l - HUF_DECBITS));

            if (pl->len)
            {
                //
                // Error: a short code has already
                // been stored in table entry *pl.
                //

                invalidTableEntry ();
            }

            pl->lit++;

            if (pl->p)
            {
                int* p = pl->p;
                pl->p  = new int[pl->lit];

                for (int i = 0; i < pl->lit - 1; ++i)
                    pl->p[i] = p[i];

                delete[] p;
            }
            else { pl->p = new int[1]; }

            pl->p[pl->lit - 1] = im;
        }
        else if (l)
        {
            //
            // Short code: init all primary entries
            //

            HufDec* pl = hdecod + (c << (HUF_DECBITS - l));

            for (uint64_t i = 1 << (HUF_DECBITS - l); i > 0; i--, pl++)
            {
                if (pl->len || pl->p)
                {
                    //
                    // Error: a short code or a long code has
                    // already been stored in table entry *pl.
                    //

                    invalidTableEntry ();
                }

                pl->len = l;
                pl->lit = im;
            }
        }
    }
}

//
// Free the long code entries of a decoding table built by hufBuildDecTable()
//

void
hufFreeDecTable (HufDec* hdecod) // io: Decoding table
{
    for (int i = 0; i < HUF_DECSIZE; i++)
    {
        if (hdecod[i].p)
        {
            delete[] hdecod[i].p;
            hdecod[i].p = 0;
        }
    }
}

//
// ENCODING
//

inline void
outputCode (uint64_t code, uint64_t& c, int& lc, char*& out)
{
    outputBits (hufLength (code), hufCode (code), c, lc, out);
}

inline void
sendCode (
    uint64_t  sCode,
    int       runCount,
    uint64_t  runCode,
    uint64_t& c,
    int&      lc,
    char*&    out)
{
    //
    // Output a run of runCount instances of the symbol sCount.
    // Output the symbols explicitly, or if that is shorter, output
    // the sCode symbol once followed by a runCode symbol and runCount
    // expressed as an 8-bit number.
    //

    if (hufLength (sCode) + hufLength (runCode) + 8 <
        hufLength (sCode) * runCount)
    {
        outputCode (sCode, c, lc, out);
        outputCode (runCode, c, lc, out);
        outputBits (8, runCount, c, lc, out);
    }
    else
    {
        while (runCount-- >= 0)
            outputCode (sCode, c, lc, out);
    }
}

//
// Encode (compress) ni values based on the Huffman encoding table hcode:
//

int hufEncode                     // return: output size (in bits)
    (const uint64_t*       hcode, // i : encoding table
     const unsigned short* in,    // i : uncompressed input buffer
     const int             ni,    // i : input buffer size (in bytes)
     int                   rlc,   // i : rl code
     char*                 out)                   //  o: compressed output buffer
{
    char*    outStart = out;
    uint64_t c        = 0; // bits not yet written to out
    int      lc       = 0; // number of valid bits in c (LSB)
    int      s        = in[0];
    int      cs       = 0;

    //
    // Loop on input values
    //

    for (int i = 1; i < ni; i++)
    {
        //
        // Count same values or send code
        //

        if (s == in[i] && cs < 255) { cs++; }
        else
        {
            sendCode (hcode[s], cs, hcode[rlc], c, lc, out);
            cs = 0;
        }

        s = in[i];
    }

    //
    // Send remaining code
    //

    sendCode (hcode[s], cs, hcode[rlc], c, lc, out);

    if (lc) *out = (c << (8 - lc)) & 0xff;

    return (out - outStart) * 8 + lc;
}

//
// DECODING
//

//
// In order to force the compiler to inline them,
// getChar() and getCode() are implemented as macros
// instead of "inline" functions.
//

#define getChar(c, lc, in)                                                     \
    {                                                                          \
        c = (c << 8) | *(unsigned char*) (in++);                               \
        lc += 8;                                                               \
    }

#define getCode(po, rlc, c, lc, in, out, ob, oe)                               \
    {                                                                          \
        if (po == rlc)                                                         \
        {                                                                      \
            if (lc < 8) getChar (c, lc, in);                                   \
                                                                               \
            lc -= 8;                                                           \
                                                                               \
            unsigned char cs = (c >> lc);                                      \
                                                                               \
            if (out + cs > oe)                                                 \
                tooMuchData ();                                                \
            else if (out - 1 < ob)                                             \
                notEnoughData ();                                              \
                                                                               \
            unsigned short s = out[-1];                                        \
                                                                               \
            while (cs-- > 0)                                                   \
                *out++ = s;                                                    \
        }                                                                      \
        else if (out < oe) { *out++ = po; }                                    \
        else { tooMuchData (); }                                               \
    }

//
// Decode (uncompress) ni bits based on encoding & decoding tables:
//

void
hufDecode (
    const uint64_t* hcode,  // i : encoding table
    const HufDec*   hdecod, // i : decoding table
    const char*     in,     // i : compressed input buffer
    int             ni,     // i : input size (in bits)
    int             rlc,    // i : run-length code
    int             no,     // i : expected output size (in bytes)
    unsigned short* out)    //  o: uncompressed output buffer
{
    uint64_t        c    = 0;
    int             lc   = 0;
    unsigned short* outb = out;
    unsigned short* oe   = out + no;
    const char*     ie   = in + (ni + 7) / 8; // input byte size

    //
    // Loop on input bytes
    //

    while (in < ie)
    {
        getChar (c, lc, in);

        //
        // Access decoding table
        //

        while (lc >= HUF_DECBITS)
        {
            const HufDec pl = hdecod[(c >> (lc - HUF_DECBITS)) & HUF_DECMASK];

            if (pl.len)
            {
                //
                // Get short code
                //

                lc -= pl.len;

                if (lc < 0)
                {
                    invalidCode (); // code length too long
                }
                getCode (pl.lit, rlc, c, lc, in, out, outb, oe);
            }
            else
            {
                if (!pl.p) invalidCode (); // wrong code

                //
                // Search long code
                //

                int j;

                for (j = 0; j < pl.lit; j++)
                {
                    int l = hufLength (hcode[pl.p[j]]);

                    while (lc < l && in < ie) // get more bits
                        getChar (c, lc, in);

                    if (lc >= l)
                    {
                        if (hufCode (hcode[pl.p[j]]) ==
                            ((c >> (lc - l)) & ((uint64_t (1) << l) - 1)))
                        {
                            //
                            // Found : get long code
                            //

                            lc -= l;
                            getCode (pl.p[j], rlc, c, lc, in, out, outb, oe);
                            break;
                        }
                    }
                }

                if (j == pl.lit) invalidCode (); // Not found
            }
        }
    }

    //
    // Get remaining (short) codes
    //

    int i = (8 - ni) & 7;
    c >>= i;
    lc -= i;

    while (lc > 0)
    {
        const HufDec pl = hdecod[(c << (HUF_DECBITS - lc)) & HUF_DECMASK];

        if (pl.len)
        {
            lc -= pl.len;
            if (lc < 0)
            {
                invalidCode (); // code length too long
            }
            getCode (pl.lit, rlc, c, lc, in, out, outb, oe);
        }
        else
        {
            invalidCode (); // wrong (long) code
        }
    }

    if (out - outb != no) notEnoughData ();
}

#if !defined(OPENEXR_IMF_HAVE_LARGE_STACK)
void
countFrequencies (uint64_t* freq, const unsigned short data[/*n*/], int n)
#else
void
countFrequencies (
    uint64_t freq[HUF_ENCSIZE], const unsigned short data[/*n*/], int n)
#endif
{
    for (int i = 0; i < HUF_ENCSIZE; ++i)
        freq[i] = 0;

    for (int i = 0; i < n; ++i)
        ++freq[data[i]];
}

void
writeUInt (char buf[4], unsigned int i)
{
    unsigned char* b = (unsigned char*) buf;

    b[0] = i;
    b[1] = i >> 8;
    b[2] = i >> 16;
    b[3] = i >> 24;
}

unsigned int
readUInt (const char buf[4])
{
    const unsigned char* b = (const unsigned char*) buf;

    return (b[0] & 0x000000ff) | ((b[1] << 8) & 0x0000ff00) |
           ((b[2] << 16) & 0x00ff0000) | ((b[3] << 24) & 0xff000000);
}

} // namespace

//
// EXTERNAL INTERFACE
//

int
hufCompress (const unsigned short raw[], int nRaw, char compressed[])
{
    if (nRaw == 0) return 0;

    AutoArray<uint64_t, HUF_ENCSIZE> freq;

    countFrequencies (freq, raw, nRaw);

    int im = 0;
    int iM = 0;
    hufBuildEncTable (freq, &im, &iM);

    char* tableStart = compressed + 20;
    char* tableEnd   = tableStart;
    hufPackEncTable (freq, im, iM, &tableEnd);
    int tableLength = tableEnd - tableStart;

    char* dataStart  = tableEnd;
    int   nBits      = hufEncode (freq, raw, nRaw, iM, dataStart);
    int   dataLength = (nBits + 7) / 8;

    writeUInt (compressed, im);
    writeUInt (compressed + 4, iM);
    writeUInt (compressed + 8, tableLength);
    writeUInt (compressed + 12, nBits);
    writeUInt (compressed + 16, 0); // room for future extensions

    return dataStart + dataLength - compressed;
}

void
hufUncompress (
    const char compressed[], int nCompressed, unsigned short raw[], int nRaw)
{
    //
    // need at least 20 bytes for header
    //
    if (nCompressed < 20)
    {
        if (nRaw != 0) notEnoughData ();

        return;
    }

    int im = readUInt (compressed);
    int iM = readUInt (compressed + 4);
    // int tableLength = readUInt (compressed + 8);
    int nBits = readUInt (compressed + 12);

    if (im < 0 || im >= HUF_ENCSIZE || iM < 0 || iM >= HUF_ENCSIZE)
        invalidTableSize ();

    const char* ptr = compressed + 20;

    uint64_t nBytes = (static_cast<uint64_t> (nBits) + 7) / 8;

    if (ptr + nBytes > compressed + nCompressed)
    {
        notEnoughData ();
        return;
    }

    //
    // Fast decoder needs at least 2x64-bits of compressed data, and
    // needs to be run-able on this platform. Otherwise, fall back
    // to the original decoder
    //

    if (FastHufDecoder::enabled () && nBits > 128)
    {
        FastHufDecoder fhd (ptr, nCompressed - (ptr - compressed), im, iM, iM);

        // must be nBytes remaining in buffer
        if (ptr - compressed + nBytes > static_cast<uint64_t> (nCompressed))
        {
            notEnoughData ();
            return;
        }

        fhd.decode ((unsigned char*) ptr, nBits, raw, nRaw);
    }
    else
    {
        AutoArray<uint64_t, HUF_ENCSIZE> freq;
        AutoArray<HufDec, HUF_DECSIZE>   hdec;

        hufClearDecTable (hdec);

        hufUnpackEncTable (
            &ptr, nCompressed - (ptr - compressed), im, iM, freq);

        try
        {
            if (nBits > 8 * (nCompressed - (ptr - compressed))) invalidNBits ();

            hufBuildDecTable (freq, im, iM, hdec);
            hufDecode (freq, hdec, ptr, nBits, iM, nRaw, raw);
        }
        catch (...)
        {
            hufFreeDecTable (hdec);
            throw;
        }

        hufFreeDecTable (hdec);
    }
}

OPENEXR_IMF_INTERNAL_NAMESPACE_SOURCE_EXIT