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