vrshoot

annotate libs/zlib/inftrees.c @ 0:b2f14e535253

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