1 /* -*- Mode: C++; tab-width: 2; 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 // PowerOfTwo is a value type that always hold a power of 2.
8 // It has the same size as their underlying unsigned type, but offer the
9 // guarantee of being a power of 2, which permits some optimizations when
10 // involved in modulo operations (using masking instead of actual modulo).
12 // PowerOfTwoMask contains a mask corresponding to a power of 2.
13 // E.g., 2^8 is 256 or 0x100, the corresponding mask is 2^8-1 or 255 or 0xFF.
14 // It should be used instead of PowerOfTwo in situations where most operations
15 // would be modulo, this saves having to recompute the mask from the stored
18 // One common use would be for ring-buffer containers with a power-of-2 size,
19 // where an index is usually converted to an in-buffer offset by `i % size`.
20 // Instead, the container could store a PowerOfTwo or PowerOfTwoMask, and do
21 // `i % p2` or `i & p2m`, which is more efficient than for arbitrary sizes.
23 // Shortcuts for common 32- and 64-bit values: PowerOfTwo32, etc.
25 // To create constexpr constants, use MakePowerOfTwo<Type, Value>(), etc.
30 #include "mozilla/MathAlgorithms.h"
36 // Compute the smallest power of 2 greater than or equal to aInput, except if
37 // that would overflow in which case the highest possible power of 2 if chosen.
38 // 0->1, 1->1, 2->2, 3->4, ... 2^31->2^31, 2^31+1->2^31 (for uint32_t), etc.
40 T
FriendlyRoundUpPow2(T aInput
) {
41 // This is the same code as `RoundUpPow2()`, except we handle any type (that
42 // CeilingLog2 supports) and allow the greater-than-max-power case.
43 constexpr T max
= T(1) << (sizeof(T
) * CHAR_BIT
- 1);
47 return T(1) << CeilingLog2(aInput
);
51 // Same function name `CountLeadingZeroes` with uint32_t and uint64_t overloads.
52 inline uint_fast8_t CountLeadingZeroes(uint32_t aValue
) {
53 MOZ_ASSERT(aValue
!= 0);
54 return detail::CountLeadingZeroes32(aValue
);
56 inline uint_fast8_t CountLeadingZeroes(uint64_t aValue
) {
57 MOZ_ASSERT(aValue
!= 0);
58 return detail::CountLeadingZeroes64(aValue
);
60 // Refuse anything else.
62 inline uint_fast8_t CountLeadingZeroes(T aValue
) = delete;
65 // Compute the smallest 2^N-1 mask where aInput can fit.
66 // I.e., `x & mask == x`, but `x & (mask >> 1) != x`.
67 // Or looking at binary, we want a mask with as many leading zeroes as the
68 // input, by right-shifting a full mask: (8-bit examples)
69 // input: 00000000 00000001 00000010 00010110 01111111 10000000
70 // N leading 0s: ^^^^^^^^ 8 ^^^^^^^ 7 ^^^^^^ 6 ^^^ 3 ^ 1 0
71 // full mask: 11111111 11111111 11111111 11111111 11111111 11111111
72 // full mask >> N: 00000000 00000001 00000011 00011111 01111111 11111111
74 T
RoundUpPow2Mask(T aInput
) {
75 // Special case, as CountLeadingZeroes(0) is undefined. (And even if that was
76 // defined, shifting by the full type size is also undefined!)
80 return T(-1) >> detail::CountLeadingZeroes(aInput
);
86 template <typename T
, T Mask
>
87 constexpr PowerOfTwoMask
<T
> MakePowerOfTwoMask();
92 template <typename T
, T Value
>
93 constexpr PowerOfTwo
<T
> MakePowerOfTwo();
95 // PowerOfTwoMask will always contain a mask for a power of 2, which is useful
96 // for power-of-2 modulo operations (e.g., to keep an index inside a power-of-2
98 // Use this instead of PowerOfTwo if masking is the primary use of the value.
100 // Note that this class can store a "full" mask where all bits are set, so it
101 // works for mask corresponding to the power of 2 that would overflow `T`
102 // (e.g., 2^32 for uint32_t gives a mask of 2^32-1, which fits in a uint32_t).
103 // For this reason there is no API that computes the power of 2 corresponding to
104 // the mask; But this can be done explicitly with `MaskValue() + 1`, which may
105 // be useful for computing things like distance-to-the-end by doing
106 // `MaskValue() + 1 - offset`, which works fine with unsigned number types.
107 template <typename T
>
108 class PowerOfTwoMask
{
109 static_assert(!std::numeric_limits
<T
>::is_signed
,
110 "PowerOfTwoMask must use an unsigned type");
113 // Construct a power of 2 mask where the given value can fit.
114 // Cannot be constexpr because of `RoundUpPow2Mask()`.
115 explicit PowerOfTwoMask(T aInput
) : mMask(RoundUpPow2Mask(aInput
)) {}
117 // Compute the mask corresponding to a PowerOfTwo.
118 // This saves having to compute the nearest 2^N-1.
119 // Not a conversion constructor, as that could be ambiguous whether we'd want
120 // the mask corresponding to the power of 2 (2^N -> 2^N-1), or the mask that
121 // can *contain* the PowerOfTwo value (2^N -> 2^(N+1)-1).
122 // Note: Not offering reverse PowerOfTwoMark-to-PowerOfTwo conversion, because
123 // that could result in an unexpected 0 result for the largest possible mask.
124 template <typename U
>
125 static constexpr PowerOfTwoMask
<U
> MaskForPowerOfTwo(
126 const PowerOfTwo
<U
>& aP2
) {
127 return PowerOfTwoMask(aP2
);
130 // Allow smaller unsigned types as input.
131 // Bigger or signed types must be explicitly converted by the caller.
132 template <typename U
>
133 explicit constexpr PowerOfTwoMask(U aInput
)
134 : mMask(RoundUpPow2Mask(static_cast<T
>(aInput
))) {
135 static_assert(!std::numeric_limits
<T
>::is_signed
,
136 "PowerOfTwoMask does not accept signed types");
137 static_assert(sizeof(U
) <= sizeof(T
),
138 "PowerOfTwoMask does not accept bigger types");
141 constexpr T
MaskValue() const { return mMask
; }
143 // `x & aPowerOfTwoMask` just works.
144 template <typename U
>
145 friend U
operator&(U aNumber
, PowerOfTwoMask aP2M
) {
146 return static_cast<U
>(aNumber
& aP2M
.MaskValue());
149 // `aPowerOfTwoMask & x` just works.
150 template <typename U
>
151 friend constexpr U
operator&(PowerOfTwoMask aP2M
, U aNumber
) {
152 return static_cast<U
>(aP2M
.MaskValue() & aNumber
);
155 // `x % aPowerOfTwoMask(2^N-1)` is equivalent to `x % 2^N` but is more
156 // optimal by doing `x & (2^N-1)`.
157 // Useful for templated code doing modulo with a template argument type.
158 template <typename U
>
159 friend constexpr U
operator%(U aNumerator
, PowerOfTwoMask aDenominator
) {
160 return aNumerator
& aDenominator
.MaskValue();
163 constexpr bool operator==(const PowerOfTwoMask
& aRhs
) const {
164 return mMask
== aRhs
.mMask
;
166 constexpr bool operator!=(const PowerOfTwoMask
& aRhs
) const {
167 return mMask
!= aRhs
.mMask
;
171 // Trust `PowerOfTwo` to call the private Trusted constructor below.
172 friend class PowerOfTwo
<T
>;
174 // Trust `MakePowerOfTwoMask()` to call the private Trusted constructor below.
175 template <typename U
, U Mask
>
176 friend constexpr PowerOfTwoMask
<U
> MakePowerOfTwoMask();
181 // Construct the mask corresponding to a PowerOfTwo.
182 // This saves having to compute the nearest 2^N-1.
183 // Note: Not a public PowerOfTwo->PowerOfTwoMask conversion constructor, as
184 // that could be ambiguous whether we'd want the mask corresponding to the
185 // power of 2 (2^N -> 2^N-1), or the mask that can *contain* the PowerOfTwo
186 // value (2^N -> 2^(N+1)-1).
187 explicit constexpr PowerOfTwoMask(const Trusted
& aP2
) : mMask(aP2
.mMask
) {}
192 // Make a PowerOfTwoMask constant, statically-checked.
193 template <typename T
, T Mask
>
194 constexpr PowerOfTwoMask
<T
> MakePowerOfTwoMask() {
195 static_assert(Mask
== T(-1) || IsPowerOfTwo(Mask
+ 1),
196 "MakePowerOfTwoMask<T, Mask>: Mask must be 2^N-1");
197 using Trusted
= typename PowerOfTwoMask
<T
>::Trusted
;
198 return PowerOfTwoMask
<T
>(Trusted
{Mask
});
201 // PowerOfTwo will always contain a power of 2.
202 template <typename T
>
204 static_assert(!std::numeric_limits
<T
>::is_signed
,
205 "PowerOfTwo must use an unsigned type");
208 // Construct a power of 2 that can fit the given value, or the highest power
210 // Caller should explicitly check/assert `Value() <= aInput` if they want to.
211 // Cannot be constexpr because of `FriendlyRoundUpPow2()`.
212 explicit PowerOfTwo(T aInput
) : mValue(FriendlyRoundUpPow2(aInput
)) {}
214 // Allow smaller unsigned types as input.
215 // Bigger or signed types must be explicitly converted by the caller.
216 template <typename U
>
217 explicit PowerOfTwo(U aInput
)
218 : mValue(FriendlyRoundUpPow2(static_cast<T
>(aInput
))) {
219 static_assert(!std::numeric_limits
<T
>::is_signed
,
220 "PowerOfTwo does not accept signed types");
221 static_assert(sizeof(U
) <= sizeof(T
),
222 "PowerOfTwo does not accept bigger types");
225 constexpr T
Value() const { return mValue
; }
227 // Binary mask corresponding to the power of 2, useful for modulo.
228 // E.g., `x & powerOfTwo(y).Mask()` == `x % powerOfTwo(y)`.
229 // Consider PowerOfTwoMask class instead of PowerOfTwo if masking is the
231 constexpr T
MaskValue() const { return mValue
- 1; }
233 // PowerOfTwoMask corresponding to this power of 2, useful for modulo.
234 constexpr PowerOfTwoMask
<T
> Mask() const {
235 using Trusted
= typename PowerOfTwoMask
<T
>::Trusted
;
236 return PowerOfTwoMask
<T
>(Trusted
{MaskValue()});
239 // `x % aPowerOfTwo` works optimally.
240 // Useful for templated code doing modulo with a template argument type.
241 // Use PowerOfTwoMask class instead if masking is the primary use case.
242 template <typename U
>
243 friend constexpr U
operator%(U aNumerator
, PowerOfTwo aDenominator
) {
244 return aNumerator
& aDenominator
.MaskValue();
247 constexpr bool operator==(const PowerOfTwo
& aRhs
) const {
248 return mValue
== aRhs
.mValue
;
250 constexpr bool operator!=(const PowerOfTwo
& aRhs
) const {
251 return mValue
!= aRhs
.mValue
;
253 constexpr bool operator<(const PowerOfTwo
& aRhs
) const {
254 return mValue
< aRhs
.mValue
;
256 constexpr bool operator<=(const PowerOfTwo
& aRhs
) const {
257 return mValue
<= aRhs
.mValue
;
259 constexpr bool operator>(const PowerOfTwo
& aRhs
) const {
260 return mValue
> aRhs
.mValue
;
262 constexpr bool operator>=(const PowerOfTwo
& aRhs
) const {
263 return mValue
>= aRhs
.mValue
;
267 // Trust `MakePowerOfTwo()` to call the private Trusted constructor below.
268 template <typename U
, U Value
>
269 friend constexpr PowerOfTwo
<U
> MakePowerOfTwo();
274 // Construct a PowerOfTwo with the given trusted value.
275 // This saves having to compute the nearest 2^N.
276 // Note: Not offering PowerOfTwoMark-to-PowerOfTwo conversion, because that
277 // could result in an unexpected 0 result for the largest possible mask.
278 explicit constexpr PowerOfTwo(const Trusted
& aP2
) : mValue(aP2
.mValue
) {}
280 // The smallest power of 2 is 2^0 == 1.
284 // Make a PowerOfTwo constant, statically-checked.
285 template <typename T
, T Value
>
286 constexpr PowerOfTwo
<T
> MakePowerOfTwo() {
287 static_assert(IsPowerOfTwo(Value
),
288 "MakePowerOfTwo<T, Value>: Value must be 2^N");
289 using Trusted
= typename PowerOfTwo
<T
>::Trusted
;
290 return PowerOfTwo
<T
>(Trusted
{Value
});
293 // Shortcuts for the most common types and functions.
295 using PowerOfTwoMask32
= PowerOfTwoMask
<uint32_t>;
296 using PowerOfTwo32
= PowerOfTwo
<uint32_t>;
297 using PowerOfTwoMask64
= PowerOfTwoMask
<uint64_t>;
298 using PowerOfTwo64
= PowerOfTwo
<uint64_t>;
300 template <uint32_t Mask
>
301 constexpr PowerOfTwoMask32
MakePowerOfTwoMask32() {
302 return MakePowerOfTwoMask
<uint32_t, Mask
>();
305 template <uint32_t Value
>
306 constexpr PowerOfTwo32
MakePowerOfTwo32() {
307 return MakePowerOfTwo
<uint32_t, Value
>();
310 template <uint64_t Mask
>
311 constexpr PowerOfTwoMask64
MakePowerOfTwoMask64() {
312 return MakePowerOfTwoMask
<uint64_t, Mask
>();
315 template <uint64_t Value
>
316 constexpr PowerOfTwo64
MakePowerOfTwo64() {
317 return MakePowerOfTwo
<uint64_t, Value
>();
320 } // namespace mozilla
322 #endif // PowerOfTwo_h