home *** CD-ROM | disk | FTP | other *** search
/ Compressed Image File Formats / CompressedImageFileFormatsJohnMiano.iso / pc / Library / source / pnghuffe.cpp < prev    next >
Encoding:
C/C++ Source or Header  |  1998-12-17  |  12.4 KB  |  418 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:  PngHuffmanEncoder implementation
  15. //
  16. //  Author:  John M. Miano  miano@colosseumbuilders.com
  17. //
  18. //  Description:
  19. //
  20. //    This class handles Huffman Encoding for PNG images.
  21. //
  22.  
  23. #include "pnghuffe.h"
  24. #include "pngencod.h"
  25. #include "pngpvt.h"
  26.  
  27. //
  28. //  Description:
  29. //
  30. //    Default Class Constructor
  31. //
  32. PngHuffmanEncoder::PngHuffmanEncoder ()
  33. {
  34.   frequencies = new unsigned int [PngMaxNumberOfHuffmanCodes] ;
  35.   ehufsi = new UBYTE1 [PngMaxNumberOfHuffmanCodes] ;
  36.   ehufco = new UBYTE2 [PngMaxNumberOfHuffmanCodes] ;
  37.  
  38.   Reset () ;
  39.   return ;
  40. }
  41.  
  42. //
  43. //  Description:
  44. //
  45. //    Class Destructor
  46. //
  47. PngHuffmanEncoder::~PngHuffmanEncoder ()
  48. {
  49.   delete [] frequencies ; frequencies = NULL ;
  50.   delete [] ehufsi ; ehufsi = NULL ;
  51.   delete [] ehufco ; ehufco = NULL ;
  52.   return ;
  53. }
  54.  
  55. //
  56. //  Description:
  57. //
  58. //    After Huffman codes have been generated the object is in a state
  59. //    where it cannot be used to create a new set of code. This function
  60. //    places the object in a state where it can be reused to generate a
  61. //    new set of Huffman Codes.
  62. //
  63. void PngHuffmanEncoder::Reset ()
  64. {
  65.   memset (frequencies, 0, sizeof (*frequencies) * PngMaxNumberOfHuffmanCodes) ;
  66.   return ;
  67. }
  68.  
  69. //
  70. //  Description:
  71. //
  72. //    Function to increment the frequency for a value.
  73. //
  74. //  Parameters:
  75. //    value:  The value to increase the usage frequency of.
  76. //
  77. void PngHuffmanEncoder::IncrementFrequency (unsigned int value)
  78. {
  79.   if (value >= PngMaxNumberOfHuffmanCodes)
  80.     throw EPngError ("Index out of range") ;
  81.  
  82.   ++ frequencies [value] ;
  83.   return ;
  84. }
  85.  
  86. //
  87. //  Description:
  88. //
  89. //    This function generates the Huffman Codes using the frequency data. 
  90. //
  91. //    The outputs from this function are the following member variables:
  92. //
  93. //     ehufsi [n] : The length of the Huffman Code for value "n"
  94. //     ehufco [n] : The Huffman Code for value "n"
  95. //
  96. //    The first two arrays are used to encode Huffman values. The last two
  97. //    are for writing the table to the output file.
  98. //
  99. //    The code generation process is:
  100. //
  101. //    1. Arrange the Huffman Values into a binary tree so that the most
  102. //       frequently used codes are closest to the root of the tree. At the end
  103. //       of this process the temporary array codesize [n] contains the length
  104. //       of the pure Huffman code for the value "n"
  105. //
  106. //    2. Determine the number of Huffman Codes of for each code length. This
  107. //       step places the number of codes of length "n+1" in huffbits[].
  108. //
  109. //    3. The Default places limites on the size of Huffman Codes. If
  110. //       codes longer that the specified limits were generated in the 
  111. //       previous steps then we need to reduce the maximum depth of the 
  112. //       tree created in step 1. The input and output to this step is the
  113. //       array huffbits[] created in the previous step.
  114. //
  115. //    4. Sort the Huffman values in code length order. codesize [n] is the
  116. //       input to this step and huffvalues [n] is the output. At this point
  117. //       all the information needed to write the Huffman Table to the output
  118. //       stream has been found.
  119. //
  120. //    5. Determine the code size for each value. At the end of this step
  121. //       the temporary array huffsizes [n] is the Huffman code length for
  122. //       huffvalues [n].
  123. //
  124. //    6. Determine the Huffman code for each value. The temporary array
  125. //       huffcodes [n] is the Huffman Code of length huffsizes [n] for
  126. //       the value huffvalue [n].
  127. //
  128. //    7. Using huffsizes [] and huffcodes created in steps 6 and 7 create
  129. //       the arrays ehufco [n] and ehufsi [n] giving the Huffman Code and
  130. //       Code Size for n.
  131. //
  132. //  Parameters:
  133. //    maxlength:  The maximum code length to generate
  134. //
  135. void PngHuffmanEncoder::BuildTable (unsigned int maxlength)
  136. {
  137.   bool codestoolong = false ;
  138.  
  139.   // We need these because MSVC++ does not follow standard
  140.   // scoping rules with for statements.
  141.   unsigned int ii, kk, si ;
  142.  
  143.   memset (ehufsi, 0, sizeof (UBYTE1) * PngMaxNumberOfHuffmanCodes) ;
  144.   memset (ehufco, 0, sizeof (UBYTE2) * PngMaxNumberOfHuffmanCodes) ;
  145.  
  146.   // The tmp array is used for validating the integrity of the Huffman code
  147.   // table. We need a temporary array since frequencies [] gets trashed
  148.   // during the code generation process.
  149.   unsigned int tmp [PngMaxNumberOfHuffmanCodes] ;
  150.  
  151.   for (ii = 0 ; ii < PngMaxNumberOfHuffmanCodes ; ++ ii)
  152.        tmp [ii] = frequencies [ii] ;
  153.  
  154.   // Build the Huffman Code Length Lists
  155.   int others [PngMaxNumberOfHuffmanCodes ] ;
  156.   for (ii = 0 ; ii < PngMaxNumberOfHuffmanCodes ; ++ ii)
  157.     others [ii] = -1 ;
  158.  
  159.   unsigned int codesize [PngMaxNumberOfHuffmanCodes] ;
  160.   memset (codesize, 0, sizeof (codesize)) ;
  161.   while (true)
  162.   {
  163.     // Find the two smallest non-zero values
  164.     int v1 = -1 ;
  165.     int v2 = -1 ;
  166.     for (unsigned int ii = 0 ; ii < PngMaxNumberOfHuffmanCodes ; ++ ii)
  167.     {
  168.       if (frequencies [ii] != 0)
  169.       {
  170.         if (v1 < 0 || frequencies [ii] <= frequencies [v1])
  171.         {
  172.           v2 = v1 ;
  173.           v1 = ii ;
  174.         }
  175.         else if (v2 < 0 || frequencies [ii] <= frequencies [v2])
  176.         {
  177.           v2 = ii ;
  178.         }
  179.       }
  180.     }
  181.     if (v2 < 0)
  182.     {
  183.       if (v1 < 0)
  184.         return ; // No codes defined
  185.  
  186.       if (codesize [v1] == 0)
  187.         codesize [v1] = 1 ;  // Only one code defined
  188.       break ;
  189.     }
  190.     // Join the two tree nodes.
  191.     frequencies [v1] = frequencies [v1] + frequencies [v2] ;
  192.     frequencies [v2] = 0 ;
  193.  
  194.     for (++ codesize [v1] ; others [v1] >= 0 ; ++ codesize [v1])
  195.       v1 = others [v1] ;
  196.  
  197.     others [v1] = v2 ;
  198.  
  199.     for (++ codesize [v2] ; others [v2] >= 0 ; ++ codesize [v2])
  200.       v2 = others [v2] ;
  201.   }
  202.  
  203.   // Determine the number of codes of length [n]
  204.   unsigned int huffbits [30] ; // 2x needed for encoding only.
  205.   memset (huffbits, 0, sizeof (huffbits)) ;
  206.   for (ii = 0 ; ii < PngMaxNumberOfHuffmanCodes ; ++ ii)
  207.   {
  208.     if (codesize [ii] != 0)
  209.     {
  210.       ++ huffbits [codesize [ii] - 1] ;
  211.     }
  212.   }
  213.  
  214.   // Ensure that no code is longer than maxlength.
  215.   for (ii = 2 * maxlength -  1 ;
  216.        ii >= maxlength ;
  217.        -- ii)
  218.   {
  219.     while (huffbits [ii] != 0)
  220.     {
  221.       codestoolong = true ; // Remember that we had to reorder the tree
  222.  
  223.       unsigned int jj = ii - 1 ;
  224.       do
  225.       {
  226.         -- jj ;
  227.       }
  228.       while (huffbits [jj] == 0) ;
  229.  
  230.       huffbits [ii] -= 2 ;
  231.       ++ huffbits [ii - 1] ;
  232.       huffbits [jj + 1] += 2 ;
  233.       -- huffbits [jj] ;
  234.     }
  235.   }
  236.  
  237.   // Make sure that the total number of symbols is correct.
  238.   unsigned int count = 0 ;
  239.   for (ii = 0 ; ii < maxlength ; ++ ii)
  240.   {
  241.     count += huffbits [ii] ;
  242.   }
  243.   if (count >= PngMaxNumberOfHuffmanCodes)
  244.     throw EPngError ("INTERNAL ERROR - Too many codes defined") ;
  245.  
  246.   // Sort the values in order of code length
  247.   UBYTE2 huffvalues [PngMaxNumberOfHuffmanCodes] ;
  248.   memset (huffvalues, 0, sizeof (huffvalues)) ;
  249.   for (ii = 1, kk = 0 ; ii < 2 * maxlength ; ++ ii)
  250.   {
  251.     for (unsigned int jj = 0 ; jj < PngMaxNumberOfHuffmanCodes ; ++ jj)
  252.     {
  253.       if (codesize [jj]  == ii)
  254.       {
  255.         huffvalues [kk] = jj ;
  256.         ++ kk ;
  257.       }
  258.     }
  259.   }
  260.  
  261.   // Convert the array "huffbits" containing the count of codes for each
  262.   // length 1..maxlength into an array containing the length for each code.
  263.   unsigned int huffsizes [PngMaxNumberOfHuffmanCodes] ;
  264.   memset (huffsizes, 0, sizeof (huffsizes)) ;
  265.   for (ii = 0, kk = 0 ; ii < maxlength ; ++ ii)
  266.   {
  267.      for (unsigned int jj = 0 ; jj < huffbits [ii] ; ++ jj)
  268.      {
  269.         huffsizes [kk] = ii + 1 ;
  270.         ++ kk ;
  271.      }
  272.      huffsizes [kk] = 0 ;
  273.   }
  274.  
  275.   // Calculate the Huffman code for each Huffman value.
  276.   UBYTE2 code = 0 ;
  277.   unsigned int huffcodes [PngMaxNumberOfHuffmanCodes] ;
  278.   memset (huffcodes, 0, sizeof (huffcodes)) ;
  279.   for (kk = 0, si = huffsizes [0] ;
  280.        huffsizes [kk] != 0  ;
  281.        ++ si, code <<= 1)
  282.   {
  283.      for ( ; huffsizes [kk] == si ; ++ code, ++ kk)
  284.      {
  285.         huffcodes [kk] = code ;
  286.      }
  287.   }
  288.  
  289.   memset (ehufco, 0, sizeof (ehufco)) ;
  290.   memset (ehufsi, 0, sizeof (ehufsi)) ;
  291.   for (kk = 0 ; kk < PngMaxNumberOfHuffmanCodes ; ++ kk)
  292.   {
  293.     if (huffsizes [kk] != 0)
  294.     {
  295.       unsigned int ii = huffvalues [kk] ;
  296.       ehufco [ii] = huffcodes [kk] ;
  297.       ehufsi [ii] = huffsizes [kk] ;
  298.       if (ehufsi [ii] > maxlength)
  299.         throw EPngError ("Invalid Huffman Code Generated") ;
  300.     }
  301.   }
  302.  
  303.   // If the pure Huffman code generation created codes longer than the
  304.   // maximum the it is possible that the order got screwed up. Such a
  305.   // situation could occur if the maximum code length is 15 and during the
  306.   // pure process we the value 150 got assigned a length of 13, 100 a length
  307.   // of 15 and 200 a length of 17. During the process of reducing the code
  308.   // length for 200 it is possible that 150 would have its code length
  309.   // increased to 14 and 100 would have its code length reduced to 14.
  310.   // Unfortunately the Huffman codes would be assigned using the old
  311.   // order so that 150 would get assigned a smaller Huffman code than
  312.   // 100.  Here we fix that and ensure that if ehufsi [ii] == ehufsi [jj]
  313.   //  and ii < jj then ehufco [ii] < ehufco [jj].
  314.   if (codestoolong)
  315.   {
  316.     for (unsigned int ii = 0 ; ii < PngMaxNumberOfHuffmanCodes - 1 ; ++ ii)
  317.     {
  318.       for (unsigned int jj = ii + 1 ; jj < PngMaxNumberOfHuffmanCodes ; ++ jj)
  319.       {
  320.         if (ehufsi [ii] == ehufsi [jj] && ehufco [ii] > ehufco [jj])
  321.         {
  322.           // The codes got out of order so switch them.
  323.           UBYTE2 tmp = ehufco [jj] ;
  324.           ehufco [jj] = ehufco [ii] ;
  325.           ehufco [ii] = tmp ;
  326.         }
  327.       }
  328.     }
  329.   }
  330.   // Validations
  331.   // This remaining code is not necessary other than to ensure the
  332.   // integrity of the Huffman table that is generated.
  333.  
  334.   // Make sure each value is used exactly once.
  335.   for (ii = 0 ; ii < PngMaxNumberOfHuffmanCodes ; ++ ii)
  336.   {
  337.     int count = 0 ;
  338.     if (tmp [ii] != 0)
  339.     {
  340.       if (ehufsi [ii] == 0)
  341.         throw EPngError ("INTERNAL ERROR - Missing Huffman Code Size") ;
  342.  
  343.       for (unsigned int jj = 0 ; jj < PngMaxNumberOfHuffmanCodes ; ++ jj)
  344.       {
  345.         if (ii == huffvalues [jj] && huffsizes [jj] != 0)
  346.           ++ count ;
  347.         if (count > 1)
  348.           throw EPngError ("INTERNAL ERROR - Duplicate Huffman Value") ;
  349.       }
  350.       if (count == 0)
  351.         throw EPngError ("INTERNAL ERROR - Missing Huffman Value") ;
  352.     }
  353.   }
  354.  
  355.   // Ensure that each huffman code is used once annd that the values
  356.   // are in range.
  357.   for (ii = 0 ; ii < PngMaxNumberOfHuffmanCodes ; ++ ii)
  358.   {
  359.     if (ehufsi [ii] != 0)
  360.     {
  361.       if (ehufsi [ii] > maxlength)
  362.         throw EPngError ("INTERNAL ERROR - Invalid Huffman Range") ;
  363.  
  364.       for (unsigned int jj = ii + 1 ; jj < PngMaxNumberOfHuffmanCodes ; ++ jj)
  365.       {
  366.         if (ehufco [ii] == ehufco [jj] && ehufsi [jj] != 0)
  367.           throw EPngError ("INTERNAL ERROR - Duplicate Huffman Code") ;
  368.       }
  369.     }
  370.   }
  371.  
  372.   //
  373.   // In PNG the Huffman codes are stored backwards. Here we reverse
  374.   // each code.
  375.   for (ii = 0 ; ii < PngMaxNumberOfHuffmanCodes ; ++ ii)
  376.   {
  377.     unsigned int value = 0 ;
  378.     unsigned int code = ehufco [ii] ;
  379.     unsigned int size = ehufsi [ii] ;
  380.     for (unsigned int jj = 0 ; jj < ehufsi [ii] ; ++ jj)
  381.     {
  382.       unsigned int bit = (code & (1 << jj)) >> jj ;
  383.       value |= bit << (size - jj - 1) ;
  384.     }
  385.     ehufco [ii] = value ;
  386.   }
  387.  
  388.   return ;
  389. }
  390.  
  391. //
  392. //  Description:
  393. //
  394. //    This function returns the Huffman Code and Code Size for a given value.
  395. //
  396. //  Parameters:
  397. //    value:  The value to encode
  398. //    code:   The Huffman Code
  399. //    size:   The Huffman Code Length
  400. //
  401. void PngHuffmanEncoder::Encode (unsigned int value,
  402.                                 UBYTE2 &code,
  403.                                 UBYTE1 &size) const
  404. {
  405.   if (value >= PngMaxNumberOfHuffmanCodes)
  406.     throw EPngError ("Index Out of Range") ;
  407.  
  408.   if (ehufsi [value] == 0)
  409.     throw EPngError ("INTERNAL ERROR - Missing Huffman Code") ;
  410.  
  411.   code = ehufco [value] ;
  412.   size = ehufsi [value] ;
  413.   return ;
  414. }
  415.  
  416.  
  417.  
  418.