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