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