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