1 /*
2 * Copyright (C) 2015 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #ifndef ART_RUNTIME_BASE_BIT_UTILS_H_
18 #define ART_RUNTIME_BASE_BIT_UTILS_H_
19
20 #include <iterator>
21 #include <limits>
22 #include <type_traits>
23
24 #include "base/logging.h"
25 #include "base/iteration_range.h"
26
27 namespace art {
28
29 template<typename T>
CLZ(T x)30 static constexpr int CLZ(T x) {
31 static_assert(std::is_integral<T>::value, "T must be integral");
32 // TODO: assert unsigned. There is currently many uses with signed values.
33 static_assert(sizeof(T) <= sizeof(long long), // NOLINT [runtime/int] [4]
34 "T too large, must be smaller than long long");
35 return (sizeof(T) == sizeof(uint32_t))
36 ? __builtin_clz(x) // TODO: __builtin_clz[ll] has undefined behavior for x=0
37 : __builtin_clzll(x);
38 }
39
40 template<typename T>
CTZ(T x)41 static constexpr int CTZ(T x) {
42 static_assert(std::is_integral<T>::value, "T must be integral");
43 // TODO: assert unsigned. There is currently many uses with signed values.
44 return (sizeof(T) == sizeof(uint32_t))
45 ? __builtin_ctz(x)
46 : __builtin_ctzll(x);
47 }
48
49 template<typename T>
POPCOUNT(T x)50 static constexpr int POPCOUNT(T x) {
51 return (sizeof(T) == sizeof(uint32_t))
52 ? __builtin_popcount(x)
53 : __builtin_popcountll(x);
54 }
55
56 // Find the bit position of the most significant bit (0-based), or -1 if there were no bits set.
57 template <typename T>
MostSignificantBit(T value)58 static constexpr ssize_t MostSignificantBit(T value) {
59 static_assert(std::is_integral<T>::value, "T must be integral");
60 static_assert(std::is_unsigned<T>::value, "T must be unsigned");
61 static_assert(std::numeric_limits<T>::radix == 2, "Unexpected radix!");
62 return (value == 0) ? -1 : std::numeric_limits<T>::digits - 1 - CLZ(value);
63 }
64
65 // Find the bit position of the least significant bit (0-based), or -1 if there were no bits set.
66 template <typename T>
LeastSignificantBit(T value)67 static constexpr ssize_t LeastSignificantBit(T value) {
68 static_assert(std::is_integral<T>::value, "T must be integral");
69 static_assert(std::is_unsigned<T>::value, "T must be unsigned");
70 return (value == 0) ? -1 : CTZ(value);
71 }
72
73 // How many bits (minimally) does it take to store the constant 'value'? i.e. 1 for 1, 3 for 5, etc.
74 template <typename T>
MinimumBitsToStore(T value)75 static constexpr size_t MinimumBitsToStore(T value) {
76 return static_cast<size_t>(MostSignificantBit(value) + 1);
77 }
78
79 template <typename T>
RoundUpToPowerOfTwo(T x)80 static constexpr inline T RoundUpToPowerOfTwo(T x) {
81 static_assert(std::is_integral<T>::value, "T must be integral");
82 static_assert(std::is_unsigned<T>::value, "T must be unsigned");
83 // NOTE: Undefined if x > (1 << (std::numeric_limits<T>::digits - 1)).
84 return (x < 2u) ? x : static_cast<T>(1u) << (std::numeric_limits<T>::digits - CLZ(x - 1u));
85 }
86
87 template<typename T>
IsPowerOfTwo(T x)88 static constexpr bool IsPowerOfTwo(T x) {
89 static_assert(std::is_integral<T>::value, "T must be integral");
90 // TODO: assert unsigned. There is currently many uses with signed values.
91 return (x & (x - 1)) == 0;
92 }
93
94 template<typename T>
WhichPowerOf2(T x)95 static inline int WhichPowerOf2(T x) {
96 static_assert(std::is_integral<T>::value, "T must be integral");
97 // TODO: assert unsigned. There is currently many uses with signed values.
98 DCHECK((x != 0) && IsPowerOfTwo(x));
99 return CTZ(x);
100 }
101
102 // For rounding integers.
103 // NOTE: In the absence of std::omit_from_type_deduction<T> or std::identity<T>, use std::decay<T>.
104 template<typename T>
105 static constexpr T RoundDown(T x, typename std::decay<T>::type n) WARN_UNUSED;
106
107 template<typename T>
RoundDown(T x,typename std::decay<T>::type n)108 static constexpr T RoundDown(T x, typename std::decay<T>::type n) {
109 return
110 DCHECK_CONSTEXPR(IsPowerOfTwo(n), , T(0))
111 (x & -n);
112 }
113
114 template<typename T>
115 static constexpr T RoundUp(T x, typename std::remove_reference<T>::type n) WARN_UNUSED;
116
117 template<typename T>
RoundUp(T x,typename std::remove_reference<T>::type n)118 static constexpr T RoundUp(T x, typename std::remove_reference<T>::type n) {
119 return RoundDown(x + n - 1, n);
120 }
121
122 // For aligning pointers.
123 template<typename T>
124 static inline T* AlignDown(T* x, uintptr_t n) WARN_UNUSED;
125
126 template<typename T>
AlignDown(T * x,uintptr_t n)127 static inline T* AlignDown(T* x, uintptr_t n) {
128 return reinterpret_cast<T*>(RoundDown(reinterpret_cast<uintptr_t>(x), n));
129 }
130
131 template<typename T>
132 static inline T* AlignUp(T* x, uintptr_t n) WARN_UNUSED;
133
134 template<typename T>
AlignUp(T * x,uintptr_t n)135 static inline T* AlignUp(T* x, uintptr_t n) {
136 return reinterpret_cast<T*>(RoundUp(reinterpret_cast<uintptr_t>(x), n));
137 }
138
139 template<int n, typename T>
IsAligned(T x)140 static inline bool IsAligned(T x) {
141 static_assert((n & (n - 1)) == 0, "n is not a power of two");
142 return (x & (n - 1)) == 0;
143 }
144
145 template<int n, typename T>
IsAligned(T * x)146 static inline bool IsAligned(T* x) {
147 return IsAligned<n>(reinterpret_cast<const uintptr_t>(x));
148 }
149
150 template<typename T>
IsAlignedParam(T x,int n)151 static inline bool IsAlignedParam(T x, int n) {
152 return (x & (n - 1)) == 0;
153 }
154
155 #define CHECK_ALIGNED(value, alignment) \
156 CHECK(::art::IsAligned<alignment>(value)) << reinterpret_cast<const void*>(value)
157
158 #define DCHECK_ALIGNED(value, alignment) \
159 DCHECK(::art::IsAligned<alignment>(value)) << reinterpret_cast<const void*>(value)
160
161 #define DCHECK_ALIGNED_PARAM(value, alignment) \
162 DCHECK(::art::IsAlignedParam(value, alignment)) << reinterpret_cast<const void*>(value)
163
164 // Like sizeof, but count how many bits a type takes. Pass type explicitly.
165 template <typename T>
BitSizeOf()166 static constexpr size_t BitSizeOf() {
167 static_assert(std::is_integral<T>::value, "T must be integral");
168 typedef typename std::make_unsigned<T>::type unsigned_type;
169 static_assert(sizeof(T) == sizeof(unsigned_type), "Unexpected type size mismatch!");
170 static_assert(std::numeric_limits<unsigned_type>::radix == 2, "Unexpected radix!");
171 return std::numeric_limits<unsigned_type>::digits;
172 }
173
174 // Like sizeof, but count how many bits a type takes. Infers type from parameter.
175 template <typename T>
BitSizeOf(T)176 static constexpr size_t BitSizeOf(T /*x*/) {
177 return BitSizeOf<T>();
178 }
179
Low16Bits(uint32_t value)180 static inline uint16_t Low16Bits(uint32_t value) {
181 return static_cast<uint16_t>(value);
182 }
183
High16Bits(uint32_t value)184 static inline uint16_t High16Bits(uint32_t value) {
185 return static_cast<uint16_t>(value >> 16);
186 }
187
Low32Bits(uint64_t value)188 static inline uint32_t Low32Bits(uint64_t value) {
189 return static_cast<uint32_t>(value);
190 }
191
High32Bits(uint64_t value)192 static inline uint32_t High32Bits(uint64_t value) {
193 return static_cast<uint32_t>(value >> 32);
194 }
195
196 // Check whether an N-bit two's-complement representation can hold value.
197 template <typename T>
IsInt(size_t N,T value)198 static inline bool IsInt(size_t N, T value) {
199 if (N == BitSizeOf<T>()) {
200 return true;
201 } else {
202 CHECK_LT(0u, N);
203 CHECK_LT(N, BitSizeOf<T>());
204 T limit = static_cast<T>(1) << (N - 1u);
205 return (-limit <= value) && (value < limit);
206 }
207 }
208
209 template <typename T>
GetIntLimit(size_t bits)210 static constexpr T GetIntLimit(size_t bits) {
211 return
212 DCHECK_CONSTEXPR(bits > 0, "bits cannot be zero", 0)
213 DCHECK_CONSTEXPR(bits < BitSizeOf<T>(), "kBits must be < max.", 0)
214 static_cast<T>(1) << (bits - 1);
215 }
216
217 template <size_t kBits, typename T>
IsInt(T value)218 static constexpr bool IsInt(T value) {
219 static_assert(kBits > 0, "kBits cannot be zero.");
220 static_assert(kBits <= BitSizeOf<T>(), "kBits must be <= max.");
221 static_assert(std::is_signed<T>::value, "Needs a signed type.");
222 // Corner case for "use all bits." Can't use the limits, as they would overflow, but it is
223 // trivially true.
224 return (kBits == BitSizeOf<T>()) ?
225 true :
226 (-GetIntLimit<T>(kBits) <= value) && (value < GetIntLimit<T>(kBits));
227 }
228
229 template <size_t kBits, typename T>
IsUint(T value)230 static constexpr bool IsUint(T value) {
231 static_assert(kBits > 0, "kBits cannot be zero.");
232 static_assert(kBits <= BitSizeOf<T>(), "kBits must be <= max.");
233 static_assert(std::is_integral<T>::value, "Needs an integral type.");
234 // Corner case for "use all bits." Can't use the limits, as they would overflow, but it is
235 // trivially true.
236 // NOTE: To avoid triggering assertion in GetIntLimit(kBits+1) if kBits+1==BitSizeOf<T>(),
237 // use GetIntLimit(kBits)*2u. The unsigned arithmetic works well for us if it overflows.
238 return (0 <= value) &&
239 (kBits == BitSizeOf<T>() ||
240 (static_cast<typename std::make_unsigned<T>::type>(value) <=
241 GetIntLimit<typename std::make_unsigned<T>::type>(kBits) * 2u - 1u));
242 }
243
244 template <size_t kBits, typename T>
IsAbsoluteUint(T value)245 static constexpr bool IsAbsoluteUint(T value) {
246 static_assert(kBits <= BitSizeOf<T>(), "kBits must be <= max.");
247 static_assert(std::is_integral<T>::value, "Needs an integral type.");
248 typedef typename std::make_unsigned<T>::type unsigned_type;
249 return (kBits == BitSizeOf<T>())
250 ? true
251 : IsUint<kBits>(value < 0
252 ? static_cast<unsigned_type>(-1 - value) + 1u // Avoid overflow.
253 : static_cast<unsigned_type>(value));
254 }
255
256 // Using the Curiously Recurring Template Pattern to implement everything shared
257 // by LowToHighBitIterator and HighToLowBitIterator, i.e. everything but operator*().
258 template <typename T, typename Iter>
259 class BitIteratorBase
260 : public std::iterator<std::forward_iterator_tag, uint32_t, ptrdiff_t, void, void> {
261 static_assert(std::is_integral<T>::value, "T must be integral");
262 static_assert(std::is_unsigned<T>::value, "T must be unsigned");
263
264 static_assert(sizeof(T) == sizeof(uint32_t) || sizeof(T) == sizeof(uint64_t), "Unsupported size");
265
266 public:
BitIteratorBase()267 BitIteratorBase() : bits_(0u) { }
BitIteratorBase(T bits)268 explicit BitIteratorBase(T bits) : bits_(bits) { }
269
270 Iter& operator++() {
271 DCHECK_NE(bits_, 0u);
272 uint32_t bit = *static_cast<Iter&>(*this);
273 bits_ &= ~(static_cast<T>(1u) << bit);
274 return static_cast<Iter&>(*this);
275 }
276
277 Iter& operator++(int) {
278 Iter tmp(static_cast<Iter&>(*this));
279 ++*this;
280 return tmp;
281 }
282
283 protected:
284 T bits_;
285
286 template <typename U, typename I>
287 friend bool operator==(const BitIteratorBase<U, I>& lhs, const BitIteratorBase<U, I>& rhs);
288 };
289
290 template <typename T, typename Iter>
291 bool operator==(const BitIteratorBase<T, Iter>& lhs, const BitIteratorBase<T, Iter>& rhs) {
292 return lhs.bits_ == rhs.bits_;
293 }
294
295 template <typename T, typename Iter>
296 bool operator!=(const BitIteratorBase<T, Iter>& lhs, const BitIteratorBase<T, Iter>& rhs) {
297 return !(lhs == rhs);
298 }
299
300 template <typename T>
301 class LowToHighBitIterator : public BitIteratorBase<T, LowToHighBitIterator<T>> {
302 public:
303 using BitIteratorBase<T, LowToHighBitIterator<T>>::BitIteratorBase;
304
305 uint32_t operator*() const {
306 DCHECK_NE(this->bits_, 0u);
307 return CTZ(this->bits_);
308 }
309 };
310
311 template <typename T>
312 class HighToLowBitIterator : public BitIteratorBase<T, HighToLowBitIterator<T>> {
313 public:
314 using BitIteratorBase<T, HighToLowBitIterator<T>>::BitIteratorBase;
315
316 uint32_t operator*() const {
317 DCHECK_NE(this->bits_, 0u);
318 static_assert(std::numeric_limits<T>::radix == 2, "Unexpected radix!");
319 return std::numeric_limits<T>::digits - 1u - CLZ(this->bits_);
320 }
321 };
322
323 template <typename T>
LowToHighBits(T bits)324 IterationRange<LowToHighBitIterator<T>> LowToHighBits(T bits) {
325 return IterationRange<LowToHighBitIterator<T>>(
326 LowToHighBitIterator<T>(bits), LowToHighBitIterator<T>());
327 }
328
329 template <typename T>
HighToLowBits(T bits)330 IterationRange<HighToLowBitIterator<T>> HighToLowBits(T bits) {
331 return IterationRange<HighToLowBitIterator<T>>(
332 HighToLowBitIterator<T>(bits), HighToLowBitIterator<T>());
333 }
334
335 } // namespace art
336
337 #endif // ART_RUNTIME_BASE_BIT_UTILS_H_
338