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