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 : // CountPopulation(value) returns the number of bits set in |value|.
31 : template <typename T>
32 : constexpr inline
33 : typename std::enable_if<std::is_unsigned<T>::value && sizeof(T) <= 8,
34 : unsigned>::type
35 : CountPopulation(T value) {
36 : #if V8_HAS_BUILTIN_POPCOUNT
37 352298 : return sizeof(T) == 8 ? __builtin_popcountll(static_cast<uint64_t>(value))
38 4350038 : : __builtin_popcount(static_cast<uint32_t>(value));
39 : #else
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]);
46 : if (sizeof(T) > 1)
47 : value = ((value >> (sizeof(T) > 1 ? 8 : 0)) & mask[3]) + (value & mask[3]);
48 : if (sizeof(T) > 2)
49 : value = ((value >> (sizeof(T) > 2 ? 16 : 0)) & mask[4]) + (value & mask[4]);
50 : if (sizeof(T) > 4)
51 : value = ((value >> (sizeof(T) > 4 ? 32 : 0)) & mask[5]) + (value & mask[5]);
52 : return static_cast<unsigned>(value);
53 : #endif
54 : }
55 :
56 : // ReverseBits(value) returns |value| in reverse bit order.
57 : template <typename T>
58 : T ReverseBits(T value) {
59 : DCHECK((sizeof(value) == 1) || (sizeof(value) == 2) || (sizeof(value) == 4) ||
60 : (sizeof(value) == 8));
61 : T result = 0;
62 : for (unsigned i = 0; i < (sizeof(value) * 8); i++) {
63 : result = (result << 1) | (value & 1);
64 : value >>= 1;
65 : }
66 : return result;
67 : }
68 :
69 : // CountLeadingZeros(value) returns the number of zero bits following the most
70 : // significant 1 bit in |value| if |value| is non-zero, otherwise it returns
71 : // {sizeof(T) * 8}.
72 : template <typename T, unsigned bits = sizeof(T) * 8>
73 : inline constexpr
74 : typename std::enable_if<std::is_unsigned<T>::value && sizeof(T) <= 8,
75 : unsigned>::type
76 : CountLeadingZeros(T value) {
77 : static_assert(bits > 0, "invalid instantiation");
78 : #if V8_HAS_BUILTIN_CLZ
79 : return value == 0
80 : ? bits
81 : : bits == 64
82 1159636 : ? __builtin_clzll(static_cast<uint64_t>(value))
83 13194622 : : __builtin_clz(static_cast<uint32_t>(value)) - (32 - bits);
84 : #else
85 : // Binary search algorithm taken from "Hacker's Delight" (by Henry S. Warren,
86 : // Jr.), figures 5-11 and 5-12.
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;
93 : #endif
94 : }
95 :
96 : inline constexpr unsigned CountLeadingZeros32(uint32_t value) {
97 : return CountLeadingZeros(value);
98 : }
99 : inline constexpr unsigned CountLeadingZeros64(uint64_t value) {
100 : return CountLeadingZeros(value);
101 : }
102 :
103 : // CountTrailingZeros(value) returns the number of zero bits preceding the
104 : // least significant 1 bit in |value| if |value| is non-zero, otherwise it
105 : // returns {sizeof(T) * 8}.
106 : template <typename T, unsigned bits = sizeof(T) * 8>
107 : inline constexpr
108 : typename std::enable_if<std::is_integral<T>::value && sizeof(T) <= 8,
109 : unsigned>::type
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 874252275 : : __builtin_ctz(static_cast<uint32_t>(value));
115 : #else
116 : // Fall back to popcount (see "Hacker's Delight" by Henry S. Warren, Jr.),
117 : // chapter 5-4. On x64, since is faster than counting in a loop and faster
118 : // than doing binary search.
119 : using U = typename std::make_unsigned<T>::type;
120 : U u = value;
121 : return CountPopulation(static_cast<U>(~u & (u - 1u)));
122 : #endif
123 : }
124 :
125 : inline constexpr unsigned CountTrailingZeros32(uint32_t value) {
126 : return CountTrailingZeros(value);
127 : }
128 : inline constexpr unsigned CountTrailingZeros64(uint64_t value) {
129 : return CountTrailingZeros(value);
130 : }
131 :
132 : // Returns true iff |value| is a power of 2.
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 55915021 : return value > 0 && (value & (value - 1)) == 0;
138 : }
139 :
140 : // RoundUpToPowerOfTwo32(value) returns the smallest power of two which is
141 : // greater than or equal to |value|. If you pass in a |value| that is already a
142 : // power of two, it is returned as is. |value| must be less than or equal to
143 : // 0x80000000u. Uses computation based on leading zeros if we have compiler
144 : // support for that. Falls back to the implementation from "Hacker's Delight" by
145 : // Henry S. Warren, Jr., figure 3-3, page 48, where the function is called clp2.
146 : V8_BASE_EXPORT uint32_t RoundUpToPowerOfTwo32(uint32_t value);
147 : // Same for 64 bit integers. |value| must be <= 2^63
148 : V8_BASE_EXPORT uint64_t RoundUpToPowerOfTwo64(uint64_t value);
149 : // Same for size_t integers.
150 : inline size_t RoundUpToPowerOfTwo(size_t value) {
151 : if (sizeof(size_t) == sizeof(uint64_t)) {
152 20288 : return RoundUpToPowerOfTwo64(value);
153 : } else {
154 : return RoundUpToPowerOfTwo32(value);
155 : }
156 : }
157 :
158 : // RoundDownToPowerOfTwo32(value) returns the greatest power of two which is
159 : // less than or equal to |value|. If you pass in a |value| that is already a
160 : // power of two, it is returned as is.
161 : inline uint32_t RoundDownToPowerOfTwo32(uint32_t value) {
162 32 : if (value > 0x80000000u) return 0x80000000u;
163 34 : uint32_t result = RoundUpToPowerOfTwo32(value);
164 34 : if (result > value) result >>= 1;
165 : return result;
166 : }
167 :
168 :
169 : // Precondition: 0 <= shift < 32
170 : inline uint32_t RotateRight32(uint32_t value, uint32_t shift) {
171 58704 : if (shift == 0) return value;
172 56916 : return (value >> shift) | (value << (32 - shift));
173 : }
174 :
175 : // Precondition: 0 <= shift < 32
176 : inline uint32_t RotateLeft32(uint32_t value, uint32_t shift) {
177 1020 : if (shift == 0) return value;
178 975 : return (value << shift) | (value >> (32 - shift));
179 : }
180 :
181 : // Precondition: 0 <= shift < 64
182 : inline uint64_t RotateRight64(uint64_t value, uint64_t shift) {
183 98415 : if (shift == 0) return value;
184 74115 : return (value >> shift) | (value << (64 - shift));
185 : }
186 :
187 : // Precondition: 0 <= shift < 64
188 : inline uint64_t RotateLeft64(uint64_t value, uint64_t shift) {
189 99690 : if (shift == 0) return value;
190 75330 : return (value << shift) | (value >> (64 - shift));
191 : }
192 :
193 :
194 : // SignedAddOverflow32(lhs,rhs,val) performs a signed summation of |lhs| and
195 : // |rhs| and stores the result into the variable pointed to by |val| and
196 : // returns true if the signed summation resulted in an overflow.
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);
200 : #else
201 38938017 : uint32_t res = static_cast<uint32_t>(lhs) + static_cast<uint32_t>(rhs);
202 1278 : *val = bit_cast<int32_t>(res);
203 38938017 : return ((res ^ lhs) & (res ^ rhs) & (1U << 31)) != 0;
204 : #endif
205 : }
206 :
207 :
208 : // SignedSubOverflow32(lhs,rhs,val) performs a signed subtraction of |lhs| and
209 : // |rhs| and stores the result into the variable pointed to by |val| and
210 : // returns true if the signed subtraction resulted in an overflow.
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);
214 : #else
215 115431 : uint32_t res = static_cast<uint32_t>(lhs) - static_cast<uint32_t>(rhs);
216 1277 : *val = bit_cast<int32_t>(res);
217 115431 : return ((res ^ lhs) & (res ^ ~rhs) & (1U << 31)) != 0;
218 : #endif
219 : }
220 :
221 : // SignedMulOverflow32(lhs,rhs,val) performs a signed multiplication of |lhs|
222 : // and |rhs| and stores the result into the variable pointed to by |val| and
223 : // returns true if the signed multiplication resulted in an overflow.
224 : V8_BASE_EXPORT bool SignedMulOverflow32(int32_t lhs, int32_t rhs, int32_t* val);
225 :
226 : // SignedAddOverflow64(lhs,rhs,val) performs a signed summation of |lhs| and
227 : // |rhs| and stores the result into the variable pointed to by |val| and
228 : // returns true if the signed summation resulted in an overflow.
229 : inline bool SignedAddOverflow64(int64_t lhs, int64_t rhs, int64_t* val) {
230 164025 : uint64_t res = static_cast<uint64_t>(lhs) + static_cast<uint64_t>(rhs);
231 : *val = bit_cast<int64_t>(res);
232 164025 : return ((res ^ lhs) & (res ^ rhs) & (1ULL << 63)) != 0;
233 : }
234 :
235 :
236 : // SignedSubOverflow64(lhs,rhs,val) performs a signed subtraction of |lhs| and
237 : // |rhs| and stores the result into the variable pointed to by |val| and
238 : // returns true if the signed subtraction resulted in an overflow.
239 : inline bool SignedSubOverflow64(int64_t lhs, int64_t rhs, int64_t* val) {
240 164025 : uint64_t res = static_cast<uint64_t>(lhs) - static_cast<uint64_t>(rhs);
241 : *val = bit_cast<int64_t>(res);
242 164025 : return ((res ^ lhs) & (res ^ ~rhs) & (1ULL << 63)) != 0;
243 : }
244 :
245 : // SignedMulOverflow64(lhs,rhs,val) performs a signed multiplication of |lhs|
246 : // and |rhs| and stores the result into the variable pointed to by |val| and
247 : // returns true if the signed multiplication resulted in an overflow.
248 : V8_BASE_EXPORT bool SignedMulOverflow64(int64_t lhs, int64_t rhs, int64_t* val);
249 :
250 : // SignedMulHigh32(lhs, rhs) multiplies two signed 32-bit values |lhs| and
251 : // |rhs|, extracts the most significant 32 bits of the result, and returns
252 : // those.
253 : V8_BASE_EXPORT int32_t SignedMulHigh32(int32_t lhs, int32_t rhs);
254 :
255 : // SignedMulHighAndAdd32(lhs, rhs, acc) multiplies two signed 32-bit values
256 : // |lhs| and |rhs|, extracts the most significant 32 bits of the result, and
257 : // adds the accumulate value |acc|.
258 : V8_BASE_EXPORT int32_t SignedMulHighAndAdd32(int32_t lhs, int32_t rhs,
259 : int32_t acc);
260 :
261 : // SignedDiv32(lhs, rhs) divides |lhs| by |rhs| and returns the quotient
262 : // truncated to int32. If |rhs| is zero, then zero is returned. If |lhs|
263 : // is minint and |rhs| is -1, it returns minint.
264 : V8_BASE_EXPORT int32_t SignedDiv32(int32_t lhs, int32_t rhs);
265 :
266 : // SignedMod32(lhs, rhs) divides |lhs| by |rhs| and returns the remainder
267 : // truncated to int32. If either |rhs| is zero or |lhs| is minint and |rhs|
268 : // is -1, it returns zero.
269 : V8_BASE_EXPORT int32_t SignedMod32(int32_t lhs, int32_t rhs);
270 :
271 : // UnsignedAddOverflow32(lhs,rhs,val) performs an unsigned summation of |lhs|
272 : // and |rhs| and stores the result into the variable pointed to by |val| and
273 : // returns true if the unsigned summation resulted in an overflow.
274 : inline bool UnsignedAddOverflow32(uint32_t lhs, uint32_t rhs, uint32_t* val) {
275 : #if V8_HAS_BUILTIN_SADD_OVERFLOW
276 : return __builtin_uadd_overflow(lhs, rhs, val);
277 : #else
278 150037702 : *val = lhs + rhs;
279 150037700 : return *val < (lhs | rhs);
280 : #endif
281 : }
282 :
283 :
284 : // UnsignedDiv32(lhs, rhs) divides |lhs| by |rhs| and returns the quotient
285 : // truncated to uint32. If |rhs| is zero, then zero is returned.
286 : inline uint32_t UnsignedDiv32(uint32_t lhs, uint32_t rhs) {
287 28108 : return rhs ? lhs / rhs : 0u;
288 : }
289 :
290 :
291 : // UnsignedMod32(lhs, rhs) divides |lhs| by |rhs| and returns the remainder
292 : // truncated to uint32. If |rhs| is zero, then zero is returned.
293 : inline uint32_t UnsignedMod32(uint32_t lhs, uint32_t rhs) {
294 28155 : return rhs ? lhs % rhs : 0u;
295 : }
296 :
297 :
298 : // Clamp |value| on overflow and underflow conditions.
299 : V8_BASE_EXPORT int64_t
300 : FromCheckedNumeric(const internal::CheckedNumeric<int64_t> value);
301 :
302 : // SignedSaturatedAdd64(lhs, rhs) adds |lhs| and |rhs|,
303 : // checks and returns the result.
304 : V8_BASE_EXPORT int64_t SignedSaturatedAdd64(int64_t lhs, int64_t rhs);
305 :
306 : // SignedSaturatedSub64(lhs, rhs) subtracts |lhs| by |rhs|,
307 : // checks and returns the result.
308 : V8_BASE_EXPORT int64_t SignedSaturatedSub64(int64_t lhs, int64_t rhs);
309 :
310 : } // namespace bits
311 : } // namespace base
312 : } // namespace v8
313 :
314 : #endif // V8_BASE_BITS_H_
|
