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