diff options
Diffstat (limited to 'src/corelib/global/qnumeric.h')
-rw-r--r-- | src/corelib/global/qnumeric.h | 415 |
1 files changed, 376 insertions, 39 deletions
diff --git a/src/corelib/global/qnumeric.h b/src/corelib/global/qnumeric.h index 2771eea64f..2238c13da0 100644 --- a/src/corelib/global/qnumeric.h +++ b/src/corelib/global/qnumeric.h @@ -1,49 +1,61 @@ -/**************************************************************************** -** -** Copyright (C) 2019 The Qt Company Ltd. -** Contact: https://www.qt.io/licensing/ -** -** This file is part of the QtCore module of the Qt Toolkit. -** -** $QT_BEGIN_LICENSE:LGPL$ -** Commercial License Usage -** Licensees holding valid commercial Qt licenses may use this file in -** accordance with the commercial license agreement provided with the -** Software or, alternatively, in accordance with the terms contained in -** a written agreement between you and The Qt Company. For licensing terms -** and conditions see https://www.qt.io/terms-conditions. For further -** information use the contact form at https://www.qt.io/contact-us. -** -** GNU Lesser General Public License Usage -** Alternatively, this file may be used under the terms of the GNU Lesser -** General Public License version 3 as published by the Free Software -** Foundation and appearing in the file LICENSE.LGPL3 included in the -** packaging of this file. Please review the following information to -** ensure the GNU Lesser General Public License version 3 requirements -** will be met: https://www.gnu.org/licenses/lgpl-3.0.html. -** -** GNU General Public License Usage -** Alternatively, this file may be used under the terms of the GNU -** General Public License version 2.0 or (at your option) the GNU General -** Public license version 3 or any later version approved by the KDE Free -** Qt Foundation. The licenses are as published by the Free Software -** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3 -** included in the packaging of this file. Please review the following -** information to ensure the GNU General Public License requirements will -** be met: https://www.gnu.org/licenses/gpl-2.0.html and -** https://www.gnu.org/licenses/gpl-3.0.html. -** -** $QT_END_LICENSE$ -** -****************************************************************************/ +// Copyright (C) 2021 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 #ifndef QNUMERIC_H #define QNUMERIC_H -#include <QtCore/qglobal.h> +#if 0 +#pragma qt_class(QtNumeric) +#endif + +#include <QtCore/qtconfigmacros.h> +#include <QtCore/qtcoreexports.h> +#include <QtCore/qtypes.h> + +#include <cmath> +#include <limits> +#include <type_traits> + +// min() and max() may be #defined by windows.h if that is included before, but we need them +// for std::numeric_limits below. You should not use the min() and max() macros, so we just #undef. +#ifdef min +# undef min +# undef max +#endif + +#if defined(Q_CC_MSVC) +# include <intrin.h> +# include <float.h> +# if defined(Q_PROCESSOR_X86_64) || defined(Q_PROCESSOR_ARM_64) +# define Q_INTRINSIC_MUL_OVERFLOW64 +# define Q_UMULH(v1, v2) __umulh(v1, v2); +# define Q_SMULH(v1, v2) __mulh(v1, v2); +# pragma intrinsic(__umulh) +# pragma intrinsic(__mulh) +# endif +#endif + +# if defined(Q_OS_INTEGRITY) && defined(Q_PROCESSOR_ARM_64) +# include <arm64_ghs.h> +# define Q_INTRINSIC_MUL_OVERFLOW64 +# define Q_UMULH(v1, v2) __MULUH64(v1, v2); +# define Q_SMULH(v1, v2) __MULSH64(v1, v2); +#endif QT_BEGIN_NAMESPACE +// To match std::is{inf,nan,finite} functions: +template <typename T> +constexpr typename std::enable_if<std::is_integral<T>::value, bool>::type +qIsInf(T) { return false; } +template <typename T> +constexpr typename std::enable_if<std::is_integral<T>::value, bool>::type +qIsNaN(T) { return false; } +template <typename T> +constexpr typename std::enable_if<std::is_integral<T>::value, bool>::type +qIsFinite(T) { return true; } + +// Floating-point types (see qfloat16.h for its overloads). Q_CORE_EXPORT Q_DECL_CONST_FUNCTION bool qIsInf(double d); Q_CORE_EXPORT Q_DECL_CONST_FUNCTION bool qIsNaN(double d); Q_CORE_EXPORT Q_DECL_CONST_FUNCTION bool qIsFinite(double d); @@ -52,6 +64,7 @@ Q_CORE_EXPORT Q_DECL_CONST_FUNCTION bool qIsInf(float f); Q_CORE_EXPORT Q_DECL_CONST_FUNCTION bool qIsNaN(float f); Q_CORE_EXPORT Q_DECL_CONST_FUNCTION bool qIsFinite(float f); Q_CORE_EXPORT Q_DECL_CONST_FUNCTION int qFpClassify(float val); + #if QT_CONFIG(signaling_nan) Q_CORE_EXPORT Q_DECL_CONST_FUNCTION double qSNaN(); #endif @@ -67,6 +80,330 @@ Q_CORE_EXPORT quint64 qFloatDistance(double a, double b); #endif #define Q_QNAN (QT_PREPEND_NAMESPACE(qQNaN)()) +// Overflow math. +// This provides efficient implementations for int, unsigned, qsizetype and +// size_t. Implementations for 8- and 16-bit types will work but may not be as +// efficient. Implementations for 64-bit may be missing on 32-bit platforms. + +#if (Q_CC_GNU >= 500 || __has_builtin(__builtin_add_overflow)) \ + && !(QT_POINTER_SIZE == 4 && defined(Q_CC_CLANG)) +// GCC 5 and Clang 3.8 have builtins to detect overflows +// 32 bit Clang has the builtins but tries to link a library which hasn't +#define Q_INTRINSIC_MUL_OVERFLOW64 + +template <typename T> inline +typename std::enable_if_t<std::is_unsigned_v<T> || std::is_signed_v<T>, bool> +qAddOverflow(T v1, T v2, T *r) +{ return __builtin_add_overflow(v1, v2, r); } + +template <typename T> inline +typename std::enable_if_t<std::is_unsigned_v<T> || std::is_signed_v<T>, bool> +qSubOverflow(T v1, T v2, T *r) +{ return __builtin_sub_overflow(v1, v2, r); } + +template <typename T> inline +typename std::enable_if_t<std::is_unsigned_v<T> || std::is_signed_v<T>, bool> +qMulOverflow(T v1, T v2, T *r) +{ return __builtin_mul_overflow(v1, v2, r); } + +#else +// Generic implementations + +template <typename T> inline typename std::enable_if_t<std::is_unsigned_v<T>, bool> +qAddOverflow(T v1, T v2, T *r) +{ + // unsigned additions are well-defined + *r = v1 + v2; + return v1 > T(v1 + v2); +} + +template <typename T> inline typename std::enable_if_t<std::is_signed_v<T>, bool> +qAddOverflow(T v1, T v2, T *r) +{ + // Here's how we calculate the overflow: + // 1) unsigned addition is well-defined, so we can always execute it + // 2) conversion from unsigned back to signed is implementation- + // defined and in the implementations we use, it's a no-op. + // 3) signed integer overflow happens if the sign of the two input operands + // is the same but the sign of the result is different. In other words, + // the sign of the result must be the same as the sign of either + // operand. + + using U = typename std::make_unsigned_t<T>; + *r = T(U(v1) + U(v2)); + + // If int is two's complement, assume all integer types are too. + if (std::is_same_v<int32_t, int>) { + // Two's complement equivalent (generates slightly shorter code): + // x ^ y is negative if x and y have different signs + // x & y is negative if x and y are negative + // (x ^ z) & (y ^ z) is negative if x and z have different signs + // AND y and z have different signs + return ((v1 ^ *r) & (v2 ^ *r)) < 0; + } + + bool s1 = (v1 < 0); + bool s2 = (v2 < 0); + bool sr = (*r < 0); + return s1 != sr && s2 != sr; + // also: return s1 == s2 && s1 != sr; +} + +template <typename T> inline typename std::enable_if_t<std::is_unsigned_v<T>, bool> +qSubOverflow(T v1, T v2, T *r) +{ + // unsigned subtractions are well-defined + *r = v1 - v2; + return v1 < v2; +} + +template <typename T> inline typename std::enable_if_t<std::is_signed_v<T>, bool> +qSubOverflow(T v1, T v2, T *r) +{ + // See above for explanation. This is the same with some signs reversed. + // We can't use qAddOverflow(v1, -v2, r) because it would be UB if + // v2 == std::numeric_limits<T>::min(). + + using U = typename std::make_unsigned_t<T>; + *r = T(U(v1) - U(v2)); + + if (std::is_same_v<int32_t, int>) + return ((v1 ^ *r) & (~v2 ^ *r)) < 0; + + bool s1 = (v1 < 0); + bool s2 = !(v2 < 0); + bool sr = (*r < 0); + return s1 != sr && s2 != sr; + // also: return s1 == s2 && s1 != sr; +} + +template <typename T> inline +typename std::enable_if_t<std::is_unsigned_v<T> || std::is_signed_v<T>, bool> +qMulOverflow(T v1, T v2, T *r) +{ + // use the next biggest type + // Note: for 64-bit systems where __int128 isn't supported, this will cause an error. + using LargerInt = QIntegerForSize<sizeof(T) * 2>; + using Larger = typename std::conditional_t<std::is_signed_v<T>, + typename LargerInt::Signed, typename LargerInt::Unsigned>; + Larger lr = Larger(v1) * Larger(v2); + *r = T(lr); + return lr > (std::numeric_limits<T>::max)() || lr < (std::numeric_limits<T>::min)(); +} + +# if defined(Q_INTRINSIC_MUL_OVERFLOW64) +template <> inline bool qMulOverflow(quint64 v1, quint64 v2, quint64 *r) +{ + *r = v1 * v2; + return Q_UMULH(v1, v2); +} +template <> inline bool qMulOverflow(qint64 v1, qint64 v2, qint64 *r) +{ + // This is slightly more complex than the unsigned case above: the sign bit + // of 'low' must be replicated as the entire 'high', so the only valid + // values for 'high' are 0 and -1. Use unsigned multiply since it's the same + // as signed for the low bits and use a signed right shift to verify that + // 'high' is nothing but sign bits that match the sign of 'low'. + + qint64 high = Q_SMULH(v1, v2); + *r = qint64(quint64(v1) * quint64(v2)); + return (*r >> 63) != high; +} + +# if defined(Q_OS_INTEGRITY) && defined(Q_PROCESSOR_ARM_64) +template <> inline bool qMulOverflow(uint64_t v1, uint64_t v2, uint64_t *r) +{ + return qMulOverflow<quint64>(v1,v2,reinterpret_cast<quint64*>(r)); +} + +template <> inline bool qMulOverflow(int64_t v1, int64_t v2, int64_t *r) +{ + return qMulOverflow<qint64>(v1,v2,reinterpret_cast<qint64*>(r)); +} +# endif // OS_INTEGRITY ARM64 +# endif // Q_INTRINSIC_MUL_OVERFLOW64 + +# if defined(Q_CC_MSVC) && defined(Q_PROCESSOR_X86) +// We can use intrinsics for the unsigned operations with MSVC +template <> inline bool qAddOverflow(unsigned v1, unsigned v2, unsigned *r) +{ return _addcarry_u32(0, v1, v2, r); } + +// 32-bit qMulOverflow is fine with the generic code above + +template <> inline bool qAddOverflow(quint64 v1, quint64 v2, quint64 *r) +{ +# if defined(Q_PROCESSOR_X86_64) + return _addcarry_u64(0, v1, v2, reinterpret_cast<unsigned __int64 *>(r)); +# else + uint low, high; + uchar carry = _addcarry_u32(0, unsigned(v1), unsigned(v2), &low); + carry = _addcarry_u32(carry, v1 >> 32, v2 >> 32, &high); + *r = (quint64(high) << 32) | low; + return carry; +# endif // !x86-64 +} +# endif // MSVC X86 +#endif // !GCC + +// Implementations for addition, subtraction or multiplication by a +// compile-time constant. For addition and subtraction, we simply call the code +// that detects overflow at runtime. For multiplication, we compare to the +// maximum possible values before multiplying to ensure no overflow happens. + +template <typename T, T V2> bool qAddOverflow(T v1, std::integral_constant<T, V2>, T *r) +{ + return qAddOverflow(v1, V2, r); +} + +template <auto V2, typename T> bool qAddOverflow(T v1, T *r) +{ + return qAddOverflow(v1, std::integral_constant<T, V2>{}, r); +} + +template <typename T, T V2> bool qSubOverflow(T v1, std::integral_constant<T, V2>, T *r) +{ + return qSubOverflow(v1, V2, r); +} + +template <auto V2, typename T> bool qSubOverflow(T v1, T *r) +{ + return qSubOverflow(v1, std::integral_constant<T, V2>{}, r); +} + +template <typename T, T V2> bool qMulOverflow(T v1, std::integral_constant<T, V2>, T *r) +{ + // Runtime detection for anything smaller than or equal to a register + // width, as most architectures' multiplication instructions actually + // produce a result twice as wide as the input registers, allowing us to + // efficiently detect the overflow. + if constexpr (sizeof(T) <= sizeof(qregisteruint)) { + return qMulOverflow(v1, V2, r); + +#ifdef Q_INTRINSIC_MUL_OVERFLOW64 + } else if constexpr (sizeof(T) <= sizeof(quint64)) { + // If we have intrinsics detecting overflow of 64-bit multiplications, + // then detect overflows through them up to 64 bits. + return qMulOverflow(v1, V2, r); +#endif + + } else if constexpr (V2 == 0 || V2 == 1) { + // trivial cases (and simplify logic below due to division by zero) + *r = v1 * V2; + return false; + } else if constexpr (V2 == -1) { + // multiplication by -1 is valid *except* for signed minimum values + // (necessary to avoid diving min() by -1, which is an overflow) + if (v1 < 0 && v1 == (std::numeric_limits<T>::min)()) + return true; + *r = -v1; + return false; + } else { + // For 64-bit multiplications on 32-bit platforms, let's instead compare v1 + // against the bounds that would overflow. + constexpr T Highest = (std::numeric_limits<T>::max)() / V2; + constexpr T Lowest = (std::numeric_limits<T>::min)() / V2; + if constexpr (Highest > Lowest) { + if (v1 > Highest || v1 < Lowest) + return true; + } else { + // this can only happen if V2 < 0 + static_assert(V2 < 0); + if (v1 > Lowest || v1 < Highest) + return true; + } + + *r = v1 * V2; + return false; + } +} + +template <auto V2, typename T> bool qMulOverflow(T v1, T *r) +{ + if constexpr (V2 == 2) + return qAddOverflow(v1, v1, r); + return qMulOverflow(v1, std::integral_constant<T, V2>{}, r); +} + +template <typename T> +constexpr inline T qAbs(const T &t) { return t >= 0 ? t : -t; } + +// gcc < 10 doesn't have __has_builtin +#if defined(Q_PROCESSOR_ARM_64) && (__has_builtin(__builtin_round) || defined(Q_CC_GNU)) && !defined(Q_CC_CLANG) +// ARM64 has a single instruction that can do C++ rounding with conversion to integer. +// Note current clang versions have non-constexpr __builtin_round, ### allow clang this path when they fix it. +constexpr inline int qRound(double d) +{ return int(__builtin_round(d)); } +constexpr inline int qRound(float f) +{ return int(__builtin_roundf(f)); } +constexpr inline qint64 qRound64(double d) +{ return qint64(__builtin_round(d)); } +constexpr inline qint64 qRound64(float f) +{ return qint64(__builtin_roundf(f)); } +#elif defined(__SSE2__) && (__has_builtin(__builtin_copysign) || defined(Q_CC_GNU)) +// SSE has binary operations directly on floating point making copysign fast +constexpr inline int qRound(double d) +{ return int(d + __builtin_copysign(0.5, d)); } +constexpr inline int qRound(float f) +{ return int(f + __builtin_copysignf(0.5f, f)); } +constexpr inline qint64 qRound64(double d) +{ return qint64(d + __builtin_copysign(0.5, d)); } +constexpr inline qint64 qRound64(float f) +{ return qint64(f + __builtin_copysignf(0.5f, f)); } +#else +constexpr inline int qRound(double d) +{ return d >= 0.0 ? int(d + 0.5) : int(d - 0.5); } +constexpr inline int qRound(float d) +{ return d >= 0.0f ? int(d + 0.5f) : int(d - 0.5f); } + +constexpr inline qint64 qRound64(double d) +{ return d >= 0.0 ? qint64(d + 0.5) : qint64(d - 0.5); } +constexpr inline qint64 qRound64(float d) +{ return d >= 0.0f ? qint64(d + 0.5f) : qint64(d - 0.5f); } +#endif + +namespace QtPrivate { +template <typename T> +constexpr inline const T &min(const T &a, const T &b) { return (a < b) ? a : b; } +} + +[[nodiscard]] constexpr bool qFuzzyCompare(double p1, double p2) +{ + return (qAbs(p1 - p2) * 1000000000000. <= QtPrivate::min(qAbs(p1), qAbs(p2))); +} + +[[nodiscard]] constexpr bool qFuzzyCompare(float p1, float p2) +{ + return (qAbs(p1 - p2) * 100000.f <= QtPrivate::min(qAbs(p1), qAbs(p2))); +} + +[[nodiscard]] constexpr bool qFuzzyIsNull(double d) +{ + return qAbs(d) <= 0.000000000001; +} + +[[nodiscard]] constexpr bool qFuzzyIsNull(float f) +{ + return qAbs(f) <= 0.00001f; +} + +QT_WARNING_PUSH +QT_WARNING_DISABLE_FLOAT_COMPARE + +[[nodiscard]] constexpr bool qIsNull(double d) noexcept +{ + return d == 0.0; +} + +[[nodiscard]] constexpr bool qIsNull(float f) noexcept +{ + return f == 0.0f; +} + +QT_WARNING_POP + +inline int qIntCast(double f) { return int(f); } +inline int qIntCast(float f) { return int(f); } + QT_END_NAMESPACE #endif // QNUMERIC_H |