14 #ifndef WPIUTIL_WPI_MATHEXTRAS_H 15 #define WPIUTIL_WPI_MATHEXTRAS_H 17 #include "wpi/Compiler.h" 25 #include <type_traits> 46 return std::numeric_limits<T>::digits;
51 std::size_t ZeroBits = 0;
52 T Shift = std::numeric_limits<T>::digits >> 1;
53 T Mask = std::numeric_limits<T>::max() >> Shift;
55 if ((Val & Mask) == 0) {
66 #if __GNUC__ >= 4 || defined(_MSC_VER) 72 #if __has_builtin(__builtin_ctz) || LLVM_GNUC_PREREQ(4, 0, 0) 73 return __builtin_ctz(Val);
74 #elif defined(_MSC_VER) 76 _BitScanForward(&Index, Val);
82 #if !defined(_MSC_VER) || defined(_M_X64) 88 #if __has_builtin(__builtin_ctzll) || LLVM_GNUC_PREREQ(4, 0, 0) 89 return __builtin_ctzll(Val);
90 #elif defined(_MSC_VER) 92 _BitScanForward64(&Index, Val);
108 template <
typename T>
110 static_assert(std::numeric_limits<T>::is_integer &&
111 !std::numeric_limits<T>::is_signed,
112 "Only unsigned integral types are allowed.");
120 return std::numeric_limits<T>::digits;
123 std::size_t ZeroBits = 0;
124 for (T Shift = std::numeric_limits<T>::digits >> 1; Shift; Shift >>= 1) {
125 T Tmp = Val >> Shift;
135 #if __GNUC__ >= 4 || defined(_MSC_VER) 141 #if __has_builtin(__builtin_clz) || LLVM_GNUC_PREREQ(4, 0, 0) 142 return __builtin_clz(Val);
143 #elif defined(_MSC_VER) 145 _BitScanReverse(&Index, Val);
151 #if !defined(_MSC_VER) || defined(_M_X64) 157 #if __has_builtin(__builtin_clzll) || LLVM_GNUC_PREREQ(4, 0, 0) 158 return __builtin_clzll(Val);
159 #elif defined(_MSC_VER) 161 _BitScanReverse64(&Index, Val);
177 template <
typename T>
179 static_assert(std::numeric_limits<T>::is_integer &&
180 !std::numeric_limits<T>::is_signed,
181 "Only unsigned integral types are allowed.");
193 if (ZB ==
ZB_Max && Val == 0)
194 return std::numeric_limits<T>::max();
202 static_assert(std::is_unsigned<T>::value,
"Invalid type!");
203 const unsigned Bits = CHAR_BIT *
sizeof(T);
204 assert(N <= Bits &&
"Invalid bit index");
205 return N == 0 ? 0 : (T(-1) >> (Bits - N));
211 return ~maskTrailingOnes<T>(CHAR_BIT *
sizeof(T) - N);
217 return maskLeadingOnes<T>(CHAR_BIT *
sizeof(T) - N);
223 return maskTrailingOnes<T>(CHAR_BIT *
sizeof(T) - N);
234 if (ZB ==
ZB_Max && Val == 0)
235 return std::numeric_limits<T>::max();
240 (std::numeric_limits<T>::digits - 1);
246 static const unsigned char BitReverseTable256[256] = {
247 #define R2(n) n, n + 2 * 64, n + 1 * 64, n + 3 * 64 248 #define R4(n) R2(n), R2(n + 2 * 16), R2(n + 1 * 16), R2(n + 3 * 16) 249 #define R6(n) R4(n), R4(n + 2 * 4), R4(n + 1 * 4), R4(n + 3 * 4) 250 R6(0), R6(2), R6(1), R6(3)
257 template <
typename T>
259 unsigned char in[
sizeof(Val)];
260 unsigned char out[
sizeof(Val)];
261 std::memcpy(in, &Val,
sizeof(Val));
262 for (
unsigned i = 0; i <
sizeof(Val); ++i)
263 out[(
sizeof(Val) - i) - 1] = BitReverseTable256[in[i]];
264 std::memcpy(&Val, out,
sizeof(Val));
273 constexpr
inline uint32_t
Hi_32(uint64_t Value) {
274 return static_cast<uint32_t
>(Value >> 32);
278 constexpr
inline uint32_t
Lo_32(uint64_t Value) {
279 return static_cast<uint32_t
>(Value);
283 constexpr
inline uint64_t
Make_64(uint32_t High, uint32_t Low) {
284 return ((uint64_t)High << 32) | (uint64_t)Low;
288 template <
unsigned N> constexpr
inline bool isInt(int64_t x) {
289 return N >= 64 || (-(INT64_C(1)<<(N-1)) <= x && x < (INT64_C(1)<<(N-1)));
292 template <> constexpr
inline bool isInt<8>(int64_t x) {
293 return static_cast<int8_t
>(x) == x;
295 template <> constexpr
inline bool isInt<16>(int64_t x) {
296 return static_cast<int16_t
>(x) == x;
298 template <> constexpr
inline bool isInt<32>(int64_t x) {
299 return static_cast<int32_t
>(x) == x;
303 template <
unsigned N,
unsigned S>
306 N > 0,
"isShiftedInt<0> doesn't make sense (refers to a 0-bit number.");
307 static_assert(N + S <= 64,
"isShiftedInt<N, S> with N + S > 64 is too wide.");
308 return isInt<N + S>(x) && (x % (UINT64_C(1) << S) == 0);
319 template <
unsigned N>
320 constexpr
inline typename std::enable_if<(N < 64), bool>::type
322 static_assert(N > 0,
"isUInt<0> doesn't make sense");
323 return X < (UINT64_C(1) << (N));
325 template <
unsigned N>
326 constexpr
inline typename std::enable_if<N >= 64,
bool>::type
332 template <> constexpr
inline bool isUInt<8>(uint64_t x) {
333 return static_cast<uint8_t
>(x) == x;
335 template <> constexpr
inline bool isUInt<16>(uint64_t x) {
336 return static_cast<uint16_t
>(x) == x;
338 template <> constexpr
inline bool isUInt<32>(uint64_t x) {
339 return static_cast<uint32_t
>(x) == x;
343 template <
unsigned N,
unsigned S>
346 N > 0,
"isShiftedUInt<0> doesn't make sense (refers to a 0-bit number)");
347 static_assert(N + S <= 64,
348 "isShiftedUInt<N, S> with N + S > 64 is too wide.");
351 return isUInt<N + S>(x) && (x % (UINT64_C(1) << S) == 0);
356 assert(N > 0 && N <= 64 &&
"integer width out of range");
362 return UINT64_MAX >> (64 - N);
367 assert(N > 0 && N <= 64 &&
"integer width out of range");
369 return -(UINT64_C(1)<<(N-1));
374 assert(N > 0 && N <= 64 &&
"integer width out of range");
378 return (UINT64_C(1) << (N - 1)) - 1;
387 inline bool isIntN(
unsigned N, int64_t x) {
395 return Value && ((Value + 1) & Value) == 0;
401 return Value && ((Value + 1) & Value) == 0;
407 return Value &&
isMask_32((Value - 1) | Value);
413 return Value &&
isMask_64((Value - 1) | Value);
419 return Value && !(Value & (Value - 1));
424 return Value && !(Value & (Value - 1));
435 template <
typename T>
437 static_assert(std::numeric_limits<T>::is_integer &&
438 !std::numeric_limits<T>::is_signed,
439 "Only unsigned integral types are allowed.");
440 return countLeadingZeros<T>(~Value, ZB);
451 template <
typename T>
453 static_assert(std::numeric_limits<T>::is_integer &&
454 !std::numeric_limits<T>::is_signed,
455 "Only unsigned integral types are allowed.");
456 return countTrailingZeros<T>(~Value, ZB);
461 static unsigned count(T Value) {
463 static_assert(SizeOfT <= 4,
"Not implemented!");
465 return __builtin_popcount(Value);
468 v = v - ((v >> 1) & 0x55555555);
469 v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
470 return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
476 static unsigned count(T Value) {
478 return __builtin_popcountll(Value);
481 v = v - ((v >> 1) & 0x5555555555555555ULL);
482 v = (v & 0x3333333333333333ULL) + ((v >> 2) & 0x3333333333333333ULL);
483 v = (v + (v >> 4)) & 0x0F0F0F0F0F0F0F0FULL;
484 return unsigned((uint64_t)(v * 0x0101010101010101ULL) >> 56);
493 template <
typename T>
495 static_assert(std::numeric_limits<T>::is_integer &&
496 !std::numeric_limits<T>::is_signed,
497 "Only unsigned integral types are allowed.");
502 inline double Log2(
double Value) {
503 #if defined(__ANDROID_API__) && __ANDROID_API__ < 18 504 return __builtin_log(Value) / __builtin_log(2.0);
506 return std::log2(Value);
549 static_assert(
sizeof(uint64_t) ==
sizeof(
double),
"Unexpected type sizes");
550 memcpy(&D, &Bits,
sizeof(Bits));
557 static_assert(
sizeof(uint32_t) ==
sizeof(
float),
"Unexpected type sizes");
558 memcpy(&F, &Bits,
sizeof(Bits));
567 static_assert(
sizeof(uint64_t) ==
sizeof(
double),
"Unexpected type sizes");
568 memcpy(&Bits, &Double,
sizeof(Double));
577 static_assert(
sizeof(uint32_t) ==
sizeof(
float),
"Unexpected type sizes");
578 memcpy(&Bits, &Float,
sizeof(Float));
584 constexpr
inline uint64_t
MinAlign(uint64_t A, uint64_t B) {
590 return (A | B) & (1 + ~(A | B));
597 inline uintptr_t
alignAddr(
const void *Addr,
size_t Alignment) {
599 "Alignment is not a power of two!");
601 assert((uintptr_t)Addr + Alignment - 1 >= (uintptr_t)Addr);
603 return (((uintptr_t)Addr + Alignment - 1) & ~(uintptr_t)(Alignment - 1));
609 return alignAddr(Ptr, Alignment) - (uintptr_t)Ptr;
659 inline uint64_t
alignTo(uint64_t Value, uint64_t Align, uint64_t Skew = 0) {
660 assert(Align != 0u &&
"Align can't be 0.");
662 return (Value + Align - 1 - Skew) / Align * Align + Skew;
667 template <u
int64_t Align> constexpr
inline uint64_t
alignTo(uint64_t Value) {
668 static_assert(Align != 0u,
"Align must be non-zero");
669 return (Value + Align - 1) / Align * Align;
673 inline uint64_t
divideCeil(uint64_t Numerator, uint64_t Denominator) {
674 return alignTo(Numerator, Denominator) / Denominator;
681 template <u
int64_t Align>
683 static_assert(Align != 0u,
"Align must be non-zero");
684 template <u
int64_t Value>
686 static const uint64_t value = (Value + Align - 1) / Align * Align;
692 inline uint64_t
alignDown(uint64_t Value, uint64_t Align, uint64_t Skew = 0) {
693 assert(Align != 0u &&
"Align can't be 0.");
695 return (Value - Skew) / Align * Align + Skew;
702 return alignTo(Value, Align) - Value;
707 template <
unsigned B> constexpr
inline int32_t
SignExtend32(uint32_t X) {
708 static_assert(B > 0,
"Bit width can't be 0.");
709 static_assert(B <= 32,
"Bit width out of range.");
710 return int32_t(X << (32 - B)) >> (32 - B);
716 assert(B > 0 &&
"Bit width can't be 0.");
717 assert(B <= 32 &&
"Bit width out of range.");
718 return int32_t(X << (32 - B)) >> (32 - B);
723 template <
unsigned B> constexpr
inline int64_t
SignExtend64(uint64_t x) {
724 static_assert(B > 0,
"Bit width can't be 0.");
725 static_assert(B <= 64,
"Bit width out of range.");
726 return int64_t(x << (64 - B)) >> (64 - B);
732 assert(B > 0 &&
"Bit width can't be 0.");
733 assert(B <= 64 &&
"Bit width out of range.");
734 return int64_t(X << (64 - B)) >> (64 - B);
739 template <
typename T>
740 typename std::enable_if<std::is_unsigned<T>::value, T>::type
742 return std::max(X, Y) - std::min(X, Y);
748 template <
typename T>
749 typename std::enable_if<std::is_unsigned<T>::value, T>::type
752 bool &Overflowed = ResultOverflowed ? *ResultOverflowed : Dummy;
755 Overflowed = (Z < X || Z < Y);
757 return std::numeric_limits<T>::max();
765 template <
typename T>
766 typename std::enable_if<std::is_unsigned<T>::value, T>::type
769 bool &Overflowed = ResultOverflowed ? *ResultOverflowed : Dummy;
782 const T Max = std::numeric_limits<T>::max();
784 if (Log2Z < Log2Max) {
787 if (Log2Z > Log2Max) {
796 if (Z & ~(Max >> 1)) {
811 template <
typename T>
812 typename std::enable_if<std::is_unsigned<T>::value, T>::type
815 bool &Overflowed = ResultOverflowed ? *ResultOverflowed : Dummy;
constexpr bool isShiftedMask_64(uint64_t Value)
Return true if the argument contains a non-empty sequence of ones with the remainder zero (64 bit ver...
Definition: MathExtras.h:412
unsigned Log2_32_Ceil(uint32_t Value)
Return the ceil log base 2 of the specified value, 32 if the value is zero.
Definition: MathExtras.h:526
std::size_t countLeadingZeros(T Val, ZeroBehavior ZB=ZB_Width)
Count number of 0's from the most significant bit to the least stopping at the first 1...
Definition: MathExtras.h:178
constexpr int64_t SignExtend64(uint64_t x)
Sign-extend the number in the bottom B bits of X to a 64-bit integer.
Definition: MathExtras.h:723
std::size_t countTrailingZeros(T Val, ZeroBehavior ZB=ZB_Width)
Count number of 0's from the least significant bit to the most stopping at the first 1...
Definition: MathExtras.h:109
bool isUIntN(unsigned N, uint64_t x)
Checks if an unsigned integer fits into the given (dynamic) bit width.
Definition: MathExtras.h:382
uint64_t divideCeil(uint64_t Numerator, uint64_t Denominator)
Returns the integer ceil(Numerator / Denominator).
Definition: MathExtras.h:673
T findFirstSet(T Val, ZeroBehavior ZB=ZB_Max)
Get the index of the first set bit starting from the least significant bit.
Definition: MathExtras.h:192
Definition: MathExtras.h:460
constexpr bool isPowerOf2_32(uint32_t Value)
Return true if the argument is a power of two > 0.
Definition: MathExtras.h:418
constexpr bool isShiftedUInt(uint64_t x)
Checks if a unsigned integer is an N bit number shifted left by S.
Definition: MathExtras.h:344
std::size_t countLeadingOnes(T Value, ZeroBehavior ZB=ZB_Width)
Count the number of ones from the most significant bit to the first zero bit.
Definition: MathExtras.h:436
constexpr uint64_t MinAlign(uint64_t A, uint64_t B)
A and B are either alignments or offsets.
Definition: MathExtras.h:584
The returned value is undefined.
Definition: MathExtras.h:35
int64_t maxIntN(int64_t N)
Gets the maximum value for a N-bit signed integer.
Definition: MathExtras.h:373
ZeroBehavior
The behavior an operation has on an input of 0.
Definition: MathExtras.h:33
std::enable_if< std::is_unsigned< T >::value, T >::type SaturatingAdd(T X, T Y, bool *ResultOverflowed=nullptr)
Add two unsigned integers, X and Y, of type T.
Definition: MathExtras.h:750
constexpr bool isMask_64(uint64_t Value)
Return true if the argument is a non-empty sequence of ones starting at the least significant bit wit...
Definition: MathExtras.h:400
The returned value is numeric_limits<T>::digits.
Definition: MathExtras.h:39
uint64_t alignDown(uint64_t Value, uint64_t Align, uint64_t Skew=0)
Returns the largest uint64_t less than or equal to Value and is Skew mod Align.
Definition: MathExtras.h:692
The returned value is numeric_limits<T>::max()
Definition: MathExtras.h:37
Definition: MathExtras.h:43
namespace to hold default to_json function
Definition: json_binary_writer.cpp:39
std::enable_if< std::is_unsigned< T >::value, T >::type AbsoluteDifference(T X, T Y)
Subtract two unsigned integers, X and Y, of type T and return the absolute value of the result...
Definition: MathExtras.h:741
std::enable_if< std::is_unsigned< T >::value, T >::type SaturatingMultiply(T X, T Y, bool *ResultOverflowed=nullptr)
Multiply two unsigned integers, X and Y, of type T.
Definition: MathExtras.h:767
alignTo for contexts where a constant expression is required.
Definition: MathExtras.h:682
double Log2(double Value)
Return the log base 2 of the specified value.
Definition: MathExtras.h:502
uint64_t maxUIntN(uint64_t N)
Gets the maximum value for a N-bit unsigned integer.
Definition: MathExtras.h:355
uint64_t NextPowerOf2(uint64_t A)
Returns the next power of two (in 64-bits) that is strictly greater than A.
Definition: MathExtras.h:614
T maskTrailingZeros(unsigned N)
Create a bitmask with the N right-most bits set to 0, and all other bits set to 1.
Definition: MathExtras.h:216
bool isIntN(unsigned N, int64_t x)
Checks if an signed integer fits into the given (dynamic) bit width.
Definition: MathExtras.h:387
constexpr bool isMask_32(uint32_t Value)
Return true if the argument is a non-empty sequence of ones starting at the least significant bit wit...
Definition: MathExtras.h:394
float BitsToFloat(uint32_t Bits)
This function takes a 32-bit integer and returns the bit equivalent float.
Definition: MathExtras.h:555
unsigned Log2_32(uint32_t Value)
Return the floor log base 2 of the specified value, -1 if the value is zero.
Definition: MathExtras.h:513
constexpr bool isShiftedInt(int64_t x)
Checks if a signed integer is an N bit number shifted left by S.
Definition: MathExtras.h:304
std::size_t countTrailingOnes(T Value, ZeroBehavior ZB=ZB_Width)
Count the number of ones from the least significant bit to the first zero bit.
Definition: MathExtras.h:452
uint64_t alignTo(uint64_t Value, uint64_t Align, uint64_t Skew=0)
Returns the next integer (mod 2**64) that is greater than or equal to Value and is a multiple of Alig...
Definition: MathExtras.h:659
T maskTrailingOnes(unsigned N)
Create a bitmask with the N right-most bits set to 1, and all other bits set to 0.
Definition: MathExtras.h:201
constexpr std::enable_if<(N< 64), bool >::type isUInt(uint64_t X)
Checks if an unsigned integer fits into the given bit width.
Definition: MathExtras.h:321
uint64_t PowerOf2Ceil(uint64_t A)
Returns the power of two which is greater than or equal to the given value.
Definition: MathExtras.h:633
size_t alignmentAdjustment(const void *Ptr, size_t Alignment)
Returns the necessary adjustment for aligning Ptr to Alignment bytes, rounding up.
Definition: MathExtras.h:608
constexpr uint64_t Make_64(uint32_t High, uint32_t Low)
Make a 64-bit integer from a high / low pair of 32-bit integers.
Definition: MathExtras.h:283
constexpr bool isInt(int64_t x)
Checks if an integer fits into the given bit width.
Definition: MathExtras.h:288
constexpr uint32_t Hi_32(uint64_t Value)
Return the high 32 bits of a 64 bit value.
Definition: MathExtras.h:273
constexpr uint32_t Lo_32(uint64_t Value)
Return the low 32 bits of a 64 bit value.
Definition: MathExtras.h:278
unsigned Log2_64(uint64_t Value)
Return the floor log base 2 of the specified value, -1 if the value is zero.
Definition: MathExtras.h:519
T maskLeadingOnes(unsigned N)
Create a bitmask with the N left-most bits set to 1, and all other bits set to 0. ...
Definition: MathExtras.h:210
Definition: MathExtras.h:117
uint64_t PowerOf2Floor(uint64_t A)
Returns the power of two which is less than or equal to the given value.
Definition: MathExtras.h:626
uint64_t OffsetToAlignment(uint64_t Value, uint64_t Align)
Returns the offset to the next integer (mod 2**64) that is greater than or equal to Value and is a mu...
Definition: MathExtras.h:701
std::enable_if< std::is_unsigned< T >::value, T >::type SaturatingMultiplyAdd(T X, T Y, T A, bool *ResultOverflowed=nullptr)
Multiply two unsigned integers, X and Y, and add the unsigned integer, A to the product.
Definition: MathExtras.h:813
constexpr int32_t SignExtend32(uint32_t X)
Sign-extend the number in the bottom B bits of X to a 32-bit integer.
Definition: MathExtras.h:707
T findLastSet(T Val, ZeroBehavior ZB=ZB_Max)
Get the index of the last set bit starting from the least significant bit.
Definition: MathExtras.h:233
constexpr bool isPowerOf2_64(uint64_t Value)
Return true if the argument is a power of two > 0 (64 bit edition.)
Definition: MathExtras.h:423
double BitsToDouble(uint64_t Bits)
This function takes a 64-bit integer and returns the bit equivalent double.
Definition: MathExtras.h:547
T maskLeadingZeros(unsigned N)
Create a bitmask with the N left-most bits set to 0, and all other bits set to 1. ...
Definition: MathExtras.h:222
uintptr_t alignAddr(const void *Addr, size_t Alignment)
Aligns Addr to Alignment bytes, rounding up.
Definition: MathExtras.h:597
int64_t minIntN(int64_t N)
Gets the minimum value for a N-bit signed integer.
Definition: MathExtras.h:366
auto count(R &&Range, const E &Element) -> typename std::iterator_traits< decltype(adl_begin(Range))>::difference_type
Wrapper function around std::count to count the number of times an element Element occurs in the give...
Definition: STLExtras.h:941
constexpr bool isShiftedMask_32(uint32_t Value)
Return true if the argument contains a non-empty sequence of ones with the remainder zero (32 bit ver...
Definition: MathExtras.h:406
uint64_t DoubleToBits(double Double)
This function takes a double and returns the bit equivalent 64-bit integer.
Definition: MathExtras.h:565
unsigned countPopulation(T Value)
Count the number of set bits in a value.
Definition: MathExtras.h:494
T reverseBits(T Val)
Reverse the bits in Val.
Definition: MathExtras.h:258
Definition: MathExtras.h:685
unsigned Log2_64_Ceil(uint64_t Value)
Return the ceil log base 2 of the specified value, 64 if the value is zero.
Definition: MathExtras.h:532
uint32_t FloatToBits(float Float)
This function takes a float and returns the bit equivalent 32-bit integer.
Definition: MathExtras.h:575
uint64_t GreatestCommonDivisor64(uint64_t A, uint64_t B)
Return the greatest common divisor of the values using Euclid's algorithm.
Definition: MathExtras.h:537