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"
19 #include "llvm/Support/type_traits.h"
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 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) {
50 return std::numeric_limits<T>::digits;
55 std::size_t ZeroBits = 0;
56 T Shift = std::numeric_limits<T>::digits >> 1;
57 T Mask = std::numeric_limits<T>::max() >> Shift;
59 if ((Val & Mask) == 0) {
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;
75 #if __GNUC__ >= 4 || _MSC_VER
77 inline std::size_t countTrailingZeros<uint32_t>(uint32_t Val, ZeroBehavior ZB) {
78 if (ZB != ZB_Undefined && Val == 0)
82 return __builtin_ctz(Val);
85 _BitScanForward(&Index, Val);
90 #if !defined(_MSC_VER) || defined(_M_X64)
92 inline std::size_t countTrailingZeros<uint64_t>(uint64_t Val, ZeroBehavior ZB) {
93 if (ZB != ZB_Undefined && Val == 0)
97 return __builtin_ctzll(Val);
100 _BitScanForward64(&Index, Val);
107 /// \brief Count number of 0's from the most significant bit to the least
108 /// stopping at the first 1.
110 /// Only unsigned integral types are allowed.
112 /// \param ZB the behavior on an input of 0. Only ZB_Width and ZB_Undefined are
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) {
119 return std::numeric_limits<T>::digits;
122 std::size_t ZeroBits = 0;
123 for (T Shift = std::numeric_limits<T>::digits >> 1; Shift; Shift >>= 1) {
124 T Tmp = Val >> Shift;
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;
139 #if __GNUC__ >= 4 || _MSC_VER
141 inline std::size_t countLeadingZeros<uint32_t>(uint32_t Val, ZeroBehavior ZB) {
142 if (ZB != ZB_Undefined && Val == 0)
146 return __builtin_clz(Val);
149 _BitScanReverse(&Index, Val);
154 #if !defined(_MSC_VER) || defined(_M_X64)
156 inline std::size_t countLeadingZeros<uint64_t>(uint64_t Val, ZeroBehavior ZB) {
157 if (ZB != ZB_Undefined && Val == 0)
161 return __builtin_clzll(Val);
164 _BitScanReverse64(&Index, Val);
171 /// \brief Get the index of the first set bit starting from the least
174 /// Only unsigned integral types are allowed.
176 /// \param ZB the behavior on an input of 0. Only ZB_Max and ZB_Undefined are
178 template <typename T>
179 typename enable_if_c<std::numeric_limits<T>::is_integer &&
180 !std::numeric_limits<T>::is_signed, T>::type
181 findFirstSet(T Val, ZeroBehavior ZB = ZB_Max) {
182 if (ZB == ZB_Max && Val == 0)
183 return std::numeric_limits<T>::max();
185 return countTrailingZeros(Val, ZB_Undefined);
189 template <typename T>
190 typename enable_if_c<std::numeric_limits<T>::is_integer &&
191 std::numeric_limits<T>::is_signed, T>::type
192 findFirstSet(T Val, ZeroBehavior ZB = ZB_Max) LLVM_DELETED_FUNCTION;
194 /// \brief Get the index of the last set bit starting from the least
197 /// Only unsigned integral types are allowed.
199 /// \param ZB the behavior on an input of 0. Only ZB_Max and ZB_Undefined are
201 template <typename T>
202 typename enable_if_c<std::numeric_limits<T>::is_integer &&
203 !std::numeric_limits<T>::is_signed, T>::type
204 findLastSet(T Val, ZeroBehavior ZB = ZB_Max) {
205 if (ZB == ZB_Max && Val == 0)
206 return std::numeric_limits<T>::max();
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);
215 template <typename T>
216 typename enable_if_c<std::numeric_limits<T>::is_integer &&
217 std::numeric_limits<T>::is_signed, T>::type
218 findLastSet(T Val, ZeroBehavior ZB = ZB_Max) LLVM_DELETED_FUNCTION;
220 /// \brief Macro compressed bit reversal table for 256 bits.
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)
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));
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
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);
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);
256 /// isInt - Checks if an integer fits into the given bit width.
258 inline bool isInt(int64_t x) {
259 return N >= 64 || (-(INT64_C(1)<<(N-1)) <= x && x < (INT64_C(1)<<(N-1)));
261 // Template specializations to get better code for common cases.
263 inline bool isInt<8>(int64_t x) {
264 return static_cast<int8_t>(x) == x;
267 inline bool isInt<16>(int64_t x) {
268 return static_cast<int16_t>(x) == x;
271 inline bool isInt<32>(int64_t x) {
272 return static_cast<int32_t>(x) == x;
275 /// isShiftedInt<N,S> - Checks if a signed integer is an N bit number shifted
277 template<unsigned N, unsigned S>
278 inline bool isShiftedInt(int64_t x) {
279 return isInt<N+S>(x) && (x % (1<<S) == 0);
282 /// isUInt - Checks if an unsigned integer fits into the given bit width.
284 inline bool isUInt(uint64_t x) {
285 return N >= 64 || x < (UINT64_C(1)<<(N));
287 // Template specializations to get better code for common cases.
289 inline bool isUInt<8>(uint64_t x) {
290 return static_cast<uint8_t>(x) == x;
293 inline bool isUInt<16>(uint64_t x) {
294 return static_cast<uint16_t>(x) == x;
297 inline bool isUInt<32>(uint64_t x) {
298 return static_cast<uint32_t>(x) == x;
301 /// isShiftedUInt<N,S> - Checks if a unsigned integer is an N bit number shifted
303 template<unsigned N, unsigned S>
304 inline bool isShiftedUInt(uint64_t x) {
305 return isUInt<N+S>(x) && (x % (1<<S) == 0);
308 /// isUIntN - Checks if an unsigned integer fits into the given (dynamic)
310 inline bool isUIntN(unsigned N, uint64_t x) {
311 return x == (x & (~0ULL >> (64 - N)));
314 /// isIntN - Checks if an signed integer fits into the given (dynamic)
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)));
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;
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
330 inline bool isMask_64(uint64_t Value) {
331 return Value && ((Value + 1) & Value) == 0;
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);
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);
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));
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)));
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);
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);
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);
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
384 // PowerPC is defined for __builtin_clz(0)
385 #if !defined(__ppc__) && !defined(__ppc64__)
386 if (!Value) return 32;
388 Count = __builtin_clz(Value);
390 if (!Value) return 32;
392 // bisection method for count leading zeros
393 for (unsigned Shift = 32 >> 1; Shift; Shift >>= 1) {
394 uint32_t Tmp = Value >> Shift;
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);
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
420 // PowerPC is defined for __builtin_clzll(0)
421 #if !defined(__ppc__) && !defined(__ppc64__)
422 if (!Value) return 64;
424 Count = __builtin_clzll(Value);
426 if (sizeof(long) == sizeof(int64_t)) {
427 if (!Value) return 64;
429 // bisection method for count leading zeros
430 for (unsigned Shift = 64 >> 1; Shift; Shift >>= 1) {
431 uint64_t Tmp = Value >> Shift;
440 uint32_t Hi = Hi_32(Value);
442 // if some bits in hi portion
444 // leading zeros in hi portion plus all bits in lo portion
445 Count = CountLeadingZeros_32(Hi);
448 uint32_t Lo = Lo_32(Value);
449 // same as 32 bit value
450 Count = CountLeadingZeros_32(Lo)+32;
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);
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) {
471 return Value ? __builtin_ctz(Value) : 32;
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,
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];
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);
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) {
499 return Value ? __builtin_ctzll(Value) : 64;
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
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];
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(~Value);
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) {
528 return __builtin_popcount(Value);
530 uint32_t v = Value - ((Value >> 1) & 0x55555555);
531 v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
532 return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
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) {
540 return __builtin_popcountll(Value);
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);
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(Value);
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(Value);
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(Value - 1);
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(Value - 1);
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) {
586 /// BitsToDouble - This function takes a 64-bit integer and returns the bit
587 /// equivalent double.
588 inline double BitsToDouble(uint64_t Bits) {
597 /// BitsToFloat - This function takes a 32-bit integer and returns the bit
598 /// equivalent float.
599 inline float BitsToFloat(uint32_t Bits) {
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) {
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) {
634 /// Platform-independent wrappers for the C99 isnan() function.
638 /// Platform-independent wrappers for the C99 isinf() function.
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.
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));
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) {
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.
670 /// RoundUpToAlignment(5, 8) = 8
671 /// RoundUpToAlignment(17, 8) = 24
672 /// RoundUpToAlignment(~0LL, 8) = 0
674 inline uint64_t RoundUpToAlignment(uint64_t Value, uint64_t Align) {
675 return ((Value + Align - 1) / Align) * Align;
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
681 inline uint64_t OffsetToAlignment(uint64_t Value, uint64_t Align) {
682 return RoundUpToAlignment(Value, Align) - Value;
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;
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);
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);
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);
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);
716 } // End llvm namespace