contrib/llvm/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 #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