2 * Copyright 2017 Facebook, Inc.
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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
21 #include <type_traits>
23 #include <glog/logging.h>
25 #include <folly/Bits.h>
26 #include <folly/Portability.h>
27 #include <folly/Range.h>
32 struct UnalignedNoASan : public Unaligned<T> { };
34 // As a general rule, bit operations work on unsigned values only;
35 // right-shift is arithmetic for signed values, and that can lead to
41 * Helper class to make Bits<T> (below) work with both aligned values
42 * (T, where T is an unsigned integral type) or unaligned values
43 * (Unaligned<T>, where T is an unsigned integral type)
45 template <class T, class Enable = void>
48 // Partial specialization for Unaligned<T>, where T is unsigned integral
49 // loadRMW is the same as load, but it indicates that it loads for a
50 // read-modify-write operation (we write back the bits we won't change);
51 // silence the GCC warning in that case.
53 struct BitsTraits<Unaligned<T>, typename std::enable_if<
54 (std::is_integral<T>::value)>::type> {
55 typedef T UnderlyingType;
56 static T load(const Unaligned<T>& x) { return x.value; }
57 static void store(Unaligned<T>& x, T v) { x.value = v; }
58 static T loadRMW(const Unaligned<T>& x) {
60 FOLLY_GCC_DISABLE_WARNING("-Wuninitialized")
61 #if !__clang__ // for gcc version [4.8, ?)
62 FOLLY_GCC_DISABLE_WARNING("-Wmaybe-uninitialized")
69 // Special version that allows one to disable address sanitizer on demand.
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) {
81 FOLLY_GCC_DISABLE_WARNING("-Wuninitialized")
82 #if !__clang__ // for gcc version [4.8, ?)
83 FOLLY_GCC_DISABLE_WARNING("-Wmaybe-uninitialized")
90 // Partial specialization for T, where T is unsigned integral
92 struct BitsTraits<T, typename std::enable_if<
93 (std::is_integral<T>::value)>::type> {
94 typedef T UnderlyingType;
95 static T load(const T& x) { return x; }
96 static void store(T& x, T v) { x = v; }
97 static T loadRMW(const T& x) {
99 FOLLY_GCC_DISABLE_WARNING("-Wuninitialized")
100 #if !__clang__ // for gcc version [4.8, ?)
101 FOLLY_GCC_DISABLE_WARNING("-Wmaybe-uninitialized")
108 } // namespace detail
111 * Wrapper class with static methods for various bit-level operations,
112 * treating an array of T as an array of bits (in little-endian order).
113 * (T is either an unsigned integral type or Unaligned<X>, where X is
114 * an unsigned integral type)
116 template <class T, class Traits=detail::BitsTraits<T>>
118 typedef typename Traits::UnderlyingType UnderlyingType;
120 static_assert(sizeof(T) == sizeof(UnderlyingType), "Size mismatch");
123 * Number of bits in a block.
125 static constexpr size_t bitsPerBlock = std::numeric_limits<
126 typename std::make_unsigned<UnderlyingType>::type>::digits;
129 * Byte index of the given bit.
131 static constexpr size_t blockIndex(size_t bit) {
132 return bit / bitsPerBlock;
136 * Offset in block of the given bit.
138 static constexpr size_t bitOffset(size_t bit) {
139 return bit % bitsPerBlock;
143 * Number of blocks used by the given number of bits.
145 static constexpr size_t blockCount(size_t nbits) {
146 return nbits / bitsPerBlock + (nbits % bitsPerBlock != 0);
152 static void set(T* p, size_t bit);
155 * Clear the given bit.
157 static void clear(T* p, size_t bit);
160 * Test the given bit.
162 static bool test(const T* p, size_t bit);
165 * Set count contiguous bits starting at bitStart to the values
166 * from the least significant count bits of value; little endian.
167 * (value & 1 becomes the bit at bitStart, etc)
168 * Precondition: count <= sizeof(T) * 8
169 * Precondition: value can fit in 'count' bits
171 static void set(T* p, size_t bitStart, size_t count, UnderlyingType value);
174 * Get count contiguous bits starting at bitStart.
175 * Precondition: count <= sizeof(T) * 8
177 static UnderlyingType get(const T* p, size_t bitStart, size_t count);
180 * Count the number of bits set in a range of blocks.
182 static size_t count(const T* begin, const T* end);
185 // Same as set, assumes all bits are in the same block.
186 // (bitStart < sizeof(T) * 8, bitStart + count <= sizeof(T) * 8)
187 static void innerSet(T* p, size_t bitStart, size_t count,
188 UnderlyingType value);
190 // Same as get, assumes all bits are in the same block.
191 // (bitStart < sizeof(T) * 8, bitStart + count <= sizeof(T) * 8)
192 static UnderlyingType innerGet(const T* p, size_t bitStart, size_t count);
194 static constexpr UnderlyingType zero = UnderlyingType(0);
195 static constexpr UnderlyingType one = UnderlyingType(1);
197 using UnsignedType = typename std::make_unsigned<UnderlyingType>::type;
198 static constexpr UnderlyingType ones(size_t count) {
199 return (count < bitsPerBlock)
200 ? static_cast<UnderlyingType>((UnsignedType{1} << count) - 1)
205 // gcc 4.8 needs more -Wmaybe-uninitialized tickling, as it propagates the
206 // taint upstream from loadRMW
208 FOLLY_GCC_DISABLE_WARNING("-Wuninitialized")
209 #if !__clang__ // for gcc version [4.8, ?)
210 FOLLY_GCC_DISABLE_WARNING("-Wmaybe-uninitialized")
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)));
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)));
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);
234 size_t idx = blockIndex(bitStart);
235 size_t offset = bitOffset(bitStart);
236 if (std::is_signed<UnderlyingType>::value) {
237 value &= ones(count);
239 if (offset + count <= bitsPerBlock) {
240 innerSet(p + idx, offset, count, value);
242 size_t countInThisBlock = bitsPerBlock - offset;
243 size_t countInNextBlock = count - countInThisBlock;
245 UnderlyingType thisBlock = UnderlyingType(value & ones(countInThisBlock));
246 UnderlyingType nextBlock = UnderlyingType(value >> countInThisBlock);
247 if (std::is_signed<UnderlyingType>::value) {
248 nextBlock &= ones(countInNextBlock);
250 innerSet(p + idx, offset, countInThisBlock, thisBlock);
251 innerSet(p + idx + 1, 0, countInNextBlock, nextBlock);
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);
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));
272 template <class T, class Traits>
273 inline auto Bits<T, Traits>::get(const T* p, size_t bitStart, size_t count)
276 return UnderlyingType{};
279 DCHECK_LE(count, sizeof(UnderlyingType) * 8);
280 size_t idx = blockIndex(bitStart);
281 size_t offset = bitOffset(bitStart);
283 if (offset + count <= bitsPerBlock) {
284 ret = innerGet(p + idx, offset, count);
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;
292 if (std::is_signed<UnderlyingType>::value) {
293 size_t emptyBits = bitsPerBlock - count;
300 template <class T, class Traits>
301 inline auto Bits<T, Traits>::innerGet(const T* p, size_t offset, size_t count)
303 return (Traits::load(*p) >> offset) & ones(count);
306 template <class T, class Traits>
307 inline size_t Bits<T, Traits>::count(const T* begin, const T* end) {
309 for (; begin != end; ++begin) {
310 n += popcount(Traits::load(*begin));