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 #include "llvm/Support/type_traits.h"
  19
  20 #include <cstring>
  21
  22 #ifdef _MSC_VER
  23 # include <intrin.h>
  24 #endif
  25
  26 namespace llvm {
  27 /// \brief The behavior an operation has on an input of 0.
  28 enum ZeroBehavior {
  29   /// \brief The returned value is undefined.
  30   ZB_Undefined,
  31   /// \brief The returned value is numeric_limits<T>::max()
  32   ZB_Max,
  33   /// \brief The returned value is numeric_limits<T>::digits
  34   ZB_Width
  35 };
  36
  37 /// \brief Count number of 0's from the least significant bit to the most
  38 ///   stopping at the first 1.
  39 ///
  40 /// Only unsigned integral types are allowed.
  41 ///
  42 /// \param ZB the behavior on an input of 0. Only ZB_Width and ZB_Undefined are
  43 ///   valid arguments.
  44 template <typename T>
  45 typename enable_if_c<std::numeric_limits<T>::is_integer &&
  46                      !std::numeric_limits<T>::is_signed, std::size_t>::type
  47 countTrailingZeros(T Val, ZeroBehavior ZB = ZB_Width) {
  48   if (!Val)
  49     return std::numeric_limits<T>::digits;
  50   if (Val & 0x1)
  51     return 0;
  52
  53   // Bisection method.
  54   std::size_t ZeroBits = 0;
  55   T Shift = std::numeric_limits<T>::digits >> 1;
  56   T Mask = std::numeric_limits<T>::max() >> Shift;
  57   while (Shift) {
  58     if ((Val & Mask) == 0) {
  59       Val >>= Shift;
  60       ZeroBits |= Shift;
  61     }
  62     Shift >>= 1;
  63     Mask >>= Shift;
  64   }
  65   return ZeroBits;
  66 }
  67
  68 // Disable signed.
  69 template <typename T>
  70 typename enable_if_c<std::numeric_limits<T>::is_integer &&
  71                      std::numeric_limits<T>::is_signed, std::size_t>::type
  72 countTrailingZeros(T Val, ZeroBehavior ZB = ZB_Width) LLVM_DELETED_FUNCTION;
  73
  74 #if __GNUC__ >= 4 || _MSC_VER
  75 template <>
  76 inline std::size_t countTrailingZeros<uint32_t>(uint32_t Val, ZeroBehavior ZB) {
  77   if (ZB != ZB_Undefined && Val == 0)
  78     return 32;
  79
  80 #if __GNUC__ >= 4
  81   return __builtin_ctz(Val);
  82 #elif _MSC_VER
  83   unsigned long Index;
  84   _BitScanForward(&Index, Val);
  85   return Index;
  86 #endif
  87 }
  88
  89 template <>
  90 inline std::size_t countTrailingZeros<uint64_t>(uint64_t Val, ZeroBehavior ZB) {
  91   if (ZB != ZB_Undefined && Val == 0)
  92     return 64;
  93
  94 #if __GNUC__ >= 4
  95   return __builtin_ctzll(Val);
  96 #elif _MSC_VER
  97   unsigned long Index;
  98   _BitScanForward64(&Index, Val);
  99   return Index;
 100 #endif
 101 }
 102 #endif
 103
 104 /// \brief Count number of 0's from the most significant bit to the least
 105 ///   stopping at the first 1.
 106 ///
 107 /// Only unsigned integral types are allowed.
 108 ///
 109 /// \param ZB the behavior on an input of 0. Only ZB_Width and ZB_Undefined are
 110 ///   valid arguments.
 111 template <typename T>
 112 typename enable_if_c<std::numeric_limits<T>::is_integer &&
 113                      !std::numeric_limits<T>::is_signed, std::size_t>::type
 114 countLeadingZeros(T Val, ZeroBehavior ZB = ZB_Width) {
 115   if (!Val)
 116     return std::numeric_limits<T>::digits;
 117
 118   // Bisection method.
 119   std::size_t ZeroBits = 0;
 120   for (T Shift = std::numeric_limits<T>::digits >> 1; Shift; Shift >>= 1) {
 121     T Tmp = Val >> Shift;
 122     if (Tmp)
 123       Val = Tmp;
 124     else
 125       ZeroBits |= Shift;
 126   }
 127   return ZeroBits;
 128 }
 129
 130 // Disable signed.
 131 template <typename T>
 132 typename enable_if_c<std::numeric_limits<T>::is_integer &&
 133                      std::numeric_limits<T>::is_signed, std::size_t>::type
 134 countLeadingZeros(T Val, ZeroBehavior ZB = ZB_Width) LLVM_DELETED_FUNCTION;
 135
 136 #if __GNUC__ >= 4 || _MSC_VER
 137 template <>
 138 inline std::size_t countLeadingZeros<uint32_t>(uint32_t Val, ZeroBehavior ZB) {
 139   if (ZB != ZB_Undefined && Val == 0)
 140     return 32;
 141
 142 #if __GNUC__ >= 4
 143   return __builtin_clz(Val);
 144 #elif _MSC_VER
 145   unsigned long Index;
 146   _BitScanReverse(&Index, Val);
 147   return Index ^ 31;
 148 #endif
 149 }
 150
 151 template <>
 152 inline std::size_t countLeadingZeros<uint64_t>(uint64_t Val, ZeroBehavior ZB) {
 153   if (ZB != ZB_Undefined && Val == 0)
 154     return 64;
 155
 156 #if __GNUC__ >= 4
 157   return __builtin_clzll(Val);
 158 #elif _MSC_VER
 159   unsigned long Index;
 160   _BitScanReverse64(&Index, Val);
 161   return Index ^ 63;
 162 #endif
 163 }
 164 #endif
 165
 166 /// \brief Get the index of the first set bit starting from the least
 167 ///   significant bit.
 168 ///
 169 /// Only unsigned integral types are allowed.
 170 ///
 171 /// \param ZB the behavior on an input of 0. Only ZB_Max and ZB_Undefined are
 172 ///   valid arguments.
 173 template <typename T>
 174 typename enable_if_c<std::numeric_limits<T>::is_integer &&
 175                      !std::numeric_limits<T>::is_signed, std::size_t>::type
 176 findFirstSet(T Val, ZeroBehavior ZB = ZB_Max) {
 177   if (ZB == ZB_Max && Val == 0)
 178     return std::numeric_limits<T>::max();
 179
 180   return countTrailingZeros(Val, ZB_Undefined);
 181 }
 182
 183 // Disable signed.
 184 template <typename T>
 185 typename enable_if_c<std::numeric_limits<T>::is_integer &&
 186                      std::numeric_limits<T>::is_signed, std::size_t>::type
 187 findFirstSet(T Val, ZeroBehavior ZB = ZB_Max) LLVM_DELETED_FUNCTION;
 188
 189 /// \brief Get the index of the last set bit starting from the least
 190 ///   significant bit.
 191 ///
 192 /// Only unsigned integral types are allowed.
 193 ///
 194 /// \param ZB the behavior on an input of 0. Only ZB_Max and ZB_Undefined are
 195 ///   valid arguments.
 196 template <typename T>
 197 typename enable_if_c<std::numeric_limits<T>::is_integer &&
 198                      !std::numeric_limits<T>::is_signed, std::size_t>::type
 199 findLastSet(T Val, ZeroBehavior ZB = ZB_Max) {
 200   if (ZB == ZB_Max && Val == 0)
 201     return std::numeric_limits<T>::max();
 202
 203   // Use ^ instead of - because both gcc and llvm can remove the associated ^
 204   // in the __builtin_clz intrinsic on x86.
 205   return countLeadingZeros(Val, ZB_Undefined) ^
 206          (std::numeric_limits<T>::digits - 1);
 207 }
 208
 209 // Disable signed.
 210 template <typename T>
 211 typename enable_if_c<std::numeric_limits<T>::is_integer &&
 212                      std::numeric_limits<T>::is_signed, std::size_t>::type
 213 findLastSet(T Val, ZeroBehavior ZB = ZB_Max) LLVM_DELETED_FUNCTION;
 214
 215 /// \brief Macro compressed bit reversal table for 256 bits.
 216 ///
 217 /// http://graphics.stanford.edu/~seander/bithacks.html#BitReverseTable
 218 static const unsigned char BitReverseTable256[256] = {
 219 #define R2(n) n, n + 2 * 64, n + 1 * 64, n + 3 * 64
 220 #define R4(n) R2(n), R2(n + 2 * 16), R2(n + 1 * 16), R2(n + 3 * 16)
 221 #define R6(n) R4(n), R4(n + 2 * 4), R4(n + 1 * 4), R4(n + 3 * 4)
 222   R6(0), R6(2), R6(1), R6(3)
 223 };
 224
 225 /// \brief Reverse the bits in \p Val.
 226 template <typename T>
 227 T reverseBits(T Val) {
 228   unsigned char in[sizeof(Val)];
 229   unsigned char out[sizeof(Val)];
 230   std::memcpy(in, &Val, sizeof(Val));
 231   for (unsigned i = 0; i < sizeof(Val); ++i)
 232     out[(sizeof(Val) - i) - 1] = BitReverseTable256[in[i]];
 233   std::memcpy(&Val, out, sizeof(Val));
 234   return Val;
 235 }
 236
 237 // NOTE: The following support functions use the _32/_64 extensions instead of
 238 // type overloading so that signed and unsigned integers can be used without
 239 // ambiguity.
 240
 241 /// Hi_32 - This function returns the high 32 bits of a 64 bit value.
 242 inline uint32_t Hi_32(uint64_t Value) {
 243   return static_cast<uint32_t>(Value >> 32);
 244 }
 245
 246 /// Lo_32 - This function returns the low 32 bits of a 64 bit value.
 247 inline uint32_t Lo_32(uint64_t Value) {
 248   return static_cast<uint32_t>(Value);
 249 }
 250
 251 /// isInt - Checks if an integer fits into the given bit width.
 252 template<unsigned N>
 253 inline bool isInt(int64_t x) {
 254   return N >= 64 || (-(INT64_C(1)<<(N-1)) <= x && x < (INT64_C(1)<<(N-1)));
 255 }
 256 // Template specializations to get better code for common cases.
 257 template<>
 258 inline bool isInt<8>(int64_t x) {
 259   return static_cast<int8_t>(x) == x;
 260 }
 261 template<>
 262 inline bool isInt<16>(int64_t x) {
 263   return static_cast<int16_t>(x) == x;
 264 }
 265 template<>
 266 inline bool isInt<32>(int64_t x) {
 267   return static_cast<int32_t>(x) == x;
 268 }
 269
 270 /// isShiftedInt<N,S> - Checks if a signed integer is an N bit number shifted
 271 ///                     left by S.
 272 template<unsigned N, unsigned S>
 273 inline bool isShiftedInt(int64_t x) {
 274   return isInt<N+S>(x) && (x % (1<<S) == 0);
 275 }
 276
 277 /// isUInt - Checks if an unsigned integer fits into the given bit width.
 278 template<unsigned N>
 279 inline bool isUInt(uint64_t x) {
 280   return N >= 64 || x < (UINT64_C(1)<<(N));
 281 }
 282 // Template specializations to get better code for common cases.
 283 template<>
 284 inline bool isUInt<8>(uint64_t x) {
 285   return static_cast<uint8_t>(x) == x;
 286 }
 287 template<>
 288 inline bool isUInt<16>(uint64_t x) {
 289   return static_cast<uint16_t>(x) == x;
 290 }
 291 template<>
 292 inline bool isUInt<32>(uint64_t x) {
 293   return static_cast<uint32_t>(x) == x;
 294 }
 295
 296 /// isShiftedUInt<N,S> - Checks if a unsigned integer is an N bit number shifted
 297 ///                     left by S.
 298 template<unsigned N, unsigned S>
 299 inline bool isShiftedUInt(uint64_t x) {
 300   return isUInt<N+S>(x) && (x % (1<<S) == 0);
 301 }
 302
 303 /// isUIntN - Checks if an unsigned integer fits into the given (dynamic)
 304 /// bit width.
 305 inline bool isUIntN(unsigned N, uint64_t x) {
 306   return x == (x & (~0ULL >> (64 - N)));
 307 }
 308
 309 /// isIntN - Checks if an signed integer fits into the given (dynamic)
 310 /// bit width.
 311 inline bool isIntN(unsigned N, int64_t x) {
 312   return N >= 64 || (-(INT64_C(1)<<(N-1)) <= x && x < (INT64_C(1)<<(N-1)));
 313 }
 314
 315 /// isMask_32 - This function returns true if the argument is a sequence of ones
 316 /// starting at the least significant bit with the remainder zero (32 bit
 317 /// version).   Ex. isMask_32(0x0000FFFFU) == true.
 318 inline bool isMask_32(uint32_t Value) {
 319   return Value && ((Value + 1) & Value) == 0;
 320 }
 321
 322 /// isMask_64 - This function returns true if the argument is a sequence of ones
 323 /// starting at the least significant bit with the remainder zero (64 bit
 324 /// version).
 325 inline bool isMask_64(uint64_t Value) {
 326   return Value && ((Value + 1) & Value) == 0;
 327 }
 328
 329 /// isShiftedMask_32 - This function returns true if the argument contains a
 330 /// sequence of ones with the remainder zero (32 bit version.)
 331 /// Ex. isShiftedMask_32(0x0000FF00U) == true.
 332 inline bool isShiftedMask_32(uint32_t Value) {
 333   return isMask_32((Value - 1) | Value);
 334 }
 335
 336 /// isShiftedMask_64 - This function returns true if the argument contains a
 337 /// sequence of ones with the remainder zero (64 bit version.)
 338 inline bool isShiftedMask_64(uint64_t Value) {
 339   return isMask_64((Value - 1) | Value);
 340 }
 341
 342 /// isPowerOf2_32 - This function returns true if the argument is a power of
 343 /// two > 0. Ex. isPowerOf2_32(0x00100000U) == true (32 bit edition.)
 344 inline bool isPowerOf2_32(uint32_t Value) {
 345   return Value && !(Value & (Value - 1));
 346 }
 347
 348 /// isPowerOf2_64 - This function returns true if the argument is a power of two
 349 /// > 0 (64 bit edition.)
 350 inline bool isPowerOf2_64(uint64_t Value) {
 351   return Value && !(Value & (Value - int64_t(1L)));
 352 }
 353
 354 /// ByteSwap_16 - This function returns a byte-swapped representation of the
 355 /// 16-bit argument, Value.
 356 inline uint16_t ByteSwap_16(uint16_t Value) {
 357   return sys::SwapByteOrder_16(Value);
 358 }
 359
 360 /// ByteSwap_32 - This function returns a byte-swapped representation of the
 361 /// 32-bit argument, Value.
 362 inline uint32_t ByteSwap_32(uint32_t Value) {
 363   return sys::SwapByteOrder_32(Value);
 364 }
 365
 366 /// ByteSwap_64 - This function returns a byte-swapped representation of the
 367 /// 64-bit argument, Value.
 368 inline uint64_t ByteSwap_64(uint64_t Value) {
 369   return sys::SwapByteOrder_64(Value);
 370 }
 371
 372 /// CountLeadingZeros_32 - this function performs the platform optimal form of
 373 /// counting the number of zeros from the most significant bit to the first one
 374 /// bit.  Ex. CountLeadingZeros_32(0x00F000FF) == 8.
 375 /// Returns 32 if the word is zero.
 376 inline unsigned CountLeadingZeros_32(uint32_t Value) {
 377   unsigned Count; // result
 378 #if __GNUC__ >= 4
 379   // PowerPC is defined for __builtin_clz(0)
 380 #if !defined(__ppc__) && !defined(__ppc64__)
 381   if (!Value) return 32;
 382 #endif
 383   Count = __builtin_clz(Value);
 384 #else
 385   if (!Value) return 32;
 386   Count = 0;
 387   // bisection method for count leading zeros
 388   for (unsigned Shift = 32 >> 1; Shift; Shift >>= 1) {
 389     uint32_t Tmp = Value >> Shift;
 390     if (Tmp) {
 391       Value = Tmp;
 392     } else {
 393       Count |= Shift;
 394     }
 395   }
 396 #endif
 397   return Count;
 398 }
 399
 400 /// CountLeadingOnes_32 - this function performs the operation of
 401 /// counting the number of ones from the most significant bit to the first zero
 402 /// bit.  Ex. CountLeadingOnes_32(0xFF0FFF00) == 8.
 403 /// Returns 32 if the word is all ones.
 404 inline unsigned CountLeadingOnes_32(uint32_t Value) {
 405   return CountLeadingZeros_32(~Value);
 406 }
 407
 408 /// CountLeadingZeros_64 - This function performs the platform optimal form
 409 /// of counting the number of zeros from the most significant bit to the first
 410 /// one bit (64 bit edition.)
 411 /// Returns 64 if the word is zero.
 412 inline unsigned CountLeadingZeros_64(uint64_t Value) {
 413   unsigned Count; // result
 414 #if __GNUC__ >= 4
 415   // PowerPC is defined for __builtin_clzll(0)
 416 #if !defined(__ppc__) && !defined(__ppc64__)
 417   if (!Value) return 64;
 418 #endif
 419   Count = __builtin_clzll(Value);
 420 #else
 421   if (sizeof(long) == sizeof(int64_t)) {
 422     if (!Value) return 64;
 423     Count = 0;
 424     // bisection method for count leading zeros
 425     for (unsigned Shift = 64 >> 1; Shift; Shift >>= 1) {
 426       uint64_t Tmp = Value >> Shift;
 427       if (Tmp) {
 428         Value = Tmp;
 429       } else {
 430         Count |= Shift;
 431       }
 432     }
 433   } else {
 434     // get hi portion
 435     uint32_t Hi = Hi_32(Value);
 436
 437     // if some bits in hi portion
 438     if (Hi) {
 439         // leading zeros in hi portion plus all bits in lo portion
 440         Count = CountLeadingZeros_32(Hi);
 441     } else {
 442         // get lo portion
 443         uint32_t Lo = Lo_32(Value);
 444         // same as 32 bit value
 445         Count = CountLeadingZeros_32(Lo)+32;
 446     }
 447   }
 448 #endif
 449   return Count;
 450 }
 451
 452 /// CountLeadingOnes_64 - This function performs the operation
 453 /// of counting the number of ones from the most significant bit to the first
 454 /// zero bit (64 bit edition.)
 455 /// Returns 64 if the word is all ones.
 456 inline unsigned CountLeadingOnes_64(uint64_t Value) {
 457   return CountLeadingZeros_64(~Value);
 458 }
 459
 460 /// CountTrailingZeros_32 - this function performs the platform optimal form of
 461 /// counting the number of zeros from the least significant bit to the first one
 462 /// bit.  Ex. CountTrailingZeros_32(0xFF00FF00) == 8.
 463 /// Returns 32 if the word is zero.
 464 inline unsigned CountTrailingZeros_32(uint32_t Value) {
 465 #if __GNUC__ >= 4
 466   return Value ? __builtin_ctz(Value) : 32;
 467 #else
 468   static const unsigned Mod37BitPosition[] = {
 469     32, 0, 1, 26, 2, 23, 27, 0, 3, 16, 24, 30, 28, 11, 0, 13,
 470     4, 7, 17, 0, 25, 22, 31, 15, 29, 10, 12, 6, 0, 21, 14, 9,
 471     5, 20, 8, 19, 18
 472   };
 473   // Replace "-Value" by "1+~Value" in the following commented code to avoid
 474   // MSVC warning C4146
 475   //    return Mod37BitPosition[(-Value & Value) % 37];
 476   return Mod37BitPosition[((1 + ~Value) & Value) % 37];
 477 #endif
 478 }
 479
 480 /// CountTrailingOnes_32 - this function performs the operation of
 481 /// counting the number of ones from the least significant bit to the first zero
 482 /// bit.  Ex. CountTrailingOnes_32(0x00FF00FF) == 8.
 483 /// Returns 32 if the word is all ones.
 484 inline unsigned CountTrailingOnes_32(uint32_t Value) {
 485   return CountTrailingZeros_32(~Value);
 486 }
 487
 488 /// CountTrailingZeros_64 - This function performs the platform optimal form
 489 /// of counting the number of zeros from the least significant bit to the first
 490 /// one bit (64 bit edition.)
 491 /// Returns 64 if the word is zero.
 492 inline unsigned CountTrailingZeros_64(uint64_t Value) {
 493 #if __GNUC__ >= 4
 494   return Value ? __builtin_ctzll(Value) : 64;
 495 #else
 496   static const unsigned Mod67Position[] = {
 497     64, 0, 1, 39, 2, 15, 40, 23, 3, 12, 16, 59, 41, 19, 24, 54,
 498     4, 64, 13, 10, 17, 62, 60, 28, 42, 30, 20, 51, 25, 44, 55,
 499     47, 5, 32, 65, 38, 14, 22, 11, 58, 18, 53, 63, 9, 61, 27,
 500     29, 50, 43, 46, 31, 37, 21, 57, 52, 8, 26, 49, 45, 36, 56,
 501     7, 48, 35, 6, 34, 33, 0
 502   };
 503   // Replace "-Value" by "1+~Value" in the following commented code to avoid
 504   // MSVC warning C4146
 505   //    return Mod67Position[(-Value & Value) % 67];
 506   return Mod67Position[((1 + ~Value) & Value) % 67];
 507 #endif
 508 }
 509
 510 /// CountTrailingOnes_64 - This function performs the operation
 511 /// of counting the number of ones from the least significant bit to the first
 512 /// zero bit (64 bit edition.)
 513 /// Returns 64 if the word is all ones.
 514 inline unsigned CountTrailingOnes_64(uint64_t Value) {
 515   return CountTrailingZeros_64(~Value);
 516 }
 517
 518 /// CountPopulation_32 - this function counts the number of set bits in a value.
 519 /// Ex. CountPopulation(0xF000F000) = 8
 520 /// Returns 0 if the word is zero.
 521 inline unsigned CountPopulation_32(uint32_t Value) {
 522 #if __GNUC__ >= 4
 523   return __builtin_popcount(Value);
 524 #else
 525   uint32_t v = Value - ((Value >> 1) & 0x55555555);
 526   v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
 527   return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
 528 #endif
 529 }
 530
 531 /// CountPopulation_64 - this function counts the number of set bits in a value,
 532 /// (64 bit edition.)
 533 inline unsigned CountPopulation_64(uint64_t Value) {
 534 #if __GNUC__ >= 4
 535   return __builtin_popcountll(Value);
 536 #else
 537   uint64_t v = Value - ((Value >> 1) & 0x5555555555555555ULL);
 538   v = (v & 0x3333333333333333ULL) + ((v >> 2) & 0x3333333333333333ULL);
 539   v = (v + (v >> 4)) & 0x0F0F0F0F0F0F0F0FULL;
 540   return unsigned((uint64_t)(v * 0x0101010101010101ULL) >> 56);
 541 #endif
 542 }
 543
 544 /// Log2_32 - This function returns the floor log base 2 of the specified value,
 545 /// -1 if the value is zero. (32 bit edition.)
 546 /// Ex. Log2_32(32) == 5, Log2_32(1) == 0, Log2_32(0) == -1, Log2_32(6) == 2
 547 inline unsigned Log2_32(uint32_t Value) {
 548   return 31 - CountLeadingZeros_32(Value);
 549 }
 550
 551 /// Log2_64 - This function returns the floor log base 2 of the specified value,
 552 /// -1 if the value is zero. (64 bit edition.)
 553 inline unsigned Log2_64(uint64_t Value) {
 554   return 63 - CountLeadingZeros_64(Value);
 555 }
 556
 557 /// Log2_32_Ceil - This function returns the ceil log base 2 of the specified
 558 /// value, 32 if the value is zero. (32 bit edition).
 559 /// Ex. Log2_32_Ceil(32) == 5, Log2_32_Ceil(1) == 0, Log2_32_Ceil(6) == 3
 560 inline unsigned Log2_32_Ceil(uint32_t Value) {
 561   return 32-CountLeadingZeros_32(Value-1);
 562 }
 563
 564 /// Log2_64_Ceil - This function returns the ceil log base 2 of the specified
 565 /// value, 64 if the value is zero. (64 bit edition.)
 566 inline unsigned Log2_64_Ceil(uint64_t Value) {
 567   return 64-CountLeadingZeros_64(Value-1);
 568 }
 569
 570 /// GreatestCommonDivisor64 - Return the greatest common divisor of the two
 571 /// values using Euclid's algorithm.
 572 inline uint64_t GreatestCommonDivisor64(uint64_t A, uint64_t B) {
 573   while (B) {
 574     uint64_t T = B;
 575     B = A % B;
 576     A = T;
 577   }
 578   return A;
 579 }
 580
 581 /// BitsToDouble - This function takes a 64-bit integer and returns the bit
 582 /// equivalent double.
 583 inline double BitsToDouble(uint64_t Bits) {
 584   union {
 585     uint64_t L;
 586     double D;
 587   } T;
 588   T.L = Bits;
 589   return T.D;
 590 }
 591
 592 /// BitsToFloat - This function takes a 32-bit integer and returns the bit
 593 /// equivalent float.
 594 inline float BitsToFloat(uint32_t Bits) {
 595   union {
 596     uint32_t I;
 597     float F;
 598   } T;
 599   T.I = Bits;
 600   return T.F;
 601 }
 602
 603 /// DoubleToBits - This function takes a double and returns the bit
 604 /// equivalent 64-bit integer.  Note that copying doubles around
 605 /// changes the bits of NaNs on some hosts, notably x86, so this
 606 /// routine cannot be used if these bits are needed.
 607 inline uint64_t DoubleToBits(double Double) {
 608   union {
 609     uint64_t L;
 610     double D;
 611   } T;
 612   T.D = Double;
 613   return T.L;
 614 }
 615
 616 /// FloatToBits - This function takes a float and returns the bit
 617 /// equivalent 32-bit integer.  Note that copying floats around
 618 /// changes the bits of NaNs on some hosts, notably x86, so this
 619 /// routine cannot be used if these bits are needed.
 620 inline uint32_t FloatToBits(float Float) {
 621   union {
 622     uint32_t I;
 623     float F;
 624   } T;
 625   T.F = Float;
 626   return T.I;
 627 }
 628
 629 /// Platform-independent wrappers for the C99 isnan() function.
 630 int IsNAN(float f);
 631 int IsNAN(double d);
 632
 633 /// Platform-independent wrappers for the C99 isinf() function.
 634 int IsInf(float f);
 635 int IsInf(double d);
 636
 637 /// MinAlign - A and B are either alignments or offsets.  Return the minimum
 638 /// alignment that may be assumed after adding the two together.
 639 inline uint64_t MinAlign(uint64_t A, uint64_t B) {
 640   // The largest power of 2 that divides both A and B.
 641   //
 642   // Replace "-Value" by "1+~Value" in the following commented code to avoid
 643   // MSVC warning C4146
 644   //    return (A | B) & -(A | B);
 645   return (A | B) & (1 + ~(A | B));
 646 }
 647
 648 /// NextPowerOf2 - Returns the next power of two (in 64-bits)
 649 /// that is strictly greater than A.  Returns zero on overflow.
 650 inline uint64_t NextPowerOf2(uint64_t A) {
 651   A |= (A >> 1);
 652   A |= (A >> 2);
 653   A |= (A >> 4);
 654   A |= (A >> 8);
 655   A |= (A >> 16);
 656   A |= (A >> 32);
 657   return A + 1;
 658 }
 659
 660 /// Returns the next integer (mod 2**64) that is greater than or equal to
 661 /// \p Value and is a multiple of \p Align. \p Align must be non-zero.
 662 ///
 663 /// Examples:
 664 /// \code
 665 ///   RoundUpToAlignment(5, 8) = 8
 666 ///   RoundUpToAlignment(17, 8) = 24
 667 ///   RoundUpToAlignment(~0LL, 8) = 0
 668 /// \endcode
 669 inline uint64_t RoundUpToAlignment(uint64_t Value, uint64_t Align) {
 670   return ((Value + Align - 1) / Align) * Align;
 671 }
 672
 673 /// Returns the offset to the next integer (mod 2**64) that is greater than
 674 /// or equal to \p Value and is a multiple of \p Align. \p Align must be
 675 /// non-zero.
 676 inline uint64_t OffsetToAlignment(uint64_t Value, uint64_t Align) {
 677   return RoundUpToAlignment(Value, Align) - Value;
 678 }
 679
 680 /// abs64 - absolute value of a 64-bit int.  Not all environments support
 681 /// "abs" on whatever their name for the 64-bit int type is.  The absolute
 682 /// value of the largest negative number is undefined, as with "abs".
 683 inline int64_t abs64(int64_t x) {
 684   return (x < 0) ? -x : x;
 685 }
 686
 687 /// SignExtend32 - Sign extend B-bit number x to 32-bit int.
 688 /// Usage int32_t r = SignExtend32<5>(x);
 689 template <unsigned B> inline int32_t SignExtend32(uint32_t x) {
 690   return int32_t(x << (32 - B)) >> (32 - B);
 691 }
 692
 693 /// \brief Sign extend number in the bottom B bits of X to a 32-bit int.
 694 /// Requires 0 < B <= 32.
 695 inline int32_t SignExtend32(uint32_t X, unsigned B) {
 696   return int32_t(X << (32 - B)) >> (32 - B);
 697 }
 698
 699 /// SignExtend64 - Sign extend B-bit number x to 64-bit int.
 700 /// Usage int64_t r = SignExtend64<5>(x);
 701 template <unsigned B> inline int64_t SignExtend64(uint64_t x) {
 702   return int64_t(x << (64 - B)) >> (64 - B);
 703 }
 704
 705 /// \brief Sign extend number in the bottom B bits of X to a 64-bit int.
 706 /// Requires 0 < B <= 64.
 707 inline int64_t SignExtend64(uint64_t X, unsigned B) {
 708   return int64_t(X << (64 - B)) >> (64 - B);
 709 }
 710
 711 } // End llvm namespace
 712
 713 #endif