Bumping manifests a=b2g-bump
[gecko.git] / mfbt / MathAlgorithms.h
blob99185ed59b63f518f4667eea43e0bfeabba945dd
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/. */
7 /* mfbt maths algorithms. */
9 #ifndef mozilla_MathAlgorithms_h
10 #define mozilla_MathAlgorithms_h
12 #include "mozilla/Assertions.h"
13 #include "mozilla/TypeTraits.h"
15 #include <cmath>
16 #include <limits.h>
17 #include <stdint.h>
19 namespace mozilla {
21 // Greatest Common Divisor
22 template<typename IntegerType>
23 MOZ_ALWAYS_INLINE IntegerType
24 EuclidGCD(IntegerType aA, IntegerType aB)
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));
31 while (aA != aB) {
32 if (aA > aB) {
33 aA = aA - aB;
34 } else {
35 aB = aB - aA;
39 return aA;
42 // Least Common Multiple
43 template<typename IntegerType>
44 MOZ_ALWAYS_INLINE IntegerType
45 EuclidLCM(IntegerType aA, IntegerType aB)
47 // Divide first to reduce overflow risk.
48 return (aA / EuclidGCD(aA, aB)) * aB;
51 namespace detail {
53 template<typename T>
54 struct AllowDeprecatedAbsFixed : FalseType {};
56 template<> struct AllowDeprecatedAbsFixed<int32_t> : TrueType {};
57 template<> struct AllowDeprecatedAbsFixed<int64_t> : TrueType {};
59 template<typename T>
60 struct AllowDeprecatedAbs : AllowDeprecatedAbsFixed<T> {};
62 template<> struct AllowDeprecatedAbs<int> : TrueType {};
63 template<> struct AllowDeprecatedAbs<long> : TrueType {};
65 } // namespace detail
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)
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.
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;
88 namespace detail {
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.
94 template<typename T>
95 struct AbsReturnTypeFixed;
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; };
102 template<typename T>
103 struct AbsReturnType : AbsReturnTypeFixed<T> {};
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; };
116 } // namespace detail
118 template<typename T>
119 inline typename detail::AbsReturnType<T>::Type
120 Abs(const T aValue)
122 typedef typename detail::AbsReturnType<T>::Type ReturnType;
123 return aValue >= 0 ? ReturnType(aValue) : ~ReturnType(aValue) + 1;
126 template<>
127 inline float
128 Abs<float>(const float aFloat)
130 return std::fabs(aFloat);
133 template<>
134 inline double
135 Abs<double>(const double aDouble)
137 return std::fabs(aDouble);
140 template<>
141 inline long double
142 Abs<long double>(const long double aLongDouble)
144 return std::fabs(aLongDouble);
147 } // namespace mozilla
149 #if defined(_MSC_VER) && \
150 (defined(_M_IX86) || defined(_M_AMD64) || defined(_M_X64))
151 # define MOZ_BITSCAN_WINDOWS
153 # include <intrin.h>
154 # pragma intrinsic(_BitScanForward, _BitScanReverse)
156 # if defined(_M_AMD64) || defined(_M_X64)
157 # define MOZ_BITSCAN_WINDOWS64
158 # pragma intrinsic(_BitScanForward64, _BitScanReverse64)
159 # endif
161 #endif
163 namespace mozilla {
165 namespace detail {
167 #if defined(MOZ_BITSCAN_WINDOWS)
169 inline uint_fast8_t
170 CountLeadingZeroes32(uint32_t aValue)
172 unsigned long index;
173 _BitScanReverse(&index, static_cast<unsigned long>(aValue));
174 return uint_fast8_t(31 - index);
178 inline uint_fast8_t
179 CountTrailingZeroes32(uint32_t aValue)
181 unsigned long index;
182 _BitScanForward(&index, static_cast<unsigned long>(aValue));
183 return uint_fast8_t(index);
186 inline uint_fast8_t
187 CountPopulation32(uint32_t aValue)
189 uint32_t x = aValue - ((aValue >> 1) & 0x55555555);
190 x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
191 return (((x + (x >> 4)) & 0xf0f0f0f) * 0x1010101) >> 24;
193 inline uint_fast8_t
194 CountPopulation64(uint64_t aValue)
196 return uint_fast8_t(CountPopulation32(aValue & 0xffffffff) +
197 CountPopulation32(aValue >> 32));
200 inline uint_fast8_t
201 CountLeadingZeroes64(uint64_t aValue)
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);
212 return 32u + CountLeadingZeroes32(uint32_t(aValue));
213 #endif
216 inline uint_fast8_t
217 CountTrailingZeroes64(uint64_t aValue)
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);
228 return 32u + CountTrailingZeroes32(uint32_t(aValue >> 32));
229 #endif
232 # ifdef MOZ_HAVE_BITSCAN64
233 # undef MOZ_HAVE_BITSCAN64
234 # endif
236 #elif defined(__clang__) || defined(__GNUC__)
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
246 inline uint_fast8_t
247 CountLeadingZeroes32(uint32_t aValue)
249 return __builtin_clz(aValue);
252 inline uint_fast8_t
253 CountTrailingZeroes32(uint32_t aValue)
255 return __builtin_ctz(aValue);
258 inline uint_fast8_t
259 CountPopulation32(uint32_t aValue)
261 return __builtin_popcount(aValue);
264 inline uint_fast8_t
265 CountPopulation64(uint64_t aValue)
267 return __builtin_popcountll(aValue);
270 inline uint_fast8_t
271 CountLeadingZeroes64(uint64_t aValue)
273 return __builtin_clzll(aValue);
276 inline uint_fast8_t
277 CountTrailingZeroes64(uint64_t aValue)
279 return __builtin_ctzll(aValue);
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
292 } // namespace detail
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.
300 * CountLeadingZeroes32(0xF0FF1000) is 0;
301 * CountLeadingZeroes32(0x7F8F0001) is 1;
302 * CountLeadingZeroes32(0x3FFF0100) is 2;
303 * CountLeadingZeroes32(0x1FF50010) is 3; and so on.
305 inline uint_fast8_t
306 CountLeadingZeroes32(uint32_t aValue)
308 MOZ_ASSERT(aValue != 0);
309 return detail::CountLeadingZeroes32(aValue);
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.
318 * CountTrailingZeroes32(0x0100FFFF) is 0;
319 * CountTrailingZeroes32(0x7000FFFE) is 1;
320 * CountTrailingZeroes32(0x0080FFFC) is 2;
321 * CountTrailingZeroes32(0x0080FFF8) is 3; and so on.
323 inline uint_fast8_t
324 CountTrailingZeroes32(uint32_t aValue)
326 MOZ_ASSERT(aValue != 0);
327 return detail::CountTrailingZeroes32(aValue);
331 * Compute the number of one bits in the number |aValue|,
333 inline uint_fast8_t
334 CountPopulation32(uint32_t aValue)
336 return detail::CountPopulation32(aValue);
339 /** Analogous to CoutPopulation32, but for 64-bit numbers */
340 inline uint_fast8_t
341 CountPopulation64(uint64_t aValue)
343 return detail::CountPopulation64(aValue);
346 /** Analogous to CountLeadingZeroes32, but for 64-bit numbers. */
347 inline uint_fast8_t
348 CountLeadingZeroes64(uint64_t aValue)
350 MOZ_ASSERT(aValue != 0);
351 return detail::CountLeadingZeroes64(aValue);
354 /** Analogous to CountTrailingZeroes32, but for 64-bit numbers. */
355 inline uint_fast8_t
356 CountTrailingZeroes64(uint64_t aValue)
358 MOZ_ASSERT(aValue != 0);
359 return detail::CountTrailingZeroes64(aValue);
362 namespace detail {
364 template<typename T, size_t Size = sizeof(T)>
365 class CeilingLog2;
367 template<typename T>
368 class CeilingLog2<T, 4>
370 public:
371 static uint_fast8_t compute(const T aValue)
373 // Check for <= 1 to avoid the == 0 undefined case.
374 return aValue <= 1 ? 0u : 32u - CountLeadingZeroes32(aValue - 1);
378 template<typename T>
379 class CeilingLog2<T, 8>
381 public:
382 static uint_fast8_t compute(const T aValue)
384 // Check for <= 1 to avoid the == 0 undefined case.
385 return aValue <= 1 ? 0 : 64 - CountLeadingZeroes64(aValue - 1);
389 } // namespace detail
392 * Compute the log of the least power of 2 greater than or equal to |aValue|.
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.
400 template<typename T>
401 inline uint_fast8_t
402 CeilingLog2(const T aValue)
404 return detail::CeilingLog2<T>::compute(aValue);
407 /** A CeilingLog2 variant that accepts only size_t. */
408 inline uint_fast8_t
409 CeilingLog2Size(size_t aValue)
411 return CeilingLog2(aValue);
414 namespace detail {
416 template<typename T, size_t Size = sizeof(T)>
417 class FloorLog2;
419 template<typename T>
420 class FloorLog2<T, 4>
422 public:
423 static uint_fast8_t compute(const T aValue)
425 return 31u - CountLeadingZeroes32(aValue | 1);
429 template<typename T>
430 class FloorLog2<T, 8>
432 public:
433 static uint_fast8_t compute(const T aValue)
435 return 63u - CountLeadingZeroes64(aValue | 1);
439 } // namespace detail
442 * Compute the log of the greatest power of 2 less than or equal to |aValue|.
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.
449 template<typename T>
450 inline uint_fast8_t
451 FloorLog2(const T aValue)
453 return detail::FloorLog2<T>::compute(aValue);
456 /** A FloorLog2 variant that accepts only size_t. */
457 inline uint_fast8_t
458 FloorLog2Size(size_t aValue)
460 return FloorLog2(aValue);
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|.
467 inline size_t
468 RoundUpPow2(size_t aValue)
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);
476 * Rotates the bits of the given value left by the amount of the shift width.
478 template<typename T>
479 inline T
480 RotateLeft(const T aValue, uint_fast8_t aShift)
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));
488 * Rotates the bits of the given value right by the amount of the shift width.
490 template<typename T>
491 inline T
492 RotateRight(const T aValue, uint_fast8_t aShift)
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));
499 } /* namespace mozilla */
501 #endif /* mozilla_MathAlgorithms_h */