]>
git.proxmox.com Git - rustc.git/blob - src/llvm/include/llvm/Support/MathExtras.h
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/Compiler.h"
18 #include "llvm/Support/SwapByteOrder.h"
21 #include <type_traits>
28 /// \brief The behavior an operation has on an input of 0.
30 /// \brief The returned value is undefined.
32 /// \brief The returned value is numeric_limits<T>::max()
34 /// \brief The returned value is numeric_limits<T>::digits
38 /// \brief Count number of 0's from the least significant bit to the most
39 /// stopping at the first 1.
41 /// Only unsigned integral types are allowed.
43 /// \param ZB the behavior on an input of 0. Only ZB_Width and ZB_Undefined are
46 typename
std::enable_if
<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
) {
52 return std::numeric_limits
<T
>::digits
;
57 std::size_t ZeroBits
= 0;
58 T Shift
= std::numeric_limits
<T
>::digits
>> 1;
59 T Mask
= std::numeric_limits
<T
>::max() >> Shift
;
61 if ((Val
& Mask
) == 0) {
73 typename
std::enable_if
<std::numeric_limits
<T
>::is_integer
&&
74 std::numeric_limits
<T
>::is_signed
, std::size_t>::type
75 countTrailingZeros(T Val
, ZeroBehavior ZB
= ZB_Width
) LLVM_DELETED_FUNCTION
;
77 #if __GNUC__ >= 4 || _MSC_VER
79 inline std::size_t countTrailingZeros
<uint32_t>(uint32_t Val
, ZeroBehavior ZB
) {
80 if (ZB
!= ZB_Undefined
&& Val
== 0)
83 #if __has_builtin(__builtin_ctz) || __GNUC_PREREQ(4, 0)
84 return __builtin_ctz(Val
);
87 _BitScanForward(&Index
, Val
);
92 #if !defined(_MSC_VER) || defined(_M_X64)
94 inline std::size_t countTrailingZeros
<uint64_t>(uint64_t Val
, ZeroBehavior ZB
) {
95 if (ZB
!= ZB_Undefined
&& Val
== 0)
98 #if __has_builtin(__builtin_ctzll) || __GNUC_PREREQ(4, 0)
99 return __builtin_ctzll(Val
);
102 _BitScanForward64(&Index
, Val
);
109 /// \brief Count number of 0's from the most significant bit to the least
110 /// stopping at the first 1.
112 /// Only unsigned integral types are allowed.
114 /// \param ZB the behavior on an input of 0. Only ZB_Width and ZB_Undefined are
116 template <typename T
>
117 typename
std::enable_if
<std::numeric_limits
<T
>::is_integer
&&
118 !std::numeric_limits
<T
>::is_signed
, std::size_t>::type
119 countLeadingZeros(T Val
, ZeroBehavior ZB
= ZB_Width
) {
123 return std::numeric_limits
<T
>::digits
;
126 std::size_t ZeroBits
= 0;
127 for (T Shift
= std::numeric_limits
<T
>::digits
>> 1; Shift
; Shift
>>= 1) {
128 T Tmp
= Val
>> Shift
;
138 template <typename T
>
139 typename
std::enable_if
<std::numeric_limits
<T
>::is_integer
&&
140 std::numeric_limits
<T
>::is_signed
, std::size_t>::type
141 countLeadingZeros(T Val
, ZeroBehavior ZB
= ZB_Width
) LLVM_DELETED_FUNCTION
;
143 #if __GNUC__ >= 4 || _MSC_VER
145 inline std::size_t countLeadingZeros
<uint32_t>(uint32_t Val
, ZeroBehavior ZB
) {
146 if (ZB
!= ZB_Undefined
&& Val
== 0)
149 #if __has_builtin(__builtin_clz) || __GNUC_PREREQ(4, 0)
150 return __builtin_clz(Val
);
153 _BitScanReverse(&Index
, Val
);
158 #if !defined(_MSC_VER) || defined(_M_X64)
160 inline std::size_t countLeadingZeros
<uint64_t>(uint64_t Val
, ZeroBehavior ZB
) {
161 if (ZB
!= ZB_Undefined
&& Val
== 0)
164 #if __has_builtin(__builtin_clzll) || __GNUC_PREREQ(4, 0)
165 return __builtin_clzll(Val
);
168 _BitScanReverse64(&Index
, Val
);
175 /// \brief Get the index of the first set bit starting from the least
178 /// Only unsigned integral types are allowed.
180 /// \param ZB the behavior on an input of 0. Only ZB_Max and ZB_Undefined are
182 template <typename T
>
183 typename
std::enable_if
<std::numeric_limits
<T
>::is_integer
&&
184 !std::numeric_limits
<T
>::is_signed
, T
>::type
185 findFirstSet(T Val
, ZeroBehavior ZB
= ZB_Max
) {
186 if (ZB
== ZB_Max
&& Val
== 0)
187 return std::numeric_limits
<T
>::max();
189 return countTrailingZeros(Val
, ZB_Undefined
);
193 template <typename T
>
194 typename
std::enable_if
<std::numeric_limits
<T
>::is_integer
&&
195 std::numeric_limits
<T
>::is_signed
, T
>::type
196 findFirstSet(T Val
, ZeroBehavior ZB
= ZB_Max
) LLVM_DELETED_FUNCTION
;
198 /// \brief Get the index of the last set bit starting from the least
201 /// Only unsigned integral types are allowed.
203 /// \param ZB the behavior on an input of 0. Only ZB_Max and ZB_Undefined are
205 template <typename T
>
206 typename
std::enable_if
<std::numeric_limits
<T
>::is_integer
&&
207 !std::numeric_limits
<T
>::is_signed
, T
>::type
208 findLastSet(T Val
, ZeroBehavior ZB
= ZB_Max
) {
209 if (ZB
== ZB_Max
&& Val
== 0)
210 return std::numeric_limits
<T
>::max();
212 // Use ^ instead of - because both gcc and llvm can remove the associated ^
213 // in the __builtin_clz intrinsic on x86.
214 return countLeadingZeros(Val
, ZB_Undefined
) ^
215 (std::numeric_limits
<T
>::digits
- 1);
219 template <typename T
>
220 typename
std::enable_if
<std::numeric_limits
<T
>::is_integer
&&
221 std::numeric_limits
<T
>::is_signed
, T
>::type
222 findLastSet(T Val
, ZeroBehavior ZB
= ZB_Max
) LLVM_DELETED_FUNCTION
;
224 /// \brief Macro compressed bit reversal table for 256 bits.
226 /// http://graphics.stanford.edu/~seander/bithacks.html#BitReverseTable
227 static const unsigned char BitReverseTable256
[256] = {
228 #define R2(n) n, n + 2 * 64, n + 1 * 64, n + 3 * 64
229 #define R4(n) R2(n), R2(n + 2 * 16), R2(n + 1 * 16), R2(n + 3 * 16)
230 #define R6(n) R4(n), R4(n + 2 * 4), R4(n + 1 * 4), R4(n + 3 * 4)
231 R6(0), R6(2), R6(1), R6(3)
237 /// \brief Reverse the bits in \p Val.
238 template <typename T
>
239 T
reverseBits(T Val
) {
240 unsigned char in
[sizeof(Val
)];
241 unsigned char out
[sizeof(Val
)];
242 std::memcpy(in
, &Val
, sizeof(Val
));
243 for (unsigned i
= 0; i
< sizeof(Val
); ++i
)
244 out
[(sizeof(Val
) - i
) - 1] = BitReverseTable256
[in
[i
]];
245 std::memcpy(&Val
, out
, sizeof(Val
));
249 // NOTE: The following support functions use the _32/_64 extensions instead of
250 // type overloading so that signed and unsigned integers can be used without
253 /// Hi_32 - This function returns the high 32 bits of a 64 bit value.
254 inline uint32_t Hi_32(uint64_t Value
) {
255 return static_cast<uint32_t>(Value
>> 32);
258 /// Lo_32 - This function returns the low 32 bits of a 64 bit value.
259 inline uint32_t Lo_32(uint64_t Value
) {
260 return static_cast<uint32_t>(Value
);
263 /// Make_64 - This functions makes a 64-bit integer from a high / low pair of
265 inline uint64_t Make_64(uint32_t High
, uint32_t Low
) {
266 return ((uint64_t)High
<< 32) | (uint64_t)Low
;
269 /// isInt - Checks if an integer fits into the given bit width.
271 inline bool isInt(int64_t x
) {
272 return N
>= 64 || (-(INT64_C(1)<<(N
-1)) <= x
&& x
< (INT64_C(1)<<(N
-1)));
274 // Template specializations to get better code for common cases.
276 inline bool isInt
<8>(int64_t x
) {
277 return static_cast<int8_t>(x
) == x
;
280 inline bool isInt
<16>(int64_t x
) {
281 return static_cast<int16_t>(x
) == x
;
284 inline bool isInt
<32>(int64_t x
) {
285 return static_cast<int32_t>(x
) == x
;
288 /// isShiftedInt<N,S> - Checks if a signed integer is an N bit number shifted
290 template<unsigned N
, unsigned S
>
291 inline bool isShiftedInt(int64_t x
) {
292 return isInt
<N
+S
>(x
) && (x
% (1<<S
) == 0);
295 /// isUInt - Checks if an unsigned integer fits into the given bit width.
297 inline bool isUInt(uint64_t x
) {
298 return N
>= 64 || x
< (UINT64_C(1)<<(N
));
300 // Template specializations to get better code for common cases.
302 inline bool isUInt
<8>(uint64_t x
) {
303 return static_cast<uint8_t>(x
) == x
;
306 inline bool isUInt
<16>(uint64_t x
) {
307 return static_cast<uint16_t>(x
) == x
;
310 inline bool isUInt
<32>(uint64_t x
) {
311 return static_cast<uint32_t>(x
) == x
;
314 /// isShiftedUInt<N,S> - Checks if a unsigned integer is an N bit number shifted
316 template<unsigned N
, unsigned S
>
317 inline bool isShiftedUInt(uint64_t x
) {
318 return isUInt
<N
+S
>(x
) && (x
% (1<<S
) == 0);
321 /// isUIntN - Checks if an unsigned integer fits into the given (dynamic)
323 inline bool isUIntN(unsigned N
, uint64_t x
) {
324 return x
== (x
& (~0ULL >> (64 - N
)));
327 /// isIntN - Checks if an signed integer fits into the given (dynamic)
329 inline bool isIntN(unsigned N
, int64_t x
) {
330 return N
>= 64 || (-(INT64_C(1)<<(N
-1)) <= x
&& x
< (INT64_C(1)<<(N
-1)));
333 /// isMask_32 - This function returns true if the argument is a sequence of ones
334 /// starting at the least significant bit with the remainder zero (32 bit
335 /// version). Ex. isMask_32(0x0000FFFFU) == true.
336 inline bool isMask_32(uint32_t Value
) {
337 return Value
&& ((Value
+ 1) & Value
) == 0;
340 /// isMask_64 - This function returns true if the argument is a sequence of ones
341 /// starting at the least significant bit with the remainder zero (64 bit
343 inline bool isMask_64(uint64_t Value
) {
344 return Value
&& ((Value
+ 1) & Value
) == 0;
347 /// isShiftedMask_32 - This function returns true if the argument contains a
348 /// sequence of ones with the remainder zero (32 bit version.)
349 /// Ex. isShiftedMask_32(0x0000FF00U) == true.
350 inline bool isShiftedMask_32(uint32_t Value
) {
351 return isMask_32((Value
- 1) | Value
);
354 /// isShiftedMask_64 - This function returns true if the argument contains a
355 /// sequence of ones with the remainder zero (64 bit version.)
356 inline bool isShiftedMask_64(uint64_t Value
) {
357 return isMask_64((Value
- 1) | Value
);
360 /// isPowerOf2_32 - This function returns true if the argument is a power of
361 /// two > 0. Ex. isPowerOf2_32(0x00100000U) == true (32 bit edition.)
362 inline bool isPowerOf2_32(uint32_t Value
) {
363 return Value
&& !(Value
& (Value
- 1));
366 /// isPowerOf2_64 - This function returns true if the argument is a power of two
367 /// > 0 (64 bit edition.)
368 inline bool isPowerOf2_64(uint64_t Value
) {
369 return Value
&& !(Value
& (Value
- int64_t(1L)));
372 /// ByteSwap_16 - This function returns a byte-swapped representation of the
373 /// 16-bit argument, Value.
374 inline uint16_t ByteSwap_16(uint16_t Value
) {
375 return sys::SwapByteOrder_16(Value
);
378 /// ByteSwap_32 - This function returns a byte-swapped representation of the
379 /// 32-bit argument, Value.
380 inline uint32_t ByteSwap_32(uint32_t Value
) {
381 return sys::SwapByteOrder_32(Value
);
384 /// ByteSwap_64 - This function returns a byte-swapped representation of the
385 /// 64-bit argument, Value.
386 inline uint64_t ByteSwap_64(uint64_t Value
) {
387 return sys::SwapByteOrder_64(Value
);
390 /// CountLeadingOnes_32 - this function performs the operation of
391 /// counting the number of ones from the most significant bit to the first zero
392 /// bit. Ex. CountLeadingOnes_32(0xFF0FFF00) == 8.
393 /// Returns 32 if the word is all ones.
394 inline unsigned CountLeadingOnes_32(uint32_t Value
) {
395 return countLeadingZeros(~Value
);
398 /// CountLeadingOnes_64 - This function performs the operation
399 /// of counting the number of ones from the most significant bit to the first
400 /// zero bit (64 bit edition.)
401 /// Returns 64 if the word is all ones.
402 inline unsigned CountLeadingOnes_64(uint64_t Value
) {
403 return countLeadingZeros(~Value
);
406 /// CountTrailingOnes_32 - this function performs the operation of
407 /// counting the number of ones from the least significant bit to the first zero
408 /// bit. Ex. CountTrailingOnes_32(0x00FF00FF) == 8.
409 /// Returns 32 if the word is all ones.
410 inline unsigned CountTrailingOnes_32(uint32_t Value
) {
411 return countTrailingZeros(~Value
);
414 /// CountTrailingOnes_64 - This function performs the operation
415 /// of counting the number of ones from the least significant bit to the first
416 /// zero bit (64 bit edition.)
417 /// Returns 64 if the word is all ones.
418 inline unsigned CountTrailingOnes_64(uint64_t Value
) {
419 return countTrailingZeros(~Value
);
422 /// CountPopulation_32 - this function counts the number of set bits in a value.
423 /// Ex. CountPopulation(0xF000F000) = 8
424 /// Returns 0 if the word is zero.
425 inline unsigned CountPopulation_32(uint32_t Value
) {
427 return __builtin_popcount(Value
);
429 uint32_t v
= Value
- ((Value
>> 1) & 0x55555555);
430 v
= (v
& 0x33333333) + ((v
>> 2) & 0x33333333);
431 return ((v
+ (v
>> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
435 /// CountPopulation_64 - this function counts the number of set bits in a value,
436 /// (64 bit edition.)
437 inline unsigned CountPopulation_64(uint64_t Value
) {
439 return __builtin_popcountll(Value
);
441 uint64_t v
= Value
- ((Value
>> 1) & 0x5555555555555555ULL
);
442 v
= (v
& 0x3333333333333333ULL
) + ((v
>> 2) & 0x3333333333333333ULL
);
443 v
= (v
+ (v
>> 4)) & 0x0F0F0F0F0F0F0F0FULL
;
444 return unsigned((uint64_t)(v
* 0x0101010101010101ULL
) >> 56);
448 /// Log2_32 - This function returns the floor log base 2 of the specified value,
449 /// -1 if the value is zero. (32 bit edition.)
450 /// Ex. Log2_32(32) == 5, Log2_32(1) == 0, Log2_32(0) == -1, Log2_32(6) == 2
451 inline unsigned Log2_32(uint32_t Value
) {
452 return 31 - countLeadingZeros(Value
);
455 /// Log2_64 - This function returns the floor log base 2 of the specified value,
456 /// -1 if the value is zero. (64 bit edition.)
457 inline unsigned Log2_64(uint64_t Value
) {
458 return 63 - countLeadingZeros(Value
);
461 /// Log2_32_Ceil - This function returns the ceil log base 2 of the specified
462 /// value, 32 if the value is zero. (32 bit edition).
463 /// Ex. Log2_32_Ceil(32) == 5, Log2_32_Ceil(1) == 0, Log2_32_Ceil(6) == 3
464 inline unsigned Log2_32_Ceil(uint32_t Value
) {
465 return 32 - countLeadingZeros(Value
- 1);
468 /// Log2_64_Ceil - This function returns the ceil log base 2 of the specified
469 /// value, 64 if the value is zero. (64 bit edition.)
470 inline unsigned Log2_64_Ceil(uint64_t Value
) {
471 return 64 - countLeadingZeros(Value
- 1);
474 /// GreatestCommonDivisor64 - Return the greatest common divisor of the two
475 /// values using Euclid's algorithm.
476 inline uint64_t GreatestCommonDivisor64(uint64_t A
, uint64_t B
) {
485 /// BitsToDouble - This function takes a 64-bit integer and returns the bit
486 /// equivalent double.
487 inline double BitsToDouble(uint64_t Bits
) {
496 /// BitsToFloat - This function takes a 32-bit integer and returns the bit
497 /// equivalent float.
498 inline float BitsToFloat(uint32_t Bits
) {
507 /// DoubleToBits - This function takes a double and returns the bit
508 /// equivalent 64-bit integer. Note that copying doubles around
509 /// changes the bits of NaNs on some hosts, notably x86, so this
510 /// routine cannot be used if these bits are needed.
511 inline uint64_t DoubleToBits(double Double
) {
520 /// FloatToBits - This function takes a float and returns the bit
521 /// equivalent 32-bit integer. Note that copying floats around
522 /// changes the bits of NaNs on some hosts, notably x86, so this
523 /// routine cannot be used if these bits are needed.
524 inline uint32_t FloatToBits(float Float
) {
533 /// Platform-independent wrappers for the C99 isnan() function.
537 /// Platform-independent wrappers for the C99 isinf() function.
541 /// MinAlign - A and B are either alignments or offsets. Return the minimum
542 /// alignment that may be assumed after adding the two together.
543 inline uint64_t MinAlign(uint64_t A
, uint64_t B
) {
544 // The largest power of 2 that divides both A and B.
546 // Replace "-Value" by "1+~Value" in the following commented code to avoid
547 // MSVC warning C4146
548 // return (A | B) & -(A | B);
549 return (A
| B
) & (1 + ~(A
| B
));
552 /// \brief Aligns \c Addr to \c Alignment bytes, rounding up.
554 /// Alignment should be a power of two. This method rounds up, so
555 /// alignAddr(7, 4) == 8 and alignAddr(8, 4) == 8.
556 inline uintptr_t alignAddr(void *Addr
, size_t Alignment
) {
557 assert(Alignment
&& isPowerOf2_64((uint64_t)Alignment
) &&
558 "Alignment is not a power of two!");
560 assert((uintptr_t)Addr
+ Alignment
- 1 >= (uintptr_t)Addr
);
562 return (((uintptr_t)Addr
+ Alignment
- 1) & ~(uintptr_t)(Alignment
- 1));
565 /// \brief Returns the necessary adjustment for aligning \c Ptr to \c Alignment
566 /// bytes, rounding up.
567 inline size_t alignmentAdjustment(void *Ptr
, size_t Alignment
) {
568 return alignAddr(Ptr
, Alignment
) - (uintptr_t)Ptr
;
571 /// NextPowerOf2 - Returns the next power of two (in 64-bits)
572 /// that is strictly greater than A. Returns zero on overflow.
573 inline uint64_t NextPowerOf2(uint64_t A
) {
583 /// Returns the power of two which is less than or equal to the given value.
584 /// Essentially, it is a floor operation across the domain of powers of two.
585 inline uint64_t PowerOf2Floor(uint64_t A
) {
587 return 1ull << (63 - countLeadingZeros(A
, ZB_Undefined
));
590 /// Returns the next integer (mod 2**64) that is greater than or equal to
591 /// \p Value and is a multiple of \p Align. \p Align must be non-zero.
595 /// RoundUpToAlignment(5, 8) = 8
596 /// RoundUpToAlignment(17, 8) = 24
597 /// RoundUpToAlignment(~0LL, 8) = 0
599 inline uint64_t RoundUpToAlignment(uint64_t Value
, uint64_t Align
) {
600 return ((Value
+ Align
- 1) / Align
) * Align
;
603 /// Returns the offset to the next integer (mod 2**64) that is greater than
604 /// or equal to \p Value and is a multiple of \p Align. \p Align must be
606 inline uint64_t OffsetToAlignment(uint64_t Value
, uint64_t Align
) {
607 return RoundUpToAlignment(Value
, Align
) - Value
;
610 /// abs64 - absolute value of a 64-bit int. Not all environments support
611 /// "abs" on whatever their name for the 64-bit int type is. The absolute
612 /// value of the largest negative number is undefined, as with "abs".
613 inline int64_t abs64(int64_t x
) {
614 return (x
< 0) ? -x
: x
;
617 /// SignExtend32 - Sign extend B-bit number x to 32-bit int.
618 /// Usage int32_t r = SignExtend32<5>(x);
619 template <unsigned B
> inline int32_t SignExtend32(uint32_t x
) {
620 return int32_t(x
<< (32 - B
)) >> (32 - B
);
623 /// \brief Sign extend number in the bottom B bits of X to a 32-bit int.
624 /// Requires 0 < B <= 32.
625 inline int32_t SignExtend32(uint32_t X
, unsigned B
) {
626 return int32_t(X
<< (32 - B
)) >> (32 - B
);
629 /// SignExtend64 - Sign extend B-bit number x to 64-bit int.
630 /// Usage int64_t r = SignExtend64<5>(x);
631 template <unsigned B
> inline int64_t SignExtend64(uint64_t x
) {
632 return int64_t(x
<< (64 - B
)) >> (64 - B
);
635 /// \brief Sign extend number in the bottom B bits of X to a 64-bit int.
636 /// Requires 0 < B <= 64.
637 inline int64_t SignExtend64(uint64_t X
, unsigned B
) {
638 return int64_t(X
<< (64 - B
)) >> (64 - B
);
641 extern const float huge_valf
;
642 } // End llvm namespace