180afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko/* 280afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko * Copyright (C) 2015 The Android Open Source Project 380afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko * 480afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko * Licensed under the Apache License, Version 2.0 (the "License"); 580afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko * you may not use this file except in compliance with the License. 680afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko * You may obtain a copy of the License at 780afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko * 880afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko * http://www.apache.org/licenses/LICENSE-2.0 980afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko * 1080afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko * Unless required by applicable law or agreed to in writing, software 1180afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko * distributed under the License is distributed on an "AS IS" BASIS, 1280afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 1380afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko * See the License for the specific language governing permissions and 1480afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko * limitations under the License. 1580afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko */ 1680afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko 1780afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko#ifndef ART_RUNTIME_BASE_BIT_UTILS_H_ 1880afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko#define ART_RUNTIME_BASE_BIT_UTILS_H_ 1980afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko 2080afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko#include <iterator> 2180afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko#include <limits> 2280afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko#include <type_traits> 2380afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko 2480afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko#include "base/logging.h" 2580afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko#include "base/iteration_range.h" 2688b2b80aed15bb1f931cddd40e44ca525ef10018Vladimir Marko#include "base/stl_util.h" 2780afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko 2880afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Markonamespace art { 2980afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko 3080afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Markotemplate<typename T> 3180afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Markostatic constexpr int CLZ(T x) { 3280afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko static_assert(std::is_integral<T>::value, "T must be integral"); 33151ab8d096be02b04391fd32460a31ee60ae2b0aAndreas Gampe static_assert(std::is_unsigned<T>::value, "T must be unsigned"); 3480afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko static_assert(sizeof(T) <= sizeof(long long), // NOLINT [runtime/int] [4] 3580afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko "T too large, must be smaller than long long"); 36151ab8d096be02b04391fd32460a31ee60ae2b0aAndreas Gampe return 37151ab8d096be02b04391fd32460a31ee60ae2b0aAndreas Gampe DCHECK_CONSTEXPR(x != 0, "x must not be zero", T(0)) 38151ab8d096be02b04391fd32460a31ee60ae2b0aAndreas Gampe (sizeof(T) == sizeof(uint32_t)) 39151ab8d096be02b04391fd32460a31ee60ae2b0aAndreas Gampe ? __builtin_clz(x) 40151ab8d096be02b04391fd32460a31ee60ae2b0aAndreas Gampe : __builtin_clzll(x); 4180afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko} 4280afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko 4380afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Markotemplate<typename T> 4480afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Markostatic constexpr int CTZ(T x) { 4580afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko static_assert(std::is_integral<T>::value, "T must be integral"); 46151ab8d096be02b04391fd32460a31ee60ae2b0aAndreas Gampe // It is not unreasonable to ask for trailing zeros in a negative number. As such, do not check 47151ab8d096be02b04391fd32460a31ee60ae2b0aAndreas Gampe // that T is an unsigned type. 48151ab8d096be02b04391fd32460a31ee60ae2b0aAndreas Gampe static_assert(sizeof(T) <= sizeof(long long), // NOLINT [runtime/int] [4] 49151ab8d096be02b04391fd32460a31ee60ae2b0aAndreas Gampe "T too large, must be smaller than long long"); 50151ab8d096be02b04391fd32460a31ee60ae2b0aAndreas Gampe return 51151ab8d096be02b04391fd32460a31ee60ae2b0aAndreas Gampe DCHECK_CONSTEXPR(x != 0, "x must not be zero", T(0)) 52151ab8d096be02b04391fd32460a31ee60ae2b0aAndreas Gampe (sizeof(T) == sizeof(uint32_t)) 53151ab8d096be02b04391fd32460a31ee60ae2b0aAndreas Gampe ? __builtin_ctz(x) 54151ab8d096be02b04391fd32460a31ee60ae2b0aAndreas Gampe : __builtin_ctzll(x); 5580afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko} 5680afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko 570d5a281c671444bfa75d63caf1427a8c0e6e1177Roland Levillain// Return the number of 1-bits in `x`. 5880afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Markotemplate<typename T> 5980afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Markostatic constexpr int POPCOUNT(T x) { 6080afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko return (sizeof(T) == sizeof(uint32_t)) 6180afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko ? __builtin_popcount(x) 6280afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko : __builtin_popcountll(x); 6380afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko} 6480afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko 6580afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko// Find the bit position of the most significant bit (0-based), or -1 if there were no bits set. 6680afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Markotemplate <typename T> 6780afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Markostatic constexpr ssize_t MostSignificantBit(T value) { 6880afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko static_assert(std::is_integral<T>::value, "T must be integral"); 6980afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko static_assert(std::is_unsigned<T>::value, "T must be unsigned"); 7080afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko static_assert(std::numeric_limits<T>::radix == 2, "Unexpected radix!"); 7180afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko return (value == 0) ? -1 : std::numeric_limits<T>::digits - 1 - CLZ(value); 7280afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko} 7380afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko 7480afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko// Find the bit position of the least significant bit (0-based), or -1 if there were no bits set. 7580afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Markotemplate <typename T> 7680afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Markostatic constexpr ssize_t LeastSignificantBit(T value) { 7780afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko static_assert(std::is_integral<T>::value, "T must be integral"); 7880afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko static_assert(std::is_unsigned<T>::value, "T must be unsigned"); 7980afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko return (value == 0) ? -1 : CTZ(value); 8080afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko} 8180afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko 8280afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko// How many bits (minimally) does it take to store the constant 'value'? i.e. 1 for 1, 3 for 5, etc. 8380afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Markotemplate <typename T> 8480afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Markostatic constexpr size_t MinimumBitsToStore(T value) { 8580afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko return static_cast<size_t>(MostSignificantBit(value) + 1); 8680afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko} 8780afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko 8880afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Markotemplate <typename T> 8980afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Markostatic constexpr inline T RoundUpToPowerOfTwo(T x) { 9080afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko static_assert(std::is_integral<T>::value, "T must be integral"); 9180afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko static_assert(std::is_unsigned<T>::value, "T must be unsigned"); 9280afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko // NOTE: Undefined if x > (1 << (std::numeric_limits<T>::digits - 1)). 9380afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko return (x < 2u) ? x : static_cast<T>(1u) << (std::numeric_limits<T>::digits - CLZ(x - 1u)); 9480afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko} 9580afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko 9680afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Markotemplate<typename T> 9780afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Markostatic constexpr bool IsPowerOfTwo(T x) { 9880afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko static_assert(std::is_integral<T>::value, "T must be integral"); 9980afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko // TODO: assert unsigned. There is currently many uses with signed values. 10080afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko return (x & (x - 1)) == 0; 10180afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko} 10280afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko 10380afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Markotemplate<typename T> 10480afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Markostatic inline int WhichPowerOf2(T x) { 10580afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko static_assert(std::is_integral<T>::value, "T must be integral"); 10680afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko // TODO: assert unsigned. There is currently many uses with signed values. 10780afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko DCHECK((x != 0) && IsPowerOfTwo(x)); 10880afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko return CTZ(x); 10980afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko} 11080afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko 11180afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko// For rounding integers. 11288b2b80aed15bb1f931cddd40e44ca525ef10018Vladimir Marko// Note: Omit the `n` from T type deduction, deduce only from the `x` argument. 11380afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Markotemplate<typename T> 11488b2b80aed15bb1f931cddd40e44ca525ef10018Vladimir Markostatic constexpr T RoundDown(T x, typename Identity<T>::type n) WARN_UNUSED; 11580afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko 11680afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Markotemplate<typename T> 11788b2b80aed15bb1f931cddd40e44ca525ef10018Vladimir Markostatic constexpr T RoundDown(T x, typename Identity<T>::type n) { 11880afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko return 11980afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko DCHECK_CONSTEXPR(IsPowerOfTwo(n), , T(0)) 12080afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko (x & -n); 12180afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko} 12280afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko 12380afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Markotemplate<typename T> 12480afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Markostatic constexpr T RoundUp(T x, typename std::remove_reference<T>::type n) WARN_UNUSED; 12580afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko 12680afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Markotemplate<typename T> 12780afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Markostatic constexpr T RoundUp(T x, typename std::remove_reference<T>::type n) { 12880afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko return RoundDown(x + n - 1, n); 12980afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko} 13080afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko 13180afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko// For aligning pointers. 13280afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Markotemplate<typename T> 13380afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Markostatic inline T* AlignDown(T* x, uintptr_t n) WARN_UNUSED; 13480afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko 13580afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Markotemplate<typename T> 13680afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Markostatic inline T* AlignDown(T* x, uintptr_t n) { 13780afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko return reinterpret_cast<T*>(RoundDown(reinterpret_cast<uintptr_t>(x), n)); 13880afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko} 13980afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko 14080afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Markotemplate<typename T> 14180afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Markostatic inline T* AlignUp(T* x, uintptr_t n) WARN_UNUSED; 14280afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko 14380afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Markotemplate<typename T> 14480afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Markostatic inline T* AlignUp(T* x, uintptr_t n) { 14580afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko return reinterpret_cast<T*>(RoundUp(reinterpret_cast<uintptr_t>(x), n)); 14680afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko} 14780afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko 14880afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Markotemplate<int n, typename T> 1497bf2b4f1d08050f80782217febac55c8cfc5e4efNicolas Geoffraystatic constexpr bool IsAligned(T x) { 15080afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko static_assert((n & (n - 1)) == 0, "n is not a power of two"); 15180afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko return (x & (n - 1)) == 0; 15280afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko} 15380afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko 15480afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Markotemplate<int n, typename T> 15580afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Markostatic inline bool IsAligned(T* x) { 15680afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko return IsAligned<n>(reinterpret_cast<const uintptr_t>(x)); 15780afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko} 15880afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko 15980afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Markotemplate<typename T> 16080afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Markostatic inline bool IsAlignedParam(T x, int n) { 16180afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko return (x & (n - 1)) == 0; 16280afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko} 16380afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko 16480afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko#define CHECK_ALIGNED(value, alignment) \ 16580afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko CHECK(::art::IsAligned<alignment>(value)) << reinterpret_cast<const void*>(value) 16680afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko 16780afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko#define DCHECK_ALIGNED(value, alignment) \ 16880afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko DCHECK(::art::IsAligned<alignment>(value)) << reinterpret_cast<const void*>(value) 16980afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko 170cf36d493124d8048efa0bd6f67d817ce3cd6b725Vladimir Marko#define CHECK_ALIGNED_PARAM(value, alignment) \ 171cf36d493124d8048efa0bd6f67d817ce3cd6b725Vladimir Marko CHECK(::art::IsAlignedParam(value, alignment)) << reinterpret_cast<const void*>(value) 172cf36d493124d8048efa0bd6f67d817ce3cd6b725Vladimir Marko 17380afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko#define DCHECK_ALIGNED_PARAM(value, alignment) \ 17480afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko DCHECK(::art::IsAlignedParam(value, alignment)) << reinterpret_cast<const void*>(value) 17580afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko 17680afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko// Like sizeof, but count how many bits a type takes. Pass type explicitly. 17780afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Markotemplate <typename T> 17880afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Markostatic constexpr size_t BitSizeOf() { 17980afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko static_assert(std::is_integral<T>::value, "T must be integral"); 18080afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko typedef typename std::make_unsigned<T>::type unsigned_type; 18180afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko static_assert(sizeof(T) == sizeof(unsigned_type), "Unexpected type size mismatch!"); 18280afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko static_assert(std::numeric_limits<unsigned_type>::radix == 2, "Unexpected radix!"); 18380afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko return std::numeric_limits<unsigned_type>::digits; 18480afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko} 18580afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko 18680afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko// Like sizeof, but count how many bits a type takes. Infers type from parameter. 18780afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Markotemplate <typename T> 18880afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Markostatic constexpr size_t BitSizeOf(T /*x*/) { 18980afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko return BitSizeOf<T>(); 19080afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko} 19180afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko 19280afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Markostatic inline uint16_t Low16Bits(uint32_t value) { 19380afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko return static_cast<uint16_t>(value); 19480afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko} 19580afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko 19680afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Markostatic inline uint16_t High16Bits(uint32_t value) { 19780afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko return static_cast<uint16_t>(value >> 16); 19880afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko} 19980afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko 20080afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Markostatic inline uint32_t Low32Bits(uint64_t value) { 20180afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko return static_cast<uint32_t>(value); 20280afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko} 20380afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko 20480afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Markostatic inline uint32_t High32Bits(uint64_t value) { 20580afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko return static_cast<uint32_t>(value >> 32); 20680afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko} 20780afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko 20880afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko// Check whether an N-bit two's-complement representation can hold value. 20980afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Markotemplate <typename T> 21080afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Markostatic inline bool IsInt(size_t N, T value) { 21180afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko if (N == BitSizeOf<T>()) { 21280afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko return true; 21380afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko } else { 21480afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko CHECK_LT(0u, N); 21580afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko CHECK_LT(N, BitSizeOf<T>()); 21680afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko T limit = static_cast<T>(1) << (N - 1u); 21780afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko return (-limit <= value) && (value < limit); 21880afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko } 21980afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko} 22080afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko 22180afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Markotemplate <typename T> 22280afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Markostatic constexpr T GetIntLimit(size_t bits) { 22380afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko return 22480afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko DCHECK_CONSTEXPR(bits > 0, "bits cannot be zero", 0) 22580afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko DCHECK_CONSTEXPR(bits < BitSizeOf<T>(), "kBits must be < max.", 0) 22680afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko static_cast<T>(1) << (bits - 1); 22780afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko} 22880afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko 22980afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Markotemplate <size_t kBits, typename T> 23080afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Markostatic constexpr bool IsInt(T value) { 23180afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko static_assert(kBits > 0, "kBits cannot be zero."); 23280afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko static_assert(kBits <= BitSizeOf<T>(), "kBits must be <= max."); 23380afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko static_assert(std::is_signed<T>::value, "Needs a signed type."); 23480afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko // Corner case for "use all bits." Can't use the limits, as they would overflow, but it is 23580afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko // trivially true. 23680afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko return (kBits == BitSizeOf<T>()) ? 23780afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko true : 23880afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko (-GetIntLimit<T>(kBits) <= value) && (value < GetIntLimit<T>(kBits)); 23980afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko} 24080afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko 24180afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Markotemplate <size_t kBits, typename T> 24280afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Markostatic constexpr bool IsUint(T value) { 24380afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko static_assert(kBits > 0, "kBits cannot be zero."); 24480afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko static_assert(kBits <= BitSizeOf<T>(), "kBits must be <= max."); 24580afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko static_assert(std::is_integral<T>::value, "Needs an integral type."); 24680afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko // Corner case for "use all bits." Can't use the limits, as they would overflow, but it is 24780afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko // trivially true. 24880afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko // NOTE: To avoid triggering assertion in GetIntLimit(kBits+1) if kBits+1==BitSizeOf<T>(), 24980afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko // use GetIntLimit(kBits)*2u. The unsigned arithmetic works well for us if it overflows. 25080afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko return (0 <= value) && 25180afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko (kBits == BitSizeOf<T>() || 25280afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko (static_cast<typename std::make_unsigned<T>::type>(value) <= 25380afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko GetIntLimit<typename std::make_unsigned<T>::type>(kBits) * 2u - 1u)); 25480afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko} 25580afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko 25680afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Markotemplate <size_t kBits, typename T> 25780afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Markostatic constexpr bool IsAbsoluteUint(T value) { 25880afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko static_assert(kBits <= BitSizeOf<T>(), "kBits must be <= max."); 25980afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko static_assert(std::is_integral<T>::value, "Needs an integral type."); 26080afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko typedef typename std::make_unsigned<T>::type unsigned_type; 26180afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko return (kBits == BitSizeOf<T>()) 26280afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko ? true 26380afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko : IsUint<kBits>(value < 0 26480afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko ? static_cast<unsigned_type>(-1 - value) + 1u // Avoid overflow. 26580afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko : static_cast<unsigned_type>(value)); 26680afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko} 26780afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko 268dbce0d738e9d7956d2bd73e932a0fdd28f2229b4Chris Larsen// Generate maximum/minimum values for signed/unsigned n-bit integers 269dbce0d738e9d7956d2bd73e932a0fdd28f2229b4Chris Larsentemplate <typename T> 270dbce0d738e9d7956d2bd73e932a0fdd28f2229b4Chris Larsenstatic constexpr T MaxInt(size_t bits) { 271dbce0d738e9d7956d2bd73e932a0fdd28f2229b4Chris Larsen return 27209ed09866da6d8c7448ef297c148bfa577a247c2David Srbecky DCHECK_CONSTEXPR(std::is_unsigned<T>::value || bits > 0, "bits cannot be zero for signed", 0) 273dbce0d738e9d7956d2bd73e932a0fdd28f2229b4Chris Larsen DCHECK_CONSTEXPR(bits <= BitSizeOf<T>(), "kBits must be < max.", 0) 274dbce0d738e9d7956d2bd73e932a0fdd28f2229b4Chris Larsen bits == BitSizeOf<T>() 275dbce0d738e9d7956d2bd73e932a0fdd28f2229b4Chris Larsen ? std::numeric_limits<T>::max() 276dbce0d738e9d7956d2bd73e932a0fdd28f2229b4Chris Larsen : std::is_signed<T>::value 277dbce0d738e9d7956d2bd73e932a0fdd28f2229b4Chris Larsen ? (bits == 1 278dbce0d738e9d7956d2bd73e932a0fdd28f2229b4Chris Larsen ? 0 279dbce0d738e9d7956d2bd73e932a0fdd28f2229b4Chris Larsen : static_cast<T>(MaxInt<typename std::make_unsigned<T>::type>(bits - 1))) 280dbce0d738e9d7956d2bd73e932a0fdd28f2229b4Chris Larsen : static_cast<T>(UINT64_C(1) << bits) - static_cast<T>(1); 281dbce0d738e9d7956d2bd73e932a0fdd28f2229b4Chris Larsen} 282dbce0d738e9d7956d2bd73e932a0fdd28f2229b4Chris Larsen 283dbce0d738e9d7956d2bd73e932a0fdd28f2229b4Chris Larsentemplate <typename T> 284dbce0d738e9d7956d2bd73e932a0fdd28f2229b4Chris Larsenstatic constexpr T MinInt(size_t bits) { 285dbce0d738e9d7956d2bd73e932a0fdd28f2229b4Chris Larsen return 28609ed09866da6d8c7448ef297c148bfa577a247c2David Srbecky DCHECK_CONSTEXPR(std::is_unsigned<T>::value || bits > 0, "bits cannot be zero for signed", 0) 287dbce0d738e9d7956d2bd73e932a0fdd28f2229b4Chris Larsen DCHECK_CONSTEXPR(bits <= BitSizeOf<T>(), "kBits must be < max.", 0) 288dbce0d738e9d7956d2bd73e932a0fdd28f2229b4Chris Larsen bits == BitSizeOf<T>() 289dbce0d738e9d7956d2bd73e932a0fdd28f2229b4Chris Larsen ? std::numeric_limits<T>::min() 290dbce0d738e9d7956d2bd73e932a0fdd28f2229b4Chris Larsen : std::is_signed<T>::value 291dbce0d738e9d7956d2bd73e932a0fdd28f2229b4Chris Larsen ? (bits == 1 ? -1 : static_cast<T>(-1) - MaxInt<T>(bits)) 292dbce0d738e9d7956d2bd73e932a0fdd28f2229b4Chris Larsen : static_cast<T>(0); 293dbce0d738e9d7956d2bd73e932a0fdd28f2229b4Chris Larsen} 294dbce0d738e9d7956d2bd73e932a0fdd28f2229b4Chris Larsen 29580afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko// Using the Curiously Recurring Template Pattern to implement everything shared 29680afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko// by LowToHighBitIterator and HighToLowBitIterator, i.e. everything but operator*(). 29780afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Markotemplate <typename T, typename Iter> 29880afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Markoclass BitIteratorBase 29980afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko : public std::iterator<std::forward_iterator_tag, uint32_t, ptrdiff_t, void, void> { 30080afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko static_assert(std::is_integral<T>::value, "T must be integral"); 30180afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko static_assert(std::is_unsigned<T>::value, "T must be unsigned"); 30280afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko 30380afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko static_assert(sizeof(T) == sizeof(uint32_t) || sizeof(T) == sizeof(uint64_t), "Unsupported size"); 30480afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko 30580afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko public: 30680afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko BitIteratorBase() : bits_(0u) { } 30780afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko explicit BitIteratorBase(T bits) : bits_(bits) { } 30880afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko 30980afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko Iter& operator++() { 31080afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko DCHECK_NE(bits_, 0u); 31180afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko uint32_t bit = *static_cast<Iter&>(*this); 31280afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko bits_ &= ~(static_cast<T>(1u) << bit); 31380afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko return static_cast<Iter&>(*this); 31480afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko } 31580afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko 31680afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko Iter& operator++(int) { 31780afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko Iter tmp(static_cast<Iter&>(*this)); 31880afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko ++*this; 31980afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko return tmp; 32080afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko } 32180afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko 32280afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko protected: 32380afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko T bits_; 32480afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko 32580afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko template <typename U, typename I> 32680afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko friend bool operator==(const BitIteratorBase<U, I>& lhs, const BitIteratorBase<U, I>& rhs); 32780afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko}; 32880afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko 32980afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Markotemplate <typename T, typename Iter> 33080afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Markobool operator==(const BitIteratorBase<T, Iter>& lhs, const BitIteratorBase<T, Iter>& rhs) { 33180afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko return lhs.bits_ == rhs.bits_; 33280afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko} 33380afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko 33480afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Markotemplate <typename T, typename Iter> 33580afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Markobool operator!=(const BitIteratorBase<T, Iter>& lhs, const BitIteratorBase<T, Iter>& rhs) { 33680afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko return !(lhs == rhs); 33780afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko} 33880afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko 33980afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Markotemplate <typename T> 34080afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Markoclass LowToHighBitIterator : public BitIteratorBase<T, LowToHighBitIterator<T>> { 34180afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko public: 34280afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko using BitIteratorBase<T, LowToHighBitIterator<T>>::BitIteratorBase; 34380afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko 34480afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko uint32_t operator*() const { 34580afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko DCHECK_NE(this->bits_, 0u); 34680afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko return CTZ(this->bits_); 34780afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko } 34880afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko}; 34980afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko 35080afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Markotemplate <typename T> 35180afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Markoclass HighToLowBitIterator : public BitIteratorBase<T, HighToLowBitIterator<T>> { 35280afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko public: 35380afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko using BitIteratorBase<T, HighToLowBitIterator<T>>::BitIteratorBase; 35480afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko 35580afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko uint32_t operator*() const { 35680afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko DCHECK_NE(this->bits_, 0u); 35780afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko static_assert(std::numeric_limits<T>::radix == 2, "Unexpected radix!"); 35880afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko return std::numeric_limits<T>::digits - 1u - CLZ(this->bits_); 35980afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko } 36080afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko}; 36180afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko 36280afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Markotemplate <typename T> 36380afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir MarkoIterationRange<LowToHighBitIterator<T>> LowToHighBits(T bits) { 36480afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko return IterationRange<LowToHighBitIterator<T>>( 36580afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko LowToHighBitIterator<T>(bits), LowToHighBitIterator<T>()); 36680afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko} 36780afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko 36880afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Markotemplate <typename T> 36980afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir MarkoIterationRange<HighToLowBitIterator<T>> HighToLowBits(T bits) { 37080afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko return IterationRange<HighToLowBitIterator<T>>( 37180afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko HighToLowBitIterator<T>(bits), HighToLowBitIterator<T>()); 37280afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko} 37380afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko 37480afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko} // namespace art 37580afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko 37680afd02024d20e60b197d3adfbb43cc303cf29e0Vladimir Marko#endif // ART_RUNTIME_BASE_BIT_UTILS_H_ 377