1 

     2 /* trees.cpp -- output deflated data using Huffman coding

     3  * Copyright (C) 1995-2005 Jean-loup Gailly

     4  * For conditions of distribution and use, see copyright notice in zlib.h

     5  */

     6 

     7 /*

     8  *  ALGORITHM

     9  *

    10  *      The "deflation" process uses several Huffman trees. The more

    11  *      common source values are represented by shorter bit sequences.

    12  *

    13  *      Each code tree is stored in a compressed form which is itself

    14  * a Huffman encoding of the lengths of all the code strings (in

    15  * ascending order by source values).  The actual code strings are

    16  * reconstructed from the lengths in the inflate process, as described

    17  * in the deflate specification.

    18  *

    19  *  REFERENCES

    20  *

    21  *      Deutsch, L.P.,"'Deflate' Compressed Data Format Specification".

    22  *      Available in ftp.uu.net:/pub/archiving/zip/doc/deflate-1.1.doc

    23  *

    24  *      Storer, James A.

    25  *          Data Compression:  Methods and Theory, pp. 49-50.

    26  *          Computer Science Press, 1988.  ISBN 0-7167-8156-5.

    27  *

    28  *      Sedgewick, R.

    29  *          Algorithms, p290.

    30  *          Addison-Wesley, 1983. ISBN 0-201-06672-6.

    31  */

    32 

    33 /* @(#) $Id: trees.cpp,v 1.1.2.1 2008/08/14 15:26:57 e0222316 Exp $ */

    34 

    35 /* #define GEN_TREES_H */

    36 

    37 #include "deflate.h"

    38 

    39 #ifdef DEBUG

    40 #  include <ctype.h>

    41 #endif

    42 

    43 /* ===========================================================================

    44  * Constants

    45  */

    46 

    47 #define MAX_BL_BITS 7

    48 /* Bit length codes must not exceed MAX_BL_BITS bits */

    49 

    50 #define END_BLOCK 256

    51 /* end of block literal code */

    52 

    53 #define REP_3_6      16

    54 /* repeat previous bit length 3-6 times (2 bits of repeat count) */

    55 

    56 #define REPZ_3_10    17

    57 /* repeat a zero length 3-10 times  (3 bits of repeat count) */

    58 

    59 #define REPZ_11_138  18

    60 /* repeat a zero length 11-138 times  (7 bits of repeat count) */

    61 

    62 local const int extra_lbits[LENGTH_CODES] /* extra bits for each length code */

    63    = {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};

    64 

    65 local const int extra_dbits[D_CODES] /* extra bits for each distance code */

    66    = {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};

    67 

    68 local const int extra_blbits[BL_CODES]/* extra bits for each bit length code */

    69    = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,3,7};

    70 

    71 local const uch bl_order[BL_CODES]

    72    = {16,17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15};

    73 /* The lengths of the bit length codes are sent in order of decreasing

    74  * probability, to avoid transmitting the lengths for unused bit length codes.

    75  */

    76 

    77 #define Buf_size (8 * 2*sizeof(char))

    78 /* Number of bits used within bi_buf. (bi_buf might be implemented on

    79  * more than 16 bits on some systems.)

    80  */

    81 

    82 /* ===========================================================================

    83  * Local data. These are initialized only once.

    84  */

    85 

    86 #define DIST_CODE_LEN  512 /* see definition of array dist_code below */

    87 

    88 #if defined(GEN_TREES_H) || !defined(STDC)

    89 /* non ANSI compilers may not accept trees.h */

    90 

    91 local ct_data static_ltree[L_CODES+2];

    92 /* The static literal tree. Since the bit lengths are imposed, there is no

    93  * need for the L_CODES extra codes used during heap construction. However

    94  * The codes 286 and 287 are needed to build a canonical tree (see _tr_init

    95  * below).

    96  */

    97 

    98 local ct_data static_dtree[D_CODES];

    99 /* The static distance tree. (Actually a trivial tree since all codes use

   100  * 5 bits.)

   101  */

   102 

   103 uch _dist_code[DIST_CODE_LEN];

   104 /* Distance codes. The first 256 values correspond to the distances

   105  * 3 .. 258, the last 256 values correspond to the top 8 bits of

   106  * the 15 bit distances.

   107  */

   108 

   109 uch _length_code[MAX_MATCH-MIN_MATCH+1];

   110 /* length code for each normalized match length (0 == MIN_MATCH) */

   111 

   112 local int base_length[LENGTH_CODES];

   113 /* First normalized length for each code (0 = MIN_MATCH) */

   114 

   115 local int base_dist[D_CODES];

   116 /* First normalized distance for each code (0 = distance of 1) */

   117 

   118 #else

   119 #  include "trees.h"

   120 #endif /* GEN_TREES_H */

   121 

   122 struct static_tree_desc_s {

   123     const ct_data *static_tree;  /* static tree or NULL */

   124     const intf *extra_bits;      /* extra bits for each code or NULL */

   125     int     extra_base;          /* base index for extra_bits */

   126     int     elems;               /* max number of elements in the tree */

   127     int     max_length;          /* max bit length for the codes */

   128 };

   129 #ifndef SYMBIAN_EZLIB_DEVICE

   130 local static_tree_desc  static_l_desc =

   131 {static_ltree, extra_lbits, LITERALS+1, L_CODES, MAX_BITS};

   132 

   133 local static_tree_desc  static_d_desc =

   134 {static_dtree, extra_dbits, 0,          D_CODES, MAX_BITS};

   135 

   136 local static_tree_desc  static_bl_desc =

   137 {(const ct_data *)0, extra_blbits, 0,   BL_CODES, MAX_BL_BITS};

   138 

   139 #else

   140 

   141 local const static_tree_desc  static_l_desc =

   142 {static_ltree, extra_lbits, LITERALS+1, L_CODES, MAX_BITS};

   143 

   144 local const static_tree_desc  static_d_desc =

   145 {static_dtree, extra_dbits, 0,          D_CODES, MAX_BITS};

   146 

   147 local const static_tree_desc  static_bl_desc =

   148 {(const ct_data *)0, extra_blbits, 0,   BL_CODES, MAX_BL_BITS};

   149 

   150 #endif //SYMBIAN_EZLIB_DEVICE

   151 

   152 

   153 /* ===========================================================================

   154  * Local (static) routines in this file.

   155  */

   156 

   157 local void tr_static_init OF((void));

   158 local void init_block     OF((deflate_state *s));

   159 local void pqdownheap     OF((deflate_state *s, ct_data *tree, int k));

   160 local void gen_bitlen     OF((deflate_state *s, tree_desc *desc));

   161 local void gen_codes      OF((ct_data *tree, int max_code, ushf *bl_count));

   162 local void build_tree     OF((deflate_state *s, tree_desc *desc));

   163 local void scan_tree      OF((deflate_state *s, ct_data *tree, int max_code));

   164 local void send_tree      OF((deflate_state *s, ct_data *tree, int max_code));

   165 local int  build_bl_tree  OF((deflate_state *s));

   166 local void send_all_trees OF((deflate_state *s, int lcodes, int dcodes,

   167                               int blcodes));

   168 local void compress_block OF((deflate_state *s, ct_data *ltree,

   169                               ct_data *dtree));

   170 local void set_data_type  OF((deflate_state *s));

   171 local unsigned bi_reverse OF((unsigned value, int length));

   172 local void bi_windup      OF((deflate_state *s));

   173 local void bi_flush       OF((deflate_state *s));

   174 local void copy_block     OF((deflate_state *s, charf *buf, unsigned len,

   175                               int header));

   176 

   177 #ifdef GEN_TREES_H

   178 local void gen_trees_header OF((void));

   179 #endif

   180 

   181 #ifndef DEBUG

   182 #  define send_code(s, c, tree) send_bits(s, tree[c].Code, tree[c].Len)

   183    /* Send a code of the given tree. c and tree must not have side effects */

   184 

   185 #else /* DEBUG */

   186 #  define send_code(s, c, tree) \

   187      { if (z_verbose>2) fprintf(stderr,"\ncd %3d ",(c)); \

   188        send_bits(s, tree[c].Code, tree[c].Len); }

   189 #endif

   190 

   191 /* ===========================================================================

   192  * Output a short LSB first on the stream.

   193  * IN assertion: there is enough room in pendingBuf.

   194  */

   195 #define put_short(s, w) { \

   196     put_byte(s, (uch)((w) & 0xff)); \

   197     put_byte(s, (uch)((ush)(w) >> 8)); \

   198 }

   199 

   200 /* ===========================================================================

   201  * Send a value on a given number of bits.

   202  * IN assertion: length <= 16 and value fits in length bits.

   203  */

   204 #ifdef DEBUG

   205 local void send_bits      OF((deflate_state *s, int value, int length));

   206 

   207 #ifdef __SYMBIAN32__

   208 local void send_bits(deflate_state * s, int value,int  length)

   209 #else	

   210 local void send_bits(s, value, length)

   211     deflate_state *s;

   212     int value;  /* value to send */

   213     int length; /* number of bits */

   214 #endif //__SYMBIAN32__

   215 {

   216     Tracevv((stderr," l %2d v %4x ", length, value));

   217     Assert(length > 0 && length <= 15, "invalid length");

   218     s->bits_sent += (ulg)length;

   219 

   220     /* If not enough room in bi_buf, use (valid) bits from bi_buf and

   221      * (16 - bi_valid) bits from value, leaving (width - (16-bi_valid))

   222      * unused bits in value.

   223      */

   224     if (s->bi_valid > (int)Buf_size - length) {

   225         s->bi_buf |= (value << s->bi_valid);

   226         put_short(s, s->bi_buf);

   227         s->bi_buf = (ush)value >> (Buf_size - s->bi_valid);

   228         s->bi_valid += length - Buf_size;

   229     } else {

   230         s->bi_buf |= value << s->bi_valid;

   231         s->bi_valid += length;

   232     }

   233 }

   234 #else /* !DEBUG */

   235 

   236 #define send_bits(s, value, length) \

   237 { int len = length;\

   238   if (s->bi_valid > (int)Buf_size - len) {\

   239     int val = value;\

   240     s->bi_buf |= (val << s->bi_valid);\

   241     put_short(s, s->bi_buf);\

   242 	s->bi_buf = (ush)val >> (Buf_size - s->bi_valid);\

   243     s->bi_valid += len - Buf_size;\

   244   } else {\

   245     s->bi_buf |= (value) << s->bi_valid;\

   246     s->bi_valid += len;\

   247   }\

   248 }

   249 #endif /* DEBUG */

   250 

   251 

   252 /* the arguments must not have side effects */

   253 

   254 /* ===========================================================================

   255  * Initialize the various 'constant' tables.

   256  */

   257 local void tr_static_init()

   258 {

   259 #if defined(GEN_TREES_H) || !defined(STDC)

   260     static int static_init_done = 0;

   261     int n;        /* iterates over tree elements */

   262     int bits;     /* bit counter */

   263     int length;   /* length value */

   264     int code;     /* code value */

   265     int dist;     /* distance index */

   266     ush bl_count[MAX_BITS+1];

   267     /* number of codes at each bit length for an optimal tree */

   268 

   269     if (static_init_done) return;

   270 

   271     /* For some embedded targets, global variables are not initialized: */

   272     static_l_desc.static_tree = static_ltree;

   273     static_l_desc.extra_bits = extra_lbits;

   274     static_d_desc.static_tree = static_dtree;

   275     static_d_desc.extra_bits = extra_dbits;

   276     static_bl_desc.extra_bits = extra_blbits;

   277 

   278     /* Initialize the mapping length (0..255) -> length code (0..28) */

   279     length = 0;

   280     for (code = 0; code < LENGTH_CODES-1; code++) {

   281         base_length[code] = length;

   282         for (n = 0; n < (1<<extra_lbits[code]); n++) {

   283             _length_code[length++] = (uch)code;

   284         }

   285     }

   286     Assert (length == 256, "tr_static_init: length != 256");

   287     /* Note that the length 255 (match length 258) can be represented

   288      * in two different ways: code 284 + 5 bits or code 285, so we

   289      * overwrite length_code[255] to use the best encoding:

   290      */

   291     _length_code[length-1] = (uch)code;

   292 

   293     /* Initialize the mapping dist (0..32K) -> dist code (0..29) */

   294     dist = 0;

   295     for (code = 0 ; code < 16; code++) {

   296         base_dist[code] = dist;

   297         for (n = 0; n < (1<<extra_dbits[code]); n++) {

   298             _dist_code[dist++] = (uch)code;

   299         }

   300     }

   301     Assert (dist == 256, "tr_static_init: dist != 256");

   302     dist >>= 7; /* from now on, all distances are divided by 128 */

   303     for ( ; code < D_CODES; code++) {

   304         base_dist[code] = dist << 7;

   305         for (n = 0; n < (1<<(extra_dbits[code]-7)); n++) {

   306             _dist_code[256 + dist++] = (uch)code;

   307         }

   308     }

   309     Assert (dist == 256, "tr_static_init: 256+dist != 512");

   310 

   311     /* Construct the codes of the static literal tree */

   312     for (bits = 0; bits <= MAX_BITS; bits++) bl_count[bits] = 0;

   313     n = 0;

   314     while (n <= 143) static_ltree[n++].Len = 8, bl_count[8]++;

   315     while (n <= 255) static_ltree[n++].Len = 9, bl_count[9]++;

   316     while (n <= 279) static_ltree[n++].Len = 7, bl_count[7]++;

   317     while (n <= 287) static_ltree[n++].Len = 8, bl_count[8]++;

   318     /* Codes 286 and 287 do not exist, but we must include them in the

   319      * tree construction to get a canonical Huffman tree (longest code

   320      * all ones)

   321      */

   322     gen_codes((ct_data *)static_ltree, L_CODES+1, bl_count);

   323 

   324     /* The static distance tree is trivial: */

   325     for (n = 0; n < D_CODES; n++) {

   326         static_dtree[n].Len = 5;

   327         static_dtree[n].Code = bi_reverse((unsigned)n, 5);

   328     }

   329     static_init_done = 1;

   330 

   331 #  ifdef GEN_TREES_H

   332     gen_trees_header();

   333 #  endif

   334 #endif /* defined(GEN_TREES_H) || !defined(STDC) */

   335 }

   336 /* ===========================================================================

   337  * Genererate the file trees.h describing the static trees.

   338  */

   339 #ifdef GEN_TREES_H

   340 #  ifndef DEBUG

   341 #    include <stdio.h>

   342 #  endif

   343 

   344 #  define SEPARATOR(i, last, width) \

   345       ((i) == (last)? "\n};\n\n" :    \

   346        ((i) % (width) == (width)-1 ? ",\n" : ", "))

   347 

   348 void gen_trees_header()

   349 {

   350     FILE *header = fopen("trees.h", "w");

   351     int i;

   352 

   353     Assert (header != NULL, "Can't open trees.h");

   354     fprintf(header,

   355             "/* header created automatically with -DGEN_TREES_H */\n\n");

   356 

   357     fprintf(header, "local const ct_data static_ltree[L_CODES+2] = {\n");

   358     for (i = 0; i < L_CODES+2; i++) {

   359         fprintf(header, "{{%3u},{%3u}}%s", static_ltree[i].Code,

   360                 static_ltree[i].Len, SEPARATOR(i, L_CODES+1, 5));

   361     }

   362 

   363     fprintf(header, "local const ct_data static_dtree[D_CODES] = {\n");

   364     for (i = 0; i < D_CODES; i++) {

   365         fprintf(header, "{{%2u},{%2u}}%s", static_dtree[i].Code,

   366                 static_dtree[i].Len, SEPARATOR(i, D_CODES-1, 5));

   367     }

   368 

   369     fprintf(header, "const uch _dist_code[DIST_CODE_LEN] = {\n");

   370     for (i = 0; i < DIST_CODE_LEN; i++) {

   371         fprintf(header, "%2u%s", _dist_code[i],

   372                 SEPARATOR(i, DIST_CODE_LEN-1, 20));

   373     }

   374 

   375     fprintf(header, "const uch _length_code[MAX_MATCH-MIN_MATCH+1]= {\n");

   376     for (i = 0; i < MAX_MATCH-MIN_MATCH+1; i++) {

   377         fprintf(header, "%2u%s", _length_code[i],

   378                 SEPARATOR(i, MAX_MATCH-MIN_MATCH, 20));

   379     }

   380 

   381     fprintf(header, "local const int base_length[LENGTH_CODES] = {\n");

   382     for (i = 0; i < LENGTH_CODES; i++) {

   383         fprintf(header, "%1u%s", base_length[i],

   384                 SEPARATOR(i, LENGTH_CODES-1, 20));

   385     }

   386 

   387     fprintf(header, "local const int base_dist[D_CODES] = {\n");

   388     for (i = 0; i < D_CODES; i++) {

   389         fprintf(header, "%5u%s", base_dist[i],

   390                 SEPARATOR(i, D_CODES-1, 10));

   391     }

   392 

   393     fclose(header);

   394 }

   395 #endif /* GEN_TREES_H */

   396 

   397 /* ===========================================================================

   398  * Initialize the tree data structures for a new zlib stream.

   399  */

   400 #ifdef __SYMBIAN32__

   401 void _tr_init(   deflate_state * s)

   402 #else    

   403 void _tr_init(s)

   404     deflate_state *s;

   405 #endif //__SYMBIAN32__

   406 {

   407     tr_static_init();

   408 

   409     s->l_desc.dyn_tree = s->dyn_ltree;

   410     s->l_desc.stat_desc = &static_l_desc;

   411 

   412     s->d_desc.dyn_tree = s->dyn_dtree;

   413     s->d_desc.stat_desc = &static_d_desc;

   414 

   415     s->bl_desc.dyn_tree = s->bl_tree;

   416     s->bl_desc.stat_desc = &static_bl_desc;

   417 

   418     s->bi_buf = 0;

   419     s->bi_valid = 0;

   420     s->last_eob_len = 8; /* enough lookahead for inflate */

   421 #ifdef DEBUG

   422     s->compressed_len = 0L;

   423     s->bits_sent = 0L;

   424 #endif

   425 

   426     /* Initialize the first block of the first file: */

   427     init_block(s);

   428 }

   429 

   430 /* ===========================================================================

   431  * Initialize a new block.

   432  */

   433 #ifdef __SYMBIAN32__

   434 local void init_block(    deflate_state * s)

   435 #else

   436 local void init_block(s)

   437     deflate_state *s;

   438 #endif //__SYMBIAN32__

   439 {

   440     int n; /* iterates over tree elements */

   441 

   442     /* Initialize the trees. */

   443     for (n = 0; n < L_CODES;  n++) s->dyn_ltree[n].Freq = 0;

   444     for (n = 0; n < D_CODES;  n++) s->dyn_dtree[n].Freq = 0;

   445     for (n = 0; n < BL_CODES; n++) s->bl_tree[n].Freq = 0;

   446 

   447     s->dyn_ltree[END_BLOCK].Freq = 1;

   448     s->opt_len = s->static_len = 0L;

   449     s->last_lit = s->matches = 0;

   450 }

   451 

   452 #define SMALLEST 1

   453 /* Index within the heap array of least frequent node in the Huffman tree */

   454 

   455 

   456 /* ===========================================================================

   457  * Remove the smallest element from the heap and recreate the heap with

   458  * one less element. Updates heap and heap_len.

   459  */

   460 #define pqremove(s, tree, top) \

   461 {\

   462     top = s->heap[SMALLEST]; \

   463     s->heap[SMALLEST] = s->heap[s->heap_len--]; \

   464     pqdownheap(s, tree, SMALLEST); \

   465 }

   466 

   467 /* ===========================================================================

   468  * Compares to subtrees, using the tree depth as tie breaker when

   469  * the subtrees have equal frequency. This minimizes the worst case length.

   470  */

   471 #define smaller(tree, n, m, depth) \

   472    (tree[n].Freq < tree[m].Freq || \

   473    (tree[n].Freq == tree[m].Freq && depth[n] <= depth[m]))

   474 

   475 /* ===========================================================================

   476  * Restore the heap property by moving down the tree starting at node k,

   477  * exchanging a node with the smallest of its two sons if necessary, stopping

   478  * when the heap property is re-established (each father smaller than its

   479  * two sons).

   480  */

   481 #ifdef __SYMBIAN32__

   482 local void pqdownheap(  deflate_state * s,ct_data *  tree,int k)

   483 #else

   484 local void pqdownheap(s, tree, k)

   485     deflate_state *s;

   486     ct_data *tree;  /* the tree to restore */

   487     int k;               /* node to move down */

   488 #endif //__SYMBIAN32__	

   489 {

   490     int v = s->heap[k];

   491     int j = k << 1;  /* left son of k */

   492     while (j <= s->heap_len) {

   493         /* Set j to the smallest of the two sons: */

   494         if (j < s->heap_len &&

   495             smaller(tree, s->heap[j+1], s->heap[j], s->depth)) {

   496             j++;

   497         }

   498         /* Exit if v is smaller than both sons */

   499         if (smaller(tree, v, s->heap[j], s->depth)) break;

   500 

   501         /* Exchange v with the smallest son */

   502         s->heap[k] = s->heap[j];  k = j;

   503 

   504         /* And continue down the tree, setting j to the left son of k */

   505         j <<= 1;

   506     }

   507     s->heap[k] = v;

   508 }

   509 

   510 /* ===========================================================================

   511  * Compute the optimal bit lengths for a tree and update the total bit length

   512  * for the current block.

   513  * IN assertion: the fields freq and dad are set, heap[heap_max] and

   514  *    above are the tree nodes sorted by increasing frequency.

   515  * OUT assertions: the field len is set to the optimal bit length, the

   516  *     array bl_count contains the frequencies for each bit length.

   517  *     The length opt_len is updated; static_len is also updated if stree is

   518  *     not null.

   519  */

   520 #ifdef __SYMBIAN32__

   521 local void gen_bitlen(    deflate_state * s,     tree_desc * desc)

   522 #else

   523 local void gen_bitlen(s, desc)

   524     deflate_state *s;

   525     tree_desc *desc;    /* the tree descriptor */

   526 #endif //__SYMBIAN32__

   527 {

   528     ct_data *tree        = desc->dyn_tree;

   529     int max_code         = desc->max_code;

   530     const ct_data *stree = desc->stat_desc->static_tree;

   531     const intf *extra    = desc->stat_desc->extra_bits;

   532     int base             = desc->stat_desc->extra_base;

   533     int max_length       = desc->stat_desc->max_length;

   534     int h;              /* heap index */

   535     int n, m;           /* iterate over the tree elements */

   536     int bits;           /* bit length */

   537     int xbits;          /* extra bits */

   538     ush f;              /* frequency */

   539     int overflow = 0;   /* number of elements with bit length too large */

   540 

   541     for (bits = 0; bits <= MAX_BITS; bits++) s->bl_count[bits] = 0;

   542 

   543     /* In a first pass, compute the optimal bit lengths (which may

   544      * overflow in the case of the bit length tree).

   545      */

   546     tree[s->heap[s->heap_max]].Len = 0; /* root of the heap */

   547 

   548     for (h = s->heap_max+1; h < HEAP_SIZE; h++) {

   549         n = s->heap[h];

   550         bits = tree[tree[n].Dad].Len + 1;

   551         if (bits > max_length) bits = max_length, overflow++;

   552         tree[n].Len = (ush)bits;

   553         /* We overwrite tree[n].Dad which is no longer needed */

   554 

   555         if (n > max_code) continue; /* not a leaf node */

   556 

   557         s->bl_count[bits]++;

   558         xbits = 0;

   559         if (n >= base) xbits = extra[n-base];

   560         f = tree[n].Freq;

   561         s->opt_len += (ulg)f * (bits + xbits);

   562         if (stree) s->static_len += (ulg)f * (stree[n].Len + xbits);

   563     }

   564     if (overflow == 0) return;

   565 

   566     Trace((stderr,"\nbit length overflow\n"));

   567     /* This happens for example on obj2 and pic of the Calgary corpus */

   568 

   569     /* Find the first bit length which could increase: */

   570     do {

   571         bits = max_length-1;

   572         while (s->bl_count[bits] == 0) bits--;

   573         s->bl_count[bits]--;      /* move one leaf down the tree */

   574         s->bl_count[bits+1] += 2; /* move one overflow item as its brother */

   575         s->bl_count[max_length]--;

   576         /* The brother of the overflow item also moves one step up,

   577          * but this does not affect bl_count[max_length]

   578          */

   579         overflow -= 2;

   580     } while (overflow > 0);

   581 

   582     /* Now recompute all bit lengths, scanning in increasing frequency.

   583      * h is still equal to HEAP_SIZE. (It is simpler to reconstruct all

   584      * lengths instead of fixing only the wrong ones. This idea is taken

   585      * from 'ar' written by Haruhiko Okumura.)

   586      */

   587     for (bits = max_length; bits != 0; bits--) {

   588         n = s->bl_count[bits];

   589         while (n != 0) {

   590             m = s->heap[--h];

   591             if (m > max_code) continue;

   592             if ((unsigned) tree[m].Len != (unsigned) bits) {

   593                 Trace((stderr,"code %d bits %d->%d\n", m, tree[m].Len, bits));

   594                 s->opt_len += ((long)bits - (long)tree[m].Len)

   595                               *(long)tree[m].Freq;

   596                 tree[m].Len = (ush)bits;

   597             }

   598             n--;

   599         }

   600     }

   601 }

   602 

   603 /* ===========================================================================

   604  * Generate the codes for a given tree and bit counts (which need not be

   605  * optimal).

   606  * IN assertion: the array bl_count contains the bit length statistics for

   607  * the given tree and the field len is set for all tree elements.

   608  * OUT assertion: the field code is set for all tree elements of non

   609  *     zero code length.

   610  */

   611 #ifdef __SYMBIAN32__

   612 local void gen_codes (    ct_data * tree, int max_code,    ushf *  bl_count)

   613 #else

   614 local void gen_codes (tree, max_code, bl_count)

   615     ct_data *tree;             /* the tree to decorate */

   616     int max_code;              /* largest code with non zero frequency */

   617     ushf *bl_count;            /* number of codes at each bit length */

   618 #endif //__SYMBIAN32__

   619 {

   620     ush next_code[MAX_BITS+1]; /* next code value for each bit length */

   621     ush code = 0;              /* running code value */

   622     int bits;                  /* bit index */

   623     int n;                     /* code index */

   624 

   625     /* The distribution counts are first used to generate the code values

   626      * without bit reversal.

   627      */

   628     for (bits = 1; bits <= MAX_BITS; bits++) {

   629         next_code[bits] = code = (code + bl_count[bits-1]) << 1;

   630     }

   631     /* Check that the bit counts in bl_count are consistent. The last code

   632      * must be all ones.

   633      */

   634     Assert (code + bl_count[MAX_BITS]-1 == (1<<MAX_BITS)-1,

   635             "inconsistent bit counts");

   636     Tracev((stderr,"\ngen_codes: max_code %d ", max_code));

   637 

   638     for (n = 0;  n <= max_code; n++) {

   639         int len = tree[n].Len;

   640         if (len == 0) continue;

   641         /* Now reverse the bits */

   642         tree[n].Code = bi_reverse(next_code[len]++, len);

   643 

   644         Tracecv(tree != static_ltree, (stderr,"\nn %3d %c l %2d c %4x (%x) ",

   645              n, (isgraph(n) ? n : ' '), len, tree[n].Code, next_code[len]-1));

   646     }

   647 }

   648 

   649 /* ===========================================================================

   650  * Construct one Huffman tree and assigns the code bit strings and lengths.

   651  * Update the total bit length for the current block.

   652  * IN assertion: the field freq is set for all tree elements.

   653  * OUT assertions: the fields len and code are set to the optimal bit length

   654  *     and corresponding code. The length opt_len is updated; static_len is

   655  *     also updated if stree is not null. The field max_code is set.

   656  */

   657 #ifdef __SYMBIAN32__

   658 local void build_tree(    deflate_state * s,    tree_desc *  desc)

   659 #else

   660 local void build_tree(s, desc)

   661     deflate_state *s;

   662     tree_desc *desc; /* the tree descriptor */

   663 #endif //__SYMBIAN32__

   664 {

   665     ct_data *tree         = desc->dyn_tree;

   666     const ct_data *stree  = desc->stat_desc->static_tree;

   667     int elems             = desc->stat_desc->elems;

   668     int n, m;          /* iterate over heap elements */

   669     int max_code = -1; /* largest code with non zero frequency */

   670     int node;          /* new node being created */

   671 

   672     /* Construct the initial heap, with least frequent element in

   673      * heap[SMALLEST]. The sons of heap[n] are heap[2*n] and heap[2*n+1].

   674      * heap[0] is not used.

   675      */

   676     s->heap_len = 0, s->heap_max = HEAP_SIZE;

   677 

   678     for (n = 0; n < elems; n++) {

   679         if (tree[n].Freq != 0) {

   680             s->heap[++(s->heap_len)] = max_code = n;

   681             s->depth[n] = 0;

   682         } else {

   683             tree[n].Len = 0;

   684         }

   685     }

   686 

   687     /* The pkzip format requires that at least one distance code exists,

   688      * and that at least one bit should be sent even if there is only one

   689      * possible code. So to avoid special checks later on we force at least

   690      * two codes of non zero frequency.

   691      */

   692     while (s->heap_len < 2) {

   693         node = s->heap[++(s->heap_len)] = (max_code < 2 ? ++max_code : 0);

   694         tree[node].Freq = 1;

   695         s->depth[node] = 0;

   696         s->opt_len--; if (stree) s->static_len -= stree[node].Len;

   697         /* node is 0 or 1 so it does not have extra bits */

   698     }

   699     desc->max_code = max_code;

   700 

   701     /* The elements heap[heap_len/2+1 .. heap_len] are leaves of the tree,

   702      * establish sub-heaps of increasing lengths:

   703      */

   704     for (n = s->heap_len/2; n >= 1; n--) pqdownheap(s, tree, n);

   705 

   706     /* Construct the Huffman tree by repeatedly combining the least two

   707      * frequent nodes.

   708      */

   709     node = elems;              /* next internal node of the tree */

   710     do {

   711         pqremove(s, tree, n);  /* n = node of least frequency */

   712         m = s->heap[SMALLEST]; /* m = node of next least frequency */

   713 

   714         s->heap[--(s->heap_max)] = n; /* keep the nodes sorted by frequency */

   715         s->heap[--(s->heap_max)] = m;

   716 

   717         /* Create a new node father of n and m */

   718         tree[node].Freq = tree[n].Freq + tree[m].Freq;

   719         s->depth[node] = (uch)((s->depth[n] >= s->depth[m] ?

   720                                 s->depth[n] : s->depth[m]) + 1);

   721         tree[n].Dad = tree[m].Dad = (ush)node;

   722 #ifdef DUMP_BL_TREE

   723         if (tree == s->bl_tree) {

   724             fprintf(stderr,"\nnode %d(%d), sons %d(%d) %d(%d)",

   725                     node, tree[node].Freq, n, tree[n].Freq, m, tree[m].Freq);

   726         }

   727 #endif

   728         /* and insert the new node in the heap */

   729         s->heap[SMALLEST] = node++;

   730         pqdownheap(s, tree, SMALLEST);

   731 

   732     } while (s->heap_len >= 2);

   733 

   734     s->heap[--(s->heap_max)] = s->heap[SMALLEST];

   735 

   736     /* At this point, the fields freq and dad are set. We can now

   737      * generate the bit lengths.

   738      */

   739     gen_bitlen(s, (tree_desc *)desc);

   740 

   741     /* The field len is now set, we can generate the bit codes */

   742     gen_codes ((ct_data *)tree, max_code, s->bl_count);

   743 }

   744 

   745 /* ===========================================================================

   746  * Scan a literal or distance tree to determine the frequencies of the codes

   747  * in the bit length tree.

   748  */

   749  #ifdef __SYMBIAN32__

   750  local void scan_tree (   deflate_state * s,   ct_data *  tree,int  max_code)

   751  #else

   752 local void scan_tree (s, tree, max_code)

   753     deflate_state *s;

   754     ct_data *tree;   /* the tree to be scanned */

   755     int max_code;    /* and its largest code of non zero frequency */

   756 #endif //__SYMBIAN32__

   757 {

   758     int n;                     /* iterates over all tree elements */

   759     int prevlen = -1;          /* last emitted length */

   760     int curlen;                /* length of current code */

   761     int nextlen = tree[0].Len; /* length of next code */

   762     int count = 0;             /* repeat count of the current code */

   763     int max_count = 7;         /* max repeat count */

   764     int min_count = 4;         /* min repeat count */

   765 

   766     if (nextlen == 0) max_count = 138, min_count = 3;

   767     tree[max_code+1].Len = (ush)0xffff; /* guard */

   768 

   769     for (n = 0; n <= max_code; n++) {

   770         curlen = nextlen; nextlen = tree[n+1].Len;

   771         if (++count < max_count && curlen == nextlen) {

   772             continue;

   773         } else if (count < min_count) {

   774             s->bl_tree[curlen].Freq += count;

   775         } else if (curlen != 0) {

   776             if (curlen != prevlen) s->bl_tree[curlen].Freq++;

   777             s->bl_tree[REP_3_6].Freq++;

   778         } else if (count <= 10) {

   779             s->bl_tree[REPZ_3_10].Freq++;

   780         } else {

   781             s->bl_tree[REPZ_11_138].Freq++;

   782         }

   783         count = 0; prevlen = curlen;

   784         if (nextlen == 0) {

   785             max_count = 138, min_count = 3;

   786         } else if (curlen == nextlen) {

   787             max_count = 6, min_count = 3;

   788         } else {

   789             max_count = 7, min_count = 4;

   790         }

   791     }

   792 }

   793 

   794 /* ===========================================================================

   795  * Send a literal or distance tree in compressed form, using the codes in

   796  * bl_tree.

   797  */

   798 #ifdef __SYMBIAN32__

   799 local void send_tree (    deflate_state * s,    ct_data *  tree, int max_code)

   800 #else

   801 local void send_tree (s, tree, max_code)

   802     deflate_state *s;

   803     ct_data *tree; /* the tree to be scanned */

   804     int max_code;       /* and its largest code of non zero frequency */

   805 #endif //__SYMBIAN32__

   806 {

   807     int n;                     /* iterates over all tree elements */

   808     int prevlen = -1;          /* last emitted length */

   809     int curlen;                /* length of current code */

   810     int nextlen = tree[0].Len; /* length of next code */

   811     int count = 0;             /* repeat count of the current code */

   812     int max_count = 7;         /* max repeat count */

   813     int min_count = 4;         /* min repeat count */

   814 

   815     /* tree[max_code+1].Len = -1; */  /* guard already set */

   816     if (nextlen == 0) max_count = 138, min_count = 3;

   817 

   818     for (n = 0; n <= max_code; n++) {

   819         curlen = nextlen; nextlen = tree[n+1].Len;

   820         if (++count < max_count && curlen == nextlen) {

   821             continue;

   822         } else if (count < min_count) {

   823             do { send_code(s, curlen, s->bl_tree); } while (--count != 0);

   824 

   825         } else if (curlen != 0) {

   826             if (curlen != prevlen) {

   827                 send_code(s, curlen, s->bl_tree); count--;

   828             }

   829             Assert(count >= 3 && count <= 6, " 3_6?");

   830             send_code(s, REP_3_6, s->bl_tree); send_bits(s, count-3, 2);

   831 

   832         } else if (count <= 10) {

   833             send_code(s, REPZ_3_10, s->bl_tree); send_bits(s, count-3, 3);

   834 

   835         } else {

   836             send_code(s, REPZ_11_138, s->bl_tree); send_bits(s, count-11, 7);

   837         }

   838         count = 0; prevlen = curlen;

   839         if (nextlen == 0) {

   840             max_count = 138, min_count = 3;

   841         } else if (curlen == nextlen) {

   842             max_count = 6, min_count = 3;

   843         } else {

   844             max_count = 7, min_count = 4;

   845         }

   846     }

   847 }

   848 

   849 /* ===========================================================================

   850  * Construct the Huffman tree for the bit lengths and return the index in

   851  * bl_order of the last bit length code to send.

   852  */

   853 #ifdef __SYMBIAN32__

   854 local int build_bl_tree(  deflate_state * s)

   855 #else

   856 local int build_bl_tree(s)

   857     deflate_state *s;

   858 #endif //__SYMBIAN32__

   859 {

   860     int max_blindex;  /* index of last bit length code of non zero freq */

   861 

   862     /* Determine the bit length frequencies for literal and distance trees */

   863     scan_tree(s, (ct_data *)s->dyn_ltree, s->l_desc.max_code);

   864     scan_tree(s, (ct_data *)s->dyn_dtree, s->d_desc.max_code);

   865 

   866     /* Build the bit length tree: */

   867     build_tree(s, (tree_desc *)(&(s->bl_desc)));

   868     /* opt_len now includes the length of the tree representations, except

   869      * the lengths of the bit lengths codes and the 5+5+4 bits for the counts.

   870      */

   871 

   872     /* Determine the number of bit length codes to send. The pkzip format

   873      * requires that at least 4 bit length codes be sent. (appnote.txt says

   874      * 3 but the actual value used is 4.)

   875      */

   876     for (max_blindex = BL_CODES-1; max_blindex >= 3; max_blindex--) {

   877         if (s->bl_tree[bl_order[max_blindex]].Len != 0) break;

   878     }

   879     /* Update opt_len to include the bit length tree and counts */

   880     s->opt_len += 3*(max_blindex+1) + 5+5+4;

   881     Tracev((stderr, "\ndyn trees: dyn %ld, stat %ld",

   882             s->opt_len, s->static_len));

   883 

   884     return max_blindex;

   885 }

   886 

   887 /* ===========================================================================

   888  * Send the header for a block using dynamic Huffman trees: the counts, the

   889  * lengths of the bit length codes, the literal tree and the distance tree.

   890  * IN assertion: lcodes >= 257, dcodes >= 1, blcodes >= 4.

   891  */

   892 #ifdef __SYMBIAN32__

   893 local void send_all_trees(   deflate_state * s, int lcodes, int dcodes, int blcodes)

   894 #else	

   895 local void send_all_trees(s, lcodes, dcodes, blcodes)

   896     deflate_state *s;

   897     int lcodes, dcodes, blcodes; /* number of codes for each tree */

   898 #endif //__SYMBIAN32__

   899 {

   900     int rank;                    /* index in bl_order */

   901 

   902     Assert (lcodes >= 257 && dcodes >= 1 && blcodes >= 4, "not enough codes");

   903     Assert (lcodes <= L_CODES && dcodes <= D_CODES && blcodes <= BL_CODES,

   904             "too many codes");

   905     Tracev((stderr, "\nbl counts: "));

   906     send_bits(s, lcodes-257, 5); /* not +255 as stated in appnote.txt */

   907     send_bits(s, dcodes-1,   5);

   908     send_bits(s, blcodes-4,  4); /* not -3 as stated in appnote.txt */

   909     for (rank = 0; rank < blcodes; rank++) {

   910         Tracev((stderr, "\nbl code %2d ", bl_order[rank]));

   911         send_bits(s, s->bl_tree[bl_order[rank]].Len, 3);

   912     }

   913     Tracev((stderr, "\nbl tree: sent %ld", s->bits_sent));

   914 

   915     send_tree(s, (ct_data *)s->dyn_ltree, lcodes-1); /* literal tree */

   916     Tracev((stderr, "\nlit tree: sent %ld", s->bits_sent));

   917 

   918     send_tree(s, (ct_data *)s->dyn_dtree, dcodes-1); /* distance tree */

   919     Tracev((stderr, "\ndist tree: sent %ld", s->bits_sent));

   920 }

   921 

   922 /* ===========================================================================

   923  * Send a stored block

   924  */

   925 #ifdef __SYMBIAN32__

   926 void _tr_stored_block(   deflate_state * s,    charf *  buf,ulg  stored_len, int eof)

   927 #else

   928 void _tr_stored_block(s, buf, stored_len, eof)

   929     deflate_state *s;

   930     charf *buf;       /* input block */

   931     ulg stored_len;   /* length of input block */

   932     int eof;          /* true if this is the last block for a file */

   933 #endif //__SYMBIAN32__	

   934 {

   935     send_bits(s, (STORED_BLOCK<<1)+eof, 3);  /* send block type */

   936 #ifdef DEBUG

   937     s->compressed_len = (s->compressed_len + 3 + 7) & (ulg)~7L;

   938     s->compressed_len += (stored_len + 4) << 3;

   939 #endif

   940     copy_block(s, buf, (unsigned)stored_len, 1); /* with header */

   941 }

   942 

   943 /* ===========================================================================

   944  * Send one empty static block to give enough lookahead for inflate.

   945  * This takes 10 bits, of which 7 may remain in the bit buffer.

   946  * The current inflate code requires 9 bits of lookahead. If the

   947  * last two codes for the previous block (real code plus EOB) were coded

   948  * on 5 bits or less, inflate may have only 5+3 bits of lookahead to decode

   949  * the last real code. In this case we send two empty static blocks instead

   950  * of one. (There are no problems if the previous block is stored or fixed.)

   951  * To simplify the code, we assume the worst case of last real code encoded

   952  * on one bit only.

   953  */

   954 #ifdef __SYMBIAN32__

   955 void _tr_align(    deflate_state * s)

   956 #else

   957 void _tr_align(s)

   958     deflate_state *s;

   959 #endif //__SYMBIAN32__

   960 {

   961     send_bits(s, STATIC_TREES<<1, 3);

   962     send_code(s, END_BLOCK, static_ltree);

   963 #ifdef DEBUG

   964     s->compressed_len += 10L; /* 3 for block type, 7 for EOB */

   965 #endif

   966     bi_flush(s);

   967     /* Of the 10 bits for the empty block, we have already sent

   968      * (10 - bi_valid) bits. The lookahead for the last real code (before

   969      * the EOB of the previous block) was thus at least one plus the length

   970      * of the EOB plus what we have just sent of the empty static block.

   971      */

   972     if (1 + s->last_eob_len + 10 - s->bi_valid < 9) {

   973         send_bits(s, STATIC_TREES<<1, 3);

   974         send_code(s, END_BLOCK, static_ltree);

   975 #ifdef DEBUG

   976         s->compressed_len += 10L;

   977 #endif

   978         bi_flush(s);

   979     }

   980     s->last_eob_len = 7;

   981 }

   982 

   983 /* ===========================================================================

   984  * Determine the best encoding for the current block: dynamic trees, static

   985  * trees or store, and output the encoded block to the zip file.

   986  */

   987 #ifdef __SYMBIAN32__

   988 void _tr_flush_block(  deflate_state * s,    charf *  buf,ulg  stored_len,int  eof)

   989 #else

   990 void _tr_flush_block(s, buf, stored_len, eof)

   991     deflate_state *s;

   992     charf *buf;       /* input block, or NULL if too old */

   993     ulg stored_len;   /* length of input block */

   994     int eof;          /* true if this is the last block for a file */

   995 #endif //__SYMBIAN32__	

   996 {

   997     ulg opt_lenb, static_lenb; /* opt_len and static_len in bytes */

   998     int max_blindex = 0;  /* index of last bit length code of non zero freq */

   999 

  1000     /* Build the Huffman trees unless a stored block is forced */

  1001     if (s->level > 0) {

  1002 

  1003         /* Check if the file is binary or text */

  1004         if (stored_len > 0 && s->strm->data_type == Z_UNKNOWN)

  1005             set_data_type(s);

  1006 

  1007         /* Construct the literal and distance trees */

  1008         build_tree(s, (tree_desc *)(&(s->l_desc)));

  1009         Tracev((stderr, "\nlit data: dyn %ld, stat %ld", s->opt_len,

  1010                 s->static_len));

  1011 

  1012         build_tree(s, (tree_desc *)(&(s->d_desc)));

  1013         Tracev((stderr, "\ndist data: dyn %ld, stat %ld", s->opt_len,

  1014                 s->static_len));

  1015         /* At this point, opt_len and static_len are the total bit lengths of

  1016          * the compressed block data, excluding the tree representations.

  1017          */

  1018 

  1019         /* Build the bit length tree for the above two trees, and get the index

  1020          * in bl_order of the last bit length code to send.

  1021          */

  1022         max_blindex = build_bl_tree(s);

  1023 

  1024         /* Determine the best encoding. Compute the block lengths in bytes. */

  1025         opt_lenb = (s->opt_len+3+7)>>3;

  1026         static_lenb = (s->static_len+3+7)>>3;

  1027 

  1028         Tracev((stderr, "\nopt %lu(%lu) stat %lu(%lu) stored %lu lit %u ",

  1029                 opt_lenb, s->opt_len, static_lenb, s->static_len, stored_len,

  1030                 s->last_lit));

  1031 

  1032         if (static_lenb <= opt_lenb) opt_lenb = static_lenb;

  1033 

  1034     } else {

  1035         Assert(buf != (char*)0, "lost buf");

  1036         opt_lenb = static_lenb = stored_len + 5; /* force a stored block */

  1037     }

  1038 

  1039 #ifdef FORCE_STORED

  1040     if (buf != (char*)0) { /* force stored block */

  1041 #else

  1042     if (stored_len+4 <= opt_lenb && buf != (char*)0) {

  1043                        /* 4: two words for the lengths */

  1044 #endif

  1045         /* The test buf != NULL is only necessary if LIT_BUFSIZE > WSIZE.

  1046          * Otherwise we can't have processed more than WSIZE input bytes since

  1047          * the last block flush, because compression would have been

  1048          * successful. If LIT_BUFSIZE <= WSIZE, it is never too late to

  1049          * transform a block into a stored block.

  1050          */

  1051         _tr_stored_block(s, buf, stored_len, eof);

  1052 

  1053 #ifdef FORCE_STATIC

  1054     } else if (static_lenb >= 0) { /* force static trees */

  1055 #else

  1056     } else if (s->strategy == Z_FIXED || static_lenb == opt_lenb) {

  1057 #endif

  1058         send_bits(s, (STATIC_TREES<<1)+eof, 3);

  1059         compress_block(s, (ct_data *)static_ltree, (ct_data *)static_dtree);

  1060 #ifdef DEBUG

  1061         s->compressed_len += 3 + s->static_len;

  1062 #endif

  1063     } else {

  1064         send_bits(s, (DYN_TREES<<1)+eof, 3);

  1065         send_all_trees(s, s->l_desc.max_code+1, s->d_desc.max_code+1,

  1066                        max_blindex+1);

  1067         compress_block(s, (ct_data *)s->dyn_ltree, (ct_data *)s->dyn_dtree);

  1068 #ifdef DEBUG

  1069         s->compressed_len += 3 + s->opt_len;

  1070 #endif

  1071     }

  1072     Assert (s->compressed_len == s->bits_sent, "bad compressed size");

  1073     /* The above check is made mod 2^32, for files larger than 512 MB

  1074      * and uLong implemented on 32 bits.

  1075      */

  1076     init_block(s);

  1077 

  1078     if (eof) {

  1079         bi_windup(s);

  1080 #ifdef DEBUG

  1081         s->compressed_len += 7;  /* align on byte boundary */

  1082 #endif

  1083     }

  1084     Tracev((stderr,"\ncomprlen %lu(%lu) ", s->compressed_len>>3,

  1085            s->compressed_len-7*eof));

  1086 }

  1087 

  1088 /* ===========================================================================

  1089  * Save the match info and tally the frequency counts. Return true if

  1090  * the current block must be flushed.

  1091  */

  1092 #ifndef SYMBIAN_EZLIB_DEVICE

  1093 

  1094 #ifdef __SYMBIAN32__

  1095 int _tr_tally (   deflate_state * s,unsigned  dist,unsigned  lc)

  1096 #else

  1097 int _tr_tally (s, dist, lc)

  1098     deflate_state *s;

  1099     unsigned dist;  /* distance of matched string */

  1100     unsigned lc;    /* match length-MIN_MATCH or unmatched char (if dist==0) */

  1101 #endif //__SYMBIAN32__

  1102 {

  1103     s->d_buf[s->last_lit] = (ush)dist;

  1104     s->l_buf[s->last_lit++] = (uch)lc;

  1105     if (dist == 0) {

  1106         /* lc is the unmatched char */

  1107         s->dyn_ltree[lc].Freq++;

  1108     } else {

  1109         s->matches++;

  1110         /* Here, lc is the match length - MIN_MATCH */

  1111         dist--;             /* dist = match distance - 1 */

  1112         Assert((ush)dist < (ush)MAX_DIST(s) &&

  1113                (ush)lc <= (ush)(MAX_MATCH-MIN_MATCH) &&

  1114                (ush)d_code(dist) < (ush)D_CODES,  "_tr_tally: bad match");

  1115 

  1116         s->dyn_ltree[_length_code[lc]+LITERALS+1].Freq++;

  1117         s->dyn_dtree[d_code(dist)].Freq++;

  1118     }

  1119 

  1120 #ifdef TRUNCATE_BLOCK

  1121     /* Try to guess if it is profitable to stop the current block here */

  1122     if ((s->last_lit & 0x1fff) == 0 && s->level > 2) {

  1123         /* Compute an upper bound for the compressed length */

  1124         ulg out_length = (ulg)s->last_lit*8L;

  1125         ulg in_length = (ulg)((long)s->strstart - s->block_start);

  1126         int dcode;

  1127         for (dcode = 0; dcode < D_CODES; dcode++) {

  1128             out_length += (ulg)s->dyn_dtree[dcode].Freq *

  1129                 (5L+extra_dbits[dcode]);

  1130         }

  1131         out_length >>= 3;

  1132         Tracev((stderr,"\nlast_lit %u, in %ld, out ~%ld(%ld%%) ",

  1133                s->last_lit, in_length, out_length,

  1134                100L - out_length*100L/in_length));