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