OLD | NEW |
1 /* trees.c -- output deflated data using Huffman coding | 1 /* trees.c -- output deflated data using Huffman coding |
2 * Copyright (C) 1995-2005 Jean-loup Gailly | 2 * Copyright (C) 1995-2010 Jean-loup Gailly |
| 3 * detect_data_type() function provided freely by Cosmin Truta, 2006 |
3 * 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 |
4 */ | 5 */ |
5 | 6 |
6 /* | 7 /* |
7 * ALGORITHM | 8 * ALGORITHM |
8 * | 9 * |
9 * The "deflation" process uses several Huffman trees. The more | 10 * The "deflation" process uses several Huffman trees. The more |
10 * common source values are represented by shorter bit sequences. | 11 * common source values are represented by shorter bit sequences. |
11 * | 12 * |
12 * Each code tree is stored in a compressed form which is itself | 13 * Each code tree is stored in a compressed form which is itself |
13 * a Huffman encoding of the lengths of all the code strings (in | 14 * a Huffman encoding of the lengths of all the code strings (in |
14 * ascending order by source values). The actual code strings are | 15 * ascending order by source values). The actual code strings are |
15 * reconstructed from the lengths in the inflate process, as described | 16 * reconstructed from the lengths in the inflate process, as described |
16 * in the deflate specification. | 17 * in the deflate specification. |
17 * | 18 * |
18 * REFERENCES | 19 * REFERENCES |
19 * | 20 * |
20 * Deutsch, L.P.,"'Deflate' Compressed Data Format Specification". | 21 * Deutsch, L.P.,"'Deflate' Compressed Data Format Specification". |
21 * Available in ftp.uu.net:/pub/archiving/zip/doc/deflate-1.1.doc | 22 * Available in ftp.uu.net:/pub/archiving/zip/doc/deflate-1.1.doc |
22 * | 23 * |
23 * Storer, James A. | 24 * Storer, James A. |
24 * Data Compression: Methods and Theory, pp. 49-50. | 25 * Data Compression: Methods and Theory, pp. 49-50. |
25 * Computer Science Press, 1988. ISBN 0-7167-8156-5. | 26 * Computer Science Press, 1988. ISBN 0-7167-8156-5. |
26 * | 27 * |
27 * Sedgewick, R. | 28 * Sedgewick, R. |
28 * Algorithms, p290. | 29 * Algorithms, p290. |
29 * Addison-Wesley, 1983. ISBN 0-201-06672-6. | 30 * Addison-Wesley, 1983. ISBN 0-201-06672-6. |
30 */ | 31 */ |
31 | 32 |
32 /* @(#) $Id: trees.c,v 3.6 2005/08/04 19:14:14 tor%cs.brown.edu Exp $ */ | 33 /* @(#) $Id$ */ |
33 | 34 |
34 /* #define GEN_TREES_H */ | 35 /* #define GEN_TREES_H */ |
35 | 36 |
36 #include "deflate.h" | 37 #include "deflate.h" |
37 | 38 |
38 #ifdef DEBUG | 39 #ifdef DEBUG |
39 # include <ctype.h> | 40 # include <ctype.h> |
40 #endif | 41 #endif |
41 | 42 |
42 /* =========================================================================== | 43 /* =========================================================================== |
(...skipping 102 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
145 local void gen_bitlen OF((deflate_state *s, tree_desc *desc)); | 146 local void gen_bitlen OF((deflate_state *s, tree_desc *desc)); |
146 local void gen_codes OF((ct_data *tree, int max_code, ushf *bl_count)); | 147 local void gen_codes OF((ct_data *tree, int max_code, ushf *bl_count)); |
147 local void build_tree OF((deflate_state *s, tree_desc *desc)); | 148 local void build_tree OF((deflate_state *s, tree_desc *desc)); |
148 local void scan_tree OF((deflate_state *s, ct_data *tree, int max_code)); | 149 local void scan_tree OF((deflate_state *s, ct_data *tree, int max_code)); |
149 local void send_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)); |
150 local int build_bl_tree OF((deflate_state *s)); | 151 local int build_bl_tree OF((deflate_state *s)); |
151 local void send_all_trees OF((deflate_state *s, int lcodes, int dcodes, | 152 local void send_all_trees OF((deflate_state *s, int lcodes, int dcodes, |
152 int blcodes)); | 153 int blcodes)); |
153 local void compress_block OF((deflate_state *s, ct_data *ltree, | 154 local void compress_block OF((deflate_state *s, ct_data *ltree, |
154 ct_data *dtree)); | 155 ct_data *dtree)); |
155 local void set_data_type OF((deflate_state *s)); | 156 local int detect_data_type OF((deflate_state *s)); |
156 local unsigned bi_reverse OF((unsigned value, int length)); | 157 local unsigned bi_reverse OF((unsigned value, int length)); |
157 local void bi_windup OF((deflate_state *s)); | 158 local void bi_windup OF((deflate_state *s)); |
158 local void bi_flush OF((deflate_state *s)); | 159 local void bi_flush OF((deflate_state *s)); |
159 local void copy_block OF((deflate_state *s, charf *buf, unsigned len, | 160 local void copy_block OF((deflate_state *s, charf *buf, unsigned len, |
160 int header)); | 161 int header)); |
161 | 162 |
162 #ifdef GEN_TREES_H | 163 #ifdef GEN_TREES_H |
163 local void gen_trees_header OF((void)); | 164 local void gen_trees_header OF((void)); |
164 #endif | 165 #endif |
165 | 166 |
(...skipping 30 matching lines...) Expand all Loading... |
196 { | 197 { |
197 Tracevv((stderr," l %2d v %4x ", length, value)); | 198 Tracevv((stderr," l %2d v %4x ", length, value)); |
198 Assert(length > 0 && length <= 15, "invalid length"); | 199 Assert(length > 0 && length <= 15, "invalid length"); |
199 s->bits_sent += (ulg)length; | 200 s->bits_sent += (ulg)length; |
200 | 201 |
201 /* If not enough room in bi_buf, use (valid) bits from bi_buf and | 202 /* If not enough room in bi_buf, use (valid) bits from bi_buf and |
202 * (16 - bi_valid) bits from value, leaving (width - (16-bi_valid)) | 203 * (16 - bi_valid) bits from value, leaving (width - (16-bi_valid)) |
203 * unused bits in value. | 204 * unused bits in value. |
204 */ | 205 */ |
205 if (s->bi_valid > (int)Buf_size - length) { | 206 if (s->bi_valid > (int)Buf_size - length) { |
206 s->bi_buf |= (value << s->bi_valid); | 207 s->bi_buf |= (ush)value << s->bi_valid; |
207 put_short(s, s->bi_buf); | 208 put_short(s, s->bi_buf); |
208 s->bi_buf = (ush)value >> (Buf_size - s->bi_valid); | 209 s->bi_buf = (ush)value >> (Buf_size - s->bi_valid); |
209 s->bi_valid += length - Buf_size; | 210 s->bi_valid += length - Buf_size; |
210 } else { | 211 } else { |
211 s->bi_buf |= value << s->bi_valid; | 212 s->bi_buf |= (ush)value << s->bi_valid; |
212 s->bi_valid += length; | 213 s->bi_valid += length; |
213 } | 214 } |
214 } | 215 } |
215 #else /* !DEBUG */ | 216 #else /* !DEBUG */ |
216 | 217 |
217 #define send_bits(s, value, length) \ | 218 #define send_bits(s, value, length) \ |
218 { int len = length;\ | 219 { int len = length;\ |
219 if (s->bi_valid > (int)Buf_size - len) {\ | 220 if (s->bi_valid > (int)Buf_size - len) {\ |
220 int val = value;\ | 221 int val = value;\ |
221 s->bi_buf |= (val << s->bi_valid);\ | 222 s->bi_buf |= (ush)val << s->bi_valid;\ |
222 put_short(s, s->bi_buf);\ | 223 put_short(s, s->bi_buf);\ |
223 s->bi_buf = (ush)val >> (Buf_size - s->bi_valid);\ | 224 s->bi_buf = (ush)val >> (Buf_size - s->bi_valid);\ |
224 s->bi_valid += len - Buf_size;\ | 225 s->bi_valid += len - Buf_size;\ |
225 } else {\ | 226 } else {\ |
226 s->bi_buf |= (value) << s->bi_valid;\ | 227 s->bi_buf |= (ush)(value) << s->bi_valid;\ |
227 s->bi_valid += len;\ | 228 s->bi_valid += len;\ |
228 }\ | 229 }\ |
229 } | 230 } |
230 #endif /* DEBUG */ | 231 #endif /* DEBUG */ |
231 | 232 |
232 | 233 |
233 /* the arguments must not have side effects */ | 234 /* the arguments must not have side effects */ |
234 | 235 |
235 /* =========================================================================== | 236 /* =========================================================================== |
236 * Initialize the various 'constant' tables. | 237 * Initialize the various 'constant' tables. |
237 */ | 238 */ |
238 local void tr_static_init() | 239 local void tr_static_init() |
239 { | 240 { |
240 #if defined(GEN_TREES_H) || !defined(STDC) | 241 #if defined(GEN_TREES_H) || !defined(STDC) |
241 static int static_init_done = 0; | 242 static int static_init_done = 0; |
242 int n; /* iterates over tree elements */ | 243 int n; /* iterates over tree elements */ |
243 int bits; /* bit counter */ | 244 int bits; /* bit counter */ |
244 int length; /* length value */ | 245 int length; /* length value */ |
245 int code; /* code value */ | 246 int code; /* code value */ |
246 int dist; /* distance index */ | 247 int dist; /* distance index */ |
247 ush bl_count[MAX_BITS+1]; | 248 ush bl_count[MAX_BITS+1]; |
248 /* number of codes at each bit length for an optimal tree */ | 249 /* number of codes at each bit length for an optimal tree */ |
249 | 250 |
250 if (static_init_done) return; | 251 if (static_init_done) return; |
251 | 252 |
252 /* For some embedded targets, global variables are not initialized: */ | 253 /* For some embedded targets, global variables are not initialized: */ |
| 254 #ifdef NO_INIT_GLOBAL_POINTERS |
253 static_l_desc.static_tree = static_ltree; | 255 static_l_desc.static_tree = static_ltree; |
254 static_l_desc.extra_bits = extra_lbits; | 256 static_l_desc.extra_bits = extra_lbits; |
255 static_d_desc.static_tree = static_dtree; | 257 static_d_desc.static_tree = static_dtree; |
256 static_d_desc.extra_bits = extra_dbits; | 258 static_d_desc.extra_bits = extra_dbits; |
257 static_bl_desc.extra_bits = extra_blbits; | 259 static_bl_desc.extra_bits = extra_blbits; |
| 260 #endif |
258 | 261 |
259 /* Initialize the mapping length (0..255) -> length code (0..28) */ | 262 /* Initialize the mapping length (0..255) -> length code (0..28) */ |
260 length = 0; | 263 length = 0; |
261 for (code = 0; code < LENGTH_CODES-1; code++) { | 264 for (code = 0; code < LENGTH_CODES-1; code++) { |
262 base_length[code] = length; | 265 base_length[code] = length; |
263 for (n = 0; n < (1<<extra_lbits[code]); n++) { | 266 for (n = 0; n < (1<<extra_lbits[code]); n++) { |
264 _length_code[length++] = (uch)code; | 267 _length_code[length++] = (uch)code; |
265 } | 268 } |
266 } | 269 } |
267 Assert (length == 256, "tr_static_init: length != 256"); | 270 Assert (length == 256, "tr_static_init: length != 256"); |
(...skipping 73 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
341 fprintf(header, "{{%3u},{%3u}}%s", static_ltree[i].Code, | 344 fprintf(header, "{{%3u},{%3u}}%s", static_ltree[i].Code, |
342 static_ltree[i].Len, SEPARATOR(i, L_CODES+1, 5)); | 345 static_ltree[i].Len, SEPARATOR(i, L_CODES+1, 5)); |
343 } | 346 } |
344 | 347 |
345 fprintf(header, "local const ct_data static_dtree[D_CODES] = {\n"); | 348 fprintf(header, "local const ct_data static_dtree[D_CODES] = {\n"); |
346 for (i = 0; i < D_CODES; i++) { | 349 for (i = 0; i < D_CODES; i++) { |
347 fprintf(header, "{{%2u},{%2u}}%s", static_dtree[i].Code, | 350 fprintf(header, "{{%2u},{%2u}}%s", static_dtree[i].Code, |
348 static_dtree[i].Len, SEPARATOR(i, D_CODES-1, 5)); | 351 static_dtree[i].Len, SEPARATOR(i, D_CODES-1, 5)); |
349 } | 352 } |
350 | 353 |
351 fprintf(header, "const uch _dist_code[DIST_CODE_LEN] = {\n"); | 354 fprintf(header, "const uch ZLIB_INTERNAL _dist_code[DIST_CODE_LEN] = {\n"); |
352 for (i = 0; i < DIST_CODE_LEN; i++) { | 355 for (i = 0; i < DIST_CODE_LEN; i++) { |
353 fprintf(header, "%2u%s", _dist_code[i], | 356 fprintf(header, "%2u%s", _dist_code[i], |
354 SEPARATOR(i, DIST_CODE_LEN-1, 20)); | 357 SEPARATOR(i, DIST_CODE_LEN-1, 20)); |
355 } | 358 } |
356 | 359 |
357 fprintf(header, "const uch _length_code[MAX_MATCH-MIN_MATCH+1]= {\n"); | 360 fprintf(header, |
| 361 "const uch ZLIB_INTERNAL _length_code[MAX_MATCH-MIN_MATCH+1]= {\n"); |
358 for (i = 0; i < MAX_MATCH-MIN_MATCH+1; i++) { | 362 for (i = 0; i < MAX_MATCH-MIN_MATCH+1; i++) { |
359 fprintf(header, "%2u%s", _length_code[i], | 363 fprintf(header, "%2u%s", _length_code[i], |
360 SEPARATOR(i, MAX_MATCH-MIN_MATCH, 20)); | 364 SEPARATOR(i, MAX_MATCH-MIN_MATCH, 20)); |
361 } | 365 } |
362 | 366 |
363 fprintf(header, "local const int base_length[LENGTH_CODES] = {\n"); | 367 fprintf(header, "local const int base_length[LENGTH_CODES] = {\n"); |
364 for (i = 0; i < LENGTH_CODES; i++) { | 368 for (i = 0; i < LENGTH_CODES; i++) { |
365 fprintf(header, "%1u%s", base_length[i], | 369 fprintf(header, "%1u%s", base_length[i], |
366 SEPARATOR(i, LENGTH_CODES-1, 20)); | 370 SEPARATOR(i, LENGTH_CODES-1, 20)); |
367 } | 371 } |
368 | 372 |
369 fprintf(header, "local const int base_dist[D_CODES] = {\n"); | 373 fprintf(header, "local const int base_dist[D_CODES] = {\n"); |
370 for (i = 0; i < D_CODES; i++) { | 374 for (i = 0; i < D_CODES; i++) { |
371 fprintf(header, "%5u%s", base_dist[i], | 375 fprintf(header, "%5u%s", base_dist[i], |
372 SEPARATOR(i, D_CODES-1, 10)); | 376 SEPARATOR(i, D_CODES-1, 10)); |
373 } | 377 } |
374 | 378 |
375 fclose(header); | 379 fclose(header); |
376 } | 380 } |
377 #endif /* GEN_TREES_H */ | 381 #endif /* GEN_TREES_H */ |
378 | 382 |
379 /* =========================================================================== | 383 /* =========================================================================== |
380 * Initialize the tree data structures for a new zlib stream. | 384 * Initialize the tree data structures for a new zlib stream. |
381 */ | 385 */ |
382 void _tr_init(s) | 386 void ZLIB_INTERNAL _tr_init(s) |
383 deflate_state *s; | 387 deflate_state *s; |
384 { | 388 { |
385 tr_static_init(); | 389 tr_static_init(); |
386 | 390 |
387 s->l_desc.dyn_tree = s->dyn_ltree; | 391 s->l_desc.dyn_tree = s->dyn_ltree; |
388 s->l_desc.stat_desc = &static_l_desc; | 392 s->l_desc.stat_desc = &static_l_desc; |
389 | 393 |
390 s->d_desc.dyn_tree = s->dyn_dtree; | 394 s->d_desc.dyn_tree = s->dyn_dtree; |
391 s->d_desc.stat_desc = &static_d_desc; | 395 s->d_desc.stat_desc = &static_d_desc; |
392 | 396 |
(...skipping 464 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
857 send_tree(s, (ct_data *)s->dyn_ltree, lcodes-1); /* literal tree */ | 861 send_tree(s, (ct_data *)s->dyn_ltree, lcodes-1); /* literal tree */ |
858 Tracev((stderr, "\nlit tree: sent %ld", s->bits_sent)); | 862 Tracev((stderr, "\nlit tree: sent %ld", s->bits_sent)); |
859 | 863 |
860 send_tree(s, (ct_data *)s->dyn_dtree, dcodes-1); /* distance tree */ | 864 send_tree(s, (ct_data *)s->dyn_dtree, dcodes-1); /* distance tree */ |
861 Tracev((stderr, "\ndist tree: sent %ld", s->bits_sent)); | 865 Tracev((stderr, "\ndist tree: sent %ld", s->bits_sent)); |
862 } | 866 } |
863 | 867 |
864 /* =========================================================================== | 868 /* =========================================================================== |
865 * Send a stored block | 869 * Send a stored block |
866 */ | 870 */ |
867 void _tr_stored_block(s, buf, stored_len, eof) | 871 void ZLIB_INTERNAL _tr_stored_block(s, buf, stored_len, last) |
868 deflate_state *s; | 872 deflate_state *s; |
869 charf *buf; /* input block */ | 873 charf *buf; /* input block */ |
870 ulg stored_len; /* length of input block */ | 874 ulg stored_len; /* length of input block */ |
871 int eof; /* true if this is the last block for a file */ | 875 int last; /* one if this is the last block for a file */ |
872 { | 876 { |
873 send_bits(s, (STORED_BLOCK<<1)+eof, 3); /* send block type */ | 877 send_bits(s, (STORED_BLOCK<<1)+last, 3); /* send block type */ |
874 #ifdef DEBUG | 878 #ifdef DEBUG |
875 s->compressed_len = (s->compressed_len + 3 + 7) & (ulg)~7L; | 879 s->compressed_len = (s->compressed_len + 3 + 7) & (ulg)~7L; |
876 s->compressed_len += (stored_len + 4) << 3; | 880 s->compressed_len += (stored_len + 4) << 3; |
877 #endif | 881 #endif |
878 copy_block(s, buf, (unsigned)stored_len, 1); /* with header */ | 882 copy_block(s, buf, (unsigned)stored_len, 1); /* with header */ |
879 } | 883 } |
880 | 884 |
881 /* =========================================================================== | 885 /* =========================================================================== |
882 * Send one empty static block to give enough lookahead for inflate. | 886 * Send one empty static block to give enough lookahead for inflate. |
883 * This takes 10 bits, of which 7 may remain in the bit buffer. | 887 * This takes 10 bits, of which 7 may remain in the bit buffer. |
884 * The current inflate code requires 9 bits of lookahead. If the | 888 * The current inflate code requires 9 bits of lookahead. If the |
885 * last two codes for the previous block (real code plus EOB) were coded | 889 * last two codes for the previous block (real code plus EOB) were coded |
886 * on 5 bits or less, inflate may have only 5+3 bits of lookahead to decode | 890 * on 5 bits or less, inflate may have only 5+3 bits of lookahead to decode |
887 * the last real code. In this case we send two empty static blocks instead | 891 * the last real code. In this case we send two empty static blocks instead |
888 * of one. (There are no problems if the previous block is stored or fixed.) | 892 * of one. (There are no problems if the previous block is stored or fixed.) |
889 * To simplify the code, we assume the worst case of last real code encoded | 893 * To simplify the code, we assume the worst case of last real code encoded |
890 * on one bit only. | 894 * on one bit only. |
891 */ | 895 */ |
892 void _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 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 /* Of the 10 bits for the empty block, we have already sent | 905 /* Of the 10 bits for the empty block, we have already sent |
902 * (10 - bi_valid) bits. The lookahead for the last real code (before | 906 * (10 - bi_valid) bits. The lookahead for the last real code (before |
903 * the EOB of the previous block) was thus at least one plus the length | 907 * the EOB of the previous block) was thus at least one plus the length |
904 * of the EOB plus what we have just sent of the empty static block. | 908 * of the EOB plus what we have just sent of the empty static block. |
905 */ | 909 */ |
906 if (1 + s->last_eob_len + 10 - s->bi_valid < 9) { | 910 if (1 + s->last_eob_len + 10 - s->bi_valid < 9) { |
907 send_bits(s, STATIC_TREES<<1, 3); | 911 send_bits(s, STATIC_TREES<<1, 3); |
908 send_code(s, END_BLOCK, static_ltree); | 912 send_code(s, END_BLOCK, static_ltree); |
909 #ifdef DEBUG | 913 #ifdef DEBUG |
910 s->compressed_len += 10L; | 914 s->compressed_len += 10L; |
911 #endif | 915 #endif |
912 bi_flush(s); | 916 bi_flush(s); |
913 } | 917 } |
914 s->last_eob_len = 7; | 918 s->last_eob_len = 7; |
915 } | 919 } |
916 | 920 |
917 /* =========================================================================== | 921 /* =========================================================================== |
918 * Determine the best encoding for the current block: dynamic trees, static | 922 * Determine the best encoding for the current block: dynamic trees, static |
919 * trees or store, and output the encoded block to the zip file. | 923 * trees or store, and output the encoded block to the zip file. |
920 */ | 924 */ |
921 void _tr_flush_block(s, buf, stored_len, eof) | 925 void ZLIB_INTERNAL _tr_flush_block(s, buf, stored_len, last) |
922 deflate_state *s; | 926 deflate_state *s; |
923 charf *buf; /* input block, or NULL if too old */ | 927 charf *buf; /* input block, or NULL if too old */ |
924 ulg stored_len; /* length of input block */ | 928 ulg stored_len; /* length of input block */ |
925 int eof; /* true if this is the last block for a file */ | 929 int last; /* one if this is the last block for a file */ |
926 { | 930 { |
927 ulg opt_lenb, static_lenb; /* opt_len and static_len in bytes */ | 931 ulg opt_lenb, static_lenb; /* opt_len and static_len in bytes */ |
928 int max_blindex = 0; /* index of last bit length code of non zero freq */ | 932 int max_blindex = 0; /* index of last bit length code of non zero freq */ |
929 | 933 |
930 /* Build the Huffman trees unless a stored block is forced */ | 934 /* Build the Huffman trees unless a stored block is forced */ |
931 if (s->level > 0) { | 935 if (s->level > 0) { |
932 | 936 |
933 /* Check if the file is binary or text */ | 937 /* Check if the file is binary or text */ |
934 if (stored_len > 0 && s->strm->data_type == Z_UNKNOWN) | 938 if (s->strm->data_type == Z_UNKNOWN) |
935 set_data_type(s); | 939 s->strm->data_type = detect_data_type(s); |
936 | 940 |
937 /* Construct the literal and distance trees */ | 941 /* Construct the literal and distance trees */ |
938 build_tree(s, (tree_desc *)(&(s->l_desc))); | 942 build_tree(s, (tree_desc *)(&(s->l_desc))); |
939 Tracev((stderr, "\nlit data: dyn %ld, stat %ld", s->opt_len, | 943 Tracev((stderr, "\nlit data: dyn %ld, stat %ld", s->opt_len, |
940 s->static_len)); | 944 s->static_len)); |
941 | 945 |
942 build_tree(s, (tree_desc *)(&(s->d_desc))); | 946 build_tree(s, (tree_desc *)(&(s->d_desc))); |
943 Tracev((stderr, "\ndist data: dyn %ld, stat %ld", s->opt_len, | 947 Tracev((stderr, "\ndist data: dyn %ld, stat %ld", s->opt_len, |
944 s->static_len)); | 948 s->static_len)); |
945 /* At this point, opt_len and static_len are the total bit lengths of | 949 /* At this point, opt_len and static_len are the total bit lengths of |
(...skipping 25 matching lines...) Expand all Loading... |
971 #else | 975 #else |
972 if (stored_len+4 <= opt_lenb && buf != (char*)0) { | 976 if (stored_len+4 <= opt_lenb && buf != (char*)0) { |
973 /* 4: two words for the lengths */ | 977 /* 4: two words for the lengths */ |
974 #endif | 978 #endif |
975 /* The test buf != NULL is only necessary if LIT_BUFSIZE > WSIZE. | 979 /* The test buf != NULL is only necessary if LIT_BUFSIZE > WSIZE. |
976 * Otherwise we can't have processed more than WSIZE input bytes since | 980 * Otherwise we can't have processed more than WSIZE input bytes since |
977 * the last block flush, because compression would have been | 981 * the last block flush, because compression would have been |
978 * successful. If LIT_BUFSIZE <= WSIZE, it is never too late to | 982 * successful. If LIT_BUFSIZE <= WSIZE, it is never too late to |
979 * transform a block into a stored block. | 983 * transform a block into a stored block. |
980 */ | 984 */ |
981 _tr_stored_block(s, buf, stored_len, eof); | 985 _tr_stored_block(s, buf, stored_len, last); |
982 | 986 |
983 #ifdef FORCE_STATIC | 987 #ifdef FORCE_STATIC |
984 } else if (static_lenb >= 0) { /* force static trees */ | 988 } else if (static_lenb >= 0) { /* force static trees */ |
985 #else | 989 #else |
986 } else if (s->strategy == Z_FIXED || static_lenb == opt_lenb) { | 990 } else if (s->strategy == Z_FIXED || static_lenb == opt_lenb) { |
987 #endif | 991 #endif |
988 send_bits(s, (STATIC_TREES<<1)+eof, 3); | 992 send_bits(s, (STATIC_TREES<<1)+last, 3); |
989 compress_block(s, (ct_data *)static_ltree, (ct_data *)static_dtree); | 993 compress_block(s, (ct_data *)static_ltree, (ct_data *)static_dtree); |
990 #ifdef DEBUG | 994 #ifdef DEBUG |
991 s->compressed_len += 3 + s->static_len; | 995 s->compressed_len += 3 + s->static_len; |
992 #endif | 996 #endif |
993 } else { | 997 } else { |
994 send_bits(s, (DYN_TREES<<1)+eof, 3); | 998 send_bits(s, (DYN_TREES<<1)+last, 3); |
995 send_all_trees(s, s->l_desc.max_code+1, s->d_desc.max_code+1, | 999 send_all_trees(s, s->l_desc.max_code+1, s->d_desc.max_code+1, |
996 max_blindex+1); | 1000 max_blindex+1); |
997 compress_block(s, (ct_data *)s->dyn_ltree, (ct_data *)s->dyn_dtree); | 1001 compress_block(s, (ct_data *)s->dyn_ltree, (ct_data *)s->dyn_dtree); |
998 #ifdef DEBUG | 1002 #ifdef DEBUG |
999 s->compressed_len += 3 + s->opt_len; | 1003 s->compressed_len += 3 + s->opt_len; |
1000 #endif | 1004 #endif |
1001 } | 1005 } |
1002 Assert (s->compressed_len == s->bits_sent, "bad compressed size"); | 1006 Assert (s->compressed_len == s->bits_sent, "bad compressed size"); |
1003 /* The above check is made mod 2^32, for files larger than 512 MB | 1007 /* The above check is made mod 2^32, for files larger than 512 MB |
1004 * and uLong implemented on 32 bits. | 1008 * and uLong implemented on 32 bits. |
1005 */ | 1009 */ |
1006 init_block(s); | 1010 init_block(s); |
1007 | 1011 |
1008 if (eof) { | 1012 if (last) { |
1009 bi_windup(s); | 1013 bi_windup(s); |
1010 #ifdef DEBUG | 1014 #ifdef DEBUG |
1011 s->compressed_len += 7; /* align on byte boundary */ | 1015 s->compressed_len += 7; /* align on byte boundary */ |
1012 #endif | 1016 #endif |
1013 } | 1017 } |
1014 Tracev((stderr,"\ncomprlen %lu(%lu) ", s->compressed_len>>3, | 1018 Tracev((stderr,"\ncomprlen %lu(%lu) ", s->compressed_len>>3, |
1015 s->compressed_len-7*eof)); | 1019 s->compressed_len-7*last)); |
1016 } | 1020 } |
1017 | 1021 |
1018 /* =========================================================================== | 1022 /* =========================================================================== |
1019 * Save the match info and tally the frequency counts. Return true if | 1023 * Save the match info and tally the frequency counts. Return true if |
1020 * the current block must be flushed. | 1024 * the current block must be flushed. |
1021 */ | 1025 */ |
1022 int _tr_tally (s, dist, lc) | 1026 int ZLIB_INTERNAL _tr_tally (s, dist, lc) |
1023 deflate_state *s; | 1027 deflate_state *s; |
1024 unsigned dist; /* distance of matched string */ | 1028 unsigned dist; /* distance of matched string */ |
1025 unsigned lc; /* match length-MIN_MATCH or unmatched char (if dist==0) */ | 1029 unsigned lc; /* match length-MIN_MATCH or unmatched char (if dist==0) */ |
1026 { | 1030 { |
1027 s->d_buf[s->last_lit] = (ush)dist; | 1031 s->d_buf[s->last_lit] = (ush)dist; |
1028 s->l_buf[s->last_lit++] = (uch)lc; | 1032 s->l_buf[s->last_lit++] = (uch)lc; |
1029 if (dist == 0) { | 1033 if (dist == 0) { |
1030 /* lc is the unmatched char */ | 1034 /* lc is the unmatched char */ |
1031 s->dyn_ltree[lc].Freq++; | 1035 s->dyn_ltree[lc].Freq++; |
1032 } else { | 1036 } else { |
(...skipping 78 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1111 Assert((uInt)(s->pending) < s->lit_bufsize + 2*lx, | 1115 Assert((uInt)(s->pending) < s->lit_bufsize + 2*lx, |
1112 "pendingBuf overflow"); | 1116 "pendingBuf overflow"); |
1113 | 1117 |
1114 } while (lx < s->last_lit); | 1118 } while (lx < s->last_lit); |
1115 | 1119 |
1116 send_code(s, END_BLOCK, ltree); | 1120 send_code(s, END_BLOCK, ltree); |
1117 s->last_eob_len = ltree[END_BLOCK].Len; | 1121 s->last_eob_len = ltree[END_BLOCK].Len; |
1118 } | 1122 } |
1119 | 1123 |
1120 /* =========================================================================== | 1124 /* =========================================================================== |
1121 * Set the data type to BINARY or TEXT, using a crude approximation: | 1125 * Check if the data type is TEXT or BINARY, using the following algorithm: |
1122 * set it to Z_TEXT if all symbols are either printable characters (33 to 255) | 1126 * - TEXT if the two conditions below are satisfied: |
1123 * or white spaces (9 to 13, or 32); or set it to Z_BINARY otherwise. | 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}). |
1124 * IN assertion: the fields Freq of dyn_ltree are set. | 1135 * IN assertion: the fields Freq of dyn_ltree are set. |
1125 */ | 1136 */ |
1126 local void set_data_type(s) | 1137 local int detect_data_type(s) |
1127 deflate_state *s; | 1138 deflate_state *s; |
1128 { | 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; |
1129 int n; | 1145 int n; |
1130 | 1146 |
1131 for (n = 0; n < 9; n++) | 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++) |
1132 if (s->dyn_ltree[n].Freq != 0) | 1157 if (s->dyn_ltree[n].Freq != 0) |
1133 break; | 1158 return Z_TEXT; |
1134 if (n == 9) | 1159 |
1135 for (n = 14; n < 32; n++) | 1160 /* There are no "black-listed" or "white-listed" bytes: |
1136 if (s->dyn_ltree[n].Freq != 0) | 1161 * this stream either is empty or has tolerated ("gray-listed") bytes only. |
1137 break; | 1162 */ |
1138 s->strm->data_type = (n == 32) ? Z_TEXT : Z_BINARY; | 1163 return Z_BINARY; |
1139 } | 1164 } |
1140 | 1165 |
1141 /* =========================================================================== | 1166 /* =========================================================================== |
1142 * Reverse the first len bits of a code, using straightforward code (a faster | 1167 * Reverse the first len bits of a code, using straightforward code (a faster |
1143 * method would use a table) | 1168 * method would use a table) |
1144 * IN assertion: 1 <= len <= 15 | 1169 * IN assertion: 1 <= len <= 15 |
1145 */ | 1170 */ |
1146 local unsigned bi_reverse(code, len) | 1171 local unsigned bi_reverse(code, len) |
1147 unsigned code; /* the value to invert */ | 1172 unsigned code; /* the value to invert */ |
1148 int len; /* its bit length */ | 1173 int len; /* its bit length */ |
(...skipping 61 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1210 s->bits_sent += 2*16; | 1235 s->bits_sent += 2*16; |
1211 #endif | 1236 #endif |
1212 } | 1237 } |
1213 #ifdef DEBUG | 1238 #ifdef DEBUG |
1214 s->bits_sent += (ulg)len<<3; | 1239 s->bits_sent += (ulg)len<<3; |
1215 #endif | 1240 #endif |
1216 while (len--) { | 1241 while (len--) { |
1217 put_byte(s, *buf++); | 1242 put_byte(s, *buf++); |
1218 } | 1243 } |
1219 } | 1244 } |
OLD | NEW |