]> git.ipfire.org Git - thirdparty/gcc.git/blame - libstdc++-v3/include/std/bit
P0556R3 Integral power-of-2 operations, P0553R2 Bit operations
[thirdparty/gcc.git] / libstdc++-v3 / include / std / bit
CommitLineData
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
39namespace 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