commit 37953497d8689bdde65837b00f56bf8ff1e0e459 Author: Nick Mathewson <nickm@torproject.org> Date: Thu Sep 13 10:34:49 2012 -0400 Don't compute ((uint64_t)1)<<64 in round_to_power_of_2 This would be undefined behavior if it happened. (It can't actually happen as we're using round_to_power_of_2, since we would have to be trying to allocate exabytes of data.) While we're at it, fix the behavior of round_to_power_of_2(0), and document the function better. Fix for bug 6831. --- changes/bug6831 | 4 ++++ src/common/util.c | 18 +++++++++++++++--- src/test/test_util.c | 13 ++++++++++++- 3 files changed, 31 insertions(+), 4 deletions(-) diff --git a/changes/bug6831 b/changes/bug6831 new file mode 100644 index 0000000..ac4775b --- /dev/null +++ b/changes/bug6831 @@ -0,0 +1,4 @@ + o Minor bugfixes: + - Fix round_to_power_of_2 so it doesn't invoke undefined behavior + with large values. This was untriggered, but nevertheless incorrect. + Fixes bug 6831; bugfix on 0.2.0.1-alpha. diff --git a/src/common/util.c b/src/common/util.c index 84b3150..0e0dcb1 100644 --- a/src/common/util.c +++ b/src/common/util.c @@ -394,12 +394,24 @@ tor_log2(uint64_t u64) return r; } -/** Return the power of 2 closest to <b>u64</b>. */ +/** Return the power of 2 in range [1,UINT64_MAX] closest to <b>u64</b>. If + * there are two powers of 2 equally close, round down. */ uint64_t round_to_power_of_2(uint64_t u64) { - int lg2 = tor_log2(u64); - uint64_t low = U64_LITERAL(1) << lg2, high = U64_LITERAL(1) << (lg2+1); + int lg2; + uint64_t low; + uint64_t high; + if (u64 == 0) + return 1; + + lg2 = tor_log2(u64); + low = U64_LITERAL(1) << lg2; + + if (lg2 == 63) + return low; + + high = U64_LITERAL(1) << (lg2+1); if (high - u64 < u64 - low) return high; else diff --git a/src/test/test_util.c b/src/test/test_util.c index 7ef4d1f..2a194ef 100644 --- a/src/test/test_util.c +++ b/src/test/test_util.c @@ -1109,6 +1109,7 @@ test_util_pow2(void) test_eq(tor_log2(64), 6); test_eq(tor_log2(65), 6); test_eq(tor_log2(63), 5); + test_eq(tor_log2(0), 0); /* incorrect mathematically, but as specified */ test_eq(tor_log2(1), 0); test_eq(tor_log2(2), 1); test_eq(tor_log2(3), 1); @@ -1123,7 +1124,17 @@ test_util_pow2(void) test_eq(round_to_power_of_2(130), 128); test_eq(round_to_power_of_2(U64_LITERAL(40000000000000000)), U64_LITERAL(1)<<55); - test_eq(round_to_power_of_2(0), 2); + test_eq(round_to_power_of_2(U64_LITERAL(0xffffffffffffffff)), + U64_LITERAL(1)<<63); + test_eq(round_to_power_of_2(0), 1); + test_eq(round_to_power_of_2(1), 1); + test_eq(round_to_power_of_2(2), 2); + test_eq(round_to_power_of_2(3), 2); + test_eq(round_to_power_of_2(4), 4); + test_eq(round_to_power_of_2(4), 4); + test_eq(round_to_power_of_2(5), 4); + test_eq(round_to_power_of_2(6), 4); + test_eq(round_to_power_of_2(7), 8); done: ;