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