Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame^] | 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_ |