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 a, IntegerType b)
  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(a > IntegerType(0));
  29   MOZ_ASSERT(b > IntegerType(0));
  30
  31   while (a != b) {
  32     if (a > b) {
  33       a = a - b;
  34     } else {
  35       b = b - a;
  36     }
  37   }
  38
  39   return a;
  40 }
  41
  42 // Least Common Multiple
  43 template<typename IntegerType>
  44 MOZ_ALWAYS_INLINE IntegerType
  45 EuclidLCM(IntegerType a, IntegerType b)
  46 {
  47   // Divide first to reduce overflow risk.
  48   return (a / EuclidGCD(a, b)) * b;
  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 t)
  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(t >= 0 ||
  83              -(t + 1) != T((1ULL << (CHAR_BIT * sizeof(T) - 1)) - 1),
  84              "You can't negate the smallest possible negative integer!");
  85   return t >= 0 ? t : -t;
  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> : EnableIf<char(-1) < char(0), unsigned char> {};
 106 template<> struct AbsReturnType<signed char> { typedef unsigned char Type; };
 107 template<> struct AbsReturnType<short> { typedef unsigned short Type; };
 108 template<> struct AbsReturnType<int> { typedef unsigned int Type; };
 109 template<> struct AbsReturnType<long> { typedef unsigned long Type; };
 110 template<> struct AbsReturnType<long long> { typedef unsigned long long Type; };
 111 template<> struct AbsReturnType<float> { typedef float Type; };
 112 template<> struct AbsReturnType<double> { typedef double Type; };
 113 template<> struct AbsReturnType<long double> { typedef long double Type; };
 114
 115 } // namespace detail
 116
 117 template<typename T>
 118 inline typename detail::AbsReturnType<T>::Type
 119 Abs(const T t)
 120 {
 121   typedef typename detail::AbsReturnType<T>::Type ReturnType;
 122   return t >= 0 ? ReturnType(t) : ~ReturnType(t) + 1;
 123 }
 124
 125 template<>
 126 inline float
 127 Abs<float>(const float f)
 128 {
 129   return std::fabs(f);
 130 }
 131
 132 template<>
 133 inline double
 134 Abs<double>(const double d)
 135 {
 136   return std::fabs(d);
 137 }
 138
 139 template<>
 140 inline long double
 141 Abs<long double>(const long double d)
 142 {
 143   return std::fabs(d);
 144 }
 145
 146 } // namespace mozilla
 147
 148 #if defined(_WIN32) && (_MSC_VER >= 1300) && (defined(_M_IX86) || defined(_M_AMD64) || defined(_M_X64))
 149 #  define MOZ_BITSCAN_WINDOWS
 150
 151   extern "C" {
 152     unsigned char _BitScanForward(unsigned long* Index, unsigned long mask);
 153     unsigned char _BitScanReverse(unsigned long* Index, unsigned long mask);
 154 #  pragma intrinsic(_BitScanForward, _BitScanReverse)
 155
 156 #  if defined(_M_AMD64) || defined(_M_X64)
 157 #    define MOZ_BITSCAN_WINDOWS64
 158     unsigned char _BitScanForward64(unsigned long* index, unsigned __int64 mask);
 159     unsigned char _BitScanReverse64(unsigned long* index, unsigned __int64 mask);
 160 #   pragma intrinsic(_BitScanForward64, _BitScanReverse64)
 161 #  endif
 162   } // extern "C"
 163
 164 #endif
 165
 166 namespace mozilla {
 167
 168 namespace detail {
 169
 170 #if defined(MOZ_BITSCAN_WINDOWS)
 171
 172   inline uint_fast8_t
 173   CountLeadingZeroes32(uint32_t u)
 174   {
 175     unsigned long index;
 176     _BitScanReverse(&index, static_cast<unsigned long>(u));
 177     return uint_fast8_t(31 - index);
 178   }
 179
 180
 181   inline uint_fast8_t
 182   CountTrailingZeroes32(uint32_t u)
 183   {
 184     unsigned long index;
 185     _BitScanForward(&index, static_cast<unsigned long>(u));
 186     return uint_fast8_t(index);
 187   }
 188
 189   inline uint_fast8_t
 190   CountPopulation32(uint32_t u)
 191   {
 192     uint32_t x = u - ((u >> 1) & 0x55555555);
 193     x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
 194     return (((x + (x >> 4)) & 0xf0f0f0f) * 0x1010101) >> 24;
 195   }
 196
 197   inline uint_fast8_t
 198   CountLeadingZeroes64(uint64_t u)
 199   {
 200 #  if defined(MOZ_BITSCAN_WINDOWS64)
 201     unsigned long index;
 202     _BitScanReverse64(&index, static_cast<unsigned __int64>(u));
 203     return uint_fast8_t(63 - index);
 204 #  else
 205     uint32_t hi = uint32_t(u >> 32);
 206     if (hi != 0)
 207       return CountLeadingZeroes32(hi);
 208     return 32u + CountLeadingZeroes32(uint32_t(u));
 209 #  endif
 210   }
 211
 212   inline uint_fast8_t
 213   CountTrailingZeroes64(uint64_t u)
 214   {
 215 #  if defined(MOZ_BITSCAN_WINDOWS64)
 216     unsigned long index;
 217     _BitScanForward64(&index, static_cast<unsigned __int64>(u));
 218     return uint_fast8_t(index);
 219 #  else
 220     uint32_t lo = uint32_t(u);
 221     if (lo != 0)
 222       return CountTrailingZeroes32(lo);
 223     return 32u + CountTrailingZeroes32(uint32_t(u >> 32));
 224 #  endif
 225   }
 226
 227 #  ifdef MOZ_HAVE_BITSCAN64
 228 #    undef MOZ_HAVE_BITSCAN64
 229 #  endif
 230
 231 #elif defined(__clang__) || defined(__GNUC__)
 232
 233 #  if defined(__clang__)
 234 #    if !__has_builtin(__builtin_ctz) || !__has_builtin(__builtin_clz)
 235 #      error "A clang providing __builtin_c[lt]z is required to build"
 236 #    endif
 237 #  else
 238      // gcc has had __builtin_clz and friends since 3.4: no need to check.
 239 #  endif
 240
 241   inline uint_fast8_t
 242   CountLeadingZeroes32(uint32_t u)
 243   {
 244     return __builtin_clz(u);
 245   }
 246
 247   inline uint_fast8_t
 248   CountTrailingZeroes32(uint32_t u)
 249   {
 250     return __builtin_ctz(u);
 251   }
 252
 253   inline uint_fast8_t
 254   CountPopulation32(uint32_t u)
 255   {
 256     return __builtin_popcount(u);
 257   }
 258
 259   inline uint_fast8_t
 260   CountLeadingZeroes64(uint64_t u)
 261   {
 262     return __builtin_clzll(u);
 263   }
 264
 265   inline uint_fast8_t
 266   CountTrailingZeroes64(uint64_t u)
 267   {
 268     return __builtin_ctzll(u);
 269   }
 270
 271 #else
 272 #  error "Implement these!"
 273   inline uint_fast8_t CountLeadingZeroes32(uint32_t u) MOZ_DELETE;
 274   inline uint_fast8_t CountTrailingZeroes32(uint32_t u) MOZ_DELETE;
 275   inline uint_fast8_t CountPopulation32(uint32_t u) MOZ_DELETE;
 276   inline uint_fast8_t CountLeadingZeroes64(uint64_t u) MOZ_DELETE;
 277   inline uint_fast8_t CountTrailingZeroes64(uint64_t u) MOZ_DELETE;
 278 #endif
 279
 280 } // namespace detail
 281
 282 /**
 283  * Compute the number of high-order zero bits in the NON-ZERO number |u|.  That
 284  * is, looking at the bitwise representation of the number, with the highest-
 285  * valued bits at the start, return the number of zeroes before the first one
 286  * is observed.
 287  *
 288  * CountLeadingZeroes32(0xF0FF1000) is 0;
 289  * CountLeadingZeroes32(0x7F8F0001) is 1;
 290  * CountLeadingZeroes32(0x3FFF0100) is 2;
 291  * CountLeadingZeroes32(0x1FF50010) is 3; and so on.
 292  */
 293 inline uint_fast8_t
 294 CountLeadingZeroes32(uint32_t u)
 295 {
 296   MOZ_ASSERT(u != 0);
 297   return detail::CountLeadingZeroes32(u);
 298 }
 299
 300 /**
 301  * Compute the number of low-order zero bits in the NON-ZERO number |u|.  That
 302  * is, looking at the bitwise representation of the number, with the lowest-
 303  * valued bits at the start, return the number of zeroes before the first one
 304  * is observed.
 305  *
 306  * CountTrailingZeroes32(0x0100FFFF) is 0;
 307  * CountTrailingZeroes32(0x7000FFFE) is 1;
 308  * CountTrailingZeroes32(0x0080FFFC) is 2;
 309  * CountTrailingZeroes32(0x0080FFF8) is 3; and so on.
 310  */
 311 inline uint_fast8_t
 312 CountTrailingZeroes32(uint32_t u)
 313 {
 314   MOZ_ASSERT(u != 0);
 315   return detail::CountTrailingZeroes32(u);
 316 }
 317
 318 /**
 319  * Compute the number of one bits in the number |u|,
 320  */
 321 inline uint_fast8_t
 322 CountPopulation32(uint32_t u)
 323 {
 324   return detail::CountPopulation32(u);
 325 }
 326
 327 /** Analogous to CountLeadingZeroes32, but for 64-bit numbers. */
 328 inline uint_fast8_t
 329 CountLeadingZeroes64(uint64_t u)
 330 {
 331   MOZ_ASSERT(u != 0);
 332   return detail::CountLeadingZeroes64(u);
 333 }
 334
 335 /** Analogous to CountTrailingZeroes32, but for 64-bit numbers. */
 336 inline uint_fast8_t
 337 CountTrailingZeroes64(uint64_t u)
 338 {
 339   MOZ_ASSERT(u != 0);
 340   return detail::CountTrailingZeroes64(u);
 341 }
 342
 343 namespace detail {
 344
 345 template<typename T, size_t Size = sizeof(T)>
 346 class CeilingLog2;
 347
 348 template<typename T>
 349 class CeilingLog2<T, 4>
 350 {
 351   public:
 352     static uint_fast8_t compute(const T t) {
 353       // Check for <= 1 to avoid the == 0 undefined case.
 354       return t <= 1 ? 0u : 32u - CountLeadingZeroes32(t - 1);
 355     }
 356 };
 357
 358 template<typename T>
 359 class CeilingLog2<T, 8>
 360 {
 361   public:
 362     static uint_fast8_t compute(const T t) {
 363       // Check for <= 1 to avoid the == 0 undefined case.
 364       return t <= 1 ? 0 : 64 - CountLeadingZeroes64(t - 1);
 365     }
 366 };
 367
 368 } // namespace detail
 369
 370 /**
 371  * Compute the log of the least power of 2 greater than or equal to |t|.
 372  *
 373  * CeilingLog2(0..1) is 0;
 374  * CeilingLog2(2) is 1;
 375  * CeilingLog2(3..4) is 2;
 376  * CeilingLog2(5..8) is 3;
 377  * CeilingLog2(9..16) is 4; and so on.
 378  */
 379 template<typename T>
 380 inline uint_fast8_t
 381 CeilingLog2(const T t)
 382 {
 383   return detail::CeilingLog2<T>::compute(t);
 384 }
 385
 386 /** A CeilingLog2 variant that accepts only size_t. */
 387 inline uint_fast8_t
 388 CeilingLog2Size(size_t n)
 389 {
 390   return CeilingLog2(n);
 391 }
 392
 393 namespace detail {
 394
 395 template<typename T, size_t Size = sizeof(T)>
 396 class FloorLog2;
 397
 398 template<typename T>
 399 class FloorLog2<T, 4>
 400 {
 401   public:
 402     static uint_fast8_t compute(const T t) {
 403       return 31u - CountLeadingZeroes32(t | 1);
 404     }
 405 };
 406
 407 template<typename T>
 408 class FloorLog2<T, 8>
 409 {
 410   public:
 411     static uint_fast8_t compute(const T t) {
 412       return 63u - CountLeadingZeroes64(t | 1);
 413     }
 414 };
 415
 416 } // namespace detail
 417
 418 /**
 419  * Compute the log of the greatest power of 2 less than or equal to |t|.
 420  *
 421  * FloorLog2(0..1) is 0;
 422  * FloorLog2(2..3) is 1;
 423  * FloorLog2(4..7) is 2;
 424  * FloorLog2(8..15) is 3; and so on.
 425  */
 426 template<typename T>
 427 inline uint_fast8_t
 428 FloorLog2(const T t)
 429 {
 430   return detail::FloorLog2<T>::compute(t);
 431 }
 432
 433 /** A FloorLog2 variant that accepts only size_t. */
 434 inline uint_fast8_t
 435 FloorLog2Size(size_t n)
 436 {
 437   return FloorLog2(n);
 438 }
 439
 440 /*
 441  * Compute the smallest power of 2 greater than or equal to |x|.  |x| must not
 442  * be so great that the computed value would overflow |size_t|.
 443  */
 444 inline size_t
 445 RoundUpPow2(size_t x)
 446 {
 447   MOZ_ASSERT(x <= (size_t(1) << (sizeof(size_t) * CHAR_BIT - 1)),
 448              "can't round up -- will overflow!");
 449   return size_t(1) << CeilingLog2(x);
 450 }
 451
 452 /**
 453  * Rotates the bits of the given value left by the amount of the shift width.
 454  */
 455 template<typename T>
 456 inline T
 457 RotateLeft(const T t, uint_fast8_t shift)
 458 {
 459   MOZ_ASSERT(shift < sizeof(T) * CHAR_BIT, "Shift value is too large!");
 460   static_assert(IsUnsigned<T>::value, "Rotates require unsigned values");
 461   return (t << shift) | (t >> (sizeof(T) * CHAR_BIT - shift));
 462 }
 463
 464 /**
 465  * Rotates the bits of the given value right by the amount of the shift width.
 466  */
 467 template<typename T>
 468 inline T
 469 RotateRight(const T t, uint_fast8_t shift)
 470 {
 471   MOZ_ASSERT(shift < sizeof(T) * CHAR_BIT, "Shift value is too large!");
 472   static_assert(IsUnsigned<T>::value, "Rotates require unsigned values");
 473   return (t >> shift) | (t << (sizeof(T) * CHAR_BIT - shift));
 474 }
 475
 476 } /* namespace mozilla */
 477
 478 #endif /* mozilla_MathAlgorithms_h */