folly/Bits.h

   1 /*
   2  * Copyright 2014 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)  [constexpr]
  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)  [constexpr]
  25  *    find last (most significant) bit set in a value of an integral type,
  26  *    1-based.  0 = no bits are set (x == 0)
  27  *    for x != 0, findLastSet(x) == 1 + floor(log2(x))
  28  *
  29  * nextPowTwo(x)  [constexpr]
  30  *    Finds the next power of two >= x.
  31  *
  32  * isPowTwo(x)  [constexpr]
  33  *    return true iff x is a power of two
  34  *
  35  * popcount(x)
  36  *    return the number of 1 bits in x
  37  *
  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 #if !defined(__clang__) && !defined(_MSC_VER)
  61 #define FOLLY_INTRINSIC_CONSTEXPR constexpr
  62 #else
  63 // GCC is the only compiler with intrinsics constexpr.
  64 #define FOLLY_INTRINSIC_CONSTEXPR const
  65 #endif
  66
  67 #include <folly/Portability.h>
  68
  69 #include <folly/detail/BitsDetail.h>
  70 #include <folly/detail/BitIteratorDetail.h>
  71 #include <folly/Likely.h>
  72
  73 #if FOLLY_HAVE_BYTESWAP_H
  74 # include <byteswap.h>
  75 #endif
  76
  77 #ifdef _MSC_VER
  78 # include <intrin.h>
  79 # pragma intrinsic(_BitScanForward)
  80 # pragma intrinsic(_BitScanForward64)
  81 # pragma intrinsic(_BitScanReverse)
  82 # pragma intrinsic(_BitScanReverse64)
  83 #endif
  84
  85 #include <cassert>
  86 #include <cinttypes>
  87 #include <iterator>
  88 #include <limits>
  89 #include <type_traits>
  90 #include <boost/iterator/iterator_adaptor.hpp>
  91 #include <stdint.h>
  92
  93 namespace folly {
  94
  95 // Generate overloads for findFirstSet as wrappers around
  96 // appropriate ffs, ffsl, ffsll gcc builtins
  97 template <class T>
  98 inline FOLLY_INTRINSIC_CONSTEXPR
  99 typename std::enable_if<
 100   (std::is_integral<T>::value &&
 101    std::is_unsigned<T>::value &&
 102    sizeof(T) <= sizeof(unsigned int)),
 103   unsigned int>::type
 104   findFirstSet(T x) {
 105 #ifdef _MSC_VER
 106   unsigned long index;
 107   return _BitScanForward(&index, x) ? index : 0;
 108 #else
 109   return __builtin_ffs(x);
 110 #endif
 111 }
 112
 113 template <class T>
 114 inline FOLLY_INTRINSIC_CONSTEXPR
 115 typename std::enable_if<
 116   (std::is_integral<T>::value &&
 117    std::is_unsigned<T>::value &&
 118    sizeof(T) > sizeof(unsigned int) &&
 119    sizeof(T) <= sizeof(unsigned long)),
 120   unsigned int>::type
 121   findFirstSet(T x) {
 122 #ifdef _MSC_VER
 123   unsigned long index;
 124   return _BitScanForward(&index, x) ? index : 0;
 125 #else
 126   return __builtin_ffsl(x);
 127 #endif
 128 }
 129
 130 template <class T>
 131 inline FOLLY_INTRINSIC_CONSTEXPR
 132 typename std::enable_if<
 133   (std::is_integral<T>::value &&
 134    std::is_unsigned<T>::value &&
 135    sizeof(T) > sizeof(unsigned long) &&
 136    sizeof(T) <= sizeof(unsigned long long)),
 137   unsigned int>::type
 138   findFirstSet(T x) {
 139 #ifdef _MSC_VER
 140   unsigned long index;
 141   return _BitScanForward64(&index, x) ? index : 0;
 142 #else
 143   return __builtin_ffsll(x);
 144 #endif
 145 }
 146
 147 template <class T>
 148 inline FOLLY_INTRINSIC_CONSTEXPR
 149 typename std::enable_if<
 150   (std::is_integral<T>::value && std::is_signed<T>::value),
 151   unsigned int>::type
 152   findFirstSet(T x) {
 153   // Note that conversion from a signed type to the corresponding unsigned
 154   // type is technically implementation-defined, but will likely work
 155   // on any impementation that uses two's complement.
 156   return findFirstSet(static_cast<typename std::make_unsigned<T>::type>(x));
 157 }
 158
 159 // findLastSet: return the 1-based index of the highest bit set
 160 // for x > 0, findLastSet(x) == 1 + floor(log2(x))
 161 template <class T>
 162 inline FOLLY_INTRINSIC_CONSTEXPR
 163 typename std::enable_if<
 164   (std::is_integral<T>::value &&
 165    std::is_unsigned<T>::value &&
 166    sizeof(T) <= sizeof(unsigned int)),
 167   unsigned int>::type
 168   findLastSet(T x) {
 169 #ifdef _MSC_VER
 170   unsigned long index;
 171   int clz;
 172   if (_BitScanReverse(&index, x)) {
 173     clz = static_cast<int>(31 - index);
 174   } else {
 175     clz = 32;
 176   }
 177   return x ? 8 * sizeof(unsigned int) - clz : 0;
 178 #else
 179   return x ? 8 * sizeof(unsigned int) - __builtin_clz(x) : 0;
 180 #endif
 181 }
 182
 183 template <class T>
 184 inline FOLLY_INTRINSIC_CONSTEXPR
 185 typename std::enable_if<
 186   (std::is_integral<T>::value &&
 187    std::is_unsigned<T>::value &&
 188    sizeof(T) > sizeof(unsigned int) &&
 189    sizeof(T) <= sizeof(unsigned long)),
 190   unsigned int>::type
 191   findLastSet(T x) {
 192 #ifdef _MSC_VER
 193   unsigned long index;
 194   int clz;
 195   if (_BitScanReverse(&index, x)) {
 196     clz = static_cast<int>(31 - index);
 197   } else {
 198     clz = 32;
 199   }
 200   return x ? 8 * sizeof(unsigned int) - clz : 0;
 201 #else
 202   return x ? 8 * sizeof(unsigned long) - __builtin_clzl(x) : 0;
 203 #endif
 204 }
 205
 206 template <class T>
 207 inline FOLLY_INTRINSIC_CONSTEXPR
 208 typename std::enable_if<
 209   (std::is_integral<T>::value &&
 210    std::is_unsigned<T>::value &&
 211    sizeof(T) > sizeof(unsigned long) &&
 212    sizeof(T) <= sizeof(unsigned long long)),
 213   unsigned int>::type
 214   findLastSet(T x) {
 215 #ifdef _MSC_VER
 216   unsigned long index;
 217   unsigned long long clz;
 218   if (_BitScanReverse(&index, x)) {
 219     clz = static_cast<unsigned long long>(63 - index);
 220   } else {
 221     clz = 64;
 222   }
 223   return x ? 8 * sizeof(unsigned long long) - clz : 0;
 224 #else
 225   return x ? 8 * sizeof(unsigned long long) - __builtin_clzll(x) : 0;
 226 #endif
 227 }
 228
 229 template <class T>
 230 inline FOLLY_INTRINSIC_CONSTEXPR
 231 typename std::enable_if<
 232   (std::is_integral<T>::value &&
 233    std::is_signed<T>::value),
 234   unsigned int>::type
 235   findLastSet(T x) {
 236   return findLastSet(static_cast<typename std::make_unsigned<T>::type>(x));
 237 }
 238
 239 template <class T>
 240 inline FOLLY_INTRINSIC_CONSTEXPR
 241 typename std::enable_if<
 242   std::is_integral<T>::value && std::is_unsigned<T>::value,
 243   T>::type
 244 nextPowTwo(T v) {
 245   return v ? (1ul << findLastSet(v - 1)) : 1;
 246 }
 247
 248 template <class T>
 249 inline constexpr
 250 typename std::enable_if<
 251   std::is_integral<T>::value && std::is_unsigned<T>::value,
 252   bool>::type
 253 isPowTwo(T v) {
 254   return (v != 0) && !(v & (v - 1));
 255 }
 256
 257 /**
 258  * Population count
 259  */
 260 template <class T>
 261 inline typename std::enable_if<
 262   (std::is_integral<T>::value &&
 263    std::is_unsigned<T>::value &&
 264    sizeof(T) <= sizeof(unsigned int)),
 265   size_t>::type
 266   popcount(T x) {
 267   return detail::popcount(x);
 268 }
 269
 270 template <class T>
 271 inline typename std::enable_if<
 272   (std::is_integral<T>::value &&
 273    std::is_unsigned<T>::value &&
 274    sizeof(T) > sizeof(unsigned int) &&
 275    sizeof(T) <= sizeof(unsigned long long)),
 276   size_t>::type
 277   popcount(T x) {
 278   return detail::popcountll(x);
 279 }
 280
 281 /**
 282  * Endianness detection and manipulation primitives.
 283  */
 284 namespace detail {
 285
 286 template <class T>
 287 struct EndianIntBase {
 288  public:
 289   static T swap(T x);
 290 };
 291
 292 #ifndef _MSC_VER
 293
 294 /**
 295  * If we have the bswap_16 macro from byteswap.h, use it; otherwise, provide our
 296  * own definition.
 297  */
 298 #ifdef bswap_16
 299 # define our_bswap16 bswap_16
 300 #else
 301
 302 template<class Int16>
 303 inline constexpr typename std::enable_if<
 304   sizeof(Int16) == 2,
 305   Int16>::type
 306 our_bswap16(Int16 x) {
 307   return ((x >> 8) & 0xff) | ((x & 0xff) << 8);
 308 }
 309 #endif
 310
 311 #endif
 312
 313 #define FB_GEN(t, fn) \
 314 template<> inline t EndianIntBase<t>::swap(t x) { return fn(x); }
 315
 316 // fn(x) expands to (x) if the second argument is empty, which is exactly
 317 // what we want for [u]int8_t. Also, gcc 4.7 on Intel doesn't have
 318 // __builtin_bswap16 for some reason, so we have to provide our own.
 319 FB_GEN( int8_t,)
 320 FB_GEN(uint8_t,)
 321 #ifdef _MSC_VER
 322 FB_GEN( int64_t, _byteswap_uint64)
 323 FB_GEN(uint64_t, _byteswap_uint64)
 324 FB_GEN( int32_t, _byteswap_ulong)
 325 FB_GEN(uint32_t, _byteswap_ulong)
 326 FB_GEN( int16_t, _byteswap_ushort)
 327 FB_GEN(uint16_t, _byteswap_ushort)
 328 #else
 329 FB_GEN( int64_t, __builtin_bswap64)
 330 FB_GEN(uint64_t, __builtin_bswap64)
 331 FB_GEN( int32_t, __builtin_bswap32)
 332 FB_GEN(uint32_t, __builtin_bswap32)
 333 FB_GEN( int16_t, our_bswap16)
 334 FB_GEN(uint16_t, our_bswap16)
 335 #endif
 336
 337 #undef FB_GEN
 338
 339 #if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
 340
 341 template <class T>
 342 struct EndianInt : public detail::EndianIntBase<T> {
 343  public:
 344   static T big(T x) { return EndianInt::swap(x); }
 345   static T little(T x) { return x; }
 346 };
 347
 348 #elif __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__
 349
 350 template <class T>
 351 struct EndianInt : public detail::EndianIntBase<T> {
 352  public:
 353   static T big(T x) { return x; }
 354   static T little(T x) { return EndianInt::swap(x); }
 355 };
 356
 357 #else
 358 # error Your machine uses a weird endianness!
 359 #endif  /* __BYTE_ORDER__ */
 360
 361 }  // namespace detail
 362
 363 // big* convert between native and big-endian representations
 364 // little* convert between native and little-endian representations
 365 // swap* convert between big-endian and little-endian representations
 366 //
 367 // ntohs, htons == big16
 368 // ntohl, htonl == big32
 369 #define FB_GEN1(fn, t, sz) \
 370   static t fn##sz(t x) { return fn<t>(x); } \
 371
 372 #define FB_GEN2(t, sz) \
 373   FB_GEN1(swap, t, sz) \
 374   FB_GEN1(big, t, sz) \
 375   FB_GEN1(little, t, sz)
 376
 377 #define FB_GEN(sz) \
 378   FB_GEN2(uint##sz##_t, sz) \
 379   FB_GEN2(int##sz##_t, sz)
 380
 381 class Endian {
 382  public:
 383   enum class Order : uint8_t {
 384     LITTLE,
 385     BIG
 386   };
 387
 388   static constexpr Order order =
 389 #if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
 390     Order::LITTLE;
 391 #elif __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__
 392     Order::BIG;
 393 #else
 394 # error Your machine uses a weird endianness!
 395 #endif  /* __BYTE_ORDER__ */
 396
 397   template <class T> static T swap(T x) {
 398     return detail::EndianInt<T>::swap(x);
 399   }
 400   template <class T> static T big(T x) {
 401     return detail::EndianInt<T>::big(x);
 402   }
 403   template <class T> static T little(T x) {
 404     return detail::EndianInt<T>::little(x);
 405   }
 406
 407   FB_GEN(64)
 408   FB_GEN(32)
 409   FB_GEN(16)
 410   FB_GEN(8)
 411 };
 412
 413 #undef FB_GEN
 414 #undef FB_GEN2
 415 #undef FB_GEN1
 416
 417 /**
 418  * Fast bit iteration facility.
 419  */
 420
 421
 422 template <class BaseIter> class BitIterator;
 423 template <class BaseIter>
 424 BitIterator<BaseIter> findFirstSet(BitIterator<BaseIter>,
 425                                    BitIterator<BaseIter>);
 426 /**
 427  * Wrapper around an iterator over an integer type that iterates
 428  * over its underlying bits in LSb to MSb order.
 429  *
 430  * BitIterator models the same iterator concepts as the base iterator.
 431  */
 432 template <class BaseIter>
 433 class BitIterator
 434   : public bititerator_detail::BitIteratorBase<BaseIter>::type {
 435  public:
 436   /**
 437    * Return the number of bits in an element of the underlying iterator.
 438    */
 439   static size_t bitsPerBlock() {
 440     return std::numeric_limits<
 441       typename std::make_unsigned<
 442         typename std::iterator_traits<BaseIter>::value_type
 443       >::type
 444     >::digits;
 445   }
 446
 447   /**
 448    * Construct a BitIterator that points at a given bit offset (default 0)
 449    * in iter.
 450    */
 451   #pragma GCC diagnostic push // bitOffset shadows a member
 452   #pragma GCC diagnostic ignored "-Wshadow"
 453   explicit BitIterator(const BaseIter& iter, size_t bitOffset=0)
 454     : bititerator_detail::BitIteratorBase<BaseIter>::type(iter),
 455       bitOffset_(bitOffset) {
 456     assert(bitOffset_ < bitsPerBlock());
 457   }
 458   #pragma GCC diagnostic pop
 459
 460   size_t bitOffset() const {
 461     return bitOffset_;
 462   }
 463
 464   void advanceToNextBlock() {
 465     bitOffset_ = 0;
 466     ++this->base_reference();
 467   }
 468
 469   BitIterator& operator=(const BaseIter& other) {
 470     this->~BitIterator();
 471     new (this) BitIterator(other);
 472     return *this;
 473   }
 474
 475  private:
 476   friend class boost::iterator_core_access;
 477   friend BitIterator findFirstSet<>(BitIterator, BitIterator);
 478
 479   typedef bititerator_detail::BitReference<
 480       typename std::iterator_traits<BaseIter>::reference,
 481       typename std::iterator_traits<BaseIter>::value_type
 482     > BitRef;
 483
 484   void advanceInBlock(size_t n) {
 485     bitOffset_ += n;
 486     assert(bitOffset_ < bitsPerBlock());
 487   }
 488
 489   BitRef dereference() const {
 490     return BitRef(*this->base_reference(), bitOffset_);
 491   }
 492
 493   void advance(ssize_t n) {
 494     size_t bpb = bitsPerBlock();
 495     ssize_t blocks = n / bpb;
 496     bitOffset_ += n % bpb;
 497     if (bitOffset_ >= bpb) {
 498       bitOffset_ -= bpb;
 499       ++blocks;
 500     }
 501     this->base_reference() += blocks;
 502   }
 503
 504   void increment() {
 505     if (++bitOffset_ == bitsPerBlock()) {
 506       advanceToNextBlock();
 507     }
 508   }
 509
 510   void decrement() {
 511     if (bitOffset_-- == 0) {
 512       bitOffset_ = bitsPerBlock() - 1;
 513       --this->base_reference();
 514     }
 515   }
 516
 517   bool equal(const BitIterator& other) const {
 518     return (bitOffset_ == other.bitOffset_ &&
 519             this->base_reference() == other.base_reference());
 520   }
 521
 522   ssize_t distance_to(const BitIterator& other) const {
 523     return
 524       (other.base_reference() - this->base_reference()) * bitsPerBlock() +
 525       (other.bitOffset_ - bitOffset_);
 526   }
 527
 528   ssize_t bitOffset_;
 529 };
 530
 531 /**
 532  * Helper function, so you can write
 533  * auto bi = makeBitIterator(container.begin());
 534  */
 535 template <class BaseIter>
 536 BitIterator<BaseIter> makeBitIterator(const BaseIter& iter) {
 537   return BitIterator<BaseIter>(iter);
 538 }
 539
 540
 541 /**
 542  * Find first bit set in a range of bit iterators.
 543  * 4.5x faster than the obvious std::find(begin, end, true);
 544  */
 545 template <class BaseIter>
 546 BitIterator<BaseIter> findFirstSet(BitIterator<BaseIter> begin,
 547                                    BitIterator<BaseIter> end) {
 548   // shortcut to avoid ugly static_cast<>
 549   static const typename BaseIter::value_type one = 1;
 550
 551   while (begin.base() != end.base()) {
 552     typename BaseIter::value_type v = *begin.base();
 553     // mask out the bits that don't matter (< begin.bitOffset)
 554     v &= ~((one << begin.bitOffset()) - 1);
 555     size_t firstSet = findFirstSet(v);
 556     if (firstSet) {
 557       --firstSet;  // now it's 0-based
 558       assert(firstSet >= begin.bitOffset());
 559       begin.advanceInBlock(firstSet - begin.bitOffset());
 560       return begin;
 561     }
 562     begin.advanceToNextBlock();
 563   }
 564
 565   // now begin points to the same block as end
 566   if (end.bitOffset() != 0) {  // assume end is dereferenceable
 567     typename BaseIter::value_type v = *begin.base();
 568     // mask out the bits that don't matter (< begin.bitOffset)
 569     v &= ~((one << begin.bitOffset()) - 1);
 570     // mask out the bits that don't matter (>= end.bitOffset)
 571     v &= (one << end.bitOffset()) - 1;
 572     size_t firstSet = findFirstSet(v);
 573     if (firstSet) {
 574       --firstSet;  // now it's 0-based
 575       assert(firstSet >= begin.bitOffset());
 576       begin.advanceInBlock(firstSet - begin.bitOffset());
 577       return begin;
 578     }
 579   }
 580
 581   return end;
 582 }
 583
 584
 585 template <class T, class Enable=void> struct Unaligned;
 586
 587 /**
 588  * Representation of an unaligned value of a POD type.
 589  */
 590 FOLLY_PACK_PUSH
 591 template <class T>
 592 struct Unaligned<
 593     T,
 594     typename std::enable_if<std::is_pod<T>::value>::type> {
 595   Unaligned() = default;  // uninitialized
 596   /* implicit */ Unaligned(T v) : value(v) { }
 597   T value;
 598 } FOLLY_PACK_ATTR;
 599 FOLLY_PACK_POP
 600
 601 /**
 602  * Read an unaligned value of type T and return it.
 603  */
 604 template <class T>
 605 inline T loadUnaligned(const void* p) {
 606   static_assert(sizeof(Unaligned<T>) == sizeof(T), "Invalid unaligned size");
 607   static_assert(alignof(Unaligned<T>) == 1, "Invalid alignment");
 608   return static_cast<const Unaligned<T>*>(p)->value;
 609 }
 610
 611 /**
 612  * Write an unaligned value of type T.
 613  */
 614 template <class T>
 615 inline void storeUnaligned(void* p, T value) {
 616   static_assert(sizeof(Unaligned<T>) == sizeof(T), "Invalid unaligned size");
 617   static_assert(alignof(Unaligned<T>) == 1, "Invalid alignment");
 618   new (p) Unaligned<T>(value);
 619 }
 620
 621 }  // namespace folly
 622
 623 #endif /* FOLLY_BITS_H_ */