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"
21 // NOTE: The following support functions use the _32/_64 extensions instead of
22 // type overloading so that signed and unsigned integers can be used without
25 /// Hi_32 - This function returns the high 32 bits of a 64 bit value.
26 inline uint32_t Hi_32(uint64_t Value) {
27 return static_cast<uint32_t>(Value >> 32);
30 /// Lo_32 - This function returns the low 32 bits of a 64 bit value.
31 inline uint32_t Lo_32(uint64_t Value) {
32 return static_cast<uint32_t>(Value);
35 /// isInt - Checks if an integer fits into the given bit width.
37 inline bool isInt(int64_t x) {
38 return N >= 64 || (-(INT64_C(1)<<(N-1)) <= x && x < (INT64_C(1)<<(N-1)));
40 // Template specializations to get better code for common cases.
42 inline bool isInt<8>(int64_t x) {
43 return static_cast<int8_t>(x) == x;
46 inline bool isInt<16>(int64_t x) {
47 return static_cast<int16_t>(x) == x;
50 inline bool isInt<32>(int64_t x) {
51 return static_cast<int32_t>(x) == x;
54 /// isShiftedInt<N,S> - Checks if a signed integer is an N bit number shifted
56 template<unsigned N, unsigned S>
57 inline bool isShiftedInt(int64_t x) {
58 return isInt<N+S>(x) && (x % (1<<S) == 0);
61 /// isUInt - Checks if an unsigned integer fits into the given bit width.
63 inline bool isUInt(uint64_t x) {
64 return N >= 64 || x < (UINT64_C(1)<<N);
66 // Template specializations to get better code for common cases.
68 inline bool isUInt<8>(uint64_t x) {
69 return static_cast<uint8_t>(x) == x;
72 inline bool isUInt<16>(uint64_t x) {
73 return static_cast<uint16_t>(x) == x;
76 inline bool isUInt<32>(uint64_t x) {
77 return static_cast<uint32_t>(x) == x;
80 /// isShiftedUInt<N,S> - Checks if a unsigned integer is an N bit number shifted
82 template<unsigned N, unsigned S>
83 inline bool isShiftedUInt(uint64_t x) {
84 return isUInt<N+S>(x) && (x % (1<<S) == 0);
87 /// isUIntN - Checks if an unsigned integer fits into the given (dynamic)
89 inline bool isUIntN(unsigned N, uint64_t x) {
90 return x == (x & (~0ULL >> (64 - N)));
93 /// isIntN - Checks if an signed integer fits into the given (dynamic)
95 inline bool isIntN(unsigned N, int64_t x) {
96 return N >= 64 || (-(INT64_C(1)<<(N-1)) <= x && x < (INT64_C(1)<<(N-1)));
99 /// isMask_32 - This function returns true if the argument is a sequence of ones
100 /// starting at the least significant bit with the remainder zero (32 bit
101 /// version). Ex. isMask_32(0x0000FFFFU) == true.
102 inline bool isMask_32(uint32_t Value) {
103 return Value && ((Value + 1) & Value) == 0;
106 /// isMask_64 - This function returns true if the argument is a sequence of ones
107 /// starting at the least significant bit with the remainder zero (64 bit
109 inline bool isMask_64(uint64_t Value) {
110 return Value && ((Value + 1) & Value) == 0;
113 /// isShiftedMask_32 - This function returns true if the argument contains a
114 /// sequence of ones with the remainder zero (32 bit version.)
115 /// Ex. isShiftedMask_32(0x0000FF00U) == true.
116 inline bool isShiftedMask_32(uint32_t Value) {
117 return isMask_32((Value - 1) | Value);
120 /// isShiftedMask_64 - This function returns true if the argument contains a
121 /// sequence of ones with the remainder zero (64 bit version.)
122 inline bool isShiftedMask_64(uint64_t Value) {
123 return isMask_64((Value - 1) | Value);
126 /// isPowerOf2_32 - This function returns true if the argument is a power of
127 /// two > 0. Ex. isPowerOf2_32(0x00100000U) == true (32 bit edition.)
128 inline bool isPowerOf2_32(uint32_t Value) {
129 return Value && !(Value & (Value - 1));
132 /// isPowerOf2_64 - This function returns true if the argument is a power of two
133 /// > 0 (64 bit edition.)
134 inline bool isPowerOf2_64(uint64_t Value) {
135 return Value && !(Value & (Value - int64_t(1L)));
138 /// ByteSwap_16 - This function returns a byte-swapped representation of the
139 /// 16-bit argument, Value.
140 inline uint16_t ByteSwap_16(uint16_t Value) {
141 return sys::SwapByteOrder_16(Value);
144 /// ByteSwap_32 - This function returns a byte-swapped representation of the
145 /// 32-bit argument, Value.
146 inline uint32_t ByteSwap_32(uint32_t Value) {
147 return sys::SwapByteOrder_32(Value);
150 /// ByteSwap_64 - This function returns a byte-swapped representation of the
151 /// 64-bit argument, Value.
152 inline uint64_t ByteSwap_64(uint64_t Value) {
153 return sys::SwapByteOrder_64(Value);
156 /// CountLeadingZeros_32 - this function performs the platform optimal form of
157 /// counting the number of zeros from the most significant bit to the first one
158 /// bit. Ex. CountLeadingZeros_32(0x00F000FF) == 8.
159 /// Returns 32 if the word is zero.
160 inline unsigned CountLeadingZeros_32(uint32_t Value) {
161 unsigned Count; // result
163 // PowerPC is defined for __builtin_clz(0)
164 #if !defined(__ppc__) && !defined(__ppc64__)
165 if (!Value) return 32;
167 Count = __builtin_clz(Value);
169 if (!Value) return 32;
171 // bisection method for count leading zeros
172 for (unsigned Shift = 32 >> 1; Shift; Shift >>= 1) {
173 uint32_t Tmp = Value >> Shift;
184 /// CountLeadingOnes_32 - this function performs the operation of
185 /// counting the number of ones from the most significant bit to the first zero
186 /// bit. Ex. CountLeadingOnes_32(0xFF0FFF00) == 8.
187 /// Returns 32 if the word is all ones.
188 inline unsigned CountLeadingOnes_32(uint32_t Value) {
189 return CountLeadingZeros_32(~Value);
192 /// CountLeadingZeros_64 - This function performs the platform optimal form
193 /// of counting the number of zeros from the most significant bit to the first
194 /// one bit (64 bit edition.)
195 /// Returns 64 if the word is zero.
196 inline unsigned CountLeadingZeros_64(uint64_t Value) {
197 unsigned Count; // result
199 // PowerPC is defined for __builtin_clzll(0)
200 #if !defined(__ppc__) && !defined(__ppc64__)
201 if (!Value) return 64;
203 Count = __builtin_clzll(Value);
205 if (sizeof(long) == sizeof(int64_t)) {
206 if (!Value) return 64;
208 // bisection method for count leading zeros
209 for (unsigned Shift = 64 >> 1; Shift; Shift >>= 1) {
210 uint64_t Tmp = Value >> Shift;
219 uint32_t Hi = Hi_32(Value);
221 // if some bits in hi portion
223 // leading zeros in hi portion plus all bits in lo portion
224 Count = CountLeadingZeros_32(Hi);
227 uint32_t Lo = Lo_32(Value);
228 // same as 32 bit value
229 Count = CountLeadingZeros_32(Lo)+32;
236 /// CountLeadingOnes_64 - This function performs the operation
237 /// of counting the number of ones from the most significant bit to the first
238 /// zero bit (64 bit edition.)
239 /// Returns 64 if the word is all ones.
240 inline unsigned CountLeadingOnes_64(uint64_t Value) {
241 return CountLeadingZeros_64(~Value);
244 /// CountTrailingZeros_32 - this function performs the platform optimal form of
245 /// counting the number of zeros from the least significant bit to the first one
246 /// bit. Ex. CountTrailingZeros_32(0xFF00FF00) == 8.
247 /// Returns 32 if the word is zero.
248 inline unsigned CountTrailingZeros_32(uint32_t Value) {
250 return Value ? __builtin_ctz(Value) : 32;
252 static const unsigned Mod37BitPosition[] = {
253 32, 0, 1, 26, 2, 23, 27, 0, 3, 16, 24, 30, 28, 11, 0, 13,
254 4, 7, 17, 0, 25, 22, 31, 15, 29, 10, 12, 6, 0, 21, 14, 9,
257 return Mod37BitPosition[(-Value & Value) % 37];
261 /// CountTrailingOnes_32 - this function performs the operation of
262 /// counting the number of ones from the least significant bit to the first zero
263 /// bit. Ex. CountTrailingOnes_32(0x00FF00FF) == 8.
264 /// Returns 32 if the word is all ones.
265 inline unsigned CountTrailingOnes_32(uint32_t Value) {
266 return CountTrailingZeros_32(~Value);
269 /// CountTrailingZeros_64 - This function performs the platform optimal form
270 /// of counting the number of zeros from the least significant bit to the first
271 /// one bit (64 bit edition.)
272 /// Returns 64 if the word is zero.
273 inline unsigned CountTrailingZeros_64(uint64_t Value) {
275 return Value ? __builtin_ctzll(Value) : 64;
277 static const unsigned Mod67Position[] = {
278 64, 0, 1, 39, 2, 15, 40, 23, 3, 12, 16, 59, 41, 19, 24, 54,
279 4, 64, 13, 10, 17, 62, 60, 28, 42, 30, 20, 51, 25, 44, 55,
280 47, 5, 32, 65, 38, 14, 22, 11, 58, 18, 53, 63, 9, 61, 27,
281 29, 50, 43, 46, 31, 37, 21, 57, 52, 8, 26, 49, 45, 36, 56,
282 7, 48, 35, 6, 34, 33, 0
284 return Mod67Position[(-Value & Value) % 67];
288 /// CountTrailingOnes_64 - This function performs the operation
289 /// of counting the number of ones from the least significant bit to the first
290 /// zero bit (64 bit edition.)
291 /// Returns 64 if the word is all ones.
292 inline unsigned CountTrailingOnes_64(uint64_t Value) {
293 return CountTrailingZeros_64(~Value);
296 /// CountPopulation_32 - this function counts the number of set bits in a value.
297 /// Ex. CountPopulation(0xF000F000) = 8
298 /// Returns 0 if the word is zero.
299 inline unsigned CountPopulation_32(uint32_t Value) {
301 return __builtin_popcount(Value);
303 uint32_t v = Value - ((Value >> 1) & 0x55555555);
304 v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
305 return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
309 /// CountPopulation_64 - this function counts the number of set bits in a value,
310 /// (64 bit edition.)
311 inline unsigned CountPopulation_64(uint64_t Value) {
313 return __builtin_popcountll(Value);
315 uint64_t v = Value - ((Value >> 1) & 0x5555555555555555ULL);
316 v = (v & 0x3333333333333333ULL) + ((v >> 2) & 0x3333333333333333ULL);
317 v = (v + (v >> 4)) & 0x0F0F0F0F0F0F0F0FULL;
318 return unsigned((uint64_t)(v * 0x0101010101010101ULL) >> 56);
322 /// Log2_32 - This function returns the floor log base 2 of the specified value,
323 /// -1 if the value is zero. (32 bit edition.)
324 /// Ex. Log2_32(32) == 5, Log2_32(1) == 0, Log2_32(0) == -1, Log2_32(6) == 2
325 inline unsigned Log2_32(uint32_t Value) {
326 return 31 - CountLeadingZeros_32(Value);
329 /// Log2_64 - This function returns the floor log base 2 of the specified value,
330 /// -1 if the value is zero. (64 bit edition.)
331 inline unsigned Log2_64(uint64_t Value) {
332 return 63 - CountLeadingZeros_64(Value);
335 /// Log2_32_Ceil - This function returns the ceil log base 2 of the specified
336 /// value, 32 if the value is zero. (32 bit edition).
337 /// Ex. Log2_32_Ceil(32) == 5, Log2_32_Ceil(1) == 0, Log2_32_Ceil(6) == 3
338 inline unsigned Log2_32_Ceil(uint32_t Value) {
339 return 32-CountLeadingZeros_32(Value-1);
342 /// Log2_64_Ceil - This function returns the ceil log base 2 of the specified
343 /// value, 64 if the value is zero. (64 bit edition.)
344 inline unsigned Log2_64_Ceil(uint64_t Value) {
345 return 64-CountLeadingZeros_64(Value-1);
348 /// GreatestCommonDivisor64 - Return the greatest common divisor of the two
349 /// values using Euclid's algorithm.
350 inline uint64_t GreatestCommonDivisor64(uint64_t A, uint64_t B) {
359 /// BitsToDouble - This function takes a 64-bit integer and returns the bit
360 /// equivalent double.
361 inline double BitsToDouble(uint64_t Bits) {
370 /// BitsToFloat - This function takes a 32-bit integer and returns the bit
371 /// equivalent float.
372 inline float BitsToFloat(uint32_t Bits) {
381 /// DoubleToBits - This function takes a double and returns the bit
382 /// equivalent 64-bit integer. Note that copying doubles around
383 /// changes the bits of NaNs on some hosts, notably x86, so this
384 /// routine cannot be used if these bits are needed.
385 inline uint64_t DoubleToBits(double Double) {
394 /// FloatToBits - This function takes a float and returns the bit
395 /// equivalent 32-bit integer. Note that copying floats around
396 /// changes the bits of NaNs on some hosts, notably x86, so this
397 /// routine cannot be used if these bits are needed.
398 inline uint32_t FloatToBits(float Float) {
407 /// Platform-independent wrappers for the C99 isnan() function.
411 /// Platform-independent wrappers for the C99 isinf() function.
415 /// MinAlign - A and B are either alignments or offsets. Return the minimum
416 /// alignment that may be assumed after adding the two together.
417 inline uint64_t MinAlign(uint64_t A, uint64_t B) {
418 // The largest power of 2 that divides both A and B.
419 return (A | B) & -(A | B);
422 /// NextPowerOf2 - Returns the next power of two (in 64-bits)
423 /// that is strictly greater than A. Returns zero on overflow.
424 inline uint64_t NextPowerOf2(uint64_t A) {
434 /// Returns the next integer (mod 2**64) that is greater than or equal to
435 /// \p Value and is a multiple of \p Align. \p Align must be non-zero.
439 /// RoundUpToAlignment(5, 8) = 8
440 /// RoundUpToAlignment(17, 8) = 24
441 /// RoundUpToAlignment(~0LL, 8) = 0
443 inline uint64_t RoundUpToAlignment(uint64_t Value, uint64_t Align) {
444 return ((Value + Align - 1) / Align) * Align;
447 /// Returns the offset to the next integer (mod 2**64) that is greater than
448 /// or equal to \p Value and is a multiple of \p Align. \p Align must be
450 inline uint64_t OffsetToAlignment(uint64_t Value, uint64_t Align) {
451 return RoundUpToAlignment(Value, Align) - Value;
454 /// abs64 - absolute value of a 64-bit int. Not all environments support
455 /// "abs" on whatever their name for the 64-bit int type is. The absolute
456 /// value of the largest negative number is undefined, as with "abs".
457 inline int64_t abs64(int64_t x) {
458 return (x < 0) ? -x : x;
461 /// SignExtend32 - Sign extend B-bit number x to 32-bit int.
462 /// Usage int32_t r = SignExtend32<5>(x);
463 template <unsigned B> inline int32_t SignExtend32(uint32_t x) {
464 return int32_t(x << (32 - B)) >> (32 - B);
467 /// \brief Sign extend number in the bottom B bits of X to a 32-bit int.
468 /// Requires 0 < B <= 32.
469 inline int32_t SignExtend32(uint32_t X, unsigned B) {
470 return int32_t(X << (32 - B)) >> (32 - B);
473 /// SignExtend64 - Sign extend B-bit number x to 64-bit int.
474 /// Usage int64_t r = SignExtend64<5>(x);
475 template <unsigned B> inline int64_t SignExtend64(uint64_t x) {
476 return int64_t(x << (64 - B)) >> (64 - B);
479 /// \brief Sign extend number in the bottom B bits of X to a 64-bit int.
480 /// Requires 0 < B <= 64.
481 inline int64_t SignExtend64(uint64_t X, unsigned B) {
482 return int64_t(X << (64 - B)) >> (64 - B);
485 } // End llvm namespace