trees.c
上传用户:maxiaolivb
上传日期:2022-06-07
资源大小:915k
文件大小:32k
源码类别:

游戏引擎

开发平台:

Visual C++

  1. /* trees.c -- output deflated data using Huffman coding
  2.  * Copyright (C) 1995-2003 Jean-loup Gailly
  3.  * For conditions of distribution and use, see copyright notice in zlib.h
  4.  */
  5. /*
  6.  *  ALGORITHM
  7.  *
  8.  *      The "deflation" process uses several Huffman trees. The more
  9.  *      common source values are represented by shorter bit sequences.
  10.  *
  11.  *      Each code tree is stored in a compressed form which is itself
  12.  * a Huffman encoding of the lengths of all the code strings (in
  13.  * ascending order by source values).  The actual code strings are
  14.  * reconstructed from the lengths in the inflate process, as described
  15.  * in the deflate specification.
  16.  *
  17.  *  REFERENCES
  18.  *
  19.  *      Deutsch, L.P.,"'Deflate' Compressed Data Format Specification".
  20.  *      Available in ftp.uu.net:/pub/archiving/zip/doc/deflate-1.1.doc
  21.  *
  22.  *      Storer, James A.
  23.  *          Data Compression:  Methods and Theory, pp. 49-50.
  24.  *          Computer Science Press, 1988.  ISBN 0-7167-8156-5.
  25.  *
  26.  *      Sedgewick, R.
  27.  *          Algorithms, p290.
  28.  *          Addison-Wesley, 1983. ISBN 0-201-06672-6.
  29.  */
  30. /* @(#) $Id: trees.c,v 1.1 2005/11/23 14:29:59 stingerx Exp $ */
  31. #include "deflate.h"
  32. /* ===========================================================================
  33.  * Constants
  34.  */
  35. #define MAX_BL_BITS 7
  36. #define END_BLOCK 256
  37. #define REP_3_6      16
  38. #define REPZ_3_10    17
  39. #define REPZ_11_138  18
  40. static const int extra_lbits[LENGTH_CODES] =
  41. {
  42.   0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0
  43. };
  44. static const int extra_dbits[D_CODES] =
  45. {
  46.   0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13
  47. };
  48. static const int extra_blbits[BL_CODES] =
  49. {
  50.   0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 3, 7
  51. };
  52. static const BYTE bl_order[BL_CODES] =
  53. {
  54.   16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15
  55. };
  56. /* The lengths of the bit length codes are sent in order of decreasing
  57.  * probability, to avoid transmitting the lengths for unused bit length codes.
  58.  */
  59. #define Buf_size (8 * 2*sizeof(char))
  60. /* Number of bits used within bi_buf. (bi_buf might be implemented on
  61.  * more than 16 bits on some systems.)
  62.  */
  63. /* ===========================================================================
  64.  * static data. These are initialized only once.
  65.  */
  66. #define DIST_CODE_LEN  512 /* see definition of array dist_code below */
  67. #include "trees.h"
  68. struct static_tree_desc_s
  69. {
  70.   const ct_data *static_tree; /* static tree or NULL */
  71.   const intf *extra_bits; /* extra bits for each code or NULL */
  72.   int extra_base; /* base index for extra_bits */
  73.   int elems; /* max number of elements in the tree */
  74.   int max_length; /* max bit length for the codes */
  75. };
  76. static static_tree_desc static_l_desc =
  77. {
  78.   static_ltree, extra_lbits, LITERALS + 1, L_CODES, MAX_BITS
  79. };
  80. static static_tree_desc static_d_desc =
  81. {
  82.   static_dtree, extra_dbits, 0, D_CODES, MAX_BITS
  83. };
  84. static static_tree_desc static_bl_desc =
  85. {
  86.   (const ct_data*)0, extra_blbits, 0, BL_CODES, MAX_BL_BITS
  87. };
  88. /* ===========================================================================
  89.  * Local (static) routines in this file.
  90.  */
  91. static void tr_static_init(void);
  92. static void init_block(deflate_state *s);
  93. static void pqdownheap OF((deflate_state *s, ct_data *tree, int k));
  94. static void gen_bitlen OF((deflate_state *s, tree_desc *desc));
  95. static void gen_codes OF((ct_data *tree, int max_code, WORD *bl_count));
  96. static void build_tree OF((deflate_state *s, tree_desc *desc));
  97. static void scan_tree OF((deflate_state *s, ct_data *tree, int max_code));
  98. static void send_tree OF((deflate_state *s, ct_data *tree, int max_code));
  99. static int build_bl_tree OF((deflate_state *s));
  100. static void send_all_trees OF((deflate_state *s, int lcodes, int dcodes, int blcodes));
  101. static void compress_block OF((deflate_state *s, ct_data *ltree, ct_data *dtree));
  102. static void set_data_type OF((deflate_state *s));
  103. static DWORD bi_reverse OF((DWORD value, int length));
  104. static void bi_windup OF((deflate_state *s));
  105. static void bi_flush OF((deflate_state *s));
  106. static void copy_block OF((deflate_state *s, BYTE *buf, DWORD len, int header));
  107. #define send_code(s, c, tree) send_bits(s, tree[c].Code, tree[c].Len)
  108. /* Send a code of the given tree. c and tree must not have side effects */
  109. /* ===========================================================================
  110.  * Output a short LSB first on the stream.
  111.  * IN assertion: there is enough room in pendingBuf.
  112.  */
  113. #define put_short(s, w) { put_byte(s, (BYTE)((w) & 0xff)); put_byte(s, (BYTE)((WORD)(w) >> 8)); }
  114. /* ===========================================================================
  115.  * Send a value on a given number of bits.
  116.  * IN assertion: length <= 16 and value fits in length bits.
  117.  */
  118. #define send_bits(s, value, length) 
  119. { int len = length;
  120. if (s->bi_valid > (int)Buf_size - len) {
  121. int val = value;
  122. s->bi_buf |= (val << s->bi_valid);
  123. put_short(s, s->bi_buf);
  124. s->bi_buf = (WORD)val >> (Buf_size - s->bi_valid);
  125. s->bi_valid += len - Buf_size;
  126. } else {
  127. s->bi_buf |= (value) << s->bi_valid;
  128. s->bi_valid += len;
  129. }
  130. }
  131. /* the arguments must not have side effects */
  132. /* ===========================================================================
  133.  * Initialize the tree data structures for a new zlib stream.
  134.  */
  135. void _tr_init(deflate_state *s)
  136. {
  137.   s->l_desc.dyn_tree = s->dyn_ltree;
  138.   s->l_desc.stat_desc = &static_l_desc;
  139.   s->d_desc.dyn_tree = s->dyn_dtree;
  140.   s->d_desc.stat_desc = &static_d_desc;
  141.   s->bl_desc.dyn_tree = s->bl_tree;
  142.   s->bl_desc.stat_desc = &static_bl_desc;
  143.   s->bi_buf = 0;
  144.   s->bi_valid = 0;
  145.   s->last_eob_len = 8; /* enough lookahead for inflate */
  146.   /* Initialize the first block of the first file: */
  147.   init_block(s);
  148. }
  149. /* ===========================================================================
  150.  * Initialize a new block.
  151.  */
  152. static void init_block(deflate_state *s)
  153. {
  154.   int n;
  155.   for (n = 0; n < L_CODES; n++)
  156.   {
  157.     s->dyn_ltree[n].Freq = 0;
  158.   }
  159.   for (n = 0; n < D_CODES; n++)
  160.   {
  161.     s->dyn_dtree[n].Freq = 0;
  162.   }
  163.   for (n = 0; n < BL_CODES; n++)
  164.   {
  165.     s->bl_tree[n].Freq = 0;
  166.   }
  167.   s->dyn_ltree[END_BLOCK].Freq = 1;
  168.   s->opt_len = s->static_len = 0L;
  169.   s->last_lit = s->matches = 0;
  170. }
  171. //-------------------------------------------------------------------------
  172. #define SMALLEST 1
  173. /* ===========================================================================
  174.  * Remove the smallest element from the heap and recreate the heap with
  175.  * one less element. Updates heap and heap_len.
  176.  */
  177. #define pqremove(s, tree, top) 
  178. {
  179. top = s->heap[SMALLEST]; 
  180. s->heap[SMALLEST] = s->heap[s->heap_len--]; 
  181. pqdownheap(s, tree, SMALLEST); 
  182. }
  183. /* ===========================================================================
  184.  * Compares to subtrees, using the tree depth as tie breaker when
  185.  * the subtrees have equal frequency. This minimizes the worst case length.
  186.  */
  187. #define smaller(tree, n, m, depth) 
  188. (tree[n].Freq < tree[m].Freq || 
  189. (tree[n].Freq == tree[m].Freq && depth[n] <= depth[m]))
  190. /* ===========================================================================
  191.  * Restore the heap property by moving down the tree starting at node k,
  192.  * exchanging a node with the smallest of its two sons if necessary, stopping
  193.  * when the heap property is re-established (each father smaller than its
  194.  * two sons).
  195.  */
  196. static void pqdownheap(deflate_state *s, ct_data *tree, int k)
  197. {
  198.   int v = s->heap[k];
  199.   int j = k << 1; /* left son of k */
  200.   while (j <= s->heap_len)
  201.   {
  202.     /* Set j to the smallest of the two sons: */
  203.     if (j < s->heap_len && smaller(tree, s->heap[j + 1], s->heap[j], s->depth))
  204.     {
  205.       j++;
  206.     }
  207.     /* Exit if v is smaller than both sons */
  208.     if (smaller(tree, v, s->heap[j], s->depth))
  209.     {
  210.       break;
  211.     }
  212.     /* Exchange v with the smallest son */
  213.     s->heap[k] = s->heap[j];
  214.     k = j;
  215.     /* And continue down the tree, setting j to the left son of k */
  216.     j <<= 1;
  217.   }
  218.   s->heap[k] = v;
  219. }
  220. /* ===========================================================================
  221.  * Compute the optimal bit lengths for a tree and update the total bit length
  222.  * for the current block.
  223.  * IN assertion: the fields freq and dad are set, heap[heap_max] and
  224.  *    above are the tree nodes sorted by increasing frequency.
  225.  * OUT assertions: the field len is set to the optimal bit length, the
  226.  *     array bl_count contains the frequencies for each bit length.
  227.  *     The length opt_len is updated; static_len is also updated if stree is
  228.  *     not null.
  229.  */
  230. static void gen_bitlen(deflate_state *s, tree_desc *desc)
  231. {
  232.   ct_data *tree = desc->dyn_tree;
  233.   int max_code = desc->max_code;
  234.   const ct_data *stree = desc->stat_desc->static_tree;
  235.   const intf *extra = desc->stat_desc->extra_bits;
  236.   int base = desc->stat_desc->extra_base;
  237.   int max_length = desc->stat_desc->max_length;
  238.   int h; /* heap index */
  239.   int n, m; /* iterate over the tree elements */
  240.   int bits; /* bit length */
  241.   int xbits; /* extra bits */
  242.   WORD f; /* frequency */
  243.   int overflow = 0; /* number of elements with bit length too large */
  244.   for (bits = 0; bits <= MAX_BITS; bits++)
  245.   {
  246.     s->bl_count[bits] = 0;
  247.   }
  248.   /* In a first pass, compute the optimal bit lengths (which may
  249.    * overflow in the case of the bit length tree).
  250.    */
  251.   tree[s->heap[s->heap_max]].Len = 0; /* root of the heap */
  252.   for (h = s->heap_max + 1; h < HEAP_SIZE; h++)
  253.   {
  254.     n = s->heap[h];
  255.     bits = tree[tree[n].Dad].Len + 1;
  256.     if (bits > max_length)
  257.     {
  258.       bits = max_length, overflow++;
  259.     }
  260.     tree[n].Len = (WORD)bits;
  261.     /* We overwrite tree[n].Dad which is no longer needed */
  262.     if (n > max_code)
  263.     {
  264.       continue;
  265.     }
  266.     /* not a leaf node */
  267.     s->bl_count[bits]++;
  268.     xbits = 0;
  269.     if (n >= base)
  270.     {
  271.       xbits = extra[n - base];
  272.     }
  273.     f = tree[n].Freq;
  274.     s->opt_len += (DWORD)f *(bits + xbits);
  275.     if (stree)
  276.     {
  277.       s->static_len += (DWORD)f *(stree[n].Len + xbits);
  278.     }
  279.   }
  280.   if (!overflow)
  281.   {
  282.     return ;
  283.   }
  284.   /* This happens for example on obj2 and pic of the Calgary corpus */
  285.   /* Find the first bit length which could increase: */
  286.   do
  287.   {
  288.     bits = max_length - 1;
  289.     while (s->bl_count[bits] == 0)bits--;
  290.     s->bl_count[bits]--; /* move one leaf down the tree */
  291.     s->bl_count[bits + 1] += 2; /* move one overflow item as its brother */
  292.     s->bl_count[max_length]--;
  293.     /* The brother of the overflow item also moves one step up,
  294.      * but this does not affect bl_count[max_length]
  295.      */
  296.     overflow -= 2;
  297.   }
  298.   while (overflow > 0)
  299.     ;
  300.   /* Now recompute all bit lengths, scanning in increasing frequency.
  301.    * h is still equal to HEAP_SIZE. (It is simpler to reconstruct all
  302.    * lengths instead of fixing only the wrong ones. This idea is taken
  303.    * from 'ar' written by Haruhiko Okumura.)
  304.    */
  305.   for (bits = max_length; bits != 0; bits--)
  306.   {
  307.     n = s->bl_count[bits];
  308.     while (n != 0)
  309.     {
  310.       m = s->heap[--h];
  311.       if (m > max_code)
  312.       {
  313.         continue;
  314.       }
  315.       if (tree[m].Len != (DWORD)bits)
  316.       {
  317.         s->opt_len += ((long)bits - (long)tree[m].Len)*(long)tree[m].Freq;
  318.         tree[m].Len = (WORD)bits;
  319.       }
  320.       n--;
  321.     }
  322.   }
  323. }
  324. /* ===========================================================================
  325.  * Generate the codes for a given tree and bit counts (which need not be
  326.  * optimal).
  327.  * IN assertion: the array bl_count contains the bit length statistics for
  328.  * the given tree and the field len is set for all tree elements.
  329.  * OUT assertion: the field code is set for all tree elements of non
  330.  *     zero code length.
  331.  */
  332. static void gen_codes(ct_data *tree, int max_code, WORD *bl_count)
  333. {
  334.   WORD next_code[MAX_BITS + 1]; /* next code value for each bit length */
  335.   WORD code = 0; /* running code value */
  336.   int bits; /* bit index */
  337.   int n; /* code index */
  338.   /* The distribution counts are first used to generate the code values
  339.    * without bit reversal.
  340.    */
  341.   for (bits = 1; bits <= MAX_BITS; bits++)
  342.   {
  343.     next_code[bits] = code = (code + bl_count[bits - 1]) << 1;
  344.   }
  345.   /* Check that the bit counts in bl_count are consistent. The last code
  346.    * must be all ones.
  347.    */
  348.   for (n = 0; n <= max_code; n++)
  349.   {
  350.     int len = tree[n].Len;
  351.     if (len == 0)
  352.     {
  353.       continue;
  354.     }
  355.     /* Now reverse the bits - DW */
  356.     tree[n].Code = (WORD)bi_reverse(next_code[len]++, len);
  357.   }
  358. }
  359. /* ===========================================================================
  360.  * Construct one Huffman tree and assigns the code bit strings and lengths.
  361.  * Update the total bit length for the current block.
  362.  * IN assertion: the field freq is set for all tree elements.
  363.  * OUT assertions: the fields len and code are set to the optimal bit length
  364.  *     and corresponding code. The length opt_len is updated; static_len is
  365.  *     also updated if stree is not null. The field max_code is set.
  366.  */
  367. static void build_tree(deflate_state *s, tree_desc *desc)
  368. {
  369.   ct_data *tree = desc->dyn_tree;
  370.   const ct_data *stree = desc->stat_desc->static_tree;
  371.   int elems = desc->stat_desc->elems;
  372.   int n, m; /* iterate over heap elements */
  373.   int max_code =  - 1; /* largest code with non zero frequency */
  374.   int node; /* new node being created */
  375.   /* Construct the initial heap, with least frequent element in
  376.    * heap[SMALLEST]. The sons of heap[n] are heap[2*n] and heap[2*n+1].
  377.    * heap[0] is not used.
  378.    */
  379.   s->heap_len = 0, s->heap_max = HEAP_SIZE;
  380.   for (n = 0; n < elems; n++)
  381.   {
  382.     if (tree[n].Freq != 0)
  383.     {
  384.       s->heap[++(s->heap_len)] = max_code = n;
  385.       s->depth[n] = 0;
  386.     }
  387.     else
  388.     {
  389.       tree[n].Len = 0;
  390.     }
  391.   }
  392.   /* The pkzip format requires that at least one distance code exists,
  393.    * and that at least one bit should be sent even if there is only one
  394.    * possible code. So to avoid special checks later on we force at least
  395.    * two codes of non zero frequency.
  396.    */
  397.   while (s->heap_len < 2)
  398.   {
  399.     node = s->heap[++(s->heap_len)] = (max_code < 2 ? ++max_code: 0);
  400.     tree[node].Freq = 1;
  401.     s->depth[node] = 0;
  402.     s->opt_len--;
  403.     if (stree)
  404.     {
  405.       s->static_len -= stree[node].Len;
  406.     }
  407.     /* node is 0 or 1 so it does not have extra bits */
  408.   }
  409.   desc->max_code = max_code;
  410.   /* The elements heap[heap_len/2+1 .. heap_len] are leaves of the tree,
  411.    * establish sub-heaps of increasing lengths:
  412.    */
  413.   for (n = s->heap_len / 2; n >= 1; n--)
  414.   {
  415.     pqdownheap(s, tree, n);
  416.   }
  417.   /* Construct the Huffman tree by repeatedly combining the least two
  418.    * frequent nodes.
  419.    */
  420.   node = elems; /* next internal node of the tree */
  421.   do
  422.   {
  423.     pqremove(s, tree, n); /* n = node of least frequency */
  424.     m = s->heap[SMALLEST]; /* m = node of next least frequency */
  425.     s->heap[--(s->heap_max)] = n; /* keep the nodes sorted by frequency */
  426.     s->heap[--(s->heap_max)] = m;
  427.     /* Create a new node father of n and m */
  428.     tree[node].Freq = tree[n].Freq + tree[m].Freq;
  429.     s->depth[node] = (BYTE)((s->depth[n] >= s->depth[m] ? s->depth[n]: s->depth[m]) + 1);
  430.     tree[n].Dad = tree[m].Dad = (WORD)node;
  431.     #ifdef DUMP_BL_TREE
  432.       if (tree == s->bl_tree)
  433.       {
  434.         fprintf(stderr, "nnode %d(%d), sons %d(%d) %d(%d)", node, tree[node].Freq, n, tree[n].Freq, m, tree[m].Freq);
  435.       }
  436.     #endif
  437.     /* and insert the new node in the heap */
  438.     s->heap[SMALLEST] = node++;
  439.     pqdownheap(s, tree, SMALLEST);
  440.   }
  441.   while (s->heap_len >= 2);
  442.   s->heap[--(s->heap_max)] = s->heap[SMALLEST];  
  443.   /* At this point, the fields freq and dad are set. We can now
  444.    * generate the bit lengths.
  445.    */
  446.   gen_bitlen(s, (tree_desc*)desc);
  447.   /* The field len is now set, we can generate the bit codes */
  448.   gen_codes((ct_data*)tree, max_code, s->bl_count);
  449. }
  450. /* ===========================================================================
  451.  * Scan a literal or distance tree to determine the frequencies of the codes
  452.  * in the bit length tree.
  453.  */
  454. static void scan_tree(deflate_state *s, ct_data *tree, int max_code)
  455. {
  456.   int n; /* iterates over all tree elements */
  457.   int prevlen =  - 1; /* last emitted length */
  458.   int curlen; /* length of current code */
  459.   int nextlen = tree[0].Len; /* length of next code */
  460.   int count = 0; /* repeat count of the current code */
  461.   int max_count = 7; /* max repeat count */
  462.   int min_count = 4; /* min repeat count */
  463.   if (nextlen == 0)
  464.   {
  465.     max_count = 138, min_count = 3;
  466.   }
  467.   tree[max_code + 1].Len = (WORD)0xffff; /* guard */
  468.   for (n = 0; n <= max_code; n++)
  469.   {
  470.     curlen = nextlen;
  471.     nextlen = tree[n + 1].Len;
  472.     if (++count < max_count && curlen == nextlen)
  473.     {
  474.       continue;
  475.     }
  476.     else if (count < min_count)
  477.     {
  478.       s->bl_tree[curlen].Freq += count;
  479.     }
  480.     else if (curlen != 0)
  481.     {
  482.       if (curlen != prevlen)
  483.       {
  484.         s->bl_tree[curlen].Freq++;
  485.       }
  486.       s->bl_tree[REP_3_6].Freq++;
  487.     }
  488.     else if (count <= 10)
  489.     {
  490.       s->bl_tree[REPZ_3_10].Freq++;
  491.     }
  492.     else
  493.     {
  494.       s->bl_tree[REPZ_11_138].Freq++;
  495.     }
  496.     count = 0;
  497.     prevlen = curlen;
  498.     if (nextlen == 0)
  499.     {
  500.       max_count = 138, min_count = 3;
  501.     }
  502.     else if (curlen == nextlen)
  503.     {
  504.       max_count = 6, min_count = 3;
  505.     }
  506.     else
  507.     {
  508.       max_count = 7, min_count = 4;
  509.     }
  510.   }
  511. }
  512. /* ===========================================================================
  513.  * Send a literal or distance tree in compressed form, using the codes in
  514.  * bl_tree.
  515.  */
  516. static void send_tree(deflate_state *s, ct_data *tree, int max_code)
  517. {
  518.   int n; /* iterates over all tree elements */
  519.   int prevlen =  - 1; /* last emitted length */
  520.   int curlen; /* length of current code */
  521.   int nextlen = tree[0].Len; /* length of next code */
  522.   int count = 0; /* repeat count of the current code */
  523.   int max_count = 7; /* max repeat count */
  524.   int min_count = 4; /* min repeat count */
  525.    /* tree[max_code+1].Len = -1; */ /* guard already set */
  526.   if (nextlen == 0)
  527.   {
  528.     max_count = 138, min_count = 3;
  529.   }
  530.   for (n = 0; n <= max_code; n++)
  531.   {
  532.     curlen = nextlen;
  533.     nextlen = tree[n + 1].Len;
  534.     if (++count < max_count && curlen == nextlen)
  535.     {
  536.       continue;
  537.     }
  538.     else if (count < min_count)
  539.     {
  540.       do
  541.       {
  542.         send_code(s, curlen, s->bl_tree);
  543.       }
  544.       while (--count != 0);
  545.     }
  546.     else if (curlen != 0)
  547.     {
  548.       if (curlen != prevlen)
  549.       {
  550.         send_code(s, curlen, s->bl_tree);
  551.         count--;
  552.       }
  553.       send_code(s, REP_3_6, s->bl_tree);
  554.       send_bits(s, count - 3, 2);
  555.     }
  556.     else if (count <= 10)
  557.     {
  558.       send_code(s, REPZ_3_10, s->bl_tree);
  559.       send_bits(s, count - 3, 3);
  560.     }
  561.     else
  562.     {
  563.       send_code(s, REPZ_11_138, s->bl_tree);
  564.       send_bits(s, count - 11, 7);
  565.     }
  566.     count = 0;
  567.     prevlen = curlen;
  568.     if (nextlen == 0)
  569.     {
  570.       max_count = 138, min_count = 3;
  571.     }
  572.     else if (curlen == nextlen)
  573.     {
  574.       max_count = 6, min_count = 3;
  575.     }
  576.     else
  577.     {
  578.       max_count = 7, min_count = 4;
  579.     }
  580.   }
  581. }
  582. /* ===========================================================================
  583.  * Construct the Huffman tree for the bit lengths and return the index in
  584.  * bl_order of the last bit length code to send.
  585.  */
  586. static int build_bl_tree(deflate_state *s)
  587. {
  588.   int max_blindex; /* index of last bit length code of non zero freq */
  589.   /* Determine the bit length frequencies for literal and distance trees */
  590.   scan_tree(s, (ct_data*)s->dyn_ltree, s->l_desc.max_code);
  591.   scan_tree(s, (ct_data*)s->dyn_dtree, s->d_desc.max_code);
  592.   /* Build the bit length tree: */
  593.   build_tree(s, (tree_desc*)(&(s->bl_desc)));
  594.   /* opt_len now includes the length of the tree representations, except
  595.    * the lengths of the bit lengths codes and the 5+5+4 bits for the counts.
  596.    */
  597.   /* Determine the number of bit length codes to send. The pkzip format
  598.    * requires that at least 4 bit length codes be sent. (appnote.txt says
  599.    * 3 but the actual value used is 4.)
  600.    */
  601.   for (max_blindex = BL_CODES - 1; max_blindex >= 3; max_blindex--)
  602.   {
  603.     if (s->bl_tree[bl_order[max_blindex]].Len != 0)
  604.     {
  605.       break;
  606.     }
  607.   }
  608.   /* Update opt_len to include the bit length tree and counts */
  609.   s->opt_len += 3 *(max_blindex + 1) + 5+5+4;
  610.   return max_blindex;
  611. }
  612. /* ===========================================================================
  613.  * Send the header for a block using dynamic Huffman trees: the counts, the
  614.  * lengths of the bit length codes, the literal tree and the distance tree.
  615.  * IN assertion: lcodes >= 257, dcodes >= 1, blcodes >= 4.
  616.  */
  617. static void send_all_trees(deflate_state *s, int lcodes, int dcodes, int blcodes)
  618. {
  619.   int rank; /* index in bl_order */
  620.   send_bits(s, lcodes - 257, 5); /* not +255 as stated in appnote.txt */
  621.   send_bits(s, dcodes - 1, 5);
  622.   send_bits(s, blcodes - 4, 4); /* not -3 as stated in appnote.txt */
  623.   for (rank = 0; rank < blcodes; rank++)
  624.   {
  625.     send_bits(s, s->bl_tree[bl_order[rank]].Len, 3);
  626.   }
  627.   send_tree(s, (ct_data*)s->dyn_ltree, lcodes - 1); /* literal tree */
  628.   send_tree(s, (ct_data*)s->dyn_dtree, dcodes - 1); /* distance tree */
  629. }
  630. /* ===========================================================================
  631.  * Send a stored block
  632.  */
  633. void _tr_stored_block(deflate_state *s, BYTE *buf, DWORD stored_len, int eof)
  634. {
  635.   send_bits(s, (STORED_BLOCK << 1) + eof, 3); /* send block type */
  636.   copy_block(s, buf, (DWORD)stored_len, 1); /* with header */
  637. }
  638. /* ===========================================================================
  639.  * Send one empty static block to give enough lookahead for inflate.
  640.  * This takes 10 bits, of which 7 may remain in the bit buffer.
  641.  * The current inflate code requires 9 bits of lookahead. If the
  642.  * last two codes for the previous block (real code plus EOB) were coded
  643.  * on 5 bits or less, inflate may have only 5+3 bits of lookahead to decode
  644.  * the last real code. In this case we send two empty static blocks instead
  645.  * of one. (There are no problems if the previous block is stored or fixed.)
  646.  * To simplify the code, we assume the worst case of last real code encoded
  647.  * on one bit only.
  648.  */
  649. void _tr_align(deflate_state *s)
  650. {
  651.   send_bits(s, STATIC_TREES << 1, 3);
  652.   send_code(s, END_BLOCK, static_ltree);
  653.   bi_flush(s);
  654.   /* Of the 10 bits for the empty block, we have already sent
  655.    * (10 - bi_valid) bits. The lookahead for the last real code (before
  656.    * the EOB of the previous block) was thus at least one plus the length
  657.    * of the EOB plus what we have just sent of the empty static block.
  658.    */
  659.   if (1+s->last_eob_len + 10-s->bi_valid < 9)
  660.   {
  661.     send_bits(s, STATIC_TREES << 1, 3);
  662.     send_code(s, END_BLOCK, static_ltree);
  663.     bi_flush(s);
  664.   }
  665.   s->last_eob_len = 7;
  666. }
  667. /* ===========================================================================
  668.  * Determine the best encoding for the current block: dynamic trees, static
  669.  * trees or store, and output the encoded block to the zip file.
  670.  */
  671. void _tr_flush_block(deflate_state *s, BYTE *buf, DWORD stored_len, int eof)
  672. {
  673.   DWORD opt_lenb, static_lenb; /* opt_len and static_len in bytes */
  674.   int max_blindex = 0; /* index of last bit length code of non zero freq */
  675.   /* Build the Huffman trees unless a stored block is forced */
  676.   if (s->level > 0)
  677.   {
  678.     /* Check if the file is ascii or binary */
  679.     if (s->data_type == Z_UNKNOWN)
  680.     {
  681.       set_data_type(s);
  682.     }
  683.     /* Construct the literal and distance trees */
  684.     build_tree(s, (tree_desc*)(&(s->l_desc)));
  685.     build_tree(s, (tree_desc*)(&(s->d_desc)));
  686.     /* At this point, opt_len and static_len are the total bit lengths of
  687.      * the compressed block data, excluding the tree representations.
  688.      */
  689.     /* Build the bit length tree for the above two trees, and get the index
  690.      * in bl_order of the last bit length code to send.
  691.      */
  692.     max_blindex = build_bl_tree(s);
  693.     /* Determine the best encoding. Compute the block lengths in bytes. */
  694.     opt_lenb = (s->opt_len + 3+7) >> 3;
  695.     static_lenb = (s->static_len + 3+7) >> 3;
  696.     if (static_lenb <= opt_lenb)
  697.     {
  698.       opt_lenb = static_lenb;
  699.     }
  700.   }
  701.   else
  702.   {
  703.     opt_lenb = static_lenb = stored_len + 5; /* force a stored block */
  704.   }
  705.   #ifdef FORCE_STORED
  706.     if (buf != (char*)0)
  707.     {
  708.       /* force stored block */
  709.     #else
  710.       if (stored_len + 4 <= opt_lenb && buf != (char*)0)
  711.       {
  712.         /* 4: two words for the lengths */
  713.       #endif
  714.       /* The test buf != NULL is only necessary if LIT_BUFSIZE > WSIZE.
  715.        * Otherwise we can't have processed more than WSIZE input bytes since
  716.        * the last block flush, because compression would have been
  717.        * successful. If LIT_BUFSIZE <= WSIZE, it is never too late to
  718.        * transform a block into a stored block.
  719.        */
  720.       _tr_stored_block(s, buf, stored_len, eof);
  721.       #ifdef FORCE_STATIC
  722.       }
  723.       else if (static_lenb >= 0)
  724.       {
  725.         /* force static trees */
  726.       #else
  727.       }
  728.       else if (static_lenb == opt_lenb)
  729.       {
  730.       #endif
  731.       send_bits(s, (STATIC_TREES << 1) + eof, 3);
  732.       compress_block(s, (ct_data*)static_ltree, (ct_data*)static_dtree);
  733.     }
  734.     else
  735.     {
  736.       send_bits(s, (DYN_TREES << 1) + eof, 3);
  737.       send_all_trees(s, s->l_desc.max_code + 1, s->d_desc.max_code + 1, max_blindex + 1);
  738.       compress_block(s, (ct_data*)s->dyn_ltree, (ct_data*)s->dyn_dtree);
  739.     }
  740.     /* The above check is made mod 2^32, for files larger than 512 MB
  741.      * and uLong implemented on 32 bits.
  742.      */
  743.     init_block(s);
  744.     if (eof)
  745.     {
  746.       bi_windup(s);
  747.     }
  748.   }
  749.   /* ===========================================================================
  750.    * Save the match info and tally the frequency counts. Return true if
  751.    * the current block must be flushed.
  752.    */
  753.   int _tr_tally(s, dist, lc)deflate_state *s;
  754.   DWORD dist; /* distance of matched string */
  755.   DWORD lc; /* match length-MIN_MATCH or unmatched char (if dist==0) */
  756.   {
  757.     s->d_buf[s->last_lit] = (WORD)dist;
  758.     s->l_buf[s->last_lit++] = (BYTE)lc;
  759.     if (dist == 0)
  760.     {
  761.       /* lc is the unmatched char */
  762.       s->dyn_ltree[lc].Freq++;
  763.     }
  764.     else
  765.     {
  766.       s->matches++;
  767.       /* Here, lc is the match length - MIN_MATCH */
  768.       dist--; /* dist = match distance - 1 */
  769.       s->dyn_ltree[_length_code[lc] + LITERALS + 1].Freq++;
  770.       s->dyn_dtree[d_code(dist)].Freq++;
  771.     }
  772.     #ifdef TRUNCATE_BLOCK
  773.       /* Try to guess if it is profitable to stop the current block here */
  774.       if ((s->last_lit &0x1fff) == 0 && s->level > 2)
  775.       {
  776.         /* Compute an upper bound for the compressed length */
  777.         ulg out_length = (ulg)s->last_lit *8L;
  778.         ulg in_length = (ulg)((long)s->strstart - s->block_start);
  779.         int dcode;
  780.         for (dcode = 0; dcode < D_CODES; dcode++)
  781.         {
  782.           out_length += (ulg)s->dyn_dtree[dcode].Freq *(5L + extra_dbits[dcode]);
  783.         }
  784.         out_length >>= 3;
  785.         Tracev((stderr, "nlast_lit %u, in %ld, out ~%ld(%ld%%) ", s->last_lit, in_length, out_length, 100L - out_length * 100L / in_length));
  786.         if (s->matches < s->last_lit / 2 && out_length < in_length / 2)
  787.         {
  788.           return 1;
  789.         }
  790.       }
  791.     #endif
  792.     return (s->last_lit == s->lit_bufsize - 1);
  793.     /* We avoid equality with lit_bufsize because of wraparound at 64K
  794.      * on 16 bit machines and because stored blocks are restricted to
  795.      * 64K-1 bytes.
  796.      */
  797.   }
  798.   /* ===========================================================================
  799.    * Send the block data compressed using the given Huffman trees
  800.    */
  801.   static void compress_block(deflate_state *s, ct_data *ltree, ct_data *dtree)
  802.   {
  803.     DWORD dist; /* distance of matched string */
  804.     int lc; /* match length or unmatched char (if dist == 0) */
  805.     DWORD lx = 0; /* running index in l_buf */
  806.     DWORD code; /* the code to send */
  807.     int extra; /* number of extra bits to send */
  808.     if (s->last_lit != 0)
  809.     {
  810.       do
  811.       {
  812.         dist = s->d_buf[lx];
  813.         lc = s->l_buf[lx++];
  814.         if (dist == 0)
  815.         {
  816.           send_code(s, lc, ltree); /* send a literal byte */
  817.         }
  818.         else
  819.         {
  820.           /* Here, lc is the match length - MIN_MATCH */
  821.           code = _length_code[lc];
  822.           send_code(s, code + LITERALS + 1, ltree); /* send the length code */
  823.           extra = extra_lbits[code];
  824.           if (extra != 0)
  825.           {
  826.             lc -= base_length[code];
  827.             send_bits(s, lc, extra); /* send the extra length bits */
  828.           }
  829.           dist--; /* dist is now the match distance - 1 */
  830.           code = d_code(dist);
  831.           send_code(s, code, dtree); /* send the distance code */
  832.           extra = extra_dbits[code];
  833.           if (extra != 0)
  834.           {
  835.             dist -= base_dist[code];
  836.             send_bits(s, dist, extra); /* send the extra distance bits */
  837.           }
  838.         } /* literal or match pair ? */
  839.         /* Check that the overlay between pending_buf and d_buf+l_buf is ok: */
  840.       }
  841.       while (lx < s->last_lit);
  842.     }
  843.     send_code(s, END_BLOCK, ltree)
  844.       ;
  845.     s->last_eob_len = ltree[END_BLOCK].Len;
  846.   }
  847.   /* ===========================================================================
  848.    * Set the data type to ASCII or BINARY, using a crude approximation:
  849.    * binary if more than 20% of the bytes are <= 6 or >= 128, ascii otherwise.
  850.    * IN assertion: the fields freq of dyn_ltree are set and the total of all
  851.    * frequencies does not exceed 64K (to fit in an int on 16 bit machines).
  852.    */
  853.   static void set_data_type(deflate_state *s)
  854.   {
  855.     int n = 0;
  856.     DWORD ascii_freq = 0;
  857.     DWORD bin_freq = 0;
  858.     while (n < 7)
  859.     {
  860.       bin_freq += s->dyn_ltree[n++].Freq;
  861.     }
  862.     while (n < 128)
  863.     {
  864.       ascii_freq += s->dyn_ltree[n++].Freq;
  865.     }
  866.     while (n < LITERALS)
  867.     {
  868.       bin_freq += s->dyn_ltree[n++].Freq;
  869.     }
  870.     s->data_type = (Byte)(bin_freq > (ascii_freq >> 2) ? Z_BINARY : Z_ASCII);
  871.   }
  872.   /* ===========================================================================
  873.    * Reverse the first len bits of a code, using straightforward code (a faster
  874.    * method would use a table)
  875.    * IN assertion: 1 <= len <= 15
  876.    */
  877.   static DWORD bi_reverse(DWORD code, int len)
  878.   {
  879.     register DWORD res = 0;
  880.     do
  881.     {
  882.       res |= code &1;
  883.       code >>= 1, res <<= 1;
  884.     }
  885.     while (--len > 0);
  886.     return res >> 1;
  887.   }
  888.   /* ===========================================================================
  889.    * Flush the bit buffer, keeping at most 7 bits in it.
  890.    */
  891.   static void bi_flush(deflate_state *s)
  892.   {
  893.     if (s->bi_valid == 16)
  894.     {
  895.       put_short(s, s->bi_buf);
  896.       s->bi_buf = 0;
  897.       s->bi_valid = 0;
  898.     }
  899.     else if (s->bi_valid >= 8)
  900.     {
  901.       put_byte(s, (Byte)s->bi_buf);
  902.       s->bi_buf >>= 8;
  903.       s->bi_valid -= 8;
  904.     }
  905.   }
  906.   /* ===========================================================================
  907.    * Flush the bit buffer and align the output on a byte boundary
  908.    */
  909.   static void bi_windup(deflate_state *s)
  910.   {
  911.     if (s->bi_valid > 8)
  912.     {
  913.       put_short(s, s->bi_buf);
  914.     }
  915.     else if (s->bi_valid > 0)
  916.     {
  917.       put_byte(s, (Byte)s->bi_buf);
  918.     }
  919.     s->bi_buf = 0;
  920.     s->bi_valid = 0;
  921.   }
  922.   /* ===========================================================================
  923.    * Copy a stored block, storing first the length and its
  924.    * one's complement if requested.
  925.    */
  926.   static void copy_block(deflate_state *s, BYTE *buf, DWORD len, int header)
  927.   {
  928.     bi_windup(s); /* align on byte boundary */
  929.     s->last_eob_len = 8; /* enough lookahead for inflate */
  930.     if (header)
  931.     {
  932.       put_short(s, (WORD)len);
  933.       put_short(s, (WORD)~len);
  934.     }
  935.     while (len--)
  936.     {
  937.       put_byte(s,  *buf++);
  938.     }
  939.   }