ยปCore Development>Code coverage>Modules/zlib/trees.c

Python code coverage for Modules/zlib/trees.c

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