On Fri, 17 Nov 2023 at 01:34, Cassio Neri wrote:
>
> The following functions invoke signed integer overflow (UB) for some extreme
> values of days and months [1]:
>
> weekday operator+(const weekday& x, const days& y); // #1
> month operator+(const month& x, const months& y); // #2
>
> For #1, the crux of the problem is that, in libstdc++, days::rep is int64_t.
> Other implementations use int32_t and cast operands to int64_t and perform
> arithmetic operations without fear of overflowing. For instance, #1 evaluates:
>
> modulo(static_cast<long long>(unsigned{x}._M_wd) + __y.count(), 7);
>
> Sadly, libstdc++ doesn't have this luxury. For #2, casting to a larger type
> could help but all implementations follow the Standard's "Returns clause"
> and evaluate:
>
> modulo(static_cast<long long>(unsigned{__x}) + (__y.count() - 1), 12);
>
> Hence, overflow occurs when __y.count() is the minimum value of its type.
> When
> long long is larger than months::rep, this is a fix:
>
> modulo(static_cast<long long>(unsigned{__x}) + 11 + __y.count(), 12);
>
> Again, this is not possible for libstdc++. To fix these UB, this patch
> implements:
>
> template <unsigned __d, typename _T>
> unsigned __add_modulo(unsigned __x, _T __y);
>
> which returns the remainder of Euclidean division of __x +__y by __d without
> overflowing. This function replaces
>
> constexpr unsigned __modulo(long long __n, unsigned __d);
>
> which also calculates the reminder but takes the sum __n as argument at which
> point the overflow might have already occurred.
>
> In addition to solve the UB issues, __add_modulo allows shorter branchless
> code
> on x86-64 and ARM [2].
>
> [1] https://godbolt.org/z/WqvosbrvG
> [2] https://godbolt.org/z/o63794GEE
>
> libstdc++-v3/ChangeLog:
>
> * include/std/chrono: Fix operator+ for months and weekdays.
> * testsuite/std/time/month/1.cc: Add constexpr tests against overflow.
> * testsuite/std/time/month/2.cc: New test for extreme values.
> * testsuite/std/time/weekday/1.cc: Add constexpr tests against
> overflow.
> * testsuite/std/time/weekday/2.cc: New test for extreme values.
> ---
>
> If desirable, I think I'm able to do something similar for operator-(x, y)
> (month/weekday x and months/days y) which is specified as:
> Returns: x + -y;
> All implementations follow the above and -y overflows when y has the minimum
> value of its type.
I'm not sure we need to care about wday - days(INT_MIN), that seems
pretty unlikely to happen except in test suites.
I suppose somebody could use the minimum value as a placeholder for
"invalid value" and then forget to check for it before doing the
arithmetic.
More comments below ...
>
> libstdc++-v3/include/std/chrono | 61 ++++++++++++--------
> libstdc++-v3/testsuite/std/time/month/1.cc | 9 +++
> libstdc++-v3/testsuite/std/time/month/2.cc | 47 +++++++++++++++
> libstdc++-v3/testsuite/std/time/weekday/1.cc | 8 +++
> libstdc++-v3/testsuite/std/time/weekday/2.cc | 47 +++++++++++++++
> 5 files changed, 148 insertions(+), 24 deletions(-)
> create mode 100644 libstdc++-v3/testsuite/std/time/month/2.cc
> create mode 100644 libstdc++-v3/testsuite/std/time/weekday/2.cc
>
> diff --git a/libstdc++-v3/include/std/chrono b/libstdc++-v3/include/std/chrono
> index 10bdd1c4ede..02087a9374c 100644
> --- a/libstdc++-v3/include/std/chrono
> +++ b/libstdc++-v3/include/std/chrono
> @@ -497,18 +497,38 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>
> namespace __detail
> {
> - // Compute the remainder of the Euclidean division of __n divided by
> __d.
> - // Euclidean division truncates toward negative infinity and always
> - // produces a remainder in the range of [0,__d-1] (whereas standard
> - // division truncates toward zero and yields a nonpositive remainder
> - // for negative __n).
> + // Compute the remainder of the Euclidean division of __x + __y
> divided by
> + // __d without overflowing. Typically, __x <= 255 + d - 1 is sum of
> + // weekday/month and an offset in [0, d - 1] and __y is a duration
> count.
> + // For instance, [time.cal.month.nonmembers] says that given month x
> and
> + // months y, to get x + y one must calculate:
> + //
> + // modulo(static_cast<long long>(unsigned{x}) + (y.count() - 1), 12) +
> 1.
> + //
> + // Since y.count() is a 64-bits signed value the subtraction y.count()
> - 1
> + // or the addition of this value with static_cast<long
> long>(unsigned{x})
> + // might overflow. This function can be used to avoid this problem:
> + // __add_modulo<12>(unsigned{x} + 11, y.count()) + 1;
> + // (More details in the implementation of operator+(month, months).)
> + template <unsigned __d, typename _T>
> constexpr unsigned
> - __modulo(long long __n, unsigned __d)
> - {
> - if (__n >= 0)
> - return __n % __d;
> - else
> - return (__d + (__n % __d)) % __d;
> + __add_modulo(unsigned __x, _T __y)
> + {
> + using _U = make_unsigned_t<_T>;
We need to use _Tp and _Up here to avoid clashing with libc ctype constants, see
https://gcc.gnu.org/onlinedocs/libstdc++/manual/source_code_style.html#coding_style.bad_identifiers
> diff --git a/libstdc++-v3/testsuite/std/time/month/2.cc
> b/libstdc++-v3/testsuite/std/time/month/2.cc
> new file mode 100644
> index 00000000000..c53c5a2fc6f
> --- /dev/null
> +++ b/libstdc++-v3/testsuite/std/time/month/2.cc
> @@ -0,0 +1,47 @@
> +// { dg-do run { target c++20 } }
> +
> +// Copyright (C) 2020-2023 Free Software Foundation, Inc.
New files should have just 2023 as the copyright year, or leave the
copyright+license header off completely for trivial tests. I don't
bother with it these days. IMO there's no original idea being put to
use in tests like this, just fairly dull, repetitive operations
exercising the API.
