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 | |
Vladimir Marko | 80afd02 | 2015-05-19 18:08:00 +0100 | [diff] [blame] | 20 | #include <limits> |
| 21 | #include <type_traits> |
| 22 | |
Andreas Gampe | 5794381 | 2017-12-06 21:39:13 -0800 | [diff] [blame] | 23 | #include <android-base/logging.h> |
| 24 | |
Andreas Gampe | 5678db5 | 2017-06-08 14:11:18 -0700 | [diff] [blame] | 25 | #include "base/stl_util_identity.h" |
Vladimir Marko | 80afd02 | 2015-05-19 18:08:00 +0100 | [diff] [blame] | 26 | |
| 27 | namespace art { |
| 28 | |
buzbee | 31afbec | 2017-03-14 15:30:19 -0700 | [diff] [blame] | 29 | // Like sizeof, but count how many bits a type takes. Pass type explicitly. |
| 30 | template <typename T> |
| 31 | constexpr size_t BitSizeOf() { |
| 32 | static_assert(std::is_integral<T>::value, "T must be integral"); |
| 33 | using unsigned_type = typename std::make_unsigned<T>::type; |
| 34 | static_assert(sizeof(T) == sizeof(unsigned_type), "Unexpected type size mismatch!"); |
| 35 | static_assert(std::numeric_limits<unsigned_type>::radix == 2, "Unexpected radix!"); |
| 36 | return std::numeric_limits<unsigned_type>::digits; |
| 37 | } |
| 38 | |
| 39 | // Like sizeof, but count how many bits a type takes. Infers type from parameter. |
| 40 | template <typename T> |
| 41 | constexpr size_t BitSizeOf(T /*x*/) { |
| 42 | return BitSizeOf<T>(); |
| 43 | } |
| 44 | |
Vladimir Marko | 80afd02 | 2015-05-19 18:08:00 +0100 | [diff] [blame] | 45 | template<typename T> |
Vladimir Marko | f04cf54 | 2016-08-31 15:25:25 +0100 | [diff] [blame] | 46 | constexpr int CLZ(T x) { |
Vladimir Marko | 80afd02 | 2015-05-19 18:08:00 +0100 | [diff] [blame] | 47 | static_assert(std::is_integral<T>::value, "T must be integral"); |
Andreas Gampe | 151ab8d | 2015-08-14 23:01:49 +0000 | [diff] [blame] | 48 | static_assert(std::is_unsigned<T>::value, "T must be unsigned"); |
Vladimir Marko | dc682aa | 2018-01-04 18:42:57 +0000 | [diff] [blame] | 49 | static_assert(std::numeric_limits<T>::radix == 2, "Unexpected radix!"); |
| 50 | static_assert(sizeof(T) == sizeof(uint64_t) || sizeof(T) <= sizeof(uint32_t), |
| 51 | "Unsupported sizeof(T)"); |
Vladimir Marko | f04cf54 | 2016-08-31 15:25:25 +0100 | [diff] [blame] | 52 | DCHECK_NE(x, 0u); |
Vladimir Marko | dc682aa | 2018-01-04 18:42:57 +0000 | [diff] [blame] | 53 | constexpr bool is_64_bit = (sizeof(T) == sizeof(uint64_t)); |
| 54 | constexpr size_t adjustment = |
| 55 | is_64_bit ? 0u : std::numeric_limits<uint32_t>::digits - std::numeric_limits<T>::digits; |
| 56 | return is_64_bit ? __builtin_clzll(x) : __builtin_clz(x) - adjustment; |
Vladimir Marko | 80afd02 | 2015-05-19 18:08:00 +0100 | [diff] [blame] | 57 | } |
| 58 | |
buzbee | 31afbec | 2017-03-14 15:30:19 -0700 | [diff] [blame] | 59 | // Similar to CLZ except that on zero input it returns bitwidth and supports signed integers. |
| 60 | template<typename T> |
| 61 | constexpr int JAVASTYLE_CLZ(T x) { |
| 62 | static_assert(std::is_integral<T>::value, "T must be integral"); |
| 63 | using unsigned_type = typename std::make_unsigned<T>::type; |
| 64 | return (x == 0) ? BitSizeOf<T>() : CLZ(static_cast<unsigned_type>(x)); |
| 65 | } |
| 66 | |
Vladimir Marko | 80afd02 | 2015-05-19 18:08:00 +0100 | [diff] [blame] | 67 | template<typename T> |
Vladimir Marko | f04cf54 | 2016-08-31 15:25:25 +0100 | [diff] [blame] | 68 | constexpr int CTZ(T x) { |
Vladimir Marko | 80afd02 | 2015-05-19 18:08:00 +0100 | [diff] [blame] | 69 | static_assert(std::is_integral<T>::value, "T must be integral"); |
Andreas Gampe | 151ab8d | 2015-08-14 23:01:49 +0000 | [diff] [blame] | 70 | // It is not unreasonable to ask for trailing zeros in a negative number. As such, do not check |
| 71 | // that T is an unsigned type. |
Vladimir Marko | dc682aa | 2018-01-04 18:42:57 +0000 | [diff] [blame] | 72 | static_assert(sizeof(T) == sizeof(uint64_t) || sizeof(T) <= sizeof(uint32_t), |
| 73 | "Unsupported sizeof(T)"); |
Vladimir Marko | f04cf54 | 2016-08-31 15:25:25 +0100 | [diff] [blame] | 74 | DCHECK_NE(x, static_cast<T>(0)); |
Vladimir Marko | dc682aa | 2018-01-04 18:42:57 +0000 | [diff] [blame] | 75 | return (sizeof(T) == sizeof(uint64_t)) ? __builtin_ctzll(x) : __builtin_ctz(x); |
Vladimir Marko | 80afd02 | 2015-05-19 18:08:00 +0100 | [diff] [blame] | 76 | } |
| 77 | |
buzbee | 31afbec | 2017-03-14 15:30:19 -0700 | [diff] [blame] | 78 | // Similar to CTZ except that on zero input it returns bitwidth and supports signed integers. |
| 79 | template<typename T> |
| 80 | constexpr int JAVASTYLE_CTZ(T x) { |
| 81 | static_assert(std::is_integral<T>::value, "T must be integral"); |
| 82 | using unsigned_type = typename std::make_unsigned<T>::type; |
| 83 | return (x == 0) ? BitSizeOf<T>() : CTZ(static_cast<unsigned_type>(x)); |
| 84 | } |
| 85 | |
Roland Levillain | 0d5a281 | 2015-11-13 10:07:31 +0000 | [diff] [blame] | 86 | // Return the number of 1-bits in `x`. |
Vladimir Marko | 80afd02 | 2015-05-19 18:08:00 +0100 | [diff] [blame] | 87 | template<typename T> |
Vladimir Marko | f04cf54 | 2016-08-31 15:25:25 +0100 | [diff] [blame] | 88 | constexpr int POPCOUNT(T x) { |
| 89 | return (sizeof(T) == sizeof(uint32_t)) ? __builtin_popcount(x) : __builtin_popcountll(x); |
Vladimir Marko | 80afd02 | 2015-05-19 18:08:00 +0100 | [diff] [blame] | 90 | } |
| 91 | |
buzbee | 31afbec | 2017-03-14 15:30:19 -0700 | [diff] [blame] | 92 | // Swap bytes. |
| 93 | template<typename T> |
| 94 | constexpr T BSWAP(T x) { |
| 95 | if (sizeof(T) == sizeof(uint16_t)) { |
| 96 | return __builtin_bswap16(x); |
| 97 | } else if (sizeof(T) == sizeof(uint32_t)) { |
| 98 | return __builtin_bswap32(x); |
| 99 | } else { |
| 100 | return __builtin_bswap64(x); |
| 101 | } |
| 102 | } |
| 103 | |
Vladimir Marko | 80afd02 | 2015-05-19 18:08:00 +0100 | [diff] [blame] | 104 | // Find the bit position of the most significant bit (0-based), or -1 if there were no bits set. |
| 105 | template <typename T> |
Vladimir Marko | f04cf54 | 2016-08-31 15:25:25 +0100 | [diff] [blame] | 106 | constexpr ssize_t MostSignificantBit(T value) { |
Vladimir Marko | 80afd02 | 2015-05-19 18:08:00 +0100 | [diff] [blame] | 107 | static_assert(std::is_integral<T>::value, "T must be integral"); |
| 108 | static_assert(std::is_unsigned<T>::value, "T must be unsigned"); |
| 109 | static_assert(std::numeric_limits<T>::radix == 2, "Unexpected radix!"); |
| 110 | return (value == 0) ? -1 : std::numeric_limits<T>::digits - 1 - CLZ(value); |
| 111 | } |
| 112 | |
| 113 | // Find the bit position of the least significant bit (0-based), or -1 if there were no bits set. |
| 114 | template <typename T> |
Vladimir Marko | f04cf54 | 2016-08-31 15:25:25 +0100 | [diff] [blame] | 115 | constexpr ssize_t LeastSignificantBit(T value) { |
Vladimir Marko | 80afd02 | 2015-05-19 18:08:00 +0100 | [diff] [blame] | 116 | static_assert(std::is_integral<T>::value, "T must be integral"); |
| 117 | static_assert(std::is_unsigned<T>::value, "T must be unsigned"); |
| 118 | return (value == 0) ? -1 : CTZ(value); |
| 119 | } |
| 120 | |
| 121 | // How many bits (minimally) does it take to store the constant 'value'? i.e. 1 for 1, 3 for 5, etc. |
| 122 | template <typename T> |
Vladimir Marko | f04cf54 | 2016-08-31 15:25:25 +0100 | [diff] [blame] | 123 | constexpr size_t MinimumBitsToStore(T value) { |
Vladimir Marko | 80afd02 | 2015-05-19 18:08:00 +0100 | [diff] [blame] | 124 | return static_cast<size_t>(MostSignificantBit(value) + 1); |
| 125 | } |
| 126 | |
| 127 | template <typename T> |
Vladimir Marko | f04cf54 | 2016-08-31 15:25:25 +0100 | [diff] [blame] | 128 | constexpr T RoundUpToPowerOfTwo(T x) { |
Vladimir Marko | 80afd02 | 2015-05-19 18:08:00 +0100 | [diff] [blame] | 129 | static_assert(std::is_integral<T>::value, "T must be integral"); |
| 130 | static_assert(std::is_unsigned<T>::value, "T must be unsigned"); |
| 131 | // NOTE: Undefined if x > (1 << (std::numeric_limits<T>::digits - 1)). |
| 132 | return (x < 2u) ? x : static_cast<T>(1u) << (std::numeric_limits<T>::digits - CLZ(x - 1u)); |
| 133 | } |
| 134 | |
Artem Serov | f26bb6c | 2017-09-01 10:59:03 +0100 | [diff] [blame] | 135 | // Return highest possible N - a power of two - such that val >= N. |
| 136 | template <typename T> |
| 137 | constexpr T TruncToPowerOfTwo(T val) { |
| 138 | static_assert(std::is_integral<T>::value, "T must be integral"); |
| 139 | static_assert(std::is_unsigned<T>::value, "T must be unsigned"); |
| 140 | return (val != 0) ? static_cast<T>(1u) << (BitSizeOf<T>() - CLZ(val) - 1u) : 0; |
| 141 | } |
| 142 | |
Vladimir Marko | 80afd02 | 2015-05-19 18:08:00 +0100 | [diff] [blame] | 143 | template<typename T> |
Vladimir Marko | f04cf54 | 2016-08-31 15:25:25 +0100 | [diff] [blame] | 144 | constexpr bool IsPowerOfTwo(T x) { |
Vladimir Marko | 80afd02 | 2015-05-19 18:08:00 +0100 | [diff] [blame] | 145 | static_assert(std::is_integral<T>::value, "T must be integral"); |
| 146 | // TODO: assert unsigned. There is currently many uses with signed values. |
| 147 | return (x & (x - 1)) == 0; |
| 148 | } |
| 149 | |
| 150 | template<typename T> |
Vladimir Marko | f04cf54 | 2016-08-31 15:25:25 +0100 | [diff] [blame] | 151 | constexpr int WhichPowerOf2(T x) { |
Vladimir Marko | 80afd02 | 2015-05-19 18:08:00 +0100 | [diff] [blame] | 152 | static_assert(std::is_integral<T>::value, "T must be integral"); |
| 153 | // TODO: assert unsigned. There is currently many uses with signed values. |
| 154 | DCHECK((x != 0) && IsPowerOfTwo(x)); |
| 155 | return CTZ(x); |
| 156 | } |
| 157 | |
| 158 | // For rounding integers. |
Vladimir Marko | 88b2b80 | 2015-12-04 14:19:04 +0000 | [diff] [blame] | 159 | // Note: Omit the `n` from T type deduction, deduce only from the `x` argument. |
Vladimir Marko | 80afd02 | 2015-05-19 18:08:00 +0100 | [diff] [blame] | 160 | template<typename T> |
Vladimir Marko | f04cf54 | 2016-08-31 15:25:25 +0100 | [diff] [blame] | 161 | constexpr T RoundDown(T x, typename Identity<T>::type n) WARN_UNUSED; |
Vladimir Marko | 80afd02 | 2015-05-19 18:08:00 +0100 | [diff] [blame] | 162 | |
| 163 | template<typename T> |
Vladimir Marko | f04cf54 | 2016-08-31 15:25:25 +0100 | [diff] [blame] | 164 | constexpr T RoundDown(T x, typename Identity<T>::type n) { |
| 165 | DCHECK(IsPowerOfTwo(n)); |
| 166 | return (x & -n); |
Vladimir Marko | 80afd02 | 2015-05-19 18:08:00 +0100 | [diff] [blame] | 167 | } |
| 168 | |
| 169 | template<typename T> |
Vladimir Marko | f04cf54 | 2016-08-31 15:25:25 +0100 | [diff] [blame] | 170 | constexpr T RoundUp(T x, typename std::remove_reference<T>::type n) WARN_UNUSED; |
Vladimir Marko | 80afd02 | 2015-05-19 18:08:00 +0100 | [diff] [blame] | 171 | |
| 172 | template<typename T> |
Vladimir Marko | f04cf54 | 2016-08-31 15:25:25 +0100 | [diff] [blame] | 173 | constexpr T RoundUp(T x, typename std::remove_reference<T>::type n) { |
Vladimir Marko | 80afd02 | 2015-05-19 18:08:00 +0100 | [diff] [blame] | 174 | return RoundDown(x + n - 1, n); |
| 175 | } |
| 176 | |
| 177 | // For aligning pointers. |
| 178 | template<typename T> |
Vladimir Marko | f04cf54 | 2016-08-31 15:25:25 +0100 | [diff] [blame] | 179 | inline T* AlignDown(T* x, uintptr_t n) WARN_UNUSED; |
Vladimir Marko | 80afd02 | 2015-05-19 18:08:00 +0100 | [diff] [blame] | 180 | |
| 181 | template<typename T> |
Vladimir Marko | f04cf54 | 2016-08-31 15:25:25 +0100 | [diff] [blame] | 182 | inline T* AlignDown(T* x, uintptr_t n) { |
Vladimir Marko | 80afd02 | 2015-05-19 18:08:00 +0100 | [diff] [blame] | 183 | return reinterpret_cast<T*>(RoundDown(reinterpret_cast<uintptr_t>(x), n)); |
| 184 | } |
| 185 | |
| 186 | template<typename T> |
Vladimir Marko | f04cf54 | 2016-08-31 15:25:25 +0100 | [diff] [blame] | 187 | inline T* AlignUp(T* x, uintptr_t n) WARN_UNUSED; |
Vladimir Marko | 80afd02 | 2015-05-19 18:08:00 +0100 | [diff] [blame] | 188 | |
| 189 | template<typename T> |
Vladimir Marko | f04cf54 | 2016-08-31 15:25:25 +0100 | [diff] [blame] | 190 | inline T* AlignUp(T* x, uintptr_t n) { |
Vladimir Marko | 80afd02 | 2015-05-19 18:08:00 +0100 | [diff] [blame] | 191 | return reinterpret_cast<T*>(RoundUp(reinterpret_cast<uintptr_t>(x), n)); |
| 192 | } |
| 193 | |
| 194 | template<int n, typename T> |
Vladimir Marko | f04cf54 | 2016-08-31 15:25:25 +0100 | [diff] [blame] | 195 | constexpr bool IsAligned(T x) { |
Vladimir Marko | 80afd02 | 2015-05-19 18:08:00 +0100 | [diff] [blame] | 196 | static_assert((n & (n - 1)) == 0, "n is not a power of two"); |
| 197 | return (x & (n - 1)) == 0; |
| 198 | } |
| 199 | |
| 200 | template<int n, typename T> |
Vladimir Marko | f04cf54 | 2016-08-31 15:25:25 +0100 | [diff] [blame] | 201 | inline bool IsAligned(T* x) { |
Vladimir Marko | 80afd02 | 2015-05-19 18:08:00 +0100 | [diff] [blame] | 202 | return IsAligned<n>(reinterpret_cast<const uintptr_t>(x)); |
| 203 | } |
| 204 | |
| 205 | template<typename T> |
Vladimir Marko | f04cf54 | 2016-08-31 15:25:25 +0100 | [diff] [blame] | 206 | inline bool IsAlignedParam(T x, int n) { |
Vladimir Marko | 80afd02 | 2015-05-19 18:08:00 +0100 | [diff] [blame] | 207 | return (x & (n - 1)) == 0; |
| 208 | } |
| 209 | |
Hiroshi Yamauchi | 3c3c4a1 | 2017-02-21 16:49:59 -0800 | [diff] [blame] | 210 | template<typename T> |
| 211 | inline bool IsAlignedParam(T* x, int n) { |
| 212 | return IsAlignedParam(reinterpret_cast<const uintptr_t>(x), n); |
| 213 | } |
| 214 | |
Vladimir Marko | 80afd02 | 2015-05-19 18:08:00 +0100 | [diff] [blame] | 215 | #define CHECK_ALIGNED(value, alignment) \ |
| 216 | CHECK(::art::IsAligned<alignment>(value)) << reinterpret_cast<const void*>(value) |
| 217 | |
| 218 | #define DCHECK_ALIGNED(value, alignment) \ |
| 219 | DCHECK(::art::IsAligned<alignment>(value)) << reinterpret_cast<const void*>(value) |
| 220 | |
Vladimir Marko | cf36d49 | 2015-08-12 19:27:26 +0100 | [diff] [blame] | 221 | #define CHECK_ALIGNED_PARAM(value, alignment) \ |
| 222 | CHECK(::art::IsAlignedParam(value, alignment)) << reinterpret_cast<const void*>(value) |
| 223 | |
Vladimir Marko | 80afd02 | 2015-05-19 18:08:00 +0100 | [diff] [blame] | 224 | #define DCHECK_ALIGNED_PARAM(value, alignment) \ |
| 225 | DCHECK(::art::IsAlignedParam(value, alignment)) << reinterpret_cast<const void*>(value) |
| 226 | |
Vladimir Marko | f04cf54 | 2016-08-31 15:25:25 +0100 | [diff] [blame] | 227 | inline uint16_t Low16Bits(uint32_t value) { |
Vladimir Marko | 80afd02 | 2015-05-19 18:08:00 +0100 | [diff] [blame] | 228 | return static_cast<uint16_t>(value); |
| 229 | } |
| 230 | |
Vladimir Marko | f04cf54 | 2016-08-31 15:25:25 +0100 | [diff] [blame] | 231 | inline uint16_t High16Bits(uint32_t value) { |
Vladimir Marko | 80afd02 | 2015-05-19 18:08:00 +0100 | [diff] [blame] | 232 | return static_cast<uint16_t>(value >> 16); |
| 233 | } |
| 234 | |
Vladimir Marko | f04cf54 | 2016-08-31 15:25:25 +0100 | [diff] [blame] | 235 | inline uint32_t Low32Bits(uint64_t value) { |
Vladimir Marko | 80afd02 | 2015-05-19 18:08:00 +0100 | [diff] [blame] | 236 | return static_cast<uint32_t>(value); |
| 237 | } |
| 238 | |
Vladimir Marko | f04cf54 | 2016-08-31 15:25:25 +0100 | [diff] [blame] | 239 | inline uint32_t High32Bits(uint64_t value) { |
Vladimir Marko | 80afd02 | 2015-05-19 18:08:00 +0100 | [diff] [blame] | 240 | return static_cast<uint32_t>(value >> 32); |
| 241 | } |
| 242 | |
| 243 | // Check whether an N-bit two's-complement representation can hold value. |
| 244 | template <typename T> |
Vladimir Marko | f04cf54 | 2016-08-31 15:25:25 +0100 | [diff] [blame] | 245 | inline bool IsInt(size_t N, T value) { |
Vladimir Marko | 80afd02 | 2015-05-19 18:08:00 +0100 | [diff] [blame] | 246 | if (N == BitSizeOf<T>()) { |
| 247 | return true; |
| 248 | } else { |
| 249 | CHECK_LT(0u, N); |
| 250 | CHECK_LT(N, BitSizeOf<T>()); |
| 251 | T limit = static_cast<T>(1) << (N - 1u); |
| 252 | return (-limit <= value) && (value < limit); |
| 253 | } |
| 254 | } |
| 255 | |
| 256 | template <typename T> |
Vladimir Marko | f04cf54 | 2016-08-31 15:25:25 +0100 | [diff] [blame] | 257 | constexpr T GetIntLimit(size_t bits) { |
| 258 | DCHECK_NE(bits, 0u); |
| 259 | DCHECK_LT(bits, BitSizeOf<T>()); |
| 260 | return static_cast<T>(1) << (bits - 1); |
Vladimir Marko | 80afd02 | 2015-05-19 18:08:00 +0100 | [diff] [blame] | 261 | } |
| 262 | |
| 263 | template <size_t kBits, typename T> |
Vladimir Marko | f04cf54 | 2016-08-31 15:25:25 +0100 | [diff] [blame] | 264 | constexpr bool IsInt(T value) { |
Vladimir Marko | 80afd02 | 2015-05-19 18:08:00 +0100 | [diff] [blame] | 265 | static_assert(kBits > 0, "kBits cannot be zero."); |
| 266 | static_assert(kBits <= BitSizeOf<T>(), "kBits must be <= max."); |
| 267 | static_assert(std::is_signed<T>::value, "Needs a signed type."); |
| 268 | // Corner case for "use all bits." Can't use the limits, as they would overflow, but it is |
| 269 | // trivially true. |
| 270 | return (kBits == BitSizeOf<T>()) ? |
| 271 | true : |
| 272 | (-GetIntLimit<T>(kBits) <= value) && (value < GetIntLimit<T>(kBits)); |
| 273 | } |
| 274 | |
| 275 | template <size_t kBits, typename T> |
Vladimir Marko | f04cf54 | 2016-08-31 15:25:25 +0100 | [diff] [blame] | 276 | constexpr bool IsUint(T value) { |
Vladimir Marko | 80afd02 | 2015-05-19 18:08:00 +0100 | [diff] [blame] | 277 | static_assert(kBits > 0, "kBits cannot be zero."); |
| 278 | static_assert(kBits <= BitSizeOf<T>(), "kBits must be <= max."); |
| 279 | static_assert(std::is_integral<T>::value, "Needs an integral type."); |
| 280 | // Corner case for "use all bits." Can't use the limits, as they would overflow, but it is |
| 281 | // trivially true. |
| 282 | // NOTE: To avoid triggering assertion in GetIntLimit(kBits+1) if kBits+1==BitSizeOf<T>(), |
| 283 | // use GetIntLimit(kBits)*2u. The unsigned arithmetic works well for us if it overflows. |
Vladimir Marko | f04cf54 | 2016-08-31 15:25:25 +0100 | [diff] [blame] | 284 | using unsigned_type = typename std::make_unsigned<T>::type; |
Vladimir Marko | 80afd02 | 2015-05-19 18:08:00 +0100 | [diff] [blame] | 285 | return (0 <= value) && |
| 286 | (kBits == BitSizeOf<T>() || |
Vladimir Marko | f04cf54 | 2016-08-31 15:25:25 +0100 | [diff] [blame] | 287 | (static_cast<unsigned_type>(value) <= GetIntLimit<unsigned_type>(kBits) * 2u - 1u)); |
Vladimir Marko | 80afd02 | 2015-05-19 18:08:00 +0100 | [diff] [blame] | 288 | } |
| 289 | |
| 290 | template <size_t kBits, typename T> |
Vladimir Marko | f04cf54 | 2016-08-31 15:25:25 +0100 | [diff] [blame] | 291 | constexpr bool IsAbsoluteUint(T value) { |
Vladimir Marko | 80afd02 | 2015-05-19 18:08:00 +0100 | [diff] [blame] | 292 | static_assert(kBits <= BitSizeOf<T>(), "kBits must be <= max."); |
| 293 | static_assert(std::is_integral<T>::value, "Needs an integral type."); |
Vladimir Marko | f04cf54 | 2016-08-31 15:25:25 +0100 | [diff] [blame] | 294 | using unsigned_type = typename std::make_unsigned<T>::type; |
Vladimir Marko | 80afd02 | 2015-05-19 18:08:00 +0100 | [diff] [blame] | 295 | return (kBits == BitSizeOf<T>()) |
| 296 | ? true |
| 297 | : IsUint<kBits>(value < 0 |
| 298 | ? static_cast<unsigned_type>(-1 - value) + 1u // Avoid overflow. |
| 299 | : static_cast<unsigned_type>(value)); |
| 300 | } |
| 301 | |
Chris Larsen | dbce0d7 | 2015-09-17 13:34:00 -0700 | [diff] [blame] | 302 | // Generate maximum/minimum values for signed/unsigned n-bit integers |
| 303 | template <typename T> |
Vladimir Marko | f04cf54 | 2016-08-31 15:25:25 +0100 | [diff] [blame] | 304 | constexpr T MaxInt(size_t bits) { |
| 305 | DCHECK(std::is_unsigned<T>::value || bits > 0u) << "bits cannot be zero for signed."; |
| 306 | DCHECK_LE(bits, BitSizeOf<T>()); |
| 307 | using unsigned_type = typename std::make_unsigned<T>::type; |
| 308 | return bits == BitSizeOf<T>() |
| 309 | ? std::numeric_limits<T>::max() |
| 310 | : std::is_signed<T>::value |
| 311 | ? ((bits == 1u) ? 0 : static_cast<T>(MaxInt<unsigned_type>(bits - 1))) |
| 312 | : static_cast<T>(UINT64_C(1) << bits) - static_cast<T>(1); |
Chris Larsen | dbce0d7 | 2015-09-17 13:34:00 -0700 | [diff] [blame] | 313 | } |
| 314 | |
| 315 | template <typename T> |
Vladimir Marko | f04cf54 | 2016-08-31 15:25:25 +0100 | [diff] [blame] | 316 | constexpr T MinInt(size_t bits) { |
| 317 | DCHECK(std::is_unsigned<T>::value || bits > 0) << "bits cannot be zero for signed."; |
| 318 | DCHECK_LE(bits, BitSizeOf<T>()); |
| 319 | return bits == BitSizeOf<T>() |
| 320 | ? std::numeric_limits<T>::min() |
| 321 | : std::is_signed<T>::value |
| 322 | ? ((bits == 1u) ? -1 : static_cast<T>(-1) - MaxInt<T>(bits)) |
| 323 | : static_cast<T>(0); |
Chris Larsen | dbce0d7 | 2015-09-17 13:34:00 -0700 | [diff] [blame] | 324 | } |
| 325 | |
buzbee | 31afbec | 2017-03-14 15:30:19 -0700 | [diff] [blame] | 326 | // Returns value with bit set in lowest one-bit position or 0 if 0. (java.lang.X.lowestOneBit). |
| 327 | template <typename kind> |
| 328 | inline static kind LowestOneBitValue(kind opnd) { |
| 329 | // Hacker's Delight, Section 2-1 |
| 330 | return opnd & -opnd; |
| 331 | } |
| 332 | |
| 333 | // Returns value with bit set in hightest one-bit position or 0 if 0. (java.lang.X.highestOneBit). |
| 334 | template <typename T> |
| 335 | inline static T HighestOneBitValue(T opnd) { |
| 336 | using unsigned_type = typename std::make_unsigned<T>::type; |
| 337 | T res; |
| 338 | if (opnd == 0) { |
| 339 | res = 0; |
| 340 | } else { |
| 341 | int bit_position = BitSizeOf<T>() - (CLZ(static_cast<unsigned_type>(opnd)) + 1); |
| 342 | res = static_cast<T>(UINT64_C(1) << bit_position); |
| 343 | } |
| 344 | return res; |
| 345 | } |
| 346 | |
| 347 | // Rotate bits. |
| 348 | template <typename T, bool left> |
| 349 | inline static T Rot(T opnd, int distance) { |
| 350 | int mask = BitSizeOf<T>() - 1; |
| 351 | int unsigned_right_shift = left ? (-distance & mask) : (distance & mask); |
| 352 | int signed_left_shift = left ? (distance & mask) : (-distance & mask); |
| 353 | using unsigned_type = typename std::make_unsigned<T>::type; |
| 354 | return (static_cast<unsigned_type>(opnd) >> unsigned_right_shift) | (opnd << signed_left_shift); |
| 355 | } |
| 356 | |
| 357 | // TUNING: use rbit for arm/arm64 |
| 358 | inline static uint32_t ReverseBits32(uint32_t opnd) { |
| 359 | // Hacker's Delight 7-1 |
| 360 | opnd = ((opnd >> 1) & 0x55555555) | ((opnd & 0x55555555) << 1); |
| 361 | opnd = ((opnd >> 2) & 0x33333333) | ((opnd & 0x33333333) << 2); |
| 362 | opnd = ((opnd >> 4) & 0x0F0F0F0F) | ((opnd & 0x0F0F0F0F) << 4); |
| 363 | opnd = ((opnd >> 8) & 0x00FF00FF) | ((opnd & 0x00FF00FF) << 8); |
| 364 | opnd = ((opnd >> 16)) | ((opnd) << 16); |
| 365 | return opnd; |
| 366 | } |
| 367 | |
| 368 | // TUNING: use rbit for arm/arm64 |
| 369 | inline static uint64_t ReverseBits64(uint64_t opnd) { |
| 370 | // Hacker's Delight 7-1 |
| 371 | opnd = (opnd & 0x5555555555555555L) << 1 | ((opnd >> 1) & 0x5555555555555555L); |
| 372 | opnd = (opnd & 0x3333333333333333L) << 2 | ((opnd >> 2) & 0x3333333333333333L); |
| 373 | opnd = (opnd & 0x0f0f0f0f0f0f0f0fL) << 4 | ((opnd >> 4) & 0x0f0f0f0f0f0f0f0fL); |
| 374 | opnd = (opnd & 0x00ff00ff00ff00ffL) << 8 | ((opnd >> 8) & 0x00ff00ff00ff00ffL); |
| 375 | opnd = (opnd << 48) | ((opnd & 0xffff0000L) << 16) | ((opnd >> 16) & 0xffff0000L) | (opnd >> 48); |
| 376 | return opnd; |
| 377 | } |
| 378 | |
Igor Murashkin | 1e77d27 | 2017-10-07 14:09:43 +0000 | [diff] [blame] | 379 | // Create a mask for the least significant "bits" |
| 380 | // The returned value is always unsigned to prevent undefined behavior for bitwise ops. |
| 381 | // |
| 382 | // Given 'bits', |
| 383 | // Returns: |
| 384 | // <--- bits ---> |
| 385 | // +-----------------+------------+ |
| 386 | // | 0 ............0 | 1.....1 | |
| 387 | // +-----------------+------------+ |
| 388 | // msb lsb |
| 389 | template <typename T = size_t> |
| 390 | inline static constexpr std::make_unsigned_t<T> MaskLeastSignificant(size_t bits) { |
| 391 | DCHECK_GE(BitSizeOf<T>(), bits) << "Bits out of range for type T"; |
| 392 | using unsigned_T = std::make_unsigned_t<T>; |
| 393 | if (bits >= BitSizeOf<T>()) { |
| 394 | return std::numeric_limits<unsigned_T>::max(); |
| 395 | } else { |
Igor Murashkin | 2f36629 | 2017-10-09 13:37:50 -0700 | [diff] [blame] | 396 | auto kOne = static_cast<unsigned_T>(1); // Do not truncate for T>size_t. |
| 397 | return static_cast<unsigned_T>((kOne << bits) - kOne); |
Igor Murashkin | 1e77d27 | 2017-10-07 14:09:43 +0000 | [diff] [blame] | 398 | } |
| 399 | } |
| 400 | |
| 401 | // Clears the bitfield starting at the least significant bit "lsb" with a bitwidth of 'width'. |
| 402 | // (Equivalent of ARM BFC instruction). |
| 403 | // |
| 404 | // Given: |
| 405 | // <-- width --> |
| 406 | // +--------+------------+--------+ |
| 407 | // | ABC... | bitfield | XYZ... + |
| 408 | // +--------+------------+--------+ |
| 409 | // lsb 0 |
| 410 | // Returns: |
| 411 | // <-- width --> |
| 412 | // +--------+------------+--------+ |
| 413 | // | ABC... | 0........0 | XYZ... + |
| 414 | // +--------+------------+--------+ |
| 415 | // lsb 0 |
| 416 | template <typename T> |
| 417 | inline static constexpr T BitFieldClear(T value, size_t lsb, size_t width) { |
| 418 | DCHECK_GE(BitSizeOf(value), lsb + width) << "Bit field out of range for value"; |
| 419 | const auto val = static_cast<std::make_unsigned_t<T>>(value); |
| 420 | const auto mask = MaskLeastSignificant<T>(width); |
| 421 | |
| 422 | return static_cast<T>(val & ~(mask << lsb)); |
| 423 | } |
| 424 | |
| 425 | // Inserts the contents of 'data' into bitfield of 'value' starting |
| 426 | // at the least significant bit "lsb" with a bitwidth of 'width'. |
| 427 | // Note: data must be within range of [MinInt(width), MaxInt(width)]. |
| 428 | // (Equivalent of ARM BFI instruction). |
| 429 | // |
| 430 | // Given (data): |
| 431 | // <-- width --> |
| 432 | // +--------+------------+--------+ |
| 433 | // | ABC... | bitfield | XYZ... + |
| 434 | // +--------+------------+--------+ |
| 435 | // lsb 0 |
| 436 | // Returns: |
| 437 | // <-- width --> |
| 438 | // +--------+------------+--------+ |
| 439 | // | ABC... | 0...data | XYZ... + |
| 440 | // +--------+------------+--------+ |
| 441 | // lsb 0 |
| 442 | |
| 443 | template <typename T, typename T2> |
| 444 | inline static constexpr T BitFieldInsert(T value, T2 data, size_t lsb, size_t width) { |
| 445 | DCHECK_GE(BitSizeOf(value), lsb + width) << "Bit field out of range for value"; |
| 446 | if (width != 0u) { |
| 447 | DCHECK_GE(MaxInt<T2>(width), data) << "Data out of range [too large] for bitwidth"; |
| 448 | DCHECK_LE(MinInt<T2>(width), data) << "Data out of range [too small] for bitwidth"; |
| 449 | } else { |
| 450 | DCHECK_EQ(static_cast<T2>(0), data) << "Data out of range [nonzero] for bitwidth 0"; |
| 451 | } |
| 452 | const auto data_mask = MaskLeastSignificant<T2>(width); |
| 453 | const auto value_cleared = BitFieldClear(value, lsb, width); |
| 454 | |
| 455 | return static_cast<T>(value_cleared | ((data & data_mask) << lsb)); |
| 456 | } |
| 457 | |
| 458 | // Extracts the bitfield starting at the least significant bit "lsb" with a bitwidth of 'width'. |
| 459 | // Signed types are sign-extended during extraction. (Equivalent of ARM UBFX/SBFX instruction). |
| 460 | // |
| 461 | // Given: |
| 462 | // <-- width --> |
| 463 | // +--------+-------------+-------+ |
| 464 | // | | bitfield | + |
| 465 | // +--------+-------------+-------+ |
| 466 | // lsb 0 |
| 467 | // (Unsigned) Returns: |
| 468 | // <-- width --> |
| 469 | // +----------------+-------------+ |
| 470 | // | 0... 0 | bitfield | |
| 471 | // +----------------+-------------+ |
| 472 | // 0 |
| 473 | // (Signed) Returns: |
| 474 | // <-- width --> |
| 475 | // +----------------+-------------+ |
| 476 | // | S... S | bitfield | |
| 477 | // +----------------+-------------+ |
| 478 | // 0 |
| 479 | // where S is the highest bit in 'bitfield'. |
| 480 | template <typename T> |
| 481 | inline static constexpr T BitFieldExtract(T value, size_t lsb, size_t width) { |
| 482 | DCHECK_GE(BitSizeOf(value), lsb + width) << "Bit field out of range for value"; |
| 483 | const auto val = static_cast<std::make_unsigned_t<T>>(value); |
| 484 | |
| 485 | const T bitfield_unsigned = |
| 486 | static_cast<T>((val >> lsb) & MaskLeastSignificant<T>(width)); |
| 487 | if (std::is_signed<T>::value) { |
| 488 | // Perform sign extension |
| 489 | if (width == 0) { // Avoid underflow. |
| 490 | return static_cast<T>(0); |
| 491 | } else if (bitfield_unsigned & (1 << (width - 1))) { // Detect if sign bit was set. |
| 492 | // MSB <width> LSB |
| 493 | // 0b11111...100...000000 |
| 494 | const auto ones_negmask = ~MaskLeastSignificant<T>(width); |
| 495 | return static_cast<T>(bitfield_unsigned | ones_negmask); |
| 496 | } |
| 497 | } |
| 498 | // Skip sign extension. |
| 499 | return bitfield_unsigned; |
| 500 | } |
| 501 | |
Vladimir Marko | 80afd02 | 2015-05-19 18:08:00 +0100 | [diff] [blame] | 502 | } // namespace art |
| 503 | |
| 504 | #endif // ART_RUNTIME_BASE_BIT_UTILS_H_ |