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
|
// 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- OpenVPN Inc.
//
// SPDX-License-Identifier: MPL-2.0 OR AGPL-3.0-only WITH openvpn3-openssl-exception
//
#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
|
