summaryrefslogtreecommitdiff
path: root/mfbt/MathAlgorithms.h
diff options
context:
space:
mode:
Diffstat (limited to 'mfbt/MathAlgorithms.h')
-rw-r--r--mfbt/MathAlgorithms.h547
1 files changed, 547 insertions, 0 deletions
diff --git a/mfbt/MathAlgorithms.h b/mfbt/MathAlgorithms.h
new file mode 100644
index 0000000000..4db6de497b
--- /dev/null
+++ b/mfbt/MathAlgorithms.h
@@ -0,0 +1,547 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* vim: set ts=8 sts=2 et sw=2 tw=80: */
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+/* mfbt maths algorithms. */
+
+#ifndef mozilla_MathAlgorithms_h
+#define mozilla_MathAlgorithms_h
+
+#include "mozilla/Assertions.h"
+#include "mozilla/TypeTraits.h"
+
+#include <cmath>
+#include <limits.h>
+#include <stdint.h>
+
+namespace mozilla {
+
+// Greatest Common Divisor
+template<typename IntegerType>
+MOZ_ALWAYS_INLINE IntegerType
+EuclidGCD(IntegerType aA, IntegerType aB)
+{
+ // Euclid's algorithm; O(N) in the worst case. (There are better
+ // ways, but we don't need them for the current use of this algo.)
+ MOZ_ASSERT(aA > IntegerType(0));
+ MOZ_ASSERT(aB > IntegerType(0));
+
+ while (aA != aB) {
+ if (aA > aB) {
+ aA = aA - aB;
+ } else {
+ aB = aB - aA;
+ }
+ }
+
+ return aA;
+}
+
+// Least Common Multiple
+template<typename IntegerType>
+MOZ_ALWAYS_INLINE IntegerType
+EuclidLCM(IntegerType aA, IntegerType aB)
+{
+ // Divide first to reduce overflow risk.
+ return (aA / EuclidGCD(aA, aB)) * aB;
+}
+
+namespace detail {
+
+template<typename T>
+struct AllowDeprecatedAbsFixed : FalseType {};
+
+template<> struct AllowDeprecatedAbsFixed<int32_t> : TrueType {};
+template<> struct AllowDeprecatedAbsFixed<int64_t> : TrueType {};
+
+template<typename T>
+struct AllowDeprecatedAbs : AllowDeprecatedAbsFixed<T> {};
+
+template<> struct AllowDeprecatedAbs<int> : TrueType {};
+template<> struct AllowDeprecatedAbs<long> : TrueType {};
+
+} // namespace detail
+
+// DO NOT USE DeprecatedAbs. It exists only until its callers can be converted
+// to Abs below, and it will be removed when all callers have been changed.
+template<typename T>
+inline typename mozilla::EnableIf<detail::AllowDeprecatedAbs<T>::value, T>::Type
+DeprecatedAbs(const T aValue)
+{
+ // The absolute value of the smallest possible value of a signed-integer type
+ // won't fit in that type (on twos-complement systems -- and we're blithely
+ // assuming we're on such systems, for the non-<stdint.h> types listed above),
+ // so assert that the input isn't that value.
+ //
+ // This is the case if: the value is non-negative; or if adding one (giving a
+ // value in the range [-maxvalue, 0]), then negating (giving a value in the
+ // range [0, maxvalue]), doesn't produce maxvalue (because in twos-complement,
+ // (minvalue + 1) == -maxvalue).
+ MOZ_ASSERT(aValue >= 0 ||
+ -(aValue + 1) != T((1ULL << (CHAR_BIT * sizeof(T) - 1)) - 1),
+ "You can't negate the smallest possible negative integer!");
+ return aValue >= 0 ? aValue : -aValue;
+}
+
+namespace detail {
+
+// For now mozilla::Abs only takes intN_T, the signed natural types, and
+// float/double/long double. Feel free to add overloads for other standard,
+// signed types if you need them.
+
+template<typename T>
+struct AbsReturnTypeFixed;
+
+template<> struct AbsReturnTypeFixed<int8_t> { typedef uint8_t Type; };
+template<> struct AbsReturnTypeFixed<int16_t> { typedef uint16_t Type; };
+template<> struct AbsReturnTypeFixed<int32_t> { typedef uint32_t Type; };
+template<> struct AbsReturnTypeFixed<int64_t> { typedef uint64_t Type; };
+
+template<typename T>
+struct AbsReturnType : AbsReturnTypeFixed<T> {};
+
+template<> struct AbsReturnType<char> :
+ EnableIf<char(-1) < char(0), unsigned char> {};
+template<> struct AbsReturnType<signed char> { typedef unsigned char Type; };
+template<> struct AbsReturnType<short> { typedef unsigned short Type; };
+template<> struct AbsReturnType<int> { typedef unsigned int Type; };
+template<> struct AbsReturnType<long> { typedef unsigned long Type; };
+template<> struct AbsReturnType<long long> { typedef unsigned long long Type; };
+template<> struct AbsReturnType<float> { typedef float Type; };
+template<> struct AbsReturnType<double> { typedef double Type; };
+template<> struct AbsReturnType<long double> { typedef long double Type; };
+
+} // namespace detail
+
+template<typename T>
+inline typename detail::AbsReturnType<T>::Type
+Abs(const T aValue)
+{
+ typedef typename detail::AbsReturnType<T>::Type ReturnType;
+ return aValue >= 0 ? ReturnType(aValue) : ~ReturnType(aValue) + 1;
+}
+
+template<>
+inline float
+Abs<float>(const float aFloat)
+{
+ return std::fabs(aFloat);
+}
+
+template<>
+inline double
+Abs<double>(const double aDouble)
+{
+ return std::fabs(aDouble);
+}
+
+template<>
+inline long double
+Abs<long double>(const long double aLongDouble)
+{
+ return std::fabs(aLongDouble);
+}
+
+} // namespace mozilla
+
+#if defined(_MSC_VER) && \
+ (defined(_M_IX86) || defined(_M_AMD64) || defined(_M_X64))
+# define MOZ_BITSCAN_WINDOWS
+
+# include <intrin.h>
+# pragma intrinsic(_BitScanForward, _BitScanReverse)
+
+# if defined(_M_AMD64) || defined(_M_X64)
+# define MOZ_BITSCAN_WINDOWS64
+# pragma intrinsic(_BitScanForward64, _BitScanReverse64)
+# endif
+
+#endif
+
+namespace mozilla {
+
+namespace detail {
+
+#if defined(MOZ_BITSCAN_WINDOWS)
+
+inline uint_fast8_t
+CountLeadingZeroes32(uint32_t aValue)
+{
+ unsigned long index;
+ if (!_BitScanReverse(&index, static_cast<unsigned long>(aValue)))
+ return 32;
+ return uint_fast8_t(31 - index);
+}
+
+
+inline uint_fast8_t
+CountTrailingZeroes32(uint32_t aValue)
+{
+ unsigned long index;
+ if (!_BitScanForward(&index, static_cast<unsigned long>(aValue)))
+ return 32;
+ return uint_fast8_t(index);
+}
+
+inline uint_fast8_t
+CountPopulation32(uint32_t aValue)
+{
+ uint32_t x = aValue - ((aValue >> 1) & 0x55555555);
+ x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
+ return (((x + (x >> 4)) & 0xf0f0f0f) * 0x1010101) >> 24;
+}
+inline uint_fast8_t
+CountPopulation64(uint64_t aValue)
+{
+ return uint_fast8_t(CountPopulation32(aValue & 0xffffffff) +
+ CountPopulation32(aValue >> 32));
+}
+
+inline uint_fast8_t
+CountLeadingZeroes64(uint64_t aValue)
+{
+#if defined(MOZ_BITSCAN_WINDOWS64)
+ unsigned long index;
+ if (!_BitScanReverse64(&index, static_cast<unsigned __int64>(aValue)))
+ return 64;
+ return uint_fast8_t(63 - index);
+#else
+ uint32_t hi = uint32_t(aValue >> 32);
+ if (hi != 0) {
+ return CountLeadingZeroes32(hi);
+ }
+ return 32u + CountLeadingZeroes32(uint32_t(aValue));
+#endif
+}
+
+inline uint_fast8_t
+CountTrailingZeroes64(uint64_t aValue)
+{
+#if defined(MOZ_BITSCAN_WINDOWS64)
+ unsigned long index;
+ if (!_BitScanForward64(&index, static_cast<unsigned __int64>(aValue)))
+ return 64;
+ return uint_fast8_t(index);
+#else
+ uint32_t lo = uint32_t(aValue);
+ if (lo != 0) {
+ return CountTrailingZeroes32(lo);
+ }
+ return 32u + CountTrailingZeroes32(uint32_t(aValue >> 32));
+#endif
+}
+
+# ifdef MOZ_HAVE_BITSCAN64
+# undef MOZ_HAVE_BITSCAN64
+# endif
+
+#elif defined(__clang__) || defined(__GNUC__)
+
+# if defined(__clang__)
+# if !__has_builtin(__builtin_ctz) || !__has_builtin(__builtin_clz)
+# error "A clang providing __builtin_c[lt]z is required to build"
+# endif
+# else
+ // gcc has had __builtin_clz and friends since 3.4: no need to check.
+# endif
+
+inline uint_fast8_t
+CountLeadingZeroes32(uint32_t aValue)
+{
+ return __builtin_clz(aValue);
+}
+
+inline uint_fast8_t
+CountTrailingZeroes32(uint32_t aValue)
+{
+ return __builtin_ctz(aValue);
+}
+
+inline uint_fast8_t
+CountPopulation32(uint32_t aValue)
+{
+ return __builtin_popcount(aValue);
+}
+
+inline uint_fast8_t
+CountPopulation64(uint64_t aValue)
+{
+ return __builtin_popcountll(aValue);
+}
+
+inline uint_fast8_t
+CountLeadingZeroes64(uint64_t aValue)
+{
+ return __builtin_clzll(aValue);
+}
+
+inline uint_fast8_t
+CountTrailingZeroes64(uint64_t aValue)
+{
+ return __builtin_ctzll(aValue);
+}
+
+#else
+# error "Implement these!"
+inline uint_fast8_t CountLeadingZeroes32(uint32_t aValue) = delete;
+inline uint_fast8_t CountTrailingZeroes32(uint32_t aValue) = delete;
+inline uint_fast8_t CountPopulation32(uint32_t aValue) = delete;
+inline uint_fast8_t CountPopulation64(uint64_t aValue) = delete;
+inline uint_fast8_t CountLeadingZeroes64(uint64_t aValue) = delete;
+inline uint_fast8_t CountTrailingZeroes64(uint64_t aValue) = delete;
+#endif
+
+} // namespace detail
+
+/**
+ * Compute the number of high-order zero bits in the NON-ZERO number |aValue|.
+ * That is, looking at the bitwise representation of the number, with the
+ * highest- valued bits at the start, return the number of zeroes before the
+ * first one is observed.
+ *
+ * CountLeadingZeroes32(0xF0FF1000) is 0;
+ * CountLeadingZeroes32(0x7F8F0001) is 1;
+ * CountLeadingZeroes32(0x3FFF0100) is 2;
+ * CountLeadingZeroes32(0x1FF50010) is 3; and so on.
+ */
+inline uint_fast8_t
+CountLeadingZeroes32(uint32_t aValue)
+{
+ MOZ_ASSERT(aValue != 0);
+ return detail::CountLeadingZeroes32(aValue);
+}
+
+/**
+ * Compute the number of low-order zero bits in the NON-ZERO number |aValue|.
+ * That is, looking at the bitwise representation of the number, with the
+ * lowest- valued bits at the start, return the number of zeroes before the
+ * first one is observed.
+ *
+ * CountTrailingZeroes32(0x0100FFFF) is 0;
+ * CountTrailingZeroes32(0x7000FFFE) is 1;
+ * CountTrailingZeroes32(0x0080FFFC) is 2;
+ * CountTrailingZeroes32(0x0080FFF8) is 3; and so on.
+ */
+inline uint_fast8_t
+CountTrailingZeroes32(uint32_t aValue)
+{
+ MOZ_ASSERT(aValue != 0);
+ return detail::CountTrailingZeroes32(aValue);
+}
+
+/**
+ * Compute the number of one bits in the number |aValue|,
+ */
+inline uint_fast8_t
+CountPopulation32(uint32_t aValue)
+{
+ return detail::CountPopulation32(aValue);
+}
+
+/** Analogous to CountPopulation32, but for 64-bit numbers */
+inline uint_fast8_t
+CountPopulation64(uint64_t aValue)
+{
+ return detail::CountPopulation64(aValue);
+}
+
+/** Analogous to CountLeadingZeroes32, but for 64-bit numbers. */
+inline uint_fast8_t
+CountLeadingZeroes64(uint64_t aValue)
+{
+ MOZ_ASSERT(aValue != 0);
+ return detail::CountLeadingZeroes64(aValue);
+}
+
+/** Analogous to CountTrailingZeroes32, but for 64-bit numbers. */
+inline uint_fast8_t
+CountTrailingZeroes64(uint64_t aValue)
+{
+ MOZ_ASSERT(aValue != 0);
+ return detail::CountTrailingZeroes64(aValue);
+}
+
+namespace detail {
+
+template<typename T, size_t Size = sizeof(T)>
+class CeilingLog2;
+
+template<typename T>
+class CeilingLog2<T, 4>
+{
+public:
+ static uint_fast8_t compute(const T aValue)
+ {
+ // Check for <= 1 to avoid the == 0 undefined case.
+ return aValue <= 1 ? 0u : 32u - CountLeadingZeroes32(aValue - 1);
+ }
+};
+
+template<typename T>
+class CeilingLog2<T, 8>
+{
+public:
+ static uint_fast8_t compute(const T aValue)
+ {
+ // Check for <= 1 to avoid the == 0 undefined case.
+ return aValue <= 1 ? 0u : 64u - CountLeadingZeroes64(aValue - 1);
+ }
+};
+
+} // namespace detail
+
+/**
+ * Compute the log of the least power of 2 greater than or equal to |aValue|.
+ *
+ * CeilingLog2(0..1) is 0;
+ * CeilingLog2(2) is 1;
+ * CeilingLog2(3..4) is 2;
+ * CeilingLog2(5..8) is 3;
+ * CeilingLog2(9..16) is 4; and so on.
+ */
+template<typename T>
+inline uint_fast8_t
+CeilingLog2(const T aValue)
+{
+ return detail::CeilingLog2<T>::compute(aValue);
+}
+
+/** A CeilingLog2 variant that accepts only size_t. */
+inline uint_fast8_t
+CeilingLog2Size(size_t aValue)
+{
+ return CeilingLog2(aValue);
+}
+
+namespace detail {
+
+template<typename T, size_t Size = sizeof(T)>
+class FloorLog2;
+
+template<typename T>
+class FloorLog2<T, 4>
+{
+public:
+ static uint_fast8_t compute(const T aValue)
+ {
+ return 31u - CountLeadingZeroes32(aValue | 1);
+ }
+};
+
+template<typename T>
+class FloorLog2<T, 8>
+{
+public:
+ static uint_fast8_t compute(const T aValue)
+ {
+ return 63u - CountLeadingZeroes64(aValue | 1);
+ }
+};
+
+} // namespace detail
+
+/**
+ * Compute the log of the greatest power of 2 less than or equal to |aValue|.
+ *
+ * FloorLog2(0..1) is 0;
+ * FloorLog2(2..3) is 1;
+ * FloorLog2(4..7) is 2;
+ * FloorLog2(8..15) is 3; and so on.
+ */
+template<typename T>
+inline uint_fast8_t
+FloorLog2(const T aValue)
+{
+ return detail::FloorLog2<T>::compute(aValue);
+}
+
+/** A FloorLog2 variant that accepts only size_t. */
+inline uint_fast8_t
+FloorLog2Size(size_t aValue)
+{
+ return FloorLog2(aValue);
+}
+
+/*
+ * Compute the smallest power of 2 greater than or equal to |x|. |x| must not
+ * be so great that the computed value would overflow |size_t|.
+ */
+inline size_t
+RoundUpPow2(size_t aValue)
+{
+ MOZ_ASSERT(aValue <= (size_t(1) << (sizeof(size_t) * CHAR_BIT - 1)),
+ "can't round up -- will overflow!");
+ return size_t(1) << CeilingLog2(aValue);
+}
+
+/**
+ * Rotates the bits of the given value left by the amount of the shift width.
+ */
+template<typename T>
+inline T
+RotateLeft(const T aValue, uint_fast8_t aShift)
+{
+ MOZ_ASSERT(aShift < sizeof(T) * CHAR_BIT, "Shift value is too large!");
+ MOZ_ASSERT(aShift > 0,
+ "Rotation by value length is undefined behavior, but compilers "
+ "do not currently fold a test into the rotate instruction. "
+ "Please remove this restriction when compilers optimize the "
+ "zero case (http://blog.regehr.org/archives/1063).");
+ static_assert(IsUnsigned<T>::value, "Rotates require unsigned values");
+ return (aValue << aShift) | (aValue >> (sizeof(T) * CHAR_BIT - aShift));
+}
+
+/**
+ * Rotates the bits of the given value right by the amount of the shift width.
+ */
+template<typename T>
+inline T
+RotateRight(const T aValue, uint_fast8_t aShift)
+{
+ MOZ_ASSERT(aShift < sizeof(T) * CHAR_BIT, "Shift value is too large!");
+ MOZ_ASSERT(aShift > 0,
+ "Rotation by value length is undefined behavior, but compilers "
+ "do not currently fold a test into the rotate instruction. "
+ "Please remove this restriction when compilers optimize the "
+ "zero case (http://blog.regehr.org/archives/1063).");
+ static_assert(IsUnsigned<T>::value, "Rotates require unsigned values");
+ return (aValue >> aShift) | (aValue << (sizeof(T) * CHAR_BIT - aShift));
+}
+
+/**
+ * Returns true if |x| is a power of two.
+ * Zero is not an integer power of two. (-Inf is not an integer)
+ */
+template<typename T>
+constexpr bool
+IsPowerOfTwo(T x)
+{
+ static_assert(IsUnsigned<T>::value,
+ "IsPowerOfTwo requires unsigned values");
+ return x && (x & (x - 1)) == 0;
+}
+
+template<typename T>
+inline T
+Clamp(const T aValue, const T aMin, const T aMax)
+{
+ static_assert(IsIntegral<T>::value,
+ "Clamp accepts only integral types, so that it doesn't have"
+ " to distinguish differently-signed zeroes (which users may"
+ " or may not care to distinguish, likely at a perf cost) or"
+ " to decide how to clamp NaN or a range with a NaN"
+ " endpoint.");
+ MOZ_ASSERT(aMin <= aMax);
+
+ if (aValue <= aMin)
+ return aMin;
+ if (aValue >= aMax)
+ return aMax;
+ return aValue;
+}
+
+} /* namespace mozilla */
+
+#endif /* mozilla_MathAlgorithms_h */
generated by cgit v1.2.3 (git 2.26.2) at 2024-11-10 14:22:04 +0000