OLD | NEW |
1 /* trees.c -- output deflated data using Huffman coding | 1 /* trees.c -- output deflated data using Huffman coding |
2 * Copyright (C) 1995-2010 Jean-loup Gailly | 2 * Copyright (C) 1995-2012 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 54 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
67 | 67 |
68 local const int extra_blbits[BL_CODES]/* extra bits for each bit length code */ | 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}; | 69 = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,3,7}; |
70 | 70 |
71 local const uch bl_order[BL_CODES] | 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}; | 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 | 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. | 74 * probability, to avoid transmitting the lengths for unused bit length codes. |
75 */ | 75 */ |
76 | 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 /* =========================================================================== | 77 /* =========================================================================== |
83 * Local data. These are initialized only once. | 78 * Local data. These are initialized only once. |
84 */ | 79 */ |
85 | 80 |
86 #define DIST_CODE_LEN 512 /* see definition of array dist_code below */ | 81 #define DIST_CODE_LEN 512 /* see definition of array dist_code below */ |
87 | 82 |
88 #if defined(GEN_TREES_H) || !defined(STDC) | 83 #if defined(GEN_TREES_H) || !defined(STDC) |
89 /* non ANSI compilers may not accept trees.h */ | 84 /* non ANSI compilers may not accept trees.h */ |
90 | 85 |
91 local ct_data static_ltree[L_CODES+2]; | 86 local ct_data static_ltree[L_CODES+2]; |
(...skipping 52 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
144 local void init_block OF((deflate_state *s)); | 139 local void init_block OF((deflate_state *s)); |
145 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)); |
146 local void gen_bitlen OF((deflate_state *s, tree_desc *desc)); | 141 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)); | 142 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)); | 143 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)); | 144 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)); | 145 local void send_tree OF((deflate_state *s, ct_data *tree, int max_code)); |
151 local int build_bl_tree OF((deflate_state *s)); | 146 local int build_bl_tree OF((deflate_state *s)); |
152 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, |
153 int blcodes)); | 148 int blcodes)); |
154 local void compress_block OF((deflate_state *s, ct_data *ltree, | 149 local void compress_block OF((deflate_state *s, const ct_data *ltree, |
155 ct_data *dtree)); | 150 const ct_data *dtree)); |
156 local int detect_data_type OF((deflate_state *s)); | 151 local int detect_data_type OF((deflate_state *s)); |
157 local unsigned bi_reverse OF((unsigned value, int length)); | 152 local unsigned bi_reverse OF((unsigned value, int length)); |
158 local void bi_windup OF((deflate_state *s)); | 153 local void bi_windup OF((deflate_state *s)); |
159 local void bi_flush OF((deflate_state *s)); | 154 local void bi_flush OF((deflate_state *s)); |
160 local void copy_block OF((deflate_state *s, charf *buf, unsigned len, | 155 local void copy_block OF((deflate_state *s, charf *buf, unsigned len, |
161 int header)); | 156 int header)); |
162 | 157 |
163 #ifdef GEN_TREES_H | 158 #ifdef GEN_TREES_H |
164 local void gen_trees_header OF((void)); | 159 local void gen_trees_header OF((void)); |
165 #endif | 160 #endif |
(...skipping 226 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
392 s->l_desc.stat_desc = &static_l_desc; | 387 s->l_desc.stat_desc = &static_l_desc; |
393 | 388 |
394 s->d_desc.dyn_tree = s->dyn_dtree; | 389 s->d_desc.dyn_tree = s->dyn_dtree; |
395 s->d_desc.stat_desc = &static_d_desc; | 390 s->d_desc.stat_desc = &static_d_desc; |
396 | 391 |
397 s->bl_desc.dyn_tree = s->bl_tree; | 392 s->bl_desc.dyn_tree = s->bl_tree; |
398 s->bl_desc.stat_desc = &static_bl_desc; | 393 s->bl_desc.stat_desc = &static_bl_desc; |
399 | 394 |
400 s->bi_buf = 0; | 395 s->bi_buf = 0; |
401 s->bi_valid = 0; | 396 s->bi_valid = 0; |
402 s->last_eob_len = 8; /* enough lookahead for inflate */ | |
403 #ifdef DEBUG | 397 #ifdef DEBUG |
404 s->compressed_len = 0L; | 398 s->compressed_len = 0L; |
405 s->bits_sent = 0L; | 399 s->bits_sent = 0L; |
406 #endif | 400 #endif |
407 | 401 |
408 /* Initialize the first block of the first file: */ | 402 /* Initialize the first block of the first file: */ |
409 init_block(s); | 403 init_block(s); |
410 } | 404 } |
411 | 405 |
412 /* =========================================================================== | 406 /* =========================================================================== |
(...skipping 463 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
876 { | 870 { |
877 send_bits(s, (STORED_BLOCK<<1)+last, 3); /* send block type */ | 871 send_bits(s, (STORED_BLOCK<<1)+last, 3); /* send block type */ |
878 #ifdef DEBUG | 872 #ifdef DEBUG |
879 s->compressed_len = (s->compressed_len + 3 + 7) & (ulg)~7L; | 873 s->compressed_len = (s->compressed_len + 3 + 7) & (ulg)~7L; |
880 s->compressed_len += (stored_len + 4) << 3; | 874 s->compressed_len += (stored_len + 4) << 3; |
881 #endif | 875 #endif |
882 copy_block(s, buf, (unsigned)stored_len, 1); /* with header */ | 876 copy_block(s, buf, (unsigned)stored_len, 1); /* with header */ |
883 } | 877 } |
884 | 878 |
885 /* =========================================================================== | 879 /* =========================================================================== |
| 880 * Flush the bits in the bit buffer to pending output (leaves at most 7 bits) |
| 881 */ |
| 882 void ZLIB_INTERNAL _tr_flush_bits(s) |
| 883 deflate_state *s; |
| 884 { |
| 885 bi_flush(s); |
| 886 } |
| 887 |
| 888 /* =========================================================================== |
886 * Send one empty static block to give enough lookahead for inflate. | 889 * 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. | 890 * 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 */ | 891 */ |
896 void ZLIB_INTERNAL _tr_align(s) | 892 void ZLIB_INTERNAL _tr_align(s) |
897 deflate_state *s; | 893 deflate_state *s; |
898 { | 894 { |
899 send_bits(s, STATIC_TREES<<1, 3); | 895 send_bits(s, STATIC_TREES<<1, 3); |
900 send_code(s, END_BLOCK, static_ltree); | 896 send_code(s, END_BLOCK, static_ltree); |
901 #ifdef DEBUG | 897 #ifdef DEBUG |
902 s->compressed_len += 10L; /* 3 for block type, 7 for EOB */ | 898 s->compressed_len += 10L; /* 3 for block type, 7 for EOB */ |
903 #endif | 899 #endif |
904 bi_flush(s); | 900 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 } | 901 } |
920 | 902 |
921 /* =========================================================================== | 903 /* =========================================================================== |
922 * Determine the best encoding for the current block: dynamic trees, static | 904 * Determine the best encoding for the current block: dynamic trees, static |
923 * trees or store, and output the encoded block to the zip file. | 905 * trees or store, and output the encoded block to the zip file. |
924 */ | 906 */ |
925 void ZLIB_INTERNAL _tr_flush_block(s, buf, stored_len, last) | 907 void ZLIB_INTERNAL _tr_flush_block(s, buf, stored_len, last) |
926 deflate_state *s; | 908 deflate_state *s; |
927 charf *buf; /* input block, or NULL if too old */ | 909 charf *buf; /* input block, or NULL if too old */ |
928 ulg stored_len; /* length of input block */ | 910 ulg stored_len; /* length of input block */ |
(...skipping 54 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
983 * transform a block into a stored block. | 965 * transform a block into a stored block. |
984 */ | 966 */ |
985 _tr_stored_block(s, buf, stored_len, last); | 967 _tr_stored_block(s, buf, stored_len, last); |
986 | 968 |
987 #ifdef FORCE_STATIC | 969 #ifdef FORCE_STATIC |
988 } else if (static_lenb >= 0) { /* force static trees */ | 970 } else if (static_lenb >= 0) { /* force static trees */ |
989 #else | 971 #else |
990 } else if (s->strategy == Z_FIXED || static_lenb == opt_lenb) { | 972 } else if (s->strategy == Z_FIXED || static_lenb == opt_lenb) { |
991 #endif | 973 #endif |
992 send_bits(s, (STATIC_TREES<<1)+last, 3); | 974 send_bits(s, (STATIC_TREES<<1)+last, 3); |
993 compress_block(s, (ct_data *)static_ltree, (ct_data *)static_dtree); | 975 compress_block(s, (const ct_data *)static_ltree, |
| 976 (const ct_data *)static_dtree); |
994 #ifdef DEBUG | 977 #ifdef DEBUG |
995 s->compressed_len += 3 + s->static_len; | 978 s->compressed_len += 3 + s->static_len; |
996 #endif | 979 #endif |
997 } else { | 980 } else { |
998 send_bits(s, (DYN_TREES<<1)+last, 3); | 981 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, | 982 send_all_trees(s, s->l_desc.max_code+1, s->d_desc.max_code+1, |
1000 max_blindex+1); | 983 max_blindex+1); |
1001 compress_block(s, (ct_data *)s->dyn_ltree, (ct_data *)s->dyn_dtree); | 984 compress_block(s, (const ct_data *)s->dyn_ltree, |
| 985 (const ct_data *)s->dyn_dtree); |
1002 #ifdef DEBUG | 986 #ifdef DEBUG |
1003 s->compressed_len += 3 + s->opt_len; | 987 s->compressed_len += 3 + s->opt_len; |
1004 #endif | 988 #endif |
1005 } | 989 } |
1006 Assert (s->compressed_len == s->bits_sent, "bad compressed size"); | 990 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 | 991 /* The above check is made mod 2^32, for files larger than 512 MB |
1008 * and uLong implemented on 32 bits. | 992 * and uLong implemented on 32 bits. |
1009 */ | 993 */ |
1010 init_block(s); | 994 init_block(s); |
1011 | 995 |
(...skipping 56 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1068 * on 16 bit machines and because stored blocks are restricted to | 1052 * on 16 bit machines and because stored blocks are restricted to |
1069 * 64K-1 bytes. | 1053 * 64K-1 bytes. |
1070 */ | 1054 */ |
1071 } | 1055 } |
1072 | 1056 |
1073 /* =========================================================================== | 1057 /* =========================================================================== |
1074 * Send the block data compressed using the given Huffman trees | 1058 * Send the block data compressed using the given Huffman trees |
1075 */ | 1059 */ |
1076 local void compress_block(s, ltree, dtree) | 1060 local void compress_block(s, ltree, dtree) |
1077 deflate_state *s; | 1061 deflate_state *s; |
1078 ct_data *ltree; /* literal tree */ | 1062 const ct_data *ltree; /* literal tree */ |
1079 ct_data *dtree; /* distance tree */ | 1063 const ct_data *dtree; /* distance tree */ |
1080 { | 1064 { |
1081 unsigned dist; /* distance of matched string */ | 1065 unsigned dist; /* distance of matched string */ |
1082 int lc; /* match length or unmatched char (if dist == 0) */ | 1066 int lc; /* match length or unmatched char (if dist == 0) */ |
1083 unsigned lx = 0; /* running index in l_buf */ | 1067 unsigned lx = 0; /* running index in l_buf */ |
1084 unsigned code; /* the code to send */ | 1068 unsigned code; /* the code to send */ |
1085 int extra; /* number of extra bits to send */ | 1069 int extra; /* number of extra bits to send */ |
1086 | 1070 |
1087 if (s->last_lit != 0) do { | 1071 if (s->last_lit != 0) do { |
1088 dist = s->d_buf[lx]; | 1072 dist = s->d_buf[lx]; |
1089 lc = s->l_buf[lx++]; | 1073 lc = s->l_buf[lx++]; |
(...skipping 21 matching lines...) Expand all Loading... |
1111 } | 1095 } |
1112 } /* literal or match pair ? */ | 1096 } /* literal or match pair ? */ |
1113 | 1097 |
1114 /* Check that the overlay between pending_buf and d_buf+l_buf is ok: */ | 1098 /* Check that the overlay between pending_buf and d_buf+l_buf is ok: */ |
1115 Assert((uInt)(s->pending) < s->lit_bufsize + 2*lx, | 1099 Assert((uInt)(s->pending) < s->lit_bufsize + 2*lx, |
1116 "pendingBuf overflow"); | 1100 "pendingBuf overflow"); |
1117 | 1101 |
1118 } while (lx < s->last_lit); | 1102 } while (lx < s->last_lit); |
1119 | 1103 |
1120 send_code(s, END_BLOCK, ltree); | 1104 send_code(s, END_BLOCK, ltree); |
1121 s->last_eob_len = ltree[END_BLOCK].Len; | |
1122 } | 1105 } |
1123 | 1106 |
1124 /* =========================================================================== | 1107 /* =========================================================================== |
1125 * Check if the data type is TEXT or BINARY, using the following algorithm: | 1108 * Check if the data type is TEXT or BINARY, using the following algorithm: |
1126 * - TEXT if the two conditions below are satisfied: | 1109 * - TEXT if the two conditions below are satisfied: |
1127 * a) There are no non-portable control characters belonging to the | 1110 * a) There are no non-portable control characters belonging to the |
1128 * "black list" (0..6, 14..25, 28..31). | 1111 * "black list" (0..6, 14..25, 28..31). |
1129 * b) There is at least one printable character belonging to the | 1112 * b) There is at least one printable character belonging to the |
1130 * "white list" (9 {TAB}, 10 {LF}, 13 {CR}, 32..255). | 1113 * "white list" (9 {TAB}, 10 {LF}, 13 {CR}, 32..255). |
1131 * - BINARY otherwise. | 1114 * - BINARY otherwise. |
(...skipping 87 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1219 * Copy a stored block, storing first the length and its | 1202 * Copy a stored block, storing first the length and its |
1220 * one's complement if requested. | 1203 * one's complement if requested. |
1221 */ | 1204 */ |
1222 local void copy_block(s, buf, len, header) | 1205 local void copy_block(s, buf, len, header) |
1223 deflate_state *s; | 1206 deflate_state *s; |
1224 charf *buf; /* the input data */ | 1207 charf *buf; /* the input data */ |
1225 unsigned len; /* its length */ | 1208 unsigned len; /* its length */ |
1226 int header; /* true if block header must be written */ | 1209 int header; /* true if block header must be written */ |
1227 { | 1210 { |
1228 bi_windup(s); /* align on byte boundary */ | 1211 bi_windup(s); /* align on byte boundary */ |
1229 s->last_eob_len = 8; /* enough lookahead for inflate */ | |
1230 | 1212 |
1231 if (header) { | 1213 if (header) { |
1232 put_short(s, (ush)len); | 1214 put_short(s, (ush)len); |
1233 put_short(s, (ush)~len); | 1215 put_short(s, (ush)~len); |
1234 #ifdef DEBUG | 1216 #ifdef DEBUG |
1235 s->bits_sent += 2*16; | 1217 s->bits_sent += 2*16; |
1236 #endif | 1218 #endif |
1237 } | 1219 } |
1238 #ifdef DEBUG | 1220 #ifdef DEBUG |
1239 s->bits_sent += (ulg)len<<3; | 1221 s->bits_sent += (ulg)len<<3; |
1240 #endif | 1222 #endif |
1241 while (len--) { | 1223 while (len--) { |
1242 put_byte(s, *buf++); | 1224 put_byte(s, *buf++); |
1243 } | 1225 } |
1244 } | 1226 } |
OLD | NEW |