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