home *** CD-ROM | disk | FTP | other *** search
/ Compressed Image File Formats / CompressedImageFileFormatsJohnMiano.iso / pc / Examples / c06 / src / jpdehuff.cpp < prev    next >
Encoding:
C/C++ Source or Header  |  1998-12-17  |  7.8 KB  |  276 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. // JPEG Decoder Huffman Table Class Implementation
  15. //
  16. // Author:  John M. Miano miano@colosseumbuilders.com
  17. //
  18.  
  19.  
  20. #include "jpdehuff.h"
  21. #include "jpegdeco.h"
  22. #include "jpgexcep.h"
  23.  
  24. using namespace std ;
  25.  
  26. //
  27. //  Description:
  28. //
  29. //    Class defualt constructor
  30. //
  31.  
  32. JpegHuffmanDecoder::JpegHuffmanDecoder ()
  33. {
  34.   table_defined = false ;
  35.   return ;
  36. }
  37.  
  38. //
  39. //  Description:
  40. //
  41. //    This function reads a Huffman table from the input stream. A DHT
  42. //    marker can define more than one Huffman table. This function reads
  43. //    just one of those tables.
  44. //
  45. //  Parameters:
  46. //    decoder:  The JPEG decoder that owns the Huffman table
  47. //
  48. //  Return Value:
  49. //    The size of the Huffman table in the input stream
  50. //    (the number of bytes read).
  51. //
  52. unsigned int JpegHuffmanDecoder::ReadTable (JpegDecoder &decoder)
  53. {
  54.   // We declare this here because MSVC++ does not handle for
  55.   // statement scoping rules correctly.
  56.   unsigned int jj ;
  57.  
  58.   // B.2.4.2
  59.   UBYTE1 huffbits [JpegMaxHuffmanCodeLength] ;
  60.  
  61.   unsigned int count = 0 ; // Count of codes in the Huffman table.
  62.  
  63.   // Read the 16 1-byte length counts and count the number of
  64.   // codes in the table.
  65.   for (jj = 0 ; jj < JpegMaxHuffmanCodeLength ; ++ jj)
  66.   {
  67.     // These values are called Li in the standard.
  68.     huffbits [jj] = decoder.ReadByte () ;
  69.     count += huffbits [jj] ;
  70.   }
  71.   if (count > JpegMaxNumberOfHuffmanCodes)
  72.      throw EJpegBadData ("Huffman count > 256") ;
  73.  
  74.   // Read the Huffman values.
  75.   for (jj = 0 ; jj < count ; ++ jj)
  76.   {
  77.     // These values are called Vi in the standard.
  78.     huff_values [jj] = decoder.ReadByte () ;
  79.   }
  80.  
  81.   // Generate the Structures for Huffman Decoding.
  82.   MakeTable (huffbits) ;
  83.  
  84.   table_defined = true ; // This table can now be used.
  85.  
  86.   return JpegMaxHuffmanCodeLength + count ;
  87. }
  88.  
  89. //
  90. //  Description:
  91. //
  92. //    This function generates the data used for Huffman decoding.
  93. //
  94. //    The implicit outputs are the member variables mincode [n],
  95. //     maxcode [n] and valptr [n]. These are the minimum Huffman Code of
  96. //    length n+1, the maximum Huffman Code of length n+1, and the index
  97. //    into huff_values [] for the first value with a Huffman code of length
  98. //    n+1.
  99. //
  100. //  Parameters:
  101. //    huffibts: The count of Huffman codes of length n+1) 
  102. //
  103. void JpegHuffmanDecoder::MakeTable (UBYTE1 huffbits [JpegMaxHuffmanCodeLength])
  104. {
  105.   // We have to declare the loop indices here because MSVC++ does not
  106.   // handle scoping in for statements correctly.
  107.   unsigned int ii, jj, kk ;
  108.  
  109.   // These values in these arrays correspond to the elements of the
  110.   // "values" array. The Huffman code for values [N] is huffcodes [N]
  111.   // and the length of the code is huffsizes [N].
  112.  
  113.   UBYTE2 huffcodes [JpegMaxNumberOfHuffmanCodes] ;
  114.   unsigned int huffsizes [JpegMaxNumberOfHuffmanCodes + 1] ;
  115.  
  116.   // Section C.2 Figure C.1
  117.   // Convert the array "huff_bits" containing the count of codes
  118.   // for each length 1..16 into an array containing the length for each
  119.   // code.
  120.   for (ii = 0, kk = 0 ; ii < JpegMaxHuffmanCodeLength ; ++ ii)
  121.   {
  122.      for (int jj = 0 ; jj < huffbits [ii] ; ++ jj)
  123.      {
  124.         huffsizes [kk] = ii + 1 ;
  125.         ++ kk ;
  126.      }
  127.      huffsizes [kk] = 0 ;
  128.   }
  129.  
  130.   // Section C.2 Figure C.2
  131.   // Calculate the Huffman code for each Huffman value.
  132.   UBYTE2 code = 0 ;
  133.   unsigned int si ;
  134.   for (kk = 0, si = huffsizes [0] ;
  135.        huffsizes [kk] != 0  ;
  136.        ++ si, code <<= 1)
  137.   {
  138.      for ( ; huffsizes [kk] == si ; ++ code, ++ kk)
  139.      {
  140.         huffcodes [kk] = code ;
  141.      }
  142.   }
  143.  
  144.   // Section F.2.2. Figure F.15
  145.   // Create three arrays.
  146.   // mincode [n] : The smallest Huffman code of length n + 1.
  147.   // maxcode [n] : The largest Huffman code of length n + 1.
  148.   // valptr [n] : Index into the values array. First value with a code
  149.   //                    of length n + 1.
  150.   for (ii=0, jj=0 ; ii < JpegMaxHuffmanCodeLength ; ++ ii)
  151.   {
  152.      // ii is the index into Huffman code lengths
  153.      // jj is the index into Huffman code values
  154.      if (huffbits [ii] != 0)
  155.      {
  156.         // The jj'th Huffman value is the first with a Huffman code
  157.         // of length ii.
  158.         valptr [ii] = jj ;
  159.         mincode [ii] = huffcodes [jj] ;
  160.         jj += huffbits [ii] ;
  161.         maxcode [ii] = huffcodes [jj - 1] ;
  162.      }
  163.      else
  164.      {
  165.         // There are no Huffman codes of length (ii + 1).
  166.         maxcode [ii] = -1 ;
  167.         // An illegal value > maxcode[]
  168.         mincode [ii] = JpegMaxNumberOfHuffmanCodes + 1 ;
  169.         valptr [ii] = 0 ;
  170.      }
  171.   }
  172.   return ;
  173. }
  174.  
  175. //
  176. //  Description:
  177. //
  178. //    This function decodes the next Huffman-encoded value in the input
  179. //    stream.
  180. //
  181. //  Parameters:
  182. //    decoder:  The JPEG decoder that owns the Huffman table.
  183. //
  184. int JpegHuffmanDecoder::Decode (JpegDecoder &decoder)
  185. {
  186.    // This function decodes the next byte in the input stream using this
  187.    // Huffman table.
  188.  
  189.    // Section A F.2.2.3 Figure F.16
  190.  
  191.    UBYTE2 code = decoder.NextBit () ;
  192.    int codelength ; // Called I in the standard.
  193.  
  194.    // Here we are taking advantage of the fact that 1 bits are used as
  195.    // a prefix to the longer codes.
  196.    for (codelength = 0 ;
  197.         (code > maxcode [codelength] && codelength <
  198.          JpegMaxHuffmanCodeLength) ;
  199.         ++ codelength)
  200.    {
  201.       code = (UBYTE2) ((code << 1) | decoder.NextBit ()) ;
  202.    }
  203.  
  204.    if (codelength >= JpegMaxHuffmanCodeLength)
  205.     throw EJpegBadData ("Bad Huffman Code Length") ;
  206.  
  207.    // Now we have a Huffman code of length (codelength + 1) that
  208.    // is somewhere in the range
  209.    // mincode [codelength]..maxcode [codelength].
  210.  
  211.    // This code is the (offset + 1)'th code of (codelength + 1) ;
  212.    int offset = code - mincode [codelength] ;
  213.  
  214.    // valptr [codelength] is the first code of length (codelength + 1)
  215.    // so now we can look up the value for the Huffman code in the table.
  216.    int index = valptr [codelength] + offset ;
  217.    return huff_values [index] ;
  218. }
  219.  
  220. //
  221. //  Description:
  222. //
  223. //    This is a debugging function for writing the contents of the Huffman
  224. //    table to a stream.
  225. //
  226. //  Parameters:
  227. //    strm:  The output stream
  228. //
  229. void JpegHuffmanDecoder::Dump (std::ostream &strm) const
  230. {
  231.   // We have the loop index here because MSVC++ does not handle
  232.   // scoping in for statements correctly.
  233.  
  234.   unsigned int ii ;
  235.  
  236.   int count ;
  237.   for (ii = 0 ; ii < JpegMaxHuffmanCodeLength ; ++ ii)
  238.   {
  239.     if (valptr [ii] < 255)
  240.       count = valptr [ii] ;
  241.   }
  242.  
  243.   strm << "   Code Values: " ;
  244.   for (ii = 0 ; ii < count ; ++ ii)
  245.     strm << dec << ii << hex << (UBYTE2) huff_values [ii] << " " ;
  246.   strm << endl ;
  247.   strm << "Length" << "\t\t" << "Mincode" << "\t\t"
  248.        << "Maxcode" << "\t\t" << "Valptr" << endl ;
  249.   strm << "-------------------------------------------------------" << endl ;
  250.   for (ii = 0 ; ii < JpegMaxHuffmanCodeLength ; ++ ii)
  251.   {
  252.     strm << dec << ii << "\t\t" << (int) mincode [ii] << "\t\t"
  253.          << (int)maxcode [ii] << "\t\t"<< (int) valptr [ii] << endl ;
  254.   }
  255.   return ;
  256. }
  257.  
  258. //
  259. //  Description:
  260. //
  261. //   This function tells if the Huffman table has been defined
  262. //   by the JPEG input stream.  It is used to detect corrupt
  263. //   streams that have scans that use a Huffman table before
  264. //   it has been defined.
  265. //
  266. //  Return Value:
  267. //
  268. //    true => The table has been defind
  269. //    false => The table has not been defined
  270. //
  271.  
  272. bool JpegHuffmanDecoder::Defined () const
  273. {
  274.   return table_defined ;
  275. }
  276.