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