home *** CD-ROM | disk | FTP | other *** search
/ Compressed Image File Formats / CompressedImageFileFormatsJohnMiano.iso / pc / Examples / c14 / src / pnghuffd.cpp < prev   
Encoding:
C/C++ Source or Header  |  1998-12-17  |  6.2 KB  |  225 lines
  1. //
  2. // Copyright (c) 1997,1998 Colosseum Builders, Inc.
  3. // All rights reserved.
  4. //
  5. // Colosseum Builders, Inc. makes no warranty, expressed or implied
  6. // with regards to this software. It is provided as is.
  7. //
  8. // See the README.TXT file that came with this software for restrictions
  9. // on the use and redistribution of this file or send E-mail to
  10. // info@colosseumbuilders.com
  11. //
  12.  
  13. //
  14. //  Title:  PngHuffmanDecoder implementation
  15. //
  16. //  Author:  John M. Miano  miano@colosseumbuilders.com
  17. //
  18. //  Description:
  19. //
  20. //    This class handles Huffman decoding for PNG images.
  21. //
  22.  
  23. #include <iostream>
  24.  
  25. #include "pnghuffd.h"
  26. #include "pngdecod.h"
  27.  
  28. const unsigned int BADCODE = 0xFFFFFFF ;
  29.  
  30. using namespace std ;
  31.  
  32. //
  33. //  Description:
  34. //
  35. //    This function creates a Huffman table from an array of code lengths.
  36. //
  37. //  Parameters:
  38. //    valuecount: The number of huffman values
  39. //    codelengths: Array of code lengths [0..valuecount-1]
  40. //
  41. //    codelengths [n] is the length of the Huffman code for the value n.
  42. //
  43. void PngHuffmanDecoder::MakeTable (unsigned int valuecount,
  44.                               const unsigned int codelengths [])
  45. {
  46.   // We need this because MSVC++ does not follow standard scoping rules
  47.   // in for statements.
  48.   unsigned int ii ;
  49.  
  50.   value_count = valuecount ;
  51.   unsigned int huffsizes [PngMaxNumberOfHuffmanCodes + 1] ;
  52.   memset (huffsizes, 0, sizeof (huffsizes)) ;
  53.   // Set up arrays to associate codes with code lengths. We have to do a copy
  54.   // because this function can be called using fixed Huffman codes.
  55.   for (ii = 0 ; ii < valuecount ; ++ ii)
  56.   {
  57.     huff_values [ii] = ii ;
  58.     huffsizes [ii] = codelengths [ii] ;
  59.   }
  60.  
  61.   // Sort the values. Primary key is code size. Secondary key is value.
  62.   for (ii = 0 ; ii < valuecount - 1 ; ++ ii)
  63.   {
  64.     for (unsigned int jj = ii + 1 ; jj < valuecount ; ++ jj)
  65.     {
  66.       if (huffsizes [jj] < huffsizes [ii]
  67.           || (huffsizes [jj] == huffsizes [ii]
  68.               && huff_values [jj] < huff_values [ii]))
  69.       {
  70.         unsigned int tmp ;
  71.         tmp = huffsizes [jj] ;
  72.         huffsizes [jj] = huffsizes [ii] ;
  73.         huffsizes [ii] = tmp ;
  74.         tmp = huff_values [jj] ;
  75.         huff_values [jj] = huff_values [ii] ;
  76.         huff_values [ii] = tmp ;
  77.       }
  78.     }
  79.   }
  80.   // These values in these arrays correspond to the elements of the
  81.   // "values" array. The Huffman code for values [N] is huffcodes [N]
  82.   // and the length of the code is huffsizes [N].
  83.  
  84.   UBYTE2 huffcodes [PngMaxNumberOfHuffmanCodes] ;
  85.   memset (huffcodes, 0, sizeof (huffcodes)) ;
  86.   unsigned int lastlen ;
  87.   unsigned int code ;
  88.   for (ii = 0, lastlen = 0, code = 0  ; ii < valuecount ; ++ ii)
  89.   {
  90.     while (lastlen != huffsizes [ii])
  91.     {
  92.       ++ lastlen ;
  93.       code <<= 1 ;
  94.     }
  95.  
  96.     if (lastlen != 0)
  97.     {
  98.       huffcodes [ii] = code ;
  99.       ++ code ;
  100.     }
  101.   }
  102.  
  103.   // mincode [n] : The smallest Huffman code of length n + 1.
  104.   // maxcode [n] : The largest Huffman code of length n + 1.
  105.   // valptr [n] : Index into the values array. First value with a code
  106.   //                    of length n + 1.
  107.   for (ii = 0 ; ii < MaxHuffmanCodeLength ; ++ ii)
  108.   {
  109.     valptr [ii] = 0 ;
  110.     mincode [ii] = BADCODE ;
  111.     maxcode [ii] = -1 ;
  112.   }
  113.  
  114.   unsigned int last ;
  115.   for (ii = 0, last = 0 ; ii < valuecount ; ++ ii)
  116.   {
  117.     if (last != huffsizes [ii])
  118.     {
  119.        last = huffsizes [ii] ;
  120.        valptr [last-1] = ii ;
  121.        mincode [last-1] = huffcodes [ii] ;
  122.     }
  123.     if (last != 0)
  124.       maxcode [last-1] = huffcodes [ii] ;
  125.   }
  126.   return ;
  127. }
  128.  
  129. //
  130. //  Description:
  131. //
  132. //    This function decodes the next Huffman-encoded value in the input
  133. //    stream.
  134. //
  135. //  Parameters:
  136. //    decoder:  The PNG Decoder object.
  137. //
  138. int PngHuffmanDecoder::Decode (PngDecoder &decoder)
  139. {
  140.    // This function decodes the next byte in the input stream using this
  141.    // Huffman table.
  142.  
  143.    UBYTE2 code = decoder.GetBits (1) ;
  144.    int codelength ; // Called I in the standard.
  145.  
  146.    // Here we are taking advantage of the fact that 1 bits are used as
  147.    // a prefix to the longer codes.
  148.    for (codelength = 0 ;
  149.         (code > maxcode [codelength] && codelength <
  150.          MaxHuffmanCodeLength) ;
  151.         ++ codelength)
  152.    {
  153.       code = (UBYTE2) ((code << 1) | decoder.GetBits (1)) ;
  154.    }
  155.  
  156.    if (codelength >= MaxHuffmanCodeLength)
  157.     throw EPngError ("Bad Huffman Code Length") ;
  158.  
  159.    // Now we have a Huffman code of length (codelength + 1) that
  160.    // is somewhere in the range
  161.    // mincode [codelength]..maxcode [codelength].
  162.  
  163.    // This code is the (offset + 1)'th code of (codelength + 1) ;
  164.    int offset = code - mincode [codelength] ;
  165.  
  166.    // valptr [codelength] is the first code of length (codelength + 1)
  167.    // so now we can look up the value for the Huffman code in the table.
  168.    int index = valptr [codelength] + offset ;
  169.    return huff_values [index] ;
  170. }
  171.  
  172. //
  173. //  Description:
  174. //
  175. //    This is a debugging function for writing the contents of the Huffman
  176. //    table to cout.
  177. //
  178. void PngHuffmanDecoder::Dump () const
  179. {
  180.   // We need this because MSVC++ does not follow standard scoping rules
  181.   // for variables declared in for statements.
  182.   unsigned int ii ;
  183.  
  184.   cout << "   Code Values (" << (int) value_count << "): " << endl ;
  185.   for (ii = 0 ; ii < value_count ; ++ ii)
  186.   {
  187.     cout << dec << " (" << ii << ") " << (UBYTE2) huff_values [ii]  ;
  188.     if ((ii + 1) % 8 == 0)
  189.       cout << endl ;
  190.   }
  191.   cout << endl ;
  192.   cout << "Length" << "\t\t" << "Mincode" << "\t\t"
  193.        << "Maxcode" << "\t\t" << "Valptr" << endl ;
  194.   cout << "-------------------------------------------------------" << endl ;
  195.  
  196.   unsigned int firstcode ;
  197.   unsigned int lastcode ;
  198.   for (firstcode = 0 ;
  199.        mincode [firstcode] == BADCODE ;
  200.        ++ firstcode)
  201.   {
  202.     // NoOp
  203.   }
  204.   for (ii = firstcode + 1 ;
  205.        ii < MaxHuffmanCodeLength ;
  206.        ++ ii)
  207.   {
  208.     if (mincode [ii] != BADCODE)
  209.       lastcode = ii + 1 ;
  210.   }
  211.  
  212.   for (ii = firstcode ; ii < lastcode ; ++ ii)
  213.   {
  214.     if (mincode [ii] != BADCODE)
  215.     {
  216.       cout << dec << (ii + 1) << "\t\t" << Binary (mincode [ii], ii + 1)
  217.            << "\t\t" << Binary (maxcode [ii], ii + 1) << "\t\t"
  218.            << (int) valptr [ii] << endl ;
  219.     }
  220.   }
  221.   return ;
  222. }
  223.  
  224.  
  225.