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|.
CountPopulation32(uint32_t 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.
CountLeadingZeros32(uint32_t value)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.
CountTrailingZeros32(uint32_t value)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.
IsPowerOfTwo32(uint32_t value)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.
IsPowerOfTwo64(uint64_t value)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.
RoundDownToPowerOfTwo32(uint32_t value)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
RotateRight32(uint32_t value,uint32_t shift)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
RotateRight64(uint64_t value,uint64_t shift)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.
SignedAddOverflow32(int32_t lhs,int32_t rhs,int32_t * val)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.
SignedSubOverflow32(int32_t lhs,int32_t rhs,int32_t * val)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_
151