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