1 | /* |
2 | * Copyright 2011-present 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 | /** |
18 | * Various low-level, bit-manipulation routines. |
19 | * |
20 | * findFirstSet(x) [constexpr] |
21 | * find first (least significant) bit set in a value of an integral type, |
22 | * 1-based (like ffs()). 0 = no bits are set (x == 0) |
23 | * |
24 | * findLastSet(x) [constexpr] |
25 | * find last (most significant) bit set in a value of an integral type, |
26 | * 1-based. 0 = no bits are set (x == 0) |
27 | * for x != 0, findLastSet(x) == 1 + floor(log2(x)) |
28 | * |
29 | * nextPowTwo(x) [constexpr] |
30 | * Finds the next power of two >= x. |
31 | * |
32 | * isPowTwo(x) [constexpr] |
33 | * return true iff x is a power of two |
34 | * |
35 | * popcount(x) |
36 | * return the number of 1 bits in x |
37 | * |
38 | * Endian |
39 | * convert between native, big, and little endian representation |
40 | * Endian::big(x) big <-> native |
41 | * Endian::little(x) little <-> native |
42 | * Endian::swap(x) big <-> little |
43 | * |
44 | * @author Tudor Bosman (tudorb@fb.com) |
45 | */ |
46 | |
47 | #pragma once |
48 | |
49 | #include <cassert> |
50 | #include <cinttypes> |
51 | #include <cstdint> |
52 | #include <cstring> |
53 | #include <limits> |
54 | #include <type_traits> |
55 | |
56 | #include <folly/ConstexprMath.h> |
57 | #include <folly/Portability.h> |
58 | #include <folly/Utility.h> |
59 | #include <folly/lang/Assume.h> |
60 | #include <folly/portability/Builtins.h> |
61 | |
62 | namespace folly { |
63 | |
64 | namespace detail { |
65 | template <typename Dst, typename Src> |
66 | constexpr std::make_signed_t<Dst> bits_to_signed(Src const s) { |
67 | static_assert(std::is_signed<Dst>::value, "unsigned type" ); |
68 | return to_signed(static_cast<std::make_unsigned_t<Dst>>(to_unsigned(s))); |
69 | } |
70 | template <typename Dst, typename Src> |
71 | constexpr std::make_unsigned_t<Dst> bits_to_unsigned(Src const s) { |
72 | static_assert(std::is_unsigned<Dst>::value, "signed type" ); |
73 | return static_cast<Dst>(to_unsigned(s)); |
74 | } |
75 | } // namespace detail |
76 | |
77 | /// findFirstSet |
78 | /// |
79 | /// Return the 1-based index of the least significant bit which is set. |
80 | /// For x > 0, the exponent in the largest power of two which does not divide x. |
81 | template <typename T> |
82 | inline constexpr unsigned int findFirstSet(T const v) { |
83 | using S0 = int; |
84 | using S1 = long int; |
85 | using S2 = long long int; |
86 | using detail::bits_to_signed; |
87 | static_assert(sizeof(T) <= sizeof(S2), "over-sized type" ); |
88 | static_assert(std::is_integral<T>::value, "non-integral type" ); |
89 | static_assert(!std::is_same<T, bool>::value, "bool type" ); |
90 | |
91 | // clang-format off |
92 | return static_cast<unsigned int>( |
93 | sizeof(T) <= sizeof(S0) ? __builtin_ffs(bits_to_signed<S0>(v)) : |
94 | sizeof(T) <= sizeof(S1) ? __builtin_ffsl(bits_to_signed<S1>(v)) : |
95 | sizeof(T) <= sizeof(S2) ? __builtin_ffsll(bits_to_signed<S2>(v)) : |
96 | 0); |
97 | // clang-format on |
98 | } |
99 | |
100 | /// findLastSet |
101 | /// |
102 | /// Return the 1-based index of the most significant bit which is set. |
103 | /// For x > 0, findLastSet(x) == 1 + floor(log2(x)). |
104 | template <typename T> |
105 | inline constexpr unsigned int findLastSet(T const v) { |
106 | using U0 = unsigned int; |
107 | using U1 = unsigned long int; |
108 | using U2 = unsigned long long int; |
109 | using detail::bits_to_unsigned; |
110 | static_assert(sizeof(T) <= sizeof(U2), "over-sized type" ); |
111 | static_assert(std::is_integral<T>::value, "non-integral type" ); |
112 | static_assert(!std::is_same<T, bool>::value, "bool type" ); |
113 | |
114 | // If X is a power of two X - Y = 1 + ((X - 1) ^ Y). Doing this transformation |
115 | // allows GCC to remove its own xor that it adds to implement clz using bsr. |
116 | // clang-format off |
117 | using size = index_constant<constexpr_max(sizeof(T), sizeof(U0))>; |
118 | return v ? 1u + static_cast<unsigned int>((8u * size{} - 1u) ^ ( |
119 | sizeof(T) <= sizeof(U0) ? __builtin_clz(bits_to_unsigned<U0>(v)) : |
120 | sizeof(T) <= sizeof(U1) ? __builtin_clzl(bits_to_unsigned<U1>(v)) : |
121 | sizeof(T) <= sizeof(U2) ? __builtin_clzll(bits_to_unsigned<U2>(v)) : |
122 | 0)) : 0u; |
123 | // clang-format on |
124 | } |
125 | |
126 | /// popcount |
127 | /// |
128 | /// Returns the number of bits which are set. |
129 | template <typename T> |
130 | inline constexpr unsigned int popcount(T const v) { |
131 | using U0 = unsigned int; |
132 | using U1 = unsigned long int; |
133 | using U2 = unsigned long long int; |
134 | using detail::bits_to_unsigned; |
135 | static_assert(sizeof(T) <= sizeof(U2), "over-sized type" ); |
136 | static_assert(std::is_integral<T>::value, "non-integral type" ); |
137 | static_assert(!std::is_same<T, bool>::value, "bool type" ); |
138 | |
139 | // clang-format off |
140 | return static_cast<unsigned int>( |
141 | sizeof(T) <= sizeof(U0) ? __builtin_popcount(bits_to_unsigned<U0>(v)) : |
142 | sizeof(T) <= sizeof(U1) ? __builtin_popcountl(bits_to_unsigned<U1>(v)) : |
143 | sizeof(T) <= sizeof(U2) ? __builtin_popcountll(bits_to_unsigned<U2>(v)) : |
144 | 0); |
145 | // clang-format on |
146 | } |
147 | |
148 | template <class T> |
149 | inline constexpr T nextPowTwo(T const v) { |
150 | static_assert(std::is_unsigned<T>::value, "signed type" ); |
151 | return v ? (T(1) << findLastSet(v - 1)) : T(1); |
152 | } |
153 | |
154 | template <class T> |
155 | inline constexpr T prevPowTwo(T const v) { |
156 | static_assert(std::is_unsigned<T>::value, "signed type" ); |
157 | return v ? (T(1) << (findLastSet(v) - 1)) : T(0); |
158 | } |
159 | |
160 | template <class T> |
161 | inline constexpr bool isPowTwo(T const v) { |
162 | static_assert(std::is_integral<T>::value, "non-integral type" ); |
163 | static_assert(std::is_unsigned<T>::value, "signed type" ); |
164 | static_assert(!std::is_same<T, bool>::value, "bool type" ); |
165 | return (v != 0) && !(v & (v - 1)); |
166 | } |
167 | |
168 | /** |
169 | * Endianness detection and manipulation primitives. |
170 | */ |
171 | namespace detail { |
172 | |
173 | template <size_t Size> |
174 | struct uint_types_by_size; |
175 | |
176 | #define FB_GEN(sz, fn) \ |
177 | static inline uint##sz##_t byteswap_gen(uint##sz##_t v) { \ |
178 | return fn(v); \ |
179 | } \ |
180 | template <> \ |
181 | struct uint_types_by_size<sz / 8> { \ |
182 | using type = uint##sz##_t; \ |
183 | }; |
184 | |
185 | FB_GEN(8, uint8_t) |
186 | #ifdef _MSC_VER |
187 | FB_GEN(64, _byteswap_uint64) |
188 | FB_GEN(32, _byteswap_ulong) |
189 | FB_GEN(16, _byteswap_ushort) |
190 | #else |
191 | FB_GEN(64, __builtin_bswap64) |
192 | FB_GEN(32, __builtin_bswap32) |
193 | FB_GEN(16, __builtin_bswap16) |
194 | #endif |
195 | |
196 | #undef FB_GEN |
197 | |
198 | template <class T> |
199 | struct EndianInt { |
200 | static_assert( |
201 | (std::is_integral<T>::value && !std::is_same<T, bool>::value) || |
202 | std::is_floating_point<T>::value, |
203 | "template type parameter must be non-bool integral or floating point" ); |
204 | static T swap(T x) { |
205 | // we implement this with memcpy because that is defined behavior in C++ |
206 | // we rely on compilers to optimize away the memcpy calls |
207 | constexpr auto s = sizeof(T); |
208 | using B = typename uint_types_by_size<s>::type; |
209 | B b; |
210 | std::memcpy(&b, &x, s); |
211 | b = byteswap_gen(b); |
212 | std::memcpy(&x, &b, s); |
213 | return x; |
214 | } |
215 | static T big(T x) { |
216 | return kIsLittleEndian ? EndianInt::swap(x) : x; |
217 | } |
218 | static T little(T x) { |
219 | return kIsBigEndian ? EndianInt::swap(x) : x; |
220 | } |
221 | }; |
222 | |
223 | } // namespace detail |
224 | |
225 | // big* convert between native and big-endian representations |
226 | // little* convert between native and little-endian representations |
227 | // swap* convert between big-endian and little-endian representations |
228 | // |
229 | // ntohs, htons == big16 |
230 | // ntohl, htonl == big32 |
231 | #define FB_GEN1(fn, t, sz) \ |
232 | static t fn##sz(t x) { \ |
233 | return fn<t>(x); \ |
234 | } |
235 | |
236 | #define FB_GEN2(t, sz) \ |
237 | FB_GEN1(swap, t, sz) \ |
238 | FB_GEN1(big, t, sz) \ |
239 | FB_GEN1(little, t, sz) |
240 | |
241 | #define FB_GEN(sz) \ |
242 | FB_GEN2(uint##sz##_t, sz) \ |
243 | FB_GEN2(int##sz##_t, sz) |
244 | |
245 | class Endian { |
246 | public: |
247 | enum class Order : uint8_t { |
248 | LITTLE, |
249 | BIG, |
250 | }; |
251 | |
252 | static constexpr Order order = kIsLittleEndian ? Order::LITTLE : Order::BIG; |
253 | |
254 | template <class T> |
255 | static T swap(T x) { |
256 | return folly::detail::EndianInt<T>::swap(x); |
257 | } |
258 | template <class T> |
259 | static T big(T x) { |
260 | return folly::detail::EndianInt<T>::big(x); |
261 | } |
262 | template <class T> |
263 | static T little(T x) { |
264 | return folly::detail::EndianInt<T>::little(x); |
265 | } |
266 | |
267 | #if !defined(__ANDROID__) |
268 | FB_GEN(64) |
269 | FB_GEN(32) |
270 | FB_GEN(16) |
271 | FB_GEN(8) |
272 | #endif |
273 | }; |
274 | |
275 | #undef FB_GEN |
276 | #undef FB_GEN2 |
277 | #undef FB_GEN1 |
278 | |
279 | template <class T, class Enable = void> |
280 | struct Unaligned; |
281 | |
282 | /** |
283 | * Representation of an unaligned value of a POD type. |
284 | */ |
285 | FOLLY_PACK_PUSH |
286 | template <class T> |
287 | struct Unaligned<T, typename std::enable_if<std::is_pod<T>::value>::type> { |
288 | Unaligned() = default; // uninitialized |
289 | /* implicit */ Unaligned(T v) : value(v) {} |
290 | T value; |
291 | } FOLLY_PACK_ATTR; |
292 | FOLLY_PACK_POP |
293 | |
294 | /** |
295 | * Read an unaligned value of type T and return it. |
296 | */ |
297 | template <class T> |
298 | inline T loadUnaligned(const void* p) { |
299 | static_assert(sizeof(Unaligned<T>) == sizeof(T), "Invalid unaligned size" ); |
300 | static_assert(alignof(Unaligned<T>) == 1, "Invalid alignment" ); |
301 | if (kHasUnalignedAccess) { |
302 | return static_cast<const Unaligned<T>*>(p)->value; |
303 | } else { |
304 | T value; |
305 | memcpy(&value, p, sizeof(T)); |
306 | return value; |
307 | } |
308 | } |
309 | |
310 | /** |
311 | * Read l bytes into the low bits of a value of an unsigned integral |
312 | * type T, where l < sizeof(T). |
313 | * |
314 | * This is intended as a complement to loadUnaligned to read the tail |
315 | * of a buffer when it is processed one word at a time. |
316 | */ |
317 | template <class T> |
318 | inline T partialLoadUnaligned(const void* p, size_t l) { |
319 | static_assert( |
320 | std::is_integral<T>::value && std::is_unsigned<T>::value && |
321 | sizeof(T) <= 8, |
322 | "Invalid type" ); |
323 | assume(l < sizeof(T)); |
324 | |
325 | auto cp = static_cast<const char*>(p); |
326 | T value = 0; |
327 | if (!kHasUnalignedAccess || !kIsLittleEndian) { |
328 | // Unsupported, use memcpy. |
329 | memcpy(&value, cp, l); |
330 | return value; |
331 | } |
332 | |
333 | auto avail = l; |
334 | if (l & 4) { |
335 | avail -= 4; |
336 | value = static_cast<T>(loadUnaligned<uint32_t>(cp + avail)) << (avail * 8); |
337 | } |
338 | if (l & 2) { |
339 | avail -= 2; |
340 | value |= static_cast<T>(loadUnaligned<uint16_t>(cp + avail)) << (avail * 8); |
341 | } |
342 | if (l & 1) { |
343 | value |= loadUnaligned<uint8_t>(cp); |
344 | } |
345 | return value; |
346 | } |
347 | |
348 | /** |
349 | * Write an unaligned value of type T. |
350 | */ |
351 | template <class T> |
352 | inline void storeUnaligned(void* p, T value) { |
353 | static_assert(sizeof(Unaligned<T>) == sizeof(T), "Invalid unaligned size" ); |
354 | static_assert(alignof(Unaligned<T>) == 1, "Invalid alignment" ); |
355 | if (kHasUnalignedAccess) { |
356 | // Prior to C++14, the spec says that a placement new like this |
357 | // is required to check that p is not nullptr, and to do nothing |
358 | // if p is a nullptr. By assuming it's not a nullptr, we get a |
359 | // nice loud segfault in optimized builds if p is nullptr, rather |
360 | // than just silently doing nothing. |
361 | assume(p != nullptr); |
362 | new (p) Unaligned<T>(value); |
363 | } else { |
364 | memcpy(p, &value, sizeof(T)); |
365 | } |
366 | } |
367 | |
368 | template <typename T> |
369 | T bitReverse(T n) { |
370 | auto m = static_cast<typename std::make_unsigned<T>::type>(n); |
371 | m = ((m & 0xAAAAAAAAAAAAAAAA) >> 1) | ((m & 0x5555555555555555) << 1); |
372 | m = ((m & 0xCCCCCCCCCCCCCCCC) >> 2) | ((m & 0x3333333333333333) << 2); |
373 | m = ((m & 0xF0F0F0F0F0F0F0F0) >> 4) | ((m & 0x0F0F0F0F0F0F0F0F) << 4); |
374 | return static_cast<T>(Endian::swap(m)); |
375 | } |
376 | |
377 | } // namespace folly |
378 | |