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