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