Logo Search packages:      
Sourcecode: openexr version File versions  Download package

ImfHuf.cpp

///////////////////////////////////////////////////////////////////////////
//
// Copyright (c) 2002, Industrial Light & Magic, a division of Lucas
// Digital Ltd. LLC
// 
// All rights reserved.
// 
// 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.
// *       Neither the name of Industrial Light & Magic nor the names of
// its contributors may be used to endorse or promote products derived
// from this software without specific prior written permission. 
// 
// 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.
//
///////////////////////////////////////////////////////////////////////////




//-----------------------------------------------------------------------------
//
//    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 <ImfHuf.h>
#include <ImfInt64.h>
#include <ImfAutoArray.h>
#include "Iex.h"
#include <string.h>
#include <assert.h>
#include <algorithm>


using namespace std;
using namespace Iex;

namespace Imf {
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 Int64
hufLength (Int64 code)
{
    return code & 63;
}


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


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

    c |= bits;

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


inline Int64
getBits (int nBits, Int64 &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/
//

void
hufCanonicalCodeTable (Int64 hcode[HUF_ENCSIZE])
{
    Int64 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].
    //

    Int64 c = 0;

    for (int i = 58; i > 0; --i)
    {
      Int64 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();
//


struct FHeapCompare
{
    bool operator () (Int64 *a, Int64 *b) {return *a > *b;}
};


void
hufBuildEncTable
    (Int64* 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 <Int64 *, 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 <Int64, HUF_ENCSIZE> scode;
    memset (scode, 0, sizeof (Int64) * 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 (Int64) * 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 Int64* 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;
    Int64 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
     Int64*       hcode)            //  o: encoding table [HUF_ENCSIZE]
{
    memset (hcode, 0, sizeof (Int64) * HUF_ENCSIZE);

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

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

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

      if (l == (Int64) 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 >= (Int64) SHORT_ZEROCODE_RUN)
      {
          int zerun = l - SHORT_ZEROCODE_RUN + 2;

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

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

          im--;
      }
    }

    *pcode = (char *) p;

    hufCanonicalCodeTable (hcode);
}


//
// DECODING TABLE BUILDING
//

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

    memset (hdecod, 0, sizeof (HufDec) * HUF_DECSIZE);

    for (; im <= iM; im++)
    {
      Int64 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 (Int64 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 (Int64 code, Int64 &c, int &lc, char *&out)
{
    outputBits (hufLength (code), hufCode (code), c, lc, out);
}


inline void
sendCode (Int64 sCode, int runCount, Int64 runCode,
        Int64 &c, int &lc, char *&out)
{
    static const int RLMIN = 32; // min count to activate run-length coding

    if (runCount > RLMIN)
    {
      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 Int64*           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;
    Int64 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, oe)    \
{                                   \
    if (po == rlc)                        \
    {                               \
      if (lc < 8)                   \
          getChar(c, lc, in);             \
                                    \
      lc -= 8;                      \
                                    \
      unsigned char cs = (c >> lc);       \
                                    \
      if (out + cs > oe)                  \
          tooMuchData();                  \
                                    \
      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 Int64 *      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
{
    Int64 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;
            getCode (pl.lit, rlc, c, lc, in, out, 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)) & ((Int64(1) << l) - 1)))
                  {
                      //
                      // Found : get long code
                      //

                      lc -= l;
                      getCode (pl.p[j], rlc, c, lc, in, out, 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;
          getCode (pl.lit, rlc, c, lc, in, out, oe);
      }
      else
      {
          invalidCode(); // wrong (long) code
      }
    }

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


void
countFrequencies (Int64 freq[HUF_ENCSIZE],
              const unsigned short data[/*n*/],
              int n)
{
    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 <Int64, HUF_ENCSIZE> freq;

    countFrequencies (freq, raw, nRaw);

    int im, iM;
    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)
{
    if (nCompressed == 0)
    {
      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;

    AutoArray <Int64, HUF_ENCSIZE> freq;
    AutoArray <HufDec, HUF_DECSIZE> 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);
}


} // namespace Imf

Generated by  Doxygen 1.6.0   Back to index