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