diff options
| author | Mark Adler <madler@alumni.caltech.edu> | 2012-08-18 17:59:50 -0700 |
|---|---|---|
| committer | Mark Adler <madler@alumni.caltech.edu> | 2012-08-18 18:07:26 -0700 |
| commit | 17068938ce5544ec3728402abd39bf3c55aec113 (patch) | |
| tree | e366e8de99ddad7b53231d27bb797bd608ccbfce /examples/enough.c | |
| parent | 3d9df6ecf83a41a3990fbff5c276f854d158e8ad (diff) | |
| download | zlib-17068938ce5544ec3728402abd39bf3c55aec113.tar.gz zlib-17068938ce5544ec3728402abd39bf3c55aec113.tar.bz2 zlib-17068938ce5544ec3728402abd39bf3c55aec113.zip | |
Avoid shift equal to bits in type (caused endless loop).
Also clean up comparisons between different types, and some odd
indentation problems that showed up somehow.
A new endless loop was introduced by the clang compiler, which
apparently does odd things when the right operand of << is equal to
or greater than the number of bits in the type. The C standard in
fact states that the behavior of << is undefined in that case. The
loop was rewritten to use single-bit shifts.
Diffstat (limited to '')
| -rw-r--r-- | examples/enough.c | 39 |
1 files changed, 21 insertions, 18 deletions
diff --git a/examples/enough.c b/examples/enough.c index c40410b..b991144 100644 --- a/examples/enough.c +++ b/examples/enough.c | |||
| @@ -1,7 +1,7 @@ | |||
| 1 | /* enough.c -- determine the maximum size of inflate's Huffman code tables over | 1 | /* enough.c -- determine the maximum size of inflate's Huffman code tables over |
| 2 | * all possible valid and complete Huffman codes, subject to a length limit. | 2 | * all possible valid and complete Huffman codes, subject to a length limit. |
| 3 | * Copyright (C) 2007, 2008 Mark Adler | 3 | * Copyright (C) 2007, 2008, 2012 Mark Adler |
| 4 | * Version 1.3 17 February 2008 Mark Adler | 4 | * Version 1.4 18 August 2012 Mark Adler |
| 5 | */ | 5 | */ |
| 6 | 6 | ||
| 7 | /* Version history: | 7 | /* Version history: |
| @@ -14,6 +14,9 @@ | |||
| 14 | 1.3 17 Feb 2008 Add argument for initial root table size | 14 | 1.3 17 Feb 2008 Add argument for initial root table size |
| 15 | Fix bug for initial root table size == max - 1 | 15 | Fix bug for initial root table size == max - 1 |
| 16 | Use a macro to compute the history index | 16 | Use a macro to compute the history index |
| 17 | 1.4 18 Aug 2012 Avoid shifts more than bits in type (caused endless loop!) | ||
| 18 | Clean up comparisons of different types | ||
| 19 | Clean up code indentation | ||
| 17 | */ | 20 | */ |
| 18 | 21 | ||
| 19 | /* | 22 | /* |
| @@ -236,8 +239,8 @@ local big_t count(int syms, int len, int left) | |||
| 236 | for (use = least; use <= most; use++) { | 239 | for (use = least; use <= most; use++) { |
| 237 | got = count(syms - use, len + 1, (left - use) << 1); | 240 | got = count(syms - use, len + 1, (left - use) << 1); |
| 238 | sum += got; | 241 | sum += got; |
| 239 | if (got == -1 || sum < got) /* overflow */ | 242 | if (got == (big_t)0 - 1 || sum < got) /* overflow */ |
| 240 | return -1; | 243 | return (big_t)0 - 1; |
| 241 | } | 244 | } |
| 242 | 245 | ||
| 243 | /* verify that all recursive calls are productive */ | 246 | /* verify that all recursive calls are productive */ |
| @@ -458,6 +461,7 @@ int main(int argc, char **argv) | |||
| 458 | int n; /* number of symbols to code for this run */ | 461 | int n; /* number of symbols to code for this run */ |
| 459 | big_t got; /* return value of count() */ | 462 | big_t got; /* return value of count() */ |
| 460 | big_t sum; /* accumulated number of codes over n */ | 463 | big_t sum; /* accumulated number of codes over n */ |
| 464 | code_t word; /* for counting bits in code_t */ | ||
| 461 | 465 | ||
| 462 | /* set up globals for cleanup() */ | 466 | /* set up globals for cleanup() */ |
| 463 | code = NULL; | 467 | code = NULL; |
| @@ -466,19 +470,19 @@ int main(int argc, char **argv) | |||
| 466 | 470 | ||
| 467 | /* get arguments -- default to the deflate literal/length code */ | 471 | /* get arguments -- default to the deflate literal/length code */ |
| 468 | syms = 286; | 472 | syms = 286; |
| 469 | root = 9; | 473 | root = 9; |
| 470 | max = 15; | 474 | max = 15; |
| 471 | if (argc > 1) { | 475 | if (argc > 1) { |
| 472 | syms = atoi(argv[1]); | 476 | syms = atoi(argv[1]); |
| 473 | if (argc > 2) { | 477 | if (argc > 2) { |
| 474 | root = atoi(argv[2]); | 478 | root = atoi(argv[2]); |
| 475 | if (argc > 3) | 479 | if (argc > 3) |
| 476 | max = atoi(argv[3]); | 480 | max = atoi(argv[3]); |
| 477 | } | 481 | } |
| 478 | } | 482 | } |
| 479 | if (argc > 4 || syms < 2 || root < 1 || max < 1) { | 483 | if (argc > 4 || syms < 2 || root < 1 || max < 1) { |
| 480 | fputs("invalid arguments, need: [sym >= 2 [root >= 1 [max >= 1]]]\n", | 484 | fputs("invalid arguments, need: [sym >= 2 [root >= 1 [max >= 1]]]\n", |
| 481 | stderr); | 485 | stderr); |
| 482 | return 1; | 486 | return 1; |
| 483 | } | 487 | } |
| 484 | 488 | ||
| @@ -487,18 +491,17 @@ int main(int argc, char **argv) | |||
| 487 | max = syms - 1; | 491 | max = syms - 1; |
| 488 | 492 | ||
| 489 | /* determine the number of bits in a code_t */ | 493 | /* determine the number of bits in a code_t */ |
| 490 | n = 0; | 494 | for (n = 0, word = 1; word; n++, word <<= 1) |
| 491 | while (((code_t)1 << n) != 0) | 495 | ; |
| 492 | n++; | ||
| 493 | 496 | ||
| 494 | /* make sure that the calculation of most will not overflow */ | 497 | /* make sure that the calculation of most will not overflow */ |
| 495 | if (max > n || syms - 2 >= (((code_t)0 - 1) >> (max - 1))) { | 498 | if (max > n || (code_t)(syms - 2) >= (((code_t)0 - 1) >> (max - 1))) { |
| 496 | fputs("abort: code length too long for internal types\n", stderr); | 499 | fputs("abort: code length too long for internal types\n", stderr); |
| 497 | return 1; | 500 | return 1; |
| 498 | } | 501 | } |
| 499 | 502 | ||
| 500 | /* reject impossible code requests */ | 503 | /* reject impossible code requests */ |
| 501 | if (syms - 1 > ((code_t)1 << max) - 1) { | 504 | if ((code_t)(syms - 1) > ((code_t)1 << max) - 1) { |
| 502 | fprintf(stderr, "%d symbols cannot be coded in %d bits\n", | 505 | fprintf(stderr, "%d symbols cannot be coded in %d bits\n", |
| 503 | syms, max); | 506 | syms, max); |
| 504 | return 1; | 507 | return 1; |
| @@ -532,7 +535,7 @@ int main(int argc, char **argv) | |||
| 532 | for (n = 2; n <= syms; n++) { | 535 | for (n = 2; n <= syms; n++) { |
| 533 | got = count(n, 1, 2); | 536 | got = count(n, 1, 2); |
| 534 | sum += got; | 537 | sum += got; |
| 535 | if (got == -1 || sum < got) { /* overflow */ | 538 | if (got == (big_t)0 - 1 || sum < got) { /* overflow */ |
| 536 | fputs("abort: can't count that high!\n", stderr); | 539 | fputs("abort: can't count that high!\n", stderr); |
| 537 | cleanup(); | 540 | cleanup(); |
| 538 | return 1; | 541 | return 1; |
| @@ -556,9 +559,9 @@ int main(int argc, char **argv) | |||
| 556 | } | 559 | } |
| 557 | 560 | ||
| 558 | /* find and show maximum inflate table usage */ | 561 | /* find and show maximum inflate table usage */ |
| 559 | if (root > max) /* reduce root to max length */ | 562 | if (root > max) /* reduce root to max length */ |
| 560 | root = max; | 563 | root = max; |
| 561 | if (syms < ((code_t)1 << (root + 1))) | 564 | if ((code_t)syms < ((code_t)1 << (root + 1))) |
| 562 | enough(syms); | 565 | enough(syms); |
| 563 | else | 566 | else |
| 564 | puts("cannot handle minimum code lengths > root"); | 567 | puts("cannot handle minimum code lengths > root"); |