5 #ifndef V8_BASE_BITS_H_ 6 #define V8_BASE_BITS_H_ 11 #include "src/base/base-export.h" 12 #include "src/base/macros.h" 17 #include "src/base/win32-headers.h" 33 typename std::enable_if<std::is_unsigned<T>::value &&
sizeof(
T) <= 8,
35 CountPopulation(
T value) {
36 #if V8_HAS_BUILTIN_POPCOUNT 37 return sizeof(
T) == 8 ? __builtin_popcountll(static_cast<uint64_t>(value))
38 : __builtin_popcount(static_cast<uint32_t>(value));
40 constexpr uint64_t mask[] = {0x5555555555555555, 0x3333333333333333,
41 0x0f0f0f0f0f0f0f0f, 0x00ff00ff00ff00ff,
42 0x0000ffff0000ffff, 0x00000000ffffffff};
43 value = ((value >> 1) & mask[0]) + (value & mask[0]);
44 value = ((value >> 2) & mask[1]) + (value & mask[1]);
45 value = ((value >> 4) & mask[2]) + (value & mask[2]);
47 value = ((value >> (
sizeof(T) > 1 ? 8 : 0)) & mask[3]) + (value & mask[3]);
49 value = ((value >> (
sizeof(T) > 2 ? 16 : 0)) & mask[4]) + (value & mask[4]);
51 value = ((value >> (
sizeof(T) > 4 ? 32 : 0)) & mask[5]) + (value & mask[5]);
52 return static_cast<unsigned>(value);
58 T ReverseBits(
T value) {
59 DCHECK((
sizeof(value) == 1) || (
sizeof(value) == 2) || (
sizeof(value) == 4) ||
60 (
sizeof(value) == 8));
62 for (
unsigned i = 0;
i < (
sizeof(value) * 8);
i++) {
63 result = (result << 1) | (value & 1);
72 template <
typename T,
unsigned bits = sizeof(T) * 8>
74 typename std::enable_if<std::is_unsigned<T>::value &&
sizeof(T) <= 8,
76 CountLeadingZeros(T value) {
77 static_assert(bits > 0,
"invalid instantiation");
78 #if V8_HAS_BUILTIN_CLZ 82 ? __builtin_clzll(static_cast<uint64_t>(value))
83 : __builtin_clz(static_cast<
uint32_t>(value)) - (32 - bits);
87 if (bits == 1)
return static_cast<unsigned>(value) ^ 1;
88 T upper_half = value >> (bits / 2);
89 T next_value = upper_half != 0 ? upper_half : value;
90 unsigned add = upper_half != 0 ? 0 : bits / 2;
91 constexpr
unsigned next_bits = bits == 1 ? 1 : bits / 2;
92 return CountLeadingZeros<T, next_bits>(next_value) + add;
96 inline constexpr
unsigned CountLeadingZeros32(
uint32_t value) {
97 return CountLeadingZeros(value);
99 inline constexpr
unsigned CountLeadingZeros64(uint64_t value) {
100 return CountLeadingZeros(value);
106 template <
typename T,
unsigned bits = sizeof(T) * 8>
108 typename std::enable_if<std::is_integral<T>::value &&
sizeof(T) <= 8,
110 CountTrailingZeros(T value) {
111 #if V8_HAS_BUILTIN_CTZ 112 return value == 0 ? bits
113 : bits == 64 ? __builtin_ctzll(static_cast<uint64_t>(value))
114 : __builtin_ctz(static_cast<
uint32_t>(value));
119 using U =
typename std::make_unsigned<T>::type;
121 return CountPopulation(static_cast<U>(~u & (u - 1u)));
125 inline constexpr
unsigned CountTrailingZeros32(
uint32_t value) {
126 return CountTrailingZeros(value);
128 inline constexpr
unsigned CountTrailingZeros64(uint64_t value) {
129 return CountTrailingZeros(value);
133 template <
typename T,
134 typename =
typename std::enable_if<std::is_integral<T>::value ||
135 std::is_enum<T>::value>::type>
136 constexpr
inline bool IsPowerOfTwo(T value) {
137 return value > 0 && (value & (value - 1)) == 0;
148 V8_BASE_EXPORT uint64_t RoundUpToPowerOfTwo64(uint64_t value);
150 inline size_t RoundUpToPowerOfTwo(
size_t value) {
151 if (
sizeof(
size_t) ==
sizeof(uint64_t)) {
152 return RoundUpToPowerOfTwo64(value);
154 return RoundUpToPowerOfTwo32(value);
162 if (value > 0x80000000u)
return 0x80000000u;
163 uint32_t result = RoundUpToPowerOfTwo32(value);
164 if (result > value) result >>= 1;
171 if (shift == 0)
return value;
172 return (value >> shift) | (value << (32 - shift));
177 if (shift == 0)
return value;
178 return (value << shift) | (value >> (32 - shift));
182 inline uint64_t RotateRight64(uint64_t value, uint64_t shift) {
183 if (shift == 0)
return value;
184 return (value >> shift) | (value << (64 - shift));
188 inline uint64_t RotateLeft64(uint64_t value, uint64_t shift) {
189 if (shift == 0)
return value;
190 return (value << shift) | (value >> (64 - shift));
197 inline bool SignedAddOverflow32(int32_t lhs, int32_t rhs, int32_t* val) {
198 #if V8_HAS_BUILTIN_SADD_OVERFLOW 199 return __builtin_sadd_overflow(lhs, rhs, val);
202 *val = bit_cast<int32_t>(res);
203 return ((res ^ lhs) & (res ^ rhs) & (1U << 31)) != 0;
211 inline bool SignedSubOverflow32(int32_t lhs, int32_t rhs, int32_t* val) {
212 #if V8_HAS_BUILTIN_SSUB_OVERFLOW 213 return __builtin_ssub_overflow(lhs, rhs, val);
216 *val = bit_cast<int32_t>(res);
217 return ((res ^ lhs) & (res ^ ~rhs) & (1U << 31)) != 0;
224 V8_BASE_EXPORT
bool SignedMulOverflow32(int32_t lhs, int32_t rhs, int32_t* val);
230 uint64_t res =
static_cast<uint64_t
>(lhs) + static_cast<uint64_t>(rhs);
232 return ((res ^ lhs) & (res ^ rhs) & (1ULL << 63)) != 0;
240 uint64_t res =
static_cast<uint64_t
>(lhs) - static_cast<uint64_t>(rhs);
242 return ((res ^ lhs) & (res ^ ~rhs) & (1ULL << 63)) != 0;
253 V8_BASE_EXPORT int32_t SignedMulHigh32(int32_t lhs, int32_t rhs);
258 V8_BASE_EXPORT int32_t SignedMulHighAndAdd32(int32_t lhs, int32_t rhs,
264 V8_BASE_EXPORT int32_t SignedDiv32(int32_t lhs, int32_t rhs);
269 V8_BASE_EXPORT int32_t SignedMod32(int32_t lhs, int32_t rhs);
275 #if V8_HAS_BUILTIN_SADD_OVERFLOW 276 return __builtin_uadd_overflow(lhs, rhs, val);
279 return *val < (lhs | rhs);
287 return rhs ? lhs / rhs : 0u;
294 return rhs ? lhs % rhs : 0u;
300 FromCheckedNumeric(
const internal::CheckedNumeric<int64_t> value);
314 #endif // V8_BASE_BITS_H_