LLVM API Documentation
00001 //===-- llvm/Support/MathExtras.h - Useful math functions -------*- C++ -*-===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file contains some functions that are useful for math stuff. 00011 // 00012 //===----------------------------------------------------------------------===// 00013 00014 #ifndef LLVM_SUPPORT_MATHEXTRAS_H 00015 #define LLVM_SUPPORT_MATHEXTRAS_H 00016 00017 #include "llvm/Support/DataTypes.h" 00018 00019 namespace llvm { 00020 00021 // NOTE: The following support functions use the _32/_64 extensions instead of 00022 // type overloading so that signed and unsigned integers can be used without 00023 // ambiguity. 00024 00025 /// Hi_32 - This function returns the high 32 bits of a 64 bit value. 00026 inline uint32_t Hi_32(uint64_t Value) { 00027 return static_cast<uint32_t>(Value >> 32); 00028 } 00029 00030 /// Lo_32 - This function returns the low 32 bits of a 64 bit value. 00031 inline uint32_t Lo_32(uint64_t Value) { 00032 return static_cast<uint32_t>(Value); 00033 } 00034 00035 /// is?Type - these functions produce optimal testing for integer data types. 00036 inline bool isInt8 (int64_t Value) { 00037 return static_cast<int8_t>(Value) == Value; 00038 } 00039 inline bool isUInt8 (int64_t Value) { 00040 return static_cast<uint8_t>(Value) == Value; 00041 } 00042 inline bool isInt16 (int64_t Value) { 00043 return static_cast<int16_t>(Value) == Value; 00044 } 00045 inline bool isUInt16(int64_t Value) { 00046 return static_cast<uint16_t>(Value) == Value; 00047 } 00048 inline bool isInt32 (int64_t Value) { 00049 return static_cast<int32_t>(Value) == Value; 00050 } 00051 inline bool isUInt32(int64_t Value) { 00052 return static_cast<uint32_t>(Value) == Value; 00053 } 00054 00055 template<unsigned N> 00056 inline bool isInt(int64_t x) { 00057 return N >= 64 || (-(INT64_C(1)<<(N-1)) <= x && x < (INT64_C(1)<<(N-1))); 00058 } 00059 00060 template<unsigned N> 00061 inline bool isUint(uint64_t x) { 00062 return N >= 64 || x < (UINT64_C(1)<<N); 00063 } 00064 00065 /// isMask_32 - This function returns true if the argument is a sequence of ones 00066 /// starting at the least significant bit with the remainder zero (32 bit 00067 /// version). Ex. isMask_32(0x0000FFFFU) == true. 00068 inline bool isMask_32(uint32_t Value) { 00069 return Value && ((Value + 1) & Value) == 0; 00070 } 00071 00072 /// isMask_64 - This function returns true if the argument is a sequence of ones 00073 /// starting at the least significant bit with the remainder zero (64 bit 00074 /// version). 00075 inline bool isMask_64(uint64_t Value) { 00076 return Value && ((Value + 1) & Value) == 0; 00077 } 00078 00079 /// isShiftedMask_32 - This function returns true if the argument contains a 00080 /// sequence of ones with the remainder zero (32 bit version.) 00081 /// Ex. isShiftedMask_32(0x0000FF00U) == true. 00082 inline bool isShiftedMask_32(uint32_t Value) { 00083 return isMask_32((Value - 1) | Value); 00084 } 00085 00086 /// isShiftedMask_64 - This function returns true if the argument contains a 00087 /// sequence of ones with the remainder zero (64 bit version.) 00088 inline bool isShiftedMask_64(uint64_t Value) { 00089 return isMask_64((Value - 1) | Value); 00090 } 00091 00092 /// isPowerOf2_32 - This function returns true if the argument is a power of 00093 /// two > 0. Ex. isPowerOf2_32(0x00100000U) == true (32 bit edition.) 00094 inline bool isPowerOf2_32(uint32_t Value) { 00095 return Value && !(Value & (Value - 1)); 00096 } 00097 00098 /// isPowerOf2_64 - This function returns true if the argument is a power of two 00099 /// > 0 (64 bit edition.) 00100 inline bool isPowerOf2_64(uint64_t Value) { 00101 return Value && !(Value & (Value - int64_t(1L))); 00102 } 00103 00104 /// ByteSwap_16 - This function returns a byte-swapped representation of the 00105 /// 16-bit argument, Value. 00106 inline uint16_t ByteSwap_16(uint16_t Value) { 00107 #if defined(_MSC_VER) && !defined(_DEBUG) 00108 // The DLL version of the runtime lacks these functions (bug!?), but in a 00109 // release build they're replaced with BSWAP instructions anyway. 00110 return _byteswap_ushort(Value); 00111 #else 00112 uint16_t Hi = Value << 8; 00113 uint16_t Lo = Value >> 8; 00114 return Hi | Lo; 00115 #endif 00116 } 00117 00118 /// ByteSwap_32 - This function returns a byte-swapped representation of the 00119 /// 32-bit argument, Value. 00120 inline uint32_t ByteSwap_32(uint32_t Value) { 00121 #if (__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 3)) && !defined(__ICC) 00122 return __builtin_bswap32(Value); 00123 #elif defined(_MSC_VER) && !defined(_DEBUG) 00124 return _byteswap_ulong(Value); 00125 #else 00126 uint32_t Byte0 = Value & 0x000000FF; 00127 uint32_t Byte1 = Value & 0x0000FF00; 00128 uint32_t Byte2 = Value & 0x00FF0000; 00129 uint32_t Byte3 = Value & 0xFF000000; 00130 return (Byte0 << 24) | (Byte1 << 8) | (Byte2 >> 8) | (Byte3 >> 24); 00131 #endif 00132 } 00133 00134 /// ByteSwap_64 - This function returns a byte-swapped representation of the 00135 /// 64-bit argument, Value. 00136 inline uint64_t ByteSwap_64(uint64_t Value) { 00137 #if (__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 3)) && !defined(__ICC) 00138 return __builtin_bswap64(Value); 00139 #elif defined(_MSC_VER) && !defined(_DEBUG) 00140 return _byteswap_uint64(Value); 00141 #else 00142 uint64_t Hi = ByteSwap_32(uint32_t(Value)); 00143 uint32_t Lo = ByteSwap_32(uint32_t(Value >> 32)); 00144 return (Hi << 32) | Lo; 00145 #endif 00146 } 00147 00148 /// CountLeadingZeros_32 - this function performs the platform optimal form of 00149 /// counting the number of zeros from the most significant bit to the first one 00150 /// bit. Ex. CountLeadingZeros_32(0x00F000FF) == 8. 00151 /// Returns 32 if the word is zero. 00152 inline unsigned CountLeadingZeros_32(uint32_t Value) { 00153 unsigned Count; // result 00154 #if __GNUC__ >= 4 00155 // PowerPC is defined for __builtin_clz(0) 00156 #if !defined(__ppc__) && !defined(__ppc64__) 00157 if (!Value) return 32; 00158 #endif 00159 Count = __builtin_clz(Value); 00160 #else 00161 if (!Value) return 32; 00162 Count = 0; 00163 // bisecton method for count leading zeros 00164 for (unsigned Shift = 32 >> 1; Shift; Shift >>= 1) { 00165 uint32_t Tmp = Value >> Shift; 00166 if (Tmp) { 00167 Value = Tmp; 00168 } else { 00169 Count |= Shift; 00170 } 00171 } 00172 #endif 00173 return Count; 00174 } 00175 00176 /// CountLeadingOnes_32 - this function performs the operation of 00177 /// counting the number of ones from the most significant bit to the first zero 00178 /// bit. Ex. CountLeadingOnes_32(0xFF0FFF00) == 8. 00179 /// Returns 32 if the word is all ones. 00180 inline unsigned CountLeadingOnes_32(uint32_t Value) { 00181 return CountLeadingZeros_32(~Value); 00182 } 00183 00184 /// CountLeadingZeros_64 - This function performs the platform optimal form 00185 /// of counting the number of zeros from the most significant bit to the first 00186 /// one bit (64 bit edition.) 00187 /// Returns 64 if the word is zero. 00188 inline unsigned CountLeadingZeros_64(uint64_t Value) { 00189 unsigned Count; // result 00190 #if __GNUC__ >= 4 00191 // PowerPC is defined for __builtin_clzll(0) 00192 #if !defined(__ppc__) && !defined(__ppc64__) 00193 if (!Value) return 64; 00194 #endif 00195 Count = __builtin_clzll(Value); 00196 #else 00197 if (sizeof(long) == sizeof(int64_t)) { 00198 if (!Value) return 64; 00199 Count = 0; 00200 // bisecton method for count leading zeros 00201 for (unsigned Shift = 64 >> 1; Shift; Shift >>= 1) { 00202 uint64_t Tmp = Value >> Shift; 00203 if (Tmp) { 00204 Value = Tmp; 00205 } else { 00206 Count |= Shift; 00207 } 00208 } 00209 } else { 00210 // get hi portion 00211 uint32_t Hi = Hi_32(Value); 00212 00213 // if some bits in hi portion 00214 if (Hi) { 00215 // leading zeros in hi portion plus all bits in lo portion 00216 Count = CountLeadingZeros_32(Hi); 00217 } else { 00218 // get lo portion 00219 uint32_t Lo = Lo_32(Value); 00220 // same as 32 bit value 00221 Count = CountLeadingZeros_32(Lo)+32; 00222 } 00223 } 00224 #endif 00225 return Count; 00226 } 00227 00228 /// CountLeadingOnes_64 - This function performs the operation 00229 /// of counting the number of ones from the most significant bit to the first 00230 /// zero bit (64 bit edition.) 00231 /// Returns 64 if the word is all ones. 00232 inline unsigned CountLeadingOnes_64(uint64_t Value) { 00233 return CountLeadingZeros_64(~Value); 00234 } 00235 00236 /// CountTrailingZeros_32 - this function performs the platform optimal form of 00237 /// counting the number of zeros from the least significant bit to the first one 00238 /// bit. Ex. CountTrailingZeros_32(0xFF00FF00) == 8. 00239 /// Returns 32 if the word is zero. 00240 inline unsigned CountTrailingZeros_32(uint32_t Value) { 00241 #if __GNUC__ >= 4 00242 return Value ? __builtin_ctz(Value) : 32; 00243 #else 00244 static const unsigned Mod37BitPosition[] = { 00245 32, 0, 1, 26, 2, 23, 27, 0, 3, 16, 24, 30, 28, 11, 0, 13, 00246 4, 7, 17, 0, 25, 22, 31, 15, 29, 10, 12, 6, 0, 21, 14, 9, 00247 5, 20, 8, 19, 18 00248 }; 00249 return Mod37BitPosition[(-Value & Value) % 37]; 00250 #endif 00251 } 00252 00253 /// CountTrailingOnes_32 - this function performs the operation of 00254 /// counting the number of ones from the least significant bit to the first zero 00255 /// bit. Ex. CountTrailingOnes_32(0x00FF00FF) == 8. 00256 /// Returns 32 if the word is all ones. 00257 inline unsigned CountTrailingOnes_32(uint32_t Value) { 00258 return CountTrailingZeros_32(~Value); 00259 } 00260 00261 /// CountTrailingZeros_64 - This function performs the platform optimal form 00262 /// of counting the number of zeros from the least significant bit to the first 00263 /// one bit (64 bit edition.) 00264 /// Returns 64 if the word is zero. 00265 inline unsigned CountTrailingZeros_64(uint64_t Value) { 00266 #if __GNUC__ >= 4 00267 return Value ? __builtin_ctzll(Value) : 64; 00268 #else 00269 static const unsigned Mod67Position[] = { 00270 64, 0, 1, 39, 2, 15, 40, 23, 3, 12, 16, 59, 41, 19, 24, 54, 00271 4, 64, 13, 10, 17, 62, 60, 28, 42, 30, 20, 51, 25, 44, 55, 00272 47, 5, 32, 65, 38, 14, 22, 11, 58, 18, 53, 63, 9, 61, 27, 00273 29, 50, 43, 46, 31, 37, 21, 57, 52, 8, 26, 49, 45, 36, 56, 00274 7, 48, 35, 6, 34, 33, 0 00275 }; 00276 return Mod67Position[(-Value & Value) % 67]; 00277 #endif 00278 } 00279 00280 /// CountTrailingOnes_64 - This function performs the operation 00281 /// of counting the number of ones from the least significant bit to the first 00282 /// zero bit (64 bit edition.) 00283 /// Returns 64 if the word is all ones. 00284 inline unsigned CountTrailingOnes_64(uint64_t Value) { 00285 return CountTrailingZeros_64(~Value); 00286 } 00287 00288 /// CountPopulation_32 - this function counts the number of set bits in a value. 00289 /// Ex. CountPopulation(0xF000F000) = 8 00290 /// Returns 0 if the word is zero. 00291 inline unsigned CountPopulation_32(uint32_t Value) { 00292 #if __GNUC__ >= 4 00293 return __builtin_popcount(Value); 00294 #else 00295 uint32_t v = Value - ((Value >> 1) & 0x55555555); 00296 v = (v & 0x33333333) + ((v >> 2) & 0x33333333); 00297 return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; 00298 #endif 00299 } 00300 00301 /// CountPopulation_64 - this function counts the number of set bits in a value, 00302 /// (64 bit edition.) 00303 inline unsigned CountPopulation_64(uint64_t Value) { 00304 #if __GNUC__ >= 4 00305 return __builtin_popcountll(Value); 00306 #else 00307 uint64_t v = Value - ((Value >> 1) & 0x5555555555555555ULL); 00308 v = (v & 0x3333333333333333ULL) + ((v >> 2) & 0x3333333333333333ULL); 00309 v = (v + (v >> 4)) & 0x0F0F0F0F0F0F0F0FULL; 00310 return unsigned((uint64_t)(v * 0x0101010101010101ULL) >> 56); 00311 #endif 00312 } 00313 00314 /// Log2_32 - This function returns the floor log base 2 of the specified value, 00315 /// -1 if the value is zero. (32 bit edition.) 00316 /// Ex. Log2_32(32) == 5, Log2_32(1) == 0, Log2_32(0) == -1, Log2_32(6) == 2 00317 inline unsigned Log2_32(uint32_t Value) { 00318 return 31 - CountLeadingZeros_32(Value); 00319 } 00320 00321 /// Log2_64 - This function returns the floor log base 2 of the specified value, 00322 /// -1 if the value is zero. (64 bit edition.) 00323 inline unsigned Log2_64(uint64_t Value) { 00324 return 63 - CountLeadingZeros_64(Value); 00325 } 00326 00327 /// Log2_32_Ceil - This function returns the ceil log base 2 of the specified 00328 /// value, 32 if the value is zero. (32 bit edition). 00329 /// Ex. Log2_32_Ceil(32) == 5, Log2_32_Ceil(1) == 0, Log2_32_Ceil(6) == 3 00330 inline unsigned Log2_32_Ceil(uint32_t Value) { 00331 return 32-CountLeadingZeros_32(Value-1); 00332 } 00333 00334 /// Log2_64_Ceil - This function returns the ceil log base 2 of the specified 00335 /// value, 64 if the value is zero. (64 bit edition.) 00336 inline unsigned Log2_64_Ceil(uint64_t Value) { 00337 return 64-CountLeadingZeros_64(Value-1); 00338 } 00339 00340 /// GreatestCommonDivisor64 - Return the greatest common divisor of the two 00341 /// values using Euclid's algorithm. 00342 inline uint64_t GreatestCommonDivisor64(uint64_t A, uint64_t B) { 00343 while (B) { 00344 uint64_t T = B; 00345 B = A % B; 00346 A = T; 00347 } 00348 return A; 00349 } 00350 00351 /// BitsToDouble - This function takes a 64-bit integer and returns the bit 00352 /// equivalent double. 00353 inline double BitsToDouble(uint64_t Bits) { 00354 union { 00355 uint64_t L; 00356 double D; 00357 } T; 00358 T.L = Bits; 00359 return T.D; 00360 } 00361 00362 /// BitsToFloat - This function takes a 32-bit integer and returns the bit 00363 /// equivalent float. 00364 inline float BitsToFloat(uint32_t Bits) { 00365 union { 00366 uint32_t I; 00367 float F; 00368 } T; 00369 T.I = Bits; 00370 return T.F; 00371 } 00372 00373 /// DoubleToBits - This function takes a double and returns the bit 00374 /// equivalent 64-bit integer. Note that copying doubles around 00375 /// changes the bits of NaNs on some hosts, notably x86, so this 00376 /// routine cannot be used if these bits are needed. 00377 inline uint64_t DoubleToBits(double Double) { 00378 union { 00379 uint64_t L; 00380 double D; 00381 } T; 00382 T.D = Double; 00383 return T.L; 00384 } 00385 00386 /// FloatToBits - This function takes a float and returns the bit 00387 /// equivalent 32-bit integer. Note that copying floats around 00388 /// changes the bits of NaNs on some hosts, notably x86, so this 00389 /// routine cannot be used if these bits are needed. 00390 inline uint32_t FloatToBits(float Float) { 00391 union { 00392 uint32_t I; 00393 float F; 00394 } T; 00395 T.F = Float; 00396 return T.I; 00397 } 00398 00399 /// Platform-independent wrappers for the C99 isnan() function. 00400 int IsNAN(float f); 00401 int IsNAN(double d); 00402 00403 /// Platform-independent wrappers for the C99 isinf() function. 00404 int IsInf(float f); 00405 int IsInf(double d); 00406 00407 /// MinAlign - A and B are either alignments or offsets. Return the minimum 00408 /// alignment that may be assumed after adding the two together. 00409 static inline uint64_t MinAlign(uint64_t A, uint64_t B) { 00410 // The largest power of 2 that divides both A and B. 00411 return (A | B) & -(A | B); 00412 } 00413 00414 /// NextPowerOf2 - Returns the next power of two (in 64-bits) 00415 /// that is strictly greater than A. Returns zero on overflow. 00416 static inline uint64_t NextPowerOf2(uint64_t A) { 00417 A |= (A >> 1); 00418 A |= (A >> 2); 00419 A |= (A >> 4); 00420 A |= (A >> 8); 00421 A |= (A >> 16); 00422 A |= (A >> 32); 00423 return A + 1; 00424 } 00425 00426 /// RoundUpToAlignment - Returns the next integer (mod 2**64) that is 00427 /// greater than or equal to \arg Value and is a multiple of \arg 00428 /// Align. Align must be non-zero. 00429 /// 00430 /// Examples: 00431 /// RoundUpToAlignment(5, 8) = 8 00432 /// RoundUpToAlignment(17, 8) = 24 00433 /// RoundUpToAlignment(~0LL, 8) = 0 00434 inline uint64_t RoundUpToAlignment(uint64_t Value, uint64_t Align) { 00435 return ((Value + Align - 1) / Align) * Align; 00436 } 00437 00438 /// abs64 - absolute value of a 64-bit int. Not all environments support 00439 /// "abs" on whatever their name for the 64-bit int type is. The absolute 00440 /// value of the largest negative number is undefined, as with "abs". 00441 inline int64_t abs64(int64_t x) { 00442 return (x < 0) ? -x : x; 00443 } 00444 00445 } // End llvm namespace 00446 00447 #endif