
//
//  Title:  PngHuffmanDecoder implementation
//
//  Copyright 1997-1999, Colosseum Builders, Inc.
//  All rights reserved.
//
//  Colosseum Builders, Inc. makes no warranty, expressed or implied
//  with regards to this software. It is provided as is.
//
//  Author:  John M. Miano (miano@colosseumbuilders.com)
//
//  Date:    March 15, 1999
//
//  Version: 1
//
//  Description:
//
//    This class handles Huffman decoding for PNG images.
//
//  Revision History:
//
//

#include <iostream>

#include "checks.h"
#include "inflatehuffmandecoder.h"
#include "inflateinputstream.h"

namespace Colosseum
{

const unsigned int BADCODE = 0xFFFFFFF ;

using namespace std ;
static inline const char *Binary (int vv, int ll)
{
  static const char digit [2] = { '0', '1' } ;
  static char value [33] ;
  value [0] = '\000' ;
  for (unsigned int ii = ll , jj = 0 ; ii > 0 ; -- ii, ++ jj)
  {
    value [jj] = digit [(vv & (1 << (ii-1))) != 0 ] ;
    value [jj+1] = 0 ;
  }
  return value ;
}

//
//  Description:
//
//    This function creates a Huffman table from an array of code lengths.
//
//  Parameters:
//    valuecount: The number of huffman values
//    codelengths: Array of code lengths [0..valuecount-1]
//
//    codelengths [n] is the length of the Huffman code for the value n.
//
void InflateHuffmanDecoder::makeTable (unsigned int maxcodesize,
                                unsigned int valuecount,
                                const unsigned int codelengths [])
{
  maxcode.reserve (maxcodesize) ;
  mincode.reserve (maxcodesize) ;
  valptr.reserve (valuecount) ;
  huff_values.reserve (valuecount) ;
  max_code_size = maxcodesize ;

  // We need this because MSVC++ does not follow standard scoping rules
  // in for statements.
  unsigned int ii ;

  value_count = valuecount ;
  vector<unsigned int> huffsizes (valuecount + 1, 0) ;
  // Set up arrays to associate codes with code lengths. We have to do a copy
  // because this function can be called using fixed Huffman codes.
  for (ii = 0 ; ii < valuecount ; ++ ii)
  {
    huff_values [ii] = ii ;
    huffsizes [ii] = codelengths [ii] ;
  }

  // Sort the values. Primary key is code size. Secondary key is value.
  for (ii = 0 ; ii < valuecount - 1 ; ++ ii)
  {
    for (unsigned int jj = ii + 1 ; jj < valuecount ; ++ jj)
    {
      if (huffsizes [jj] < huffsizes [ii]
          || (huffsizes [jj] == huffsizes [ii]
              && huff_values [jj] < huff_values [ii]))
      {
        unsigned int tmp ;
        tmp = huffsizes [jj] ;
        huffsizes [jj] = huffsizes [ii] ;
        huffsizes [ii] = tmp ;
        tmp = huff_values [jj] ;
        huff_values [jj] = huff_values [ii] ;
        huff_values [ii] = tmp ;
      }
    }
  }

  // These values in these arrays correspond to the elements of the
  // "values" array. The Huffman code for values [N] is huffcodes [N]
  // and the length of the code is huffsizes [N].

  vector<unsigned int> huffcodes (valuecount, 0) ;
  unsigned int lastlen ;
  unsigned int code ;
  for (ii = 0, lastlen = 0, code = 0  ; ii < valuecount ; ++ ii)
  {
    while (lastlen != huffsizes [ii])
    {
      ++ lastlen ;
      code <<= 1 ;
    }

    if (lastlen != 0)
    {
      huffcodes [ii] = code ;
      ++ code ;
    }
  }

  // mincode [n] : The smallest Huffman code of length n + 1.
  // maxcode [n] : The largest Huffman code of length n + 1.
  // valptr [n] : Index into the values array. First value with a code
  //                    of length n + 1.
  for (ii = 0 ; ii < max_code_size ; ++ ii)
  {
    mincode [ii] = BADCODE ;
    maxcode [ii] = -1 ;
  }

  for (ii = 0 ; ii < valuecount ; ++ ii)
    valptr [ii] = 0 ;

  unsigned int last ;
  for (ii = 0, last = 0 ; ii < valuecount ; ++ ii)
  {
    if (last != huffsizes [ii])
    {
       last = huffsizes [ii] ;
       valptr [last-1] = ii ;
       mincode [last-1] = huffcodes [ii] ;
    }
    if (last != 0)
      maxcode [last-1] = huffcodes [ii] ;
  }

  return ;
}

//
//  Description:
//
//    This function decodes the next Huffman-encoded value in the input
//    stream.
//
//  Parameters:
//    decoder:  The PNG Decoder object.
//
#if ! defined (INLINEHUFFMAN) 
int InflateHuffmanDecoder::decode (InflateInputStream &inputstream) const
{
  // We can't cheat by reading multiple bits here because read are reversing the
  // bits as they appear in the input stream.

  int code = inputstream.nextBit () ;
  unsigned int codelength ; // Code length minus 1

  // Here we are taking advantage of the fact that 1 bits are used as
  // a prefix to the longer codes.
  for (codelength = 0 ;
      (code > maxcode [codelength]) ;
      ++ codelength)
  {
    ASSERT (codelength < max_code_size)
    code = ((code << 1) | inputstream.nextBit ()) ;
  }

  // Now we have a Huffman code of length (codelength + 1) that
  // is somewhere in the range
  // mincode [codelength]..maxcode [codelength].

  // This code is the (offset + 1)'th code of (codelength + 1) ;
  int offset = code - mincode [codelength] ;

  // valptr [codelength] is the first code of length (codelength + 1)
  // so now we can look up the value for the Huffman code in the table.
  int index = valptr [codelength] + offset ;
  unsigned int value = huff_values [index] ;
  return value ;
}
#endif

//
//  Description:
//
//    This is a debugging function for writing the contents of the Huffman
//    table to cout.
//
void InflateHuffmanDecoder::dump () const
{
  // We need this because MSVC++ does not follow standard scoping rules
  // for variables declared in for statements.
  unsigned int ii ;

  cout << "   Code Values (" << (int) value_count << "): " << endl ;
  for (ii = 0 ; ii < value_count ; ++ ii)
  {
    cout << dec << " (" << ii << ") " << huff_values [ii]  ;
    if ((ii + 1) % 8 == 0)
      cout << endl ;
  }
  cout << endl ;
  cout << "Length" << "\t\t" << "Mincode" << "\t\t"
       << "Maxcode" << "\t\t" << "Valptr" << endl ;
  cout << "-------------------------------------------------------" << endl ;

  unsigned int firstcode ;
  unsigned int lastcode ;
  for (firstcode = 0 ;
       mincode [firstcode] == BADCODE ;
       ++ firstcode)
  {
    // NoOp
  }
  for (ii = firstcode + 1 ;
       ii < max_code_size ;
       ++ ii)
  {
    if (mincode [ii] != BADCODE)
      lastcode = ii + 1 ;
  }

  for (ii = firstcode ; ii < lastcode ; ++ ii)
  {
    if (mincode [ii] != BADCODE)
    {
      cout << dec << (ii + 1) << "\t\t" << Binary (mincode [ii], ii + 1)
           << "\t\t" << Binary (maxcode [ii], ii + 1) << "\t\t"
           << (int) valptr [ii] << endl ;
    }
  }
  return ;
}


} // End Namespace
