2 * Copyright 2014 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.
17 #ifndef FOLLY_EXPERIMENTAL_BITS_H_
18 #define FOLLY_EXPERIMENTAL_BITS_H_
21 #include <type_traits>
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 // make sure we compile without warning on gcc 4.6 with -Wpragmas
61 #if __GNUC_PREREQ(4, 7)
62 #pragma GCC diagnostic ignored "-Wmaybe-uninitialized"
65 #pragma GCC diagnostic pop
69 // Special version that allows 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) {
80 #pragma GCC diagnostic push
81 #pragma GCC diagnostic ignored "-Wuninitialized"
82 // make sure we compile without warning on gcc 4.6 with -Wpragmas
83 #if __GNUC_PREREQ(4, 7)
84 #pragma GCC diagnostic ignored "-Wmaybe-uninitialized"
87 #pragma GCC diagnostic pop
91 // Partial specialization for T, where T is unsigned integral
93 struct BitsTraits<T, typename std::enable_if<
94 (std::is_integral<T>::value)>::type> {
95 typedef T UnderlyingType;
96 static T load(const T& x) { return x; }
97 static void store(T& x, T v) { x = v; }
98 static T loadRMW(const T& x) {
99 #pragma GCC diagnostic push
100 #pragma GCC diagnostic ignored "-Wuninitialized"
101 #if __GNUC_PREREQ(4, 7)
102 #pragma GCC diagnostic ignored "-Wmaybe-uninitialized"
105 #pragma GCC diagnostic pop
109 } // namespace detail
112 * Wrapper class with static methods for various bit-level operations,
113 * treating an array of T as an array of bits (in little-endian order).
114 * (T is either an unsigned integral type or Unaligned<X>, where X is
115 * an unsigned integral type)
117 template <class T, class Traits=detail::BitsTraits<T>>
119 typedef typename Traits::UnderlyingType UnderlyingType;
121 static_assert(sizeof(T) == sizeof(UnderlyingType), "Size mismatch");
124 * Number of bits in a block.
126 static constexpr size_t bitsPerBlock = std::numeric_limits<
127 typename std::make_unsigned<UnderlyingType>::type>::digits;
130 * Byte index of the given bit.
132 static constexpr size_t blockIndex(size_t bit) {
133 return bit / bitsPerBlock;
137 * Offset in block of the given bit.
139 static constexpr size_t bitOffset(size_t bit) {
140 return bit % bitsPerBlock;
144 * Number of blocks used by the given number of bits.
146 static constexpr size_t blockCount(size_t nbits) {
147 return nbits / bitsPerBlock + (nbits % bitsPerBlock != 0);
153 static void set(T* p, size_t bit);
156 * Clear the given bit.
158 static void clear(T* p, size_t bit);
161 * Test the given bit.
163 static bool test(const T* p, size_t bit);
166 * Set count contiguous bits starting at bitStart to the values
167 * from the least significant count bits of value; little endian.
168 * (value & 1 becomes the bit at bitStart, etc)
169 * Precondition: count <= sizeof(T) * 8
170 * Precondition: value can fit in 'count' bits
172 static void set(T* p, size_t bitStart, size_t count, UnderlyingType value);
175 * Get count contiguous bits starting at bitStart.
176 * Precondition: count <= sizeof(T) * 8
178 static UnderlyingType get(const T* p, size_t bitStart, size_t count);
181 * Count the number of bits set in a range of blocks.
183 static size_t count(const T* begin, const T* end);
186 // Same as set, assumes all bits are in the same block.
187 // (bitStart < sizeof(T) * 8, bitStart + count <= sizeof(T) * 8)
188 static void innerSet(T* p, size_t bitStart, size_t count,
189 UnderlyingType value);
191 // Same as get, assumes all bits are in the same block.
192 // (bitStart < sizeof(T) * 8, bitStart + count <= sizeof(T) * 8)
193 static UnderlyingType innerGet(const T* p, size_t bitStart, size_t count);
195 static constexpr UnderlyingType zero = UnderlyingType(0);
196 static constexpr UnderlyingType one = UnderlyingType(1);
198 static constexpr UnderlyingType ones(size_t count) {
199 return count < bitsPerBlock ? (one << count) - 1 : ~zero;
203 // gcc 4.8 needs more -Wmaybe-uninitialized tickling, as it propagates the
204 // taint upstream from loadRMW
206 #pragma GCC diagnostic push
207 #pragma GCC diagnostic ignored "-Wuninitialized"
208 #if __GNUC_PREREQ(4, 7)
209 #pragma GCC diagnostic ignored "-Wmaybe-uninitialized"
212 template <class T, class Traits>
213 inline void Bits<T, Traits>::set(T* p, size_t bit) {
214 T& block = p[blockIndex(bit)];
215 Traits::store(block, Traits::loadRMW(block) | (one << bitOffset(bit)));
218 template <class T, class Traits>
219 inline void Bits<T, Traits>::clear(T* p, size_t bit) {
220 T& block = p[blockIndex(bit)];
221 Traits::store(block, Traits::loadRMW(block) & ~(one << bitOffset(bit)));
224 template <class T, class Traits>
225 inline void Bits<T, Traits>::set(T* p, size_t bitStart, size_t count,
226 UnderlyingType value) {
227 assert(count <= sizeof(UnderlyingType) * 8);
228 size_t cut = bitsPerBlock - count;
229 assert(value == (value << cut >> cut));
230 size_t idx = blockIndex(bitStart);
231 size_t offset = bitOffset(bitStart);
232 if (std::is_signed<UnderlyingType>::value) {
233 value &= ones(count);
235 if (offset + count <= bitsPerBlock) {
236 innerSet(p + idx, offset, count, value);
238 size_t countInThisBlock = bitsPerBlock - offset;
239 size_t countInNextBlock = count - countInThisBlock;
241 UnderlyingType thisBlock = value & ((one << countInThisBlock) - 1);
242 UnderlyingType nextBlock = value >> countInThisBlock;
243 if (std::is_signed<UnderlyingType>::value) {
244 nextBlock &= ones(countInNextBlock);
246 innerSet(p + idx, offset, countInThisBlock, thisBlock);
247 innerSet(p + idx + 1, 0, countInNextBlock, nextBlock);
251 template <class T, class Traits>
252 inline void Bits<T, Traits>::innerSet(T* p, size_t offset, size_t count,
253 UnderlyingType value) {
254 // Mask out bits and set new value
255 UnderlyingType v = Traits::loadRMW(*p);
256 v &= ~(ones(count) << offset);
257 v |= (value << offset);
258 Traits::store(*p, v);
261 #pragma GCC diagnostic pop
263 template <class T, class Traits>
264 inline bool Bits<T, Traits>::test(const T* p, size_t bit) {
265 return Traits::load(p[blockIndex(bit)]) & (one << bitOffset(bit));
268 template <class T, class Traits>
269 inline auto Bits<T, Traits>::get(const T* p, size_t bitStart, size_t count)
271 assert(count <= sizeof(UnderlyingType) * 8);
272 size_t idx = blockIndex(bitStart);
273 size_t offset = bitOffset(bitStart);
275 if (offset + count <= bitsPerBlock) {
276 ret = innerGet(p + idx, offset, count);
278 size_t countInThisBlock = bitsPerBlock - offset;
279 size_t countInNextBlock = count - countInThisBlock;
280 UnderlyingType thisBlockValue = innerGet(p + idx, offset, countInThisBlock);
281 UnderlyingType nextBlockValue = innerGet(p + idx + 1, 0, countInNextBlock);
282 ret = (nextBlockValue << countInThisBlock) | thisBlockValue;
284 if (std::is_signed<UnderlyingType>::value) {
285 size_t emptyBits = bitsPerBlock - count;
292 template <class T, class Traits>
293 inline auto Bits<T, Traits>::innerGet(const T* p, size_t offset, size_t count)
295 return (Traits::load(*p) >> offset) & ones(count);
298 template <class T, class Traits>
299 inline size_t Bits<T, Traits>::count(const T* begin, const T* end) {
301 for (; begin != end; ++begin) {
302 n += popcount(Traits::load(*begin));
309 #endif /* FOLLY_EXPERIMENTAL_BITS_H_ */