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

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

Issue 1955383002: Update Zlib to version 1.2.8 (Closed) Base URL: https://chromium.googlesource.com/chromium/src.git@master
Patch Set: fix unzip on win platform 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/inflate.c ('k') | third_party/zlib/mixed-source.patch » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
1 /* inftrees.c -- generate Huffman trees for efficient decoding 1 /* inftrees.c -- generate Huffman trees for efficient decoding
2 * Copyright (C) 1995-2010 Mark Adler 2 * Copyright (C) 1995-2013 Mark Adler
3 * For conditions of distribution and use, see copyright notice in zlib.h 3 * For conditions of distribution and use, see copyright notice in zlib.h
4 */ 4 */
5 5
6 #include "zutil.h" 6 #include "zutil.h"
7 #include "inftrees.h" 7 #include "inftrees.h"
8 8
9 #define MAXBITS 15 9 #define MAXBITS 15
10 10
11 const char inflate_copyright[] = 11 const char inflate_copyright[] =
12 " inflate 1.2.5 Copyright 1995-2010 Mark Adler "; 12 " inflate 1.2.8 Copyright 1995-2013 Mark Adler ";
13 /* 13 /*
14 If you use the zlib library in a product, an acknowledgment is welcome 14 If you use the zlib library in a product, an acknowledgment is welcome
15 in the documentation of your product. If for some reason you cannot 15 in the documentation of your product. If for some reason you cannot
16 include such an acknowledgment, I would appreciate that you keep this 16 include such an acknowledgment, I would appreciate that you keep this
17 copyright string in the executable of your product. 17 copyright string in the executable of your product.
18 */ 18 */
19 19
20 /* 20 /*
21 Build a set of tables to decode the provided canonical Huffman code. 21 Build a set of tables to decode the provided canonical Huffman code.
22 The code lengths are lens[0..codes-1]. The result starts at *table, 22 The code lengths are lens[0..codes-1]. The result starts at *table,
(...skipping 32 matching lines...) Expand 10 before | Expand all | Expand 10 after
55 const unsigned short FAR *base; /* base value table to use */ 55 const unsigned short FAR *base; /* base value table to use */
56 const unsigned short FAR *extra; /* extra bits table to use */ 56 const unsigned short FAR *extra; /* extra bits table to use */
57 int end; /* use base and extra for symbol > end */ 57 int end; /* use base and extra for symbol > end */
58 unsigned short count[MAXBITS+1]; /* number of codes of each length */ 58 unsigned short count[MAXBITS+1]; /* number of codes of each length */
59 unsigned short offs[MAXBITS+1]; /* offsets in table for each length */ 59 unsigned short offs[MAXBITS+1]; /* offsets in table for each length */
60 static const unsigned short lbase[31] = { /* Length codes 257..285 base */ 60 static const unsigned short lbase[31] = { /* Length codes 257..285 base */
61 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, 61 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
62 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0}; 62 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0};
63 static const unsigned short lext[31] = { /* Length codes 257..285 extra */ 63 static const unsigned short lext[31] = { /* Length codes 257..285 extra */
64 16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, 18, 18, 18, 18, 64 16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, 18, 18, 18, 18,
65 19, 19, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21, 16, 73, 195}; 65 19, 19, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21, 16, 72, 78};
66 static const unsigned short dbase[32] = { /* Distance codes 0..29 base */ 66 static const unsigned short dbase[32] = { /* Distance codes 0..29 base */
67 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 67 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
68 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145, 68 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
69 8193, 12289, 16385, 24577, 0, 0}; 69 8193, 12289, 16385, 24577, 0, 0};
70 static const unsigned short dext[32] = { /* Distance codes 0..29 extra */ 70 static const unsigned short dext[32] = { /* Distance codes 0..29 extra */
71 16, 16, 16, 16, 17, 17, 18, 18, 19, 19, 20, 20, 21, 21, 22, 22, 71 16, 16, 16, 16, 17, 17, 18, 18, 19, 19, 20, 20, 21, 21, 22, 22,
72 23, 23, 24, 24, 25, 25, 26, 26, 27, 27, 72 23, 23, 24, 24, 25, 25, 26, 26, 27, 27,
73 28, 28, 29, 29, 64, 64}; 73 28, 28, 29, 29, 64, 64};
74 74
75 /* 75 /*
(...skipping 125 matching lines...) Expand 10 before | Expand all | Expand 10 after
201 sym = 0; /* starting code symbol */ 201 sym = 0; /* starting code symbol */
202 len = min; /* starting code length */ 202 len = min; /* starting code length */
203 next = *table; /* current table to fill in */ 203 next = *table; /* current table to fill in */
204 curr = root; /* current table index bits */ 204 curr = root; /* current table index bits */
205 drop = 0; /* current bits to drop from code for index */ 205 drop = 0; /* current bits to drop from code for index */
206 low = (unsigned)(-1); /* trigger new sub-table when len > root */ 206 low = (unsigned)(-1); /* trigger new sub-table when len > root */
207 used = 1U << root; /* use root table entries */ 207 used = 1U << root; /* use root table entries */
208 mask = used - 1; /* mask for comparing low */ 208 mask = used - 1; /* mask for comparing low */
209 209
210 /* check available table space */ 210 /* check available table space */
211 if ((type == LENS && used >= ENOUGH_LENS) || 211 if ((type == LENS && used > ENOUGH_LENS) ||
212 (type == DISTS && used >= ENOUGH_DISTS)) 212 (type == DISTS && used > ENOUGH_DISTS))
213 return 1; 213 return 1;
214 214
215 /* process all codes and make table entries */ 215 /* process all codes and make table entries */
216 for (;;) { 216 for (;;) {
217 /* create table entry */ 217 /* create table entry */
218 here.bits = (unsigned char)(len - drop); 218 here.bits = (unsigned char)(len - drop);
219 if ((int)(work[sym]) < end) { 219 if ((int)(work[sym]) < end) {
220 here.op = (unsigned char)0; 220 here.op = (unsigned char)0;
221 here.val = work[sym]; 221 here.val = work[sym];
222 } 222 }
(...skipping 47 matching lines...) Expand 10 before | Expand all | Expand 10 after
270 left = (int)(1 << curr); 270 left = (int)(1 << curr);
271 while (curr + drop < max) { 271 while (curr + drop < max) {
272 left -= count[curr + drop]; 272 left -= count[curr + drop];
273 if (left <= 0) break; 273 if (left <= 0) break;
274 curr++; 274 curr++;
275 left <<= 1; 275 left <<= 1;
276 } 276 }
277 277
278 /* check for enough space */ 278 /* check for enough space */
279 used += 1U << curr; 279 used += 1U << curr;
280 if ((type == LENS && used >= ENOUGH_LENS) || 280 if ((type == LENS && used > ENOUGH_LENS) ||
281 (type == DISTS && used >= ENOUGH_DISTS)) 281 (type == DISTS && used > ENOUGH_DISTS))
282 return 1; 282 return 1;
283 283
284 /* point entry in root table to sub-table */ 284 /* point entry in root table to sub-table */
285 low = huff & mask; 285 low = huff & mask;
286 (*table)[low].op = (unsigned char)curr; 286 (*table)[low].op = (unsigned char)curr;
287 (*table)[low].bits = (unsigned char)root; 287 (*table)[low].bits = (unsigned char)root;
288 (*table)[low].val = (unsigned short)(next - *table); 288 (*table)[low].val = (unsigned short)(next - *table);
289 } 289 }
290 } 290 }
291 291
292 /* 292 /* fill in remaining table entry if code is incomplete (guaranteed to have
293 Fill in rest of table for incomplete codes. This loop is similar to the 293 at most one remaining entry, since if the code is incomplete, the
294 loop above in incrementing huff for table indices. It is assumed that 294 maximum code length that was allowed to get this far is one bit) */
295 len is equal to curr + drop, so there is no loop needed to increment 295 if (huff != 0) {
296 through high index bits. When the current sub-table is filled, the loop 296 here.op = (unsigned char)64; /* invalid code marker */
297 drops back to the root table to fill in any remaining entries there. 297 here.bits = (unsigned char)(len - drop);
298 */ 298 here.val = (unsigned short)0;
299 here.op = (unsigned char)64; /* invalid code marker */ 299 next[huff] = here;
300 here.bits = (unsigned char)(len - drop);
301 here.val = (unsigned short)0;
302 while (huff != 0) {
303 /* when done with sub-table, drop back to root table */
304 if (drop != 0 && (huff & mask) != low) {
305 drop = 0;
306 len = root;
307 next = *table;
308 here.bits = (unsigned char)len;
309 }
310
311 /* put invalid code marker in table */
312 next[huff >> drop] = here;
313
314 /* backwards increment the len-bit code huff */
315 incr = 1U << (len - 1);
316 while (huff & incr)
317 incr >>= 1;
318 if (incr != 0) {
319 huff &= incr - 1;
320 huff += incr;
321 }
322 else
323 huff = 0;
324 } 300 }
325 301
326 /* set return parameters */ 302 /* set return parameters */
327 *table += used; 303 *table += used;
328 *bits = root; 304 *bits = root;
329 return 0; 305 return 0;
330 } 306 }
OLDNEW
« no previous file with comments | « third_party/zlib/inflate.c ('k') | third_party/zlib/mixed-source.patch » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698