1// Copyright (C) 2020 The Qt Company Ltd.
2// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
3
4#ifndef QALGORITHMS_H
5#define QALGORITHMS_H
6
7#if 0
8#pragma qt_class(QtAlgorithms)
9#endif
10
11#include <QtCore/qglobal.h>
12
13#if __has_include(<bit>) && __cplusplus > 201703L
14#include <bit>
15#endif
16
17#ifdef Q_CC_MSVC
18#include <intrin.h>
19#endif
20
21QT_BEGIN_NAMESPACE
22
23template <typename ForwardIterator>
24Q_OUTOFLINE_TEMPLATE void qDeleteAll(ForwardIterator begin, ForwardIterator end)
25{
26 while (begin != end) {
27 delete *begin;
28 ++begin;
29 }
30}
31
32template <typename Container>
33inline void qDeleteAll(const Container &c)
34{
35 qDeleteAll(c.begin(), c.end());
36}
37
38/*
39 Warning: The contents of QAlgorithmsPrivate is not a part of the public Qt API
40 and may be changed from version to version or even be completely removed.
41*/
42namespace QAlgorithmsPrivate {
43
44#if defined(__cpp_lib_bitops) && __cpp_lib_bitops >= 201907L
45// We use C++20 <bit> operations instead which ensures constexpr bit ops
46# define QT_HAS_CONSTEXPR_BITOPS
47#elif defined(Q_CC_GNU)
48# define QT_HAS_CONSTEXPR_BITOPS
49# define QT_HAS_BUILTIN_CTZS
50constexpr Q_ALWAYS_INLINE uint qt_builtin_ctzs(quint16 v) noexcept
51{
52# if __has_builtin(__builtin_ctzs)
53 return __builtin_ctzs(v);
54# else
55 return __builtin_ctz(v);
56# endif
57}
58#define QT_HAS_BUILTIN_CLZS
59constexpr Q_ALWAYS_INLINE uint qt_builtin_clzs(quint16 v) noexcept
60{
61# if __has_builtin(__builtin_clzs)
62 return __builtin_clzs(v);
63# else
64 return __builtin_clz(v) - 16U;
65# endif
66}
67#define QT_HAS_BUILTIN_CTZ
68constexpr Q_ALWAYS_INLINE uint qt_builtin_ctz(quint32 v) noexcept
69{
70 return __builtin_ctz(v);
71}
72#define QT_HAS_BUILTIN_CLZ
73constexpr Q_ALWAYS_INLINE uint qt_builtin_clz(quint32 v) noexcept
74{
75 return __builtin_clz(v);
76}
77#define QT_HAS_BUILTIN_CTZLL
78constexpr Q_ALWAYS_INLINE uint qt_builtin_ctzll(quint64 v) noexcept
79{
80 return __builtin_ctzll(v);
81}
82#define QT_HAS_BUILTIN_CLZLL
83constexpr Q_ALWAYS_INLINE uint qt_builtin_clzll(quint64 v) noexcept
84{
85 return __builtin_clzll(v);
86}
87#define QALGORITHMS_USE_BUILTIN_POPCOUNT
88constexpr Q_ALWAYS_INLINE uint qt_builtin_popcount(quint32 v) noexcept
89{
90 return __builtin_popcount(v);
91}
92constexpr Q_ALWAYS_INLINE uint qt_builtin_popcount(quint8 v) noexcept
93{
94 return __builtin_popcount(v);
95}
96constexpr Q_ALWAYS_INLINE uint qt_builtin_popcount(quint16 v) noexcept
97{
98 return __builtin_popcount(v);
99}
100#define QALGORITHMS_USE_BUILTIN_POPCOUNTLL
101constexpr Q_ALWAYS_INLINE uint qt_builtin_popcountll(quint64 v) noexcept
102{
103 return __builtin_popcountll(v);
104}
105#elif defined(Q_CC_MSVC) && !defined(Q_PROCESSOR_ARM)
106#define QT_HAS_BUILTIN_CTZ
107Q_ALWAYS_INLINE unsigned long qt_builtin_ctz(quint32 val)
108{
109 unsigned long result;
110 _BitScanForward(&result, val);
111 return result;
112}
113#define QT_HAS_BUILTIN_CLZ
114Q_ALWAYS_INLINE unsigned long qt_builtin_clz(quint32 val)
115{
116 unsigned long result;
117 _BitScanReverse(&result, val);
118 // Now Invert the result: clz will count *down* from the msb to the lsb, so the msb index is 31
119 // and the lsb index is 0. The result for the index when counting up: msb index is 0 (because it
120 // starts there), and the lsb index is 31.
121 result ^= sizeof(quint32) * 8 - 1;
122 return result;
123}
124#if Q_PROCESSOR_WORDSIZE == 8
125// These are only defined for 64bit builds.
126#define QT_HAS_BUILTIN_CTZLL
127Q_ALWAYS_INLINE unsigned long qt_builtin_ctzll(quint64 val)
128{
129 unsigned long result;
130 _BitScanForward64(&result, val);
131 return result;
132}
133// MSVC calls it _BitScanReverse and returns the carry flag, which we don't need
134#define QT_HAS_BUILTIN_CLZLL
135Q_ALWAYS_INLINE unsigned long qt_builtin_clzll(quint64 val)
136{
137 unsigned long result;
138 _BitScanReverse64(&result, val);
139 // see qt_builtin_clz
140 result ^= sizeof(quint64) * 8 - 1;
141 return result;
142}
143#endif // MSVC 64bit
144# define QT_HAS_BUILTIN_CTZS
145Q_ALWAYS_INLINE uint qt_builtin_ctzs(quint16 v) noexcept
146{
147 return qt_builtin_ctz(v);
148}
149#define QT_HAS_BUILTIN_CLZS
150Q_ALWAYS_INLINE uint qt_builtin_clzs(quint16 v) noexcept
151{
152 return qt_builtin_clz(v) - 16U;
153}
154
155// Neither MSVC nor the Intel compiler define a macro for the POPCNT processor
156// feature, so we're using either the SSE4.2 or the AVX macro as a proxy (Clang
157// does define the macro). It's incorrect for two reasons:
158// 1. It's a separate bit in CPUID, so a processor could implement SSE4.2 and
159// not POPCNT, but that's unlikely to happen.
160// 2. There are processors that support POPCNT but not AVX (Intel Nehalem
161// architecture), but unlike the other compilers, MSVC has no option
162// to generate code for those processors.
163// So it's an acceptable compromise.
164#if defined(__AVX__) || defined(__SSE4_2__) || defined(__POPCNT__)
165#define QT_POPCOUNT_CONSTEXPR
166#define QT_POPCOUNT_RELAXED_CONSTEXPR
167#define QALGORITHMS_USE_BUILTIN_POPCOUNT
168#define QALGORITHMS_USE_BUILTIN_POPCOUNTLL
169Q_ALWAYS_INLINE uint qt_builtin_popcount(quint32 v) noexcept
170{
171 return __popcnt(v);
172}
173Q_ALWAYS_INLINE uint qt_builtin_popcount(quint8 v) noexcept
174{
175 return __popcnt16(v);
176}
177Q_ALWAYS_INLINE uint qt_builtin_popcount(quint16 v) noexcept
178{
179 return __popcnt16(v);
180}
181Q_ALWAYS_INLINE uint qt_builtin_popcountll(quint64 v) noexcept
182{
183#if Q_PROCESSOR_WORDSIZE == 8
184 return __popcnt64(v);
185#else
186 return __popcnt(quint32(v)) + __popcnt(quint32(v >> 32));
187#endif // MSVC 64bit
188}
189
190#endif // __AVX__ || __SSE4_2__ || __POPCNT__
191
192#endif // MSVC
193
194#ifndef QT_POPCOUNT_CONSTEXPR
195#define QT_POPCOUNT_CONSTEXPR constexpr
196#define QT_POPCOUNT_RELAXED_CONSTEXPR constexpr
197#endif
198
199} //namespace QAlgorithmsPrivate
200
201Q_DECL_CONST_FUNCTION QT_POPCOUNT_CONSTEXPR inline uint qPopulationCount(quint32 v) noexcept
202{
203#if defined(__cpp_lib_bitops) && __cpp_lib_bitops >= 201907L
204 return std::popcount(v);
205#elif defined QALGORITHMS_USE_BUILTIN_POPCOUNT
206 return QAlgorithmsPrivate::qt_builtin_popcount(v);
207#else
208 // See http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel
209 return
210 (((v ) & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f +
211 (((v >> 12) & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f +
212 (((v >> 24) & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f;
213#endif
214}
215
216Q_DECL_CONST_FUNCTION QT_POPCOUNT_CONSTEXPR inline uint qPopulationCount(quint8 v) noexcept
217{
218#if defined(__cpp_lib_bitops) && __cpp_lib_bitops >= 201907L
219 return std::popcount(v);
220#elif defined QALGORITHMS_USE_BUILTIN_POPCOUNT
221 return QAlgorithmsPrivate::qt_builtin_popcount(v);
222#else
223 return
224 (((v ) & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f;
225#endif
226}
227
228Q_DECL_CONST_FUNCTION QT_POPCOUNT_CONSTEXPR inline uint qPopulationCount(quint16 v) noexcept
229{
230#if defined(__cpp_lib_bitops) && __cpp_lib_bitops >= 201907L
231 return std::popcount(v);
232#elif defined QALGORITHMS_USE_BUILTIN_POPCOUNT
233 return QAlgorithmsPrivate::qt_builtin_popcount(v);
234#else
235 return
236 (((v ) & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f +
237 (((v >> 12) & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f;
238#endif
239}
240
241Q_DECL_CONST_FUNCTION QT_POPCOUNT_CONSTEXPR inline uint qPopulationCount(quint64 v) noexcept
242{
243#if defined(__cpp_lib_bitops) && __cpp_lib_bitops >= 201907L
244 return std::popcount(v);
245#elif defined QALGORITHMS_USE_BUILTIN_POPCOUNTLL
246 return QAlgorithmsPrivate::qt_builtin_popcountll(v);
247#else
248 return
249 (((v ) & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f +
250 (((v >> 12) & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f +
251 (((v >> 24) & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f +
252 (((v >> 36) & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f +
253 (((v >> 48) & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f +
254 (((v >> 60) & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f;
255#endif
256}
257
258Q_DECL_CONST_FUNCTION QT_POPCOUNT_CONSTEXPR inline uint qPopulationCount(long unsigned int v) noexcept
259{
260 return qPopulationCount(v: static_cast<quint64>(v));
261}
262
263#if defined(QALGORITHMS_USE_BUILTIN_POPCOUNT)
264#undef QALGORITHMS_USE_BUILTIN_POPCOUNT
265#endif
266#undef QT_POPCOUNT_CONSTEXPR
267
268namespace QtPrivate {
269constexpr inline uint qConstexprCountTrailingZeroBits(quint32 v) noexcept
270{
271 // see http://graphics.stanford.edu/~seander/bithacks.html#ZerosOnRightParallel
272 unsigned int c = 32; // c will be the number of zero bits on the right
273 v &= -signed(v);
274 if (v) c--;
275 if (v & 0x0000FFFF) c -= 16;
276 if (v & 0x00FF00FF) c -= 8;
277 if (v & 0x0F0F0F0F) c -= 4;
278 if (v & 0x33333333) c -= 2;
279 if (v & 0x55555555) c -= 1;
280 return c;
281}
282
283constexpr inline uint qConstexprCountTrailingZeroBits(quint64 v) noexcept
284{
285 quint32 x = static_cast<quint32>(v);
286 return x ? qConstexprCountTrailingZeroBits(v: x)
287 : 32 + qConstexprCountTrailingZeroBits(v: static_cast<quint32>(v >> 32));
288}
289
290constexpr inline uint qConstexprCountTrailingZeroBits(quint8 v) noexcept
291{
292 unsigned int c = 8; // c will be the number of zero bits on the right
293 v &= quint8(-signed(v));
294 if (v) c--;
295 if (v & 0x0000000F) c -= 4;
296 if (v & 0x00000033) c -= 2;
297 if (v & 0x00000055) c -= 1;
298 return c;
299}
300
301constexpr inline uint qConstexprCountTrailingZeroBits(quint16 v) noexcept
302{
303 unsigned int c = 16; // c will be the number of zero bits on the right
304 v &= quint16(-signed(v));
305 if (v) c--;
306 if (v & 0x000000FF) c -= 8;
307 if (v & 0x00000F0F) c -= 4;
308 if (v & 0x00003333) c -= 2;
309 if (v & 0x00005555) c -= 1;
310 return c;
311}
312
313constexpr inline uint qConstexprCountTrailingZeroBits(unsigned long v) noexcept
314{
315 return qConstexprCountTrailingZeroBits(v: QIntegerForSizeof<long>::Unsigned(v));
316}
317}
318
319constexpr inline uint qCountTrailingZeroBits(quint32 v) noexcept
320{
321#if defined(__cpp_lib_bitops) && __cpp_lib_bitops >= 201907L
322 return std::countr_zero(v);
323#elif defined(QT_HAS_BUILTIN_CTZ)
324 return v ? QAlgorithmsPrivate::qt_builtin_ctz(v) : 32U;
325#else
326 return QtPrivate::qConstexprCountTrailingZeroBits(v);
327#endif
328}
329
330constexpr inline uint qCountTrailingZeroBits(quint8 v) noexcept
331{
332#if defined(__cpp_lib_bitops) && __cpp_lib_bitops >= 201907L
333 return std::countr_zero(v);
334#elif defined(QT_HAS_BUILTIN_CTZ)
335 return v ? QAlgorithmsPrivate::qt_builtin_ctz(v) : 8U;
336#else
337 return QtPrivate::qConstexprCountTrailingZeroBits(v);
338#endif
339}
340
341constexpr inline uint qCountTrailingZeroBits(quint16 v) noexcept
342{
343#if defined(__cpp_lib_bitops) && __cpp_lib_bitops >= 201907L
344 return std::countr_zero(v);
345#elif defined(QT_HAS_BUILTIN_CTZS)
346 return v ? QAlgorithmsPrivate::qt_builtin_ctzs(v) : 16U;
347#else
348 return QtPrivate::qConstexprCountTrailingZeroBits(v);
349#endif
350}
351
352constexpr inline uint qCountTrailingZeroBits(quint64 v) noexcept
353{
354#if defined(__cpp_lib_bitops) && __cpp_lib_bitops >= 201907L
355 return std::countr_zero(v);
356#elif defined(QT_HAS_BUILTIN_CTZLL)
357 return v ? QAlgorithmsPrivate::qt_builtin_ctzll(v) : 64;
358#else
359 return QtPrivate::qConstexprCountTrailingZeroBits(v);
360#endif
361}
362
363constexpr inline uint qCountTrailingZeroBits(unsigned long v) noexcept
364{
365 return qCountTrailingZeroBits(v: QIntegerForSizeof<long>::Unsigned(v));
366}
367
368QT_POPCOUNT_RELAXED_CONSTEXPR inline uint qCountLeadingZeroBits(quint32 v) noexcept
369{
370#if defined(__cpp_lib_bitops) && __cpp_lib_bitops >= 201907L
371 return std::countl_zero(v);
372#elif defined(QT_HAS_BUILTIN_CLZ)
373 return v ? QAlgorithmsPrivate::qt_builtin_clz(v) : 32U;
374#else
375 // Hacker's Delight, 2nd ed. Fig 5-16, p. 102
376 v = v | (v >> 1);
377 v = v | (v >> 2);
378 v = v | (v >> 4);
379 v = v | (v >> 8);
380 v = v | (v >> 16);
381 return qPopulationCount(~v);
382#endif
383}
384
385QT_POPCOUNT_RELAXED_CONSTEXPR inline uint qCountLeadingZeroBits(quint8 v) noexcept
386{
387#if defined(__cpp_lib_bitops) && __cpp_lib_bitops >= 201907L
388 return std::countl_zero(v);
389#elif defined(QT_HAS_BUILTIN_CLZ)
390 return v ? QAlgorithmsPrivate::qt_builtin_clz(v)-24U : 8U;
391#else
392 v = v | (v >> 1);
393 v = v | (v >> 2);
394 v = v | (v >> 4);
395 return qPopulationCount(static_cast<quint8>(~v));
396#endif
397}
398
399QT_POPCOUNT_RELAXED_CONSTEXPR inline uint qCountLeadingZeroBits(quint16 v) noexcept
400{
401#if defined(__cpp_lib_bitops) && __cpp_lib_bitops >= 201907L
402 return std::countl_zero(v);
403#elif defined(QT_HAS_BUILTIN_CLZS)
404 return v ? QAlgorithmsPrivate::qt_builtin_clzs(v) : 16U;
405#else
406 v = v | (v >> 1);
407 v = v | (v >> 2);
408 v = v | (v >> 4);
409 v = v | (v >> 8);
410 return qPopulationCount(static_cast<quint16>(~v));
411#endif
412}
413
414QT_POPCOUNT_RELAXED_CONSTEXPR inline uint qCountLeadingZeroBits(quint64 v) noexcept
415{
416#if defined(__cpp_lib_bitops) && __cpp_lib_bitops >= 201907L
417 return std::countl_zero(v);
418#elif defined(QT_HAS_BUILTIN_CLZLL)
419 return v ? QAlgorithmsPrivate::qt_builtin_clzll(v) : 64U;
420#else
421 v = v | (v >> 1);
422 v = v | (v >> 2);
423 v = v | (v >> 4);
424 v = v | (v >> 8);
425 v = v | (v >> 16);
426 v = v | (v >> 32);
427 return qPopulationCount(~v);
428#endif
429}
430
431QT_POPCOUNT_RELAXED_CONSTEXPR inline uint qCountLeadingZeroBits(unsigned long v) noexcept
432{
433 return qCountLeadingZeroBits(v: QIntegerForSizeof<long>::Unsigned(v));
434}
435
436#undef QT_POPCOUNT_RELAXED_CONSTEXPR
437
438QT_END_NAMESPACE
439
440#endif // QALGORITHMS_H
441

source code of qtbase/src/corelib/tools/qalgorithms.h