Wei Chang Shen / DMemWin

Dependencies:   emwin_lib

Fork of DMemWin by Embedded Artists

png/inftrees.c@4:20387dbf7ecf, 2016-06-02 (annotated)

Committer:
destinyXfate
Date:
Thu Jun 02 04:55:08 2016 +0000
Revision:
4:20387dbf7ecf
Parent:
2:0e2ef1edf01b 
;

Who changed what in which revision?

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