#ifndef LLVM_SUPPORT_MATHEXTRAS_H
#define LLVM_SUPPORT_MATHEXTRAS_H
#include "llvm/Support/Compiler.h"
#include "llvm/Support/SwapByteOrder.h"
#include "llvm/Support/type_traits.h"
#include <cstring>
#ifdef _MSC_VER
#include <intrin.h>
#include <limits>
#endif
namespace llvm {
enum ZeroBehavior {
ZB_Undefined,
ZB_Max,
ZB_Width
};
template <typename T>
typename enable_if_c<std::numeric_limits<T>::is_integer &&
!std::numeric_limits<T>::is_signed, std::size_t>::type
countTrailingZeros(T Val, ZeroBehavior ZB = ZB_Width) {
(void)ZB;
if (!Val)
return std::numeric_limits<T>::digits;
if (Val & 0x1)
return 0;
std::size_t ZeroBits = 0;
T Shift = std::numeric_limits<T>::digits >> 1;
T Mask = std::numeric_limits<T>::max() >> Shift;
while (Shift) {
if ((Val & Mask) == 0) {
Val >>= Shift;
ZeroBits |= Shift;
}
Shift >>= 1;
Mask >>= Shift;
}
return ZeroBits;
}
template <typename T>
typename enable_if_c<std::numeric_limits<T>::is_integer &&
std::numeric_limits<T>::is_signed, std::size_t>::type
countTrailingZeros(T Val, ZeroBehavior ZB = ZB_Width) LLVM_DELETED_FUNCTION;
#if __GNUC__ >= 4 || _MSC_VER
template <>
inline std::size_t countTrailingZeros<uint32_t>(uint32_t Val, ZeroBehavior ZB) {
if (ZB != ZB_Undefined && Val == 0)
return 32;
#if __has_builtin(__builtin_ctz) || __GNUC_PREREQ(4, 0)
return __builtin_ctz(Val);
#elif _MSC_VER
unsigned long Index;
_BitScanForward(&Index, Val);
return Index;
#endif
}
#if !defined(_MSC_VER) || defined(_M_X64)
template <>
inline std::size_t countTrailingZeros<uint64_t>(uint64_t Val, ZeroBehavior ZB) {
if (ZB != ZB_Undefined && Val == 0)
return 64;
#if __has_builtin(__builtin_ctzll) || __GNUC_PREREQ(4, 0)
return __builtin_ctzll(Val);
#elif _MSC_VER
unsigned long Index;
_BitScanForward64(&Index, Val);
return Index;
#endif
}
#endif
#endif
template <typename T>
typename enable_if_c<std::numeric_limits<T>::is_integer &&
!std::numeric_limits<T>::is_signed, std::size_t>::type
countLeadingZeros(T Val, ZeroBehavior ZB = ZB_Width) {
(void)ZB;
if (!Val)
return std::numeric_limits<T>::digits;
std::size_t ZeroBits = 0;
for (T Shift = std::numeric_limits<T>::digits >> 1; Shift; Shift >>= 1) {
T Tmp = Val >> Shift;
if (Tmp)
Val = Tmp;
else
ZeroBits |= Shift;
}
return ZeroBits;
}
template <typename T>
typename enable_if_c<std::numeric_limits<T>::is_integer &&
std::numeric_limits<T>::is_signed, std::size_t>::type
countLeadingZeros(T Val, ZeroBehavior ZB = ZB_Width) LLVM_DELETED_FUNCTION;
#if __GNUC__ >= 4 || _MSC_VER
template <>
inline std::size_t countLeadingZeros<uint32_t>(uint32_t Val, ZeroBehavior ZB) {
if (ZB != ZB_Undefined && Val == 0)
return 32;
#if __has_builtin(__builtin_clz) || __GNUC_PREREQ(4, 0)
return __builtin_clz(Val);
#elif _MSC_VER
unsigned long Index;
_BitScanReverse(&Index, Val);
return Index ^ 31;
#endif
}
#if !defined(_MSC_VER) || defined(_M_X64)
template <>
inline std::size_t countLeadingZeros<uint64_t>(uint64_t Val, ZeroBehavior ZB) {
if (ZB != ZB_Undefined && Val == 0)
return 64;
#if __has_builtin(__builtin_clzll) || __GNUC_PREREQ(4, 0)
return __builtin_clzll(Val);
#elif _MSC_VER
unsigned long Index;
_BitScanReverse64(&Index, Val);
return Index ^ 63;
#endif
}
#endif
#endif
template <typename T>
typename enable_if_c<std::numeric_limits<T>::is_integer &&
!std::numeric_limits<T>::is_signed, T>::type
findFirstSet(T Val, ZeroBehavior ZB = ZB_Max) {
if (ZB == ZB_Max && Val == 0)
return std::numeric_limits<T>::max();
return countTrailingZeros(Val, ZB_Undefined);
}
template <typename T>
typename enable_if_c<std::numeric_limits<T>::is_integer &&
std::numeric_limits<T>::is_signed, T>::type
findFirstSet(T Val, ZeroBehavior ZB = ZB_Max) LLVM_DELETED_FUNCTION;
template <typename T>
typename enable_if_c<std::numeric_limits<T>::is_integer &&
!std::numeric_limits<T>::is_signed, T>::type
findLastSet(T Val, ZeroBehavior ZB = ZB_Max) {
if (ZB == ZB_Max && Val == 0)
return std::numeric_limits<T>::max();
return countLeadingZeros(Val, ZB_Undefined) ^
(std::numeric_limits<T>::digits - 1);
}
template <typename T>
typename enable_if_c<std::numeric_limits<T>::is_integer &&
std::numeric_limits<T>::is_signed, T>::type
findLastSet(T Val, ZeroBehavior ZB = ZB_Max) LLVM_DELETED_FUNCTION;
static const unsigned char BitReverseTable256[256] = {
#define R2(n) n, n + 2 * 64, n + 1 * 64, n + 3 * 64
#define R4(n) R2(n), R2(n + 2 * 16), R2(n + 1 * 16), R2(n + 3 * 16)
#define R6(n) R4(n), R4(n + 2 * 4), R4(n + 1 * 4), R4(n + 3 * 4)
R6(0), R6(2), R6(1), R6(3)
};
template <typename T>
T reverseBits(T Val) {
unsigned char in[sizeof(Val)];
unsigned char out[sizeof(Val)];
std::memcpy(in, &Val, sizeof(Val));
for (unsigned i = 0; i < sizeof(Val); ++i)
out[(sizeof(Val) - i) - 1] = BitReverseTable256[in[i]];
std::memcpy(&Val, out, sizeof(Val));
return Val;
}
inline uint32_t Hi_32(uint64_t Value) {
return static_cast<uint32_t>(Value >> 32);
}
inline uint32_t Lo_32(uint64_t Value) {
return static_cast<uint32_t>(Value);
}
template<unsigned N>
inline bool isInt(int64_t x) {
return N >= 64 || (-(INT64_C(1)<<(N-1)) <= x && x < (INT64_C(1)<<(N-1)));
}
template<>
inline bool isInt<8>(int64_t x) {
return static_cast<int8_t>(x) == x;
}
template<>
inline bool isInt<16>(int64_t x) {
return static_cast<int16_t>(x) == x;
}
template<>
inline bool isInt<32>(int64_t x) {
return static_cast<int32_t>(x) == x;
}
template<unsigned N, unsigned S>
inline bool isShiftedInt(int64_t x) {
return isInt<N+S>(x) && (x % (1<<S) == 0);
}
template<unsigned N>
inline bool isUInt(uint64_t x) {
return N >= 64 || x < (UINT64_C(1)<<(N));
}
template<>
inline bool isUInt<8>(uint64_t x) {
return static_cast<uint8_t>(x) == x;
}
template<>
inline bool isUInt<16>(uint64_t x) {
return static_cast<uint16_t>(x) == x;
}
template<>
inline bool isUInt<32>(uint64_t x) {
return static_cast<uint32_t>(x) == x;
}
template<unsigned N, unsigned S>
inline bool isShiftedUInt(uint64_t x) {
return isUInt<N+S>(x) && (x % (1<<S) == 0);
}
inline bool isUIntN(unsigned N, uint64_t x) {
return x == (x & (~0ULL >> (64 - N)));
}
inline bool isIntN(unsigned N, int64_t x) {
return N >= 64 || (-(INT64_C(1)<<(N-1)) <= x && x < (INT64_C(1)<<(N-1)));
}
inline bool isMask_32(uint32_t Value) {
return Value && ((Value + 1) & Value) == 0;
}
inline bool isMask_64(uint64_t Value) {
return Value && ((Value + 1) & Value) == 0;
}
inline bool isShiftedMask_32(uint32_t Value) {
return isMask_32((Value - 1) | Value);
}
inline bool isShiftedMask_64(uint64_t Value) {
return isMask_64((Value - 1) | Value);
}
inline bool isPowerOf2_32(uint32_t Value) {
return Value && !(Value & (Value - 1));
}
inline bool isPowerOf2_64(uint64_t Value) {
return Value && !(Value & (Value - int64_t(1L)));
}
inline uint16_t ByteSwap_16(uint16_t Value) {
return sys::SwapByteOrder_16(Value);
}
inline uint32_t ByteSwap_32(uint32_t Value) {
return sys::SwapByteOrder_32(Value);
}
inline uint64_t ByteSwap_64(uint64_t Value) {
return sys::SwapByteOrder_64(Value);
}
inline unsigned CountLeadingOnes_32(uint32_t Value) {
return countLeadingZeros(~Value);
}
inline unsigned CountLeadingOnes_64(uint64_t Value) {
return countLeadingZeros(~Value);
}
inline unsigned CountTrailingOnes_32(uint32_t Value) {
return countTrailingZeros(~Value);
}
inline unsigned CountTrailingOnes_64(uint64_t Value) {
return countTrailingZeros(~Value);
}
inline unsigned CountPopulation_32(uint32_t Value) {
#if __GNUC__ >= 4
return __builtin_popcount(Value);
#else
uint32_t v = Value - ((Value >> 1) & 0x55555555);
v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
#endif
}
inline unsigned CountPopulation_64(uint64_t Value) {
#if __GNUC__ >= 4
return __builtin_popcountll(Value);
#else
uint64_t v = Value - ((Value >> 1) & 0x5555555555555555ULL);
v = (v & 0x3333333333333333ULL) + ((v >> 2) & 0x3333333333333333ULL);
v = (v + (v >> 4)) & 0x0F0F0F0F0F0F0F0FULL;
return unsigned((uint64_t)(v * 0x0101010101010101ULL) >> 56);
#endif
}
inline unsigned Log2_32(uint32_t Value) {
return 31 - countLeadingZeros(Value);
}
inline unsigned Log2_64(uint64_t Value) {
return 63 - countLeadingZeros(Value);
}
inline unsigned Log2_32_Ceil(uint32_t Value) {
return 32 - countLeadingZeros(Value - 1);
}
inline unsigned Log2_64_Ceil(uint64_t Value) {
return 64 - countLeadingZeros(Value - 1);
}
inline uint64_t GreatestCommonDivisor64(uint64_t A, uint64_t B) {
while (B) {
uint64_t T = B;
B = A % B;
A = T;
}
return A;
}
inline double BitsToDouble(uint64_t Bits) {
union {
uint64_t L;
double D;
} T;
T.L = Bits;
return T.D;
}
inline float BitsToFloat(uint32_t Bits) {
union {
uint32_t I;
float F;
} T;
T.I = Bits;
return T.F;
}
inline uint64_t DoubleToBits(double Double) {
union {
uint64_t L;
double D;
} T;
T.D = Double;
return T.L;
}
inline uint32_t FloatToBits(float Float) {
union {
uint32_t I;
float F;
} T;
T.F = Float;
return T.I;
}
int IsNAN(float f);
int IsNAN(double d);
int IsInf(float f);
int IsInf(double d);
inline uint64_t MinAlign(uint64_t A, uint64_t B) {
return (A | B) & (1 + ~(A | B));
}
inline uint64_t NextPowerOf2(uint64_t A) {
A |= (A >> 1);
A |= (A >> 2);
A |= (A >> 4);
A |= (A >> 8);
A |= (A >> 16);
A |= (A >> 32);
return A + 1;
}
inline uint64_t RoundUpToAlignment(uint64_t Value, uint64_t Align) {
return ((Value + Align - 1) / Align) * Align;
}
inline uint64_t OffsetToAlignment(uint64_t Value, uint64_t Align) {
return RoundUpToAlignment(Value, Align) - Value;
}
inline int64_t abs64(int64_t x) {
return (x < 0) ? -x : x;
}
template <unsigned B> inline int32_t SignExtend32(uint32_t x) {
return int32_t(x << (32 - B)) >> (32 - B);
}
inline int32_t SignExtend32(uint32_t X, unsigned B) {
return int32_t(X << (32 - B)) >> (32 - B);
}
template <unsigned B> inline int64_t SignExtend64(uint64_t x) {
return int64_t(x << (64 - B)) >> (64 - B);
}
inline int64_t SignExtend64(uint64_t X, unsigned B) {
return int64_t(X << (64 - B)) >> (64 - B);
}
#if defined(_MSC_VER)
const float huge_valf = std::numeric_limits<float>::infinity();
#else
const float huge_valf = HUGE_VALF;
#endif
}
#endif