folly/experimental/Bits.h

   1 /*
   2  * Copyright 2017 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 #pragma once
  18
  19 #include <cstddef>
  20 #include <type_traits>
  21 #include <limits>
  22 #include <glog/logging.h>
  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 #if !__clang__ // for gcc version [4.8, ?)
  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 one 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)>::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 #if !__clang__ // for gcc version [4.8, ?)
  82 #pragma GCC diagnostic ignored "-Wmaybe-uninitialized"
  83 #endif
  84     return x.value;
  85 #pragma GCC diagnostic pop
  86   }
  87 };
  88
  89 // Partial specialization for T, where T is unsigned integral
  90 template <class T>
  91 struct BitsTraits<T, typename std::enable_if<
  92     (std::is_integral<T>::value)>::type> {
  93   typedef T UnderlyingType;
  94   static T load(const T& x) { return x; }
  95   static void store(T& x, T v) { x = v; }
  96   static T loadRMW(const T& x) {
  97 #pragma GCC diagnostic push
  98 #pragma GCC diagnostic ignored "-Wuninitialized"
  99 #if !__clang__ // for gcc version [4.8, ?)
 100 #pragma GCC diagnostic ignored "-Wmaybe-uninitialized"
 101 #endif
 102     return x;
 103 #pragma GCC diagnostic pop
 104   }
 105 };
 106
 107 }  // namespace detail
 108
 109 /**
 110  * Wrapper class with static methods for various bit-level operations,
 111  * treating an array of T as an array of bits (in little-endian order).
 112  * (T is either an unsigned integral type or Unaligned<X>, where X is
 113  * an unsigned integral type)
 114  */
 115 template <class T, class Traits=detail::BitsTraits<T>>
 116 struct Bits {
 117   typedef typename Traits::UnderlyingType UnderlyingType;
 118   typedef T type;
 119   static_assert(sizeof(T) == sizeof(UnderlyingType), "Size mismatch");
 120
 121   /**
 122    * Number of bits in a block.
 123    */
 124   static constexpr size_t bitsPerBlock = std::numeric_limits<
 125       typename std::make_unsigned<UnderlyingType>::type>::digits;
 126
 127   /**
 128    * Byte index of the given bit.
 129    */
 130   static constexpr size_t blockIndex(size_t bit) {
 131     return bit / bitsPerBlock;
 132   }
 133
 134   /**
 135    * Offset in block of the given bit.
 136    */
 137   static constexpr size_t bitOffset(size_t bit) {
 138     return bit % bitsPerBlock;
 139   }
 140
 141   /**
 142    * Number of blocks used by the given number of bits.
 143    */
 144   static constexpr size_t blockCount(size_t nbits) {
 145     return nbits / bitsPerBlock + (nbits % bitsPerBlock != 0);
 146   }
 147
 148   /**
 149    * Set the given bit.
 150    */
 151   static void set(T* p, size_t bit);
 152
 153   /**
 154    * Clear the given bit.
 155    */
 156   static void clear(T* p, size_t bit);
 157
 158   /**
 159    * Test the given bit.
 160    */
 161   static bool test(const T* p, size_t bit);
 162
 163   /**
 164    * Set count contiguous bits starting at bitStart to the values
 165    * from the least significant count bits of value; little endian.
 166    * (value & 1 becomes the bit at bitStart, etc)
 167    * Precondition: count <= sizeof(T) * 8
 168    * Precondition: value can fit in 'count' bits
 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   using UnsignedType = typename std::make_unsigned<UnderlyingType>::type;
 197   static constexpr UnderlyingType ones(size_t count) {
 198     return (count < bitsPerBlock)
 199         ? static_cast<UnderlyingType>((UnsignedType{1} << count) - 1)
 200         : ~zero;
 201   }
 202 };
 203
 204 // gcc 4.8 needs more -Wmaybe-uninitialized tickling, as it propagates the
 205 // taint upstream from loadRMW
 206
 207 #pragma GCC diagnostic push
 208 #pragma GCC diagnostic ignored "-Wuninitialized"
 209 #if !__clang__ // for gcc version [4.8, ?)
 210 #pragma GCC diagnostic ignored "-Wmaybe-uninitialized"
 211 #endif
 212
 213 template <class T, class Traits>
 214 inline void Bits<T, Traits>::set(T* p, size_t bit) {
 215   T& block = p[blockIndex(bit)];
 216   Traits::store(block, Traits::loadRMW(block) | (one << bitOffset(bit)));
 217 }
 218
 219 template <class T, class Traits>
 220 inline void Bits<T, Traits>::clear(T* p, size_t bit) {
 221   T& block = p[blockIndex(bit)];
 222   Traits::store(block, Traits::loadRMW(block) & ~(one << bitOffset(bit)));
 223 }
 224
 225 template <class T, class Traits>
 226 inline void Bits<T, Traits>::set(T* p, size_t bitStart, size_t count,
 227                                  UnderlyingType value) {
 228   DCHECK_LE(count, sizeof(UnderlyingType) * 8);
 229   size_t cut = bitsPerBlock - count;
 230   if (cut != 8 * sizeof(UnderlyingType)) {
 231     using U = typename std::make_unsigned<UnderlyingType>::type;
 232     DCHECK_EQ(value, UnderlyingType(U(value) << cut) >> cut);
 233   }
 234   size_t idx = blockIndex(bitStart);
 235   size_t offset = bitOffset(bitStart);
 236   if (std::is_signed<UnderlyingType>::value) {
 237     value &= ones(count);
 238   }
 239   if (offset + count <= bitsPerBlock) {
 240     innerSet(p + idx, offset, count, value);
 241   } else {
 242     size_t countInThisBlock = bitsPerBlock - offset;
 243     size_t countInNextBlock = count - countInThisBlock;
 244
 245     UnderlyingType thisBlock = value & ((one << countInThisBlock) - 1);
 246     UnderlyingType nextBlock = value >> countInThisBlock;
 247     if (std::is_signed<UnderlyingType>::value) {
 248       nextBlock &= ones(countInNextBlock);
 249     }
 250     innerSet(p + idx, offset, countInThisBlock, thisBlock);
 251     innerSet(p + idx + 1, 0, countInNextBlock, nextBlock);
 252   }
 253 }
 254
 255 template <class T, class Traits>
 256 inline void Bits<T, Traits>::innerSet(T* p, size_t offset, size_t count,
 257                                       UnderlyingType value) {
 258   // Mask out bits and set new value
 259   UnderlyingType v = Traits::loadRMW(*p);
 260   v &= ~(ones(count) << offset);
 261   v |= (value << offset);
 262   Traits::store(*p, v);
 263 }
 264
 265 #pragma GCC diagnostic pop
 266
 267 template <class T, class Traits>
 268 inline bool Bits<T, Traits>::test(const T* p, size_t bit) {
 269   return Traits::load(p[blockIndex(bit)]) & (one << bitOffset(bit));
 270 }
 271
 272 template <class T, class Traits>
 273 inline auto Bits<T, Traits>::get(const T* p, size_t bitStart, size_t count)
 274   -> UnderlyingType {
 275   if (count == 0) {
 276     return UnderlyingType{};
 277   }
 278
 279   DCHECK_LE(count, sizeof(UnderlyingType) * 8);
 280   size_t idx = blockIndex(bitStart);
 281   size_t offset = bitOffset(bitStart);
 282   UnderlyingType ret;
 283   if (offset + count <= bitsPerBlock) {
 284     ret = innerGet(p + idx, offset, count);
 285   } else {
 286     size_t countInThisBlock = bitsPerBlock - offset;
 287     size_t countInNextBlock = count - countInThisBlock;
 288     UnderlyingType thisBlockValue = innerGet(p + idx, offset, countInThisBlock);
 289     UnderlyingType nextBlockValue = innerGet(p + idx + 1, 0, countInNextBlock);
 290     ret = (nextBlockValue << countInThisBlock) | thisBlockValue;
 291   }
 292   if (std::is_signed<UnderlyingType>::value) {
 293     size_t emptyBits = bitsPerBlock - count;
 294     ret <<= emptyBits;
 295     ret >>= emptyBits;
 296   }
 297   return ret;
 298 }
 299
 300 template <class T, class Traits>
 301 inline auto Bits<T, Traits>::innerGet(const T* p, size_t offset, size_t count)
 302     -> UnderlyingType {
 303   return (Traits::load(*p) >> offset) & ones(count);
 304 }
 305
 306 template <class T, class Traits>
 307 inline size_t Bits<T, Traits>::count(const T* begin, const T* end) {
 308   size_t n = 0;
 309   for (; begin != end; ++begin) {
 310     n += popcount(Traits::load(*begin));
 311   }
 312   return n;
 313 }
 314
 315 }  // namespace folly