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 :
10 : #include "src/base/base-export.h"
11 : #include "src/base/macros.h"
12 : #if V8_CC_MSVC
13 : #include <intrin.h>
14 : #endif
15 : #if V8_OS_WIN32
16 : #include "src/base/win32-headers.h"
17 : #endif
18 :
19 : namespace v8 {
20 : namespace base {
21 :
22 : namespace internal {
23 : template <typename T>
24 : class CheckedNumeric;
25 : }
26 :
27 : namespace bits {
28 :
29 : // CountPopulation32(value) returns the number of bits set in |value|.
30 : inline unsigned CountPopulation32(uint32_t value) {
31 : #if V8_HAS_BUILTIN_POPCOUNT
32 8679 : return __builtin_popcount(value);
33 : #else
34 : value = ((value >> 1) & 0x55555555) + (value & 0x55555555);
35 : value = ((value >> 2) & 0x33333333) + (value & 0x33333333);
36 : value = ((value >> 4) & 0x0f0f0f0f) + (value & 0x0f0f0f0f);
37 : value = ((value >> 8) & 0x00ff00ff) + (value & 0x00ff00ff);
38 : value = ((value >> 16) & 0x0000ffff) + (value & 0x0000ffff);
39 : return static_cast<unsigned>(value);
40 : #endif
41 : }
42 :
43 :
44 : // CountPopulation64(value) returns the number of bits set in |value|.
45 : inline unsigned CountPopulation64(uint64_t value) {
46 : #if V8_HAS_BUILTIN_POPCOUNT
47 247929 : return __builtin_popcountll(value);
48 : #else
49 : return CountPopulation32(static_cast<uint32_t>(value)) +
50 : CountPopulation32(static_cast<uint32_t>(value >> 32));
51 : #endif
52 : }
53 :
54 :
55 : // Overloaded versions of CountPopulation32/64.
56 : inline unsigned CountPopulation(uint32_t value) {
57 : return CountPopulation32(value);
58 : }
59 :
60 :
61 : inline unsigned CountPopulation(uint64_t value) {
62 : return CountPopulation64(value);
63 : }
64 :
65 :
66 : // CountLeadingZeros32(value) returns the number of zero bits following the most
67 : // significant 1 bit in |value| if |value| is non-zero, otherwise it returns 32.
68 69419860 : inline unsigned CountLeadingZeros32(uint32_t value) {
69 : #if V8_HAS_BUILTIN_CLZ
70 69420322 : return value ? __builtin_clz(value) : 32;
71 : #elif V8_CC_MSVC
72 : unsigned long result; // NOLINT(runtime/int)
73 : if (!_BitScanReverse(&result, value)) return 32;
74 : return static_cast<unsigned>(31 - result);
75 : #else
76 : value = value | (value >> 1);
77 : value = value | (value >> 2);
78 : value = value | (value >> 4);
79 : value = value | (value >> 8);
80 : value = value | (value >> 16);
81 : return CountPopulation32(~value);
82 : #endif
83 : }
84 :
85 :
86 : // CountLeadingZeros64(value) returns the number of zero bits following the most
87 : // significant 1 bit in |value| if |value| is non-zero, otherwise it returns 64.
88 : inline unsigned CountLeadingZeros64(uint64_t value) {
89 : #if V8_HAS_BUILTIN_CLZ
90 2348621 : return value ? __builtin_clzll(value) : 64;
91 : #else
92 : value = value | (value >> 1);
93 : value = value | (value >> 2);
94 : value = value | (value >> 4);
95 : value = value | (value >> 8);
96 : value = value | (value >> 16);
97 : value = value | (value >> 32);
98 : return CountPopulation64(~value);
99 : #endif
100 : }
101 :
102 :
103 : // ReverseBits(value) returns |value| in reverse bit order.
104 : template <typename T>
105 : T ReverseBits(T value) {
106 : DCHECK((sizeof(value) == 1) || (sizeof(value) == 2) || (sizeof(value) == 4) ||
107 : (sizeof(value) == 8));
108 : T result = 0;
109 : for (unsigned i = 0; i < (sizeof(value) * 8); i++) {
110 : result = (result << 1) | (value & 1);
111 : value >>= 1;
112 : }
113 : return result;
114 : }
115 :
116 : // CountTrailingZeros32(value) returns the number of zero bits preceding the
117 : // least significant 1 bit in |value| if |value| is non-zero, otherwise it
118 : // returns 32.
119 : inline unsigned CountTrailingZeros32(uint32_t value) {
120 : #if V8_HAS_BUILTIN_CTZ
121 884281361 : return value ? __builtin_ctz(value) : 32;
122 : #elif V8_CC_MSVC
123 : unsigned long result; // NOLINT(runtime/int)
124 : if (!_BitScanForward(&result, value)) return 32;
125 : return static_cast<unsigned>(result);
126 : #else
127 : if (value == 0) return 32;
128 : unsigned count = 0;
129 : for (value ^= value - 1; value >>= 1; ++count) {
130 : }
131 : return count;
132 : #endif
133 : }
134 :
135 :
136 : // CountTrailingZeros64(value) returns the number of zero bits preceding the
137 : // least significant 1 bit in |value| if |value| is non-zero, otherwise it
138 : // returns 64.
139 : inline unsigned CountTrailingZeros64(uint64_t value) {
140 : #if V8_HAS_BUILTIN_CTZ
141 2348635 : return value ? __builtin_ctzll(value) : 64;
142 : #else
143 : if (value == 0) return 64;
144 : unsigned count = 0;
145 : for (value ^= value - 1; value >>= 1; ++count) {
146 : }
147 : return count;
148 : #endif
149 : }
150 :
151 : // Overloaded versions of CountTrailingZeros32/64.
152 : inline unsigned CountTrailingZeros(uint32_t value) {
153 : return CountTrailingZeros32(value);
154 : }
155 :
156 : inline unsigned CountTrailingZeros(uint64_t value) {
157 : return CountTrailingZeros64(value);
158 : }
159 :
160 : // Returns true iff |value| is a power of 2.
161 : inline bool IsPowerOfTwo32(uint32_t value) {
162 325908 : return value && !(value & (value - 1));
163 : }
164 :
165 :
166 : // Returns true iff |value| is a power of 2.
167 : inline bool IsPowerOfTwo64(uint64_t value) {
168 12659 : return value && !(value & (value - 1));
169 : }
170 :
171 :
172 : // RoundUpToPowerOfTwo32(value) returns the smallest power of two which is
173 : // greater than or equal to |value|. If you pass in a |value| that is already a
174 : // power of two, it is returned as is. |value| must be less than or equal to
175 : // 0x80000000u. Implementation is from "Hacker's Delight" by Henry S. Warren,
176 : // Jr., figure 3-3, page 48, where the function is called clp2.
177 : V8_BASE_EXPORT uint32_t RoundUpToPowerOfTwo32(uint32_t value);
178 :
179 : // RoundDownToPowerOfTwo32(value) returns the greatest power of two which is
180 : // less than or equal to |value|. If you pass in a |value| that is already a
181 : // power of two, it is returned as is.
182 : inline uint32_t RoundDownToPowerOfTwo32(uint32_t value) {
183 : if (value > 0x80000000u) return 0x80000000u;
184 : uint32_t result = RoundUpToPowerOfTwo32(value);
185 : if (result > value) result >>= 1;
186 : return result;
187 : }
188 :
189 :
190 : // Precondition: 0 <= shift < 32
191 : inline uint32_t RotateRight32(uint32_t value, uint32_t shift) {
192 1516 : if (shift == 0) return value;
193 1516 : return (value >> shift) | (value << (32 - shift));
194 : }
195 :
196 : // Precondition: 0 <= shift < 32
197 : inline uint32_t RotateLeft32(uint32_t value, uint32_t shift) {
198 : if (shift == 0) return value;
199 : return (value << shift) | (value >> (32 - shift));
200 : }
201 :
202 : // Precondition: 0 <= shift < 64
203 : inline uint64_t RotateRight64(uint64_t value, uint64_t shift) {
204 : if (shift == 0) return value;
205 : return (value >> shift) | (value << (64 - shift));
206 : }
207 :
208 : // Precondition: 0 <= shift < 64
209 : inline uint64_t RotateLeft64(uint64_t value, uint64_t shift) {
210 : if (shift == 0) return value;
211 : return (value << shift) | (value >> (64 - shift));
212 : }
213 :
214 :
215 : // SignedAddOverflow32(lhs,rhs,val) performs a signed summation of |lhs| and
216 : // |rhs| and stores the result into the variable pointed to by |val| and
217 : // returns true if the signed summation resulted in an overflow.
218 : inline bool SignedAddOverflow32(int32_t lhs, int32_t rhs, int32_t* val) {
219 : #if V8_HAS_BUILTIN_SADD_OVERFLOW
220 : return __builtin_sadd_overflow(lhs, rhs, val);
221 : #else
222 20038 : uint32_t res = static_cast<uint32_t>(lhs) + static_cast<uint32_t>(rhs);
223 : *val = bit_cast<int32_t>(res);
224 20038 : return ((res ^ lhs) & (res ^ rhs) & (1U << 31)) != 0;
225 : #endif
226 : }
227 :
228 :
229 : // SignedSubOverflow32(lhs,rhs,val) performs a signed subtraction of |lhs| and
230 : // |rhs| and stores the result into the variable pointed to by |val| and
231 : // returns true if the signed subtraction resulted in an overflow.
232 : inline bool SignedSubOverflow32(int32_t lhs, int32_t rhs, int32_t* val) {
233 : #if V8_HAS_BUILTIN_SSUB_OVERFLOW
234 : return __builtin_ssub_overflow(lhs, rhs, val);
235 : #else
236 20024 : uint32_t res = static_cast<uint32_t>(lhs) - static_cast<uint32_t>(rhs);
237 : *val = bit_cast<int32_t>(res);
238 20024 : return ((res ^ lhs) & (res ^ ~rhs) & (1U << 31)) != 0;
239 : #endif
240 : }
241 :
242 : // SignedMulOverflow32(lhs,rhs,val) performs a signed multiplication of |lhs|
243 : // and |rhs| and stores the result into the variable pointed to by |val| and
244 : // returns true if the signed multiplication resulted in an overflow.
245 : V8_BASE_EXPORT bool SignedMulOverflow32(int32_t lhs, int32_t rhs, int32_t* val);
246 :
247 : // SignedAddOverflow64(lhs,rhs,val) performs a signed summation of |lhs| and
248 : // |rhs| and stores the result into the variable pointed to by |val| and
249 : // returns true if the signed summation resulted in an overflow.
250 : inline bool SignedAddOverflow64(int64_t lhs, int64_t rhs, int64_t* val) {
251 : uint64_t res = static_cast<uint64_t>(lhs) + static_cast<uint64_t>(rhs);
252 : *val = bit_cast<int64_t>(res);
253 : return ((res ^ lhs) & (res ^ rhs) & (1ULL << 63)) != 0;
254 : }
255 :
256 :
257 : // SignedSubOverflow64(lhs,rhs,val) performs a signed subtraction of |lhs| and
258 : // |rhs| and stores the result into the variable pointed to by |val| and
259 : // returns true if the signed subtraction resulted in an overflow.
260 : inline bool SignedSubOverflow64(int64_t lhs, int64_t rhs, int64_t* val) {
261 : uint64_t res = static_cast<uint64_t>(lhs) - static_cast<uint64_t>(rhs);
262 : *val = bit_cast<int64_t>(res);
263 : return ((res ^ lhs) & (res ^ ~rhs) & (1ULL << 63)) != 0;
264 : }
265 :
266 : // SignedMulOverflow64(lhs,rhs,val) performs a signed multiplication of |lhs|
267 : // and |rhs| and stores the result into the variable pointed to by |val| and
268 : // returns true if the signed multiplication resulted in an overflow.
269 : V8_BASE_EXPORT bool SignedMulOverflow64(int64_t lhs, int64_t rhs, int64_t* val);
270 :
271 : // SignedMulHigh32(lhs, rhs) multiplies two signed 32-bit values |lhs| and
272 : // |rhs|, extracts the most significant 32 bits of the result, and returns
273 : // those.
274 : V8_BASE_EXPORT int32_t SignedMulHigh32(int32_t lhs, int32_t rhs);
275 :
276 : // SignedMulHighAndAdd32(lhs, rhs, acc) multiplies two signed 32-bit values
277 : // |lhs| and |rhs|, extracts the most significant 32 bits of the result, and
278 : // adds the accumulate value |acc|.
279 : V8_BASE_EXPORT int32_t SignedMulHighAndAdd32(int32_t lhs, int32_t rhs,
280 : int32_t acc);
281 :
282 : // SignedDiv32(lhs, rhs) divides |lhs| by |rhs| and returns the quotient
283 : // truncated to int32. If |rhs| is zero, then zero is returned. If |lhs|
284 : // is minint and |rhs| is -1, it returns minint.
285 : V8_BASE_EXPORT int32_t SignedDiv32(int32_t lhs, int32_t rhs);
286 :
287 : // SignedMod32(lhs, rhs) divides |lhs| by |rhs| and returns the remainder
288 : // truncated to int32. If either |rhs| is zero or |lhs| is minint and |rhs|
289 : // is -1, it returns zero.
290 : V8_BASE_EXPORT int32_t SignedMod32(int32_t lhs, int32_t rhs);
291 :
292 : // UnsignedAddOverflow32(lhs,rhs,val) performs an unsigned summation of |lhs|
293 : // and |rhs| and stores the result into the variable pointed to by |val| and
294 : // returns true if the unsigned summation resulted in an overflow.
295 : inline bool UnsignedAddOverflow32(uint32_t lhs, uint32_t rhs, uint32_t* val) {
296 : #if V8_HAS_BUILTIN_SADD_OVERFLOW
297 : return __builtin_uadd_overflow(lhs, rhs, val);
298 : #else
299 112379445 : *val = lhs + rhs;
300 112379445 : return *val < (lhs | rhs);
301 : #endif
302 : }
303 :
304 :
305 : // UnsignedDiv32(lhs, rhs) divides |lhs| by |rhs| and returns the quotient
306 : // truncated to uint32. If |rhs| is zero, then zero is returned.
307 : inline uint32_t UnsignedDiv32(uint32_t lhs, uint32_t rhs) {
308 21516 : return rhs ? lhs / rhs : 0u;
309 : }
310 :
311 :
312 : // UnsignedMod32(lhs, rhs) divides |lhs| by |rhs| and returns the remainder
313 : // truncated to uint32. If |rhs| is zero, then zero is returned.
314 : inline uint32_t UnsignedMod32(uint32_t lhs, uint32_t rhs) {
315 21526 : return rhs ? lhs % rhs : 0u;
316 : }
317 :
318 :
319 : // Clamp |value| on overflow and underflow conditions.
320 : V8_BASE_EXPORT int64_t
321 : FromCheckedNumeric(const internal::CheckedNumeric<int64_t> value);
322 :
323 : // SignedSaturatedAdd64(lhs, rhs) adds |lhs| and |rhs|,
324 : // checks and returns the result.
325 : V8_BASE_EXPORT int64_t SignedSaturatedAdd64(int64_t lhs, int64_t rhs);
326 :
327 : // SignedSaturatedSub64(lhs, rhs) substracts |lhs| by |rhs|,
328 : // checks and returns the result.
329 : V8_BASE_EXPORT int64_t SignedSaturatedSub64(int64_t lhs, int64_t rhs);
330 :
331 : } // namespace bits
332 : } // namespace base
333 : } // namespace v8
334 :
335 : #endif // V8_BASE_BITS_H_
|
