14 #ifndef LLVM_SUPPORT_MATHEXTRAS_H 15 #define LLVM_SUPPORT_MATHEXTRAS_H 17 #include "llvm/Compiler.h" 23 #include <type_traits> 43 static std::size_t count(T Val, ZeroBehavior) {
45 return std::numeric_limits<T>::digits;
48 std::size_t ZeroBits = 0;
49 for (T Shift = std::numeric_limits<T>::digits >> 1; Shift; Shift >>= 1) {
60 #if __GNUC__ >= 4 || defined(_MSC_VER) 62 static std::size_t count(T Val, ZeroBehavior ZB) {
63 if (ZB != ZB_Undefined && Val == 0)
66 #if __has_builtin(__builtin_clz) || LLVM_GNUC_PREREQ(4, 0, 0) 67 return __builtin_clz(Val);
68 #elif defined(_MSC_VER) 70 _BitScanReverse(&Index, Val);
76 #if !defined(_MSC_VER) || defined(_M_X64) 78 static std::size_t count(T Val, ZeroBehavior ZB) {
79 if (ZB != ZB_Undefined && Val == 0)
82 #if __has_builtin(__builtin_clzll) || LLVM_GNUC_PREREQ(4, 0, 0) 83 return __builtin_clzll(Val);
84 #elif defined(_MSC_VER) 86 _BitScanReverse64(&Index, Val);
102 template <
typename T>
103 std::size_t countLeadingZeros(T Val, ZeroBehavior ZB = ZB_Width) {
104 static_assert(std::numeric_limits<T>::is_integer &&
105 !std::numeric_limits<T>::is_signed,
106 "Only unsigned integral types are allowed.");
117 template <
typename T> T findLastSet(T Val, ZeroBehavior ZB = ZB_Max) {
118 if (ZB == ZB_Max && Val == 0)
119 return std::numeric_limits<T>::max();
123 return countLeadingZeros(Val, ZB_Undefined) ^
124 (std::numeric_limits<T>::digits - 1);
130 static const unsigned char BitReverseTable256[256] = {
131 #define R2(n) n, n + 2 * 64, n + 1 * 64, n + 3 * 64 132 #define R4(n) R2(n), R2(n + 2 * 16), R2(n + 1 * 16), R2(n + 3 * 16) 133 #define R6(n) R4(n), R4(n + 2 * 4), R4(n + 1 * 4), R4(n + 3 * 4) 134 R6(0), R6(2), R6(1), R6(3)
141 template <
typename T>
142 T reverseBits(T Val) {
143 unsigned char in[
sizeof(Val)];
144 unsigned char out[
sizeof(Val)];
145 std::memcpy(in, &Val,
sizeof(Val));
146 for (
unsigned i = 0; i <
sizeof(Val); ++i)
147 out[(
sizeof(Val) - i) - 1] = BitReverseTable256[in[i]];
148 std::memcpy(&Val, out,
sizeof(Val));
157 inline uint32_t Hi_32(uint64_t Value) {
158 return static_cast<uint32_t
>(Value >> 32);
162 inline uint32_t Lo_32(uint64_t Value) {
163 return static_cast<uint32_t
>(Value);
168 inline uint64_t Make_64(uint32_t High, uint32_t Low) {
169 return ((uint64_t)High << 32) | (uint64_t)Low;
174 inline bool isInt(int64_t x) {
175 return N >= 64 || (-(INT64_C(1)<<(N-1)) <= x && x < (INT64_C(1)<<(N-1)));
179 inline bool isInt<8>(int64_t x) {
180 return static_cast<int8_t
>(x) == x;
183 inline bool isInt<16>(int64_t x) {
184 return static_cast<int16_t
>(x) == x;
187 inline bool isInt<32>(int64_t x) {
188 return static_cast<int32_t
>(x) == x;
193 template<
unsigned N,
unsigned S>
194 inline bool isShiftedInt(int64_t x) {
195 return isInt<N+S>(x) && (x % (1<<S) == 0);
200 inline bool isUInt(uint64_t x) {
201 return N >= 64 || x < (UINT64_C(1)<<(N));
205 inline bool isUInt<8>(uint64_t x) {
206 return static_cast<uint8_t
>(x) == x;
209 inline bool isUInt<16>(uint64_t x) {
210 return static_cast<uint16_t
>(x) == x;
213 inline bool isUInt<32>(uint64_t x) {
214 return static_cast<uint32_t
>(x) == x;
219 template<
unsigned N,
unsigned S>
220 inline bool isShiftedUInt(uint64_t x) {
221 return isUInt<N+S>(x) && (x % (1<<S) == 0);
225 inline uint64_t maxUIntN(uint64_t N) {
226 assert(N > 0 && N <= 64 &&
"integer width out of range");
228 return (UINT64_C(1) << N) - 1;
232 inline int64_t minIntN(int64_t N) {
233 assert(N > 0 && N <= 64 &&
"integer width out of range");
235 return -(INT64_C(1)<<(N-1));
239 inline int64_t maxIntN(int64_t N) {
240 assert(N > 0 && N <= 64 &&
"integer width out of range");
242 return (INT64_C(1)<<(N-1)) - 1;
247 inline bool isUIntN(
unsigned N, uint64_t x) {
248 return N >= 64 || x <= maxUIntN(N);
253 inline bool isIntN(
unsigned N, int64_t x) {
254 return N >= 64 || (minIntN(N) <= x && x <= maxIntN(N));
260 inline bool isMask_32(uint32_t Value) {
261 return Value && ((Value + 1) & Value) == 0;
267 inline bool isMask_64(uint64_t Value) {
268 return Value && ((Value + 1) & Value) == 0;
274 inline bool isShiftedMask_32(uint32_t Value) {
275 return Value && isMask_32((Value - 1) | Value);
280 inline bool isShiftedMask_64(uint64_t Value) {
281 return Value && isMask_64((Value - 1) | Value);
286 inline bool isPowerOf2_32(uint32_t Value) {
287 return Value && !(Value & (Value - 1));
292 inline bool isPowerOf2_64(uint64_t Value) {
293 return Value && !(Value & (Value - int64_t(1L)));
304 template <
typename T>
305 std::size_t countLeadingOnes(T Value, ZeroBehavior ZB = ZB_Width) {
306 static_assert(std::numeric_limits<T>::is_integer &&
307 !std::numeric_limits<T>::is_signed,
308 "Only unsigned integral types are allowed.");
309 return countLeadingZeros(~Value, ZB);
314 static unsigned count(T Value) {
316 static_assert(SizeOfT <= 4,
"Not implemented!");
318 return __builtin_popcount(Value);
321 v = v - ((v >> 1) & 0x55555555);
322 v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
323 return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
329 static unsigned count(T Value) {
331 return __builtin_popcountll(Value);
334 v = v - ((v >> 1) & 0x5555555555555555ULL);
335 v = (v & 0x3333333333333333ULL) + ((v >> 2) & 0x3333333333333333ULL);
336 v = (v + (v >> 4)) & 0x0F0F0F0F0F0F0F0FULL;
337 return unsigned((uint64_t)(v * 0x0101010101010101ULL) >> 56);
346 template <
typename T>
347 inline unsigned countPopulation(T Value) {
348 static_assert(std::numeric_limits<T>::is_integer &&
349 !std::numeric_limits<T>::is_signed,
350 "Only unsigned integral types are allowed.");
355 inline double Log2(
double Value) {
356 #if defined(__ANDROID_API__) && __ANDROID_API__ < 18 357 return __builtin_log(Value) / __builtin_log(2.0);
359 return std::log2(Value);
366 inline unsigned Log2_32(uint32_t Value) {
367 return 31 - countLeadingZeros(Value);
372 inline unsigned Log2_64(uint64_t Value) {
373 return 63 - countLeadingZeros(Value);
379 inline unsigned Log2_32_Ceil(uint32_t Value) {
380 return 32 - countLeadingZeros(Value - 1);
385 inline unsigned Log2_64_Ceil(uint64_t Value) {
386 return 64 - countLeadingZeros(Value - 1);
391 inline uint64_t GreatestCommonDivisor64(uint64_t A, uint64_t B) {
402 inline double BitsToDouble(uint64_t Bits) {
413 inline float BitsToFloat(uint32_t Bits) {
426 inline uint64_t DoubleToBits(
double Double) {
439 inline uint32_t FloatToBits(
float Float) {
450 inline uint64_t MinAlign(uint64_t A, uint64_t B) {
456 return (A | B) & (1 + ~(A | B));
463 inline uintptr_t alignAddr(
const void *Addr,
size_t Alignment) {
464 assert(Alignment && isPowerOf2_64((uint64_t)Alignment) &&
465 "Alignment is not a power of two!");
467 assert((uintptr_t)Addr + Alignment - 1 >= (uintptr_t)Addr);
469 return (((uintptr_t)Addr + Alignment - 1) & ~(uintptr_t)(Alignment - 1));
474 inline size_t alignmentAdjustment(
const void *Ptr,
size_t Alignment) {
475 return alignAddr(Ptr, Alignment) - (uintptr_t)Ptr;
480 inline uint64_t NextPowerOf2(uint64_t A) {
492 inline uint64_t PowerOf2Floor(uint64_t A) {
494 return 1ull << (63 - countLeadingZeros(A, ZB_Undefined));
517 inline uint64_t alignTo(uint64_t Value, uint64_t Align, uint64_t Skew = 0) {
519 return (Value + Align - 1 - Skew) / Align * Align + Skew;
524 inline uint64_t alignDown(uint64_t Value, uint64_t Align, uint64_t Skew = 0) {
526 return (Value - Skew) / Align * Align + Skew;
532 inline uint64_t OffsetToAlignment(uint64_t Value, uint64_t Align) {
533 return alignTo(Value, Align) - Value;
538 template <
unsigned B>
inline int32_t SignExtend32(uint32_t x) {
539 return int32_t(x << (32 - B)) >> (32 - B);
544 inline int32_t SignExtend32(uint32_t X,
unsigned B) {
545 return int32_t(X << (32 - B)) >> (32 - B);
550 template <
unsigned B>
inline int64_t SignExtend64(uint64_t x) {
551 return int64_t(x << (64 - B)) >> (64 - B);
556 inline int64_t SignExtend64(uint64_t X,
unsigned B) {
557 return int64_t(X << (64 - B)) >> (64 - B);
562 template <
typename T>
563 typename std::enable_if<std::is_unsigned<T>::value, T>::type
564 AbsoluteDifference(T X, T Y) {
565 return std::max(X, Y) - std::min(X, Y);
572 template <
typename T>
573 typename std::enable_if<std::is_unsigned<T>::value, T>::type
574 SaturatingAdd(T X, T Y,
bool *ResultOverflowed =
nullptr) {
576 bool &Overflowed = ResultOverflowed ? *ResultOverflowed : Dummy;
579 Overflowed = (Z < X || Z < Y);
581 return std::numeric_limits<T>::max();
590 template <
typename T>
591 typename std::enable_if<std::is_unsigned<T>::value, T>::type
592 SaturatingMultiply(T X, T Y,
bool *ResultOverflowed =
nullptr) {
594 bool &Overflowed = ResultOverflowed ? *ResultOverflowed : Dummy;
606 int Log2Z = Log2_64(X) + Log2_64(Y);
607 const T Max = std::numeric_limits<T>::max();
608 int Log2Max = Log2_64(Max);
609 if (Log2Z < Log2Max) {
612 if (Log2Z > Log2Max) {
621 if (Z & ~(Max >> 1)) {
627 return SaturatingAdd(Z, Y, ResultOverflowed);
638 template <
typename T>
639 typename std::enable_if<std::is_unsigned<T>::value, T>::type
640 SaturatingMultiplyAdd(T X, T Y, T A,
bool *ResultOverflowed =
nullptr) {
642 bool &Overflowed = ResultOverflowed ? *ResultOverflowed : Dummy;
644 T Product = SaturatingMultiply(X, Y, &Overflowed);
648 return SaturatingAdd(A, Product, &Overflowed);
Definition: MathExtras.h:42
Definition: MathExtras.h:313