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