--- /dev/null
+/* inftrees.c -- generate Huffman trees for efficient decoding\r
+ * Copyright (C) 1995-2013 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.8 Copyright 1995-2013 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 ZLIB_INTERNAL 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 here; /* 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, 72, 78};\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
+ here.op = (unsigned char)64; /* invalid code marker */\r
+ here.bits = (unsigned char)1;\r
+ here.val = (unsigned short)0;\r
+ *(*table)++ = here; /* make a table to force an error */\r
+ *(*table)++ = here;\r
+ *bits = 1;\r
+ return 0; /* no symbols, but wait for decoding to report error */\r
+ }\r
+ for (min = 1; min < max; 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 for LENS and DIST tables against\r
+ the constants ENOUGH_LENS and ENOUGH_DISTS to guard against changes in\r
+ the initial root table size constants. See the comments in inftrees.h\r
+ for more information.\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_LENS) ||\r
+ (type == DISTS && used > ENOUGH_DISTS))\r
+ return 1;\r
+\r
+ /* process all codes and make table entries */\r
+ for (;;) {\r
+ /* create table entry */\r
+ here.bits = (unsigned char)(len - drop);\r
+ if ((int)(work[sym]) < end) {\r
+ here.op = (unsigned char)0;\r
+ here.val = work[sym];\r
+ }\r
+ else if ((int)(work[sym]) > end) {\r
+ here.op = (unsigned char)(extra[work[sym]]);\r
+ here.val = base[work[sym]];\r
+ }\r
+ else {\r
+ here.op = (unsigned char)(32 + 64); /* end of block */\r
+ here.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] = here;\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_LENS) ||\r
+ (type == DISTS && used > ENOUGH_DISTS))\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
+ /* fill in remaining table entry if code is incomplete (guaranteed to have\r
+ at most one remaining entry, since if the code is incomplete, the\r
+ maximum code length that was allowed to get this far is one bit) */\r
+ if (huff != 0) {\r
+ here.op = (unsigned char)64; /* invalid code marker */\r
+ here.bits = (unsigned char)(len - drop);\r
+ here.val = (unsigned short)0;\r
+ next[huff] = here;\r
+ }\r
+\r
+ /* set return parameters */\r
+ *table += used;\r
+ *bits = root;\r
+ return 0;\r
+}\r
projects / mirror_edk2.git / blobdiff