include/llvm/Support/MathExtras.h

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