The Tor Browser: comparison mfbt/MathAlgorithms.h

--1:000000000000
+:340231384103
+/* -*- 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 a, IntegerType b)
+{
+// 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(a > 0);
+MOZ_ASSERT(b > 0);
+while (a != b) {
+if (a > b) {
+a = a - b;
+} else {
+b = b - a;
+}
+}
+return a;
+}
+// Least Common Multiple
+template<typename IntegerType>
+MOZ_ALWAYS_INLINE IntegerType
+EuclidLCM(IntegerType a, IntegerType b)
+{
+// Divide first to reduce overflow risk.
+return (a / EuclidGCD(a, b)) * b;
+}
+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 t)
+{
+// 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(t >= 0 ||
+-(t + 1) != T((1ULL << (CHAR_BIT * sizeof(T) - 1)) - 1),
+"You can't negate the smallest possible negative integer!");
+return t >= 0 ? t : -t;
+}
+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 t)
+{
+typedef typename detail::AbsReturnType<T>::Type ReturnType;
+return t >= 0 ? ReturnType(t) : ~ReturnType(t) + 1;
+}
+template<>
+inline float
+Abs<float>(const float f)
+{
+return std::fabs(f);
+}
+template<>
+inline double
+Abs<double>(const double d)
+{
+return std::fabs(d);
+}
+template<>
+inline long double
+Abs<long double>(const long double d)
+{
+return std::fabs(d);
+}
+} // namespace mozilla
+#if defined(_WIN32) && (_MSC_VER >= 1300) && (defined(_M_IX86) || defined(_M_AMD64) || defined(_M_X64))
+#  define MOZ_BITSCAN_WINDOWS
+extern "C" {
+unsigned char _BitScanForward(unsigned long* Index, unsigned long mask);
+unsigned char _BitScanReverse(unsigned long* Index, unsigned long mask);
+#  pragma intrinsic(_BitScanForward, _BitScanReverse)
+#  if defined(_M_AMD64) || defined(_M_X64)
+#    define MOZ_BITSCAN_WINDOWS64
+unsigned char _BitScanForward64(unsigned long* index, unsigned __int64 mask);
+unsigned char _BitScanReverse64(unsigned long* index, unsigned __int64 mask);
+#   pragma intrinsic(_BitScanForward64, _BitScanReverse64)
+#  endif
+} // extern "C"
+#endif
+namespace mozilla {
+namespace detail {
+#if defined(MOZ_BITSCAN_WINDOWS)
+inline uint_fast8_t
+CountLeadingZeroes32(uint32_t u)
+{
+unsigned long index;
+_BitScanReverse(&index, static_cast<unsigned long>(u));
+return uint_fast8_t(31 - index);
+}
+inline uint_fast8_t
+CountTrailingZeroes32(uint32_t u)
+{
+unsigned long index;
+_BitScanForward(&index, static_cast<unsigned long>(u));
+return uint_fast8_t(index);
+}
+inline uint_fast8_t
+CountPopulation32(uint32_t u)
+{
+uint32_t x = u - ((u >> 1) & 0x55555555);
+x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
+return (((x + (x >> 4)) & 0xf0f0f0f) * 0x1010101) >> 24;
+}
+inline uint_fast8_t
+CountLeadingZeroes64(uint64_t u)
+{
+#  if defined(MOZ_BITSCAN_WINDOWS64)
+unsigned long index;
+_BitScanReverse64(&index, static_cast<unsigned __int64>(u));
+return uint_fast8_t(63 - index);
+#  else
+uint32_t hi = uint32_t(u >> 32);
+if (hi != 0)
+return CountLeadingZeroes32(hi);
+return 32 + CountLeadingZeroes32(uint32_t(u));
+#  endif
+}
+inline uint_fast8_t
+CountTrailingZeroes64(uint64_t u)
+{
+#  if defined(MOZ_BITSCAN_WINDOWS64)
+unsigned long index;
+_BitScanForward64(&index, static_cast<unsigned __int64>(u));
+return uint_fast8_t(index);
+#  else
+uint32_t lo = uint32_t(u);
+if (lo != 0)
+return CountTrailingZeroes32(lo);
+return 32 + CountTrailingZeroes32(uint32_t(u >> 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 u)
+{
+return __builtin_clz(u);
+}
+inline uint_fast8_t
+CountTrailingZeroes32(uint32_t u)
+{
+return __builtin_ctz(u);
+}
+inline uint_fast8_t
+CountPopulation32(uint32_t u)
+{
+return __builtin_popcount(u);
+}
+inline uint_fast8_t
+CountLeadingZeroes64(uint64_t u)
+{
+return __builtin_clzll(u);
+}
+inline uint_fast8_t
+CountTrailingZeroes64(uint64_t u)
+{
+return __builtin_ctzll(u);
+}
+#else
+#  error "Implement these!"
+inline uint_fast8_t CountLeadingZeroes32(uint32_t u) MOZ_DELETE;
+inline uint_fast8_t CountTrailingZeroes32(uint32_t u) MOZ_DELETE;
+inline uint_fast8_t CountPopulation32(uint32_t u) MOZ_DELETE;
+inline uint_fast8_t CountLeadingZeroes64(uint64_t u) MOZ_DELETE;
+inline uint_fast8_t CountTrailingZeroes64(uint64_t u) MOZ_DELETE;
+#endif
+} // namespace detail
+/**
+* Compute the number of high-order zero bits in the NON-ZERO number |u|.  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 u)
+{
+MOZ_ASSERT(u != 0);
+return detail::CountLeadingZeroes32(u);
+}
+/**
+* Compute the number of low-order zero bits in the NON-ZERO number |u|.  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 u)
+{
+MOZ_ASSERT(u != 0);
+return detail::CountTrailingZeroes32(u);
+}
+/**
+* Compute the number of one bits in the number |u|,
+*/
+inline uint_fast8_t
+CountPopulation32(uint32_t u)
+{
+return detail::CountPopulation32(u);
+}
+/** Analogous to CountLeadingZeroes32, but for 64-bit numbers. */
+inline uint_fast8_t
+CountLeadingZeroes64(uint64_t u)
+{
+MOZ_ASSERT(u != 0);
+return detail::CountLeadingZeroes64(u);
+}
+/** Analogous to CountTrailingZeroes32, but for 64-bit numbers. */
+inline uint_fast8_t
+CountTrailingZeroes64(uint64_t u)
+{
+MOZ_ASSERT(u != 0);
+return detail::CountTrailingZeroes64(u);
+}
+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 t) {
+// Check for <= 1 to avoid the == 0 undefined case.
+return t <= 1 ? 0 : 32 - CountLeadingZeroes32(t - 1);
+}
+};
+template<typename T>
+class CeilingLog2<T, 8>
+{
+public:
+static uint_fast8_t compute(const T t) {
+// Check for <= 1 to avoid the == 0 undefined case.
+return t <= 1 ? 0 : 64 - CountLeadingZeroes64(t - 1);
+}
+};
+} // namespace detail
+/**
+* Compute the log of the least power of 2 greater than or equal to |t|.
+*
+* 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 t)
+{
+return detail::CeilingLog2<T>::compute(t);
+}
+/** A CeilingLog2 variant that accepts only size_t. */
+inline uint_fast8_t
+CeilingLog2Size(size_t n)
+{
+return CeilingLog2(n);
+}
+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 t) {
+return 31 - CountLeadingZeroes32(t | 1);
+}
+};
+template<typename T>
+class FloorLog2<T, 8>
+{
+public:
+static uint_fast8_t compute(const T t) {
+return 63 - CountLeadingZeroes64(t | 1);
+}
+};
+} // namespace detail
+/**
+* Compute the log of the greatest power of 2 less than or equal to |t|.
+*
+* 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 t)
+{
+return detail::FloorLog2<T>::compute(t);
+}
+/** A FloorLog2 variant that accepts only size_t. */
+inline uint_fast8_t
+FloorLog2Size(size_t n)
+{
+return FloorLog2(n);
+}
+/*
+* 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 x)
+{
+MOZ_ASSERT(x <= (size_t(1) << (sizeof(size_t) * CHAR_BIT - 1)),
+"can't round up -- will overflow!");
+return size_t(1) << CeilingLog2(x);
+}
+/**
+* Rotates the bits of the given value left by the amount of the shift width.
+*/
+template<typename T>
+inline T
+RotateLeft(const T t, uint_fast8_t shift)
+{
+MOZ_ASSERT(shift < sizeof(T) * CHAR_BIT, "Shift value is too large!");
+static_assert(IsUnsigned<T>::value, "Rotates require unsigned values");
+return (t << shift) | (t >> (sizeof(T) * CHAR_BIT - shift));
+}
+/**
+* Rotates the bits of the given value right by the amount of the shift width.
+*/
+template<typename T>
+inline T
+RotateRight(const T t, uint_fast8_t shift)
+{
+MOZ_ASSERT(shift < sizeof(T) * CHAR_BIT, "Shift value is too large!");
+static_assert(IsUnsigned<T>::value, "Rotates require unsigned values");
+return (t >> shift) | (t << (sizeof(T) * CHAR_BIT - shift));
+}
+} /* namespace mozilla */
+#endif /* mozilla_MathAlgorithms_h */

The Tor Browser / file comparison

comparison: mfbt/MathAlgorithms.h

mfbt/MathAlgorithms.h