| /* enough.c -- determine the maximum size of inflate's Huffman code tables over |
| * all possible valid and complete prefix codes, subject to a length limit. |
| * Copyright (C) 2007, 2008, 2012, 2018 Mark Adler |
| * Version 1.5 5 August 2018 Mark Adler |
| */ |
| |
| /* Version history: |
| 1.0 3 Jan 2007 First version (derived from codecount.c version 1.4) |
| 1.1 4 Jan 2007 Use faster incremental table usage computation |
| Prune examine() search on previously visited states |
| 1.2 5 Jan 2007 Comments clean up |
| As inflate does, decrease root for short codes |
| Refuse cases where inflate would increase root |
| 1.3 17 Feb 2008 Add argument for initial root table size |
| Fix bug for initial root table size == max - 1 |
| Use a macro to compute the history index |
| 1.4 18 Aug 2012 Avoid shifts more than bits in type (caused endless loop!) |
| Clean up comparisons of different types |
| Clean up code indentation |
| 1.5 5 Aug 2018 Clean up code style, formatting, and comments |
| Show all the codes for the maximum, and only the maximum |
| */ |
| |
| /* |
| Examine all possible prefix codes for a given number of symbols and a |
| maximum code length in bits to determine the maximum table size for zlib's |
| inflate. Only complete prefix codes are counted. |
| |
| Two codes are considered distinct if the vectors of the number of codes per |
| length are not identical. So permutations of the symbol assignments result |
| in the same code for the counting, as do permutations of the assignments of |
| the bit values to the codes (i.e. only canonical codes are counted). |
| |
| We build a code from shorter to longer lengths, determining how many symbols |
| are coded at each length. At each step, we have how many symbols remain to |
| be coded, what the last code length used was, and how many bit patterns of |
| that length remain unused. Then we add one to the code length and double the |
| number of unused patterns to graduate to the next code length. We then |
| assign all portions of the remaining symbols to that code length that |
| preserve the properties of a correct and eventually complete code. Those |
| properties are: we cannot use more bit patterns than are available; and when |
| all the symbols are used, there are exactly zero possible bit patterns left |
| unused. |
| |
| The inflate Huffman decoding algorithm uses two-level lookup tables for |
| speed. There is a single first-level table to decode codes up to root bits |
| in length (root == 9 for literal/length codes and root == 6 for distance |
| codes, in the current inflate implementation). The base table has 1 << root |
| entries and is indexed by the next root bits of input. Codes shorter than |
| root bits have replicated table entries, so that the correct entry is |
| pointed to regardless of the bits that follow the short code. If the code is |
| longer than root bits, then the table entry points to a second-level table. |
| The size of that table is determined by the longest code with that root-bit |
| prefix. If that longest code has length len, then the table has size 1 << |
| (len - root), to index the remaining bits in that set of codes. Each |
| subsequent root-bit prefix then has its own sub-table. The total number of |
| table entries required by the code is calculated incrementally as the number |
| of codes at each bit length is populated. When all of the codes are shorter |
| than root bits, then root is reduced to the longest code length, resulting |
| in a single, smaller, one-level table. |
| |
| The inflate algorithm also provides for small values of root (relative to |
| the log2 of the number of symbols), where the shortest code has more bits |
| than root. In that case, root is increased to the length of the shortest |
| code. This program, by design, does not handle that case, so it is verified |
| that the number of symbols is less than 1 << (root + 1). |
| |
| In order to speed up the examination (by about ten orders of magnitude for |
| the default arguments), the intermediate states in the build-up of a code |
| are remembered and previously visited branches are pruned. The memory |
| required for this will increase rapidly with the total number of symbols and |
| the maximum code length in bits. However this is a very small price to pay |
| for the vast speedup. |
| |
| First, all of the possible prefix codes are counted, and reachable |
| intermediate states are noted by a non-zero count in a saved-results array. |
| Second, the intermediate states that lead to (root + 1) bit or longer codes |
| are used to look at all sub-codes from those junctures for their inflate |
| memory usage. (The amount of memory used is not affected by the number of |
| codes of root bits or less in length.) Third, the visited states in the |
| construction of those sub-codes and the associated calculation of the table |
| size is recalled in order to avoid recalculating from the same juncture. |
| Beginning the code examination at (root + 1) bit codes, which is enabled by |
| identifying the reachable nodes, accounts for about six of the orders of |
| magnitude of improvement for the default arguments. About another four |
| orders of magnitude come from not revisiting previous states. Out of |
| approximately 2x10^16 possible prefix codes, only about 2x10^6 sub-codes |
| need to be examined to cover all of the possible table memory usage cases |
| for the default arguments of 286 symbols limited to 15-bit codes. |
| |
| Note that the uintmax_t type is used for counting. It is quite easy to |
| exceed the capacity of an eight-byte integer with a large number of symbols |
| and a large maximum code length, so multiple-precision arithmetic would need |
| to replace the integer arithmetic in that case. This program will abort if |
| an overflow occurs. The big_t type identifies where the counting takes |
| place. |
| |
| The uintmax_t type is also used for calculating the number of possible codes |
| remaining at the maximum length. This limits the maximum code length to the |
| number of bits in a long long minus the number of bits needed to represent |
| the symbols in a flat code. The code_t type identifies where the bit-pattern |
| counting takes place. |
| */ |
| |
| #include <stdio.h> |
| #include <stdlib.h> |
| #include <string.h> |
| #include <stdarg.h> |
| #include <stdint.h> |
| #include <assert.h> |
| |
| #define local static |
| |
| // Special data types. |
| typedef uintmax_t big_t; // type for code counting |
| #define PRIbig "ju" // printf format for big_t |
| typedef uintmax_t code_t; // type for bit pattern counting |
| struct tab { // type for been-here check |
| size_t len; // allocated length of bit vector in octets |
| char *vec; // allocated bit vector |
| }; |
| |
| /* The array for saving results, num[], is indexed with this triplet: |
| |
| syms: number of symbols remaining to code |
| left: number of available bit patterns at length len |
| len: number of bits in the codes currently being assigned |
| |
| Those indices are constrained thusly when saving results: |
| |
| syms: 3..totsym (totsym == total symbols to code) |
| left: 2..syms - 1, but only the evens (so syms == 8 -> 2, 4, 6) |
| len: 1..max - 1 (max == maximum code length in bits) |
| |
| syms == 2 is not saved since that immediately leads to a single code. left |
| must be even, since it represents the number of available bit patterns at |
| the current length, which is double the number at the previous length. left |
| ends at syms-1 since left == syms immediately results in a single code. |
| (left > sym is not allowed since that would result in an incomplete code.) |
| len is less than max, since the code completes immediately when len == max. |
| |
| The offset into the array is calculated for the three indices with the first |
| one (syms) being outermost, and the last one (len) being innermost. We build |
| the array with length max-1 lists for the len index, with syms-3 of those |
| for each symbol. There are totsym-2 of those, with each one varying in |
| length as a function of sym. See the calculation of index in map() for the |
| index, and the calculation of size in main() for the size of the array. |
| |
| For the deflate example of 286 symbols limited to 15-bit codes, the array |
| has 284,284 entries, taking up 2.17 MB for an 8-byte big_t. More than half |
| of the space allocated for saved results is actually used -- not all |
| possible triplets are reached in the generation of valid prefix codes. |
| */ |
| |
| /* The array for tracking visited states, done[], is itself indexed identically |
| to the num[] array as described above for the (syms, left, len) triplet. |
| Each element in the array is further indexed by the (mem, rem) doublet, |
| where mem is the amount of inflate table space used so far, and rem is the |
| remaining unused entries in the current inflate sub-table. Each indexed |
| element is simply one bit indicating whether the state has been visited or |
| not. Since the ranges for mem and rem are not known a priori, each bit |
| vector is of a variable size, and grows as needed to accommodate the visited |
| states. mem and rem are used to calculate a single index in a triangular |
| array. Since the range of mem is expected in the default case to be about |
| ten times larger than the range of rem, the array is skewed to reduce the |
| memory usage, with eight times the range for mem than for rem. See the |
| calculations for offset and bit in been_here() for the details. |
| |
| For the deflate example of 286 symbols limited to 15-bit codes, the bit |
| vectors grow to total 5.5 MB, in addition to the 4.3 MB done array itself. |
| */ |
| |
| // Type for a variable-length, allocated string. |
| typedef struct { |
| char *str; // pointer to allocated string |
| size_t size; // size of allocation |
| size_t len; // length of string, not including terminating zero |
| } string_t; |
| |
| // Clear a string_t. |
| local void string_clear(string_t *s) { |
| s->str[0] = 0; |
| s->len = 0; |
| } |
| |
| // Initialize a string_t. |
| local void string_init(string_t *s) { |
| s->size = 16; |
| s->str = malloc(s->size); |
| assert(s->str != NULL && "out of memory"); |
| string_clear(s); |
| } |
| |
| // Release the allocation of a string_t. |
| local void string_free(string_t *s) { |
| free(s->str); |
| s->str = NULL; |
| s->size = 0; |
| s->len = 0; |
| } |
| |
| // Save the results of printf with fmt and the subsequent argument list to s. |
| // Each call appends to s. The allocated space for s is increased as needed. |
| local void string_printf(string_t *s, char *fmt, ...) { |
| va_list ap; |
| va_start(ap, fmt); |
| size_t len = s->len; |
| int ret = vsnprintf(s->str + len, s->size - len, fmt, ap); |
| assert(ret >= 0 && "out of memory"); |
| s->len += ret; |
| if (s->size < s->len + 1) { |
| do { |
| s->size <<= 1; |
| assert(s->size != 0 && "overflow"); |
| } while (s->size < s->len + 1); |
| s->str = realloc(s->str, s->size); |
| assert(s->str != NULL && "out of memory"); |
| vsnprintf(s->str + len, s->size - len, fmt, ap); |
| } |
| va_end(ap); |
| } |
| |
| // Globals to avoid propagating constants or constant pointers recursively. |
| struct { |
| int max; // maximum allowed bit length for the codes |
| int root; // size of base code table in bits |
| int large; // largest code table so far |
| size_t size; // number of elements in num and done |
| big_t tot; // total number of codes with maximum tables size |
| string_t out; // display of subcodes for maximum tables size |
| int *code; // number of symbols assigned to each bit length |
| big_t *num; // saved results array for code counting |
| struct tab *done; // states already evaluated array |
| } g; |
| |
| // Index function for num[] and done[]. |
| local inline size_t map(int syms, int left, int len) { |
| return ((size_t)((syms - 1) >> 1) * ((syms - 2) >> 1) + |
| (left >> 1) - 1) * (g.max - 1) + |
| len - 1; |
| } |
| |
| // Free allocated space in globals. |
| local void cleanup(void) { |
| if (g.done != NULL) { |
| for (size_t n = 0; n < g.size; n++) |
| if (g.done[n].len) |
| free(g.done[n].vec); |
| g.size = 0; |
| free(g.done); g.done = NULL; |
| } |
| free(g.num); g.num = NULL; |
| free(g.code); g.code = NULL; |
| string_free(&g.out); |
| } |
| |
| // Return the number of possible prefix codes using bit patterns of lengths len |
| // through max inclusive, coding syms symbols, with left bit patterns of length |
| // len unused -- return -1 if there is an overflow in the counting. Keep a |
| // record of previous results in num to prevent repeating the same calculation. |
| local big_t count(int syms, int left, int len) { |
| // see if only one possible code |
| if (syms == left) |
| return 1; |
| |
| // note and verify the expected state |
| assert(syms > left && left > 0 && len < g.max); |
| |
| // see if we've done this one already |
| size_t index = map(syms, left, len); |
| big_t got = g.num[index]; |
| if (got) |
| return got; // we have -- return the saved result |
| |
| // we need to use at least this many bit patterns so that the code won't be |
| // incomplete at the next length (more bit patterns than symbols) |
| int least = (left << 1) - syms; |
| if (least < 0) |
| least = 0; |
| |
| // we can use at most this many bit patterns, lest there not be enough |
| // available for the remaining symbols at the maximum length (if there were |
| // no limit to the code length, this would become: most = left - 1) |
| int most = (((code_t)left << (g.max - len)) - syms) / |
| (((code_t)1 << (g.max - len)) - 1); |
| |
| // count all possible codes from this juncture and add them up |
| big_t sum = 0; |
| for (int use = least; use <= most; use++) { |
| got = count(syms - use, (left - use) << 1, len + 1); |
| sum += got; |
| if (got == (big_t)-1 || sum < got) // overflow |
| return (big_t)-1; |
| } |
| |
| // verify that all recursive calls are productive |
| assert(sum != 0); |
| |
| // save the result and return it |
| g.num[index] = sum; |
| return sum; |
| } |
| |
| // Return true if we've been here before, set to true if not. Set a bit in a |
| // bit vector to indicate visiting this state. Each (syms,len,left) state has a |
| // variable size bit vector indexed by (mem,rem). The bit vector is lengthened |
| // as needed to allow setting the (mem,rem) bit. |
| local int been_here(int syms, int left, int len, int mem, int rem) { |
| // point to vector for (syms,left,len), bit in vector for (mem,rem) |
| size_t index = map(syms, left, len); |
| mem -= 1 << g.root; // mem always includes the root table |
| mem >>= 1; // mem and rem are always even |
| rem >>= 1; |
| size_t offset = (mem >> 3) + rem; |
| offset = ((offset * (offset + 1)) >> 1) + rem; |
| int bit = 1 << (mem & 7); |
| |
| // see if we've been here |
| size_t length = g.done[index].len; |
| if (offset < length && (g.done[index].vec[offset] & bit) != 0) |
| return 1; // done this! |
| |
| // we haven't been here before -- set the bit to show we have now |
| |
| // see if we need to lengthen the vector in order to set the bit |
| if (length <= offset) { |
| // if we have one already, enlarge it, zero out the appended space |
| char *vector; |
| if (length) { |
| do { |
| length <<= 1; |
| } while (length <= offset); |
| vector = realloc(g.done[index].vec, length); |
| assert(vector != NULL && "out of memory"); |
| memset(vector + g.done[index].len, 0, length - g.done[index].len); |
| } |
| |
| // otherwise we need to make a new vector and zero it out |
| else { |
| length = 16; |
| while (length <= offset) |
| length <<= 1; |
| vector = calloc(length, 1); |
| assert(vector != NULL && "out of memory"); |
| } |
| |
| // install the new vector |
| g.done[index].len = length; |
| g.done[index].vec = vector; |
| } |
| |
| // set the bit |
| g.done[index].vec[offset] |= bit; |
| return 0; |
| } |
| |
| // Examine all possible codes from the given node (syms, len, left). Compute |
| // the amount of memory required to build inflate's decoding tables, where the |
| // number of code structures used so far is mem, and the number remaining in |
| // the current sub-table is rem. |
| local void examine(int syms, int left, int len, int mem, int rem) { |
| // see if we have a complete code |
| if (syms == left) { |
| // set the last code entry |
| g.code[len] = left; |
| |
| // complete computation of memory used by this code |
| while (rem < left) { |
| left -= rem; |
| rem = 1 << (len - g.root); |
| mem += rem; |
| } |
| assert(rem == left); |
| |
| // if this is at the maximum, show the sub-code |
| if (mem >= g.large) { |
| // if this is a new maximum, update the maximum and clear out the |
| // printed sub-codes from the previous maximum |
| if (mem > g.large) { |
| g.large = mem; |
| string_clear(&g.out); |
| } |
| |
| // compute the starting state for this sub-code |
| syms = 0; |
| left = 1 << g.max; |
| for (int bits = g.max; bits > g.root; bits--) { |
| syms += g.code[bits]; |
| left -= g.code[bits]; |
| assert((left & 1) == 0); |
| left >>= 1; |
| } |
| |
| // print the starting state and the resulting sub-code to g.out |
| string_printf(&g.out, "<%u, %u, %u>:", |
| syms, g.root + 1, ((1 << g.root) - left) << 1); |
| for (int bits = g.root + 1; bits <= g.max; bits++) |
| if (g.code[bits]) |
| string_printf(&g.out, " %d[%d]", g.code[bits], bits); |
| string_printf(&g.out, "\n"); |
| } |
| |
| // remove entries as we drop back down in the recursion |
| g.code[len] = 0; |
| return; |
| } |
| |
| // prune the tree if we can |
| if (been_here(syms, left, len, mem, rem)) |
| return; |
| |
| // we need to use at least this many bit patterns so that the code won't be |
| // incomplete at the next length (more bit patterns than symbols) |
| int least = (left << 1) - syms; |
| if (least < 0) |
| least = 0; |
| |
| // we can use at most this many bit patterns, lest there not be enough |
| // available for the remaining symbols at the maximum length (if there were |
| // no limit to the code length, this would become: most = left - 1) |
| int most = (((code_t)left << (g.max - len)) - syms) / |
| (((code_t)1 << (g.max - len)) - 1); |
| |
| // occupy least table spaces, creating new sub-tables as needed |
| int use = least; |
| while (rem < use) { |
| use -= rem; |
| rem = 1 << (len - g.root); |
| mem += rem; |
| } |
| rem -= use; |
| |
| // examine codes from here, updating table space as we go |
| for (use = least; use <= most; use++) { |
| g.code[len] = use; |
| examine(syms - use, (left - use) << 1, len + 1, |
| mem + (rem ? 1 << (len - g.root) : 0), rem << 1); |
| if (rem == 0) { |
| rem = 1 << (len - g.root); |
| mem += rem; |
| } |
| rem--; |
| } |
| |
| // remove entries as we drop back down in the recursion |
| g.code[len] = 0; |
| } |
| |
| // Look at all sub-codes starting with root + 1 bits. Look at only the valid |
| // intermediate code states (syms, left, len). For each completed code, |
| // calculate the amount of memory required by inflate to build the decoding |
| // tables. Find the maximum amount of memory required and show the codes that |
| // require that maximum. |
| local void enough(int syms) { |
| // clear code |
| for (int n = 0; n <= g.max; n++) |
| g.code[n] = 0; |
| |
| // look at all (root + 1) bit and longer codes |
| string_clear(&g.out); // empty saved results |
| g.large = 1 << g.root; // base table |
| if (g.root < g.max) // otherwise, there's only a base table |
| for (int n = 3; n <= syms; n++) |
| for (int left = 2; left < n; left += 2) { |
| // look at all reachable (root + 1) bit nodes, and the |
| // resulting codes (complete at root + 2 or more) |
| size_t index = map(n, left, g.root + 1); |
| if (g.root + 1 < g.max && g.num[index]) // reachable node |
| examine(n, left, g.root + 1, 1 << g.root, 0); |
| |
| // also look at root bit codes with completions at root + 1 |
| // bits (not saved in num, since complete), just in case |
| if (g.num[index - 1] && n <= left << 1) |
| examine((n - left) << 1, (n - left) << 1, g.root + 1, |
| 1 << g.root, 0); |
| } |
| |
| // done |
| printf("maximum of %d table entries for root = %d\n", g.large, g.root); |
| fputs(g.out.str, stdout); |
| } |
| |
| // Examine and show the total number of possible prefix codes for a given |
| // maximum number of symbols, initial root table size, and maximum code length |
| // in bits -- those are the command arguments in that order. The default values |
| // are 286, 9, and 15 respectively, for the deflate literal/length code. The |
| // possible codes are counted for each number of coded symbols from two to the |
| // maximum. The counts for each of those and the total number of codes are |
| // shown. The maximum number of inflate table entries is then calculated across |
| // all possible codes. Each new maximum number of table entries and the |
| // associated sub-code (starting at root + 1 == 10 bits) is shown. |
| // |
| // To count and examine prefix codes that are not length-limited, provide a |
| // maximum length equal to the number of symbols minus one. |
| // |
| // For the deflate literal/length code, use "enough". For the deflate distance |
| // code, use "enough 30 6". |
| int main(int argc, char **argv) { |
| // set up globals for cleanup() |
| g.code = NULL; |
| g.num = NULL; |
| g.done = NULL; |
| string_init(&g.out); |
| |
| // get arguments -- default to the deflate literal/length code |
| int syms = 286; |
| g.root = 9; |
| g.max = 15; |
| if (argc > 1) { |
| syms = atoi(argv[1]); |
| if (argc > 2) { |
| g.root = atoi(argv[2]); |
| if (argc > 3) |
| g.max = atoi(argv[3]); |
| } |
| } |
| if (argc > 4 || syms < 2 || g.root < 1 || g.max < 1) { |
| fputs("invalid arguments, need: [sym >= 2 [root >= 1 [max >= 1]]]\n", |
| stderr); |
| return 1; |
| } |
| |
| // if not restricting the code length, the longest is syms - 1 |
| if (g.max > syms - 1) |
| g.max = syms - 1; |
| |
| // determine the number of bits in a code_t |
| int bits = 0; |
| for (code_t word = 1; word; word <<= 1) |
| bits++; |
| |
| // make sure that the calculation of most will not overflow |
| if (g.max > bits || (code_t)(syms - 2) >= ((code_t)-1 >> (g.max - 1))) { |
| fputs("abort: code length too long for internal types\n", stderr); |
| return 1; |
| } |
| |
| // reject impossible code requests |
| if ((code_t)(syms - 1) > ((code_t)1 << g.max) - 1) { |
| fprintf(stderr, "%d symbols cannot be coded in %d bits\n", |
| syms, g.max); |
| return 1; |
| } |
| |
| // allocate code vector |
| g.code = calloc(g.max + 1, sizeof(int)); |
| assert(g.code != NULL && "out of memory"); |
| |
| // determine size of saved results array, checking for overflows, |
| // allocate and clear the array (set all to zero with calloc()) |
| if (syms == 2) // iff max == 1 |
| g.num = NULL; // won't be saving any results |
| else { |
| g.size = syms >> 1; |
| int n = (syms - 1) >> 1; |
| assert(g.size <= (size_t)-1 / n && "overflow"); |
| g.size *= n; |
| n = g.max - 1; |
| assert(g.size <= (size_t)-1 / n && "overflow"); |
| g.size *= n; |
| g.num = calloc(g.size, sizeof(big_t)); |
| assert(g.num != NULL && "out of memory"); |
| } |
| |
| // count possible codes for all numbers of symbols, add up counts |
| big_t sum = 0; |
| for (int n = 2; n <= syms; n++) { |
| big_t got = count(n, 2, 1); |
| sum += got; |
| assert(got != (big_t)-1 && sum >= got && "overflow"); |
| } |
| printf("%"PRIbig" total codes for 2 to %d symbols", sum, syms); |
| if (g.max < syms - 1) |
| printf(" (%d-bit length limit)\n", g.max); |
| else |
| puts(" (no length limit)"); |
| |
| // allocate and clear done array for been_here() |
| if (syms == 2) |
| g.done = NULL; |
| else { |
| g.done = calloc(g.size, sizeof(struct tab)); |
| assert(g.done != NULL && "out of memory"); |
| } |
| |
| // find and show maximum inflate table usage |
| if (g.root > g.max) // reduce root to max length |
| g.root = g.max; |
| if ((code_t)syms < ((code_t)1 << (g.root + 1))) |
| enough(syms); |
| else |
| fputs("cannot handle minimum code lengths > root", stderr); |
| |
| // done |
| cleanup(); |
| return 0; |
| } |
