1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/mfbt/MathAlgorithms.h Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,478 @@
1.4 +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
1.5 +/* vim: set ts=8 sts=2 et sw=2 tw=80: */
1.6 +/* This Source Code Form is subject to the terms of the Mozilla Public
1.7 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.8 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.9 +
1.10 +/* mfbt maths algorithms. */
1.11 +
1.12 +#ifndef mozilla_MathAlgorithms_h
1.13 +#define mozilla_MathAlgorithms_h
1.14 +
1.15 +#include "mozilla/Assertions.h"
1.16 +#include "mozilla/TypeTraits.h"
1.17 +
1.18 +#include <cmath>
1.19 +#include <limits.h>
1.20 +#include <stdint.h>
1.21 +
1.22 +namespace mozilla {
1.23 +
1.24 +// Greatest Common Divisor
1.25 +template<typename IntegerType>
1.26 +MOZ_ALWAYS_INLINE IntegerType
1.27 +EuclidGCD(IntegerType a, IntegerType b)
1.28 +{
1.29 + // Euclid's algorithm; O(N) in the worst case. (There are better
1.30 + // ways, but we don't need them for the current use of this algo.)
1.31 + MOZ_ASSERT(a > 0);
1.32 + MOZ_ASSERT(b > 0);
1.33 +
1.34 + while (a != b) {
1.35 + if (a > b) {
1.36 + a = a - b;
1.37 + } else {
1.38 + b = b - a;
1.39 + }
1.40 + }
1.41 +
1.42 + return a;
1.43 +}
1.44 +
1.45 +// Least Common Multiple
1.46 +template<typename IntegerType>
1.47 +MOZ_ALWAYS_INLINE IntegerType
1.48 +EuclidLCM(IntegerType a, IntegerType b)
1.49 +{
1.50 + // Divide first to reduce overflow risk.
1.51 + return (a / EuclidGCD(a, b)) * b;
1.52 +}
1.53 +
1.54 +namespace detail {
1.55 +
1.56 +template<typename T>
1.57 +struct AllowDeprecatedAbsFixed : FalseType {};
1.58 +
1.59 +template<> struct AllowDeprecatedAbsFixed<int32_t> : TrueType {};
1.60 +template<> struct AllowDeprecatedAbsFixed<int64_t> : TrueType {};
1.61 +
1.62 +template<typename T>
1.63 +struct AllowDeprecatedAbs : AllowDeprecatedAbsFixed<T> {};
1.64 +
1.65 +template<> struct AllowDeprecatedAbs<int> : TrueType {};
1.66 +template<> struct AllowDeprecatedAbs<long> : TrueType {};
1.67 +
1.68 +} // namespace detail
1.69 +
1.70 +// DO NOT USE DeprecatedAbs. It exists only until its callers can be converted
1.71 +// to Abs below, and it will be removed when all callers have been changed.
1.72 +template<typename T>
1.73 +inline typename mozilla::EnableIf<detail::AllowDeprecatedAbs<T>::value, T>::Type
1.74 +DeprecatedAbs(const T t)
1.75 +{
1.76 + // The absolute value of the smallest possible value of a signed-integer type
1.77 + // won't fit in that type (on twos-complement systems -- and we're blithely
1.78 + // assuming we're on such systems, for the non-<stdint.h> types listed above),
1.79 + // so assert that the input isn't that value.
1.80 + //
1.81 + // This is the case if: the value is non-negative; or if adding one (giving a
1.82 + // value in the range [-maxvalue, 0]), then negating (giving a value in the
1.83 + // range [0, maxvalue]), doesn't produce maxvalue (because in twos-complement,
1.84 + // (minvalue + 1) == -maxvalue).
1.85 + MOZ_ASSERT(t >= 0 ||
1.86 + -(t + 1) != T((1ULL << (CHAR_BIT * sizeof(T) - 1)) - 1),
1.87 + "You can't negate the smallest possible negative integer!");
1.88 + return t >= 0 ? t : -t;
1.89 +}
1.90 +
1.91 +namespace detail {
1.92 +
1.93 +// For now mozilla::Abs only takes intN_T, the signed natural types, and
1.94 +// float/double/long double. Feel free to add overloads for other standard,
1.95 +// signed types if you need them.
1.96 +
1.97 +template<typename T>
1.98 +struct AbsReturnTypeFixed;
1.99 +
1.100 +template<> struct AbsReturnTypeFixed<int8_t> { typedef uint8_t Type; };
1.101 +template<> struct AbsReturnTypeFixed<int16_t> { typedef uint16_t Type; };
1.102 +template<> struct AbsReturnTypeFixed<int32_t> { typedef uint32_t Type; };
1.103 +template<> struct AbsReturnTypeFixed<int64_t> { typedef uint64_t Type; };
1.104 +
1.105 +template<typename T>
1.106 +struct AbsReturnType : AbsReturnTypeFixed<T> {};
1.107 +
1.108 +template<> struct AbsReturnType<char> : EnableIf<char(-1) < char(0), unsigned char> {};
1.109 +template<> struct AbsReturnType<signed char> { typedef unsigned char Type; };
1.110 +template<> struct AbsReturnType<short> { typedef unsigned short Type; };
1.111 +template<> struct AbsReturnType<int> { typedef unsigned int Type; };
1.112 +template<> struct AbsReturnType<long> { typedef unsigned long Type; };
1.113 +template<> struct AbsReturnType<long long> { typedef unsigned long long Type; };
1.114 +template<> struct AbsReturnType<float> { typedef float Type; };
1.115 +template<> struct AbsReturnType<double> { typedef double Type; };
1.116 +template<> struct AbsReturnType<long double> { typedef long double Type; };
1.117 +
1.118 +} // namespace detail
1.119 +
1.120 +template<typename T>
1.121 +inline typename detail::AbsReturnType<T>::Type
1.122 +Abs(const T t)
1.123 +{
1.124 + typedef typename detail::AbsReturnType<T>::Type ReturnType;
1.125 + return t >= 0 ? ReturnType(t) : ~ReturnType(t) + 1;
1.126 +}
1.127 +
1.128 +template<>
1.129 +inline float
1.130 +Abs<float>(const float f)
1.131 +{
1.132 + return std::fabs(f);
1.133 +}
1.134 +
1.135 +template<>
1.136 +inline double
1.137 +Abs<double>(const double d)
1.138 +{
1.139 + return std::fabs(d);
1.140 +}
1.141 +
1.142 +template<>
1.143 +inline long double
1.144 +Abs<long double>(const long double d)
1.145 +{
1.146 + return std::fabs(d);
1.147 +}
1.148 +
1.149 +} // namespace mozilla
1.150 +
1.151 +#if defined(_WIN32) && (_MSC_VER >= 1300) && (defined(_M_IX86) || defined(_M_AMD64) || defined(_M_X64))
1.152 +# define MOZ_BITSCAN_WINDOWS
1.153 +
1.154 + extern "C" {
1.155 + unsigned char _BitScanForward(unsigned long* Index, unsigned long mask);
1.156 + unsigned char _BitScanReverse(unsigned long* Index, unsigned long mask);
1.157 +# pragma intrinsic(_BitScanForward, _BitScanReverse)
1.158 +
1.159 +# if defined(_M_AMD64) || defined(_M_X64)
1.160 +# define MOZ_BITSCAN_WINDOWS64
1.161 + unsigned char _BitScanForward64(unsigned long* index, unsigned __int64 mask);
1.162 + unsigned char _BitScanReverse64(unsigned long* index, unsigned __int64 mask);
1.163 +# pragma intrinsic(_BitScanForward64, _BitScanReverse64)
1.164 +# endif
1.165 + } // extern "C"
1.166 +
1.167 +#endif
1.168 +
1.169 +namespace mozilla {
1.170 +
1.171 +namespace detail {
1.172 +
1.173 +#if defined(MOZ_BITSCAN_WINDOWS)
1.174 +
1.175 + inline uint_fast8_t
1.176 + CountLeadingZeroes32(uint32_t u)
1.177 + {
1.178 + unsigned long index;
1.179 + _BitScanReverse(&index, static_cast<unsigned long>(u));
1.180 + return uint_fast8_t(31 - index);
1.181 + }
1.182 +
1.183 +
1.184 + inline uint_fast8_t
1.185 + CountTrailingZeroes32(uint32_t u)
1.186 + {
1.187 + unsigned long index;
1.188 + _BitScanForward(&index, static_cast<unsigned long>(u));
1.189 + return uint_fast8_t(index);
1.190 + }
1.191 +
1.192 + inline uint_fast8_t
1.193 + CountPopulation32(uint32_t u)
1.194 + {
1.195 + uint32_t x = u - ((u >> 1) & 0x55555555);
1.196 + x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
1.197 + return (((x + (x >> 4)) & 0xf0f0f0f) * 0x1010101) >> 24;
1.198 + }
1.199 +
1.200 + inline uint_fast8_t
1.201 + CountLeadingZeroes64(uint64_t u)
1.202 + {
1.203 +# if defined(MOZ_BITSCAN_WINDOWS64)
1.204 + unsigned long index;
1.205 + _BitScanReverse64(&index, static_cast<unsigned __int64>(u));
1.206 + return uint_fast8_t(63 - index);
1.207 +# else
1.208 + uint32_t hi = uint32_t(u >> 32);
1.209 + if (hi != 0)
1.210 + return CountLeadingZeroes32(hi);
1.211 + return 32 + CountLeadingZeroes32(uint32_t(u));
1.212 +# endif
1.213 + }
1.214 +
1.215 + inline uint_fast8_t
1.216 + CountTrailingZeroes64(uint64_t u)
1.217 + {
1.218 +# if defined(MOZ_BITSCAN_WINDOWS64)
1.219 + unsigned long index;
1.220 + _BitScanForward64(&index, static_cast<unsigned __int64>(u));
1.221 + return uint_fast8_t(index);
1.222 +# else
1.223 + uint32_t lo = uint32_t(u);
1.224 + if (lo != 0)
1.225 + return CountTrailingZeroes32(lo);
1.226 + return 32 + CountTrailingZeroes32(uint32_t(u >> 32));
1.227 +# endif
1.228 + }
1.229 +
1.230 +# ifdef MOZ_HAVE_BITSCAN64
1.231 +# undef MOZ_HAVE_BITSCAN64
1.232 +# endif
1.233 +
1.234 +#elif defined(__clang__) || defined(__GNUC__)
1.235 +
1.236 +# if defined(__clang__)
1.237 +# if !__has_builtin(__builtin_ctz) || !__has_builtin(__builtin_clz)
1.238 +# error "A clang providing __builtin_c[lt]z is required to build"
1.239 +# endif
1.240 +# else
1.241 + // gcc has had __builtin_clz and friends since 3.4: no need to check.
1.242 +# endif
1.243 +
1.244 + inline uint_fast8_t
1.245 + CountLeadingZeroes32(uint32_t u)
1.246 + {
1.247 + return __builtin_clz(u);
1.248 + }
1.249 +
1.250 + inline uint_fast8_t
1.251 + CountTrailingZeroes32(uint32_t u)
1.252 + {
1.253 + return __builtin_ctz(u);
1.254 + }
1.255 +
1.256 + inline uint_fast8_t
1.257 + CountPopulation32(uint32_t u)
1.258 + {
1.259 + return __builtin_popcount(u);
1.260 + }
1.261 +
1.262 + inline uint_fast8_t
1.263 + CountLeadingZeroes64(uint64_t u)
1.264 + {
1.265 + return __builtin_clzll(u);
1.266 + }
1.267 +
1.268 + inline uint_fast8_t
1.269 + CountTrailingZeroes64(uint64_t u)
1.270 + {
1.271 + return __builtin_ctzll(u);
1.272 + }
1.273 +
1.274 +#else
1.275 +# error "Implement these!"
1.276 + inline uint_fast8_t CountLeadingZeroes32(uint32_t u) MOZ_DELETE;
1.277 + inline uint_fast8_t CountTrailingZeroes32(uint32_t u) MOZ_DELETE;
1.278 + inline uint_fast8_t CountPopulation32(uint32_t u) MOZ_DELETE;
1.279 + inline uint_fast8_t CountLeadingZeroes64(uint64_t u) MOZ_DELETE;
1.280 + inline uint_fast8_t CountTrailingZeroes64(uint64_t u) MOZ_DELETE;
1.281 +#endif
1.282 +
1.283 +} // namespace detail
1.284 +
1.285 +/**
1.286 + * Compute the number of high-order zero bits in the NON-ZERO number |u|. That
1.287 + * is, looking at the bitwise representation of the number, with the highest-
1.288 + * valued bits at the start, return the number of zeroes before the first one
1.289 + * is observed.
1.290 + *
1.291 + * CountLeadingZeroes32(0xF0FF1000) is 0;
1.292 + * CountLeadingZeroes32(0x7F8F0001) is 1;
1.293 + * CountLeadingZeroes32(0x3FFF0100) is 2;
1.294 + * CountLeadingZeroes32(0x1FF50010) is 3; and so on.
1.295 + */
1.296 +inline uint_fast8_t
1.297 +CountLeadingZeroes32(uint32_t u)
1.298 +{
1.299 + MOZ_ASSERT(u != 0);
1.300 + return detail::CountLeadingZeroes32(u);
1.301 +}
1.302 +
1.303 +/**
1.304 + * Compute the number of low-order zero bits in the NON-ZERO number |u|. That
1.305 + * is, looking at the bitwise representation of the number, with the lowest-
1.306 + * valued bits at the start, return the number of zeroes before the first one
1.307 + * is observed.
1.308 + *
1.309 + * CountTrailingZeroes32(0x0100FFFF) is 0;
1.310 + * CountTrailingZeroes32(0x7000FFFE) is 1;
1.311 + * CountTrailingZeroes32(0x0080FFFC) is 2;
1.312 + * CountTrailingZeroes32(0x0080FFF8) is 3; and so on.
1.313 + */
1.314 +inline uint_fast8_t
1.315 +CountTrailingZeroes32(uint32_t u)
1.316 +{
1.317 + MOZ_ASSERT(u != 0);
1.318 + return detail::CountTrailingZeroes32(u);
1.319 +}
1.320 +
1.321 +/**
1.322 + * Compute the number of one bits in the number |u|,
1.323 + */
1.324 +inline uint_fast8_t
1.325 +CountPopulation32(uint32_t u)
1.326 +{
1.327 + return detail::CountPopulation32(u);
1.328 +}
1.329 +
1.330 +/** Analogous to CountLeadingZeroes32, but for 64-bit numbers. */
1.331 +inline uint_fast8_t
1.332 +CountLeadingZeroes64(uint64_t u)
1.333 +{
1.334 + MOZ_ASSERT(u != 0);
1.335 + return detail::CountLeadingZeroes64(u);
1.336 +}
1.337 +
1.338 +/** Analogous to CountTrailingZeroes32, but for 64-bit numbers. */
1.339 +inline uint_fast8_t
1.340 +CountTrailingZeroes64(uint64_t u)
1.341 +{
1.342 + MOZ_ASSERT(u != 0);
1.343 + return detail::CountTrailingZeroes64(u);
1.344 +}
1.345 +
1.346 +namespace detail {
1.347 +
1.348 +template<typename T, size_t Size = sizeof(T)>
1.349 +class CeilingLog2;
1.350 +
1.351 +template<typename T>
1.352 +class CeilingLog2<T, 4>
1.353 +{
1.354 + public:
1.355 + static uint_fast8_t compute(const T t) {
1.356 + // Check for <= 1 to avoid the == 0 undefined case.
1.357 + return t <= 1 ? 0 : 32 - CountLeadingZeroes32(t - 1);
1.358 + }
1.359 +};
1.360 +
1.361 +template<typename T>
1.362 +class CeilingLog2<T, 8>
1.363 +{
1.364 + public:
1.365 + static uint_fast8_t compute(const T t) {
1.366 + // Check for <= 1 to avoid the == 0 undefined case.
1.367 + return t <= 1 ? 0 : 64 - CountLeadingZeroes64(t - 1);
1.368 + }
1.369 +};
1.370 +
1.371 +} // namespace detail
1.372 +
1.373 +/**
1.374 + * Compute the log of the least power of 2 greater than or equal to |t|.
1.375 + *
1.376 + * CeilingLog2(0..1) is 0;
1.377 + * CeilingLog2(2) is 1;
1.378 + * CeilingLog2(3..4) is 2;
1.379 + * CeilingLog2(5..8) is 3;
1.380 + * CeilingLog2(9..16) is 4; and so on.
1.381 + */
1.382 +template<typename T>
1.383 +inline uint_fast8_t
1.384 +CeilingLog2(const T t)
1.385 +{
1.386 + return detail::CeilingLog2<T>::compute(t);
1.387 +}
1.388 +
1.389 +/** A CeilingLog2 variant that accepts only size_t. */
1.390 +inline uint_fast8_t
1.391 +CeilingLog2Size(size_t n)
1.392 +{
1.393 + return CeilingLog2(n);
1.394 +}
1.395 +
1.396 +namespace detail {
1.397 +
1.398 +template<typename T, size_t Size = sizeof(T)>
1.399 +class FloorLog2;
1.400 +
1.401 +template<typename T>
1.402 +class FloorLog2<T, 4>
1.403 +{
1.404 + public:
1.405 + static uint_fast8_t compute(const T t) {
1.406 + return 31 - CountLeadingZeroes32(t | 1);
1.407 + }
1.408 +};
1.409 +
1.410 +template<typename T>
1.411 +class FloorLog2<T, 8>
1.412 +{
1.413 + public:
1.414 + static uint_fast8_t compute(const T t) {
1.415 + return 63 - CountLeadingZeroes64(t | 1);
1.416 + }
1.417 +};
1.418 +
1.419 +} // namespace detail
1.420 +
1.421 +/**
1.422 + * Compute the log of the greatest power of 2 less than or equal to |t|.
1.423 + *
1.424 + * FloorLog2(0..1) is 0;
1.425 + * FloorLog2(2..3) is 1;
1.426 + * FloorLog2(4..7) is 2;
1.427 + * FloorLog2(8..15) is 3; and so on.
1.428 + */
1.429 +template<typename T>
1.430 +inline uint_fast8_t
1.431 +FloorLog2(const T t)
1.432 +{
1.433 + return detail::FloorLog2<T>::compute(t);
1.434 +}
1.435 +
1.436 +/** A FloorLog2 variant that accepts only size_t. */
1.437 +inline uint_fast8_t
1.438 +FloorLog2Size(size_t n)
1.439 +{
1.440 + return FloorLog2(n);
1.441 +}
1.442 +
1.443 +/*
1.444 + * Compute the smallest power of 2 greater than or equal to |x|. |x| must not
1.445 + * be so great that the computed value would overflow |size_t|.
1.446 + */
1.447 +inline size_t
1.448 +RoundUpPow2(size_t x)
1.449 +{
1.450 + MOZ_ASSERT(x <= (size_t(1) << (sizeof(size_t) * CHAR_BIT - 1)),
1.451 + "can't round up -- will overflow!");
1.452 + return size_t(1) << CeilingLog2(x);
1.453 +}
1.454 +
1.455 +/**
1.456 + * Rotates the bits of the given value left by the amount of the shift width.
1.457 + */
1.458 +template<typename T>
1.459 +inline T
1.460 +RotateLeft(const T t, uint_fast8_t shift)
1.461 +{
1.462 + MOZ_ASSERT(shift < sizeof(T) * CHAR_BIT, "Shift value is too large!");
1.463 + static_assert(IsUnsigned<T>::value, "Rotates require unsigned values");
1.464 + return (t << shift) | (t >> (sizeof(T) * CHAR_BIT - shift));
1.465 +}
1.466 +
1.467 +/**
1.468 + * Rotates the bits of the given value right by the amount of the shift width.
1.469 + */
1.470 +template<typename T>
1.471 +inline T
1.472 +RotateRight(const T t, uint_fast8_t shift)
1.473 +{
1.474 + MOZ_ASSERT(shift < sizeof(T) * CHAR_BIT, "Shift value is too large!");
1.475 + static_assert(IsUnsigned<T>::value, "Rotates require unsigned values");
1.476 + return (t >> shift) | (t << (sizeof(T) * CHAR_BIT - shift));
1.477 +}
1.478 +
1.479 +} /* namespace mozilla */
1.480 +
1.481 +#endif /* mozilla_MathAlgorithms_h */
