]>
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; | |
49 | if (__sN) | |
50 | return (__x << __sN) | (__x >> (_Nd - __sN)); | |
51 | return __x; | |
52 | } | |
53 | ||
54 | template<typename _Tp> | |
55 | constexpr _Tp | |
56 | __rotr(_Tp __x, unsigned int __s) noexcept | |
57 | { | |
58 | constexpr auto _Nd = numeric_limits<_Tp>::digits; | |
59 | const unsigned __sN = __s % _Nd; | |
60 | if (__sN) | |
61 | return (__x >> __sN) | (__x << (_Nd - __sN)); | |
62 | return __x; | |
63 | } | |
64 | ||
65 | template<typename _Tp> | |
66 | constexpr int | |
67 | __countl_zero(_Tp __x) noexcept | |
68 | { | |
69 | using __limits = numeric_limits<_Tp>; | |
70 | ||
71 | if (__x == 0) | |
72 | return __limits::digits; | |
73 | ||
74 | using __limits_ull = numeric_limits<unsigned long long>; | |
75 | using __limits_ul = numeric_limits<unsigned long>; | |
76 | using __limits_u = numeric_limits<unsigned>; | |
77 | ||
78 | if _GLIBCXX17_CONSTEXPR (__limits::digits <= __limits_u::digits) | |
79 | { | |
80 | constexpr int __diff = __limits_u::digits - __limits::digits; | |
81 | return __builtin_clz(__x) - __diff; | |
82 | } | |
83 | else if _GLIBCXX17_CONSTEXPR (__limits::digits <= __limits_ul::digits) | |
84 | { | |
85 | constexpr int __diff = __limits_ul::digits - __limits::digits; | |
86 | return __builtin_clzl(__x) - __diff; | |
87 | } | |
88 | else if _GLIBCXX17_CONSTEXPR (__limits::digits <= __limits_ull::digits) | |
89 | { | |
90 | constexpr int __diff = __limits_ull::digits - __limits::digits; | |
91 | return __builtin_clzll(__x) - __diff; | |
92 | } | |
93 | else // (__limits::digits > __limits_ull::digits) | |
94 | { | |
95 | static_assert(__limits::digits <= (2 * __limits_ull::digits), | |
96 | "Maximum supported integer size is 128-bit"); | |
97 | ||
98 | unsigned long long __high = __x >> __limits_ull::digits; | |
99 | if (__high != 0) | |
100 | { | |
101 | constexpr int __diff | |
102 | = (2 * __limits_ull::digits) - __limits::digits; | |
103 | return __builtin_clzll(__high) - __diff; | |
104 | } | |
105 | unsigned long long __low = __x & __limits_ull::max(); | |
106 | return (__limits::digits - __limits_ull::digits) | |
107 | + __builtin_clzll(__low); | |
108 | } | |
109 | } | |
110 | ||
111 | template<typename _Tp> | |
112 | constexpr int | |
113 | __countl_one(_Tp __x) noexcept | |
114 | { | |
115 | if (__x == numeric_limits<_Tp>::max()) | |
116 | return numeric_limits<_Tp>::digits; | |
117 | return std::__countl_zero<_Tp>((_Tp)~__x); | |
118 | } | |
119 | ||
120 | template<typename _Tp> | |
121 | constexpr int | |
122 | __countr_zero(_Tp __x) noexcept | |
123 | { | |
124 | using __limits = numeric_limits<_Tp>; | |
125 | ||
126 | if (__x == 0) | |
127 | return __limits::digits; | |
128 | ||
129 | using __limits_ull = numeric_limits<unsigned long long>; | |
130 | using __limits_ul = numeric_limits<unsigned long>; | |
131 | using __limits_u = numeric_limits<unsigned>; | |
132 | ||
133 | if _GLIBCXX17_CONSTEXPR (__limits::digits <= __limits_u::digits) | |
134 | return __builtin_ctz(__x); | |
135 | else if _GLIBCXX17_CONSTEXPR (__limits::digits <= __limits_ul::digits) | |
136 | return __builtin_ctzl(__x); | |
137 | else if _GLIBCXX17_CONSTEXPR (__limits::digits <= __limits_ull::digits) | |
138 | return __builtin_ctzll(__x); | |
139 | else // (__limits::digits > __limits_ull::digits) | |
140 | { | |
141 | static_assert(__limits::digits <= (2 * __limits_ull::digits), | |
142 | "Maximum supported integer size is 128-bit"); | |
143 | ||
144 | unsigned long long __low = __x & __limits_ull::max(); | |
145 | if (__low != 0) | |
146 | return __builtin_ctzll(__low); | |
147 | unsigned long long __high = __x >> __limits_ull::digits; | |
148 | return __builtin_ctzll(__high) + __limits_ull::digits; | |
149 | } | |
150 | } | |
151 | ||
152 | template<typename _Tp> | |
153 | constexpr int | |
154 | __countr_one(_Tp __x) noexcept | |
155 | { | |
156 | if (__x == numeric_limits<_Tp>::max()) | |
157 | return numeric_limits<_Tp>::digits; | |
158 | return std::__countr_zero((_Tp)~__x); | |
159 | } | |
160 | ||
161 | template<typename _Tp> | |
162 | constexpr int | |
163 | __popcount(_Tp __x) noexcept | |
164 | { | |
165 | using __limits = numeric_limits<_Tp>; | |
166 | ||
167 | if (__x == 0) | |
168 | return 0; | |
169 | ||
170 | using __limits_ull = numeric_limits<unsigned long long>; | |
171 | using __limits_ul = numeric_limits<unsigned long>; | |
172 | using __limits_u = numeric_limits<unsigned>; | |
173 | ||
174 | if _GLIBCXX17_CONSTEXPR (__limits::digits <= __limits_u::digits) | |
175 | return __builtin_popcount(__x); | |
176 | else if _GLIBCXX17_CONSTEXPR (__limits::digits <= __limits_ul::digits) | |
177 | return __builtin_popcountl(__x); | |
178 | else if _GLIBCXX17_CONSTEXPR (__limits::digits <= __limits_ull::digits) | |
179 | return __builtin_popcountll(__x); | |
180 | else // (__limits::digits > __limits_ull::digits) | |
181 | { | |
182 | static_assert(__limits::digits <= (2 * __limits_ull::digits), | |
183 | "Maximum supported integer size is 128-bit"); | |
184 | ||
185 | unsigned long long __low = __x & __limits_ull::max(); | |
186 | unsigned long long __high = __x >> __limits_ull::digits; | |
187 | return __builtin_popcountll(__low) + __builtin_popcountll(__high); | |
188 | } | |
189 | } | |
190 | ||
191 | template<typename _Tp> | |
192 | constexpr bool | |
193 | __ispow2(_Tp __x) noexcept | |
194 | { return std::__popcount(__x) == 1; } | |
195 | ||
196 | template<typename _Tp> | |
197 | constexpr _Tp | |
198 | __ceil2(_Tp __x) noexcept | |
199 | { | |
200 | constexpr auto _Nd = numeric_limits<_Tp>::digits; | |
201 | if (__x == 0) | |
202 | return 1; | |
203 | return (_Tp)1u << (_Nd - std::__countl_zero((_Tp)(__x - 1u))); | |
204 | } | |
205 | ||
206 | template<typename _Tp> | |
207 | constexpr _Tp | |
208 | __floor2(_Tp __x) noexcept | |
209 | { | |
210 | constexpr auto _Nd = numeric_limits<_Tp>::digits; | |
211 | if (__x == 0) | |
212 | return 0; | |
213 | return (_Tp)1u << (_Nd - std::__countl_zero((_Tp)(__x >> 1))); | |
214 | } | |
215 | ||
216 | template<typename _Tp> | |
217 | constexpr _Tp | |
218 | __log2p1(_Tp __x) noexcept | |
219 | { | |
220 | constexpr auto _Nd = numeric_limits<_Tp>::digits; | |
221 | if (__x == 0) | |
222 | return 0; | |
223 | return _Nd - std::__countl_zero(__x); | |
224 | } | |
225 | ||
226 | #if __cplusplus > 201703L | |
227 | ||
228 | template<typename _Tp, typename _Up, bool = is_integral_v<_Tp>> | |
229 | struct _If_is_unsigned_integer_type { }; | |
230 | ||
231 | template<typename _Up> | |
232 | struct _If_is_unsigned_integer_type<bool, _Up, true> { }; | |
233 | ||
234 | template<typename _Tp, typename _Up> | |
235 | struct _If_is_unsigned_integer_type<_Tp, _Up, true> | |
236 | : enable_if<is_same_v<_Tp, make_unsigned_t<_Tp>>, _Up> { }; | |
237 | ||
238 | template<typename _Tp, typename _Up = _Tp> | |
239 | using _If_is_unsigned_integer | |
240 | = typename _If_is_unsigned_integer_type<_Tp, _Up>::type; | |
241 | ||
242 | #if ! __STRICT_ANSI__ | |
243 | // [bitops.rot], rotating | |
244 | ||
245 | template<typename _Tp> | |
246 | constexpr _If_is_unsigned_integer<_Tp> | |
247 | rotl(_Tp __x, unsigned int __s) noexcept | |
248 | { return std::__rotl(__x, __s); } | |
249 | ||
250 | template<typename _Tp> | |
251 | constexpr _If_is_unsigned_integer<_Tp> | |
252 | rotr(_Tp __x, unsigned int __s) noexcept | |
253 | { return std::__rotr(__x, __s); } | |
254 | ||
255 | // [bitops.count], counting | |
256 | ||
257 | template<typename _Tp> | |
258 | constexpr _If_is_unsigned_integer<_Tp, int> | |
259 | countl_zero(_Tp __x) noexcept | |
260 | { return std::__countl_zero(__x); } | |
261 | ||
262 | template<typename _Tp> | |
263 | constexpr _If_is_unsigned_integer<_Tp, int> | |
264 | countl_one(_Tp __x) noexcept | |
265 | { return std::__countl_one(__x); } | |
266 | ||
267 | template<typename _Tp> | |
268 | constexpr _If_is_unsigned_integer<_Tp, int> | |
269 | countr_zero(_Tp __x) noexcept | |
270 | { return std::__countr_zero(__x); } | |
271 | ||
272 | template<typename _Tp> | |
273 | constexpr _If_is_unsigned_integer<_Tp, int> | |
274 | countr_one(_Tp __x) noexcept | |
275 | { return std::__countr_one(__x); } | |
276 | ||
277 | template<typename _Tp> | |
278 | constexpr _If_is_unsigned_integer<_Tp, int> | |
279 | popcount(_Tp __x) noexcept | |
280 | { return std::__popcount(__x); } | |
281 | #endif | |
282 | ||
283 | // Integral power-of-two operations | |
284 | ||
285 | template<typename _Tp> | |
286 | constexpr _If_is_unsigned_integer<_Tp, bool> | |
287 | ispow2(_Tp __x) noexcept | |
288 | { return std::__ispow2(__x); } | |
289 | ||
290 | template<typename _Tp> | |
291 | constexpr _If_is_unsigned_integer<_Tp> | |
292 | ceil2(_Tp __x) noexcept | |
293 | { return std::__ceil2(__x); } | |
294 | ||
295 | template<typename _Tp> | |
296 | constexpr _If_is_unsigned_integer<_Tp> | |
297 | floor2(_Tp __x) noexcept | |
298 | { return std::__floor2(__x); } | |
299 | ||
300 | template<typename _Tp> | |
301 | constexpr _If_is_unsigned_integer<_Tp> | |
302 | log2p1(_Tp __x) noexcept | |
303 | { return std::__log2p1(__x); } | |
304 | ||
305 | #if ! __STRICT_ANSI__ | |
306 | enum class byte : unsigned char; | |
307 | ||
308 | constexpr byte | |
309 | rotl(byte __x, unsigned int __s) noexcept | |
310 | { return (byte)std::__rotl((unsigned char)__x, __s); } | |
311 | ||
312 | constexpr byte | |
313 | rotr(byte __x, unsigned int __s) noexcept | |
314 | { return (byte)std::__rotr((unsigned char)__x, __s); } | |
315 | ||
316 | constexpr int | |
317 | countl_zero(byte __x) noexcept | |
318 | { return std::__countl_zero((unsigned char)__x); } | |
319 | ||
320 | constexpr int | |
321 | countl_one(byte __x) noexcept | |
322 | { return std::__countl_one((unsigned char)__x); } | |
323 | ||
324 | constexpr int | |
325 | countr_zero(byte __x) noexcept | |
326 | { return std::__countr_zero((unsigned char)__x); } | |
327 | ||
328 | constexpr int | |
329 | countr_one(byte __x) noexcept | |
330 | { return std::__countr_one((unsigned char)__x); } | |
331 | ||
332 | constexpr int | |
333 | popcount(byte __x) noexcept | |
334 | { return std::__popcount((unsigned char)__x); } | |
335 | ||
336 | constexpr bool | |
337 | ispow2(byte __x) noexcept | |
338 | { return std::__ispow2((unsigned char)__x); } | |
339 | ||
340 | constexpr byte | |
341 | ceil2(byte __x) noexcept | |
342 | { return (byte)std::__ceil2((unsigned char)__x); } | |
343 | ||
344 | constexpr byte | |
345 | floor2(byte __x) noexcept | |
346 | { return (byte)std::__floor2((unsigned char)__x); } | |
347 | ||
348 | constexpr byte | |
349 | log2p1(byte __x) noexcept | |
350 | { return (byte)std::__log2p1((unsigned char)__x); } | |
351 | #endif | |
352 | ||
353 | #endif // C++2a | |
354 | ||
355 | _GLIBCXX_END_NAMESPACE_VERSION | |
356 | } // namespace std | |
357 | ||
358 | #endif // C++14 | |
359 | #endif // _GLIBCXX_BIT |