1 //===-- llvm/Support/MathExtras.h - Useful math functions -------*- C++ -*-===//
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
9 // This file contains some functions that are useful for math stuff.
11 //===----------------------------------------------------------------------===//
13 #ifndef LLVM_SUPPORT_MATHEXTRAS_H
14 #define LLVM_SUPPORT_MATHEXTRAS_H
16 #include "llvm/Support/Compiler.h"
17 #include "llvm/Support/SwapByteOrder.h"
23 #include <type_traits>
25 #ifdef __ANDROID_NDK__
26 #include <android/api-level.h>
30 // Declare these intrinsics manually rather including intrin.h. It's very
31 // expensive, and MathExtras.h is popular.
32 // #include <intrin.h>
34 unsigned char _BitScanForward(unsigned long *_Index
, unsigned long _Mask
);
35 unsigned char _BitScanForward64(unsigned long *_Index
, unsigned __int64 _Mask
);
36 unsigned char _BitScanReverse(unsigned long *_Index
, unsigned long _Mask
);
37 unsigned char _BitScanReverse64(unsigned long *_Index
, unsigned __int64 _Mask
);
43 /// The behavior an operation has on an input of 0.
45 /// The returned value is undefined.
47 /// The returned value is numeric_limits<T>::max()
49 /// The returned value is numeric_limits<T>::digits
53 /// Mathematical constants.
55 // TODO: Track C++20 std::numbers.
56 // TODO: Favor using the hexadecimal FP constants (requires C++17).
57 constexpr double e
= 2.7182818284590452354, // (0x1.5bf0a8b145749P+1) https://oeis.org/A001113
58 egamma
= .57721566490153286061, // (0x1.2788cfc6fb619P-1) https://oeis.org/A001620
59 ln2
= .69314718055994530942, // (0x1.62e42fefa39efP-1) https://oeis.org/A002162
60 ln10
= 2.3025850929940456840, // (0x1.24bb1bbb55516P+1) https://oeis.org/A002392
61 log2e
= 1.4426950408889634074, // (0x1.71547652b82feP+0)
62 log10e
= .43429448190325182765, // (0x1.bcb7b1526e50eP-2)
63 pi
= 3.1415926535897932385, // (0x1.921fb54442d18P+1) https://oeis.org/A000796
64 inv_pi
= .31830988618379067154, // (0x1.45f306bc9c883P-2) https://oeis.org/A049541
65 sqrtpi
= 1.7724538509055160273, // (0x1.c5bf891b4ef6bP+0) https://oeis.org/A002161
66 inv_sqrtpi
= .56418958354775628695, // (0x1.20dd750429b6dP-1) https://oeis.org/A087197
67 sqrt2
= 1.4142135623730950488, // (0x1.6a09e667f3bcdP+0) https://oeis.org/A00219
68 inv_sqrt2
= .70710678118654752440, // (0x1.6a09e667f3bcdP-1)
69 sqrt3
= 1.7320508075688772935, // (0x1.bb67ae8584caaP+0) https://oeis.org/A002194
70 inv_sqrt3
= .57735026918962576451, // (0x1.279a74590331cP-1)
71 phi
= 1.6180339887498948482; // (0x1.9e3779b97f4a8P+0) https://oeis.org/A001622
72 constexpr float ef
= 2.71828183F
, // (0x1.5bf0a8P+1) https://oeis.org/A001113
73 egammaf
= .577215665F
, // (0x1.2788d0P-1) https://oeis.org/A001620
74 ln2f
= .693147181F
, // (0x1.62e430P-1) https://oeis.org/A002162
75 ln10f
= 2.30258509F
, // (0x1.26bb1cP+1) https://oeis.org/A002392
76 log2ef
= 1.44269504F
, // (0x1.715476P+0)
77 log10ef
= .434294482F
, // (0x1.bcb7b2P-2)
78 pif
= 3.14159265F
, // (0x1.921fb6P+1) https://oeis.org/A000796
79 inv_pif
= .318309886F
, // (0x1.45f306P-2) https://oeis.org/A049541
80 sqrtpif
= 1.77245385F
, // (0x1.c5bf8aP+0) https://oeis.org/A002161
81 inv_sqrtpif
= .564189584F
, // (0x1.20dd76P-1) https://oeis.org/A087197
82 sqrt2f
= 1.41421356F
, // (0x1.6a09e6P+0) https://oeis.org/A002193
83 inv_sqrt2f
= .707106781F
, // (0x1.6a09e6P-1)
84 sqrt3f
= 1.73205081F
, // (0x1.bb67aeP+0) https://oeis.org/A002194
85 inv_sqrt3f
= .577350269F
, // (0x1.279a74P-1)
86 phif
= 1.61803399F
; // (0x1.9e377aP+0) https://oeis.org/A001622
87 } // namespace numbers
90 template <typename T
, std::size_t SizeOfT
> struct TrailingZerosCounter
{
91 static unsigned count(T Val
, ZeroBehavior
) {
93 return std::numeric_limits
<T
>::digits
;
98 unsigned ZeroBits
= 0;
99 T Shift
= std::numeric_limits
<T
>::digits
>> 1;
100 T Mask
= std::numeric_limits
<T
>::max() >> Shift
;
102 if ((Val
& Mask
) == 0) {
113 #if defined(__GNUC__) || defined(_MSC_VER)
114 template <typename T
> struct TrailingZerosCounter
<T
, 4> {
115 static unsigned count(T Val
, ZeroBehavior ZB
) {
116 if (ZB
!= ZB_Undefined
&& Val
== 0)
119 #if __has_builtin(__builtin_ctz) || defined(__GNUC__)
120 return __builtin_ctz(Val
);
121 #elif defined(_MSC_VER)
123 _BitScanForward(&Index
, Val
);
129 #if !defined(_MSC_VER) || defined(_M_X64)
130 template <typename T
> struct TrailingZerosCounter
<T
, 8> {
131 static unsigned count(T Val
, ZeroBehavior ZB
) {
132 if (ZB
!= ZB_Undefined
&& Val
== 0)
135 #if __has_builtin(__builtin_ctzll) || defined(__GNUC__)
136 return __builtin_ctzll(Val
);
137 #elif defined(_MSC_VER)
139 _BitScanForward64(&Index
, Val
);
146 } // namespace detail
148 /// Count number of 0's from the least significant bit to the most
149 /// stopping at the first 1.
151 /// Only unsigned integral types are allowed.
153 /// \param ZB the behavior on an input of 0. Only ZB_Width and ZB_Undefined are
155 template <typename T
>
156 unsigned countTrailingZeros(T Val
, ZeroBehavior ZB
= ZB_Width
) {
157 static_assert(std::numeric_limits
<T
>::is_integer
&&
158 !std::numeric_limits
<T
>::is_signed
,
159 "Only unsigned integral types are allowed.");
160 return llvm::detail::TrailingZerosCounter
<T
, sizeof(T
)>::count(Val
, ZB
);
164 template <typename T
, std::size_t SizeOfT
> struct LeadingZerosCounter
{
165 static unsigned count(T Val
, ZeroBehavior
) {
167 return std::numeric_limits
<T
>::digits
;
170 unsigned ZeroBits
= 0;
171 for (T Shift
= std::numeric_limits
<T
>::digits
>> 1; Shift
; Shift
>>= 1) {
172 T Tmp
= Val
>> Shift
;
182 #if defined(__GNUC__) || defined(_MSC_VER)
183 template <typename T
> struct LeadingZerosCounter
<T
, 4> {
184 static unsigned count(T Val
, ZeroBehavior ZB
) {
185 if (ZB
!= ZB_Undefined
&& Val
== 0)
188 #if __has_builtin(__builtin_clz) || defined(__GNUC__)
189 return __builtin_clz(Val
);
190 #elif defined(_MSC_VER)
192 _BitScanReverse(&Index
, Val
);
198 #if !defined(_MSC_VER) || defined(_M_X64)
199 template <typename T
> struct LeadingZerosCounter
<T
, 8> {
200 static unsigned count(T Val
, ZeroBehavior ZB
) {
201 if (ZB
!= ZB_Undefined
&& Val
== 0)
204 #if __has_builtin(__builtin_clzll) || defined(__GNUC__)
205 return __builtin_clzll(Val
);
206 #elif defined(_MSC_VER)
208 _BitScanReverse64(&Index
, Val
);
215 } // namespace detail
217 /// Count number of 0's from the most significant bit to the least
218 /// stopping at the first 1.
220 /// Only unsigned integral types are allowed.
222 /// \param ZB the behavior on an input of 0. Only ZB_Width and ZB_Undefined are
224 template <typename T
>
225 unsigned countLeadingZeros(T Val
, ZeroBehavior ZB
= ZB_Width
) {
226 static_assert(std::numeric_limits
<T
>::is_integer
&&
227 !std::numeric_limits
<T
>::is_signed
,
228 "Only unsigned integral types are allowed.");
229 return llvm::detail::LeadingZerosCounter
<T
, sizeof(T
)>::count(Val
, ZB
);
232 /// Get the index of the first set bit starting from the least
235 /// Only unsigned integral types are allowed.
237 /// \param ZB the behavior on an input of 0. Only ZB_Max and ZB_Undefined are
239 template <typename T
> T
findFirstSet(T Val
, ZeroBehavior ZB
= ZB_Max
) {
240 if (ZB
== ZB_Max
&& Val
== 0)
241 return std::numeric_limits
<T
>::max();
243 return countTrailingZeros(Val
, ZB_Undefined
);
246 /// Create a bitmask with the N right-most bits set to 1, and all other
247 /// bits set to 0. Only unsigned types are allowed.
248 template <typename T
> T
maskTrailingOnes(unsigned N
) {
249 static_assert(std::is_unsigned
<T
>::value
, "Invalid type!");
250 const unsigned Bits
= CHAR_BIT
* sizeof(T
);
251 assert(N
<= Bits
&& "Invalid bit index");
252 return N
== 0 ? 0 : (T(-1) >> (Bits
- N
));
255 /// Create a bitmask with the N left-most bits set to 1, and all other
256 /// bits set to 0. Only unsigned types are allowed.
257 template <typename T
> T
maskLeadingOnes(unsigned N
) {
258 return ~maskTrailingOnes
<T
>(CHAR_BIT
* sizeof(T
) - N
);
261 /// Create a bitmask with the N right-most bits set to 0, and all other
262 /// bits set to 1. Only unsigned types are allowed.
263 template <typename T
> T
maskTrailingZeros(unsigned N
) {
264 return maskLeadingOnes
<T
>(CHAR_BIT
* sizeof(T
) - N
);
267 /// Create a bitmask with the N left-most bits set to 0, and all other
268 /// bits set to 1. Only unsigned types are allowed.
269 template <typename T
> T
maskLeadingZeros(unsigned N
) {
270 return maskTrailingOnes
<T
>(CHAR_BIT
* sizeof(T
) - N
);
273 /// Get the index of the last set bit starting from the least
276 /// Only unsigned integral types are allowed.
278 /// \param ZB the behavior on an input of 0. Only ZB_Max and ZB_Undefined are
280 template <typename T
> T
findLastSet(T Val
, ZeroBehavior ZB
= ZB_Max
) {
281 if (ZB
== ZB_Max
&& Val
== 0)
282 return std::numeric_limits
<T
>::max();
284 // Use ^ instead of - because both gcc and llvm can remove the associated ^
285 // in the __builtin_clz intrinsic on x86.
286 return countLeadingZeros(Val
, ZB_Undefined
) ^
287 (std::numeric_limits
<T
>::digits
- 1);
290 /// Macro compressed bit reversal table for 256 bits.
292 /// http://graphics.stanford.edu/~seander/bithacks.html#BitReverseTable
293 static const unsigned char BitReverseTable256
[256] = {
294 #define R2(n) n, n + 2 * 64, n + 1 * 64, n + 3 * 64
295 #define R4(n) R2(n), R2(n + 2 * 16), R2(n + 1 * 16), R2(n + 3 * 16)
296 #define R6(n) R4(n), R4(n + 2 * 4), R4(n + 1 * 4), R4(n + 3 * 4)
297 R6(0), R6(2), R6(1), R6(3)
303 /// Reverse the bits in \p Val.
304 template <typename T
>
305 T
reverseBits(T Val
) {
306 unsigned char in
[sizeof(Val
)];
307 unsigned char out
[sizeof(Val
)];
308 std::memcpy(in
, &Val
, sizeof(Val
));
309 for (unsigned i
= 0; i
< sizeof(Val
); ++i
)
310 out
[(sizeof(Val
) - i
) - 1] = BitReverseTable256
[in
[i
]];
311 std::memcpy(&Val
, out
, sizeof(Val
));
315 // NOTE: The following support functions use the _32/_64 extensions instead of
316 // type overloading so that signed and unsigned integers can be used without
319 /// Return the high 32 bits of a 64 bit value.
320 constexpr inline uint32_t Hi_32(uint64_t Value
) {
321 return static_cast<uint32_t>(Value
>> 32);
324 /// Return the low 32 bits of a 64 bit value.
325 constexpr inline uint32_t Lo_32(uint64_t Value
) {
326 return static_cast<uint32_t>(Value
);
329 /// Make a 64-bit integer from a high / low pair of 32-bit integers.
330 constexpr inline uint64_t Make_64(uint32_t High
, uint32_t Low
) {
331 return ((uint64_t)High
<< 32) | (uint64_t)Low
;
334 /// Checks if an integer fits into the given bit width.
335 template <unsigned N
> constexpr inline bool isInt(int64_t x
) {
336 return N
>= 64 || (-(INT64_C(1)<<(N
-1)) <= x
&& x
< (INT64_C(1)<<(N
-1)));
338 // Template specializations to get better code for common cases.
339 template <> constexpr inline bool isInt
<8>(int64_t x
) {
340 return static_cast<int8_t>(x
) == x
;
342 template <> constexpr inline bool isInt
<16>(int64_t x
) {
343 return static_cast<int16_t>(x
) == x
;
345 template <> constexpr inline bool isInt
<32>(int64_t x
) {
346 return static_cast<int32_t>(x
) == x
;
349 /// Checks if a signed integer is an N bit number shifted left by S.
350 template <unsigned N
, unsigned S
>
351 constexpr inline bool isShiftedInt(int64_t x
) {
353 N
> 0, "isShiftedInt<0> doesn't make sense (refers to a 0-bit number.");
354 static_assert(N
+ S
<= 64, "isShiftedInt<N, S> with N + S > 64 is too wide.");
355 return isInt
<N
+ S
>(x
) && (x
% (UINT64_C(1) << S
) == 0);
358 /// Checks if an unsigned integer fits into the given bit width.
360 /// This is written as two functions rather than as simply
362 /// return N >= 64 || X < (UINT64_C(1) << N);
364 /// to keep MSVC from (incorrectly) warning on isUInt<64> that we're shifting
365 /// left too many places.
366 template <unsigned N
>
367 constexpr inline typename
std::enable_if
<(N
< 64), bool>::type
369 static_assert(N
> 0, "isUInt<0> doesn't make sense");
370 return X
< (UINT64_C(1) << (N
));
372 template <unsigned N
>
373 constexpr inline typename
std::enable_if
<N
>= 64, bool>::type
378 // Template specializations to get better code for common cases.
379 template <> constexpr inline bool isUInt
<8>(uint64_t x
) {
380 return static_cast<uint8_t>(x
) == x
;
382 template <> constexpr inline bool isUInt
<16>(uint64_t x
) {
383 return static_cast<uint16_t>(x
) == x
;
385 template <> constexpr inline bool isUInt
<32>(uint64_t x
) {
386 return static_cast<uint32_t>(x
) == x
;
389 /// Checks if a unsigned integer is an N bit number shifted left by S.
390 template <unsigned N
, unsigned S
>
391 constexpr inline bool isShiftedUInt(uint64_t x
) {
393 N
> 0, "isShiftedUInt<0> doesn't make sense (refers to a 0-bit number)");
394 static_assert(N
+ S
<= 64,
395 "isShiftedUInt<N, S> with N + S > 64 is too wide.");
396 // Per the two static_asserts above, S must be strictly less than 64. So
397 // 1 << S is not undefined behavior.
398 return isUInt
<N
+ S
>(x
) && (x
% (UINT64_C(1) << S
) == 0);
401 /// Gets the maximum value for a N-bit unsigned integer.
402 inline uint64_t maxUIntN(uint64_t N
) {
403 assert(N
> 0 && N
<= 64 && "integer width out of range");
405 // uint64_t(1) << 64 is undefined behavior, so we can't do
406 // (uint64_t(1) << N) - 1
407 // without checking first that N != 64. But this works and doesn't have a
409 return UINT64_MAX
>> (64 - N
);
412 /// Gets the minimum value for a N-bit signed integer.
413 inline int64_t minIntN(int64_t N
) {
414 assert(N
> 0 && N
<= 64 && "integer width out of range");
416 return -(UINT64_C(1)<<(N
-1));
419 /// Gets the maximum value for a N-bit signed integer.
420 inline int64_t maxIntN(int64_t N
) {
421 assert(N
> 0 && N
<= 64 && "integer width out of range");
423 // This relies on two's complement wraparound when N == 64, so we convert to
424 // int64_t only at the very end to avoid UB.
425 return (UINT64_C(1) << (N
- 1)) - 1;
428 /// Checks if an unsigned integer fits into the given (dynamic) bit width.
429 inline bool isUIntN(unsigned N
, uint64_t x
) {
430 return N
>= 64 || x
<= maxUIntN(N
);
433 /// Checks if an signed integer fits into the given (dynamic) bit width.
434 inline bool isIntN(unsigned N
, int64_t x
) {
435 return N
>= 64 || (minIntN(N
) <= x
&& x
<= maxIntN(N
));
438 /// Return true if the argument is a non-empty sequence of ones starting at the
439 /// least significant bit with the remainder zero (32 bit version).
440 /// Ex. isMask_32(0x0000FFFFU) == true.
441 constexpr inline bool isMask_32(uint32_t Value
) {
442 return Value
&& ((Value
+ 1) & Value
) == 0;
445 /// Return true if the argument is a non-empty sequence of ones starting at the
446 /// least significant bit with the remainder zero (64 bit version).
447 constexpr inline bool isMask_64(uint64_t Value
) {
448 return Value
&& ((Value
+ 1) & Value
) == 0;
451 /// Return true if the argument contains a non-empty sequence of ones with the
452 /// remainder zero (32 bit version.) Ex. isShiftedMask_32(0x0000FF00U) == true.
453 constexpr inline bool isShiftedMask_32(uint32_t Value
) {
454 return Value
&& isMask_32((Value
- 1) | Value
);
457 /// Return true if the argument contains a non-empty sequence of ones with the
458 /// remainder zero (64 bit version.)
459 constexpr inline bool isShiftedMask_64(uint64_t Value
) {
460 return Value
&& isMask_64((Value
- 1) | Value
);
463 /// Return true if the argument is a power of two > 0.
464 /// Ex. isPowerOf2_32(0x00100000U) == true (32 bit edition.)
465 constexpr inline bool isPowerOf2_32(uint32_t Value
) {
466 return Value
&& !(Value
& (Value
- 1));
469 /// Return true if the argument is a power of two > 0 (64 bit edition.)
470 constexpr inline bool isPowerOf2_64(uint64_t Value
) {
471 return Value
&& !(Value
& (Value
- 1));
474 /// Return a byte-swapped representation of the 16-bit argument.
475 inline uint16_t ByteSwap_16(uint16_t Value
) {
476 return sys::SwapByteOrder_16(Value
);
479 /// Return a byte-swapped representation of the 32-bit argument.
480 inline uint32_t ByteSwap_32(uint32_t Value
) {
481 return sys::SwapByteOrder_32(Value
);
484 /// Return a byte-swapped representation of the 64-bit argument.
485 inline uint64_t ByteSwap_64(uint64_t Value
) {
486 return sys::SwapByteOrder_64(Value
);
489 /// Count the number of ones from the most significant bit to the first
492 /// Ex. countLeadingOnes(0xFF0FFF00) == 8.
493 /// Only unsigned integral types are allowed.
495 /// \param ZB the behavior on an input of all ones. Only ZB_Width and
496 /// ZB_Undefined are valid arguments.
497 template <typename T
>
498 unsigned countLeadingOnes(T Value
, ZeroBehavior ZB
= ZB_Width
) {
499 static_assert(std::numeric_limits
<T
>::is_integer
&&
500 !std::numeric_limits
<T
>::is_signed
,
501 "Only unsigned integral types are allowed.");
502 return countLeadingZeros
<T
>(~Value
, ZB
);
505 /// Count the number of ones from the least significant bit to the first
508 /// Ex. countTrailingOnes(0x00FF00FF) == 8.
509 /// Only unsigned integral types are allowed.
511 /// \param ZB the behavior on an input of all ones. Only ZB_Width and
512 /// ZB_Undefined are valid arguments.
513 template <typename T
>
514 unsigned countTrailingOnes(T Value
, ZeroBehavior ZB
= ZB_Width
) {
515 static_assert(std::numeric_limits
<T
>::is_integer
&&
516 !std::numeric_limits
<T
>::is_signed
,
517 "Only unsigned integral types are allowed.");
518 return countTrailingZeros
<T
>(~Value
, ZB
);
522 template <typename T
, std::size_t SizeOfT
> struct PopulationCounter
{
523 static unsigned count(T Value
) {
524 // Generic version, forward to 32 bits.
525 static_assert(SizeOfT
<= 4, "Not implemented!");
526 #if defined(__GNUC__)
527 return __builtin_popcount(Value
);
530 v
= v
- ((v
>> 1) & 0x55555555);
531 v
= (v
& 0x33333333) + ((v
>> 2) & 0x33333333);
532 return ((v
+ (v
>> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
537 template <typename T
> struct PopulationCounter
<T
, 8> {
538 static unsigned count(T Value
) {
539 #if defined(__GNUC__)
540 return __builtin_popcountll(Value
);
543 v
= v
- ((v
>> 1) & 0x5555555555555555ULL
);
544 v
= (v
& 0x3333333333333333ULL
) + ((v
>> 2) & 0x3333333333333333ULL
);
545 v
= (v
+ (v
>> 4)) & 0x0F0F0F0F0F0F0F0FULL
;
546 return unsigned((uint64_t)(v
* 0x0101010101010101ULL
) >> 56);
550 } // namespace detail
552 /// Count the number of set bits in a value.
553 /// Ex. countPopulation(0xF000F000) = 8
554 /// Returns 0 if the word is zero.
555 template <typename T
>
556 inline unsigned countPopulation(T Value
) {
557 static_assert(std::numeric_limits
<T
>::is_integer
&&
558 !std::numeric_limits
<T
>::is_signed
,
559 "Only unsigned integral types are allowed.");
560 return detail::PopulationCounter
<T
, sizeof(T
)>::count(Value
);
563 /// Compile time Log2.
564 /// Valid only for positive powers of two.
565 template <size_t kValue
> constexpr inline size_t CTLog2() {
566 static_assert(kValue
> 0 && llvm::isPowerOf2_64(kValue
),
567 "Value is not a valid power of 2");
568 return 1 + CTLog2
<kValue
/ 2>();
571 template <> constexpr inline size_t CTLog2
<1>() { return 0; }
573 /// Return the log base 2 of the specified value.
574 inline double Log2(double Value
) {
575 #if defined(__ANDROID_API__) && __ANDROID_API__ < 18
576 return __builtin_log(Value
) / __builtin_log(2.0);
582 /// Return the floor log base 2 of the specified value, -1 if the value is zero.
583 /// (32 bit edition.)
584 /// Ex. Log2_32(32) == 5, Log2_32(1) == 0, Log2_32(0) == -1, Log2_32(6) == 2
585 inline unsigned Log2_32(uint32_t Value
) {
586 return 31 - countLeadingZeros(Value
);
589 /// Return the floor log base 2 of the specified value, -1 if the value is zero.
590 /// (64 bit edition.)
591 inline unsigned Log2_64(uint64_t Value
) {
592 return 63 - countLeadingZeros(Value
);
595 /// Return the ceil log base 2 of the specified value, 32 if the value is zero.
596 /// (32 bit edition).
597 /// Ex. Log2_32_Ceil(32) == 5, Log2_32_Ceil(1) == 0, Log2_32_Ceil(6) == 3
598 inline unsigned Log2_32_Ceil(uint32_t Value
) {
599 return 32 - countLeadingZeros(Value
- 1);
602 /// Return the ceil log base 2 of the specified value, 64 if the value is zero.
603 /// (64 bit edition.)
604 inline unsigned Log2_64_Ceil(uint64_t Value
) {
605 return 64 - countLeadingZeros(Value
- 1);
608 /// Return the greatest common divisor of the values using Euclid's algorithm.
609 template <typename T
>
610 inline T
greatestCommonDivisor(T A
, T B
) {
619 inline uint64_t GreatestCommonDivisor64(uint64_t A
, uint64_t B
) {
620 return greatestCommonDivisor
<uint64_t>(A
, B
);
623 /// This function takes a 64-bit integer and returns the bit equivalent double.
624 inline double BitsToDouble(uint64_t Bits
) {
626 static_assert(sizeof(uint64_t) == sizeof(double), "Unexpected type sizes");
627 memcpy(&D
, &Bits
, sizeof(Bits
));
631 /// This function takes a 32-bit integer and returns the bit equivalent float.
632 inline float BitsToFloat(uint32_t Bits
) {
634 static_assert(sizeof(uint32_t) == sizeof(float), "Unexpected type sizes");
635 memcpy(&F
, &Bits
, sizeof(Bits
));
639 /// This function takes a double and returns the bit equivalent 64-bit integer.
640 /// Note that copying doubles around changes the bits of NaNs on some hosts,
641 /// notably x86, so this routine cannot be used if these bits are needed.
642 inline uint64_t DoubleToBits(double Double
) {
644 static_assert(sizeof(uint64_t) == sizeof(double), "Unexpected type sizes");
645 memcpy(&Bits
, &Double
, sizeof(Double
));
649 /// This function takes a float and returns the bit equivalent 32-bit integer.
650 /// Note that copying floats around changes the bits of NaNs on some hosts,
651 /// notably x86, so this routine cannot be used if these bits are needed.
652 inline uint32_t FloatToBits(float Float
) {
654 static_assert(sizeof(uint32_t) == sizeof(float), "Unexpected type sizes");
655 memcpy(&Bits
, &Float
, sizeof(Float
));
659 /// A and B are either alignments or offsets. Return the minimum alignment that
660 /// may be assumed after adding the two together.
661 constexpr inline uint64_t MinAlign(uint64_t A
, uint64_t B
) {
662 // The largest power of 2 that divides both A and B.
664 // Replace "-Value" by "1+~Value" in the following commented code to avoid
665 // MSVC warning C4146
666 // return (A | B) & -(A | B);
667 return (A
| B
) & (1 + ~(A
| B
));
670 /// Returns the next power of two (in 64-bits) that is strictly greater than A.
671 /// Returns zero on overflow.
672 inline uint64_t NextPowerOf2(uint64_t A
) {
682 /// Returns the power of two which is less than or equal to the given value.
683 /// Essentially, it is a floor operation across the domain of powers of two.
684 inline uint64_t PowerOf2Floor(uint64_t A
) {
686 return 1ull << (63 - countLeadingZeros(A
, ZB_Undefined
));
689 /// Returns the power of two which is greater than or equal to the given value.
690 /// Essentially, it is a ceil operation across the domain of powers of two.
691 inline uint64_t PowerOf2Ceil(uint64_t A
) {
694 return NextPowerOf2(A
- 1);
697 /// Returns the next integer (mod 2**64) that is greater than or equal to
698 /// \p Value and is a multiple of \p Align. \p Align must be non-zero.
700 /// If non-zero \p Skew is specified, the return value will be a minimal
701 /// integer that is greater than or equal to \p Value and equal to
702 /// \p Align * N + \p Skew for some integer N. If \p Skew is larger than
703 /// \p Align, its value is adjusted to '\p Skew mod \p Align'.
707 /// alignTo(5, 8) = 8
708 /// alignTo(17, 8) = 24
709 /// alignTo(~0LL, 8) = 0
710 /// alignTo(321, 255) = 510
712 /// alignTo(5, 8, 7) = 7
713 /// alignTo(17, 8, 1) = 17
714 /// alignTo(~0LL, 8, 3) = 3
715 /// alignTo(321, 255, 42) = 552
717 inline uint64_t alignTo(uint64_t Value
, uint64_t Align
, uint64_t Skew
= 0) {
718 assert(Align
!= 0u && "Align can't be 0.");
720 return (Value
+ Align
- 1 - Skew
) / Align
* Align
+ Skew
;
723 /// Returns the next integer (mod 2**64) that is greater than or equal to
724 /// \p Value and is a multiple of \c Align. \c Align must be non-zero.
725 template <uint64_t Align
> constexpr inline uint64_t alignTo(uint64_t Value
) {
726 static_assert(Align
!= 0u, "Align must be non-zero");
727 return (Value
+ Align
- 1) / Align
* Align
;
730 /// Returns the integer ceil(Numerator / Denominator).
731 inline uint64_t divideCeil(uint64_t Numerator
, uint64_t Denominator
) {
732 return alignTo(Numerator
, Denominator
) / Denominator
;
735 /// Returns the largest uint64_t less than or equal to \p Value and is
736 /// \p Skew mod \p Align. \p Align must be non-zero
737 inline uint64_t alignDown(uint64_t Value
, uint64_t Align
, uint64_t Skew
= 0) {
738 assert(Align
!= 0u && "Align can't be 0.");
740 return (Value
- Skew
) / Align
* Align
+ Skew
;
743 /// Sign-extend the number in the bottom B bits of X to a 32-bit integer.
744 /// Requires 0 < B <= 32.
745 template <unsigned B
> constexpr inline int32_t SignExtend32(uint32_t X
) {
746 static_assert(B
> 0, "Bit width can't be 0.");
747 static_assert(B
<= 32, "Bit width out of range.");
748 return int32_t(X
<< (32 - B
)) >> (32 - B
);
751 /// Sign-extend the number in the bottom B bits of X to a 32-bit integer.
752 /// Requires 0 < B < 32.
753 inline int32_t SignExtend32(uint32_t X
, unsigned B
) {
754 assert(B
> 0 && "Bit width can't be 0.");
755 assert(B
<= 32 && "Bit width out of range.");
756 return int32_t(X
<< (32 - B
)) >> (32 - B
);
759 /// Sign-extend the number in the bottom B bits of X to a 64-bit integer.
760 /// Requires 0 < B < 64.
761 template <unsigned B
> constexpr inline int64_t SignExtend64(uint64_t x
) {
762 static_assert(B
> 0, "Bit width can't be 0.");
763 static_assert(B
<= 64, "Bit width out of range.");
764 return int64_t(x
<< (64 - B
)) >> (64 - B
);
767 /// Sign-extend the number in the bottom B bits of X to a 64-bit integer.
768 /// Requires 0 < B < 64.
769 inline int64_t SignExtend64(uint64_t X
, unsigned B
) {
770 assert(B
> 0 && "Bit width can't be 0.");
771 assert(B
<= 64 && "Bit width out of range.");
772 return int64_t(X
<< (64 - B
)) >> (64 - B
);
775 /// Subtract two unsigned integers, X and Y, of type T and return the absolute
776 /// value of the result.
777 template <typename T
>
778 typename
std::enable_if
<std::is_unsigned
<T
>::value
, T
>::type
779 AbsoluteDifference(T X
, T Y
) {
780 return std::max(X
, Y
) - std::min(X
, Y
);
783 /// Add two unsigned integers, X and Y, of type T. Clamp the result to the
784 /// maximum representable value of T on overflow. ResultOverflowed indicates if
785 /// the result is larger than the maximum representable value of type T.
786 template <typename T
>
787 typename
std::enable_if
<std::is_unsigned
<T
>::value
, T
>::type
788 SaturatingAdd(T X
, T Y
, bool *ResultOverflowed
= nullptr) {
790 bool &Overflowed
= ResultOverflowed
? *ResultOverflowed
: Dummy
;
791 // Hacker's Delight, p. 29
793 Overflowed
= (Z
< X
|| Z
< Y
);
795 return std::numeric_limits
<T
>::max();
800 /// Multiply two unsigned integers, X and Y, of type T. Clamp the result to the
801 /// maximum representable value of T on overflow. ResultOverflowed indicates if
802 /// the result is larger than the maximum representable value of type T.
803 template <typename T
>
804 typename
std::enable_if
<std::is_unsigned
<T
>::value
, T
>::type
805 SaturatingMultiply(T X
, T Y
, bool *ResultOverflowed
= nullptr) {
807 bool &Overflowed
= ResultOverflowed
? *ResultOverflowed
: Dummy
;
809 // Hacker's Delight, p. 30 has a different algorithm, but we don't use that
810 // because it fails for uint16_t (where multiplication can have undefined
811 // behavior due to promotion to int), and requires a division in addition
812 // to the multiplication.
816 // Log2(Z) would be either Log2Z or Log2Z + 1.
817 // Special case: if X or Y is 0, Log2_64 gives -1, and Log2Z
818 // will necessarily be less than Log2Max as desired.
819 int Log2Z
= Log2_64(X
) + Log2_64(Y
);
820 const T Max
= std::numeric_limits
<T
>::max();
821 int Log2Max
= Log2_64(Max
);
822 if (Log2Z
< Log2Max
) {
825 if (Log2Z
> Log2Max
) {
830 // We're going to use the top bit, and maybe overflow one
831 // bit past it. Multiply all but the bottom bit then add
832 // that on at the end.
834 if (Z
& ~(Max
>> 1)) {
840 return SaturatingAdd(Z
, Y
, ResultOverflowed
);
845 /// Multiply two unsigned integers, X and Y, and add the unsigned integer, A to
846 /// the product. Clamp the result to the maximum representable value of T on
847 /// overflow. ResultOverflowed indicates if the result is larger than the
848 /// maximum representable value of type T.
849 template <typename T
>
850 typename
std::enable_if
<std::is_unsigned
<T
>::value
, T
>::type
851 SaturatingMultiplyAdd(T X
, T Y
, T A
, bool *ResultOverflowed
= nullptr) {
853 bool &Overflowed
= ResultOverflowed
? *ResultOverflowed
: Dummy
;
855 T Product
= SaturatingMultiply(X
, Y
, &Overflowed
);
859 return SaturatingAdd(A
, Product
, &Overflowed
);
862 /// Use this rather than HUGE_VALF; the latter causes warnings on MSVC.
863 extern const float huge_valf
;
866 /// Add two signed integers, computing the two's complement truncated result,
867 /// returning true if overflow occured.
868 template <typename T
>
869 typename
std::enable_if
<std::is_signed
<T
>::value
, T
>::type
870 AddOverflow(T X
, T Y
, T
&Result
) {
871 #if __has_builtin(__builtin_add_overflow)
872 return __builtin_add_overflow(X
, Y
, &Result
);
874 // Perform the unsigned addition.
875 using U
= typename
std::make_unsigned
<T
>::type
;
876 const U UX
= static_cast<U
>(X
);
877 const U UY
= static_cast<U
>(Y
);
878 const U UResult
= UX
+ UY
;
880 // Convert to signed.
881 Result
= static_cast<T
>(UResult
);
883 // Adding two positive numbers should result in a positive number.
886 // Adding two negatives should result in a negative number.
893 /// Subtract two signed integers, computing the two's complement truncated
894 /// result, returning true if an overflow ocurred.
895 template <typename T
>
896 typename
std::enable_if
<std::is_signed
<T
>::value
, T
>::type
897 SubOverflow(T X
, T Y
, T
&Result
) {
898 #if __has_builtin(__builtin_sub_overflow)
899 return __builtin_sub_overflow(X
, Y
, &Result
);
901 // Perform the unsigned addition.
902 using U
= typename
std::make_unsigned
<T
>::type
;
903 const U UX
= static_cast<U
>(X
);
904 const U UY
= static_cast<U
>(Y
);
905 const U UResult
= UX
- UY
;
907 // Convert to signed.
908 Result
= static_cast<T
>(UResult
);
910 // Subtracting a positive number from a negative results in a negative number.
913 // Subtracting a negative number from a positive results in a positive number.
921 /// Multiply two signed integers, computing the two's complement truncated
922 /// result, returning true if an overflow ocurred.
923 template <typename T
>
924 typename
std::enable_if
<std::is_signed
<T
>::value
, T
>::type
925 MulOverflow(T X
, T Y
, T
&Result
) {
926 // Perform the unsigned multiplication on absolute values.
927 using U
= typename
std::make_unsigned
<T
>::type
;
928 const U UX
= X
< 0 ? (0 - static_cast<U
>(X
)) : static_cast<U
>(X
);
929 const U UY
= Y
< 0 ? (0 - static_cast<U
>(Y
)) : static_cast<U
>(Y
);
930 const U UResult
= UX
* UY
;
932 // Convert to signed.
933 const bool IsNegative
= (X
< 0) ^ (Y
< 0);
934 Result
= IsNegative
? (0 - UResult
) : UResult
;
936 // If any of the args was 0, result is 0 and no overflow occurs.
937 if (UX
== 0 || UY
== 0)
940 // UX and UY are in [1, 2^n], where n is the number of digits.
941 // Check how the max allowed absolute value (2^n for negative, 2^(n-1) for
942 // positive) divided by an argument compares to the other.
944 return UX
> (static_cast<U
>(std::numeric_limits
<T
>::max()) + U(1)) / UY
;
946 return UX
> (static_cast<U
>(std::numeric_limits
<T
>::max())) / UY
;
949 } // End llvm namespace