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 19 namespace v8 { 20 namespace base { 21 22 namespace internal { 23 template <typename T> 24 class CheckedNumeric; 25 } 26 27 namespace bits { 28 29 // CountPopulation32(value) returns the number of bits set in |value|. 30 inline 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|. 45 inline 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. 56 inline unsigned CountPopulation(uint32_t value) { 57 return CountPopulation32(value); 58 } 59 60 61 inline 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. 68 inline 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. 88 inline 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. 104 template <typename T> 105 T 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. 119 inline 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. 139 inline 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. 152 inline unsigned CountTrailingZeros(uint32_t value) { 153 return CountTrailingZeros32(value); 154 } 155 156 inline unsigned CountTrailingZeros(uint64_t value) { 157 return CountTrailingZeros64(value); 158 } 159 160 // Returns true iff |value| is a power of 2. 161 inline bool IsPowerOfTwo32(uint32_t value) { 162 return value && !(value & (value - 1)); 163 } 164 165 166 // Returns true iff |value| is a power of 2. 167 inline 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. 177 V8_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. 182 inline 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 191 inline 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 197 inline 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 203 inline 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 209 inline 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. 218 inline 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. 232 inline 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. 245 V8_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. 250 inline 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. 260 inline 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. 269 V8_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. 274 V8_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|. 279 V8_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. 285 V8_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. 290 V8_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. 295 inline 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. 307 inline 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. 314 inline 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. 320 V8_BASE_EXPORT int64_t 321 FromCheckedNumeric(const internal::CheckedNumeric<int64_t> value); 322 323 // SignedSaturatedAdd64(lhs, rhs) adds |lhs| and |rhs|, 324 // checks and returns the result. 325 V8_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. 329 V8_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
