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_LIBARTBASE_BASE_BIT_UTILS_H_
18 #define ART_LIBARTBASE_BASE_BIT_UTILS_H_
19
20 #include <limits>
21 #include <type_traits>
22
23 #include <android-base/logging.h>
24
25 #include "base/stl_util_identity.h"
26
27 namespace art {
28
29 // Like sizeof, but count how many bits a type takes. Pass type explicitly.
30 template <typename T>
BitSizeOf()31 constexpr size_t BitSizeOf() {
32 static_assert(std::is_integral<T>::value, "T must be integral");
33 using unsigned_type = typename std::make_unsigned<T>::type;
34 static_assert(sizeof(T) == sizeof(unsigned_type), "Unexpected type size mismatch!");
35 static_assert(std::numeric_limits<unsigned_type>::radix == 2, "Unexpected radix!");
36 return std::numeric_limits<unsigned_type>::digits;
37 }
38
39 // Like sizeof, but count how many bits a type takes. Infers type from parameter.
40 template <typename T>
BitSizeOf(T)41 constexpr size_t BitSizeOf(T /*x*/) {
42 return BitSizeOf<T>();
43 }
44
45 template<typename T>
CLZ(T x)46 constexpr int CLZ(T x) {
47 static_assert(std::is_integral<T>::value, "T must be integral");
48 static_assert(std::is_unsigned<T>::value, "T must be unsigned");
49 static_assert(std::numeric_limits<T>::radix == 2, "Unexpected radix!");
50 static_assert(sizeof(T) == sizeof(uint64_t) || sizeof(T) <= sizeof(uint32_t),
51 "Unsupported sizeof(T)");
52 DCHECK_NE(x, 0u);
53 constexpr bool is_64_bit = (sizeof(T) == sizeof(uint64_t));
54 constexpr size_t adjustment =
55 is_64_bit ? 0u : std::numeric_limits<uint32_t>::digits - std::numeric_limits<T>::digits;
56 return is_64_bit ? __builtin_clzll(x) : __builtin_clz(x) - adjustment;
57 }
58
59 // Similar to CLZ except that on zero input it returns bitwidth and supports signed integers.
60 template<typename T>
JAVASTYLE_CLZ(T x)61 constexpr int JAVASTYLE_CLZ(T x) {
62 static_assert(std::is_integral<T>::value, "T must be integral");
63 using unsigned_type = typename std::make_unsigned<T>::type;
64 return (x == 0) ? BitSizeOf<T>() : CLZ(static_cast<unsigned_type>(x));
65 }
66
67 template<typename T>
CTZ(T x)68 constexpr int CTZ(T x) {
69 static_assert(std::is_integral<T>::value, "T must be integral");
70 // It is not unreasonable to ask for trailing zeros in a negative number. As such, do not check
71 // that T is an unsigned type.
72 static_assert(sizeof(T) == sizeof(uint64_t) || sizeof(T) <= sizeof(uint32_t),
73 "Unsupported sizeof(T)");
74 DCHECK_NE(x, static_cast<T>(0));
75 return (sizeof(T) == sizeof(uint64_t)) ? __builtin_ctzll(x) : __builtin_ctz(x);
76 }
77
78 // Similar to CTZ except that on zero input it returns bitwidth and supports signed integers.
79 template<typename T>
JAVASTYLE_CTZ(T x)80 constexpr int JAVASTYLE_CTZ(T x) {
81 static_assert(std::is_integral<T>::value, "T must be integral");
82 using unsigned_type = typename std::make_unsigned<T>::type;
83 return (x == 0) ? BitSizeOf<T>() : CTZ(static_cast<unsigned_type>(x));
84 }
85
86 // Return the number of 1-bits in `x`.
87 template<typename T>
POPCOUNT(T x)88 constexpr int POPCOUNT(T x) {
89 return (sizeof(T) == sizeof(uint32_t)) ? __builtin_popcount(x) : __builtin_popcountll(x);
90 }
91
92 // Swap bytes.
93 template<typename T>
BSWAP(T x)94 constexpr T BSWAP(T x) {
95 if (sizeof(T) == sizeof(uint16_t)) {
96 return __builtin_bswap16(x);
97 } else if (sizeof(T) == sizeof(uint32_t)) {
98 return __builtin_bswap32(x);
99 } else {
100 return __builtin_bswap64(x);
101 }
102 }
103
104 // Find the bit position of the most significant bit (0-based), or -1 if there were no bits set.
105 template <typename T>
MostSignificantBit(T value)106 constexpr ssize_t MostSignificantBit(T value) {
107 static_assert(std::is_integral<T>::value, "T must be integral");
108 static_assert(std::is_unsigned<T>::value, "T must be unsigned");
109 static_assert(std::numeric_limits<T>::radix == 2, "Unexpected radix!");
110 return (value == 0) ? -1 : std::numeric_limits<T>::digits - 1 - CLZ(value);
111 }
112
113 // Find the bit position of the least significant bit (0-based), or -1 if there were no bits set.
114 template <typename T>
LeastSignificantBit(T value)115 constexpr ssize_t LeastSignificantBit(T value) {
116 static_assert(std::is_integral<T>::value, "T must be integral");
117 static_assert(std::is_unsigned<T>::value, "T must be unsigned");
118 return (value == 0) ? -1 : CTZ(value);
119 }
120
121 // How many bits (minimally) does it take to store the constant 'value'? i.e. 1 for 1, 3 for 5, etc.
122 template <typename T>
MinimumBitsToStore(T value)123 constexpr size_t MinimumBitsToStore(T value) {
124 return static_cast<size_t>(MostSignificantBit(value) + 1);
125 }
126
127 template <typename T>
RoundUpToPowerOfTwo(T x)128 constexpr T RoundUpToPowerOfTwo(T x) {
129 static_assert(std::is_integral<T>::value, "T must be integral");
130 static_assert(std::is_unsigned<T>::value, "T must be unsigned");
131 // NOTE: Undefined if x > (1 << (std::numeric_limits<T>::digits - 1)).
132 return (x < 2u) ? x : static_cast<T>(1u) << (std::numeric_limits<T>::digits - CLZ(x - 1u));
133 }
134
135 // Return highest possible N - a power of two - such that val >= N.
136 template <typename T>
TruncToPowerOfTwo(T val)137 constexpr T TruncToPowerOfTwo(T val) {
138 static_assert(std::is_integral<T>::value, "T must be integral");
139 static_assert(std::is_unsigned<T>::value, "T must be unsigned");
140 return (val != 0) ? static_cast<T>(1u) << (BitSizeOf<T>() - CLZ(val) - 1u) : 0;
141 }
142
143 template<typename T>
IsPowerOfTwo(T x)144 constexpr bool IsPowerOfTwo(T x) {
145 static_assert(std::is_integral<T>::value, "T must be integral");
146 // TODO: assert unsigned. There is currently many uses with signed values.
147 return (x & (x - 1)) == 0;
148 }
149
150 template<typename T>
WhichPowerOf2(T x)151 constexpr int WhichPowerOf2(T x) {
152 static_assert(std::is_integral<T>::value, "T must be integral");
153 // TODO: assert unsigned. There is currently many uses with signed values.
154 DCHECK((x != 0) && IsPowerOfTwo(x));
155 return CTZ(x);
156 }
157
158 // For rounding integers.
159 // Note: Omit the `n` from T type deduction, deduce only from the `x` argument.
160 template<typename T>
161 constexpr T RoundDown(T x, typename Identity<T>::type n) WARN_UNUSED;
162
163 template<typename T>
RoundDown(T x,typename Identity<T>::type n)164 constexpr T RoundDown(T x, typename Identity<T>::type n) {
165 DCHECK(IsPowerOfTwo(n));
166 return (x & -n);
167 }
168
169 template<typename T>
170 constexpr T RoundUp(T x, typename std::remove_reference<T>::type n) WARN_UNUSED;
171
172 template<typename T>
RoundUp(T x,typename std::remove_reference<T>::type n)173 constexpr T RoundUp(T x, typename std::remove_reference<T>::type n) {
174 return RoundDown(x + n - 1, n);
175 }
176
177 // For aligning pointers.
178 template<typename T>
179 inline T* AlignDown(T* x, uintptr_t n) WARN_UNUSED;
180
181 template<typename T>
AlignDown(T * x,uintptr_t n)182 inline T* AlignDown(T* x, uintptr_t n) {
183 return reinterpret_cast<T*>(RoundDown(reinterpret_cast<uintptr_t>(x), n));
184 }
185
186 template<typename T>
187 inline T* AlignUp(T* x, uintptr_t n) WARN_UNUSED;
188
189 template<typename T>
AlignUp(T * x,uintptr_t n)190 inline T* AlignUp(T* x, uintptr_t n) {
191 return reinterpret_cast<T*>(RoundUp(reinterpret_cast<uintptr_t>(x), n));
192 }
193
194 template<int n, typename T>
IsAligned(T x)195 constexpr bool IsAligned(T x) {
196 static_assert((n & (n - 1)) == 0, "n is not a power of two");
197 return (x & (n - 1)) == 0;
198 }
199
200 template<int n, typename T>
IsAligned(T * x)201 inline bool IsAligned(T* x) {
202 return IsAligned<n>(reinterpret_cast<const uintptr_t>(x));
203 }
204
205 template<typename T>
IsAlignedParam(T x,int n)206 inline bool IsAlignedParam(T x, int n) {
207 return (x & (n - 1)) == 0;
208 }
209
210 template<typename T>
IsAlignedParam(T * x,int n)211 inline bool IsAlignedParam(T* x, int n) {
212 return IsAlignedParam(reinterpret_cast<const uintptr_t>(x), n);
213 }
214
215 #define CHECK_ALIGNED(value, alignment) \
216 CHECK(::art::IsAligned<alignment>(value)) << reinterpret_cast<const void*>(value)
217
218 #define DCHECK_ALIGNED(value, alignment) \
219 DCHECK(::art::IsAligned<alignment>(value)) << reinterpret_cast<const void*>(value)
220
221 #define CHECK_ALIGNED_PARAM(value, alignment) \
222 CHECK(::art::IsAlignedParam(value, alignment)) << reinterpret_cast<const void*>(value)
223
224 #define DCHECK_ALIGNED_PARAM(value, alignment) \
225 DCHECK(::art::IsAlignedParam(value, alignment)) << reinterpret_cast<const void*>(value)
226
Low16Bits(uint32_t value)227 inline uint16_t Low16Bits(uint32_t value) {
228 return static_cast<uint16_t>(value);
229 }
230
High16Bits(uint32_t value)231 inline uint16_t High16Bits(uint32_t value) {
232 return static_cast<uint16_t>(value >> 16);
233 }
234
Low32Bits(uint64_t value)235 inline uint32_t Low32Bits(uint64_t value) {
236 return static_cast<uint32_t>(value);
237 }
238
High32Bits(uint64_t value)239 inline uint32_t High32Bits(uint64_t value) {
240 return static_cast<uint32_t>(value >> 32);
241 }
242
243 // Check whether an N-bit two's-complement representation can hold value.
244 template <typename T>
IsInt(size_t N,T value)245 inline bool IsInt(size_t N, T value) {
246 if (N == BitSizeOf<T>()) {
247 return true;
248 } else {
249 CHECK_LT(0u, N);
250 CHECK_LT(N, BitSizeOf<T>());
251 T limit = static_cast<T>(1) << (N - 1u);
252 return (-limit <= value) && (value < limit);
253 }
254 }
255
256 template <typename T>
GetIntLimit(size_t bits)257 constexpr T GetIntLimit(size_t bits) {
258 DCHECK_NE(bits, 0u);
259 DCHECK_LT(bits, BitSizeOf<T>());
260 return static_cast<T>(1) << (bits - 1);
261 }
262
263 template <size_t kBits, typename T>
IsInt(T value)264 constexpr bool IsInt(T value) {
265 static_assert(kBits > 0, "kBits cannot be zero.");
266 static_assert(kBits <= BitSizeOf<T>(), "kBits must be <= max.");
267 static_assert(std::is_signed<T>::value, "Needs a signed type.");
268 // Corner case for "use all bits." Can't use the limits, as they would overflow, but it is
269 // trivially true.
270 return (kBits == BitSizeOf<T>()) ?
271 true :
272 (-GetIntLimit<T>(kBits) <= value) && (value < GetIntLimit<T>(kBits));
273 }
274
275 template <size_t kBits, typename T>
IsUint(T value)276 constexpr bool IsUint(T value) {
277 static_assert(kBits > 0, "kBits cannot be zero.");
278 static_assert(kBits <= BitSizeOf<T>(), "kBits must be <= max.");
279 static_assert(std::is_integral<T>::value, "Needs an integral type.");
280 // Corner case for "use all bits." Can't use the limits, as they would overflow, but it is
281 // trivially true.
282 // NOTE: To avoid triggering assertion in GetIntLimit(kBits+1) if kBits+1==BitSizeOf<T>(),
283 // use GetIntLimit(kBits)*2u. The unsigned arithmetic works well for us if it overflows.
284 using unsigned_type = typename std::make_unsigned<T>::type;
285 return (0 <= value) &&
286 (kBits == BitSizeOf<T>() ||
287 (static_cast<unsigned_type>(value) <= GetIntLimit<unsigned_type>(kBits) * 2u - 1u));
288 }
289
290 template <size_t kBits, typename T>
IsAbsoluteUint(T value)291 constexpr bool IsAbsoluteUint(T value) {
292 static_assert(kBits <= BitSizeOf<T>(), "kBits must be <= max.");
293 static_assert(std::is_integral<T>::value, "Needs an integral type.");
294 using unsigned_type = typename std::make_unsigned<T>::type;
295 return (kBits == BitSizeOf<T>())
296 ? true
297 : IsUint<kBits>(value < 0
298 ? static_cast<unsigned_type>(-1 - value) + 1u // Avoid overflow.
299 : static_cast<unsigned_type>(value));
300 }
301
302 // Generate maximum/minimum values for signed/unsigned n-bit integers
303 template <typename T>
MaxInt(size_t bits)304 constexpr T MaxInt(size_t bits) {
305 DCHECK(std::is_unsigned<T>::value || bits > 0u) << "bits cannot be zero for signed.";
306 DCHECK_LE(bits, BitSizeOf<T>());
307 using unsigned_type = typename std::make_unsigned<T>::type;
308 return bits == BitSizeOf<T>()
309 ? std::numeric_limits<T>::max()
310 : std::is_signed<T>::value
311 ? ((bits == 1u) ? 0 : static_cast<T>(MaxInt<unsigned_type>(bits - 1)))
312 : static_cast<T>(UINT64_C(1) << bits) - static_cast<T>(1);
313 }
314
315 template <typename T>
MinInt(size_t bits)316 constexpr T MinInt(size_t bits) {
317 DCHECK(std::is_unsigned<T>::value || bits > 0) << "bits cannot be zero for signed.";
318 DCHECK_LE(bits, BitSizeOf<T>());
319 return bits == BitSizeOf<T>()
320 ? std::numeric_limits<T>::min()
321 : std::is_signed<T>::value
322 ? ((bits == 1u) ? -1 : static_cast<T>(-1) - MaxInt<T>(bits))
323 : static_cast<T>(0);
324 }
325
326 // Returns value with bit set in lowest one-bit position or 0 if 0. (java.lang.X.lowestOneBit).
327 template <typename kind>
LowestOneBitValue(kind opnd)328 inline static kind LowestOneBitValue(kind opnd) {
329 // Hacker's Delight, Section 2-1
330 return opnd & -opnd;
331 }
332
333 // Returns value with bit set in hightest one-bit position or 0 if 0. (java.lang.X.highestOneBit).
334 template <typename T>
HighestOneBitValue(T opnd)335 inline static T HighestOneBitValue(T opnd) {
336 using unsigned_type = typename std::make_unsigned<T>::type;
337 T res;
338 if (opnd == 0) {
339 res = 0;
340 } else {
341 int bit_position = BitSizeOf<T>() - (CLZ(static_cast<unsigned_type>(opnd)) + 1);
342 res = static_cast<T>(UINT64_C(1) << bit_position);
343 }
344 return res;
345 }
346
347 // Rotate bits.
348 template <typename T, bool left>
Rot(T opnd,int distance)349 inline static T Rot(T opnd, int distance) {
350 int mask = BitSizeOf<T>() - 1;
351 int unsigned_right_shift = left ? (-distance & mask) : (distance & mask);
352 int signed_left_shift = left ? (distance & mask) : (-distance & mask);
353 using unsigned_type = typename std::make_unsigned<T>::type;
354 return (static_cast<unsigned_type>(opnd) >> unsigned_right_shift) | (opnd << signed_left_shift);
355 }
356
357 // TUNING: use rbit for arm/arm64
ReverseBits32(uint32_t opnd)358 inline static uint32_t ReverseBits32(uint32_t opnd) {
359 // Hacker's Delight 7-1
360 opnd = ((opnd >> 1) & 0x55555555) | ((opnd & 0x55555555) << 1);
361 opnd = ((opnd >> 2) & 0x33333333) | ((opnd & 0x33333333) << 2);
362 opnd = ((opnd >> 4) & 0x0F0F0F0F) | ((opnd & 0x0F0F0F0F) << 4);
363 opnd = ((opnd >> 8) & 0x00FF00FF) | ((opnd & 0x00FF00FF) << 8);
364 opnd = ((opnd >> 16)) | ((opnd) << 16);
365 return opnd;
366 }
367
368 // TUNING: use rbit for arm/arm64
ReverseBits64(uint64_t opnd)369 inline static uint64_t ReverseBits64(uint64_t opnd) {
370 // Hacker's Delight 7-1
371 opnd = (opnd & 0x5555555555555555L) << 1 | ((opnd >> 1) & 0x5555555555555555L);
372 opnd = (opnd & 0x3333333333333333L) << 2 | ((opnd >> 2) & 0x3333333333333333L);
373 opnd = (opnd & 0x0f0f0f0f0f0f0f0fL) << 4 | ((opnd >> 4) & 0x0f0f0f0f0f0f0f0fL);
374 opnd = (opnd & 0x00ff00ff00ff00ffL) << 8 | ((opnd >> 8) & 0x00ff00ff00ff00ffL);
375 opnd = (opnd << 48) | ((opnd & 0xffff0000L) << 16) | ((opnd >> 16) & 0xffff0000L) | (opnd >> 48);
376 return opnd;
377 }
378
379 // Create a mask for the least significant "bits"
380 // The returned value is always unsigned to prevent undefined behavior for bitwise ops.
381 //
382 // Given 'bits',
383 // Returns:
384 // <--- bits --->
385 // +-----------------+------------+
386 // | 0 ............0 | 1.....1 |
387 // +-----------------+------------+
388 // msb lsb
389 template <typename T = size_t>
MaskLeastSignificant(size_t bits)390 inline static constexpr std::make_unsigned_t<T> MaskLeastSignificant(size_t bits) {
391 DCHECK_GE(BitSizeOf<T>(), bits) << "Bits out of range for type T";
392 using unsigned_T = std::make_unsigned_t<T>;
393 if (bits >= BitSizeOf<T>()) {
394 return std::numeric_limits<unsigned_T>::max();
395 } else {
396 auto kOne = static_cast<unsigned_T>(1); // Do not truncate for T>size_t.
397 return static_cast<unsigned_T>((kOne << bits) - kOne);
398 }
399 }
400
401 // Clears the bitfield starting at the least significant bit "lsb" with a bitwidth of 'width'.
402 // (Equivalent of ARM BFC instruction).
403 //
404 // Given:
405 // <-- width -->
406 // +--------+------------+--------+
407 // | ABC... | bitfield | XYZ... +
408 // +--------+------------+--------+
409 // lsb 0
410 // Returns:
411 // <-- width -->
412 // +--------+------------+--------+
413 // | ABC... | 0........0 | XYZ... +
414 // +--------+------------+--------+
415 // lsb 0
416 template <typename T>
BitFieldClear(T value,size_t lsb,size_t width)417 inline static constexpr T BitFieldClear(T value, size_t lsb, size_t width) {
418 DCHECK_GE(BitSizeOf(value), lsb + width) << "Bit field out of range for value";
419 const auto val = static_cast<std::make_unsigned_t<T>>(value);
420 const auto mask = MaskLeastSignificant<T>(width);
421
422 return static_cast<T>(val & ~(mask << lsb));
423 }
424
425 // Inserts the contents of 'data' into bitfield of 'value' starting
426 // at the least significant bit "lsb" with a bitwidth of 'width'.
427 // Note: data must be within range of [MinInt(width), MaxInt(width)].
428 // (Equivalent of ARM BFI instruction).
429 //
430 // Given (data):
431 // <-- width -->
432 // +--------+------------+--------+
433 // | ABC... | bitfield | XYZ... +
434 // +--------+------------+--------+
435 // lsb 0
436 // Returns:
437 // <-- width -->
438 // +--------+------------+--------+
439 // | ABC... | 0...data | XYZ... +
440 // +--------+------------+--------+
441 // lsb 0
442
443 template <typename T, typename T2>
BitFieldInsert(T value,T2 data,size_t lsb,size_t width)444 inline static constexpr T BitFieldInsert(T value, T2 data, size_t lsb, size_t width) {
445 DCHECK_GE(BitSizeOf(value), lsb + width) << "Bit field out of range for value";
446 if (width != 0u) {
447 DCHECK_GE(MaxInt<T2>(width), data) << "Data out of range [too large] for bitwidth";
448 DCHECK_LE(MinInt<T2>(width), data) << "Data out of range [too small] for bitwidth";
449 } else {
450 DCHECK_EQ(static_cast<T2>(0), data) << "Data out of range [nonzero] for bitwidth 0";
451 }
452 const auto data_mask = MaskLeastSignificant<T2>(width);
453 const auto value_cleared = BitFieldClear(value, lsb, width);
454
455 return static_cast<T>(value_cleared | ((data & data_mask) << lsb));
456 }
457
458 // Extracts the bitfield starting at the least significant bit "lsb" with a bitwidth of 'width'.
459 // Signed types are sign-extended during extraction. (Equivalent of ARM UBFX/SBFX instruction).
460 //
461 // Given:
462 // <-- width -->
463 // +--------+-------------+-------+
464 // | | bitfield | +
465 // +--------+-------------+-------+
466 // lsb 0
467 // (Unsigned) Returns:
468 // <-- width -->
469 // +----------------+-------------+
470 // | 0... 0 | bitfield |
471 // +----------------+-------------+
472 // 0
473 // (Signed) Returns:
474 // <-- width -->
475 // +----------------+-------------+
476 // | S... S | bitfield |
477 // +----------------+-------------+
478 // 0
479 // where S is the highest bit in 'bitfield'.
480 template <typename T>
BitFieldExtract(T value,size_t lsb,size_t width)481 inline static constexpr T BitFieldExtract(T value, size_t lsb, size_t width) {
482 DCHECK_GE(BitSizeOf(value), lsb + width) << "Bit field out of range for value";
483 const auto val = static_cast<std::make_unsigned_t<T>>(value);
484
485 const T bitfield_unsigned =
486 static_cast<T>((val >> lsb) & MaskLeastSignificant<T>(width));
487 if (std::is_signed<T>::value) {
488 // Perform sign extension
489 if (width == 0) { // Avoid underflow.
490 return static_cast<T>(0);
491 } else if (bitfield_unsigned & (1 << (width - 1))) { // Detect if sign bit was set.
492 // MSB <width> LSB
493 // 0b11111...100...000000
494 const auto ones_negmask = ~MaskLeastSignificant<T>(width);
495 return static_cast<T>(bitfield_unsigned | ones_negmask);
496 }
497 }
498 // Skip sign extension.
499 return bitfield_unsigned;
500 }
501
502 } // namespace art
503
504 #endif // ART_LIBARTBASE_BASE_BIT_UTILS_H_
505