istereo

annotate libs/zlib/inftrees.c @ 28:c0ae8e668447

find changesets by author, revision, files, or words in the commit message
added vmath library
author John Tsiombikas <nuclear@mutantstargoat.com>
date Thu, 08 Sep 2011 08:30:42 +0300
parents
children
rev   line source
nuclear@26 1 /* inftrees.c -- generate Huffman trees for efficient decoding
nuclear@26 2 * Copyright (C) 1995-2005 Mark Adler
nuclear@26 3 * For conditions of distribution and use, see copyright notice in zlib.h
nuclear@26 4 */
nuclear@26 5
nuclear@26 6 #include "zutil.h"
nuclear@26 7 #include "inftrees.h"
nuclear@26 8
nuclear@26 9 #define MAXBITS 15
nuclear@26 10
nuclear@26 11 const char inflate_copyright[] =
nuclear@26 12 " inflate 1.2.3 Copyright 1995-2005 Mark Adler ";
nuclear@26 13 /*
nuclear@26 14 If you use the zlib library in a product, an acknowledgment is welcome
nuclear@26 15 in the documentation of your product. If for some reason you cannot
nuclear@26 16 include such an acknowledgment, I would appreciate that you keep this
nuclear@26 17 copyright string in the executable of your product.
nuclear@26 18 */
nuclear@26 19
nuclear@26 20 /*
nuclear@26 21 Build a set of tables to decode the provided canonical Huffman code.
nuclear@26 22 The code lengths are lens[0..codes-1]. The result starts at *table,
nuclear@26 23 whose indices are 0..2^bits-1. work is a writable array of at least
nuclear@26 24 lens shorts, which is used as a work area. type is the type of code
nuclear@26 25 to be generated, CODES, LENS, or DISTS. On return, zero is success,
nuclear@26 26 -1 is an invalid code, and +1 means that ENOUGH isn't enough. table
nuclear@26 27 on return points to the next available entry's address. bits is the
nuclear@26 28 requested root table index bits, and on return it is the actual root
nuclear@26 29 table index bits. It will differ if the request is greater than the
nuclear@26 30 longest code or if it is less than the shortest code.
nuclear@26 31 */
nuclear@26 32 int inflate_table(type, lens, codes, table, bits, work)
nuclear@26 33 codetype type;
nuclear@26 34 unsigned short FAR *lens;
nuclear@26 35 unsigned codes;
nuclear@26 36 code FAR * FAR *table;
nuclear@26 37 unsigned FAR *bits;
nuclear@26 38 unsigned short FAR *work;
nuclear@26 39 {
nuclear@26 40 unsigned len; /* a code's length in bits */
nuclear@26 41 unsigned sym; /* index of code symbols */
nuclear@26 42 unsigned min, max; /* minimum and maximum code lengths */
nuclear@26 43 unsigned root; /* number of index bits for root table */
nuclear@26 44 unsigned curr; /* number of index bits for current table */
nuclear@26 45 unsigned drop; /* code bits to drop for sub-table */
nuclear@26 46 int left; /* number of prefix codes available */
nuclear@26 47 unsigned used; /* code entries in table used */
nuclear@26 48 unsigned huff; /* Huffman code */
nuclear@26 49 unsigned incr; /* for incrementing code, index */
nuclear@26 50 unsigned fill; /* index for replicating entries */
nuclear@26 51 unsigned low; /* low bits for current root entry */
nuclear@26 52 unsigned mask; /* mask for low root bits */
nuclear@26 53 code this; /* table entry for duplication */
nuclear@26 54 code FAR *next; /* next available space in table */
nuclear@26 55 const unsigned short FAR *base; /* base value table to use */
nuclear@26 56 const unsigned short FAR *extra; /* extra bits table to use */
nuclear@26 57 int end; /* use base and extra for symbol > end */
nuclear@26 58 unsigned short count[MAXBITS+1]; /* number of codes of each length */
nuclear@26 59 unsigned short offs[MAXBITS+1]; /* offsets in table for each length */
nuclear@26 60 static const unsigned short lbase[31] = { /* Length codes 257..285 base */
nuclear@26 61 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
nuclear@26 62 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0};
nuclear@26 63 static const unsigned short lext[31] = { /* Length codes 257..285 extra */
nuclear@26 64 16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, 18, 18, 18, 18,
nuclear@26 65 19, 19, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21, 16, 201, 196};
nuclear@26 66 static const unsigned short dbase[32] = { /* Distance codes 0..29 base */
nuclear@26 67 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
nuclear@26 68 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
nuclear@26 69 8193, 12289, 16385, 24577, 0, 0};
nuclear@26 70 static const unsigned short dext[32] = { /* Distance codes 0..29 extra */
nuclear@26 71 16, 16, 16, 16, 17, 17, 18, 18, 19, 19, 20, 20, 21, 21, 22, 22,
nuclear@26 72 23, 23, 24, 24, 25, 25, 26, 26, 27, 27,
nuclear@26 73 28, 28, 29, 29, 64, 64};
nuclear@26 74
nuclear@26 75 /*
nuclear@26 76 Process a set of code lengths to create a canonical Huffman code. The
nuclear@26 77 code lengths are lens[0..codes-1]. Each length corresponds to the
nuclear@26 78 symbols 0..codes-1. The Huffman code is generated by first sorting the
nuclear@26 79 symbols by length from short to long, and retaining the symbol order
nuclear@26 80 for codes with equal lengths. Then the code starts with all zero bits
nuclear@26 81 for the first code of the shortest length, and the codes are integer
nuclear@26 82 increments for the same length, and zeros are appended as the length
nuclear@26 83 increases. For the deflate format, these bits are stored backwards
nuclear@26 84 from their more natural integer increment ordering, and so when the
nuclear@26 85 decoding tables are built in the large loop below, the integer codes
nuclear@26 86 are incremented backwards.
nuclear@26 87
nuclear@26 88 This routine assumes, but does not check, that all of the entries in
nuclear@26 89 lens[] are in the range 0..MAXBITS. The caller must assure this.
nuclear@26 90 1..MAXBITS is interpreted as that code length. zero means that that
nuclear@26 91 symbol does not occur in this code.
nuclear@26 92
nuclear@26 93 The codes are sorted by computing a count of codes for each length,
nuclear@26 94 creating from that a table of starting indices for each length in the
nuclear@26 95 sorted table, and then entering the symbols in order in the sorted
nuclear@26 96 table. The sorted table is work[], with that space being provided by
nuclear@26 97 the caller.
nuclear@26 98
nuclear@26 99 The length counts are used for other purposes as well, i.e. finding
nuclear@26 100 the minimum and maximum length codes, determining if there are any
nuclear@26 101 codes at all, checking for a valid set of lengths, and looking ahead
nuclear@26 102 at length counts to determine sub-table sizes when building the
nuclear@26 103 decoding tables.
nuclear@26 104 */
nuclear@26 105
nuclear@26 106 /* accumulate lengths for codes (assumes lens[] all in 0..MAXBITS) */
nuclear@26 107 for (len = 0; len <= MAXBITS; len++)
nuclear@26 108 count[len] = 0;
nuclear@26 109 for (sym = 0; sym < codes; sym++)
nuclear@26 110 count[lens[sym]]++;
nuclear@26 111
nuclear@26 112 /* bound code lengths, force root to be within code lengths */
nuclear@26 113 root = *bits;
nuclear@26 114 for (max = MAXBITS; max >= 1; max--)
nuclear@26 115 if (count[max] != 0) break;
nuclear@26 116 if (root > max) root = max;
nuclear@26 117 if (max == 0) { /* no symbols to code at all */
nuclear@26 118 this.op = (unsigned char)64; /* invalid code marker */
nuclear@26 119 this.bits = (unsigned char)1;
nuclear@26 120 this.val = (unsigned short)0;
nuclear@26 121 *(*table)++ = this; /* make a table to force an error */
nuclear@26 122 *(*table)++ = this;
nuclear@26 123 *bits = 1;
nuclear@26 124 return 0; /* no symbols, but wait for decoding to report error */
nuclear@26 125 }
nuclear@26 126 for (min = 1; min <= MAXBITS; min++)
nuclear@26 127 if (count[min] != 0) break;
nuclear@26 128 if (root < min) root = min;
nuclear@26 129
nuclear@26 130 /* check for an over-subscribed or incomplete set of lengths */
nuclear@26 131 left = 1;
nuclear@26 132 for (len = 1; len <= MAXBITS; len++) {
nuclear@26 133 left <<= 1;
nuclear@26 134 left -= count[len];
nuclear@26 135 if (left < 0) return -1; /* over-subscribed */
nuclear@26 136 }
nuclear@26 137 if (left > 0 && (type == CODES || max != 1))
nuclear@26 138 return -1; /* incomplete set */
nuclear@26 139
nuclear@26 140 /* generate offsets into symbol table for each length for sorting */
nuclear@26 141 offs[1] = 0;
nuclear@26 142 for (len = 1; len < MAXBITS; len++)
nuclear@26 143 offs[len + 1] = offs[len] + count[len];
nuclear@26 144
nuclear@26 145 /* sort symbols by length, by symbol order within each length */
nuclear@26 146 for (sym = 0; sym < codes; sym++)
nuclear@26 147 if (lens[sym] != 0) work[offs[lens[sym]]++] = (unsigned short)sym;
nuclear@26 148
nuclear@26 149 /*
nuclear@26 150 Create and fill in decoding tables. In this loop, the table being
nuclear@26 151 filled is at next and has curr index bits. The code being used is huff
nuclear@26 152 with length len. That code is converted to an index by dropping drop
nuclear@26 153 bits off of the bottom. For codes where len is less than drop + curr,
nuclear@26 154 those top drop + curr - len bits are incremented through all values to
nuclear@26 155 fill the table with replicated entries.
nuclear@26 156
nuclear@26 157 root is the number of index bits for the root table. When len exceeds
nuclear@26 158 root, sub-tables are created pointed to by the root entry with an index
nuclear@26 159 of the low root bits of huff. This is saved in low to check for when a
nuclear@26 160 new sub-table should be started. drop is zero when the root table is
nuclear@26 161 being filled, and drop is root when sub-tables are being filled.
nuclear@26 162
nuclear@26 163 When a new sub-table is needed, it is necessary to look ahead in the
nuclear@26 164 code lengths to determine what size sub-table is needed. The length
nuclear@26 165 counts are used for this, and so count[] is decremented as codes are
nuclear@26 166 entered in the tables.
nuclear@26 167
nuclear@26 168 used keeps track of how many table entries have been allocated from the
nuclear@26 169 provided *table space. It is checked when a LENS table is being made
nuclear@26 170 against the space in *table, ENOUGH, minus the maximum space needed by
nuclear@26 171 the worst case distance code, MAXD. This should never happen, but the
nuclear@26 172 sufficiency of ENOUGH has not been proven exhaustively, hence the check.
nuclear@26 173 This assumes that when type == LENS, bits == 9.
nuclear@26 174
nuclear@26 175 sym increments through all symbols, and the loop terminates when
nuclear@26 176 all codes of length max, i.e. all codes, have been processed. This
nuclear@26 177 routine permits incomplete codes, so another loop after this one fills
nuclear@26 178 in the rest of the decoding tables with invalid code markers.
nuclear@26 179 */
nuclear@26 180
nuclear@26 181 /* set up for code type */
nuclear@26 182 switch (type) {
nuclear@26 183 case CODES:
nuclear@26 184 base = extra = work; /* dummy value--not used */
nuclear@26 185 end = 19;
nuclear@26 186 break;
nuclear@26 187 case LENS:
nuclear@26 188 base = lbase;
nuclear@26 189 base -= 257;
nuclear@26 190 extra = lext;
nuclear@26 191 extra -= 257;
nuclear@26 192 end = 256;
nuclear@26 193 break;
nuclear@26 194 default: /* DISTS */
nuclear@26 195 base = dbase;
nuclear@26 196 extra = dext;
nuclear@26 197 end = -1;
nuclear@26 198 }
nuclear@26 199
nuclear@26 200 /* initialize state for loop */
nuclear@26 201 huff = 0; /* starting code */
nuclear@26 202 sym = 0; /* starting code symbol */
nuclear@26 203 len = min; /* starting code length */
nuclear@26 204 next = *table; /* current table to fill in */
nuclear@26 205 curr = root; /* current table index bits */
nuclear@26 206 drop = 0; /* current bits to drop from code for index */
nuclear@26 207 low = (unsigned)(-1); /* trigger new sub-table when len > root */
nuclear@26 208 used = 1U << root; /* use root table entries */
nuclear@26 209 mask = used - 1; /* mask for comparing low */
nuclear@26 210
nuclear@26 211 /* check available table space */
nuclear@26 212 if (type == LENS && used >= ENOUGH - MAXD)
nuclear@26 213 return 1;
nuclear@26 214
nuclear@26 215 /* process all codes and make table entries */
nuclear@26 216 for (;;) {
nuclear@26 217 /* create table entry */
nuclear@26 218 this.bits = (unsigned char)(len - drop);
nuclear@26 219 if ((int)(work[sym]) < end) {
nuclear@26 220 this.op = (unsigned char)0;
nuclear@26 221 this.val = work[sym];
nuclear@26 222 }
nuclear@26 223 else if ((int)(work[sym]) > end) {
nuclear@26 224 this.op = (unsigned char)(extra[work[sym]]);
nuclear@26 225 this.val = base[work[sym]];
nuclear@26 226 }
nuclear@26 227 else {
nuclear@26 228 this.op = (unsigned char)(32 + 64); /* end of block */
nuclear@26 229 this.val = 0;
nuclear@26 230 }
nuclear@26 231
nuclear@26 232 /* replicate for those indices with low len bits equal to huff */
nuclear@26 233 incr = 1U << (len - drop);
nuclear@26 234 fill = 1U << curr;
nuclear@26 235 min = fill; /* save offset to next table */
nuclear@26 236 do {
nuclear@26 237 fill -= incr;
nuclear@26 238 next[(huff >> drop) + fill] = this;
nuclear@26 239 } while (fill != 0);
nuclear@26 240
nuclear@26 241 /* backwards increment the len-bit code huff */
nuclear@26 242 incr = 1U << (len - 1);
nuclear@26 243 while (huff & incr)
nuclear@26 244 incr >>= 1;
nuclear@26 245 if (incr != 0) {
nuclear@26 246 huff &= incr - 1;
nuclear@26 247 huff += incr;
nuclear@26 248 }
nuclear@26 249 else
nuclear@26 250 huff = 0;
nuclear@26 251
nuclear@26 252 /* go to next symbol, update count, len */
nuclear@26 253 sym++;
nuclear@26 254 if (--(count[len]) == 0) {
nuclear@26 255 if (len == max) break;
nuclear@26 256 len = lens[work[sym]];
nuclear@26 257 }
nuclear@26 258
nuclear@26 259 /* create new sub-table if needed */
nuclear@26 260 if (len > root && (huff & mask) != low) {
nuclear@26 261 /* if first time, transition to sub-tables */
nuclear@26 262 if (drop == 0)
nuclear@26 263 drop = root;
nuclear@26 264
nuclear@26 265 /* increment past last table */
nuclear@26 266 next += min; /* here min is 1 << curr */
nuclear@26 267
nuclear@26 268 /* determine length of next table */
nuclear@26 269 curr = len - drop;
nuclear@26 270 left = (int)(1 << curr);
nuclear@26 271 while (curr + drop < max) {
nuclear@26 272 left -= count[curr + drop];
nuclear@26 273 if (left <= 0) break;
nuclear@26 274 curr++;
nuclear@26 275 left <<= 1;
nuclear@26 276 }
nuclear@26 277
nuclear@26 278 /* check for enough space */
nuclear@26 279 used += 1U << curr;
nuclear@26 280 if (type == LENS && used >= ENOUGH - MAXD)
nuclear@26 281 return 1;
nuclear@26 282
nuclear@26 283 /* point entry in root table to sub-table */
nuclear@26 284 low = huff & mask;
nuclear@26 285 (*table)[low].op = (unsigned char)curr;
nuclear@26 286 (*table)[low].bits = (unsigned char)root;
nuclear@26 287 (*table)[low].val = (unsigned short)(next - *table);
nuclear@26 288 }
nuclear@26 289 }
nuclear@26 290
nuclear@26 291 /*
nuclear@26 292 Fill in rest of table for incomplete codes. This loop is similar to the
nuclear@26 293 loop above in incrementing huff for table indices. It is assumed that
nuclear@26 294 len is equal to curr + drop, so there is no loop needed to increment
nuclear@26 295 through high index bits. When the current sub-table is filled, the loop
nuclear@26 296 drops back to the root table to fill in any remaining entries there.
nuclear@26 297 */
nuclear@26 298 this.op = (unsigned char)64; /* invalid code marker */
nuclear@26 299 this.bits = (unsigned char)(len - drop);
nuclear@26 300 this.val = (unsigned short)0;
nuclear@26 301 while (huff != 0) {
nuclear@26 302 /* when done with sub-table, drop back to root table */
nuclear@26 303 if (drop != 0 && (huff & mask) != low) {
nuclear@26 304 drop = 0;
nuclear@26 305 len = root;
nuclear@26 306 next = *table;
nuclear@26 307 this.bits = (unsigned char)len;
nuclear@26 308 }
nuclear@26 309
nuclear@26 310 /* put invalid code marker in table */
nuclear@26 311 next[huff >> drop] = this;
nuclear@26 312
nuclear@26 313 /* backwards increment the len-bit code huff */
nuclear@26 314 incr = 1U << (len - 1);
nuclear@26 315 while (huff & incr)
nuclear@26 316 incr >>= 1;
nuclear@26 317 if (incr != 0) {
nuclear@26 318 huff &= incr - 1;
nuclear@26 319 huff += incr;
nuclear@26 320 }
nuclear@26 321 else
nuclear@26 322 huff = 0;
nuclear@26 323 }
nuclear@26 324
nuclear@26 325 /* set return parameters */
nuclear@26 326 *table += used;
nuclear@26 327 *bits = root;
nuclear@26 328 return 0;
nuclear@26 329 }