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