]>
Commit | Line | Data |
---|---|---|
f3e91052 JW |
1 | // <bit> -*- C++ -*- |
2 | ||
3 | // Copyright (C) 2018 Free Software Foundation, Inc. | |
4 | // | |
5 | // This file is part of the GNU ISO C++ Library. This library is free | |
6 | // software; you can redistribute it and/or modify it under the | |
7 | // terms of the GNU General Public License as published by the | |
8 | // Free Software Foundation; either version 3, or (at your option) | |
9 | // any later version. | |
10 | ||
11 | // This library is distributed in the hope that it will be useful, | |
12 | // but WITHOUT ANY WARRANTY; without even the implied warranty of | |
13 | // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
14 | // GNU General Public License for more details. | |
15 | ||
16 | // Under Section 7 of GPL version 3, you are granted additional | |
17 | // permissions described in the GCC Runtime Library Exception, version | |
18 | // 3.1, as published by the Free Software Foundation. | |
19 | ||
20 | // You should have received a copy of the GNU General Public License and | |
21 | // a copy of the GCC Runtime Library Exception along with this program; | |
22 | // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see | |
23 | // <http://www.gnu.org/licenses/>. | |
24 | ||
25 | /** @file include/bit | |
26 | * This is a Standard C++ Library header. | |
27 | */ | |
28 | ||
29 | #ifndef _GLIBCXX_BIT | |
30 | #define _GLIBCXX_BIT 1 | |
31 | ||
32 | #pragma GCC system_header | |
33 | ||
34 | #if __cplusplus >= 201402L | |
35 | ||
36 | #include <type_traits> | |
37 | #include <limits> | |
38 | ||
39 | namespace std _GLIBCXX_VISIBILITY(default) | |
40 | { | |
41 | _GLIBCXX_BEGIN_NAMESPACE_VERSION | |
42 | ||
43 | template<typename _Tp> | |
44 | constexpr _Tp | |
45 | __rotl(_Tp __x, unsigned int __s) noexcept | |
46 | { | |
47 | constexpr auto _Nd = numeric_limits<_Tp>::digits; | |
48 | const unsigned __sN = __s % _Nd; | |
4e4120a2 | 49 | return (__x << __sN) | (__x >> ((_Nd - __sN) % _Nd)); |
f3e91052 JW |
50 | } |
51 | ||
52 | template<typename _Tp> | |
53 | constexpr _Tp | |
54 | __rotr(_Tp __x, unsigned int __s) noexcept | |
55 | { | |
56 | constexpr auto _Nd = numeric_limits<_Tp>::digits; | |
57 | const unsigned __sN = __s % _Nd; | |
4e4120a2 | 58 | return (__x >> __sN) | (__x << ((_Nd - __sN) % _Nd)); |
f3e91052 JW |
59 | } |
60 | ||
61 | template<typename _Tp> | |
62 | constexpr int | |
63 | __countl_zero(_Tp __x) noexcept | |
64 | { | |
65 | using __limits = numeric_limits<_Tp>; | |
66 | ||
67 | if (__x == 0) | |
68 | return __limits::digits; | |
69 | ||
70 | using __limits_ull = numeric_limits<unsigned long long>; | |
71 | using __limits_ul = numeric_limits<unsigned long>; | |
72 | using __limits_u = numeric_limits<unsigned>; | |
73 | ||
74 | if _GLIBCXX17_CONSTEXPR (__limits::digits <= __limits_u::digits) | |
75 | { | |
76 | constexpr int __diff = __limits_u::digits - __limits::digits; | |
77 | return __builtin_clz(__x) - __diff; | |
78 | } | |
79 | else if _GLIBCXX17_CONSTEXPR (__limits::digits <= __limits_ul::digits) | |
80 | { | |
81 | constexpr int __diff = __limits_ul::digits - __limits::digits; | |
82 | return __builtin_clzl(__x) - __diff; | |
83 | } | |
84 | else if _GLIBCXX17_CONSTEXPR (__limits::digits <= __limits_ull::digits) | |
85 | { | |
86 | constexpr int __diff = __limits_ull::digits - __limits::digits; | |
87 | return __builtin_clzll(__x) - __diff; | |
88 | } | |
89 | else // (__limits::digits > __limits_ull::digits) | |
90 | { | |
91 | static_assert(__limits::digits <= (2 * __limits_ull::digits), | |
92 | "Maximum supported integer size is 128-bit"); | |
93 | ||
94 | unsigned long long __high = __x >> __limits_ull::digits; | |
95 | if (__high != 0) | |
96 | { | |
97 | constexpr int __diff | |
98 | = (2 * __limits_ull::digits) - __limits::digits; | |
99 | return __builtin_clzll(__high) - __diff; | |
100 | } | |
101 | unsigned long long __low = __x & __limits_ull::max(); | |
102 | return (__limits::digits - __limits_ull::digits) | |
103 | + __builtin_clzll(__low); | |
104 | } | |
105 | } | |
106 | ||
107 | template<typename _Tp> | |
108 | constexpr int | |
109 | __countl_one(_Tp __x) noexcept | |
110 | { | |
111 | if (__x == numeric_limits<_Tp>::max()) | |
112 | return numeric_limits<_Tp>::digits; | |
113 | return std::__countl_zero<_Tp>((_Tp)~__x); | |
114 | } | |
115 | ||
116 | template<typename _Tp> | |
117 | constexpr int | |
118 | __countr_zero(_Tp __x) noexcept | |
119 | { | |
120 | using __limits = numeric_limits<_Tp>; | |
121 | ||
122 | if (__x == 0) | |
123 | return __limits::digits; | |
124 | ||
125 | using __limits_ull = numeric_limits<unsigned long long>; | |
126 | using __limits_ul = numeric_limits<unsigned long>; | |
127 | using __limits_u = numeric_limits<unsigned>; | |
128 | ||
129 | if _GLIBCXX17_CONSTEXPR (__limits::digits <= __limits_u::digits) | |
130 | return __builtin_ctz(__x); | |
131 | else if _GLIBCXX17_CONSTEXPR (__limits::digits <= __limits_ul::digits) | |
132 | return __builtin_ctzl(__x); | |
133 | else if _GLIBCXX17_CONSTEXPR (__limits::digits <= __limits_ull::digits) | |
134 | return __builtin_ctzll(__x); | |
135 | else // (__limits::digits > __limits_ull::digits) | |
136 | { | |
137 | static_assert(__limits::digits <= (2 * __limits_ull::digits), | |
138 | "Maximum supported integer size is 128-bit"); | |
139 | ||
140 | unsigned long long __low = __x & __limits_ull::max(); | |
141 | if (__low != 0) | |
142 | return __builtin_ctzll(__low); | |
143 | unsigned long long __high = __x >> __limits_ull::digits; | |
144 | return __builtin_ctzll(__high) + __limits_ull::digits; | |
145 | } | |
146 | } | |
147 | ||
148 | template<typename _Tp> | |
149 | constexpr int | |
150 | __countr_one(_Tp __x) noexcept | |
151 | { | |
152 | if (__x == numeric_limits<_Tp>::max()) | |
153 | return numeric_limits<_Tp>::digits; | |
154 | return std::__countr_zero((_Tp)~__x); | |
155 | } | |
156 | ||
157 | template<typename _Tp> | |
158 | constexpr int | |
159 | __popcount(_Tp __x) noexcept | |
160 | { | |
161 | using __limits = numeric_limits<_Tp>; | |
162 | ||
163 | if (__x == 0) | |
164 | return 0; | |
165 | ||
166 | using __limits_ull = numeric_limits<unsigned long long>; | |
167 | using __limits_ul = numeric_limits<unsigned long>; | |
168 | using __limits_u = numeric_limits<unsigned>; | |
169 | ||
170 | if _GLIBCXX17_CONSTEXPR (__limits::digits <= __limits_u::digits) | |
171 | return __builtin_popcount(__x); | |
172 | else if _GLIBCXX17_CONSTEXPR (__limits::digits <= __limits_ul::digits) | |
173 | return __builtin_popcountl(__x); | |
174 | else if _GLIBCXX17_CONSTEXPR (__limits::digits <= __limits_ull::digits) | |
175 | return __builtin_popcountll(__x); | |
176 | else // (__limits::digits > __limits_ull::digits) | |
177 | { | |
178 | static_assert(__limits::digits <= (2 * __limits_ull::digits), | |
179 | "Maximum supported integer size is 128-bit"); | |
180 | ||
181 | unsigned long long __low = __x & __limits_ull::max(); | |
182 | unsigned long long __high = __x >> __limits_ull::digits; | |
183 | return __builtin_popcountll(__low) + __builtin_popcountll(__high); | |
184 | } | |
185 | } | |
186 | ||
187 | template<typename _Tp> | |
188 | constexpr bool | |
189 | __ispow2(_Tp __x) noexcept | |
190 | { return std::__popcount(__x) == 1; } | |
191 | ||
192 | template<typename _Tp> | |
193 | constexpr _Tp | |
194 | __ceil2(_Tp __x) noexcept | |
195 | { | |
196 | constexpr auto _Nd = numeric_limits<_Tp>::digits; | |
197 | if (__x == 0) | |
198 | return 1; | |
199 | return (_Tp)1u << (_Nd - std::__countl_zero((_Tp)(__x - 1u))); | |
200 | } | |
201 | ||
202 | template<typename _Tp> | |
203 | constexpr _Tp | |
204 | __floor2(_Tp __x) noexcept | |
205 | { | |
206 | constexpr auto _Nd = numeric_limits<_Tp>::digits; | |
207 | if (__x == 0) | |
208 | return 0; | |
209 | return (_Tp)1u << (_Nd - std::__countl_zero((_Tp)(__x >> 1))); | |
210 | } | |
211 | ||
212 | template<typename _Tp> | |
213 | constexpr _Tp | |
214 | __log2p1(_Tp __x) noexcept | |
215 | { | |
216 | constexpr auto _Nd = numeric_limits<_Tp>::digits; | |
217 | if (__x == 0) | |
218 | return 0; | |
219 | return _Nd - std::__countl_zero(__x); | |
220 | } | |
221 | ||
222 | #if __cplusplus > 201703L | |
223 | ||
224 | template<typename _Tp, typename _Up, bool = is_integral_v<_Tp>> | |
225 | struct _If_is_unsigned_integer_type { }; | |
226 | ||
227 | template<typename _Up> | |
228 | struct _If_is_unsigned_integer_type<bool, _Up, true> { }; | |
229 | ||
230 | template<typename _Tp, typename _Up> | |
231 | struct _If_is_unsigned_integer_type<_Tp, _Up, true> | |
232 | : enable_if<is_same_v<_Tp, make_unsigned_t<_Tp>>, _Up> { }; | |
233 | ||
234 | template<typename _Tp, typename _Up = _Tp> | |
235 | using _If_is_unsigned_integer | |
90fc44ec | 236 | = typename _If_is_unsigned_integer_type<remove_cv_t<_Tp>, _Up>::type; |
f3e91052 JW |
237 | |
238 | #if ! __STRICT_ANSI__ | |
239 | // [bitops.rot], rotating | |
240 | ||
241 | template<typename _Tp> | |
242 | constexpr _If_is_unsigned_integer<_Tp> | |
243 | rotl(_Tp __x, unsigned int __s) noexcept | |
244 | { return std::__rotl(__x, __s); } | |
245 | ||
246 | template<typename _Tp> | |
247 | constexpr _If_is_unsigned_integer<_Tp> | |
248 | rotr(_Tp __x, unsigned int __s) noexcept | |
249 | { return std::__rotr(__x, __s); } | |
250 | ||
251 | // [bitops.count], counting | |
252 | ||
253 | template<typename _Tp> | |
254 | constexpr _If_is_unsigned_integer<_Tp, int> | |
255 | countl_zero(_Tp __x) noexcept | |
256 | { return std::__countl_zero(__x); } | |
257 | ||
258 | template<typename _Tp> | |
259 | constexpr _If_is_unsigned_integer<_Tp, int> | |
260 | countl_one(_Tp __x) noexcept | |
261 | { return std::__countl_one(__x); } | |
262 | ||
263 | template<typename _Tp> | |
264 | constexpr _If_is_unsigned_integer<_Tp, int> | |
265 | countr_zero(_Tp __x) noexcept | |
266 | { return std::__countr_zero(__x); } | |
267 | ||
268 | template<typename _Tp> | |
269 | constexpr _If_is_unsigned_integer<_Tp, int> | |
270 | countr_one(_Tp __x) noexcept | |
271 | { return std::__countr_one(__x); } | |
272 | ||
273 | template<typename _Tp> | |
274 | constexpr _If_is_unsigned_integer<_Tp, int> | |
275 | popcount(_Tp __x) noexcept | |
276 | { return std::__popcount(__x); } | |
277 | #endif | |
278 | ||
279 | // Integral power-of-two operations | |
280 | ||
281 | template<typename _Tp> | |
282 | constexpr _If_is_unsigned_integer<_Tp, bool> | |
283 | ispow2(_Tp __x) noexcept | |
284 | { return std::__ispow2(__x); } | |
285 | ||
286 | template<typename _Tp> | |
287 | constexpr _If_is_unsigned_integer<_Tp> | |
288 | ceil2(_Tp __x) noexcept | |
289 | { return std::__ceil2(__x); } | |
290 | ||
291 | template<typename _Tp> | |
292 | constexpr _If_is_unsigned_integer<_Tp> | |
293 | floor2(_Tp __x) noexcept | |
294 | { return std::__floor2(__x); } | |
295 | ||
296 | template<typename _Tp> | |
297 | constexpr _If_is_unsigned_integer<_Tp> | |
298 | log2p1(_Tp __x) noexcept | |
299 | { return std::__log2p1(__x); } | |
300 | ||
301 | #if ! __STRICT_ANSI__ | |
302 | enum class byte : unsigned char; | |
303 | ||
304 | constexpr byte | |
305 | rotl(byte __x, unsigned int __s) noexcept | |
306 | { return (byte)std::__rotl((unsigned char)__x, __s); } | |
307 | ||
308 | constexpr byte | |
309 | rotr(byte __x, unsigned int __s) noexcept | |
310 | { return (byte)std::__rotr((unsigned char)__x, __s); } | |
311 | ||
312 | constexpr int | |
313 | countl_zero(byte __x) noexcept | |
314 | { return std::__countl_zero((unsigned char)__x); } | |
315 | ||
316 | constexpr int | |
317 | countl_one(byte __x) noexcept | |
318 | { return std::__countl_one((unsigned char)__x); } | |
319 | ||
320 | constexpr int | |
321 | countr_zero(byte __x) noexcept | |
322 | { return std::__countr_zero((unsigned char)__x); } | |
323 | ||
324 | constexpr int | |
325 | countr_one(byte __x) noexcept | |
326 | { return std::__countr_one((unsigned char)__x); } | |
327 | ||
328 | constexpr int | |
329 | popcount(byte __x) noexcept | |
330 | { return std::__popcount((unsigned char)__x); } | |
331 | ||
332 | constexpr bool | |
333 | ispow2(byte __x) noexcept | |
334 | { return std::__ispow2((unsigned char)__x); } | |
335 | ||
336 | constexpr byte | |
337 | ceil2(byte __x) noexcept | |
338 | { return (byte)std::__ceil2((unsigned char)__x); } | |
339 | ||
340 | constexpr byte | |
341 | floor2(byte __x) noexcept | |
342 | { return (byte)std::__floor2((unsigned char)__x); } | |
343 | ||
344 | constexpr byte | |
345 | log2p1(byte __x) noexcept | |
346 | { return (byte)std::__log2p1((unsigned char)__x); } | |
347 | #endif | |
348 | ||
349 | #endif // C++2a | |
350 | ||
351 | _GLIBCXX_END_NAMESPACE_VERSION | |
352 | } // namespace std | |
353 | ||
354 | #endif // C++14 | |
355 | #endif // _GLIBCXX_BIT |