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