folly/Bits.h

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