1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
|
// OpenVPN -- An application to securely tunnel IP networks
// over a single port, with support for SSL/TLS-based
// session authentication and key exchange,
// packet encryption, packet authentication, and
// packet compression.
//
// Copyright (C) 2012-2022 OpenVPN Inc.
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU Affero General Public License Version 3
// as published by the Free Software Foundation.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU Affero General Public License for more details.
//
// You should have received a copy of the GNU Affero General Public License
// along with this program in the COPYING file.
// If not, see <http://www.gnu.org/licenses/>.
#ifndef OPENVPN_COMMON_FFS_H
#define OPENVPN_COMMON_FFS_H
// find_first_set: find the one-based position of the first 1 bit in
// a word (scanning from least significant bit to most significant)
// find_last_set: find the one-based position of the last 1 bit in
// a word (scanning from most significant bit to least significant)
namespace openvpn {
#if defined(__GNUC__)
template <typename T>
inline constexpr int n_bits_type()
{
return sizeof(T) * 8;
}
template <typename T>
inline constexpr int n_bits_type(const T &v)
{
return sizeof(v) * 8;
}
inline int find_first_set(const unsigned int v)
{
if (!v)
return 0;
return __builtin_ffs(v);
}
inline int find_first_set(const int v)
{
return find_first_set(static_cast<unsigned int>(v));
}
inline int find_last_set(const unsigned int v)
{
if (!v)
return 0;
return n_bits_type(v) - __builtin_clz(v);
}
inline int find_last_set(const int v)
{
return find_last_set(static_cast<unsigned int>(v));
}
inline int find_first_set(const unsigned long v)
{
if (!v)
return 0;
return __builtin_ffsl(v);
}
inline int find_first_set(const long v)
{
return find_first_set(static_cast<unsigned long>(v));
}
inline int find_last_set(const unsigned long v)
{
if (!v)
return 0;
return n_bits_type(v) - __builtin_clzl(v);
}
inline int find_last_set(const long v)
{
return find_last_set(static_cast<unsigned long>(v));
}
inline int find_first_set(const unsigned long long v)
{
if (!v)
return 0;
return __builtin_ffsll(v);
}
inline int find_first_set(const long long v)
{
return find_first_set(static_cast<unsigned long long>(v));
}
inline int find_last_set(const unsigned long long v)
{
if (!v)
return 0;
return n_bits_type(v) - __builtin_clzll(v);
}
inline int find_last_set(const long long v)
{
return find_last_set(static_cast<unsigned long long>(v));
}
#elif defined(_MSC_VER)
#include <intrin.h>
inline int find_first_set(unsigned int x)
{
if (!x)
return 0;
unsigned int r = 0;
_BitScanForward((unsigned long *)&r, x);
return r + 1;
}
inline int find_last_set(unsigned int x)
{
if (!x)
return 0;
unsigned int r = 0;
_BitScanReverse((unsigned long *)&r, x);
return r + 1;
}
#else
#error no find_first_set / find_last_set implementation for this platform
#endif
template <typename T>
inline bool is_pow2(const T v)
{
return v && find_first_set(v) == find_last_set(v);
}
template <typename T>
inline int log2(const T v)
{
return find_last_set(v) - 1;
}
} // namespace openvpn
#endif // OPENVPN_COMMON_FFS_H
|
