123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569 |
- #include <stdio.h>
- #include <stdlib.h>
- #include <string.h>
- #include <assert.h>
- #define local static
- typedef unsigned long long big_t;
- typedef unsigned long long code_t;
- struct tab {
- size_t len;
- char *vec;
- };
- local int max;
- local int root;
- local int large;
- local size_t size;
- local int *code;
- local big_t *num;
- local struct tab *done;
- #define INDEX(i,j,k) (((size_t)((i-1)>>1)*((i-2)>>1)+(j>>1)-1)*(max-1)+k-1)
- 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 (num != NULL)
- free(num);
- if (code != NULL)
- free(code);
- }
- local big_t count(int syms, int len, int left)
- {
- big_t sum;
- big_t got;
- int least;
- int most;
- int use;
- size_t index;
-
- if (syms == left)
- return 1;
-
- assert(syms > left && left > 0 && len < max);
-
- index = INDEX(syms, left, len);
- got = num[index];
- if (got)
- return got;
-
- least = (left << 1) - syms;
- if (least < 0)
- least = 0;
-
- most = (((code_t)left << (max - len)) - syms) /
- (((code_t)1 << (max - len)) - 1);
-
- sum = 0;
- for (use = least; use <= most; use++) {
- got = count(syms - use, len + 1, (left - use) << 1);
- sum += got;
- if (got == -1 || sum < got)
- return -1;
- }
-
- assert(sum != 0);
-
- num[index] = sum;
- return sum;
- }
- local int beenhere(int syms, int len, int left, int mem, int rem)
- {
- size_t index;
- size_t offset;
- int bit;
- size_t length;
- char *vector;
-
- index = INDEX(syms, left, len);
- mem -= 1 << root;
- offset = (mem >> 3) + rem;
- offset = ((offset * (offset + 1)) >> 1) + rem;
- bit = 1 << (mem & 7);
-
- length = done[index].len;
- if (offset < length && (done[index].vec[offset] & bit) != 0)
- return 1;
-
-
- if (length <= offset) {
-
- if (length) {
- do {
- length <<= 1;
- } while (length <= offset);
- vector = realloc(done[index].vec, length);
- if (vector != NULL)
- memset(vector + done[index].len, 0, length - done[index].len);
- }
-
- else {
- length = 1 << (len - root);
- while (length <= offset)
- length <<= 1;
- vector = calloc(length, sizeof(char));
- }
-
- if (vector == NULL) {
- fputs("abort: unable to allocate enough memory\n", stderr);
- cleanup();
- exit(1);
- }
-
- done[index].len = length;
- done[index].vec = vector;
- }
-
- done[index].vec[offset] |= bit;
- return 0;
- }
- local void examine(int syms, int len, int left, int mem, int rem)
- {
- int least;
- int most;
- int use;
-
- if (syms == left) {
-
- code[len] = left;
-
- while (rem < left) {
- left -= rem;
- rem = 1 << (len - root);
- mem += rem;
- }
- assert(rem == left);
-
- if (mem > large) {
- large = mem;
- printf("max %d: ", mem);
- for (use = root + 1; use <= max; use++)
- if (code[use])
- printf("%d[%d] ", code[use], use);
- putchar('\n');
- fflush(stdout);
- }
-
- code[len] = 0;
- return;
- }
-
- if (beenhere(syms, len, left, mem, rem))
- return;
-
- least = (left << 1) - syms;
- if (least < 0)
- least = 0;
-
- most = (((code_t)left << (max - len)) - syms) /
- (((code_t)1 << (max - len)) - 1);
-
- use = least;
- while (rem < use) {
- use -= rem;
- rem = 1 << (len - root);
- mem += rem;
- }
- rem -= use;
-
- for (use = least; use <= most; use++) {
- code[len] = use;
- examine(syms - use, len + 1, (left - use) << 1,
- mem + (rem ? 1 << (len - root) : 0), rem << 1);
- if (rem == 0) {
- rem = 1 << (len - root);
- mem += rem;
- }
- rem--;
- }
-
- code[len] = 0;
- }
- local void enough(int syms)
- {
- int n;
- int left;
- size_t index;
-
- for (n = 0; n <= max; n++)
- code[n] = 0;
-
- large = 1 << root;
- if (root < max)
- for (n = 3; n <= syms; n++)
- for (left = 2; left < n; left += 2)
- {
-
- index = INDEX(n, left, root + 1);
- if (root + 1 < max && num[index])
- examine(n, root + 1, left, 1 << root, 0);
-
- if (num[index - 1] && n <= left << 1)
- examine((n - left) << 1, root + 1, (n - left) << 1,
- 1 << root, 0);
- }
-
- printf("done: maximum of %d table entries\n", large);
- }
- int main(int argc, char **argv)
- {
- int syms;
- int n;
- big_t got;
- big_t sum;
-
- code = NULL;
- num = NULL;
- done = NULL;
-
- syms = 286;
- root = 9;
- max = 15;
- if (argc > 1) {
- syms = atoi(argv[1]);
- if (argc > 2) {
- root = atoi(argv[2]);
- if (argc > 3)
- max = atoi(argv[3]);
- }
- }
- if (argc > 4 || syms < 2 || root < 1 || max < 1) {
- fputs("invalid arguments, need: [sym >= 2 [root >= 1 [max >= 1]]]\n",
- stderr);
- return 1;
- }
-
- if (max > syms - 1)
- max = syms - 1;
-
- n = 0;
- while (((code_t)1 << n) != 0)
- n++;
-
- if (max > n || syms - 2 >= (((code_t)0 - 1) >> (max - 1))) {
- fputs("abort: code length too long for internal types\n", stderr);
- return 1;
- }
-
- if (syms - 1 > ((code_t)1 << max) - 1) {
- fprintf(stderr, "%d symbols cannot be coded in %d bits\n",
- syms, max);
- return 1;
- }
-
- code = calloc(max + 1, sizeof(int));
- if (code == NULL) {
- fputs("abort: unable to allocate enough memory\n", stderr);
- return 1;
- }
-
- if (syms == 2)
- num = NULL;
- 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) {
- fputs("abort: unable to allocate enough memory\n", stderr);
- cleanup();
- return 1;
- }
- }
-
- sum = 0;
- for (n = 2; n <= syms; n++) {
- got = count(n, 1, 2);
- sum += got;
- if (got == -1 || sum < got) {
- 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);
- else
- puts(" (no length limit)");
-
- if (syms == 2)
- done = NULL;
- else if (size > ((size_t)0 - 1) / sizeof(struct tab) ||
- (done = calloc(size, sizeof(struct tab))) == NULL) {
- fputs("abort: unable to allocate enough memory\n", stderr);
- cleanup();
- return 1;
- }
-
- if (root > max)
- root = max;
- if (syms < ((code_t)1 << (root + 1)))
- enough(syms);
- else
- puts("cannot handle minimum code lengths > root");
-
- cleanup();
- return 0;
- }
|