File Coverage

cpan/Compress-Raw-Zlib/trees.c
Criterion Covered Total %
statement 216 250 86.4
branch n/a
condition n/a
subroutine n/a
total 216 250 86.4


line stmt bran cond sub time code
1           /* trees.c -- output deflated data using Huffman coding
2           * Copyright (C) 1995-2012 Jean-loup Gailly
3           * detect_data_type() function provided freely by Cosmin Truta, 2006
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$ */
34            
35           /* #define GEN_TREES_H */
36            
37           #include "deflate.h"
38            
39           #ifdef DEBUG
40           # include
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           /* ===========================================================================
78           * Local data. These are initialized only once.
79           */
80            
81           #define DIST_CODE_LEN 512 /* see definition of array dist_code below */
82            
83           #if defined(GEN_TREES_H) || !defined(STDC)
84           /* non ANSI compilers may not accept trees.h */
85            
86           local ct_data static_ltree[L_CODES+2];
87           /* The static literal tree. Since the bit lengths are imposed, there is no
88           * need for the L_CODES extra codes used during heap construction. However
89           * The codes 286 and 287 are needed to build a canonical tree (see _tr_init
90           * below).
91           */
92            
93           local ct_data static_dtree[D_CODES];
94           /* The static distance tree. (Actually a trivial tree since all codes use
95           * 5 bits.)
96           */
97            
98           uch _dist_code[DIST_CODE_LEN];
99           /* Distance codes. The first 256 values correspond to the distances
100           * 3 .. 258, the last 256 values correspond to the top 8 bits of
101           * the 15 bit distances.
102           */
103            
104           uch _length_code[MAX_MATCH-MIN_MATCH+1];
105           /* length code for each normalized match length (0 == MIN_MATCH) */
106            
107           local int base_length[LENGTH_CODES];
108           /* First normalized length for each code (0 = MIN_MATCH) */
109            
110           local int base_dist[D_CODES];
111           /* First normalized distance for each code (0 = distance of 1) */
112            
113           #else
114           # include "trees.h"
115           #endif /* GEN_TREES_H */
116            
117           struct static_tree_desc_s {
118           const ct_data *static_tree; /* static tree or NULL */
119           const intf *extra_bits; /* extra bits for each code or NULL */
120           int extra_base; /* base index for extra_bits */
121           int elems; /* max number of elements in the tree */
122           int max_length; /* max bit length for the codes */
123           };
124            
125           local static_tree_desc static_l_desc =
126           {static_ltree, extra_lbits, LITERALS+1, L_CODES, MAX_BITS};
127            
128           local static_tree_desc static_d_desc =
129           {static_dtree, extra_dbits, 0, D_CODES, MAX_BITS};
130            
131           local static_tree_desc static_bl_desc =
132           {(const ct_data *)0, extra_blbits, 0, BL_CODES, MAX_BL_BITS};
133            
134           /* ===========================================================================
135           * Local (static) routines in this file.
136           */
137            
138           local void tr_static_init OF((void));
139           local void init_block OF((deflate_state *s));
140           local void pqdownheap OF((deflate_state *s, ct_data *tree, int k));
141           local void gen_bitlen OF((deflate_state *s, tree_desc *desc));
142           local void gen_codes OF((ct_data *tree, int max_code, ushf *bl_count));
143           local void build_tree OF((deflate_state *s, tree_desc *desc));
144           local void scan_tree OF((deflate_state *s, ct_data *tree, int max_code));
145           local void send_tree OF((deflate_state *s, ct_data *tree, int max_code));
146           local int build_bl_tree OF((deflate_state *s));
147           local void send_all_trees OF((deflate_state *s, int lcodes, int dcodes,
148           int blcodes));
149           local void compress_block OF((deflate_state *s, const ct_data *ltree,
150           const ct_data *dtree));
151           local int detect_data_type OF((deflate_state *s));
152           local unsigned bi_reverse OF((unsigned value, int length));
153           local void bi_windup OF((deflate_state *s));
154           local void bi_flush OF((deflate_state *s));
155           local void copy_block OF((deflate_state *s, charf *buf, unsigned len,
156           int header));
157            
158           #ifdef GEN_TREES_H
159           local void gen_trees_header OF((void));
160           #endif
161            
162           #ifndef DEBUG
163           # define send_code(s, c, tree) send_bits(s, tree[c].Code, tree[c].Len)
164           /* Send a code of the given tree. c and tree must not have side effects */
165            
166           #else /* DEBUG */
167           # define send_code(s, c, tree) \
168           { if (z_verbose>2) fprintf(stderr,"\ncd %3d ",(c)); \
169           send_bits(s, tree[c].Code, tree[c].Len); }
170           #endif
171            
172           /* ===========================================================================
173           * Output a short LSB first on the stream.
174           * IN assertion: there is enough room in pendingBuf.
175           */
176           #define put_short(s, w) { \
177           put_byte(s, (uch)((w) & 0xff)); \
178           put_byte(s, (uch)((ush)(w) >> 8)); \
179           }
180            
181           /* ===========================================================================
182           * Send a value on a given number of bits.
183           * IN assertion: length <= 16 and value fits in length bits.
184           */
185           #ifdef DEBUG
186           local void send_bits OF((deflate_state *s, int value, int length));
187            
188           local void send_bits(
189           deflate_state *s,
190           int value,
191           int length)
192           {
193           Tracevv((stderr," l %2d v %4x ", length, value));
194           Assert(length > 0 && length <= 15, "invalid length");
195           s->bits_sent += (ulg)length;
196            
197           /* If not enough room in bi_buf, use (valid) bits from bi_buf and
198           * (16 - bi_valid) bits from value, leaving (width - (16-bi_valid))
199           * unused bits in value.
200           */
201           if (s->bi_valid > (int)Buf_size - length) {
202           s->bi_buf |= (ush)value << s->bi_valid;
203           put_short(s, s->bi_buf);
204           s->bi_buf = (ush)value >> (Buf_size - s->bi_valid);
205           s->bi_valid += length - Buf_size;
206           } else {
207           s->bi_buf |= (ush)value << s->bi_valid;
208           s->bi_valid += length;
209           }
210           }
211           #else /* !DEBUG */
212            
213           #define send_bits(s, value, length) \
214           { int len = length;\
215           if (s->bi_valid > (int)Buf_size - len) {\
216           int val = value;\
217           s->bi_buf |= (ush)val << s->bi_valid;\
218           put_short(s, s->bi_buf);\
219           s->bi_buf = (ush)val >> (Buf_size - s->bi_valid);\
220           s->bi_valid += len - Buf_size;\
221           } else {\
222           s->bi_buf |= (ush)(value) << s->bi_valid;\
223           s->bi_valid += len;\
224           }\
225           }
226           #endif /* DEBUG */
227            
228            
229           /* the arguments must not have side effects */
230            
231           /* ===========================================================================
232           * Initialize the various 'constant' tables.
233           */
234           local void tr_static_init()
235           {
236           #if defined(GEN_TREES_H) || !defined(STDC)
237           static int static_init_done = 0;
238           int n; /* iterates over tree elements */
239           int bits; /* bit counter */
240           int length; /* length value */
241           int code; /* code value */
242           int dist; /* distance index */
243           ush bl_count[MAX_BITS+1];
244           /* number of codes at each bit length for an optimal tree */
245            
246           if (static_init_done) return;
247            
248           /* For some embedded targets, global variables are not initialized: */
249           #ifdef NO_INIT_GLOBAL_POINTERS
250           static_l_desc.static_tree = static_ltree;
251           static_l_desc.extra_bits = extra_lbits;
252           static_d_desc.static_tree = static_dtree;
253           static_d_desc.extra_bits = extra_dbits;
254           static_bl_desc.extra_bits = extra_blbits;
255           #endif
256            
257           /* Initialize the mapping length (0..255) -> length code (0..28) */
258           length = 0;
259           for (code = 0; code < LENGTH_CODES-1; code++) {
260           base_length[code] = length;
261           for (n = 0; n < (1<
262           _length_code[length++] = (uch)code;
263           }
264           }
265           Assert (length == 256, "tr_static_init: length != 256");
266           /* Note that the length 255 (match length 258) can be represented
267           * in two different ways: code 284 + 5 bits or code 285, so we
268           * overwrite length_code[255] to use the best encoding:
269           */
270           _length_code[length-1] = (uch)code;
271            
272           /* Initialize the mapping dist (0..32K) -> dist code (0..29) */
273           dist = 0;
274           for (code = 0 ; code < 16; code++) {
275           base_dist[code] = dist;
276           for (n = 0; n < (1<
277           _dist_code[dist++] = (uch)code;
278           }
279           }
280           Assert (dist == 256, "tr_static_init: dist != 256");
281           dist >>= 7; /* from now on, all distances are divided by 128 */
282           for ( ; code < D_CODES; code++) {
283           base_dist[code] = dist << 7;
284           for (n = 0; n < (1<<(extra_dbits[code]-7)); n++) {
285           _dist_code[256 + dist++] = (uch)code;
286           }
287           }
288           Assert (dist == 256, "tr_static_init: 256+dist != 512");
289            
290           /* Construct the codes of the static literal tree */
291           for (bits = 0; bits <= MAX_BITS; bits++) bl_count[bits] = 0;
292           n = 0;
293           while (n <= 143) static_ltree[n++].Len = 8, bl_count[8]++;
294           while (n <= 255) static_ltree[n++].Len = 9, bl_count[9]++;
295           while (n <= 279) static_ltree[n++].Len = 7, bl_count[7]++;
296           while (n <= 287) static_ltree[n++].Len = 8, bl_count[8]++;
297           /* Codes 286 and 287 do not exist, but we must include them in the
298           * tree construction to get a canonical Huffman tree (longest code
299           * all ones)
300           */
301           gen_codes((ct_data *)static_ltree, L_CODES+1, bl_count);
302            
303           /* The static distance tree is trivial: */
304           for (n = 0; n < D_CODES; n++) {
305           static_dtree[n].Len = 5;
306           static_dtree[n].Code = bi_reverse((unsigned)n, 5);
307           }
308           static_init_done = 1;
309            
310           # ifdef GEN_TREES_H
311           gen_trees_header();
312           # endif
313           #endif /* defined(GEN_TREES_H) || !defined(STDC) */
314           }
315            
316           /* ===========================================================================
317           * Genererate the file trees.h describing the static trees.
318           */
319           #ifdef GEN_TREES_H
320           # ifndef DEBUG
321           # include
322           # endif
323            
324           # define SEPARATOR(i, last, width) \
325           ((i) == (last)? "\n};\n\n" : \
326           ((i) % (width) == (width)-1 ? ",\n" : ", "))
327            
328           void gen_trees_header()
329           {
330           FILE *header = fopen("trees.h", "w");
331           int i;
332            
333           Assert (header != NULL, "Can't open trees.h");
334           fprintf(header,
335           "/* header created automatically with -DGEN_TREES_H */\n\n");
336            
337           fprintf(header, "local const ct_data static_ltree[L_CODES+2] = {\n");
338           for (i = 0; i < L_CODES+2; i++) {
339           fprintf(header, "{{%3u},{%3u}}%s", static_ltree[i].Code,
340           static_ltree[i].Len, SEPARATOR(i, L_CODES+1, 5));
341           }
342            
343           fprintf(header, "local const ct_data static_dtree[D_CODES] = {\n");
344           for (i = 0; i < D_CODES; i++) {
345           fprintf(header, "{{%2u},{%2u}}%s", static_dtree[i].Code,
346           static_dtree[i].Len, SEPARATOR(i, D_CODES-1, 5));
347           }
348            
349           fprintf(header, "const uch ZLIB_INTERNAL _dist_code[DIST_CODE_LEN] = {\n");
350           for (i = 0; i < DIST_CODE_LEN; i++) {
351           fprintf(header, "%2u%s", _dist_code[i],
352           SEPARATOR(i, DIST_CODE_LEN-1, 20));
353           }
354            
355           fprintf(header,
356           "const uch ZLIB_INTERNAL _length_code[MAX_MATCH-MIN_MATCH+1]= {\n");
357           for (i = 0; i < MAX_MATCH-MIN_MATCH+1; i++) {
358           fprintf(header, "%2u%s", _length_code[i],
359           SEPARATOR(i, MAX_MATCH-MIN_MATCH, 20));
360           }
361            
362           fprintf(header, "local const int base_length[LENGTH_CODES] = {\n");
363           for (i = 0; i < LENGTH_CODES; i++) {
364           fprintf(header, "%1u%s", base_length[i],
365           SEPARATOR(i, LENGTH_CODES-1, 20));
366           }
367            
368           fprintf(header, "local const int base_dist[D_CODES] = {\n");
369           for (i = 0; i < D_CODES; i++) {
370           fprintf(header, "%5u%s", base_dist[i],
371           SEPARATOR(i, D_CODES-1, 10));
372           }
373            
374           fclose(header);
375           }
376           #endif /* GEN_TREES_H */
377            
378           /* ===========================================================================
379           * Initialize the tree data structures for a new zlib stream.
380           */
381 3050         void ZLIB_INTERNAL _tr_init(
382           deflate_state *s)
383           {
384           tr_static_init();
385            
386 3050         s->l_desc.dyn_tree = s->dyn_ltree;
387 3050         s->l_desc.stat_desc = &static_l_desc;
388            
389 3050         s->d_desc.dyn_tree = s->dyn_dtree;
390 3050         s->d_desc.stat_desc = &static_d_desc;
391            
392 3050         s->bl_desc.dyn_tree = s->bl_tree;
393 3050         s->bl_desc.stat_desc = &static_bl_desc;
394            
395 3050         s->bi_buf = 0;
396 3050         s->bi_valid = 0;
397           #ifdef DEBUG
398           s->compressed_len = 0L;
399           s->bits_sent = 0L;
400           #endif
401            
402           /* Initialize the first block of the first file: */
403           init_block(s);
404 3050         }
405            
406           /* ===========================================================================
407           * Initialize a new block.
408           */
409           local void init_block(
410           deflate_state *s)
411           {
412           int n; /* iterates over tree elements */
413            
414           /* Initialize the trees. */
415 1750320         for (n = 0; n < L_CODES; n++) s->dyn_ltree[n].Freq = 0;
416 183600         for (n = 0; n < D_CODES; n++) s->dyn_dtree[n].Freq = 0;
417 116280         for (n = 0; n < BL_CODES; n++) s->bl_tree[n].Freq = 0;
418            
419 6120         s->dyn_ltree[END_BLOCK].Freq = 1;
420 6120         s->opt_len = s->static_len = 0L;
421 6120         s->last_lit = s->matches = 0;
422           }
423            
424           #define SMALLEST 1
425           /* Index within the heap array of least frequent node in the Huffman tree */
426            
427            
428           /* ===========================================================================
429           * Remove the smallest element from the heap and recreate the heap with
430           * one less element. Updates heap and heap_len.
431           */
432           #define pqremove(s, tree, top) \
433           {\
434           top = s->heap[SMALLEST]; \
435           s->heap[SMALLEST] = s->heap[s->heap_len--]; \
436           pqdownheap(s, tree, SMALLEST); \
437           }
438            
439           /* ===========================================================================
440           * Compares to subtrees, using the tree depth as tie breaker when
441           * the subtrees have equal frequency. This minimizes the worst case length.
442           */
443           #define smaller(tree, n, m, depth) \
444           (tree[n].Freq < tree[m].Freq || \
445           (tree[n].Freq == tree[m].Freq && depth[n] <= depth[m]))
446            
447           /* ===========================================================================
448           * Restore the heap property by moving down the tree starting at node k,
449           * exchanging a node with the smallest of its two sons if necessary, stopping
450           * when the heap property is re-established (each father smaller than its
451           * two sons).
452           */
453 137104         local void pqdownheap(
454           deflate_state *s,
455           ct_data *tree,
456           int k)
457           {
458 137104         int v = s->heap[k];
459 137104         int j = k << 1; /* left son of k */
460 517050         while (j <= s->heap_len) {
461           /* Set j to the smallest of the two sons: */
462 541284         if (j < s->heap_len &&
463 461528         smaller(tree, s->heap[j+1], s->heap[j], s->depth)) {
464 127604         j++;
465           }
466           /* Exit if v is smaller than both sons */
467 284378         if (smaller(tree, v, s->heap[j], s->depth)) break;
468            
469           /* Exchange v with the smallest son */
470 242842         s->heap[k] = s->heap[j]; k = j;
471            
472           /* And continue down the tree, setting j to the left son of k */
473 242842         j <<= 1;
474           }
475 137104         s->heap[k] = v;
476 137104         }
477            
478           /* ===========================================================================
479           * Compute the optimal bit lengths for a tree and update the total bit length
480           * for the current block.
481           * IN assertion: the fields freq and dad are set, heap[heap_max] and
482           * above are the tree nodes sorted by increasing frequency.
483           * OUT assertions: the field len is set to the optimal bit length, the
484           * array bl_count contains the frequencies for each bit length.
485           * The length opt_len is updated; static_len is also updated if stree is
486           * not null.
487           */
488 9162         local void gen_bitlen(
489           deflate_state *s,
490           tree_desc *desc)
491           {
492 9162         ct_data *tree = desc->dyn_tree;
493 9162         int max_code = desc->max_code;
494 9162         const ct_data *stree = desc->stat_desc->static_tree;
495 9162         const intf *extra = desc->stat_desc->extra_bits;
496 9162         int base = desc->stat_desc->extra_base;
497 9162         int max_length = desc->stat_desc->max_length;
498           int h; /* heap index */
499           int n, m; /* iterate over the tree elements */
500           int bits; /* bit length */
501           int xbits; /* extra bits */
502           ush f; /* frequency */
503           int overflow = 0; /* number of elements with bit length too large */
504            
505 9162         for (bits = 0; bits <= MAX_BITS; bits++) s->bl_count[bits] = 0;
506            
507           /* In a first pass, compute the optimal bit lengths (which may
508           * overflow in the case of the bit length tree).
509           */
510 9162         tree[s->heap[s->heap_max]].Len = 0; /* root of the heap */
511            
512 116166         for (h = s->heap_max+1; h < HEAP_SIZE; h++) {
513 107004         n = s->heap[h];
514 107004         bits = tree[tree[n].Dad].Len + 1;
515 107004         if (bits > max_length) bits = max_length, overflow++;
516 107004         tree[n].Len = (ush)bits;
517           /* We overwrite tree[n].Dad which is no longer needed */
518            
519 107004         if (n > max_code) continue; /* not a leaf node */
520            
521 62664         s->bl_count[bits]++;
522           xbits = 0;
523 62664         if (n >= base) xbits = extra[n-base];
524 62664         f = tree[n].Freq;
525 62664         s->opt_len += (ulg)f * (bits + xbits);
526 62664         if (stree) s->static_len += (ulg)f * (stree[n].Len + xbits);
527           }
528 18324         if (overflow == 0) return;
529            
530           Trace((stderr,"\nbit length overflow\n"));
531           /* This happens for example on obj2 and pic of the Calgary corpus */
532            
533           /* Find the first bit length which could increase: */
534           do {
535 0         bits = max_length-1;
536 0         while (s->bl_count[bits] == 0) bits--;
537 0         s->bl_count[bits]--; /* move one leaf down the tree */
538 0         s->bl_count[bits+1] += 2; /* move one overflow item as its brother */
539 0         s->bl_count[max_length]--;
540           /* The brother of the overflow item also moves one step up,
541           * but this does not affect bl_count[max_length]
542           */
543 0         overflow -= 2;
544 0         } while (overflow > 0);
545            
546           /* Now recompute all bit lengths, scanning in increasing frequency.
547           * h is still equal to HEAP_SIZE. (It is simpler to reconstruct all
548           * lengths instead of fixing only the wrong ones. This idea is taken
549           * from 'ar' written by Haruhiko Okumura.)
550           */
551 0         for (bits = max_length; bits != 0; bits--) {
552 0         n = s->bl_count[bits];
553 0         while (n != 0) {
554 0         m = s->heap[--h];
555 0         if (m > max_code) continue;
556 0         if ((unsigned) tree[m].Len != (unsigned) bits) {
557           Trace((stderr,"code %d bits %d->%d\n", m, tree[m].Len, bits));
558 0         s->opt_len += ((long)bits - (long)tree[m].Len)
559 0         *(long)tree[m].Freq;
560 0         tree[m].Len = (ush)bits;
561           }
562 0         n--;
563           }
564           }
565           }
566            
567           /* ===========================================================================
568           * Generate the codes for a given tree and bit counts (which need not be
569           * optimal).
570           * IN assertion: the array bl_count contains the bit length statistics for
571           * the given tree and the field len is set for all tree elements.
572           * OUT assertion: the field code is set for all tree elements of non
573           * zero code length.
574           */
575           local void gen_codes (
576           ct_data *tree,
577           int max_code,
578           ushf *bl_count)
579           {
580           ush next_code[MAX_BITS+1]; /* next code value for each bit length */
581           ush code = 0; /* running code value */
582           int bits; /* bit index */
583           int n; /* code index */
584            
585           /* The distribution counts are first used to generate the code values
586           * without bit reversal.
587           */
588 137430         for (bits = 1; bits <= MAX_BITS; bits++) {
589 137430         next_code[bits] = code = (code + bl_count[bits-1]) << 1;
590           }
591           /* Check that the bit counts in bl_count are consistent. The last code
592           * must be all ones.
593           */
594           Assert (code + bl_count[MAX_BITS]-1 == (1<
595           "inconsistent bit counts");
596           Tracev((stderr,"\ngen_codes: max_code %d ", max_code));
597            
598 868760         for (n = 0; n <= max_code; n++) {
599 868760         int len = tree[n].Len;
600 868760         if (len == 0) continue;
601           /* Now reverse the bits */
602 125328         tree[n].Code = bi_reverse(next_code[len]++, len);
603            
604           Tracecv(tree != static_ltree, (stderr,"\nn %3d %c l %2d c %4x (%x) ",
605           n, (isgraph(n) ? n : ' '), len, tree[n].Code, next_code[len]-1));
606           }
607           }
608            
609           /* ===========================================================================
610           * Construct one Huffman tree and assigns the code bit strings and lengths.
611           * Update the total bit length for the current block.
612           * IN assertion: the field freq is set for all tree elements.
613           * OUT assertions: the fields len and code are set to the optimal bit length
614           * and corresponding code. The length opt_len is updated; static_len is
615           * also updated if stree is not null. The field max_code is set.
616           */
617 9162         local void build_tree(
618           deflate_state *s,
619           tree_desc *desc)
620           {
621 9162         ct_data *tree = desc->dyn_tree;
622 9162         const ct_data *stree = desc->stat_desc->static_tree;
623 9162         int elems = desc->stat_desc->elems;
624           int n, m; /* iterate over heap elements */
625           int max_code = -1; /* largest code with non zero frequency */
626           int node; /* new node being created */
627            
628           /* Construct the initial heap, with least frequent element in
629           * heap[SMALLEST]. The sons of heap[n] are heap[2*n] and heap[2*n+1].
630           * heap[0] is not used.
631           */
632 9162         s->heap_len = 0, s->heap_max = HEAP_SIZE;
633            
634 1032252         for (n = 0; n < elems; n++) {
635 1023090         if (tree[n].Freq != 0) {
636 57060         s->heap[++(s->heap_len)] = max_code = n;
637 57060         s->depth[n] = 0;
638           } else {
639 966030         tree[n].Len = 0;
640           }
641           }
642            
643           /* The pkzip format requires that at least one distance code exists,
644           * and that at least one bit should be sent even if there is only one
645           * possible code. So to avoid special checks later on we force at least
646           * two codes of non zero frequency.
647           */
648 14766         while (s->heap_len < 2) {
649 5604         node = s->heap[++(s->heap_len)] = (max_code < 2 ? ++max_code : 0);
650 5604         tree[node].Freq = 1;
651 5604         s->depth[node] = 0;
652 5604         s->opt_len--; if (stree) s->static_len -= stree[node].Len;
653           /* node is 0 or 1 so it does not have extra bits */
654           }
655 9162         desc->max_code = max_code;
656            
657           /* The elements heap[heap_len/2+1 .. heap_len] are leaves of the tree,
658           * establish sub-heaps of increasing lengths:
659           */
660 9162         for (n = s->heap_len/2; n >= 1; n--) pqdownheap(s, tree, n);
661            
662           /* Construct the Huffman tree by repeatedly combining the least two
663           * frequent nodes.
664           */
665           node = elems; /* next internal node of the tree */
666           do {
667 53502         pqremove(s, tree, n); /* n = node of least frequency */
668 53502         m = s->heap[SMALLEST]; /* m = node of next least frequency */
669            
670 53502         s->heap[--(s->heap_max)] = n; /* keep the nodes sorted by frequency */
671 53502         s->heap[--(s->heap_max)] = m;
672            
673           /* Create a new node father of n and m */
674 53502         tree[node].Freq = tree[n].Freq + tree[m].Freq;
675 107004         s->depth[node] = (uch)((s->depth[n] >= s->depth[m] ?
676 53502         s->depth[n] : s->depth[m]) + 1);
677 53502         tree[n].Dad = tree[m].Dad = (ush)node;
678           #ifdef DUMP_BL_TREE
679           if (tree == s->bl_tree) {
680           fprintf(stderr,"\nnode %d(%d), sons %d(%d) %d(%d)",
681           node, tree[node].Freq, n, tree[n].Freq, m, tree[m].Freq);
682           }
683           #endif
684           /* and insert the new node in the heap */
685 53502         s->heap[SMALLEST] = node++;
686 53502         pqdownheap(s, tree, SMALLEST);
687            
688 53502         } while (s->heap_len >= 2);
689            
690 9162         s->heap[--(s->heap_max)] = s->heap[SMALLEST];
691            
692           /* At this point, the fields freq and dad are set. We can now
693           * generate the bit lengths.
694           */
695 9162         gen_bitlen(s, (tree_desc *)desc);
696            
697           /* The field len is now set, we can generate the bit codes */
698           gen_codes ((ct_data *)tree, max_code, s->bl_count);
699 9162         }
700            
701           /* ===========================================================================
702           * Scan a literal or distance tree to determine the frequencies of the codes
703           * in the bit length tree.
704           */
705 6108         local void scan_tree (
706           deflate_state *s,
707           ct_data *tree,
708           int max_code)
709           {
710           int n; /* iterates over all tree elements */
711           int prevlen = -1; /* last emitted length */
712           int curlen; /* length of current code */
713 6108         int nextlen = tree[0].Len; /* length of next code */
714           int count = 0; /* repeat count of the current code */
715           int max_count = 7; /* max repeat count */
716           int min_count = 4; /* min repeat count */
717            
718 6108         if (nextlen == 0) max_count = 138, min_count = 3;
719 6108         tree[max_code+1].Len = (ush)0xffff; /* guard */
720            
721 816888         for (n = 0; n <= max_code; n++) {
722 810780         curlen = nextlen; nextlen = tree[n+1].Len;
723 810780         if (++count < max_count && curlen == nextlen) {
724 756324         continue;
725 54456         } else if (count < min_count) {
726 38068         s->bl_tree[curlen].Freq += count;
727 16388         } else if (curlen != 0) {
728 1450         if (curlen != prevlen) s->bl_tree[curlen].Freq++;
729 1450         s->bl_tree[REP_3_6].Freq++;
730 14938         } else if (count <= 10) {
731 4910         s->bl_tree[REPZ_3_10].Freq++;
732           } else {
733 10028         s->bl_tree[REPZ_11_138].Freq++;
734           }
735           count = 0; prevlen = curlen;
736 54456         if (nextlen == 0) {
737           max_count = 138, min_count = 3;
738 35818         } else if (curlen == nextlen) {
739           max_count = 6, min_count = 3;
740           } else {
741           max_count = 7, min_count = 4;
742           }
743           }
744 6108         }
745            
746           /* ===========================================================================
747           * Send a literal or distance tree in compressed form, using the codes in
748           * bl_tree.
749           */
750 916         local void send_tree (
751           deflate_state *s,
752           ct_data *tree,
753           int max_code)
754           {
755           int n; /* iterates over all tree elements */
756           int prevlen = -1; /* last emitted length */
757           int curlen; /* length of current code */
758 916         int nextlen = tree[0].Len; /* length of next code */
759           int count = 0; /* repeat count of the current code */
760           int max_count = 7; /* max repeat count */
761           int min_count = 4; /* min repeat count */
762            
763           /* tree[max_code+1].Len = -1; */ /* guard already set */
764 916         if (nextlen == 0) max_count = 138, min_count = 3;
765            
766 133272         for (n = 0; n <= max_code; n++) {
767 133272         curlen = nextlen; nextlen = tree[n+1].Len;
768 133272         if (++count < max_count && curlen == nextlen) {
769 116266         continue;
770 17006         } else if (count < min_count) {
771 16246         do { send_code(s, curlen, s->bl_tree); } while (--count != 0);
772            
773 3900         } else if (curlen != 0) {
774 98         if (curlen != prevlen) {
775 98         send_code(s, curlen, s->bl_tree); count--;
776           }
777           Assert(count >= 3 && count <= 6, " 3_6?");
778 98         send_code(s, REP_3_6, s->bl_tree); send_bits(s, count-3, 2);
779            
780 3802         } else if (count <= 10) {
781 1478         send_code(s, REPZ_3_10, s->bl_tree); send_bits(s, count-3, 3);
782            
783           } else {
784 2324         send_code(s, REPZ_11_138, s->bl_tree); send_bits(s, count-11, 7);
785           }
786           count = 0; prevlen = curlen;
787 17006         if (nextlen == 0) {
788           max_count = 138, min_count = 3;
789 11574         } else if (curlen == nextlen) {
790           max_count = 6, min_count = 3;
791           } else {
792           max_count = 7, min_count = 4;
793           }
794           }
795 916         }
796            
797           /* ===========================================================================
798           * Construct the Huffman tree for the bit lengths and return the index in
799           * bl_order of the last bit length code to send.
800           */
801           local int build_bl_tree(
802           deflate_state *s)
803           {
804           int max_blindex; /* index of last bit length code of non zero freq */
805            
806           /* Determine the bit length frequencies for literal and distance trees */
807 3054         scan_tree(s, (ct_data *)s->dyn_ltree, s->l_desc.max_code);
808 3054         scan_tree(s, (ct_data *)s->dyn_dtree, s->d_desc.max_code);
809            
810           /* Build the bit length tree: */
811 3054         build_tree(s, (tree_desc *)(&(s->bl_desc)));
812           /* opt_len now includes the length of the tree representations, except
813           * the lengths of the bit lengths codes and the 5+5+4 bits for the counts.
814           */
815            
816           /* Determine the number of bit length codes to send. The pkzip format
817           * requires that at least 4 bit length codes be sent. (appnote.txt says
818           * 3 but the actual value used is 4.)
819           */
820 3134         for (max_blindex = BL_CODES-1; max_blindex >= 3; max_blindex--) {
821 6188         if (s->bl_tree[bl_order[max_blindex]].Len != 0) break;
822           }
823           /* Update opt_len to include the bit length tree and counts */
824 3054         s->opt_len += 3*(max_blindex+1) + 5+5+4;
825           Tracev((stderr, "\ndyn trees: dyn %ld, stat %ld",
826           s->opt_len, s->static_len));
827            
828           return max_blindex;
829           }
830            
831           /* ===========================================================================
832           * Send the header for a block using dynamic Huffman trees: the counts, the
833           * lengths of the bit length codes, the literal tree and the distance tree.
834           * IN assertion: lcodes >= 257, dcodes >= 1, blcodes >= 4.
835           */
836 458         local void send_all_trees(
837           deflate_state *s,
838           int lcodes,
839           int dcodes,
840           int blcodes)
841           {
842           int rank; /* index in bl_order */
843            
844           Assert (lcodes >= 257 && dcodes >= 1 && blcodes >= 4, "not enough codes");
845           Assert (lcodes <= L_CODES && dcodes <= D_CODES && blcodes <= BL_CODES,
846           "too many codes");
847           Tracev((stderr, "\nbl counts: "));
848 458         send_bits(s, lcodes-257, 5); /* not +255 as stated in appnote.txt */
849 458         send_bits(s, dcodes-1, 5);
850 458         send_bits(s, blcodes-4, 4); /* not -3 as stated in appnote.txt */
851 8176         for (rank = 0; rank < blcodes; rank++) {
852           Tracev((stderr, "\nbl code %2d ", bl_order[rank]));
853 8176         send_bits(s, s->bl_tree[bl_order[rank]].Len, 3);
854           }
855           Tracev((stderr, "\nbl tree: sent %ld", s->bits_sent));
856            
857 458         send_tree(s, (ct_data *)s->dyn_ltree, lcodes-1); /* literal tree */
858           Tracev((stderr, "\nlit tree: sent %ld", s->bits_sent));
859            
860 458         send_tree(s, (ct_data *)s->dyn_dtree, dcodes-1); /* distance tree */
861           Tracev((stderr, "\ndist tree: sent %ld", s->bits_sent));
862 458         }
863            
864           /* ===========================================================================
865           * Send a stored block
866           */
867 72         void ZLIB_INTERNAL _tr_stored_block(
868           deflate_state *s,
869           charf *buf,
870           ulg stored_len,
871           int last)
872           {
873 72         send_bits(s, (STORED_BLOCK<<1)+last, 3); /* send block type */
874           #ifdef DEBUG
875           s->compressed_len = (s->compressed_len + 3 + 7) & (ulg)~7L;
876           s->compressed_len += (stored_len + 4) << 3;
877           #endif
878 72         copy_block(s, buf, (unsigned)stored_len, 1); /* with header */
879 72         }
880            
881           /* ===========================================================================
882           * Flush the bits in the bit buffer to pending output (leaves at most 7 bits)
883           */
884 3966         void ZLIB_INTERNAL _tr_flush_bits(
885           deflate_state *s)
886           {
887           bi_flush(s);
888 3966         }
889            
890           /* ===========================================================================
891           * Send one empty static block to give enough lookahead for inflate.
892           * This takes 10 bits, of which 7 may remain in the bit buffer.
893           */
894 0         void ZLIB_INTERNAL _tr_align(
895           deflate_state *s)
896           {
897 0         send_bits(s, STATIC_TREES<<1, 3);
898 0         send_code(s, END_BLOCK, static_ltree);
899           #ifdef DEBUG
900           s->compressed_len += 10L; /* 3 for block type, 7 for EOB */
901           #endif
902           bi_flush(s);
903 0         }
904            
905           /* ===========================================================================
906           * Determine the best encoding for the current block: dynamic trees, static
907           * trees or store, and output the encoded block to the zip file.
908           */
909 3070         void ZLIB_INTERNAL _tr_flush_block(
910           deflate_state *s,
911           charf *buf,
912           ulg stored_len,
913           int last)
914           {
915           ulg opt_lenb, static_lenb; /* opt_len and static_len in bytes */
916           int max_blindex = 0; /* index of last bit length code of non zero freq */
917            
918           /* Build the Huffman trees unless a stored block is forced */
919 3070         if (s->level > 0) {
920            
921           /* Check if the file is binary or text */
922 3054         if (s->strm->data_type == Z_UNKNOWN)
923 6052         s->strm->data_type = detect_data_type(s);
924            
925           /* Construct the literal and distance trees */
926 3054         build_tree(s, (tree_desc *)(&(s->l_desc)));
927           Tracev((stderr, "\nlit data: dyn %ld, stat %ld", s->opt_len,
928           s->static_len));
929            
930 3054         build_tree(s, (tree_desc *)(&(s->d_desc)));
931           Tracev((stderr, "\ndist data: dyn %ld, stat %ld", s->opt_len,
932           s->static_len));
933           /* At this point, opt_len and static_len are the total bit lengths of
934           * the compressed block data, excluding the tree representations.
935           */
936            
937           /* Build the bit length tree for the above two trees, and get the index
938           * in bl_order of the last bit length code to send.
939           */
940           max_blindex = build_bl_tree(s);
941            
942           /* Determine the best encoding. Compute the block lengths in bytes. */
943 3054         opt_lenb = (s->opt_len+3+7)>>3;
944 3054         static_lenb = (s->static_len+3+7)>>3;
945            
946           Tracev((stderr, "\nopt %lu(%lu) stat %lu(%lu) stored %lu lit %u ",
947           opt_lenb, s->opt_len, static_lenb, s->static_len, stored_len,
948           s->last_lit));
949            
950 3054         if (static_lenb <= opt_lenb) opt_lenb = static_lenb;
951            
952           } else {
953           Assert(buf != (char*)0, "lost buf");
954 16         opt_lenb = static_lenb = stored_len + 5; /* force a stored block */
955           }
956            
957           #ifdef FORCE_STORED
958           if (buf != (char*)0) { /* force stored block */
959           #else
960 3070         if (stored_len+4 <= opt_lenb && buf != (char*)0) {
961           /* 4: two words for the lengths */
962           #endif
963           /* The test buf != NULL is only necessary if LIT_BUFSIZE > WSIZE.
964           * Otherwise we can't have processed more than WSIZE input bytes since
965           * the last block flush, because compression would have been
966           * successful. If LIT_BUFSIZE <= WSIZE, it is never too late to
967           * transform a block into a stored block.
968           */
969 48         _tr_stored_block(s, buf, stored_len, last);
970            
971           #ifdef FORCE_STATIC
972           } else if (static_lenb >= 0) { /* force static trees */
973           #else
974 3022         } else if (s->strategy == Z_FIXED || static_lenb == opt_lenb) {
975           #endif
976 2564         send_bits(s, (STATIC_TREES<<1)+last, 3);
977 2564         compress_block(s, (const ct_data *)static_ltree,
978           (const ct_data *)static_dtree);
979           #ifdef DEBUG
980           s->compressed_len += 3 + s->static_len;
981           #endif
982           } else {
983 458         send_bits(s, (DYN_TREES<<1)+last, 3);
984 458         send_all_trees(s, s->l_desc.max_code+1, s->d_desc.max_code+1,
985           max_blindex+1);
986 458         compress_block(s, (const ct_data *)s->dyn_ltree,
987 458         (const ct_data *)s->dyn_dtree);
988           #ifdef DEBUG
989           s->compressed_len += 3 + s->opt_len;
990           #endif
991           }
992           Assert (s->compressed_len == s->bits_sent, "bad compressed size");
993           /* The above check is made mod 2^32, for files larger than 512 MB
994           * and uLong implemented on 32 bits.
995           */
996           init_block(s);
997            
998 3070         if (last) {
999           bi_windup(s);
1000           #ifdef DEBUG
1001           s->compressed_len += 7; /* align on byte boundary */
1002           #endif
1003           }
1004           Tracev((stderr,"\ncomprlen %lu(%lu) ", s->compressed_len>>3,
1005           s->compressed_len-7*last));
1006 3070         }
1007            
1008           /* ===========================================================================
1009           * Save the match info and tally the frequency counts. Return true if
1010           * the current block must be flushed.
1011           */
1012 0         int ZLIB_INTERNAL _tr_tally (
1013           deflate_state *s,
1014           unsigned dist,
1015           unsigned lc)
1016           {
1017 0         s->d_buf[s->last_lit] = (ush)dist;
1018 0         s->l_buf[s->last_lit++] = (uch)lc;
1019 0         if (dist == 0) {
1020           /* lc is the unmatched char */
1021 0         s->dyn_ltree[lc].Freq++;
1022           } else {
1023 0         s->matches++;
1024           /* Here, lc is the match length - MIN_MATCH */
1025 0         dist--; /* dist = match distance - 1 */
1026           Assert((ush)dist < (ush)MAX_DIST(s) &&
1027           (ush)lc <= (ush)(MAX_MATCH-MIN_MATCH) &&
1028           (ush)d_code(dist) < (ush)D_CODES, "_tr_tally: bad match");
1029            
1030 0         s->dyn_ltree[_length_code[lc]+LITERALS+1].Freq++;
1031 0         s->dyn_dtree[d_code(dist)].Freq++;
1032           }
1033            
1034           #ifdef TRUNCATE_BLOCK
1035           /* Try to guess if it is profitable to stop the current block here */
1036           if ((s->last_lit & 0x1fff) == 0 && s->level > 2) {
1037           /* Compute an upper bound for the compressed length */
1038           ulg out_length = (ulg)s->last_lit*8L;
1039           ulg in_length = (ulg)((long)s->strstart - s->block_start);
1040           int dcode;
1041           for (dcode = 0; dcode < D_CODES; dcode++) {
1042           out_length += (ulg)s->dyn_dtree[dcode].Freq *
1043           (5L+extra_dbits[dcode]);
1044           }
1045           out_length >>= 3;
1046           Tracev((stderr,"\nlast_lit %u, in %ld, out ~%ld(%ld%%) ",
1047           s->last_lit, in_length, out_length,
1048           100L - out_length*100L/in_length));
1049           if (s->matches < s->last_lit/2 && out_length < in_length/2) return 1;
1050           }
1051           #endif
1052 0         return (s->last_lit == s->lit_bufsize-1);
1053           /* We avoid equality with lit_bufsize because of wraparound at 64K
1054           * on 16 bit machines and because stored blocks are restricted to
1055           * 64K-1 bytes.
1056           */
1057           }
1058            
1059           /* ===========================================================================
1060           * Send the block data compressed using the given Huffman trees
1061           */
1062 3022         local void compress_block(
1063           deflate_state *s,
1064           const ct_data *ltree,
1065           const ct_data *dtree)
1066           {
1067           unsigned dist; /* distance of matched string */
1068           int lc; /* match length or unmatched char (if dist == 0) */
1069           unsigned lx = 0; /* running index in l_buf */
1070           unsigned code; /* the code to send */
1071           int extra; /* number of extra bits to send */
1072            
1073 3022         if (s->last_lit != 0) do {
1074 464838         dist = s->d_buf[lx];
1075 464838         lc = s->l_buf[lx++];
1076 464838         if (dist == 0) {
1077 393622         send_code(s, lc, ltree); /* send a literal byte */
1078           Tracecv(isgraph(lc), (stderr," '%c' ", lc));
1079           } else {
1080           /* Here, lc is the match length - MIN_MATCH */
1081 71216         code = _length_code[lc];
1082 71216         send_code(s, code+LITERALS+1, ltree); /* send the length code */
1083 71216         extra = extra_lbits[code];
1084 71216         if (extra != 0) {
1085 6720         lc -= base_length[code];
1086 6720         send_bits(s, lc, extra); /* send the extra length bits */
1087           }
1088 71216         dist--; /* dist is now the match distance - 1 */
1089 71216         code = d_code(dist);
1090           Assert (code < D_CODES, "bad d_code");
1091            
1092 71216         send_code(s, code, dtree); /* send the distance code */
1093 71216         extra = extra_dbits[code];
1094 71216         if (extra != 0) {
1095 69888         dist -= base_dist[code];
1096 69888         send_bits(s, dist, extra); /* send the extra distance bits */
1097           }
1098           } /* literal or match pair ? */
1099            
1100           /* Check that the overlay between pending_buf and d_buf+l_buf is ok: */
1101           Assert((uInt)(s->pending) < s->lit_bufsize + 2*lx,
1102           "pendingBuf overflow");
1103            
1104 464838         } while (lx < s->last_lit);
1105            
1106 3022         send_code(s, END_BLOCK, ltree);
1107 3022         }
1108            
1109           /* ===========================================================================
1110           * Check if the data type is TEXT or BINARY, using the following algorithm:
1111           * - TEXT if the two conditions below are satisfied:
1112           * a) There are no non-portable control characters belonging to the
1113           * "black list" (0..6, 14..25, 28..31).
1114           * b) There is at least one printable character belonging to the
1115           * "white list" (9 {TAB}, 10 {LF}, 13 {CR}, 32..255).
1116           * - BINARY otherwise.
1117           * - The following partially-portable control characters form a
1118           * "gray list" that is ignored in this detection algorithm:
1119           * (7 {BEL}, 8 {BS}, 11 {VT}, 12 {FF}, 26 {SUB}, 27 {ESC}).
1120           * IN assertion: the fields Freq of dyn_ltree are set.
1121           */
1122           local int detect_data_type(
1123           deflate_state *s)
1124           {
1125           /* black_mask is the bit mask of black-listed bytes
1126           * set bits 0..6, 14..25, and 28..31
1127           * 0xf3ffc07f = binary 11110011111111111100000001111111
1128           */
1129           unsigned long black_mask = 0xf3ffc07fUL;
1130           int n;
1131            
1132           /* Check for non-textual ("black-listed") bytes. */
1133 94220         for (n = 0; n <= 31; n++, black_mask >>= 1)
1134 94302         if ((black_mask & 1) && (s->dyn_ltree[n].Freq != 0))
1135           return Z_BINARY;
1136            
1137           /* Check for textual ("white-listed") bytes. */
1138 2944         if (s->dyn_ltree[9].Freq != 0 || s->dyn_ltree[10].Freq != 0
1139 2186         || s->dyn_ltree[13].Freq != 0)
1140           return Z_TEXT;
1141 209594         for (n = 32; n < LITERALS; n++)
1142 211058         if (s->dyn_ltree[n].Freq != 0)
1143           return Z_TEXT;
1144            
1145           /* There are no "black-listed" or "white-listed" bytes:
1146           * this stream either is empty or has tolerated ("gray-listed") bytes only.
1147           */
1148           return Z_BINARY;
1149           }
1150            
1151           /* ===========================================================================
1152           * Reverse the first len bits of a code, using straightforward code (a faster
1153           * method would use a table)
1154           * IN assertion: 1 <= len <= 15
1155           */
1156           local unsigned bi_reverse(
1157           unsigned code,
1158           int len)
1159           {
1160           register unsigned res = 0;
1161           do {
1162 257192         res |= code & 1;
1163 257192         code >>= 1, res <<= 1;
1164 257192         } while (--len > 0);
1165 62664         return res >> 1;
1166           }
1167            
1168           /* ===========================================================================
1169           * Flush the bit buffer, keeping at most 7 bits in it.
1170           */
1171           local void bi_flush(
1172           deflate_state *s)
1173           {
1174 3966         if (s->bi_valid == 16) {
1175 0         put_short(s, s->bi_buf);
1176 0         s->bi_buf = 0;
1177 0         s->bi_valid = 0;
1178 3966         } else if (s->bi_valid >= 8) {
1179 8         put_byte(s, (Byte)s->bi_buf);
1180 8         s->bi_buf >>= 8;
1181 8         s->bi_valid -= 8;
1182           }
1183           }
1184            
1185           /* ===========================================================================
1186           * Flush the bit buffer and align the output on a byte boundary
1187           */
1188           local void bi_windup(
1189           deflate_state *s)
1190           {
1191 3102         if (s->bi_valid > 8) {
1192 1606         put_short(s, s->bi_buf);
1193 1496         } else if (s->bi_valid > 0) {
1194 1454         put_byte(s, (Byte)s->bi_buf);
1195           }
1196 3102         s->bi_buf = 0;
1197 3102         s->bi_valid = 0;
1198           #ifdef DEBUG
1199           s->bits_sent = (s->bits_sent+7) & ~7;
1200           #endif
1201           }
1202            
1203           /* ===========================================================================
1204           * Copy a stored block, storing first the length and its
1205           * one's complement if requested.
1206           */
1207 72         local void copy_block(
1208           deflate_state *s,
1209           charf *buf,
1210           unsigned len,
1211           int header)
1212           {
1213           bi_windup(s); /* align on byte boundary */
1214            
1215 72         if (header) {
1216 72         put_short(s, (ush)len);
1217 72         put_short(s, (ush)~len);
1218           #ifdef DEBUG
1219           s->bits_sent += 2*16;
1220           #endif
1221           }
1222           #ifdef DEBUG
1223           s->bits_sent += (ulg)len<<3;
1224           #endif
1225 472078         while (len--) {
1226 472006         put_byte(s, *buf++);
1227           }
1228 72         }