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
19namespace v8 {
20namespace base {
21
22namespace internal {
23template <typename T>
24class CheckedNumeric;
25}
26
27namespace bits {
28
29// CountPopulation32(value) returns the number of bits set in |value|.
30inline unsigned CountPopulation32(uint32_t value) {
31#if V8_HAS_BUILTIN_POPCOUNT
32  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|.
45inline unsigned CountPopulation64(uint64_t value) {
46#if V8_HAS_BUILTIN_POPCOUNT
47  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.
56inline unsigned CountPopulation(uint32_t value) {
57  return CountPopulation32(value);
58}
59
60
61inline 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.
68inline unsigned CountLeadingZeros32(uint32_t value) {
69#if V8_HAS_BUILTIN_CLZ
70  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.
88inline unsigned CountLeadingZeros64(uint64_t value) {
89#if V8_HAS_BUILTIN_CLZ
90  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.
104template <typename T>
105T 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.
119inline unsigned CountTrailingZeros32(uint32_t value) {
120#if V8_HAS_BUILTIN_CTZ
121  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.
139inline unsigned CountTrailingZeros64(uint64_t value) {
140#if V8_HAS_BUILTIN_CTZ
141  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.
152inline unsigned CountTrailingZeros(uint32_t value) {
153  return CountTrailingZeros32(value);
154}
155
156inline unsigned CountTrailingZeros(uint64_t value) {
157  return CountTrailingZeros64(value);
158}
159
160// Returns true iff |value| is a power of 2.
161inline bool IsPowerOfTwo32(uint32_t value) {
162  return value && !(value & (value - 1));
163}
164
165
166// Returns true iff |value| is a power of 2.
167inline bool IsPowerOfTwo64(uint64_t value) {
168  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.
177V8_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.
182inline 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
191inline uint32_t RotateRight32(uint32_t value, uint32_t shift) {
192  if (shift == 0) return value;
193  return (value >> shift) | (value << (32 - shift));
194}
195
196// Precondition: 0 <= shift < 32
197inline 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
203inline 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
209inline 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.
218inline 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  uint32_t res = static_cast<uint32_t>(lhs) + static_cast<uint32_t>(rhs);
223  *val = bit_cast<int32_t>(res);
224  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.
232inline 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  uint32_t res = static_cast<uint32_t>(lhs) - static_cast<uint32_t>(rhs);
237  *val = bit_cast<int32_t>(res);
238  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.
245V8_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.
250inline 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.
260inline 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.
269V8_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.
274V8_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|.
279V8_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.
285V8_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.
290V8_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.
295inline 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  *val = lhs + rhs;
300  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.
307inline uint32_t UnsignedDiv32(uint32_t lhs, uint32_t rhs) {
308  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.
314inline uint32_t UnsignedMod32(uint32_t lhs, uint32_t rhs) {
315  return rhs ? lhs % rhs : 0u;
316}
317
318
319// Clamp |value| on overflow and underflow conditions.
320V8_BASE_EXPORT int64_t
321FromCheckedNumeric(const internal::CheckedNumeric<int64_t> value);
322
323// SignedSaturatedAdd64(lhs, rhs) adds |lhs| and |rhs|,
324// checks and returns the result.
325V8_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.
329V8_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_
336