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/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;
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 bool isMask_32(uint32_t 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 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 bool isShiftedMask_32(uint32_t 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 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(uint32_t 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 uint16_t ByteSwap_16(uint16_t Value) {
97 #if defined(_MSC_VER) && !defined(_DEBUG)
98 // The DLL version of the runtime lacks these functions (bug!?), but in a
99 // release build they're replaced with BSWAP instructions anyway.
100 return _byteswap_ushort(Value);
102 uint16_t Hi = Value << 8;
103 uint16_t Lo = Value >> 8;
108 /// ByteSwap_32 - This function returns a byte-swapped representation of the
109 /// 32-bit argument, Value.
110 inline uint32_t ByteSwap_32(uint32_t Value) {
111 #if __GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 3)
112 return __builtin_bswap32(Value);
113 #elif defined(_MSC_VER) && !defined(_DEBUG)
114 return _byteswap_ulong(Value);
116 uint32_t Byte0 = Value & 0x000000FF;
117 uint32_t Byte1 = Value & 0x0000FF00;
118 uint32_t Byte2 = Value & 0x00FF0000;
119 uint32_t Byte3 = Value & 0xFF000000;
120 return (Byte0 << 24) | (Byte1 << 8) | (Byte2 >> 8) | (Byte3 >> 24);
124 /// ByteSwap_64 - This function returns a byte-swapped representation of the
125 /// 64-bit argument, Value.
126 inline uint64_t ByteSwap_64(uint64_t Value) {
127 #if __GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 3)
128 return __builtin_bswap64(Value);
129 #elif defined(_MSC_VER) && !defined(_DEBUG)
130 return _byteswap_uint64(Value);
132 uint64_t Hi = ByteSwap_32(uint32_t(Value));
133 uint32_t Lo = ByteSwap_32(uint32_t(Value >> 32));
134 return (Hi << 32) | Lo;
138 /// CountLeadingZeros_32 - this function performs the platform optimal form of
139 /// counting the number of zeros from the most significant bit to the first one
140 /// bit. Ex. CountLeadingZeros_32(0x00F000FF) == 8.
141 /// Returns 32 if the word is zero.
142 inline unsigned CountLeadingZeros_32(uint32_t Value) {
143 unsigned Count; // result
145 // PowerPC is defined for __builtin_clz(0)
146 #if !defined(__ppc__) && !defined(__ppc64__)
147 if (!Value) return 32;
149 Count = __builtin_clz(Value);
151 if (!Value) return 32;
153 // bisecton method for count leading zeros
154 for (unsigned Shift = 32 >> 1; Shift; Shift >>= 1) {
155 uint32_t Tmp = Value >> Shift;
166 /// CountLeadingOnes_32 - this function performs the operation of
167 /// counting the number of ones from the most significant bit to the first zero
168 /// bit. Ex. CountLeadingOnes_32(0xFF0FFF00) == 8.
169 /// Returns 32 if the word is all ones.
170 inline unsigned CountLeadingOnes_32(uint32_t Value) {
171 return CountLeadingZeros_32(~Value);
174 /// CountLeadingZeros_64 - This function performs the platform optimal form
175 /// of counting the number of zeros from the most significant bit to the first
176 /// one bit (64 bit edition.)
177 /// Returns 64 if the word is zero.
178 inline unsigned CountLeadingZeros_64(uint64_t Value) {
179 unsigned Count; // result
181 // PowerPC is defined for __builtin_clzll(0)
182 #if !defined(__ppc__) && !defined(__ppc64__)
183 if (!Value) return 64;
185 Count = __builtin_clzll(Value);
187 if (sizeof(long) == sizeof(int64_t)) {
188 if (!Value) return 64;
190 // bisecton method for count leading zeros
191 for (unsigned Shift = 64 >> 1; Shift; Shift >>= 1) {
192 uint64_t Tmp = Value >> Shift;
201 uint32_t Hi = Hi_32(Value);
203 // if some bits in hi portion
205 // leading zeros in hi portion plus all bits in lo portion
206 Count = CountLeadingZeros_32(Hi);
209 uint32_t Lo = Lo_32(Value);
210 // same as 32 bit value
211 Count = CountLeadingZeros_32(Lo)+32;
218 /// CountLeadingOnes_64 - This function performs the operation
219 /// of counting the number of ones from the most significant bit to the first
220 /// zero bit (64 bit edition.)
221 /// Returns 64 if the word is all ones.
222 inline unsigned CountLeadingOnes_64(uint64_t Value) {
223 return CountLeadingZeros_64(~Value);
226 /// CountTrailingZeros_32 - this function performs the platform optimal form of
227 /// counting the number of zeros from the least significant bit to the first one
228 /// bit. Ex. CountTrailingZeros_32(0xFF00FF00) == 8.
229 /// Returns 32 if the word is zero.
230 inline unsigned CountTrailingZeros_32(uint32_t Value) {
232 return Value ? __builtin_ctz(Value) : 32;
234 static const unsigned Mod37BitPosition[] = {
235 32, 0, 1, 26, 2, 23, 27, 0, 3, 16, 24, 30, 28, 11, 0, 13,
236 4, 7, 17, 0, 25, 22, 31, 15, 29, 10, 12, 6, 0, 21, 14, 9,
239 return Mod37BitPosition[(-Value & Value) % 37];
243 /// CountTrailingOnes_32 - this function performs the operation of
244 /// counting the number of ones from the least significant bit to the first zero
245 /// bit. Ex. CountTrailingOnes_32(0x00FF00FF) == 8.
246 /// Returns 32 if the word is all ones.
247 inline unsigned CountTrailingOnes_32(uint32_t Value) {
248 return CountTrailingZeros_32(~Value);
251 /// CountTrailingZeros_64 - This function performs the platform optimal form
252 /// of counting the number of zeros from the least significant bit to the first
253 /// one bit (64 bit edition.)
254 /// Returns 64 if the word is zero.
255 inline unsigned CountTrailingZeros_64(uint64_t Value) {
257 return Value ? __builtin_ctzll(Value) : 64;
259 static const unsigned Mod67Position[] = {
260 64, 0, 1, 39, 2, 15, 40, 23, 3, 12, 16, 59, 41, 19, 24, 54,
261 4, 64, 13, 10, 17, 62, 60, 28, 42, 30, 20, 51, 25, 44, 55,
262 47, 5, 32, 65, 38, 14, 22, 11, 58, 18, 53, 63, 9, 61, 27,
263 29, 50, 43, 46, 31, 37, 21, 57, 52, 8, 26, 49, 45, 36, 56,
264 7, 48, 35, 6, 34, 33, 0
266 return Mod67Position[(-Value & Value) % 67];
270 /// CountTrailingOnes_64 - This function performs the operation
271 /// of counting the number of ones from the least significant bit to the first
272 /// zero bit (64 bit edition.)
273 /// Returns 64 if the word is all ones.
274 inline unsigned CountTrailingOnes_64(uint64_t Value) {
275 return CountTrailingZeros_64(~Value);
278 /// CountPopulation_32 - this function counts the number of set bits in a value.
279 /// Ex. CountPopulation(0xF000F000) = 8
280 /// Returns 0 if the word is zero.
281 inline unsigned CountPopulation_32(uint32_t Value) {
283 return __builtin_popcount(Value);
285 uint32_t v = Value - ((Value >> 1) & 0x55555555);
286 v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
287 return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
291 /// CountPopulation_64 - this function counts the number of set bits in a value,
292 /// (64 bit edition.)
293 inline unsigned CountPopulation_64(uint64_t Value) {
295 return __builtin_popcountll(Value);
297 uint64_t v = Value - ((Value >> 1) & 0x5555555555555555ULL);
298 v = (v & 0x3333333333333333ULL) + ((v >> 2) & 0x3333333333333333ULL);
299 v = (v + (v >> 4)) & 0x0F0F0F0F0F0F0F0FULL;
300 return unsigned((uint64_t)(v * 0x0101010101010101ULL) >> 56);
304 /// Log2_32 - This function returns the floor log base 2 of the specified value,
305 /// -1 if the value is zero. (32 bit edition.)
306 /// Ex. Log2_32(32) == 5, Log2_32(1) == 0, Log2_32(0) == -1, Log2_32(6) == 2
307 inline unsigned Log2_32(uint32_t Value) {
308 return 31 - CountLeadingZeros_32(Value);
311 /// Log2_64 - This function returns the floor log base 2 of the specified value,
312 /// -1 if the value is zero. (64 bit edition.)
313 inline unsigned Log2_64(uint64_t Value) {
314 return 63 - CountLeadingZeros_64(Value);
317 /// Log2_32_Ceil - This function returns the ceil log base 2 of the specified
318 /// value, 32 if the value is zero. (32 bit edition).
319 /// Ex. Log2_32_Ceil(32) == 5, Log2_32_Ceil(1) == 0, Log2_32_Ceil(6) == 3
320 inline unsigned Log2_32_Ceil(uint32_t Value) {
321 return 32-CountLeadingZeros_32(Value-1);
324 /// Log2_64 - This function returns the ceil log base 2 of the specified value,
325 /// 64 if the value is zero. (64 bit edition.)
326 inline unsigned Log2_64_Ceil(uint64_t Value) {
327 return 64-CountLeadingZeros_64(Value-1);
330 /// GreatestCommonDivisor64 - Return the greatest common divisor of the two
331 /// values using Euclid's algorithm.
332 inline uint64_t GreatestCommonDivisor64(uint64_t A, uint64_t B) {
341 /// BitsToDouble - This function takes a 64-bit integer and returns the bit
342 /// equivalent double.
343 inline double BitsToDouble(uint64_t Bits) {
352 /// BitsToFloat - This function takes a 32-bit integer and returns the bit
353 /// equivalent float.
354 inline float BitsToFloat(uint32_t Bits) {
363 /// DoubleToBits - This function takes a double and returns the bit
364 /// equivalent 64-bit integer. Note that copying doubles around
365 /// changes the bits of NaNs on some hosts, notably x86, so this
366 /// routine cannot be used if these bits are needed.
367 inline uint64_t DoubleToBits(double Double) {
376 /// FloatToBits - This function takes a float and returns the bit
377 /// equivalent 32-bit integer. Note that copying floats around
378 /// changes the bits of NaNs on some hosts, notably x86, so this
379 /// routine cannot be used if these bits are needed.
380 inline uint32_t FloatToBits(float Float) {
389 /// Platform-independent wrappers for the C99 isnan() function.
393 /// Platform-independent wrappers for the C99 isinf() function.
397 /// MinAlign - A and B are either alignments or offsets. Return the minimum
398 /// alignment that may be assumed after adding the two together.
399 static inline uint64_t MinAlign(uint64_t A, uint64_t B) {
400 // The largest power of 2 that divides both A and B.
401 return (A | B) & -(A | B);
404 /// NextPowerOf2 - Returns the next power of two (in 64-bits)
405 /// that is strictly greater than A. Returns zero on overflow.
406 static inline uint64_t NextPowerOf2(uint64_t A) {
416 /// RoundUpToAlignment - Returns the next integer (mod 2**64) that is
417 /// greater than or equal to \arg Value and is a multiple of \arg
418 /// Align. Align must be non-zero.
421 /// RoundUpToAlignment(5, 8) = 8
422 /// RoundUpToAlignment(17, 8) = 24
423 /// RoundUpToAlignment(~0LL, 8) = 0
424 inline uint64_t RoundUpToAlignment(uint64_t Value, uint64_t Align) {
425 return ((Value + Align - 1) / Align) * Align;
428 } // End llvm namespace