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