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
  24 EuclidGCD(IntegerType aA, IntegerType aB)
  25 {
  26   // Euclid's algorithm; O(N) in the worst case.  (There are better
  27   // ways, but we don't need them for the current use of this algo.)
  28   MOZ_ASSERT(aA > IntegerType(0));
  29   MOZ_ASSERT(aB > IntegerType(0));
  30
  31   while (aA != aB) {
  32     if (aA > aB) {
  33       aA = aA - aB;
  34     } else {
  35       aB = aB - aA;
  36     }
  37   }
  38
  39   return aA;
  40 }
  41
  42 // Least Common Multiple
  43 template<typename IntegerType>
  44 MOZ_ALWAYS_INLINE IntegerType
  45 EuclidLCM(IntegerType aA, IntegerType aB)
  46 {
  47   // Divide first to reduce overflow risk.
  48   return (aA / EuclidGCD(aA, aB)) * aB;
  49 }
  50
  51 namespace detail {
  52
  53 template<typename T>
  54 struct AllowDeprecatedAbsFixed : FalseType {};
  55
  56 template<> struct AllowDeprecatedAbsFixed<int32_t> : TrueType {};
  57 template<> struct AllowDeprecatedAbsFixed<int64_t> : TrueType {};
  58
  59 template<typename T>
  60 struct AllowDeprecatedAbs : AllowDeprecatedAbsFixed<T> {};
  61
  62 template<> struct AllowDeprecatedAbs<int> : TrueType {};
  63 template<> 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 {
  73   // The absolute value of the smallest possible value of a signed-integer type
  74   // won't fit in that type (on twos-complement systems -- and we're blithely
  75   // assuming we're on such systems, for the non-<stdint.h> types listed above),
  76   // so assert that the input isn't that value.
  77   //
  78   // This is the case if: the value is non-negative; or if adding one (giving a
  79   // value in the range [-maxvalue, 0]), then negating (giving a value in the
  80   // range [0, maxvalue]), doesn't produce maxvalue (because in twos-complement,
  81   // (minvalue + 1) == -maxvalue).
  82   MOZ_ASSERT(aValue >= 0 ||
  83              -(aValue + 1) != T((1ULL << (CHAR_BIT * sizeof(T) - 1)) - 1),
  84              "You can't negate the smallest possible negative integer!");
  85   return aValue >= 0 ? aValue : -aValue;
  86 }
  87
  88 namespace detail {
  89
  90 // For now mozilla::Abs only takes intN_T, the signed natural types, and
  91 // float/double/long double.  Feel free to add overloads for other standard,
  92 // signed types if you need them.
  93
  94 template<typename T>
  95 struct AbsReturnTypeFixed;
  96
  97 template<> struct AbsReturnTypeFixed<int8_t> { typedef uint8_t Type; };
  98 template<> struct AbsReturnTypeFixed<int16_t> { typedef uint16_t Type; };
  99 template<> struct AbsReturnTypeFixed<int32_t> { typedef uint32_t Type; };
 100 template<> struct AbsReturnTypeFixed<int64_t> { typedef uint64_t Type; };
 101
 102 template<typename T>
 103 struct AbsReturnType : AbsReturnTypeFixed<T> {};
 104
 105 template<> struct AbsReturnType<char> :
 106   EnableIf<char(-1) < char(0), unsigned char> {};
 107 template<> struct AbsReturnType<signed char> { typedef unsigned char Type; };
 108 template<> struct AbsReturnType<short> { typedef unsigned short Type; };
 109 template<> struct AbsReturnType<int> { typedef unsigned int Type; };
 110 template<> struct AbsReturnType<long> { typedef unsigned long Type; };
 111 template<> struct AbsReturnType<long long> { typedef unsigned long long Type; };
 112 template<> struct AbsReturnType<float> { typedef float Type; };
 113 template<> struct AbsReturnType<double> { typedef double Type; };
 114 template<> struct AbsReturnType<long double> { typedef long double Type; };
 115
 116 } // namespace detail
 117
 118 template<typename T>
 119 inline typename detail::AbsReturnType<T>::Type
 120 Abs(const T aValue)
 121 {
 122   typedef typename detail::AbsReturnType<T>::Type ReturnType;
 123   return aValue >= 0 ? ReturnType(aValue) : ~ReturnType(aValue) + 1;
 124 }
 125
 126 template<>
 127 inline float
 128 Abs<float>(const float aFloat)
 129 {
 130   return std::fabs(aFloat);
 131 }
 132
 133 template<>
 134 inline double
 135 Abs<double>(const double aDouble)
 136 {
 137   return std::fabs(aDouble);
 138 }
 139
 140 template<>
 141 inline long double
 142 Abs<long double>(const long double aLongDouble)
 143 {
 144   return std::fabs(aLongDouble);
 145 }
 146
 147 } // namespace mozilla
 148
 149 #if defined(_MSC_VER) && \
 150     (defined(_M_IX86) || defined(_M_AMD64) || defined(_M_X64))
 151 #  define MOZ_BITSCAN_WINDOWS
 152
 153 #  include <intrin.h>
 154 #  pragma intrinsic(_BitScanForward, _BitScanReverse)
 155
 156 #  if defined(_M_AMD64) || defined(_M_X64)
 157 #    define MOZ_BITSCAN_WINDOWS64
 158 #   pragma intrinsic(_BitScanForward64, _BitScanReverse64)
 159 #  endif
 160
 161 #endif
 162
 163 namespace mozilla {
 164
 165 namespace detail {
 166
 167 #if defined(MOZ_BITSCAN_WINDOWS)
 168
 169 inline uint_fast8_t
 170 CountLeadingZeroes32(uint32_t aValue)
 171 {
 172   unsigned long index;
 173   _BitScanReverse(&index, static_cast<unsigned long>(aValue));
 174   return uint_fast8_t(31 - index);
 175 }
 176
 177
 178 inline uint_fast8_t
 179 CountTrailingZeroes32(uint32_t aValue)
 180 {
 181   unsigned long index;
 182   _BitScanForward(&index, static_cast<unsigned long>(aValue));
 183   return uint_fast8_t(index);
 184 }
 185
 186 inline uint_fast8_t
 187 CountPopulation32(uint32_t aValue)
 188 {
 189   uint32_t x = aValue - ((aValue >> 1) & 0x55555555);
 190   x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
 191   return (((x + (x >> 4)) & 0xf0f0f0f) * 0x1010101) >> 24;
 192 }
 193 inline uint_fast8_t
 194 CountPopulation64(uint64_t aValue)
 195 {
 196   return uint_fast8_t(CountPopulation32(aValue & 0xffffffff) +
 197                       CountPopulation32(aValue >> 32));
 198 }
 199
 200 inline uint_fast8_t
 201 CountLeadingZeroes64(uint64_t aValue)
 202 {
 203 #if defined(MOZ_BITSCAN_WINDOWS64)
 204   unsigned long index;
 205   _BitScanReverse64(&index, static_cast<unsigned __int64>(aValue));
 206   return uint_fast8_t(63 - index);
 207 #else
 208   uint32_t hi = uint32_t(aValue >> 32);
 209   if (hi != 0) {
 210     return CountLeadingZeroes32(hi);
 211   }
 212   return 32u + CountLeadingZeroes32(uint32_t(aValue));
 213 #endif
 214 }
 215
 216 inline uint_fast8_t
 217 CountTrailingZeroes64(uint64_t aValue)
 218 {
 219 #if defined(MOZ_BITSCAN_WINDOWS64)
 220   unsigned long index;
 221   _BitScanForward64(&index, static_cast<unsigned __int64>(aValue));
 222   return uint_fast8_t(index);
 223 #else
 224   uint32_t lo = uint32_t(aValue);
 225   if (lo != 0) {
 226     return CountTrailingZeroes32(lo);
 227   }
 228   return 32u + CountTrailingZeroes32(uint32_t(aValue >> 32));
 229 #endif
 230 }
 231
 232 #  ifdef MOZ_HAVE_BITSCAN64
 233 #    undef MOZ_HAVE_BITSCAN64
 234 #  endif
 235
 236 #elif defined(__clang__) || defined(__GNUC__)
 237
 238 #  if defined(__clang__)
 239 #    if !__has_builtin(__builtin_ctz) || !__has_builtin(__builtin_clz)
 240 #      error "A clang providing __builtin_c[lt]z is required to build"
 241 #    endif
 242 #  else
 243      // gcc has had __builtin_clz and friends since 3.4: no need to check.
 244 #  endif
 245
 246 inline uint_fast8_t
 247 CountLeadingZeroes32(uint32_t aValue)
 248 {
 249   return __builtin_clz(aValue);
 250 }
 251
 252 inline uint_fast8_t
 253 CountTrailingZeroes32(uint32_t aValue)
 254 {
 255   return __builtin_ctz(aValue);
 256 }
 257
 258 inline uint_fast8_t
 259 CountPopulation32(uint32_t aValue)
 260 {
 261   return __builtin_popcount(aValue);
 262 }
 263
 264 inline uint_fast8_t
 265 CountPopulation64(uint64_t aValue)
 266 {
 267   return __builtin_popcountll(aValue);
 268 }
 269
 270 inline uint_fast8_t
 271 CountLeadingZeroes64(uint64_t aValue)
 272 {
 273   return __builtin_clzll(aValue);
 274 }
 275
 276 inline uint_fast8_t
 277 CountTrailingZeroes64(uint64_t aValue)
 278 {
 279   return __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
 306 CountLeadingZeroes32(uint32_t aValue)
 307 {
 308   MOZ_ASSERT(aValue != 0);
 309   return detail::CountLeadingZeroes32(aValue);
 310 }
 311
 312 /**
 313  * Compute the number of low-order zero bits in the NON-ZERO number |aValue|.
 314  * That is, looking at the bitwise representation of the number, with the
 315  * lowest- valued bits at the start, return the number of zeroes before the
 316  * first one is observed.
 317  *
 318  * CountTrailingZeroes32(0x0100FFFF) is 0;
 319  * CountTrailingZeroes32(0x7000FFFE) is 1;
 320  * CountTrailingZeroes32(0x0080FFFC) is 2;
 321  * CountTrailingZeroes32(0x0080FFF8) is 3; and so on.
 322  */
 323 inline uint_fast8_t
 324 CountTrailingZeroes32(uint32_t aValue)
 325 {
 326   MOZ_ASSERT(aValue != 0);
 327   return detail::CountTrailingZeroes32(aValue);
 328 }
 329
 330 /**
 331  * Compute the number of one bits in the number |aValue|,
 332  */
 333 inline uint_fast8_t
 334 CountPopulation32(uint32_t aValue)
 335 {
 336   return detail::CountPopulation32(aValue);
 337 }
 338
 339 /** Analogous to CoutPopulation32, but for 64-bit numbers */
 340 inline uint_fast8_t
 341 CountPopulation64(uint64_t aValue)
 342 {
 343   return detail::CountPopulation64(aValue);
 344 }
 345
 346 /** Analogous to CountLeadingZeroes32, but for 64-bit numbers. */
 347 inline uint_fast8_t
 348 CountLeadingZeroes64(uint64_t aValue)
 349 {
 350   MOZ_ASSERT(aValue != 0);
 351   return detail::CountLeadingZeroes64(aValue);
 352 }
 353
 354 /** Analogous to CountTrailingZeroes32, but for 64-bit numbers. */
 355 inline uint_fast8_t
 356 CountTrailingZeroes64(uint64_t aValue)
 357 {
 358   MOZ_ASSERT(aValue != 0);
 359   return detail::CountTrailingZeroes64(aValue);
 360 }
 361
 362 namespace detail {
 363
 364 template<typename T, size_t Size = sizeof(T)>
 365 class CeilingLog2;
 366
 367 template<typename T>
 368 class CeilingLog2<T, 4>
 369 {
 370 public:
 371   static uint_fast8_t compute(const T aValue)
 372   {
 373     // Check for <= 1 to avoid the == 0 undefined case.
 374     return aValue <= 1 ? 0u : 32u - CountLeadingZeroes32(aValue - 1);
 375   }
 376 };
 377
 378 template<typename T>
 379 class CeilingLog2<T, 8>
 380 {
 381 public:
 382   static uint_fast8_t compute(const T aValue)
 383   {
 384     // Check for <= 1 to avoid the == 0 undefined case.
 385     return aValue <= 1 ? 0 : 64 - CountLeadingZeroes64(aValue - 1);
 386   }
 387 };
 388
 389 } // namespace detail
 390
 391 /**
 392  * Compute the log of the least power of 2 greater than or equal to |aValue|.
 393  *
 394  * CeilingLog2(0..1) is 0;
 395  * CeilingLog2(2) is 1;
 396  * CeilingLog2(3..4) is 2;
 397  * CeilingLog2(5..8) is 3;
 398  * CeilingLog2(9..16) is 4; and so on.
 399  */
 400 template<typename T>
 401 inline uint_fast8_t
 402 CeilingLog2(const T aValue)
 403 {
 404   return detail::CeilingLog2<T>::compute(aValue);
 405 }
 406
 407 /** A CeilingLog2 variant that accepts only size_t. */
 408 inline uint_fast8_t
 409 CeilingLog2Size(size_t aValue)
 410 {
 411   return CeilingLog2(aValue);
 412 }
 413
 414 namespace detail {
 415
 416 template<typename T, size_t Size = sizeof(T)>
 417 class FloorLog2;
 418
 419 template<typename T>
 420 class FloorLog2<T, 4>
 421 {
 422 public:
 423   static uint_fast8_t compute(const T aValue)
 424   {
 425     return 31u - CountLeadingZeroes32(aValue | 1);
 426   }
 427 };
 428
 429 template<typename T>
 430 class FloorLog2<T, 8>
 431 {
 432 public:
 433   static uint_fast8_t compute(const T aValue)
 434   {
 435     return 63u - CountLeadingZeroes64(aValue | 1);
 436   }
 437 };
 438
 439 } // namespace detail
 440
 441 /**
 442  * Compute the log of the greatest power of 2 less than or equal to |aValue|.
 443  *
 444  * FloorLog2(0..1) is 0;
 445  * FloorLog2(2..3) is 1;
 446  * FloorLog2(4..7) is 2;
 447  * FloorLog2(8..15) is 3; and so on.
 448  */
 449 template<typename T>
 450 inline uint_fast8_t
 451 FloorLog2(const T aValue)
 452 {
 453   return detail::FloorLog2<T>::compute(aValue);
 454 }
 455
 456 /** A FloorLog2 variant that accepts only size_t. */
 457 inline uint_fast8_t
 458 FloorLog2Size(size_t aValue)
 459 {
 460   return FloorLog2(aValue);
 461 }
 462
 463 /*
 464  * Compute the smallest power of 2 greater than or equal to |x|.  |x| must not
 465  * be so great that the computed value would overflow |size_t|.
 466  */
 467 inline size_t
 468 RoundUpPow2(size_t aValue)
 469 {
 470   MOZ_ASSERT(aValue <= (size_t(1) << (sizeof(size_t) * CHAR_BIT - 1)),
 471              "can't round up -- will overflow!");
 472   return size_t(1) << CeilingLog2(aValue);
 473 }
 474
 475 /**
 476  * Rotates the bits of the given value left by the amount of the shift width.
 477  */
 478 template<typename T>
 479 inline T
 480 RotateLeft(const T aValue, uint_fast8_t aShift)
 481 {
 482   MOZ_ASSERT(aShift < sizeof(T) * CHAR_BIT, "Shift value is too large!");
 483   static_assert(IsUnsigned<T>::value, "Rotates require unsigned values");
 484   return (aValue << aShift) | (aValue >> (sizeof(T) * CHAR_BIT - aShift));
 485 }
 486
 487 /**
 488  * Rotates the bits of the given value right by the amount of the shift width.
 489  */
 490 template<typename T>
 491 inline T
 492 RotateRight(const T aValue, uint_fast8_t aShift)
 493 {
 494   MOZ_ASSERT(aShift < sizeof(T) * CHAR_BIT, "Shift value is too large!");
 495   static_assert(IsUnsigned<T>::value, "Rotates require unsigned values");
 496   return (aValue >> aShift) | (aValue << (sizeof(T) * CHAR_BIT - aShift));
 497 }
 498
 499 } /* namespace mozilla */
 500
 501 #endif /* mozilla_MathAlgorithms_h */