/* enough.c -- determine the maximum size of inflate's Huffman code tables over
* all possible valid and complete Huffman codes, subject to a length limit.
- * Copyright (C) 2007, 2008 Mark Adler
- * Version 1.3 17 February 2008 Mark Adler
+ * Copyright (C) 2007, 2008, 2012 Mark Adler
+ * Version 1.4 18 August 2012 Mark Adler
*/
/* Version history:
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
*/
/*
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 Huffman codes.
+ possible triplets are reached in the generation of valid Huffman codes.
*/
/* The array for tracking visited states, done[], is itself indexed identically
*/
/* Globals to avoid propagating constants or constant pointers recursively */
-local int max; /* maximum allowed bit length for the codes */
-local int root; /* size of base code table in bits */
-local int large; /* largest code table so far */
-local size_t size; /* number of elements in num and done */
-local int *code; /* number of symbols assigned to each bit length */
-local big_t *num; /* saved results array for code counting */
-local struct tab *done; /* states already evaluated array */
+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 */
+ 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[] */
-#define INDEX(i,j,k) (((size_t)((i-1)>>1)*((i-2)>>1)+(j>>1)-1)*(max-1)+k-1)
+#define INDEX(i,j,k) (((size_t)((i-1)>>1)*((i-2)>>1)+(j>>1)-1)*(g.max-1)+k-1)
/* Free allocated space. Uses globals code, num, and done. */
local void cleanup(void)
{
size_t n;
- if (done != NULL) {
- for (n = 0; n < size; n++)
- if (done[n].len)
- free(done[n].vec);
- free(done);
+ if (g.done != NULL) {
+ for (n = 0; n < g.size; n++)
+ if (g.done[n].len)
+ free(g.done[n].vec);
+ free(g.done);
}
- if (num != NULL)
- free(num);
- if (code != NULL)
- free(code);
+ if (g.num != NULL)
+ free(g.num);
+ if (g.code != NULL)
+ free(g.code);
}
/* Return the number of possible Huffman codes using bit patterns of lengths
return 1;
/* note and verify the expected state */
- assert(syms > left && left > 0 && len < max);
+ assert(syms > left && left > 0 && len < g.max);
/* see if we've done this one already */
index = INDEX(syms, left, len);
- got = num[index];
+ got = g.num[index];
if (got)
return got; /* we have -- return the saved result */
/* 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) */
- most = (((code_t)left << (max - len)) - syms) /
- (((code_t)1 << (max - len)) - 1);
+ 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 */
sum = 0;
for (use = least; use <= most; use++) {
got = count(syms - use, len + 1, (left - use) << 1);
sum += got;
- if (got == -1 || sum < got) /* overflow */
- return -1;
+ if (got == (big_t)0 - 1 || sum < got) /* overflow */
+ return (big_t)0 - 1;
}
/* verify that all recursive calls are productive */
assert(sum != 0);
/* save the result and return it */
- num[index] = sum;
+ g.num[index] = sum;
return sum;
}
/* point to vector for (syms,left,len), bit in vector for (mem,rem) */
index = INDEX(syms, left, len);
- mem -= 1 << root;
+ mem -= 1 << g.root;
offset = (mem >> 3) + rem;
offset = ((offset * (offset + 1)) >> 1) + rem;
bit = 1 << (mem & 7);
/* see if we've been here */
- length = done[index].len;
- if (offset < length && (done[index].vec[offset] & bit) != 0)
+ 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 */
do {
length <<= 1;
} while (length <= offset);
- vector = realloc(done[index].vec, length);
+ vector = realloc(g.done[index].vec, length);
if (vector != NULL)
- memset(vector + done[index].len, 0, length - done[index].len);
+ 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 = 1 << (len - root);
+ length = 1 << (len - g.root);
while (length <= offset)
length <<= 1;
vector = calloc(length, sizeof(char));
}
/* install the new vector */
- done[index].len = length;
- done[index].vec = vector;
+ g.done[index].len = length;
+ g.done[index].vec = vector;
}
/* set the bit */
- done[index].vec[offset] |= bit;
+ g.done[index].vec[offset] |= bit;
return 0;
}
/* see if we have a complete code */
if (syms == left) {
/* set the last code entry */
- code[len] = left;
+ g.code[len] = left;
/* complete computation of memory used by this code */
while (rem < left) {
left -= rem;
- rem = 1 << (len - root);
+ rem = 1 << (len - g.root);
mem += rem;
}
assert(rem == left);
/* if this is a new maximum, show the entries used and the sub-code */
- if (mem > large) {
- large = mem;
+ if (mem > g.large) {
+ g.large = mem;
printf("max %d: ", mem);
- for (use = root + 1; use <= max; use++)
- if (code[use])
- printf("%d[%d] ", code[use], use);
+ for (use = g.root + 1; use <= g.max; use++)
+ if (g.code[use])
+ printf("%d[%d] ", g.code[use], use);
putchar('\n');
fflush(stdout);
}
/* remove entries as we drop back down in the recursion */
- code[len] = 0;
+ g.code[len] = 0;
return;
}
/* 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) */
- most = (((code_t)left << (max - len)) - syms) /
- (((code_t)1 << (max - len)) - 1);
+ 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 */
use = least;
while (rem < use) {
use -= rem;
- rem = 1 << (len - root);
+ 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++) {
- code[len] = use;
+ g.code[len] = use;
examine(syms - use, len + 1, (left - use) << 1,
- mem + (rem ? 1 << (len - root) : 0), rem << 1);
+ mem + (rem ? 1 << (len - g.root) : 0), rem << 1);
if (rem == 0) {
- rem = 1 << (len - root);
+ rem = 1 << (len - g.root);
mem += rem;
}
rem--;
}
/* remove entries as we drop back down in the recursion */
- code[len] = 0;
+ g.code[len] = 0;
}
/* Look at all sub-codes starting with root + 1 bits. Look at only the valid
size_t index; /* index of this case in *num */
/* clear code */
- for (n = 0; n <= max; n++)
- code[n] = 0;
+ for (n = 0; n <= g.max; n++)
+ g.code[n] = 0;
/* look at all (root + 1) bit and longer codes */
- large = 1 << root; /* base table */
- if (root < max) /* otherwise, there's only a base table */
+ g.large = 1 << g.root; /* base table */
+ if (g.root < g.max) /* otherwise, there's only a base table */
for (n = 3; n <= syms; n++)
for (left = 2; left < n; left += 2)
{
/* look at all reachable (root + 1) bit nodes, and the
resulting codes (complete at root + 2 or more) */
- index = INDEX(n, left, root + 1);
- if (root + 1 < max && num[index]) /* reachable node */
- examine(n, root + 1, left, 1 << root, 0);
+ index = INDEX(n, left, g.root + 1);
+ if (g.root + 1 < g.max && g.num[index]) /* reachable node */
+ examine(n, g.root + 1, left, 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 (num[index - 1] && n <= left << 1)
- examine((n - left) << 1, root + 1, (n - left) << 1,
- 1 << root, 0);
+ if (g.num[index - 1] && n <= left << 1)
+ examine((n - left) << 1, g.root + 1, (n - left) << 1,
+ 1 << g.root, 0);
}
/* done */
- printf("done: maximum of %d table entries\n", large);
+ printf("done: maximum of %d table entries\n", g.large);
}
/*
int n; /* number of symbols to code for this run */
big_t got; /* return value of count() */
big_t sum; /* accumulated number of codes over n */
+ code_t word; /* for counting bits in code_t */
/* set up globals for cleanup() */
- code = NULL;
- num = NULL;
- done = NULL;
+ g.code = NULL;
+ g.num = NULL;
+ g.done = NULL;
/* get arguments -- default to the deflate literal/length code */
syms = 286;
- root = 9;
- max = 15;
+ g.root = 9;
+ g.max = 15;
if (argc > 1) {
syms = atoi(argv[1]);
if (argc > 2) {
- root = atoi(argv[2]);
- if (argc > 3)
- max = atoi(argv[3]);
- }
+ g.root = atoi(argv[2]);
+ if (argc > 3)
+ g.max = atoi(argv[3]);
+ }
}
- if (argc > 4 || syms < 2 || root < 1 || max < 1) {
+ if (argc > 4 || syms < 2 || g.root < 1 || g.max < 1) {
fputs("invalid arguments, need: [sym >= 2 [root >= 1 [max >= 1]]]\n",
- stderr);
+ stderr);
return 1;
}
/* if not restricting the code length, the longest is syms - 1 */
- if (max > syms - 1)
- max = syms - 1;
+ if (g.max > syms - 1)
+ g.max = syms - 1;
/* determine the number of bits in a code_t */
- n = 0;
- while (((code_t)1 << n) != 0)
- n++;
+ for (n = 0, word = 1; word; n++, word <<= 1)
+ ;
/* make sure that the calculation of most will not overflow */
- if (max > n || syms - 2 >= (((code_t)0 - 1) >> (max - 1))) {
+ if (g.max > n || (code_t)(syms - 2) >= (((code_t)0 - 1) >> (g.max - 1))) {
fputs("abort: code length too long for internal types\n", stderr);
return 1;
}
/* reject impossible code requests */
- if (syms - 1 > ((code_t)1 << max) - 1) {
+ if ((code_t)(syms - 1) > ((code_t)1 << g.max) - 1) {
fprintf(stderr, "%d symbols cannot be coded in %d bits\n",
- syms, max);
+ syms, g.max);
return 1;
}
/* allocate code vector */
- code = calloc(max + 1, sizeof(int));
- if (code == NULL) {
+ g.code = calloc(g.max + 1, sizeof(int));
+ if (g.code == NULL) {
fputs("abort: unable to allocate enough memory\n", stderr);
return 1;
}
/* 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 */
- num = NULL; /* won't be saving any results */
+ g.num = NULL; /* won't be saving any results */
else {
- size = syms >> 1;
- if (size > ((size_t)0 - 1) / (n = (syms - 1) >> 1) ||
- (size *= n, size > ((size_t)0 - 1) / (n = max - 1)) ||
- (size *= n, size > ((size_t)0 - 1) / sizeof(big_t)) ||
- (num = calloc(size, sizeof(big_t))) == NULL) {
+ g.size = syms >> 1;
+ if (g.size > ((size_t)0 - 1) / (n = (syms - 1) >> 1) ||
+ (g.size *= n, g.size > ((size_t)0 - 1) / (n = g.max - 1)) ||
+ (g.size *= n, g.size > ((size_t)0 - 1) / sizeof(big_t)) ||
+ (g.num = calloc(g.size, sizeof(big_t))) == NULL) {
fputs("abort: unable to allocate enough memory\n", stderr);
cleanup();
return 1;
for (n = 2; n <= syms; n++) {
got = count(n, 1, 2);
sum += got;
- if (got == -1 || sum < got) { /* overflow */
+ if (got == (big_t)0 - 1 || sum < got) { /* overflow */
fputs("abort: can't count that high!\n", stderr);
cleanup();
return 1;
printf("%llu %d-codes\n", got, n);
}
printf("%llu total codes for 2 to %d symbols", sum, syms);
- if (max < syms - 1)
- printf(" (%d-bit length limit)\n", max);
+ if (g.max < syms - 1)
+ printf(" (%d-bit length limit)\n", g.max);
else
puts(" (no length limit)");
/* allocate and clear done array for beenhere() */
if (syms == 2)
- done = NULL;
- else if (size > ((size_t)0 - 1) / sizeof(struct tab) ||
- (done = calloc(size, sizeof(struct tab))) == NULL) {
+ g.done = NULL;
+ else if (g.size > ((size_t)0 - 1) / sizeof(struct tab) ||
+ (g.done = calloc(g.size, sizeof(struct tab))) == NULL) {
fputs("abort: unable to allocate enough memory\n", stderr);
cleanup();
return 1;
}
/* find and show maximum inflate table usage */
- if (root > max) /* reduce root to max length */
- root = max;
- if (syms < ((code_t)1 << (root + 1)))
+ 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
puts("cannot handle minimum code lengths > root");
projects / zlib.git / blobdiff