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