/* inftrees.c -- generate Huffman trees for efficient decoding
- * Copyright (C) 1995-2003 Mark Adler
+ * Copyright (C) 1995-2022 Mark Adler
* For conditions of distribution and use, see copyright notice in zlib.h
*/
#define MAXBITS 15
const char inflate_copyright[] =
- " inflate 1.2.1 Copyright 1995-2003 Mark Adler ";
+ " inflate 1.2.12 Copyright 1995-2022 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
table index bits. It will differ if the request is greater than the
longest code or if it is less than the shortest code.
*/
-int inflate_table(type, lens, codes, table, bits, work)
+int ZLIB_INTERNAL inflate_table(type, lens, codes, table, bits, work)
codetype type;
unsigned short FAR *lens;
unsigned codes;
unsigned fill; /* index for replicating entries */
unsigned low; /* low bits for current root entry */
unsigned mask; /* mask for low root bits */
- code this; /* table entry for duplication */
+ code here; /* table entry for duplication */
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 */
- int end; /* use base and extra for symbol > end */
+ unsigned match; /* use base and extra for symbol >= match */
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 */
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, 76, 66};
+ 19, 19, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21, 16, 199, 202};
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,
for (max = MAXBITS; max >= 1; max--)
if (count[max] != 0) break;
if (root > max) root = max;
- if (max == 0) return -1; /* no codes! */
- for (min = 1; min <= MAXBITS; min++)
+ if (max == 0) { /* no symbols to code at all */
+ here.op = (unsigned char)64; /* invalid code marker */
+ here.bits = (unsigned char)1;
+ here.val = (unsigned short)0;
+ *(*table)++ = here; /* make a table to force an error */
+ *(*table)++ = here;
+ *bits = 1;
+ return 0; /* no symbols, but wait for decoding to report error */
+ }
+ for (min = 1; min < max; min++)
if (count[min] != 0) break;
if (root < min) root = min;
left -= count[len];
if (left < 0) return -1; /* over-subscribed */
}
- if (left > 0 && (type == CODES || (codes - count[0] != 1)))
+ if (left > 0 && (type == CODES || max != 1))
return -1; /* incomplete set */
/* generate offsets into symbol table for each length for sorting */
entered in the tables.
used keeps track of how many table entries have been allocated from the
- provided *table space. It is checked when a LENS table is being made
- against the space in *table, ENOUGH, minus the maximum space needed by
- the worst case distance code, MAXD. This should never happen, but the
- sufficiency of ENOUGH has not been proven exhaustively, hence the check.
- This assumes that when type == LENS, bits == 9.
+ provided *table space. It is checked for LENS and DIST tables against
+ the constants ENOUGH_LENS and ENOUGH_DISTS to guard against changes in
+ the initial root table size constants. See the comments in inftrees.h
+ for more information.
sym increments through all symbols, and the loop terminates when
all codes of length max, i.e. all codes, have been processed. This
switch (type) {
case CODES:
base = extra = work; /* dummy value--not used */
- end = 19;
+ match = 20;
break;
case LENS:
base = lbase;
- base -= 257;
extra = lext;
- extra -= 257;
- end = 256;
+ match = 257;
break;
- default: /* DISTS */
+ default: /* DISTS */
base = dbase;
extra = dext;
- end = -1;
+ match = 0;
}
/* initialize state for loop */
mask = used - 1; /* mask for comparing low */
/* check available table space */
- if (type == LENS && used >= ENOUGH - MAXD)
+ if ((type == LENS && used > ENOUGH_LENS) ||
+ (type == DISTS && used > ENOUGH_DISTS))
return 1;
/* process all codes and make table entries */
for (;;) {
/* create table entry */
- this.bits = (unsigned char)(len - drop);
- if ((int)(work[sym]) < end) {
- this.op = (unsigned char)0;
- this.val = work[sym];
+ here.bits = (unsigned char)(len - drop);
+ if (work[sym] + 1U < match) {
+ here.op = (unsigned char)0;
+ here.val = work[sym];
}
- else if ((int)(work[sym]) > end) {
- this.op = (unsigned char)(extra[work[sym]]);
- this.val = base[work[sym]];
+ else if (work[sym] >= match) {
+ here.op = (unsigned char)(extra[work[sym] - match]);
+ here.val = base[work[sym] - match];
}
else {
- this.op = (unsigned char)(32 + 64); /* end of block */
- this.val = 0;
+ here.op = (unsigned char)(32 + 64); /* end of block */
+ here.val = 0;
}
/* replicate for those indices with low len bits equal to huff */
incr = 1U << (len - drop);
fill = 1U << curr;
+ min = fill; /* save offset to next table */
do {
fill -= incr;
- next[(huff >> drop) + fill] = this;
+ next[(huff >> drop) + fill] = here;
} while (fill != 0);
/* backwards increment the len-bit code huff */
drop = root;
/* increment past last table */
- next += 1U << curr;
+ next += min; /* here min is 1 << curr */
/* determine length of next table */
curr = len - drop;
/* check for enough space */
used += 1U << curr;
- if (type == LENS && used >= ENOUGH - MAXD)
+ if ((type == LENS && used > ENOUGH_LENS) ||
+ (type == DISTS && used > ENOUGH_DISTS))
return 1;
/* point entry in root table to sub-table */
}
}
- /*
- 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.
- */
- this.op = (unsigned char)64; /* invalid code marker */
- this.bits = (unsigned char)(len - drop);
- this.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;
- curr = root;
- this.bits = (unsigned char)len;
- }
-
- /* put invalid code marker in table */
- next[huff >> drop] = this;
-
- /* 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;
+ /* 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;
}
/* set return parameters */
projects / zlib.git / blobdiff