include/QtCore/q20bit.h

0001 // Copyright (C) 2025 Intel Corporation.
0002 // Copyright (C) 2020 The Qt Company Ltd.
0003 // SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
0004 // Qt-Security score:significant reason:default
0005
0006 #ifndef Q20BIT_H
0007 #define Q20BIT_H
0008
0009 #include <QtCore/q20type_traits.h>
0010
0011 #if defined(__cpp_lib_bitops) || defined(__cpp_lib_int_pow2)
0012 #  include <bit>
0013 #else
0014 #  include <QtCore/qtypes.h>
0015 #  include <limits>
0016
0017 #  ifdef Q_CC_MSVC
0018 // avoiding qsimd.h -> immintrin.h unless necessary, because it increases
0019 // compilation time
0020 #    include <QtCore/qsimd.h>
0021 #    include <intrin.h>
0022 #  endif
0023 #endif
0024
0025 //
0026 //  W A R N I N G
0027 //  -------------
0028 //
0029 // This file is not part of the Qt API. Types and functions defined in this
0030 // file can reliably be replaced by their std counterparts, once available.
0031 // You may use these definitions in your own code, but be aware that we
0032 // will remove them once Qt depends on the C++ version that supports
0033 // them in namespace std. There will be NO deprecation warning, the
0034 // definitions will JUST go away.
0035 //
0036 // If you can't agree to these terms, don't use these definitions!
0037 //
0038 // We mean it.
0039 //
0040
0041 QT_BEGIN_NAMESPACE
0042
0043 namespace q20 {
0044 #if defined(__cpp_lib_bitops)
0045 using std::countl_zero;
0046 using std::countr_zero;
0047 using std::popcount;
0048 using std::rotl;
0049 using std::rotr;
0050 #else
0051 namespace detail {
0052 template <typename T> /*non-constexpr*/ inline auto hw_popcount(T v) noexcept
0053 {
0054 #if defined(Q_CC_MSVC) && defined(Q_PROCESSOR_X86) && defined(__POPCNT__)
0055     // Note: __POPCNT__ comes from qsimd.h, not the compiler.
0056 #  ifdef Q_PROCESSOR_X86_64
0057     if constexpr (sizeof(T) == sizeof(quint64))
0058         return int(__popcnt64(v));
0059 #  endif
0060     if constexpr (sizeof(T) == sizeof(quint64))
0061         return int(__popcnt(quint32(v)) + __popcnt(quint32(v >> 32)));
0062     if constexpr (sizeof(T) == sizeof(quint32))
0063         return int(__popcnt(v));
0064     return int(__popcnt16(v));
0065 #else
0066     Q_UNUSED(v);
0067 #endif
0068 }
0069
0070 template <typename T> /*non-constexpr*/ inline auto hw_countl_zero(T v) noexcept
0071 {
0072 #if defined(Q_CC_MSVC) && defined(Q_PROCESSOR_X86) && defined(__LZCNT__)
0073     // Note: __LZCNT__ comes from qsimd.h, not the compiler
0074 #  if defined(Q_PROCESSOR_X86_64)
0075     if constexpr (sizeof(T) == sizeof(quint64))
0076         return int(__lzcnt64(v));
0077 #  endif
0078     if constexpr (sizeof(T) == sizeof(quint32))
0079         return int(__lzcnt(v));
0080     if constexpr (sizeof(T) == sizeof(quint16))
0081         return int(__lzcnt16(v));
0082     if constexpr (sizeof(T) == sizeof(quint8))
0083         return int(__lzcnt(v)) - 24;
0084 #endif
0085 #if defined(Q_CC_MSVC) && defined(Q_PROCESSOR_X86)
0086     constexpr int Digits = std::numeric_limits<T>::digits;
0087     unsigned long result;
0088
0089     if constexpr (sizeof(T) == sizeof(quint64)) {
0090 #  ifdef Q_PROCESSOR_X86_64
0091         if (_BitScanReverse64(&result, v) == 0)
0092             return Digits;
0093 #  else
0094         if (quint32 h = quint32(v >> 32))
0095             return hw_countl_zero(h);
0096         return hw_countl_zero(quint32(v)) + 32;
0097 #  endif
0098     } else {
0099         if (_BitScanReverse(&result, v) == 0)
0100             return Digits;
0101     }
0102
0103     // Now Invert the result: clz will count *down* from the msb to the lsb, so the msb index is 31
0104     // and the lsb index is 0. The result for the index when counting up: msb index is 0 (because it
0105     // starts there), and the lsb index is 31.
0106     result ^= sizeof(T) * 8 - 1;
0107     return int(result);
0108 #else
0109     Q_UNUSED(v);
0110 #endif
0111 }
0112
0113 template <typename T> /*non-constexpr*/ inline auto hw_countr_zero(T v) noexcept
0114 {
0115 #if defined(Q_CC_MSVC) && defined(Q_PROCESSOR_X86) && defined(__BMI__)
0116     // Note: __BMI__ comes from qsimd.h, not the compiler
0117 #  if defined(Q_PROCESSOR_X86_64)
0118     if constexpr (sizeof(T) == sizeof(quint64))
0119         return int(_tzcnt_u64(v));
0120 #  endif
0121     if constexpr (sizeof(T) == sizeof(quint32))
0122         return int(_tzcnt_u32(v));
0123     // No _tzcnt_u16 or u8 intrinsics
0124 #endif
0125 #if defined(Q_CC_MSVC) && defined(Q_PROCESSOR_X86)
0126     constexpr int Digits = std::numeric_limits<T>::digits;
0127     unsigned long result;
0128     if constexpr (sizeof(T) <= sizeof(quint32))
0129         return _BitScanForward(&result, v) ? int(result) : Digits;
0130 #  ifdef Q_PROCESSOR_X86_64
0131     return _BitScanForward64(&result, v) ? int(result) : Digits;
0132 #  endif
0133 #else
0134     Q_UNUSED(v);
0135 #endif
0136 }
0137 } // namespace q20::detail
0138
0139 template <typename T> constexpr std::enable_if_t<std::is_unsigned_v<T>, int>
0140 popcount(T v) noexcept
0141 {
0142 #if __has_builtin(__builtin_popcountg)
0143     return __builtin_popcountg(v);
0144 #endif
0145
0146     if constexpr (sizeof(T) > sizeof(quint64)) {
0147         static_assert(sizeof(T) == 16, "Unsupported integer size");
0148         return popcount(quint64(v)) + popcount(quint64(v >> 64));
0149     }
0150
0151 #  if __has_builtin(__builtin_popcount)
0152     // These GCC/Clang intrinsics are constexpr and use the HW instructions
0153     // where available. Note: no runtime detection.
0154     if constexpr (sizeof(T) > sizeof(quint32))
0155         return __builtin_popcountll(v);
0156     return __builtin_popcount(v);
0157 #  endif
0158
0159 #  ifdef QT_SUPPORTS_IS_CONSTANT_EVALUATED
0160     // Try hardware functions if not constexpr. Note: no runtime detection.
0161     if (!is_constant_evaluated()) {
0162         if constexpr (std::is_integral_v<decltype(detail::hw_popcount(v))>)
0163             return detail::hw_popcount(v);
0164     }
0165 #  endif
0166
0167     constexpr int Digits = std::numeric_limits<T>::digits;
0168     int r =  (((v      ) & 0xfff)    * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f;
0169     if constexpr (Digits > 12)
0170         r += (((v >> 12) & 0xfff)    * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f;
0171     if constexpr (Digits > 24)
0172         r += (((v >> 24) & 0xfff)    * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f;
0173     if constexpr (Digits > 36) {
0174         r += (((v >> 36) & 0xfff)    * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f +
0175              (((v >> 48) & 0xfff)    * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f +
0176              (((v >> 60) & 0xfff)    * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f;
0177     }
0178     return r;
0179 }
0180
0181 template <typename T> constexpr std::enable_if_t<std::is_unsigned_v<T>, int>
0182 countl_zero(T v) noexcept
0183 {
0184 #if __has_builtin(__builtin_clzg)
0185     // "If two arguments are specified, and first argument is 0, the result is
0186     // the second argument."
0187     return __builtin_clzg(v, std::numeric_limits<T>::digits);
0188 #endif
0189
0190     if constexpr (sizeof(T) > sizeof(quint64)) {
0191         static_assert(sizeof(T) == 16, "Unsupported integer size");
0192         if (quint64 h = quint64(v >> 64))
0193             return countl_zero(h);
0194         return countl_zero(quint64(v)) + 64;
0195     }
0196
0197 #if __has_builtin(__builtin_clz)
0198     // These GCC/Clang intrinsics are constexpr and use the HW instructions
0199     // where available.
0200     if (!v)
0201         return std::numeric_limits<T>::digits;
0202     if constexpr (sizeof(T) == sizeof(quint64))
0203         return __builtin_clzll(v);
0204 #  if __has_builtin(__builtin_clzs)
0205     if constexpr (sizeof(T) == sizeof(quint16))
0206         return __builtin_clzs(v);
0207 #  endif
0208     return __builtin_clz(v) - (32 - std::numeric_limits<T>::digits);
0209 #endif
0210
0211 #ifdef QT_SUPPORTS_IS_CONSTANT_EVALUATED
0212     // Try hardware functions if not constexpr. Note: no runtime detection.
0213     if (!is_constant_evaluated()) {
0214         if constexpr (std::is_integral_v<decltype(detail::hw_countl_zero(v))>)
0215             return detail::hw_countl_zero(v);
0216     }
0217 #endif
0218
0219     // Hacker's Delight, 2nd ed. Fig 5-16, p. 102
0220     v = v | (v >> 1);
0221     v = v | (v >> 2);
0222     v = v | (v >> 4);
0223     if constexpr (sizeof(T) > sizeof(quint8))
0224         v = v | (v >> 8);
0225     if constexpr (sizeof(T) > sizeof(quint16))
0226         v = v | (v >> 16);
0227     if constexpr (sizeof(T) > sizeof(quint32))
0228         v = v | (v >> 32);
0229     return popcount(T(~v));
0230 }
0231
0232 template <typename T> constexpr std::enable_if_t<std::is_unsigned_v<T>, int>
0233 countr_zero(T v) noexcept
0234 {
0235 #if __has_builtin(__builtin_ctzg)
0236     // "If two arguments are specified, and first argument is 0, the result is
0237     // the second argument."
0238     return __builtin_ctzg(v, std::numeric_limits<T>::digits);
0239 #endif
0240
0241     if constexpr (sizeof(T) > sizeof(quint64)) {
0242         static_assert(sizeof(T) == 16, "Unsupported integer size");
0243         quint64 l = quint64(v);
0244         return l ? countr_zero(l) : 64 + countr_zero(quint64(v >> 64));
0245     }
0246
0247 #if __has_builtin(__builtin_ctz)
0248     // These GCC/Clang intrinsics are constexpr and use the HW instructions
0249     // where available.
0250     if (!v)
0251         return std::numeric_limits<T>::digits;
0252     if constexpr (sizeof(T) == sizeof(quint64))
0253         return __builtin_ctzll(v);
0254 #  if __has_builtin(__builtin_ctzs)
0255     if constexpr (sizeof(T) == sizeof(quint16))
0256         return __builtin_ctzs(v);
0257 #  endif
0258     return __builtin_ctz(v);
0259 #endif
0260
0261 #ifdef QT_SUPPORTS_IS_CONSTANT_EVALUATED
0262     // Try hardware functions if not constexpr. Note: no runtime detection.
0263     if (!is_constant_evaluated()) {
0264         if constexpr (std::is_integral_v<decltype(detail::hw_countr_zero(v))>)
0265             return detail::hw_countr_zero(v);
0266     }
0267 #endif
0268
0269     if constexpr (sizeof(T) > sizeof(quint32)) {
0270         quint32 l = quint32(v);
0271         return l ? countr_zero(l) : 32 + countr_zero(quint32(v >> 32));
0272     }
0273
0274     // see http://graphics.stanford.edu/~seander/bithacks.html#ZerosOnRightParallel
0275     int c = std::numeric_limits<T>::digits; // c will be the number of zero bits on the right
0276 QT_WARNING_PUSH
0277 QT_WARNING_DISABLE_MSVC(4146)   // unary minus operator applied to unsigned type, result still unsigned
0278     v &= T(-v);
0279 QT_WARNING_POP
0280     if (v) c--;
0281     if constexpr (sizeof(T) == sizeof(quint32)) {
0282         if (v & 0x0000FFFF) c -= 16;
0283         if (v & 0x00FF00FF) c -= 8;
0284         if (v & 0x0F0F0F0F) c -= 4;
0285         if (v & 0x33333333) c -= 2;
0286         if (v & 0x55555555) c -= 1;
0287     } else if constexpr (sizeof(T) == sizeof(quint16)) {
0288         if (v & 0x000000FF) c -= 8;
0289         if (v & 0x00000F0F) c -= 4;
0290         if (v & 0x00003333) c -= 2;
0291         if (v & 0x00005555) c -= 1;
0292     } else /*if constexpr (sizeof(T) == sizeof(quint8))*/ {
0293         if (v & 0x0000000F) c -= 4;
0294         if (v & 0x00000033) c -= 2;
0295         if (v & 0x00000055) c -= 1;
0296     }
0297     return c;
0298 }
0299
0300 template <typename T> constexpr std::enable_if_t<std::is_unsigned_v<T>, T>
0301 rotl(T v, int s) noexcept
0302 {
0303     constexpr int Digits = std::numeric_limits<T>::digits;
0304     unsigned n = unsigned(s) % Digits;
0305     return (v << n) | (v >> (Digits - n));
0306 }
0307
0308 template <typename T> constexpr std::enable_if_t<std::is_unsigned_v<T>, T>
0309 rotr(T v, int s) noexcept
0310 {
0311     constexpr int Digits = std::numeric_limits<T>::digits;
0312     unsigned n = unsigned(s) % Digits;
0313     return (v >> n) | (v << (Digits - n));
0314 }
0315 #endif // __cpp_lib_bitops
0316
0317 #if defined(__cpp_lib_int_pow2)
0318 using std::bit_ceil;
0319 using std::bit_floor;
0320 using std::bit_width;
0321 #else
0322 template <typename T> constexpr std::enable_if_t<std::is_unsigned_v<T>, T>
0323 bit_ceil(T v) noexcept
0324 {
0325     // Difference from standard: we do not enforce UB
0326     constexpr int Digits = std::numeric_limits<T>::digits;
0327     if (v <= 1)
0328         return 1;
0329     return T(1) << (Digits - countl_zero(T(v - 1)));
0330 }
0331
0332 template <typename T> constexpr std::enable_if_t<std::is_unsigned_v<T>, T>
0333 bit_width(T v) noexcept
0334 {
0335     return std::numeric_limits<T>::digits - countl_zero(v);
0336 }
0337
0338 template <typename T> constexpr std::enable_if_t<std::is_unsigned_v<T>, T>
0339 bit_floor(T v) noexcept
0340 {
0341     return v ? T(1) << (bit_width(v) - 1) : 0;
0342 }
0343 #endif // __cpp_lib_int_pow2
0344 } // namespace q20
0345
0346 QT_END_NAMESPACE
0347
0348 #endif // Q20BIT_H