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 | |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 8 | #include <stdint.h> |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 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|. |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 22 | inline unsigned CountPopulation32(uint32_t value) { |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 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); |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 31 | return static_cast<unsigned>(value); |
| 32 | #endif |
| 33 | } |
| 34 | |
| 35 | |
| 36 | // CountPopulation64(value) returns the number of bits set in |value|. |
| 37 | inline unsigned CountPopulation64(uint64_t value) { |
| 38 | #if V8_HAS_BUILTIN_POPCOUNT |
| 39 | return __builtin_popcountll(value); |
| 40 | #else |
| 41 | return CountPopulation32(static_cast<uint32_t>(value)) + |
| 42 | CountPopulation32(static_cast<uint32_t>(value >> 32)); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 43 | #endif |
| 44 | } |
| 45 | |
| 46 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame^] | 47 | // Overloaded versions of CountPopulation32/64. |
| 48 | inline unsigned CountPopulation(uint32_t value) { |
| 49 | return CountPopulation32(value); |
| 50 | } |
| 51 | |
| 52 | |
| 53 | inline unsigned CountPopulation(uint64_t value) { |
| 54 | return CountPopulation64(value); |
| 55 | } |
| 56 | |
| 57 | |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 58 | // CountLeadingZeros32(value) returns the number of zero bits following the most |
| 59 | // significant 1 bit in |value| if |value| is non-zero, otherwise it returns 32. |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 60 | inline unsigned CountLeadingZeros32(uint32_t value) { |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 61 | #if V8_HAS_BUILTIN_CLZ |
| 62 | return value ? __builtin_clz(value) : 32; |
| 63 | #elif V8_CC_MSVC |
| 64 | unsigned long result; // NOLINT(runtime/int) |
| 65 | if (!_BitScanReverse(&result, value)) return 32; |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 66 | return static_cast<unsigned>(31 - result); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 67 | #else |
| 68 | value = value | (value >> 1); |
| 69 | value = value | (value >> 2); |
| 70 | value = value | (value >> 4); |
| 71 | value = value | (value >> 8); |
| 72 | value = value | (value >> 16); |
| 73 | return CountPopulation32(~value); |
| 74 | #endif |
| 75 | } |
| 76 | |
| 77 | |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 78 | // CountLeadingZeros64(value) returns the number of zero bits following the most |
| 79 | // significant 1 bit in |value| if |value| is non-zero, otherwise it returns 64. |
| 80 | inline unsigned CountLeadingZeros64(uint64_t value) { |
| 81 | #if V8_HAS_BUILTIN_CLZ |
| 82 | return value ? __builtin_clzll(value) : 64; |
| 83 | #else |
| 84 | value = value | (value >> 1); |
| 85 | value = value | (value >> 2); |
| 86 | value = value | (value >> 4); |
| 87 | value = value | (value >> 8); |
| 88 | value = value | (value >> 16); |
| 89 | value = value | (value >> 32); |
| 90 | return CountPopulation64(~value); |
| 91 | #endif |
| 92 | } |
| 93 | |
| 94 | |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 95 | // CountTrailingZeros32(value) returns the number of zero bits preceding the |
| 96 | // least significant 1 bit in |value| if |value| is non-zero, otherwise it |
| 97 | // returns 32. |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 98 | inline unsigned CountTrailingZeros32(uint32_t value) { |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 99 | #if V8_HAS_BUILTIN_CTZ |
| 100 | return value ? __builtin_ctz(value) : 32; |
| 101 | #elif V8_CC_MSVC |
| 102 | unsigned long result; // NOLINT(runtime/int) |
| 103 | if (!_BitScanForward(&result, value)) return 32; |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 104 | return static_cast<unsigned>(result); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 105 | #else |
| 106 | if (value == 0) return 32; |
| 107 | unsigned count = 0; |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame^] | 108 | for (value ^= value - 1; value >>= 1; ++count) { |
| 109 | } |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 110 | return count; |
| 111 | #endif |
| 112 | } |
| 113 | |
| 114 | |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 115 | // CountTrailingZeros64(value) returns the number of zero bits preceding the |
| 116 | // least significant 1 bit in |value| if |value| is non-zero, otherwise it |
| 117 | // returns 64. |
| 118 | inline unsigned CountTrailingZeros64(uint64_t value) { |
| 119 | #if V8_HAS_BUILTIN_CTZ |
| 120 | return value ? __builtin_ctzll(value) : 64; |
| 121 | #else |
| 122 | if (value == 0) return 64; |
| 123 | unsigned count = 0; |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame^] | 124 | for (value ^= value - 1; value >>= 1; ++count) { |
| 125 | } |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 126 | return count; |
| 127 | #endif |
| 128 | } |
| 129 | |
| 130 | |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 131 | // Returns true iff |value| is a power of 2. |
| 132 | inline bool IsPowerOfTwo32(uint32_t value) { |
| 133 | return value && !(value & (value - 1)); |
| 134 | } |
| 135 | |
| 136 | |
| 137 | // Returns true iff |value| is a power of 2. |
| 138 | inline bool IsPowerOfTwo64(uint64_t value) { |
| 139 | return value && !(value & (value - 1)); |
| 140 | } |
| 141 | |
| 142 | |
| 143 | // RoundUpToPowerOfTwo32(value) returns the smallest power of two which is |
| 144 | // greater than or equal to |value|. If you pass in a |value| that is already a |
| 145 | // power of two, it is returned as is. |value| must be less than or equal to |
| 146 | // 0x80000000u. Implementation is from "Hacker's Delight" by Henry S. Warren, |
| 147 | // Jr., figure 3-3, page 48, where the function is called clp2. |
| 148 | uint32_t RoundUpToPowerOfTwo32(uint32_t value); |
| 149 | |
| 150 | |
| 151 | // RoundDownToPowerOfTwo32(value) returns the greatest power of two which is |
| 152 | // less than or equal to |value|. If you pass in a |value| that is already a |
| 153 | // power of two, it is returned as is. |
| 154 | inline uint32_t RoundDownToPowerOfTwo32(uint32_t value) { |
| 155 | if (value > 0x80000000u) return 0x80000000u; |
| 156 | uint32_t result = RoundUpToPowerOfTwo32(value); |
| 157 | if (result > value) result >>= 1; |
| 158 | return result; |
| 159 | } |
| 160 | |
| 161 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame^] | 162 | // Precondition: 0 <= shift < 32 |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 163 | inline uint32_t RotateRight32(uint32_t value, uint32_t shift) { |
| 164 | if (shift == 0) return value; |
| 165 | return (value >> shift) | (value << (32 - shift)); |
| 166 | } |
| 167 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame^] | 168 | // Precondition: 0 <= shift < 32 |
| 169 | inline uint32_t RotateLeft32(uint32_t value, uint32_t shift) { |
| 170 | if (shift == 0) return value; |
| 171 | return (value << shift) | (value >> (32 - shift)); |
| 172 | } |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 173 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame^] | 174 | // Precondition: 0 <= shift < 64 |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 175 | inline uint64_t RotateRight64(uint64_t value, uint64_t shift) { |
| 176 | if (shift == 0) return value; |
| 177 | return (value >> shift) | (value << (64 - shift)); |
| 178 | } |
| 179 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame^] | 180 | // Precondition: 0 <= shift < 64 |
| 181 | inline uint64_t RotateLeft64(uint64_t value, uint64_t shift) { |
| 182 | if (shift == 0) return value; |
| 183 | return (value << shift) | (value >> (64 - shift)); |
| 184 | } |
| 185 | |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 186 | |
| 187 | // SignedAddOverflow32(lhs,rhs,val) performs a signed summation of |lhs| and |
| 188 | // |rhs| and stores the result into the variable pointed to by |val| and |
| 189 | // returns true if the signed summation resulted in an overflow. |
| 190 | inline bool SignedAddOverflow32(int32_t lhs, int32_t rhs, int32_t* val) { |
| 191 | #if V8_HAS_BUILTIN_SADD_OVERFLOW |
| 192 | return __builtin_sadd_overflow(lhs, rhs, val); |
| 193 | #else |
| 194 | uint32_t res = static_cast<uint32_t>(lhs) + static_cast<uint32_t>(rhs); |
| 195 | *val = bit_cast<int32_t>(res); |
| 196 | return ((res ^ lhs) & (res ^ rhs) & (1U << 31)) != 0; |
| 197 | #endif |
| 198 | } |
| 199 | |
| 200 | |
| 201 | // SignedSubOverflow32(lhs,rhs,val) performs a signed subtraction of |lhs| and |
| 202 | // |rhs| and stores the result into the variable pointed to by |val| and |
| 203 | // returns true if the signed subtraction resulted in an overflow. |
| 204 | inline bool SignedSubOverflow32(int32_t lhs, int32_t rhs, int32_t* val) { |
| 205 | #if V8_HAS_BUILTIN_SSUB_OVERFLOW |
| 206 | return __builtin_ssub_overflow(lhs, rhs, val); |
| 207 | #else |
| 208 | uint32_t res = static_cast<uint32_t>(lhs) - static_cast<uint32_t>(rhs); |
| 209 | *val = bit_cast<int32_t>(res); |
| 210 | return ((res ^ lhs) & (res ^ ~rhs) & (1U << 31)) != 0; |
| 211 | #endif |
| 212 | } |
| 213 | |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 214 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame^] | 215 | // SignedAddOverflow64(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 SignedAddOverflow64(int64_t lhs, int64_t rhs, int64_t* val) { |
| 219 | uint64_t res = static_cast<uint64_t>(lhs) + static_cast<uint64_t>(rhs); |
| 220 | *val = bit_cast<int64_t>(res); |
| 221 | return ((res ^ lhs) & (res ^ rhs) & (1ULL << 63)) != 0; |
| 222 | } |
| 223 | |
| 224 | |
| 225 | // SignedSubOverflow64(lhs,rhs,val) performs a signed subtraction of |lhs| and |
| 226 | // |rhs| and stores the result into the variable pointed to by |val| and |
| 227 | // returns true if the signed subtraction resulted in an overflow. |
| 228 | inline bool SignedSubOverflow64(int64_t lhs, int64_t rhs, int64_t* val) { |
| 229 | uint64_t res = static_cast<uint64_t>(lhs) - static_cast<uint64_t>(rhs); |
| 230 | *val = bit_cast<int64_t>(res); |
| 231 | return ((res ^ lhs) & (res ^ ~rhs) & (1ULL << 63)) != 0; |
| 232 | } |
| 233 | |
| 234 | |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 235 | // SignedMulHigh32(lhs, rhs) multiplies two signed 32-bit values |lhs| and |
| 236 | // |rhs|, extracts the most significant 32 bits of the result, and returns |
| 237 | // those. |
| 238 | int32_t SignedMulHigh32(int32_t lhs, int32_t rhs); |
| 239 | |
| 240 | |
| 241 | // SignedMulHighAndAdd32(lhs, rhs, acc) multiplies two signed 32-bit values |
| 242 | // |lhs| and |rhs|, extracts the most significant 32 bits of the result, and |
| 243 | // adds the accumulate value |acc|. |
| 244 | int32_t SignedMulHighAndAdd32(int32_t lhs, int32_t rhs, int32_t acc); |
| 245 | |
| 246 | |
| 247 | // SignedDiv32(lhs, rhs) divides |lhs| by |rhs| and returns the quotient |
| 248 | // truncated to int32. If |rhs| is zero, then zero is returned. If |lhs| |
| 249 | // is minint and |rhs| is -1, it returns minint. |
| 250 | int32_t SignedDiv32(int32_t lhs, int32_t rhs); |
| 251 | |
| 252 | |
| 253 | // SignedMod32(lhs, rhs) divides |lhs| by |rhs| and returns the remainder |
| 254 | // truncated to int32. If either |rhs| is zero or |lhs| is minint and |rhs| |
| 255 | // is -1, it returns zero. |
| 256 | int32_t SignedMod32(int32_t lhs, int32_t rhs); |
| 257 | |
| 258 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame^] | 259 | // UnsignedAddOverflow32(lhs,rhs,val) performs an unsigned summation of |lhs| |
| 260 | // and |rhs| and stores the result into the variable pointed to by |val| and |
| 261 | // returns true if the unsigned summation resulted in an overflow. |
| 262 | inline bool UnsignedAddOverflow32(uint32_t lhs, uint32_t rhs, uint32_t* val) { |
| 263 | #if V8_HAS_BUILTIN_SADD_OVERFLOW |
| 264 | return __builtin_uadd_overflow(lhs, rhs, val); |
| 265 | #else |
| 266 | *val = lhs + rhs; |
| 267 | return *val < (lhs | rhs); |
| 268 | #endif |
| 269 | } |
| 270 | |
| 271 | |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 272 | // UnsignedDiv32(lhs, rhs) divides |lhs| by |rhs| and returns the quotient |
| 273 | // truncated to uint32. If |rhs| is zero, then zero is returned. |
| 274 | inline uint32_t UnsignedDiv32(uint32_t lhs, uint32_t rhs) { |
| 275 | return rhs ? lhs / rhs : 0u; |
| 276 | } |
| 277 | |
| 278 | |
| 279 | // UnsignedMod32(lhs, rhs) divides |lhs| by |rhs| and returns the remainder |
| 280 | // truncated to uint32. If |rhs| is zero, then zero is returned. |
| 281 | inline uint32_t UnsignedMod32(uint32_t lhs, uint32_t rhs) { |
| 282 | return rhs ? lhs % rhs : 0u; |
| 283 | } |
| 284 | |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 285 | } // namespace bits |
| 286 | } // namespace base |
| 287 | } // namespace v8 |
| 288 | |
| 289 | #endif // V8_BASE_BITS_H_ |