text: ///////////////////////////////////////////////////////////////////////////
  //
  // 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 "ImfFastHuf.h"
  #include "Iex.h"
  #include <cstring>
  #include <cassert>
  #include <algorithm>
  
  
  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 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 = 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 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.
      // Assumes that hufClearDecTable(hdecod) has already been called.
      //
  
      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)
  {
      //
      // 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 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 = 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)
  {
      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;
  
      // 
      // 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);
          fhd.decode ((unsigned char*)ptr, nBits, raw, nRaw);
      }
      else
      {
          AutoArray <Int64, 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
  