diff options
| author | Nick Mathewson <nickm@torproject.org> | 2012-09-14 09:54:08 -0400 |
|---|---|---|
| committer | Nick Mathewson <nickm@torproject.org> | 2012-09-14 09:54:08 -0400 |
| commit | 6492a75b9f23ff4d22aa4b4ffa2fe4a4f7193bad (patch) | |
| tree | 116dbb183798fceb748fc5ef0b6be33dc8ef662d /src | |
| parent | 9ab3b332aec076451dd93d11ce7ce1fd81ff7294 (diff) | |
| parent | 37953497d8689bdde65837b00f56bf8ff1e0e459 (diff) | |
| download | tor-6492a75b9f23ff4d22aa4b4ffa2fe4a4f7193bad.tar.gz tor-6492a75b9f23ff4d22aa4b4ffa2fe4a4f7193bad.zip | |
Merge branch 'bug6831_v2'
Diffstat (limited to 'src')
| -rw-r--r-- | src/common/util.c | 18 | ||||
| -rw-r--r-- | src/test/test_util.c | 13 |
2 files changed, 27 insertions, 4 deletions
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: ; |