lemon-project-template-glpk

annotate deps/glpk/src/zlib/inftrees.c @ 9:33de93886c88

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