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