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