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/System/DataTypes.h"
18 #include "llvm/System/SwapByteOrder.h"
22 // NOTE: The following support functions use the _32/_64 extensions instead of
23 // type overloading so that signed and unsigned integers can be used without
26 /// Hi_32 - This function returns the high 32 bits of a 64 bit value.
27 inline uint32_t Hi_32(uint64_t Value) {
28 return static_cast<uint32_t>(Value >> 32);
31 /// Lo_32 - This function returns the low 32 bits of a 64 bit value.
32 inline uint32_t Lo_32(uint64_t Value) {
33 return static_cast<uint32_t>(Value);
36 /// isInt - Checks if an integer fits into the given bit width.
38 inline bool isInt(int64_t x) {
39 return N >= 64 || (-(INT64_C(1)<<(N-1)) <= x && x < (INT64_C(1)<<(N-1)));
41 // Template specializations to get better code for common cases.
43 inline bool isInt<8>(int64_t x) {
44 return static_cast<int8_t>(x) == x;
47 inline bool isInt<16>(int64_t x) {
48 return static_cast<int16_t>(x) == x;
51 inline bool isInt<32>(int64_t x) {
52 return static_cast<int32_t>(x) == x;
55 /// isUInt - Checks if an unsigned integer fits into the given bit width.
57 inline bool isUInt(uint64_t x) {
58 return N >= 64 || x < (UINT64_C(1)<<N);
60 // Template specializations to get better code for common cases.
62 inline bool isUInt<8>(uint64_t x) {
63 return static_cast<uint8_t>(x) == x;
66 inline bool isUInt<16>(uint64_t x) {
67 return static_cast<uint16_t>(x) == x;
70 inline bool isUInt<32>(uint64_t x) {
71 return static_cast<uint32_t>(x) == x;
74 /// isUIntN - Checks if an unsigned integer fits into the given (dynamic)
76 inline bool isUIntN(unsigned N, uint64_t x) {
77 return x == (x & (~0ULL >> (64 - N)));
80 /// isMask_32 - This function returns true if the argument is a sequence of ones
81 /// starting at the least significant bit with the remainder zero (32 bit
82 /// version). Ex. isMask_32(0x0000FFFFU) == true.
83 inline bool isMask_32(uint32_t Value) {
84 return Value && ((Value + 1) & Value) == 0;
87 /// isMask_64 - This function returns true if the argument is a sequence of ones
88 /// starting at the least significant bit with the remainder zero (64 bit
90 inline bool isMask_64(uint64_t Value) {
91 return Value && ((Value + 1) & Value) == 0;
94 /// isShiftedMask_32 - This function returns true if the argument contains a
95 /// sequence of ones with the remainder zero (32 bit version.)
96 /// Ex. isShiftedMask_32(0x0000FF00U) == true.
97 inline bool isShiftedMask_32(uint32_t Value) {
98 return isMask_32((Value - 1) | Value);
101 /// isShiftedMask_64 - This function returns true if the argument contains a
102 /// sequence of ones with the remainder zero (64 bit version.)
103 inline bool isShiftedMask_64(uint64_t Value) {
104 return isMask_64((Value - 1) | Value);
107 /// isPowerOf2_32 - This function returns true if the argument is a power of
108 /// two > 0. Ex. isPowerOf2_32(0x00100000U) == true (32 bit edition.)
109 inline bool isPowerOf2_32(uint32_t Value) {
110 return Value && !(Value & (Value - 1));
113 /// isPowerOf2_64 - This function returns true if the argument is a power of two
114 /// > 0 (64 bit edition.)
115 inline bool isPowerOf2_64(uint64_t Value) {
116 return Value && !(Value & (Value - int64_t(1L)));
119 /// ByteSwap_16 - This function returns a byte-swapped representation of the
120 /// 16-bit argument, Value.
121 inline uint16_t ByteSwap_16(uint16_t Value) {
122 return sys::SwapByteOrder(Value);
125 /// ByteSwap_32 - This function returns a byte-swapped representation of the
126 /// 32-bit argument, Value.
127 inline uint32_t ByteSwap_32(uint32_t Value) {
128 return sys::SwapByteOrder(Value);
131 /// ByteSwap_64 - This function returns a byte-swapped representation of the
132 /// 64-bit argument, Value.
133 inline uint64_t ByteSwap_64(uint64_t Value) {
134 return sys::SwapByteOrder(Value);
137 /// CountLeadingZeros_32 - this function performs the platform optimal form of
138 /// counting the number of zeros from the most significant bit to the first one
139 /// bit. Ex. CountLeadingZeros_32(0x00F000FF) == 8.
140 /// Returns 32 if the word is zero.
141 inline unsigned CountLeadingZeros_32(uint32_t Value) {
142 unsigned Count; // result
144 // PowerPC is defined for __builtin_clz(0)
145 #if !defined(__ppc__) && !defined(__ppc64__)
146 if (!Value) return 32;
148 Count = __builtin_clz(Value);
150 if (!Value) return 32;
152 // bisection method for count leading zeros
153 for (unsigned Shift = 32 >> 1; Shift; Shift >>= 1) {
154 uint32_t Tmp = Value >> Shift;
165 /// CountLeadingOnes_32 - this function performs the operation of
166 /// counting the number of ones from the most significant bit to the first zero
167 /// bit. Ex. CountLeadingOnes_32(0xFF0FFF00) == 8.
168 /// Returns 32 if the word is all ones.
169 inline unsigned CountLeadingOnes_32(uint32_t Value) {
170 return CountLeadingZeros_32(~Value);
173 /// CountLeadingZeros_64 - This function performs the platform optimal form
174 /// of counting the number of zeros from the most significant bit to the first
175 /// one bit (64 bit edition.)
176 /// Returns 64 if the word is zero.
177 inline unsigned CountLeadingZeros_64(uint64_t Value) {
178 unsigned Count; // result
180 // PowerPC is defined for __builtin_clzll(0)
181 #if !defined(__ppc__) && !defined(__ppc64__)
182 if (!Value) return 64;
184 Count = __builtin_clzll(Value);
186 if (sizeof(long) == sizeof(int64_t)) {
187 if (!Value) return 64;
189 // bisection method for count leading zeros
190 for (unsigned Shift = 64 >> 1; Shift; Shift >>= 1) {
191 uint64_t Tmp = Value >> Shift;
200 uint32_t Hi = Hi_32(Value);
202 // if some bits in hi portion
204 // leading zeros in hi portion plus all bits in lo portion
205 Count = CountLeadingZeros_32(Hi);
208 uint32_t Lo = Lo_32(Value);
209 // same as 32 bit value
210 Count = CountLeadingZeros_32(Lo)+32;
217 /// CountLeadingOnes_64 - This function performs the operation
218 /// of counting the number of ones from the most significant bit to the first
219 /// zero bit (64 bit edition.)
220 /// Returns 64 if the word is all ones.
221 inline unsigned CountLeadingOnes_64(uint64_t Value) {
222 return CountLeadingZeros_64(~Value);
225 /// CountTrailingZeros_32 - this function performs the platform optimal form of
226 /// counting the number of zeros from the least significant bit to the first one
227 /// bit. Ex. CountTrailingZeros_32(0xFF00FF00) == 8.
228 /// Returns 32 if the word is zero.
229 inline unsigned CountTrailingZeros_32(uint32_t Value) {
231 return Value ? __builtin_ctz(Value) : 32;
233 static const unsigned Mod37BitPosition[] = {
234 32, 0, 1, 26, 2, 23, 27, 0, 3, 16, 24, 30, 28, 11, 0, 13,
235 4, 7, 17, 0, 25, 22, 31, 15, 29, 10, 12, 6, 0, 21, 14, 9,
238 return Mod37BitPosition[(-Value & Value) % 37];
242 /// CountTrailingOnes_32 - this function performs the operation of
243 /// counting the number of ones from the least significant bit to the first zero
244 /// bit. Ex. CountTrailingOnes_32(0x00FF00FF) == 8.
245 /// Returns 32 if the word is all ones.
246 inline unsigned CountTrailingOnes_32(uint32_t Value) {
247 return CountTrailingZeros_32(~Value);
250 /// CountTrailingZeros_64 - This function performs the platform optimal form
251 /// of counting the number of zeros from the least significant bit to the first
252 /// one bit (64 bit edition.)
253 /// Returns 64 if the word is zero.
254 inline unsigned CountTrailingZeros_64(uint64_t Value) {
256 return Value ? __builtin_ctzll(Value) : 64;
258 static const unsigned Mod67Position[] = {
259 64, 0, 1, 39, 2, 15, 40, 23, 3, 12, 16, 59, 41, 19, 24, 54,
260 4, 64, 13, 10, 17, 62, 60, 28, 42, 30, 20, 51, 25, 44, 55,
261 47, 5, 32, 65, 38, 14, 22, 11, 58, 18, 53, 63, 9, 61, 27,
262 29, 50, 43, 46, 31, 37, 21, 57, 52, 8, 26, 49, 45, 36, 56,
263 7, 48, 35, 6, 34, 33, 0
265 return Mod67Position[(-Value & Value) % 67];
269 /// CountTrailingOnes_64 - This function performs the operation
270 /// of counting the number of ones from the least significant bit to the first
271 /// zero bit (64 bit edition.)
272 /// Returns 64 if the word is all ones.
273 inline unsigned CountTrailingOnes_64(uint64_t Value) {
274 return CountTrailingZeros_64(~Value);
277 /// CountPopulation_32 - this function counts the number of set bits in a value.
278 /// Ex. CountPopulation(0xF000F000) = 8
279 /// Returns 0 if the word is zero.
280 inline unsigned CountPopulation_32(uint32_t Value) {
282 return __builtin_popcount(Value);
284 uint32_t v = Value - ((Value >> 1) & 0x55555555);
285 v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
286 return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
290 /// CountPopulation_64 - this function counts the number of set bits in a value,
291 /// (64 bit edition.)
292 inline unsigned CountPopulation_64(uint64_t Value) {
294 return __builtin_popcountll(Value);
296 uint64_t v = Value - ((Value >> 1) & 0x5555555555555555ULL);
297 v = (v & 0x3333333333333333ULL) + ((v >> 2) & 0x3333333333333333ULL);
298 v = (v + (v >> 4)) & 0x0F0F0F0F0F0F0F0FULL;
299 return unsigned((uint64_t)(v * 0x0101010101010101ULL) >> 56);
303 /// Log2_32 - This function returns the floor log base 2 of the specified value,
304 /// -1 if the value is zero. (32 bit edition.)
305 /// Ex. Log2_32(32) == 5, Log2_32(1) == 0, Log2_32(0) == -1, Log2_32(6) == 2
306 inline unsigned Log2_32(uint32_t Value) {
307 return 31 - CountLeadingZeros_32(Value);
310 /// Log2_64 - This function returns the floor log base 2 of the specified value,
311 /// -1 if the value is zero. (64 bit edition.)
312 inline unsigned Log2_64(uint64_t Value) {
313 return 63 - CountLeadingZeros_64(Value);
316 /// Log2_32_Ceil - This function returns the ceil log base 2 of the specified
317 /// value, 32 if the value is zero. (32 bit edition).
318 /// Ex. Log2_32_Ceil(32) == 5, Log2_32_Ceil(1) == 0, Log2_32_Ceil(6) == 3
319 inline unsigned Log2_32_Ceil(uint32_t Value) {
320 return 32-CountLeadingZeros_32(Value-1);
323 /// Log2_64_Ceil - This function returns the ceil log base 2 of the specified
324 /// value, 64 if the value is zero. (64 bit edition.)
325 inline unsigned Log2_64_Ceil(uint64_t Value) {
326 return 64-CountLeadingZeros_64(Value-1);
329 /// GreatestCommonDivisor64 - Return the greatest common divisor of the two
330 /// values using Euclid's algorithm.
331 inline uint64_t GreatestCommonDivisor64(uint64_t A, uint64_t B) {
340 /// BitsToDouble - This function takes a 64-bit integer and returns the bit
341 /// equivalent double.
342 inline double BitsToDouble(uint64_t Bits) {
351 /// BitsToFloat - This function takes a 32-bit integer and returns the bit
352 /// equivalent float.
353 inline float BitsToFloat(uint32_t Bits) {
362 /// DoubleToBits - This function takes a double and returns the bit
363 /// equivalent 64-bit integer. Note that copying doubles around
364 /// changes the bits of NaNs on some hosts, notably x86, so this
365 /// routine cannot be used if these bits are needed.
366 inline uint64_t DoubleToBits(double Double) {
375 /// FloatToBits - This function takes a float and returns the bit
376 /// equivalent 32-bit integer. Note that copying floats around
377 /// changes the bits of NaNs on some hosts, notably x86, so this
378 /// routine cannot be used if these bits are needed.
379 inline uint32_t FloatToBits(float Float) {
388 /// Platform-independent wrappers for the C99 isnan() function.
392 /// Platform-independent wrappers for the C99 isinf() function.
396 /// MinAlign - A and B are either alignments or offsets. Return the minimum
397 /// alignment that may be assumed after adding the two together.
398 static inline uint64_t MinAlign(uint64_t A, uint64_t B) {
399 // The largest power of 2 that divides both A and B.
400 return (A | B) & -(A | B);
403 /// NextPowerOf2 - Returns the next power of two (in 64-bits)
404 /// that is strictly greater than A. Returns zero on overflow.
405 static inline uint64_t NextPowerOf2(uint64_t A) {
415 /// RoundUpToAlignment - Returns the next integer (mod 2**64) that is
416 /// greater than or equal to \arg Value and is a multiple of \arg
417 /// Align. Align must be non-zero.
420 /// RoundUpToAlignment(5, 8) = 8
421 /// RoundUpToAlignment(17, 8) = 24
422 /// RoundUpToAlignment(~0LL, 8) = 0
423 inline uint64_t RoundUpToAlignment(uint64_t Value, uint64_t Align) {
424 return ((Value + Align - 1) / Align) * Align;
427 /// OffsetToAlignment - Return the offset to the next integer (mod 2**64) that
428 /// is greater than or equal to \arg Value and is a multiple of \arg
429 /// Align. Align must be non-zero.
430 inline uint64_t OffsetToAlignment(uint64_t Value, uint64_t Align) {
431 return RoundUpToAlignment(Value, Align) - Value;
434 /// abs64 - absolute value of a 64-bit int. Not all environments support
435 /// "abs" on whatever their name for the 64-bit int type is. The absolute
436 /// value of the largest negative number is undefined, as with "abs".
437 inline int64_t abs64(int64_t x) {
438 return (x < 0) ? -x : x;
441 /// SignExtend32 - Sign extend B-bit number x to 32-bit int.
442 /// Usage int32_t r = SignExtend32<5>(x);
443 template <unsigned B> inline int32_t SignExtend32(uint32_t x) {
444 return int32_t(x << (32 - B)) >> (32 - B);
447 /// SignExtend64 - Sign extend B-bit number x to 64-bit int.
448 /// Usage int64_t r = SignExtend64<5>(x);
449 template <unsigned B> inline int64_t SignExtend64(uint64_t x) {
450 return int64_t(x << (64 - B)) >> (64 - B);
453 } // End llvm namespace