Line data Source code
1 : // Copyright 2014 the V8 project authors. All rights reserved.
2 : // Use of this source code is governed by a BSD-style license that can be
3 : // found in the LICENSE file.
4 :
5 : #ifndef V8_BASE_BITS_H_
6 : #define V8_BASE_BITS_H_
7 :
8 : #include <stdint.h>
9 : #include <type_traits>
10 :
11 : #include "src/base/base-export.h"
12 : #include "src/base/macros.h"
13 : #if V8_CC_MSVC
14 : #include <intrin.h>
15 : #endif
16 : #if V8_OS_WIN32
17 : #include "src/base/win32-headers.h"
18 : #endif
19 :
20 : namespace v8 {
21 : namespace base {
22 :
23 : namespace internal {
24 : template <typename T>
25 : class CheckedNumeric;
26 : }
27 :
28 : namespace bits {
29 :
30 : // Define overloaded |Name| for |Name32| and |Name64|, depending on the size of
31 : // the given value.
32 : //
33 : // The overloads are only defined for input types of size 4 and 8, respectively,
34 : // using enable_if and SFINAE to disable them otherwise. enable_if<bool,
35 : // typename> only has a "type" member if the first parameter is true, in which
36 : // case "type" is a typedef to the second member (here, set to "unsigned").
37 : // Otherwise, enable_if::type doesn't exist, making the function signature
38 : // invalid, and so the entire function is thrown away (without an error) due to
39 : // SFINAE.
40 : //
41 : // Not that we cannot simply check sizeof(T) using an if statement, as we need
42 : // both branches of the if to be syntactically valid even if one of the branches
43 : // is dead.
44 : #define DEFINE_32_64_OVERLOADS(Name) \
45 : template <typename T> \
46 : inline typename std::enable_if<sizeof(T) == 4, unsigned>::type Name( \
47 : T value) { \
48 : return Name##32(value); \
49 : } \
50 : \
51 : template <typename T> \
52 : inline typename std::enable_if<sizeof(T) == 8, unsigned>::type Name( \
53 : T value) { \
54 : return Name##64(value); \
55 : }
56 :
57 : // CountPopulation(value) returns the number of bits set in |value|.
58 : template <typename T>
59 : constexpr inline
60 : typename std::enable_if<std::is_unsigned<T>::value && sizeof(T) <= 8,
61 : unsigned>::type
62 : CountPopulation(T value) {
63 : #if V8_HAS_BUILTIN_POPCOUNT
64 334572 : return sizeof(T) == 8 ? __builtin_popcountll(static_cast<uint64_t>(value))
65 475842 : : __builtin_popcount(static_cast<uint32_t>(value));
66 : #else
67 : constexpr uint64_t mask[] = {0x5555555555555555, 0x3333333333333333,
68 : 0x0f0f0f0f0f0f0f0f, 0x00ff00ff00ff00ff,
69 : 0x0000ffff0000ffff, 0x00000000ffffffff};
70 : value = ((value >> 1) & mask[0]) + (value & mask[0]);
71 : value = ((value >> 2) & mask[1]) + (value & mask[1]);
72 : value = ((value >> 4) & mask[2]) + (value & mask[2]);
73 : if (sizeof(T) > 1)
74 : value = ((value >> (sizeof(T) > 1 ? 8 : 0)) & mask[3]) + (value & mask[3]);
75 : if (sizeof(T) > 2)
76 : value = ((value >> (sizeof(T) > 2 ? 16 : 0)) & mask[4]) + (value & mask[4]);
77 : if (sizeof(T) > 4)
78 : value = ((value >> (sizeof(T) > 4 ? 32 : 0)) & mask[5]) + (value & mask[5]);
79 : return static_cast<unsigned>(value);
80 : #endif
81 : }
82 :
83 : // CountLeadingZeros32(value) returns the number of zero bits following the most
84 : // significant 1 bit in |value| if |value| is non-zero, otherwise it returns 32.
85 47494242 : inline unsigned CountLeadingZeros32(uint32_t value) {
86 : #if V8_HAS_BUILTIN_CLZ
87 55813398 : return value ? __builtin_clz(value) : 32;
88 : #elif V8_CC_MSVC
89 : unsigned long result; // NOLINT(runtime/int)
90 : if (!_BitScanReverse(&result, value)) return 32;
91 : return static_cast<unsigned>(31 - result);
92 : #else
93 : value = value | (value >> 1);
94 : value = value | (value >> 2);
95 : value = value | (value >> 4);
96 : value = value | (value >> 8);
97 : value = value | (value >> 16);
98 : return CountPopulation(~value);
99 : #endif
100 : }
101 :
102 :
103 : // CountLeadingZeros64(value) returns the number of zero bits following the most
104 : // significant 1 bit in |value| if |value| is non-zero, otherwise it returns 64.
105 : inline unsigned CountLeadingZeros64(uint64_t value) {
106 : #if V8_HAS_BUILTIN_CLZ
107 565068 : return value ? __builtin_clzll(value) : 64;
108 : #else
109 : value = value | (value >> 1);
110 : value = value | (value >> 2);
111 : value = value | (value >> 4);
112 : value = value | (value >> 8);
113 : value = value | (value >> 16);
114 : value = value | (value >> 32);
115 : return CountPopulation(~value);
116 : #endif
117 : }
118 :
119 : DEFINE_32_64_OVERLOADS(CountLeadingZeros)
120 :
121 : // ReverseBits(value) returns |value| in reverse bit order.
122 : template <typename T>
123 : T ReverseBits(T value) {
124 : DCHECK((sizeof(value) == 1) || (sizeof(value) == 2) || (sizeof(value) == 4) ||
125 : (sizeof(value) == 8));
126 : T result = 0;
127 : for (unsigned i = 0; i < (sizeof(value) * 8); i++) {
128 : result = (result << 1) | (value & 1);
129 : value >>= 1;
130 : }
131 : return result;
132 : }
133 :
134 : // CountTrailingZeros32(value) returns the number of zero bits preceding the
135 : // least significant 1 bit in |value| if |value| is non-zero, otherwise it
136 : // returns 32.
137 : inline unsigned CountTrailingZeros32(uint32_t value) {
138 : #if V8_HAS_BUILTIN_CTZ
139 721663023 : return value ? __builtin_ctz(value) : 32;
140 : #elif V8_CC_MSVC
141 : unsigned long result; // NOLINT(runtime/int)
142 : if (!_BitScanForward(&result, value)) return 32;
143 : return static_cast<unsigned>(result);
144 : #else
145 : if (value == 0) return 32;
146 : unsigned count = 0;
147 : for (value ^= value - 1; value >>= 1; ++count) {
148 : }
149 : return count;
150 : #endif
151 : }
152 :
153 :
154 : // CountTrailingZeros64(value) returns the number of zero bits preceding the
155 : // least significant 1 bit in |value| if |value| is non-zero, otherwise it
156 : // returns 64.
157 : inline unsigned CountTrailingZeros64(uint64_t value) {
158 : #if V8_HAS_BUILTIN_CTZ
159 434715 : return value ? __builtin_ctzll(value) : 64;
160 : #else
161 : if (value == 0) return 64;
162 : unsigned count = 0;
163 : for (value ^= value - 1; value >>= 1; ++count) {
164 : }
165 : return count;
166 : #endif
167 : }
168 :
169 : DEFINE_32_64_OVERLOADS(CountTrailingZeros)
170 :
171 : // Returns true iff |value| is a power of 2.
172 : template <typename T,
173 : typename = typename std::enable_if<std::is_integral<T>::value>::type>
174 : constexpr inline bool IsPowerOfTwo(T value) {
175 68850849 : return value > 0 && (value & (value - 1)) == 0;
176 : }
177 :
178 : // RoundUpToPowerOfTwo32(value) returns the smallest power of two which is
179 : // greater than or equal to |value|. If you pass in a |value| that is already a
180 : // power of two, it is returned as is. |value| must be less than or equal to
181 : // 0x80000000u. Uses computation based on leading zeros if we have compiler
182 : // support for that. Falls back to the implementation from "Hacker's Delight" by
183 : // Henry S. Warren, Jr., figure 3-3, page 48, where the function is called clp2.
184 : V8_BASE_EXPORT uint32_t RoundUpToPowerOfTwo32(uint32_t value);
185 : // Same for 64 bit integers. |value| must be <= 2^63
186 : V8_BASE_EXPORT uint64_t RoundUpToPowerOfTwo64(uint64_t value);
187 :
188 : // RoundDownToPowerOfTwo32(value) returns the greatest power of two which is
189 : // less than or equal to |value|. If you pass in a |value| that is already a
190 : // power of two, it is returned as is.
191 : inline uint32_t RoundDownToPowerOfTwo32(uint32_t value) {
192 32 : if (value > 0x80000000u) return 0x80000000u;
193 34 : uint32_t result = RoundUpToPowerOfTwo32(value);
194 34 : if (result > value) result >>= 1;
195 : return result;
196 : }
197 :
198 :
199 : // Precondition: 0 <= shift < 32
200 : inline uint32_t RotateRight32(uint32_t value, uint32_t shift) {
201 58704 : if (shift == 0) return value;
202 56916 : return (value >> shift) | (value << (32 - shift));
203 : }
204 :
205 : // Precondition: 0 <= shift < 32
206 : inline uint32_t RotateLeft32(uint32_t value, uint32_t shift) {
207 : if (shift == 0) return value;
208 : return (value << shift) | (value >> (32 - shift));
209 : }
210 :
211 : // Precondition: 0 <= shift < 64
212 : inline uint64_t RotateRight64(uint64_t value, uint64_t shift) {
213 78732 : if (shift == 0) return value;
214 59292 : return (value >> shift) | (value << (64 - shift));
215 : }
216 :
217 : // Precondition: 0 <= shift < 64
218 : inline uint64_t RotateLeft64(uint64_t value, uint64_t shift) {
219 78732 : if (shift == 0) return value;
220 59292 : return (value << shift) | (value >> (64 - shift));
221 : }
222 :
223 :
224 : // SignedAddOverflow32(lhs,rhs,val) performs a signed summation of |lhs| and
225 : // |rhs| and stores the result into the variable pointed to by |val| and
226 : // returns true if the signed summation resulted in an overflow.
227 : inline bool SignedAddOverflow32(int32_t lhs, int32_t rhs, int32_t* val) {
228 : #if V8_HAS_BUILTIN_SADD_OVERFLOW
229 : return __builtin_sadd_overflow(lhs, rhs, val);
230 : #else
231 115391 : uint32_t res = static_cast<uint32_t>(lhs) + static_cast<uint32_t>(rhs);
232 1278 : *val = bit_cast<int32_t>(res);
233 115391 : return ((res ^ lhs) & (res ^ rhs) & (1U << 31)) != 0;
234 : #endif
235 : }
236 :
237 :
238 : // SignedSubOverflow32(lhs,rhs,val) performs a signed subtraction of |lhs| and
239 : // |rhs| and stores the result into the variable pointed to by |val| and
240 : // returns true if the signed subtraction resulted in an overflow.
241 : inline bool SignedSubOverflow32(int32_t lhs, int32_t rhs, int32_t* val) {
242 : #if V8_HAS_BUILTIN_SSUB_OVERFLOW
243 : return __builtin_ssub_overflow(lhs, rhs, val);
244 : #else
245 115417 : uint32_t res = static_cast<uint32_t>(lhs) - static_cast<uint32_t>(rhs);
246 1277 : *val = bit_cast<int32_t>(res);
247 115417 : return ((res ^ lhs) & (res ^ ~rhs) & (1U << 31)) != 0;
248 : #endif
249 : }
250 :
251 : // SignedMulOverflow32(lhs,rhs,val) performs a signed multiplication of |lhs|
252 : // and |rhs| and stores the result into the variable pointed to by |val| and
253 : // returns true if the signed multiplication resulted in an overflow.
254 : V8_BASE_EXPORT bool SignedMulOverflow32(int32_t lhs, int32_t rhs, int32_t* val);
255 :
256 : // SignedAddOverflow64(lhs,rhs,val) performs a signed summation of |lhs| and
257 : // |rhs| and stores the result into the variable pointed to by |val| and
258 : // returns true if the signed summation resulted in an overflow.
259 : inline bool SignedAddOverflow64(int64_t lhs, int64_t rhs, int64_t* val) {
260 164025 : uint64_t res = static_cast<uint64_t>(lhs) + static_cast<uint64_t>(rhs);
261 : *val = bit_cast<int64_t>(res);
262 164025 : return ((res ^ lhs) & (res ^ rhs) & (1ULL << 63)) != 0;
263 : }
264 :
265 :
266 : // SignedSubOverflow64(lhs,rhs,val) performs a signed subtraction of |lhs| and
267 : // |rhs| and stores the result into the variable pointed to by |val| and
268 : // returns true if the signed subtraction resulted in an overflow.
269 : inline bool SignedSubOverflow64(int64_t lhs, int64_t rhs, int64_t* val) {
270 164025 : uint64_t res = static_cast<uint64_t>(lhs) - static_cast<uint64_t>(rhs);
271 : *val = bit_cast<int64_t>(res);
272 164025 : return ((res ^ lhs) & (res ^ ~rhs) & (1ULL << 63)) != 0;
273 : }
274 :
275 : // SignedMulOverflow64(lhs,rhs,val) performs a signed multiplication of |lhs|
276 : // and |rhs| and stores the result into the variable pointed to by |val| and
277 : // returns true if the signed multiplication resulted in an overflow.
278 : V8_BASE_EXPORT bool SignedMulOverflow64(int64_t lhs, int64_t rhs, int64_t* val);
279 :
280 : // SignedMulHigh32(lhs, rhs) multiplies two signed 32-bit values |lhs| and
281 : // |rhs|, extracts the most significant 32 bits of the result, and returns
282 : // those.
283 : V8_BASE_EXPORT int32_t SignedMulHigh32(int32_t lhs, int32_t rhs);
284 :
285 : // SignedMulHighAndAdd32(lhs, rhs, acc) multiplies two signed 32-bit values
286 : // |lhs| and |rhs|, extracts the most significant 32 bits of the result, and
287 : // adds the accumulate value |acc|.
288 : V8_BASE_EXPORT int32_t SignedMulHighAndAdd32(int32_t lhs, int32_t rhs,
289 : int32_t acc);
290 :
291 : // SignedDiv32(lhs, rhs) divides |lhs| by |rhs| and returns the quotient
292 : // truncated to int32. If |rhs| is zero, then zero is returned. If |lhs|
293 : // is minint and |rhs| is -1, it returns minint.
294 : V8_BASE_EXPORT int32_t SignedDiv32(int32_t lhs, int32_t rhs);
295 :
296 : // SignedMod32(lhs, rhs) divides |lhs| by |rhs| and returns the remainder
297 : // truncated to int32. If either |rhs| is zero or |lhs| is minint and |rhs|
298 : // is -1, it returns zero.
299 : V8_BASE_EXPORT int32_t SignedMod32(int32_t lhs, int32_t rhs);
300 :
301 : // UnsignedAddOverflow32(lhs,rhs,val) performs an unsigned summation of |lhs|
302 : // and |rhs| and stores the result into the variable pointed to by |val| and
303 : // returns true if the unsigned summation resulted in an overflow.
304 : inline bool UnsignedAddOverflow32(uint32_t lhs, uint32_t rhs, uint32_t* val) {
305 : #if V8_HAS_BUILTIN_SADD_OVERFLOW
306 : return __builtin_uadd_overflow(lhs, rhs, val);
307 : #else
308 111349020 : *val = lhs + rhs;
309 111349018 : return *val < (lhs | rhs);
310 : #endif
311 : }
312 :
313 :
314 : // UnsignedDiv32(lhs, rhs) divides |lhs| by |rhs| and returns the quotient
315 : // truncated to uint32. If |rhs| is zero, then zero is returned.
316 : inline uint32_t UnsignedDiv32(uint32_t lhs, uint32_t rhs) {
317 31294 : return rhs ? lhs / rhs : 0u;
318 : }
319 :
320 :
321 : // UnsignedMod32(lhs, rhs) divides |lhs| by |rhs| and returns the remainder
322 : // truncated to uint32. If |rhs| is zero, then zero is returned.
323 : inline uint32_t UnsignedMod32(uint32_t lhs, uint32_t rhs) {
324 31336 : return rhs ? lhs % rhs : 0u;
325 : }
326 :
327 :
328 : // Clamp |value| on overflow and underflow conditions.
329 : V8_BASE_EXPORT int64_t
330 : FromCheckedNumeric(const internal::CheckedNumeric<int64_t> value);
331 :
332 : // SignedSaturatedAdd64(lhs, rhs) adds |lhs| and |rhs|,
333 : // checks and returns the result.
334 : V8_BASE_EXPORT int64_t SignedSaturatedAdd64(int64_t lhs, int64_t rhs);
335 :
336 : // SignedSaturatedSub64(lhs, rhs) subtracts |lhs| by |rhs|,
337 : // checks and returns the result.
338 : V8_BASE_EXPORT int64_t SignedSaturatedSub64(int64_t lhs, int64_t rhs);
339 :
340 : #undef DEFINE_32_64_OVERLOADS
341 :
342 : } // namespace bits
343 : } // namespace base
344 : } // namespace v8
345 :
346 : #endif // V8_BASE_BITS_H_
|
