diff options
| -rw-r--r-- | changes/bug6831 | 4 | ||||
| -rw-r--r-- | src/common/util.c | 18 | ||||
| -rw-r--r-- | 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 0000000000..ac4775ba83 --- /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 84b31502e6..0e0dcb179c 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 7ef4d1f78c..2a194ef840 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: ; |