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 /// isUInt - Checks if an unsigned integer fits into the given bit width.
56 inline bool isUInt(uint64_t x) {
57 return N >= 64 || x < (UINT64_C(1)<<N);
59 // Template specializations to get better code for common cases.
61 inline bool isUInt<8>(uint64_t x) {
62 return static_cast<uint8_t>(x) == x;
65 inline bool isUInt<16>(uint64_t x) {
66 return static_cast<uint16_t>(x) == x;
69 inline bool isUInt<32>(uint64_t x) {
70 return static_cast<uint32_t>(x) == x;
73 /// isUIntN - Checks if an unsigned integer fits into the given (dynamic)
75 inline bool isUIntN(unsigned N, uint64_t x) {
76 return x == (x & (~0ULL >> (64 - N)));
79 /// isMask_32 - This function returns true if the argument is a sequence of ones
80 /// starting at the least significant bit with the remainder zero (32 bit
81 /// version). Ex. isMask_32(0x0000FFFFU) == true.
82 inline bool isMask_32(uint32_t Value) {
83 return Value && ((Value + 1) & Value) == 0;
86 /// isMask_64 - This function returns true if the argument is a sequence of ones
87 /// starting at the least significant bit with the remainder zero (64 bit
89 inline bool isMask_64(uint64_t Value) {
90 return Value && ((Value + 1) & Value) == 0;
93 /// isShiftedMask_32 - This function returns true if the argument contains a
94 /// sequence of ones with the remainder zero (32 bit version.)
95 /// Ex. isShiftedMask_32(0x0000FF00U) == true.
96 inline bool isShiftedMask_32(uint32_t Value) {
97 return isMask_32((Value - 1) | Value);
100 /// isShiftedMask_64 - This function returns true if the argument contains a
101 /// sequence of ones with the remainder zero (64 bit version.)
102 inline bool isShiftedMask_64(uint64_t Value) {
103 return isMask_64((Value - 1) | Value);
106 /// isPowerOf2_32 - This function returns true if the argument is a power of
107 /// two > 0. Ex. isPowerOf2_32(0x00100000U) == true (32 bit edition.)
108 inline bool isPowerOf2_32(uint32_t Value) {
109 return Value && !(Value & (Value - 1));
112 /// isPowerOf2_64 - This function returns true if the argument is a power of two
113 /// > 0 (64 bit edition.)
114 inline bool isPowerOf2_64(uint64_t Value) {
115 return Value && !(Value & (Value - int64_t(1L)));
118 /// ByteSwap_16 - This function returns a byte-swapped representation of the
119 /// 16-bit argument, Value.
120 inline uint16_t ByteSwap_16(uint16_t Value) {
121 return sys::SwapByteOrder_16(Value);
124 /// ByteSwap_32 - This function returns a byte-swapped representation of the
125 /// 32-bit argument, Value.
126 inline uint32_t ByteSwap_32(uint32_t Value) {
127 return sys::SwapByteOrder_32(Value);
130 /// ByteSwap_64 - This function returns a byte-swapped representation of the
131 /// 64-bit argument, Value.
132 inline uint64_t ByteSwap_64(uint64_t Value) {
133 return sys::SwapByteOrder_64(Value);
136 /// CountLeadingZeros_32 - this function performs the platform optimal form of
137 /// counting the number of zeros from the most significant bit to the first one
138 /// bit. Ex. CountLeadingZeros_32(0x00F000FF) == 8.
139 /// Returns 32 if the word is zero.
140 inline unsigned CountLeadingZeros_32(uint32_t Value) {
141 unsigned Count; // result
143 // PowerPC is defined for __builtin_clz(0)
144 #if !defined(__ppc__) && !defined(__ppc64__)
145 if (!Value) return 32;
147 Count = __builtin_clz(Value);
149 if (!Value) return 32;
151 // bisection method for count leading zeros
152 for (unsigned Shift = 32 >> 1; Shift; Shift >>= 1) {
153 uint32_t Tmp = Value >> Shift;
164 /// CountLeadingOnes_32 - this function performs the operation of
165 /// counting the number of ones from the most significant bit to the first zero
166 /// bit. Ex. CountLeadingOnes_32(0xFF0FFF00) == 8.
167 /// Returns 32 if the word is all ones.
168 inline unsigned CountLeadingOnes_32(uint32_t Value) {
169 return CountLeadingZeros_32(~Value);
172 /// CountLeadingZeros_64 - This function performs the platform optimal form
173 /// of counting the number of zeros from the most significant bit to the first
174 /// one bit (64 bit edition.)
175 /// Returns 64 if the word is zero.
176 inline unsigned CountLeadingZeros_64(uint64_t Value) {
177 unsigned Count; // result
179 // PowerPC is defined for __builtin_clzll(0)
180 #if !defined(__ppc__) && !defined(__ppc64__)
181 if (!Value) return 64;
183 Count = __builtin_clzll(Value);
185 if (sizeof(long) == sizeof(int64_t)) {
186 if (!Value) return 64;
188 // bisection method for count leading zeros
189 for (unsigned Shift = 64 >> 1; Shift; Shift >>= 1) {
190 uint64_t Tmp = Value >> Shift;
199 uint32_t Hi = Hi_32(Value);
201 // if some bits in hi portion
203 // leading zeros in hi portion plus all bits in lo portion
204 Count = CountLeadingZeros_32(Hi);
207 uint32_t Lo = Lo_32(Value);
208 // same as 32 bit value
209 Count = CountLeadingZeros_32(Lo)+32;
216 /// CountLeadingOnes_64 - This function performs the operation
217 /// of counting the number of ones from the most significant bit to the first
218 /// zero bit (64 bit edition.)
219 /// Returns 64 if the word is all ones.
220 inline unsigned CountLeadingOnes_64(uint64_t Value) {
221 return CountLeadingZeros_64(~Value);
224 /// CountTrailingZeros_32 - this function performs the platform optimal form of
225 /// counting the number of zeros from the least significant bit to the first one
226 /// bit. Ex. CountTrailingZeros_32(0xFF00FF00) == 8.
227 /// Returns 32 if the word is zero.
228 inline unsigned CountTrailingZeros_32(uint32_t Value) {
230 return Value ? __builtin_ctz(Value) : 32;
232 static const unsigned Mod37BitPosition[] = {
233 32, 0, 1, 26, 2, 23, 27, 0, 3, 16, 24, 30, 28, 11, 0, 13,
234 4, 7, 17, 0, 25, 22, 31, 15, 29, 10, 12, 6, 0, 21, 14, 9,
237 return Mod37BitPosition[(-Value & Value) % 37];
241 /// CountTrailingOnes_32 - this function performs the operation of
242 /// counting the number of ones from the least significant bit to the first zero
243 /// bit. Ex. CountTrailingOnes_32(0x00FF00FF) == 8.
244 /// Returns 32 if the word is all ones.
245 inline unsigned CountTrailingOnes_32(uint32_t Value) {
246 return CountTrailingZeros_32(~Value);
249 /// CountTrailingZeros_64 - This function performs the platform optimal form
250 /// of counting the number of zeros from the least significant bit to the first
251 /// one bit (64 bit edition.)
252 /// Returns 64 if the word is zero.
253 inline unsigned CountTrailingZeros_64(uint64_t Value) {
255 return Value ? __builtin_ctzll(Value) : 64;
257 static const unsigned Mod67Position[] = {
258 64, 0, 1, 39, 2, 15, 40, 23, 3, 12, 16, 59, 41, 19, 24, 54,
259 4, 64, 13, 10, 17, 62, 60, 28, 42, 30, 20, 51, 25, 44, 55,
260 47, 5, 32, 65, 38, 14, 22, 11, 58, 18, 53, 63, 9, 61, 27,
261 29, 50, 43, 46, 31, 37, 21, 57, 52, 8, 26, 49, 45, 36, 56,
262 7, 48, 35, 6, 34, 33, 0
264 return Mod67Position[(-Value & Value) % 67];
268 /// CountTrailingOnes_64 - This function performs the operation
269 /// of counting the number of ones from the least significant bit to the first
270 /// zero bit (64 bit edition.)
271 /// Returns 64 if the word is all ones.
272 inline unsigned CountTrailingOnes_64(uint64_t Value) {
273 return CountTrailingZeros_64(~Value);
276 /// CountPopulation_32 - this function counts the number of set bits in a value.
277 /// Ex. CountPopulation(0xF000F000) = 8
278 /// Returns 0 if the word is zero.
279 inline unsigned CountPopulation_32(uint32_t Value) {
281 return __builtin_popcount(Value);
283 uint32_t v = Value - ((Value >> 1) & 0x55555555);
284 v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
285 return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
289 /// CountPopulation_64 - this function counts the number of set bits in a value,
290 /// (64 bit edition.)
291 inline unsigned CountPopulation_64(uint64_t Value) {
293 return __builtin_popcountll(Value);
295 uint64_t v = Value - ((Value >> 1) & 0x5555555555555555ULL);
296 v = (v & 0x3333333333333333ULL) + ((v >> 2) & 0x3333333333333333ULL);
297 v = (v + (v >> 4)) & 0x0F0F0F0F0F0F0F0FULL;
298 return unsigned((uint64_t)(v * 0x0101010101010101ULL) >> 56);
302 /// Log2_32 - This function returns the floor log base 2 of the specified value,
303 /// -1 if the value is zero. (32 bit edition.)
304 /// Ex. Log2_32(32) == 5, Log2_32(1) == 0, Log2_32(0) == -1, Log2_32(6) == 2
305 inline unsigned Log2_32(uint32_t Value) {
306 return 31 - CountLeadingZeros_32(Value);
309 /// Log2_64 - This function returns the floor log base 2 of the specified value,
310 /// -1 if the value is zero. (64 bit edition.)
311 inline unsigned Log2_64(uint64_t Value) {
312 return 63 - CountLeadingZeros_64(Value);
315 /// Log2_32_Ceil - This function returns the ceil log base 2 of the specified
316 /// value, 32 if the value is zero. (32 bit edition).
317 /// Ex. Log2_32_Ceil(32) == 5, Log2_32_Ceil(1) == 0, Log2_32_Ceil(6) == 3
318 inline unsigned Log2_32_Ceil(uint32_t Value) {
319 return 32-CountLeadingZeros_32(Value-1);
322 /// Log2_64_Ceil - This function returns the ceil log base 2 of the specified
323 /// value, 64 if the value is zero. (64 bit edition.)
324 inline unsigned Log2_64_Ceil(uint64_t Value) {
325 return 64-CountLeadingZeros_64(Value-1);
328 /// GreatestCommonDivisor64 - Return the greatest common divisor of the two
329 /// values using Euclid's algorithm.
330 inline uint64_t GreatestCommonDivisor64(uint64_t A, uint64_t B) {
339 /// BitsToDouble - This function takes a 64-bit integer and returns the bit
340 /// equivalent double.
341 inline double BitsToDouble(uint64_t Bits) {
350 /// BitsToFloat - This function takes a 32-bit integer and returns the bit
351 /// equivalent float.
352 inline float BitsToFloat(uint32_t Bits) {
361 /// DoubleToBits - This function takes a double and returns the bit
362 /// equivalent 64-bit integer. Note that copying doubles around
363 /// changes the bits of NaNs on some hosts, notably x86, so this
364 /// routine cannot be used if these bits are needed.
365 inline uint64_t DoubleToBits(double Double) {
374 /// FloatToBits - This function takes a float and returns the bit
375 /// equivalent 32-bit integer. Note that copying floats around
376 /// changes the bits of NaNs on some hosts, notably x86, so this
377 /// routine cannot be used if these bits are needed.
378 inline uint32_t FloatToBits(float Float) {
387 /// Platform-independent wrappers for the C99 isnan() function.
391 /// Platform-independent wrappers for the C99 isinf() function.
395 /// MinAlign - A and B are either alignments or offsets. Return the minimum
396 /// alignment that may be assumed after adding the two together.
397 static inline uint64_t MinAlign(uint64_t A, uint64_t B) {
398 // The largest power of 2 that divides both A and B.
399 return (A | B) & -(A | B);
402 /// NextPowerOf2 - Returns the next power of two (in 64-bits)
403 /// that is strictly greater than A. Returns zero on overflow.
404 static inline uint64_t NextPowerOf2(uint64_t A) {
414 /// RoundUpToAlignment - Returns the next integer (mod 2**64) that is
415 /// greater than or equal to \arg Value and is a multiple of \arg
416 /// Align. Align must be non-zero.
419 /// RoundUpToAlignment(5, 8) = 8
420 /// RoundUpToAlignment(17, 8) = 24
421 /// RoundUpToAlignment(~0LL, 8) = 0
422 inline uint64_t RoundUpToAlignment(uint64_t Value, uint64_t Align) {
423 return ((Value + Align - 1) / Align) * Align;
426 /// OffsetToAlignment - Return the offset to the next integer (mod 2**64) that
427 /// is greater than or equal to \arg Value and is a multiple of \arg
428 /// Align. Align must be non-zero.
429 inline uint64_t OffsetToAlignment(uint64_t Value, uint64_t Align) {
430 return RoundUpToAlignment(Value, Align) - Value;
433 /// abs64 - absolute value of a 64-bit int. Not all environments support
434 /// "abs" on whatever their name for the 64-bit int type is. The absolute
435 /// value of the largest negative number is undefined, as with "abs".
436 inline int64_t abs64(int64_t x) {
437 return (x < 0) ? -x : x;
440 /// SignExtend32 - Sign extend B-bit number x to 32-bit int.
441 /// Usage int32_t r = SignExtend32<5>(x);
442 template <unsigned B> inline int32_t SignExtend32(uint32_t x) {
443 return int32_t(x << (32 - B)) >> (32 - B);
446 /// SignExtend64 - Sign extend B-bit number x to 64-bit int.
447 /// Usage int64_t r = SignExtend64<5>(x);
448 template <unsigned B> inline int64_t SignExtend64(uint64_t x) {
449 return int64_t(x << (64 - B)) >> (64 - B);
452 } // End llvm namespace