PowerOfTwo.h (12233B)
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/. */ 6 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). 11 // 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 16 // power of 2. 17 // 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. 22 // 23 // Shortcuts for common 32- and 64-bit values: PowerOfTwo32, etc. 24 // 25 // To create constexpr constants, use MakePowerOfTwo<Type, Value>(), etc. 26 27 #ifndef PowerOfTwo_h 28 #define PowerOfTwo_h 29 30 #include "mozilla/MathAlgorithms.h" 31 32 #include <limits> 33 34 namespace mozilla { 35 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. 39 template <typename T> 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); 44 if (aInput >= max) { 45 return max; 46 } 47 return T(1) << CeilingLog2(aInput); 48 } 49 50 namespace detail { 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); 55 } 56 inline uint_fast8_t CountLeadingZeroes(uint64_t aValue) { 57 MOZ_ASSERT(aValue != 0); 58 return detail::CountLeadingZeroes64(aValue); 59 } 60 // Refuse anything else. 61 template <typename T> 62 inline uint_fast8_t CountLeadingZeroes(T aValue) = delete; 63 } // namespace detail 64 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 73 template <typename T> 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!) 77 if (aInput == 0) { 78 return 0; 79 } 80 return T(-1) >> detail::CountLeadingZeroes(aInput); 81 } 82 83 template <typename T> 84 class PowerOfTwoMask; 85 86 template <typename T, T Mask> 87 constexpr PowerOfTwoMask<T> MakePowerOfTwoMask(); 88 89 template <typename T> 90 class PowerOfTwo; 91 92 template <typename T, T Value> 93 constexpr PowerOfTwo<T> MakePowerOfTwo(); 94 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 97 // container). 98 // Use this instead of PowerOfTwo if masking is the primary use of the value. 99 // 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"); 111 112 public: 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)) {} 116 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); 128 } 129 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"); 139 } 140 141 constexpr T MaskValue() const { return mMask; } 142 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()); 147 } 148 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); 153 } 154 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(); 161 } 162 163 constexpr bool operator==(const PowerOfTwoMask& aRhs) const { 164 return mMask == aRhs.mMask; 165 } 166 constexpr bool operator!=(const PowerOfTwoMask& aRhs) const { 167 return mMask != aRhs.mMask; 168 } 169 170 private: 171 // Trust `PowerOfTwo` to call the private Trusted constructor below. 172 friend class PowerOfTwo<T>; 173 174 // Trust `MakePowerOfTwoMask()` to call the private Trusted constructor below. 175 template <typename U, U Mask> 176 friend constexpr PowerOfTwoMask<U> MakePowerOfTwoMask(); 177 178 struct Trusted { 179 T mMask; 180 }; 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) {} 188 189 T mMask = 0; 190 }; 191 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}); 199 } 200 201 // PowerOfTwo will always contain a power of 2. 202 template <typename T> 203 class PowerOfTwo { 204 static_assert(!std::numeric_limits<T>::is_signed, 205 "PowerOfTwo must use an unsigned type"); 206 207 public: 208 // Construct a power of 2 that can fit the given value, or the highest power 209 // of 2 possible. 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)) {} 213 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"); 223 } 224 225 constexpr T Value() const { return mValue; } 226 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 230 // primary use case. 231 constexpr T MaskValue() const { return mValue - 1; } 232 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()}); 237 } 238 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(); 245 } 246 247 constexpr bool operator==(const PowerOfTwo& aRhs) const { 248 return mValue == aRhs.mValue; 249 } 250 constexpr bool operator!=(const PowerOfTwo& aRhs) const { 251 return mValue != aRhs.mValue; 252 } 253 constexpr bool operator<(const PowerOfTwo& aRhs) const { 254 return mValue < aRhs.mValue; 255 } 256 constexpr bool operator<=(const PowerOfTwo& aRhs) const { 257 return mValue <= aRhs.mValue; 258 } 259 constexpr bool operator>(const PowerOfTwo& aRhs) const { 260 return mValue > aRhs.mValue; 261 } 262 constexpr bool operator>=(const PowerOfTwo& aRhs) const { 263 return mValue >= aRhs.mValue; 264 } 265 266 private: 267 // Trust `MakePowerOfTwo()` to call the private Trusted constructor below. 268 template <typename U, U Value> 269 friend constexpr PowerOfTwo<U> MakePowerOfTwo(); 270 271 struct Trusted { 272 T mValue; 273 }; 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) {} 279 280 // The smallest power of 2 is 2^0 == 1. 281 T mValue = 1; 282 }; 283 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}); 291 } 292 293 // Shortcuts for the most common types and functions. 294 295 using PowerOfTwoMask32 = PowerOfTwoMask<uint32_t>; 296 using PowerOfTwo32 = PowerOfTwo<uint32_t>; 297 using PowerOfTwoMask64 = PowerOfTwoMask<uint64_t>; 298 using PowerOfTwo64 = PowerOfTwo<uint64_t>; 299 300 template <uint32_t Mask> 301 constexpr PowerOfTwoMask32 MakePowerOfTwoMask32() { 302 return MakePowerOfTwoMask<uint32_t, Mask>(); 303 } 304 305 template <uint32_t Value> 306 constexpr PowerOfTwo32 MakePowerOfTwo32() { 307 return MakePowerOfTwo<uint32_t, Value>(); 308 } 309 310 template <uint64_t Mask> 311 constexpr PowerOfTwoMask64 MakePowerOfTwoMask64() { 312 return MakePowerOfTwoMask<uint64_t, Mask>(); 313 } 314 315 template <uint64_t Value> 316 constexpr PowerOfTwo64 MakePowerOfTwo64() { 317 return MakePowerOfTwo<uint64_t, Value>(); 318 } 319 320 } // namespace mozilla 321 322 #endif // PowerOfTwo_h