1 //===-- llvm/Support/MathExtras.h - Useful math functions -------*- C++ -*-===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file contains some functions that are useful for math stuff.
11 //
12 //===----------------------------------------------------------------------===//
13
14 #ifndef LLVM_SUPPORT_MATHEXTRAS_H
15 #define LLVM_SUPPORT_MATHEXTRAS_H
16
17 #include "llvm/System/DataTypes.h"
18
19 namespace llvm {
20
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
23 // ambiguity.
24
25 /// Hi_32 - This function returns the high 32 bits of a 64 bit value.
Hi_32(uint64_t Value)26 inline uint32_t Hi_32(uint64_t Value) {
27 return static_cast<uint32_t>(Value >> 32);
28 }
29
30 /// Lo_32 - This function returns the low 32 bits of a 64 bit value.
Lo_32(uint64_t Value)31 inline uint32_t Lo_32(uint64_t Value) {
32 return static_cast<uint32_t>(Value);
33 }
34
35 /// isInt - Checks if an integer fits into the given bit width.
36 template<unsigned N>
isInt(int64_t x)37 inline bool isInt(int64_t x) {
38 return N >= 64 || (-(INT64_C(1)<<(N-1)) <= x && x < (INT64_C(1)<<(N-1)));
39 }
40 // Template specializations to get better code for common cases.
41 template<>
42 inline bool isInt<8>(int64_t x) {
43 return static_cast<int8_t>(x) == x;
44 }
45 template<>
46 inline bool isInt<16>(int64_t x) {
47 return static_cast<int16_t>(x) == x;
48 }
49 template<>
50 inline bool isInt<32>(int64_t x) {
51 return static_cast<int32_t>(x) == x;
52 }
53
54 /// isUInt - Checks if an unsigned integer fits into the given bit width.
55 template<unsigned N>
isUInt(uint64_t x)56 inline bool isUInt(uint64_t x) {
57 return N >= 64 || x < (UINT64_C(1)<<N);
58 }
59 // Template specializations to get better code for common cases.
60 template<>
61 inline bool isUInt<8>(uint64_t x) {
62 return static_cast<uint8_t>(x) == x;
63 }
64 template<>
65 inline bool isUInt<16>(uint64_t x) {
66 return static_cast<uint16_t>(x) == x;
67 }
68 template<>
69 inline bool isUInt<32>(uint64_t x) {
70 return static_cast<uint32_t>(x) == x;
71 }
72
73 /// isMask_32 - This function returns true if the argument is a sequence of ones
74 /// starting at the least significant bit with the remainder zero (32 bit
75 /// version). Ex. isMask_32(0x0000FFFFU) == true.
isMask_32(uint32_t Value)76 inline bool isMask_32(uint32_t Value) {
77 return Value && ((Value + 1) & Value) == 0;
78 }
79
80 /// isMask_64 - This function returns true if the argument is a sequence of ones
81 /// starting at the least significant bit with the remainder zero (64 bit
82 /// version).
isMask_64(uint64_t Value)83 inline bool isMask_64(uint64_t Value) {
84 return Value && ((Value + 1) & Value) == 0;
85 }
86
87 /// isShiftedMask_32 - This function returns true if the argument contains a
88 /// sequence of ones with the remainder zero (32 bit version.)
89 /// Ex. isShiftedMask_32(0x0000FF00U) == true.
isShiftedMask_32(uint32_t Value)90 inline bool isShiftedMask_32(uint32_t Value) {
91 return isMask_32((Value - 1) | Value);
92 }
93
94 /// isShiftedMask_64 - This function returns true if the argument contains a
95 /// sequence of ones with the remainder zero (64 bit version.)
isShiftedMask_64(uint64_t Value)96 inline bool isShiftedMask_64(uint64_t Value) {
97 return isMask_64((Value - 1) | Value);
98 }
99
100 /// isPowerOf2_32 - This function returns true if the argument is a power of
101 /// two > 0. Ex. isPowerOf2_32(0x00100000U) == true (32 bit edition.)
isPowerOf2_32(uint32_t Value)102 inline bool isPowerOf2_32(uint32_t Value) {
103 return Value && !(Value & (Value - 1));
104 }
105
106 /// isPowerOf2_64 - This function returns true if the argument is a power of two
107 /// > 0 (64 bit edition.)
isPowerOf2_64(uint64_t Value)108 inline bool isPowerOf2_64(uint64_t Value) {
109 return Value && !(Value & (Value - int64_t(1L)));
110 }
111
112 /// ByteSwap_16 - This function returns a byte-swapped representation of the
113 /// 16-bit argument, Value.
ByteSwap_16(uint16_t Value)114 inline uint16_t ByteSwap_16(uint16_t Value) {
115 #if defined(_MSC_VER) && !defined(_DEBUG)
116 // The DLL version of the runtime lacks these functions (bug!?), but in a
117 // release build they're replaced with BSWAP instructions anyway.
118 return _byteswap_ushort(Value);
119 #else
120 uint16_t Hi = Value << 8;
121 uint16_t Lo = Value >> 8;
122 return Hi | Lo;
123 #endif
124 }
125
126 /// ByteSwap_32 - This function returns a byte-swapped representation of the
127 /// 32-bit argument, Value.
ByteSwap_32(uint32_t Value)128 inline uint32_t ByteSwap_32(uint32_t Value) {
129 #if defined(__llvm__) || \
130 (__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 3)) && !defined(__ICC)
131 return __builtin_bswap32(Value);
132 #elif defined(_MSC_VER) && !defined(_DEBUG)
133 return _byteswap_ulong(Value);
134 #else
135 uint32_t Byte0 = Value & 0x000000FF;
136 uint32_t Byte1 = Value & 0x0000FF00;
137 uint32_t Byte2 = Value & 0x00FF0000;
138 uint32_t Byte3 = Value & 0xFF000000;
139 return (Byte0 << 24) | (Byte1 << 8) | (Byte2 >> 8) | (Byte3 >> 24);
140 #endif
141 }
142
143 /// ByteSwap_64 - This function returns a byte-swapped representation of the
144 /// 64-bit argument, Value.
ByteSwap_64(uint64_t Value)145 inline uint64_t ByteSwap_64(uint64_t Value) {
146 #if defined(__llvm__) || \
147 (__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 3)) && !defined(__ICC)
148 return __builtin_bswap64(Value);
149 #elif defined(_MSC_VER) && !defined(_DEBUG)
150 return _byteswap_uint64(Value);
151 #else
152 uint64_t Hi = ByteSwap_32(uint32_t(Value));
153 uint32_t Lo = ByteSwap_32(uint32_t(Value >> 32));
154 return (Hi << 32) | Lo;
155 #endif
156 }
157
158 /// CountLeadingZeros_32 - this function performs the platform optimal form of
159 /// counting the number of zeros from the most significant bit to the first one
160 /// bit. Ex. CountLeadingZeros_32(0x00F000FF) == 8.
161 /// Returns 32 if the word is zero.
CountLeadingZeros_32(uint32_t Value)162 inline unsigned CountLeadingZeros_32(uint32_t Value) {
163 unsigned Count; // result
164 #if __GNUC__ >= 4
165 // PowerPC is defined for __builtin_clz(0)
166 #if !defined(__ppc__) && !defined(__ppc64__)
167 if (!Value) return 32;
168 #endif
169 Count = __builtin_clz(Value);
170 #else
171 if (!Value) return 32;
172 Count = 0;
173 // bisection method for count leading zeros
174 for (unsigned Shift = 32 >> 1; Shift; Shift >>= 1) {
175 uint32_t Tmp = Value >> Shift;
176 if (Tmp) {
177 Value = Tmp;
178 } else {
179 Count |= Shift;
180 }
181 }
182 #endif
183 return Count;
184 }
185
186 /// CountLeadingOnes_32 - this function performs the operation of
187 /// counting the number of ones from the most significant bit to the first zero
188 /// bit. Ex. CountLeadingOnes_32(0xFF0FFF00) == 8.
189 /// Returns 32 if the word is all ones.
CountLeadingOnes_32(uint32_t Value)190 inline unsigned CountLeadingOnes_32(uint32_t Value) {
191 return CountLeadingZeros_32(~Value);
192 }
193
194 /// CountLeadingZeros_64 - This function performs the platform optimal form
195 /// of counting the number of zeros from the most significant bit to the first
196 /// one bit (64 bit edition.)
197 /// Returns 64 if the word is zero.
CountLeadingZeros_64(uint64_t Value)198 inline unsigned CountLeadingZeros_64(uint64_t Value) {
199 unsigned Count; // result
200 #if __GNUC__ >= 4
201 // PowerPC is defined for __builtin_clzll(0)
202 #if !defined(__ppc__) && !defined(__ppc64__)
203 if (!Value) return 64;
204 #endif
205 Count = __builtin_clzll(Value);
206 #else
207 if (sizeof(long) == sizeof(int64_t)) {
208 if (!Value) return 64;
209 Count = 0;
210 // bisection method for count leading zeros
211 for (unsigned Shift = 64 >> 1; Shift; Shift >>= 1) {
212 uint64_t Tmp = Value >> Shift;
213 if (Tmp) {
214 Value = Tmp;
215 } else {
216 Count |= Shift;
217 }
218 }
219 } else {
220 // get hi portion
221 uint32_t Hi = Hi_32(Value);
222
223 // if some bits in hi portion
224 if (Hi) {
225 // leading zeros in hi portion plus all bits in lo portion
226 Count = CountLeadingZeros_32(Hi);
227 } else {
228 // get lo portion
229 uint32_t Lo = Lo_32(Value);
230 // same as 32 bit value
231 Count = CountLeadingZeros_32(Lo)+32;
232 }
233 }
234 #endif
235 return Count;
236 }
237
238 /// CountLeadingOnes_64 - This function performs the operation
239 /// of counting the number of ones from the most significant bit to the first
240 /// zero bit (64 bit edition.)
241 /// Returns 64 if the word is all ones.
CountLeadingOnes_64(uint64_t Value)242 inline unsigned CountLeadingOnes_64(uint64_t Value) {
243 return CountLeadingZeros_64(~Value);
244 }
245
246 /// CountTrailingZeros_32 - this function performs the platform optimal form of
247 /// counting the number of zeros from the least significant bit to the first one
248 /// bit. Ex. CountTrailingZeros_32(0xFF00FF00) == 8.
249 /// Returns 32 if the word is zero.
CountTrailingZeros_32(uint32_t Value)250 inline unsigned CountTrailingZeros_32(uint32_t Value) {
251 #if __GNUC__ >= 4
252 return Value ? __builtin_ctz(Value) : 32;
253 #else
254 static const unsigned Mod37BitPosition[] = {
255 32, 0, 1, 26, 2, 23, 27, 0, 3, 16, 24, 30, 28, 11, 0, 13,
256 4, 7, 17, 0, 25, 22, 31, 15, 29, 10, 12, 6, 0, 21, 14, 9,
257 5, 20, 8, 19, 18
258 };
259 return Mod37BitPosition[(-Value & Value) % 37];
260 #endif
261 }
262
263 /// CountTrailingOnes_32 - this function performs the operation of
264 /// counting the number of ones from the least significant bit to the first zero
265 /// bit. Ex. CountTrailingOnes_32(0x00FF00FF) == 8.
266 /// Returns 32 if the word is all ones.
CountTrailingOnes_32(uint32_t Value)267 inline unsigned CountTrailingOnes_32(uint32_t Value) {
268 return CountTrailingZeros_32(~Value);
269 }
270
271 /// CountTrailingZeros_64 - This function performs the platform optimal form
272 /// of counting the number of zeros from the least significant bit to the first
273 /// one bit (64 bit edition.)
274 /// Returns 64 if the word is zero.
CountTrailingZeros_64(uint64_t Value)275 inline unsigned CountTrailingZeros_64(uint64_t Value) {
276 #if __GNUC__ >= 4
277 return Value ? __builtin_ctzll(Value) : 64;
278 #else
279 static const unsigned Mod67Position[] = {
280 64, 0, 1, 39, 2, 15, 40, 23, 3, 12, 16, 59, 41, 19, 24, 54,
281 4, 64, 13, 10, 17, 62, 60, 28, 42, 30, 20, 51, 25, 44, 55,
282 47, 5, 32, 65, 38, 14, 22, 11, 58, 18, 53, 63, 9, 61, 27,
283 29, 50, 43, 46, 31, 37, 21, 57, 52, 8, 26, 49, 45, 36, 56,
284 7, 48, 35, 6, 34, 33, 0
285 };
286 return Mod67Position[(-Value & Value) % 67];
287 #endif
288 }
289
290 /// CountTrailingOnes_64 - This function performs the operation
291 /// of counting the number of ones from the least significant bit to the first
292 /// zero bit (64 bit edition.)
293 /// Returns 64 if the word is all ones.
CountTrailingOnes_64(uint64_t Value)294 inline unsigned CountTrailingOnes_64(uint64_t Value) {
295 return CountTrailingZeros_64(~Value);
296 }
297
298 /// CountPopulation_32 - this function counts the number of set bits in a value.
299 /// Ex. CountPopulation(0xF000F000) = 8
300 /// Returns 0 if the word is zero.
CountPopulation_32(uint32_t Value)301 inline unsigned CountPopulation_32(uint32_t Value) {
302 #if __GNUC__ >= 4
303 return __builtin_popcount(Value);
304 #else
305 uint32_t v = Value - ((Value >> 1) & 0x55555555);
306 v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
307 return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
308 #endif
309 }
310
311 /// CountPopulation_64 - this function counts the number of set bits in a value,
312 /// (64 bit edition.)
CountPopulation_64(uint64_t Value)313 inline unsigned CountPopulation_64(uint64_t Value) {
314 #if __GNUC__ >= 4
315 return __builtin_popcountll(Value);
316 #else
317 uint64_t v = Value - ((Value >> 1) & 0x5555555555555555ULL);
318 v = (v & 0x3333333333333333ULL) + ((v >> 2) & 0x3333333333333333ULL);
319 v = (v + (v >> 4)) & 0x0F0F0F0F0F0F0F0FULL;
320 return unsigned((uint64_t)(v * 0x0101010101010101ULL) >> 56);
321 #endif
322 }
323
324 /// Log2_32 - This function returns the floor log base 2 of the specified value,
325 /// -1 if the value is zero. (32 bit edition.)
326 /// Ex. Log2_32(32) == 5, Log2_32(1) == 0, Log2_32(0) == -1, Log2_32(6) == 2
Log2_32(uint32_t Value)327 inline unsigned Log2_32(uint32_t Value) {
328 return 31 - CountLeadingZeros_32(Value);
329 }
330
331 /// Log2_64 - This function returns the floor log base 2 of the specified value,
332 /// -1 if the value is zero. (64 bit edition.)
Log2_64(uint64_t Value)333 inline unsigned Log2_64(uint64_t Value) {
334 return 63 - CountLeadingZeros_64(Value);
335 }
336
337 /// Log2_32_Ceil - This function returns the ceil log base 2 of the specified
338 /// value, 32 if the value is zero. (32 bit edition).
339 /// Ex. Log2_32_Ceil(32) == 5, Log2_32_Ceil(1) == 0, Log2_32_Ceil(6) == 3
Log2_32_Ceil(uint32_t Value)340 inline unsigned Log2_32_Ceil(uint32_t Value) {
341 return 32-CountLeadingZeros_32(Value-1);
342 }
343
344 /// Log2_64_Ceil - This function returns the ceil log base 2 of the specified
345 /// value, 64 if the value is zero. (64 bit edition.)
Log2_64_Ceil(uint64_t Value)346 inline unsigned Log2_64_Ceil(uint64_t Value) {
347 return 64-CountLeadingZeros_64(Value-1);
348 }
349
350 /// GreatestCommonDivisor64 - Return the greatest common divisor of the two
351 /// values using Euclid's algorithm.
GreatestCommonDivisor64(uint64_t A,uint64_t B)352 inline uint64_t GreatestCommonDivisor64(uint64_t A, uint64_t B) {
353 while (B) {
354 uint64_t T = B;
355 B = A % B;
356 A = T;
357 }
358 return A;
359 }
360
361 /// BitsToDouble - This function takes a 64-bit integer and returns the bit
362 /// equivalent double.
BitsToDouble(uint64_t Bits)363 inline double BitsToDouble(uint64_t Bits) {
364 union {
365 uint64_t L;
366 double D;
367 } T;
368 T.L = Bits;
369 return T.D;
370 }
371
372 /// BitsToFloat - This function takes a 32-bit integer and returns the bit
373 /// equivalent float.
BitsToFloat(uint32_t Bits)374 inline float BitsToFloat(uint32_t Bits) {
375 union {
376 uint32_t I;
377 float F;
378 } T;
379 T.I = Bits;
380 return T.F;
381 }
382
383 /// DoubleToBits - This function takes a double and returns the bit
384 /// equivalent 64-bit integer. Note that copying doubles around
385 /// changes the bits of NaNs on some hosts, notably x86, so this
386 /// routine cannot be used if these bits are needed.
DoubleToBits(double Double)387 inline uint64_t DoubleToBits(double Double) {
388 union {
389 uint64_t L;
390 double D;
391 } T;
392 T.D = Double;
393 return T.L;
394 }
395
396 /// FloatToBits - This function takes a float and returns the bit
397 /// equivalent 32-bit integer. Note that copying floats around
398 /// changes the bits of NaNs on some hosts, notably x86, so this
399 /// routine cannot be used if these bits are needed.
FloatToBits(float Float)400 inline uint32_t FloatToBits(float Float) {
401 union {
402 uint32_t I;
403 float F;
404 } T;
405 T.F = Float;
406 return T.I;
407 }
408
409 /// Platform-independent wrappers for the C99 isnan() function.
410 int IsNAN(float f);
411 int IsNAN(double d);
412
413 /// Platform-independent wrappers for the C99 isinf() function.
414 int IsInf(float f);
415 int IsInf(double d);
416
417 /// MinAlign - A and B are either alignments or offsets. Return the minimum
418 /// alignment that may be assumed after adding the two together.
MinAlign(uint64_t A,uint64_t B)419 static inline uint64_t MinAlign(uint64_t A, uint64_t B) {
420 // The largest power of 2 that divides both A and B.
421 return (A | B) & -(A | B);
422 }
423
424 /// NextPowerOf2 - Returns the next power of two (in 64-bits)
425 /// that is strictly greater than A. Returns zero on overflow.
NextPowerOf2(uint64_t A)426 static inline uint64_t NextPowerOf2(uint64_t A) {
427 A |= (A >> 1);
428 A |= (A >> 2);
429 A |= (A >> 4);
430 A |= (A >> 8);
431 A |= (A >> 16);
432 A |= (A >> 32);
433 return A + 1;
434 }
435
436 /// RoundUpToAlignment - Returns the next integer (mod 2**64) that is
437 /// greater than or equal to \arg Value and is a multiple of \arg
438 /// Align. Align must be non-zero.
439 ///
440 /// Examples:
441 /// RoundUpToAlignment(5, 8) = 8
442 /// RoundUpToAlignment(17, 8) = 24
443 /// RoundUpToAlignment(~0LL, 8) = 0
RoundUpToAlignment(uint64_t Value,uint64_t Align)444 inline uint64_t RoundUpToAlignment(uint64_t Value, uint64_t Align) {
445 return ((Value + Align - 1) / Align) * Align;
446 }
447
448 /// OffsetToAlignment - Return the offset to the next integer (mod 2**64) that
449 /// is greater than or equal to \arg Value and is a multiple of \arg
450 /// Align. Align must be non-zero.
OffsetToAlignment(uint64_t Value,uint64_t Align)451 inline uint64_t OffsetToAlignment(uint64_t Value, uint64_t Align) {
452 return RoundUpToAlignment(Value, Align) - Value;
453 }
454
455 /// abs64 - absolute value of a 64-bit int. Not all environments support
456 /// "abs" on whatever their name for the 64-bit int type is. The absolute
457 /// value of the largest negative number is undefined, as with "abs".
abs64(int64_t x)458 inline int64_t abs64(int64_t x) {
459 return (x < 0) ? -x : x;
460 }
461
462 /// SignExtend32 - Sign extend B-bit number x to 32-bit int.
463 /// Usage int32_t r = SignExtend32<5>(x);
SignExtend32(uint32_t x)464 template <unsigned B> inline int32_t SignExtend32(uint32_t x) {
465 return int32_t(x << (32 - B)) >> (32 - B);
466 }
467
468 /// SignExtend64 - Sign extend B-bit number x to 64-bit int.
469 /// Usage int64_t r = SignExtend64<5>(x);
SignExtend64(uint64_t x)470 template <unsigned B> inline int64_t SignExtend64(uint64_t x) {
471 return int64_t(x << (64 - B)) >> (64 - B);
472 }
473
474 } // End llvm namespace
475
476 #endif
477