/src/tor/src/lib/intmath/bits.c
Line | Count | Source |
1 | | /* Copyright (c) 2003-2004, Roger Dingledine |
2 | | * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson. |
3 | | * Copyright (c) 2007-2021, The Tor Project, Inc. */ |
4 | | /* See LICENSE for licensing information */ |
5 | | |
6 | | /** |
7 | | * \file bits.c |
8 | | * |
9 | | * \brief Count the bits in an integer, manipulate powers of 2, etc. |
10 | | **/ |
11 | | |
12 | | #include "lib/intmath/bits.h" |
13 | | |
14 | | /** Returns floor(log2(u64)). If u64 is 0, (incorrectly) returns 0. */ |
15 | | int |
16 | | tor_log2(uint64_t u64) |
17 | 0 | { |
18 | 0 | int r = 0; |
19 | 0 | if (u64 >= (UINT64_C(1)<<32)) { |
20 | 0 | u64 >>= 32; |
21 | 0 | r = 32; |
22 | 0 | } |
23 | 0 | if (u64 >= (UINT64_C(1)<<16)) { |
24 | 0 | u64 >>= 16; |
25 | 0 | r += 16; |
26 | 0 | } |
27 | 0 | if (u64 >= (UINT64_C(1)<<8)) { |
28 | 0 | u64 >>= 8; |
29 | 0 | r += 8; |
30 | 0 | } |
31 | 0 | if (u64 >= (UINT64_C(1)<<4)) { |
32 | 0 | u64 >>= 4; |
33 | 0 | r += 4; |
34 | 0 | } |
35 | 0 | if (u64 >= (UINT64_C(1)<<2)) { |
36 | 0 | u64 >>= 2; |
37 | 0 | r += 2; |
38 | 0 | } |
39 | 0 | if (u64 >= (UINT64_C(1)<<1)) { |
40 | | // u64 >>= 1; // not using this any more. |
41 | 0 | r += 1; |
42 | 0 | } |
43 | 0 | return r; |
44 | 0 | } |
45 | | |
46 | | /** Return the power of 2 in range [1,UINT64_MAX] closest to <b>u64</b>. If |
47 | | * there are two powers of 2 equally close, round down. */ |
48 | | uint64_t |
49 | | round_to_power_of_2(uint64_t u64) |
50 | 0 | { |
51 | 0 | int lg2; |
52 | 0 | uint64_t low; |
53 | 0 | uint64_t high; |
54 | 0 | if (u64 == 0) |
55 | 0 | return 1; |
56 | | |
57 | 0 | lg2 = tor_log2(u64); |
58 | 0 | low = UINT64_C(1) << lg2; |
59 | |
|
60 | 0 | if (lg2 == 63) |
61 | 0 | return low; |
62 | | |
63 | 0 | high = UINT64_C(1) << (lg2+1); |
64 | 0 | if (high - u64 < u64 - low) |
65 | 0 | return high; |
66 | 0 | else |
67 | 0 | return low; |
68 | 0 | } |
69 | | |
70 | | /** Return the number of bits set in <b>v</b>. */ |
71 | | int |
72 | | n_bits_set_u8(uint8_t v) |
73 | 0 | { |
74 | 0 | static const int nybble_table[] = { |
75 | 0 | 0, /* 0000 */ |
76 | 0 | 1, /* 0001 */ |
77 | 0 | 1, /* 0010 */ |
78 | 0 | 2, /* 0011 */ |
79 | 0 | 1, /* 0100 */ |
80 | 0 | 2, /* 0101 */ |
81 | 0 | 2, /* 0110 */ |
82 | 0 | 3, /* 0111 */ |
83 | 0 | 1, /* 1000 */ |
84 | 0 | 2, /* 1001 */ |
85 | 0 | 2, /* 1010 */ |
86 | 0 | 3, /* 1011 */ |
87 | 0 | 2, /* 1100 */ |
88 | 0 | 3, /* 1101 */ |
89 | 0 | 3, /* 1110 */ |
90 | 0 | 4, /* 1111 */ |
91 | 0 | }; |
92 | |
|
93 | 0 | return nybble_table[v & 15] + nybble_table[v>>4]; |
94 | 0 | } |