-/* inftrees.c -- generate Huffman trees for efficient decoding\r
- * Copyright (C) 1995-2005 Mark Adler\r
- * For conditions of distribution and use, see copyright notice in zlib.h\r
- */\r
-\r
-#include "zutil.h"\r
-#include "inftrees.h"\r
-\r
-#define MAXBITS 15\r
-\r
-const char inflate_copyright[] =\r
- " inflate 1.2.3 Copyright 1995-2005 Mark Adler ";\r
-/*\r
- If you use the zlib library in a product, an acknowledgment is welcome\r
- in the documentation of your product. If for some reason you cannot\r
- include such an acknowledgment, I would appreciate that you keep this\r
- copyright string in the executable of your product.\r
- */\r
-\r
-/*\r
- Build a set of tables to decode the provided canonical Huffman code.\r
- The code lengths are lens[0..codes-1]. The result starts at *table,\r
- whose indices are 0..2^bits-1. work is a writable array of at least\r
- lens shorts, which is used as a work area. type is the type of code\r
- to be generated, CODES, LENS, or DISTS. On return, zero is success,\r
- -1 is an invalid code, and +1 means that ENOUGH isn't enough. table\r
- on return points to the next available entry's address. bits is the\r
- requested root table index bits, and on return it is the actual root\r
- table index bits. It will differ if the request is greater than the\r
- longest code or if it is less than the shortest code.\r
- */\r
-int inflate_table(type, lens, codes, table, bits, work)\r
-codetype type;\r
-unsigned short FAR *lens;\r
-unsigned codes;\r
-code FAR * FAR *table;\r
-unsigned FAR *bits;\r
-unsigned short FAR *work;\r
-{\r
- unsigned len; /* a code's length in bits */\r
- unsigned sym; /* index of code symbols */\r
- unsigned min, max; /* minimum and maximum code lengths */\r
- unsigned root; /* number of index bits for root table */\r
- unsigned curr; /* number of index bits for current table */\r
- unsigned drop; /* code bits to drop for sub-table */\r
- int left; /* number of prefix codes available */\r
- unsigned used; /* code entries in table used */\r
- unsigned huff; /* Huffman code */\r
- unsigned incr; /* for incrementing code, index */\r
- unsigned fill; /* index for replicating entries */\r
- unsigned low; /* low bits for current root entry */\r
- unsigned mask; /* mask for low root bits */\r
- code this; /* table entry for duplication */\r
- code FAR *next; /* next available space in table */\r
- const unsigned short FAR *base; /* base value table to use */\r
- const unsigned short FAR *extra; /* extra bits table to use */\r
- int end; /* use base and extra for symbol > end */\r
- unsigned short count[MAXBITS+1]; /* number of codes of each length */\r
- unsigned short offs[MAXBITS+1]; /* offsets in table for each length */\r
- static const unsigned short lbase[31] = { /* Length codes 257..285 base */\r
- 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,\r
- 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0};\r
- static const unsigned short lext[31] = { /* Length codes 257..285 extra */\r
- 16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, 18, 18, 18, 18,\r
- 19, 19, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21, 16, 201, 196};\r
- static const unsigned short dbase[32] = { /* Distance codes 0..29 base */\r
- 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,\r
- 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,\r
- 8193, 12289, 16385, 24577, 0, 0};\r
- static const unsigned short dext[32] = { /* Distance codes 0..29 extra */\r
- 16, 16, 16, 16, 17, 17, 18, 18, 19, 19, 20, 20, 21, 21, 22, 22,\r
- 23, 23, 24, 24, 25, 25, 26, 26, 27, 27,\r
- 28, 28, 29, 29, 64, 64};\r
-\r
- /*\r
- Process a set of code lengths to create a canonical Huffman code. The\r
- code lengths are lens[0..codes-1]. Each length corresponds to the\r
- symbols 0..codes-1. The Huffman code is generated by first sorting the\r
- symbols by length from short to long, and retaining the symbol order\r
- for codes with equal lengths. Then the code starts with all zero bits\r
- for the first code of the shortest length, and the codes are integer\r
- increments for the same length, and zeros are appended as the length\r
- increases. For the deflate format, these bits are stored backwards\r
- from their more natural integer increment ordering, and so when the\r
- decoding tables are built in the large loop below, the integer codes\r
- are incremented backwards.\r
-\r
- This routine assumes, but does not check, that all of the entries in\r
- lens[] are in the range 0..MAXBITS. The caller must assure this.\r
- 1..MAXBITS is interpreted as that code length. zero means that that\r
- symbol does not occur in this code.\r
-\r
- The codes are sorted by computing a count of codes for each length,\r
- creating from that a table of starting indices for each length in the\r
- sorted table, and then entering the symbols in order in the sorted\r
- table. The sorted table is work[], with that space being provided by\r
- the caller.\r
-\r
- The length counts are used for other purposes as well, i.e. finding\r
- the minimum and maximum length codes, determining if there are any\r
- codes at all, checking for a valid set of lengths, and looking ahead\r
- at length counts to determine sub-table sizes when building the\r
- decoding tables.\r
- */\r
-\r
- /* accumulate lengths for codes (assumes lens[] all in 0..MAXBITS) */\r
- for (len = 0; len <= MAXBITS; len++)\r
- count[len] = 0;\r
- for (sym = 0; sym < codes; sym++)\r
- count[lens[sym]]++;\r
-\r
- /* bound code lengths, force root to be within code lengths */\r
- root = *bits;\r
- for (max = MAXBITS; max >= 1; max--)\r
- if (count[max] != 0) break;\r
- if (root > max) root = max;\r
- if (max == 0) { /* no symbols to code at all */\r
- this.op = (unsigned char)64; /* invalid code marker */\r
- this.bits = (unsigned char)1;\r
- this.val = (unsigned short)0;\r
- *(*table)++ = this; /* make a table to force an error */\r
- *(*table)++ = this;\r
- *bits = 1;\r
- return 0; /* no symbols, but wait for decoding to report error */\r
- }\r
- for (min = 1; min <= MAXBITS; min++)\r
- if (count[min] != 0) break;\r
- if (root < min) root = min;\r
-\r
- /* check for an over-subscribed or incomplete set of lengths */\r
- left = 1;\r
- for (len = 1; len <= MAXBITS; len++) {\r
- left <<= 1;\r
- left -= count[len];\r
- if (left < 0) return -1; /* over-subscribed */\r
- }\r
- if (left > 0 && (type == CODES || max != 1))\r
- return -1; /* incomplete set */\r
-\r
- /* generate offsets into symbol table for each length for sorting */\r
- offs[1] = 0;\r
- for (len = 1; len < MAXBITS; len++)\r
- offs[len + 1] = offs[len] + count[len];\r
-\r
- /* sort symbols by length, by symbol order within each length */\r
- for (sym = 0; sym < codes; sym++)\r
- if (lens[sym] != 0) work[offs[lens[sym]]++] = (unsigned short)sym;\r
-\r
- /*\r
- Create and fill in decoding tables. In this loop, the table being\r
- filled is at next and has curr index bits. The code being used is huff\r
- with length len. That code is converted to an index by dropping drop\r
- bits off of the bottom. For codes where len is less than drop + curr,\r
- those top drop + curr - len bits are incremented through all values to\r
- fill the table with replicated entries.\r
-\r
- root is the number of index bits for the root table. When len exceeds\r
- root, sub-tables are created pointed to by the root entry with an index\r
- of the low root bits of huff. This is saved in low to check for when a\r
- new sub-table should be started. drop is zero when the root table is\r
- being filled, and drop is root when sub-tables are being filled.\r
-\r
- When a new sub-table is needed, it is necessary to look ahead in the\r
- code lengths to determine what size sub-table is needed. The length\r
- counts are used for this, and so count[] is decremented as codes are\r
- entered in the tables.\r
-\r
- used keeps track of how many table entries have been allocated from the\r
- provided *table space. It is checked when a LENS table is being made\r
- against the space in *table, ENOUGH, minus the maximum space needed by\r
- the worst case distance code, MAXD. This should never happen, but the\r
- sufficiency of ENOUGH has not been proven exhaustively, hence the check.\r
- This assumes that when type == LENS, bits == 9.\r
-\r
- sym increments through all symbols, and the loop terminates when\r
- all codes of length max, i.e. all codes, have been processed. This\r
- routine permits incomplete codes, so another loop after this one fills\r
- in the rest of the decoding tables with invalid code markers.\r
- */\r
-\r
- /* set up for code type */\r
- switch (type) {\r
- case CODES:\r
- base = extra = work; /* dummy value--not used */\r
- end = 19;\r
- break;\r
- case LENS:\r
- base = lbase;\r
- base -= 257;\r
- extra = lext;\r
- extra -= 257;\r
- end = 256;\r
- break;\r
- default: /* DISTS */\r
- base = dbase;\r
- extra = dext;\r
- end = -1;\r
- }\r
-\r
- /* initialize state for loop */\r
- huff = 0; /* starting code */\r
- sym = 0; /* starting code symbol */\r
- len = min; /* starting code length */\r
- next = *table; /* current table to fill in */\r
- curr = root; /* current table index bits */\r
- drop = 0; /* current bits to drop from code for index */\r
- low = (unsigned)(-1); /* trigger new sub-table when len > root */\r
- used = 1U << root; /* use root table entries */\r
- mask = used - 1; /* mask for comparing low */\r
-\r
- /* check available table space */\r
- if (type == LENS && used >= ENOUGH - MAXD)\r
- return 1;\r
-\r
- /* process all codes and make table entries */\r
- for (;;) {\r
- /* create table entry */\r
- this.bits = (unsigned char)(len - drop);\r
- if ((int)(work[sym]) < end) {\r
- this.op = (unsigned char)0;\r
- this.val = work[sym];\r
- }\r
- else if ((int)(work[sym]) > end) {\r
- this.op = (unsigned char)(extra[work[sym]]);\r
- this.val = base[work[sym]];\r
- }\r
- else {\r
- this.op = (unsigned char)(32 + 64); /* end of block */\r
- this.val = 0;\r
- }\r
-\r
- /* replicate for those indices with low len bits equal to huff */\r
- incr = 1U << (len - drop);\r
- fill = 1U << curr;\r
- min = fill; /* save offset to next table */\r
- do {\r
- fill -= incr;\r
- next[(huff >> drop) + fill] = this;\r
- } while (fill != 0);\r
-\r
- /* backwards increment the len-bit code huff */\r
- incr = 1U << (len - 1);\r
- while (huff & incr)\r
- incr >>= 1;\r
- if (incr != 0) {\r
- huff &= incr - 1;\r
- huff += incr;\r
- }\r
- else\r
- huff = 0;\r
-\r
- /* go to next symbol, update count, len */\r
- sym++;\r
- if (--(count[len]) == 0) {\r
- if (len == max) break;\r
- len = lens[work[sym]];\r
- }\r
-\r
- /* create new sub-table if needed */\r
- if (len > root && (huff & mask) != low) {\r
- /* if first time, transition to sub-tables */\r
- if (drop == 0)\r
- drop = root;\r
-\r
- /* increment past last table */\r
- next += min; /* here min is 1 << curr */\r
-\r
- /* determine length of next table */\r
- curr = len - drop;\r
- left = (int)(1 << curr);\r
- while (curr + drop < max) {\r
- left -= count[curr + drop];\r
- if (left <= 0) break;\r
- curr++;\r
- left <<= 1;\r
- }\r
-\r
- /* check for enough space */\r
- used += 1U << curr;\r
- if (type == LENS && used >= ENOUGH - MAXD)\r
- return 1;\r
-\r
- /* point entry in root table to sub-table */\r
- low = huff & mask;\r
- (*table)[low].op = (unsigned char)curr;\r
- (*table)[low].bits = (unsigned char)root;\r
- (*table)[low].val = (unsigned short)(next - *table);\r
- }\r
- }\r
-\r
- /*\r
- Fill in rest of table for incomplete codes. This loop is similar to the\r
- loop above in incrementing huff for table indices. It is assumed that\r
- len is equal to curr + drop, so there is no loop needed to increment\r
- through high index bits. When the current sub-table is filled, the loop\r
- drops back to the root table to fill in any remaining entries there.\r
- */\r
- this.op = (unsigned char)64; /* invalid code marker */\r
- this.bits = (unsigned char)(len - drop);\r
- this.val = (unsigned short)0;\r
- while (huff != 0) {\r
- /* when done with sub-table, drop back to root table */\r
- if (drop != 0 && (huff & mask) != low) {\r
- drop = 0;\r
- len = root;\r
- next = *table;\r
- this.bits = (unsigned char)len;\r
- }\r
-\r
- /* put invalid code marker in table */\r
- next[huff >> drop] = this;\r
-\r
- /* backwards increment the len-bit code huff */\r
- incr = 1U << (len - 1);\r
- while (huff & incr)\r
- incr >>= 1;\r
- if (incr != 0) {\r
- huff &= incr - 1;\r
- huff += incr;\r
- }\r
- else\r
- huff = 0;\r
- }\r
-\r
- /* set return parameters */\r
- *table += used;\r
- *bits = root;\r
- return 0;\r
-}\r
+/* inftrees.c -- generate Huffman trees for efficient decoding
+ * Copyright (C) 1995-2005 Mark Adler
+ * For conditions of distribution and use, see copyright notice in zlib.h
+ */
+
+#include "zutil.h"
+#include "inftrees.h"
+
+#define MAXBITS 15
+
+const char inflate_copyright[] =
+ " inflate 1.2.3 Copyright 1995-2005 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
+ include such an acknowledgment, I would appreciate that you keep this
+ copyright string in the executable of your product.
+ */
+
+/*
+ Build a set of tables to decode the provided canonical Huffman code.
+ The code lengths are lens[0..codes-1]. The result starts at *table,
+ whose indices are 0..2^bits-1. work is a writable array of at least
+ lens shorts, which is used as a work area. type is the type of code
+ to be generated, CODES, LENS, or DISTS. On return, zero is success,
+ -1 is an invalid code, and +1 means that ENOUGH isn't enough. table
+ on return points to the next available entry's address. bits is the
+ requested root table index bits, and on return it is the actual root
+ 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)
+codetype type;
+unsigned short FAR *lens;
+unsigned codes;
+code FAR * FAR *table;
+unsigned FAR *bits;
+unsigned short FAR *work;
+{
+ unsigned len; /* a code's length in bits */
+ unsigned sym; /* index of code symbols */
+ unsigned min, max; /* minimum and maximum code lengths */
+ unsigned root; /* number of index bits for root table */
+ unsigned curr; /* number of index bits for current table */
+ unsigned drop; /* code bits to drop for sub-table */
+ int left; /* number of prefix codes available */
+ unsigned used; /* code entries in table used */
+ unsigned huff; /* Huffman code */
+ unsigned incr; /* for incrementing code, index */
+ 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 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 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 */
+ 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
+ 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, 201, 196};
+ 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,
+ 8193, 12289, 16385, 24577, 0, 0};
+ static const unsigned short dext[32] = { /* Distance codes 0..29 extra */
+ 16, 16, 16, 16, 17, 17, 18, 18, 19, 19, 20, 20, 21, 21, 22, 22,
+ 23, 23, 24, 24, 25, 25, 26, 26, 27, 27,
+ 28, 28, 29, 29, 64, 64};
+
+ /*
+ Process a set of code lengths to create a canonical Huffman code. The
+ code lengths are lens[0..codes-1]. Each length corresponds to the
+ symbols 0..codes-1. The Huffman code is generated by first sorting the
+ symbols by length from short to long, and retaining the symbol order
+ for codes with equal lengths. Then the code starts with all zero bits
+ for the first code of the shortest length, and the codes are integer
+ increments for the same length, and zeros are appended as the length
+ increases. For the deflate format, these bits are stored backwards
+ from their more natural integer increment ordering, and so when the
+ decoding tables are built in the large loop below, the integer codes
+ are incremented backwards.
+
+ This routine assumes, but does not check, that all of the entries in
+ lens[] are in the range 0..MAXBITS. The caller must assure this.
+ 1..MAXBITS is interpreted as that code length. zero means that that
+ symbol does not occur in this code.
+
+ The codes are sorted by computing a count of codes for each length,
+ creating from that a table of starting indices for each length in the
+ sorted table, and then entering the symbols in order in the sorted
+ table. The sorted table is work[], with that space being provided by
+ the caller.
+
+ The length counts are used for other purposes as well, i.e. finding
+ the minimum and maximum length codes, determining if there are any
+ codes at all, checking for a valid set of lengths, and looking ahead
+ at length counts to determine sub-table sizes when building the
+ decoding tables.
+ */
+
+ /* accumulate lengths for codes (assumes lens[] all in 0..MAXBITS) */
+ for (len = 0; len <= MAXBITS; len++)
+ count[len] = 0;
+ for (sym = 0; sym < codes; sym++)
+ count[lens[sym]]++;
+
+ /* bound code lengths, force root to be within code lengths */
+ root = *bits;
+ for (max = MAXBITS; max >= 1; max--)
+ if (count[max] != 0) break;
+ if (root > max) root = max;
+ if (max == 0) { /* no symbols to code at all */
+ this.op = (unsigned char)64; /* invalid code marker */
+ this.bits = (unsigned char)1;
+ this.val = (unsigned short)0;
+ *(*table)++ = this; /* make a table to force an error */
+ *(*table)++ = this;
+ *bits = 1;
+ return 0; /* no symbols, but wait for decoding to report error */
+ }
+ for (min = 1; min <= MAXBITS; min++)
+ if (count[min] != 0) break;
+ if (root < min) root = min;
+
+ /* check for an over-subscribed or incomplete set of lengths */
+ left = 1;
+ for (len = 1; len <= MAXBITS; len++) {
+ left <<= 1;
+ left -= count[len];
+ if (left < 0) return -1; /* over-subscribed */
+ }
+ if (left > 0 && (type == CODES || max != 1))
+ return -1; /* incomplete set */
+
+ /* generate offsets into symbol table for each length for sorting */
+ offs[1] = 0;
+ for (len = 1; len < MAXBITS; len++)
+ offs[len + 1] = offs[len] + count[len];
+
+ /* sort symbols by length, by symbol order within each length */
+ for (sym = 0; sym < codes; sym++)
+ if (lens[sym] != 0) work[offs[lens[sym]]++] = (unsigned short)sym;
+
+ /*
+ Create and fill in decoding tables. In this loop, the table being
+ filled is at next and has curr index bits. The code being used is huff
+ with length len. That code is converted to an index by dropping drop
+ bits off of the bottom. For codes where len is less than drop + curr,
+ those top drop + curr - len bits are incremented through all values to
+ fill the table with replicated entries.
+
+ root is the number of index bits for the root table. When len exceeds
+ root, sub-tables are created pointed to by the root entry with an index
+ of the low root bits of huff. This is saved in low to check for when a
+ new sub-table should be started. drop is zero when the root table is
+ being filled, and drop is root when sub-tables are being filled.
+
+ When a new sub-table is needed, it is necessary to look ahead in the
+ code lengths to determine what size sub-table is needed. The length
+ counts are used for this, and so count[] is decremented as codes are
+ 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.
+
+ sym increments through all symbols, and the loop terminates when
+ all codes of length max, i.e. all codes, have been processed. This
+ routine permits incomplete codes, so another loop after this one fills
+ in the rest of the decoding tables with invalid code markers.
+ */
+
+ /* set up for code type */
+ switch (type) {
+ case CODES:
+ base = extra = work; /* dummy value--not used */
+ end = 19;
+ break;
+ case LENS:
+ base = lbase;
+ base -= 257;
+ extra = lext;
+ extra -= 257;
+ end = 256;
+ break;
+ default: /* DISTS */
+ base = dbase;
+ extra = dext;
+ end = -1;
+ }
+
+ /* initialize state for loop */
+ huff = 0; /* starting code */
+ sym = 0; /* starting code symbol */
+ len = min; /* starting code length */
+ next = *table; /* current table to fill in */
+ curr = root; /* current table index bits */
+ drop = 0; /* current bits to drop from code for index */
+ low = (unsigned)(-1); /* trigger new sub-table when len > root */
+ used = 1U << root; /* use root table entries */
+ mask = used - 1; /* mask for comparing low */
+
+ /* check available table space */
+ if (type == LENS && used >= ENOUGH - MAXD)
+ 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];
+ }
+ else if ((int)(work[sym]) > end) {
+ this.op = (unsigned char)(extra[work[sym]]);
+ this.val = base[work[sym]];
+ }
+ else {
+ this.op = (unsigned char)(32 + 64); /* end of block */
+ this.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;
+ } while (fill != 0);
+
+ /* 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;
+
+ /* go to next symbol, update count, len */
+ sym++;
+ if (--(count[len]) == 0) {
+ if (len == max) break;
+ len = lens[work[sym]];
+ }
+
+ /* create new sub-table if needed */
+ if (len > root && (huff & mask) != low) {
+ /* if first time, transition to sub-tables */
+ if (drop == 0)
+ drop = root;
+
+ /* increment past last table */
+ next += min; /* here min is 1 << curr */
+
+ /* determine length of next table */
+ curr = len - drop;
+ left = (int)(1 << curr);
+ while (curr + drop < max) {
+ left -= count[curr + drop];
+ if (left <= 0) break;
+ curr++;
+ left <<= 1;
+ }
+
+ /* check for enough space */
+ used += 1U << curr;
+ if (type == LENS && used >= ENOUGH - MAXD)
+ return 1;
+
+ /* point entry in root table to sub-table */
+ low = huff & mask;
+ (*table)[low].op = (unsigned char)curr;
+ (*table)[low].bits = (unsigned char)root;
+ (*table)[low].val = (unsigned short)(next - *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;
+ 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;
+ }
+
+ /* set return parameters */
+ *table += used;
+ *bits = root;
+ return 0;
+}