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