179 #define INDEX(i,j,k) (((size_t)((i-1)>>1)*((i-2)>>1)+(j>>1)-1)*(max-1)+k-1) 187 for (n = 0; n <
size; n++)
217 assert(syms > left && left > 0 && len <
max);
220 index =
INDEX(syms, left, len);
227 least = (left << 1) - syms;
234 most = (((
code_t)left << (
max - len)) - syms) /
239 for (use = least; use <= most; use++) {
240 got =
count(syms - use, len + 1, (left - use) << 1);
242 if (got == (
big_t)0 - 1 || sum < got)
267 index =
INDEX(syms, left, len);
269 offset = (mem >> 3) + rem;
270 offset = ((offset * (offset + 1)) >> 1) + rem;
271 bit = 1 << (mem & 7);
274 length = done[
index].len;
275 if (offset < length && (done[index].
vec[offset] & bit) != 0)
281 if (length <= offset) {
286 }
while (length <= offset);
287 vector = realloc(done[index].
vec, length);
289 memset(vector + done[index].len, 0, length - done[index].len);
294 length = 1 << (len -
root);
295 while (length <= offset)
297 vector = calloc(length,
sizeof(
char));
301 if (vector ==
NULL) {
302 fputs(
"abort: unable to allocate enough memory\n", stderr);
309 done[
index].vec = vector;
336 rem = 1 << (len -
root);
344 printf(
"max %d: ", mem);
345 for (use =
root + 1; use <=
max; use++)
347 printf(
"%d[%d] ",
code[use], use);
358 if (
beenhere(syms, len, left, mem, rem))
363 least = (left << 1) - syms;
370 most = (((
code_t)left << (
max - len)) - syms) /
377 rem = 1 << (len -
root);
383 for (use = least; use <= most; use++) {
385 examine(syms - use, len + 1, (left - use) << 1,
386 mem + (rem ? 1 << (len -
root) : 0), rem << 1);
388 rem = 1 << (len -
root);
410 for (n = 0; n <=
max; n++)
416 for (n = 3; n <= syms; n++)
417 for (left = 2; left <
n; left += 2)
427 if (
num[index - 1] && n <= left << 1)
428 examine((n - left) << 1,
root + 1, (n - left) << 1,
433 printf(
"done: maximum of %d table entries\n",
large);
458 int main(
int argc,
char **argv)
476 syms = atoi(argv[1]);
478 root = atoi(argv[2]);
483 if (argc > 4 || syms < 2 ||
root < 1 ||
max < 1) {
484 fputs(
"invalid arguments, need: [sym >= 2 [root >= 1 [max >= 1]]]\n",
494 for (n = 0, word = 1; word; n++, word <<= 1)
499 fputs(
"abort: code length too long for internal types\n", stderr);
505 fprintf(stderr,
"%d symbols cannot be coded in %d bits\n",
511 code = calloc(
max + 1,
sizeof(
int));
513 fputs(
"abort: unable to allocate enough memory\n", stderr);
523 if (
size > ((
size_t)0 - 1) / (n = (syms - 1) >> 1) ||
524 (
size *= n,
size > ((
size_t)0 - 1) / (n =
max - 1)) ||
527 fputs(
"abort: unable to allocate enough memory\n", stderr);
535 for (n = 2; n <= syms; n++) {
536 got =
count(n, 1, 2);
538 if (got == (
big_t)0 - 1 || sum < got) {
539 fputs(
"abort: can't count that high!\n", stderr);
543 printf(
"%llu %d-codes\n", got, n);
545 printf(
"%llu total codes for 2 to %d symbols", sum, syms);
547 printf(
" (%d-bit length limit)\n",
max);
549 puts(
" (no length limit)");
554 else if (
size > ((
size_t)0 - 1) /
sizeof(
struct tab) ||
555 (done = calloc(
size,
sizeof(
struct tab))) ==
NULL) {
556 fputs(
"abort: unable to allocate enough memory\n", stderr);
567 puts(
"cannot handle minimum code lengths > root");
GLenum GLuint GLenum GLsizei length
local void examine(int syms, int len, int left, int mem, int rem)
local void enough(int syms)
unsigned long long code_t
local big_t count(int syms, int len, int left)
local int beenhere(int syms, int len, int left, int mem, int rem)
int main(int argc, char **argv)