folly/Bits.h

   1 /*
   2  * Copyright 2017 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 #pragma once
  56
  57 #if !defined(__clang__) && !(defined(_MSC_VER) && (_MSC_VER < 1900))
  58 #define FOLLY_INTRINSIC_CONSTEXPR constexpr
  59 #else
  60 // GCC and MSVC 2015+ are the only compilers with
  61 // intrinsics constexpr.
  62 #define FOLLY_INTRINSIC_CONSTEXPR const
  63 #endif
  64
  65 #include <folly/Portability.h>
  66 #include <folly/portability/Builtins.h>
  67
  68 #include <folly/Assume.h>
  69 #include <folly/detail/BitsDetail.h>
  70 #include <folly/detail/BitIteratorDetail.h>
  71 #include <folly/Likely.h>
  72
  73 #include <cassert>
  74 #include <cstring>
  75 #include <cinttypes>
  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
  85 // appropriate ffs, ffsl, ffsll gcc builtins
  86 template <class T>
  87 inline FOLLY_INTRINSIC_CONSTEXPR
  88 typename std::enable_if<
  89   (std::is_integral<T>::value &&
  90    std::is_unsigned<T>::value &&
  91    sizeof(T) <= sizeof(unsigned int)),
  92   unsigned int>::type
  93   findFirstSet(T x) {
  94   return static_cast<unsigned int>(__builtin_ffs(static_cast<int>(x)));
  95 }
  96
  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    sizeof(T) <= sizeof(unsigned long)),
 104   unsigned int>::type
 105   findFirstSet(T x) {
 106   return static_cast<unsigned int>(__builtin_ffsl(static_cast<long>(x)));
 107 }
 108
 109 template <class T>
 110 inline FOLLY_INTRINSIC_CONSTEXPR
 111 typename std::enable_if<
 112   (std::is_integral<T>::value &&
 113    std::is_unsigned<T>::value &&
 114    sizeof(T) > sizeof(unsigned long) &&
 115    sizeof(T) <= sizeof(unsigned long long)),
 116   unsigned int>::type
 117   findFirstSet(T x) {
 118   return static_cast<unsigned int>(__builtin_ffsll(static_cast<long long>(x)));
 119 }
 120
 121 template <class T>
 122 inline FOLLY_INTRINSIC_CONSTEXPR
 123 typename std::enable_if<
 124   (std::is_integral<T>::value && std::is_signed<T>::value),
 125   unsigned int>::type
 126   findFirstSet(T x) {
 127   // Note that conversion from a signed type to the corresponding unsigned
 128   // type is technically implementation-defined, but will likely work
 129   // on any impementation that uses two's complement.
 130   return findFirstSet(static_cast<typename std::make_unsigned<T>::type>(x));
 131 }
 132
 133 // findLastSet: return the 1-based index of the highest bit set
 134 // for x > 0, findLastSet(x) == 1 + floor(log2(x))
 135 template <class T>
 136 inline FOLLY_INTRINSIC_CONSTEXPR
 137 typename std::enable_if<
 138   (std::is_integral<T>::value &&
 139    std::is_unsigned<T>::value &&
 140    sizeof(T) <= sizeof(unsigned int)),
 141   unsigned int>::type
 142   findLastSet(T x) {
 143   // If X is a power of two X - Y = ((X - 1) ^ Y) + 1. Doing this transformation
 144   // allows GCC to remove its own xor that it adds to implement clz using bsr
 145   return x ? ((8 * sizeof(unsigned int) - 1) ^ __builtin_clz(x)) + 1 : 0;
 146 }
 147
 148 template <class T>
 149 inline FOLLY_INTRINSIC_CONSTEXPR
 150 typename std::enable_if<
 151   (std::is_integral<T>::value &&
 152    std::is_unsigned<T>::value &&
 153    sizeof(T) > sizeof(unsigned int) &&
 154    sizeof(T) <= sizeof(unsigned long)),
 155   unsigned int>::type
 156   findLastSet(T x) {
 157   return x ? ((8 * sizeof(unsigned long) - 1) ^ __builtin_clzl(x)) + 1 : 0;
 158 }
 159
 160 template <class T>
 161 inline FOLLY_INTRINSIC_CONSTEXPR
 162 typename std::enable_if<
 163   (std::is_integral<T>::value &&
 164    std::is_unsigned<T>::value &&
 165    sizeof(T) > sizeof(unsigned long) &&
 166    sizeof(T) <= sizeof(unsigned long long)),
 167   unsigned int>::type
 168   findLastSet(T x) {
 169   return x ? ((8 * sizeof(unsigned long long) - 1) ^ __builtin_clzll(x)) + 1
 170            : 0;
 171 }
 172
 173 template <class T>
 174 inline FOLLY_INTRINSIC_CONSTEXPR
 175 typename std::enable_if<
 176   (std::is_integral<T>::value &&
 177    std::is_signed<T>::value),
 178   unsigned int>::type
 179   findLastSet(T x) {
 180   return findLastSet(static_cast<typename std::make_unsigned<T>::type>(x));
 181 }
 182
 183 template <class T>
 184 inline FOLLY_INTRINSIC_CONSTEXPR
 185 typename std::enable_if<
 186   std::is_integral<T>::value && std::is_unsigned<T>::value,
 187   T>::type
 188 nextPowTwo(T v) {
 189   return v ? (T(1) << findLastSet(v - 1)) : 1;
 190 }
 191
 192 template <class T>
 193 inline FOLLY_INTRINSIC_CONSTEXPR typename std::
 194     enable_if<std::is_integral<T>::value && std::is_unsigned<T>::value, T>::type
 195     prevPowTwo(T v) {
 196   return v ? (T(1) << (findLastSet(v) - 1)) : 0;
 197 }
 198
 199 template <class T>
 200 inline constexpr typename std::enable_if<
 201     std::is_integral<T>::value && std::is_unsigned<T>::value,
 202     bool>::type
 203 isPowTwo(T v) {
 204   return (v != 0) && !(v & (v - 1));
 205 }
 206
 207 /**
 208  * Population count
 209  */
 210 template <class T>
 211 inline typename std::enable_if<
 212   (std::is_integral<T>::value &&
 213    std::is_unsigned<T>::value &&
 214    sizeof(T) <= sizeof(unsigned int)),
 215   size_t>::type
 216   popcount(T x) {
 217   return size_t(detail::popcount(x));
 218 }
 219
 220 template <class T>
 221 inline typename std::enable_if<
 222   (std::is_integral<T>::value &&
 223    std::is_unsigned<T>::value &&
 224    sizeof(T) > sizeof(unsigned int) &&
 225    sizeof(T) <= sizeof(unsigned long long)),
 226   size_t>::type
 227   popcount(T x) {
 228   return size_t(detail::popcountll(x));
 229 }
 230
 231 /**
 232  * Endianness detection and manipulation primitives.
 233  */
 234 namespace detail {
 235
 236 template <size_t Size>
 237 struct uint_types_by_size;
 238
 239 #define FB_GEN(sz, fn)                                      \
 240   static inline uint##sz##_t byteswap_gen(uint##sz##_t v) { \
 241     return fn(v);                                           \
 242   }                                                         \
 243   template <>                                               \
 244   struct uint_types_by_size<sz / 8> {                       \
 245     using type = uint##sz##_t;                              \
 246   };
 247
 248 FB_GEN(8, uint8_t)
 249 #ifdef _MSC_VER
 250 FB_GEN(64, _byteswap_uint64)
 251 FB_GEN(32, _byteswap_ulong)
 252 FB_GEN(16, _byteswap_ushort)
 253 #else
 254 FB_GEN(64, __builtin_bswap64)
 255 FB_GEN(32, __builtin_bswap32)
 256 FB_GEN(16, __builtin_bswap16)
 257 #endif
 258
 259 #undef FB_GEN
 260
 261 template <class T>
 262 struct EndianInt {
 263   static_assert(
 264       (std::is_integral<T>::value && !std::is_same<T, bool>::value) ||
 265           std::is_floating_point<T>::value,
 266       "template type parameter must be non-bool integral or floating point");
 267   static T swap(T x) {
 268     // we implement this with memcpy because that is defined behavior in C++
 269     // we rely on compilers to optimize away the memcpy calls
 270     constexpr auto s = sizeof(T);
 271     using B = typename uint_types_by_size<s>::type;
 272     B b;
 273     std::memcpy(&b, &x, s);
 274     b = byteswap_gen(b);
 275     std::memcpy(&x, &b, s);
 276     return x;
 277   }
 278   static T big(T x) {
 279     return kIsLittleEndian ? EndianInt::swap(x) : x;
 280   }
 281   static T little(T x) {
 282     return kIsBigEndian ? EndianInt::swap(x) : x;
 283   }
 284 };
 285
 286 }  // namespace detail
 287
 288 // big* convert between native and big-endian representations
 289 // little* convert between native and little-endian representations
 290 // swap* convert between big-endian and little-endian representations
 291 //
 292 // ntohs, htons == big16
 293 // ntohl, htonl == big32
 294 #define FB_GEN1(fn, t, sz) \
 295   static t fn##sz(t x) { return fn<t>(x); } \
 296
 297 #define FB_GEN2(t, sz) \
 298   FB_GEN1(swap, t, sz) \
 299   FB_GEN1(big, t, sz) \
 300   FB_GEN1(little, t, sz)
 301
 302 #define FB_GEN(sz) \
 303   FB_GEN2(uint##sz##_t, sz) \
 304   FB_GEN2(int##sz##_t, sz)
 305
 306 class Endian {
 307  public:
 308   enum class Order : uint8_t {
 309     LITTLE,
 310     BIG
 311   };
 312
 313   static constexpr Order order = kIsLittleEndian ? Order::LITTLE : Order::BIG;
 314
 315   template <class T> static T swap(T x) {
 316     return folly::detail::EndianInt<T>::swap(x);
 317   }
 318   template <class T> static T big(T x) {
 319     return folly::detail::EndianInt<T>::big(x);
 320   }
 321   template <class T> static T little(T x) {
 322     return folly::detail::EndianInt<T>::little(x);
 323   }
 324
 325 #if !defined(__ANDROID__)
 326   FB_GEN(64)
 327   FB_GEN(32)
 328   FB_GEN(16)
 329   FB_GEN(8)
 330 #endif
 331 };
 332
 333 #undef FB_GEN
 334 #undef FB_GEN2
 335 #undef FB_GEN1
 336
 337 /**
 338  * Fast bit iteration facility.
 339  */
 340
 341
 342 template <class BaseIter> class BitIterator;
 343 template <class BaseIter>
 344 BitIterator<BaseIter> findFirstSet(BitIterator<BaseIter>,
 345                                    BitIterator<BaseIter>);
 346 /**
 347  * Wrapper around an iterator over an integer type that iterates
 348  * over its underlying bits in LSb to MSb order.
 349  *
 350  * BitIterator models the same iterator concepts as the base iterator.
 351  */
 352 template <class BaseIter>
 353 class BitIterator
 354   : public bititerator_detail::BitIteratorBase<BaseIter>::type {
 355  public:
 356   /**
 357    * Return the number of bits in an element of the underlying iterator.
 358    */
 359   static unsigned int bitsPerBlock() {
 360     return std::numeric_limits<
 361       typename std::make_unsigned<
 362         typename std::iterator_traits<BaseIter>::value_type
 363       >::type
 364     >::digits;
 365   }
 366
 367   /**
 368    * Construct a BitIterator that points at a given bit offset (default 0)
 369    * in iter.
 370    */
 371   explicit BitIterator(const BaseIter& iter, size_t bitOff=0)
 372     : bititerator_detail::BitIteratorBase<BaseIter>::type(iter),
 373       bitOffset_(bitOff) {
 374     assert(bitOffset_ < bitsPerBlock());
 375   }
 376
 377   size_t bitOffset() const {
 378     return bitOffset_;
 379   }
 380
 381   void advanceToNextBlock() {
 382     bitOffset_ = 0;
 383     ++this->base_reference();
 384   }
 385
 386   BitIterator& operator=(const BaseIter& other) {
 387     this->~BitIterator();
 388     new (this) BitIterator(other);
 389     return *this;
 390   }
 391
 392  private:
 393   friend class boost::iterator_core_access;
 394   friend BitIterator findFirstSet<>(BitIterator, BitIterator);
 395
 396   typedef bititerator_detail::BitReference<
 397       typename std::iterator_traits<BaseIter>::reference,
 398       typename std::iterator_traits<BaseIter>::value_type
 399     > BitRef;
 400
 401   void advanceInBlock(size_t n) {
 402     bitOffset_ += n;
 403     assert(bitOffset_ < bitsPerBlock());
 404   }
 405
 406   BitRef dereference() const {
 407     return BitRef(*this->base_reference(), bitOffset_);
 408   }
 409
 410   void advance(ssize_t n) {
 411     size_t bpb = bitsPerBlock();
 412     ssize_t blocks = n / ssize_t(bpb);
 413     bitOffset_ += n % bpb;
 414     if (bitOffset_ >= bpb) {
 415       bitOffset_ -= bpb;
 416       ++blocks;
 417     }
 418     this->base_reference() += blocks;
 419   }
 420
 421   void increment() {
 422     if (++bitOffset_ == bitsPerBlock()) {
 423       advanceToNextBlock();
 424     }
 425   }
 426
 427   void decrement() {
 428     if (bitOffset_-- == 0) {
 429       bitOffset_ = bitsPerBlock() - 1;
 430       --this->base_reference();
 431     }
 432   }
 433
 434   bool equal(const BitIterator& other) const {
 435     return (bitOffset_ == other.bitOffset_ &&
 436             this->base_reference() == other.base_reference());
 437   }
 438
 439   ssize_t distance_to(const BitIterator& other) const {
 440     return ssize_t(
 441         (other.base_reference() - this->base_reference()) * bitsPerBlock() +
 442         other.bitOffset_ - bitOffset_);
 443   }
 444
 445   size_t bitOffset_;
 446 };
 447
 448 /**
 449  * Helper function, so you can write
 450  * auto bi = makeBitIterator(container.begin());
 451  */
 452 template <class BaseIter>
 453 BitIterator<BaseIter> makeBitIterator(const BaseIter& iter) {
 454   return BitIterator<BaseIter>(iter);
 455 }
 456
 457
 458 /**
 459  * Find first bit set in a range of bit iterators.
 460  * 4.5x faster than the obvious std::find(begin, end, true);
 461  */
 462 template <class BaseIter>
 463 BitIterator<BaseIter> findFirstSet(BitIterator<BaseIter> begin,
 464                                    BitIterator<BaseIter> end) {
 465   // shortcut to avoid ugly static_cast<>
 466   static const typename BaseIter::value_type one = 1;
 467
 468   while (begin.base() != end.base()) {
 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     size_t firstSet = findFirstSet(v);
 473     if (firstSet) {
 474       --firstSet;  // now it's 0-based
 475       assert(firstSet >= begin.bitOffset());
 476       begin.advanceInBlock(firstSet - begin.bitOffset());
 477       return begin;
 478     }
 479     begin.advanceToNextBlock();
 480   }
 481
 482   // now begin points to the same block as end
 483   if (end.bitOffset() != 0) {  // assume end is dereferenceable
 484     typename BaseIter::value_type v = *begin.base();
 485     // mask out the bits that don't matter (< begin.bitOffset)
 486     v &= ~((one << begin.bitOffset()) - 1);
 487     // mask out the bits that don't matter (>= end.bitOffset)
 488     v &= (one << end.bitOffset()) - 1;
 489     size_t firstSet = findFirstSet(v);
 490     if (firstSet) {
 491       --firstSet;  // now it's 0-based
 492       assert(firstSet >= begin.bitOffset());
 493       begin.advanceInBlock(firstSet - begin.bitOffset());
 494       return begin;
 495     }
 496   }
 497
 498   return end;
 499 }
 500
 501
 502 template <class T, class Enable=void> struct Unaligned;
 503
 504 /**
 505  * Representation of an unaligned value of a POD type.
 506  */
 507 FOLLY_PACK_PUSH
 508 template <class T>
 509 struct Unaligned<
 510     T,
 511     typename std::enable_if<std::is_pod<T>::value>::type> {
 512   Unaligned() = default;  // uninitialized
 513   /* implicit */ Unaligned(T v) : value(v) { }
 514   T value;
 515 } FOLLY_PACK_ATTR;
 516 FOLLY_PACK_POP
 517
 518 /**
 519  * Read an unaligned value of type T and return it.
 520  */
 521 template <class T>
 522 inline T loadUnaligned(const void* p) {
 523   static_assert(sizeof(Unaligned<T>) == sizeof(T), "Invalid unaligned size");
 524   static_assert(alignof(Unaligned<T>) == 1, "Invalid alignment");
 525   if (kHasUnalignedAccess) {
 526     return static_cast<const Unaligned<T>*>(p)->value;
 527   } else {
 528     T value;
 529     memcpy(&value, p, sizeof(T));
 530     return value;
 531   }
 532 }
 533
 534 /**
 535  * Write an unaligned value of type T.
 536  */
 537 template <class T>
 538 inline void storeUnaligned(void* p, T value) {
 539   static_assert(sizeof(Unaligned<T>) == sizeof(T), "Invalid unaligned size");
 540   static_assert(alignof(Unaligned<T>) == 1, "Invalid alignment");
 541   if (kHasUnalignedAccess) {
 542     // Prior to C++14, the spec says that a placement new like this
 543     // is required to check that p is not nullptr, and to do nothing
 544     // if p is a nullptr. By assuming it's not a nullptr, we get a
 545     // nice loud segfault in optimized builds if p is nullptr, rather
 546     // than just silently doing nothing.
 547     folly::assume(p != nullptr);
 548     new (p) Unaligned<T>(value);
 549   } else {
 550     memcpy(p, &value, sizeof(T));
 551   }
 552 }
 553
 554 }  // namespace folly