1.1 --- a/sourcepawn/jit/zlib/inftrees.c Fri Jul 11 06:51:21 2008 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,329 +0,0 @@
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 -}
