Rev 1896 | Go to most recent revision | Show entire file | Regard whitespace | Details | Blame | Last modification | View Log | RSS feed
| Rev 1896 | Rev 3926 | ||
|---|---|---|---|
| Line 1... | Line 1... | ||
| 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 | */ |
| Line 5... | Line 5... | ||
| 5 | 5 | ||
| 6 | #include "zutil.h" |
6 | #include "zutil.h" |
| Line 7... | Line 7... | ||
| 7 | #include "inftrees.h" |
7 | #include "inftrees.h" |
| Line 8... | Line 8... | ||
| 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 |
| Line 60... | Line 60... | ||
| 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 */ |
| Line 206... | Line 206... | ||
| 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 */ |
| Line 209... | Line 209... | ||
| 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)) |
| Line 213... | Line 213... | ||
| 213 | return 1; |
213 | return 1; |
| 214 | 214 | ||
| 215 | /* process all codes and make table entries */ |
215 | /* process all codes and make table entries */ |
| Line 275... | Line 275... | ||
| 275 | left <<= 1; |
275 | left <<= 1; |
| 276 | } |
276 | } |
| Line 277... | Line 277... | ||
| 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)) |
| Line 282... | Line 282... | ||
| 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); |
| Line 289... | Line -... | ||
| 289 | } |
- | |
| 290 | } |
289 | } |
| 291 | 290 | } |
|
| 292 | /* |
- | |
| 293 | Fill in rest of table for incomplete codes. This loop is similar to the |
- | |
| 294 | loop above in incrementing huff for table indices. It is assumed that |
291 | |
| 295 | len is equal to curr + drop, so there is no loop needed to increment |
292 | /* fill in remaining table entry if code is incomplete (guaranteed to have |
| 296 | through high index bits. When the current sub-table is filled, the loop |
293 | at most one remaining entry, since if the code is incomplete, the |
| 297 | drops back to the root table to fill in any remaining entries there. |
294 | maximum code length that was allowed to get this far is one bit) */ |
| 298 | */ |
295 | if (huff != 0) { |
| 299 | here.op = (unsigned char)64; /* invalid code marker */ |
- | |
| 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 | } |
296 | here.op = (unsigned char)64; /* invalid code marker */ |
| 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 | } |
297 | here.bits = (unsigned char)(len - drop); |
| Line 322... | Line 298... | ||
| 322 | else |
298 | here.val = (unsigned short)0; |
| 323 | huff = 0; |
299 | next[huff] = here; |
| 324 | } |
300 | } |