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