1/****************************************************************************
2**
3** Copyright (C) 2020 The Qt Company Ltd.
4** Copyright (C) 2020 Intel Corporation.
5** Contact: https://www.qt.io/licensing/
6**
7** This file is part of the QtCore module of the Qt Toolkit.
8**
9** $QT_BEGIN_LICENSE:LGPL$
10** Commercial License Usage
11** Licensees holding valid commercial Qt licenses may use this file in
12** accordance with the commercial license agreement provided with the
13** Software or, alternatively, in accordance with the terms contained in
14** a written agreement between you and The Qt Company. For licensing terms
15** and conditions see https://www.qt.io/terms-conditions. For further
16** information use the contact form at https://www.qt.io/contact-us.
17**
18** GNU Lesser General Public License Usage
19** Alternatively, this file may be used under the terms of the GNU Lesser
20** General Public License version 3 as published by the Free Software
21** Foundation and appearing in the file LICENSE.LGPL3 included in the
22** packaging of this file. Please review the following information to
23** ensure the GNU Lesser General Public License version 3 requirements
24** will be met: https://www.gnu.org/licenses/lgpl-3.0.html.
25**
26** GNU General Public License Usage
27** Alternatively, this file may be used under the terms of the GNU
28** General Public License version 2.0 or (at your option) the GNU General
29** Public license version 3 or any later version approved by the KDE Free
30** Qt Foundation. The licenses are as published by the Free Software
31** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3
32** included in the packaging of this file. Please review the following
33** information to ensure the GNU General Public License requirements will
34** be met: https://www.gnu.org/licenses/gpl-2.0.html and
35** https://www.gnu.org/licenses/gpl-3.0.html.
36**
37** $QT_END_LICENSE$
38**
39****************************************************************************/
40
41#ifndef QNUMERIC_P_H
42#define QNUMERIC_P_H
43
44//
45// W A R N I N G
46// -------------
47//
48// This file is not part of the Qt API. It exists purely as an
49// implementation detail. This header file may change from version to
50// version without notice, or even be removed.
51//
52// We mean it.
53//
54
55#include "QtCore/private/qglobal_p.h"
56#include <cmath>
57#include <limits>
58#include <type_traits>
59
60#if defined(Q_CC_MSVC)
61# include <intrin.h>
62# include <float.h>
63# if defined(Q_PROCESSOR_X86_64) || defined(Q_PROCESSOR_ARM_64)
64# define Q_INTRINSIC_MUL_OVERFLOW64
65# define Q_UMULH(v1, v2) __umulh(v1, v2);
66# define Q_SMULH(v1, v2) __mulh(v1, v2);
67# pragma intrinsic(__umulh)
68# pragma intrinsic(__mulh)
69# endif
70#endif
71
72# if defined(Q_OS_INTEGRITY) && defined(Q_PROCESSOR_ARM_64)
73#include <arm64_ghs.h>
74# define Q_INTRINSIC_MUL_OVERFLOW64
75# define Q_UMULH(v1, v2) __MULUH64(v1, v2);
76# define Q_SMULH(v1, v2) __MULSH64(v1, v2);
77#endif
78
79#if !defined(Q_CC_MSVC) && (defined(Q_OS_QNX) || defined(Q_CC_INTEL))
80# include <math.h>
81# ifdef isnan
82# define QT_MATH_H_DEFINES_MACROS
83QT_BEGIN_NAMESPACE
84namespace qnumeric_std_wrapper {
85// the 'using namespace std' below is cases where the stdlib already put the math.h functions in the std namespace and undefined the macros.
86Q_DECL_CONST_FUNCTION static inline bool math_h_isnan(double d) { using namespace std; return isnan(d); }
87Q_DECL_CONST_FUNCTION static inline bool math_h_isinf(double d) { using namespace std; return isinf(d); }
88Q_DECL_CONST_FUNCTION static inline bool math_h_isfinite(double d) { using namespace std; return isfinite(d); }
89Q_DECL_CONST_FUNCTION static inline int math_h_fpclassify(double d) { using namespace std; return fpclassify(d); }
90Q_DECL_CONST_FUNCTION static inline bool math_h_isnan(float f) { using namespace std; return isnan(f); }
91Q_DECL_CONST_FUNCTION static inline bool math_h_isinf(float f) { using namespace std; return isinf(f); }
92Q_DECL_CONST_FUNCTION static inline bool math_h_isfinite(float f) { using namespace std; return isfinite(f); }
93Q_DECL_CONST_FUNCTION static inline int math_h_fpclassify(float f) { using namespace std; return fpclassify(f); }
94}
95QT_END_NAMESPACE
96// These macros from math.h conflict with the real functions in the std namespace.
97# undef signbit
98# undef isnan
99# undef isinf
100# undef isfinite
101# undef fpclassify
102# endif // defined(isnan)
103#endif
104
105QT_BEGIN_NAMESPACE
106
107namespace qnumeric_std_wrapper {
108#if defined(QT_MATH_H_DEFINES_MACROS)
109# undef QT_MATH_H_DEFINES_MACROS
110Q_DECL_CONST_FUNCTION static inline bool isnan(double d) { return math_h_isnan(d); }
111Q_DECL_CONST_FUNCTION static inline bool isinf(double d) { return math_h_isinf(d); }
112Q_DECL_CONST_FUNCTION static inline bool isfinite(double d) { return math_h_isfinite(d); }
113Q_DECL_CONST_FUNCTION static inline int fpclassify(double d) { return math_h_fpclassify(d); }
114Q_DECL_CONST_FUNCTION static inline bool isnan(float f) { return math_h_isnan(f); }
115Q_DECL_CONST_FUNCTION static inline bool isinf(float f) { return math_h_isinf(f); }
116Q_DECL_CONST_FUNCTION static inline bool isfinite(float f) { return math_h_isfinite(f); }
117Q_DECL_CONST_FUNCTION static inline int fpclassify(float f) { return math_h_fpclassify(f); }
118#else
119Q_DECL_CONST_FUNCTION static inline bool isnan(double d) { return std::isnan(d); }
120Q_DECL_CONST_FUNCTION static inline bool isinf(double d) { return std::isinf(d); }
121Q_DECL_CONST_FUNCTION static inline bool isfinite(double d) { return std::isfinite(d); }
122Q_DECL_CONST_FUNCTION static inline int fpclassify(double d) { return std::fpclassify(d); }
123Q_DECL_CONST_FUNCTION static inline bool isnan(float f) { return std::isnan(f); }
124Q_DECL_CONST_FUNCTION static inline bool isinf(float f) { return std::isinf(f); }
125Q_DECL_CONST_FUNCTION static inline bool isfinite(float f) { return std::isfinite(f); }
126Q_DECL_CONST_FUNCTION static inline int fpclassify(float f) { return std::fpclassify(f); }
127#endif
128}
129
130constexpr Q_DECL_CONST_FUNCTION static inline double qt_inf() noexcept
131{
132 static_assert(std::numeric_limits<double>::has_infinity,
133 "platform has no definition for infinity for type double");
134 return std::numeric_limits<double>::infinity();
135}
136
137#if QT_CONFIG(signaling_nan)
138constexpr Q_DECL_CONST_FUNCTION static inline double qt_snan() noexcept
139{
140 static_assert(std::numeric_limits<double>::has_signaling_NaN,
141 "platform has no definition for signaling NaN for type double");
142 return std::numeric_limits<double>::signaling_NaN();
143}
144#endif
145
146// Quiet NaN
147constexpr Q_DECL_CONST_FUNCTION static inline double qt_qnan() noexcept
148{
149 static_assert(std::numeric_limits<double>::has_quiet_NaN,
150 "platform has no definition for quiet NaN for type double");
151 return std::numeric_limits<double>::quiet_NaN();
152}
153
154Q_DECL_CONST_FUNCTION static inline bool qt_is_inf(double d)
155{
156 return qnumeric_std_wrapper::isinf(d);
157}
158
159Q_DECL_CONST_FUNCTION static inline bool qt_is_nan(double d)
160{
161 return qnumeric_std_wrapper::isnan(d);
162}
163
164Q_DECL_CONST_FUNCTION static inline bool qt_is_finite(double d)
165{
166 return qnumeric_std_wrapper::isfinite(d);
167}
168
169Q_DECL_CONST_FUNCTION static inline int qt_fpclassify(double d)
170{
171 return qnumeric_std_wrapper::fpclassify(d);
172}
173
174Q_DECL_CONST_FUNCTION static inline bool qt_is_inf(float f)
175{
176 return qnumeric_std_wrapper::isinf(f);
177}
178
179Q_DECL_CONST_FUNCTION static inline bool qt_is_nan(float f)
180{
181 return qnumeric_std_wrapper::isnan(f);
182}
183
184Q_DECL_CONST_FUNCTION static inline bool qt_is_finite(float f)
185{
186 return qnumeric_std_wrapper::isfinite(f);
187}
188
189Q_DECL_CONST_FUNCTION static inline int qt_fpclassify(float f)
190{
191 return qnumeric_std_wrapper::fpclassify(f);
192}
193
194#ifndef Q_CLANG_QDOC
195namespace {
196/*!
197 Returns true if the double \a v can be converted to type \c T, false if
198 it's out of range. If the conversion is successful, the converted value is
199 stored in \a value; if it was not successful, \a value will contain the
200 minimum or maximum of T, depending on the sign of \a d. If \c T is
201 unsigned, then \a value contains the absolute value of \a v.
202
203 This function works for v containing infinities, but not NaN. It's the
204 caller's responsibility to exclude that possibility before calling it.
205*/
206template<typename T>
207static inline bool convertDoubleTo(double v, T *value, bool allow_precision_upgrade = true)
208{
209 static_assert(std::numeric_limits<T>::is_integer);
210
211 // The [conv.fpint] (7.10 Floating-integral conversions) section of the C++
212 // standard says only exact conversions are guaranteed. Converting
213 // integrals to floating-point with loss of precision has implementation-
214 // defined behavior whether the next higher or next lower is returned;
215 // converting FP to integral is UB if it can't be represented.
216 //
217 // That means we can't write UINT64_MAX+1. Writing ldexp(1, 64) would be
218 // correct, but Clang, ICC and MSVC don't realize that it's a constant and
219 // the math call stays in the compiled code.
220
221 double supremum;
222 if (std::numeric_limits<T>::is_signed) {
223 supremum = -1.0 * std::numeric_limits<T>::min(); // -1 * (-2^63) = 2^63, exact (for T = qint64)
224 *value = std::numeric_limits<T>::min();
225 if (v < std::numeric_limits<T>::min())
226 return false;
227 } else {
228 using ST = typename std::make_signed<T>::type;
229 supremum = -2.0 * std::numeric_limits<ST>::min(); // -2 * (-2^63) = 2^64, exact (for T = quint64)
230 v = fabs(v);
231 }
232 if (std::is_integral<T>::value && sizeof(T) > 4 && !allow_precision_upgrade) {
233 if (v > double(Q_INT64_C(1)<<53) || v < double(-((Q_INT64_C(1)<<53) + 1)))
234 return false;
235 }
236
237 *value = std::numeric_limits<T>::max();
238 if (v >= supremum)
239 return false;
240
241 // Now we can convert, these two conversions cannot be UB
242 *value = T(v);
243
244QT_WARNING_PUSH
245QT_WARNING_DISABLE_FLOAT_COMPARE
246
247 return *value == v;
248
249QT_WARNING_POP
250}
251
252// Overflow math.
253// This provides efficient implementations for int, unsigned, qsizetype and
254// size_t. Implementations for 8- and 16-bit types will work but may not be as
255// efficient. Implementations for 64-bit may be missing on 32-bit platforms.
256
257#if ((defined(Q_CC_INTEL) ? (Q_CC_INTEL >= 1800 && !defined(Q_OS_WIN)) : defined(Q_CC_GNU)) \
258 && Q_CC_GNU >= 500) || __has_builtin(__builtin_add_overflow)
259// GCC 5, ICC 18, and Clang 3.8 have builtins to detect overflows
260#define Q_INTRINSIC_MUL_OVERFLOW64
261
262template <typename T> inline
263typename std::enable_if<std::is_unsigned<T>::value || std::is_signed<T>::value, bool>::type
264add_overflow(T v1, T v2, T *r)
265{ return __builtin_add_overflow(v1, v2, r); }
266
267template <typename T> inline
268typename std::enable_if<std::is_unsigned<T>::value || std::is_signed<T>::value, bool>::type
269sub_overflow(T v1, T v2, T *r)
270{ return __builtin_sub_overflow(v1, v2, r); }
271
272template <typename T> inline
273typename std::enable_if<std::is_unsigned<T>::value || std::is_signed<T>::value, bool>::type
274mul_overflow(T v1, T v2, T *r)
275{ return __builtin_mul_overflow(v1, v2, r); }
276
277#else
278// Generic implementations
279
280template <typename T> inline typename std::enable_if<std::is_unsigned<T>::value, bool>::type
281add_overflow(T v1, T v2, T *r)
282{
283 // unsigned additions are well-defined
284 *r = v1 + v2;
285 return v1 > T(v1 + v2);
286}
287
288template <typename T> inline typename std::enable_if<std::is_signed<T>::value, bool>::type
289add_overflow(T v1, T v2, T *r)
290{
291 // Here's how we calculate the overflow:
292 // 1) unsigned addition is well-defined, so we can always execute it
293 // 2) conversion from unsigned back to signed is implementation-
294 // defined and in the implementations we use, it's a no-op.
295 // 3) signed integer overflow happens if the sign of the two input operands
296 // is the same but the sign of the result is different. In other words,
297 // the sign of the result must be the same as the sign of either
298 // operand.
299
300 using U = typename std::make_unsigned<T>::type;
301 *r = T(U(v1) + U(v2));
302
303 // If int is two's complement, assume all integer types are too.
304 if (std::is_same<int32_t, int>::value) {
305 // Two's complement equivalent (generates slightly shorter code):
306 // x ^ y is negative if x and y have different signs
307 // x & y is negative if x and y are negative
308 // (x ^ z) & (y ^ z) is negative if x and z have different signs
309 // AND y and z have different signs
310 return ((v1 ^ *r) & (v2 ^ *r)) < 0;
311 }
312
313 bool s1 = (v1 < 0);
314 bool s2 = (v2 < 0);
315 bool sr = (*r < 0);
316 return s1 != sr && s2 != sr;
317 // also: return s1 == s2 && s1 != sr;
318}
319
320template <typename T> inline typename std::enable_if<std::is_unsigned<T>::value, bool>::type
321sub_overflow(T v1, T v2, T *r)
322{
323 // unsigned subtractions are well-defined
324 *r = v1 - v2;
325 return v1 < v2;
326}
327
328template <typename T> inline typename std::enable_if<std::is_signed<T>::value, bool>::type
329sub_overflow(T v1, T v2, T *r)
330{
331 // See above for explanation. This is the same with some signs reversed.
332 // We can't use add_overflow(v1, -v2, r) because it would be UB if
333 // v2 == std::numeric_limits<T>::min().
334
335 using U = typename std::make_unsigned<T>::type;
336 *r = T(U(v1) - U(v2));
337
338 if (std::is_same<int32_t, int>::value)
339 return ((v1 ^ *r) & (~v2 ^ *r)) < 0;
340
341 bool s1 = (v1 < 0);
342 bool s2 = !(v2 < 0);
343 bool sr = (*r < 0);
344 return s1 != sr && s2 != sr;
345 // also: return s1 == s2 && s1 != sr;
346}
347
348template <typename T> inline
349typename std::enable_if<std::is_unsigned<T>::value || std::is_signed<T>::value, bool>::type
350mul_overflow(T v1, T v2, T *r)
351{
352 // use the next biggest type
353 // Note: for 64-bit systems where __int128 isn't supported, this will cause an error.
354 using LargerInt = QIntegerForSize<sizeof(T) * 2>;
355 using Larger = typename std::conditional<std::is_signed<T>::value,
356 typename LargerInt::Signed, typename LargerInt::Unsigned>::type;
357 Larger lr = Larger(v1) * Larger(v2);
358 *r = T(lr);
359 return lr > std::numeric_limits<T>::max() || lr < std::numeric_limits<T>::min();
360}
361
362# if defined(Q_INTRINSIC_MUL_OVERFLOW64)
363template <> inline bool mul_overflow(quint64 v1, quint64 v2, quint64 *r)
364{
365 *r = v1 * v2;
366 return Q_UMULH(v1, v2);
367}
368template <> inline bool mul_overflow(qint64 v1, qint64 v2, qint64 *r)
369{
370 // This is slightly more complex than the unsigned case above: the sign bit
371 // of 'low' must be replicated as the entire 'high', so the only valid
372 // values for 'high' are 0 and -1. Use unsigned multiply since it's the same
373 // as signed for the low bits and use a signed right shift to verify that
374 // 'high' is nothing but sign bits that match the sign of 'low'.
375
376 qint64 high = Q_SMULH(v1, v2);
377 *r = qint64(quint64(v1) * quint64(v2));
378 return (*r >> 63) != high;
379}
380
381# if defined(Q_OS_INTEGRITY) && defined(Q_PROCESSOR_ARM_64)
382template <> inline bool mul_overflow(uint64_t v1, uint64_t v2, uint64_t *r)
383{
384 return mul_overflow<quint64>(v1,v2,reinterpret_cast<quint64*>(r));
385}
386
387template <> inline bool mul_overflow(int64_t v1, int64_t v2, int64_t *r)
388{
389 return mul_overflow<qint64>(v1,v2,reinterpret_cast<qint64*>(r));
390}
391# endif // OS_INTEGRITY ARM64
392# endif // Q_INTRINSIC_MUL_OVERFLOW64
393
394# if defined(Q_CC_MSVC) && defined(Q_PROCESSOR_X86)
395// We can use intrinsics for the unsigned operations with MSVC
396template <> inline bool add_overflow(unsigned v1, unsigned v2, unsigned *r)
397{ return _addcarry_u32(0, v1, v2, r); }
398
399// 32-bit mul_overflow is fine with the generic code above
400
401template <> inline bool add_overflow(quint64 v1, quint64 v2, quint64 *r)
402{
403# if defined(Q_PROCESSOR_X86_64)
404 return _addcarry_u64(0, v1, v2, reinterpret_cast<unsigned __int64 *>(r));
405# else
406 uint low, high;
407 uchar carry = _addcarry_u32(0, unsigned(v1), unsigned(v2), &low);
408 carry = _addcarry_u32(carry, v1 >> 32, v2 >> 32, &high);
409 *r = (quint64(high) << 32) | low;
410 return carry;
411# endif // !x86-64
412}
413# endif // MSVC X86
414#endif // !GCC
415
416// Implementations for addition, subtraction or multiplication by a
417// compile-time constant. For addition and subtraction, we simply call the code
418// that detects overflow at runtime. For multiplication, we compare to the
419// maximum possible values before multiplying to ensure no overflow happens.
420
421template <typename T, T V2> bool add_overflow(T v1, std::integral_constant<T, V2>, T *r)
422{
423 return add_overflow(v1, V2, r);
424}
425
426template <auto V2, typename T> bool add_overflow(T v1, T *r)
427{
428 return add_overflow(v1, std::integral_constant<T, V2>{}, r);
429}
430
431template <typename T, T V2> bool sub_overflow(T v1, std::integral_constant<T, V2>, T *r)
432{
433 return sub_overflow(v1, V2, r);
434}
435
436template <auto V2, typename T> bool sub_overflow(T v1, T *r)
437{
438 return sub_overflow(v1, std::integral_constant<T, V2>{}, r);
439}
440
441template <typename T, T V2> bool mul_overflow(T v1, std::integral_constant<T, V2>, T *r)
442{
443 // Runtime detection for anything smaller than or equal to a register
444 // width, as most architectures' multiplication instructions actually
445 // produce a result twice as wide as the input registers, allowing us to
446 // efficiently detect the overflow.
447 if constexpr (sizeof(T) <= sizeof(qregisteruint)) {
448 return mul_overflow(v1, V2, r);
449
450#ifdef Q_INTRINSIC_MUL_OVERFLOW64
451 } else if constexpr (sizeof(T) <= sizeof(quint64)) {
452 // If we have intrinsics detecting overflow of 64-bit multiplications,
453 // then detect overflows through them up to 64 bits.
454 return mul_overflow(v1, V2, r);
455#endif
456
457 } else if constexpr (V2 == 0 || V2 == 1) {
458 // trivial cases (and simplify logic below due to division by zero)
459 *r = v1 * V2;
460 return false;
461 } else if constexpr (V2 == -1) {
462 // multiplication by -1 is valid *except* for signed minimum values
463 // (necessary to avoid diving min() by -1, which is an overflow)
464 if (v1 < 0 && v1 == std::numeric_limits<T>::min())
465 return true;
466 *r = -v1;
467 return false;
468 } else {
469 // For 64-bit multiplications on 32-bit platforms, let's instead compare v1
470 // against the bounds that would overflow.
471 constexpr T Highest = std::numeric_limits<T>::max() / V2;
472 constexpr T Lowest = std::numeric_limits<T>::min() / V2;
473 if constexpr (Highest > Lowest) {
474 if (v1 > Highest || v1 < Lowest)
475 return true;
476 } else {
477 // this can only happen if V2 < 0
478 static_assert(V2 < 0);
479 if (v1 > Lowest || v1 < Highest)
480 return true;
481 }
482
483 *r = v1 * V2;
484 return false;
485 }
486}
487
488template <auto V2, typename T> bool mul_overflow(T v1, T *r)
489{
490 return mul_overflow(v1, std::integral_constant<T, V2>{}, r);
491}
492}
493#endif // Q_CLANG_QDOC
494
495QT_END_NAMESPACE
496
497#endif // QNUMERIC_P_H
498