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