Re: [PATCH v3] libstdc++: Remove UB from operator+ of months and weekdays.
Actually, disregard this patch. I'm preparing a better one which also
tackles UB in
month - months{INT_MIN}
weekday - days{INT_MIN}
Best wishes,
Cassio.
On Sat, 18 Nov 2023, 00:19 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 problem is that in libstdc++ days::rep is int64_t. Other
> implementations use int32_t and cast operands to int64_t. Hence then
> perform
> arithmetic operations without fear of overflowing. For instance, #1
> evaluates:
>
> modulo(static_cast(unsigned{x}._M_wd) + __y.count(), 7);
>
> For x86-64, long long is int64 so the cast is useless. For #2, casting to
> a
> larger type could help but all implementations follow the Standard's
> "Returns
> clause" and evaluate:
>
>modulo(static_cast(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(unsigned{__x}) + 11 + __y.count(), 12);
>
> Again, this is not possible for libstdc++. The fix uses this new function:
>
> template
> 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);
>
> 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.
> ---
>
> Changes with respect to previous versions:
> v3: Fix screwed up email send with v2. (Sorry about that. I shall learn at
> some point.)
> v2: Replaced _T with _Tp and _U with _Up. Removed copyright+license from
> test.
>
> libstdc++-v3/include/std/chrono | 61
> libstdc++-v3/testsuite/std/time/month/1.cc | 9 +++
> libstdc++-v3/testsuite/std/time/month/2.cc | 30 ++
> libstdc++-v3/testsuite/std/time/weekday/1.cc | 8 +++
> libstdc++-v3/testsuite/std/time/weekday/2.cc | 30 ++
> 5 files changed, 114 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..691bb106bb9 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(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>(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
>constexpr unsigned
> - __modulo(long long __n, unsigned __d)
> - {
> - if (__n >= 0)
> - return __n % __d;
> - else
> - return (__d + (__n % __d)) % __d;
> + __add_modulo(unsigned __x, _Tp __y)
> + {
> + using _Up = make_unsigned_t<_Tp>;
> + // For __y >= 0, _Up(__y) has the same mathematical value as __y
> and
> + // this function simply returns (__x + _Up(__y)) % d. Typically,
> this
> + // doesn't overflow since the range of _Up contains many more
> positive
> + // values than _Tp's.
[PATCH v3] libstdc++: Remove UB from operator+ of months and weekdays.
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 problem is that in libstdc++ days::rep is int64_t. Other
implementations use int32_t and cast operands to int64_t. Hence then perform
arithmetic operations without fear of overflowing. For instance, #1 evaluates:
modulo(static_cast(unsigned{x}._M_wd) + __y.count(), 7);
For x86-64, long long is int64 so the cast is useless. For #2, casting to a
larger type could help but all implementations follow the Standard's "Returns
clause" and evaluate:
modulo(static_cast(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(unsigned{__x}) + 11 + __y.count(), 12);
Again, this is not possible for libstdc++. The fix uses this new function:
template
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);
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.
---
Changes with respect to previous versions:
v3: Fix screwed up email send with v2. (Sorry about that. I shall learn at
some point.)
v2: Replaced _T with _Tp and _U with _Up. Removed copyright+license from test.
libstdc++-v3/include/std/chrono | 61
libstdc++-v3/testsuite/std/time/month/1.cc | 9 +++
libstdc++-v3/testsuite/std/time/month/2.cc | 30 ++
libstdc++-v3/testsuite/std/time/weekday/1.cc | 8 +++
libstdc++-v3/testsuite/std/time/weekday/2.cc | 30 ++
5 files changed, 114 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..691bb106bb9 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(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(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
constexpr unsigned
- __modulo(long long __n, unsigned __d)
- {
- if (__n >= 0)
- return __n % __d;
- else
- return (__d + (__n % __d)) % __d;
+ __add_modulo(unsigned __x, _Tp __y)
+ {
+ using _Up = make_unsigned_t<_Tp>;
+ // For __y >= 0, _Up(__y) has the same mathematical value as __y and
+ // this function simply returns (__x + _Up(__y)) % d. Typically, this
+ // doesn't overflow since the range of _Up contains many more positive
+ // values than _Tp's. For __y < 0, _Up(__y) has a mathematical value in
+ // the upper-half range of _Up so that adding a positive value to it
+ // might overflow. Moreover, most likely, _Up(__y) != __y mod d. To
+ // fix both issues we from _Up(__y)"subtract" an __offset >=
+ // 255 + d - 1 to make room for the addition to __x and shift the modulo
+ // to the correct value.
+ auto constexpr __a = _Up(-1) - _Up(255
