xref: /freebsd/contrib/llvm-project/libcxx/include/bit (revision cfd6422a5217410fbd66f7a7a8a64d9d85e61229) 
1// -*- C++ -*-
2//===------------------------------ bit ----------------------------------===//
3//
4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5// See https://llvm.org/LICENSE.txt for license information.
6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7//
8//===---------------------------------------------------------------------===//
9
10#ifndef _LIBCPP_BIT
11#define _LIBCPP_BIT
12
13/*
14    bit synopsis
15
16namespace std {
17
18  // [bit.pow.two], integral powers of 2
19  template <class T>
20    constexpr bool ispow2(T x) noexcept; // C++20
21  template <class T>
22    constexpr T ceil2(T x);              // C++20
23  template <class T>
24    constexpr T floor2(T x) noexcept;    // C++20
25  template <class T>
26    constexpr T log2p1(T x) noexcept;    // C++20
27
28  // [bit.rotate], rotating
29  template<class T>
30    constexpr T rotl(T x, unsigned int s) noexcept; // C++20
31  template<class T>
32    constexpr T rotr(T x, unsigned int s) noexcept; // C++20
33
34  // [bit.count], counting
35  template<class T>
36    constexpr int countl_zero(T x) noexcept;  // C++20
37  template<class T>
38    constexpr int countl_one(T x) noexcept;   // C++20
39  template<class T>
40    constexpr int countr_zero(T x) noexcept;  // C++20
41  template<class T>
42    constexpr int countr_one(T x) noexcept;   // C++20
43  template<class T>
44    constexpr int popcount(T x) noexcept;     // C++20
45
46  // [bit.endian], endian
47  enum class endian {
48    little = see below,        // C++20
49    big = see below,           // C++20
50    native = see below         // C++20
51};
52
53} // namespace std
54
55*/
56
57#include <__config>
58#include <limits>
59#include <type_traits>
60#include <version>
61#include <__debug>
62
63#if defined(__IBMCPP__)
64#include "support/ibm/support.h"
65#endif
66#if defined(_LIBCPP_COMPILER_MSVC)
67#include <intrin.h>
68#endif
69
70#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
71#pragma GCC system_header
72#endif
73
74_LIBCPP_PUSH_MACROS
75#include <__undef_macros>
76
77_LIBCPP_BEGIN_NAMESPACE_STD
78
79#ifndef _LIBCPP_COMPILER_MSVC
80
81inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
82int __libcpp_ctz(unsigned __x)           _NOEXCEPT { return __builtin_ctz(__x); }
83
84inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
85int __libcpp_ctz(unsigned long __x)      _NOEXCEPT { return __builtin_ctzl(__x); }
86
87inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
88int __libcpp_ctz(unsigned long long __x) _NOEXCEPT { return __builtin_ctzll(__x); }
89
90
91inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
92int __libcpp_clz(unsigned __x)           _NOEXCEPT { return __builtin_clz(__x); }
93
94inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
95int __libcpp_clz(unsigned long __x)      _NOEXCEPT { return __builtin_clzl(__x); }
96
97inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
98int __libcpp_clz(unsigned long long __x) _NOEXCEPT { return __builtin_clzll(__x); }
99
100
101inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
102int __libcpp_popcount(unsigned __x)           _NOEXCEPT { return __builtin_popcount(__x); }
103
104inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
105int __libcpp_popcount(unsigned long __x)      _NOEXCEPT { return __builtin_popcountl(__x); }
106
107inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
108int __libcpp_popcount(unsigned long long __x) _NOEXCEPT { return __builtin_popcountll(__x); }
109
110#else  // _LIBCPP_COMPILER_MSVC
111
112// Precondition:  __x != 0
113inline _LIBCPP_INLINE_VISIBILITY
114int __libcpp_ctz(unsigned __x) {
115  static_assert(sizeof(unsigned) == sizeof(unsigned long), "");
116  static_assert(sizeof(unsigned long) == 4, "");
117  unsigned long __where;
118  if (_BitScanForward(&__where, __x))
119    return static_cast<int>(__where);
120  return 32;
121}
122
123inline _LIBCPP_INLINE_VISIBILITY
124int __libcpp_ctz(unsigned long __x) {
125    static_assert(sizeof(unsigned long) == sizeof(unsigned), "");
126    return __ctz(static_cast<unsigned>(__x));
127}
128
129inline _LIBCPP_INLINE_VISIBILITY
130int __libcpp_ctz(unsigned long long __x) {
131    unsigned long __where;
132#if defined(_LIBCPP_HAS_BITSCAN64)
133    (defined(_M_AMD64) || defined(__x86_64__))
134  if (_BitScanForward64(&__where, __x))
135    return static_cast<int>(__where);
136#else
137  // Win32 doesn't have _BitScanForward64 so emulate it with two 32 bit calls.
138  if (_BitScanForward(&__where, static_cast<unsigned long>(__x)))
139    return static_cast<int>(__where);
140  if (_BitScanForward(&__where, static_cast<unsigned long>(__x >> 32)))
141    return static_cast<int>(__where + 32);
142#endif
143  return 64;
144}
145
146// Precondition:  __x != 0
147inline _LIBCPP_INLINE_VISIBILITY
148int __libcpp_clz(unsigned __x) {
149  static_assert(sizeof(unsigned) == sizeof(unsigned long), "");
150  static_assert(sizeof(unsigned long) == 4, "");
151  unsigned long __where;
152  if (_BitScanReverse(&__where, __x))
153    return static_cast<int>(31 - __where);
154  return 32; // Undefined Behavior.
155}
156
157inline _LIBCPP_INLINE_VISIBILITY
158int __libcpp_clz(unsigned long __x) {
159    static_assert(sizeof(unsigned) == sizeof(unsigned long), "");
160    return __libcpp_clz(static_cast<unsigned>(__x));
161}
162
163inline _LIBCPP_INLINE_VISIBILITY
164int __libcpp_clz(unsigned long long __x) {
165  unsigned long __where;
166#if defined(_LIBCPP_HAS_BITSCAN64)
167  if (_BitScanReverse64(&__where, __x))
168    return static_cast<int>(63 - __where);
169#else
170  // Win32 doesn't have _BitScanReverse64 so emulate it with two 32 bit calls.
171  if (_BitScanReverse(&__where, static_cast<unsigned long>(__x >> 32)))
172    return static_cast<int>(63 - (__where + 32));
173  if (_BitScanReverse(&__where, static_cast<unsigned long>(__x)))
174    return static_cast<int>(63 - __where);
175#endif
176  return 64; // Undefined Behavior.
177}
178
179inline _LIBCPP_INLINE_VISIBILITY int __libcpp_popcount(unsigned __x) {
180  static_assert(sizeof(unsigned) == 4, "");
181  return __popcnt(__x);
182}
183
184inline _LIBCPP_INLINE_VISIBILITY int __libcpp_popcount(unsigned long __x) {
185  static_assert(sizeof(unsigned long) == 4, "");
186  return __popcnt(__x);
187}
188
189inline _LIBCPP_INLINE_VISIBILITY int __libcpp_popcount(unsigned long long __x) {
190  static_assert(sizeof(unsigned long long) == 8, "");
191  return __popcnt64(__x);
192}
193
194#endif // _LIBCPP_COMPILER_MSVC
195
196template <class _Tp>
197using __bitop_unsigned_integer _LIBCPP_NODEBUG_TYPE = integral_constant<bool,
198         is_integral<_Tp>::value &&
199         is_unsigned<_Tp>::value &&
200        _IsNotSame<typename remove_cv<_Tp>::type, bool>::value &&
201        _IsNotSame<typename remove_cv<_Tp>::type, signed char>::value &&
202        _IsNotSame<typename remove_cv<_Tp>::type, wchar_t>::value &&
203        _IsNotSame<typename remove_cv<_Tp>::type, char16_t>::value &&
204        _IsNotSame<typename remove_cv<_Tp>::type, char32_t>::value
205    >;
206
207
208template<class _Tp>
209_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
210_Tp __rotl(_Tp __t, unsigned int __cnt) _NOEXCEPT
211{
212    static_assert(__bitop_unsigned_integer<_Tp>::value, "__rotl requires unsigned");
213    const unsigned int __dig = numeric_limits<_Tp>::digits;
214    if ((__cnt % __dig) == 0)
215        return __t;
216    return (__t << (__cnt % __dig)) | (__t >> (__dig - (__cnt % __dig)));
217}
218
219
220template<class _Tp>
221_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
222_Tp __rotr(_Tp __t, unsigned int __cnt) _NOEXCEPT
223{
224    static_assert(__bitop_unsigned_integer<_Tp>::value, "__rotr requires unsigned");
225    const unsigned int __dig = numeric_limits<_Tp>::digits;
226    if ((__cnt % __dig) == 0)
227        return __t;
228    return (__t >> (__cnt % __dig)) | (__t << (__dig - (__cnt % __dig)));
229}
230
231
232
233template<class _Tp>
234_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
235int __countr_zero(_Tp __t) _NOEXCEPT
236{
237    static_assert(__bitop_unsigned_integer<_Tp>::value, "__countr_zero requires unsigned");
238    if (__t == 0)
239        return numeric_limits<_Tp>::digits;
240
241    if      (sizeof(_Tp) <= sizeof(unsigned int))
242        return __libcpp_ctz(static_cast<unsigned int>(__t));
243    else if (sizeof(_Tp) <= sizeof(unsigned long))
244        return __libcpp_ctz(static_cast<unsigned long>(__t));
245    else if (sizeof(_Tp) <= sizeof(unsigned long long))
246        return __libcpp_ctz(static_cast<unsigned long long>(__t));
247    else
248    {
249        int __ret = 0;
250        int __iter = 0;
251        const unsigned int __ulldigits = numeric_limits<unsigned long long>::digits;
252        while ((__iter = __libcpp_ctz(static_cast<unsigned long long>(__t))) == __ulldigits)
253        {
254            __ret += __iter;
255            __t >>= __ulldigits;
256        }
257        return __ret + __iter;
258    }
259}
260
261template<class _Tp>
262_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
263int __countl_zero(_Tp __t) _NOEXCEPT
264{
265    static_assert(__bitop_unsigned_integer<_Tp>::value, "__countl_zero requires unsigned");
266    if (__t == 0)
267        return numeric_limits<_Tp>::digits;
268
269    if      (sizeof(_Tp) <= sizeof(unsigned int))
270        return __libcpp_clz(static_cast<unsigned int>(__t))
271              - (numeric_limits<unsigned int>::digits - numeric_limits<_Tp>::digits);
272    else if (sizeof(_Tp) <= sizeof(unsigned long))
273        return __libcpp_clz(static_cast<unsigned long>(__t))
274              - (numeric_limits<unsigned long>::digits - numeric_limits<_Tp>::digits);
275    else if (sizeof(_Tp) <= sizeof(unsigned long long))
276        return __libcpp_clz(static_cast<unsigned long long>(__t))
277              - (numeric_limits<unsigned long long>::digits - numeric_limits<_Tp>::digits);
278    else
279    {
280        int __ret = 0;
281        int __iter = 0;
282        const unsigned int __ulldigits = numeric_limits<unsigned long long>::digits;
283        while (true) {
284            __t = __rotr(__t, __ulldigits);
285            if ((__iter = __countl_zero(static_cast<unsigned long long>(__t))) != __ulldigits)
286                break;
287            __ret += __iter;
288            }
289        return __ret + __iter;
290    }
291}
292
293template<class _Tp>
294_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
295int __countl_one(_Tp __t) _NOEXCEPT
296{
297    static_assert(__bitop_unsigned_integer<_Tp>::value, "__countl_one requires unsigned");
298    return __t != numeric_limits<_Tp>::max()
299        ? __countl_zero(static_cast<_Tp>(~__t))
300        : numeric_limits<_Tp>::digits;
301}
302
303
304template<class _Tp>
305_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
306int __countr_one(_Tp __t) _NOEXCEPT
307{
308    static_assert(__bitop_unsigned_integer<_Tp>::value, "__countr_one requires unsigned");
309    return __t != numeric_limits<_Tp>::max()
310        ? __countr_zero(static_cast<_Tp>(~__t))
311        : numeric_limits<_Tp>::digits;
312}
313
314
315template<class _Tp>
316_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
317int
318__popcount(_Tp __t) _NOEXCEPT
319{
320    static_assert(__bitop_unsigned_integer<_Tp>::value, "__libcpp_popcount requires unsigned");
321    if      (sizeof(_Tp) <= sizeof(unsigned int))
322        return __libcpp_popcount(static_cast<unsigned int>(__t));
323    else if (sizeof(_Tp) <= sizeof(unsigned long))
324        return __libcpp_popcount(static_cast<unsigned long>(__t));
325    else if (sizeof(_Tp) <= sizeof(unsigned long long))
326        return __libcpp_popcount(static_cast<unsigned long long>(__t));
327    else
328    {
329        int __ret = 0;
330        while (__t != 0)
331        {
332            __ret += __libcpp_popcount(static_cast<unsigned long long>(__t));
333            __t >>= numeric_limits<unsigned long long>::digits;
334        }
335        return __ret;
336    }
337}
338
339
340// integral log base 2
341template<class _Tp>
342_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
343unsigned __bit_log2(_Tp __t) _NOEXCEPT
344{
345    static_assert(__bitop_unsigned_integer<_Tp>::value, "__bit_log2 requires unsigned");
346    return std::numeric_limits<_Tp>::digits - 1 - __countl_zero(__t);
347}
348
349template <class _Tp>
350_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
351bool __ispow2(_Tp __t) _NOEXCEPT
352{
353    static_assert(__bitop_unsigned_integer<_Tp>::value, "__ispow2 requires unsigned");
354    return __t != 0 && (((__t & (__t - 1)) == 0));
355}
356
357
358#if _LIBCPP_STD_VER > 17
359
360template<class _Tp>
361_LIBCPP_INLINE_VISIBILITY constexpr
362enable_if_t<__bitop_unsigned_integer<_Tp>::value, _Tp>
363rotl(_Tp __t, unsigned int __cnt) noexcept
364{
365    return __rotl(__t, __cnt);
366}
367
368
369// rotr
370template<class _Tp>
371_LIBCPP_INLINE_VISIBILITY constexpr
372enable_if_t<__bitop_unsigned_integer<_Tp>::value, _Tp>
373rotr(_Tp __t, unsigned int __cnt) noexcept
374{
375    return __rotr(__t, __cnt);
376}
377
378
379template<class _Tp>
380_LIBCPP_INLINE_VISIBILITY constexpr
381enable_if_t<__bitop_unsigned_integer<_Tp>::value, int>
382countl_zero(_Tp __t) noexcept
383{
384    return __countl_zero(__t);
385}
386
387
388template<class _Tp>
389_LIBCPP_INLINE_VISIBILITY constexpr
390enable_if_t<__bitop_unsigned_integer<_Tp>::value, int>
391countl_one(_Tp __t) noexcept
392{
393    return __countl_one(__t);
394}
395
396
397template<class _Tp>
398_LIBCPP_INLINE_VISIBILITY constexpr
399enable_if_t<__bitop_unsigned_integer<_Tp>::value, int>
400countr_zero(_Tp __t) noexcept
401{
402	return __countr_zero(__t);
403}
404
405
406template<class _Tp>
407_LIBCPP_INLINE_VISIBILITY constexpr
408enable_if_t<__bitop_unsigned_integer<_Tp>::value, int>
409countr_one(_Tp __t) noexcept
410{
411    return __countr_one(__t);
412}
413
414
415template<class _Tp>
416_LIBCPP_INLINE_VISIBILITY constexpr
417enable_if_t<__bitop_unsigned_integer<_Tp>::value, int>
418popcount(_Tp __t) noexcept
419{
420    return __popcount(__t);
421}
422
423
424template <class _Tp>
425_LIBCPP_INLINE_VISIBILITY constexpr
426enable_if_t<__bitop_unsigned_integer<_Tp>::value, bool>
427ispow2(_Tp __t) noexcept
428{
429    return __ispow2(__t);
430}
431
432template <class _Tp>
433_LIBCPP_INLINE_VISIBILITY constexpr
434enable_if_t<__bitop_unsigned_integer<_Tp>::value, _Tp>
435floor2(_Tp __t) noexcept
436{
437    return __t == 0 ? 0 : _Tp{1} << __bit_log2(__t);
438}
439
440template <class _Tp>
441_LIBCPP_INLINE_VISIBILITY constexpr
442enable_if_t<__bitop_unsigned_integer<_Tp>::value, _Tp>
443ceil2(_Tp __t) noexcept
444{
445    if (__t < 2) return 1;
446    const unsigned __n = numeric_limits<_Tp>::digits - countl_zero((_Tp)(__t - 1u));
447    _LIBCPP_DEBUG_ASSERT(__libcpp_is_constant_evaluated() || __n != numeric_limits<_Tp>::digits, "Bad input to ceil2");
448
449    if constexpr (sizeof(_Tp) >= sizeof(unsigned))
450        return _Tp{1} << __n;
451    else
452    {
453        const unsigned __extra = numeric_limits<unsigned>::digits  - numeric_limits<_Tp>::digits;
454        const unsigned __retVal = 1u << (__n + __extra);
455        return (_Tp) (__retVal >> __extra);
456    }
457}
458
459template <class _Tp>
460_LIBCPP_INLINE_VISIBILITY constexpr
461enable_if_t<__bitop_unsigned_integer<_Tp>::value, _Tp>
462log2p1(_Tp __t) noexcept
463{
464    return __t == 0 ? 0 : __bit_log2(__t) + 1;
465}
466
467
468enum class endian
469{
470    little = 0xDEAD,
471    big    = 0xFACE,
472#if defined(_LIBCPP_LITTLE_ENDIAN)
473    native = little
474#elif defined(_LIBCPP_BIG_ENDIAN)
475    native = big
476#else
477    native = 0xCAFE
478#endif
479};
480
481#endif // _LIBCPP_STD_VER > 17
482
483_LIBCPP_END_NAMESPACE_STD
484
485_LIBCPP_POP_MACROS
486
487#endif // _LIBCPP_BIT
488