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/. */
10 #include <type_traits>
12 #include "mozilla/CheckedInt.h"
13 #include "mozilla/TemplateLib.h"
15 // Helper for log2 of powers of 2 at compile time.
17 struct Log2
: mozilla::tl::CeilingLog2
<N
> {
18 using mozilla::tl::CeilingLog2
<N
>::value
;
19 static_assert(1ULL << value
== N
, "Number is not a power of 2");
21 #define LOG2(N) Log2<N>::value
29 // Compare two integers. Returns whether the first integer is Less,
30 // Equal or Greater than the second integer.
32 Order
CompareInt(T aValue1
, T aValue2
) {
33 static_assert(std::is_integral_v
<T
>, "Type must be integral");
34 if (aValue1
< aValue2
) {
37 if (aValue1
> aValue2
) {
38 return Order::eGreater
;
43 // Compare two addresses. Returns whether the first address is Less,
44 // Equal or Greater than the second address.
46 Order
CompareAddr(T
* aAddr1
, T
* aAddr2
) {
47 return CompareInt(uintptr_t(aAddr1
), uintptr_t(aAddr2
));
50 // Helper for (fast) comparison of fractions without involving divisions or
54 explicit constexpr Fraction(size_t aNumerator
, size_t aDenominator
)
55 : mNumerator(aNumerator
), mDenominator(aDenominator
) {}
57 MOZ_IMPLICIT
constexpr Fraction(long double aValue
)
58 // We use an arbitrary power of two as denominator that provides enough
59 // precision for our use case.
60 : mNumerator(aValue
* 4096), mDenominator(4096) {}
62 inline bool operator<(const Fraction
& aOther
) const {
64 // We are comparing A / B < C / D, with all A, B, C and D being positive
65 // numbers. Multiplying both sides with B * D, we have:
66 // (A * B * D) / B < (C * B * D) / D, which can then be simplified as
67 // A * D < C * B. When can thus compare our fractions without actually
68 // doing any division.
69 // This however assumes the multiplied quantities are small enough not
70 // to overflow the multiplication. We use CheckedInt on debug builds
71 // to enforce the assumption.
72 return mNumerator
* aOther
.mDenominator
< aOther
.mNumerator
* mDenominator
;
74 mozilla::CheckedInt
<size_t> numerator(mNumerator
);
75 mozilla::CheckedInt
<size_t> denominator(mDenominator
);
76 // value() asserts when the multiplication overflowed.
77 size_t lhs
= (numerator
* aOther
.mDenominator
).value();
78 size_t rhs
= (aOther
.mNumerator
* denominator
).value();
83 inline bool operator>(const Fraction
& aOther
) const { return aOther
< *this; }
85 inline bool operator>=(const Fraction
& aOther
) const {
86 return !(*this < aOther
);
89 inline bool operator<=(const Fraction
& aOther
) const {
90 return !(*this > aOther
);
93 inline bool operator==(const Fraction
& aOther
) const {
95 // Same logic as operator<
96 return mNumerator
* aOther
.mDenominator
== aOther
.mNumerator
* mDenominator
;
98 mozilla::CheckedInt
<size_t> numerator(mNumerator
);
99 mozilla::CheckedInt
<size_t> denominator(mDenominator
);
100 size_t lhs
= (numerator
* aOther
.mDenominator
).value();
101 size_t rhs
= (aOther
.mNumerator
* denominator
).value();
106 inline bool operator!=(const Fraction
& aOther
) const {
107 return !(*this == aOther
);