xref: /freebsd/contrib/llvm-project/libcxx/include/bit (revision 43a5ec4eb41567cc92586503212743d89686d78f) 
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 has_single_bit(T x) noexcept; // C++20
21  template <class T>
22    constexpr T bit_ceil(T x);                   // C++20
23  template <class T>
24    constexpr T bit_floor(T x) noexcept;         // C++20
25  template <class T>
26    constexpr T bit_width(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 <__bits> // __libcpp_clz
59#include <__debug>
60#include <limits>
61#include <type_traits>
62#include <version>
63
64#if defined(__IBMCPP__)
65#include "__support/ibm/support.h"
66#endif
67#if defined(_LIBCPP_COMPILER_MSVC)
68#include <intrin.h>
69#endif
70
71#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
72#pragma GCC system_header
73#endif
74
75_LIBCPP_PUSH_MACROS
76#include <__undef_macros>
77
78_LIBCPP_BEGIN_NAMESPACE_STD
79
80template<class _Tp>
81_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
82_Tp __rotl(_Tp __t, unsigned int __cnt) _NOEXCEPT
83{
84    static_assert(__libcpp_is_unsigned_integer<_Tp>::value, "__rotl requires an unsigned integer type");
85    const unsigned int __dig = numeric_limits<_Tp>::digits;
86    if ((__cnt % __dig) == 0)
87        return __t;
88    return (__t << (__cnt % __dig)) | (__t >> (__dig - (__cnt % __dig)));
89}
90
91template<class _Tp>
92_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
93_Tp __rotr(_Tp __t, unsigned int __cnt) _NOEXCEPT
94{
95    static_assert(__libcpp_is_unsigned_integer<_Tp>::value, "__rotr requires an unsigned integer type");
96    const unsigned int __dig = numeric_limits<_Tp>::digits;
97    if ((__cnt % __dig) == 0)
98        return __t;
99    return (__t >> (__cnt % __dig)) | (__t << (__dig - (__cnt % __dig)));
100}
101
102template<class _Tp>
103_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
104int __countr_zero(_Tp __t) _NOEXCEPT
105{
106    static_assert(__libcpp_is_unsigned_integer<_Tp>::value, "__countr_zero requires an unsigned integer type");
107    if (__t == 0)
108        return numeric_limits<_Tp>::digits;
109
110    if      (sizeof(_Tp) <= sizeof(unsigned int))
111        return __libcpp_ctz(static_cast<unsigned int>(__t));
112    else if (sizeof(_Tp) <= sizeof(unsigned long))
113        return __libcpp_ctz(static_cast<unsigned long>(__t));
114    else if (sizeof(_Tp) <= sizeof(unsigned long long))
115        return __libcpp_ctz(static_cast<unsigned long long>(__t));
116    else
117    {
118        int __ret = 0;
119        const unsigned int __ulldigits = numeric_limits<unsigned long long>::digits;
120        while (static_cast<unsigned long long>(__t) == 0uLL)
121        {
122            __ret += __ulldigits;
123            __t >>= __ulldigits;
124        }
125        return __ret + __libcpp_ctz(static_cast<unsigned long long>(__t));
126    }
127}
128
129template<class _Tp>
130_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
131int __countl_zero(_Tp __t) _NOEXCEPT
132{
133    static_assert(__libcpp_is_unsigned_integer<_Tp>::value, "__countl_zero requires an unsigned integer type");
134    if (__t == 0)
135        return numeric_limits<_Tp>::digits;
136
137    if      (sizeof(_Tp) <= sizeof(unsigned int))
138        return __libcpp_clz(static_cast<unsigned int>(__t))
139              - (numeric_limits<unsigned int>::digits - numeric_limits<_Tp>::digits);
140    else if (sizeof(_Tp) <= sizeof(unsigned long))
141        return __libcpp_clz(static_cast<unsigned long>(__t))
142              - (numeric_limits<unsigned long>::digits - numeric_limits<_Tp>::digits);
143    else if (sizeof(_Tp) <= sizeof(unsigned long long))
144        return __libcpp_clz(static_cast<unsigned long long>(__t))
145              - (numeric_limits<unsigned long long>::digits - numeric_limits<_Tp>::digits);
146    else
147    {
148        int __ret = 0;
149        int __iter = 0;
150        const unsigned int __ulldigits = numeric_limits<unsigned long long>::digits;
151        while (true) {
152            __t = __rotr(__t, __ulldigits);
153            if ((__iter = __countl_zero(static_cast<unsigned long long>(__t))) != __ulldigits)
154                break;
155            __ret += __iter;
156            }
157        return __ret + __iter;
158    }
159}
160
161template<class _Tp>
162_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
163int __countl_one(_Tp __t) _NOEXCEPT
164{
165    static_assert(__libcpp_is_unsigned_integer<_Tp>::value, "__countl_one requires an unsigned integer type");
166    return __t != numeric_limits<_Tp>::max()
167        ? __countl_zero(static_cast<_Tp>(~__t))
168        : numeric_limits<_Tp>::digits;
169}
170
171template<class _Tp>
172_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
173int __countr_one(_Tp __t) _NOEXCEPT
174{
175    static_assert(__libcpp_is_unsigned_integer<_Tp>::value, "__countr_one requires an unsigned integer type");
176    return __t != numeric_limits<_Tp>::max()
177        ? __countr_zero(static_cast<_Tp>(~__t))
178        : numeric_limits<_Tp>::digits;
179}
180
181template<class _Tp>
182_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
183int __popcount(_Tp __t) _NOEXCEPT
184{
185    static_assert(__libcpp_is_unsigned_integer<_Tp>::value, "__popcount requires an unsigned integer type");
186    if      (sizeof(_Tp) <= sizeof(unsigned int))
187        return __libcpp_popcount(static_cast<unsigned int>(__t));
188    else if (sizeof(_Tp) <= sizeof(unsigned long))
189        return __libcpp_popcount(static_cast<unsigned long>(__t));
190    else if (sizeof(_Tp) <= sizeof(unsigned long long))
191        return __libcpp_popcount(static_cast<unsigned long long>(__t));
192    else
193    {
194        int __ret = 0;
195        while (__t != 0)
196        {
197            __ret += __libcpp_popcount(static_cast<unsigned long long>(__t));
198            __t >>= numeric_limits<unsigned long long>::digits;
199        }
200        return __ret;
201    }
202}
203
204// integral log base 2
205template<class _Tp>
206_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
207unsigned __bit_log2(_Tp __t) _NOEXCEPT
208{
209    static_assert(__libcpp_is_unsigned_integer<_Tp>::value, "__bit_log2 requires an unsigned integer type");
210    return numeric_limits<_Tp>::digits - 1 - __countl_zero(__t);
211}
212
213template <class _Tp>
214_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
215bool __has_single_bit(_Tp __t) _NOEXCEPT
216{
217    static_assert(__libcpp_is_unsigned_integer<_Tp>::value, "__has_single_bit requires an unsigned integer type");
218    return __t != 0 && (((__t & (__t - 1)) == 0));
219}
220
221#if _LIBCPP_STD_VER > 17
222
223template<class _Tp>
224_LIBCPP_INLINE_VISIBILITY constexpr
225_EnableIf<__libcpp_is_unsigned_integer<_Tp>::value, _Tp>
226rotl(_Tp __t, unsigned int __cnt) noexcept
227{
228    return __rotl(__t, __cnt);
229}
230
231template<class _Tp>
232_LIBCPP_INLINE_VISIBILITY constexpr
233_EnableIf<__libcpp_is_unsigned_integer<_Tp>::value, _Tp>
234rotr(_Tp __t, unsigned int __cnt) noexcept
235{
236    return __rotr(__t, __cnt);
237}
238
239template<class _Tp>
240_LIBCPP_INLINE_VISIBILITY constexpr
241_EnableIf<__libcpp_is_unsigned_integer<_Tp>::value, int>
242countl_zero(_Tp __t) noexcept
243{
244    return __countl_zero(__t);
245}
246
247template<class _Tp>
248_LIBCPP_INLINE_VISIBILITY constexpr
249_EnableIf<__libcpp_is_unsigned_integer<_Tp>::value, int>
250countl_one(_Tp __t) noexcept
251{
252    return __countl_one(__t);
253}
254
255template<class _Tp>
256_LIBCPP_INLINE_VISIBILITY constexpr
257_EnableIf<__libcpp_is_unsigned_integer<_Tp>::value, int>
258countr_zero(_Tp __t) noexcept
259{
260    return __countr_zero(__t);
261}
262
263template<class _Tp>
264_LIBCPP_INLINE_VISIBILITY constexpr
265_EnableIf<__libcpp_is_unsigned_integer<_Tp>::value, int>
266countr_one(_Tp __t) noexcept
267{
268    return __countr_one(__t);
269}
270
271template<class _Tp>
272_LIBCPP_INLINE_VISIBILITY constexpr
273_EnableIf<__libcpp_is_unsigned_integer<_Tp>::value, int>
274popcount(_Tp __t) noexcept
275{
276    return __popcount(__t);
277}
278
279template <class _Tp>
280_LIBCPP_INLINE_VISIBILITY constexpr
281_EnableIf<__libcpp_is_unsigned_integer<_Tp>::value, bool>
282has_single_bit(_Tp __t) noexcept
283{
284    return __has_single_bit(__t);
285}
286
287template <class _Tp>
288_LIBCPP_INLINE_VISIBILITY constexpr
289_EnableIf<__libcpp_is_unsigned_integer<_Tp>::value, _Tp>
290bit_floor(_Tp __t) noexcept
291{
292    return __t == 0 ? 0 : _Tp{1} << __bit_log2(__t);
293}
294
295template <class _Tp>
296_LIBCPP_INLINE_VISIBILITY constexpr
297_EnableIf<__libcpp_is_unsigned_integer<_Tp>::value, _Tp>
298bit_ceil(_Tp __t) noexcept
299{
300    if (__t < 2) return 1;
301    const unsigned __n = numeric_limits<_Tp>::digits - countl_zero((_Tp)(__t - 1u));
302    _LIBCPP_DEBUG_ASSERT(__libcpp_is_constant_evaluated() || __n != numeric_limits<_Tp>::digits, "Bad input to bit_ceil");
303
304    if constexpr (sizeof(_Tp) >= sizeof(unsigned))
305        return _Tp{1} << __n;
306    else
307    {
308        const unsigned __extra = numeric_limits<unsigned>::digits  - numeric_limits<_Tp>::digits;
309        const unsigned __retVal = 1u << (__n + __extra);
310        return (_Tp) (__retVal >> __extra);
311    }
312}
313
314template <class _Tp>
315_LIBCPP_INLINE_VISIBILITY constexpr
316_EnableIf<__libcpp_is_unsigned_integer<_Tp>::value, _Tp>
317bit_width(_Tp __t) noexcept
318{
319    return __t == 0 ? 0 : __bit_log2(__t) + 1;
320}
321
322enum class endian
323{
324    little = 0xDEAD,
325    big    = 0xFACE,
326#if defined(_LIBCPP_LITTLE_ENDIAN)
327    native = little
328#elif defined(_LIBCPP_BIG_ENDIAN)
329    native = big
330#else
331    native = 0xCAFE
332#endif
333};
334
335#endif // _LIBCPP_STD_VER > 17
336
337_LIBCPP_END_NAMESPACE_STD
338
339_LIBCPP_POP_MACROS
340
341#endif // _LIBCPP_BIT
342