V8 API Reference, 7.2.502.16 (for Deno 0.2.4)
bits.h
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>
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  return sizeof(T) == 8 ? __builtin_popcountll(static_cast<uint64_t>(value))
38  : __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  ? __builtin_clzll(static_cast<uint64_t>(value))
83  : __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  : __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  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  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  if (value > 0x80000000u) return 0x80000000u;
163  uint32_t result = RoundUpToPowerOfTwo32(value);
164  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  if (shift == 0) return value;
172  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  if (shift == 0) return value;
178  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  if (shift == 0) return value;
184  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  if (shift == 0) return value;
190  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  uint32_t res = static_cast<uint32_t>(lhs) + static_cast<uint32_t>(rhs);
202  *val = bit_cast<int32_t>(res);
203  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  uint32_t res = static_cast<uint32_t>(lhs) - static_cast<uint32_t>(rhs);
216  *val = bit_cast<int32_t>(res);
217  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  uint64_t res = static_cast<uint64_t>(lhs) + static_cast<uint64_t>(rhs);
231  *val = bit_cast<int64_t>(res);
232  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  uint64_t res = static_cast<uint64_t>(lhs) - static_cast<uint64_t>(rhs);
241  *val = bit_cast<int64_t>(res);
242  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  *val = lhs + rhs;
279  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  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  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_
Definition: libplatform.h:13