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