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 */
9 * \brief Count the bits in an integer, manipulate powers of 2, etc.
12 #include "lib/intmath/bits.h"
14 /** Returns floor(log2(u64)). If u64 is 0, (incorrectly) returns 0. */
16 tor_log2(uint64_t u64
)
19 if (u64
>= (UINT64_C(1)<<32)) {
23 if (u64
>= (UINT64_C(1)<<16)) {
27 if (u64
>= (UINT64_C(1)<<8)) {
31 if (u64
>= (UINT64_C(1)<<4)) {
35 if (u64
>= (UINT64_C(1)<<2)) {
39 if (u64
>= (UINT64_C(1)<<1)) {
40 // u64 >>= 1; // not using this any more.
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. */
49 round_to_power_of_2(uint64_t u64
)
58 low
= UINT64_C(1) << lg2
;
63 high
= UINT64_C(1) << (lg2
+1);
64 if (high
- u64
< u64
- low
)
70 /** Return the number of bits set in <b>v</b>. */
72 n_bits_set_u8(uint8_t v
)
74 static const int nybble_table
[] = {
93 return nybble_table
[v
& 15] + nybble_table
[v
>>4];