Vladimir Marko | 80afd02 | 2015-05-19 18:08:00 +0100 | [diff] [blame^] | 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_ |