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