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