/Users/deen/code/yugabyte-db/src/yb/gutil/bits.h
Line | Count | Source (jump to first uncovered line) |
1 | | // Copyright 2002 and onwards Google Inc. |
2 | | // |
3 | | // The following only applies to changes made to this file as part of YugaByte development. |
4 | | // |
5 | | // Portions Copyright (c) YugaByte, Inc. |
6 | | // |
7 | | // Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except |
8 | | // in compliance with the License. You may obtain a copy of the License at |
9 | | // |
10 | | // http://www.apache.org/licenses/LICENSE-2.0 |
11 | | // |
12 | | // Unless required by applicable law or agreed to in writing, software distributed under the License |
13 | | // is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express |
14 | | // or implied. See the License for the specific language governing permissions and limitations |
15 | | // under the License. |
16 | | // |
17 | | // A collection of useful (static) bit-twiddling functions. |
18 | | |
19 | | #ifndef YB_GUTIL_BITS_H |
20 | | #define YB_GUTIL_BITS_H |
21 | | |
22 | | #include <glog/logging.h> |
23 | | |
24 | | #include "yb/gutil/integral_types.h" |
25 | | #include "yb/gutil/logging-inl.h" |
26 | | #include "yb/gutil/macros.h" |
27 | | |
28 | | class Bits { |
29 | | public: |
30 | | // Return the number of one bits in the given integer. |
31 | | static int CountOnesInByte(unsigned char n); |
32 | | |
33 | 0 | static int CountOnes(uint32 n) { |
34 | 0 | n -= ((n >> 1) & 0x55555555); |
35 | 0 | n = ((n >> 2) & 0x33333333) + (n & 0x33333333); |
36 | 0 | return (((n + (n >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24; |
37 | 0 | } |
38 | | |
39 | | // Count bits using sideways addition [WWG'57]. See Knuth TAOCP v4 7.1.3(59) |
40 | 0 | static inline int CountOnes64(uint64 n) { |
41 | 0 | #if defined(__x86_64__) |
42 | 0 | n -= (n >> 1) & 0x5555555555555555ULL; |
43 | 0 | n = ((n >> 2) & 0x3333333333333333ULL) + (n & 0x3333333333333333ULL); |
44 | 0 | return (((n + (n >> 4)) & 0xF0F0F0F0F0F0F0FULL) |
45 | 0 | * 0x101010101010101ULL) >> 56; |
46 | 0 | #else |
47 | 0 | return CountOnes(n >> 32) + CountOnes(n & 0xffffffff); |
48 | 0 | #endif |
49 | 0 | } |
50 | | |
51 | | // Reverse the bits in the given integer. |
52 | | static uint8 ReverseBits8(uint8 n); |
53 | | static uint32 ReverseBits32(uint32 n); |
54 | | static uint64 ReverseBits64(uint64 n); |
55 | | |
56 | | // Return the number of one bits in the byte sequence. |
57 | | static int Count(const void *m, int num_bytes); |
58 | | |
59 | | // Return the number of different bits in the given byte sequences. |
60 | | // (i.e., the Hamming distance) |
61 | | static int Difference(const void *m1, const void *m2, int num_bytes); |
62 | | |
63 | | // Return the number of different bits in the given byte sequences, |
64 | | // up to a maximum. Values larger than the maximum may be returned |
65 | | // (because multiple bits are checked at a time), but the function |
66 | | // may exit early if the cap is exceeded. |
67 | | static int CappedDifference(const void *m1, const void *m2, |
68 | | int num_bytes, int cap); |
69 | | |
70 | | // Return floor(log2(n)) for positive integer n. Returns -1 iff n == 0. |
71 | | static int Log2Floor(uint32 n); |
72 | | static int Log2Floor64(uint64 n); |
73 | | |
74 | | // Potentially faster version of Log2Floor() that returns an |
75 | | // undefined value if n == 0 |
76 | | static int Log2FloorNonZero(uint32 n); |
77 | | static int Log2FloorNonZero64(uint64 n); |
78 | | |
79 | | // Return ceiling(log2(n)) for positive integer n. Returns -1 iff n == 0. |
80 | | static int Log2Ceiling(uint32 n); |
81 | | static int Log2Ceiling64(uint64 n); |
82 | | |
83 | | // Return the first set least / most significant bit, 0-indexed. Returns an |
84 | | // undefined value if n == 0. FindLSBSetNonZero() is similar to ffs() except |
85 | | // that it's 0-indexed, while FindMSBSetNonZero() is the same as |
86 | | // Log2FloorNonZero(). |
87 | | static int FindLSBSetNonZero(uint32 n); |
88 | | static int FindLSBSetNonZero64(uint64 n); |
89 | 0 | static int FindMSBSetNonZero(uint32 n) { return Log2FloorNonZero(n); } |
90 | 0 | static int FindMSBSetNonZero64(uint64 n) { return Log2FloorNonZero64(n); } |
91 | | |
92 | | // Portable implementations |
93 | | static int Log2Floor_Portable(uint32 n); |
94 | | static int Log2FloorNonZero_Portable(uint32 n); |
95 | | static int FindLSBSetNonZero_Portable(uint32 n); |
96 | | static int Log2Floor64_Portable(uint64 n); |
97 | | static int Log2FloorNonZero64_Portable(uint64 n); |
98 | | static int FindLSBSetNonZero64_Portable(uint64 n); |
99 | | |
100 | | // Viewing bytes as a stream of unsigned bytes, does that stream |
101 | | // contain any byte equal to c? |
102 | | template <class T> static bool BytesContainByte(T bytes, uint8 c); |
103 | | |
104 | | // Viewing bytes as a stream of unsigned bytes, does that stream |
105 | | // contain any byte b < c? |
106 | | template <class T> static bool BytesContainByteLessThan(T bytes, uint8 c); |
107 | | |
108 | | // Viewing bytes as a stream of unsigned bytes, are all elements of that |
109 | | // stream in [lo, hi]? |
110 | | template <class T> static bool BytesAllInRange(T bytes, uint8 lo, uint8 hi); |
111 | | |
112 | | private: |
113 | | static const char num_bits[]; |
114 | | static const unsigned char bit_reverse_table[]; |
115 | | DISALLOW_COPY_AND_ASSIGN(Bits); |
116 | | }; |
117 | | |
118 | | // A utility class for some handy bit patterns. The names l and h |
119 | | // were chosen to match Knuth Volume 4: l is 0x010101... and h is 0x808080...; |
120 | | // half_ones is ones in the lower half only. We assume sizeof(T) is 1 or even. |
121 | | template <class T> struct BitPattern { |
122 | | static const T half_ones = (static_cast<T>(1) << (sizeof(T)*4)) - 1; |
123 | | static const T l = (sizeof(T) == 1) ? 1 : |
124 | | (half_ones / 0xff * (half_ones + 2)); |
125 | | static const T h = ~(l * 0x7f); |
126 | | }; |
127 | | |
128 | | // ------------------------------------------------------------------------ |
129 | | // Implementation details follow |
130 | | // ------------------------------------------------------------------------ |
131 | | |
132 | | // use GNU builtins where available |
133 | | #if defined(__GNUC__) && \ |
134 | | ((__GNUC__ == 3 && __GNUC_MINOR__ >= 4) || __GNUC__ >= 4) |
135 | 7.30M | inline int Bits::Log2Floor(uint32 n) { |
136 | 7.30M | return n == 0 ? -1 : 31 ^ __builtin_clz(n); |
137 | 7.30M | } |
138 | | |
139 | 0 | inline int Bits::Log2FloorNonZero(uint32 n) { |
140 | 0 | return 31 ^ __builtin_clz(n); |
141 | 0 | } |
142 | | |
143 | 7 | inline int Bits::FindLSBSetNonZero(uint32 n) { |
144 | 7 | return __builtin_ctz(n); |
145 | 7 | } |
146 | | |
147 | 271M | inline int Bits::Log2Floor64(uint64 n) { |
148 | 271M | return n == 0 ? -1 : 63 ^ __builtin_clzll(n); |
149 | 271M | } |
150 | | |
151 | 0 | inline int Bits::Log2FloorNonZero64(uint64 n) { |
152 | 0 | return 63 ^ __builtin_clzll(n); |
153 | 0 | } |
154 | | |
155 | 0 | inline int Bits::FindLSBSetNonZero64(uint64 n) { |
156 | 0 | return __builtin_ctzll(n); |
157 | 0 | } |
158 | | #elif defined(_MSC_VER) |
159 | | #include "yb/gutil/bits-internal-windows.h" |
160 | | #else |
161 | | #include "yb/gutil/bits-internal-unknown.h" |
162 | | #endif |
163 | | |
164 | 0 | inline int Bits::CountOnesInByte(unsigned char n) { |
165 | 0 | return num_bits[n]; |
166 | 0 | } |
167 | | |
168 | 0 | inline uint8 Bits::ReverseBits8(unsigned char n) { |
169 | 0 | n = ((n >> 1) & 0x55) | ((n & 0x55) << 1); |
170 | 0 | n = ((n >> 2) & 0x33) | ((n & 0x33) << 2); |
171 | 0 | return ((n >> 4) & 0x0f) | ((n & 0x0f) << 4); |
172 | 0 | } |
173 | | |
174 | 0 | inline uint32 Bits::ReverseBits32(uint32 n) { |
175 | 0 | n = ((n >> 1) & 0x55555555) | ((n & 0x55555555) << 1); |
176 | 0 | n = ((n >> 2) & 0x33333333) | ((n & 0x33333333) << 2); |
177 | 0 | n = ((n >> 4) & 0x0F0F0F0F) | ((n & 0x0F0F0F0F) << 4); |
178 | 0 | n = ((n >> 8) & 0x00FF00FF) | ((n & 0x00FF00FF) << 8); |
179 | 0 | return ( n >> 16 ) | ( n << 16); |
180 | 0 | } |
181 | | |
182 | 0 | inline uint64 Bits::ReverseBits64(uint64 n) { |
183 | 0 | #if defined(__x86_64__) |
184 | 0 | n = ((n >> 1) & 0x5555555555555555ULL) | ((n & 0x5555555555555555ULL) << 1); |
185 | 0 | n = ((n >> 2) & 0x3333333333333333ULL) | ((n & 0x3333333333333333ULL) << 2); |
186 | 0 | n = ((n >> 4) & 0x0F0F0F0F0F0F0F0FULL) | ((n & 0x0F0F0F0F0F0F0F0FULL) << 4); |
187 | 0 | n = ((n >> 8) & 0x00FF00FF00FF00FFULL) | ((n & 0x00FF00FF00FF00FFULL) << 8); |
188 | 0 | n = ((n >> 16) & 0x0000FFFF0000FFFFULL) | ((n & 0x0000FFFF0000FFFFULL) << 16); |
189 | 0 | return ( n >> 32 ) | ( n << 32); |
190 | 0 | #else |
191 | 0 | return ReverseBits32( n >> 32 ) | |
192 | 0 | (static_cast<uint64>(ReverseBits32( n & 0xffffffff )) << 32); |
193 | 0 | #endif |
194 | 0 | } |
195 | | |
196 | 0 | inline int Bits::Log2FloorNonZero_Portable(uint32 n) { |
197 | 0 | // Just use the common routine |
198 | 0 | return Log2Floor(n); |
199 | 0 | } |
200 | | |
201 | | // Log2Floor64() is defined in terms of Log2Floor32(), Log2FloorNonZero32() |
202 | 0 | inline int Bits::Log2Floor64_Portable(uint64 n) { |
203 | 0 | const uint32 topbits = static_cast<uint32>(n >> 32); |
204 | 0 | if (topbits == 0) { |
205 | 0 | // Top bits are zero, so scan in bottom bits |
206 | 0 | return Log2Floor(static_cast<uint32>(n)); |
207 | 0 | } else { |
208 | 0 | return 32 + Log2FloorNonZero(topbits); |
209 | 0 | } |
210 | 0 | } |
211 | | |
212 | | // Log2FloorNonZero64() is defined in terms of Log2FloorNonZero32() |
213 | 0 | inline int Bits::Log2FloorNonZero64_Portable(uint64 n) { |
214 | 0 | const uint32 topbits = static_cast<uint32>(n >> 32); |
215 | 0 | if (topbits == 0) { |
216 | 0 | // Top bits are zero, so scan in bottom bits |
217 | 0 | return Log2FloorNonZero(static_cast<uint32>(n)); |
218 | 0 | } else { |
219 | 0 | return 32 + Log2FloorNonZero(topbits); |
220 | 0 | } |
221 | 0 | } |
222 | | |
223 | | // FindLSBSetNonZero64() is defined in terms of FindLSBSetNonZero() |
224 | 0 | inline int Bits::FindLSBSetNonZero64_Portable(uint64 n) { |
225 | 0 | const uint32 bottombits = static_cast<uint32>(n); |
226 | 0 | if (bottombits == 0) { |
227 | 0 | // Bottom bits are zero, so scan in top bits |
228 | 0 | return 32 + FindLSBSetNonZero(static_cast<uint32>(n >> 32)); |
229 | 0 | } else { |
230 | 0 | return FindLSBSetNonZero(bottombits); |
231 | 0 | } |
232 | 0 | } |
233 | | |
234 | | template <class T> |
235 | | inline bool Bits::BytesContainByteLessThan(T bytes, uint8 c) { |
236 | | T l = BitPattern<T>::l; |
237 | | T h = BitPattern<T>::h; |
238 | | // The c <= 0x80 code is straight out of Knuth Volume 4. |
239 | | // Usually c will be manifestly constant. |
240 | | return c <= 0x80 ? |
241 | | ((h & (bytes - l * c) & ~bytes) != 0) : |
242 | | ((((bytes - l * c) | (bytes ^ h)) & h) != 0); |
243 | | } |
244 | | |
245 | | template <class T> inline bool Bits::BytesContainByte(T bytes, uint8 c) { |
246 | | // Usually c will be manifestly constant. |
247 | | return Bits::BytesContainByteLessThan<T>(bytes ^ (c * BitPattern<T>::l), 1); |
248 | | } |
249 | | |
250 | | template <class T> |
251 | | inline bool Bits::BytesAllInRange(T bytes, uint8 lo, uint8 hi) { |
252 | | T l = BitPattern<T>::l; |
253 | | T h = BitPattern<T>::h; |
254 | | // In the common case, lo and hi are manifest constants. |
255 | | if (lo > hi) { |
256 | | return false; |
257 | | } |
258 | | if (hi - lo < 128) { |
259 | | T x = bytes - l * lo; |
260 | | T y = bytes + l * (127 - hi); |
261 | | return ((x | y) & h) == 0; |
262 | | } |
263 | | return !Bits::BytesContainByteLessThan(bytes + (255 - hi) * l, |
264 | | lo + (255 - hi)); |
265 | | } |
266 | | |
267 | | #endif // YB_GUTIL_BITS_H |