MathExtras.h revision f17a25c88b892d30c2b41ba7ecdfbdfb2b4be9cc
1//===-- llvm/Support/MathExtras.h - Useful math functions -------*- C++ -*-===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file was developed by the LLVM research group and is distributed under 6// the University of Illinois Open Source 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/Support/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 55/// isMask_32 - This function returns true if the argument is a sequence of ones 56/// starting at the least significant bit with the remainder zero (32 bit 57/// version). Ex. isMask_32(0x0000FFFFU) == true. 58inline bool isMask_32(uint32_t Value) { 59 return Value && ((Value + 1) & Value) == 0; 60} 61 62/// isMask_64 - This function returns true if the argument is a sequence of ones 63/// starting at the least significant bit with the remainder zero (64 bit 64/// version). 65inline bool isMask_64(uint64_t Value) { 66 return Value && ((Value + 1) & Value) == 0; 67} 68 69/// isShiftedMask_32 - This function returns true if the argument contains a 70/// sequence of ones with the remainder zero (32 bit version.) 71/// Ex. isShiftedMask_32(0x0000FF00U) == true. 72inline bool isShiftedMask_32(uint32_t Value) { 73 return isMask_32((Value - 1) | Value); 74} 75 76/// isShiftedMask_64 - This function returns true if the argument contains a 77/// sequence of ones with the remainder zero (64 bit version.) 78inline bool isShiftedMask_64(uint64_t Value) { 79 return isMask_64((Value - 1) | Value); 80} 81 82/// isPowerOf2_32 - This function returns true if the argument is a power of 83/// two > 0. Ex. isPowerOf2_32(0x00100000U) == true (32 bit edition.) 84inline bool isPowerOf2_32(uint32_t Value) { 85 return Value && !(Value & (Value - 1)); 86} 87 88/// isPowerOf2_64 - This function returns true if the argument is a power of two 89/// > 0 (64 bit edition.) 90inline bool isPowerOf2_64(uint64_t Value) { 91 return Value && !(Value & (Value - int64_t(1L))); 92} 93 94/// ByteSwap_16 - This function returns a byte-swapped representation of the 95/// 16-bit argument, Value. 96inline uint16_t ByteSwap_16(uint16_t Value) { 97#if defined(_MSC_VER) && !defined(_DEBUG) 98 // The DLL version of the runtime lacks these functions (bug!?), but in a 99 // release build they're replaced with BSWAP instructions anyway. 100 return _byteswap_ushort(Value); 101#else 102 uint16_t Hi = Value << 8; 103 uint16_t Lo = Value >> 8; 104 return Hi | Lo; 105#endif 106} 107 108/// ByteSwap_32 - This function returns a byte-swapped representation of the 109/// 32-bit argument, Value. 110inline uint32_t ByteSwap_32(uint32_t Value) { 111#if __GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 3) 112 return __builtin_bswap32(Value); 113#elif defined(_MSC_VER) && !defined(_DEBUG) 114 return _byteswap_ulong(Value); 115#else 116 uint32_t Byte0 = Value & 0x000000FF; 117 uint32_t Byte1 = Value & 0x0000FF00; 118 uint32_t Byte2 = Value & 0x00FF0000; 119 uint32_t Byte3 = Value & 0xFF000000; 120 return (Byte0 << 24) | (Byte1 << 8) | (Byte2 >> 8) | (Byte3 >> 24); 121#endif 122} 123 124/// ByteSwap_64 - This function returns a byte-swapped representation of the 125/// 64-bit argument, Value. 126inline uint64_t ByteSwap_64(uint64_t Value) { 127#if __GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 3) 128 return __builtin_bswap64(Value); 129#elif defined(_MSC_VER) && !defined(_DEBUG) 130 return _byteswap_uint64(Value); 131#else 132 uint64_t Hi = ByteSwap_32(uint32_t(Value)); 133 uint32_t Lo = ByteSwap_32(uint32_t(Value >> 32)); 134 return (Hi << 32) | Lo; 135#endif 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 // bisecton 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/// CountLeadingZeros_64 - This function performs the platform optimal form 167/// of counting the number of zeros from the most significant bit to the first 168/// one bit (64 bit edition.) 169/// Returns 64 if the word is zero. 170inline unsigned CountLeadingZeros_64(uint64_t Value) { 171 unsigned Count; // result 172#if __GNUC__ >= 4 173 // PowerPC is defined for __builtin_clzll(0) 174#if !defined(__ppc__) && !defined(__ppc64__) 175 if (!Value) return 64; 176#endif 177 Count = __builtin_clzll(Value); 178#else 179 if (sizeof(long) == sizeof(int64_t)) { 180 if (!Value) return 64; 181 Count = 0; 182 // bisecton method for count leading zeros 183 for (unsigned Shift = 64 >> 1; Shift; Shift >>= 1) { 184 uint64_t Tmp = Value >> Shift; 185 if (Tmp) { 186 Value = Tmp; 187 } else { 188 Count |= Shift; 189 } 190 } 191 } else { 192 // get hi portion 193 uint32_t Hi = Hi_32(Value); 194 195 // if some bits in hi portion 196 if (Hi) { 197 // leading zeros in hi portion plus all bits in lo portion 198 Count = CountLeadingZeros_32(Hi); 199 } else { 200 // get lo portion 201 uint32_t Lo = Lo_32(Value); 202 // same as 32 bit value 203 Count = CountLeadingZeros_32(Lo)+32; 204 } 205 } 206#endif 207 return Count; 208} 209 210/// CountTrailingZeros_32 - this function performs the platform optimal form of 211/// counting the number of zeros from the least significant bit to the first one 212/// bit. Ex. CountTrailingZeros_32(0xFF00FF00) == 8. 213/// Returns 32 if the word is zero. 214inline unsigned CountTrailingZeros_32(uint32_t Value) { 215#if __GNUC__ >= 4 216 return Value ? __builtin_ctz(Value) : 32; 217#else 218 static const unsigned Mod37BitPosition[] = { 219 32, 0, 1, 26, 2, 23, 27, 0, 3, 16, 24, 30, 28, 11, 0, 13, 220 4, 7, 17, 0, 25, 22, 31, 15, 29, 10, 12, 6, 0, 21, 14, 9, 221 5, 20, 8, 19, 18 222 }; 223 return Mod37BitPosition[(-Value & Value) % 37]; 224#endif 225} 226 227/// CountTrailingZeros_64 - This function performs the platform optimal form 228/// of counting the number of zeros from the least significant bit to the first 229/// one bit (64 bit edition.) 230/// Returns 64 if the word is zero. 231inline unsigned CountTrailingZeros_64(uint64_t Value) { 232#if __GNUC__ >= 4 233 return Value ? __builtin_ctzll(Value) : 64; 234#else 235 static const unsigned Mod67Position[] = { 236 64, 0, 1, 39, 2, 15, 40, 23, 3, 12, 16, 59, 41, 19, 24, 54, 237 4, 64, 13, 10, 17, 62, 60, 28, 42, 30, 20, 51, 25, 44, 55, 238 47, 5, 32, 65, 38, 14, 22, 11, 58, 18, 53, 63, 9, 61, 27, 239 29, 50, 43, 46, 31, 37, 21, 57, 52, 8, 26, 49, 45, 36, 56, 240 7, 48, 35, 6, 34, 33, 0 241 }; 242 return Mod67Position[(-Value & Value) % 67]; 243#endif 244} 245 246/// CountPopulation_32 - this function counts the number of set bits in a value. 247/// Ex. CountPopulation(0xF000F000) = 8 248/// Returns 0 if the word is zero. 249inline unsigned CountPopulation_32(uint32_t Value) { 250#if __GNUC__ >= 4 251 return __builtin_popcount(Value); 252#else 253 uint32_t v = Value - ((Value >> 1) & 0x55555555); 254 v = (v & 0x33333333) + ((v >> 2) & 0x33333333); 255 return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; 256#endif 257} 258 259/// CountPopulation_64 - this function counts the number of set bits in a value, 260/// (64 bit edition.) 261inline unsigned CountPopulation_64(uint64_t Value) { 262#if __GNUC__ >= 4 263 return __builtin_popcountll(Value); 264#else 265 uint64_t v = Value - ((Value >> 1) & 0x5555555555555555ULL); 266 v = (v & 0x3333333333333333ULL) + ((v >> 2) & 0x3333333333333333ULL); 267 v = (v + (v >> 4)) & 0x0F0F0F0F0F0F0F0FULL; 268 return unsigned((uint64_t)(v * 0x0101010101010101ULL) >> 56); 269#endif 270} 271 272/// Log2_32 - This function returns the floor log base 2 of the specified value, 273/// -1 if the value is zero. (32 bit edition.) 274/// Ex. Log2_32(32) == 5, Log2_32(1) == 0, Log2_32(0) == -1, Log2_32(6) == 2 275inline unsigned Log2_32(uint32_t Value) { 276 return 31 - CountLeadingZeros_32(Value); 277} 278 279/// Log2_64 - This function returns the floor log base 2 of the specified value, 280/// -1 if the value is zero. (64 bit edition.) 281inline unsigned Log2_64(uint64_t Value) { 282 return 63 - CountLeadingZeros_64(Value); 283} 284 285/// Log2_32_Ceil - This function returns the ceil log base 2 of the specified 286/// value, 32 if the value is zero. (32 bit edition). 287/// Ex. Log2_32_Ceil(32) == 5, Log2_32_Ceil(1) == 0, Log2_32_Ceil(6) == 3 288inline unsigned Log2_32_Ceil(uint32_t Value) { 289 return 32-CountLeadingZeros_32(Value-1); 290} 291 292/// Log2_64 - This function returns the ceil log base 2 of the specified value, 293/// 64 if the value is zero. (64 bit edition.) 294inline unsigned Log2_64_Ceil(uint64_t Value) { 295 return 64-CountLeadingZeros_64(Value-1); 296} 297 298/// GreatestCommonDivisor64 - Return the greatest common divisor of the two 299/// values using Euclid's algorithm. 300inline uint64_t GreatestCommonDivisor64(uint64_t A, uint64_t B) { 301 while (B) { 302 uint64_t T = B; 303 B = A % B; 304 A = T; 305 } 306 return A; 307} 308 309/// BitsToDouble - This function takes a 64-bit integer and returns the bit 310/// equivalent double. 311inline double BitsToDouble(uint64_t Bits) { 312 union { 313 uint64_t L; 314 double D; 315 } T; 316 T.L = Bits; 317 return T.D; 318} 319 320/// BitsToFloat - This function takes a 32-bit integer and returns the bit 321/// equivalent float. 322inline float BitsToFloat(uint32_t Bits) { 323 union { 324 uint32_t I; 325 float F; 326 } T; 327 T.I = Bits; 328 return T.F; 329} 330 331/// DoubleToBits - This function takes a double and returns the bit 332/// equivalent 64-bit integer. 333inline uint64_t DoubleToBits(double Double) { 334 union { 335 uint64_t L; 336 double D; 337 } T; 338 T.D = Double; 339 return T.L; 340} 341 342/// FloatToBits - This function takes a float and returns the bit 343/// equivalent 32-bit integer. 344inline uint32_t FloatToBits(float Float) { 345 union { 346 uint32_t I; 347 float F; 348 } T; 349 T.F = Float; 350 return T.I; 351} 352 353/// Platform-independent wrappers for the C99 isnan() function. 354int IsNAN(float f); 355int IsNAN(double d); 356 357/// Platform-independent wrappers for the C99 isinf() function. 358int IsInf(float f); 359int IsInf(double d); 360 361} // End llvm namespace 362 363#endif 364