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 <algorithm>
  16 #include <limits.h>
  17 #include <stdint.h>
  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 #if defined(_MSC_VER) && (defined(_M_IX86) || defined(_M_AMD64) || \
 104                           defined(_M_X64) || defined(_M_ARM64))
 105 #  define MOZ_BITSCAN_WINDOWS
 106
 107 #  include <intrin.h>
 108 #  pragma intrinsic(_BitScanForward, _BitScanReverse)
 109
 110 #  if defined(_M_AMD64) || defined(_M_X64) || defined(_M_ARM64)
 111 #    define MOZ_BITSCAN_WINDOWS64
 112 #    pragma intrinsic(_BitScanForward64, _BitScanReverse64)
 113 #  endif
 114
 115 #endif
 116
 117 namespace mozilla {
 118
 119 namespace detail {
 120
 121 #if defined(MOZ_BITSCAN_WINDOWS)
 122
 123 inline uint_fast8_t CountLeadingZeroes32(uint32_t aValue) {
 124   unsigned long index;
 125   if (!_BitScanReverse(&index, static_cast<unsigned long>(aValue))) return 32;
 126   return uint_fast8_t(31 - index);
 127 }
 128
 129 inline uint_fast8_t CountTrailingZeroes32(uint32_t aValue) {
 130   unsigned long index;
 131   if (!_BitScanForward(&index, static_cast<unsigned long>(aValue))) return 32;
 132   return uint_fast8_t(index);
 133 }
 134
 135 inline uint_fast8_t CountPopulation32(uint32_t aValue) {
 136   uint32_t x = aValue - ((aValue >> 1) & 0x55555555);
 137   x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
 138   return (((x + (x >> 4)) & 0xf0f0f0f) * 0x1010101) >> 24;
 139 }
 140 inline uint_fast8_t CountPopulation64(uint64_t aValue) {
 141   return uint_fast8_t(CountPopulation32(aValue & 0xffffffff) +
 142                       CountPopulation32(aValue >> 32));
 143 }
 144
 145 inline uint_fast8_t CountLeadingZeroes64(uint64_t aValue) {
 146 #  if defined(MOZ_BITSCAN_WINDOWS64)
 147   unsigned long index;
 148   if (!_BitScanReverse64(&index, static_cast<unsigned __int64>(aValue)))
 149     return 64;
 150   return uint_fast8_t(63 - index);
 151 #  else
 152   uint32_t hi = uint32_t(aValue >> 32);
 153   if (hi != 0) {
 154     return CountLeadingZeroes32(hi);
 155   }
 156   return 32u + CountLeadingZeroes32(uint32_t(aValue));
 157 #  endif
 158 }
 159
 160 inline uint_fast8_t CountTrailingZeroes64(uint64_t aValue) {
 161 #  if defined(MOZ_BITSCAN_WINDOWS64)
 162   unsigned long index;
 163   if (!_BitScanForward64(&index, static_cast<unsigned __int64>(aValue)))
 164     return 64;
 165   return uint_fast8_t(index);
 166 #  else
 167   uint32_t lo = uint32_t(aValue);
 168   if (lo != 0) {
 169     return CountTrailingZeroes32(lo);
 170   }
 171   return 32u + CountTrailingZeroes32(uint32_t(aValue >> 32));
 172 #  endif
 173 }
 174
 175 #elif defined(__clang__) || defined(__GNUC__)
 176
 177 #  if defined(__clang__)
 178 #    if !__has_builtin(__builtin_ctz) || !__has_builtin(__builtin_clz)
 179 #      error "A clang providing __builtin_c[lt]z is required to build"
 180 #    endif
 181 #  else
 182 // gcc has had __builtin_clz and friends since 3.4: no need to check.
 183 #  endif
 184
 185 inline uint_fast8_t CountLeadingZeroes32(uint32_t aValue) {
 186   return static_cast<uint_fast8_t>(__builtin_clz(aValue));
 187 }
 188
 189 inline uint_fast8_t CountTrailingZeroes32(uint32_t aValue) {
 190   return static_cast<uint_fast8_t>(__builtin_ctz(aValue));
 191 }
 192
 193 inline uint_fast8_t CountPopulation32(uint32_t aValue) {
 194   return static_cast<uint_fast8_t>(__builtin_popcount(aValue));
 195 }
 196
 197 inline uint_fast8_t CountPopulation64(uint64_t aValue) {
 198   return static_cast<uint_fast8_t>(__builtin_popcountll(aValue));
 199 }
 200
 201 inline uint_fast8_t CountLeadingZeroes64(uint64_t aValue) {
 202   return static_cast<uint_fast8_t>(__builtin_clzll(aValue));
 203 }
 204
 205 inline uint_fast8_t CountTrailingZeroes64(uint64_t aValue) {
 206   return static_cast<uint_fast8_t>(__builtin_ctzll(aValue));
 207 }
 208
 209 #else
 210 #  error "Implement these!"
 211 inline uint_fast8_t CountLeadingZeroes32(uint32_t aValue) = delete;
 212 inline uint_fast8_t CountTrailingZeroes32(uint32_t aValue) = delete;
 213 inline uint_fast8_t CountPopulation32(uint32_t aValue) = delete;
 214 inline uint_fast8_t CountPopulation64(uint64_t aValue) = delete;
 215 inline uint_fast8_t CountLeadingZeroes64(uint64_t aValue) = delete;
 216 inline uint_fast8_t CountTrailingZeroes64(uint64_t aValue) = delete;
 217 #endif
 218
 219 }  // namespace detail
 220
 221 /**
 222  * Compute the number of high-order zero bits in the NON-ZERO number |aValue|.
 223  * That is, looking at the bitwise representation of the number, with the
 224  * highest- valued bits at the start, return the number of zeroes before the
 225  * first one is observed.
 226  *
 227  * CountLeadingZeroes32(0xF0FF1000) is 0;
 228  * CountLeadingZeroes32(0x7F8F0001) is 1;
 229  * CountLeadingZeroes32(0x3FFF0100) is 2;
 230  * CountLeadingZeroes32(0x1FF50010) is 3; and so on.
 231  */
 232 inline uint_fast8_t CountLeadingZeroes32(uint32_t aValue) {
 233   MOZ_ASSERT(aValue != 0);
 234   return detail::CountLeadingZeroes32(aValue);
 235 }
 236
 237 /**
 238  * Compute the number of low-order zero bits in the NON-ZERO number |aValue|.
 239  * That is, looking at the bitwise representation of the number, with the
 240  * lowest- valued bits at the start, return the number of zeroes before the
 241  * first one is observed.
 242  *
 243  * CountTrailingZeroes32(0x0100FFFF) is 0;
 244  * CountTrailingZeroes32(0x7000FFFE) is 1;
 245  * CountTrailingZeroes32(0x0080FFFC) is 2;
 246  * CountTrailingZeroes32(0x0080FFF8) is 3; and so on.
 247  */
 248 inline uint_fast8_t CountTrailingZeroes32(uint32_t aValue) {
 249   MOZ_ASSERT(aValue != 0);
 250   return detail::CountTrailingZeroes32(aValue);
 251 }
 252
 253 /**
 254  * Compute the number of one bits in the number |aValue|,
 255  */
 256 inline uint_fast8_t CountPopulation32(uint32_t aValue) {
 257   return detail::CountPopulation32(aValue);
 258 }
 259
 260 /** Analogous to CountPopulation32, but for 64-bit numbers */
 261 inline uint_fast8_t CountPopulation64(uint64_t aValue) {
 262   return detail::CountPopulation64(aValue);
 263 }
 264
 265 /** Analogous to CountLeadingZeroes32, but for 64-bit numbers. */
 266 inline uint_fast8_t CountLeadingZeroes64(uint64_t aValue) {
 267   MOZ_ASSERT(aValue != 0);
 268   return detail::CountLeadingZeroes64(aValue);
 269 }
 270
 271 /** Analogous to CountTrailingZeroes32, but for 64-bit numbers. */
 272 inline uint_fast8_t CountTrailingZeroes64(uint64_t aValue) {
 273   MOZ_ASSERT(aValue != 0);
 274   return detail::CountTrailingZeroes64(aValue);
 275 }
 276
 277 namespace detail {
 278
 279 template <typename T, size_t Size = sizeof(T)>
 280 class CeilingLog2;
 281
 282 template <typename T>
 283 class CeilingLog2<T, 4> {
 284  public:
 285   static uint_fast8_t compute(const T aValue) {
 286     // Check for <= 1 to avoid the == 0 undefined case.
 287     return aValue <= 1 ? 0u : 32u - CountLeadingZeroes32(aValue - 1);
 288   }
 289 };
 290
 291 template <typename T>
 292 class CeilingLog2<T, 8> {
 293  public:
 294   static uint_fast8_t compute(const T aValue) {
 295     // Check for <= 1 to avoid the == 0 undefined case.
 296     return aValue <= 1 ? 0u : 64u - CountLeadingZeroes64(aValue - 1);
 297   }
 298 };
 299
 300 }  // namespace detail
 301
 302 /**
 303  * Compute the log of the least power of 2 greater than or equal to |aValue|.
 304  *
 305  * CeilingLog2(0..1) is 0;
 306  * CeilingLog2(2) is 1;
 307  * CeilingLog2(3..4) is 2;
 308  * CeilingLog2(5..8) is 3;
 309  * CeilingLog2(9..16) is 4; and so on.
 310  */
 311 template <typename T>
 312 inline uint_fast8_t CeilingLog2(const T aValue) {
 313   return detail::CeilingLog2<T>::compute(aValue);
 314 }
 315
 316 /** A CeilingLog2 variant that accepts only size_t. */
 317 inline uint_fast8_t CeilingLog2Size(size_t aValue) {
 318   return CeilingLog2(aValue);
 319 }
 320
 321 namespace detail {
 322
 323 template <typename T, size_t Size = sizeof(T)>
 324 class FloorLog2;
 325
 326 template <typename T>
 327 class FloorLog2<T, 4> {
 328  public:
 329   static uint_fast8_t compute(const T aValue) {
 330     return 31u - CountLeadingZeroes32(aValue | 1);
 331   }
 332 };
 333
 334 template <typename T>
 335 class FloorLog2<T, 8> {
 336  public:
 337   static uint_fast8_t compute(const T aValue) {
 338     return 63u - CountLeadingZeroes64(aValue | 1);
 339   }
 340 };
 341
 342 }  // namespace detail
 343
 344 /**
 345  * Compute the log of the greatest power of 2 less than or equal to |aValue|.
 346  *
 347  * FloorLog2(0..1) is 0;
 348  * FloorLog2(2..3) is 1;
 349  * FloorLog2(4..7) is 2;
 350  * FloorLog2(8..15) is 3; and so on.
 351  */
 352 template <typename T>
 353 inline constexpr uint_fast8_t FloorLog2(const T aValue) {
 354   return detail::FloorLog2<T>::compute(aValue);
 355 }
 356
 357 /** A FloorLog2 variant that accepts only size_t. */
 358 inline uint_fast8_t FloorLog2Size(size_t aValue) { return FloorLog2(aValue); }
 359
 360 /*
 361  * Compute the smallest power of 2 greater than or equal to |x|.  |x| must not
 362  * be so great that the computed value would overflow |size_t|.
 363  */
 364 inline size_t RoundUpPow2(size_t aValue) {
 365   MOZ_ASSERT(aValue <= (size_t(1) << (sizeof(size_t) * CHAR_BIT - 1)),
 366              "can't round up -- will overflow!");
 367   return size_t(1) << CeilingLog2(aValue);
 368 }
 369
 370 /**
 371  * Rotates the bits of the given value left by the amount of the shift width.
 372  */
 373 template <typename T>
 374 MOZ_NO_SANITIZE_UNSIGNED_OVERFLOW inline T RotateLeft(const T aValue,
 375                                                       uint_fast8_t aShift) {
 376   static_assert(std::is_unsigned_v<T>, "Rotates require unsigned values");
 377
 378   MOZ_ASSERT(aShift < sizeof(T) * CHAR_BIT, "Shift value is too large!");
 379   MOZ_ASSERT(aShift > 0,
 380              "Rotation by value length is undefined behavior, but compilers "
 381              "do not currently fold a test into the rotate instruction. "
 382              "Please remove this restriction when compilers optimize the "
 383              "zero case (http://blog.regehr.org/archives/1063).");
 384
 385   return (aValue << aShift) | (aValue >> (sizeof(T) * CHAR_BIT - aShift));
 386 }
 387
 388 /**
 389  * Rotates the bits of the given value right by the amount of the shift width.
 390  */
 391 template <typename T>
 392 MOZ_NO_SANITIZE_UNSIGNED_OVERFLOW inline T RotateRight(const T aValue,
 393                                                        uint_fast8_t aShift) {
 394   static_assert(std::is_unsigned_v<T>, "Rotates require unsigned values");
 395
 396   MOZ_ASSERT(aShift < sizeof(T) * CHAR_BIT, "Shift value is too large!");
 397   MOZ_ASSERT(aShift > 0,
 398              "Rotation by value length is undefined behavior, but compilers "
 399              "do not currently fold a test into the rotate instruction. "
 400              "Please remove this restriction when compilers optimize the "
 401              "zero case (http://blog.regehr.org/archives/1063).");
 402
 403   return (aValue >> aShift) | (aValue << (sizeof(T) * CHAR_BIT - aShift));
 404 }
 405
 406 /**
 407  * Returns true if |x| is a power of two.
 408  * Zero is not an integer power of two. (-Inf is not an integer)
 409  */
 410 template <typename T>
 411 constexpr bool IsPowerOfTwo(T x) {
 412   static_assert(std::is_unsigned_v<T>, "IsPowerOfTwo requires unsigned values");
 413   return x && (x & (x - 1)) == 0;
 414 }
 415
 416 template <typename T>
 417 inline T Clamp(const T aValue, const T aMin, const T aMax) {
 418   static_assert(std::is_integral_v<T>,
 419                 "Clamp accepts only integral types, so that it doesn't have"
 420                 " to distinguish differently-signed zeroes (which users may"
 421                 " or may not care to distinguish, likely at a perf cost) or"
 422                 " to decide how to clamp NaN or a range with a NaN"
 423                 " endpoint.");
 424   MOZ_ASSERT(aMin <= aMax);
 425
 426   if (aValue <= aMin) return aMin;
 427   if (aValue >= aMax) return aMax;
 428   return aValue;
 429 }
 430
 431 template <typename T>
 432 inline uint_fast8_t CountTrailingZeroes(T aValue) {
 433   static_assert(sizeof(T) <= 8);
 434   static_assert(std::is_integral_v<T>);
 435   // This casts to 32-bits
 436   if constexpr (sizeof(T) <= 4) {
 437     return CountTrailingZeroes32(aValue);
 438   }
 439   // This doesn't
 440   if constexpr (sizeof(T) == 8) {
 441     return CountTrailingZeroes64(aValue);
 442   }
 443 }
 444
 445 // Greatest Common Divisor, from
 446 // https://en.wikipedia.org/wiki/Binary_GCD_algorithm#Implementation
 447 template <typename T>
 448 MOZ_ALWAYS_INLINE T GCD(T aA, T aB) {
 449   static_assert(std::is_integral_v<T>);
 450
 451   MOZ_ASSERT(aA >= 0);
 452   MOZ_ASSERT(aB >= 0);
 453
 454   if (aA == 0) {
 455     return aB;
 456   }
 457   if (aB == 0) {
 458     return aA;
 459   }
 460
 461   T az = CountTrailingZeroes(aA);
 462   T bz = CountTrailingZeroes(aB);
 463   T shift = std::min<T>(az, bz);
 464   aA >>= az;
 465   aB >>= bz;
 466
 467   while (aA != 0) {
 468     if constexpr (!std::is_signed_v<T>) {
 469       if (aA < aB) {
 470         std::swap(aA, aB);
 471       }
 472     }
 473     T diff = aA - aB;
 474     if constexpr (std::is_signed_v<T>) {
 475       aB = std::min<T>(aA, aB);
 476     }
 477     if constexpr (std::is_signed_v<T>) {
 478       aA = std::abs(diff);
 479     } else {
 480       aA = diff;
 481     }
 482     if (aA) {
 483       aA >>= CountTrailingZeroes(aA);
 484     }
 485   }
 486
 487   return aB << shift;
 488 }
 489
 490 } /* namespace mozilla */
 491
 492 #endif /* mozilla_MathAlgorithms_h */