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