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