istereo2

annotate libs/zlib/inftrees.c @ 20:2b85d05df3f2

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