mfbt/MathAlgorithms.h

   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 <cmath>
  15 #include <limits.h>
  16 #include <stdint.h>
  17 #include <type_traits>
  18
  19 namespace mozilla {
  20
  21 // Greatest Common Divisor
  22 template <typename IntegerType>
  23 MOZ_ALWAYS_INLINE IntegerType EuclidGCD(IntegerType aA, IntegerType aB) {
  24   // Euclid's algorithm; O(N) in the worst case.  (There are better
  25   // ways, but we don't need them for the current use of this algo.)
  26   MOZ_ASSERT(aA > IntegerType(0));
  27   MOZ_ASSERT(aB > IntegerType(0));
  28
  29   while (aA != aB) {
  30     if (aA > aB) {
  31       aA = aA - aB;
  32     } else {
  33       aB = aB - aA;
  34     }
  35   }
  36
  37   return aA;
  38 }
  39
  40 // Least Common Multiple
  41 template <typename IntegerType>
  42 MOZ_ALWAYS_INLINE IntegerType EuclidLCM(IntegerType aA, IntegerType aB) {
  43   // Divide first to reduce overflow risk.
  44   return (aA / EuclidGCD(aA, aB)) * aB;
  45 }
  46
  47 namespace detail {
  48
  49 template <typename T>
  50 struct AllowDeprecatedAbsFixed : std::false_type {};
  51
  52 template <>
  53 struct AllowDeprecatedAbsFixed<int32_t> : std::true_type {};
  54 template <>
  55 struct AllowDeprecatedAbsFixed<int64_t> : std::true_type {};
  56
  57 template <typename T>
  58 struct AllowDeprecatedAbs : AllowDeprecatedAbsFixed<T> {};
  59
  60 template <>
  61 struct AllowDeprecatedAbs<int> : std::true_type {};
  62 template <>
  63 struct AllowDeprecatedAbs<long> : std::true_type {};
  64
  65 }  // namespace detail
  66
  67 // DO NOT USE DeprecatedAbs.  It exists only until its callers can be converted
  68 // to Abs below, and it will be removed when all callers have been changed.
  69 template <typename T>
  70 inline std::enable_if_t<detail::AllowDeprecatedAbs<T>::value, T> DeprecatedAbs(
  71     const T aValue) {
  72   // The absolute value of the smallest possible value of a signed-integer type
  73   // won't fit in that type (on twos-complement systems -- and we're blithely
  74   // assuming we're on such systems, for the non-<stdint.h> types listed above),
  75   // so assert that the input isn't that value.
  76   //
  77   // This is the case if: the value is non-negative; or if adding one (giving a
  78   // value in the range [-maxvalue, 0]), then negating (giving a value in the
  79   // range [0, maxvalue]), doesn't produce maxvalue (because in twos-complement,
  80   // (minvalue + 1) == -maxvalue).
  81   MOZ_ASSERT(aValue >= 0 ||
  82                  -(aValue + 1) != T((1ULL << (CHAR_BIT * sizeof(T) - 1)) - 1),
  83              "You can't negate the smallest possible negative integer!");
  84   return aValue >= 0 ? aValue : -aValue;
  85 }
  86
  87 namespace detail {
  88
  89 template <typename T, typename = void>
  90 struct AbsReturnType;
  91
  92 template <typename T>
  93 struct AbsReturnType<
  94     T, std::enable_if_t<std::is_integral_v<T> && std::is_signed_v<T>>> {
  95   using Type = std::make_unsigned_t<T>;
  96 };
  97
  98 template <typename T>
  99 struct AbsReturnType<T, std::enable_if_t<std::is_floating_point_v<T>>> {
 100   using Type = T;
 101 };
 102
 103 }  // namespace detail
 104
 105 template <typename T>
 106 inline constexpr typename detail::AbsReturnType<T>::Type Abs(const T aValue) {
 107   using ReturnType = typename detail::AbsReturnType<T>::Type;
 108   return aValue >= 0 ? ReturnType(aValue) : ~ReturnType(aValue) + 1;
 109 }
 110
 111 template <>
 112 inline float Abs<float>(const float aFloat) {
 113   return std::fabs(aFloat);
 114 }
 115
 116 template <>
 117 inline double Abs<double>(const double aDouble) {
 118   return std::fabs(aDouble);
 119 }
 120
 121 template <>
 122 inline long double Abs<long double>(const long double aLongDouble) {
 123   return std::fabs(aLongDouble);
 124 }
 125
 126 }  // namespace mozilla
 127
 128 #if defined(_MSC_VER) && (defined(_M_IX86) || defined(_M_AMD64) || \
 129                           defined(_M_X64) || defined(_M_ARM64))
 130 #  define MOZ_BITSCAN_WINDOWS
 131
 132 #  include <intrin.h>
 133 #  pragma intrinsic(_BitScanForward, _BitScanReverse)
 134
 135 #  if defined(_M_AMD64) || defined(_M_X64) || defined(_M_ARM64)
 136 #    define MOZ_BITSCAN_WINDOWS64
 137 #    pragma intrinsic(_BitScanForward64, _BitScanReverse64)
 138 #  endif
 139
 140 #endif
 141
 142 namespace mozilla {
 143
 144 namespace detail {
 145
 146 #if defined(MOZ_BITSCAN_WINDOWS)
 147
 148 inline uint_fast8_t CountLeadingZeroes32(uint32_t aValue) {
 149   unsigned long index;
 150   if (!_BitScanReverse(&index, static_cast<unsigned long>(aValue))) return 32;
 151   return uint_fast8_t(31 - index);
 152 }
 153
 154 inline uint_fast8_t CountTrailingZeroes32(uint32_t aValue) {
 155   unsigned long index;
 156   if (!_BitScanForward(&index, static_cast<unsigned long>(aValue))) return 32;
 157   return uint_fast8_t(index);
 158 }
 159
 160 inline uint_fast8_t CountPopulation32(uint32_t aValue) {
 161   uint32_t x = aValue - ((aValue >> 1) & 0x55555555);
 162   x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
 163   return (((x + (x >> 4)) & 0xf0f0f0f) * 0x1010101) >> 24;
 164 }
 165 inline uint_fast8_t CountPopulation64(uint64_t aValue) {
 166   return uint_fast8_t(CountPopulation32(aValue & 0xffffffff) +
 167                       CountPopulation32(aValue >> 32));
 168 }
 169
 170 inline uint_fast8_t CountLeadingZeroes64(uint64_t aValue) {
 171 #  if defined(MOZ_BITSCAN_WINDOWS64)
 172   unsigned long index;
 173   if (!_BitScanReverse64(&index, static_cast<unsigned __int64>(aValue)))
 174     return 64;
 175   return uint_fast8_t(63 - index);
 176 #  else
 177   uint32_t hi = uint32_t(aValue >> 32);
 178   if (hi != 0) {
 179     return CountLeadingZeroes32(hi);
 180   }
 181   return 32u + CountLeadingZeroes32(uint32_t(aValue));
 182 #  endif
 183 }
 184
 185 inline uint_fast8_t CountTrailingZeroes64(uint64_t aValue) {
 186 #  if defined(MOZ_BITSCAN_WINDOWS64)
 187   unsigned long index;
 188   if (!_BitScanForward64(&index, static_cast<unsigned __int64>(aValue)))
 189     return 64;
 190   return uint_fast8_t(index);
 191 #  else
 192   uint32_t lo = uint32_t(aValue);
 193   if (lo != 0) {
 194     return CountTrailingZeroes32(lo);
 195   }
 196   return 32u + CountTrailingZeroes32(uint32_t(aValue >> 32));
 197 #  endif
 198 }
 199
 200 #elif defined(__clang__) || defined(__GNUC__)
 201
 202 #  if defined(__clang__)
 203 #    if !__has_builtin(__builtin_ctz) || !__has_builtin(__builtin_clz)
 204 #      error "A clang providing __builtin_c[lt]z is required to build"
 205 #    endif
 206 #  else
 207 // gcc has had __builtin_clz and friends since 3.4: no need to check.
 208 #  endif
 209
 210 inline uint_fast8_t CountLeadingZeroes32(uint32_t aValue) {
 211   return static_cast<uint_fast8_t>(__builtin_clz(aValue));
 212 }
 213
 214 inline uint_fast8_t CountTrailingZeroes32(uint32_t aValue) {
 215   return static_cast<uint_fast8_t>(__builtin_ctz(aValue));
 216 }
 217
 218 inline uint_fast8_t CountPopulation32(uint32_t aValue) {
 219   return static_cast<uint_fast8_t>(__builtin_popcount(aValue));
 220 }
 221
 222 inline uint_fast8_t CountPopulation64(uint64_t aValue) {
 223   return static_cast<uint_fast8_t>(__builtin_popcountll(aValue));
 224 }
 225
 226 inline uint_fast8_t CountLeadingZeroes64(uint64_t aValue) {
 227   return static_cast<uint_fast8_t>(__builtin_clzll(aValue));
 228 }
 229
 230 inline uint_fast8_t CountTrailingZeroes64(uint64_t aValue) {
 231   return static_cast<uint_fast8_t>(__builtin_ctzll(aValue));
 232 }
 233
 234 #else
 235 #  error "Implement these!"
 236 inline uint_fast8_t CountLeadingZeroes32(uint32_t aValue) = delete;
 237 inline uint_fast8_t CountTrailingZeroes32(uint32_t aValue) = delete;
 238 inline uint_fast8_t CountPopulation32(uint32_t aValue) = delete;
 239 inline uint_fast8_t CountPopulation64(uint64_t aValue) = delete;
 240 inline uint_fast8_t CountLeadingZeroes64(uint64_t aValue) = delete;
 241 inline uint_fast8_t CountTrailingZeroes64(uint64_t aValue) = delete;
 242 #endif
 243
 244 }  // namespace detail
 245
 246 /**
 247  * Compute the number of high-order zero bits in the NON-ZERO number |aValue|.
 248  * That is, looking at the bitwise representation of the number, with the
 249  * highest- valued bits at the start, return the number of zeroes before the
 250  * first one is observed.
 251  *
 252  * CountLeadingZeroes32(0xF0FF1000) is 0;
 253  * CountLeadingZeroes32(0x7F8F0001) is 1;
 254  * CountLeadingZeroes32(0x3FFF0100) is 2;
 255  * CountLeadingZeroes32(0x1FF50010) is 3; and so on.
 256  */
 257 inline uint_fast8_t CountLeadingZeroes32(uint32_t aValue) {
 258   MOZ_ASSERT(aValue != 0);
 259   return detail::CountLeadingZeroes32(aValue);
 260 }
 261
 262 /**
 263  * Compute the number of low-order zero bits in the NON-ZERO number |aValue|.
 264  * That is, looking at the bitwise representation of the number, with the
 265  * lowest- valued bits at the start, return the number of zeroes before the
 266  * first one is observed.
 267  *
 268  * CountTrailingZeroes32(0x0100FFFF) is 0;
 269  * CountTrailingZeroes32(0x7000FFFE) is 1;
 270  * CountTrailingZeroes32(0x0080FFFC) is 2;
 271  * CountTrailingZeroes32(0x0080FFF8) is 3; and so on.
 272  */
 273 inline uint_fast8_t CountTrailingZeroes32(uint32_t aValue) {
 274   MOZ_ASSERT(aValue != 0);
 275   return detail::CountTrailingZeroes32(aValue);
 276 }
 277
 278 /**
 279  * Compute the number of one bits in the number |aValue|,
 280  */
 281 inline uint_fast8_t CountPopulation32(uint32_t aValue) {
 282   return detail::CountPopulation32(aValue);
 283 }
 284
 285 /** Analogous to CountPopulation32, but for 64-bit numbers */
 286 inline uint_fast8_t CountPopulation64(uint64_t aValue) {
 287   return detail::CountPopulation64(aValue);
 288 }
 289
 290 /** Analogous to CountLeadingZeroes32, but for 64-bit numbers. */
 291 inline uint_fast8_t CountLeadingZeroes64(uint64_t aValue) {
 292   MOZ_ASSERT(aValue != 0);
 293   return detail::CountLeadingZeroes64(aValue);
 294 }
 295
 296 /** Analogous to CountTrailingZeroes32, but for 64-bit numbers. */
 297 inline uint_fast8_t CountTrailingZeroes64(uint64_t aValue) {
 298   MOZ_ASSERT(aValue != 0);
 299   return detail::CountTrailingZeroes64(aValue);
 300 }
 301
 302 namespace detail {
 303
 304 template <typename T, size_t Size = sizeof(T)>
 305 class CeilingLog2;
 306
 307 template <typename T>
 308 class CeilingLog2<T, 4> {
 309  public:
 310   static uint_fast8_t compute(const T aValue) {
 311     // Check for <= 1 to avoid the == 0 undefined case.
 312     return aValue <= 1 ? 0u : 32u - CountLeadingZeroes32(aValue - 1);
 313   }
 314 };
 315
 316 template <typename T>
 317 class CeilingLog2<T, 8> {
 318  public:
 319   static uint_fast8_t compute(const T aValue) {
 320     // Check for <= 1 to avoid the == 0 undefined case.
 321     return aValue <= 1 ? 0u : 64u - CountLeadingZeroes64(aValue - 1);
 322   }
 323 };
 324
 325 }  // namespace detail
 326
 327 /**
 328  * Compute the log of the least power of 2 greater than or equal to |aValue|.
 329  *
 330  * CeilingLog2(0..1) is 0;
 331  * CeilingLog2(2) is 1;
 332  * CeilingLog2(3..4) is 2;
 333  * CeilingLog2(5..8) is 3;
 334  * CeilingLog2(9..16) is 4; and so on.
 335  */
 336 template <typename T>
 337 inline uint_fast8_t CeilingLog2(const T aValue) {
 338   return detail::CeilingLog2<T>::compute(aValue);
 339 }
 340
 341 /** A CeilingLog2 variant that accepts only size_t. */
 342 inline uint_fast8_t CeilingLog2Size(size_t aValue) {
 343   return CeilingLog2(aValue);
 344 }
 345
 346 namespace detail {
 347
 348 template <typename T, size_t Size = sizeof(T)>
 349 class FloorLog2;
 350
 351 template <typename T>
 352 class FloorLog2<T, 4> {
 353  public:
 354   static uint_fast8_t compute(const T aValue) {
 355     return 31u - CountLeadingZeroes32(aValue | 1);
 356   }
 357 };
 358
 359 template <typename T>
 360 class FloorLog2<T, 8> {
 361  public:
 362   static uint_fast8_t compute(const T aValue) {
 363     return 63u - CountLeadingZeroes64(aValue | 1);
 364   }
 365 };
 366
 367 }  // namespace detail
 368
 369 /**
 370  * Compute the log of the greatest power of 2 less than or equal to |aValue|.
 371  *
 372  * FloorLog2(0..1) is 0;
 373  * FloorLog2(2..3) is 1;
 374  * FloorLog2(4..7) is 2;
 375  * FloorLog2(8..15) is 3; and so on.
 376  */
 377 template <typename T>
 378 inline constexpr uint_fast8_t FloorLog2(const T aValue) {
 379   return detail::FloorLog2<T>::compute(aValue);
 380 }
 381
 382 /** A FloorLog2 variant that accepts only size_t. */
 383 inline uint_fast8_t FloorLog2Size(size_t aValue) { return FloorLog2(aValue); }
 384
 385 /*
 386  * Compute the smallest power of 2 greater than or equal to |x|.  |x| must not
 387  * be so great that the computed value would overflow |size_t|.
 388  */
 389 inline size_t RoundUpPow2(size_t aValue) {
 390   MOZ_ASSERT(aValue <= (size_t(1) << (sizeof(size_t) * CHAR_BIT - 1)),
 391              "can't round up -- will overflow!");
 392   return size_t(1) << CeilingLog2(aValue);
 393 }
 394
 395 /**
 396  * Rotates the bits of the given value left by the amount of the shift width.
 397  */
 398 template <typename T>
 399 MOZ_NO_SANITIZE_UNSIGNED_OVERFLOW inline T RotateLeft(const T aValue,
 400                                                       uint_fast8_t aShift) {
 401   static_assert(std::is_unsigned_v<T>, "Rotates require unsigned values");
 402
 403   MOZ_ASSERT(aShift < sizeof(T) * CHAR_BIT, "Shift value is too large!");
 404   MOZ_ASSERT(aShift > 0,
 405              "Rotation by value length is undefined behavior, but compilers "
 406              "do not currently fold a test into the rotate instruction. "
 407              "Please remove this restriction when compilers optimize the "
 408              "zero case (http://blog.regehr.org/archives/1063).");
 409
 410   return (aValue << aShift) | (aValue >> (sizeof(T) * CHAR_BIT - aShift));
 411 }
 412
 413 /**
 414  * Rotates the bits of the given value right by the amount of the shift width.
 415  */
 416 template <typename T>
 417 MOZ_NO_SANITIZE_UNSIGNED_OVERFLOW inline T RotateRight(const T aValue,
 418                                                        uint_fast8_t aShift) {
 419   static_assert(std::is_unsigned_v<T>, "Rotates require unsigned values");
 420
 421   MOZ_ASSERT(aShift < sizeof(T) * CHAR_BIT, "Shift value is too large!");
 422   MOZ_ASSERT(aShift > 0,
 423              "Rotation by value length is undefined behavior, but compilers "
 424              "do not currently fold a test into the rotate instruction. "
 425              "Please remove this restriction when compilers optimize the "
 426              "zero case (http://blog.regehr.org/archives/1063).");
 427
 428   return (aValue >> aShift) | (aValue << (sizeof(T) * CHAR_BIT - aShift));
 429 }
 430
 431 /**
 432  * Returns true if |x| is a power of two.
 433  * Zero is not an integer power of two. (-Inf is not an integer)
 434  */
 435 template <typename T>
 436 constexpr bool IsPowerOfTwo(T x) {
 437   static_assert(std::is_unsigned_v<T>, "IsPowerOfTwo requires unsigned values");
 438   return x && (x & (x - 1)) == 0;
 439 }
 440
 441 template <typename T>
 442 inline T Clamp(const T aValue, const T aMin, const T aMax) {
 443   static_assert(std::is_integral_v<T>,
 444                 "Clamp accepts only integral types, so that it doesn't have"
 445                 " to distinguish differently-signed zeroes (which users may"
 446                 " or may not care to distinguish, likely at a perf cost) or"
 447                 " to decide how to clamp NaN or a range with a NaN"
 448                 " endpoint.");
 449   MOZ_ASSERT(aMin <= aMax);
 450
 451   if (aValue <= aMin) return aMin;
 452   if (aValue >= aMax) return aMax;
 453   return aValue;
 454 }
 455
 456 } /* namespace mozilla */
 457
 458 #endif /* mozilla_MathAlgorithms_h */