bit_utils.h revision 51db2c217052fd6881b81f3ac5162fe88c36dbf0
1/* 2 * Copyright (C) 2015 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17#ifndef ART_RUNTIME_BASE_BIT_UTILS_H_ 18#define ART_RUNTIME_BASE_BIT_UTILS_H_ 19 20#include <iterator> 21#include <limits> 22#include <type_traits> 23 24#include "base/logging.h" 25#include "base/iteration_range.h" 26 27namespace art { 28 29template<typename T> 30static constexpr int CLZ(T x) { 31 static_assert(std::is_integral<T>::value, "T must be integral"); 32 static_assert(std::is_unsigned<T>::value, "T must be unsigned"); 33 static_assert(sizeof(T) <= sizeof(long long), // NOLINT [runtime/int] [4] 34 "T too large, must be smaller than long long"); 35 return 36 DCHECK_CONSTEXPR(x != 0, "x must not be zero", T(0)) 37 (sizeof(T) == sizeof(uint32_t)) 38 ? __builtin_clz(x) 39 : __builtin_clzll(x); 40} 41 42template<typename T> 43static constexpr int CTZ(T x) { 44 static_assert(std::is_integral<T>::value, "T must be integral"); 45 // A similar check to the above does not make sense. It isn't as non-intuitive to ask for 46 // trailing zeros in a negative number, and the quick backends do this for immediate encodings. 47 static_assert(sizeof(T) <= sizeof(long long), // NOLINT [runtime/int] [4] 48 "T too large, must be smaller than long long"); 49 return 50 DCHECK_CONSTEXPR(x != 0, "x must not be zero", T(0)) 51 (sizeof(T) == sizeof(uint32_t)) 52 ? __builtin_ctz(x) 53 : __builtin_ctzll(x); 54} 55 56template<typename T> 57static constexpr int POPCOUNT(T x) { 58 return (sizeof(T) == sizeof(uint32_t)) 59 ? __builtin_popcount(x) 60 : __builtin_popcountll(x); 61} 62 63// Find the bit position of the most significant bit (0-based), or -1 if there were no bits set. 64template <typename T> 65static constexpr ssize_t MostSignificantBit(T value) { 66 static_assert(std::is_integral<T>::value, "T must be integral"); 67 static_assert(std::is_unsigned<T>::value, "T must be unsigned"); 68 static_assert(std::numeric_limits<T>::radix == 2, "Unexpected radix!"); 69 return (value == 0) ? -1 : std::numeric_limits<T>::digits - 1 - CLZ(value); 70} 71 72// Find the bit position of the least significant bit (0-based), or -1 if there were no bits set. 73template <typename T> 74static constexpr ssize_t LeastSignificantBit(T value) { 75 static_assert(std::is_integral<T>::value, "T must be integral"); 76 static_assert(std::is_unsigned<T>::value, "T must be unsigned"); 77 return (value == 0) ? -1 : CTZ(value); 78} 79 80// How many bits (minimally) does it take to store the constant 'value'? i.e. 1 for 1, 3 for 5, etc. 81template <typename T> 82static constexpr size_t MinimumBitsToStore(T value) { 83 return static_cast<size_t>(MostSignificantBit(value) + 1); 84} 85 86template <typename T> 87static constexpr inline T RoundUpToPowerOfTwo(T x) { 88 static_assert(std::is_integral<T>::value, "T must be integral"); 89 static_assert(std::is_unsigned<T>::value, "T must be unsigned"); 90 // NOTE: Undefined if x > (1 << (std::numeric_limits<T>::digits - 1)). 91 return (x < 2u) ? x : static_cast<T>(1u) << (std::numeric_limits<T>::digits - CLZ(x - 1u)); 92} 93 94template<typename T> 95static constexpr bool IsPowerOfTwo(T x) { 96 static_assert(std::is_integral<T>::value, "T must be integral"); 97 // TODO: assert unsigned. There is currently many uses with signed values. 98 return (x & (x - 1)) == 0; 99} 100 101template<typename T> 102static inline int WhichPowerOf2(T x) { 103 static_assert(std::is_integral<T>::value, "T must be integral"); 104 // TODO: assert unsigned. There is currently many uses with signed values. 105 DCHECK((x != 0) && IsPowerOfTwo(x)); 106 return CTZ(x); 107} 108 109// For rounding integers. 110// NOTE: In the absence of std::omit_from_type_deduction<T> or std::identity<T>, use std::decay<T>. 111template<typename T> 112static constexpr T RoundDown(T x, typename std::decay<T>::type n) WARN_UNUSED; 113 114template<typename T> 115static constexpr T RoundDown(T x, typename std::decay<T>::type n) { 116 return 117 DCHECK_CONSTEXPR(IsPowerOfTwo(n), , T(0)) 118 (x & -n); 119} 120 121template<typename T> 122static constexpr T RoundUp(T x, typename std::remove_reference<T>::type n) WARN_UNUSED; 123 124template<typename T> 125static constexpr T RoundUp(T x, typename std::remove_reference<T>::type n) { 126 return RoundDown(x + n - 1, n); 127} 128 129// For aligning pointers. 130template<typename T> 131static inline T* AlignDown(T* x, uintptr_t n) WARN_UNUSED; 132 133template<typename T> 134static inline T* AlignDown(T* x, uintptr_t n) { 135 return reinterpret_cast<T*>(RoundDown(reinterpret_cast<uintptr_t>(x), n)); 136} 137 138template<typename T> 139static inline T* AlignUp(T* x, uintptr_t n) WARN_UNUSED; 140 141template<typename T> 142static inline T* AlignUp(T* x, uintptr_t n) { 143 return reinterpret_cast<T*>(RoundUp(reinterpret_cast<uintptr_t>(x), n)); 144} 145 146template<int n, typename T> 147static constexpr bool IsAligned(T x) { 148 static_assert((n & (n - 1)) == 0, "n is not a power of two"); 149 return (x & (n - 1)) == 0; 150} 151 152template<int n, typename T> 153static inline bool IsAligned(T* x) { 154 return IsAligned<n>(reinterpret_cast<const uintptr_t>(x)); 155} 156 157template<typename T> 158static inline bool IsAlignedParam(T x, int n) { 159 return (x & (n - 1)) == 0; 160} 161 162#define CHECK_ALIGNED(value, alignment) \ 163 CHECK(::art::IsAligned<alignment>(value)) << reinterpret_cast<const void*>(value) 164 165#define DCHECK_ALIGNED(value, alignment) \ 166 DCHECK(::art::IsAligned<alignment>(value)) << reinterpret_cast<const void*>(value) 167 168#define DCHECK_ALIGNED_PARAM(value, alignment) \ 169 DCHECK(::art::IsAlignedParam(value, alignment)) << reinterpret_cast<const void*>(value) 170 171// Like sizeof, but count how many bits a type takes. Pass type explicitly. 172template <typename T> 173static constexpr size_t BitSizeOf() { 174 static_assert(std::is_integral<T>::value, "T must be integral"); 175 typedef typename std::make_unsigned<T>::type unsigned_type; 176 static_assert(sizeof(T) == sizeof(unsigned_type), "Unexpected type size mismatch!"); 177 static_assert(std::numeric_limits<unsigned_type>::radix == 2, "Unexpected radix!"); 178 return std::numeric_limits<unsigned_type>::digits; 179} 180 181// Like sizeof, but count how many bits a type takes. Infers type from parameter. 182template <typename T> 183static constexpr size_t BitSizeOf(T /*x*/) { 184 return BitSizeOf<T>(); 185} 186 187static inline uint16_t Low16Bits(uint32_t value) { 188 return static_cast<uint16_t>(value); 189} 190 191static inline uint16_t High16Bits(uint32_t value) { 192 return static_cast<uint16_t>(value >> 16); 193} 194 195static inline uint32_t Low32Bits(uint64_t value) { 196 return static_cast<uint32_t>(value); 197} 198 199static inline uint32_t High32Bits(uint64_t value) { 200 return static_cast<uint32_t>(value >> 32); 201} 202 203// Check whether an N-bit two's-complement representation can hold value. 204template <typename T> 205static inline bool IsInt(size_t N, T value) { 206 if (N == BitSizeOf<T>()) { 207 return true; 208 } else { 209 CHECK_LT(0u, N); 210 CHECK_LT(N, BitSizeOf<T>()); 211 T limit = static_cast<T>(1) << (N - 1u); 212 return (-limit <= value) && (value < limit); 213 } 214} 215 216template <typename T> 217static constexpr T GetIntLimit(size_t bits) { 218 return 219 DCHECK_CONSTEXPR(bits > 0, "bits cannot be zero", 0) 220 DCHECK_CONSTEXPR(bits < BitSizeOf<T>(), "kBits must be < max.", 0) 221 static_cast<T>(1) << (bits - 1); 222} 223 224template <size_t kBits, typename T> 225static constexpr bool IsInt(T value) { 226 static_assert(kBits > 0, "kBits cannot be zero."); 227 static_assert(kBits <= BitSizeOf<T>(), "kBits must be <= max."); 228 static_assert(std::is_signed<T>::value, "Needs a signed type."); 229 // Corner case for "use all bits." Can't use the limits, as they would overflow, but it is 230 // trivially true. 231 return (kBits == BitSizeOf<T>()) ? 232 true : 233 (-GetIntLimit<T>(kBits) <= value) && (value < GetIntLimit<T>(kBits)); 234} 235 236template <size_t kBits, typename T> 237static constexpr bool IsUint(T value) { 238 static_assert(kBits > 0, "kBits cannot be zero."); 239 static_assert(kBits <= BitSizeOf<T>(), "kBits must be <= max."); 240 static_assert(std::is_integral<T>::value, "Needs an integral type."); 241 // Corner case for "use all bits." Can't use the limits, as they would overflow, but it is 242 // trivially true. 243 // NOTE: To avoid triggering assertion in GetIntLimit(kBits+1) if kBits+1==BitSizeOf<T>(), 244 // use GetIntLimit(kBits)*2u. The unsigned arithmetic works well for us if it overflows. 245 return (0 <= value) && 246 (kBits == BitSizeOf<T>() || 247 (static_cast<typename std::make_unsigned<T>::type>(value) <= 248 GetIntLimit<typename std::make_unsigned<T>::type>(kBits) * 2u - 1u)); 249} 250 251template <size_t kBits, typename T> 252static constexpr bool IsAbsoluteUint(T value) { 253 static_assert(kBits <= BitSizeOf<T>(), "kBits must be <= max."); 254 static_assert(std::is_integral<T>::value, "Needs an integral type."); 255 typedef typename std::make_unsigned<T>::type unsigned_type; 256 return (kBits == BitSizeOf<T>()) 257 ? true 258 : IsUint<kBits>(value < 0 259 ? static_cast<unsigned_type>(-1 - value) + 1u // Avoid overflow. 260 : static_cast<unsigned_type>(value)); 261} 262 263// Using the Curiously Recurring Template Pattern to implement everything shared 264// by LowToHighBitIterator and HighToLowBitIterator, i.e. everything but operator*(). 265template <typename T, typename Iter> 266class BitIteratorBase 267 : public std::iterator<std::forward_iterator_tag, uint32_t, ptrdiff_t, void, void> { 268 static_assert(std::is_integral<T>::value, "T must be integral"); 269 static_assert(std::is_unsigned<T>::value, "T must be unsigned"); 270 271 static_assert(sizeof(T) == sizeof(uint32_t) || sizeof(T) == sizeof(uint64_t), "Unsupported size"); 272 273 public: 274 BitIteratorBase() : bits_(0u) { } 275 explicit BitIteratorBase(T bits) : bits_(bits) { } 276 277 Iter& operator++() { 278 DCHECK_NE(bits_, 0u); 279 uint32_t bit = *static_cast<Iter&>(*this); 280 bits_ &= ~(static_cast<T>(1u) << bit); 281 return static_cast<Iter&>(*this); 282 } 283 284 Iter& operator++(int) { 285 Iter tmp(static_cast<Iter&>(*this)); 286 ++*this; 287 return tmp; 288 } 289 290 protected: 291 T bits_; 292 293 template <typename U, typename I> 294 friend bool operator==(const BitIteratorBase<U, I>& lhs, const BitIteratorBase<U, I>& rhs); 295}; 296 297template <typename T, typename Iter> 298bool operator==(const BitIteratorBase<T, Iter>& lhs, const BitIteratorBase<T, Iter>& rhs) { 299 return lhs.bits_ == rhs.bits_; 300} 301 302template <typename T, typename Iter> 303bool operator!=(const BitIteratorBase<T, Iter>& lhs, const BitIteratorBase<T, Iter>& rhs) { 304 return !(lhs == rhs); 305} 306 307template <typename T> 308class LowToHighBitIterator : public BitIteratorBase<T, LowToHighBitIterator<T>> { 309 public: 310 using BitIteratorBase<T, LowToHighBitIterator<T>>::BitIteratorBase; 311 312 uint32_t operator*() const { 313 DCHECK_NE(this->bits_, 0u); 314 return CTZ(this->bits_); 315 } 316}; 317 318template <typename T> 319class HighToLowBitIterator : public BitIteratorBase<T, HighToLowBitIterator<T>> { 320 public: 321 using BitIteratorBase<T, HighToLowBitIterator<T>>::BitIteratorBase; 322 323 uint32_t operator*() const { 324 DCHECK_NE(this->bits_, 0u); 325 static_assert(std::numeric_limits<T>::radix == 2, "Unexpected radix!"); 326 return std::numeric_limits<T>::digits - 1u - CLZ(this->bits_); 327 } 328}; 329 330template <typename T> 331IterationRange<LowToHighBitIterator<T>> LowToHighBits(T bits) { 332 return IterationRange<LowToHighBitIterator<T>>( 333 LowToHighBitIterator<T>(bits), LowToHighBitIterator<T>()); 334} 335 336template <typename T> 337IterationRange<HighToLowBitIterator<T>> HighToLowBits(T bits) { 338 return IterationRange<HighToLowBitIterator<T>>( 339 HighToLowBitIterator<T>(bits), HighToLowBitIterator<T>()); 340} 341 342} // namespace art 343 344#endif // ART_RUNTIME_BASE_BIT_UTILS_H_ 345