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 17 namespace v8 { 18 namespace base { 19 namespace bits { 20 21 // CountPopulation32(value) returns the number of bits set in |value|. 22 inline 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. 38 inline 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. 59 inline 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. 77 inline bool IsPowerOfTwo32(uint32_t value) { 78 return value && !(value & (value - 1)); 79 } 80 81 82 // Returns true iff |value| is a power of 2. 83 inline 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. 93 uint32_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. 99 inline 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 107 inline 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 113 inline 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. 122 inline 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. 136 inline 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