WPILibC++  unspecified
MathExtras.h
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/Compiler.h"
18 #include <cstdint>
19 #include <algorithm>
20 #include <cassert>
21 #include <cmath>
22 #include <cstring>
23 #include <type_traits>
24 #include <limits>
25 
26 #ifdef _MSC_VER
27 #include <intrin.h>
28 #endif
29 
30 namespace llvm {
32 enum ZeroBehavior {
34  ZB_Undefined,
36  ZB_Max,
38  ZB_Width
39 };
40 
41 namespace detail {
42 template <typename T, std::size_t SizeOfT> struct LeadingZerosCounter {
43  static std::size_t count(T Val, ZeroBehavior) {
44  if (!Val)
45  return std::numeric_limits<T>::digits;
46 
47  // Bisection method.
48  std::size_t ZeroBits = 0;
49  for (T Shift = std::numeric_limits<T>::digits >> 1; Shift; Shift >>= 1) {
50  T Tmp = Val >> Shift;
51  if (Tmp)
52  Val = Tmp;
53  else
54  ZeroBits |= Shift;
55  }
56  return ZeroBits;
57  }
58 };
59 
60 #if __GNUC__ >= 4 || defined(_MSC_VER)
61 template <typename T> struct LeadingZerosCounter<T, 4> {
62  static std::size_t count(T Val, ZeroBehavior ZB) {
63  if (ZB != ZB_Undefined && Val == 0)
64  return 32;
65 
66 #if __has_builtin(__builtin_clz) || LLVM_GNUC_PREREQ(4, 0, 0)
67  return __builtin_clz(Val);
68 #elif defined(_MSC_VER)
69  unsigned long Index;
70  _BitScanReverse(&Index, Val);
71  return Index ^ 31;
72 #endif
73  }
74 };
75 
76 #if !defined(_MSC_VER) || defined(_M_X64)
77 template <typename T> struct LeadingZerosCounter<T, 8> {
78  static std::size_t count(T Val, ZeroBehavior ZB) {
79  if (ZB != ZB_Undefined && Val == 0)
80  return 64;
81 
82 #if __has_builtin(__builtin_clzll) || LLVM_GNUC_PREREQ(4, 0, 0)
83  return __builtin_clzll(Val);
84 #elif defined(_MSC_VER)
85  unsigned long Index;
86  _BitScanReverse64(&Index, Val);
87  return Index ^ 63;
88 #endif
89  }
90 };
91 #endif
92 #endif
93 } // namespace detail
94 
102 template <typename T>
103 std::size_t countLeadingZeros(T Val, ZeroBehavior ZB = ZB_Width) {
104  static_assert(std::numeric_limits<T>::is_integer &&
105  !std::numeric_limits<T>::is_signed,
106  "Only unsigned integral types are allowed.");
108 }
109 
117 template <typename T> T findLastSet(T Val, ZeroBehavior ZB = ZB_Max) {
118  if (ZB == ZB_Max && Val == 0)
119  return std::numeric_limits<T>::max();
120 
121  // Use ^ instead of - because both gcc and llvm can remove the associated ^
122  // in the __builtin_clz intrinsic on x86.
123  return countLeadingZeros(Val, ZB_Undefined) ^
124  (std::numeric_limits<T>::digits - 1);
125 }
126 
130 static const unsigned char BitReverseTable256[256] = {
131 #define R2(n) n, n + 2 * 64, n + 1 * 64, n + 3 * 64
132 #define R4(n) R2(n), R2(n + 2 * 16), R2(n + 1 * 16), R2(n + 3 * 16)
133 #define R6(n) R4(n), R4(n + 2 * 4), R4(n + 1 * 4), R4(n + 3 * 4)
134  R6(0), R6(2), R6(1), R6(3)
135 #undef R2
136 #undef R4
137 #undef R6
138 };
139 
141 template <typename T>
142 T reverseBits(T Val) {
143  unsigned char in[sizeof(Val)];
144  unsigned char out[sizeof(Val)];
145  std::memcpy(in, &Val, sizeof(Val));
146  for (unsigned i = 0; i < sizeof(Val); ++i)
147  out[(sizeof(Val) - i) - 1] = BitReverseTable256[in[i]];
148  std::memcpy(&Val, out, sizeof(Val));
149  return Val;
150 }
151 
152 // NOTE: The following support functions use the _32/_64 extensions instead of
153 // type overloading so that signed and unsigned integers can be used without
154 // ambiguity.
155 
157 inline uint32_t Hi_32(uint64_t Value) {
158  return static_cast<uint32_t>(Value >> 32);
159 }
160 
162 inline uint32_t Lo_32(uint64_t Value) {
163  return static_cast<uint32_t>(Value);
164 }
165 
168 inline uint64_t Make_64(uint32_t High, uint32_t Low) {
169  return ((uint64_t)High << 32) | (uint64_t)Low;
170 }
171 
173 template<unsigned N>
174 inline bool isInt(int64_t x) {
175  return N >= 64 || (-(INT64_C(1)<<(N-1)) <= x && x < (INT64_C(1)<<(N-1)));
176 }
177 // Template specializations to get better code for common cases.
178 template<>
179 inline bool isInt<8>(int64_t x) {
180  return static_cast<int8_t>(x) == x;
181 }
182 template<>
183 inline bool isInt<16>(int64_t x) {
184  return static_cast<int16_t>(x) == x;
185 }
186 template<>
187 inline bool isInt<32>(int64_t x) {
188  return static_cast<int32_t>(x) == x;
189 }
190 
193 template<unsigned N, unsigned S>
194 inline bool isShiftedInt(int64_t x) {
195  return isInt<N+S>(x) && (x % (1<<S) == 0);
196 }
197 
199 template<unsigned N>
200 inline bool isUInt(uint64_t x) {
201  return N >= 64 || x < (UINT64_C(1)<<(N));
202 }
203 // Template specializations to get better code for common cases.
204 template<>
205 inline bool isUInt<8>(uint64_t x) {
206  return static_cast<uint8_t>(x) == x;
207 }
208 template<>
209 inline bool isUInt<16>(uint64_t x) {
210  return static_cast<uint16_t>(x) == x;
211 }
212 template<>
213 inline bool isUInt<32>(uint64_t x) {
214  return static_cast<uint32_t>(x) == x;
215 }
216 
219 template<unsigned N, unsigned S>
220 inline bool isShiftedUInt(uint64_t x) {
221  return isUInt<N+S>(x) && (x % (1<<S) == 0);
222 }
223 
225 inline uint64_t maxUIntN(uint64_t N) {
226  assert(N > 0 && N <= 64 && "integer width out of range");
227 
228  return (UINT64_C(1) << N) - 1;
229 }
230 
232 inline int64_t minIntN(int64_t N) {
233  assert(N > 0 && N <= 64 && "integer width out of range");
234 
235  return -(INT64_C(1)<<(N-1));
236 }
237 
239 inline int64_t maxIntN(int64_t N) {
240  assert(N > 0 && N <= 64 && "integer width out of range");
241 
242  return (INT64_C(1)<<(N-1)) - 1;
243 }
244 
247 inline bool isUIntN(unsigned N, uint64_t x) {
248  return N >= 64 || x <= maxUIntN(N);
249 }
250 
253 inline bool isIntN(unsigned N, int64_t x) {
254  return N >= 64 || (minIntN(N) <= x && x <= maxIntN(N));
255 }
256 
260 inline bool isMask_32(uint32_t Value) {
261  return Value && ((Value + 1) & Value) == 0;
262 }
263 
267 inline bool isMask_64(uint64_t Value) {
268  return Value && ((Value + 1) & Value) == 0;
269 }
270 
274 inline bool isShiftedMask_32(uint32_t Value) {
275  return Value && isMask_32((Value - 1) | Value);
276 }
277 
280 inline bool isShiftedMask_64(uint64_t Value) {
281  return Value && isMask_64((Value - 1) | Value);
282 }
283 
286 inline bool isPowerOf2_32(uint32_t Value) {
287  return Value && !(Value & (Value - 1));
288 }
289 
292 inline bool isPowerOf2_64(uint64_t Value) {
293  return Value && !(Value & (Value - int64_t(1L)));
294 }
295 
304 template <typename T>
305 std::size_t countLeadingOnes(T Value, ZeroBehavior ZB = ZB_Width) {
306  static_assert(std::numeric_limits<T>::is_integer &&
307  !std::numeric_limits<T>::is_signed,
308  "Only unsigned integral types are allowed.");
309  return countLeadingZeros(~Value, ZB);
310 }
311 
312 namespace detail {
313 template <typename T, std::size_t SizeOfT> struct PopulationCounter {
314  static unsigned count(T Value) {
315  // Generic version, forward to 32 bits.
316  static_assert(SizeOfT <= 4, "Not implemented!");
317 #if __GNUC__ >= 4
318  return __builtin_popcount(Value);
319 #else
320  uint32_t v = Value;
321  v = v - ((v >> 1) & 0x55555555);
322  v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
323  return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
324 #endif
325  }
326 };
327 
328 template <typename T> struct PopulationCounter<T, 8> {
329  static unsigned count(T Value) {
330 #if __GNUC__ >= 4
331  return __builtin_popcountll(Value);
332 #else
333  uint64_t v = Value;
334  v = v - ((v >> 1) & 0x5555555555555555ULL);
335  v = (v & 0x3333333333333333ULL) + ((v >> 2) & 0x3333333333333333ULL);
336  v = (v + (v >> 4)) & 0x0F0F0F0F0F0F0F0FULL;
337  return unsigned((uint64_t)(v * 0x0101010101010101ULL) >> 56);
338 #endif
339  }
340 };
341 } // namespace detail
342 
346 template <typename T>
347 inline unsigned countPopulation(T Value) {
348  static_assert(std::numeric_limits<T>::is_integer &&
349  !std::numeric_limits<T>::is_signed,
350  "Only unsigned integral types are allowed.");
352 }
353 
355 inline double Log2(double Value) {
356 #if defined(__ANDROID_API__) && __ANDROID_API__ < 18
357  return __builtin_log(Value) / __builtin_log(2.0);
358 #else
359  return std::log2(Value);
360 #endif
361 }
362 
366 inline unsigned Log2_32(uint32_t Value) {
367  return 31 - countLeadingZeros(Value);
368 }
369 
372 inline unsigned Log2_64(uint64_t Value) {
373  return 63 - countLeadingZeros(Value);
374 }
375 
379 inline unsigned Log2_32_Ceil(uint32_t Value) {
380  return 32 - countLeadingZeros(Value - 1);
381 }
382 
385 inline unsigned Log2_64_Ceil(uint64_t Value) {
386  return 64 - countLeadingZeros(Value - 1);
387 }
388 
391 inline uint64_t GreatestCommonDivisor64(uint64_t A, uint64_t B) {
392  while (B) {
393  uint64_t T = B;
394  B = A % B;
395  A = T;
396  }
397  return A;
398 }
399 
402 inline double BitsToDouble(uint64_t Bits) {
403  union {
404  uint64_t L;
405  double D;
406  } T;
407  T.L = Bits;
408  return T.D;
409 }
410 
413 inline float BitsToFloat(uint32_t Bits) {
414  union {
415  uint32_t I;
416  float F;
417  } T;
418  T.I = Bits;
419  return T.F;
420 }
421 
426 inline uint64_t DoubleToBits(double Double) {
427  union {
428  uint64_t L;
429  double D;
430  } T;
431  T.D = Double;
432  return T.L;
433 }
434 
439 inline uint32_t FloatToBits(float Float) {
440  union {
441  uint32_t I;
442  float F;
443  } T;
444  T.F = Float;
445  return T.I;
446 }
447 
450 inline uint64_t MinAlign(uint64_t A, uint64_t B) {
451  // The largest power of 2 that divides both A and B.
452  //
453  // Replace "-Value" by "1+~Value" in the following commented code to avoid
454  // MSVC warning C4146
455  // return (A | B) & -(A | B);
456  return (A | B) & (1 + ~(A | B));
457 }
458 
463 inline uintptr_t alignAddr(const void *Addr, size_t Alignment) {
464  assert(Alignment && isPowerOf2_64((uint64_t)Alignment) &&
465  "Alignment is not a power of two!");
466 
467  assert((uintptr_t)Addr + Alignment - 1 >= (uintptr_t)Addr);
468 
469  return (((uintptr_t)Addr + Alignment - 1) & ~(uintptr_t)(Alignment - 1));
470 }
471 
474 inline size_t alignmentAdjustment(const void *Ptr, size_t Alignment) {
475  return alignAddr(Ptr, Alignment) - (uintptr_t)Ptr;
476 }
477 
480 inline uint64_t NextPowerOf2(uint64_t A) {
481  A |= (A >> 1);
482  A |= (A >> 2);
483  A |= (A >> 4);
484  A |= (A >> 8);
485  A |= (A >> 16);
486  A |= (A >> 32);
487  return A + 1;
488 }
489 
492 inline uint64_t PowerOf2Floor(uint64_t A) {
493  if (!A) return 0;
494  return 1ull << (63 - countLeadingZeros(A, ZB_Undefined));
495 }
496 
517 inline uint64_t alignTo(uint64_t Value, uint64_t Align, uint64_t Skew = 0) {
518  Skew %= Align;
519  return (Value + Align - 1 - Skew) / Align * Align + Skew;
520 }
521 
524 inline uint64_t alignDown(uint64_t Value, uint64_t Align, uint64_t Skew = 0) {
525  Skew %= Align;
526  return (Value - Skew) / Align * Align + Skew;
527 }
528 
532 inline uint64_t OffsetToAlignment(uint64_t Value, uint64_t Align) {
533  return alignTo(Value, Align) - Value;
534 }
535 
538 template <unsigned B> inline int32_t SignExtend32(uint32_t x) {
539  return int32_t(x << (32 - B)) >> (32 - B);
540 }
541 
544 inline int32_t SignExtend32(uint32_t X, unsigned B) {
545  return int32_t(X << (32 - B)) >> (32 - B);
546 }
547 
550 template <unsigned B> inline int64_t SignExtend64(uint64_t x) {
551  return int64_t(x << (64 - B)) >> (64 - B);
552 }
553 
556 inline int64_t SignExtend64(uint64_t X, unsigned B) {
557  return int64_t(X << (64 - B)) >> (64 - B);
558 }
559 
562 template <typename T>
563 typename std::enable_if<std::is_unsigned<T>::value, T>::type
564 AbsoluteDifference(T X, T Y) {
565  return std::max(X, Y) - std::min(X, Y);
566 }
567 
572 template <typename T>
573 typename std::enable_if<std::is_unsigned<T>::value, T>::type
574 SaturatingAdd(T X, T Y, bool *ResultOverflowed = nullptr) {
575  bool Dummy;
576  bool &Overflowed = ResultOverflowed ? *ResultOverflowed : Dummy;
577  // Hacker's Delight, p. 29
578  T Z = X + Y;
579  Overflowed = (Z < X || Z < Y);
580  if (Overflowed)
581  return std::numeric_limits<T>::max();
582  else
583  return Z;
584 }
585 
590 template <typename T>
591 typename std::enable_if<std::is_unsigned<T>::value, T>::type
592 SaturatingMultiply(T X, T Y, bool *ResultOverflowed = nullptr) {
593  bool Dummy;
594  bool &Overflowed = ResultOverflowed ? *ResultOverflowed : Dummy;
595 
596  // Hacker's Delight, p. 30 has a different algorithm, but we don't use that
597  // because it fails for uint16_t (where multiplication can have undefined
598  // behavior due to promotion to int), and requires a division in addition
599  // to the multiplication.
600 
601  Overflowed = false;
602 
603  // Log2(Z) would be either Log2Z or Log2Z + 1.
604  // Special case: if X or Y is 0, Log2_64 gives -1, and Log2Z
605  // will necessarily be less than Log2Max as desired.
606  int Log2Z = Log2_64(X) + Log2_64(Y);
607  const T Max = std::numeric_limits<T>::max();
608  int Log2Max = Log2_64(Max);
609  if (Log2Z < Log2Max) {
610  return X * Y;
611  }
612  if (Log2Z > Log2Max) {
613  Overflowed = true;
614  return Max;
615  }
616 
617  // We're going to use the top bit, and maybe overflow one
618  // bit past it. Multiply all but the bottom bit then add
619  // that on at the end.
620  T Z = (X >> 1) * Y;
621  if (Z & ~(Max >> 1)) {
622  Overflowed = true;
623  return Max;
624  }
625  Z <<= 1;
626  if (X & 1)
627  return SaturatingAdd(Z, Y, ResultOverflowed);
628 
629  return Z;
630 }
631 
638 template <typename T>
639 typename std::enable_if<std::is_unsigned<T>::value, T>::type
640 SaturatingMultiplyAdd(T X, T Y, T A, bool *ResultOverflowed = nullptr) {
641  bool Dummy;
642  bool &Overflowed = ResultOverflowed ? *ResultOverflowed : Dummy;
643 
644  T Product = SaturatingMultiply(X, Y, &Overflowed);
645  if (Overflowed)
646  return Product;
647 
648  return SaturatingAdd(A, Product, &Overflowed);
649 }
650 
651 } // namespace llvm
652 
653 #endif
Definition: Path.inc:27
Definition: MathExtras.h:42
Definition: MathExtras.h:313