Tor  0.4.6.0-alpha-dev
bits.c
Go to the documentation of this file.
1 /* Copyright (c) 2003-2004, Roger Dingledine
2  * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
3  * Copyright (c) 2007-2020, 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 }
n_bits_set_u8
int n_bits_set_u8(uint8_t v)
Definition: bits.c:72
bits.h