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