1//===-- llvm/Support/MathExtras.h - Useful math functions -------*- C++ -*-===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file contains some functions that are useful for math stuff. 11// 12//===----------------------------------------------------------------------===// 13 14// Taken from llvmCore-3425.0.31. 15 16#ifndef LLVM_SUPPORT_MATHEXTRAS_H 17#define LLVM_SUPPORT_MATHEXTRAS_H 18 19namespace objc { 20 21// NOTE: The following support functions use the _32/_64 extensions instead of 22// type overloading so that signed and unsigned integers can be used without 23// ambiguity. 24 25/// Hi_32 - This function returns the high 32 bits of a 64 bit value. 26inline uint32_t Hi_32(uint64_t Value) { 27 return static_cast<uint32_t>(Value >> 32); 28} 29 30/// Lo_32 - This function returns the low 32 bits of a 64 bit value. 31inline uint32_t Lo_32(uint64_t Value) { 32 return static_cast<uint32_t>(Value); 33} 34 35/// isInt - Checks if an integer fits into the given bit width. 36template<unsigned N> 37inline bool isInt(int64_t x) { 38 return N >= 64 || (-(INT64_C(1)<<(N-1)) <= x && x < (INT64_C(1)<<(N-1))); 39} 40// Template specializations to get better code for common cases. 41template<> 42inline bool isInt<8>(int64_t x) { 43 return static_cast<int8_t>(x) == x; 44} 45template<> 46inline bool isInt<16>(int64_t x) { 47 return static_cast<int16_t>(x) == x; 48} 49template<> 50inline bool isInt<32>(int64_t x) { 51 return static_cast<int32_t>(x) == x; 52} 53 54/// isShiftedInt<N,S> - Checks if a signed integer is an N bit number shifted 55/// left by S. 56template<unsigned N, unsigned S> 57inline bool isShiftedInt(int64_t x) { 58 return isInt<N+S>(x) && (x % (1<<S) == 0); 59} 60 61/// isUInt - Checks if an unsigned integer fits into the given bit width. 62template<unsigned N> 63inline bool isUInt(uint64_t x) { 64 return N >= 64 || x < (UINT64_C(1)<<N); 65} 66// Template specializations to get better code for common cases. 67template<> 68inline bool isUInt<8>(uint64_t x) { 69 return static_cast<uint8_t>(x) == x; 70} 71template<> 72inline bool isUInt<16>(uint64_t x) { 73 return static_cast<uint16_t>(x) == x; 74} 75template<> 76inline bool isUInt<32>(uint64_t x) { 77 return static_cast<uint32_t>(x) == x; 78} 79 80/// isShiftedUInt<N,S> - Checks if a unsigned integer is an N bit number shifted 81/// left by S. 82template<unsigned N, unsigned S> 83inline bool isShiftedUInt(uint64_t x) { 84 return isUInt<N+S>(x) && (x % (1<<S) == 0); 85} 86 87/// isUIntN - Checks if an unsigned integer fits into the given (dynamic) 88/// bit width. 89inline bool isUIntN(unsigned N, uint64_t x) { 90 return x == (x & (~0ULL >> (64 - N))); 91} 92 93/// isIntN - Checks if an signed integer fits into the given (dynamic) 94/// bit width. 95inline bool isIntN(unsigned N, int64_t x) { 96 return N >= 64 || (-(INT64_C(1)<<(N-1)) <= x && x < (INT64_C(1)<<(N-1))); 97} 98 99/// isMask_32 - This function returns true if the argument is a sequence of ones 100/// starting at the least significant bit with the remainder zero (32 bit 101/// version). Ex. isMask_32(0x0000FFFFU) == true. 102inline bool isMask_32(uint32_t Value) { 103 return Value && ((Value + 1) & Value) == 0; 104} 105 106/// isMask_64 - This function returns true if the argument is a sequence of ones 107/// starting at the least significant bit with the remainder zero (64 bit 108/// version). 109inline bool isMask_64(uint64_t Value) { 110 return Value && ((Value + 1) & Value) == 0; 111} 112 113/// isShiftedMask_32 - This function returns true if the argument contains a 114/// sequence of ones with the remainder zero (32 bit version.) 115/// Ex. isShiftedMask_32(0x0000FF00U) == true. 116inline bool isShiftedMask_32(uint32_t Value) { 117 return isMask_32((Value - 1) | Value); 118} 119 120/// isShiftedMask_64 - This function returns true if the argument contains a 121/// sequence of ones with the remainder zero (64 bit version.) 122inline bool isShiftedMask_64(uint64_t Value) { 123 return isMask_64((Value - 1) | Value); 124} 125 126/// isPowerOf2_32 - This function returns true if the argument is a power of 127/// two > 0. Ex. isPowerOf2_32(0x00100000U) == true (32 bit edition.) 128inline bool isPowerOf2_32(uint32_t Value) { 129 return Value && !(Value & (Value - 1)); 130} 131 132/// isPowerOf2_64 - This function returns true if the argument is a power of two 133/// > 0 (64 bit edition.) 134inline bool isPowerOf2_64(uint64_t Value) { 135 return Value && !(Value & (Value - int64_t(1L))); 136} 137 138/// CountLeadingZeros_32 - this function performs the platform optimal form of 139/// counting the number of zeros from the most significant bit to the first one 140/// bit. Ex. CountLeadingZeros_32(0x00F000FF) == 8. 141/// Returns 32 if the word is zero. 142inline unsigned CountLeadingZeros_32(uint32_t Value) { 143 unsigned Count; // result 144#if __GNUC__ >= 4 145 // PowerPC is defined for __builtin_clz(0) 146#if !defined(__ppc__) && !defined(__ppc64__) 147 if (!Value) return 32; 148#endif 149 Count = __builtin_clz(Value); 150#else 151 if (!Value) return 32; 152 Count = 0; 153 // bisection method for count leading zeros 154 for (unsigned Shift = 32 >> 1; Shift; Shift >>= 1) { 155 uint32_t Tmp = Value >> Shift; 156 if (Tmp) { 157 Value = Tmp; 158 } else { 159 Count |= Shift; 160 } 161 } 162#endif 163 return Count; 164} 165 166/// CountLeadingOnes_32 - this function performs the operation of 167/// counting the number of ones from the most significant bit to the first zero 168/// bit. Ex. CountLeadingOnes_32(0xFF0FFF00) == 8. 169/// Returns 32 if the word is all ones. 170inline unsigned CountLeadingOnes_32(uint32_t Value) { 171 return CountLeadingZeros_32(~Value); 172} 173 174/// CountLeadingZeros_64 - This function performs the platform optimal form 175/// of counting the number of zeros from the most significant bit to the first 176/// one bit (64 bit edition.) 177/// Returns 64 if the word is zero. 178inline unsigned CountLeadingZeros_64(uint64_t Value) { 179 unsigned Count; // result 180#if __GNUC__ >= 4 181 // PowerPC is defined for __builtin_clzll(0) 182#if !defined(__ppc__) && !defined(__ppc64__) 183 if (!Value) return 64; 184#endif 185 Count = __builtin_clzll(Value); 186#else 187 if (sizeof(long) == sizeof(int64_t)) { 188 if (!Value) return 64; 189 Count = 0; 190 // bisection method for count leading zeros 191 for (unsigned Shift = 64 >> 1; Shift; Shift >>= 1) { 192 uint64_t Tmp = Value >> Shift; 193 if (Tmp) { 194 Value = Tmp; 195 } else { 196 Count |= Shift; 197 } 198 } 199 } else { 200 // get hi portion 201 uint32_t Hi = Hi_32(Value); 202 203 // if some bits in hi portion 204 if (Hi) { 205 // leading zeros in hi portion plus all bits in lo portion 206 Count = CountLeadingZeros_32(Hi); 207 } else { 208 // get lo portion 209 uint32_t Lo = Lo_32(Value); 210 // same as 32 bit value 211 Count = CountLeadingZeros_32(Lo)+32; 212 } 213 } 214#endif 215 return Count; 216} 217 218/// CountLeadingOnes_64 - This function performs the operation 219/// of counting the number of ones from the most significant bit to the first 220/// zero bit (64 bit edition.) 221/// Returns 64 if the word is all ones. 222inline unsigned CountLeadingOnes_64(uint64_t Value) { 223 return CountLeadingZeros_64(~Value); 224} 225 226/// CountTrailingZeros_32 - this function performs the platform optimal form of 227/// counting the number of zeros from the least significant bit to the first one 228/// bit. Ex. CountTrailingZeros_32(0xFF00FF00) == 8. 229/// Returns 32 if the word is zero. 230inline unsigned CountTrailingZeros_32(uint32_t Value) { 231#if __GNUC__ >= 4 232 return Value ? __builtin_ctz(Value) : 32; 233#else 234 static const unsigned Mod37BitPosition[] = { 235 32, 0, 1, 26, 2, 23, 27, 0, 3, 16, 24, 30, 28, 11, 0, 13, 236 4, 7, 17, 0, 25, 22, 31, 15, 29, 10, 12, 6, 0, 21, 14, 9, 237 5, 20, 8, 19, 18 238 }; 239 return Mod37BitPosition[(-Value & Value) % 37]; 240#endif 241} 242 243/// CountTrailingOnes_32 - this function performs the operation of 244/// counting the number of ones from the least significant bit to the first zero 245/// bit. Ex. CountTrailingOnes_32(0x00FF00FF) == 8. 246/// Returns 32 if the word is all ones. 247inline unsigned CountTrailingOnes_32(uint32_t Value) { 248 return CountTrailingZeros_32(~Value); 249} 250 251/// CountTrailingZeros_64 - This function performs the platform optimal form 252/// of counting the number of zeros from the least significant bit to the first 253/// one bit (64 bit edition.) 254/// Returns 64 if the word is zero. 255inline unsigned CountTrailingZeros_64(uint64_t Value) { 256#if __GNUC__ >= 4 257 return Value ? __builtin_ctzll(Value) : 64; 258#else 259 static const unsigned Mod67Position[] = { 260 64, 0, 1, 39, 2, 15, 40, 23, 3, 12, 16, 59, 41, 19, 24, 54, 261 4, 64, 13, 10, 17, 62, 60, 28, 42, 30, 20, 51, 25, 44, 55, 262 47, 5, 32, 65, 38, 14, 22, 11, 58, 18, 53, 63, 9, 61, 27, 263 29, 50, 43, 46, 31, 37, 21, 57, 52, 8, 26, 49, 45, 36, 56, 264 7, 48, 35, 6, 34, 33, 0 265 }; 266 return Mod67Position[(-Value & Value) % 67]; 267#endif 268} 269 270/// CountTrailingOnes_64 - This function performs the operation 271/// of counting the number of ones from the least significant bit to the first 272/// zero bit (64 bit edition.) 273/// Returns 64 if the word is all ones. 274inline unsigned CountTrailingOnes_64(uint64_t Value) { 275 return CountTrailingZeros_64(~Value); 276} 277 278/// CountPopulation_32 - this function counts the number of set bits in a value. 279/// Ex. CountPopulation(0xF000F000) = 8 280/// Returns 0 if the word is zero. 281inline unsigned CountPopulation_32(uint32_t Value) { 282#if __GNUC__ >= 4 283 return __builtin_popcount(Value); 284#else 285 uint32_t v = Value - ((Value >> 1) & 0x55555555); 286 v = (v & 0x33333333) + ((v >> 2) & 0x33333333); 287 return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; 288#endif 289} 290 291/// CountPopulation_64 - this function counts the number of set bits in a value, 292/// (64 bit edition.) 293inline unsigned CountPopulation_64(uint64_t Value) { 294#if __GNUC__ >= 4 295 return __builtin_popcountll(Value); 296#else 297 uint64_t v = Value - ((Value >> 1) & 0x5555555555555555ULL); 298 v = (v & 0x3333333333333333ULL) + ((v >> 2) & 0x3333333333333333ULL); 299 v = (v + (v >> 4)) & 0x0F0F0F0F0F0F0F0FULL; 300 return unsigned((uint64_t)(v * 0x0101010101010101ULL) >> 56); 301#endif 302} 303 304/// Log2_32 - This function returns the floor log base 2 of the specified value, 305/// -1 if the value is zero. (32 bit edition.) 306/// Ex. Log2_32(32) == 5, Log2_32(1) == 0, Log2_32(0) == -1, Log2_32(6) == 2 307inline unsigned Log2_32(uint32_t Value) { 308 return 31 - CountLeadingZeros_32(Value); 309} 310 311/// Log2_64 - This function returns the floor log base 2 of the specified value, 312/// -1 if the value is zero. (64 bit edition.) 313inline unsigned Log2_64(uint64_t Value) { 314 return 63 - CountLeadingZeros_64(Value); 315} 316 317/// Log2_32_Ceil - This function returns the ceil log base 2 of the specified 318/// value, 32 if the value is zero. (32 bit edition). 319/// Ex. Log2_32_Ceil(32) == 5, Log2_32_Ceil(1) == 0, Log2_32_Ceil(6) == 3 320inline unsigned Log2_32_Ceil(uint32_t Value) { 321 return 32-CountLeadingZeros_32(Value-1); 322} 323 324/// Log2_64_Ceil - This function returns the ceil log base 2 of the specified 325/// value, 64 if the value is zero. (64 bit edition.) 326inline unsigned Log2_64_Ceil(uint64_t Value) { 327 return 64-CountLeadingZeros_64(Value-1); 328} 329 330/// GreatestCommonDivisor64 - Return the greatest common divisor of the two 331/// values using Euclid's algorithm. 332inline uint64_t GreatestCommonDivisor64(uint64_t A, uint64_t B) { 333 while (B) { 334 uint64_t T = B; 335 B = A % B; 336 A = T; 337 } 338 return A; 339} 340 341/// BitsToDouble - This function takes a 64-bit integer and returns the bit 342/// equivalent double. 343inline double BitsToDouble(uint64_t Bits) { 344 union { 345 uint64_t L; 346 double D; 347 } T; 348 T.L = Bits; 349 return T.D; 350} 351 352/// BitsToFloat - This function takes a 32-bit integer and returns the bit 353/// equivalent float. 354inline float BitsToFloat(uint32_t Bits) { 355 union { 356 uint32_t I; 357 float F; 358 } T; 359 T.I = Bits; 360 return T.F; 361} 362 363/// DoubleToBits - This function takes a double and returns the bit 364/// equivalent 64-bit integer. Note that copying doubles around 365/// changes the bits of NaNs on some hosts, notably x86, so this 366/// routine cannot be used if these bits are needed. 367inline uint64_t DoubleToBits(double Double) { 368 union { 369 uint64_t L; 370 double D; 371 } T; 372 T.D = Double; 373 return T.L; 374} 375 376/// FloatToBits - This function takes a float and returns the bit 377/// equivalent 32-bit integer. Note that copying floats around 378/// changes the bits of NaNs on some hosts, notably x86, so this 379/// routine cannot be used if these bits are needed. 380inline uint32_t FloatToBits(float Float) { 381 union { 382 uint32_t I; 383 float F; 384 } T; 385 T.F = Float; 386 return T.I; 387} 388 389/// Platform-independent wrappers for the C99 isnan() function. 390int IsNAN(float f); 391int IsNAN(double d); 392 393/// Platform-independent wrappers for the C99 isinf() function. 394int IsInf(float f); 395int IsInf(double d); 396 397/// MinAlign - A and B are either alignments or offsets. Return the minimum 398/// alignment that may be assumed after adding the two together. 399inline uint64_t MinAlign(uint64_t A, uint64_t B) { 400 // The largest power of 2 that divides both A and B. 401 return (A | B) & -(A | B); 402} 403 404/// NextPowerOf2 - Returns the next power of two (in 64-bits) 405/// that is strictly greater than A. Returns zero on overflow. 406inline uint64_t NextPowerOf2(uint64_t A) { 407 A |= (A >> 1); 408 A |= (A >> 2); 409 A |= (A >> 4); 410 A |= (A >> 8); 411 A |= (A >> 16); 412 A |= (A >> 32); 413 return A + 1; 414} 415 416/// NextPowerOf2 - Returns the next power of two (in 32-bits) 417/// that is strictly greater than A. Returns zero on overflow. 418inline uint32_t NextPowerOf2(uint32_t A) { 419 A |= (A >> 1); 420 A |= (A >> 2); 421 A |= (A >> 4); 422 A |= (A >> 8); 423 A |= (A >> 16); 424 return A + 1; 425} 426 427/// Returns the next integer (mod 2**64) that is greater than or equal to 428/// \p Value and is a multiple of \p Align. \p Align must be non-zero. 429/// 430/// Examples: 431/// \code 432/// RoundUpToAlignment(5, 8) = 8 433/// RoundUpToAlignment(17, 8) = 24 434/// RoundUpToAlignment(~0LL, 8) = 0 435/// \endcode 436inline uint64_t RoundUpToAlignment(uint64_t Value, uint64_t Align) { 437 return ((Value + Align - 1) / Align) * Align; 438} 439 440/// Returns the offset to the next integer (mod 2**64) that is greater than 441/// or equal to \p Value and is a multiple of \p Align. \p Align must be 442/// non-zero. 443inline uint64_t OffsetToAlignment(uint64_t Value, uint64_t Align) { 444 return RoundUpToAlignment(Value, Align) - Value; 445} 446 447/// abs64 - absolute value of a 64-bit int. Not all environments support 448/// "abs" on whatever their name for the 64-bit int type is. The absolute 449/// value of the largest negative number is undefined, as with "abs". 450inline int64_t abs64(int64_t x) { 451 return (x < 0) ? -x : x; 452} 453 454/// SignExtend32 - Sign extend B-bit number x to 32-bit int. 455/// Usage int32_t r = SignExtend32<5>(x); 456template <unsigned B> inline int32_t SignExtend32(uint32_t x) { 457 return int32_t(x << (32 - B)) >> (32 - B); 458} 459 460/// \brief Sign extend number in the bottom B bits of X to a 32-bit int. 461/// Requires 0 < B <= 32. 462inline int32_t SignExtend32(uint32_t X, unsigned B) { 463 return int32_t(X << (32 - B)) >> (32 - B); 464} 465 466/// SignExtend64 - Sign extend B-bit number x to 64-bit int. 467/// Usage int64_t r = SignExtend64<5>(x); 468template <unsigned B> inline int64_t SignExtend64(uint64_t x) { 469 return int64_t(x << (64 - B)) >> (64 - B); 470} 471 472/// \brief Sign extend number in the bottom B bits of X to a 64-bit int. 473/// Requires 0 < B <= 64. 474inline int64_t SignExtend64(uint64_t X, unsigned B) { 475 return int64_t(X << (64 - B)) >> (64 - B); 476} 477 478} // End llvm namespace 479 480#endif 481