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 #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 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   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 !__clang__ // for gcc version [4.8, ?)
 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   DCHECK_LE(count, sizeof(UnderlyingType) * 8);
 226   size_t cut = bitsPerBlock - count;
 227   DCHECK_EQ(value, value << cut >> cut);
 228   size_t idx = blockIndex(bitStart);
 229   size_t offset = bitOffset(bitStart);
 230   if (std::is_signed<UnderlyingType>::value) {
 231     value &= ones(count);
 232   }
 233   if (offset + count <= bitsPerBlock) {
 234     innerSet(p + idx, offset, count, value);
 235   } else {
 236     size_t countInThisBlock = bitsPerBlock - offset;
 237     size_t countInNextBlock = count - countInThisBlock;
 238
 239     UnderlyingType thisBlock = value & ((one << countInThisBlock) - 1);
 240     UnderlyingType nextBlock = value >> countInThisBlock;
 241     if (std::is_signed<UnderlyingType>::value) {
 242       nextBlock &= ones(countInNextBlock);
 243     }
 244     innerSet(p + idx, offset, countInThisBlock, thisBlock);
 245     innerSet(p + idx + 1, 0, countInNextBlock, nextBlock);
 246   }
 247 }
 248
 249 template <class T, class Traits>
 250 inline void Bits<T, Traits>::innerSet(T* p, size_t offset, size_t count,
 251                                       UnderlyingType value) {
 252   // Mask out bits and set new value
 253   UnderlyingType v = Traits::loadRMW(*p);
 254   v &= ~(ones(count) << offset);
 255   v |= (value << offset);
 256   Traits::store(*p, v);
 257 }
 258
 259 #pragma GCC diagnostic pop
 260
 261 template <class T, class Traits>
 262 inline bool Bits<T, Traits>::test(const T* p, size_t bit) {
 263   return Traits::load(p[blockIndex(bit)]) & (one << bitOffset(bit));
 264 }
 265
 266 template <class T, class Traits>
 267 inline auto Bits<T, Traits>::get(const T* p, size_t bitStart, size_t count)
 268   -> UnderlyingType {
 269   DCHECK_LE(count, sizeof(UnderlyingType) * 8);
 270   size_t idx = blockIndex(bitStart);
 271   size_t offset = bitOffset(bitStart);
 272   UnderlyingType ret;
 273   if (offset + count <= bitsPerBlock) {
 274     ret = innerGet(p + idx, offset, count);
 275   } else {
 276     size_t countInThisBlock = bitsPerBlock - offset;
 277     size_t countInNextBlock = count - countInThisBlock;
 278     UnderlyingType thisBlockValue = innerGet(p + idx, offset, countInThisBlock);
 279     UnderlyingType nextBlockValue = innerGet(p + idx + 1, 0, countInNextBlock);
 280     ret = (nextBlockValue << countInThisBlock) | thisBlockValue;
 281   }
 282   if (std::is_signed<UnderlyingType>::value) {
 283     size_t emptyBits = bitsPerBlock - count;
 284     ret <<= emptyBits;
 285     ret >>= emptyBits;
 286   }
 287   return ret;
 288 }
 289
 290 template <class T, class Traits>
 291 inline auto Bits<T, Traits>::innerGet(const T* p, size_t offset, size_t count)
 292     -> UnderlyingType {
 293   return (Traits::load(*p) >> offset) & ones(count);
 294 }
 295
 296 template <class T, class Traits>
 297 inline size_t Bits<T, Traits>::count(const T* begin, const T* end) {
 298   size_t n = 0;
 299   for (; begin != end; ++begin) {
 300     n += popcount(Traits::load(*begin));
 301   }
 302   return n;
 303 }
 304
 305 }  // namespace folly