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