Line data Source code
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 0 : EuclidGCD(IntegerType aA, IntegerType aB)
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 0 : MOZ_ASSERT(aA > IntegerType(0));
29 0 : MOZ_ASSERT(aB > IntegerType(0));
30 :
31 0 : while (aA != aB) {
32 0 : if (aA > aB) {
33 0 : aA = aA - aB;
34 : } else {
35 0 : aB = aB - aA;
36 : }
37 : }
38 :
39 0 : return aA;
40 : }
41 :
42 : // Least Common Multiple
43 : template<typename IntegerType>
44 : MOZ_ALWAYS_INLINE IntegerType
45 0 : EuclidLCM(IntegerType aA, IntegerType aB)
46 : {
47 : // Divide first to reduce overflow risk.
48 0 : return (aA / EuclidGCD(aA, aB)) * aB;
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 0 : DeprecatedAbs(const T aValue)
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 0 : 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 0 : return aValue >= 0 ? aValue : -aValue;
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> :
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; };
115 :
116 : } // namespace detail
117 :
118 : template<typename T>
119 : inline typename detail::AbsReturnType<T>::Type
120 3222 : Abs(const T aValue)
121 : {
122 : typedef typename detail::AbsReturnType<T>::Type ReturnType;
123 3222 : return aValue >= 0 ? ReturnType(aValue) : ~ReturnType(aValue) + 1;
124 : }
125 :
126 : template<>
127 : inline float
128 578 : Abs<float>(const float aFloat)
129 : {
130 578 : return std::fabs(aFloat);
131 : }
132 :
133 : template<>
134 : inline double
135 120 : Abs<double>(const double aDouble)
136 : {
137 120 : return std::fabs(aDouble);
138 : }
139 :
140 : template<>
141 : inline long double
142 : Abs<long double>(const long double aLongDouble)
143 : {
144 : return std::fabs(aLongDouble);
145 : }
146 :
147 : } // namespace mozilla
148 :
149 : #if defined(_MSC_VER) && \
150 : (defined(_M_IX86) || defined(_M_AMD64) || defined(_M_X64))
151 : # define MOZ_BITSCAN_WINDOWS
152 :
153 : # include <intrin.h>
154 : # pragma intrinsic(_BitScanForward, _BitScanReverse)
155 :
156 : # if defined(_M_AMD64) || defined(_M_X64)
157 : # define MOZ_BITSCAN_WINDOWS64
158 : # pragma intrinsic(_BitScanForward64, _BitScanReverse64)
159 : # endif
160 :
161 : #endif
162 :
163 : namespace mozilla {
164 :
165 : namespace detail {
166 :
167 : #if defined(MOZ_BITSCAN_WINDOWS)
168 :
169 : inline uint_fast8_t
170 : CountLeadingZeroes32(uint32_t aValue)
171 : {
172 : unsigned long index;
173 : if (!_BitScanReverse(&index, static_cast<unsigned long>(aValue)))
174 : return 32;
175 : return uint_fast8_t(31 - index);
176 : }
177 :
178 :
179 : inline uint_fast8_t
180 : CountTrailingZeroes32(uint32_t aValue)
181 : {
182 : unsigned long index;
183 : if (!_BitScanForward(&index, static_cast<unsigned long>(aValue)))
184 : return 32;
185 : return uint_fast8_t(index);
186 : }
187 :
188 : inline uint_fast8_t
189 : CountPopulation32(uint32_t aValue)
190 : {
191 : uint32_t x = aValue - ((aValue >> 1) & 0x55555555);
192 : x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
193 : return (((x + (x >> 4)) & 0xf0f0f0f) * 0x1010101) >> 24;
194 : }
195 : inline uint_fast8_t
196 : CountPopulation64(uint64_t aValue)
197 : {
198 : return uint_fast8_t(CountPopulation32(aValue & 0xffffffff) +
199 : CountPopulation32(aValue >> 32));
200 : }
201 :
202 : inline uint_fast8_t
203 : CountLeadingZeroes64(uint64_t aValue)
204 : {
205 : #if defined(MOZ_BITSCAN_WINDOWS64)
206 : unsigned long index;
207 : if (!_BitScanReverse64(&index, static_cast<unsigned __int64>(aValue)))
208 : return 64;
209 : return uint_fast8_t(63 - index);
210 : #else
211 : uint32_t hi = uint32_t(aValue >> 32);
212 : if (hi != 0) {
213 : return CountLeadingZeroes32(hi);
214 : }
215 : return 32u + CountLeadingZeroes32(uint32_t(aValue));
216 : #endif
217 : }
218 :
219 : inline uint_fast8_t
220 : CountTrailingZeroes64(uint64_t aValue)
221 : {
222 : #if defined(MOZ_BITSCAN_WINDOWS64)
223 : unsigned long index;
224 : if (!_BitScanForward64(&index, static_cast<unsigned __int64>(aValue)))
225 : return 64;
226 : return uint_fast8_t(index);
227 : #else
228 : uint32_t lo = uint32_t(aValue);
229 : if (lo != 0) {
230 : return CountTrailingZeroes32(lo);
231 : }
232 : return 32u + CountTrailingZeroes32(uint32_t(aValue >> 32));
233 : #endif
234 : }
235 :
236 : # ifdef MOZ_HAVE_BITSCAN64
237 : # undef MOZ_HAVE_BITSCAN64
238 : # endif
239 :
240 : #elif defined(__clang__) || defined(__GNUC__)
241 :
242 : # if defined(__clang__)
243 : # if !__has_builtin(__builtin_ctz) || !__has_builtin(__builtin_clz)
244 : # error "A clang providing __builtin_c[lt]z is required to build"
245 : # endif
246 : # else
247 : // gcc has had __builtin_clz and friends since 3.4: no need to check.
248 : # endif
249 :
250 : inline uint_fast8_t
251 234682 : CountLeadingZeroes32(uint32_t aValue)
252 : {
253 234682 : return __builtin_clz(aValue);
254 : }
255 :
256 : inline uint_fast8_t
257 209264 : CountTrailingZeroes32(uint32_t aValue)
258 : {
259 209264 : return __builtin_ctz(aValue);
260 : }
261 :
262 : inline uint_fast8_t
263 113737 : CountPopulation32(uint32_t aValue)
264 : {
265 113737 : return __builtin_popcount(aValue);
266 : }
267 :
268 : inline uint_fast8_t
269 0 : CountPopulation64(uint64_t aValue)
270 : {
271 0 : return __builtin_popcountll(aValue);
272 : }
273 :
274 : inline uint_fast8_t
275 2475534 : CountLeadingZeroes64(uint64_t aValue)
276 : {
277 2475534 : return __builtin_clzll(aValue);
278 : }
279 :
280 : inline uint_fast8_t
281 7155 : CountTrailingZeroes64(uint64_t aValue)
282 : {
283 7155 : return __builtin_ctzll(aValue);
284 : }
285 :
286 : #else
287 : # error "Implement these!"
288 : inline uint_fast8_t CountLeadingZeroes32(uint32_t aValue) = delete;
289 : inline uint_fast8_t CountTrailingZeroes32(uint32_t aValue) = delete;
290 : inline uint_fast8_t CountPopulation32(uint32_t aValue) = delete;
291 : inline uint_fast8_t CountPopulation64(uint64_t aValue) = delete;
292 : inline uint_fast8_t CountLeadingZeroes64(uint64_t aValue) = delete;
293 : inline uint_fast8_t CountTrailingZeroes64(uint64_t aValue) = delete;
294 : #endif
295 :
296 : } // namespace detail
297 :
298 : /**
299 : * Compute the number of high-order zero bits in the NON-ZERO number |aValue|.
300 : * That is, looking at the bitwise representation of the number, with the
301 : * highest- valued bits at the start, return the number of zeroes before the
302 : * first one is observed.
303 : *
304 : * CountLeadingZeroes32(0xF0FF1000) is 0;
305 : * CountLeadingZeroes32(0x7F8F0001) is 1;
306 : * CountLeadingZeroes32(0x3FFF0100) is 2;
307 : * CountLeadingZeroes32(0x1FF50010) is 3; and so on.
308 : */
309 : inline uint_fast8_t
310 182879 : CountLeadingZeroes32(uint32_t aValue)
311 : {
312 182879 : MOZ_ASSERT(aValue != 0);
313 182879 : return detail::CountLeadingZeroes32(aValue);
314 : }
315 :
316 : /**
317 : * Compute the number of low-order zero bits in the NON-ZERO number |aValue|.
318 : * That is, looking at the bitwise representation of the number, with the
319 : * lowest- valued bits at the start, return the number of zeroes before the
320 : * first one is observed.
321 : *
322 : * CountTrailingZeroes32(0x0100FFFF) is 0;
323 : * CountTrailingZeroes32(0x7000FFFE) is 1;
324 : * CountTrailingZeroes32(0x0080FFFC) is 2;
325 : * CountTrailingZeroes32(0x0080FFF8) is 3; and so on.
326 : */
327 : inline uint_fast8_t
328 209264 : CountTrailingZeroes32(uint32_t aValue)
329 : {
330 209264 : MOZ_ASSERT(aValue != 0);
331 209264 : return detail::CountTrailingZeroes32(aValue);
332 : }
333 :
334 : /**
335 : * Compute the number of one bits in the number |aValue|,
336 : */
337 : inline uint_fast8_t
338 113737 : CountPopulation32(uint32_t aValue)
339 : {
340 113737 : return detail::CountPopulation32(aValue);
341 : }
342 :
343 : /** Analogous to CountPopulation32, but for 64-bit numbers */
344 : inline uint_fast8_t
345 0 : CountPopulation64(uint64_t aValue)
346 : {
347 0 : return detail::CountPopulation64(aValue);
348 : }
349 :
350 : /** Analogous to CountLeadingZeroes32, but for 64-bit numbers. */
351 : inline uint_fast8_t
352 662344 : CountLeadingZeroes64(uint64_t aValue)
353 : {
354 662344 : MOZ_ASSERT(aValue != 0);
355 662344 : return detail::CountLeadingZeroes64(aValue);
356 : }
357 :
358 : /** Analogous to CountTrailingZeroes32, but for 64-bit numbers. */
359 : inline uint_fast8_t
360 7155 : CountTrailingZeroes64(uint64_t aValue)
361 : {
362 7155 : MOZ_ASSERT(aValue != 0);
363 7155 : return detail::CountTrailingZeroes64(aValue);
364 : }
365 :
366 : namespace detail {
367 :
368 : template<typename T, size_t Size = sizeof(T)>
369 : class CeilingLog2;
370 :
371 : template<typename T>
372 : class CeilingLog2<T, 4>
373 : {
374 : public:
375 13622 : static uint_fast8_t compute(const T aValue)
376 : {
377 : // Check for <= 1 to avoid the == 0 undefined case.
378 13622 : return aValue <= 1 ? 0u : 32u - CountLeadingZeroes32(aValue - 1);
379 : }
380 : };
381 :
382 : template<typename T>
383 : class CeilingLog2<T, 8>
384 : {
385 : public:
386 1813610 : static uint_fast8_t compute(const T aValue)
387 : {
388 : // Check for <= 1 to avoid the == 0 undefined case.
389 1813610 : return aValue <= 1 ? 0u : 64u - CountLeadingZeroes64(aValue - 1);
390 : }
391 : };
392 :
393 : } // namespace detail
394 :
395 : /**
396 : * Compute the log of the least power of 2 greater than or equal to |aValue|.
397 : *
398 : * CeilingLog2(0..1) is 0;
399 : * CeilingLog2(2) is 1;
400 : * CeilingLog2(3..4) is 2;
401 : * CeilingLog2(5..8) is 3;
402 : * CeilingLog2(9..16) is 4; and so on.
403 : */
404 : template<typename T>
405 : inline uint_fast8_t
406 1827231 : CeilingLog2(const T aValue)
407 : {
408 1827231 : return detail::CeilingLog2<T>::compute(aValue);
409 : }
410 :
411 : /** A CeilingLog2 variant that accepts only size_t. */
412 : inline uint_fast8_t
413 2717 : CeilingLog2Size(size_t aValue)
414 : {
415 2717 : return CeilingLog2(aValue);
416 : }
417 :
418 : namespace detail {
419 :
420 : template<typename T, size_t Size = sizeof(T)>
421 : class FloorLog2;
422 :
423 : template<typename T>
424 : class FloorLog2<T, 4>
425 : {
426 : public:
427 37601 : static uint_fast8_t compute(const T aValue)
428 : {
429 37601 : return 31u - CountLeadingZeroes32(aValue | 1);
430 : }
431 : };
432 :
433 : template<typename T>
434 : class FloorLog2<T, 8>
435 : {
436 : public:
437 0 : static uint_fast8_t compute(const T aValue)
438 : {
439 0 : return 63u - CountLeadingZeroes64(aValue | 1);
440 : }
441 : };
442 :
443 : } // namespace detail
444 :
445 : /**
446 : * Compute the log of the greatest power of 2 less than or equal to |aValue|.
447 : *
448 : * FloorLog2(0..1) is 0;
449 : * FloorLog2(2..3) is 1;
450 : * FloorLog2(4..7) is 2;
451 : * FloorLog2(8..15) is 3; and so on.
452 : */
453 : template<typename T>
454 : inline uint_fast8_t
455 37601 : FloorLog2(const T aValue)
456 : {
457 37601 : return detail::FloorLog2<T>::compute(aValue);
458 : }
459 :
460 : /** A FloorLog2 variant that accepts only size_t. */
461 : inline uint_fast8_t
462 0 : FloorLog2Size(size_t aValue)
463 : {
464 0 : return FloorLog2(aValue);
465 : }
466 :
467 : /*
468 : * Compute the smallest power of 2 greater than or equal to |x|. |x| must not
469 : * be so great that the computed value would overflow |size_t|.
470 : */
471 : inline size_t
472 1810856 : RoundUpPow2(size_t aValue)
473 : {
474 1810856 : MOZ_ASSERT(aValue <= (size_t(1) << (sizeof(size_t) * CHAR_BIT - 1)),
475 : "can't round up -- will overflow!");
476 1810856 : return size_t(1) << CeilingLog2(aValue);
477 : }
478 :
479 : /**
480 : * Rotates the bits of the given value left by the amount of the shift width.
481 : */
482 : template<typename T>
483 : inline T
484 702700 : RotateLeft(const T aValue, uint_fast8_t aShift)
485 : {
486 702700 : MOZ_ASSERT(aShift < sizeof(T) * CHAR_BIT, "Shift value is too large!");
487 702700 : MOZ_ASSERT(aShift > 0,
488 : "Rotation by value length is undefined behavior, but compilers "
489 : "do not currently fold a test into the rotate instruction. "
490 : "Please remove this restriction when compilers optimize the "
491 : "zero case (http://blog.regehr.org/archives/1063).");
492 : static_assert(IsUnsigned<T>::value, "Rotates require unsigned values");
493 702700 : return (aValue << aShift) | (aValue >> (sizeof(T) * CHAR_BIT - aShift));
494 : }
495 :
496 : /**
497 : * Rotates the bits of the given value right by the amount of the shift width.
498 : */
499 : template<typename T>
500 : inline T
501 : RotateRight(const T aValue, uint_fast8_t aShift)
502 : {
503 : MOZ_ASSERT(aShift < sizeof(T) * CHAR_BIT, "Shift value is too large!");
504 : MOZ_ASSERT(aShift > 0,
505 : "Rotation by value length is undefined behavior, but compilers "
506 : "do not currently fold a test into the rotate instruction. "
507 : "Please remove this restriction when compilers optimize the "
508 : "zero case (http://blog.regehr.org/archives/1063).");
509 : static_assert(IsUnsigned<T>::value, "Rotates require unsigned values");
510 : return (aValue >> aShift) | (aValue << (sizeof(T) * CHAR_BIT - aShift));
511 : }
512 :
513 : /**
514 : * Returns true if |x| is a power of two.
515 : * Zero is not an integer power of two. (-Inf is not an integer)
516 : */
517 : template<typename T>
518 : constexpr bool
519 39906 : IsPowerOfTwo(T x)
520 : {
521 : static_assert(IsUnsigned<T>::value,
522 : "IsPowerOfTwo requires unsigned values");
523 39906 : return x && (x & (x - 1)) == 0;
524 : }
525 :
526 : template<typename T>
527 : inline T
528 0 : Clamp(const T aValue, const T aMin, const T aMax)
529 : {
530 : static_assert(IsIntegral<T>::value,
531 : "Clamp accepts only integral types, so that it doesn't have"
532 : " to distinguish differently-signed zeroes (which users may"
533 : " or may not care to distinguish, likely at a perf cost) or"
534 : " to decide how to clamp NaN or a range with a NaN"
535 : " endpoint.");
536 0 : MOZ_ASSERT(aMin <= aMax);
537 :
538 0 : if (aValue <= aMin)
539 0 : return aMin;
540 0 : if (aValue >= aMax)
541 0 : return aMax;
542 0 : return aValue;
543 : }
544 :
545 : } /* namespace mozilla */
546 :
547 : #endif /* mozilla_MathAlgorithms_h */
|
