Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(1)

Side by Side Diff: third_party/zlib/trees.c

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

Powered by Google App Engine
This is Rietveld 408576698