OLD | NEW |
1 /* trees.c -- output deflated data using Huffman coding | 1 /* trees.c -- output deflated data using Huffman coding |
2 * Copyright (C) 1995-2012 Jean-loup Gailly | 2 * Copyright (C) 1995-2017 Jean-loup Gailly |
3 * detect_data_type() function provided freely by Cosmin Truta, 2006 | 3 * detect_data_type() function provided freely by Cosmin Truta, 2006 |
4 * For conditions of distribution and use, see copyright notice in zlib.h | 4 * For conditions of distribution and use, see copyright notice in zlib.h |
5 */ | 5 */ |
6 | 6 |
7 /* | 7 /* |
8 * ALGORITHM | 8 * ALGORITHM |
9 * | 9 * |
10 * The "deflation" process uses several Huffman trees. The more | 10 * The "deflation" process uses several Huffman trees. The more |
11 * common source values are represented by shorter bit sequences. | 11 * common source values are represented by shorter bit sequences. |
12 * | 12 * |
(...skipping 16 matching lines...) Expand all Loading... |
29 * Algorithms, p290. | 29 * Algorithms, p290. |
30 * Addison-Wesley, 1983. ISBN 0-201-06672-6. | 30 * Addison-Wesley, 1983. ISBN 0-201-06672-6. |
31 */ | 31 */ |
32 | 32 |
33 /* @(#) $Id$ */ | 33 /* @(#) $Id$ */ |
34 | 34 |
35 /* #define GEN_TREES_H */ | 35 /* #define GEN_TREES_H */ |
36 | 36 |
37 #include "deflate.h" | 37 #include "deflate.h" |
38 | 38 |
39 #ifdef DEBUG | 39 #ifdef ZLIB_DEBUG |
40 # include <ctype.h> | 40 # include <ctype.h> |
41 #endif | 41 #endif |
42 | 42 |
43 /* =========================================================================== | 43 /* =========================================================================== |
44 * Constants | 44 * Constants |
45 */ | 45 */ |
46 | 46 |
47 #define MAX_BL_BITS 7 | 47 #define MAX_BL_BITS 7 |
48 /* Bit length codes must not exceed MAX_BL_BITS bits */ | 48 /* Bit length codes must not exceed MAX_BL_BITS bits */ |
49 | 49 |
(...skipping 65 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
115 #endif /* GEN_TREES_H */ | 115 #endif /* GEN_TREES_H */ |
116 | 116 |
117 struct static_tree_desc_s { | 117 struct static_tree_desc_s { |
118 const ct_data *static_tree; /* static tree or NULL */ | 118 const ct_data *static_tree; /* static tree or NULL */ |
119 const intf *extra_bits; /* extra bits for each code or NULL */ | 119 const intf *extra_bits; /* extra bits for each code or NULL */ |
120 int extra_base; /* base index for extra_bits */ | 120 int extra_base; /* base index for extra_bits */ |
121 int elems; /* max number of elements in the tree */ | 121 int elems; /* max number of elements in the tree */ |
122 int max_length; /* max bit length for the codes */ | 122 int max_length; /* max bit length for the codes */ |
123 }; | 123 }; |
124 | 124 |
125 local static_tree_desc static_l_desc = | 125 local const static_tree_desc static_l_desc = |
126 {static_ltree, extra_lbits, LITERALS+1, L_CODES, MAX_BITS}; | 126 {static_ltree, extra_lbits, LITERALS+1, L_CODES, MAX_BITS}; |
127 | 127 |
128 local static_tree_desc static_d_desc = | 128 local const static_tree_desc static_d_desc = |
129 {static_dtree, extra_dbits, 0, D_CODES, MAX_BITS}; | 129 {static_dtree, extra_dbits, 0, D_CODES, MAX_BITS}; |
130 | 130 |
131 local static_tree_desc static_bl_desc = | 131 local const static_tree_desc static_bl_desc = |
132 {(const ct_data *)0, extra_blbits, 0, BL_CODES, MAX_BL_BITS}; | 132 {(const ct_data *)0, extra_blbits, 0, BL_CODES, MAX_BL_BITS}; |
133 | 133 |
134 /* =========================================================================== | 134 /* =========================================================================== |
135 * Local (static) routines in this file. | 135 * Local (static) routines in this file. |
136 */ | 136 */ |
137 | 137 |
138 local void tr_static_init OF((void)); | 138 local void tr_static_init OF((void)); |
139 local void init_block OF((deflate_state *s)); | 139 local void init_block OF((deflate_state *s)); |
140 local void pqdownheap OF((deflate_state *s, ct_data *tree, int k)); | 140 local void pqdownheap OF((deflate_state *s, ct_data *tree, int k)); |
141 local void gen_bitlen OF((deflate_state *s, tree_desc *desc)); | 141 local void gen_bitlen OF((deflate_state *s, tree_desc *desc)); |
142 local void gen_codes OF((ct_data *tree, int max_code, ushf *bl_count)); | 142 local void gen_codes OF((ct_data *tree, int max_code, ushf *bl_count)); |
143 local void build_tree OF((deflate_state *s, tree_desc *desc)); | 143 local void build_tree OF((deflate_state *s, tree_desc *desc)); |
144 local void scan_tree OF((deflate_state *s, ct_data *tree, int max_code)); | 144 local void scan_tree OF((deflate_state *s, ct_data *tree, int max_code)); |
145 local void send_tree OF((deflate_state *s, ct_data *tree, int max_code)); | 145 local void send_tree OF((deflate_state *s, ct_data *tree, int max_code)); |
146 local int build_bl_tree OF((deflate_state *s)); | 146 local int build_bl_tree OF((deflate_state *s)); |
147 local void send_all_trees OF((deflate_state *s, int lcodes, int dcodes, | 147 local void send_all_trees OF((deflate_state *s, int lcodes, int dcodes, |
148 int blcodes)); | 148 int blcodes)); |
149 local void compress_block OF((deflate_state *s, const ct_data *ltree, | 149 local void compress_block OF((deflate_state *s, const ct_data *ltree, |
150 const ct_data *dtree)); | 150 const ct_data *dtree)); |
151 local int detect_data_type OF((deflate_state *s)); | 151 local int detect_data_type OF((deflate_state *s)); |
152 local unsigned bi_reverse OF((unsigned value, int length)); | 152 local unsigned bi_reverse OF((unsigned value, int length)); |
153 local void bi_windup OF((deflate_state *s)); | 153 local void bi_windup OF((deflate_state *s)); |
154 local void bi_flush OF((deflate_state *s)); | 154 local void bi_flush OF((deflate_state *s)); |
155 local void copy_block OF((deflate_state *s, charf *buf, unsigned len, | |
156 int header)); | |
157 | 155 |
158 #ifdef GEN_TREES_H | 156 #ifdef GEN_TREES_H |
159 local void gen_trees_header OF((void)); | 157 local void gen_trees_header OF((void)); |
160 #endif | 158 #endif |
161 | 159 |
162 #ifndef DEBUG | 160 #ifndef ZLIB_DEBUG |
163 # define send_code(s, c, tree) send_bits(s, tree[c].Code, tree[c].Len) | 161 # define send_code(s, c, tree) send_bits(s, tree[c].Code, tree[c].Len) |
164 /* Send a code of the given tree. c and tree must not have side effects */ | 162 /* Send a code of the given tree. c and tree must not have side effects */ |
165 | 163 |
166 #else /* DEBUG */ | 164 #else /* !ZLIB_DEBUG */ |
167 # define send_code(s, c, tree) \ | 165 # define send_code(s, c, tree) \ |
168 { if (z_verbose>2) fprintf(stderr,"\ncd %3d ",(c)); \ | 166 { if (z_verbose>2) fprintf(stderr,"\ncd %3d ",(c)); \ |
169 send_bits(s, tree[c].Code, tree[c].Len); } | 167 send_bits(s, tree[c].Code, tree[c].Len); } |
170 #endif | 168 #endif |
171 | 169 |
172 /* =========================================================================== | 170 /* =========================================================================== |
173 * Output a short LSB first on the stream. | 171 * Output a short LSB first on the stream. |
174 * IN assertion: there is enough room in pendingBuf. | 172 * IN assertion: there is enough room in pendingBuf. |
175 */ | 173 */ |
176 #define put_short(s, w) { \ | 174 #define put_short(s, w) { \ |
177 put_byte(s, (uch)((w) & 0xff)); \ | 175 put_byte(s, (uch)((w) & 0xff)); \ |
178 put_byte(s, (uch)((ush)(w) >> 8)); \ | 176 put_byte(s, (uch)((ush)(w) >> 8)); \ |
179 } | 177 } |
180 | 178 |
181 /* =========================================================================== | 179 /* =========================================================================== |
182 * Send a value on a given number of bits. | 180 * Send a value on a given number of bits. |
183 * IN assertion: length <= 16 and value fits in length bits. | 181 * IN assertion: length <= 16 and value fits in length bits. |
184 */ | 182 */ |
185 #ifdef DEBUG | 183 #ifdef ZLIB_DEBUG |
186 local void send_bits OF((deflate_state *s, int value, int length)); | 184 local void send_bits OF((deflate_state *s, int value, int length)); |
187 | 185 |
188 local void send_bits(s, value, length) | 186 local void send_bits(s, value, length) |
189 deflate_state *s; | 187 deflate_state *s; |
190 int value; /* value to send */ | 188 int value; /* value to send */ |
191 int length; /* number of bits */ | 189 int length; /* number of bits */ |
192 { | 190 { |
193 Tracevv((stderr," l %2d v %4x ", length, value)); | 191 Tracevv((stderr," l %2d v %4x ", length, value)); |
194 Assert(length > 0 && length <= 15, "invalid length"); | 192 Assert(length > 0 && length <= 15, "invalid length"); |
195 s->bits_sent += (ulg)length; | 193 s->bits_sent += (ulg)length; |
196 | 194 |
197 /* If not enough room in bi_buf, use (valid) bits from bi_buf and | 195 /* If not enough room in bi_buf, use (valid) bits from bi_buf and |
198 * (16 - bi_valid) bits from value, leaving (width - (16-bi_valid)) | 196 * (16 - bi_valid) bits from value, leaving (width - (16-bi_valid)) |
199 * unused bits in value. | 197 * unused bits in value. |
200 */ | 198 */ |
201 if (s->bi_valid > (int)Buf_size - length) { | 199 if (s->bi_valid > (int)Buf_size - length) { |
202 s->bi_buf |= (ush)value << s->bi_valid; | 200 s->bi_buf |= (ush)value << s->bi_valid; |
203 put_short(s, s->bi_buf); | 201 put_short(s, s->bi_buf); |
204 s->bi_buf = (ush)value >> (Buf_size - s->bi_valid); | 202 s->bi_buf = (ush)value >> (Buf_size - s->bi_valid); |
205 s->bi_valid += length - Buf_size; | 203 s->bi_valid += length - Buf_size; |
206 } else { | 204 } else { |
207 s->bi_buf |= (ush)value << s->bi_valid; | 205 s->bi_buf |= (ush)value << s->bi_valid; |
208 s->bi_valid += length; | 206 s->bi_valid += length; |
209 } | 207 } |
210 } | 208 } |
211 #else /* !DEBUG */ | 209 #else /* !ZLIB_DEBUG */ |
212 | 210 |
213 #define send_bits(s, value, length) \ | 211 #define send_bits(s, value, length) \ |
214 { int len = length;\ | 212 { int len = length;\ |
215 if (s->bi_valid > (int)Buf_size - len) {\ | 213 if (s->bi_valid > (int)Buf_size - len) {\ |
216 int val = value;\ | 214 int val = (int)value;\ |
217 s->bi_buf |= (ush)val << s->bi_valid;\ | 215 s->bi_buf |= (ush)val << s->bi_valid;\ |
218 put_short(s, s->bi_buf);\ | 216 put_short(s, s->bi_buf);\ |
219 s->bi_buf = (ush)val >> (Buf_size - s->bi_valid);\ | 217 s->bi_buf = (ush)val >> (Buf_size - s->bi_valid);\ |
220 s->bi_valid += len - Buf_size;\ | 218 s->bi_valid += len - Buf_size;\ |
221 } else {\ | 219 } else {\ |
222 s->bi_buf |= (ush)(value) << s->bi_valid;\ | 220 s->bi_buf |= (ush)(value) << s->bi_valid;\ |
223 s->bi_valid += len;\ | 221 s->bi_valid += len;\ |
224 }\ | 222 }\ |
225 } | 223 } |
226 #endif /* DEBUG */ | 224 #endif /* ZLIB_DEBUG */ |
227 | 225 |
228 | 226 |
229 /* the arguments must not have side effects */ | 227 /* the arguments must not have side effects */ |
230 | 228 |
231 /* =========================================================================== | 229 /* =========================================================================== |
232 * Initialize the various 'constant' tables. | 230 * Initialize the various 'constant' tables. |
233 */ | 231 */ |
234 local void tr_static_init() | 232 local void tr_static_init() |
235 { | 233 { |
236 #if defined(GEN_TREES_H) || !defined(STDC) | 234 #if defined(GEN_TREES_H) || !defined(STDC) |
(...skipping 73 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
310 # ifdef GEN_TREES_H | 308 # ifdef GEN_TREES_H |
311 gen_trees_header(); | 309 gen_trees_header(); |
312 # endif | 310 # endif |
313 #endif /* defined(GEN_TREES_H) || !defined(STDC) */ | 311 #endif /* defined(GEN_TREES_H) || !defined(STDC) */ |
314 } | 312 } |
315 | 313 |
316 /* =========================================================================== | 314 /* =========================================================================== |
317 * Genererate the file trees.h describing the static trees. | 315 * Genererate the file trees.h describing the static trees. |
318 */ | 316 */ |
319 #ifdef GEN_TREES_H | 317 #ifdef GEN_TREES_H |
320 # ifndef DEBUG | 318 # ifndef ZLIB_DEBUG |
321 # include <stdio.h> | 319 # include <stdio.h> |
322 # endif | 320 # endif |
323 | 321 |
324 # define SEPARATOR(i, last, width) \ | 322 # define SEPARATOR(i, last, width) \ |
325 ((i) == (last)? "\n};\n\n" : \ | 323 ((i) == (last)? "\n};\n\n" : \ |
326 ((i) % (width) == (width)-1 ? ",\n" : ", ")) | 324 ((i) % (width) == (width)-1 ? ",\n" : ", ")) |
327 | 325 |
328 void gen_trees_header() | 326 void gen_trees_header() |
329 { | 327 { |
330 FILE *header = fopen("trees.h", "w"); | 328 FILE *header = fopen("trees.h", "w"); |
(...skipping 56 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
387 s->l_desc.stat_desc = &static_l_desc; | 385 s->l_desc.stat_desc = &static_l_desc; |
388 | 386 |
389 s->d_desc.dyn_tree = s->dyn_dtree; | 387 s->d_desc.dyn_tree = s->dyn_dtree; |
390 s->d_desc.stat_desc = &static_d_desc; | 388 s->d_desc.stat_desc = &static_d_desc; |
391 | 389 |
392 s->bl_desc.dyn_tree = s->bl_tree; | 390 s->bl_desc.dyn_tree = s->bl_tree; |
393 s->bl_desc.stat_desc = &static_bl_desc; | 391 s->bl_desc.stat_desc = &static_bl_desc; |
394 | 392 |
395 s->bi_buf = 0; | 393 s->bi_buf = 0; |
396 s->bi_valid = 0; | 394 s->bi_valid = 0; |
397 #ifdef DEBUG | 395 #ifdef ZLIB_DEBUG |
398 s->compressed_len = 0L; | 396 s->compressed_len = 0L; |
399 s->bits_sent = 0L; | 397 s->bits_sent = 0L; |
400 #endif | 398 #endif |
401 | 399 |
402 /* Initialize the first block of the first file: */ | 400 /* Initialize the first block of the first file: */ |
403 init_block(s); | 401 init_block(s); |
404 } | 402 } |
405 | 403 |
406 /* =========================================================================== | 404 /* =========================================================================== |
407 * Initialize a new block. | 405 * Initialize a new block. |
(...skipping 107 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
515 if (bits > max_length) bits = max_length, overflow++; | 513 if (bits > max_length) bits = max_length, overflow++; |
516 tree[n].Len = (ush)bits; | 514 tree[n].Len = (ush)bits; |
517 /* We overwrite tree[n].Dad which is no longer needed */ | 515 /* We overwrite tree[n].Dad which is no longer needed */ |
518 | 516 |
519 if (n > max_code) continue; /* not a leaf node */ | 517 if (n > max_code) continue; /* not a leaf node */ |
520 | 518 |
521 s->bl_count[bits]++; | 519 s->bl_count[bits]++; |
522 xbits = 0; | 520 xbits = 0; |
523 if (n >= base) xbits = extra[n-base]; | 521 if (n >= base) xbits = extra[n-base]; |
524 f = tree[n].Freq; | 522 f = tree[n].Freq; |
525 s->opt_len += (ulg)f * (bits + xbits); | 523 s->opt_len += (ulg)f * (unsigned)(bits + xbits); |
526 if (stree) s->static_len += (ulg)f * (stree[n].Len + xbits); | 524 if (stree) s->static_len += (ulg)f * (unsigned)(stree[n].Len + xbits); |
527 } | 525 } |
528 if (overflow == 0) return; | 526 if (overflow == 0) return; |
529 | 527 |
530 Trace((stderr,"\nbit length overflow\n")); | 528 Tracev((stderr,"\nbit length overflow\n")); |
531 /* This happens for example on obj2 and pic of the Calgary corpus */ | 529 /* This happens for example on obj2 and pic of the Calgary corpus */ |
532 | 530 |
533 /* Find the first bit length which could increase: */ | 531 /* Find the first bit length which could increase: */ |
534 do { | 532 do { |
535 bits = max_length-1; | 533 bits = max_length-1; |
536 while (s->bl_count[bits] == 0) bits--; | 534 while (s->bl_count[bits] == 0) bits--; |
537 s->bl_count[bits]--; /* move one leaf down the tree */ | 535 s->bl_count[bits]--; /* move one leaf down the tree */ |
538 s->bl_count[bits+1] += 2; /* move one overflow item as its brother */ | 536 s->bl_count[bits+1] += 2; /* move one overflow item as its brother */ |
539 s->bl_count[max_length]--; | 537 s->bl_count[max_length]--; |
540 /* The brother of the overflow item also moves one step up, | 538 /* The brother of the overflow item also moves one step up, |
541 * but this does not affect bl_count[max_length] | 539 * but this does not affect bl_count[max_length] |
542 */ | 540 */ |
543 overflow -= 2; | 541 overflow -= 2; |
544 } while (overflow > 0); | 542 } while (overflow > 0); |
545 | 543 |
546 /* Now recompute all bit lengths, scanning in increasing frequency. | 544 /* Now recompute all bit lengths, scanning in increasing frequency. |
547 * h is still equal to HEAP_SIZE. (It is simpler to reconstruct all | 545 * h is still equal to HEAP_SIZE. (It is simpler to reconstruct all |
548 * lengths instead of fixing only the wrong ones. This idea is taken | 546 * lengths instead of fixing only the wrong ones. This idea is taken |
549 * from 'ar' written by Haruhiko Okumura.) | 547 * from 'ar' written by Haruhiko Okumura.) |
550 */ | 548 */ |
551 for (bits = max_length; bits != 0; bits--) { | 549 for (bits = max_length; bits != 0; bits--) { |
552 n = s->bl_count[bits]; | 550 n = s->bl_count[bits]; |
553 while (n != 0) { | 551 while (n != 0) { |
554 m = s->heap[--h]; | 552 m = s->heap[--h]; |
555 if (m > max_code) continue; | 553 if (m > max_code) continue; |
556 if ((unsigned) tree[m].Len != (unsigned) bits) { | 554 if ((unsigned) tree[m].Len != (unsigned) bits) { |
557 Trace((stderr,"code %d bits %d->%d\n", m, tree[m].Len, bits)); | 555 Tracev((stderr,"code %d bits %d->%d\n", m, tree[m].Len, bits)); |
558 s->opt_len += ((long)bits - (long)tree[m].Len) | 556 s->opt_len += ((ulg)bits - tree[m].Len) * tree[m].Freq; |
559 *(long)tree[m].Freq; | |
560 tree[m].Len = (ush)bits; | 557 tree[m].Len = (ush)bits; |
561 } | 558 } |
562 n--; | 559 n--; |
563 } | 560 } |
564 } | 561 } |
565 } | 562 } |
566 | 563 |
567 /* =========================================================================== | 564 /* =========================================================================== |
568 * Generate the codes for a given tree and bit counts (which need not be | 565 * Generate the codes for a given tree and bit counts (which need not be |
569 * optimal). | 566 * optimal). |
570 * IN assertion: the array bl_count contains the bit length statistics for | 567 * IN assertion: the array bl_count contains the bit length statistics for |
571 * the given tree and the field len is set for all tree elements. | 568 * the given tree and the field len is set for all tree elements. |
572 * OUT assertion: the field code is set for all tree elements of non | 569 * OUT assertion: the field code is set for all tree elements of non |
573 * zero code length. | 570 * zero code length. |
574 */ | 571 */ |
575 local void gen_codes (tree, max_code, bl_count) | 572 local void gen_codes (tree, max_code, bl_count) |
576 ct_data *tree; /* the tree to decorate */ | 573 ct_data *tree; /* the tree to decorate */ |
577 int max_code; /* largest code with non zero frequency */ | 574 int max_code; /* largest code with non zero frequency */ |
578 ushf *bl_count; /* number of codes at each bit length */ | 575 ushf *bl_count; /* number of codes at each bit length */ |
579 { | 576 { |
580 ush next_code[MAX_BITS+1]; /* next code value for each bit length */ | 577 ush next_code[MAX_BITS+1]; /* next code value for each bit length */ |
581 ush code = 0; /* running code value */ | 578 unsigned code = 0; /* running code value */ |
582 int bits; /* bit index */ | 579 int bits; /* bit index */ |
583 int n; /* code index */ | 580 int n; /* code index */ |
584 | 581 |
585 /* The distribution counts are first used to generate the code values | 582 /* The distribution counts are first used to generate the code values |
586 * without bit reversal. | 583 * without bit reversal. |
587 */ | 584 */ |
588 for (bits = 1; bits <= MAX_BITS; bits++) { | 585 for (bits = 1; bits <= MAX_BITS; bits++) { |
589 next_code[bits] = code = (code + bl_count[bits-1]) << 1; | 586 code = (code + bl_count[bits-1]) << 1; |
| 587 next_code[bits] = (ush)code; |
590 } | 588 } |
591 /* Check that the bit counts in bl_count are consistent. The last code | 589 /* Check that the bit counts in bl_count are consistent. The last code |
592 * must be all ones. | 590 * must be all ones. |
593 */ | 591 */ |
594 Assert (code + bl_count[MAX_BITS]-1 == (1<<MAX_BITS)-1, | 592 Assert (code + bl_count[MAX_BITS]-1 == (1<<MAX_BITS)-1, |
595 "inconsistent bit counts"); | 593 "inconsistent bit counts"); |
596 Tracev((stderr,"\ngen_codes: max_code %d ", max_code)); | 594 Tracev((stderr,"\ngen_codes: max_code %d ", max_code)); |
597 | 595 |
598 for (n = 0; n <= max_code; n++) { | 596 for (n = 0; n <= max_code; n++) { |
599 int len = tree[n].Len; | 597 int len = tree[n].Len; |
600 if (len == 0) continue; | 598 if (len == 0) continue; |
601 /* Now reverse the bits */ | 599 /* Now reverse the bits */ |
602 tree[n].Code = bi_reverse(next_code[len]++, len); | 600 tree[n].Code = (ush)bi_reverse(next_code[len]++, len); |
603 | 601 |
604 Tracecv(tree != static_ltree, (stderr,"\nn %3d %c l %2d c %4x (%x) ", | 602 Tracecv(tree != static_ltree, (stderr,"\nn %3d %c l %2d c %4x (%x) ", |
605 n, (isgraph(n) ? n : ' '), len, tree[n].Code, next_code[len]-1)); | 603 n, (isgraph(n) ? n : ' '), len, tree[n].Code, next_code[len]-1)); |
606 } | 604 } |
607 } | 605 } |
608 | 606 |
609 /* =========================================================================== | 607 /* =========================================================================== |
610 * Construct one Huffman tree and assigns the code bit strings and lengths. | 608 * Construct one Huffman tree and assigns the code bit strings and lengths. |
611 * Update the total bit length for the current block. | 609 * Update the total bit length for the current block. |
612 * IN assertion: the field freq is set for all tree elements. | 610 * IN assertion: the field freq is set for all tree elements. |
(...skipping 201 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
814 */ | 812 */ |
815 | 813 |
816 /* Determine the number of bit length codes to send. The pkzip format | 814 /* Determine the number of bit length codes to send. The pkzip format |
817 * requires that at least 4 bit length codes be sent. (appnote.txt says | 815 * requires that at least 4 bit length codes be sent. (appnote.txt says |
818 * 3 but the actual value used is 4.) | 816 * 3 but the actual value used is 4.) |
819 */ | 817 */ |
820 for (max_blindex = BL_CODES-1; max_blindex >= 3; max_blindex--) { | 818 for (max_blindex = BL_CODES-1; max_blindex >= 3; max_blindex--) { |
821 if (s->bl_tree[bl_order[max_blindex]].Len != 0) break; | 819 if (s->bl_tree[bl_order[max_blindex]].Len != 0) break; |
822 } | 820 } |
823 /* Update opt_len to include the bit length tree and counts */ | 821 /* Update opt_len to include the bit length tree and counts */ |
824 s->opt_len += 3*(max_blindex+1) + 5+5+4; | 822 s->opt_len += 3*((ulg)max_blindex+1) + 5+5+4; |
825 Tracev((stderr, "\ndyn trees: dyn %ld, stat %ld", | 823 Tracev((stderr, "\ndyn trees: dyn %ld, stat %ld", |
826 s->opt_len, s->static_len)); | 824 s->opt_len, s->static_len)); |
827 | 825 |
828 return max_blindex; | 826 return max_blindex; |
829 } | 827 } |
830 | 828 |
831 /* =========================================================================== | 829 /* =========================================================================== |
832 * Send the header for a block using dynamic Huffman trees: the counts, the | 830 * Send the header for a block using dynamic Huffman trees: the counts, the |
833 * lengths of the bit length codes, the literal tree and the distance tree. | 831 * lengths of the bit length codes, the literal tree and the distance tree. |
834 * IN assertion: lcodes >= 257, dcodes >= 1, blcodes >= 4. | 832 * IN assertion: lcodes >= 257, dcodes >= 1, blcodes >= 4. |
(...skipping 27 matching lines...) Expand all Loading... |
862 /* =========================================================================== | 860 /* =========================================================================== |
863 * Send a stored block | 861 * Send a stored block |
864 */ | 862 */ |
865 void ZLIB_INTERNAL _tr_stored_block(s, buf, stored_len, last) | 863 void ZLIB_INTERNAL _tr_stored_block(s, buf, stored_len, last) |
866 deflate_state *s; | 864 deflate_state *s; |
867 charf *buf; /* input block */ | 865 charf *buf; /* input block */ |
868 ulg stored_len; /* length of input block */ | 866 ulg stored_len; /* length of input block */ |
869 int last; /* one if this is the last block for a file */ | 867 int last; /* one if this is the last block for a file */ |
870 { | 868 { |
871 send_bits(s, (STORED_BLOCK<<1)+last, 3); /* send block type */ | 869 send_bits(s, (STORED_BLOCK<<1)+last, 3); /* send block type */ |
872 #ifdef DEBUG | 870 bi_windup(s); /* align on byte boundary */ |
| 871 put_short(s, (ush)stored_len); |
| 872 put_short(s, (ush)~stored_len); |
| 873 zmemcpy(s->pending_buf + s->pending, (Bytef *)buf, stored_len); |
| 874 s->pending += stored_len; |
| 875 #ifdef ZLIB_DEBUG |
873 s->compressed_len = (s->compressed_len + 3 + 7) & (ulg)~7L; | 876 s->compressed_len = (s->compressed_len + 3 + 7) & (ulg)~7L; |
874 s->compressed_len += (stored_len + 4) << 3; | 877 s->compressed_len += (stored_len + 4) << 3; |
| 878 s->bits_sent += 2*16; |
| 879 s->bits_sent += stored_len<<3; |
875 #endif | 880 #endif |
876 copy_block(s, buf, (unsigned)stored_len, 1); /* with header */ | |
877 } | 881 } |
878 | 882 |
879 /* =========================================================================== | 883 /* =========================================================================== |
880 * Flush the bits in the bit buffer to pending output (leaves at most 7 bits) | 884 * Flush the bits in the bit buffer to pending output (leaves at most 7 bits) |
881 */ | 885 */ |
882 void ZLIB_INTERNAL _tr_flush_bits(s) | 886 void ZLIB_INTERNAL _tr_flush_bits(s) |
883 deflate_state *s; | 887 deflate_state *s; |
884 { | 888 { |
885 bi_flush(s); | 889 bi_flush(s); |
886 } | 890 } |
887 | 891 |
888 /* =========================================================================== | 892 /* =========================================================================== |
889 * Send one empty static block to give enough lookahead for inflate. | 893 * Send one empty static block to give enough lookahead for inflate. |
890 * This takes 10 bits, of which 7 may remain in the bit buffer. | 894 * This takes 10 bits, of which 7 may remain in the bit buffer. |
891 */ | 895 */ |
892 void ZLIB_INTERNAL _tr_align(s) | 896 void ZLIB_INTERNAL _tr_align(s) |
893 deflate_state *s; | 897 deflate_state *s; |
894 { | 898 { |
895 send_bits(s, STATIC_TREES<<1, 3); | 899 send_bits(s, STATIC_TREES<<1, 3); |
896 send_code(s, END_BLOCK, static_ltree); | 900 send_code(s, END_BLOCK, static_ltree); |
897 #ifdef DEBUG | 901 #ifdef ZLIB_DEBUG |
898 s->compressed_len += 10L; /* 3 for block type, 7 for EOB */ | 902 s->compressed_len += 10L; /* 3 for block type, 7 for EOB */ |
899 #endif | 903 #endif |
900 bi_flush(s); | 904 bi_flush(s); |
901 } | 905 } |
902 | 906 |
903 /* =========================================================================== | 907 /* =========================================================================== |
904 * Determine the best encoding for the current block: dynamic trees, static | 908 * Determine the best encoding for the current block: dynamic trees, static |
905 * trees or store, and output the encoded block to the zip file. | 909 * trees or store, and write out the encoded block. |
906 */ | 910 */ |
907 void ZLIB_INTERNAL _tr_flush_block(s, buf, stored_len, last) | 911 void ZLIB_INTERNAL _tr_flush_block(s, buf, stored_len, last) |
908 deflate_state *s; | 912 deflate_state *s; |
909 charf *buf; /* input block, or NULL if too old */ | 913 charf *buf; /* input block, or NULL if too old */ |
910 ulg stored_len; /* length of input block */ | 914 ulg stored_len; /* length of input block */ |
911 int last; /* one if this is the last block for a file */ | 915 int last; /* one if this is the last block for a file */ |
912 { | 916 { |
913 ulg opt_lenb, static_lenb; /* opt_len and static_len in bytes */ | 917 ulg opt_lenb, static_lenb; /* opt_len and static_len in bytes */ |
914 int max_blindex = 0; /* index of last bit length code of non zero freq */ | 918 int max_blindex = 0; /* index of last bit length code of non zero freq */ |
915 | 919 |
(...skipping 51 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
967 _tr_stored_block(s, buf, stored_len, last); | 971 _tr_stored_block(s, buf, stored_len, last); |
968 | 972 |
969 #ifdef FORCE_STATIC | 973 #ifdef FORCE_STATIC |
970 } else if (static_lenb >= 0) { /* force static trees */ | 974 } else if (static_lenb >= 0) { /* force static trees */ |
971 #else | 975 #else |
972 } else if (s->strategy == Z_FIXED || static_lenb == opt_lenb) { | 976 } else if (s->strategy == Z_FIXED || static_lenb == opt_lenb) { |
973 #endif | 977 #endif |
974 send_bits(s, (STATIC_TREES<<1)+last, 3); | 978 send_bits(s, (STATIC_TREES<<1)+last, 3); |
975 compress_block(s, (const ct_data *)static_ltree, | 979 compress_block(s, (const ct_data *)static_ltree, |
976 (const ct_data *)static_dtree); | 980 (const ct_data *)static_dtree); |
977 #ifdef DEBUG | 981 #ifdef ZLIB_DEBUG |
978 s->compressed_len += 3 + s->static_len; | 982 s->compressed_len += 3 + s->static_len; |
979 #endif | 983 #endif |
980 } else { | 984 } else { |
981 send_bits(s, (DYN_TREES<<1)+last, 3); | 985 send_bits(s, (DYN_TREES<<1)+last, 3); |
982 send_all_trees(s, s->l_desc.max_code+1, s->d_desc.max_code+1, | 986 send_all_trees(s, s->l_desc.max_code+1, s->d_desc.max_code+1, |
983 max_blindex+1); | 987 max_blindex+1); |
984 compress_block(s, (const ct_data *)s->dyn_ltree, | 988 compress_block(s, (const ct_data *)s->dyn_ltree, |
985 (const ct_data *)s->dyn_dtree); | 989 (const ct_data *)s->dyn_dtree); |
986 #ifdef DEBUG | 990 #ifdef ZLIB_DEBUG |
987 s->compressed_len += 3 + s->opt_len; | 991 s->compressed_len += 3 + s->opt_len; |
988 #endif | 992 #endif |
989 } | 993 } |
990 Assert (s->compressed_len == s->bits_sent, "bad compressed size"); | 994 Assert (s->compressed_len == s->bits_sent, "bad compressed size"); |
991 /* The above check is made mod 2^32, for files larger than 512 MB | 995 /* The above check is made mod 2^32, for files larger than 512 MB |
992 * and uLong implemented on 32 bits. | 996 * and uLong implemented on 32 bits. |
993 */ | 997 */ |
994 init_block(s); | 998 init_block(s); |
995 | 999 |
996 if (last) { | 1000 if (last) { |
997 bi_windup(s); | 1001 bi_windup(s); |
998 #ifdef DEBUG | 1002 #ifdef ZLIB_DEBUG |
999 s->compressed_len += 7; /* align on byte boundary */ | 1003 s->compressed_len += 7; /* align on byte boundary */ |
1000 #endif | 1004 #endif |
1001 } | 1005 } |
1002 Tracev((stderr,"\ncomprlen %lu(%lu) ", s->compressed_len>>3, | 1006 Tracev((stderr,"\ncomprlen %lu(%lu) ", s->compressed_len>>3, |
1003 s->compressed_len-7*last)); | 1007 s->compressed_len-7*last)); |
1004 } | 1008 } |
1005 | 1009 |
1006 /* =========================================================================== | 1010 /* =========================================================================== |
1007 * Save the match info and tally the frequency counts. Return true if | 1011 * Save the match info and tally the frequency counts. Return true if |
1008 * the current block must be flushed. | 1012 * the current block must be flushed. |
(...skipping 74 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1083 lc -= base_length[code]; | 1087 lc -= base_length[code]; |
1084 send_bits(s, lc, extra); /* send the extra length bits */ | 1088 send_bits(s, lc, extra); /* send the extra length bits */ |
1085 } | 1089 } |
1086 dist--; /* dist is now the match distance - 1 */ | 1090 dist--; /* dist is now the match distance - 1 */ |
1087 code = d_code(dist); | 1091 code = d_code(dist); |
1088 Assert (code < D_CODES, "bad d_code"); | 1092 Assert (code < D_CODES, "bad d_code"); |
1089 | 1093 |
1090 send_code(s, code, dtree); /* send the distance code */ | 1094 send_code(s, code, dtree); /* send the distance code */ |
1091 extra = extra_dbits[code]; | 1095 extra = extra_dbits[code]; |
1092 if (extra != 0) { | 1096 if (extra != 0) { |
1093 dist -= base_dist[code]; | 1097 dist -= (unsigned)base_dist[code]; |
1094 send_bits(s, dist, extra); /* send the extra distance bits */ | 1098 send_bits(s, dist, extra); /* send the extra distance bits */ |
1095 } | 1099 } |
1096 } /* literal or match pair ? */ | 1100 } /* literal or match pair ? */ |
1097 | 1101 |
1098 /* Check that the overlay between pending_buf and d_buf+l_buf is ok: */ | 1102 /* Check that the overlay between pending_buf and d_buf+l_buf is ok: */ |
1099 Assert((uInt)(s->pending) < s->lit_bufsize + 2*lx, | 1103 Assert((uInt)(s->pending) < s->lit_bufsize + 2*lx, |
1100 "pendingBuf overflow"); | 1104 "pendingBuf overflow"); |
1101 | 1105 |
1102 } while (lx < s->last_lit); | 1106 } while (lx < s->last_lit); |
1103 | 1107 |
(...skipping 82 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1186 local void bi_windup(s) | 1190 local void bi_windup(s) |
1187 deflate_state *s; | 1191 deflate_state *s; |
1188 { | 1192 { |
1189 if (s->bi_valid > 8) { | 1193 if (s->bi_valid > 8) { |
1190 put_short(s, s->bi_buf); | 1194 put_short(s, s->bi_buf); |
1191 } else if (s->bi_valid > 0) { | 1195 } else if (s->bi_valid > 0) { |
1192 put_byte(s, (Byte)s->bi_buf); | 1196 put_byte(s, (Byte)s->bi_buf); |
1193 } | 1197 } |
1194 s->bi_buf = 0; | 1198 s->bi_buf = 0; |
1195 s->bi_valid = 0; | 1199 s->bi_valid = 0; |
1196 #ifdef DEBUG | 1200 #ifdef ZLIB_DEBUG |
1197 s->bits_sent = (s->bits_sent+7) & ~7; | 1201 s->bits_sent = (s->bits_sent+7) & ~7; |
1198 #endif | 1202 #endif |
1199 } | 1203 } |
1200 | |
1201 /* =========================================================================== | |
1202 * Copy a stored block, storing first the length and its | |
1203 * one's complement if requested. | |
1204 */ | |
1205 local void copy_block(s, buf, len, header) | |
1206 deflate_state *s; | |
1207 charf *buf; /* the input data */ | |
1208 unsigned len; /* its length */ | |
1209 int header; /* true if block header must be written */ | |
1210 { | |
1211 bi_windup(s); /* align on byte boundary */ | |
1212 | |
1213 if (header) { | |
1214 put_short(s, (ush)len); | |
1215 put_short(s, (ush)~len); | |
1216 #ifdef DEBUG | |
1217 s->bits_sent += 2*16; | |
1218 #endif | |
1219 } | |
1220 #ifdef DEBUG | |
1221 s->bits_sent += (ulg)len<<3; | |
1222 #endif | |
1223 while (len--) { | |
1224 put_byte(s, *buf++); | |
1225 } | |
1226 } | |
OLD | NEW |