2 * Copyright 2016 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.
20 #include <type_traits>
22 #include <glog/logging.h>
24 #include <folly/Bits.h>
25 #include <folly/Portability.h>
26 #include <folly/Range.h>
31 struct UnalignedNoASan : public Unaligned<T> { };
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
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)
44 template <class T, class Enable = void>
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.
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"
64 #pragma GCC diagnostic pop
68 // Special version that allows to disable address sanitizer on demand.
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"
85 #pragma GCC diagnostic pop
89 // Partial specialization for T, where T is unsigned integral
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"
103 #pragma GCC diagnostic pop
107 } // namespace detail
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)
115 template <class T, class Traits=detail::BitsTraits<T>>
117 typedef typename Traits::UnderlyingType UnderlyingType;
119 static_assert(sizeof(T) == sizeof(UnderlyingType), "Size mismatch");
122 * Number of bits in a block.
124 static constexpr size_t bitsPerBlock = std::numeric_limits<
125 typename std::make_unsigned<UnderlyingType>::type>::digits;
128 * Byte index of the given bit.
130 static constexpr size_t blockIndex(size_t bit) {
131 return bit / bitsPerBlock;
135 * Offset in block of the given bit.
137 static constexpr size_t bitOffset(size_t bit) {
138 return bit % bitsPerBlock;
142 * Number of blocks used by the given number of bits.
144 static constexpr size_t blockCount(size_t nbits) {
145 return nbits / bitsPerBlock + (nbits % bitsPerBlock != 0);
151 static void set(T* p, size_t bit);
154 * Clear the given bit.
156 static void clear(T* p, size_t bit);
159 * Test the given bit.
161 static bool test(const T* p, size_t bit);
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
170 static void set(T* p, size_t bitStart, size_t count, UnderlyingType value);
173 * Get count contiguous bits starting at bitStart.
174 * Precondition: count <= sizeof(T) * 8
176 static UnderlyingType get(const T* p, size_t bitStart, size_t count);
179 * Count the number of bits set in a range of blocks.
181 static size_t count(const T* begin, const T* end);
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);
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);
193 static constexpr UnderlyingType zero = UnderlyingType(0);
194 static constexpr UnderlyingType one = UnderlyingType(1);
196 static constexpr UnderlyingType ones(size_t count) {
197 return count < bitsPerBlock ? (one << count) - 1 : ~zero;
201 // gcc 4.8 needs more -Wmaybe-uninitialized tickling, as it propagates the
202 // taint upstream from loadRMW
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"
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)));
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)));
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);
233 if (offset + count <= bitsPerBlock) {
234 innerSet(p + idx, offset, count, value);
236 size_t countInThisBlock = bitsPerBlock - offset;
237 size_t countInNextBlock = count - countInThisBlock;
239 UnderlyingType thisBlock = value & ((one << countInThisBlock) - 1);
240 UnderlyingType nextBlock = value >> countInThisBlock;
241 if (std::is_signed<UnderlyingType>::value) {
242 nextBlock &= ones(countInNextBlock);
244 innerSet(p + idx, offset, countInThisBlock, thisBlock);
245 innerSet(p + idx + 1, 0, countInNextBlock, nextBlock);
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);
259 #pragma GCC diagnostic pop
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));
266 template <class T, class Traits>
267 inline auto Bits<T, Traits>::get(const T* p, size_t bitStart, size_t count)
269 DCHECK_LE(count, sizeof(UnderlyingType) * 8);
270 size_t idx = blockIndex(bitStart);
271 size_t offset = bitOffset(bitStart);
273 if (offset + count <= bitsPerBlock) {
274 ret = innerGet(p + idx, offset, count);
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;
282 if (std::is_signed<UnderlyingType>::value) {
283 size_t emptyBits = bitsPerBlock - count;
290 template <class T, class Traits>
291 inline auto Bits<T, Traits>::innerGet(const T* p, size_t offset, size_t count)
293 return (Traits::load(*p) >> offset) & ones(count);
296 template <class T, class Traits>
297 inline size_t Bits<T, Traits>::count(const T* begin, const T* end) {
299 for (; begin != end; ++begin) {
300 n += popcount(Traits::load(*begin));