tor-browser

The Tor Browser
git clone https://git.dasho.dev/tor-browser.git
Log | Files | Refs | README | LICENSE

MathAlgorithms.h (12321B)

      1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
      2 /* vim: set ts=8 sts=2 et sw=2 tw=80: */
      3 /* This Source Code Form is subject to the terms of the Mozilla Public
      4 * License, v. 2.0. If a copy of the MPL was not distributed with this
      5 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
      6 
      7 /* mfbt maths algorithms. */
      8 
      9 #ifndef mozilla_MathAlgorithms_h
     10 #define mozilla_MathAlgorithms_h
     11 
     12 #include "mozilla/Assertions.h"
     13 
     14 #include <algorithm>
     15 #include <cmath>
     16 #include <climits>
     17 #include <cstdint>
     18 #include <type_traits>
     19 
     20 namespace mozilla {
     21 
     22 namespace detail {
     23 
     24 template <typename T>
     25 struct AllowDeprecatedAbsFixed : std::false_type {};
     26 
     27 template <>
     28 struct AllowDeprecatedAbsFixed<int32_t> : std::true_type {};
     29 template <>
     30 struct AllowDeprecatedAbsFixed<int64_t> : std::true_type {};
     31 
     32 template <typename T>
     33 struct AllowDeprecatedAbs : AllowDeprecatedAbsFixed<T> {};
     34 
     35 template <>
     36 struct AllowDeprecatedAbs<int> : std::true_type {};
     37 template <>
     38 struct AllowDeprecatedAbs<long> : std::true_type {};
     39 
     40 }  // namespace detail
     41 
     42 // DO NOT USE DeprecatedAbs.  It exists only until its callers can be converted
     43 // to Abs below, and it will be removed when all callers have been changed.
     44 template <typename T>
     45 inline std::enable_if_t<detail::AllowDeprecatedAbs<T>::value, T> DeprecatedAbs(
     46    const T aValue) {
     47  // The absolute value of the smallest possible value of a signed-integer type
     48  // won't fit in that type (on twos-complement systems -- and we're blithely
     49  // assuming we're on such systems, for the non-<stdint.h> types listed above),
     50  // so assert that the input isn't that value.
     51  //
     52  // This is the case if: the value is non-negative; or if adding one (giving a
     53  // value in the range [-maxvalue, 0]), then negating (giving a value in the
     54  // range [0, maxvalue]), doesn't produce maxvalue (because in twos-complement,
     55  // (minvalue + 1) == -maxvalue).
     56  MOZ_ASSERT(aValue >= 0 ||
     57                 -(aValue + 1) != T((1ULL << (CHAR_BIT * sizeof(T) - 1)) - 1),
     58             "You can't negate the smallest possible negative integer!");
     59  return aValue >= 0 ? aValue : -aValue;
     60 }
     61 
     62 namespace detail {
     63 
     64 template <typename T, typename = void>
     65 struct AbsReturnType;
     66 
     67 template <typename T>
     68 struct AbsReturnType<
     69    T, std::enable_if_t<std::is_integral_v<T> && std::is_signed_v<T>>> {
     70  using Type = std::make_unsigned_t<T>;
     71 };
     72 
     73 template <typename T>
     74 struct AbsReturnType<T, std::enable_if_t<std::is_floating_point_v<T>>> {
     75  using Type = T;
     76 };
     77 
     78 }  // namespace detail
     79 
     80 template <typename T>
     81 inline constexpr typename detail::AbsReturnType<T>::Type Abs(const T aValue) {
     82  using ReturnType = typename detail::AbsReturnType<T>::Type;
     83  return aValue >= 0 ? ReturnType(aValue) : ~ReturnType(aValue) + 1;
     84 }
     85 
     86 template <>
     87 inline float Abs<float>(const float aFloat) {
     88  return std::fabs(aFloat);
     89 }
     90 
     91 template <>
     92 inline double Abs<double>(const double aDouble) {
     93  return std::fabs(aDouble);
     94 }
     95 
     96 template <>
     97 inline long double Abs<long double>(const long double aLongDouble) {
     98  return std::fabs(aLongDouble);
     99 }
    100 
    101 }  // namespace mozilla
    102 
    103 namespace mozilla {
    104 
    105 namespace detail {
    106 
    107 // FIXME: use std::count[lr]_zero once we move to C++20
    108 
    109 #if defined(__clang__) || defined(__GNUC__)
    110 
    111 #  if defined(__clang__)
    112 #    if !__has_builtin(__builtin_ctz) || !__has_builtin(__builtin_clz)
    113 #      error "A clang providing __builtin_c[lt]z is required to build"
    114 #    endif
    115 #  else
    116 // gcc has had __builtin_clz and friends since 3.4: no need to check.
    117 #  endif
    118 
    119 constexpr uint_fast8_t CountLeadingZeroes32(uint32_t aValue) {
    120  return static_cast<uint_fast8_t>(__builtin_clz(aValue));
    121 }
    122 
    123 constexpr uint_fast8_t CountTrailingZeroes32(uint32_t aValue) {
    124  return static_cast<uint_fast8_t>(__builtin_ctz(aValue));
    125 }
    126 
    127 constexpr uint_fast8_t CountPopulation32(uint32_t aValue) {
    128  return static_cast<uint_fast8_t>(__builtin_popcount(aValue));
    129 }
    130 
    131 constexpr uint_fast8_t CountPopulation64(uint64_t aValue) {
    132  return static_cast<uint_fast8_t>(__builtin_popcountll(aValue));
    133 }
    134 
    135 constexpr uint_fast8_t CountLeadingZeroes64(uint64_t aValue) {
    136  return static_cast<uint_fast8_t>(__builtin_clzll(aValue));
    137 }
    138 
    139 constexpr uint_fast8_t CountTrailingZeroes64(uint64_t aValue) {
    140  return static_cast<uint_fast8_t>(__builtin_ctzll(aValue));
    141 }
    142 
    143 #else
    144 #  error "Implement these!"
    145 constexpr uint_fast8_t CountLeadingZeroes32(uint32_t aValue) = delete;
    146 constexpr uint_fast8_t CountTrailingZeroes32(uint32_t aValue) = delete;
    147 constexpr uint_fast8_t CountPopulation32(uint32_t aValue) = delete;
    148 constexpr uint_fast8_t CountPopulation64(uint64_t aValue) = delete;
    149 constexpr uint_fast8_t CountLeadingZeroes64(uint64_t aValue) = delete;
    150 constexpr uint_fast8_t CountTrailingZeroes64(uint64_t aValue) = delete;
    151 #endif
    152 
    153 }  // namespace detail
    154 
    155 /**
    156 * Compute the number of high-order zero bits in the NON-ZERO number |aValue|.
    157 * That is, looking at the bitwise representation of the number, with the
    158 * highest- valued bits at the start, return the number of zeroes before the
    159 * first one is observed.
    160 *
    161 * CountLeadingZeroes32(0xF0FF1000) is 0;
    162 * CountLeadingZeroes32(0x7F8F0001) is 1;
    163 * CountLeadingZeroes32(0x3FFF0100) is 2;
    164 * CountLeadingZeroes32(0x1FF50010) is 3; and so on.
    165 */
    166 constexpr uint_fast8_t CountLeadingZeroes32(uint32_t aValue) {
    167  MOZ_ASSERT(aValue != 0);
    168  return detail::CountLeadingZeroes32(aValue);
    169 }
    170 
    171 /**
    172 * Compute the number of low-order zero bits in the NON-ZERO number |aValue|.
    173 * That is, looking at the bitwise representation of the number, with the
    174 * lowest- valued bits at the start, return the number of zeroes before the
    175 * first one is observed.
    176 *
    177 * CountTrailingZeroes32(0x0100FFFF) is 0;
    178 * CountTrailingZeroes32(0x7000FFFE) is 1;
    179 * CountTrailingZeroes32(0x0080FFFC) is 2;
    180 * CountTrailingZeroes32(0x0080FFF8) is 3; and so on.
    181 */
    182 constexpr uint_fast8_t CountTrailingZeroes32(uint32_t aValue) {
    183  MOZ_ASSERT(aValue != 0);
    184  return detail::CountTrailingZeroes32(aValue);
    185 }
    186 
    187 /**
    188 * Compute the number of one bits in the number |aValue|,
    189 */
    190 constexpr uint_fast8_t CountPopulation32(uint32_t aValue) {
    191  return detail::CountPopulation32(aValue);
    192 }
    193 
    194 /** Analogous to CountPopulation32, but for 64-bit numbers */
    195 constexpr uint_fast8_t CountPopulation64(uint64_t aValue) {
    196  return detail::CountPopulation64(aValue);
    197 }
    198 
    199 /** Analogous to CountLeadingZeroes32, but for 64-bit numbers. */
    200 constexpr uint_fast8_t CountLeadingZeroes64(uint64_t aValue) {
    201  MOZ_ASSERT(aValue != 0);
    202  return detail::CountLeadingZeroes64(aValue);
    203 }
    204 
    205 /** Analogous to CountTrailingZeroes32, but for 64-bit numbers. */
    206 constexpr uint_fast8_t CountTrailingZeroes64(uint64_t aValue) {
    207  MOZ_ASSERT(aValue != 0);
    208  return detail::CountTrailingZeroes64(aValue);
    209 }
    210 
    211 namespace detail {
    212 
    213 template <typename T, size_t Size = sizeof(T)>
    214 class CeilingLog2;
    215 
    216 template <typename T>
    217 class CeilingLog2<T, 4> {
    218 public:
    219  static constexpr uint_fast8_t compute(const T aValue) {
    220    // Check for <= 1 to avoid the == 0 undefined case.
    221    return aValue <= 1 ? 0u : 32u - CountLeadingZeroes32(aValue - 1);
    222  }
    223 };
    224 
    225 template <typename T>
    226 class CeilingLog2<T, 8> {
    227 public:
    228  static constexpr uint_fast8_t compute(const T aValue) {
    229    // Check for <= 1 to avoid the == 0 undefined case.
    230    return aValue <= 1 ? 0u : 64u - CountLeadingZeroes64(aValue - 1);
    231  }
    232 };
    233 
    234 }  // namespace detail
    235 
    236 /**
    237 * Compute the log of the least power of 2 greater than or equal to |aValue|.
    238 *
    239 * CeilingLog2(0..1) is 0;
    240 * CeilingLog2(2) is 1;
    241 * CeilingLog2(3..4) is 2;
    242 * CeilingLog2(5..8) is 3;
    243 * CeilingLog2(9..16) is 4; and so on.
    244 */
    245 template <typename T>
    246 constexpr uint_fast8_t CeilingLog2(const T aValue) {
    247  return detail::CeilingLog2<T>::compute(aValue);
    248 }
    249 
    250 /** A CeilingLog2 variant that accepts only size_t. */
    251 constexpr uint_fast8_t CeilingLog2Size(size_t aValue) {
    252  return CeilingLog2(aValue);
    253 }
    254 
    255 /**
    256 * Compute the bit position of the most significant bit set in
    257 * |aValue|. Requires that |aValue| is non-zero.
    258 */
    259 template <typename T>
    260 constexpr uint_fast8_t FindMostSignificantBit(T aValue) {
    261  static_assert(sizeof(T) <= 8);
    262  static_assert(std::is_integral_v<T>);
    263  MOZ_ASSERT(aValue != 0);
    264  // This casts to 32-bits
    265  if constexpr (sizeof(T) <= 4) {
    266    return 31u - CountLeadingZeroes32(aValue);
    267  }
    268  // This doesn't
    269  if constexpr (sizeof(T) == 8) {
    270    return 63u - CountLeadingZeroes64(aValue);
    271  }
    272 }
    273 
    274 /**
    275 * Compute the log of the greatest power of 2 less than or equal to |aValue|.
    276 *
    277 * FloorLog2(0..1) is 0;
    278 * FloorLog2(2..3) is 1;
    279 * FloorLog2(4..7) is 2;
    280 * FloorLog2(8..15) is 3; and so on.
    281 */
    282 template <typename T>
    283 constexpr uint_fast8_t FloorLog2(const T aValue) {
    284  return FindMostSignificantBit(aValue | 1);
    285 }
    286 
    287 /** A FloorLog2 variant that accepts only size_t. */
    288 constexpr uint_fast8_t FloorLog2Size(size_t aValue) {
    289  return FloorLog2(aValue);
    290 }
    291 
    292 /*
    293 * Compute the smallest power of 2 greater than or equal to |x|.  |x| must not
    294 * be so great that the computed value would overflow |size_t|.
    295 */
    296 constexpr size_t RoundUpPow2(size_t aValue) {
    297  MOZ_ASSERT(aValue <= (size_t(1) << (sizeof(size_t) * CHAR_BIT - 1)),
    298             "can't round up -- will overflow!");
    299  return size_t(1) << CeilingLog2(aValue);
    300 }
    301 
    302 /**
    303 * Rotates the bits of the given value left by the amount of the shift width.
    304 */
    305 template <typename T>
    306 MOZ_NO_SANITIZE_UNSIGNED_OVERFLOW constexpr T RotateLeft(const T aValue,
    307                                                         uint_fast8_t aShift) {
    308  static_assert(std::is_unsigned_v<T>, "Rotates require unsigned values");
    309 
    310  MOZ_ASSERT(aShift < sizeof(T) * CHAR_BIT, "Shift value is too large!");
    311  MOZ_ASSERT(aShift > 0,
    312             "Rotation by value length is undefined behavior, but compilers "
    313             "do not currently fold a test into the rotate instruction. "
    314             "Please remove this restriction when compilers optimize the "
    315             "zero case (http://blog.regehr.org/archives/1063).");
    316 
    317  return (aValue << aShift) | (aValue >> (sizeof(T) * CHAR_BIT - aShift));
    318 }
    319 
    320 /**
    321 * Rotates the bits of the given value right by the amount of the shift width.
    322 */
    323 template <typename T>
    324 MOZ_NO_SANITIZE_UNSIGNED_OVERFLOW constexpr T RotateRight(const T aValue,
    325                                                          uint_fast8_t aShift) {
    326  static_assert(std::is_unsigned_v<T>, "Rotates require unsigned values");
    327 
    328  MOZ_ASSERT(aShift < sizeof(T) * CHAR_BIT, "Shift value is too large!");
    329  MOZ_ASSERT(aShift > 0,
    330             "Rotation by value length is undefined behavior, but compilers "
    331             "do not currently fold a test into the rotate instruction. "
    332             "Please remove this restriction when compilers optimize the "
    333             "zero case (http://blog.regehr.org/archives/1063).");
    334 
    335  return (aValue >> aShift) | (aValue << (sizeof(T) * CHAR_BIT - aShift));
    336 }
    337 
    338 /**
    339 * Returns true if |x| is a power of two.
    340 * Zero is not an integer power of two. (-Inf is not an integer)
    341 */
    342 template <typename T>
    343 constexpr bool IsPowerOfTwo(T x) {
    344  static_assert(std::is_unsigned_v<T>, "IsPowerOfTwo requires unsigned values");
    345  return x && (x & (x - 1)) == 0;
    346 }
    347 
    348 template <typename T>
    349 constexpr uint_fast8_t CountTrailingZeroes(T aValue) {
    350  static_assert(sizeof(T) <= 8);
    351  static_assert(std::is_integral_v<T>);
    352  // This casts to 32-bits
    353  if constexpr (sizeof(T) <= 4) {
    354    return CountTrailingZeroes32(aValue);
    355  }
    356  // This doesn't
    357  if constexpr (sizeof(T) == 8) {
    358    return CountTrailingZeroes64(aValue);
    359  }
    360 }
    361 
    362 // Greatest Common Divisor, from
    363 // https://en.wikipedia.org/wiki/Binary_GCD_algorithm#Implementation
    364 template <typename T>
    365 MOZ_ALWAYS_INLINE T GCD(T aA, T aB) {
    366  static_assert(std::is_integral_v<T>);
    367 
    368  MOZ_ASSERT(aA >= 0);
    369  MOZ_ASSERT(aB >= 0);
    370 
    371  if (aA == 0) {
    372    return aB;
    373  }
    374  if (aB == 0) {
    375    return aA;
    376  }
    377 
    378  T az = CountTrailingZeroes(aA);
    379  T bz = CountTrailingZeroes(aB);
    380  T shift = std::min<T>(az, bz);
    381  aA >>= az;
    382  aB >>= bz;
    383 
    384  while (aA != 0) {
    385    if constexpr (!std::is_signed_v<T>) {
    386      if (aA < aB) {
    387        std::swap(aA, aB);
    388      }
    389    }
    390    T diff = aA - aB;
    391    if constexpr (std::is_signed_v<T>) {
    392      aB = std::min<T>(aA, aB);
    393    }
    394    if constexpr (std::is_signed_v<T>) {
    395      aA = std::abs(diff);
    396    } else {
    397      aA = diff;
    398    }
    399    if (aA) {
    400      aA >>= CountTrailingZeroes(aA);
    401    }
    402  }
    403 
    404  return aB << shift;
    405 }
    406 
    407 } /* namespace mozilla */
    408 
    409 #endif /* mozilla_MathAlgorithms_h */