1 //===-- llvm/Support/MathExtras.h - Useful math functions -------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file was developed by the LLVM research group and is distributed under
6 // the University of Illinois Open Source 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/DataTypes.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 unsigned Hi_32(uint64_t Value) {
27 return static_cast<unsigned>(Value >> 32);
30 /// Lo_32 - This function returns the low 32 bits of a 64 bit value.
31 inline unsigned Lo_32(uint64_t Value) {
32 return static_cast<unsigned>(Value);
35 /// is?Type - these functions produce optimal testing for integer data types.
36 inline bool isInt8 (int64_t Value) {
37 return static_cast<signed char>(Value) == Value;
39 inline bool isUInt8 (int64_t Value) {
40 return static_cast<unsigned char>(Value) == Value;
42 inline bool isInt16 (int64_t Value) {
43 return static_cast<signed short>(Value) == Value;
45 inline bool isUInt16(int64_t Value) {
46 return static_cast<unsigned short>(Value) == Value;
48 inline bool isInt32 (int64_t Value) {
49 return static_cast<signed int>(Value) == Value;
51 inline bool isUInt32(int64_t Value) {
52 return static_cast<unsigned int>(Value) == Value;
55 /// isMask_32 - This function returns true if the argument is a sequence of ones
56 /// starting at the least significant bit with the remainder zero (32 bit
57 /// version). Ex. isMask_32(0x0000FFFFU) == true.
58 inline const bool isMask_32(unsigned Value) {
59 return Value && ((Value + 1) & Value) == 0;
62 /// isMask_64 - This function returns true if the argument is a sequence of ones
63 /// starting at the least significant bit with the remainder zero (64 bit
65 inline const bool isMask_64(uint64_t Value) {
66 return Value && ((Value + 1) & Value) == 0;
69 /// isShiftedMask_32 - This function returns true if the argument contains a
70 /// sequence of ones with the remainder zero (32 bit version.)
71 /// Ex. isShiftedMask_32(0x0000FF00U) == true.
72 inline const bool isShiftedMask_32(unsigned Value) {
73 return isMask_32((Value - 1) | Value);
76 /// isShiftedMask_64 - This function returns true if the argument contains a
77 /// sequence of ones with the remainder zero (64 bit version.)
78 inline const bool isShiftedMask_64(uint64_t Value) {
79 return isMask_64((Value - 1) | Value);
82 /// isPowerOf2_32 - This function returns true if the argument is a power of
83 /// two > 0. Ex. isPowerOf2_32(0x00100000U) == true (32 bit edition.)
84 inline bool isPowerOf2_32(unsigned Value) {
85 return Value && !(Value & (Value - 1));
88 /// isPowerOf2_64 - This function returns true if the argument is a power of two
89 /// > 0 (64 bit edition.)
90 inline bool isPowerOf2_64(uint64_t Value) {
91 return Value && !(Value & (Value - int64_t(1L)));
94 /// ByteSwap_16 - This function returns a byte-swapped representation of the
95 /// 16-bit argument, Value.
96 inline unsigned short ByteSwap_16(unsigned short Value) {
97 unsigned short Hi = Value << 8;
98 unsigned short Lo = Value >> 8;
102 /// ByteSwap_32 - This function returns a byte-swapped representation of the
103 /// 32-bit argument, Value.
104 inline unsigned ByteSwap_32(unsigned Value) {
105 #if __GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 3)
106 return __builtin_bswap32(Value);
108 unsigned Byte0 = Value & 0x000000FF;
109 unsigned Byte1 = Value & 0x0000FF00;
110 unsigned Byte2 = Value & 0x00FF0000;
111 unsigned Byte3 = Value & 0xFF000000;
112 return (Byte0 << 24) | (Byte1 << 8) | (Byte2 >> 8) | (Byte3 >> 24);
116 /// ByteSwap_64 - This function returns a byte-swapped representation of the
117 /// 64-bit argument, Value.
118 inline uint64_t ByteSwap_64(uint64_t Value) {
119 #if __GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 3)
120 return __builtin_bswap64(Value);
122 uint64_t Hi = ByteSwap_32(unsigned(Value));
123 uint64_t Lo = ByteSwap_32(unsigned(Value >> 32));
124 return (Hi << 32) | Lo;
128 /// CountLeadingZeros_32 - this function performs the platform optimal form of
129 /// counting the number of zeros from the most significant bit to the first one
130 /// bit. Ex. CountLeadingZeros_32(0x00F000FF) == 8.
131 /// Returns 32 if the word is zero.
132 inline unsigned CountLeadingZeros_32(unsigned Value) {
133 unsigned Count; // result
135 // PowerPC is defined for __builtin_clz(0)
136 #if !defined(__ppc__) && !defined(__ppc64__)
137 if (!Value) return 32;
139 Count = __builtin_clz(Value);
141 if (!Value) return 32;
143 // bisecton method for count leading zeros
144 for (unsigned Shift = 32 >> 1; Shift; Shift >>= 1) {
145 unsigned Tmp = Value >> Shift;
156 /// CountLeadingZeros_64 - This function performs the platform optimal form
157 /// of counting the number of zeros from the most significant bit to the first
158 /// one bit (64 bit edition.)
159 /// Returns 64 if the word is zero.
160 inline unsigned CountLeadingZeros_64(uint64_t Value) {
161 unsigned Count; // result
163 // PowerPC is defined for __builtin_clzll(0)
164 #if !defined(__ppc__) && !defined(__ppc64__)
165 if (!Value) return 64;
167 Count = __builtin_clzll(Value);
169 if (sizeof(long) == sizeof(int64_t)) {
170 if (!Value) return 64;
172 // bisecton method for count leading zeros
173 for (uint64_t Shift = 64 >> 1; Shift; Shift >>= 1) {
174 uint64_t Tmp = Value >> Shift;
183 unsigned Hi = Hi_32(Value);
185 // if some bits in hi portion
187 // leading zeros in hi portion plus all bits in lo portion
188 Count = CountLeadingZeros_32(Hi);
191 unsigned Lo = Lo_32(Value);
192 // same as 32 bit value
193 Count = CountLeadingZeros_32(Lo)+32;
200 /// CountTrailingZeros_32 - this function performs the platform optimal form of
201 /// counting the number of zeros from the least significant bit to the first one
202 /// bit. Ex. CountTrailingZeros_32(0xFF00FF00) == 8.
203 /// Returns 32 if the word is zero.
204 inline unsigned CountTrailingZeros_32(unsigned Value) {
206 return Value ? __builtin_ctz(Value) : 32;
208 static const unsigned Mod37BitPosition[] = {
209 32, 0, 1, 26, 2, 23, 27, 0, 3, 16, 24, 30, 28, 11, 0, 13,
210 4, 7, 17, 0, 25, 22, 31, 15, 29, 10, 12, 6, 0, 21, 14, 9,
213 return Mod37BitPosition[(-Value & Value) % 37];
217 /// CountTrailingZeros_64 - This function performs the platform optimal form
218 /// of counting the number of zeros from the least significant bit to the first
219 /// one bit (64 bit edition.)
220 /// Returns 64 if the word is zero.
221 inline unsigned CountTrailingZeros_64(uint64_t Value) {
223 return Value ? __builtin_ctzll(Value) : 64;
225 static const unsigned Mod67Position[] = {
226 64, 0, 1, 39, 2, 15, 40, 23, 3, 12, 16, 59, 41, 19, 24, 54,
227 4, 64, 13, 10, 17, 62, 60, 28, 42, 30, 20, 51, 25, 44, 55,
228 47, 5, 32, 65, 38, 14, 22, 11, 58, 18, 53, 63, 9, 61, 27,
229 29, 50, 43, 46, 31, 37, 21, 57, 52, 8, 26, 49, 45, 36, 56,
230 7, 48, 35, 6, 34, 33, 0
232 return Mod67Position[(-Value & Value) % 67];
236 /// CountPopulation_32 - this function counts the number of set bits in a value.
237 /// Ex. CountPopulation(0xF000F000) = 8
238 /// Returns 0 if the word is zero.
239 inline unsigned CountPopulation_32(uint32_t Value) {
241 return __builtin_popcount(Value);
243 uint32_t v = Value - ((Value >> 1) & 0x55555555);
244 v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
245 return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
249 /// CountPopulation_64 - this function counts the number of set bits in a value,
250 /// (64 bit edition.)
251 inline unsigned CountPopulation_64(uint64_t Value) {
253 return __builtin_popcountll(Value);
255 uint64_t v = Value - ((Value >> 1) & 0x5555555555555555ULL);
256 v = (v & 0x3333333333333333ULL) + ((v >> 2) & 0x3333333333333333ULL);
257 v = (v + (v >> 4)) & 0x0F0F0F0F0F0F0F0FULL;
258 return unsigned((uint64_t)(v * 0x0101010101010101ULL) >> 56);
262 /// Log2_32 - This function returns the floor log base 2 of the specified value,
263 /// -1 if the value is zero. (32 bit edition.)
264 /// Ex. Log2_32(32) == 5, Log2_32(1) == 0, Log2_32(0) == -1, Log2_32(6) == 2
265 inline unsigned Log2_32(unsigned Value) {
266 return 31 - CountLeadingZeros_32(Value);
269 /// Log2_64 - This function returns the floor log base 2 of the specified value,
270 /// -1 if the value is zero. (64 bit edition.)
271 inline unsigned Log2_64(uint64_t Value) {
272 return 63 - CountLeadingZeros_64(Value);
275 /// Log2_32_Ceil - This function returns the ceil log base 2 of the specified
276 /// value, 32 if the value is zero. (32 bit edition).
277 /// Ex. Log2_32_Ceil(32) == 5, Log2_32_Ceil(1) == 0, Log2_32_Ceil(6) == 3
278 inline unsigned Log2_32_Ceil(unsigned Value) {
279 return 32-CountLeadingZeros_32(Value-1);
282 /// Log2_64 - This function returns the ceil log base 2 of the specified value,
283 /// 64 if the value is zero. (64 bit edition.)
284 inline unsigned Log2_64_Ceil(uint64_t Value) {
285 return 64-CountLeadingZeros_64(Value-1);
288 /// GreatestCommonDivisor64 - Return the greatest common divisor of the two
289 /// values using Euclid's algorithm.
290 inline uint64_t GreatestCommonDivisor64(uint64_t A, uint64_t B) {
299 /// BitsToDouble - This function takes a 64-bit integer and returns the bit
300 /// equivalent double.
301 inline double BitsToDouble(uint64_t Bits) {
310 /// BitsToFloat - This function takes a 32-bit integer and returns the bit
311 /// equivalent float.
312 inline float BitsToFloat(uint32_t Bits) {
321 /// DoubleToBits - This function takes a double and returns the bit
322 /// equivalent 64-bit integer.
323 inline uint64_t DoubleToBits(double Double) {
332 /// FloatToBits - This function takes a float and returns the bit
333 /// equivalent 32-bit integer.
334 inline uint32_t FloatToBits(float Float) {
343 /// Platform-independent wrappers for the C99 isnan() function.
347 /// Platform-independent wrappers for the C99 isinf() function.
351 } // End llvm namespace