1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/compiler-init/zlib/inftrees.c Sat Jul 15 04:51:28 2006 +0000
1.3 @@ -0,0 +1,329 @@
1.4 +/* inftrees.c -- generate Huffman trees for efficient decoding
1.5 + * Copyright (C) 1995-2005 Mark Adler
1.6 + * For conditions of distribution and use, see copyright notice in zlib.h
1.7 + */
1.8 +
1.9 +#include "zutil.h"
1.10 +#include "inftrees.h"
1.11 +
1.12 +#define MAXBITS 15
1.13 +
1.14 +const char inflate_copyright[] =
1.15 + " inflate 1.2.3 Copyright 1995-2005 Mark Adler ";
1.16 +/*
1.17 + If you use the zlib library in a product, an acknowledgment is welcome
1.18 + in the documentation of your product. If for some reason you cannot
1.19 + include such an acknowledgment, I would appreciate that you keep this
1.20 + copyright string in the executable of your product.
1.21 + */
1.22 +
1.23 +/*
1.24 + Build a set of tables to decode the provided canonical Huffman code.
1.25 + The code lengths are lens[0..codes-1]. The result starts at *table,
1.26 + whose indices are 0..2^bits-1. work is a writable array of at least
1.27 + lens shorts, which is used as a work area. type is the type of code
1.28 + to be generated, CODES, LENS, or DISTS. On return, zero is success,
1.29 + -1 is an invalid code, and +1 means that ENOUGH isn't enough. table
1.30 + on return points to the next available entry's address. bits is the
1.31 + requested root table index bits, and on return it is the actual root
1.32 + table index bits. It will differ if the request is greater than the
1.33 + longest code or if it is less than the shortest code.
1.34 + */
1.35 +int inflate_table(type, lens, codes, table, bits, work)
1.36 +codetype type;
1.37 +unsigned short FAR *lens;
1.38 +unsigned codes;
1.39 +code FAR * FAR *table;
1.40 +unsigned FAR *bits;
1.41 +unsigned short FAR *work;
1.42 +{
1.43 + unsigned len; /* a code's length in bits */
1.44 + unsigned sym; /* index of code symbols */
1.45 + unsigned min, max; /* minimum and maximum code lengths */
1.46 + unsigned root; /* number of index bits for root table */
1.47 + unsigned curr; /* number of index bits for current table */
1.48 + unsigned drop; /* code bits to drop for sub-table */
1.49 + int left; /* number of prefix codes available */
1.50 + unsigned used; /* code entries in table used */
1.51 + unsigned huff; /* Huffman code */
1.52 + unsigned incr; /* for incrementing code, index */
1.53 + unsigned fill; /* index for replicating entries */
1.54 + unsigned low; /* low bits for current root entry */
1.55 + unsigned mask; /* mask for low root bits */
1.56 + code this; /* table entry for duplication */
1.57 + code FAR *next; /* next available space in table */
1.58 + const unsigned short FAR *base; /* base value table to use */
1.59 + const unsigned short FAR *extra; /* extra bits table to use */
1.60 + int end; /* use base and extra for symbol > end */
1.61 + unsigned short count[MAXBITS+1]; /* number of codes of each length */
1.62 + unsigned short offs[MAXBITS+1]; /* offsets in table for each length */
1.63 + static const unsigned short lbase[31] = { /* Length codes 257..285 base */
1.64 + 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
1.65 + 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0};
1.66 + static const unsigned short lext[31] = { /* Length codes 257..285 extra */
1.67 + 16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, 18, 18, 18, 18,
1.68 + 19, 19, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21, 16, 201, 196};
1.69 + static const unsigned short dbase[32] = { /* Distance codes 0..29 base */
1.70 + 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
1.71 + 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
1.72 + 8193, 12289, 16385, 24577, 0, 0};
1.73 + static const unsigned short dext[32] = { /* Distance codes 0..29 extra */
1.74 + 16, 16, 16, 16, 17, 17, 18, 18, 19, 19, 20, 20, 21, 21, 22, 22,
1.75 + 23, 23, 24, 24, 25, 25, 26, 26, 27, 27,
1.76 + 28, 28, 29, 29, 64, 64};
1.77 +
1.78 + /*
1.79 + Process a set of code lengths to create a canonical Huffman code. The
1.80 + code lengths are lens[0..codes-1]. Each length corresponds to the
1.81 + symbols 0..codes-1. The Huffman code is generated by first sorting the
1.82 + symbols by length from short to long, and retaining the symbol order
1.83 + for codes with equal lengths. Then the code starts with all zero bits
1.84 + for the first code of the shortest length, and the codes are integer
1.85 + increments for the same length, and zeros are appended as the length
1.86 + increases. For the deflate format, these bits are stored backwards
1.87 + from their more natural integer increment ordering, and so when the
1.88 + decoding tables are built in the large loop below, the integer codes
1.89 + are incremented backwards.
1.90 +
1.91 + This routine assumes, but does not check, that all of the entries in
1.92 + lens[] are in the range 0..MAXBITS. The caller must assure this.
1.93 + 1..MAXBITS is interpreted as that code length. zero means that that
1.94 + symbol does not occur in this code.
1.95 +
1.96 + The codes are sorted by computing a count of codes for each length,
1.97 + creating from that a table of starting indices for each length in the
1.98 + sorted table, and then entering the symbols in order in the sorted
1.99 + table. The sorted table is work[], with that space being provided by
1.100 + the caller.
1.101 +
1.102 + The length counts are used for other purposes as well, i.e. finding
1.103 + the minimum and maximum length codes, determining if there are any
1.104 + codes at all, checking for a valid set of lengths, and looking ahead
1.105 + at length counts to determine sub-table sizes when building the
1.106 + decoding tables.
1.107 + */
1.108 +
1.109 + /* accumulate lengths for codes (assumes lens[] all in 0..MAXBITS) */
1.110 + for (len = 0; len <= MAXBITS; len++)
1.111 + count[len] = 0;
1.112 + for (sym = 0; sym < codes; sym++)
1.113 + count[lens[sym]]++;
1.114 +
1.115 + /* bound code lengths, force root to be within code lengths */
1.116 + root = *bits;
1.117 + for (max = MAXBITS; max >= 1; max--)
1.118 + if (count[max] != 0) break;
1.119 + if (root > max) root = max;
1.120 + if (max == 0) { /* no symbols to code at all */
1.121 + this.op = (unsigned char)64; /* invalid code marker */
1.122 + this.bits = (unsigned char)1;
1.123 + this.val = (unsigned short)0;
1.124 + *(*table)++ = this; /* make a table to force an error */
1.125 + *(*table)++ = this;
1.126 + *bits = 1;
1.127 + return 0; /* no symbols, but wait for decoding to report error */
1.128 + }
1.129 + for (min = 1; min <= MAXBITS; min++)
1.130 + if (count[min] != 0) break;
1.131 + if (root < min) root = min;
1.132 +
1.133 + /* check for an over-subscribed or incomplete set of lengths */
1.134 + left = 1;
1.135 + for (len = 1; len <= MAXBITS; len++) {
1.136 + left <<= 1;
1.137 + left -= count[len];
1.138 + if (left < 0) return -1; /* over-subscribed */
1.139 + }
1.140 + if (left > 0 && (type == CODES || max != 1))
1.141 + return -1; /* incomplete set */
1.142 +
1.143 + /* generate offsets into symbol table for each length for sorting */
1.144 + offs[1] = 0;
1.145 + for (len = 1; len < MAXBITS; len++)
1.146 + offs[len + 1] = offs[len] + count[len];
1.147 +
1.148 + /* sort symbols by length, by symbol order within each length */
1.149 + for (sym = 0; sym < codes; sym++)
1.150 + if (lens[sym] != 0) work[offs[lens[sym]]++] = (unsigned short)sym;
1.151 +
1.152 + /*
1.153 + Create and fill in decoding tables. In this loop, the table being
1.154 + filled is at next and has curr index bits. The code being used is huff
1.155 + with length len. That code is converted to an index by dropping drop
1.156 + bits off of the bottom. For codes where len is less than drop + curr,
1.157 + those top drop + curr - len bits are incremented through all values to
1.158 + fill the table with replicated entries.
1.159 +
1.160 + root is the number of index bits for the root table. When len exceeds
1.161 + root, sub-tables are created pointed to by the root entry with an index
1.162 + of the low root bits of huff. This is saved in low to check for when a
1.163 + new sub-table should be started. drop is zero when the root table is
1.164 + being filled, and drop is root when sub-tables are being filled.
1.165 +
1.166 + When a new sub-table is needed, it is necessary to look ahead in the
1.167 + code lengths to determine what size sub-table is needed. The length
1.168 + counts are used for this, and so count[] is decremented as codes are
1.169 + entered in the tables.
1.170 +
1.171 + used keeps track of how many table entries have been allocated from the
1.172 + provided *table space. It is checked when a LENS table is being made
1.173 + against the space in *table, ENOUGH, minus the maximum space needed by
1.174 + the worst case distance code, MAXD. This should never happen, but the
1.175 + sufficiency of ENOUGH has not been proven exhaustively, hence the check.
1.176 + This assumes that when type == LENS, bits == 9.
1.177 +
1.178 + sym increments through all symbols, and the loop terminates when
1.179 + all codes of length max, i.e. all codes, have been processed. This
1.180 + routine permits incomplete codes, so another loop after this one fills
1.181 + in the rest of the decoding tables with invalid code markers.
1.182 + */
1.183 +
1.184 + /* set up for code type */
1.185 + switch (type) {
1.186 + case CODES:
1.187 + base = extra = work; /* dummy value--not used */
1.188 + end = 19;
1.189 + break;
1.190 + case LENS:
1.191 + base = lbase;
1.192 + base -= 257;
1.193 + extra = lext;
1.194 + extra -= 257;
1.195 + end = 256;
1.196 + break;
1.197 + default: /* DISTS */
1.198 + base = dbase;
1.199 + extra = dext;
1.200 + end = -1;
1.201 + }
1.202 +
1.203 + /* initialize state for loop */
1.204 + huff = 0; /* starting code */
1.205 + sym = 0; /* starting code symbol */
1.206 + len = min; /* starting code length */
1.207 + next = *table; /* current table to fill in */
1.208 + curr = root; /* current table index bits */
1.209 + drop = 0; /* current bits to drop from code for index */
1.210 + low = (unsigned)(-1); /* trigger new sub-table when len > root */
1.211 + used = 1U << root; /* use root table entries */
1.212 + mask = used - 1; /* mask for comparing low */
1.213 +
1.214 + /* check available table space */
1.215 + if (type == LENS && used >= ENOUGH - MAXD)
1.216 + return 1;
1.217 +
1.218 + /* process all codes and make table entries */
1.219 + for (;;) {
1.220 + /* create table entry */
1.221 + this.bits = (unsigned char)(len - drop);
1.222 + if ((int)(work[sym]) < end) {
1.223 + this.op = (unsigned char)0;
1.224 + this.val = work[sym];
1.225 + }
1.226 + else if ((int)(work[sym]) > end) {
1.227 + this.op = (unsigned char)(extra[work[sym]]);
1.228 + this.val = base[work[sym]];
1.229 + }
1.230 + else {
1.231 + this.op = (unsigned char)(32 + 64); /* end of block */
1.232 + this.val = 0;
1.233 + }
1.234 +
1.235 + /* replicate for those indices with low len bits equal to huff */
1.236 + incr = 1U << (len - drop);
1.237 + fill = 1U << curr;
1.238 + min = fill; /* save offset to next table */
1.239 + do {
1.240 + fill -= incr;
1.241 + next[(huff >> drop) + fill] = this;
1.242 + } while (fill != 0);
1.243 +
1.244 + /* backwards increment the len-bit code huff */
1.245 + incr = 1U << (len - 1);
1.246 + while (huff & incr)
1.247 + incr >>= 1;
1.248 + if (incr != 0) {
1.249 + huff &= incr - 1;
1.250 + huff += incr;
1.251 + }
1.252 + else
1.253 + huff = 0;
1.254 +
1.255 + /* go to next symbol, update count, len */
1.256 + sym++;
1.257 + if (--(count[len]) == 0) {
1.258 + if (len == max) break;
1.259 + len = lens[work[sym]];
1.260 + }
1.261 +
1.262 + /* create new sub-table if needed */
1.263 + if (len > root && (huff & mask) != low) {
1.264 + /* if first time, transition to sub-tables */
1.265 + if (drop == 0)
1.266 + drop = root;
1.267 +
1.268 + /* increment past last table */
1.269 + next += min; /* here min is 1 << curr */
1.270 +
1.271 + /* determine length of next table */
1.272 + curr = len - drop;
1.273 + left = (int)(1 << curr);
1.274 + while (curr + drop < max) {
1.275 + left -= count[curr + drop];
1.276 + if (left <= 0) break;
1.277 + curr++;
1.278 + left <<= 1;
1.279 + }
1.280 +
1.281 + /* check for enough space */
1.282 + used += 1U << curr;
1.283 + if (type == LENS && used >= ENOUGH - MAXD)
1.284 + return 1;
1.285 +
1.286 + /* point entry in root table to sub-table */
1.287 + low = huff & mask;
1.288 + (*table)[low].op = (unsigned char)curr;
1.289 + (*table)[low].bits = (unsigned char)root;
1.290 + (*table)[low].val = (unsigned short)(next - *table);
1.291 + }
1.292 + }
1.293 +
1.294 + /*
1.295 + Fill in rest of table for incomplete codes. This loop is similar to the
1.296 + loop above in incrementing huff for table indices. It is assumed that
1.297 + len is equal to curr + drop, so there is no loop needed to increment
1.298 + through high index bits. When the current sub-table is filled, the loop
1.299 + drops back to the root table to fill in any remaining entries there.
1.300 + */
1.301 + this.op = (unsigned char)64; /* invalid code marker */
1.302 + this.bits = (unsigned char)(len - drop);
1.303 + this.val = (unsigned short)0;
1.304 + while (huff != 0) {
1.305 + /* when done with sub-table, drop back to root table */
1.306 + if (drop != 0 && (huff & mask) != low) {
1.307 + drop = 0;
1.308 + len = root;
1.309 + next = *table;
1.310 + this.bits = (unsigned char)len;
1.311 + }
1.312 +
1.313 + /* put invalid code marker in table */
1.314 + next[huff >> drop] = this;
1.315 +
1.316 + /* backwards increment the len-bit code huff */
1.317 + incr = 1U << (len - 1);
1.318 + while (huff & incr)
1.319 + incr >>= 1;
1.320 + if (incr != 0) {
1.321 + huff &= incr - 1;
1.322 + huff += incr;
1.323 + }
1.324 + else
1.325 + huff = 0;
1.326 + }
1.327 +
1.328 + /* set return parameters */
1.329 + *table += used;
1.330 + *bits = root;
1.331 + return 0;
1.332 +}
