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