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"
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 /// is?Type - these functions produce optimal testing for integer data types.
36 inline bool isInt8 (int64_t Value) {
37 return static_cast<int8_t>(Value) == Value;
39 inline bool isUInt8 (int64_t Value) {
40 return static_cast<uint8_t>(Value) == Value;
42 inline bool isInt16 (int64_t Value) {
43 return static_cast<int16_t>(Value) == Value;
45 inline bool isUInt16(int64_t Value) {
46 return static_cast<uint16_t>(Value) == Value;
48 inline bool isInt32 (int64_t Value) {
49 return static_cast<int32_t>(Value) == Value;
51 inline bool isUInt32(int64_t Value) {
52 return static_cast<uint32_t>(Value) == Value;
56 inline bool isInt(int64_t x) {
57 return N >= 64 || (-(INT64_C(1)<<(N-1)) <= x && x < (INT64_C(1)<<(N-1)));
61 inline bool isUint(uint64_t x) {
62 return N >= 64 || x < (UINT64_C(1)<<N);
65 /// isMask_32 - This function returns true if the argument is a sequence of ones
66 /// starting at the least significant bit with the remainder zero (32 bit
67 /// version). Ex. isMask_32(0x0000FFFFU) == true.
68 inline bool isMask_32(uint32_t Value) {
69 return Value && ((Value + 1) & Value) == 0;
72 /// isMask_64 - This function returns true if the argument is a sequence of ones
73 /// starting at the least significant bit with the remainder zero (64 bit
75 inline bool isMask_64(uint64_t Value) {
76 return Value && ((Value + 1) & Value) == 0;
79 /// isShiftedMask_32 - This function returns true if the argument contains a
80 /// sequence of ones with the remainder zero (32 bit version.)
81 /// Ex. isShiftedMask_32(0x0000FF00U) == true.
82 inline bool isShiftedMask_32(uint32_t Value) {
83 return isMask_32((Value - 1) | Value);
86 /// isShiftedMask_64 - This function returns true if the argument contains a
87 /// sequence of ones with the remainder zero (64 bit version.)
88 inline bool isShiftedMask_64(uint64_t Value) {
89 return isMask_64((Value - 1) | Value);
92 /// isPowerOf2_32 - This function returns true if the argument is a power of
93 /// two > 0. Ex. isPowerOf2_32(0x00100000U) == true (32 bit edition.)
94 inline bool isPowerOf2_32(uint32_t Value) {
95 return Value && !(Value & (Value - 1));
98 /// isPowerOf2_64 - This function returns true if the argument is a power of two
99 /// > 0 (64 bit edition.)
100 inline bool isPowerOf2_64(uint64_t Value) {
101 return Value && !(Value & (Value - int64_t(1L)));
104 /// ByteSwap_16 - This function returns a byte-swapped representation of the
105 /// 16-bit argument, Value.
106 inline uint16_t ByteSwap_16(uint16_t Value) {
107 #if defined(_MSC_VER) && !defined(_DEBUG)
108 // The DLL version of the runtime lacks these functions (bug!?), but in a
109 // release build they're replaced with BSWAP instructions anyway.
110 return _byteswap_ushort(Value);
112 uint16_t Hi = Value << 8;
113 uint16_t Lo = Value >> 8;
118 /// ByteSwap_32 - This function returns a byte-swapped representation of the
119 /// 32-bit argument, Value.
120 inline uint32_t ByteSwap_32(uint32_t Value) {
121 #if (__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 3)) && !defined(__ICC)
122 return __builtin_bswap32(Value);
123 #elif defined(_MSC_VER) && !defined(_DEBUG)
124 return _byteswap_ulong(Value);
126 uint32_t Byte0 = Value & 0x000000FF;
127 uint32_t Byte1 = Value & 0x0000FF00;
128 uint32_t Byte2 = Value & 0x00FF0000;
129 uint32_t Byte3 = Value & 0xFF000000;
130 return (Byte0 << 24) | (Byte1 << 8) | (Byte2 >> 8) | (Byte3 >> 24);
134 /// ByteSwap_64 - This function returns a byte-swapped representation of the
135 /// 64-bit argument, Value.
136 inline uint64_t ByteSwap_64(uint64_t Value) {
137 #if (__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 3)) && !defined(__ICC)
138 return __builtin_bswap64(Value);
139 #elif defined(_MSC_VER) && !defined(_DEBUG)
140 return _byteswap_uint64(Value);
142 uint64_t Hi = ByteSwap_32(uint32_t(Value));
143 uint32_t Lo = ByteSwap_32(uint32_t(Value >> 32));
144 return (Hi << 32) | Lo;
148 /// CountLeadingZeros_32 - this function performs the platform optimal form of
149 /// counting the number of zeros from the most significant bit to the first one
150 /// bit. Ex. CountLeadingZeros_32(0x00F000FF) == 8.
151 /// Returns 32 if the word is zero.
152 inline unsigned CountLeadingZeros_32(uint32_t Value) {
153 unsigned Count; // result
155 // PowerPC is defined for __builtin_clz(0)
156 #if !defined(__ppc__) && !defined(__ppc64__)
157 if (!Value) return 32;
159 Count = __builtin_clz(Value);
161 if (!Value) return 32;
163 // bisecton method for count leading zeros
164 for (unsigned Shift = 32 >> 1; Shift; Shift >>= 1) {
165 uint32_t Tmp = Value >> Shift;
176 /// CountLeadingOnes_32 - this function performs the operation of
177 /// counting the number of ones from the most significant bit to the first zero
178 /// bit. Ex. CountLeadingOnes_32(0xFF0FFF00) == 8.
179 /// Returns 32 if the word is all ones.
180 inline unsigned CountLeadingOnes_32(uint32_t Value) {
181 return CountLeadingZeros_32(~Value);
184 /// CountLeadingZeros_64 - This function performs the platform optimal form
185 /// of counting the number of zeros from the most significant bit to the first
186 /// one bit (64 bit edition.)
187 /// Returns 64 if the word is zero.
188 inline unsigned CountLeadingZeros_64(uint64_t Value) {
189 unsigned Count; // result
191 // PowerPC is defined for __builtin_clzll(0)
192 #if !defined(__ppc__) && !defined(__ppc64__)
193 if (!Value) return 64;
195 Count = __builtin_clzll(Value);
197 if (sizeof(long) == sizeof(int64_t)) {
198 if (!Value) return 64;
200 // bisecton method for count leading zeros
201 for (unsigned Shift = 64 >> 1; Shift; Shift >>= 1) {
202 uint64_t Tmp = Value >> Shift;
211 uint32_t Hi = Hi_32(Value);
213 // if some bits in hi portion
215 // leading zeros in hi portion plus all bits in lo portion
216 Count = CountLeadingZeros_32(Hi);
219 uint32_t Lo = Lo_32(Value);
220 // same as 32 bit value
221 Count = CountLeadingZeros_32(Lo)+32;
228 /// CountLeadingOnes_64 - This function performs the operation
229 /// of counting the number of ones from the most significant bit to the first
230 /// zero bit (64 bit edition.)
231 /// Returns 64 if the word is all ones.
232 inline unsigned CountLeadingOnes_64(uint64_t Value) {
233 return CountLeadingZeros_64(~Value);
236 /// CountTrailingZeros_32 - this function performs the platform optimal form of
237 /// counting the number of zeros from the least significant bit to the first one
238 /// bit. Ex. CountTrailingZeros_32(0xFF00FF00) == 8.
239 /// Returns 32 if the word is zero.
240 inline unsigned CountTrailingZeros_32(uint32_t Value) {
242 return Value ? __builtin_ctz(Value) : 32;
244 static const unsigned Mod37BitPosition[] = {
245 32, 0, 1, 26, 2, 23, 27, 0, 3, 16, 24, 30, 28, 11, 0, 13,
246 4, 7, 17, 0, 25, 22, 31, 15, 29, 10, 12, 6, 0, 21, 14, 9,
249 return Mod37BitPosition[(-Value & Value) % 37];
253 /// CountTrailingOnes_32 - this function performs the operation of
254 /// counting the number of ones from the least significant bit to the first zero
255 /// bit. Ex. CountTrailingOnes_32(0x00FF00FF) == 8.
256 /// Returns 32 if the word is all ones.
257 inline unsigned CountTrailingOnes_32(uint32_t Value) {
258 return CountTrailingZeros_32(~Value);
261 /// CountTrailingZeros_64 - This function performs the platform optimal form
262 /// of counting the number of zeros from the least significant bit to the first
263 /// one bit (64 bit edition.)
264 /// Returns 64 if the word is zero.
265 inline unsigned CountTrailingZeros_64(uint64_t Value) {
267 return Value ? __builtin_ctzll(Value) : 64;
269 static const unsigned Mod67Position[] = {
270 64, 0, 1, 39, 2, 15, 40, 23, 3, 12, 16, 59, 41, 19, 24, 54,
271 4, 64, 13, 10, 17, 62, 60, 28, 42, 30, 20, 51, 25, 44, 55,
272 47, 5, 32, 65, 38, 14, 22, 11, 58, 18, 53, 63, 9, 61, 27,
273 29, 50, 43, 46, 31, 37, 21, 57, 52, 8, 26, 49, 45, 36, 56,
274 7, 48, 35, 6, 34, 33, 0
276 return Mod67Position[(-Value & Value) % 67];
280 /// CountTrailingOnes_64 - This function performs the operation
281 /// of counting the number of ones from the least significant bit to the first
282 /// zero bit (64 bit edition.)
283 /// Returns 64 if the word is all ones.
284 inline unsigned CountTrailingOnes_64(uint64_t Value) {
285 return CountTrailingZeros_64(~Value);
288 /// CountPopulation_32 - this function counts the number of set bits in a value.
289 /// Ex. CountPopulation(0xF000F000) = 8
290 /// Returns 0 if the word is zero.
291 inline unsigned CountPopulation_32(uint32_t Value) {
293 return __builtin_popcount(Value);
295 uint32_t v = Value - ((Value >> 1) & 0x55555555);
296 v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
297 return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
301 /// CountPopulation_64 - this function counts the number of set bits in a value,
302 /// (64 bit edition.)
303 inline unsigned CountPopulation_64(uint64_t Value) {
305 return __builtin_popcountll(Value);
307 uint64_t v = Value - ((Value >> 1) & 0x5555555555555555ULL);
308 v = (v & 0x3333333333333333ULL) + ((v >> 2) & 0x3333333333333333ULL);
309 v = (v + (v >> 4)) & 0x0F0F0F0F0F0F0F0FULL;
310 return unsigned((uint64_t)(v * 0x0101010101010101ULL) >> 56);
314 /// Log2_32 - This function returns the floor log base 2 of the specified value,
315 /// -1 if the value is zero. (32 bit edition.)
316 /// Ex. Log2_32(32) == 5, Log2_32(1) == 0, Log2_32(0) == -1, Log2_32(6) == 2
317 inline unsigned Log2_32(uint32_t Value) {
318 return 31 - CountLeadingZeros_32(Value);
321 /// Log2_64 - This function returns the floor log base 2 of the specified value,
322 /// -1 if the value is zero. (64 bit edition.)
323 inline unsigned Log2_64(uint64_t Value) {
324 return 63 - CountLeadingZeros_64(Value);
327 /// Log2_32_Ceil - This function returns the ceil log base 2 of the specified
328 /// value, 32 if the value is zero. (32 bit edition).
329 /// Ex. Log2_32_Ceil(32) == 5, Log2_32_Ceil(1) == 0, Log2_32_Ceil(6) == 3
330 inline unsigned Log2_32_Ceil(uint32_t Value) {
331 return 32-CountLeadingZeros_32(Value-1);
334 /// Log2_64_Ceil - This function returns the ceil log base 2 of the specified
335 /// value, 64 if the value is zero. (64 bit edition.)
336 inline unsigned Log2_64_Ceil(uint64_t Value) {
337 return 64-CountLeadingZeros_64(Value-1);
340 /// GreatestCommonDivisor64 - Return the greatest common divisor of the two
341 /// values using Euclid's algorithm.
342 inline uint64_t GreatestCommonDivisor64(uint64_t A, uint64_t B) {
351 /// BitsToDouble - This function takes a 64-bit integer and returns the bit
352 /// equivalent double.
353 inline double BitsToDouble(uint64_t Bits) {
362 /// BitsToFloat - This function takes a 32-bit integer and returns the bit
363 /// equivalent float.
364 inline float BitsToFloat(uint32_t Bits) {
373 /// DoubleToBits - This function takes a double and returns the bit
374 /// equivalent 64-bit integer. Note that copying doubles around
375 /// changes the bits of NaNs on some hosts, notably x86, so this
376 /// routine cannot be used if these bits are needed.
377 inline uint64_t DoubleToBits(double Double) {
386 /// FloatToBits - This function takes a float and returns the bit
387 /// equivalent 32-bit integer. Note that copying floats around
388 /// changes the bits of NaNs on some hosts, notably x86, so this
389 /// routine cannot be used if these bits are needed.
390 inline uint32_t FloatToBits(float Float) {
399 /// Platform-independent wrappers for the C99 isnan() function.
403 /// Platform-independent wrappers for the C99 isinf() function.
407 /// MinAlign - A and B are either alignments or offsets. Return the minimum
408 /// alignment that may be assumed after adding the two together.
409 static inline uint64_t MinAlign(uint64_t A, uint64_t B) {
410 // The largest power of 2 that divides both A and B.
411 return (A | B) & -(A | B);
414 /// NextPowerOf2 - Returns the next power of two (in 64-bits)
415 /// that is strictly greater than A. Returns zero on overflow.
416 static inline uint64_t NextPowerOf2(uint64_t A) {
426 /// RoundUpToAlignment - Returns the next integer (mod 2**64) that is
427 /// greater than or equal to \arg Value and is a multiple of \arg
428 /// Align. Align must be non-zero.
431 /// RoundUpToAlignment(5, 8) = 8
432 /// RoundUpToAlignment(17, 8) = 24
433 /// RoundUpToAlignment(~0LL, 8) = 0
434 inline uint64_t RoundUpToAlignment(uint64_t Value, uint64_t Align) {
435 return ((Value + Align - 1) / Align) * Align;
438 /// OffsetToAlignment - Return the offset to the next integer (mod 2**64) that
439 /// is greater than or equal to \arg Value and is a multiple of \arg
440 /// Align. Align must be non-zero.
441 inline uint64_t OffsetToAlignment(uint64_t Value, uint64_t Align) {
442 return RoundUpToAlignment(Value, Align) - Value;
445 /// abs64 - absolute value of a 64-bit int. Not all environments support
446 /// "abs" on whatever their name for the 64-bit int type is. The absolute
447 /// value of the largest negative number is undefined, as with "abs".
448 inline int64_t abs64(int64_t x) {
449 return (x < 0) ? -x : x;
452 } // End llvm namespace