/*
- * Copyright 2012 Facebook, Inc.
+ * Copyright 2017 Facebook, Inc.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* limitations under the License.
*/
-#ifndef FOLLY_EXPERIMENTAL_BITS_H_
-#define FOLLY_EXPERIMENTAL_BITS_H_
+#pragma once
#include <cstddef>
#include <type_traits>
#include <limits>
+#include <glog/logging.h>
-#include "folly/Range.h"
+#include <folly/Bits.h>
+#include <folly/Portability.h>
+#include <folly/Range.h>
namespace folly {
+template <class T>
+struct UnalignedNoASan : public Unaligned<T> { };
+
+// As a general rule, bit operations work on unsigned values only;
+// right-shift is arithmetic for signed values, and that can lead to
+// unpleasant bugs.
+
+namespace detail {
+
/**
- * Population count (number of bits set), using __builtin_popcount or
- * __builtin_popcountll, depending on size.
+ * Helper class to make Bits<T> (below) work with both aligned values
+ * (T, where T is an unsigned integral type) or unaligned values
+ * (Unaligned<T>, where T is an unsigned integral type)
*/
+template <class T, class Enable = void>
+struct BitsTraits;
+
+// Partial specialization for Unaligned<T>, where T is unsigned integral
+// loadRMW is the same as load, but it indicates that it loads for a
+// read-modify-write operation (we write back the bits we won't change);
+// silence the GCC warning in that case.
template <class T>
-inline typename std::enable_if<
- (std::is_integral<T>::value &&
- std::is_unsigned<T>::value &&
- sizeof(T) <= sizeof(unsigned int)),
- size_t>::type
- popcount(T x) {
- return __builtin_popcount(x);
-}
+struct BitsTraits<Unaligned<T>, typename std::enable_if<
+ (std::is_integral<T>::value)>::type> {
+ typedef T UnderlyingType;
+ static T load(const Unaligned<T>& x) { return x.value; }
+ static void store(Unaligned<T>& x, T v) { x.value = v; }
+ static T loadRMW(const Unaligned<T>& x) {
+ FOLLY_PUSH_WARNING
+ FOLLY_GCC_DISABLE_WARNING("-Wuninitialized")
+#if !__clang__ // for gcc version [4.8, ?)
+ FOLLY_GCC_DISABLE_WARNING("-Wmaybe-uninitialized")
+#endif
+ return x.value;
+ FOLLY_POP_WARNING
+ }
+};
+// Special version that allows one to disable address sanitizer on demand.
template <class T>
-inline typename std::enable_if<
- (std::is_integral<T>::value &&
- std::is_unsigned<T>::value &&
- sizeof(T) > sizeof(unsigned int) &&
- sizeof(T) <= sizeof(unsigned long long)),
- size_t>::type
- popcount(T x) {
- return __builtin_popcountll(x);
-}
+struct BitsTraits<UnalignedNoASan<T>, typename std::enable_if<
+ (std::is_integral<T>::value)>::type> {
+ typedef T UnderlyingType;
+ static T FOLLY_DISABLE_ADDRESS_SANITIZER
+ load(const UnalignedNoASan<T>& x) { return x.value; }
+ static void FOLLY_DISABLE_ADDRESS_SANITIZER
+ store(UnalignedNoASan<T>& x, T v) { x.value = v; }
+ static T FOLLY_DISABLE_ADDRESS_SANITIZER
+ loadRMW(const UnalignedNoASan<T>& x) {
+ FOLLY_PUSH_WARNING
+ FOLLY_GCC_DISABLE_WARNING("-Wuninitialized")
+#if !__clang__ // for gcc version [4.8, ?)
+ FOLLY_GCC_DISABLE_WARNING("-Wmaybe-uninitialized")
+#endif
+ return x.value;
+ FOLLY_POP_WARNING
+ }
+};
+// Partial specialization for T, where T is unsigned integral
template <class T>
-struct Bits {
- static_assert(std::is_integral<T>::value &&
- std::is_unsigned<T>::value,
- "Unsigned integral type required");
+struct BitsTraits<T, typename std::enable_if<
+ (std::is_integral<T>::value)>::type> {
+ typedef T UnderlyingType;
+ static T load(const T& x) { return x; }
+ static void store(T& x, T v) { x = v; }
+ static T loadRMW(const T& x) {
+ FOLLY_PUSH_WARNING
+ FOLLY_GCC_DISABLE_WARNING("-Wuninitialized")
+#if !__clang__ // for gcc version [4.8, ?)
+ FOLLY_GCC_DISABLE_WARNING("-Wmaybe-uninitialized")
+#endif
+ return x;
+ FOLLY_POP_WARNING
+ }
+};
+} // namespace detail
+
+/**
+ * Wrapper class with static methods for various bit-level operations,
+ * treating an array of T as an array of bits (in little-endian order).
+ * (T is either an unsigned integral type or Unaligned<X>, where X is
+ * an unsigned integral type)
+ */
+template <class T, class Traits=detail::BitsTraits<T>>
+struct Bits {
+ typedef typename Traits::UnderlyingType UnderlyingType;
typedef T type;
- static constexpr size_t bitsPerBlock = std::numeric_limits<T>::digits;
+ static_assert(sizeof(T) == sizeof(UnderlyingType), "Size mismatch");
+
+ /**
+ * Number of bits in a block.
+ */
+ static constexpr size_t bitsPerBlock = std::numeric_limits<
+ typename std::make_unsigned<UnderlyingType>::type>::digits;
/**
* Byte index of the given bit.
*/
static bool test(const T* p, size_t bit);
+ /**
+ * Set count contiguous bits starting at bitStart to the values
+ * from the least significant count bits of value; little endian.
+ * (value & 1 becomes the bit at bitStart, etc)
+ * Precondition: count <= sizeof(T) * 8
+ * Precondition: value can fit in 'count' bits
+ */
+ static void set(T* p, size_t bitStart, size_t count, UnderlyingType value);
+
+ /**
+ * Get count contiguous bits starting at bitStart.
+ * Precondition: count <= sizeof(T) * 8
+ */
+ static UnderlyingType get(const T* p, size_t bitStart, size_t count);
+
/**
* Count the number of bits set in a range of blocks.
*/
static size_t count(const T* begin, const T* end);
private:
- static constexpr T one = T(1);
+ // Same as set, assumes all bits are in the same block.
+ // (bitStart < sizeof(T) * 8, bitStart + count <= sizeof(T) * 8)
+ static void innerSet(T* p, size_t bitStart, size_t count,
+ UnderlyingType value);
+
+ // Same as get, assumes all bits are in the same block.
+ // (bitStart < sizeof(T) * 8, bitStart + count <= sizeof(T) * 8)
+ static UnderlyingType innerGet(const T* p, size_t bitStart, size_t count);
+
+ static constexpr UnderlyingType zero = UnderlyingType(0);
+ static constexpr UnderlyingType one = UnderlyingType(1);
+
+ using UnsignedType = typename std::make_unsigned<UnderlyingType>::type;
+ static constexpr UnderlyingType ones(size_t count) {
+ return (count < bitsPerBlock)
+ ? static_cast<UnderlyingType>((UnsignedType{1} << count) - 1)
+ : ~zero;
+ }
};
-template <class T>
-inline void Bits<T>::set(T* p, size_t bit) {
- p[blockIndex(bit)] |= (one << bitOffset(bit));
+// gcc 4.8 needs more -Wmaybe-uninitialized tickling, as it propagates the
+// taint upstream from loadRMW
+FOLLY_PUSH_WARNING
+FOLLY_GCC_DISABLE_WARNING("-Wuninitialized")
+#if !__clang__ // for gcc version [4.8, ?)
+FOLLY_GCC_DISABLE_WARNING("-Wmaybe-uninitialized")
+#endif
+
+template <class T, class Traits>
+inline void Bits<T, Traits>::set(T* p, size_t bit) {
+ T& block = p[blockIndex(bit)];
+ Traits::store(block, Traits::loadRMW(block) | (one << bitOffset(bit)));
}
-template <class T>
-inline void Bits<T>::clear(T* p, size_t bit) {
- p[blockIndex(bit)] &= ~(one << bitOffset(bit));
+template <class T, class Traits>
+inline void Bits<T, Traits>::clear(T* p, size_t bit) {
+ T& block = p[blockIndex(bit)];
+ Traits::store(block, Traits::loadRMW(block) & ~(one << bitOffset(bit)));
}
-template <class T>
-inline bool Bits<T>::test(const T* p, size_t bit) {
- return p[blockIndex(bit)] & (one << bitOffset(bit));
+template <class T, class Traits>
+inline void Bits<T, Traits>::set(T* p, size_t bitStart, size_t count,
+ UnderlyingType value) {
+ DCHECK_LE(count, sizeof(UnderlyingType) * 8);
+ size_t cut = bitsPerBlock - count;
+ if (cut != 8 * sizeof(UnderlyingType)) {
+ using U = typename std::make_unsigned<UnderlyingType>::type;
+ DCHECK_EQ(value, UnderlyingType(U(value) << cut) >> cut);
+ }
+ size_t idx = blockIndex(bitStart);
+ size_t offset = bitOffset(bitStart);
+ if (std::is_signed<UnderlyingType>::value) {
+ value &= ones(count);
+ }
+ if (offset + count <= bitsPerBlock) {
+ innerSet(p + idx, offset, count, value);
+ } else {
+ size_t countInThisBlock = bitsPerBlock - offset;
+ size_t countInNextBlock = count - countInThisBlock;
+
+ UnderlyingType thisBlock = UnderlyingType(value & ones(countInThisBlock));
+ UnderlyingType nextBlock = UnderlyingType(value >> countInThisBlock);
+ if (std::is_signed<UnderlyingType>::value) {
+ nextBlock &= ones(countInNextBlock);
+ }
+ innerSet(p + idx, offset, countInThisBlock, thisBlock);
+ innerSet(p + idx + 1, 0, countInNextBlock, nextBlock);
+ }
}
-template <class T>
-inline size_t Bits<T>::count(const T* begin, const T* end) {
+template <class T, class Traits>
+inline void Bits<T, Traits>::innerSet(T* p, size_t offset, size_t count,
+ UnderlyingType value) {
+ // Mask out bits and set new value
+ UnderlyingType v = Traits::loadRMW(*p);
+ v &= ~(ones(count) << offset);
+ v |= (value << offset);
+ Traits::store(*p, v);
+}
+
+FOLLY_POP_WARNING
+
+template <class T, class Traits>
+inline bool Bits<T, Traits>::test(const T* p, size_t bit) {
+ return Traits::load(p[blockIndex(bit)]) & (one << bitOffset(bit));
+}
+
+template <class T, class Traits>
+inline auto Bits<T, Traits>::get(const T* p, size_t bitStart, size_t count)
+ -> UnderlyingType {
+ if (count == 0) {
+ return UnderlyingType{};
+ }
+
+ DCHECK_LE(count, sizeof(UnderlyingType) * 8);
+ size_t idx = blockIndex(bitStart);
+ size_t offset = bitOffset(bitStart);
+ UnderlyingType ret;
+ if (offset + count <= bitsPerBlock) {
+ ret = innerGet(p + idx, offset, count);
+ } else {
+ size_t countInThisBlock = bitsPerBlock - offset;
+ size_t countInNextBlock = count - countInThisBlock;
+ UnderlyingType thisBlockValue = innerGet(p + idx, offset, countInThisBlock);
+ UnderlyingType nextBlockValue = innerGet(p + idx + 1, 0, countInNextBlock);
+ ret = (nextBlockValue << countInThisBlock) | thisBlockValue;
+ }
+ if (std::is_signed<UnderlyingType>::value) {
+ size_t emptyBits = bitsPerBlock - count;
+ ret <<= emptyBits;
+ ret >>= emptyBits;
+ }
+ return ret;
+}
+
+template <class T, class Traits>
+inline auto Bits<T, Traits>::innerGet(const T* p, size_t offset, size_t count)
+ -> UnderlyingType {
+ return (Traits::load(*p) >> offset) & ones(count);
+}
+
+template <class T, class Traits>
+inline size_t Bits<T, Traits>::count(const T* begin, const T* end) {
size_t n = 0;
for (; begin != end; ++begin) {
- n += popcount(*begin);
+ n += popcount(Traits::load(*begin));
}
return n;
}
} // namespace folly
-
-#endif /* FOLLY_EXPERIMENTAL_BITS_H_ */
-
projects / folly.git / blobdiff