1 //===-- llvm/Support/MathExtras.h - Useful math functions -------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file contains some functions that are useful for math stuff.
12 //===----------------------------------------------------------------------===//
14 #ifndef LLVM_SUPPORT_MATHEXTRAS_H
15 #define LLVM_SUPPORT_MATHEXTRAS_H
17 #include "llvm/Support/SwapByteOrder.h"
18 #include "llvm/Support/type_traits.h"
27 /// \brief The behavior an operation has on an input of 0.
29 /// \brief The returned value is undefined.
31 /// \brief The returned value is numeric_limits<T>::max()
33 /// \brief The returned value is numeric_limits<T>::digits
37 /// \brief Count number of 0's from the least significant bit to the most
38 /// stopping at the first 1.
40 /// Only unsigned integral types are allowed.
42 /// \param ZB the behavior on an input of 0. Only ZB_Width and ZB_Undefined are
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) {
49 return std::numeric_limits<T>::digits;
54 std::size_t ZeroBits = 0;
55 T Shift = std::numeric_limits<T>::digits >> 1;
56 T Mask = std::numeric_limits<T>::max() >> Shift;
58 if ((Val & Mask) == 0) {
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;
74 #if __GNUC__ >= 4 || _MSC_VER
76 inline std::size_t countTrailingZeros<uint32_t>(uint32_t Val, ZeroBehavior ZB) {
77 if (ZB != ZB_Undefined && Val == 0)
81 return __builtin_ctz(Val);
84 _BitScanForward(&Index, Val);
90 inline std::size_t countTrailingZeros<uint64_t>(uint64_t Val, ZeroBehavior ZB) {
91 if (ZB != ZB_Undefined && Val == 0)
95 return __builtin_ctzll(Val);
98 _BitScanForward64(&Index, Val);
104 /// \brief Count number of 0's from the most significant bit to the least
105 /// stopping at the first 1.
107 /// Only unsigned integral types are allowed.
109 /// \param ZB the behavior on an input of 0. Only ZB_Width and ZB_Undefined are
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) {
116 return std::numeric_limits<T>::digits;
119 std::size_t ZeroBits = 0;
120 for (T Shift = std::numeric_limits<T>::digits >> 1; Shift; Shift >>= 1) {
121 T Tmp = Val >> Shift;
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;
136 #if __GNUC__ >= 4 || _MSC_VER
138 inline std::size_t countLeadingZeros<uint32_t>(uint32_t Val, ZeroBehavior ZB) {
139 if (ZB != ZB_Undefined && Val == 0)
143 return __builtin_clz(Val);
146 _BitScanReverse(&Index, Val);
152 inline std::size_t countLeadingZeros<uint64_t>(uint64_t Val, ZeroBehavior ZB) {
153 if (ZB != ZB_Undefined && Val == 0)
157 return __builtin_clzll(Val);
160 _BitScanReverse64(&Index, Val);
166 /// \brief Get the index of the first set bit starting from the least
169 /// Only unsigned integral types are allowed.
171 /// \param ZB the behavior on an input of 0. Only ZB_Max and ZB_Undefined are
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();
180 return countTrailingZeros(Val, ZB_Undefined);
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;
189 /// \brief Get the index of the last set bit starting from the least
192 /// Only unsigned integral types are allowed.
194 /// \param ZB the behavior on an input of 0. Only ZB_Max and ZB_Undefined are
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();
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);
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;
215 /// \brief Macro compressed bit reversal table for 256 bits.
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)
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));
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
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);
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);
251 /// isInt - Checks if an integer fits into the given bit width.
253 inline bool isInt(int64_t x) {
254 return N >= 64 || (-(INT64_C(1)<<(N-1)) <= x && x < (INT64_C(1)<<(N-1)));
256 // Template specializations to get better code for common cases.
258 inline bool isInt<8>(int64_t x) {
259 return static_cast<int8_t>(x) == x;
262 inline bool isInt<16>(int64_t x) {
263 return static_cast<int16_t>(x) == x;
266 inline bool isInt<32>(int64_t x) {
267 return static_cast<int32_t>(x) == x;
270 /// isShiftedInt<N,S> - Checks if a signed integer is an N bit number shifted
272 template<unsigned N, unsigned S>
273 inline bool isShiftedInt(int64_t x) {
274 return isInt<N+S>(x) && (x % (1<<S) == 0);
277 /// isUInt - Checks if an unsigned integer fits into the given bit width.
279 inline bool isUInt(uint64_t x) {
280 return N >= 64 || x < (UINT64_C(1)<<(N));
282 // Template specializations to get better code for common cases.
284 inline bool isUInt<8>(uint64_t x) {
285 return static_cast<uint8_t>(x) == x;
288 inline bool isUInt<16>(uint64_t x) {
289 return static_cast<uint16_t>(x) == x;
292 inline bool isUInt<32>(uint64_t x) {
293 return static_cast<uint32_t>(x) == x;
296 /// isShiftedUInt<N,S> - Checks if a unsigned integer is an N bit number shifted
298 template<unsigned N, unsigned S>
299 inline bool isShiftedUInt(uint64_t x) {
300 return isUInt<N+S>(x) && (x % (1<<S) == 0);
303 /// isUIntN - Checks if an unsigned integer fits into the given (dynamic)
305 inline bool isUIntN(unsigned N, uint64_t x) {
306 return x == (x & (~0ULL >> (64 - N)));
309 /// isIntN - Checks if an signed integer fits into the given (dynamic)
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)));
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;
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
325 inline bool isMask_64(uint64_t Value) {
326 return Value && ((Value + 1) & Value) == 0;
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);
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);
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));
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)));
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);
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);
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);
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
379 // PowerPC is defined for __builtin_clz(0)
380 #if !defined(__ppc__) && !defined(__ppc64__)
381 if (!Value) return 32;
383 Count = __builtin_clz(Value);
385 if (!Value) return 32;
387 // bisection method for count leading zeros
388 for (unsigned Shift = 32 >> 1; Shift; Shift >>= 1) {
389 uint32_t Tmp = Value >> Shift;
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);
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
415 // PowerPC is defined for __builtin_clzll(0)
416 #if !defined(__ppc__) && !defined(__ppc64__)
417 if (!Value) return 64;
419 Count = __builtin_clzll(Value);
421 if (sizeof(long) == sizeof(int64_t)) {
422 if (!Value) return 64;
424 // bisection method for count leading zeros
425 for (unsigned Shift = 64 >> 1; Shift; Shift >>= 1) {
426 uint64_t Tmp = Value >> Shift;
435 uint32_t Hi = Hi_32(Value);
437 // if some bits in hi portion
439 // leading zeros in hi portion plus all bits in lo portion
440 Count = CountLeadingZeros_32(Hi);
443 uint32_t Lo = Lo_32(Value);
444 // same as 32 bit value
445 Count = CountLeadingZeros_32(Lo)+32;
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);
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) {
466 return Value ? __builtin_ctz(Value) : 32;
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,
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];
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);
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) {
494 return Value ? __builtin_ctzll(Value) : 64;
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
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];
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);
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) {
523 return __builtin_popcount(Value);
525 uint32_t v = Value - ((Value >> 1) & 0x55555555);
526 v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
527 return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
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) {
535 return __builtin_popcountll(Value);
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);
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);
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);
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);
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);
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) {
581 /// BitsToDouble - This function takes a 64-bit integer and returns the bit
582 /// equivalent double.
583 inline double BitsToDouble(uint64_t Bits) {
592 /// BitsToFloat - This function takes a 32-bit integer and returns the bit
593 /// equivalent float.
594 inline float BitsToFloat(uint32_t Bits) {
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) {
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) {
629 /// Platform-independent wrappers for the C99 isnan() function.
633 /// Platform-independent wrappers for the C99 isinf() function.
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.
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));
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) {
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.
665 /// RoundUpToAlignment(5, 8) = 8
666 /// RoundUpToAlignment(17, 8) = 24
667 /// RoundUpToAlignment(~0LL, 8) = 0
669 inline uint64_t RoundUpToAlignment(uint64_t Value, uint64_t Align) {
670 return ((Value + Align - 1) / Align) * Align;
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
676 inline uint64_t OffsetToAlignment(uint64_t Value, uint64_t Align) {
677 return RoundUpToAlignment(Value, Align) - Value;
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;
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);
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);
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);
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);
711 } // End llvm namespace