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"
25 // NOTE: The following support functions use the _32/_64 extensions instead of
26 // type overloading so that signed and unsigned integers can be used without
29 /// Hi_32 - This function returns the high 32 bits of a 64 bit value.
30 inline uint32_t Hi_32(uint64_t Value) {
31 return static_cast<uint32_t>(Value >> 32);
34 /// Lo_32 - This function returns the low 32 bits of a 64 bit value.
35 inline uint32_t Lo_32(uint64_t Value) {
36 return static_cast<uint32_t>(Value);
39 /// isInt - Checks if an integer fits into the given bit width.
41 inline bool isInt(int64_t x) {
42 return N >= 64 || (-(INT64_C(1)<<(N-1)) <= x && x < (INT64_C(1)<<(N-1)));
44 // Template specializations to get better code for common cases.
46 inline bool isInt<8>(int64_t x) {
47 return static_cast<int8_t>(x) == x;
50 inline bool isInt<16>(int64_t x) {
51 return static_cast<int16_t>(x) == x;
54 inline bool isInt<32>(int64_t x) {
55 return static_cast<int32_t>(x) == x;
58 /// isShiftedInt<N,S> - Checks if a signed integer is an N bit number shifted
60 template<unsigned N, unsigned S>
61 inline bool isShiftedInt(int64_t x) {
62 return isInt<N+S>(x) && (x % (1<<S) == 0);
65 /// isUInt - Checks if an unsigned integer fits into the given bit width.
67 inline bool isUInt(uint64_t x) {
68 return N >= 64 || x < (UINT64_C(1)<<N);
70 // Template specializations to get better code for common cases.
72 inline bool isUInt<8>(uint64_t x) {
73 return static_cast<uint8_t>(x) == x;
76 inline bool isUInt<16>(uint64_t x) {
77 return static_cast<uint16_t>(x) == x;
80 inline bool isUInt<32>(uint64_t x) {
81 return static_cast<uint32_t>(x) == x;
84 /// isShiftedUInt<N,S> - Checks if a unsigned integer is an N bit number shifted
86 template<unsigned N, unsigned S>
87 inline bool isShiftedUInt(uint64_t x) {
88 return isUInt<N+S>(x) && (x % (1<<S) == 0);
91 /// isUIntN - Checks if an unsigned integer fits into the given (dynamic)
93 inline bool isUIntN(unsigned N, uint64_t x) {
94 return x == (x & (~0ULL >> (64 - N)));
97 /// isIntN - Checks if an signed integer fits into the given (dynamic)
99 inline bool isIntN(unsigned N, int64_t x) {
100 return N >= 64 || (-(INT64_C(1)<<(N-1)) <= x && x < (INT64_C(1)<<(N-1)));
103 /// isMask_32 - This function returns true if the argument is a sequence of ones
104 /// starting at the least significant bit with the remainder zero (32 bit
105 /// version). Ex. isMask_32(0x0000FFFFU) == true.
106 inline bool isMask_32(uint32_t Value) {
107 return Value && ((Value + 1) & Value) == 0;
110 /// isMask_64 - This function returns true if the argument is a sequence of ones
111 /// starting at the least significant bit with the remainder zero (64 bit
113 inline bool isMask_64(uint64_t Value) {
114 return Value && ((Value + 1) & Value) == 0;
117 /// isShiftedMask_32 - This function returns true if the argument contains a
118 /// sequence of ones with the remainder zero (32 bit version.)
119 /// Ex. isShiftedMask_32(0x0000FF00U) == true.
120 inline bool isShiftedMask_32(uint32_t Value) {
121 return isMask_32((Value - 1) | Value);
124 /// isShiftedMask_64 - This function returns true if the argument contains a
125 /// sequence of ones with the remainder zero (64 bit version.)
126 inline bool isShiftedMask_64(uint64_t Value) {
127 return isMask_64((Value - 1) | Value);
130 /// isPowerOf2_32 - This function returns true if the argument is a power of
131 /// two > 0. Ex. isPowerOf2_32(0x00100000U) == true (32 bit edition.)
132 inline bool isPowerOf2_32(uint32_t Value) {
133 return Value && !(Value & (Value - 1));
136 /// isPowerOf2_64 - This function returns true if the argument is a power of two
137 /// > 0 (64 bit edition.)
138 inline bool isPowerOf2_64(uint64_t Value) {
139 return Value && !(Value & (Value - int64_t(1L)));
142 /// ByteSwap_16 - This function returns a byte-swapped representation of the
143 /// 16-bit argument, Value.
144 inline uint16_t ByteSwap_16(uint16_t Value) {
145 return sys::SwapByteOrder_16(Value);
148 /// ByteSwap_32 - This function returns a byte-swapped representation of the
149 /// 32-bit argument, Value.
150 inline uint32_t ByteSwap_32(uint32_t Value) {
151 return sys::SwapByteOrder_32(Value);
154 /// ByteSwap_64 - This function returns a byte-swapped representation of the
155 /// 64-bit argument, Value.
156 inline uint64_t ByteSwap_64(uint64_t Value) {
157 return sys::SwapByteOrder_64(Value);
160 /// CountLeadingZeros_32 - this function performs the platform optimal form of
161 /// counting the number of zeros from the most significant bit to the first one
162 /// bit. Ex. CountLeadingZeros_32(0x00F000FF) == 8.
163 /// Returns 32 if the word is zero.
164 inline unsigned CountLeadingZeros_32(uint32_t Value) {
165 unsigned Count; // result
167 // PowerPC is defined for __builtin_clz(0)
168 #if !defined(__ppc__) && !defined(__ppc64__)
169 if (!Value) return 32;
171 Count = __builtin_clz(Value);
173 if (!Value) return 32;
175 // bisection method for count leading zeros
176 for (unsigned Shift = 32 >> 1; Shift; Shift >>= 1) {
177 uint32_t Tmp = Value >> Shift;
188 /// CountLeadingOnes_32 - this function performs the operation of
189 /// counting the number of ones from the most significant bit to the first zero
190 /// bit. Ex. CountLeadingOnes_32(0xFF0FFF00) == 8.
191 /// Returns 32 if the word is all ones.
192 inline unsigned CountLeadingOnes_32(uint32_t Value) {
193 return CountLeadingZeros_32(~Value);
196 /// CountLeadingZeros_64 - This function performs the platform optimal form
197 /// of counting the number of zeros from the most significant bit to the first
198 /// one bit (64 bit edition.)
199 /// Returns 64 if the word is zero.
200 inline unsigned CountLeadingZeros_64(uint64_t Value) {
201 unsigned Count; // result
203 // PowerPC is defined for __builtin_clzll(0)
204 #if !defined(__ppc__) && !defined(__ppc64__)
205 if (!Value) return 64;
207 Count = __builtin_clzll(Value);
209 if (sizeof(long) == sizeof(int64_t)) {
210 if (!Value) return 64;
212 // bisection method for count leading zeros
213 for (unsigned Shift = 64 >> 1; Shift; Shift >>= 1) {
214 uint64_t Tmp = Value >> Shift;
223 uint32_t Hi = Hi_32(Value);
225 // if some bits in hi portion
227 // leading zeros in hi portion plus all bits in lo portion
228 Count = CountLeadingZeros_32(Hi);
231 uint32_t Lo = Lo_32(Value);
232 // same as 32 bit value
233 Count = CountLeadingZeros_32(Lo)+32;
240 /// CountLeadingOnes_64 - This function performs the operation
241 /// of counting the number of ones from the most significant bit to the first
242 /// zero bit (64 bit edition.)
243 /// Returns 64 if the word is all ones.
244 inline unsigned CountLeadingOnes_64(uint64_t Value) {
245 return CountLeadingZeros_64(~Value);
248 /// CountTrailingZeros_32 - this function performs the platform optimal form of
249 /// counting the number of zeros from the least significant bit to the first one
250 /// bit. Ex. CountTrailingZeros_32(0xFF00FF00) == 8.
251 /// Returns 32 if the word is zero.
252 inline unsigned CountTrailingZeros_32(uint32_t Value) {
254 return Value ? __builtin_ctz(Value) : 32;
256 static const unsigned Mod37BitPosition[] = {
257 32, 0, 1, 26, 2, 23, 27, 0, 3, 16, 24, 30, 28, 11, 0, 13,
258 4, 7, 17, 0, 25, 22, 31, 15, 29, 10, 12, 6, 0, 21, 14, 9,
261 return Mod37BitPosition[(-Value & Value) % 37];
265 /// CountTrailingOnes_32 - this function performs the operation of
266 /// counting the number of ones from the least significant bit to the first zero
267 /// bit. Ex. CountTrailingOnes_32(0x00FF00FF) == 8.
268 /// Returns 32 if the word is all ones.
269 inline unsigned CountTrailingOnes_32(uint32_t Value) {
270 return CountTrailingZeros_32(~Value);
273 /// CountTrailingZeros_64 - This function performs the platform optimal form
274 /// of counting the number of zeros from the least significant bit to the first
275 /// one bit (64 bit edition.)
276 /// Returns 64 if the word is zero.
277 inline unsigned CountTrailingZeros_64(uint64_t Value) {
279 return Value ? __builtin_ctzll(Value) : 64;
281 static const unsigned Mod67Position[] = {
282 64, 0, 1, 39, 2, 15, 40, 23, 3, 12, 16, 59, 41, 19, 24, 54,
283 4, 64, 13, 10, 17, 62, 60, 28, 42, 30, 20, 51, 25, 44, 55,
284 47, 5, 32, 65, 38, 14, 22, 11, 58, 18, 53, 63, 9, 61, 27,
285 29, 50, 43, 46, 31, 37, 21, 57, 52, 8, 26, 49, 45, 36, 56,
286 7, 48, 35, 6, 34, 33, 0
288 return Mod67Position[(-Value & Value) % 67];
292 /// CountTrailingOnes_64 - This function performs the operation
293 /// of counting the number of ones from the least significant bit to the first
294 /// zero bit (64 bit edition.)
295 /// Returns 64 if the word is all ones.
296 inline unsigned CountTrailingOnes_64(uint64_t Value) {
297 return CountTrailingZeros_64(~Value);
300 /// CountPopulation_32 - this function counts the number of set bits in a value.
301 /// Ex. CountPopulation(0xF000F000) = 8
302 /// Returns 0 if the word is zero.
303 inline unsigned CountPopulation_32(uint32_t Value) {
305 return __builtin_popcount(Value);
306 #elif defined(_MSC_VER)
307 return __popcnt(Value);
309 uint32_t v = Value - ((Value >> 1) & 0x55555555);
310 v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
311 return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
315 /// CountPopulation_64 - this function counts the number of set bits in a value,
316 /// (64 bit edition.)
317 inline unsigned CountPopulation_64(uint64_t Value) {
319 return __builtin_popcountll(Value);
320 #elif defined(_MSC_VER) && defined(_M_X64)
321 return __popcnt64(Value);
323 uint64_t v = Value - ((Value >> 1) & 0x5555555555555555ULL);
324 v = (v & 0x3333333333333333ULL) + ((v >> 2) & 0x3333333333333333ULL);
325 v = (v + (v >> 4)) & 0x0F0F0F0F0F0F0F0FULL;
326 return unsigned((uint64_t)(v * 0x0101010101010101ULL) >> 56);
330 /// Log2_32 - This function returns the floor log base 2 of the specified value,
331 /// -1 if the value is zero. (32 bit edition.)
332 /// Ex. Log2_32(32) == 5, Log2_32(1) == 0, Log2_32(0) == -1, Log2_32(6) == 2
333 inline unsigned Log2_32(uint32_t Value) {
334 return 31 - CountLeadingZeros_32(Value);
337 /// Log2_64 - This function returns the floor log base 2 of the specified value,
338 /// -1 if the value is zero. (64 bit edition.)
339 inline unsigned Log2_64(uint64_t Value) {
340 return 63 - CountLeadingZeros_64(Value);
343 /// Log2_32_Ceil - This function returns the ceil log base 2 of the specified
344 /// value, 32 if the value is zero. (32 bit edition).
345 /// Ex. Log2_32_Ceil(32) == 5, Log2_32_Ceil(1) == 0, Log2_32_Ceil(6) == 3
346 inline unsigned Log2_32_Ceil(uint32_t Value) {
347 return 32-CountLeadingZeros_32(Value-1);
350 /// Log2_64_Ceil - This function returns the ceil log base 2 of the specified
351 /// value, 64 if the value is zero. (64 bit edition.)
352 inline unsigned Log2_64_Ceil(uint64_t Value) {
353 return 64-CountLeadingZeros_64(Value-1);
356 /// GreatestCommonDivisor64 - Return the greatest common divisor of the two
357 /// values using Euclid's algorithm.
358 inline uint64_t GreatestCommonDivisor64(uint64_t A, uint64_t B) {
367 /// BitsToDouble - This function takes a 64-bit integer and returns the bit
368 /// equivalent double.
369 inline double BitsToDouble(uint64_t Bits) {
378 /// BitsToFloat - This function takes a 32-bit integer and returns the bit
379 /// equivalent float.
380 inline float BitsToFloat(uint32_t Bits) {
389 /// DoubleToBits - This function takes a double and returns the bit
390 /// equivalent 64-bit integer. Note that copying doubles around
391 /// changes the bits of NaNs on some hosts, notably x86, so this
392 /// routine cannot be used if these bits are needed.
393 inline uint64_t DoubleToBits(double Double) {
402 /// FloatToBits - This function takes a float and returns the bit
403 /// equivalent 32-bit integer. Note that copying floats around
404 /// changes the bits of NaNs on some hosts, notably x86, so this
405 /// routine cannot be used if these bits are needed.
406 inline uint32_t FloatToBits(float Float) {
415 /// Platform-independent wrappers for the C99 isnan() function.
419 /// Platform-independent wrappers for the C99 isinf() function.
423 /// MinAlign - A and B are either alignments or offsets. Return the minimum
424 /// alignment that may be assumed after adding the two together.
425 inline uint64_t MinAlign(uint64_t A, uint64_t B) {
426 // The largest power of 2 that divides both A and B.
427 return (A | B) & -(A | B);
430 /// NextPowerOf2 - Returns the next power of two (in 64-bits)
431 /// that is strictly greater than A. Returns zero on overflow.
432 inline uint64_t NextPowerOf2(uint64_t A) {
442 /// Returns the next integer (mod 2**64) that is greater than or equal to
443 /// \p Value and is a multiple of \p Align. \p Align must be non-zero.
447 /// RoundUpToAlignment(5, 8) = 8
448 /// RoundUpToAlignment(17, 8) = 24
449 /// RoundUpToAlignment(~0LL, 8) = 0
451 inline uint64_t RoundUpToAlignment(uint64_t Value, uint64_t Align) {
452 return ((Value + Align - 1) / Align) * Align;
455 /// Returns the offset to the next integer (mod 2**64) that is greater than
456 /// or equal to \p Value and is a multiple of \p Align. \p Align must be
458 inline uint64_t OffsetToAlignment(uint64_t Value, uint64_t Align) {
459 return RoundUpToAlignment(Value, Align) - Value;
462 /// abs64 - absolute value of a 64-bit int. Not all environments support
463 /// "abs" on whatever their name for the 64-bit int type is. The absolute
464 /// value of the largest negative number is undefined, as with "abs".
465 inline int64_t abs64(int64_t x) {
466 return (x < 0) ? -x : x;
469 /// SignExtend32 - Sign extend B-bit number x to 32-bit int.
470 /// Usage int32_t r = SignExtend32<5>(x);
471 template <unsigned B> inline int32_t SignExtend32(uint32_t x) {
472 return int32_t(x << (32 - B)) >> (32 - B);
475 /// \brief Sign extend number in the bottom B bits of X to a 32-bit int.
476 /// Requires 0 < B <= 32.
477 inline int32_t SignExtend32(uint32_t X, unsigned B) {
478 return int32_t(X << (32 - B)) >> (32 - B);
481 /// SignExtend64 - Sign extend B-bit number x to 64-bit int.
482 /// Usage int64_t r = SignExtend64<5>(x);
483 template <unsigned B> inline int64_t SignExtend64(uint64_t x) {
484 return int64_t(x << (64 - B)) >> (64 - B);
487 /// \brief Sign extend number in the bottom B bits of X to a 64-bit int.
488 /// Requires 0 < B <= 64.
489 inline int64_t SignExtend64(uint64_t X, unsigned B) {
490 return int64_t(X << (64 - B)) >> (64 - B);
493 } // End llvm namespace