Tor
0.4.9.3-alpha-dev
Toggle main menu visibility
Main Page
Related Pages
Topics
Data Structures
Data Structures
Data Structure Index
Data Fields
All
_
a
b
c
d
e
f
g
h
i
j
k
l
m
n
o
p
q
r
s
t
u
v
w
x
y
Functions
Variables
_
a
b
c
d
e
f
g
h
i
j
k
l
m
n
o
p
q
r
s
t
u
v
w
x
y
Enumerator
Files
File List
Globals
All
_
a
b
c
d
e
f
g
h
i
j
k
l
m
n
o
p
q
r
s
t
u
v
w
x
z
Functions
a
b
c
d
e
f
g
h
i
k
l
m
n
o
p
q
r
s
t
u
v
w
x
Variables
a
b
c
d
e
f
g
h
i
k
l
m
n
o
p
q
r
s
t
u
v
w
x
z
Typedefs
b
c
d
f
g
h
l
m
n
o
p
r
s
v
Enumerations
a
b
c
d
f
g
h
i
k
l
m
n
o
p
q
r
s
t
u
v
w
Enumerator
a
b
c
d
e
g
h
i
m
n
o
p
q
r
s
t
v
w
Macros
_
a
b
c
d
e
f
g
h
i
j
l
m
n
o
p
r
s
t
u
v
w
x
•
All
Data Structures
Files
Functions
Variables
Typedefs
Enumerations
Enumerator
Macros
Modules
Pages
Loading...
Searching...
No Matches
lib
intmath
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. */
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
}
16
tor_log2
(uint64_t u64) {
…
}
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
}
49
round_to_power_of_2
(uint64_t u64) {
…
}
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
}
72
n_bits_set_u8
(uint8_t v) {
…
}
n_bits_set_u8
int n_bits_set_u8(uint8_t v)
Definition
bits.c:72
tor_log2
int tor_log2(uint64_t u64)
Definition
bits.c:16
round_to_power_of_2
uint64_t round_to_power_of_2(uint64_t u64)
Definition
bits.c:49
bits.h
Header for bits.c.
Generated by
1.9.8