annotate src/zlib-1.2.8/examples/enough.c @ 169:223a55898ab9 tip default

Add null config files
author Chris Cannam <cannam@all-day-breakfast.com>
date Mon, 02 Mar 2020 14:03:47 +0000
parents 5b4145a0d408
children
rev   line source
cannam@128 1 /* enough.c -- determine the maximum size of inflate's Huffman code tables over
cannam@128 2 * all possible valid and complete Huffman codes, subject to a length limit.
cannam@128 3 * Copyright (C) 2007, 2008, 2012 Mark Adler
cannam@128 4 * Version 1.4 18 August 2012 Mark Adler
cannam@128 5 */
cannam@128 6
cannam@128 7 /* Version history:
cannam@128 8 1.0 3 Jan 2007 First version (derived from codecount.c version 1.4)
cannam@128 9 1.1 4 Jan 2007 Use faster incremental table usage computation
cannam@128 10 Prune examine() search on previously visited states
cannam@128 11 1.2 5 Jan 2007 Comments clean up
cannam@128 12 As inflate does, decrease root for short codes
cannam@128 13 Refuse cases where inflate would increase root
cannam@128 14 1.3 17 Feb 2008 Add argument for initial root table size
cannam@128 15 Fix bug for initial root table size == max - 1
cannam@128 16 Use a macro to compute the history index
cannam@128 17 1.4 18 Aug 2012 Avoid shifts more than bits in type (caused endless loop!)
cannam@128 18 Clean up comparisons of different types
cannam@128 19 Clean up code indentation
cannam@128 20 */
cannam@128 21
cannam@128 22 /*
cannam@128 23 Examine all possible Huffman codes for a given number of symbols and a
cannam@128 24 maximum code length in bits to determine the maximum table size for zilb's
cannam@128 25 inflate. Only complete Huffman codes are counted.
cannam@128 26
cannam@128 27 Two codes are considered distinct if the vectors of the number of codes per
cannam@128 28 length are not identical. So permutations of the symbol assignments result
cannam@128 29 in the same code for the counting, as do permutations of the assignments of
cannam@128 30 the bit values to the codes (i.e. only canonical codes are counted).
cannam@128 31
cannam@128 32 We build a code from shorter to longer lengths, determining how many symbols
cannam@128 33 are coded at each length. At each step, we have how many symbols remain to
cannam@128 34 be coded, what the last code length used was, and how many bit patterns of
cannam@128 35 that length remain unused. Then we add one to the code length and double the
cannam@128 36 number of unused patterns to graduate to the next code length. We then
cannam@128 37 assign all portions of the remaining symbols to that code length that
cannam@128 38 preserve the properties of a correct and eventually complete code. Those
cannam@128 39 properties are: we cannot use more bit patterns than are available; and when
cannam@128 40 all the symbols are used, there are exactly zero possible bit patterns
cannam@128 41 remaining.
cannam@128 42
cannam@128 43 The inflate Huffman decoding algorithm uses two-level lookup tables for
cannam@128 44 speed. There is a single first-level table to decode codes up to root bits
cannam@128 45 in length (root == 9 in the current inflate implementation). The table
cannam@128 46 has 1 << root entries and is indexed by the next root bits of input. Codes
cannam@128 47 shorter than root bits have replicated table entries, so that the correct
cannam@128 48 entry is pointed to regardless of the bits that follow the short code. If
cannam@128 49 the code is longer than root bits, then the table entry points to a second-
cannam@128 50 level table. The size of that table is determined by the longest code with
cannam@128 51 that root-bit prefix. If that longest code has length len, then the table
cannam@128 52 has size 1 << (len - root), to index the remaining bits in that set of
cannam@128 53 codes. Each subsequent root-bit prefix then has its own sub-table. The
cannam@128 54 total number of table entries required by the code is calculated
cannam@128 55 incrementally as the number of codes at each bit length is populated. When
cannam@128 56 all of the codes are shorter than root bits, then root is reduced to the
cannam@128 57 longest code length, resulting in a single, smaller, one-level table.
cannam@128 58
cannam@128 59 The inflate algorithm also provides for small values of root (relative to
cannam@128 60 the log2 of the number of symbols), where the shortest code has more bits
cannam@128 61 than root. In that case, root is increased to the length of the shortest
cannam@128 62 code. This program, by design, does not handle that case, so it is verified
cannam@128 63 that the number of symbols is less than 2^(root + 1).
cannam@128 64
cannam@128 65 In order to speed up the examination (by about ten orders of magnitude for
cannam@128 66 the default arguments), the intermediate states in the build-up of a code
cannam@128 67 are remembered and previously visited branches are pruned. The memory
cannam@128 68 required for this will increase rapidly with the total number of symbols and
cannam@128 69 the maximum code length in bits. However this is a very small price to pay
cannam@128 70 for the vast speedup.
cannam@128 71
cannam@128 72 First, all of the possible Huffman codes are counted, and reachable
cannam@128 73 intermediate states are noted by a non-zero count in a saved-results array.
cannam@128 74 Second, the intermediate states that lead to (root + 1) bit or longer codes
cannam@128 75 are used to look at all sub-codes from those junctures for their inflate
cannam@128 76 memory usage. (The amount of memory used is not affected by the number of
cannam@128 77 codes of root bits or less in length.) Third, the visited states in the
cannam@128 78 construction of those sub-codes and the associated calculation of the table
cannam@128 79 size is recalled in order to avoid recalculating from the same juncture.
cannam@128 80 Beginning the code examination at (root + 1) bit codes, which is enabled by
cannam@128 81 identifying the reachable nodes, accounts for about six of the orders of
cannam@128 82 magnitude of improvement for the default arguments. About another four
cannam@128 83 orders of magnitude come from not revisiting previous states. Out of
cannam@128 84 approximately 2x10^16 possible Huffman codes, only about 2x10^6 sub-codes
cannam@128 85 need to be examined to cover all of the possible table memory usage cases
cannam@128 86 for the default arguments of 286 symbols limited to 15-bit codes.
cannam@128 87
cannam@128 88 Note that an unsigned long long type is used for counting. It is quite easy
cannam@128 89 to exceed the capacity of an eight-byte integer with a large number of
cannam@128 90 symbols and a large maximum code length, so multiple-precision arithmetic
cannam@128 91 would need to replace the unsigned long long arithmetic in that case. This
cannam@128 92 program will abort if an overflow occurs. The big_t type identifies where
cannam@128 93 the counting takes place.
cannam@128 94
cannam@128 95 An unsigned long long type is also used for calculating the number of
cannam@128 96 possible codes remaining at the maximum length. This limits the maximum
cannam@128 97 code length to the number of bits in a long long minus the number of bits
cannam@128 98 needed to represent the symbols in a flat code. The code_t type identifies
cannam@128 99 where the bit pattern counting takes place.
cannam@128 100 */
cannam@128 101
cannam@128 102 #include <stdio.h>
cannam@128 103 #include <stdlib.h>
cannam@128 104 #include <string.h>
cannam@128 105 #include <assert.h>
cannam@128 106
cannam@128 107 #define local static
cannam@128 108
cannam@128 109 /* special data types */
cannam@128 110 typedef unsigned long long big_t; /* type for code counting */
cannam@128 111 typedef unsigned long long code_t; /* type for bit pattern counting */
cannam@128 112 struct tab { /* type for been here check */
cannam@128 113 size_t len; /* length of bit vector in char's */
cannam@128 114 char *vec; /* allocated bit vector */
cannam@128 115 };
cannam@128 116
cannam@128 117 /* The array for saving results, num[], is indexed with this triplet:
cannam@128 118
cannam@128 119 syms: number of symbols remaining to code
cannam@128 120 left: number of available bit patterns at length len
cannam@128 121 len: number of bits in the codes currently being assigned
cannam@128 122
cannam@128 123 Those indices are constrained thusly when saving results:
cannam@128 124
cannam@128 125 syms: 3..totsym (totsym == total symbols to code)
cannam@128 126 left: 2..syms - 1, but only the evens (so syms == 8 -> 2, 4, 6)
cannam@128 127 len: 1..max - 1 (max == maximum code length in bits)
cannam@128 128
cannam@128 129 syms == 2 is not saved since that immediately leads to a single code. left
cannam@128 130 must be even, since it represents the number of available bit patterns at
cannam@128 131 the current length, which is double the number at the previous length.
cannam@128 132 left ends at syms-1 since left == syms immediately results in a single code.
cannam@128 133 (left > sym is not allowed since that would result in an incomplete code.)
cannam@128 134 len is less than max, since the code completes immediately when len == max.
cannam@128 135
cannam@128 136 The offset into the array is calculated for the three indices with the
cannam@128 137 first one (syms) being outermost, and the last one (len) being innermost.
cannam@128 138 We build the array with length max-1 lists for the len index, with syms-3
cannam@128 139 of those for each symbol. There are totsym-2 of those, with each one
cannam@128 140 varying in length as a function of sym. See the calculation of index in
cannam@128 141 count() for the index, and the calculation of size in main() for the size
cannam@128 142 of the array.
cannam@128 143
cannam@128 144 For the deflate example of 286 symbols limited to 15-bit codes, the array
cannam@128 145 has 284,284 entries, taking up 2.17 MB for an 8-byte big_t. More than
cannam@128 146 half of the space allocated for saved results is actually used -- not all
cannam@128 147 possible triplets are reached in the generation of valid Huffman codes.
cannam@128 148 */
cannam@128 149
cannam@128 150 /* The array for tracking visited states, done[], is itself indexed identically
cannam@128 151 to the num[] array as described above for the (syms, left, len) triplet.
cannam@128 152 Each element in the array is further indexed by the (mem, rem) doublet,
cannam@128 153 where mem is the amount of inflate table space used so far, and rem is the
cannam@128 154 remaining unused entries in the current inflate sub-table. Each indexed
cannam@128 155 element is simply one bit indicating whether the state has been visited or
cannam@128 156 not. Since the ranges for mem and rem are not known a priori, each bit
cannam@128 157 vector is of a variable size, and grows as needed to accommodate the visited
cannam@128 158 states. mem and rem are used to calculate a single index in a triangular
cannam@128 159 array. Since the range of mem is expected in the default case to be about
cannam@128 160 ten times larger than the range of rem, the array is skewed to reduce the
cannam@128 161 memory usage, with eight times the range for mem than for rem. See the
cannam@128 162 calculations for offset and bit in beenhere() for the details.
cannam@128 163
cannam@128 164 For the deflate example of 286 symbols limited to 15-bit codes, the bit
cannam@128 165 vectors grow to total approximately 21 MB, in addition to the 4.3 MB done[]
cannam@128 166 array itself.
cannam@128 167 */
cannam@128 168
cannam@128 169 /* Globals to avoid propagating constants or constant pointers recursively */
cannam@128 170 local int max; /* maximum allowed bit length for the codes */
cannam@128 171 local int root; /* size of base code table in bits */
cannam@128 172 local int large; /* largest code table so far */
cannam@128 173 local size_t size; /* number of elements in num and done */
cannam@128 174 local int *code; /* number of symbols assigned to each bit length */
cannam@128 175 local big_t *num; /* saved results array for code counting */
cannam@128 176 local struct tab *done; /* states already evaluated array */
cannam@128 177
cannam@128 178 /* Index function for num[] and done[] */
cannam@128 179 #define INDEX(i,j,k) (((size_t)((i-1)>>1)*((i-2)>>1)+(j>>1)-1)*(max-1)+k-1)
cannam@128 180
cannam@128 181 /* Free allocated space. Uses globals code, num, and done. */
cannam@128 182 local void cleanup(void)
cannam@128 183 {
cannam@128 184 size_t n;
cannam@128 185
cannam@128 186 if (done != NULL) {
cannam@128 187 for (n = 0; n < size; n++)
cannam@128 188 if (done[n].len)
cannam@128 189 free(done[n].vec);
cannam@128 190 free(done);
cannam@128 191 }
cannam@128 192 if (num != NULL)
cannam@128 193 free(num);
cannam@128 194 if (code != NULL)
cannam@128 195 free(code);
cannam@128 196 }
cannam@128 197
cannam@128 198 /* Return the number of possible Huffman codes using bit patterns of lengths
cannam@128 199 len through max inclusive, coding syms symbols, with left bit patterns of
cannam@128 200 length len unused -- return -1 if there is an overflow in the counting.
cannam@128 201 Keep a record of previous results in num to prevent repeating the same
cannam@128 202 calculation. Uses the globals max and num. */
cannam@128 203 local big_t count(int syms, int len, int left)
cannam@128 204 {
cannam@128 205 big_t sum; /* number of possible codes from this juncture */
cannam@128 206 big_t got; /* value returned from count() */
cannam@128 207 int least; /* least number of syms to use at this juncture */
cannam@128 208 int most; /* most number of syms to use at this juncture */
cannam@128 209 int use; /* number of bit patterns to use in next call */
cannam@128 210 size_t index; /* index of this case in *num */
cannam@128 211
cannam@128 212 /* see if only one possible code */
cannam@128 213 if (syms == left)
cannam@128 214 return 1;
cannam@128 215
cannam@128 216 /* note and verify the expected state */
cannam@128 217 assert(syms > left && left > 0 && len < max);
cannam@128 218
cannam@128 219 /* see if we've done this one already */
cannam@128 220 index = INDEX(syms, left, len);
cannam@128 221 got = num[index];
cannam@128 222 if (got)
cannam@128 223 return got; /* we have -- return the saved result */
cannam@128 224
cannam@128 225 /* we need to use at least this many bit patterns so that the code won't be
cannam@128 226 incomplete at the next length (more bit patterns than symbols) */
cannam@128 227 least = (left << 1) - syms;
cannam@128 228 if (least < 0)
cannam@128 229 least = 0;
cannam@128 230
cannam@128 231 /* we can use at most this many bit patterns, lest there not be enough
cannam@128 232 available for the remaining symbols at the maximum length (if there were
cannam@128 233 no limit to the code length, this would become: most = left - 1) */
cannam@128 234 most = (((code_t)left << (max - len)) - syms) /
cannam@128 235 (((code_t)1 << (max - len)) - 1);
cannam@128 236
cannam@128 237 /* count all possible codes from this juncture and add them up */
cannam@128 238 sum = 0;
cannam@128 239 for (use = least; use <= most; use++) {
cannam@128 240 got = count(syms - use, len + 1, (left - use) << 1);
cannam@128 241 sum += got;
cannam@128 242 if (got == (big_t)0 - 1 || sum < got) /* overflow */
cannam@128 243 return (big_t)0 - 1;
cannam@128 244 }
cannam@128 245
cannam@128 246 /* verify that all recursive calls are productive */
cannam@128 247 assert(sum != 0);
cannam@128 248
cannam@128 249 /* save the result and return it */
cannam@128 250 num[index] = sum;
cannam@128 251 return sum;
cannam@128 252 }
cannam@128 253
cannam@128 254 /* Return true if we've been here before, set to true if not. Set a bit in a
cannam@128 255 bit vector to indicate visiting this state. Each (syms,len,left) state
cannam@128 256 has a variable size bit vector indexed by (mem,rem). The bit vector is
cannam@128 257 lengthened if needed to allow setting the (mem,rem) bit. */
cannam@128 258 local int beenhere(int syms, int len, int left, int mem, int rem)
cannam@128 259 {
cannam@128 260 size_t index; /* index for this state's bit vector */
cannam@128 261 size_t offset; /* offset in this state's bit vector */
cannam@128 262 int bit; /* mask for this state's bit */
cannam@128 263 size_t length; /* length of the bit vector in bytes */
cannam@128 264 char *vector; /* new or enlarged bit vector */
cannam@128 265
cannam@128 266 /* point to vector for (syms,left,len), bit in vector for (mem,rem) */
cannam@128 267 index = INDEX(syms, left, len);
cannam@128 268 mem -= 1 << root;
cannam@128 269 offset = (mem >> 3) + rem;
cannam@128 270 offset = ((offset * (offset + 1)) >> 1) + rem;
cannam@128 271 bit = 1 << (mem & 7);
cannam@128 272
cannam@128 273 /* see if we've been here */
cannam@128 274 length = done[index].len;
cannam@128 275 if (offset < length && (done[index].vec[offset] & bit) != 0)
cannam@128 276 return 1; /* done this! */
cannam@128 277
cannam@128 278 /* we haven't been here before -- set the bit to show we have now */
cannam@128 279
cannam@128 280 /* see if we need to lengthen the vector in order to set the bit */
cannam@128 281 if (length <= offset) {
cannam@128 282 /* if we have one already, enlarge it, zero out the appended space */
cannam@128 283 if (length) {
cannam@128 284 do {
cannam@128 285 length <<= 1;
cannam@128 286 } while (length <= offset);
cannam@128 287 vector = realloc(done[index].vec, length);
cannam@128 288 if (vector != NULL)
cannam@128 289 memset(vector + done[index].len, 0, length - done[index].len);
cannam@128 290 }
cannam@128 291
cannam@128 292 /* otherwise we need to make a new vector and zero it out */
cannam@128 293 else {
cannam@128 294 length = 1 << (len - root);
cannam@128 295 while (length <= offset)
cannam@128 296 length <<= 1;
cannam@128 297 vector = calloc(length, sizeof(char));
cannam@128 298 }
cannam@128 299
cannam@128 300 /* in either case, bail if we can't get the memory */
cannam@128 301 if (vector == NULL) {
cannam@128 302 fputs("abort: unable to allocate enough memory\n", stderr);
cannam@128 303 cleanup();
cannam@128 304 exit(1);
cannam@128 305 }
cannam@128 306
cannam@128 307 /* install the new vector */
cannam@128 308 done[index].len = length;
cannam@128 309 done[index].vec = vector;
cannam@128 310 }
cannam@128 311
cannam@128 312 /* set the bit */
cannam@128 313 done[index].vec[offset] |= bit;
cannam@128 314 return 0;
cannam@128 315 }
cannam@128 316
cannam@128 317 /* Examine all possible codes from the given node (syms, len, left). Compute
cannam@128 318 the amount of memory required to build inflate's decoding tables, where the
cannam@128 319 number of code structures used so far is mem, and the number remaining in
cannam@128 320 the current sub-table is rem. Uses the globals max, code, root, large, and
cannam@128 321 done. */
cannam@128 322 local void examine(int syms, int len, int left, int mem, int rem)
cannam@128 323 {
cannam@128 324 int least; /* least number of syms to use at this juncture */
cannam@128 325 int most; /* most number of syms to use at this juncture */
cannam@128 326 int use; /* number of bit patterns to use in next call */
cannam@128 327
cannam@128 328 /* see if we have a complete code */
cannam@128 329 if (syms == left) {
cannam@128 330 /* set the last code entry */
cannam@128 331 code[len] = left;
cannam@128 332
cannam@128 333 /* complete computation of memory used by this code */
cannam@128 334 while (rem < left) {
cannam@128 335 left -= rem;
cannam@128 336 rem = 1 << (len - root);
cannam@128 337 mem += rem;
cannam@128 338 }
cannam@128 339 assert(rem == left);
cannam@128 340
cannam@128 341 /* if this is a new maximum, show the entries used and the sub-code */
cannam@128 342 if (mem > large) {
cannam@128 343 large = mem;
cannam@128 344 printf("max %d: ", mem);
cannam@128 345 for (use = root + 1; use <= max; use++)
cannam@128 346 if (code[use])
cannam@128 347 printf("%d[%d] ", code[use], use);
cannam@128 348 putchar('\n');
cannam@128 349 fflush(stdout);
cannam@128 350 }
cannam@128 351
cannam@128 352 /* remove entries as we drop back down in the recursion */
cannam@128 353 code[len] = 0;
cannam@128 354 return;
cannam@128 355 }
cannam@128 356
cannam@128 357 /* prune the tree if we can */
cannam@128 358 if (beenhere(syms, len, left, mem, rem))
cannam@128 359 return;
cannam@128 360
cannam@128 361 /* we need to use at least this many bit patterns so that the code won't be
cannam@128 362 incomplete at the next length (more bit patterns than symbols) */
cannam@128 363 least = (left << 1) - syms;
cannam@128 364 if (least < 0)
cannam@128 365 least = 0;
cannam@128 366
cannam@128 367 /* we can use at most this many bit patterns, lest there not be enough
cannam@128 368 available for the remaining symbols at the maximum length (if there were
cannam@128 369 no limit to the code length, this would become: most = left - 1) */
cannam@128 370 most = (((code_t)left << (max - len)) - syms) /
cannam@128 371 (((code_t)1 << (max - len)) - 1);
cannam@128 372
cannam@128 373 /* occupy least table spaces, creating new sub-tables as needed */
cannam@128 374 use = least;
cannam@128 375 while (rem < use) {
cannam@128 376 use -= rem;
cannam@128 377 rem = 1 << (len - root);
cannam@128 378 mem += rem;
cannam@128 379 }
cannam@128 380 rem -= use;
cannam@128 381
cannam@128 382 /* examine codes from here, updating table space as we go */
cannam@128 383 for (use = least; use <= most; use++) {
cannam@128 384 code[len] = use;
cannam@128 385 examine(syms - use, len + 1, (left - use) << 1,
cannam@128 386 mem + (rem ? 1 << (len - root) : 0), rem << 1);
cannam@128 387 if (rem == 0) {
cannam@128 388 rem = 1 << (len - root);
cannam@128 389 mem += rem;
cannam@128 390 }
cannam@128 391 rem--;
cannam@128 392 }
cannam@128 393
cannam@128 394 /* remove entries as we drop back down in the recursion */
cannam@128 395 code[len] = 0;
cannam@128 396 }
cannam@128 397
cannam@128 398 /* Look at all sub-codes starting with root + 1 bits. Look at only the valid
cannam@128 399 intermediate code states (syms, left, len). For each completed code,
cannam@128 400 calculate the amount of memory required by inflate to build the decoding
cannam@128 401 tables. Find the maximum amount of memory required and show the code that
cannam@128 402 requires that maximum. Uses the globals max, root, and num. */
cannam@128 403 local void enough(int syms)
cannam@128 404 {
cannam@128 405 int n; /* number of remaing symbols for this node */
cannam@128 406 int left; /* number of unused bit patterns at this length */
cannam@128 407 size_t index; /* index of this case in *num */
cannam@128 408
cannam@128 409 /* clear code */
cannam@128 410 for (n = 0; n <= max; n++)
cannam@128 411 code[n] = 0;
cannam@128 412
cannam@128 413 /* look at all (root + 1) bit and longer codes */
cannam@128 414 large = 1 << root; /* base table */
cannam@128 415 if (root < max) /* otherwise, there's only a base table */
cannam@128 416 for (n = 3; n <= syms; n++)
cannam@128 417 for (left = 2; left < n; left += 2)
cannam@128 418 {
cannam@128 419 /* look at all reachable (root + 1) bit nodes, and the
cannam@128 420 resulting codes (complete at root + 2 or more) */
cannam@128 421 index = INDEX(n, left, root + 1);
cannam@128 422 if (root + 1 < max && num[index]) /* reachable node */
cannam@128 423 examine(n, root + 1, left, 1 << root, 0);
cannam@128 424
cannam@128 425 /* also look at root bit codes with completions at root + 1
cannam@128 426 bits (not saved in num, since complete), just in case */
cannam@128 427 if (num[index - 1] && n <= left << 1)
cannam@128 428 examine((n - left) << 1, root + 1, (n - left) << 1,
cannam@128 429 1 << root, 0);
cannam@128 430 }
cannam@128 431
cannam@128 432 /* done */
cannam@128 433 printf("done: maximum of %d table entries\n", large);
cannam@128 434 }
cannam@128 435
cannam@128 436 /*
cannam@128 437 Examine and show the total number of possible Huffman codes for a given
cannam@128 438 maximum number of symbols, initial root table size, and maximum code length
cannam@128 439 in bits -- those are the command arguments in that order. The default
cannam@128 440 values are 286, 9, and 15 respectively, for the deflate literal/length code.
cannam@128 441 The possible codes are counted for each number of coded symbols from two to
cannam@128 442 the maximum. The counts for each of those and the total number of codes are
cannam@128 443 shown. The maximum number of inflate table entires is then calculated
cannam@128 444 across all possible codes. Each new maximum number of table entries and the
cannam@128 445 associated sub-code (starting at root + 1 == 10 bits) is shown.
cannam@128 446
cannam@128 447 To count and examine Huffman codes that are not length-limited, provide a
cannam@128 448 maximum length equal to the number of symbols minus one.
cannam@128 449
cannam@128 450 For the deflate literal/length code, use "enough". For the deflate distance
cannam@128 451 code, use "enough 30 6".
cannam@128 452
cannam@128 453 This uses the %llu printf format to print big_t numbers, which assumes that
cannam@128 454 big_t is an unsigned long long. If the big_t type is changed (for example
cannam@128 455 to a multiple precision type), the method of printing will also need to be
cannam@128 456 updated.
cannam@128 457 */
cannam@128 458 int main(int argc, char **argv)
cannam@128 459 {
cannam@128 460 int syms; /* total number of symbols to code */
cannam@128 461 int n; /* number of symbols to code for this run */
cannam@128 462 big_t got; /* return value of count() */
cannam@128 463 big_t sum; /* accumulated number of codes over n */
cannam@128 464 code_t word; /* for counting bits in code_t */
cannam@128 465
cannam@128 466 /* set up globals for cleanup() */
cannam@128 467 code = NULL;
cannam@128 468 num = NULL;
cannam@128 469 done = NULL;
cannam@128 470
cannam@128 471 /* get arguments -- default to the deflate literal/length code */
cannam@128 472 syms = 286;
cannam@128 473 root = 9;
cannam@128 474 max = 15;
cannam@128 475 if (argc > 1) {
cannam@128 476 syms = atoi(argv[1]);
cannam@128 477 if (argc > 2) {
cannam@128 478 root = atoi(argv[2]);
cannam@128 479 if (argc > 3)
cannam@128 480 max = atoi(argv[3]);
cannam@128 481 }
cannam@128 482 }
cannam@128 483 if (argc > 4 || syms < 2 || root < 1 || max < 1) {
cannam@128 484 fputs("invalid arguments, need: [sym >= 2 [root >= 1 [max >= 1]]]\n",
cannam@128 485 stderr);
cannam@128 486 return 1;
cannam@128 487 }
cannam@128 488
cannam@128 489 /* if not restricting the code length, the longest is syms - 1 */
cannam@128 490 if (max > syms - 1)
cannam@128 491 max = syms - 1;
cannam@128 492
cannam@128 493 /* determine the number of bits in a code_t */
cannam@128 494 for (n = 0, word = 1; word; n++, word <<= 1)
cannam@128 495 ;
cannam@128 496
cannam@128 497 /* make sure that the calculation of most will not overflow */
cannam@128 498 if (max > n || (code_t)(syms - 2) >= (((code_t)0 - 1) >> (max - 1))) {
cannam@128 499 fputs("abort: code length too long for internal types\n", stderr);
cannam@128 500 return 1;
cannam@128 501 }
cannam@128 502
cannam@128 503 /* reject impossible code requests */
cannam@128 504 if ((code_t)(syms - 1) > ((code_t)1 << max) - 1) {
cannam@128 505 fprintf(stderr, "%d symbols cannot be coded in %d bits\n",
cannam@128 506 syms, max);
cannam@128 507 return 1;
cannam@128 508 }
cannam@128 509
cannam@128 510 /* allocate code vector */
cannam@128 511 code = calloc(max + 1, sizeof(int));
cannam@128 512 if (code == NULL) {
cannam@128 513 fputs("abort: unable to allocate enough memory\n", stderr);
cannam@128 514 return 1;
cannam@128 515 }
cannam@128 516
cannam@128 517 /* determine size of saved results array, checking for overflows,
cannam@128 518 allocate and clear the array (set all to zero with calloc()) */
cannam@128 519 if (syms == 2) /* iff max == 1 */
cannam@128 520 num = NULL; /* won't be saving any results */
cannam@128 521 else {
cannam@128 522 size = syms >> 1;
cannam@128 523 if (size > ((size_t)0 - 1) / (n = (syms - 1) >> 1) ||
cannam@128 524 (size *= n, size > ((size_t)0 - 1) / (n = max - 1)) ||
cannam@128 525 (size *= n, size > ((size_t)0 - 1) / sizeof(big_t)) ||
cannam@128 526 (num = calloc(size, sizeof(big_t))) == NULL) {
cannam@128 527 fputs("abort: unable to allocate enough memory\n", stderr);
cannam@128 528 cleanup();
cannam@128 529 return 1;
cannam@128 530 }
cannam@128 531 }
cannam@128 532
cannam@128 533 /* count possible codes for all numbers of symbols, add up counts */
cannam@128 534 sum = 0;
cannam@128 535 for (n = 2; n <= syms; n++) {
cannam@128 536 got = count(n, 1, 2);
cannam@128 537 sum += got;
cannam@128 538 if (got == (big_t)0 - 1 || sum < got) { /* overflow */
cannam@128 539 fputs("abort: can't count that high!\n", stderr);
cannam@128 540 cleanup();
cannam@128 541 return 1;
cannam@128 542 }
cannam@128 543 printf("%llu %d-codes\n", got, n);
cannam@128 544 }
cannam@128 545 printf("%llu total codes for 2 to %d symbols", sum, syms);
cannam@128 546 if (max < syms - 1)
cannam@128 547 printf(" (%d-bit length limit)\n", max);
cannam@128 548 else
cannam@128 549 puts(" (no length limit)");
cannam@128 550
cannam@128 551 /* allocate and clear done array for beenhere() */
cannam@128 552 if (syms == 2)
cannam@128 553 done = NULL;
cannam@128 554 else if (size > ((size_t)0 - 1) / sizeof(struct tab) ||
cannam@128 555 (done = calloc(size, sizeof(struct tab))) == NULL) {
cannam@128 556 fputs("abort: unable to allocate enough memory\n", stderr);
cannam@128 557 cleanup();
cannam@128 558 return 1;
cannam@128 559 }
cannam@128 560
cannam@128 561 /* find and show maximum inflate table usage */
cannam@128 562 if (root > max) /* reduce root to max length */
cannam@128 563 root = max;
cannam@128 564 if ((code_t)syms < ((code_t)1 << (root + 1)))
cannam@128 565 enough(syms);
cannam@128 566 else
cannam@128 567 puts("cannot handle minimum code lengths > root");
cannam@128 568
cannam@128 569 /* done */
cannam@128 570 cleanup();
cannam@128 571 return 0;
cannam@128 572 }