Coverage Report

Created: 2025-03-04 07:22

/src/serenity/AK/BuiltinWrappers.h
Line
Count
Source (jump to first uncovered line)
1
/*
2
 * Copyright (c) 2021, Nick Johnson <sylvyrfysh@gmail.com>
3
 *
4
 * SPDX-License-Identifier: BSD-2-Clause
5
 */
6
7
#pragma once
8
9
#include "Concepts.h"
10
11
namespace AK {
12
13
template<Unsigned IntType>
14
inline constexpr int popcount(IntType value)
15
0
{
16
0
#if defined(AK_COMPILER_CLANG) || defined(AK_COMPILER_GCC)
17
0
    static_assert(sizeof(IntType) <= sizeof(unsigned long long));
18
    if constexpr (sizeof(IntType) <= sizeof(unsigned int))
19
0
        return __builtin_popcount(value);
20
    if constexpr (sizeof(IntType) == sizeof(unsigned long))
21
0
        return __builtin_popcountl(value);
22
    if constexpr (sizeof(IntType) == sizeof(unsigned long long))
23
0
        return __builtin_popcountll(value);
24
0
    VERIFY_NOT_REACHED();
25
#else
26
    int ones = 0;
27
    for (size_t i = 0; i < 8 * sizeof(IntType); ++i) {
28
        if ((value >> i) & 1) {
29
            ++ones;
30
        }
31
    }
32
    return ones;
33
#endif
34
0
}
Unexecuted instantiation: _ZN2AK8popcountITkNS_8Concepts8UnsignedEhEEiT_
Unexecuted instantiation: _ZN2AK8popcountITkNS_8Concepts8UnsignedEmEEiT_
Unexecuted instantiation: _ZN2AK8popcountITkNS_8Concepts8UnsignedEjEEiT_
Unexecuted instantiation: _ZN2AK8popcountITkNS_8Concepts8UnsignedEhEEiT_
Unexecuted instantiation: _ZN2AK8popcountITkNS_8Concepts8UnsignedEmEEiT_
35
36
// The function will return the number of trailing zeroes in the type. If
37
// the given number if zero, this function may contain undefined
38
// behavior, or it may return the number of bits in the number. If
39
// this function can be called with zero, the use of
40
// count_trailing_zeroes_safe is preferred.
41
template<Unsigned IntType>
42
inline constexpr int count_trailing_zeroes(IntType value)
43
3.39k
{
44
3.39k
#if defined(AK_COMPILER_CLANG) || defined(AK_COMPILER_GCC)
45
3.39k
    static_assert(sizeof(IntType) <= sizeof(unsigned long long));
46
    if constexpr (sizeof(IntType) <= sizeof(unsigned int))
47
3.39k
        return __builtin_ctz(value);
48
    if constexpr (sizeof(IntType) == sizeof(unsigned long))
49
0
        return __builtin_ctzl(value);
50
    if constexpr (sizeof(IntType) == sizeof(unsigned long long))
51
0
        return __builtin_ctzll(value);
52
3.39k
    VERIFY_NOT_REACHED();
53
#else
54
    for (size_t i = 0; i < 8 * sizeof(IntType); ++i) {
55
        if ((value >> i) & 1) {
56
            return i;
57
        }
58
    }
59
    return 8 * sizeof(IntType);
60
#endif
61
3.39k
}
Unexecuted instantiation: _ZN2AK21count_trailing_zeroesITkNS_8Concepts8UnsignedEmEEiT_
_ZN2AK21count_trailing_zeroesITkNS_8Concepts8UnsignedEjEEiT_
Line
Count
Source
43
3.39k
{
44
3.39k
#if defined(AK_COMPILER_CLANG) || defined(AK_COMPILER_GCC)
45
3.39k
    static_assert(sizeof(IntType) <= sizeof(unsigned long long));
46
    if constexpr (sizeof(IntType) <= sizeof(unsigned int))
47
3.39k
        return __builtin_ctz(value);
48
    if constexpr (sizeof(IntType) == sizeof(unsigned long))
49
        return __builtin_ctzl(value);
50
    if constexpr (sizeof(IntType) == sizeof(unsigned long long))
51
        return __builtin_ctzll(value);
52
3.39k
    VERIFY_NOT_REACHED();
53
#else
54
    for (size_t i = 0; i < 8 * sizeof(IntType); ++i) {
55
        if ((value >> i) & 1) {
56
            return i;
57
        }
58
    }
59
    return 8 * sizeof(IntType);
60
#endif
61
3.39k
}
62
63
// The function will return the number of trailing zeroes in the type. If
64
// the given number is zero, this function will return the number of bits
65
// bits in the IntType.
66
template<Unsigned IntType>
67
inline constexpr int count_trailing_zeroes_safe(IntType value)
68
1.72k
{
69
1.72k
    if (value == 0)
70
59
        return 8 * sizeof(IntType);
71
1.66k
    return count_trailing_zeroes(value);
72
1.72k
}
73
74
// The function will return the number of leading zeroes in the type. If
75
// the given number if zero, this function may contain undefined
76
// behavior, or it may return the number of bits in the number. If
77
// this function can be called with zero, the use of
78
// count_leading_zeroes_safe is preferred.
79
template<Unsigned IntType>
80
inline constexpr int count_leading_zeroes(IntType value)
81
451M
{
82
451M
#if defined(AK_COMPILER_CLANG) || defined(AK_COMPILER_GCC)
83
451M
    static_assert(sizeof(IntType) <= sizeof(unsigned long long));
84
    if constexpr (sizeof(IntType) <= sizeof(unsigned int))
85
450M
        return __builtin_clz(value) - (32 - (8 * sizeof(IntType)));
86
    if constexpr (sizeof(IntType) == sizeof(unsigned long))
87
280k
        return __builtin_clzl(value);
88
    if constexpr (sizeof(IntType) == sizeof(unsigned long long))
89
280k
        return __builtin_clzll(value);
90
451M
    VERIFY_NOT_REACHED();
91
#else
92
    // Wrap around, catch going past zero by noticing that i is greater than the number of bits in the number
93
    for (size_t i = (8 * sizeof(IntType)) - 1; i < 8 * sizeof(IntType); --i) {
94
        if ((value >> i) & 1) {
95
            return i;
96
        }
97
    }
98
    return 8 * sizeof(IntType);
99
#endif
100
451M
}
_ZN2AK20count_leading_zeroesITkNS_8Concepts8UnsignedEmEEiT_
Line
Count
Source
81
280k
{
82
280k
#if defined(AK_COMPILER_CLANG) || defined(AK_COMPILER_GCC)
83
280k
    static_assert(sizeof(IntType) <= sizeof(unsigned long long));
84
    if constexpr (sizeof(IntType) <= sizeof(unsigned int))
85
        return __builtin_clz(value) - (32 - (8 * sizeof(IntType)));
86
    if constexpr (sizeof(IntType) == sizeof(unsigned long))
87
280k
        return __builtin_clzl(value);
88
    if constexpr (sizeof(IntType) == sizeof(unsigned long long))
89
280k
        return __builtin_clzll(value);
90
280k
    VERIFY_NOT_REACHED();
91
#else
92
    // Wrap around, catch going past zero by noticing that i is greater than the number of bits in the number
93
    for (size_t i = (8 * sizeof(IntType)) - 1; i < 8 * sizeof(IntType); --i) {
94
        if ((value >> i) & 1) {
95
            return i;
96
        }
97
    }
98
    return 8 * sizeof(IntType);
99
#endif
100
280k
}
_ZN2AK20count_leading_zeroesITkNS_8Concepts8UnsignedEjEEiT_
Line
Count
Source
81
450M
{
82
450M
#if defined(AK_COMPILER_CLANG) || defined(AK_COMPILER_GCC)
83
450M
    static_assert(sizeof(IntType) <= sizeof(unsigned long long));
84
    if constexpr (sizeof(IntType) <= sizeof(unsigned int))
85
450M
        return __builtin_clz(value) - (32 - (8 * sizeof(IntType)));
86
    if constexpr (sizeof(IntType) == sizeof(unsigned long))
87
        return __builtin_clzl(value);
88
    if constexpr (sizeof(IntType) == sizeof(unsigned long long))
89
        return __builtin_clzll(value);
90
450M
    VERIFY_NOT_REACHED();
91
#else
92
    // Wrap around, catch going past zero by noticing that i is greater than the number of bits in the number
93
    for (size_t i = (8 * sizeof(IntType)) - 1; i < 8 * sizeof(IntType); --i) {
94
        if ((value >> i) & 1) {
95
            return i;
96
        }
97
    }
98
    return 8 * sizeof(IntType);
99
#endif
100
450M
}
_ZN2AK20count_leading_zeroesITkNS_8Concepts8UnsignedEtEEiT_
Line
Count
Source
81
4.52k
{
82
4.52k
#if defined(AK_COMPILER_CLANG) || defined(AK_COMPILER_GCC)
83
4.52k
    static_assert(sizeof(IntType) <= sizeof(unsigned long long));
84
    if constexpr (sizeof(IntType) <= sizeof(unsigned int))
85
4.52k
        return __builtin_clz(value) - (32 - (8 * sizeof(IntType)));
86
    if constexpr (sizeof(IntType) == sizeof(unsigned long))
87
        return __builtin_clzl(value);
88
    if constexpr (sizeof(IntType) == sizeof(unsigned long long))
89
        return __builtin_clzll(value);
90
4.52k
    VERIFY_NOT_REACHED();
91
#else
92
    // Wrap around, catch going past zero by noticing that i is greater than the number of bits in the number
93
    for (size_t i = (8 * sizeof(IntType)) - 1; i < 8 * sizeof(IntType); --i) {
94
        if ((value >> i) & 1) {
95
            return i;
96
        }
97
    }
98
    return 8 * sizeof(IntType);
99
#endif
100
4.52k
}
Unexecuted instantiation: _ZN2AK20count_leading_zeroesITkNS_8Concepts8UnsignedEhEEiT_
101
102
#ifdef __SIZEOF_INT128__
103
// This is required for math.cpp internal_scalbn
104
inline constexpr int count_leading_zeroes(unsigned __int128 value)
105
0
{
106
0
#    if defined(AK_COMPILER_CLANG) || defined(AK_COMPILER_GCC)
107
0
    return (value > __UINT64_MAX__) ? __builtin_clzll(value >> 64) : 64 + __builtin_clzll(value);
108
0
#    else
109
0
    unsigned __int128 mask = (unsigned __int128)1 << 127;
110
0
    int ret = 0;
111
0
    while ((value & mask) == 0) {
112
0
        ++ret;
113
0
        mask >>= 1;
114
0
    }
115
0
    return ret;
116
0
#    endif
117
0
}
118
#endif
119
120
// The function will return the number of leading zeroes in the type. If
121
// the given number is zero, this function will return the number of bits
122
// in the IntType.
123
template<Unsigned IntType>
124
inline constexpr int count_leading_zeroes_safe(IntType value)
125
5.28k
{
126
5.28k
    if (value == 0)
127
2.33k
        return 8 * sizeof(IntType);
128
2.94k
    return count_leading_zeroes(value);
129
5.28k
}
_ZN2AK25count_leading_zeroes_safeITkNS_8Concepts8UnsignedEtEEiT_
Line
Count
Source
125
5.28k
{
126
5.28k
    if (value == 0)
127
2.33k
        return 8 * sizeof(IntType);
128
2.94k
    return count_leading_zeroes(value);
129
5.28k
}
Unexecuted instantiation: _ZN2AK25count_leading_zeroes_safeITkNS_8Concepts8UnsignedEhEEiT_
Unexecuted instantiation: _ZN2AK25count_leading_zeroes_safeITkNS_8Concepts8UnsignedEjEEiT_
130
131
// Returns one plus the index of the least significant 1-bit of x, or if x is
132
// zero, returns zero. (See __builtin_ffs.)
133
//
134
// For numbers above zero, bit_scan_forward(n) == count_trailing_zeroes(n) + 1.
135
template<Integral IntType>
136
inline constexpr int bit_scan_forward(IntType value)
137
0
{
138
0
#if defined(AK_COMPILER_CLANG) || (defined(AK_COMPILER_GCC) && (!ARCH(RISCV64) || defined(__riscv_zbb)))
139
0
    static_assert(sizeof(IntType) <= sizeof(unsigned long long));
140
0
    if constexpr (sizeof(IntType) <= sizeof(unsigned int))
141
0
        return __builtin_ffs(value);
142
0
    if constexpr (sizeof(IntType) == sizeof(unsigned long))
143
0
        return __builtin_ffsl(value);
144
0
    if constexpr (sizeof(IntType) == sizeof(unsigned long long))
145
0
        return __builtin_ffsll(value);
146
0
    VERIFY_NOT_REACHED();
147
0
#else
148
0
    if (value == 0)
149
0
        return 0;
150
0
    return 1 + count_trailing_zeroes(static_cast<MakeUnsigned<IntType>>(value));
151
0
#endif
152
0
}
Unexecuted instantiation: _ZN2AK16bit_scan_forwardITkNS_8Concepts8IntegralEhEEiT_
Unexecuted instantiation: _ZN2AK16bit_scan_forwardITkNS_8Concepts8IntegralEmEEiT_
153
154
// Counts the minimum number of bits required to represent the value (i.e. ignoring leading null bits).
155
template<Unsigned IntType>
156
inline constexpr size_t count_required_bits(IntType value)
157
1.30M
{
158
1.30M
    if (value == 0)
159
0
        return 1;
160
161
1.30M
    return 8 * sizeof(value) - count_leading_zeroes(value);
162
1.30M
}
_ZN2AK19count_required_bitsITkNS_8Concepts8UnsignedEjEEmT_
Line
Count
Source
157
1.30M
{
158
1.30M
    if (value == 0)
159
0
        return 1;
160
161
1.30M
    return 8 * sizeof(value) - count_leading_zeroes(value);
162
1.30M
}
Unexecuted instantiation: _ZN2AK19count_required_bitsITkNS_8Concepts8UnsignedEmEEmT_
163
164
}
165
166
#if USING_AK_GLOBALLY
167
using AK::bit_scan_forward;
168
using AK::count_leading_zeroes;
169
using AK::count_leading_zeroes_safe;
170
using AK::count_required_bits;
171
using AK::count_trailing_zeroes;
172
using AK::count_trailing_zeroes_safe;
173
using AK::popcount;
174
#endif