diff options
Diffstat (limited to 'src/zlib/inftrees.c')
| -rw-r--r-- | src/zlib/inftrees.c | 74 |
1 files changed, 50 insertions, 24 deletions
diff --git a/src/zlib/inftrees.c b/src/zlib/inftrees.c index 2ea08fc..11e9c52 100644 --- a/src/zlib/inftrees.c +++ b/src/zlib/inftrees.c @@ -1,5 +1,5 @@ /* inftrees.c -- generate Huffman trees for efficient decoding - * Copyright (C) 1995-2017 Mark Adler + * Copyright (C) 1995-2010 Mark Adler * For conditions of distribution and use, see copyright notice in zlib.h */ @@ -9,7 +9,7 @@ #define MAXBITS 15 const char inflate_copyright[] = - " inflate 1.2.11 Copyright 1995-2017 Mark Adler "; + " inflate 1.2.5 Copyright 1995-2010 Mark Adler "; /* If you use the zlib library in a product, an acknowledgment is welcome in the documentation of your product. If for some reason you cannot @@ -54,7 +54,7 @@ unsigned short FAR *work; code FAR *next; /* next available space in table */ const unsigned short FAR *base; /* base value table to use */ const unsigned short FAR *extra; /* extra bits table to use */ - unsigned match; /* use base and extra for symbol >= match */ + int end; /* use base and extra for symbol > end */ unsigned short count[MAXBITS+1]; /* number of codes of each length */ unsigned short offs[MAXBITS+1]; /* offsets in table for each length */ static const unsigned short lbase[31] = { /* Length codes 257..285 base */ @@ -62,7 +62,7 @@ unsigned short FAR *work; 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0}; static const unsigned short lext[31] = { /* Length codes 257..285 extra */ 16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, 18, 18, 18, 18, - 19, 19, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21, 16, 77, 202}; + 19, 19, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21, 16, 73, 195}; static const unsigned short dbase[32] = { /* Distance codes 0..29 base */ 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145, @@ -181,17 +181,19 @@ unsigned short FAR *work; switch (type) { case CODES: base = extra = work; /* dummy value--not used */ - match = 20; + end = 19; break; case LENS: base = lbase; + base -= 257; extra = lext; - match = 257; + extra -= 257; + end = 256; break; - default: /* DISTS */ + default: /* DISTS */ base = dbase; extra = dext; - match = 0; + end = -1; } /* initialize state for loop */ @@ -206,21 +208,21 @@ unsigned short FAR *work; mask = used - 1; /* mask for comparing low */ /* check available table space */ - if ((type == LENS && used > ENOUGH_LENS) || - (type == DISTS && used > ENOUGH_DISTS)) + if ((type == LENS && used >= ENOUGH_LENS) || + (type == DISTS && used >= ENOUGH_DISTS)) return 1; /* process all codes and make table entries */ for (;;) { /* create table entry */ here.bits = (unsigned char)(len - drop); - if (work[sym] + 1U < match) { + if ((int)(work[sym]) < end) { here.op = (unsigned char)0; here.val = work[sym]; } - else if (work[sym] >= match) { - here.op = (unsigned char)(extra[work[sym] - match]); - here.val = base[work[sym] - match]; + else if ((int)(work[sym]) > end) { + here.op = (unsigned char)(extra[work[sym]]); + here.val = base[work[sym]]; } else { here.op = (unsigned char)(32 + 64); /* end of block */ @@ -275,8 +277,8 @@ unsigned short FAR *work; /* check for enough space */ used += 1U << curr; - if ((type == LENS && used > ENOUGH_LENS) || - (type == DISTS && used > ENOUGH_DISTS)) + if ((type == LENS && used >= ENOUGH_LENS) || + (type == DISTS && used >= ENOUGH_DISTS)) return 1; /* point entry in root table to sub-table */ @@ -287,14 +289,38 @@ unsigned short FAR *work; } } - /* fill in remaining table entry if code is incomplete (guaranteed to have - at most one remaining entry, since if the code is incomplete, the - maximum code length that was allowed to get this far is one bit) */ - if (huff != 0) { - here.op = (unsigned char)64; /* invalid code marker */ - here.bits = (unsigned char)(len - drop); - here.val = (unsigned short)0; - next[huff] = here; + /* + Fill in rest of table for incomplete codes. This loop is similar to the + loop above in incrementing huff for table indices. It is assumed that + len is equal to curr + drop, so there is no loop needed to increment + through high index bits. When the current sub-table is filled, the loop + drops back to the root table to fill in any remaining entries there. + */ + here.op = (unsigned char)64; /* invalid code marker */ + here.bits = (unsigned char)(len - drop); + here.val = (unsigned short)0; + while (huff != 0) { + /* when done with sub-table, drop back to root table */ + if (drop != 0 && (huff & mask) != low) { + drop = 0; + len = root; + next = *table; + here.bits = (unsigned char)len; + } + + /* put invalid code marker in table */ + next[huff >> drop] = here; + + /* backwards increment the len-bit code huff */ + incr = 1U << (len - 1); + while (huff & incr) + incr >>= 1; + if (incr != 0) { + huff &= incr - 1; + huff += incr; + } + else + huff = 0; } /* set return parameters */ |