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/iteration_range.h" 25 #include "base/logging.h" 26 #include "base/stl_util.h" 27 28 namespace art { 29 30 // Like sizeof, but count how many bits a type takes. Pass type explicitly. 31 template <typename T> 32 constexpr size_t BitSizeOf() { 33 static_assert(std::is_integral<T>::value, "T must be integral"); 34 using unsigned_type = typename std::make_unsigned<T>::type; 35 static_assert(sizeof(T) == sizeof(unsigned_type), "Unexpected type size mismatch!"); 36 static_assert(std::numeric_limits<unsigned_type>::radix == 2, "Unexpected radix!"); 37 return std::numeric_limits<unsigned_type>::digits; 38 } 39 40 // Like sizeof, but count how many bits a type takes. Infers type from parameter. 41 template <typename T> 42 constexpr size_t BitSizeOf(T /*x*/) { 43 return BitSizeOf<T>(); 44 } 45 46 template<typename T> 47 constexpr int CLZ(T x) { 48 static_assert(std::is_integral<T>::value, "T must be integral"); 49 static_assert(std::is_unsigned<T>::value, "T must be unsigned"); 50 static_assert(sizeof(T) <= sizeof(long long), // NOLINT [runtime/int] [4] 51 "T too large, must be smaller than long long"); 52 DCHECK_NE(x, 0u); 53 return (sizeof(T) == sizeof(uint32_t)) ? __builtin_clz(x) : __builtin_clzll(x); 54 } 55 56 // Similar to CLZ except that on zero input it returns bitwidth and supports signed integers. 57 template<typename T> 58 constexpr int JAVASTYLE_CLZ(T x) { 59 static_assert(std::is_integral<T>::value, "T must be integral"); 60 using unsigned_type = typename std::make_unsigned<T>::type; 61 return (x == 0) ? BitSizeOf<T>() : CLZ(static_cast<unsigned_type>(x)); 62 } 63 64 template<typename T> 65 constexpr int CTZ(T x) { 66 static_assert(std::is_integral<T>::value, "T must be integral"); 67 // It is not unreasonable to ask for trailing zeros in a negative number. As such, do not check 68 // that T is an unsigned type. 69 static_assert(sizeof(T) <= sizeof(long long), // NOLINT [runtime/int] [4] 70 "T too large, must be smaller than long long"); 71 DCHECK_NE(x, static_cast<T>(0)); 72 return (sizeof(T) == sizeof(uint32_t)) ? __builtin_ctz(x) : __builtin_ctzll(x); 73 } 74 75 // Similar to CTZ except that on zero input it returns bitwidth and supports signed integers. 76 template<typename T> 77 constexpr int JAVASTYLE_CTZ(T x) { 78 static_assert(std::is_integral<T>::value, "T must be integral"); 79 using unsigned_type = typename std::make_unsigned<T>::type; 80 return (x == 0) ? BitSizeOf<T>() : CTZ(static_cast<unsigned_type>(x)); 81 } 82 83 // Return the number of 1-bits in `x`. 84 template<typename T> 85 constexpr int POPCOUNT(T x) { 86 return (sizeof(T) == sizeof(uint32_t)) ? __builtin_popcount(x) : __builtin_popcountll(x); 87 } 88 89 // Swap bytes. 90 template<typename T> 91 constexpr T BSWAP(T x) { 92 if (sizeof(T) == sizeof(uint16_t)) { 93 return __builtin_bswap16(x); 94 } else if (sizeof(T) == sizeof(uint32_t)) { 95 return __builtin_bswap32(x); 96 } else { 97 return __builtin_bswap64(x); 98 } 99 } 100 101 // Find the bit position of the most significant bit (0-based), or -1 if there were no bits set. 102 template <typename T> 103 constexpr ssize_t MostSignificantBit(T value) { 104 static_assert(std::is_integral<T>::value, "T must be integral"); 105 static_assert(std::is_unsigned<T>::value, "T must be unsigned"); 106 static_assert(std::numeric_limits<T>::radix == 2, "Unexpected radix!"); 107 return (value == 0) ? -1 : std::numeric_limits<T>::digits - 1 - CLZ(value); 108 } 109 110 // Find the bit position of the least significant bit (0-based), or -1 if there were no bits set. 111 template <typename T> 112 constexpr ssize_t LeastSignificantBit(T value) { 113 static_assert(std::is_integral<T>::value, "T must be integral"); 114 static_assert(std::is_unsigned<T>::value, "T must be unsigned"); 115 return (value == 0) ? -1 : CTZ(value); 116 } 117 118 // How many bits (minimally) does it take to store the constant 'value'? i.e. 1 for 1, 3 for 5, etc. 119 template <typename T> 120 constexpr size_t MinimumBitsToStore(T value) { 121 return static_cast<size_t>(MostSignificantBit(value) + 1); 122 } 123 124 template <typename T> 125 constexpr T RoundUpToPowerOfTwo(T x) { 126 static_assert(std::is_integral<T>::value, "T must be integral"); 127 static_assert(std::is_unsigned<T>::value, "T must be unsigned"); 128 // NOTE: Undefined if x > (1 << (std::numeric_limits<T>::digits - 1)). 129 return (x < 2u) ? x : static_cast<T>(1u) << (std::numeric_limits<T>::digits - CLZ(x - 1u)); 130 } 131 132 template<typename T> 133 constexpr bool IsPowerOfTwo(T x) { 134 static_assert(std::is_integral<T>::value, "T must be integral"); 135 // TODO: assert unsigned. There is currently many uses with signed values. 136 return (x & (x - 1)) == 0; 137 } 138 139 template<typename T> 140 constexpr int WhichPowerOf2(T x) { 141 static_assert(std::is_integral<T>::value, "T must be integral"); 142 // TODO: assert unsigned. There is currently many uses with signed values. 143 DCHECK((x != 0) && IsPowerOfTwo(x)); 144 return CTZ(x); 145 } 146 147 // For rounding integers. 148 // Note: Omit the `n` from T type deduction, deduce only from the `x` argument. 149 template<typename T> 150 constexpr T RoundDown(T x, typename Identity<T>::type n) WARN_UNUSED; 151 152 template<typename T> 153 constexpr T RoundDown(T x, typename Identity<T>::type n) { 154 DCHECK(IsPowerOfTwo(n)); 155 return (x & -n); 156 } 157 158 template<typename T> 159 constexpr T RoundUp(T x, typename std::remove_reference<T>::type n) WARN_UNUSED; 160 161 template<typename T> 162 constexpr T RoundUp(T x, typename std::remove_reference<T>::type n) { 163 return RoundDown(x + n - 1, n); 164 } 165 166 // For aligning pointers. 167 template<typename T> 168 inline T* AlignDown(T* x, uintptr_t n) WARN_UNUSED; 169 170 template<typename T> 171 inline T* AlignDown(T* x, uintptr_t n) { 172 return reinterpret_cast<T*>(RoundDown(reinterpret_cast<uintptr_t>(x), n)); 173 } 174 175 template<typename T> 176 inline T* AlignUp(T* x, uintptr_t n) WARN_UNUSED; 177 178 template<typename T> 179 inline T* AlignUp(T* x, uintptr_t n) { 180 return reinterpret_cast<T*>(RoundUp(reinterpret_cast<uintptr_t>(x), n)); 181 } 182 183 template<int n, typename T> 184 constexpr bool IsAligned(T x) { 185 static_assert((n & (n - 1)) == 0, "n is not a power of two"); 186 return (x & (n - 1)) == 0; 187 } 188 189 template<int n, typename T> 190 inline bool IsAligned(T* x) { 191 return IsAligned<n>(reinterpret_cast<const uintptr_t>(x)); 192 } 193 194 template<typename T> 195 inline bool IsAlignedParam(T x, int n) { 196 return (x & (n - 1)) == 0; 197 } 198 199 template<typename T> 200 inline bool IsAlignedParam(T* x, int n) { 201 return IsAlignedParam(reinterpret_cast<const uintptr_t>(x), n); 202 } 203 204 #define CHECK_ALIGNED(value, alignment) \ 205 CHECK(::art::IsAligned<alignment>(value)) << reinterpret_cast<const void*>(value) 206 207 #define DCHECK_ALIGNED(value, alignment) \ 208 DCHECK(::art::IsAligned<alignment>(value)) << reinterpret_cast<const void*>(value) 209 210 #define CHECK_ALIGNED_PARAM(value, alignment) \ 211 CHECK(::art::IsAlignedParam(value, alignment)) << reinterpret_cast<const void*>(value) 212 213 #define DCHECK_ALIGNED_PARAM(value, alignment) \ 214 DCHECK(::art::IsAlignedParam(value, alignment)) << reinterpret_cast<const void*>(value) 215 216 inline uint16_t Low16Bits(uint32_t value) { 217 return static_cast<uint16_t>(value); 218 } 219 220 inline uint16_t High16Bits(uint32_t value) { 221 return static_cast<uint16_t>(value >> 16); 222 } 223 224 inline uint32_t Low32Bits(uint64_t value) { 225 return static_cast<uint32_t>(value); 226 } 227 228 inline uint32_t High32Bits(uint64_t value) { 229 return static_cast<uint32_t>(value >> 32); 230 } 231 232 // Check whether an N-bit two's-complement representation can hold value. 233 template <typename T> 234 inline bool IsInt(size_t N, T value) { 235 if (N == BitSizeOf<T>()) { 236 return true; 237 } else { 238 CHECK_LT(0u, N); 239 CHECK_LT(N, BitSizeOf<T>()); 240 T limit = static_cast<T>(1) << (N - 1u); 241 return (-limit <= value) && (value < limit); 242 } 243 } 244 245 template <typename T> 246 constexpr T GetIntLimit(size_t bits) { 247 DCHECK_NE(bits, 0u); 248 DCHECK_LT(bits, BitSizeOf<T>()); 249 return static_cast<T>(1) << (bits - 1); 250 } 251 252 template <size_t kBits, typename T> 253 constexpr bool IsInt(T value) { 254 static_assert(kBits > 0, "kBits cannot be zero."); 255 static_assert(kBits <= BitSizeOf<T>(), "kBits must be <= max."); 256 static_assert(std::is_signed<T>::value, "Needs a signed type."); 257 // Corner case for "use all bits." Can't use the limits, as they would overflow, but it is 258 // trivially true. 259 return (kBits == BitSizeOf<T>()) ? 260 true : 261 (-GetIntLimit<T>(kBits) <= value) && (value < GetIntLimit<T>(kBits)); 262 } 263 264 template <size_t kBits, typename T> 265 constexpr bool IsUint(T value) { 266 static_assert(kBits > 0, "kBits cannot be zero."); 267 static_assert(kBits <= BitSizeOf<T>(), "kBits must be <= max."); 268 static_assert(std::is_integral<T>::value, "Needs an integral type."); 269 // Corner case for "use all bits." Can't use the limits, as they would overflow, but it is 270 // trivially true. 271 // NOTE: To avoid triggering assertion in GetIntLimit(kBits+1) if kBits+1==BitSizeOf<T>(), 272 // use GetIntLimit(kBits)*2u. The unsigned arithmetic works well for us if it overflows. 273 using unsigned_type = typename std::make_unsigned<T>::type; 274 return (0 <= value) && 275 (kBits == BitSizeOf<T>() || 276 (static_cast<unsigned_type>(value) <= GetIntLimit<unsigned_type>(kBits) * 2u - 1u)); 277 } 278 279 template <size_t kBits, typename T> 280 constexpr bool IsAbsoluteUint(T value) { 281 static_assert(kBits <= BitSizeOf<T>(), "kBits must be <= max."); 282 static_assert(std::is_integral<T>::value, "Needs an integral type."); 283 using unsigned_type = typename std::make_unsigned<T>::type; 284 return (kBits == BitSizeOf<T>()) 285 ? true 286 : IsUint<kBits>(value < 0 287 ? static_cast<unsigned_type>(-1 - value) + 1u // Avoid overflow. 288 : static_cast<unsigned_type>(value)); 289 } 290 291 // Generate maximum/minimum values for signed/unsigned n-bit integers 292 template <typename T> 293 constexpr T MaxInt(size_t bits) { 294 DCHECK(std::is_unsigned<T>::value || bits > 0u) << "bits cannot be zero for signed."; 295 DCHECK_LE(bits, BitSizeOf<T>()); 296 using unsigned_type = typename std::make_unsigned<T>::type; 297 return bits == BitSizeOf<T>() 298 ? std::numeric_limits<T>::max() 299 : std::is_signed<T>::value 300 ? ((bits == 1u) ? 0 : static_cast<T>(MaxInt<unsigned_type>(bits - 1))) 301 : static_cast<T>(UINT64_C(1) << bits) - static_cast<T>(1); 302 } 303 304 template <typename T> 305 constexpr T MinInt(size_t bits) { 306 DCHECK(std::is_unsigned<T>::value || bits > 0) << "bits cannot be zero for signed."; 307 DCHECK_LE(bits, BitSizeOf<T>()); 308 return bits == BitSizeOf<T>() 309 ? std::numeric_limits<T>::min() 310 : std::is_signed<T>::value 311 ? ((bits == 1u) ? -1 : static_cast<T>(-1) - MaxInt<T>(bits)) 312 : static_cast<T>(0); 313 } 314 315 // Using the Curiously Recurring Template Pattern to implement everything shared 316 // by LowToHighBitIterator and HighToLowBitIterator, i.e. everything but operator*(). 317 template <typename T, typename Iter> 318 class BitIteratorBase 319 : public std::iterator<std::forward_iterator_tag, uint32_t, ptrdiff_t, void, void> { 320 static_assert(std::is_integral<T>::value, "T must be integral"); 321 static_assert(std::is_unsigned<T>::value, "T must be unsigned"); 322 323 static_assert(sizeof(T) == sizeof(uint32_t) || sizeof(T) == sizeof(uint64_t), "Unsupported size"); 324 325 public: 326 BitIteratorBase() : bits_(0u) { } 327 explicit BitIteratorBase(T bits) : bits_(bits) { } 328 329 Iter& operator++() { 330 DCHECK_NE(bits_, 0u); 331 uint32_t bit = *static_cast<Iter&>(*this); 332 bits_ &= ~(static_cast<T>(1u) << bit); 333 return static_cast<Iter&>(*this); 334 } 335 336 Iter& operator++(int) { 337 Iter tmp(static_cast<Iter&>(*this)); 338 ++*this; 339 return tmp; 340 } 341 342 protected: 343 T bits_; 344 345 template <typename U, typename I> 346 friend bool operator==(const BitIteratorBase<U, I>& lhs, const BitIteratorBase<U, I>& rhs); 347 }; 348 349 template <typename T, typename Iter> 350 bool operator==(const BitIteratorBase<T, Iter>& lhs, const BitIteratorBase<T, Iter>& rhs) { 351 return lhs.bits_ == rhs.bits_; 352 } 353 354 template <typename T, typename Iter> 355 bool operator!=(const BitIteratorBase<T, Iter>& lhs, const BitIteratorBase<T, Iter>& rhs) { 356 return !(lhs == rhs); 357 } 358 359 template <typename T> 360 class LowToHighBitIterator : public BitIteratorBase<T, LowToHighBitIterator<T>> { 361 public: 362 using BitIteratorBase<T, LowToHighBitIterator<T>>::BitIteratorBase; 363 364 uint32_t operator*() const { 365 DCHECK_NE(this->bits_, 0u); 366 return CTZ(this->bits_); 367 } 368 }; 369 370 template <typename T> 371 class HighToLowBitIterator : public BitIteratorBase<T, HighToLowBitIterator<T>> { 372 public: 373 using BitIteratorBase<T, HighToLowBitIterator<T>>::BitIteratorBase; 374 375 uint32_t operator*() const { 376 DCHECK_NE(this->bits_, 0u); 377 static_assert(std::numeric_limits<T>::radix == 2, "Unexpected radix!"); 378 return std::numeric_limits<T>::digits - 1u - CLZ(this->bits_); 379 } 380 }; 381 382 template <typename T> 383 IterationRange<LowToHighBitIterator<T>> LowToHighBits(T bits) { 384 return IterationRange<LowToHighBitIterator<T>>( 385 LowToHighBitIterator<T>(bits), LowToHighBitIterator<T>()); 386 } 387 388 template <typename T> 389 IterationRange<HighToLowBitIterator<T>> HighToLowBits(T bits) { 390 return IterationRange<HighToLowBitIterator<T>>( 391 HighToLowBitIterator<T>(bits), HighToLowBitIterator<T>()); 392 } 393 394 // Returns value with bit set in lowest one-bit position or 0 if 0. (java.lang.X.lowestOneBit). 395 template <typename kind> 396 inline static kind LowestOneBitValue(kind opnd) { 397 // Hacker's Delight, Section 2-1 398 return opnd & -opnd; 399 } 400 401 // Returns value with bit set in hightest one-bit position or 0 if 0. (java.lang.X.highestOneBit). 402 template <typename T> 403 inline static T HighestOneBitValue(T opnd) { 404 using unsigned_type = typename std::make_unsigned<T>::type; 405 T res; 406 if (opnd == 0) { 407 res = 0; 408 } else { 409 int bit_position = BitSizeOf<T>() - (CLZ(static_cast<unsigned_type>(opnd)) + 1); 410 res = static_cast<T>(UINT64_C(1) << bit_position); 411 } 412 return res; 413 } 414 415 // Rotate bits. 416 template <typename T, bool left> 417 inline static T Rot(T opnd, int distance) { 418 int mask = BitSizeOf<T>() - 1; 419 int unsigned_right_shift = left ? (-distance & mask) : (distance & mask); 420 int signed_left_shift = left ? (distance & mask) : (-distance & mask); 421 using unsigned_type = typename std::make_unsigned<T>::type; 422 return (static_cast<unsigned_type>(opnd) >> unsigned_right_shift) | (opnd << signed_left_shift); 423 } 424 425 // TUNING: use rbit for arm/arm64 426 inline static uint32_t ReverseBits32(uint32_t opnd) { 427 // Hacker's Delight 7-1 428 opnd = ((opnd >> 1) & 0x55555555) | ((opnd & 0x55555555) << 1); 429 opnd = ((opnd >> 2) & 0x33333333) | ((opnd & 0x33333333) << 2); 430 opnd = ((opnd >> 4) & 0x0F0F0F0F) | ((opnd & 0x0F0F0F0F) << 4); 431 opnd = ((opnd >> 8) & 0x00FF00FF) | ((opnd & 0x00FF00FF) << 8); 432 opnd = ((opnd >> 16)) | ((opnd) << 16); 433 return opnd; 434 } 435 436 // TUNING: use rbit for arm/arm64 437 inline static uint64_t ReverseBits64(uint64_t opnd) { 438 // Hacker's Delight 7-1 439 opnd = (opnd & 0x5555555555555555L) << 1 | ((opnd >> 1) & 0x5555555555555555L); 440 opnd = (opnd & 0x3333333333333333L) << 2 | ((opnd >> 2) & 0x3333333333333333L); 441 opnd = (opnd & 0x0f0f0f0f0f0f0f0fL) << 4 | ((opnd >> 4) & 0x0f0f0f0f0f0f0f0fL); 442 opnd = (opnd & 0x00ff00ff00ff00ffL) << 8 | ((opnd >> 8) & 0x00ff00ff00ff00ffL); 443 opnd = (opnd << 48) | ((opnd & 0xffff0000L) << 16) | ((opnd >> 16) & 0xffff0000L) | (opnd >> 48); 444 return opnd; 445 } 446 447 } // namespace art 448 449 #endif // ART_RUNTIME_BASE_BIT_UTILS_H_ 450
