bits.c (1798B)
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 { 18 int r = 0; 19 if (u64 >= (UINT64_C(1)<<32)) { 20 u64 >>= 32; 21 r = 32; 22 } 23 if (u64 >= (UINT64_C(1)<<16)) { 24 u64 >>= 16; 25 r += 16; 26 } 27 if (u64 >= (UINT64_C(1)<<8)) { 28 u64 >>= 8; 29 r += 8; 30 } 31 if (u64 >= (UINT64_C(1)<<4)) { 32 u64 >>= 4; 33 r += 4; 34 } 35 if (u64 >= (UINT64_C(1)<<2)) { 36 u64 >>= 2; 37 r += 2; 38 } 39 if (u64 >= (UINT64_C(1)<<1)) { 40 // u64 >>= 1; // not using this any more. 41 r += 1; 42 } 43 return r; 44 } 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 { 51 int lg2; 52 uint64_t low; 53 uint64_t high; 54 if (u64 == 0) 55 return 1; 56 57 lg2 = tor_log2(u64); 58 low = UINT64_C(1) << lg2; 59 60 if (lg2 == 63) 61 return low; 62 63 high = UINT64_C(1) << (lg2+1); 64 if (high - u64 < u64 - low) 65 return high; 66 else 67 return low; 68 } 69 70 /** Return the number of bits set in <b>v</b>. */ 71 int 72 n_bits_set_u8(uint8_t v) 73 { 74 static const int nybble_table[] = { 75 0, /* 0000 */ 76 1, /* 0001 */ 77 1, /* 0010 */ 78 2, /* 0011 */ 79 1, /* 0100 */ 80 2, /* 0101 */ 81 2, /* 0110 */ 82 3, /* 0111 */ 83 1, /* 1000 */ 84 2, /* 1001 */ 85 2, /* 1010 */ 86 3, /* 1011 */ 87 2, /* 1100 */ 88 3, /* 1101 */ 89 3, /* 1110 */ 90 4, /* 1111 */ 91 }; 92 93 return nybble_table[v & 15] + nybble_table[v>>4]; 94 }