folly/Bits.h

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