dbf-halloween2015

annotate libs/zlib/inftrees.c @ 1:c3f5c32cb210

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