1 // Copyright 2020 The Abseil Authors
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // https://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 #ifndef ABSL_NUMERIC_INTERNAL_BITS_H_
16 #define ABSL_NUMERIC_INTERNAL_BITS_H_
17
18 #include <cstdint>
19 #include <limits>
20 #include <type_traits>
21
22 // Clang on Windows has __builtin_clzll; otherwise we need to use the
23 // windows intrinsic functions.
24 #if defined(_MSC_VER) && !defined(__clang__)
25 #include <intrin.h>
26 #endif
27
28 #include "absl/base/attributes.h"
29 #include "absl/base/config.h"
30
31 #if defined(__GNUC__) && !defined(__clang__)
32 // GCC
33 #define ABSL_NUMERIC_INTERNAL_HAVE_BUILTIN_OR_GCC(x) 1
34 #else
35 #define ABSL_NUMERIC_INTERNAL_HAVE_BUILTIN_OR_GCC(x) ABSL_HAVE_BUILTIN(x)
36 #endif
37
38 #if ABSL_NUMERIC_INTERNAL_HAVE_BUILTIN_OR_GCC(__builtin_popcountl) && \
39 ABSL_NUMERIC_INTERNAL_HAVE_BUILTIN_OR_GCC(__builtin_popcountll)
40 #define ABSL_INTERNAL_CONSTEXPR_POPCOUNT constexpr
41 #define ABSL_INTERNAL_HAS_CONSTEXPR_POPCOUNT 1
42 #else
43 #define ABSL_INTERNAL_CONSTEXPR_POPCOUNT
44 #define ABSL_INTERNAL_HAS_CONSTEXPR_POPCOUNT 0
45 #endif
46
47 #if ABSL_NUMERIC_INTERNAL_HAVE_BUILTIN_OR_GCC(__builtin_clz) && \
48 ABSL_NUMERIC_INTERNAL_HAVE_BUILTIN_OR_GCC(__builtin_clzll)
49 #define ABSL_INTERNAL_CONSTEXPR_CLZ constexpr
50 #define ABSL_INTERNAL_HAS_CONSTEXPR_CLZ 1
51 #else
52 #define ABSL_INTERNAL_CONSTEXPR_CLZ
53 #define ABSL_INTERNAL_HAS_CONSTEXPR_CLZ 0
54 #endif
55
56 #if ABSL_NUMERIC_INTERNAL_HAVE_BUILTIN_OR_GCC(__builtin_ctz) && \
57 ABSL_NUMERIC_INTERNAL_HAVE_BUILTIN_OR_GCC(__builtin_ctzll)
58 #define ABSL_INTERNAL_CONSTEXPR_CTZ constexpr
59 #define ABSL_INTERNAL_HAS_CONSTEXPR_CTZ 1
60 #else
61 #define ABSL_INTERNAL_CONSTEXPR_CTZ
62 #define ABSL_INTERNAL_HAS_CONSTEXPR_CTZ 0
63 #endif
64
65 namespace absl {
66 ABSL_NAMESPACE_BEGIN
67 namespace numeric_internal {
68
IsPowerOf2(unsigned int x)69 constexpr bool IsPowerOf2(unsigned int x) noexcept {
70 return x != 0 && (x & (x - 1)) == 0;
71 }
72
73 template <class T>
RotateRight(T x,int s)74 ABSL_MUST_USE_RESULT ABSL_ATTRIBUTE_ALWAYS_INLINE constexpr T RotateRight(
75 T x, int s) noexcept {
76 static_assert(std::is_unsigned<T>::value, "T must be unsigned");
77 static_assert(IsPowerOf2(std::numeric_limits<T>::digits),
78 "T must have a power-of-2 size");
79
80 return static_cast<T>(x >> (s & (std::numeric_limits<T>::digits - 1))) |
81 static_cast<T>(x << ((-s) & (std::numeric_limits<T>::digits - 1)));
82 }
83
84 template <class T>
RotateLeft(T x,int s)85 ABSL_MUST_USE_RESULT ABSL_ATTRIBUTE_ALWAYS_INLINE constexpr T RotateLeft(
86 T x, int s) noexcept {
87 static_assert(std::is_unsigned<T>::value, "T must be unsigned");
88 static_assert(IsPowerOf2(std::numeric_limits<T>::digits),
89 "T must have a power-of-2 size");
90
91 return static_cast<T>(x << (s & (std::numeric_limits<T>::digits - 1))) |
92 static_cast<T>(x >> ((-s) & (std::numeric_limits<T>::digits - 1)));
93 }
94
95 ABSL_ATTRIBUTE_ALWAYS_INLINE ABSL_INTERNAL_CONSTEXPR_POPCOUNT inline int
Popcount32(uint32_t x)96 Popcount32(uint32_t x) noexcept {
97 #if ABSL_NUMERIC_INTERNAL_HAVE_BUILTIN_OR_GCC(__builtin_popcount)
98 static_assert(sizeof(unsigned int) == sizeof(x),
99 "__builtin_popcount does not take 32-bit arg");
100 return __builtin_popcount(x);
101 #else
102 x -= ((x >> 1) & 0x55555555);
103 x = ((x >> 2) & 0x33333333) + (x & 0x33333333);
104 return static_cast<int>((((x + (x >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24);
105 #endif
106 }
107
108 ABSL_ATTRIBUTE_ALWAYS_INLINE ABSL_INTERNAL_CONSTEXPR_POPCOUNT inline int
Popcount64(uint64_t x)109 Popcount64(uint64_t x) noexcept {
110 #if ABSL_NUMERIC_INTERNAL_HAVE_BUILTIN_OR_GCC(__builtin_popcountll)
111 static_assert(sizeof(unsigned long long) == sizeof(x), // NOLINT(runtime/int)
112 "__builtin_popcount does not take 64-bit arg");
113 return __builtin_popcountll(x);
114 #else
115 x -= (x >> 1) & 0x5555555555555555ULL;
116 x = ((x >> 2) & 0x3333333333333333ULL) + (x & 0x3333333333333333ULL);
117 return static_cast<int>(
118 (((x + (x >> 4)) & 0xF0F0F0F0F0F0F0FULL) * 0x101010101010101ULL) >> 56);
119 #endif
120 }
121
122 template <class T>
123 ABSL_ATTRIBUTE_ALWAYS_INLINE ABSL_INTERNAL_CONSTEXPR_POPCOUNT inline int
Popcount(T x)124 Popcount(T x) noexcept {
125 static_assert(std::is_unsigned<T>::value, "T must be unsigned");
126 static_assert(IsPowerOf2(std::numeric_limits<T>::digits),
127 "T must have a power-of-2 size");
128 static_assert(sizeof(x) <= sizeof(uint64_t), "T is too large");
129 return sizeof(x) <= sizeof(uint32_t) ? Popcount32(x) : Popcount64(x);
130 }
131
132 ABSL_ATTRIBUTE_ALWAYS_INLINE ABSL_INTERNAL_CONSTEXPR_CLZ inline int
CountLeadingZeroes32(uint32_t x)133 CountLeadingZeroes32(uint32_t x) {
134 #if ABSL_NUMERIC_INTERNAL_HAVE_BUILTIN_OR_GCC(__builtin_clz)
135 // Use __builtin_clz, which uses the following instructions:
136 // x86: bsr, lzcnt
137 // ARM64: clz
138 // PPC: cntlzd
139
140 static_assert(sizeof(unsigned int) == sizeof(x),
141 "__builtin_clz does not take 32-bit arg");
142 // Handle 0 as a special case because __builtin_clz(0) is undefined.
143 return x == 0 ? 32 : __builtin_clz(x);
144 #elif defined(_MSC_VER) && !defined(__clang__)
145 unsigned long result = 0; // NOLINT(runtime/int)
146 if (_BitScanReverse(&result, x)) {
147 return 31 - result;
148 }
149 return 32;
150 #else
151 int zeroes = 28;
152 if (x >> 16) {
153 zeroes -= 16;
154 x >>= 16;
155 }
156 if (x >> 8) {
157 zeroes -= 8;
158 x >>= 8;
159 }
160 if (x >> 4) {
161 zeroes -= 4;
162 x >>= 4;
163 }
164 return "\4\3\2\2\1\1\1\1\0\0\0\0\0\0\0"[x] + zeroes;
165 #endif
166 }
167
168 ABSL_ATTRIBUTE_ALWAYS_INLINE ABSL_INTERNAL_CONSTEXPR_CLZ inline int
CountLeadingZeroes16(uint16_t x)169 CountLeadingZeroes16(uint16_t x) {
170 #if ABSL_HAVE_BUILTIN(__builtin_clzg)
171 return x == 0 ? 16 : __builtin_clzg(x);
172 #elif ABSL_HAVE_BUILTIN(__builtin_clzs)
173 static_assert(sizeof(unsigned short) == sizeof(x), // NOLINT(runtime/int)
174 "__builtin_clzs does not take 16-bit arg");
175 return x == 0 ? 16 : __builtin_clzs(x);
176 #else
177 return CountLeadingZeroes32(x) - 16;
178 #endif
179 }
180
181 ABSL_ATTRIBUTE_ALWAYS_INLINE ABSL_INTERNAL_CONSTEXPR_CLZ inline int
CountLeadingZeroes64(uint64_t x)182 CountLeadingZeroes64(uint64_t x) {
183 #if ABSL_NUMERIC_INTERNAL_HAVE_BUILTIN_OR_GCC(__builtin_clzll)
184 // Use __builtin_clzll, which uses the following instructions:
185 // x86: bsr, lzcnt
186 // ARM64: clz
187 // PPC: cntlzd
188 static_assert(sizeof(unsigned long long) == sizeof(x), // NOLINT(runtime/int)
189 "__builtin_clzll does not take 64-bit arg");
190
191 // Handle 0 as a special case because __builtin_clzll(0) is undefined.
192 return x == 0 ? 64 : __builtin_clzll(x);
193 #elif defined(_MSC_VER) && !defined(__clang__) && \
194 (defined(_M_X64) || defined(_M_ARM64))
195 // MSVC does not have __buitin_clzll. Use _BitScanReverse64.
196 unsigned long result = 0; // NOLINT(runtime/int)
197 if (_BitScanReverse64(&result, x)) {
198 return 63 - result;
199 }
200 return 64;
201 #elif defined(_MSC_VER) && !defined(__clang__)
202 // MSVC does not have __buitin_clzll. Compose two calls to _BitScanReverse
203 unsigned long result = 0; // NOLINT(runtime/int)
204 if ((x >> 32) &&
205 _BitScanReverse(&result, static_cast<unsigned long>(x >> 32))) {
206 return 31 - result;
207 }
208 if (_BitScanReverse(&result, static_cast<unsigned long>(x))) {
209 return 63 - result;
210 }
211 return 64;
212 #else
213 int zeroes = 60;
214 if (x >> 32) {
215 zeroes -= 32;
216 x >>= 32;
217 }
218 if (x >> 16) {
219 zeroes -= 16;
220 x >>= 16;
221 }
222 if (x >> 8) {
223 zeroes -= 8;
224 x >>= 8;
225 }
226 if (x >> 4) {
227 zeroes -= 4;
228 x >>= 4;
229 }
230 return "\4\3\2\2\1\1\1\1\0\0\0\0\0\0\0"[x] + zeroes;
231 #endif
232 }
233
234 template <typename T>
235 ABSL_ATTRIBUTE_ALWAYS_INLINE ABSL_INTERNAL_CONSTEXPR_CLZ inline int
CountLeadingZeroes(T x)236 CountLeadingZeroes(T x) {
237 static_assert(std::is_unsigned<T>::value, "T must be unsigned");
238 static_assert(IsPowerOf2(std::numeric_limits<T>::digits),
239 "T must have a power-of-2 size");
240 static_assert(sizeof(T) <= sizeof(uint64_t), "T too large");
241 return sizeof(T) <= sizeof(uint16_t)
242 ? CountLeadingZeroes16(static_cast<uint16_t>(x)) -
243 (std::numeric_limits<uint16_t>::digits -
244 std::numeric_limits<T>::digits)
245 : (sizeof(T) <= sizeof(uint32_t)
246 ? CountLeadingZeroes32(static_cast<uint32_t>(x)) -
247 (std::numeric_limits<uint32_t>::digits -
248 std::numeric_limits<T>::digits)
249 : CountLeadingZeroes64(x));
250 }
251
252 ABSL_ATTRIBUTE_ALWAYS_INLINE ABSL_INTERNAL_CONSTEXPR_CTZ inline int
CountTrailingZeroesNonzero32(uint32_t x)253 CountTrailingZeroesNonzero32(uint32_t x) {
254 #if ABSL_NUMERIC_INTERNAL_HAVE_BUILTIN_OR_GCC(__builtin_ctz)
255 static_assert(sizeof(unsigned int) == sizeof(x),
256 "__builtin_ctz does not take 32-bit arg");
257 return __builtin_ctz(x);
258 #elif defined(_MSC_VER) && !defined(__clang__)
259 unsigned long result = 0; // NOLINT(runtime/int)
260 _BitScanForward(&result, x);
261 return result;
262 #else
263 int c = 31;
264 x &= ~x + 1;
265 if (x & 0x0000FFFF) c -= 16;
266 if (x & 0x00FF00FF) c -= 8;
267 if (x & 0x0F0F0F0F) c -= 4;
268 if (x & 0x33333333) c -= 2;
269 if (x & 0x55555555) c -= 1;
270 return c;
271 #endif
272 }
273
274 ABSL_ATTRIBUTE_ALWAYS_INLINE ABSL_INTERNAL_CONSTEXPR_CTZ inline int
CountTrailingZeroesNonzero64(uint64_t x)275 CountTrailingZeroesNonzero64(uint64_t x) {
276 #if ABSL_NUMERIC_INTERNAL_HAVE_BUILTIN_OR_GCC(__builtin_ctzll)
277 static_assert(sizeof(unsigned long long) == sizeof(x), // NOLINT(runtime/int)
278 "__builtin_ctzll does not take 64-bit arg");
279 return __builtin_ctzll(x);
280 #elif defined(_MSC_VER) && !defined(__clang__) && \
281 (defined(_M_X64) || defined(_M_ARM64))
282 unsigned long result = 0; // NOLINT(runtime/int)
283 _BitScanForward64(&result, x);
284 return result;
285 #elif defined(_MSC_VER) && !defined(__clang__)
286 unsigned long result = 0; // NOLINT(runtime/int)
287 if (static_cast<uint32_t>(x) == 0) {
288 _BitScanForward(&result, static_cast<unsigned long>(x >> 32));
289 return result + 32;
290 }
291 _BitScanForward(&result, static_cast<unsigned long>(x));
292 return result;
293 #else
294 int c = 63;
295 x &= ~x + 1;
296 if (x & 0x00000000FFFFFFFF) c -= 32;
297 if (x & 0x0000FFFF0000FFFF) c -= 16;
298 if (x & 0x00FF00FF00FF00FF) c -= 8;
299 if (x & 0x0F0F0F0F0F0F0F0F) c -= 4;
300 if (x & 0x3333333333333333) c -= 2;
301 if (x & 0x5555555555555555) c -= 1;
302 return c;
303 #endif
304 }
305
306 ABSL_ATTRIBUTE_ALWAYS_INLINE ABSL_INTERNAL_CONSTEXPR_CTZ inline int
CountTrailingZeroesNonzero16(uint16_t x)307 CountTrailingZeroesNonzero16(uint16_t x) {
308 #if ABSL_HAVE_BUILTIN(__builtin_ctzg)
309 return __builtin_ctzg(x);
310 #elif ABSL_HAVE_BUILTIN(__builtin_ctzs)
311 static_assert(sizeof(unsigned short) == sizeof(x), // NOLINT(runtime/int)
312 "__builtin_ctzs does not take 16-bit arg");
313 return __builtin_ctzs(x);
314 #else
315 return CountTrailingZeroesNonzero32(x);
316 #endif
317 }
318
319 template <class T>
320 ABSL_ATTRIBUTE_ALWAYS_INLINE ABSL_INTERNAL_CONSTEXPR_CTZ inline int
CountTrailingZeroes(T x)321 CountTrailingZeroes(T x) noexcept {
322 static_assert(std::is_unsigned<T>::value, "T must be unsigned");
323 static_assert(IsPowerOf2(std::numeric_limits<T>::digits),
324 "T must have a power-of-2 size");
325 static_assert(sizeof(T) <= sizeof(uint64_t), "T too large");
326 return x == 0 ? std::numeric_limits<T>::digits
327 : (sizeof(T) <= sizeof(uint16_t)
328 ? CountTrailingZeroesNonzero16(static_cast<uint16_t>(x))
329 : (sizeof(T) <= sizeof(uint32_t)
330 ? CountTrailingZeroesNonzero32(
331 static_cast<uint32_t>(x))
332 : CountTrailingZeroesNonzero64(x)));
333 }
334
335 // If T is narrower than unsigned, T{1} << bit_width will be promoted. We
336 // want to force it to wraparound so that bit_ceil of an invalid value are not
337 // core constant expressions.
338 template <class T>
339 ABSL_ATTRIBUTE_ALWAYS_INLINE ABSL_INTERNAL_CONSTEXPR_CLZ inline
340 typename std::enable_if<std::is_unsigned<T>::value, T>::type
BitCeilPromotionHelper(T x,T promotion)341 BitCeilPromotionHelper(T x, T promotion) {
342 return (T{1} << (x + promotion)) >> promotion;
343 }
344
345 template <class T>
346 ABSL_ATTRIBUTE_ALWAYS_INLINE ABSL_INTERNAL_CONSTEXPR_CLZ inline
347 typename std::enable_if<std::is_unsigned<T>::value, T>::type
BitCeilNonPowerOf2(T x)348 BitCeilNonPowerOf2(T x) {
349 // If T is narrower than unsigned, it undergoes promotion to unsigned when we
350 // shift. We calculate the number of bits added by the wider type.
351 return BitCeilPromotionHelper(
352 static_cast<T>(std::numeric_limits<T>::digits - CountLeadingZeroes(x)),
353 T{sizeof(T) >= sizeof(unsigned) ? 0
354 : std::numeric_limits<unsigned>::digits -
355 std::numeric_limits<T>::digits});
356 }
357
358 } // namespace numeric_internal
359 ABSL_NAMESPACE_END
360 } // namespace absl
361
362 #endif // ABSL_NUMERIC_INTERNAL_BITS_H_
363