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