OLD | NEW |
1 // Copyright 2014 the V8 project authors. All rights reserved. | 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 | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #ifndef V8_BASE_BITS_H_ | 5 #ifndef V8_BASE_BITS_H_ |
6 #define V8_BASE_BITS_H_ | 6 #define V8_BASE_BITS_H_ |
7 | 7 |
8 #include "include/v8stdint.h" | 8 #include "include/v8stdint.h" |
9 #include "src/base/macros.h" | 9 #include "src/base/macros.h" |
10 #if V8_CC_MSVC | 10 #if V8_CC_MSVC |
11 #include <intrin.h> | 11 #include <intrin.h> |
12 #endif | 12 #endif |
13 #if V8_OS_WIN32 | 13 #if V8_OS_WIN32 |
14 #include "src/base/win32-headers.h" | 14 #include "src/base/win32-headers.h" |
15 #endif | 15 #endif |
16 | 16 |
17 namespace v8 { | 17 namespace v8 { |
18 namespace base { | 18 namespace base { |
19 namespace bits { | 19 namespace bits { |
20 | 20 |
21 // CountPopulation32(value) returns the number of bits set in |value|. | 21 // CountPopulation32(value) returns the number of bits set in |value|. |
22 inline uint32_t CountPopulation32(uint32_t value) { | 22 inline unsigned CountPopulation32(uint32_t value) { |
23 #if V8_HAS_BUILTIN_POPCOUNT | 23 #if V8_HAS_BUILTIN_POPCOUNT |
24 return __builtin_popcount(value); | 24 return __builtin_popcount(value); |
25 #else | 25 #else |
26 value = ((value >> 1) & 0x55555555) + (value & 0x55555555); | 26 value = ((value >> 1) & 0x55555555) + (value & 0x55555555); |
27 value = ((value >> 2) & 0x33333333) + (value & 0x33333333); | 27 value = ((value >> 2) & 0x33333333) + (value & 0x33333333); |
28 value = ((value >> 4) & 0x0f0f0f0f) + (value & 0x0f0f0f0f); | 28 value = ((value >> 4) & 0x0f0f0f0f) + (value & 0x0f0f0f0f); |
29 value = ((value >> 8) & 0x00ff00ff) + (value & 0x00ff00ff); | 29 value = ((value >> 8) & 0x00ff00ff) + (value & 0x00ff00ff); |
30 value = ((value >> 16) & 0x0000ffff) + (value & 0x0000ffff); | 30 value = ((value >> 16) & 0x0000ffff) + (value & 0x0000ffff); |
31 return value; | 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)); |
32 #endif | 43 #endif |
33 } | 44 } |
34 | 45 |
35 | 46 |
36 // CountLeadingZeros32(value) returns the number of zero bits following the most | 47 // 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. | 48 // significant 1 bit in |value| if |value| is non-zero, otherwise it returns 32. |
38 inline uint32_t CountLeadingZeros32(uint32_t value) { | 49 inline unsigned CountLeadingZeros32(uint32_t value) { |
39 #if V8_HAS_BUILTIN_CLZ | 50 #if V8_HAS_BUILTIN_CLZ |
40 return value ? __builtin_clz(value) : 32; | 51 return value ? __builtin_clz(value) : 32; |
41 #elif V8_CC_MSVC | 52 #elif V8_CC_MSVC |
42 unsigned long result; // NOLINT(runtime/int) | 53 unsigned long result; // NOLINT(runtime/int) |
43 if (!_BitScanReverse(&result, value)) return 32; | 54 if (!_BitScanReverse(&result, value)) return 32; |
44 return static_cast<uint32_t>(31 - result); | 55 return static_cast<unsigned>(31 - result); |
45 #else | 56 #else |
46 value = value | (value >> 1); | 57 value = value | (value >> 1); |
47 value = value | (value >> 2); | 58 value = value | (value >> 2); |
48 value = value | (value >> 4); | 59 value = value | (value >> 4); |
49 value = value | (value >> 8); | 60 value = value | (value >> 8); |
50 value = value | (value >> 16); | 61 value = value | (value >> 16); |
51 return CountPopulation32(~value); | 62 return CountPopulation32(~value); |
52 #endif | 63 #endif |
53 } | 64 } |
54 | 65 |
55 | 66 |
| 67 // CountLeadingZeros64(value) returns the number of zero bits following the most |
| 68 // significant 1 bit in |value| if |value| is non-zero, otherwise it returns 64. |
| 69 inline unsigned CountLeadingZeros64(uint64_t value) { |
| 70 #if V8_HAS_BUILTIN_CLZ |
| 71 return value ? __builtin_clzll(value) : 64; |
| 72 #else |
| 73 value = value | (value >> 1); |
| 74 value = value | (value >> 2); |
| 75 value = value | (value >> 4); |
| 76 value = value | (value >> 8); |
| 77 value = value | (value >> 16); |
| 78 value = value | (value >> 32); |
| 79 return CountPopulation64(~value); |
| 80 #endif |
| 81 } |
| 82 |
| 83 |
56 // CountTrailingZeros32(value) returns the number of zero bits preceding the | 84 // CountTrailingZeros32(value) returns the number of zero bits preceding the |
57 // least significant 1 bit in |value| if |value| is non-zero, otherwise it | 85 // least significant 1 bit in |value| if |value| is non-zero, otherwise it |
58 // returns 32. | 86 // returns 32. |
59 inline uint32_t CountTrailingZeros32(uint32_t value) { | 87 inline unsigned CountTrailingZeros32(uint32_t value) { |
60 #if V8_HAS_BUILTIN_CTZ | 88 #if V8_HAS_BUILTIN_CTZ |
61 return value ? __builtin_ctz(value) : 32; | 89 return value ? __builtin_ctz(value) : 32; |
62 #elif V8_CC_MSVC | 90 #elif V8_CC_MSVC |
63 unsigned long result; // NOLINT(runtime/int) | 91 unsigned long result; // NOLINT(runtime/int) |
64 if (!_BitScanForward(&result, value)) return 32; | 92 if (!_BitScanForward(&result, value)) return 32; |
65 return static_cast<uint32_t>(result); | 93 return static_cast<unsigned>(result); |
66 #else | 94 #else |
67 if (value == 0) return 32; | 95 if (value == 0) return 32; |
68 unsigned count = 0; | 96 unsigned count = 0; |
69 for (value ^= value - 1; value >>= 1; ++count) | 97 for (value ^= value - 1; value >>= 1; ++count) |
70 ; | 98 ; |
71 return count; | 99 return count; |
72 #endif | 100 #endif |
73 } | 101 } |
74 | 102 |
75 | 103 |
| 104 // CountTrailingZeros64(value) returns the number of zero bits preceding the |
| 105 // least significant 1 bit in |value| if |value| is non-zero, otherwise it |
| 106 // returns 64. |
| 107 inline unsigned CountTrailingZeros64(uint64_t value) { |
| 108 #if V8_HAS_BUILTIN_CTZ |
| 109 return value ? __builtin_ctzll(value) : 64; |
| 110 #else |
| 111 if (value == 0) return 64; |
| 112 unsigned count = 0; |
| 113 for (value ^= value - 1; value >>= 1; ++count) |
| 114 ; |
| 115 return count; |
| 116 #endif |
| 117 } |
| 118 |
| 119 |
76 // Returns true iff |value| is a power of 2. | 120 // Returns true iff |value| is a power of 2. |
77 inline bool IsPowerOfTwo32(uint32_t value) { | 121 inline bool IsPowerOfTwo32(uint32_t value) { |
78 return value && !(value & (value - 1)); | 122 return value && !(value & (value - 1)); |
79 } | 123 } |
80 | 124 |
81 | 125 |
82 // Returns true iff |value| is a power of 2. | 126 // Returns true iff |value| is a power of 2. |
83 inline bool IsPowerOfTwo64(uint64_t value) { | 127 inline bool IsPowerOfTwo64(uint64_t value) { |
84 return value && !(value & (value - 1)); | 128 return value && !(value & (value - 1)); |
85 } | 129 } |
(...skipping 55 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
141 *val = bit_cast<int32_t>(res); | 185 *val = bit_cast<int32_t>(res); |
142 return ((res ^ lhs) & (res ^ ~rhs) & (1U << 31)) != 0; | 186 return ((res ^ lhs) & (res ^ ~rhs) & (1U << 31)) != 0; |
143 #endif | 187 #endif |
144 } | 188 } |
145 | 189 |
146 } // namespace bits | 190 } // namespace bits |
147 } // namespace base | 191 } // namespace base |
148 } // namespace v8 | 192 } // namespace v8 |
149 | 193 |
150 #endif // V8_BASE_BITS_H_ | 194 #endif // V8_BASE_BITS_H_ |
OLD | NEW |