folly/experimental/Bits.h

   1 /*
   2  * Copyright 2014 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
  24 #include "folly/Bits.h"
  25 #include "folly/Portability.h"
  26 #include "folly/Range.h"
  27
  28 namespace folly {
  29
  30 template <class T>
  31 struct UnalignedNoASan : public Unaligned<T> { };
  32
  33 // As a general rule, bit operations work on unsigned values only;
  34 // right-shift is arithmetic for signed values, and that can lead to
  35 // unpleasant bugs.
  36
  37 namespace detail {
  38
  39 /**
  40  * Helper class to make Bits<T> (below) work with both aligned values
  41  * (T, where T is an unsigned integral type) or unaligned values
  42  * (Unaligned<T>, where T is an unsigned integral type)
  43  */
  44 template <class T, class Enable=void> struct BitsTraits;
  45
  46 // Partial specialization for Unaligned<T>, where T is unsigned integral
  47 // loadRMW is the same as load, but it indicates that it loads for a
  48 // read-modify-write operation (we write back the bits we won't change);
  49 // silence the GCC warning in that case.
  50 template <class T>
  51 struct BitsTraits<Unaligned<T>, typename std::enable_if<
  52     (std::is_integral<T>::value && std::is_unsigned<T>::value)>::type> {
  53   typedef T UnderlyingType;
  54   static T load(const Unaligned<T>& x) { return x.value; }
  55   static void store(Unaligned<T>& x, T v) { x.value = v; }
  56   static T loadRMW(const Unaligned<T>& x) {
  57 #pragma GCC diagnostic push
  58 #pragma GCC diagnostic ignored "-Wuninitialized"
  59 // make sure we compile without warning on gcc 4.6 with -Wpragmas
  60 #if __GNUC_PREREQ(4, 7)
  61 #pragma GCC diagnostic ignored "-Wmaybe-uninitialized"
  62 #endif
  63     return x.value;
  64 #pragma GCC diagnostic pop
  65   }
  66 };
  67
  68 // Special version that allows to disable address sanitizer on demand.
  69 template <class T>
  70 struct BitsTraits<UnalignedNoASan<T>, typename std::enable_if<
  71     (std::is_integral<T>::value && std::is_unsigned<T>::value)>::type> {
  72   typedef T UnderlyingType;
  73   static T FOLLY_DISABLE_ADDRESS_SANITIZER
  74   load(const UnalignedNoASan<T>& x) { return x.value; }
  75   static void FOLLY_DISABLE_ADDRESS_SANITIZER
  76   store(UnalignedNoASan<T>& x, T v) { x.value = v; }
  77   static T FOLLY_DISABLE_ADDRESS_SANITIZER
  78   loadRMW(const UnalignedNoASan<T>& x) {
  79 #pragma GCC diagnostic push
  80 #pragma GCC diagnostic ignored "-Wuninitialized"
  81 // make sure we compile without warning on gcc 4.6 with -Wpragmas
  82 #if __GNUC_PREREQ(4, 7)
  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 && std::is_unsigned<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 __GNUC_PREREQ(4, 7)
 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 =
 126     std::numeric_limits<UnderlyingType>::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    */
 170   static void set(T* p, size_t bitStart, size_t count, UnderlyingType value);
 171
 172   /**
 173    * Get count contiguous bits starting at bitStart.
 174    * Precondition: count <= sizeof(T) * 8
 175    */
 176   static UnderlyingType get(const T* p, size_t bitStart, size_t count);
 177
 178   /**
 179    * Count the number of bits set in a range of blocks.
 180    */
 181   static size_t count(const T* begin, const T* end);
 182
 183  private:
 184   // Same as set, assumes all bits are in the same block.
 185   // (bitStart < sizeof(T) * 8, bitStart + count <= sizeof(T) * 8)
 186   static void innerSet(T* p, size_t bitStart, size_t count,
 187                        UnderlyingType value);
 188
 189   // Same as get, assumes all bits are in the same block.
 190   // (bitStart < sizeof(T) * 8, bitStart + count <= sizeof(T) * 8)
 191   static UnderlyingType innerGet(const T* p, size_t bitStart, size_t count);
 192
 193   static constexpr UnderlyingType zero = UnderlyingType(0);
 194   static constexpr UnderlyingType one = UnderlyingType(1);
 195
 196   static constexpr UnderlyingType ones(size_t count) {
 197     return count < bitsPerBlock ? (one << count) - 1 : ~zero;
 198   }
 199 };
 200
 201 // gcc 4.8 needs more -Wmaybe-uninitialized tickling, as it propagates the
 202 // taint upstream from loadRMW
 203
 204 #pragma GCC diagnostic push
 205 #pragma GCC diagnostic ignored "-Wuninitialized"
 206 #if __GNUC_PREREQ(4, 7)
 207 #pragma GCC diagnostic ignored "-Wmaybe-uninitialized"
 208 #endif
 209
 210 template <class T, class Traits>
 211 inline void Bits<T, Traits>::set(T* p, size_t bit) {
 212   T& block = p[blockIndex(bit)];
 213   Traits::store(block, Traits::loadRMW(block) | (one << bitOffset(bit)));
 214 }
 215
 216 template <class T, class Traits>
 217 inline void Bits<T, Traits>::clear(T* p, size_t bit) {
 218   T& block = p[blockIndex(bit)];
 219   Traits::store(block, Traits::loadRMW(block) & ~(one << bitOffset(bit)));
 220 }
 221
 222 template <class T, class Traits>
 223 inline void Bits<T, Traits>::set(T* p, size_t bitStart, size_t count,
 224                                  UnderlyingType value) {
 225   assert(count <= sizeof(UnderlyingType) * 8);
 226   size_t idx = blockIndex(bitStart);
 227   size_t offset = bitOffset(bitStart);
 228   if (offset + count <= bitsPerBlock) {
 229     innerSet(p + idx, offset, count, value);
 230   } else {
 231     size_t countInThisBlock = bitsPerBlock - offset;
 232     size_t countInNextBlock = count - countInThisBlock;
 233     innerSet(p + idx, offset, countInThisBlock,
 234              value & ((one << countInThisBlock) - 1));
 235     innerSet(p + idx + 1, 0, countInNextBlock, value >> countInThisBlock);
 236   }
 237 }
 238
 239 template <class T, class Traits>
 240 inline void Bits<T, Traits>::innerSet(T* p, size_t offset, size_t count,
 241                                       UnderlyingType value) {
 242   // Mask out bits and set new value
 243   UnderlyingType v = Traits::loadRMW(*p);
 244   v &= ~(ones(count) << offset);
 245   v |= (value << offset);
 246   Traits::store(*p, v);
 247 }
 248
 249 #pragma GCC diagnostic pop
 250
 251 template <class T, class Traits>
 252 inline bool Bits<T, Traits>::test(const T* p, size_t bit) {
 253   return Traits::load(p[blockIndex(bit)]) & (one << bitOffset(bit));
 254 }
 255
 256 template <class T, class Traits>
 257 inline auto Bits<T, Traits>::get(const T* p, size_t bitStart, size_t count)
 258   -> UnderlyingType {
 259   assert(count <= sizeof(UnderlyingType) * 8);
 260   size_t idx = blockIndex(bitStart);
 261   size_t offset = bitOffset(bitStart);
 262   if (offset + count <= bitsPerBlock) {
 263     return innerGet(p + idx, offset, count);
 264   } else {
 265     size_t countInThisBlock = bitsPerBlock - offset;
 266     size_t countInNextBlock = count - countInThisBlock;
 267     UnderlyingType thisBlockValue = innerGet(p + idx, offset, countInThisBlock);
 268     UnderlyingType nextBlockValue = innerGet(p + idx + 1, 0, countInNextBlock);
 269     return (nextBlockValue << countInThisBlock) | thisBlockValue;
 270   }
 271 }
 272
 273 template <class T, class Traits>
 274 inline auto Bits<T, Traits>::innerGet(const T* p, size_t offset, size_t count)
 275   -> UnderlyingType {
 276   return (Traits::load(*p) >> offset) & ones(count);
 277 }
 278
 279 template <class T, class Traits>
 280 inline size_t Bits<T, Traits>::count(const T* begin, const T* end) {
 281   size_t n = 0;
 282   for (; begin != end; ++begin) {
 283     n += popcount(Traits::load(*begin));
 284   }
 285   return n;
 286 }
 287
 288 }  // namespace folly
 289
 290 #endif /* FOLLY_EXPERIMENTAL_BITS_H_ */
 291