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