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.
5 #ifndef V8_BASE_BITS_H_
6 #define V8_BASE_BITS_H_
9 #include "src/base/macros.h"
14 #include "src/base/win32-headers.h"
21 // CountPopulation32(value) returns the number of bits set in |value|.
22 inline unsigned CountPopulation32(uint32_t value) {
23 #if V8_HAS_BUILTIN_POPCOUNT
24 return __builtin_popcount(value);
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 static_cast<unsigned>(value);
36 // CountPopulation64(value) returns the number of bits set in |value|.
37 inline unsigned CountPopulation64(uint64_t value) {
38 #if V8_HAS_BUILTIN_POPCOUNT
39 return __builtin_popcountll(value);
41 return CountPopulation32(static_cast<uint32_t>(value)) +
42 CountPopulation32(static_cast<uint32_t>(value >> 32));
47 // CountLeadingZeros32(value) returns the number of zero bits following the most
48 // significant 1 bit in |value| if |value| is non-zero, otherwise it returns 32.
49 inline unsigned CountLeadingZeros32(uint32_t value) {
50 #if V8_HAS_BUILTIN_CLZ
51 return value ? __builtin_clz(value) : 32;
53 unsigned long result; // NOLINT(runtime/int)
54 if (!_BitScanReverse(&result, value)) return 32;
55 return static_cast<unsigned>(31 - result);
57 value = value | (value >> 1);
58 value = value | (value >> 2);
59 value = value | (value >> 4);
60 value = value | (value >> 8);
61 value = value | (value >> 16);
62 return CountPopulation32(~value);
67 // CountLeadingZeros64(value) returns the number of zero bits following the most
68 // significant 1 bit in |value| if |value| is non-zero, otherwise it returns 64.
69 inline unsigned CountLeadingZeros64(uint64_t value) {
70 #if V8_HAS_BUILTIN_CLZ
71 return value ? __builtin_clzll(value) : 64;
73 value = value | (value >> 1);
74 value = value | (value >> 2);
75 value = value | (value >> 4);
76 value = value | (value >> 8);
77 value = value | (value >> 16);
78 value = value | (value >> 32);
79 return CountPopulation64(~value);
84 // CountTrailingZeros32(value) returns the number of zero bits preceding the
85 // least significant 1 bit in |value| if |value| is non-zero, otherwise it
87 inline unsigned CountTrailingZeros32(uint32_t value) {
88 #if V8_HAS_BUILTIN_CTZ
89 return value ? __builtin_ctz(value) : 32;
91 unsigned long result; // NOLINT(runtime/int)
92 if (!_BitScanForward(&result, value)) return 32;
93 return static_cast<unsigned>(result);
95 if (value == 0) return 32;
97 for (value ^= value - 1; value >>= 1; ++count)
104 // CountTrailingZeros64(value) returns the number of zero bits preceding the
105 // least significant 1 bit in |value| if |value| is non-zero, otherwise it
107 inline unsigned CountTrailingZeros64(uint64_t value) {
108 #if V8_HAS_BUILTIN_CTZ
109 return value ? __builtin_ctzll(value) : 64;
111 if (value == 0) return 64;
113 for (value ^= value - 1; value >>= 1; ++count)
120 // Returns true iff |value| is a power of 2.
121 inline bool IsPowerOfTwo32(uint32_t value) {
122 return value && !(value & (value - 1));
126 // Returns true iff |value| is a power of 2.
127 inline bool IsPowerOfTwo64(uint64_t value) {
128 return value && !(value & (value - 1));
132 // RoundUpToPowerOfTwo32(value) returns the smallest power of two which is
133 // greater than or equal to |value|. If you pass in a |value| that is already a
134 // power of two, it is returned as is. |value| must be less than or equal to
135 // 0x80000000u. Implementation is from "Hacker's Delight" by Henry S. Warren,
136 // Jr., figure 3-3, page 48, where the function is called clp2.
137 uint32_t RoundUpToPowerOfTwo32(uint32_t value);
140 // RoundDownToPowerOfTwo32(value) returns the greatest power of two which is
141 // less than or equal to |value|. If you pass in a |value| that is already a
142 // power of two, it is returned as is.
143 inline uint32_t RoundDownToPowerOfTwo32(uint32_t value) {
144 if (value > 0x80000000u) return 0x80000000u;
145 uint32_t result = RoundUpToPowerOfTwo32(value);
146 if (result > value) result >>= 1;
151 // Precondition: 0 <= shift < 32
152 inline uint32_t RotateRight32(uint32_t value, uint32_t shift) {
153 if (shift == 0) return value;
154 return (value >> shift) | (value << (32 - shift));
157 // Precondition: 0 <= shift < 32
158 inline uint32_t RotateLeft32(uint32_t value, uint32_t shift) {
159 if (shift == 0) return value;
160 return (value << shift) | (value >> (32 - shift));
163 // Precondition: 0 <= shift < 64
164 inline uint64_t RotateRight64(uint64_t value, uint64_t shift) {
165 if (shift == 0) return value;
166 return (value >> shift) | (value << (64 - shift));
169 // Precondition: 0 <= shift < 64
170 inline uint64_t RotateLeft64(uint64_t value, uint64_t shift) {
171 if (shift == 0) return value;
172 return (value << shift) | (value >> (64 - shift));
176 // SignedAddOverflow32(lhs,rhs,val) performs a signed summation of |lhs| and
177 // |rhs| and stores the result into the variable pointed to by |val| and
178 // returns true if the signed summation resulted in an overflow.
179 inline bool SignedAddOverflow32(int32_t lhs, int32_t rhs, int32_t* val) {
180 #if V8_HAS_BUILTIN_SADD_OVERFLOW
181 return __builtin_sadd_overflow(lhs, rhs, val);
183 uint32_t res = static_cast<uint32_t>(lhs) + static_cast<uint32_t>(rhs);
184 *val = bit_cast<int32_t>(res);
185 return ((res ^ lhs) & (res ^ rhs) & (1U << 31)) != 0;
190 // SignedSubOverflow32(lhs,rhs,val) performs a signed subtraction of |lhs| and
191 // |rhs| and stores the result into the variable pointed to by |val| and
192 // returns true if the signed subtraction resulted in an overflow.
193 inline bool SignedSubOverflow32(int32_t lhs, int32_t rhs, int32_t* val) {
194 #if V8_HAS_BUILTIN_SSUB_OVERFLOW
195 return __builtin_ssub_overflow(lhs, rhs, val);
197 uint32_t res = static_cast<uint32_t>(lhs) - static_cast<uint32_t>(rhs);
198 *val = bit_cast<int32_t>(res);
199 return ((res ^ lhs) & (res ^ ~rhs) & (1U << 31)) != 0;
204 // SignedMulHigh32(lhs, rhs) multiplies two signed 32-bit values |lhs| and
205 // |rhs|, extracts the most significant 32 bits of the result, and returns
207 int32_t SignedMulHigh32(int32_t lhs, int32_t rhs);
210 // SignedMulHighAndAdd32(lhs, rhs, acc) multiplies two signed 32-bit values
211 // |lhs| and |rhs|, extracts the most significant 32 bits of the result, and
212 // adds the accumulate value |acc|.
213 int32_t SignedMulHighAndAdd32(int32_t lhs, int32_t rhs, int32_t acc);
216 // SignedDiv32(lhs, rhs) divides |lhs| by |rhs| and returns the quotient
217 // truncated to int32. If |rhs| is zero, then zero is returned. If |lhs|
218 // is minint and |rhs| is -1, it returns minint.
219 int32_t SignedDiv32(int32_t lhs, int32_t rhs);
222 // SignedMod32(lhs, rhs) divides |lhs| by |rhs| and returns the remainder
223 // truncated to int32. If either |rhs| is zero or |lhs| is minint and |rhs|
224 // is -1, it returns zero.
225 int32_t SignedMod32(int32_t lhs, int32_t rhs);
228 // UnsignedDiv32(lhs, rhs) divides |lhs| by |rhs| and returns the quotient
229 // truncated to uint32. If |rhs| is zero, then zero is returned.
230 inline uint32_t UnsignedDiv32(uint32_t lhs, uint32_t rhs) {
231 return rhs ? lhs / rhs : 0u;
235 // UnsignedMod32(lhs, rhs) divides |lhs| by |rhs| and returns the remainder
236 // truncated to uint32. If |rhs| is zero, then zero is returned.
237 inline uint32_t UnsignedMod32(uint32_t lhs, uint32_t rhs) {
238 return rhs ? lhs % rhs : 0u;
245 #endif // V8_BASE_BITS_H_