Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
Newer
Older
100644 525 lines (454 sloc) 13.401 kb
27494a2 jdelong Pull from FB rev 63ce89e2f2301e6bba44a111cc7d4218022156f6
jdelong authored
1 /*
2 * Copyright 2012 Facebook, Inc.
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 /**
18 * Various low-level, bit-manipulation routines.
19 *
20 * findFirstSet(x)
21 * find first (least significant) bit set in a value of an integral type,
22 * 1-based (like ffs()). 0 = no bits are set (x == 0)
23 *
24 * findLastSet(x)
25 * find last (most significant) bit set in a value of an integral type,
26 * 1-based. 0 = no bits are set (x == 0)
d50251a Tudor Bosman (minor changes, part of unrelated diff)
tudor authored
27 * for x != 0, findLastSet(x) == 1 + floor(log2(x))
27494a2 jdelong Pull from FB rev 63ce89e2f2301e6bba44a111cc7d4218022156f6
jdelong authored
28 *
7fd87e7 Tudor Bosman Detect popcnt instruction at runtime, use it if available.
tudor authored
29 * popcount(x)
30 * return the number of 1 bits in x
31 *
27494a2 jdelong Pull from FB rev 63ce89e2f2301e6bba44a111cc7d4218022156f6
jdelong authored
32 * nextPowTwo(x)
33 * Finds the next power of two >= x.
34 *
ce15293 isPowTwo
Michael Curtiss authored
35 * isPowTwo(x)
36 * return true iff x is a power of two
37 *
27494a2 jdelong Pull from FB rev 63ce89e2f2301e6bba44a111cc7d4218022156f6
jdelong authored
38 * Endian
39 * convert between native, big, and little endian representation
40 * Endian::big(x) big <-> native
41 * Endian::little(x) little <-> native
42 * Endian::swap(x) big <-> little
43 *
44 * BitIterator
45 * Wrapper around an iterator over an integral type that iterates
46 * over its underlying bits in MSb to LSb order
47 *
48 * findFirstSet(BitIterator begin, BitIterator end)
49 * return a BitIterator pointing to the first 1 bit in [begin, end), or
50 * end if all bits in [begin, end) are 0
51 *
52 * @author Tudor Bosman (tudorb@fb.com)
53 */
54
55 #ifndef FOLLY_BITS_H_
56 #define FOLLY_BITS_H_
57
58 #include "folly/Portability.h"
59
60 #ifndef _GNU_SOURCE
61 #define _GNU_SOURCE 1
62 #endif
63
7fd87e7 Tudor Bosman Detect popcnt instruction at runtime, use it if available.
tudor authored
64 #ifndef __GNUC__
65 #error GCC required
66 #endif
67
68 #include "folly/detail/BitsDetail.h"
27494a2 jdelong Pull from FB rev 63ce89e2f2301e6bba44a111cc7d4218022156f6
jdelong authored
69 #include "folly/detail/BitIteratorDetail.h"
70 #include "folly/Likely.h"
71
72 #include <byteswap.h>
73 #include <cassert>
74 #include <cinttypes>
75 #include <endian.h>
76 #include <iterator>
77 #include <limits>
78 #include <type_traits>
79 #include <boost/iterator/iterator_adaptor.hpp>
80 #include <stdint.h>
81
82 namespace folly {
83
84 // Generate overloads for findFirstSet as wrappers around
2d94f42 Tudor Bosman Use gcc builtins instead of library functions for ffs*
tudor authored
85 // appropriate ffs, ffsl, ffsll gcc builtins
27494a2 jdelong Pull from FB rev 63ce89e2f2301e6bba44a111cc7d4218022156f6
jdelong authored
86 template <class T>
87 typename std::enable_if<
88 (std::is_integral<T>::value &&
2d94f42 Tudor Bosman Use gcc builtins instead of library functions for ffs*
tudor authored
89 std::is_unsigned<T>::value &&
442e1c0 Tudor Bosman sizeof works just as well as numeric_limits<T>::digits
tudor authored
90 sizeof(T) <= sizeof(unsigned int)),
27494a2 jdelong Pull from FB rev 63ce89e2f2301e6bba44a111cc7d4218022156f6
jdelong authored
91 unsigned int>::type
92 findFirstSet(T x) {
2d94f42 Tudor Bosman Use gcc builtins instead of library functions for ffs*
tudor authored
93 return __builtin_ffs(x);
27494a2 jdelong Pull from FB rev 63ce89e2f2301e6bba44a111cc7d4218022156f6
jdelong authored
94 }
95
96 template <class T>
97 typename std::enable_if<
98 (std::is_integral<T>::value &&
2d94f42 Tudor Bosman Use gcc builtins instead of library functions for ffs*
tudor authored
99 std::is_unsigned<T>::value &&
442e1c0 Tudor Bosman sizeof works just as well as numeric_limits<T>::digits
tudor authored
100 sizeof(T) > sizeof(unsigned int) &&
101 sizeof(T) <= sizeof(unsigned long)),
27494a2 jdelong Pull from FB rev 63ce89e2f2301e6bba44a111cc7d4218022156f6
jdelong authored
102 unsigned int>::type
103 findFirstSet(T x) {
2d94f42 Tudor Bosman Use gcc builtins instead of library functions for ffs*
tudor authored
104 return __builtin_ffsl(x);
27494a2 jdelong Pull from FB rev 63ce89e2f2301e6bba44a111cc7d4218022156f6
jdelong authored
105 }
106
107 template <class T>
108 typename std::enable_if<
109 (std::is_integral<T>::value &&
2d94f42 Tudor Bosman Use gcc builtins instead of library functions for ffs*
tudor authored
110 std::is_unsigned<T>::value &&
442e1c0 Tudor Bosman sizeof works just as well as numeric_limits<T>::digits
tudor authored
111 sizeof(T) > sizeof(unsigned long) &&
112 sizeof(T) <= sizeof(unsigned long long)),
27494a2 jdelong Pull from FB rev 63ce89e2f2301e6bba44a111cc7d4218022156f6
jdelong authored
113 unsigned int>::type
114 findFirstSet(T x) {
2d94f42 Tudor Bosman Use gcc builtins instead of library functions for ffs*
tudor authored
115 return __builtin_ffsll(x);
27494a2 jdelong Pull from FB rev 63ce89e2f2301e6bba44a111cc7d4218022156f6
jdelong authored
116 }
117
118 template <class T>
119 typename std::enable_if<
2d94f42 Tudor Bosman Use gcc builtins instead of library functions for ffs*
tudor authored
120 (std::is_integral<T>::value && std::is_signed<T>::value),
27494a2 jdelong Pull from FB rev 63ce89e2f2301e6bba44a111cc7d4218022156f6
jdelong authored
121 unsigned int>::type
122 findFirstSet(T x) {
2d94f42 Tudor Bosman Use gcc builtins instead of library functions for ffs*
tudor authored
123 // Note that conversion from a signed type to the corresponding unsigned
27494a2 jdelong Pull from FB rev 63ce89e2f2301e6bba44a111cc7d4218022156f6
jdelong authored
124 // type is technically implementation-defined, but will likely work
125 // on any impementation that uses two's complement.
2d94f42 Tudor Bosman Use gcc builtins instead of library functions for ffs*
tudor authored
126 return findFirstSet(static_cast<typename std::make_unsigned<T>::type>(x));
27494a2 jdelong Pull from FB rev 63ce89e2f2301e6bba44a111cc7d4218022156f6
jdelong authored
127 }
128
129 // findLastSet: return the 1-based index of the highest bit set
130 // for x > 0, findLastSet(x) == 1 + floor(log2(x))
131 template <class T>
132 typename std::enable_if<
133 (std::is_integral<T>::value &&
134 std::is_unsigned<T>::value &&
442e1c0 Tudor Bosman sizeof works just as well as numeric_limits<T>::digits
tudor authored
135 sizeof(T) <= sizeof(unsigned int)),
27494a2 jdelong Pull from FB rev 63ce89e2f2301e6bba44a111cc7d4218022156f6
jdelong authored
136 unsigned int>::type
137 findLastSet(T x) {
138 return x ? 8 * sizeof(unsigned int) - __builtin_clz(x) : 0;
139 }
140
141 template <class T>
142 typename std::enable_if<
143 (std::is_integral<T>::value &&
144 std::is_unsigned<T>::value &&
442e1c0 Tudor Bosman sizeof works just as well as numeric_limits<T>::digits
tudor authored
145 sizeof(T) > sizeof(unsigned int) &&
146 sizeof(T) <= sizeof(unsigned long)),
27494a2 jdelong Pull from FB rev 63ce89e2f2301e6bba44a111cc7d4218022156f6
jdelong authored
147 unsigned int>::type
148 findLastSet(T x) {
149 return x ? 8 * sizeof(unsigned long) - __builtin_clzl(x) : 0;
150 }
151
152 template <class T>
153 typename std::enable_if<
154 (std::is_integral<T>::value &&
155 std::is_unsigned<T>::value &&
442e1c0 Tudor Bosman sizeof works just as well as numeric_limits<T>::digits
tudor authored
156 sizeof(T) > sizeof(unsigned long) &&
157 sizeof(T) <= sizeof(unsigned long long)),
27494a2 jdelong Pull from FB rev 63ce89e2f2301e6bba44a111cc7d4218022156f6
jdelong authored
158 unsigned int>::type
159 findLastSet(T x) {
160 return x ? 8 * sizeof(unsigned long long) - __builtin_clzll(x) : 0;
161 }
162
163 template <class T>
164 typename std::enable_if<
165 (std::is_integral<T>::value &&
166 std::is_signed<T>::value),
167 unsigned int>::type
168 findLastSet(T x) {
169 return findLastSet(static_cast<typename std::make_unsigned<T>::type>(x));
170 }
171
172 template <class T>
173 inline
174 typename std::enable_if<
175 std::is_integral<T>::value && std::is_unsigned<T>::value,
176 T>::type
177 nextPowTwo(T v) {
178 if (UNLIKELY(v == 0)) {
179 return 1;
180 }
181 return 1ul << findLastSet(v - 1);
182 }
183
ce15293 isPowTwo
Michael Curtiss authored
184 template <class T>
185 inline
186 typename std::enable_if<
187 std::is_integral<T>::value && std::is_unsigned<T>::value,
188 bool>::type
189 isPowTwo(T v) {
190 return ((v != 0) && !(v & (v-1))); // yes, this is endian-agnostic
191 }
192
7fd87e7 Tudor Bosman Detect popcnt instruction at runtime, use it if available.
tudor authored
193 /**
194 * Population count
195 */
27494a2 jdelong Pull from FB rev 63ce89e2f2301e6bba44a111cc7d4218022156f6
jdelong authored
196 template <class T>
7fd87e7 Tudor Bosman Detect popcnt instruction at runtime, use it if available.
tudor authored
197 inline typename std::enable_if<
198 (std::is_integral<T>::value &&
199 std::is_unsigned<T>::value &&
200 sizeof(T) <= sizeof(unsigned int)),
201 size_t>::type
202 popcount(T x) {
203 return detail::popcount(x);
27494a2 jdelong Pull from FB rev 63ce89e2f2301e6bba44a111cc7d4218022156f6
jdelong authored
204 }
205
7fd87e7 Tudor Bosman Detect popcnt instruction at runtime, use it if available.
tudor authored
206 template <class T>
207 inline typename std::enable_if<
208 (std::is_integral<T>::value &&
209 std::is_unsigned<T>::value &&
210 sizeof(T) > sizeof(unsigned int) &&
211 sizeof(T) <= sizeof(unsigned long long)),
212 size_t>::type
213 popcount(T x) {
214 return detail::popcountll(x);
215 }
27494a2 jdelong Pull from FB rev 63ce89e2f2301e6bba44a111cc7d4218022156f6
jdelong authored
216
217 /**
218 * Endianness detection and manipulation primitives.
219 */
220 namespace detail {
221
222 template <class T>
223 struct EndianIntBase {
224 public:
225 static T swap(T x);
226 };
227
228 #define FB_GEN(t, fn) \
229 template<> inline t EndianIntBase<t>::swap(t x) { return fn(x); }
230
231 // fn(x) expands to (x) if the second argument is empty, which is exactly
232 // what we want for [u]int8_t
233 FB_GEN( int8_t,)
234 FB_GEN(uint8_t,)
235 FB_GEN( int64_t, bswap_64)
236 FB_GEN(uint64_t, bswap_64)
237 FB_GEN( int32_t, bswap_32)
238 FB_GEN(uint32_t, bswap_32)
239 FB_GEN( int16_t, bswap_16)
240 FB_GEN(uint16_t, bswap_16)
241
242 #undef FB_GEN
243
244 #if __BYTE_ORDER == __LITTLE_ENDIAN
245
246 template <class T>
247 struct EndianInt : public detail::EndianIntBase<T> {
248 public:
249 static T big(T x) { return EndianInt::swap(x); }
250 static T little(T x) { return x; }
251 };
252
253 #elif __BYTE_ORDER == __BIG_ENDIAN
254
255 template <class T>
256 struct EndianInt : public detail::EndianIntBase<T> {
257 public:
258 static T big(T x) { return x; }
259 static T little(T x) { return EndianInt::swap(x); }
260 };
261
262 #else
263 # error Your machine uses a weird endianness!
264 #endif /* __BYTE_ORDER */
265
266 } // namespace detail
267
268 // big* convert between native and big-endian representations
269 // little* convert between native and little-endian representations
270 // swap* convert between big-endian and little-endian representations
271 //
272 // ntohs, htons == big16
273 // ntohl, htonl == big32
274 #define FB_GEN1(fn, t, sz) \
275 static t fn##sz(t x) { return fn<t>(x); } \
276
277 #define FB_GEN2(t, sz) \
278 FB_GEN1(swap, t, sz) \
279 FB_GEN1(big, t, sz) \
280 FB_GEN1(little, t, sz)
281
282 #define FB_GEN(sz) \
283 FB_GEN2(uint##sz##_t, sz) \
284 FB_GEN2(int##sz##_t, sz)
285
286 class Endian {
287 public:
1034506 Tudor Bosman Minor changes to folly/experimental/io
tudor authored
288 enum class Order : uint8_t {
289 LITTLE,
290 BIG
291 };
292
293 static constexpr Order order =
294 #if __BYTE_ORDER == __LITTLE_ENDIAN
295 Order::LITTLE;
296 #elif __BYTE_ORDER == __BIG_ENDIAN
297 Order::BIG;
298 #else
299 # error Your machine uses a weird endianness!
300 #endif /* __BYTE_ORDER */
301
27494a2 jdelong Pull from FB rev 63ce89e2f2301e6bba44a111cc7d4218022156f6
jdelong authored
302 template <class T> static T swap(T x) {
303 return detail::EndianInt<T>::swap(x);
304 }
305 template <class T> static T big(T x) {
306 return detail::EndianInt<T>::big(x);
307 }
308 template <class T> static T little(T x) {
309 return detail::EndianInt<T>::little(x);
310 }
311
312 FB_GEN(64)
313 FB_GEN(32)
314 FB_GEN(16)
315 FB_GEN(8)
316 };
317
318 #undef FB_GEN
319 #undef FB_GEN2
320 #undef FB_GEN1
321
322 /**
323 * Fast bit iteration facility.
324 */
325
326
327 template <class BaseIter> class BitIterator;
328 template <class BaseIter>
329 BitIterator<BaseIter> findFirstSet(BitIterator<BaseIter>,
330 BitIterator<BaseIter>);
331 /**
332 * Wrapper around an iterator over an integer type that iterates
333 * over its underlying bits in LSb to MSb order.
334 *
335 * BitIterator models the same iterator concepts as the base iterator.
336 */
337 template <class BaseIter>
338 class BitIterator
339 : public bititerator_detail::BitIteratorBase<BaseIter>::type {
340 public:
341 /**
342 * Return the number of bits in an element of the underlying iterator.
343 */
344 static size_t bitsPerBlock() {
345 return std::numeric_limits<
346 typename std::make_unsigned<
347 typename std::iterator_traits<BaseIter>::value_type
348 >::type
349 >::digits;
350 }
351
352 /**
353 * Construct a BitIterator that points at a given bit offset (default 0)
354 * in iter.
355 */
356 explicit BitIterator(const BaseIter& iter, size_t bitOffset=0)
357 : bititerator_detail::BitIteratorBase<BaseIter>::type(iter),
358 bitOffset_(bitOffset) {
359 assert(bitOffset_ < bitsPerBlock());
360 }
361
362 size_t bitOffset() const {
363 return bitOffset_;
364 }
365
366 void advanceToNextBlock() {
367 bitOffset_ = 0;
368 ++this->base_reference();
369 }
370
371 BitIterator& operator=(const BaseIter& other) {
372 this->~BitIterator();
373 new (this) BitIterator(other);
374 return *this;
375 }
376
377 private:
378 friend class boost::iterator_core_access;
379 friend BitIterator findFirstSet<>(BitIterator, BitIterator);
380
381 typedef bititerator_detail::BitReference<
382 typename std::iterator_traits<BaseIter>::reference,
383 typename std::iterator_traits<BaseIter>::value_type
384 > BitRef;
385
386 void advanceInBlock(size_t n) {
387 bitOffset_ += n;
388 assert(bitOffset_ < bitsPerBlock());
389 }
390
391 BitRef dereference() const {
392 return BitRef(*this->base_reference(), bitOffset_);
393 }
394
395 void advance(ssize_t n) {
396 size_t bpb = bitsPerBlock();
397 ssize_t blocks = n / bpb;
398 bitOffset_ += n % bpb;
399 if (bitOffset_ >= bpb) {
400 bitOffset_ -= bpb;
401 ++blocks;
402 }
403 this->base_reference() += blocks;
404 }
405
406 void increment() {
407 if (++bitOffset_ == bitsPerBlock()) {
408 advanceToNextBlock();
409 }
410 }
411
412 void decrement() {
413 if (bitOffset_-- == 0) {
414 bitOffset_ = bitsPerBlock() - 1;
415 --this->base_reference();
416 }
417 }
418
419 bool equal(const BitIterator& other) const {
420 return (bitOffset_ == other.bitOffset_ &&
421 this->base_reference() == other.base_reference());
422 }
423
424 ssize_t distance_to(const BitIterator& other) const {
425 return
426 (other.base_reference() - this->base_reference()) * bitsPerBlock() +
427 (other.bitOffset_ - bitOffset_);
428 }
429
430 ssize_t bitOffset_;
431 };
432
433 /**
434 * Helper function, so you can write
435 * auto bi = makeBitIterator(container.begin());
436 */
437 template <class BaseIter>
438 BitIterator<BaseIter> makeBitIterator(const BaseIter& iter) {
439 return BitIterator<BaseIter>(iter);
440 }
441
442
443 /**
444 * Find first bit set in a range of bit iterators.
445 * 4.5x faster than the obvious std::find(begin, end, true);
446 */
447 template <class BaseIter>
448 BitIterator<BaseIter> findFirstSet(BitIterator<BaseIter> begin,
449 BitIterator<BaseIter> end) {
450 // shortcut to avoid ugly static_cast<>
451 static const typename BaseIter::value_type one = 1;
452
453 while (begin.base() != end.base()) {
454 typename BaseIter::value_type v = *begin.base();
455 // mask out the bits that don't matter (< begin.bitOffset)
456 v &= ~((one << begin.bitOffset()) - 1);
457 size_t firstSet = findFirstSet(v);
458 if (firstSet) {
459 --firstSet; // now it's 0-based
460 assert(firstSet >= begin.bitOffset());
461 begin.advanceInBlock(firstSet - begin.bitOffset());
462 return begin;
463 }
464 begin.advanceToNextBlock();
465 }
466
467 // now begin points to the same block as end
468 if (end.bitOffset() != 0) { // assume end is dereferenceable
469 typename BaseIter::value_type v = *begin.base();
470 // mask out the bits that don't matter (< begin.bitOffset)
471 v &= ~((one << begin.bitOffset()) - 1);
472 // mask out the bits that don't matter (>= end.bitOffset)
473 v &= (one << end.bitOffset()) - 1;
474 size_t firstSet = findFirstSet(v);
475 if (firstSet) {
476 --firstSet; // now it's 0-based
477 assert(firstSet >= begin.bitOffset());
478 begin.advanceInBlock(firstSet - begin.bitOffset());
479 return begin;
480 }
481 }
482
483 return end;
484 }
485
8ff6fe9 Tudor Bosman Deuglify unaligned accesses in GroupVarint.
tudor authored
486
487 template <class T, class Enable=void> struct Unaligned;
488
7488db1 Tudor Bosman Make Bits<T> work with T = Unaligned<X> (X is unsigned integral type)
tudor authored
489 /**
490 * Representation of an unaligned value of a POD type.
491 */
8ff6fe9 Tudor Bosman Deuglify unaligned accesses in GroupVarint.
tudor authored
492 template <class T>
493 struct Unaligned<
7488db1 Tudor Bosman Make Bits<T> work with T = Unaligned<X> (X is unsigned integral type)
tudor authored
494 T,
495 typename std::enable_if<std::is_pod<T>::value>::type> {
496 Unaligned() { } // uninitialized
497 /* implicit */ Unaligned(T v) : value(v) { }
8ff6fe9 Tudor Bosman Deuglify unaligned accesses in GroupVarint.
tudor authored
498 T value;
499 } __attribute__((packed));
500
501 /**
502 * Read an unaligned value of type T and return it.
503 */
504 template <class T>
505 inline T loadUnaligned(const void* p) {
7488db1 Tudor Bosman Make Bits<T> work with T = Unaligned<X> (X is unsigned integral type)
tudor authored
506 static_assert(sizeof(Unaligned<T>) == sizeof(T), "Invalid unaligned size");
6dca2b3 Tudor Bosman (minor changes, part of unrelated diff)
tudor authored
507 static_assert(alignof(Unaligned<T>) == 1, "Invalid alignment");
508 return static_cast<const Unaligned<T>*>(p)->value;
8ff6fe9 Tudor Bosman Deuglify unaligned accesses in GroupVarint.
tudor authored
509 }
510
511 /**
512 * Write an unaligned value of type T.
513 */
514 template <class T>
515 inline void storeUnaligned(void* p, T value) {
7488db1 Tudor Bosman Make Bits<T> work with T = Unaligned<X> (X is unsigned integral type)
tudor authored
516 static_assert(sizeof(Unaligned<T>) == sizeof(T), "Invalid unaligned size");
6dca2b3 Tudor Bosman (minor changes, part of unrelated diff)
tudor authored
517 static_assert(alignof(Unaligned<T>) == 1, "Invalid alignment");
7488db1 Tudor Bosman Make Bits<T> work with T = Unaligned<X> (X is unsigned integral type)
tudor authored
518 new (p) Unaligned<T>(value);
8ff6fe9 Tudor Bosman Deuglify unaligned accesses in GroupVarint.
tudor authored
519 }
520
27494a2 jdelong Pull from FB rev 63ce89e2f2301e6bba44a111cc7d4218022156f6
jdelong authored
521 } // namespace folly
522
523 #endif /* FOLLY_BITS_H_ */
524
Something went wrong with that request. Please try again.