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 "include/v8stdint.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 {
19namespace bits {
20
21// CountPopulation32(value) returns the number of bits set in |value|.
22inline uint32_t CountPopulation32(uint32_t value) {
23#if V8_HAS_BUILTIN_POPCOUNT
24  return __builtin_popcount(value);
25#else
26  value = ((value >> 1) & 0x55555555) + (value & 0x55555555);
27  value = ((value >> 2) & 0x33333333) + (value & 0x33333333);
28  value = ((value >> 4) & 0x0f0f0f0f) + (value & 0x0f0f0f0f);
29  value = ((value >> 8) & 0x00ff00ff) + (value & 0x00ff00ff);
30  value = ((value >> 16) & 0x0000ffff) + (value & 0x0000ffff);
31  return value;
32#endif
33}
34
35
36// CountLeadingZeros32(value) returns the number of zero bits following the most
37// significant 1 bit in |value| if |value| is non-zero, otherwise it returns 32.
38inline uint32_t CountLeadingZeros32(uint32_t value) {
39#if V8_HAS_BUILTIN_CLZ
40  return value ? __builtin_clz(value) : 32;
41#elif V8_CC_MSVC
42  unsigned long result;  // NOLINT(runtime/int)
43  if (!_BitScanReverse(&result, value)) return 32;
44  return static_cast<uint32_t>(31 - result);
45#else
46  value = value | (value >> 1);
47  value = value | (value >> 2);
48  value = value | (value >> 4);
49  value = value | (value >> 8);
50  value = value | (value >> 16);
51  return CountPopulation32(~value);
52#endif
53}
54
55
56// CountTrailingZeros32(value) returns the number of zero bits preceding the
57// least significant 1 bit in |value| if |value| is non-zero, otherwise it
58// returns 32.
59inline uint32_t CountTrailingZeros32(uint32_t value) {
60#if V8_HAS_BUILTIN_CTZ
61  return value ? __builtin_ctz(value) : 32;
62#elif V8_CC_MSVC
63  unsigned long result;  // NOLINT(runtime/int)
64  if (!_BitScanForward(&result, value)) return 32;
65  return static_cast<uint32_t>(result);
66#else
67  if (value == 0) return 32;
68  unsigned count = 0;
69  for (value ^= value - 1; value >>= 1; ++count)
70    ;
71  return count;
72#endif
73}
74
75
76// Returns true iff |value| is a power of 2.
77inline bool IsPowerOfTwo32(uint32_t value) {
78  return value && !(value & (value - 1));
79}
80
81
82// Returns true iff |value| is a power of 2.
83inline bool IsPowerOfTwo64(uint64_t value) {
84  return value && !(value & (value - 1));
85}
86
87
88// RoundUpToPowerOfTwo32(value) returns the smallest power of two which is
89// greater than or equal to |value|. If you pass in a |value| that is already a
90// power of two, it is returned as is. |value| must be less than or equal to
91// 0x80000000u. Implementation is from "Hacker's Delight" by Henry S. Warren,
92// Jr., figure 3-3, page 48, where the function is called clp2.
93uint32_t RoundUpToPowerOfTwo32(uint32_t value);
94
95
96// RoundDownToPowerOfTwo32(value) returns the greatest power of two which is
97// less than or equal to |value|. If you pass in a |value| that is already a
98// power of two, it is returned as is.
99inline uint32_t RoundDownToPowerOfTwo32(uint32_t value) {
100  if (value > 0x80000000u) return 0x80000000u;
101  uint32_t result = RoundUpToPowerOfTwo32(value);
102  if (result > value) result >>= 1;
103  return result;
104}
105
106
107inline uint32_t RotateRight32(uint32_t value, uint32_t shift) {
108  if (shift == 0) return value;
109  return (value >> shift) | (value << (32 - shift));
110}
111
112
113inline uint64_t RotateRight64(uint64_t value, uint64_t shift) {
114  if (shift == 0) return value;
115  return (value >> shift) | (value << (64 - shift));
116}
117
118
119// SignedAddOverflow32(lhs,rhs,val) performs a signed summation of |lhs| and
120// |rhs| and stores the result into the variable pointed to by |val| and
121// returns true if the signed summation resulted in an overflow.
122inline bool SignedAddOverflow32(int32_t lhs, int32_t rhs, int32_t* val) {
123#if V8_HAS_BUILTIN_SADD_OVERFLOW
124  return __builtin_sadd_overflow(lhs, rhs, val);
125#else
126  uint32_t res = static_cast<uint32_t>(lhs) + static_cast<uint32_t>(rhs);
127  *val = bit_cast<int32_t>(res);
128  return ((res ^ lhs) & (res ^ rhs) & (1U << 31)) != 0;
129#endif
130}
131
132
133// SignedSubOverflow32(lhs,rhs,val) performs a signed subtraction of |lhs| and
134// |rhs| and stores the result into the variable pointed to by |val| and
135// returns true if the signed subtraction resulted in an overflow.
136inline bool SignedSubOverflow32(int32_t lhs, int32_t rhs, int32_t* val) {
137#if V8_HAS_BUILTIN_SSUB_OVERFLOW
138  return __builtin_ssub_overflow(lhs, rhs, val);
139#else
140  uint32_t res = static_cast<uint32_t>(lhs) - static_cast<uint32_t>(rhs);
141  *val = bit_cast<int32_t>(res);
142  return ((res ^ lhs) & (res ^ ~rhs) & (1U << 31)) != 0;
143#endif
144}
145
146}  // namespace bits
147}  // namespace base
148}  // namespace v8
149
150#endif  // V8_BASE_BITS_H_
151