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 | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 95 | // ReverseBits(value) returns |value| in reverse bit order. |
| 96 | template <typename T> |
| 97 | T ReverseBits(T value) { |
| 98 | DCHECK((sizeof(value) == 1) || (sizeof(value) == 2) || (sizeof(value) == 4) || |
| 99 | (sizeof(value) == 8)); |
| 100 | T result = 0; |
| 101 | for (unsigned i = 0; i < (sizeof(value) * 8); i++) { |
| 102 | result = (result << 1) | (value & 1); |
| 103 | value >>= 1; |
| 104 | } |
| 105 | return result; |
| 106 | } |
| 107 | |
| 108 | |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 109 | // CountTrailingZeros32(value) returns the number of zero bits preceding the |
| 110 | // least significant 1 bit in |value| if |value| is non-zero, otherwise it |
| 111 | // returns 32. |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 112 | inline unsigned CountTrailingZeros32(uint32_t value) { |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 113 | #if V8_HAS_BUILTIN_CTZ |
| 114 | return value ? __builtin_ctz(value) : 32; |
| 115 | #elif V8_CC_MSVC |
| 116 | unsigned long result; // NOLINT(runtime/int) |
| 117 | if (!_BitScanForward(&result, value)) return 32; |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 118 | return static_cast<unsigned>(result); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 119 | #else |
| 120 | if (value == 0) return 32; |
| 121 | unsigned count = 0; |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 122 | for (value ^= value - 1; value >>= 1; ++count) { |
| 123 | } |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 124 | return count; |
| 125 | #endif |
| 126 | } |
| 127 | |
| 128 | |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 129 | // CountTrailingZeros64(value) returns the number of zero bits preceding the |
| 130 | // least significant 1 bit in |value| if |value| is non-zero, otherwise it |
| 131 | // returns 64. |
| 132 | inline unsigned CountTrailingZeros64(uint64_t value) { |
| 133 | #if V8_HAS_BUILTIN_CTZ |
| 134 | return value ? __builtin_ctzll(value) : 64; |
| 135 | #else |
| 136 | if (value == 0) return 64; |
| 137 | unsigned count = 0; |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 138 | for (value ^= value - 1; value >>= 1; ++count) { |
| 139 | } |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 140 | return count; |
| 141 | #endif |
| 142 | } |
| 143 | |
| 144 | |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 145 | // Returns true iff |value| is a power of 2. |
| 146 | inline bool IsPowerOfTwo32(uint32_t value) { |
| 147 | return value && !(value & (value - 1)); |
| 148 | } |
| 149 | |
| 150 | |
| 151 | // Returns true iff |value| is a power of 2. |
| 152 | inline bool IsPowerOfTwo64(uint64_t value) { |
| 153 | return value && !(value & (value - 1)); |
| 154 | } |
| 155 | |
| 156 | |
| 157 | // RoundUpToPowerOfTwo32(value) returns the smallest power of two which is |
| 158 | // greater than or equal to |value|. If you pass in a |value| that is already a |
| 159 | // power of two, it is returned as is. |value| must be less than or equal to |
| 160 | // 0x80000000u. Implementation is from "Hacker's Delight" by Henry S. Warren, |
| 161 | // Jr., figure 3-3, page 48, where the function is called clp2. |
| 162 | uint32_t RoundUpToPowerOfTwo32(uint32_t value); |
| 163 | |
| 164 | |
| 165 | // RoundDownToPowerOfTwo32(value) returns the greatest power of two which is |
| 166 | // less than or equal to |value|. If you pass in a |value| that is already a |
| 167 | // power of two, it is returned as is. |
| 168 | inline uint32_t RoundDownToPowerOfTwo32(uint32_t value) { |
| 169 | if (value > 0x80000000u) return 0x80000000u; |
| 170 | uint32_t result = RoundUpToPowerOfTwo32(value); |
| 171 | if (result > value) result >>= 1; |
| 172 | return result; |
| 173 | } |
| 174 | |
| 175 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 176 | // Precondition: 0 <= shift < 32 |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 177 | inline uint32_t RotateRight32(uint32_t value, uint32_t shift) { |
| 178 | if (shift == 0) return value; |
| 179 | return (value >> shift) | (value << (32 - shift)); |
| 180 | } |
| 181 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 182 | // Precondition: 0 <= shift < 32 |
| 183 | inline uint32_t RotateLeft32(uint32_t value, uint32_t shift) { |
| 184 | if (shift == 0) return value; |
| 185 | return (value << shift) | (value >> (32 - shift)); |
| 186 | } |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 187 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 188 | // Precondition: 0 <= shift < 64 |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 189 | inline uint64_t RotateRight64(uint64_t value, uint64_t shift) { |
| 190 | if (shift == 0) return value; |
| 191 | return (value >> shift) | (value << (64 - shift)); |
| 192 | } |
| 193 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 194 | // Precondition: 0 <= shift < 64 |
| 195 | inline uint64_t RotateLeft64(uint64_t value, uint64_t shift) { |
| 196 | if (shift == 0) return value; |
| 197 | return (value << shift) | (value >> (64 - shift)); |
| 198 | } |
| 199 | |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 200 | |
| 201 | // SignedAddOverflow32(lhs,rhs,val) performs a signed summation of |lhs| and |
| 202 | // |rhs| and stores the result into the variable pointed to by |val| and |
| 203 | // returns true if the signed summation resulted in an overflow. |
| 204 | inline bool SignedAddOverflow32(int32_t lhs, int32_t rhs, int32_t* val) { |
| 205 | #if V8_HAS_BUILTIN_SADD_OVERFLOW |
| 206 | return __builtin_sadd_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 | |
| 214 | |
| 215 | // SignedSubOverflow32(lhs,rhs,val) performs a signed subtraction of |lhs| and |
| 216 | // |rhs| and stores the result into the variable pointed to by |val| and |
| 217 | // returns true if the signed subtraction resulted in an overflow. |
| 218 | inline bool SignedSubOverflow32(int32_t lhs, int32_t rhs, int32_t* val) { |
| 219 | #if V8_HAS_BUILTIN_SSUB_OVERFLOW |
| 220 | return __builtin_ssub_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 | |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 228 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 229 | // SignedAddOverflow64(lhs,rhs,val) performs a signed summation of |lhs| and |
| 230 | // |rhs| and stores the result into the variable pointed to by |val| and |
| 231 | // returns true if the signed summation resulted in an overflow. |
| 232 | inline bool SignedAddOverflow64(int64_t lhs, int64_t rhs, int64_t* val) { |
| 233 | uint64_t res = static_cast<uint64_t>(lhs) + static_cast<uint64_t>(rhs); |
| 234 | *val = bit_cast<int64_t>(res); |
| 235 | return ((res ^ lhs) & (res ^ rhs) & (1ULL << 63)) != 0; |
| 236 | } |
| 237 | |
| 238 | |
| 239 | // SignedSubOverflow64(lhs,rhs,val) performs a signed subtraction of |lhs| and |
| 240 | // |rhs| and stores the result into the variable pointed to by |val| and |
| 241 | // returns true if the signed subtraction resulted in an overflow. |
| 242 | inline bool SignedSubOverflow64(int64_t lhs, int64_t rhs, int64_t* val) { |
| 243 | uint64_t res = static_cast<uint64_t>(lhs) - static_cast<uint64_t>(rhs); |
| 244 | *val = bit_cast<int64_t>(res); |
| 245 | return ((res ^ lhs) & (res ^ ~rhs) & (1ULL << 63)) != 0; |
| 246 | } |
| 247 | |
| 248 | |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 249 | // SignedMulHigh32(lhs, rhs) multiplies two signed 32-bit values |lhs| and |
| 250 | // |rhs|, extracts the most significant 32 bits of the result, and returns |
| 251 | // those. |
| 252 | int32_t SignedMulHigh32(int32_t lhs, int32_t rhs); |
| 253 | |
| 254 | |
| 255 | // SignedMulHighAndAdd32(lhs, rhs, acc) multiplies two signed 32-bit values |
| 256 | // |lhs| and |rhs|, extracts the most significant 32 bits of the result, and |
| 257 | // adds the accumulate value |acc|. |
| 258 | int32_t SignedMulHighAndAdd32(int32_t lhs, int32_t rhs, int32_t acc); |
| 259 | |
| 260 | |
| 261 | // SignedDiv32(lhs, rhs) divides |lhs| by |rhs| and returns the quotient |
| 262 | // truncated to int32. If |rhs| is zero, then zero is returned. If |lhs| |
| 263 | // is minint and |rhs| is -1, it returns minint. |
| 264 | int32_t SignedDiv32(int32_t lhs, int32_t rhs); |
| 265 | |
| 266 | |
| 267 | // SignedMod32(lhs, rhs) divides |lhs| by |rhs| and returns the remainder |
| 268 | // truncated to int32. If either |rhs| is zero or |lhs| is minint and |rhs| |
| 269 | // is -1, it returns zero. |
| 270 | int32_t SignedMod32(int32_t lhs, int32_t rhs); |
| 271 | |
| 272 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 273 | // UnsignedAddOverflow32(lhs,rhs,val) performs an unsigned summation of |lhs| |
| 274 | // and |rhs| and stores the result into the variable pointed to by |val| and |
| 275 | // returns true if the unsigned summation resulted in an overflow. |
| 276 | inline bool UnsignedAddOverflow32(uint32_t lhs, uint32_t rhs, uint32_t* val) { |
| 277 | #if V8_HAS_BUILTIN_SADD_OVERFLOW |
| 278 | return __builtin_uadd_overflow(lhs, rhs, val); |
| 279 | #else |
| 280 | *val = lhs + rhs; |
| 281 | return *val < (lhs | rhs); |
| 282 | #endif |
| 283 | } |
| 284 | |
| 285 | |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 286 | // UnsignedDiv32(lhs, rhs) divides |lhs| by |rhs| and returns the quotient |
| 287 | // truncated to uint32. If |rhs| is zero, then zero is returned. |
| 288 | inline uint32_t UnsignedDiv32(uint32_t lhs, uint32_t rhs) { |
| 289 | return rhs ? lhs / rhs : 0u; |
| 290 | } |
| 291 | |
| 292 | |
| 293 | // UnsignedMod32(lhs, rhs) divides |lhs| by |rhs| and returns the remainder |
| 294 | // truncated to uint32. If |rhs| is zero, then zero is returned. |
| 295 | inline uint32_t UnsignedMod32(uint32_t lhs, uint32_t rhs) { |
| 296 | return rhs ? lhs % rhs : 0u; |
| 297 | } |
| 298 | |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 299 | } // namespace bits |
| 300 | } // namespace base |
| 301 | } // namespace v8 |
| 302 | |
| 303 | #endif // V8_BASE_BITS_H_ |