Coverage Report

Created: 2020-07-11 14:00

/Users/buildslave/jenkins/workspace/coverage/llvm-project/libcxx/include/bit
Line
Count
Source (jump to first uncovered line)
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
16
namespace 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
81
inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
82
0
int __libcpp_ctz(unsigned __x)           _NOEXCEPT { return __builtin_ctz(__x); }
83
84
inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
85
0
int __libcpp_ctz(unsigned long __x)      _NOEXCEPT { return __builtin_ctzl(__x); }
86
87
inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
88
0
int __libcpp_ctz(unsigned long long __x) _NOEXCEPT { return __builtin_ctzll(__x); }
89
90
91
inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
92
int __libcpp_clz(unsigned __x)           _NOEXCEPT { return __builtin_clz(__x); }
93
94
inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
95
0
int __libcpp_clz(unsigned long __x)      _NOEXCEPT { return __builtin_clzl(__x); }
96
97
inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
98
int __libcpp_clz(unsigned long long __x) _NOEXCEPT { return __builtin_clzll(__x); }
99
100
101
inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
102
0
int __libcpp_popcount(unsigned __x)           _NOEXCEPT { return __builtin_popcount(__x); }
103
104
inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
105
int __libcpp_popcount(unsigned long __x)      _NOEXCEPT { return __builtin_popcountl(__x); }
106
107
inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
108
0
int __libcpp_popcount(unsigned long long __x) _NOEXCEPT { return __builtin_popcountll(__x); }
109
110
#else  // _LIBCPP_COMPILER_MSVC
111
112
// Precondition:  __x != 0
113
inline _LIBCPP_INLINE_VISIBILITY
114
int __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
123
inline _LIBCPP_INLINE_VISIBILITY
124
int __libcpp_ctz(unsigned long __x) {
125
    static_assert(sizeof(unsigned long) == sizeof(unsigned), "");
126
    return __ctz(static_cast<unsigned>(__x));
127
}
128
129
inline _LIBCPP_INLINE_VISIBILITY
130
int __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
147
inline _LIBCPP_INLINE_VISIBILITY
148
int __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
157
inline _LIBCPP_INLINE_VISIBILITY
158
int __libcpp_clz(unsigned long __x) {
159
    static_assert(sizeof(unsigned) == sizeof(unsigned long), "");
160
    return __libcpp_clz(static_cast<unsigned>(__x));
161
}
162
163
inline _LIBCPP_INLINE_VISIBILITY
164
int __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
179
inline _LIBCPP_INLINE_VISIBILITY int __libcpp_popcount(unsigned __x) {
180
  static_assert(sizeof(unsigned) == 4, "");
181
  return __popcnt(__x);
182
}
183
184
inline _LIBCPP_INLINE_VISIBILITY int __libcpp_popcount(unsigned long __x) {
185
  static_assert(sizeof(unsigned long) == 4, "");
186
  return __popcnt(__x);
187
}
188
189
inline _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
196
template <class _Tp>
197
using __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
208
template<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
220
template<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
233
template<class _Tp>
234
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
235
int __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
261
template<class _Tp>
262
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
263
int __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
293
template<class _Tp>
294
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
295
int __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
304
template<class _Tp>
305
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
306
int __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
315
template<class _Tp>
316
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
317
int
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
341
template<class _Tp>
342
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
343
unsigned __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
349
template <class _Tp>
350
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
351
bool __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
360
template<class _Tp>
361
_LIBCPP_INLINE_VISIBILITY constexpr
362
enable_if_t<__bitop_unsigned_integer<_Tp>::value, _Tp>
363
rotl(_Tp __t, unsigned int __cnt) noexcept
364
{
365
    return __rotl(__t, __cnt);
366
}
367
368
369
// rotr
370
template<class _Tp>
371
_LIBCPP_INLINE_VISIBILITY constexpr
372
enable_if_t<__bitop_unsigned_integer<_Tp>::value, _Tp>
373
rotr(_Tp __t, unsigned int __cnt) noexcept
374
{
375
    return __rotr(__t, __cnt);
376
}
377
378
379
template<class _Tp>
380
_LIBCPP_INLINE_VISIBILITY constexpr
381
enable_if_t<__bitop_unsigned_integer<_Tp>::value, int>
382
countl_zero(_Tp __t) noexcept
383
{
384
    return __countl_zero(__t);
385
}
386
387
388
template<class _Tp>
389
_LIBCPP_INLINE_VISIBILITY constexpr
390
enable_if_t<__bitop_unsigned_integer<_Tp>::value, int>
391
countl_one(_Tp __t) noexcept
392
{
393
    return __countl_one(__t);
394
}
395
396
397
template<class _Tp>
398
_LIBCPP_INLINE_VISIBILITY constexpr
399
enable_if_t<__bitop_unsigned_integer<_Tp>::value, int>
400
countr_zero(_Tp __t) noexcept
401
{
402
  return __countr_zero(__t);
403
}
404
405
406
template<class _Tp>
407
_LIBCPP_INLINE_VISIBILITY constexpr
408
enable_if_t<__bitop_unsigned_integer<_Tp>::value, int>
409
countr_one(_Tp __t) noexcept
410
{
411
    return __countr_one(__t);
412
}
413
414
415
template<class _Tp>
416
_LIBCPP_INLINE_VISIBILITY constexpr
417
enable_if_t<__bitop_unsigned_integer<_Tp>::value, int>
418
popcount(_Tp __t) noexcept
419
{
420
    return __popcount(__t);
421
}
422
423
424
template <class _Tp>
425
_LIBCPP_INLINE_VISIBILITY constexpr
426
enable_if_t<__bitop_unsigned_integer<_Tp>::value, bool>
427
ispow2(_Tp __t) noexcept
428
{
429
    return __ispow2(__t);
430
}
431
432
template <class _Tp>
433
_LIBCPP_INLINE_VISIBILITY constexpr
434
enable_if_t<__bitop_unsigned_integer<_Tp>::value, _Tp>
435
floor2(_Tp __t) noexcept
436
{
437
    return __t == 0 ? 0 : _Tp{1} << __bit_log2(__t);
438
}
439
440
template <class _Tp>
441
_LIBCPP_INLINE_VISIBILITY constexpr
442
enable_if_t<__bitop_unsigned_integer<_Tp>::value, _Tp>
443
ceil2(_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
459
template <class _Tp>
460
_LIBCPP_INLINE_VISIBILITY constexpr
461
enable_if_t<__bitop_unsigned_integer<_Tp>::value, _Tp>
462
log2p1(_Tp __t) noexcept
463
{
464
    return __t == 0 ? 0 : __bit_log2(__t) + 1;
465
}
466
467
468
enum 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