+++ /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