folly/experimental/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 #ifndef FOLLY_EXPERIMENTAL_BITS_H_
  18 #define FOLLY_EXPERIMENTAL_BITS_H_
  19
  20 #include <cstddef>
  21 #include <type_traits>
  22 #include <limits>
  23 #include <glog/logging.h>
  24
  25 #include <folly/Bits.h>
  26 #include <folly/Portability.h>
  27 #include <folly/Range.h>
  28
  29 namespace folly {
  30
  31 template <class T>
  32 struct UnalignedNoASan : public Unaligned<T> { };
  33
  34 // As a general rule, bit operations work on unsigned values only;
  35 // right-shift is arithmetic for signed values, and that can lead to
  36 // unpleasant bugs.
  37
  38 namespace detail {
  39
  40 /**
  41  * Helper class to make Bits<T> (below) work with both aligned values
  42  * (T, where T is an unsigned integral type) or unaligned values
  43  * (Unaligned<T>, where T is an unsigned integral type)
  44  */
  45 template <class T, class Enable = void>
  46 struct BitsTraits;
  47
  48 // Partial specialization for Unaligned<T>, where T is unsigned integral
  49 // loadRMW is the same as load, but it indicates that it loads for a
  50 // read-modify-write operation (we write back the bits we won't change);
  51 // silence the GCC warning in that case.
  52 template <class T>
  53 struct BitsTraits<Unaligned<T>, typename std::enable_if<
  54     (std::is_integral<T>::value)>::type> {
  55   typedef T UnderlyingType;
  56   static T load(const Unaligned<T>& x) { return x.value; }
  57   static void store(Unaligned<T>& x, T v) { x.value = v; }
  58   static T loadRMW(const Unaligned<T>& x) {
  59 #pragma GCC diagnostic push
  60 #pragma GCC diagnostic ignored "-Wuninitialized"
  61 #if !__clang__ // for gcc version [4.8, ?)
  62 #pragma GCC diagnostic ignored "-Wmaybe-uninitialized"
  63 #endif
  64     return x.value;
  65 #pragma GCC diagnostic pop
  66   }
  67 };
  68
  69 // Special version that allows to disable address sanitizer on demand.
  70 template <class T>
  71 struct BitsTraits<UnalignedNoASan<T>, typename std::enable_if<
  72     (std::is_integral<T>::value)>::type> {
  73   typedef T UnderlyingType;
  74   static T FOLLY_DISABLE_ADDRESS_SANITIZER
  75   load(const UnalignedNoASan<T>& x) { return x.value; }
  76   static void FOLLY_DISABLE_ADDRESS_SANITIZER
  77   store(UnalignedNoASan<T>& x, T v) { x.value = v; }
  78   static T FOLLY_DISABLE_ADDRESS_SANITIZER
  79   loadRMW(const UnalignedNoASan<T>& x) {
  80 #pragma GCC diagnostic push
  81 #pragma GCC diagnostic ignored "-Wuninitialized"
  82 #if !__clang__ // for gcc version [4.8, ?)
  83 #pragma GCC diagnostic ignored "-Wmaybe-uninitialized"
  84 #endif
  85     return x.value;
  86 #pragma GCC diagnostic pop
  87   }
  88 };
  89
  90 // Partial specialization for T, where T is unsigned integral
  91 template <class T>
  92 struct BitsTraits<T, typename std::enable_if<
  93     (std::is_integral<T>::value)>::type> {
  94   typedef T UnderlyingType;
  95   static T load(const T& x) { return x; }
  96   static void store(T& x, T v) { x = v; }
  97   static T loadRMW(const T& x) {
  98 #pragma GCC diagnostic push
  99 #pragma GCC diagnostic ignored "-Wuninitialized"
 100 #if !__clang__ // for gcc version [4.8, ?)
 101 #pragma GCC diagnostic ignored "-Wmaybe-uninitialized"
 102 #endif
 103     return x;
 104 #pragma GCC diagnostic pop
 105   }
 106 };
 107
 108 }  // namespace detail
 109
 110 /**
 111  * Wrapper class with static methods for various bit-level operations,
 112  * treating an array of T as an array of bits (in little-endian order).
 113  * (T is either an unsigned integral type or Unaligned<X>, where X is
 114  * an unsigned integral type)
 115  */
 116 template <class T, class Traits=detail::BitsTraits<T>>
 117 struct Bits {
 118   typedef typename Traits::UnderlyingType UnderlyingType;
 119   typedef T type;
 120   static_assert(sizeof(T) == sizeof(UnderlyingType), "Size mismatch");
 121
 122   /**
 123    * Number of bits in a block.
 124    */
 125   static constexpr size_t bitsPerBlock = std::numeric_limits<
 126       typename std::make_unsigned<UnderlyingType>::type>::digits;
 127
 128   /**
 129    * Byte index of the given bit.
 130    */
 131   static constexpr size_t blockIndex(size_t bit) {
 132     return bit / bitsPerBlock;
 133   }
 134
 135   /**
 136    * Offset in block of the given bit.
 137    */
 138   static constexpr size_t bitOffset(size_t bit) {
 139     return bit % bitsPerBlock;
 140   }
 141
 142   /**
 143    * Number of blocks used by the given number of bits.
 144    */
 145   static constexpr size_t blockCount(size_t nbits) {
 146     return nbits / bitsPerBlock + (nbits % bitsPerBlock != 0);
 147   }
 148
 149   /**
 150    * Set the given bit.
 151    */
 152   static void set(T* p, size_t bit);
 153
 154   /**
 155    * Clear the given bit.
 156    */
 157   static void clear(T* p, size_t bit);
 158
 159   /**
 160    * Test the given bit.
 161    */
 162   static bool test(const T* p, size_t bit);
 163
 164   /**
 165    * Set count contiguous bits starting at bitStart to the values
 166    * from the least significant count bits of value; little endian.
 167    * (value & 1 becomes the bit at bitStart, etc)
 168    * Precondition: count <= sizeof(T) * 8
 169    * Precondition: value can fit in 'count' bits
 170    */
 171   static void set(T* p, size_t bitStart, size_t count, UnderlyingType value);
 172
 173   /**
 174    * Get count contiguous bits starting at bitStart.
 175    * Precondition: count <= sizeof(T) * 8
 176    */
 177   static UnderlyingType get(const T* p, size_t bitStart, size_t count);
 178
 179   /**
 180    * Count the number of bits set in a range of blocks.
 181    */
 182   static size_t count(const T* begin, const T* end);
 183
 184  private:
 185   // Same as set, assumes all bits are in the same block.
 186   // (bitStart < sizeof(T) * 8, bitStart + count <= sizeof(T) * 8)
 187   static void innerSet(T* p, size_t bitStart, size_t count,
 188                        UnderlyingType value);
 189
 190   // Same as get, assumes all bits are in the same block.
 191   // (bitStart < sizeof(T) * 8, bitStart + count <= sizeof(T) * 8)
 192   static UnderlyingType innerGet(const T* p, size_t bitStart, size_t count);
 193
 194   static constexpr UnderlyingType zero = UnderlyingType(0);
 195   static constexpr UnderlyingType one = UnderlyingType(1);
 196
 197   static constexpr UnderlyingType ones(size_t count) {
 198     return count < bitsPerBlock ? (one << count) - 1 : ~zero;
 199   }
 200 };
 201
 202 // gcc 4.8 needs more -Wmaybe-uninitialized tickling, as it propagates the
 203 // taint upstream from loadRMW
 204
 205 #pragma GCC diagnostic push
 206 #pragma GCC diagnostic ignored "-Wuninitialized"
 207 #if !__clang__ // for gcc version [4.8, ?)
 208 #pragma GCC diagnostic ignored "-Wmaybe-uninitialized"
 209 #endif
 210
 211 template <class T, class Traits>
 212 inline void Bits<T, Traits>::set(T* p, size_t bit) {
 213   T& block = p[blockIndex(bit)];
 214   Traits::store(block, Traits::loadRMW(block) | (one << bitOffset(bit)));
 215 }
 216
 217 template <class T, class Traits>
 218 inline void Bits<T, Traits>::clear(T* p, size_t bit) {
 219   T& block = p[blockIndex(bit)];
 220   Traits::store(block, Traits::loadRMW(block) & ~(one << bitOffset(bit)));
 221 }
 222
 223 template <class T, class Traits>
 224 inline void Bits<T, Traits>::set(T* p, size_t bitStart, size_t count,
 225                                  UnderlyingType value) {
 226   DCHECK_LE(count, sizeof(UnderlyingType) * 8);
 227   size_t cut = bitsPerBlock - count;
 228   DCHECK_EQ(value, value << cut >> cut);
 229   size_t idx = blockIndex(bitStart);
 230   size_t offset = bitOffset(bitStart);
 231   if (std::is_signed<UnderlyingType>::value) {
 232     value &= ones(count);
 233   }
 234   if (offset + count <= bitsPerBlock) {
 235     innerSet(p + idx, offset, count, value);
 236   } else {
 237     size_t countInThisBlock = bitsPerBlock - offset;
 238     size_t countInNextBlock = count - countInThisBlock;
 239
 240     UnderlyingType thisBlock = value & ((one << countInThisBlock) - 1);
 241     UnderlyingType nextBlock = value >> countInThisBlock;
 242     if (std::is_signed<UnderlyingType>::value) {
 243       nextBlock &= ones(countInNextBlock);
 244     }
 245     innerSet(p + idx, offset, countInThisBlock, thisBlock);
 246     innerSet(p + idx + 1, 0, countInNextBlock, nextBlock);
 247   }
 248 }
 249
 250 template <class T, class Traits>
 251 inline void Bits<T, Traits>::innerSet(T* p, size_t offset, size_t count,
 252                                       UnderlyingType value) {
 253   // Mask out bits and set new value
 254   UnderlyingType v = Traits::loadRMW(*p);
 255   v &= ~(ones(count) << offset);
 256   v |= (value << offset);
 257   Traits::store(*p, v);
 258 }
 259
 260 #pragma GCC diagnostic pop
 261
 262 template <class T, class Traits>
 263 inline bool Bits<T, Traits>::test(const T* p, size_t bit) {
 264   return Traits::load(p[blockIndex(bit)]) & (one << bitOffset(bit));
 265 }
 266
 267 template <class T, class Traits>
 268 inline auto Bits<T, Traits>::get(const T* p, size_t bitStart, size_t count)
 269   -> UnderlyingType {
 270   DCHECK_LE(count, sizeof(UnderlyingType) * 8);
 271   size_t idx = blockIndex(bitStart);
 272   size_t offset = bitOffset(bitStart);
 273   UnderlyingType ret;
 274   if (offset + count <= bitsPerBlock) {
 275     ret = innerGet(p + idx, offset, count);
 276   } else {
 277     size_t countInThisBlock = bitsPerBlock - offset;
 278     size_t countInNextBlock = count - countInThisBlock;
 279     UnderlyingType thisBlockValue = innerGet(p + idx, offset, countInThisBlock);
 280     UnderlyingType nextBlockValue = innerGet(p + idx + 1, 0, countInNextBlock);
 281     ret = (nextBlockValue << countInThisBlock) | thisBlockValue;
 282   }
 283   if (std::is_signed<UnderlyingType>::value) {
 284     size_t emptyBits = bitsPerBlock - count;
 285     ret <<= emptyBits;
 286     ret >>= emptyBits;
 287   }
 288   return ret;
 289 }
 290
 291 template <class T, class Traits>
 292 inline auto Bits<T, Traits>::innerGet(const T* p, size_t offset, size_t count)
 293     -> UnderlyingType {
 294   return (Traits::load(*p) >> offset) & ones(count);
 295 }
 296
 297 template <class T, class Traits>
 298 inline size_t Bits<T, Traits>::count(const T* begin, const T* end) {
 299   size_t n = 0;
 300   for (; begin != end; ++begin) {
 301     n += popcount(Traits::load(*begin));
 302   }
 303   return n;
 304 }
 305
 306 }  // namespace folly
 307
 308 #endif /* FOLLY_EXPERIMENTAL_BITS_H_ */