Tor 0.4.9.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-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. */
15int
16tor_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. */
48uint64_t
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>. */
71int
72n_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}
int n_bits_set_u8(uint8_t v)
Definition: bits.c:72
int tor_log2(uint64_t u64)
Definition: bits.c:16
uint64_t round_to_power_of_2(uint64_t u64)
Definition: bits.c:49