Revision control
Copy as Markdown
// Copyright (C) 2025 Intel Corporation.
// Copyright (C) 2020 The Qt Company Ltd.
// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
// Qt-Security score:significant reason:default
#ifndef Q20BIT_H
#define Q20BIT_H
#include <QtCore/q20type_traits.h>
#if defined(__cpp_lib_bitops) || defined(__cpp_lib_int_pow2)
# include <bit>
#else
# include <QtCore/qtypes.h>
# include <limits>
# ifdef Q_CC_MSVC
// avoiding qsimd.h -> immintrin.h unless necessary, because it increases
// compilation time
# include <QtCore/qsimd.h>
# include <intrin.h>
# endif
#endif
//
// W A R N I N G
// -------------
//
// This file is not part of the Qt API. Types and functions defined in this
// file can reliably be replaced by their std counterparts, once available.
// You may use these definitions in your own code, but be aware that we
// will remove them once Qt depends on the C++ version that supports
// them in namespace std. There will be NO deprecation warning, the
// definitions will JUST go away.
//
// If you can't agree to these terms, don't use these definitions!
//
// We mean it.
//
QT_BEGIN_NAMESPACE
namespace q20 {
#if defined(__cpp_lib_bitops)
using std::countl_zero;
using std::countr_zero;
using std::popcount;
using std::rotl;
using std::rotr;
#else
namespace detail {
template <typename T> /*non-constexpr*/ inline auto hw_popcount(T v) noexcept
{
#if defined(Q_CC_MSVC) && defined(Q_PROCESSOR_ARM_64)
if constexpr (sizeof(T) == sizeof(quint64))
return int(_CountOneBits64(v));
return int(_CountOneBits(v));
#endif
#if defined(Q_CC_MSVC) && defined(Q_PROCESSOR_X86) && defined(__POPCNT__)
// Note: __POPCNT__ comes from qsimd.h, not the compiler.
# ifdef Q_PROCESSOR_X86_64
if constexpr (sizeof(T) == sizeof(quint64))
return int(__popcnt64(v));
# endif
if constexpr (sizeof(T) == sizeof(quint64))
return int(__popcnt(quint32(v)) + __popcnt(quint32(v >> 32)));
if constexpr (sizeof(T) == sizeof(quint32))
return int(__popcnt(v));
return int(__popcnt16(v));
#else
Q_UNUSED(v);
#endif
}
template <typename T> /*non-constexpr*/ inline auto hw_countl_zero(T v) noexcept
{
#if defined(Q_CC_MSVC_ONLY) && defined(Q_PROCESSOR_ARM_64)
if constexpr (sizeof(T) == sizeof(quint64))
return int(_CountLeadingZeros64(v));
return int(_CountLeadingZeros(v)) - (32 - std::numeric_limits<T>::digits);
#endif
#if defined(Q_CC_MSVC) && defined(Q_PROCESSOR_X86) && defined(__LZCNT__)
// Note: __LZCNT__ comes from qsimd.h, not the compiler
# if defined(Q_PROCESSOR_X86_64)
if constexpr (sizeof(T) == sizeof(quint64))
return int(__lzcnt64(v));
# endif
if constexpr (sizeof(T) == sizeof(quint32))
return int(__lzcnt(v));
if constexpr (sizeof(T) == sizeof(quint16))
return int(__lzcnt16(v));
if constexpr (sizeof(T) == sizeof(quint8))
return int(__lzcnt(v)) - 24;
#endif
#if defined(Q_CC_MSVC) && defined(Q_PROCESSOR_X86)
constexpr int Digits = std::numeric_limits<T>::digits;
unsigned long result;
if constexpr (sizeof(T) == sizeof(quint64)) {
# ifdef Q_PROCESSOR_X86_64
if (_BitScanReverse64(&result, v) == 0)
return Digits;
# else
if (quint32 h = quint32(v >> 32))
return hw_countl_zero(h);
return hw_countl_zero(quint32(v)) + 32;
# endif
} else {
if (_BitScanReverse(&result, v) == 0)
return Digits;
}
// Now Invert the result: clz will count *down* from the msb to the lsb, so the msb index is 31
// and the lsb index is 0. The result for the index when counting up: msb index is 0 (because it
// starts there), and the lsb index is 31.
result ^= sizeof(T) * 8 - 1;
return int(result);
#else
Q_UNUSED(v);
#endif
}
template <typename T> /*non-constexpr*/ inline auto hw_countr_zero(T v) noexcept
{
#if defined(Q_CC_MSVC_ONLY) && defined(Q_PROCESSOR_ARM_64)
if constexpr (sizeof(T) == sizeof(quint64))
return int(_CountTrailingZeros64(v));
constexpr int Digits = std::numeric_limits<T>::digits;
const int result = int(_CountTrailingZeros(v));
return result > Digits ? Digits : result;
#endif
#if defined(Q_CC_MSVC) && defined(Q_PROCESSOR_X86) && defined(__BMI__)
// Note: __BMI__ comes from qsimd.h, not the compiler
# if defined(Q_PROCESSOR_X86_64)
if constexpr (sizeof(T) == sizeof(quint64))
return int(_tzcnt_u64(v));
# endif
if constexpr (sizeof(T) == sizeof(quint32))
return int(_tzcnt_u32(v));
// No _tzcnt_u16 or u8 intrinsics
#endif
#if defined(Q_CC_MSVC) && defined(Q_PROCESSOR_X86)
constexpr int Digits = std::numeric_limits<T>::digits;
unsigned long result;
if constexpr (sizeof(T) <= sizeof(quint32))
return _BitScanForward(&result, v) ? int(result) : Digits;
# ifdef Q_PROCESSOR_X86_64
return _BitScanForward64(&result, v) ? int(result) : Digits;
# endif
#else
Q_UNUSED(v);
#endif
}
} // namespace q20::detail
template <typename T> constexpr std::enable_if_t<std::is_unsigned_v<T>, int>
popcount(T v) noexcept
{
#if __has_builtin(__builtin_popcountg)
return __builtin_popcountg(v);
#endif
if constexpr (sizeof(T) > sizeof(quint64)) {
static_assert(sizeof(T) == 16, "Unsupported integer size");
return popcount(quint64(v)) + popcount(quint64(v >> 64));
}
# if __has_builtin(__builtin_popcount)
// These GCC/Clang intrinsics are constexpr and use the HW instructions
// where available. Note: no runtime detection.
if constexpr (sizeof(T) > sizeof(quint32))
return __builtin_popcountll(v);
return __builtin_popcount(v);
# endif
# ifdef QT_SUPPORTS_IS_CONSTANT_EVALUATED
// Try hardware functions if not constexpr. Note: no runtime detection.
if (!is_constant_evaluated()) {
if constexpr (std::is_integral_v<decltype(detail::hw_popcount(v))>)
return detail::hw_popcount(v);
}
# endif
constexpr int Digits = std::numeric_limits<T>::digits;
int r = (((v ) & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f;
if constexpr (Digits > 12)
r += (((v >> 12) & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f;
if constexpr (Digits > 24)
r += (((v >> 24) & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f;
if constexpr (Digits > 36) {
r += (((v >> 36) & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f +
(((v >> 48) & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f +
(((v >> 60) & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f;
}
return r;
}
template <typename T> constexpr std::enable_if_t<std::is_unsigned_v<T>, int>
countl_zero(T v) noexcept
{
#if __has_builtin(__builtin_clzg)
// "If two arguments are specified, and first argument is 0, the result is
// the second argument."
return __builtin_clzg(v, std::numeric_limits<T>::digits);
#endif
if constexpr (sizeof(T) > sizeof(quint64)) {
static_assert(sizeof(T) == 16, "Unsupported integer size");
if (quint64 h = quint64(v >> 64))
return countl_zero(h);
return countl_zero(quint64(v)) + 64;
}
#if __has_builtin(__builtin_clz)
// These GCC/Clang intrinsics are constexpr and use the HW instructions
// where available.
if (!v)
return std::numeric_limits<T>::digits;
if constexpr (sizeof(T) == sizeof(quint64))
return __builtin_clzll(v);
# if __has_builtin(__builtin_clzs)
if constexpr (sizeof(T) == sizeof(quint16))
return __builtin_clzs(v);
# endif
return __builtin_clz(v) - (32 - std::numeric_limits<T>::digits);
#endif
#ifdef QT_SUPPORTS_IS_CONSTANT_EVALUATED
// Try hardware functions if not constexpr. Note: no runtime detection.
if (!is_constant_evaluated()) {
if constexpr (std::is_integral_v<decltype(detail::hw_countl_zero(v))>)
return detail::hw_countl_zero(v);
}
#endif
// Hacker's Delight, 2nd ed. Fig 5-16, p. 102
v = v | (v >> 1);
v = v | (v >> 2);
v = v | (v >> 4);
if constexpr (sizeof(T) > sizeof(quint8))
v = v | (v >> 8);
if constexpr (sizeof(T) > sizeof(quint16))
v = v | (v >> 16);
if constexpr (sizeof(T) > sizeof(quint32))
v = v | (v >> 32);
return popcount(T(~v));
}
template <typename T> constexpr std::enable_if_t<std::is_unsigned_v<T>, int>
countr_zero(T v) noexcept
{
#if __has_builtin(__builtin_ctzg)
// "If two arguments are specified, and first argument is 0, the result is
// the second argument."
return __builtin_ctzg(v, std::numeric_limits<T>::digits);
#endif
if constexpr (sizeof(T) > sizeof(quint64)) {
static_assert(sizeof(T) == 16, "Unsupported integer size");
quint64 l = quint64(v);
return l ? countr_zero(l) : 64 + countr_zero(quint64(v >> 64));
}
#if __has_builtin(__builtin_ctz)
// These GCC/Clang intrinsics are constexpr and use the HW instructions
// where available.
if (!v)
return std::numeric_limits<T>::digits;
if constexpr (sizeof(T) == sizeof(quint64))
return __builtin_ctzll(v);
# if __has_builtin(__builtin_ctzs)
if constexpr (sizeof(T) == sizeof(quint16))
return __builtin_ctzs(v);
# endif
return __builtin_ctz(v);
#endif
#ifdef QT_SUPPORTS_IS_CONSTANT_EVALUATED
// Try hardware functions if not constexpr. Note: no runtime detection.
if (!is_constant_evaluated()) {
if constexpr (std::is_integral_v<decltype(detail::hw_countr_zero(v))>)
return detail::hw_countr_zero(v);
}
#endif
if constexpr (sizeof(T) > sizeof(quint32)) {
quint32 l = quint32(v);
return l ? countr_zero(l) : 32 + countr_zero(quint32(v >> 32));
}
int c = std::numeric_limits<T>::digits; // c will be the number of zero bits on the right
QT_WARNING_PUSH
QT_WARNING_DISABLE_MSVC(4146) // unary minus operator applied to unsigned type, result still unsigned
v &= T(-v);
QT_WARNING_POP
if (v) c--;
if constexpr (sizeof(T) == sizeof(quint32)) {
if (v & 0x0000FFFF) c -= 16;
if (v & 0x00FF00FF) c -= 8;
if (v & 0x0F0F0F0F) c -= 4;
if (v & 0x33333333) c -= 2;
if (v & 0x55555555) c -= 1;
} else if constexpr (sizeof(T) == sizeof(quint16)) {
if (v & 0x000000FF) c -= 8;
if (v & 0x00000F0F) c -= 4;
if (v & 0x00003333) c -= 2;
if (v & 0x00005555) c -= 1;
} else /*if constexpr (sizeof(T) == sizeof(quint8))*/ {
if (v & 0x0000000F) c -= 4;
if (v & 0x00000033) c -= 2;
if (v & 0x00000055) c -= 1;
}
return c;
}
template <typename T> constexpr std::enable_if_t<std::is_unsigned_v<T>, T>
rotl(T v, int s) noexcept
{
constexpr int Digits = std::numeric_limits<T>::digits;
unsigned n = unsigned(s) % Digits;
return (v << n) | (v >> (Digits - n));
}
template <typename T> constexpr std::enable_if_t<std::is_unsigned_v<T>, T>
rotr(T v, int s) noexcept
{
constexpr int Digits = std::numeric_limits<T>::digits;
unsigned n = unsigned(s) % Digits;
return (v >> n) | (v << (Digits - n));
}
#endif // __cpp_lib_bitops
#if defined(__cpp_lib_int_pow2)
using std::bit_ceil;
using std::bit_floor;
using std::bit_width;
#else
template <typename T> constexpr std::enable_if_t<std::is_unsigned_v<T>, T>
bit_ceil(T v) noexcept
{
// Difference from standard: we do not enforce UB
constexpr int Digits = std::numeric_limits<T>::digits;
if (v <= 1)
return 1;
return T(1) << (Digits - countl_zero(T(v - 1)));
}
template <typename T> constexpr std::enable_if_t<std::is_unsigned_v<T>, T>
bit_width(T v) noexcept
{
return std::numeric_limits<T>::digits - countl_zero(v);
}
template <typename T> constexpr std::enable_if_t<std::is_unsigned_v<T>, T>
bit_floor(T v) noexcept
{
return v ? T(1) << (bit_width(v) - 1) : 0;
}
#endif // __cpp_lib_int_pow2
} // namespace q20
QT_END_NAMESPACE
#endif // Q20BIT_H