home *** CD-ROM | disk | FTP | other *** search
/ Compressed Image File Formats / CompressedImageFileFormatsJohnMiano.iso / pc / Library / source / pngencod.cpp < prev    next >
Encoding:
C/C++ Source or Header  |  1999-04-07  |  41.1 KB  |  1,543 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:  PNG Encoder Class Implementation
  15. //
  16. //  Author:  John M. Miano miano@colosseumbuilders.com
  17. //
  18. #include <limits.h>
  19.  
  20. #include "pngencod.h"
  21. #include "pngpvt.h"
  22. #include "pngchksm.h"
  23. #include "pnghuffe.h"
  24.  
  25. // Size definitions for the lookahead buffer.
  26. const unsigned int LookaheadSize = (1 << 9) ; // 1st power of 2 greater than 258
  27. const unsigned int LookaheadMask = LookaheadSize - 1 ;
  28.  
  29. // Hash Table size definitions.
  30. const unsigned int HashBits = 5 ;
  31. const unsigned int HashTableSize = 1 << (3 * HashBits) ;
  32.  
  33. // Size of the output buffer. This value defines the maximum size for
  34. // IDAT block. This value must be larger than the size of any non-IDAT
  35. // blocks used to write the image. Other than that the value can be
  36. // selected arbitrarily.
  37. const unsigned int OutputBufferSize = (1 << 13) ;
  38.  
  39. // End of image marker for the lookahead buffer.
  40. const unsigned int ENDIMAGE = 0xFFFF ;
  41.  
  42. static inline Hash (UBYTE1 v1, UBYTE1 v2, UBYTE1 v3)
  43. {
  44.   const unsigned int mask = (1 << HashBits) - 1 ;
  45.   unsigned int value = (v1 & mask )
  46.                      | ((v2 & mask) << HashBits)
  47.                      | ((v3 & mask) << (2 * HashBits)) ;
  48.   return value ;
  49.  
  50. }
  51.  
  52. static void DistanceToCode (unsigned int distance, unsigned int &code,
  53.                             unsigned int &extra, unsigned int &value)
  54. {
  55.   // maxvalue [n] is the maximum distance value for the code n.
  56.   static const unsigned int maxvalue [PngMaxDistanceCodes] =
  57.     {
  58.          1,     2,     3,     4,     6,     8,    12,    16,    24,    32,
  59.         48,    64,    96,   128,   192,   256,   384,   512,   768,  1024,
  60.       1536,  2048,  3072,  4096,  6144,  8192, 12288, 16384, 24576, 32768,
  61.     } ;
  62.   // extras [n] is the number of extra bits for the code n.
  63.   static const unsigned int extras [PngMaxDistanceCodes] =
  64.     {
  65.       0, 0,  0,  0,  1,  1,  2,  2,  3, 3,
  66.       4, 4,  5,  5,  6,  6,  7,  7,  8, 8,
  67.       9, 9, 10, 10, 11, 11, 12, 12, 13, 13,
  68.     } ;
  69.  
  70.   // bases [n] is the smallest distance value for code n.
  71.   static const unsigned int bases [PngMaxDistanceCodes] =
  72.     {
  73.          1,    2,    3,    4,    5,    7,    9,    13,    17,    25,
  74.         33,   49,   65,   97,  129,  193,  257,   385,   513,   769,
  75.       1025, 1537, 2049, 3073, 4097, 6145, 8193, 12289, 16385, 24577,
  76.     } ;
  77.  
  78.   for (code = 0 ; code < PngMaxDistanceCodes ; ++ code)
  79.   {
  80.     if (distance <=  maxvalue [code])
  81.       break ;
  82.   }
  83.   extra = extras [code] ;
  84.   value = distance - bases [code] ;
  85.   return ;
  86. }
  87.  
  88. inline static void LengthToCode (unsigned int length, unsigned int &code,
  89.                                  unsigned int &extra, unsigned int &value)
  90. {
  91.   // codes [n] is the length for for length n - 3.
  92.   static const UBYTE2 codes [PngLongestLength-2] =
  93.     {
  94.       257, 258, 259, 260, 261, 262, 263, 264,
  95.       265, 265, 266, 266, 267, 267, 268, 268,
  96.       269, 269, 269, 269, 270, 270, 270, 270,
  97.       271, 271, 271, 271, 272, 272, 272, 272,
  98.       273, 273, 273, 273, 273, 273, 273, 273,
  99.       274, 274, 274, 274, 274, 274, 274, 274,
  100.       275, 275, 275, 275, 275, 275, 275, 275,
  101.       276, 276, 276, 276, 276, 276, 276, 276,
  102.       277, 277, 277, 277, 277, 277, 277, 277,
  103.       277, 277, 277, 277, 277, 277, 277, 277,
  104.       278, 278, 278, 278, 278, 278, 278, 278,
  105.       278, 278, 278, 278, 278, 278, 278, 278,
  106.       279, 279, 279, 279, 279, 279, 279, 279,
  107.       279, 279, 279, 279, 279, 279, 279, 279,
  108.       280, 280, 280, 280, 280, 280, 280, 280,
  109.       280, 280, 280, 280, 280, 280, 280, 280,
  110.       281, 281, 281, 281, 281, 281, 281, 281,
  111.       281, 281, 281, 281, 281, 281, 281, 281,
  112.       281, 281, 281, 281, 281, 281, 281, 281,
  113.       281, 281, 281, 281, 281, 281, 281, 281,
  114.       282, 282, 282, 282, 282, 282, 282, 282,
  115.       282, 282, 282, 282, 282, 282, 282, 282,
  116.       282, 282, 282, 282, 282, 282, 282, 282,
  117.       282, 282, 282, 282, 282, 282, 282, 282,
  118.       283, 283, 283, 283, 283, 283, 283, 283,
  119.       283, 283, 283, 283, 283, 283, 283, 283,
  120.       283, 283, 283, 283, 283, 283, 283, 283,
  121.       283, 283, 283, 283, 283, 283, 283, 283,
  122.       284, 284, 284, 284, 284, 284, 284, 284,
  123.       284, 284, 284, 284, 284, 284, 284, 284,
  124.       284, 284, 284, 284, 284, 284, 284, 284,
  125.       284, 284, 284, 284, 284, 284, 284, 285,
  126.     } ;
  127.  
  128.   // extras [n] is the number of extra bits for code n.
  129.   static const UBYTE1 extras [PngMaxLengthCodes - PngFirstLengthCode] =
  130.     {
  131.       0, 0, 0, 0, 0, 0, 0, 0,
  132.       1, 1, 1, 1, 2, 2, 2, 2,
  133.       3, 3, 3, 3, 4, 4, 4, 4,
  134.       5, 5, 5, 5, 0, 0, 0, 
  135.     } ;
  136.   static const UBYTE2 basevalues [PngMaxLengthCodes - PngFirstLengthCode] =
  137.     {
  138.         3,   4,   5,   6,   7,   8,   9,  10,
  139.        11,  13,  15,  17,  19,  23,  27,  31,
  140.        35,  43,  51,  59,  67,  83,  99, 115,
  141.       131, 163, 195, 227, 258,   0,   0, 
  142.     } ;
  143.  
  144.   code = codes [length - 3] ;
  145.   extra = extras [code - PngFirstLengthCode] ;
  146.   value = length - basevalues [code - PngFirstLengthCode] ;
  147.   return ;
  148. }
  149.  
  150. //
  151. //  Description:
  152. //  
  153. //    Class Default Constructor
  154. //
  155. PngEncoder::PngEncoder ()
  156. {
  157.   Initialize () ;
  158.   return ;
  159. }
  160.  
  161. //
  162. //  Description:
  163. //
  164. //    Class Copy Constructor
  165. //
  166. PngEncoder::PngEncoder (const PngEncoder &source)
  167. {
  168.   Initialize () ;
  169.   DoCopy (source) ;
  170.   return ;
  171. }
  172.  
  173. //
  174. //  Description:
  175. //
  176. //    Class Destructor
  177. //
  178. PngEncoder::~PngEncoder ()
  179. {
  180.   FreeBuffers () ;
  181.   delete distance_table ;
  182.   delete length_table ;
  183.   delete length_length_table ;
  184.   return ;
  185. }
  186.  
  187. //
  188. //  Descriptor:
  189. //
  190. //    Assignment Operator
  191. //
  192. //  Parameters:
  193. //    source: The object to copy
  194. //
  195. PngEncoder &PngEncoder::operator=(const PngEncoder &source)
  196. {
  197.   DoCopy (source) ;
  198.   return *this ;
  199. }
  200.  
  201. //
  202. //  Description:
  203. //
  204. //    Common class initialization function. This function is
  205. //    called from constructors to initialize the object.
  206. //
  207. void PngEncoder::Initialize ()
  208. {
  209.   MakeCrcTable () ;
  210.   software_string = "Colosseum Builders Image Library" ;
  211.   current_image = NULL ;
  212.   compression_level = DefaultCompression ;
  213.  
  214.   filter_mask = 0x1 ;
  215.  
  216.   for (unsigned int ii = 0 ; ii < FilterBufferCount ; ++ ii)
  217.     filter_buffers [ii] = NULL ;
  218.  
  219.   distance_table = new PngHuffmanEncoder ;
  220.   length_table = new PngHuffmanEncoder ;
  221.   length_length_table = new PngHuffmanEncoder ;
  222.  
  223.   lz_window = NULL ;
  224.   lookahead_buffer = NULL ;
  225.  
  226.   block_buffer = NULL ;
  227.   block_buffer_size = 0x4000 ;
  228.   return ;
  229. }
  230.  
  231. //
  232. //  Description:
  233. //
  234. //    Class copy function. This function is called from the copy 
  235. //    constructor and assignment operator.
  236. //
  237. //  Parameters:
  238. //    source:  The object to copy
  239. //
  240. void PngEncoder::DoCopy (const PngEncoder &source)
  241. {
  242.   title_string = source.title_string ;
  243.   author_string = source.author_string ;
  244.   description_string = source.description_string ;
  245.   copyright_string = source.copyright_string ;
  246.   software_string = source.software_string ;
  247.   disclaimer_string = source.disclaimer_string ;
  248.   warning_string = source.warning_string ;
  249.   source_string = source.source_string ;
  250.   comment_string = source.comment_string ;
  251.   compression_level = source.compression_level ;
  252.   filter_mask = source.filter_mask ;
  253.   block_buffer_size = source.block_buffer_size ;
  254.   BitmapImageEncoder::DoCopy (source) ;
  255.   return ;
  256. }
  257.  
  258. //
  259. //  Description:
  260. //
  261. //    This function writes an image to a PNG stream.
  262. //
  263. //  Parameters:
  264. //    strm:  The output stream
  265. //    image:  The image to outpu
  266. //
  267. void PngEncoder::WriteImage (std::ostream &strm, BitmapImage &image)
  268. {
  269.   current_image = &image ;
  270.   output_stream = &strm ;
  271.  
  272.   try
  273.   {
  274.     DoWrite () ;
  275.   }
  276.   catch (...)
  277.   {
  278.     FreeBuffers () ;
  279.     throw ;
  280.   }
  281.   FreeBuffers () ;
  282.   return ;
  283. }
  284.  
  285. //
  286. //  Description:
  287. //
  288. //    This function frees the buffers allowed during the encoding
  289. //    process.
  290. //
  291. void PngEncoder::FreeBuffers ()
  292. {
  293.   current_image = NULL ;
  294.   output_stream = NULL ;
  295.   delete [] lz_window ; lz_window = NULL ;
  296.   delete [] lookahead_buffer ; lookahead_buffer = NULL ;
  297.   delete [] hash_values ; hash_values = NULL ;
  298.   delete [] hash_table ; hash_table = NULL ;
  299.   delete [] output_buffer ; output_buffer = NULL ;
  300.   for (unsigned int ii = 0 ; ii < FilterBufferCount ; ++ ii)
  301.   {
  302.     delete [] filter_buffers [ii] ; filter_buffers [ii] = NULL ;
  303.   }
  304.   return ;
  305. }
  306.  
  307. //
  308. //  Description:
  309. //
  310. //    This function calculates the hash value from a location
  311. //    in the input stream. We create the hash value by
  312. //    extracting a fixed number of the low order bits from each
  313. //    of the next three data values.
  314. //
  315. //  Parameters:
  316. //    index: The index into the lookahead buffer
  317. //
  318. //  Return Value:
  319. //    The hash value
  320. //
  321. unsigned int PngEncoder::HashValue (unsigned int index)
  322. {
  323.   unsigned int i1 = index & LookaheadMask ;
  324.   unsigned int i2 = (index + 1) & LookaheadMask ;
  325.   unsigned int i3 = (index + 2) & LookaheadMask ;
  326.  
  327.   return Hash (lookahead_buffer [i1],
  328.                lookahead_buffer [i2],
  329.                lookahead_buffer [i3]) ;
  330. }
  331.  
  332. //
  333. //  Description:
  334. //
  335. //    This function finds the longest string in the LZ
  336. //    window that matches the data in the lookahead buffer.
  337. //
  338. //    Since the hash changes can get very long under certain
  339. //    circumstances we use the search_limit to set a limit
  340. //    to how far we search in the tree.
  341. //
  342. //  Parameters:
  343. //    bestlength: The longest match found (0=>No match)
  344. //    bestoffset: The location where the best match was found
  345. //
  346. void PngEncoder::LongestMatch (unsigned int &bestlength,
  347.                                unsigned int &bestoffset)
  348. {
  349.   bestlength = 0 ;
  350.  
  351.   unsigned int hashvalue = HashValue (lookahead_position) ;
  352.   if (hash_table [hashvalue].next == NULL)
  353.     return ;
  354.  
  355.   unsigned int chain ;
  356.   HashEntry *current ;
  357.   for (chain = 0 , current = hash_table [hashvalue].next ;
  358.        current != NULL && chain < search_limit ;
  359.        current = current->next, ++ chain)
  360.   {
  361.     unsigned int src = lookahead_position ;
  362.     unsigned int dest = current->index ;
  363.     unsigned int len  ;
  364.     for (len = 0 ;
  365.          len < PngLongestLength
  366.          && ((current->index + len) & PngWindowMask)
  367.              != lz_position ;
  368.          ++ len, dest = (dest + 1) & PngWindowMask,
  369.          src = (src + 1) & LookaheadMask)
  370.     {
  371.       unsigned int lookahead = lookahead_buffer [src] ;
  372.       unsigned int window = lz_window [dest] ;
  373.       if (lookahead != window)
  374.         break ;
  375.     }
  376.     // We only care about matches longer than 3
  377.     if (len >= 3 && len > bestlength)
  378.     {
  379.       bestlength = len ;
  380.       bestoffset = PngWindowSize
  381.                 - ((PngWindowSize + current->index - lz_position)
  382.                     & PngWindowMask) ;
  383.       if (bestlength == PngLongestLength)
  384.         break ;
  385.     }
  386.   }
  387.   return ;
  388. }
  389.  
  390. //
  391. //  Description:
  392. //
  393. //    This function reads data from the input stream into the
  394. //    lookahead buffer.
  395. //
  396. //  Parameters:
  397. //    count:  The number of bytes to read
  398. //
  399. void PngEncoder::FillBuffer (unsigned int count)
  400. {
  401.   if (image_end)
  402.    return ;
  403.  
  404.   unsigned int index = (lookahead_position + LookaheadSize - count)
  405.                        & LookaheadMask ;
  406.  
  407.   if (current_image->BitCount () != 24)
  408.   {
  409.     // This block handles images with 8-bits per pixel or fewer.
  410.     for (unsigned int ii = 0 ;
  411.          ii < count && ! image_end ;
  412.          ++ ii, ++ index)
  413.     {
  414.       if (image_col >= row_width)
  415.       {
  416.         // We need to advance to the next row.
  417.         image_col = 0 ;
  418.         ++ image_row ;
  419.         if (image_row >= (int) current_image->Height ())
  420.         {
  421.           // We have hit the end of the image.
  422.           lookahead_buffer [index & LookaheadMask] = ENDIMAGE ;
  423.           image_end = true ;
  424.         }
  425.         else
  426.         {
  427.           // Here we start a new row. The data value from this
  428.           // block is the filter code.
  429.           CallProgressFunction (100 * image_row/current_image->Height ()) ;
  430.  
  431.           FilterRow (image_row) ;
  432.           lookahead_buffer [index & LookaheadMask]
  433.               = current_filter ;
  434.           adler_value
  435.               = Adler (adler_value,
  436.                        lookahead_buffer [index & LookaheadMask]) ;
  437.         }
  438.       }
  439.       else
  440.       {
  441.         // Here we are processing the middle of a pixel row.
  442.         lookahead_buffer [index & LookaheadMask]
  443.             = filter_buffers [current_filter][image_col] ;
  444.         adler_value
  445.             = Adler (adler_value,
  446.                      lookahead_buffer [index & LookaheadMask]) ;
  447.         ++ image_col ;
  448.       }
  449.     }
  450.   }
  451.   else
  452.   {
  453.     // Here we handle 24-bits per pixel images.
  454.     for (unsigned int ii = 0 ;
  455.          ii < count && ! image_end ;
  456.          ++ ii, ++ index)
  457.     {
  458.       if (image_col >= row_width)
  459.       {
  460.         // We have hit the end of the row.
  461.         image_col = 0 ;
  462.         ++ image_row ;
  463.         if (image_row >= current_image->Height ())
  464.         {
  465.           // There is no more data in the image.
  466.           lookahead_buffer [index & LookaheadMask] = ENDIMAGE ;
  467.           image_end = true ;
  468.         }
  469.         else
  470.         {
  471.           // Here we are starting a new row. The value
  472.           // we return from here is the filter value.
  473.           CallProgressFunction (100 * image_row/current_image->Height ()) ;
  474.  
  475.           FilterRow (image_row) ;
  476.           lookahead_buffer [index & LookaheadMask]
  477.             = current_filter ;
  478.           adler_value
  479.               = Adler (adler_value,
  480.                        lookahead_buffer [index & LookaheadMask]) ;
  481.         }
  482.       }
  483.       else
  484.       {
  485.         // We are processing the middle of a pixel row.
  486.  
  487.         // We would not have to go through all the trouble we do here
  488.         // if we knew the BitmapImage class stored colors in RGB order.
  489.         // For windows, they have to be in BGR order.
  490.  
  491.         unsigned int color = image_col % 3 ;
  492.         unsigned int col = image_col - color ;
  493.         if (color == 0)
  494.         {
  495.           lookahead_buffer [index & LookaheadMask]
  496.            = filter_buffers [current_filter][col + BitmapImage::RedOffset] ;
  497.         }
  498.         else if (color == 1)
  499.         {
  500.           lookahead_buffer [index & LookaheadMask]
  501.            = filter_buffers [current_filter][col + BitmapImage::GreenOffset] ;
  502.         }
  503.         else
  504.         {
  505.           lookahead_buffer [index & LookaheadMask]
  506.            = filter_buffers [current_filter][col + BitmapImage::BlueOffset] ;
  507.         }
  508.         adler_value
  509.           = Adler (adler_value,
  510.                    lookahead_buffer [index & LookaheadMask]) ;
  511.         ++ image_col ;
  512.       }
  513.     }
  514.   }
  515.   return ;
  516. }
  517.  
  518. //
  519. //  Description:
  520. //
  521. //    This function moves a hash entry corresponding to a position
  522. //    in the LZ window to a specified hash chain.
  523. //
  524. //  Parameter:
  525. //    entry: The Hash Entry (index into the LZ window)
  526. //    hashvalue:  The new hashvalue for the entry.
  527. //
  528. void PngEncoder::MoveHashEntry (unsigned int entry, unsigned int hashvalue)
  529. {
  530.   HashEntry *he = &hash_values [entry] ;
  531.   if (he->previous != NULL)
  532.     he->previous->next = he->next ;
  533.   if (he->next != NULL)
  534.     he->next->previous = he->previous ;
  535.  
  536.   he->next = hash_table [hashvalue].next ;
  537.   he->previous = &hash_table [hashvalue] ;
  538.   hash_table [hashvalue].next = he ;
  539.   if (he->next != NULL)
  540.     he->next->previous = he ;
  541.  
  542.   return ;
  543. }
  544.  
  545. //
  546. //  Description:
  547. //
  548. //    This function finds the length encoding for
  549. //    a length or distance table.
  550. //
  551. //  Parameters:
  552. //    function: The function to process the code
  553. //    lengths: lengths [n] = the length of the huffman code for n.
  554. //    count: The number of coe lengths
  555. //
  556. void PngEncoder::FindLengthCodes (LENGTHFUNCTION function,
  557.                                   UBYTE1 lengths [],
  558.                                   unsigned int count)
  559. {
  560.   for (unsigned int ii = 0, jj ; ii < count ; ii = jj)
  561.   {
  562.     if (lengths [ii] != 0)
  563.     {
  564.       (this->*function) (ii, lengths [ii], 0, 0) ;
  565.       jj = ii + 1 ;
  566.     }
  567.     else
  568.     {
  569.       // Attempt to compact runs of zero length codes.  
  570.       // First find the number of consecutive zeros.
  571.       for (jj = ii + 1;
  572.            lengths [jj] == lengths [jj-1]
  573.            && jj < count ;
  574.            ++ jj)
  575.       {
  576.       }
  577.  
  578.       // We need at least 3 consecutive zeros to compact them.
  579.       switch (jj - ii)
  580.       {
  581.       case 1:
  582.         (this->*function) (ii, lengths [ii], 0, 0) ;
  583.         break ;
  584.       case 2:
  585.         (this->*function) (ii, lengths [ii], 0, 0) ;
  586.         (this->*function) (ii + 1, lengths [ii], 0, 0) ;
  587.         break ;
  588.       default:
  589.         {
  590.           // We have at least three zeros.
  591.  
  592.           int kk = jj - ii ;
  593.           if (kk > 138)
  594.           {
  595.             kk = 138 ;
  596.             jj = ii + kk ;
  597.           }
  598.           if (kk > 10)
  599.           {
  600.             (this->*function) (ii, 18, 7, kk - 11) ;
  601.           }
  602.           else
  603.           {
  604.             (this->*function) (ii, 17, 3, kk - 3) ;
  605.           }
  606.         }
  607.         break ;
  608.       }
  609.     }
  610.   }
  611.   return ;
  612. }
  613.  
  614.  
  615. //
  616. //  Description:
  617. //
  618. //    This function is passed as a parameter to FindLengthCodes.
  619. //    It is use to find the frequency for each code.
  620. //
  621. //  Parameters:
  622. //    code:  The code generated by FindLengthCodes
  623. //
  624. void PngEncoder::GatherLengthCounts (unsigned int,
  625.                                      unsigned int code,
  626.                                      unsigned int,
  627.                                      unsigned int)
  628. {
  629.   length_length_table->IncrementFrequency (code) ;
  630.   return ;
  631. }
  632.  
  633. //
  634. //  Description:
  635. //
  636. //    This function is passed as a parameter to FindLengthCodes.
  637. //    It is use to encode and output the code to the output stream.
  638. //
  639. //  Parameters:
  640. //    code:  The code generated by FindLengthCodes
  641. //    extra:  The number of extra bits of data for the code
  642. //    value:  The extra value
  643. //
  644. void PngEncoder::OutputLengthCounts (unsigned int,   // Index - Not used here
  645.                                      unsigned int code,
  646.                                      unsigned int extra,
  647.                                      unsigned int value)
  648. {
  649.   UBYTE2 huffmancode ;
  650.   UBYTE1 huffmansize ;
  651.   length_length_table->Encode (code, huffmancode, huffmansize) ;
  652.  
  653.   OutputDataBits (huffmancode, huffmansize) ;
  654.   if (extra != 0)
  655.     OutputDataBits (value, extra) ;
  656.  
  657.   return ;
  658. }
  659.  
  660. //
  661. //  Description:
  662. //
  663. //    This function is called to start a new chunk.
  664. //
  665. //  Parameters:
  666. //    type:  The PNG Chunk type (e.g. "IHDR", "IDAT")
  667. //
  668. void PngEncoder::StartChunk (const char type [5])
  669. {
  670.   chunk_type = ChunkType (type) ;
  671.   bit_position = 0 ;
  672.   byte_position = 0 ;
  673.   output_buffer [0] = 0 ;
  674.   return ;
  675. }
  676.  
  677. //
  678. //  Description:
  679. //
  680. //    This function outputs the current chunk.
  681. //
  682. void PngEncoder::WriteCurrentChunk ()
  683. {
  684.   // Calculate the CRC value for the chunk type and data
  685.   UBYTE4 crc = 0xFFFFFFFFL ;
  686.   crc = CRC32 (crc, &chunk_type, sizeof (chunk_type)) ;
  687.   crc = CRC32 (crc, output_buffer, byte_position) ;
  688.   crc ^= 0xFFFFFFFFL ;
  689.   crc = SystemToBigEndian (crc) ;
  690.   // Output the chunk. Length, type, data, CRC
  691.   UBYTE4 length = SystemToBigEndian (byte_position) ;
  692.   output_stream->write ((char *) &length, sizeof (length)) ;
  693.   output_stream->write ((char *) &chunk_type, sizeof (chunk_type)) ;
  694.   output_stream->write ((char *) output_buffer, byte_position) ;
  695.   output_stream->write ((char *) &crc, sizeof (crc)) ;
  696.  
  697.   byte_position = 0 ;
  698.   bit_position = 0 ;
  699.   return ;
  700. }
  701.  
  702. //
  703. //  Description:
  704. //
  705. //    This function writes a block of data to the current chunk.
  706. //
  707. //  Parameters:
  708. //    data: Pointer to the data to write
  709. //    length: Number of bytes to write
  710. //
  711. void PngEncoder::OutputBlock (const void *data, unsigned int length)
  712. {
  713.   if (byte_position + length > OutputBufferSize)
  714.     throw EPngError ("Output Buffer Overrun") ;
  715.  
  716.   memcpy (&output_buffer [byte_position], data, length) ;
  717.   byte_position += length ;
  718.   return;
  719. }
  720.  
  721. //
  722. //  Description:
  723. //
  724. //    This function writes the Adler value calculated for
  725. //    the input data to the current chunk.
  726. //    
  727. void PngEncoder::OutputAdler ()
  728. {
  729.   FlushBitBuffer () ;
  730.   adler_value = SystemToBigEndian (adler_value) ;
  731.   UBYTE1 *buffer = (UBYTE1*) &adler_value ;
  732.   for (unsigned int ii = 0 ; ii < sizeof (adler_value) ; ++ ii)
  733.   {
  734.     if (byte_position == OutputBufferSize)
  735.       WriteCurrentChunk () ;
  736.  
  737.     output_buffer [byte_position] = buffer [ii] ;
  738.     ++ byte_position ;
  739.   }
  740.   return ;
  741. }
  742.  
  743. //
  744. //  Description:
  745. //
  746. //    This function writes a number of data bits within an IDAT block.
  747. //
  748. //  Parameters:
  749. //    data: The bits to output
  750. //    length:  The number of bits to output
  751. //
  752. void PngEncoder::OutputDataBits (unsigned int data, unsigned int length)
  753. {
  754.   for (unsigned int ii = 0 ; ii < length ; ++ ii)
  755.   {
  756.     if (bit_position >= CHAR_BIT)
  757.       FlushBitBuffer () ;
  758.  
  759.     if ((data & (1 << ii)) != 0)
  760.     {
  761.       output_buffer [byte_position] |= (1 << bit_position) ;
  762.     }
  763.     ++ bit_position ;
  764.   }
  765.   return ;
  766. }
  767.  
  768. //
  769. //  Description:
  770. //
  771. //    This function flushes any partial bytes that have been
  772. //    written. This allows us to start writing byte data or 
  773. //    start the next data byte.
  774. //
  775. void PngEncoder::FlushBitBuffer ()
  776. {
  777.   if (bit_position == 0)
  778.     return ;
  779.  
  780.   ++ byte_position ;
  781.   if (byte_position >= OutputBufferSize)
  782.   {
  783.     WriteCurrentChunk () ;
  784.     StartChunk ("IDAT") ;
  785.   }
  786.   output_buffer [byte_position] = 0 ;
  787.   bit_position = 0 ;
  788.   return ;
  789. }
  790.  
  791. //
  792. //  Description:
  793. //
  794. //    This function encodes the image data. Depending upon
  795. //    the function arguments this function either gathers
  796. //    Huffman usage statistics or Huffman-encodes the data.
  797. //
  798. //  Return Value:
  799. //    true => All data in the image has been processed
  800. //    false => More data remains
  801. //
  802. bool PngEncoder::ProcessImageData ()
  803. {
  804.   InitializeHashTable () ;
  805.   // Here we loop until we either fill the block_buffer or
  806.   // reach the end of the image.
  807.   for (block_buffer_count = 0 ;
  808.        block_buffer_count < block_buffer_size - 1
  809.        && lookahead_buffer [lookahead_position]
  810.           != ENDIMAGE ;
  811.        ++ block_buffer_count)
  812.   {
  813.     // See if we can find a match for the input in the
  814.     // LZ winow.
  815.     unsigned int length ;
  816.     unsigned int offset ;
  817.     LongestMatch (length, offset) ;
  818.  
  819.     if (length == 0)
  820.     {
  821.       // There is no match of at least three. Encode this value a
  822.       // literal value.
  823.       UBYTE1 literal = lookahead_buffer [lookahead_position] ;
  824.  
  825.       unsigned int hashvalue = HashValue (lookahead_position) ;
  826.       MoveHashEntry (lz_position, hashvalue) ;
  827.  
  828.       lz_window [lz_position] = literal ;
  829.  
  830.        block_buffer [block_buffer_count] = literal ;
  831.        length_table->IncrementFrequency (literal) ;
  832.  
  833.        lookahead_position
  834.           = (lookahead_position + 1) & LookaheadMask ;
  835.       lz_position = (lz_position + 1) & PngWindowMask ;
  836.  
  837.       FillBuffer (1) ;
  838.     }
  839.     else
  840.     {
  841.       // We have found a match.  First update the hash table and
  842.       // copy the data in the LZ window.
  843.       unsigned int source = (PngWindowSize + lz_position - offset)
  844.                           & PngWindowMask ;
  845.       for (unsigned int ii = 0 ; ii < length ; ++ ii, ++ source)
  846.       {
  847.         unsigned int hashvalue = HashValue (lookahead_position) ;
  848.         MoveHashEntry (lz_position, hashvalue) ;
  849.  
  850.         lz_window [lz_position]
  851.             = lz_window [source & PngWindowMask] ;
  852.         lz_position
  853.             = (lz_position + 1) & PngWindowMask ;
  854.         lookahead_position
  855.             = (lookahead_position + 1) & LookaheadMask ;
  856.       }
  857.  
  858.        block_buffer [block_buffer_count] = 256 + length ;
  859.        ++ block_buffer_count ;
  860.        block_buffer [block_buffer_count] = offset ;
  861.  
  862.       // Gather Huffman Statistics
  863.       unsigned int code ;
  864.       unsigned int extra ;
  865.       unsigned int value ;
  866.       LengthToCode (length, code, extra, value) ;
  867.        length_table->IncrementFrequency (code) ;
  868.       DistanceToCode (offset, code, extra, value) ;
  869.        distance_table->IncrementFrequency (code) ;
  870.       FillBuffer (length) ;
  871.     }
  872.   }
  873.   length_table->IncrementFrequency (PngEndCode) ;
  874.   if (lookahead_buffer [lookahead_position] == ENDIMAGE)
  875.     return true ;
  876.   else
  877.     return false ;
  878. }
  879.  
  880. //
  881. //  Description:
  882. //
  883. //    This function outputs a single data byte.
  884. //
  885. //  Parameters:
  886. //    value: The value to output
  887. //
  888. void PngEncoder::OutputByte (UBYTE1 value)
  889. {
  890.   output_buffer [byte_position] = value ;
  891.   ++ byte_position ;
  892.   return ;
  893. }
  894.  
  895. //
  896. //  Description:
  897. //
  898. //    This function calls the progress function if it has been
  899. //    defined.
  900. //
  901. //  Parameters:
  902. //    percent:  The completion percentage (0..100)
  903. //
  904. void PngEncoder::CallProgressFunction (unsigned int percent)
  905. {
  906.   if (progress_function == NULL)
  907.     return ;
  908.  
  909.   if (percent > 100)
  910.     percent = 100 ;
  911.  
  912.   bool cancel = false ;
  913.   progress_function (*this, progress_data, 1, 1,
  914.                      percent, cancel) ;
  915.   return ;
  916. }
  917.  
  918. //
  919. //  Description:
  920. // 
  921. //    This function creates a tEXt chunk.
  922. //
  923. //  Parameters:
  924. //    keyword:  The chunk keyword
  925. //    value:  The keyword value
  926. //
  927. void PngEncoder::WriteText (const std::string &keyword,
  928.                             const std::string &value)
  929. {
  930.   if (keyword.length () > 79)
  931.     throw EPngError ("tEXt Keyword Too Long") ;
  932.   if (value.length () + keyword.length () + 1 > OutputBufferSize)
  933.     throw EPngError ("tEXt Value Too Long") ;
  934.  
  935.   StartChunk ("tEXt") ;
  936.   OutputBlock (keyword.c_str (), keyword.length ()) ;
  937.   OutputByte (0) ;
  938.   OutputBlock (value.c_str (), value.length ()) ;
  939.   WriteCurrentChunk () ;
  940.   return ;
  941. }
  942.  
  943. //
  944. //  Description:
  945. //
  946. //    This function outputs tEXt blocks for any keywords
  947. //    that have values assigned to them.
  948. //
  949. void PngEncoder::WriteTextBlocks ()
  950. {
  951.   if (title_string != "")
  952.     WriteText ("Title", title_string) ;
  953.   if (author_string != "")
  954.     WriteText ("Author", author_string) ;
  955.   if (description_string != "")
  956.     WriteText ("Description", description_string) ;
  957.   if (copyright_string != "")
  958.     WriteText ("Copyright", copyright_string) ;
  959.   if (software_string != "")
  960.     WriteText ("Software", software_string) ;
  961.   if (disclaimer_string != "")
  962.     WriteText ("Disclaimer", disclaimer_string) ;
  963.   if (warning_string != "")
  964.     WriteText ("Warning", warning_string) ;
  965.   if (source_string != "")
  966.     WriteText ("Source", source_string) ;
  967.   if (comment_string != "")
  968.     WriteText ("Comment", comment_string) ;
  969.   return ;
  970. }
  971.  
  972. //
  973. //  Description:
  974. //
  975. //    This function sets the compression level used.  The compression level
  976. //    determines the depth to which hash chains are searched.
  977. //
  978. //  Parameters:
  979. //    value:  The new compression level
  980. //
  981. void PngEncoder::SetCompressionLevel (PngEncoder::CompressionLevel value)
  982. {
  983.   if (value < 0 || value > 3)
  984.     throw EPngError ("Invalid Compression Level") ;
  985.  
  986.   compression_level = value ;
  987.   return ;
  988. }
  989.  
  990. //
  991. //  Description:
  992. //
  993. //    The function returns the current compression level.
  994. //
  995. //  Return Value:
  996. //    The compresion level.
  997. //
  998. PngEncoder::CompressionLevel PngEncoder::GetCompressionLevel () const
  999. {
  1000.   return compression_level ;
  1001. }
  1002.  
  1003. //
  1004. //  Description:
  1005. //
  1006. //    This function performs the actual output of the image.
  1007. //
  1008. void PngEncoder::DoWrite ()
  1009. {
  1010.   // Needed because MSVC++ does not follow standard scoping rules
  1011.   // in for statements.
  1012.   unsigned int ii ;
  1013.  
  1014.   if (current_image->BitCount () == 24)
  1015.   {
  1016.     row_width = 3 * current_image->Width () ;
  1017.     filter_width = 3 ;
  1018.   }
  1019.   else
  1020.   {
  1021.     row_width = (current_image->BitCount () * current_image->Width ()
  1022.                  + CHAR_BIT - 1) / CHAR_BIT ;
  1023.     filter_width = 1 ;
  1024.   }
  1025.  
  1026.   lz_window = new UBYTE1 [PngWindowSize] ;
  1027.   lookahead_buffer = new UBYTE2 [LookaheadSize] ;
  1028.   hash_values = new HashEntry [PngWindowSize] ;
  1029.   hash_table = new HashEntry [HashTableSize] ;
  1030.   output_buffer = new UBYTE1 [OutputBufferSize] ;
  1031.  
  1032.   for (ii = 0 ; ii < FilterBufferCount ; ++ ii)
  1033.   {
  1034.     if (((1 << ii) & filter_mask) != 0)
  1035.       filter_buffers [ii] = new UBYTE1 [row_width] ;
  1036.   }
  1037.  
  1038.   // Convert the compression level to the maximum depth hash
  1039.   // chains are searched.
  1040.   switch (compression_level)
  1041.   {
  1042.   case FastestCompression:
  1043.     search_limit = 1 ;
  1044.     break;
  1045.   case FastCompression:
  1046.     search_limit = 64 ;
  1047.     break ;
  1048.   case DefaultCompression:
  1049.     search_limit = 128 ;
  1050.     break ;
  1051.   case MaximumCompression:
  1052.     search_limit = UINT_MAX ;
  1053.     break ;
  1054.   default:
  1055.     throw EPngError ("Invalid Compression Level") ;
  1056.   }
  1057.  
  1058.   // Fill in the image header.
  1059.   PngImageHeader header ;
  1060.   header.width = SystemToBigEndian ((UBYTE4) current_image->Width ()) ;
  1061.   header.height = SystemToBigEndian ((UBYTE4) current_image->Height ()) ;
  1062.   header.bitdepth = current_image->BitCount () ;
  1063.   if (current_image->BitCount () != 24)
  1064.   {
  1065.     // Determine if the image is grayscale.
  1066.     bool isgrayscale = true ;
  1067.     for (unsigned int ii = 0 ; ii < current_image->ColorCount () ; ++ ii)
  1068.     {
  1069.       if (current_image->ColorMap (ii).red != current_image->ColorMap (ii).green
  1070.           ||
  1071.           current_image->ColorMap (ii).red != current_image->ColorMap (ii).blue)
  1072.       {
  1073.         isgrayscale = false ;
  1074.         break ;
  1075.       }
  1076.     }
  1077.  
  1078.     if (isgrayscale)
  1079.       header.colortype = Grayscale ;
  1080.     else
  1081.       header.colortype = Palette ;
  1082.   }
  1083.   else
  1084.   {
  1085.     header.bitdepth = 8 ;
  1086.     header.colortype = RGB ;
  1087.   }
  1088.   header.compressionmethod = 0 ;
  1089.   header.filtermethod = 0 ;
  1090.   header.interlacemethod = 0 ;
  1091.  
  1092.   // Output the PNG Signature and header.
  1093.   output_stream->write ((char *) PngSignature, PngSignatureSize) ;
  1094.   StartChunk ("IHDR") ;
  1095.   OutputBlock (&header, sizeof (header)) ;
  1096.   WriteCurrentChunk () ;
  1097.  
  1098.   // Output any text blocks with keywords defined.
  1099.   WriteTextBlocks () ;
  1100.  
  1101.   // Output the palette if it is required.
  1102.   if (header.colortype == Palette)
  1103.   {
  1104.     StartChunk ("PLTE") ;
  1105.     for (unsigned int ii = 0 ; ii < current_image->ColorCount () ; ++ ii)
  1106.     {
  1107.       OutputByte (current_image->ColorMap (ii).red) ;
  1108.       OutputByte (current_image->ColorMap (ii).green) ;
  1109.       OutputByte (current_image->ColorMap (ii).blue) ;
  1110.     }
  1111.     WriteCurrentChunk () ;
  1112.   }
  1113.  
  1114.   WriteImageData () ;
  1115.  
  1116.   // Write the IEND marker.
  1117.   StartChunk ("IEND") ;
  1118.   WriteCurrentChunk () ;
  1119.  
  1120.   return ;
  1121. }
  1122.  
  1123. //
  1124. //  Description:
  1125. //
  1126. //    This function filters an image row.
  1127. //
  1128. //  Parameters:
  1129. //    row: The row to filter (1..imageheight - 1)
  1130. //
  1131. void PngEncoder::FilterRow (unsigned int row)
  1132. {
  1133.   // We need this because MSVC++ does not follow standard
  1134.   // scoping rules in for statements.
  1135.   unsigned int ii ;
  1136.   if (filter_mask == 0)
  1137.     throw EPngError ("INTERNAL ERROR - No Filters Selected") ;
  1138.  
  1139.   unsigned int mask = (1 << FilterNone) ;
  1140.  
  1141.   // Filter None
  1142.   for (ii = 0 ; ii < row_width ; ++ ii)
  1143.   {
  1144.     filter_buffers [FilterNone][ii] = (*current_image) [row][ii] ;
  1145.   }
  1146.  
  1147.   // Filter for each type in the filter_mask.
  1148.   if ((filter_mask & (1 << FilterSub)) != 0)
  1149.   {
  1150.     mask |= (1 << FilterSub) ;
  1151.  
  1152.     UBYTE1 last ;
  1153.     for (unsigned int ii = 0 ; ii < row_width ; ++ ii)
  1154.     {
  1155.       if (ii >= filter_width)
  1156.         last = (*current_image)[row][ii-filter_width] ;
  1157.       else
  1158.         last = 0 ;
  1159.  
  1160.       filter_buffers [FilterSub][ii] = (*current_image) [row][ii] - last ;
  1161.     }
  1162.   }
  1163.  
  1164.   if ((filter_mask & (1 << FilterUp)) != 0 && row > 0)
  1165.   {
  1166.     mask |= (1 << FilterUp) ;
  1167.  
  1168.     for (unsigned int ii = 0 ; ii < row_width ; ++ ii)
  1169.     {
  1170.       UBYTE1 above ;
  1171.       if (row == 0)
  1172.         above = 0 ;
  1173.       else
  1174.         above = (*current_image)[row-1][ii] ;
  1175.       filter_buffers [FilterUp][ii] = (*current_image) [row][ii] - above ;
  1176.     }
  1177.   }
  1178.  
  1179.   if ((filter_mask & (1 << FilterAverage)) != 0 && row > 0)
  1180.   {
  1181.     mask |= (1 << FilterAverage) ;
  1182.  
  1183.     UBYTE1 last ;
  1184.     UBYTE1 above ;
  1185.     for (unsigned int ii = 0 ; ii < row_width ; ++ ii)
  1186.     {
  1187.       if (ii >= filter_width)
  1188.         last = (*current_image)[row][ii - filter_width] ;
  1189.       else
  1190.         last = 0 ;
  1191.       if (row == 0)
  1192.         above = 0 ;
  1193.       else
  1194.         above = (*current_image) [row-1][ii] ;
  1195.  
  1196.       filter_buffers [FilterAverage][ii] =
  1197.         (*current_image) [row][ii] - (above + last) / 2 ;
  1198.     }
  1199.   }
  1200.  
  1201.   if ((filter_mask & (1 << FilterPaeth)) != 0 && row > 0)
  1202.   {
  1203.     mask |= (1 << FilterPaeth) ;
  1204.  
  1205.     UBYTE1 last ;
  1206.     UBYTE1 lastabove ;
  1207.     UBYTE1 above ;
  1208.     for (unsigned int ii = 0 ; ii < row_width ; ++ ii)
  1209.     {
  1210.       if (ii >= filter_width)
  1211.       {
  1212.         last = (*current_image)[row][ii-filter_width] ;
  1213.         if (row != 0)
  1214.           lastabove = (*current_image)[row-1][ii - filter_width] ;
  1215.         else
  1216.           lastabove = 0 ;
  1217.       }
  1218.       else
  1219.       {
  1220.         last = 0 ;
  1221.         lastabove = 0 ;
  1222.       }
  1223.       if (row == 0)
  1224.         above = 0 ;
  1225.       else
  1226.         above = (*current_image)[row-1][ii] ;
  1227.       filter_buffers [FilterPaeth][ii] = (*current_image) [row][ii]
  1228.                    - PaethPredictor (last, above, lastabove) ;
  1229.     }
  1230.   }
  1231.  
  1232.   // If we only performed FilterNone then we do not need to proceed
  1233.   // any further.  
  1234.   current_filter = FilterNone ;
  1235.   if (mask == (1 << FilterNone))
  1236.     return ;
  1237.  
  1238.   // Find the best filter. We do a simple test for the
  1239.   // longest runs of the same value.
  1240.  
  1241.   unsigned int longestrun = 0 ;
  1242.   for (ii = 0 ; ii < FilterBufferCount ; ++ ii)
  1243.   {
  1244.     if ((mask & (1<<ii)) != 0)
  1245.     {
  1246.       unsigned int run = 0 ;
  1247.       for (unsigned int jj = 4 ; jj < row_width ; ++ jj)
  1248.       {
  1249.         if (filter_buffers [ii][jj] == filter_buffers [ii][jj-1]
  1250.             && filter_buffers [ii][jj] == filter_buffers [ii][jj-2]
  1251.             && filter_buffers [ii][jj] == filter_buffers [ii][jj-3]
  1252.             && filter_buffers [ii][jj] == filter_buffers [ii][jj-4])
  1253.         {
  1254.           ++ run ;
  1255.         }
  1256.       }
  1257.  
  1258.       if (run > longestrun)
  1259.       {
  1260.         current_filter = ii ;
  1261.         longestrun = run ;
  1262.       }
  1263.     }
  1264.   }
  1265.   return ;
  1266. }
  1267.  
  1268. //
  1269. //  Description:
  1270. //
  1271. //    This function specifies whether or not filters are used.
  1272. //
  1273. //  Parameters:
  1274. //    value: true=>Use Filters, false=>Don't use filters
  1275. //
  1276. void PngEncoder::SetUseFilters (bool value)
  1277. {
  1278.   if (value)
  1279.     filter_mask = 0xFFFFFFFF ;
  1280.   else
  1281.     filter_mask = 0x1 ;
  1282. }
  1283.  
  1284. //
  1285. //  Description:
  1286. //
  1287. //   This function tells if filters are being used.
  1288. //
  1289. //  Return Value:
  1290. //    true=>Filters are being used
  1291. //    false=>Filters are not being used
  1292. //
  1293. bool PngEncoder::GetUseFilters () const
  1294. {
  1295.   if (filter_mask == 0x1)
  1296.     return false ;
  1297.   else
  1298.     return true ;
  1299. }
  1300.  
  1301. //
  1302. //  Description:
  1303. //
  1304. //    This function initializes the Hash Table.
  1305. //
  1306. //
  1307. void PngEncoder::InitializeHashTable ()
  1308. {
  1309.   int ii ;
  1310.   memset (hash_values, 0, sizeof (HashEntry) * PngWindowSize) ;
  1311.   memset (hash_table, 0, sizeof (HashEntry) * (1 << (3 * HashBits))) ;
  1312.  
  1313.   for (ii = 0 ; ii < PngWindowSize ; ++ ii)
  1314.     hash_values [ii].index = ii ;
  1315.  
  1316.   // Initialize the hash table to allow initial zero runs. Here we are
  1317.   // setting up the hash table so that it appears that we have read
  1318.   // 258 zero values before the actual compression begins. This way
  1319.   // if the first 258 data bytes contains a run of zeros then we already
  1320.   // have a code to compress them with.
  1321.   hash_table [Hash (0, 0, 0)].next = &hash_values [PngWindowSize - 1] ;
  1322.   hash_values [PngWindowSize - 1].next = &hash_table [0] ;
  1323.  
  1324.   for (ii = PngWindowSize - 2 ;
  1325.        ii > PngWindowSize - PngLongestLength - 1 ;
  1326.        -- ii)
  1327.   {
  1328.     hash_values [ii + 1].next = &hash_values [ii]  ;
  1329.     hash_values [ii].previous = &hash_values [ii + 1] ;
  1330.   }
  1331.   return ;
  1332. }
  1333.  
  1334. //
  1335. //  Description:
  1336. //
  1337. //    This function initializes the LZ77 Windows
  1338. //
  1339. void PngEncoder::InitializeLZWindow ()
  1340. {
  1341.   image_row = -1 ;
  1342.   image_col = 0xFFFFFFFFL ;
  1343.   image_end = false ;
  1344.  
  1345.   memset (lz_window, 0, PngWindowSize) ;
  1346.  
  1347.   lookahead_position = 0 ;
  1348.   lz_position = 0 ;
  1349.   // Final step: Fill the lookahead buffer.
  1350.   FillBuffer (LookaheadSize) ;
  1351.   FilterRow (0) ;
  1352.   return ;
  1353. }
  1354.  
  1355. //
  1356. //  Description:
  1357. //
  1358. //    This function writes a Deflate block header and Huffman table
  1359. //    descriptions to the output stream.
  1360. //
  1361. //  Parameters:
  1362. //    lastblock: true => This is the last block in the image
  1363. //               false => There are more blocks to come
  1364. //
  1365. void PngEncoder::OutputDeflateHeader (bool lastblock)
  1366. {
  1367.   // Determine the count of length/literal and distances that
  1368.   // are used.
  1369.   unsigned int lengthcount ;
  1370.   for (lengthcount = PngMaxLengthCodes ;
  1371.        lengthcount > 0 ;
  1372.        -- lengthcount)
  1373.   {
  1374.     if (length_table->ehufsi [lengthcount - 1] != 0)
  1375.       break ;
  1376.   }
  1377.  
  1378.   unsigned int distancecount ;
  1379.   for (distancecount = PngMaxLengthCodes ;
  1380.        distancecount > 0 ;
  1381.        -- distancecount)
  1382.   {
  1383.     if (distance_table->ehufsi [distancecount - 1] != 0)
  1384.       break ;
  1385.   }
  1386.  
  1387.   // Gather the Huffman statistics for encoding the
  1388.   // lengths then create the Huffman table for doing so.
  1389.   length_length_table->Reset () ;
  1390.   FindLengthCodes (&PngEncoder::GatherLengthCounts,
  1391.                    length_table->ehufsi,
  1392.                    lengthcount) ;
  1393.   FindLengthCodes (&PngEncoder::GatherLengthCounts,
  1394.                    distance_table->ehufsi,
  1395.                    distancecount) ;
  1396.   length_length_table->BuildTable (PngMaxLengthLengthCodeSize) ;
  1397.  
  1398.   // Count the number of lengths we have to output.
  1399.   unsigned int hclen ;
  1400.   for (hclen = 19 ; hclen > 0 ; -- hclen)
  1401.   {
  1402.     if (length_length_table->ehufsi [PngLengthOrder [hclen-1]] != 0)
  1403.       break ;
  1404.   }
  1405.  
  1406.   // Write the Deflate header to the IDAT bock.
  1407.   if (lastblock)
  1408.     OutputDataBits (1, 1) ;
  1409.   else
  1410.     OutputDataBits (0, 1) ;
  1411.  
  1412.   OutputDataBits (2, 2) ; // Dynamic Huffman Codes
  1413.   OutputDataBits (lengthcount - 257, 5) ;
  1414.   OutputDataBits (distancecount - 1, 5) ;
  1415.   OutputDataBits (hclen - 4, 4) ;
  1416.   // Output the data for the Huffman table that encodes the Huffman tables
  1417.   for (unsigned int ii = 0 ; ii < hclen ; ++ ii)
  1418.     OutputDataBits (length_length_table->ehufsi [PngLengthOrder [ii]], 3) ;
  1419.  
  1420.    // Huffman encode the lengths for the Length/Literal and Distance
  1421.   // Huffman tables.
  1422.   FindLengthCodes (&PngEncoder::OutputLengthCounts,
  1423.                    length_table->ehufsi,
  1424.                    lengthcount) ;
  1425.   FindLengthCodes (&PngEncoder::OutputLengthCounts,
  1426.                    distance_table->ehufsi,
  1427.                    distancecount) ;
  1428.   return ;
  1429. }
  1430.  
  1431. //
  1432. //  Description:
  1433. //
  1434. //    This function writes a ZLIB header to the output stream.
  1435. //
  1436. void PngEncoder::OutputZLibHeader ()
  1437. {
  1438.   UBYTE1 cmf = 0x78 ;  // 7=>32K Sliding Window, 8=> Deflate Compression
  1439.   UBYTE1 flg = compression_level << 6 ;
  1440.   UBYTE2 check = (cmf << 8) | flg ;
  1441.   flg |= 31 - (check % 31) ;
  1442.   OutputDataBits (cmf, 8) ;
  1443.   OutputDataBits (flg, 8) ;
  1444.   return ;
  1445. }
  1446.  
  1447. //
  1448. //  Description:
  1449. //
  1450. //    This function writes the image data to a series of IDAT blocks.
  1451. //
  1452. void PngEncoder::WriteImageData ()
  1453. {
  1454.   // Write the IDAT blocks.
  1455.   StartChunk ("IDAT") ;
  1456.  
  1457.   adler_value = 1 ;
  1458.  
  1459.   block_buffer = new UBYTE2 [block_buffer_size] ;
  1460.  
  1461.   InitializeLZWindow () ;
  1462.   OutputZLibHeader () ;
  1463.  
  1464.   CallProgressFunction (0) ;
  1465.  
  1466.   // What we are doing here is outputing the image into a series of
  1467.   // Deflate compressed blocks.
  1468.   for (bool nomoredata = false ; ! nomoredata ;)
  1469.   {
  1470.     // Save the input state
  1471.     length_table->Reset () ;
  1472.     distance_table->Reset () ;
  1473.     nomoredata = ProcessImageData () ;
  1474.     // Create the Huffman tables for length/literals and
  1475.     // distances.
  1476.     length_table->BuildTable (PngMaxLengthCodeSize) ;
  1477.     distance_table->BuildTable (PngMaxDistanceCodeSize) ;
  1478.  
  1479.     OutputDeflateHeader (nomoredata) ;
  1480.     OutputBlockData () ;
  1481.   }
  1482.  
  1483.   CallProgressFunction (100) ;
  1484.   OutputAdler () ;
  1485.   WriteCurrentChunk () ;
  1486.  
  1487.   delete [] block_buffer ; block_buffer = NULL ;
  1488.  
  1489.   return ;
  1490. }
  1491.  
  1492. //
  1493. //  Description:
  1494. //
  1495. //    This function Huffman encodes and outputs the buffered data.
  1496. //
  1497. //    The buffer is encoded so that
  1498. //
  1499. //      0..255  is a literal byte
  1500. //      256-514 is a length code of N-256
  1501. //
  1502. //    Each length code is followed by a distance code.
  1503. //
  1504. void PngEncoder::OutputBlockData ()
  1505. {
  1506.   UBYTE2 huffmancode ;
  1507.   UBYTE1 huffmansize ;
  1508.   unsigned int code ;
  1509.   unsigned int extra ;
  1510.   unsigned int value ;
  1511.   unsigned int limit = block_buffer_count ;
  1512.   for (unsigned int ii = 0 ; ii < limit ; ++ ii)
  1513.   {
  1514.     if (block_buffer [ii] < 256)
  1515.     {
  1516.       length_table->Encode (block_buffer [ii], huffmancode, huffmansize) ;
  1517.       OutputDataBits (huffmancode, huffmansize) ;
  1518.     }
  1519.     else
  1520.     {
  1521.       unsigned int length = block_buffer [ii] - 256 ;
  1522.       ++ ii ;
  1523.       unsigned int distance = block_buffer [ii] ;
  1524.       LengthToCode (length, code, extra, value) ;
  1525.       length_table->Encode (code, huffmancode, huffmansize) ;
  1526.  
  1527.       OutputDataBits (huffmancode, huffmansize) ;
  1528.       if (extra != 0)
  1529.         OutputDataBits (value, extra) ;
  1530.  
  1531.       DistanceToCode (distance, code, extra, value) ;
  1532.       distance_table->Encode (code, huffmancode, huffmansize) ;
  1533.  
  1534.       OutputDataBits (huffmancode, huffmansize) ;
  1535.       if (extra != 0)
  1536.         OutputDataBits (value, extra) ;
  1537.     }
  1538.   }
  1539.   length_table->Encode (PngEndCode, huffmancode, huffmansize) ;
  1540.   OutputDataBits (huffmancode, huffmansize) ;
  1541.   return ;
  1542. }
  1543.