folly/experimental/Bits.h

   1 /*
   2  * Copyright 2012 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/Range.h"
  26
  27 namespace folly {
  28
  29 // As a general rule, bit operations work on unsigned values only;
  30 // right-shift is arithmetic for signed values, and that can lead to
  31 // unpleasant bugs.
  32
  33 /**
  34  * Population count (number of bits set), using __builtin_popcount or
  35  * __builtin_popcountll, depending on size.
  36  */
  37 template <class T>
  38 inline typename std::enable_if<
  39   (std::is_integral<T>::value &&
  40    std::is_unsigned<T>::value &&
  41    sizeof(T) <= sizeof(unsigned int)),
  42   size_t>::type
  43   popcount(T x) {
  44   return __builtin_popcount(x);
  45 }
  46
  47 template <class T>
  48 inline typename std::enable_if<
  49   (std::is_integral<T>::value &&
  50    std::is_unsigned<T>::value &&
  51    sizeof(T) > sizeof(unsigned int) &&
  52    sizeof(T) <= sizeof(unsigned long long)),
  53   size_t>::type
  54   popcount(T x) {
  55   return __builtin_popcountll(x);
  56 }
  57
  58 namespace detail {
  59
  60 /**
  61  * Helper class to make Bits<T> (below) work with both aligned values
  62  * (T, where T is an unsigned integral type) or unaligned values
  63  * (Unaligned<T>, where T is an unsigned integral type)
  64  */
  65 template <class T, class Enable=void> struct BitsTraits;
  66
  67 // Partial specialization for Unaligned<T>, where T is unsigned integral
  68 template <class T>
  69 struct BitsTraits<Unaligned<T>, typename std::enable_if<
  70     (std::is_integral<T>::value && std::is_unsigned<T>::value)>::type> {
  71   typedef T UnderlyingType;
  72   static T load(const Unaligned<T>& x) { return x.value; }
  73   static void store(Unaligned<T>& x, T v) { x.value = v; }
  74 };
  75
  76 // Partial specialization for T, where T is unsigned integral
  77 template <class T>
  78 struct BitsTraits<T, typename std::enable_if<
  79     (std::is_integral<T>::value && std::is_unsigned<T>::value)>::type> {
  80   typedef T UnderlyingType;
  81   static T load(const T& x) { return x; }
  82   static void store(T& x, T v) { x = v; }
  83 };
  84 }  // namespace detail
  85
  86 /**
  87  * Wrapper class with static methods for various bit-level operations,
  88  * treating an array of T as an array of bits (in little-endian order).
  89  * (T is either an unsigned integral type or Unaligned<X>, where X is
  90  * an unsigned integral type)
  91  */
  92 template <class T, class Traits=detail::BitsTraits<T>>
  93 struct Bits {
  94   typedef typename Traits::UnderlyingType UnderlyingType;
  95   typedef T type;
  96   static_assert(sizeof(T) == sizeof(UnderlyingType), "Size mismatch");
  97
  98   /**
  99    * Number of bits in a block.
 100    */
 101   static constexpr size_t bitsPerBlock =
 102     std::numeric_limits<UnderlyingType>::digits;
 103
 104   /**
 105    * Byte index of the given bit.
 106    */
 107   static constexpr size_t blockIndex(size_t bit) {
 108     return bit / bitsPerBlock;
 109   }
 110
 111   /**
 112    * Offset in block of the given bit.
 113    */
 114   static constexpr size_t bitOffset(size_t bit) {
 115     return bit % bitsPerBlock;
 116   }
 117
 118   /**
 119    * Number of blocks used by the given number of bits.
 120    */
 121   static constexpr size_t blockCount(size_t nbits) {
 122     return nbits / bitsPerBlock + (nbits % bitsPerBlock != 0);
 123   }
 124
 125   /**
 126    * Set the given bit.
 127    */
 128   static void set(T* p, size_t bit);
 129
 130   /**
 131    * Clear the given bit.
 132    */
 133   static void clear(T* p, size_t bit);
 134
 135   /**
 136    * Test the given bit.
 137    */
 138   static bool test(const T* p, size_t bit);
 139
 140   /**
 141    * Set count contiguous bits starting at bitStart to the values
 142    * from the least significant count bits of value; little endian.
 143    * (value & 1 becomes the bit at bitStart, etc)
 144    * Precondition: count <= sizeof(T) * 8
 145    */
 146   static void set(T* p, size_t bitStart, size_t count, UnderlyingType value);
 147
 148   /**
 149    * Get count contiguous bits starting at bitStart.
 150    * Precondition: count <= sizeof(T) * 8
 151    */
 152   static UnderlyingType get(const T* p, size_t bitStart, size_t count);
 153
 154   /**
 155    * Count the number of bits set in a range of blocks.
 156    */
 157   static size_t count(const T* begin, const T* end);
 158
 159  private:
 160   // Same as set, assumes all bits are in the same block.
 161   // (bitStart < sizeof(T) * 8, bitStart + count <= sizeof(T) * 8)
 162   static void innerSet(T* p, size_t bitStart, size_t count,
 163                        UnderlyingType value);
 164
 165   // Same as get, assumes all bits are in the same block.
 166   // (bitStart < sizeof(T) * 8, bitStart + count <= sizeof(T) * 8)
 167   static UnderlyingType innerGet(const T* p, size_t bitStart, size_t count);
 168
 169   static constexpr UnderlyingType one = UnderlyingType(1);
 170 };
 171
 172 template <class T, class Traits>
 173 inline void Bits<T, Traits>::set(T* p, size_t bit) {
 174   T& block = p[blockIndex(bit)];
 175   Traits::store(block, Traits::load(block) | (one << bitOffset(bit)));
 176 }
 177
 178 template <class T, class Traits>
 179 inline void Bits<T, Traits>::clear(T* p, size_t bit) {
 180   T& block = p[blockIndex(bit)];
 181   Traits::store(block, Traits::load(block) & ~(one << bitOffset(bit)));
 182 }
 183
 184 template <class T, class Traits>
 185 inline bool Bits<T, Traits>::test(const T* p, size_t bit) {
 186   return Traits::load(p[blockIndex(bit)]) & (one << bitOffset(bit));
 187 }
 188
 189 template <class T, class Traits>
 190 inline void Bits<T, Traits>::set(T* p, size_t bitStart, size_t count,
 191                                  UnderlyingType value) {
 192   assert(count <= sizeof(UnderlyingType) * 8);
 193   assert(count == sizeof(UnderlyingType) ||
 194          (value & ~((one << count) - 1)) == 0);
 195   size_t idx = blockIndex(bitStart);
 196   size_t offset = bitOffset(bitStart);
 197   if (offset + count <= bitsPerBlock) {
 198     innerSet(p + idx, offset, count, value);
 199   } else {
 200     size_t countInThisBlock = bitsPerBlock - offset;
 201     size_t countInNextBlock = count - countInThisBlock;
 202     innerSet(p + idx, offset, countInThisBlock,
 203              value & ((one << countInThisBlock) - 1));
 204     innerSet(p + idx + 1, 0, countInNextBlock, value >> countInThisBlock);
 205   }
 206 }
 207
 208 template <class T, class Traits>
 209 inline auto Bits<T, Traits>::get(const T* p, size_t bitStart, size_t count)
 210   -> UnderlyingType {
 211   assert(count <= sizeof(UnderlyingType) * 8);
 212   size_t idx = blockIndex(bitStart);
 213   size_t offset = bitOffset(bitStart);
 214   if (offset + count <= bitsPerBlock) {
 215     return innerGet(p + idx, offset, count);
 216   } else {
 217     size_t countInThisBlock = bitsPerBlock - offset;
 218     size_t countInNextBlock = count - countInThisBlock;
 219     UnderlyingType thisBlockValue = innerGet(p + idx, offset, countInThisBlock);
 220     UnderlyingType nextBlockValue = innerGet(p + idx + 1, 0, countInNextBlock);
 221     return (nextBlockValue << countInThisBlock) | thisBlockValue;
 222   }
 223 }
 224
 225 template <class T, class Traits>
 226 inline void Bits<T, Traits>::innerSet(T* p, size_t offset, size_t count,
 227                                       UnderlyingType value) {
 228   // Mask out bits and set new value
 229   UnderlyingType v = Traits::load(*p);
 230   v &= ~(((one << count) - 1) << offset);
 231   v |= (value << offset);
 232   Traits::store(*p, v);
 233 }
 234
 235 template <class T, class Traits>
 236 inline auto Bits<T, Traits>::innerGet(const T* p, size_t offset, size_t count)
 237   -> UnderlyingType {
 238   return (Traits::load(*p) >> offset) & ((one << count) - 1);
 239 }
 240
 241 template <class T, class Traits>
 242 inline size_t Bits<T, Traits>::count(const T* begin, const T* end) {
 243   size_t n = 0;
 244   for (; begin != end; ++begin) {
 245     n += popcount(Traits::load(*begin));
 246   }
 247   return n;
 248 }
 249
 250 }  // namespace folly
 251
 252 #endif /* FOLLY_EXPERIMENTAL_BITS_H_ */
 253