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
(type, lens, codes, table, bits, work)
| 30 | longest code or if it is less than the shortest code. |
| 31 | */ |
| 32 | int ZLIB_INTERNAL inflate_table(type, lens, codes, table, bits, work) |
| 33 | codetype type; |
| 34 | unsigned short FAR *lens; |
| 35 | unsigned codes; |
| 36 | code FAR * FAR *table; |
| 37 | unsigned FAR *bits; |
| 38 | unsigned short FAR *work; |
| 39 | { |
| 40 | unsigned len; /* a code's length in bits */ |
| 41 | unsigned sym; /* index of code symbols */ |
| 42 | unsigned min, max; /* minimum and maximum code lengths */ |
| 43 | unsigned root; /* number of index bits for root table */ |
| 44 | unsigned curr; /* number of index bits for current table */ |
| 45 | unsigned drop; /* code bits to drop for sub-table */ |
| 46 | int left; /* number of prefix codes available */ |
| 47 | unsigned used; /* code entries in table used */ |
| 48 | unsigned huff; /* Huffman code */ |
| 49 | unsigned incr; /* for incrementing code, index */ |
| 50 | unsigned fill; /* index for replicating entries */ |
| 51 | unsigned low; /* low bits for current root entry */ |
| 52 | unsigned mask; /* mask for low root bits */ |
| 53 | code here; /* table entry for duplication */ |
| 54 | code FAR *next; /* next available space in table */ |
| 55 | const unsigned short FAR *base; /* base value table to use */ |
| 56 | const unsigned short FAR *extra; /* extra bits table to use */ |
| 57 | unsigned match; /* use base and extra for symbol >= match */ |
| 58 | unsigned short count[MAXBITS+1]; /* number of codes of each length */ |
| 59 | unsigned short offs[MAXBITS+1]; /* offsets in table for each length */ |
| 60 | static const unsigned short lbase[31] = { /* Length codes 257..285 base */ |
| 61 | 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, |
| 62 | 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0}; |
| 63 | static const unsigned short lext[31] = { /* Length codes 257..285 extra */ |
| 64 | 16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, 18, 18, 18, 18, |
| 65 | 19, 19, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21, 16, 77, 202}; |
| 66 | static const unsigned short dbase[32] = { /* Distance codes 0..29 base */ |
| 67 | 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, |
| 68 | 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145, |
| 69 | 8193, 12289, 16385, 24577, 0, 0}; |
| 70 | static const unsigned short dext[32] = { /* Distance codes 0..29 extra */ |
| 71 | 16, 16, 16, 16, 17, 17, 18, 18, 19, 19, 20, 20, 21, 21, 22, 22, |
| 72 | 23, 23, 24, 24, 25, 25, 26, 26, 27, 27, |
| 73 | 28, 28, 29, 29, 64, 64}; |
| 74 | |
| 75 | /* |
| 76 | Process a set of code lengths to create a canonical Huffman code. The |
| 77 | code lengths are lens[0..codes-1]. Each length corresponds to the |
| 78 | symbols 0..codes-1. The Huffman code is generated by first sorting the |
| 79 | symbols by length from short to long, and retaining the symbol order |
| 80 | for codes with equal lengths. Then the code starts with all zero bits |
| 81 | for the first code of the shortest length, and the codes are integer |
| 82 | increments for the same length, and zeros are appended as the length |
| 83 | increases. For the deflate format, these bits are stored backwards |
| 84 | from their more natural integer increment ordering, and so when the |
| 85 | decoding tables are built in the large loop below, the integer codes |
| 86 | are incremented backwards. |
| 87 | |
| 88 | This routine assumes, but does not check, that all of the entries in |
| 89 | lens[] are in the range 0..MAXBITS. The caller must assure this. |
no outgoing calls