[PATCH] libstdc++: Remove UB from operator+ of months and weekdays.

[PATCH] libstdc++: Remove UB from operator+ of months and weekdays.

[Cassio Neri]

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.

 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>;
+	// For __y >= 0, _U(__y) has the same mathematical value as __y and this
+	// function simply returns (__x + _U(__y)) % d.  Typically, this doesn't
+	// overflow since the range of _U contains many more positive values
+	// than _T's.  For __y < 0, _U(__y) has a mathematical value in the
+	// upper-half range of _U so that adding a positive value to it might
+	// overflow.  Moreover, most likely, _U(__y) != __y mod d.  To fix both
+	// issues we "subtract" from _U(__y) an __offset >= 255 + d - 1 to make
+	// room for the addition to __x and shift the modulo to the correct
+	// value.
+	auto constexpr __a = _U(-1) - _U(255 + __d - 2);
+	auto constexpr __b = _U(__d * (__a / __d) - 1);
+	// Notice: b <= a - 1 <= _U(-1) - _U(255 + d - 1) and b % d = d - 1.
+	auto const __offset = __y >= 0 ? _U(0) : __b - _U(-1);
+	return (__x + _U(__y) + __offset) % __d;
       }

       inline constexpr unsigned __days_per_month[12]
@@ -700,8 +720,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       friend constexpr month
       operator+(const month& __x, const months& __y) noexcept
       {
-	auto __n = static_cast<long long>(unsigned{__x}) + (__y.count() - 1);
-	return month{__detail::__modulo(__n, 12) + 1};
+	// modulo(x + (y - 1), 12) = modulo(x + (y - 1) + 12, 12)
+	//                         = modulo((x + 11) - y, 12)
+	return month{1 + __detail::__add_modulo<12>(
+	  unsigned{__x} + 11, __y.count())};
       }

       friend constexpr month
@@ -930,15 +952,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       static constexpr weekday
       _S_from_days(const days& __d)
       {
-	using _Rep = days::rep;
-	using _URep = make_unsigned_t<_Rep>;
-	const auto __n = __d.count();
-	const auto __m = static_cast<_URep>(__n);
-
-	// 1970-01-01 (__n =  0, __m = 0        ) -> Thursday (4)
-	// 1969-31-12 (__n = -1, __m = _URep(-1)) -> Wednesday (3)
-	const auto __offset = __n >= 0 ? _URep(4) : 3 - _URep(-1) % 7 - 7;
-	return weekday((__m + __offset) % 7);
+	return weekday{__detail::__add_modulo<7>(4, __d.count())};
       }

     public:
@@ -1028,8 +1042,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       friend constexpr weekday
       operator+(const weekday& __x, const days& __y) noexcept
       {
-	auto __n = static_cast<long long>(__x._M_wd) + __y.count();
-	return weekday{__detail::__modulo(__n, 7)};
+	return weekday{__detail::__add_modulo<7>(__x._M_wd, __y.count())};
       }

       friend constexpr weekday
diff --git a/libstdc++-v3/testsuite/std/time/month/1.cc b/libstdc++-v3/testsuite/std/time/month/1.cc
index 773f772bf07..f72a4ab9a5d 100644
--- a/libstdc++-v3/testsuite/std/time/month/1.cc
+++ b/libstdc++-v3/testsuite/std/time/month/1.cc
@@ -20,6 +20,7 @@
 // Class template day [time.cal.month]

 #include <chrono>
+#include <limits>

 constexpr void
 constexpr_month()
@@ -71,4 +72,12 @@ constexpr_month()
   static_assert(month{0} <=> month{1} == std::strong_ordering::less);
   static_assert(month{3} <=> month{3} == std::strong_ordering::equal);
   static_assert(month{5} <=> month{2} == std::strong_ordering::greater);
+
+  auto constexpr months_min = months{std::numeric_limits<months::rep>::min()};
+  auto constexpr m0_min     = month{ 0 } + months_min;
+  auto constexpr m255_min   = month{255} + months_min;
+
+  auto constexpr months_max = months{std::numeric_limits<months::rep>::max()};
+  auto constexpr m0_max     = month{ 0 } + months_max;
+  auto constexpr m255_max   = month{255} + months_max;
 }
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.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// Class month [time.cal.month]
+
+#include <chrono>
+#include <limits>
+#include <testsuite_hooks.h>
+
+using namespace std::chrono;
+
+void test_extreme_values(months extreme)
+{
+  for (unsigned m = 0; m < 254; ++m)
+  {
+    auto const m1 = month{  m  } + extreme;
+    auto const m2 = month{m + 1} + extreme;
+
+    auto const u1 = unsigned{m1};
+    auto const u2 = unsigned{m2};
+
+    VERIFY(u1 == 12 ? u2 == 1 : u2 == u1 + 1);
+  }
+}
+
+int main()
+{
+  test_extreme_values(months{std::numeric_limits<months::rep>::max()});
+  test_extreme_values(months{std::numeric_limits<months::rep>::min()});
+  return 0;
+}
diff --git a/libstdc++-v3/testsuite/std/time/weekday/1.cc b/libstdc++-v3/testsuite/std/time/weekday/1.cc
index e89fca47d4b..cc8b0db78f8 100644
--- a/libstdc++-v3/testsuite/std/time/weekday/1.cc
+++ b/libstdc++-v3/testsuite/std/time/weekday/1.cc
@@ -107,4 +107,12 @@ constexpr_weekday()
   static_assert(weekday{7} == weekday{0});
   static_assert(!(weekday{0} == weekday{1}));
   static_assert( (weekday{0} != weekday{2}));
+
+  auto constexpr days_min  = days{std::numeric_limits<days::rep>::min()};
+  auto constexpr wd0_min   = weekday{ 0 } + days_min;
+  auto constexpr wd255_min = weekday{255} + days_min;
+
+  auto constexpr days_max  = days{std::numeric_limits<days::rep>::max()};
+  auto constexpr m0_max    = weekday{ 0 } + days_max;
+  auto constexpr m255_max  = weekday{255} + days_max;
 }
diff --git a/libstdc++-v3/testsuite/std/time/weekday/2.cc b/libstdc++-v3/testsuite/std/time/weekday/2.cc
new file mode 100644
index 00000000000..78a90f3cce3
--- /dev/null
+++ b/libstdc++-v3/testsuite/std/time/weekday/2.cc
@@ -0,0 +1,47 @@
+// { dg-do run { target c++20 } }
+
+// Copyright (C) 2020-2023 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// Class weekday [time.cal.wd]
+
+#include <chrono>
+#include <limits>
+#include <testsuite_hooks.h>
+
+using namespace std::chrono;
+
+void test_extreme_values(days extreme)
+{
+  for (unsigned d = 0; d < 254; ++d)
+  {
+    auto const m1 = weekday{  d  } + extreme;
+    auto const m2 = weekday{d + 1} + extreme;
+
+    auto const u1 = m1.c_encoding();
+    auto const u2 = m2.c_encoding();
+
+    VERIFY(u1 == 6 ? u2 == 0 : u2 == u1 + 1);
+  }
+}
+
+int main()
+{
+  test_extreme_values(days{std::numeric_limits<days::rep>::max()});
+  test_extreme_values(days{std::numeric_limits<days::rep>::min()});
+  return 0;
+}
--
2.41.0

Re: [PATCH] libstdc++: Remove UB from operator+ of months and weekdays.

[Jonathan Wakely]

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.

[PATCH v2] The following functions invoke signed integer overflow (UB) for some extreme values of days and months [1]:

[Cassio Neri]

  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<long long>(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<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++.  The fix uses this new function:

  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);

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.
---
 libstdc++-v3/include/std/chrono              | 61 ++++++++++++--------
 libstdc++-v3/testsuite/std/time/month/1.cc   |  9 +++
 libstdc++-v3/testsuite/std/time/weekday/1.cc |  8 +++
 3 files changed, 54 insertions(+), 24 deletions(-)

 Changes with respect to previous versions:
 v2: Replaced _T with _Tp and _U with _Up. Removed copyright+license from test.

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<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 _Tp>
       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 + __d - 2);
+	auto constexpr __b = _Up(__d * (__a / __d) - 1);
+	// Notice: b <= a - 1 <= _Up(-1) - _Up(255 + d - 1) and b % d = d - 1.
+	auto const __offset = __y >= 0 ? _Up(0) : __b - _Up(-1);
+	return (__x + _Up(__y) + __offset) % __d;
       }

       inline constexpr unsigned __days_per_month[12]
@@ -700,8 +720,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       friend constexpr month
       operator+(const month& __x, const months& __y) noexcept
       {
-	auto __n = static_cast<long long>(unsigned{__x}) + (__y.count() - 1);
-	return month{__detail::__modulo(__n, 12) + 1};
+	// modulo(x + (y - 1), 12) = modulo(x + (y - 1) + 12, 12)
+	//                         = modulo((x + 11) - y, 12)
+	return month{1 + __detail::__add_modulo<12>(
+	  unsigned{__x} + 11, __y.count())};
       }

       friend constexpr month
@@ -930,15 +952,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       static constexpr weekday
       _S_from_days(const days& __d)
       {
-	using _Rep = days::rep;
-	using _URep = make_unsigned_t<_Rep>;
-	const auto __n = __d.count();
-	const auto __m = static_cast<_URep>(__n);
-
-	// 1970-01-01 (__n =  0, __m = 0        ) -> Thursday (4)
-	// 1969-31-12 (__n = -1, __m = _URep(-1)) -> Wednesday (3)
-	const auto __offset = __n >= 0 ? _URep(4) : 3 - _URep(-1) % 7 - 7;
-	return weekday((__m + __offset) % 7);
+	return weekday{__detail::__add_modulo<7>(4, __d.count())};
       }

     public:
@@ -1028,8 +1042,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       friend constexpr weekday
       operator+(const weekday& __x, const days& __y) noexcept
       {
-	auto __n = static_cast<long long>(__x._M_wd) + __y.count();
-	return weekday{__detail::__modulo(__n, 7)};
+	return weekday{__detail::__add_modulo<7>(__x._M_wd, __y.count())};
       }

       friend constexpr weekday
diff --git a/libstdc++-v3/testsuite/std/time/month/1.cc b/libstdc++-v3/testsuite/std/time/month/1.cc
index 773f772bf07..f72a4ab9a5d 100644
--- a/libstdc++-v3/testsuite/std/time/month/1.cc
+++ b/libstdc++-v3/testsuite/std/time/month/1.cc
@@ -20,6 +20,7 @@
 // Class template day [time.cal.month]

 #include <chrono>
+#include <limits>

 constexpr void
 constexpr_month()
@@ -71,4 +72,12 @@ constexpr_month()
   static_assert(month{0} <=> month{1} == std::strong_ordering::less);
   static_assert(month{3} <=> month{3} == std::strong_ordering::equal);
   static_assert(month{5} <=> month{2} == std::strong_ordering::greater);
+
+  auto constexpr months_min = months{std::numeric_limits<months::rep>::min()};
+  auto constexpr m0_min     = month{ 0 } + months_min;
+  auto constexpr m255_min   = month{255} + months_min;
+
+  auto constexpr months_max = months{std::numeric_limits<months::rep>::max()};
+  auto constexpr m0_max     = month{ 0 } + months_max;
+  auto constexpr m255_max   = month{255} + months_max;
 }
diff --git a/libstdc++-v3/testsuite/std/time/weekday/1.cc b/libstdc++-v3/testsuite/std/time/weekday/1.cc
index e89fca47d4b..cc8b0db78f8 100644
--- a/libstdc++-v3/testsuite/std/time/weekday/1.cc
+++ b/libstdc++-v3/testsuite/std/time/weekday/1.cc
@@ -107,4 +107,12 @@ constexpr_weekday()
   static_assert(weekday{7} == weekday{0});
   static_assert(!(weekday{0} == weekday{1}));
   static_assert( (weekday{0} != weekday{2}));
+
+  auto constexpr days_min  = days{std::numeric_limits<days::rep>::min()};
+  auto constexpr wd0_min   = weekday{ 0 } + days_min;
+  auto constexpr wd255_min = weekday{255} + days_min;
+
+  auto constexpr days_max  = days{std::numeric_limits<days::rep>::max()};
+  auto constexpr m0_max    = weekday{ 0 } + days_max;
+  auto constexpr m255_max  = weekday{255} + days_max;
 }
--
2.41.0

[PATCH v3] libstdc++: Remove UB from operator+ of months and weekdays.

[Cassio Neri]

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<long long>(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<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++.  The fix uses this new function:

  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);

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<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 _Tp>
       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 + __d - 2);
+	auto constexpr __b = _Up(__d * (__a / __d) - 1);
+	// Notice: b <= a - 1 <= _Up(-1) - _Up(255 + d - 1) and b % d = d - 1.
+	auto const __offset = __y >= 0 ? _Up(0) : __b - _Up(-1);
+	return (__x + _Up(__y) + __offset) % __d;
       }

       inline constexpr unsigned __days_per_month[12]
@@ -700,8 +720,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       friend constexpr month
       operator+(const month& __x, const months& __y) noexcept
       {
-	auto __n = static_cast<long long>(unsigned{__x}) + (__y.count() - 1);
-	return month{__detail::__modulo(__n, 12) + 1};
+	// modulo(x + (y - 1), 12) = modulo(x + (y - 1) + 12, 12)
+	//                         = modulo((x + 11) - y, 12)
+	return month{1 + __detail::__add_modulo<12>(
+	  unsigned{__x} + 11, __y.count())};
       }

       friend constexpr month
@@ -930,15 +952,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       static constexpr weekday
       _S_from_days(const days& __d)
       {
-	using _Rep = days::rep;
-	using _URep = make_unsigned_t<_Rep>;
-	const auto __n = __d.count();
-	const auto __m = static_cast<_URep>(__n);
-
-	// 1970-01-01 (__n =  0, __m = 0        ) -> Thursday (4)
-	// 1969-31-12 (__n = -1, __m = _URep(-1)) -> Wednesday (3)
-	const auto __offset = __n >= 0 ? _URep(4) : 3 - _URep(-1) % 7 - 7;
-	return weekday((__m + __offset) % 7);
+	return weekday{__detail::__add_modulo<7>(4, __d.count())};
       }

     public:
@@ -1028,8 +1042,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       friend constexpr weekday
       operator+(const weekday& __x, const days& __y) noexcept
       {
-	auto __n = static_cast<long long>(__x._M_wd) + __y.count();
-	return weekday{__detail::__modulo(__n, 7)};
+	return weekday{__detail::__add_modulo<7>(__x._M_wd, __y.count())};
       }

       friend constexpr weekday
diff --git a/libstdc++-v3/testsuite/std/time/month/1.cc b/libstdc++-v3/testsuite/std/time/month/1.cc
index 773f772bf07..f72a4ab9a5d 100644
--- a/libstdc++-v3/testsuite/std/time/month/1.cc
+++ b/libstdc++-v3/testsuite/std/time/month/1.cc
@@ -20,6 +20,7 @@
 // Class template day [time.cal.month]

 #include <chrono>
+#include <limits>

 constexpr void
 constexpr_month()
@@ -71,4 +72,12 @@ constexpr_month()
   static_assert(month{0} <=> month{1} == std::strong_ordering::less);
   static_assert(month{3} <=> month{3} == std::strong_ordering::equal);
   static_assert(month{5} <=> month{2} == std::strong_ordering::greater);
+
+  auto constexpr months_min = months{std::numeric_limits<months::rep>::min()};
+  auto constexpr m0_min     = month{ 0 } + months_min;
+  auto constexpr m255_min   = month{255} + months_min;
+
+  auto constexpr months_max = months{std::numeric_limits<months::rep>::max()};
+  auto constexpr m0_max     = month{ 0 } + months_max;
+  auto constexpr m255_max   = month{255} + months_max;
 }
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..85895949e4e
--- /dev/null
+++ b/libstdc++-v3/testsuite/std/time/month/2.cc
@@ -0,0 +1,30 @@
+// { dg-do run { target c++20 } }
+
+// Class month [time.cal.month]
+
+#include <chrono>
+#include <limits>
+#include <testsuite_hooks.h>
+
+using namespace std::chrono;
+
+void test_extreme_values(months extreme)
+{
+  for (unsigned m = 0; m < 254; ++m)
+  {
+    auto const m1 = month{  m  } + extreme;
+    auto const m2 = month{m + 1} + extreme;
+
+    auto const u1 = unsigned{m1};
+    auto const u2 = unsigned{m2};
+
+    VERIFY(u1 == 12 ? u2 == 1 : u2 == u1 + 1);
+  }
+}
+
+int main()
+{
+  test_extreme_values(months{std::numeric_limits<months::rep>::max()});
+  test_extreme_values(months{std::numeric_limits<months::rep>::min()});
+  return 0;
+}
diff --git a/libstdc++-v3/testsuite/std/time/weekday/1.cc b/libstdc++-v3/testsuite/std/time/weekday/1.cc
index e89fca47d4b..cc8b0db78f8 100644
--- a/libstdc++-v3/testsuite/std/time/weekday/1.cc
+++ b/libstdc++-v3/testsuite/std/time/weekday/1.cc
@@ -107,4 +107,12 @@ constexpr_weekday()
   static_assert(weekday{7} == weekday{0});
   static_assert(!(weekday{0} == weekday{1}));
   static_assert( (weekday{0} != weekday{2}));
+
+  auto constexpr days_min  = days{std::numeric_limits<days::rep>::min()};
+  auto constexpr wd0_min   = weekday{ 0 } + days_min;
+  auto constexpr wd255_min = weekday{255} + days_min;
+
+  auto constexpr days_max  = days{std::numeric_limits<days::rep>::max()};
+  auto constexpr m0_max    = weekday{ 0 } + days_max;
+  auto constexpr m255_max  = weekday{255} + days_max;
 }
diff --git a/libstdc++-v3/testsuite/std/time/weekday/2.cc b/libstdc++-v3/testsuite/std/time/weekday/2.cc
new file mode 100644
index 00000000000..82284976152
--- /dev/null
+++ b/libstdc++-v3/testsuite/std/time/weekday/2.cc
@@ -0,0 +1,30 @@
+// { dg-do run { target c++20 } }
+
+// Class weekday [time.cal.wd]
+
+#include <chrono>
+#include <limits>
+#include <testsuite_hooks.h>
+
+using namespace std::chrono;
+
+void test_extreme_values(days extreme)
+{
+  for (unsigned d = 0; d < 254; ++d)
+  {
+    auto const m1 = weekday{  d  } + extreme;
+    auto const m2 = weekday{d + 1} + extreme;
+
+    auto const u1 = m1.c_encoding();
+    auto const u2 = m2.c_encoding();
+
+    VERIFY(u1 == 6 ? u2 == 0 : u2 == u1 + 1);
+  }
+}
+
+int main()
+{
+  test_extreme_values(days{std::numeric_limits<days::rep>::max()});
+  test_extreme_values(days{std::numeric_limits<days::rep>::min()});
+  return 0;
+}
--
2.41.0

Re: [PATCH v3] libstdc++: Remove UB from operator+ of months and weekdays.

[Cassio Neri]

[-- Attachment #1: Type: text/plain, Size: 11463 bytes --]

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, <cassio.neri@gmail.com> 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<long long>(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<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++.  The fix uses this new function:
>
>   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);
>
> 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<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 _Tp>
>        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 + __d - 2);
> +       auto constexpr __b = _Up(__d * (__a / __d) - 1);
> +       // Notice: b <= a - 1 <= _Up(-1) - _Up(255 + d - 1) and b % d = d
> - 1.
> +       auto const __offset = __y >= 0 ? _Up(0) : __b - _Up(-1);
> +       return (__x + _Up(__y) + __offset) % __d;
>        }
>
>        inline constexpr unsigned __days_per_month[12]
> @@ -700,8 +720,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>        friend constexpr month
>        operator+(const month& __x, const months& __y) noexcept
>        {
> -       auto __n = static_cast<long long>(unsigned{__x}) + (__y.count() -
> 1);
> -       return month{__detail::__modulo(__n, 12) + 1};
> +       // modulo(x + (y - 1), 12) = modulo(x + (y - 1) + 12, 12)
> +       //                         = modulo((x + 11) - y, 12)
> +       return month{1 + __detail::__add_modulo<12>(
> +         unsigned{__x} + 11, __y.count())};
>        }
>
>        friend constexpr month
> @@ -930,15 +952,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>        static constexpr weekday
>        _S_from_days(const days& __d)
>        {
> -       using _Rep = days::rep;
> -       using _URep = make_unsigned_t<_Rep>;
> -       const auto __n = __d.count();
> -       const auto __m = static_cast<_URep>(__n);
> -
> -       // 1970-01-01 (__n =  0, __m = 0        ) -> Thursday (4)
> -       // 1969-31-12 (__n = -1, __m = _URep(-1)) -> Wednesday (3)
> -       const auto __offset = __n >= 0 ? _URep(4) : 3 - _URep(-1) % 7 - 7;
> -       return weekday((__m + __offset) % 7);
> +       return weekday{__detail::__add_modulo<7>(4, __d.count())};
>        }
>
>      public:
> @@ -1028,8 +1042,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>        friend constexpr weekday
>        operator+(const weekday& __x, const days& __y) noexcept
>        {
> -       auto __n = static_cast<long long>(__x._M_wd) + __y.count();
> -       return weekday{__detail::__modulo(__n, 7)};
> +       return weekday{__detail::__add_modulo<7>(__x._M_wd, __y.count())};
>        }
>
>        friend constexpr weekday
> diff --git a/libstdc++-v3/testsuite/std/time/month/1.cc
> b/libstdc++-v3/testsuite/std/time/month/1.cc
> index 773f772bf07..f72a4ab9a5d 100644
> --- a/libstdc++-v3/testsuite/std/time/month/1.cc
> +++ b/libstdc++-v3/testsuite/std/time/month/1.cc
> @@ -20,6 +20,7 @@
>  // Class template day [time.cal.month]
>
>  #include <chrono>
> +#include <limits>
>
>  constexpr void
>  constexpr_month()
> @@ -71,4 +72,12 @@ constexpr_month()
>    static_assert(month{0} <=> month{1} == std::strong_ordering::less);
>    static_assert(month{3} <=> month{3} == std::strong_ordering::equal);
>    static_assert(month{5} <=> month{2} == std::strong_ordering::greater);
> +
> +  auto constexpr months_min =
> months{std::numeric_limits<months::rep>::min()};
> +  auto constexpr m0_min     = month{ 0 } + months_min;
> +  auto constexpr m255_min   = month{255} + months_min;
> +
> +  auto constexpr months_max =
> months{std::numeric_limits<months::rep>::max()};
> +  auto constexpr m0_max     = month{ 0 } + months_max;
> +  auto constexpr m255_max   = month{255} + months_max;
>  }
> 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..85895949e4e
> --- /dev/null
> +++ b/libstdc++-v3/testsuite/std/time/month/2.cc
> @@ -0,0 +1,30 @@
> +// { dg-do run { target c++20 } }
> +
> +// Class month [time.cal.month]
> +
> +#include <chrono>
> +#include <limits>
> +#include <testsuite_hooks.h>
> +
> +using namespace std::chrono;
> +
> +void test_extreme_values(months extreme)
> +{
> +  for (unsigned m = 0; m < 254; ++m)
> +  {
> +    auto const m1 = month{  m  } + extreme;
> +    auto const m2 = month{m + 1} + extreme;
> +
> +    auto const u1 = unsigned{m1};
> +    auto const u2 = unsigned{m2};
> +
> +    VERIFY(u1 == 12 ? u2 == 1 : u2 == u1 + 1);
> +  }
> +}
> +
> +int main()
> +{
> +  test_extreme_values(months{std::numeric_limits<months::rep>::max()});
> +  test_extreme_values(months{std::numeric_limits<months::rep>::min()});
> +  return 0;
> +}
> diff --git a/libstdc++-v3/testsuite/std/time/weekday/1.cc
> b/libstdc++-v3/testsuite/std/time/weekday/1.cc
> index e89fca47d4b..cc8b0db78f8 100644
> --- a/libstdc++-v3/testsuite/std/time/weekday/1.cc
> +++ b/libstdc++-v3/testsuite/std/time/weekday/1.cc
> @@ -107,4 +107,12 @@ constexpr_weekday()
>    static_assert(weekday{7} == weekday{0});
>    static_assert(!(weekday{0} == weekday{1}));
>    static_assert( (weekday{0} != weekday{2}));
> +
> +  auto constexpr days_min  = days{std::numeric_limits<days::rep>::min()};
> +  auto constexpr wd0_min   = weekday{ 0 } + days_min;
> +  auto constexpr wd255_min = weekday{255} + days_min;
> +
> +  auto constexpr days_max  = days{std::numeric_limits<days::rep>::max()};
> +  auto constexpr m0_max    = weekday{ 0 } + days_max;
> +  auto constexpr m255_max  = weekday{255} + days_max;
>  }
> diff --git a/libstdc++-v3/testsuite/std/time/weekday/2.cc
> b/libstdc++-v3/testsuite/std/time/weekday/2.cc
> new file mode 100644
> index 00000000000..82284976152
> --- /dev/null
> +++ b/libstdc++-v3/testsuite/std/time/weekday/2.cc
> @@ -0,0 +1,30 @@
> +// { dg-do run { target c++20 } }
> +
> +// Class weekday [time.cal.wd]
> +
> +#include <chrono>
> +#include <limits>
> +#include <testsuite_hooks.h>
> +
> +using namespace std::chrono;
> +
> +void test_extreme_values(days extreme)
> +{
> +  for (unsigned d = 0; d < 254; ++d)
> +  {
> +    auto const m1 = weekday{  d  } + extreme;
> +    auto const m2 = weekday{d + 1} + extreme;
> +
> +    auto const u1 = m1.c_encoding();
> +    auto const u2 = m2.c_encoding();
> +
> +    VERIFY(u1 == 6 ? u2 == 0 : u2 == u1 + 1);
> +  }
> +}
> +
> +int main()
> +{
> +  test_extreme_values(days{std::numeric_limits<days::rep>::max()});
> +  test_extreme_values(days{std::numeric_limits<days::rep>::min()});
> +  return 0;
> +}
> --
> 2.41.0
>
>

[PATCH v4] libstdc++: Remove UB from month and weekday additions and subtractions.

[Cassio Neri]

The following invoke signed integer overflow (UB) [1]:

  month   + months{MAX} // where MAX is the maximum value of months::rep
  month   + months{MIN} // where MIN is the maximum value of months::rep
  month   - months{MIN} // where MIN is the minimum value of months::rep
  weekday + days  {MAX} // where MAX is the maximum value of days::rep
  weekday - days  {MIN} // where MIN is the minimum value of days::rep

For the additions to MAX, the crux of the problem is that, in libstdc++,
months::rep and days::rep are int64_t. Other implementations use int32_t, cast
operands to int64_t and perform arithmetic operations without risk of
overflowing.

For month + months{MIN}, the implementations follows the Standard's "returns
clause" and evaluates:

   modulo(static_cast<long long>(unsigned{__x}) + (__y.count() - 1), 12);

Overflow occurs when MIN - 1 is evaluated. Casting to a larger type could help
but, unfortunately again, this is not possible for libstdc++.

For the subtraction of MIN, the problem is that -MIN is not representable.

It's fair to say that the intentions are for these additions/subtractions to
be in modulus (12 or 7) arithmetic so that no overflow is expected.

To fix these UB, this patch implements:

  template <unsigned __d, typename _T>
  unsigned __add_modulo(unsigned __x, _T __y);

  template <unsigned __d, typename _T>
  unsigned __sub_modulo(unsigned __x, _T __y);

which respectively, returns the remainder of Euclidean division of, __x + __y
and __x - __y by __d without overflowing. These functions replace

  constexpr unsigned __modulo(long long __n, unsigned __d);

which also calculates the reminder of __n, where __n is the result of the
addition or subtraction. Hence, these operations might invoke UB before __modulo
is called and thus, __modulo can't do anything to remediate the issue.

In addition to solve the UB issues, __add_modulo and __sub_modulo allows better
codegen (shorter and branchless) on x86-64 and ARM [2].

[1] https://godbolt.org/z/a9YfWdn57
[2] https://godbolt.org/z/Gh36cr7E4

libstdc++-v3/ChangeLog:

	* include/std/chrono: Fix + and - 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:
  v4: Remove UB also from operator-.
  v3: Fix screwed up email send with v2.
  v2: Replace _T with _Tp and _U with _Up. Remove copyright+license from test.

 libstdc++-v3/include/std/chrono              | 79 +++++++++++++-------
 libstdc++-v3/testsuite/std/time/month/1.cc   | 19 +++++
 libstdc++-v3/testsuite/std/time/month/2.cc   | 32 ++++++++
 libstdc++-v3/testsuite/std/time/weekday/1.cc | 16 +++-
 libstdc++-v3/testsuite/std/time/weekday/2.cc | 32 ++++++++
 5 files changed, 151 insertions(+), 27 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 e4ba6eafceb..1b7cdb96e1c 100644
--- a/libstdc++-v3/include/std/chrono
+++ b/libstdc++-v3/include/std/chrono
@@ -501,18 +501,47 @@ _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).
+      // Helper to __add_modulo and __sub_modulo.
+      template <unsigned __d, typename _Tp>
+      constexpr auto
+      __modulo_offset()
+      {
+	using _Up = make_unsigned_t<_Tp>;
+	auto constexpr __a = _Up(-1) - _Up(255 + __d - 2);
+	auto constexpr __b = _Up(__d * (__a / __d) - 1);
+	// Notice: b <= a - 1 <= _Up(-1) - (255 + d - 1) and b % d = d - 1.
+	return _Up(-1) - __b; // >= 255 + d - 1
+      }
+
+      // 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 with a shift in [0, d - 1] and __y is a duration count.
+      template <unsigned __d, typename _Tp>
+      constexpr unsigned
+      __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 subtract from _Up(__y) an __offset >=
+	// 255 + d - 1 to make room for the addition to __x and shift the modulo
+	// to the correct value.
+	auto const __offset = __y >= 0 ? _Up(0) : __modulo_offset<__d, _Tp>();
+	return (__x + _Up(__y) - __offset) % __d;
+      }
+
+      // Similar to __add_modulo but for __x - __y.
+      template <unsigned __d, typename _Tp>
       constexpr unsigned
-      __modulo(long long __n, unsigned __d)
+      __sub_modulo(unsigned __x, _Tp __y)
       {
-	if (__n >= 0)
-	  return __n % __d;
-	else
-	  return (__d + (__n % __d)) % __d;
+	using _Up = make_unsigned_t<_Tp>;
+	auto const __offset = __y <= 0 ? _Up(0) : __modulo_offset<__d, _Tp>();
+	return (__x - _Up(__y) - __offset) % __d;
       }

       inline constexpr unsigned __days_per_month[12]
@@ -704,8 +733,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       friend constexpr month
       operator+(const month& __x, const months& __y) noexcept
       {
-	auto __n = static_cast<long long>(unsigned{__x}) + (__y.count() - 1);
-	return month{__detail::__modulo(__n, 12) + 1};
+	// modulo(x + (y - 1), 12) = modulo(x + (y - 1) + 12, 12)
+	//                         = modulo((x + 11) + y    , 12)
+	return month{1 + __detail::__add_modulo<12>(
+	  unsigned{__x} + 11, __y.count())};
       }

       friend constexpr month
@@ -714,7 +745,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION

       friend constexpr month
       operator-(const month& __x, const months& __y) noexcept
-      { return __x + -__y; }
+      {
+	// modulo(x + (-y - 1), 12) = modulo(x + (-y - 1) + 12, 12)
+	//                          = modulo((x + 11) - y     , 12)
+	return month{1 + __detail::__sub_modulo<12>(
+	  unsigned{__x} + 11, __y.count())};
+      }

       friend constexpr months
       operator-(const month& __x,  const month& __y) noexcept
@@ -934,15 +970,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       static constexpr weekday
       _S_from_days(const days& __d)
       {
-	using _Rep = days::rep;
-	using _URep = make_unsigned_t<_Rep>;
-	const auto __n = __d.count();
-	const auto __m = static_cast<_URep>(__n);
-
-	// 1970-01-01 (__n =  0, __m = 0        ) -> Thursday (4)
-	// 1969-31-12 (__n = -1, __m = _URep(-1)) -> Wednesday (3)
-	const auto __offset = __n >= 0 ? _URep(4) : 3 - _URep(-1) % 7 - 7;
-	return weekday((__m + __offset) % 7);
+	return weekday{__detail::__add_modulo<7>(4, __d.count())};
       }

     public:
@@ -1032,8 +1060,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       friend constexpr weekday
       operator+(const weekday& __x, const days& __y) noexcept
       {
-	auto __n = static_cast<long long>(__x._M_wd) + __y.count();
-	return weekday{__detail::__modulo(__n, 7)};
+	return weekday{__detail::__add_modulo<7>(__x._M_wd, __y.count())};
       }

       friend constexpr weekday
@@ -1042,7 +1069,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION

       friend constexpr weekday
       operator-(const weekday& __x, const days& __y) noexcept
-      { return __x + -__y; }
+      {
+	return weekday{__detail::__sub_modulo<7>(__x._M_wd, __y.count())};
+      }

       friend constexpr days
       operator-(const weekday& __x, const weekday& __y) noexcept
diff --git a/libstdc++-v3/testsuite/std/time/month/1.cc b/libstdc++-v3/testsuite/std/time/month/1.cc
index 773f772bf07..1b3612f27e3 100644
--- a/libstdc++-v3/testsuite/std/time/month/1.cc
+++ b/libstdc++-v3/testsuite/std/time/month/1.cc
@@ -20,6 +20,7 @@
 // Class template day [time.cal.month]

 #include <chrono>
+#include <limits>

 constexpr void
 constexpr_month()
@@ -34,6 +35,24 @@ constexpr_month()
   dm += months{3};
   dm -= months{3};

+  // Test for UB (overflow).
+  {
+    using rep = months::rep;
+    using std::numeric_limits;
+
+    auto constexpr months_min = months{numeric_limits<rep>::min()};
+    auto constexpr month_000_plus_months_min  = month{ 0 } + months_min;
+    auto constexpr month_255_plus_months_min  = month{255} + months_min;
+    auto constexpr month_000_minus_months_min = month{ 0 } - months_min;
+    auto constexpr month_255_minus_months_min = month{255} - months_min;
+
+    auto constexpr months_max = months{numeric_limits<rep>::max()};
+    auto constexpr month_000_plus_months_max  = month{ 0 } + months_max;
+    auto constexpr month_255_plus_months_max  = month{255} + months_max;
+    auto constexpr month_000_minus_months_max = month{ 0 } - months_max;
+    auto constexpr month_255_minus_months_max = month{255} - months_max;
+  }
+
   static_assert(February + months{11} == January);
   static_assert(January + months{1200} == January);
   static_assert(January + months{1201} == February);
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..3bcefa60003
--- /dev/null
+++ b/libstdc++-v3/testsuite/std/time/month/2.cc
@@ -0,0 +1,32 @@
+// { dg-do run { target c++20 } }
+
+// Class month [time.cal.month]
+
+#include <chrono>
+#include <limits>
+#include <testsuite_hooks.h>
+
+using namespace std::chrono;
+
+void test_extreme_values(months extreme)
+{
+  auto const count = extreme.count();
+  auto const safe  = count < 0 ? count + 12 : count;
+  auto const mod   = safe - 12 * ((safe < 0 ? safe - 11 : safe) / 12);
+
+  for (unsigned m = 0; m < 256; ++m)
+  {
+    auto const month_plus_extreme = month{m} + extreme;
+    VERIFY(unsigned{month_plus_extreme } == (m + 11 + mod) % 12 + 1);
+
+    auto const month_minus_extreme = month{m} - extreme;
+    VERIFY(unsigned{month_minus_extreme} == (m + 11 - mod) % 12 + 1);
+  }
+}
+
+int main()
+{
+  test_extreme_values(months{std::numeric_limits<months::rep>::max()});
+  test_extreme_values(months{std::numeric_limits<months::rep>::min()});
+  return 0;
+}
diff --git a/libstdc++-v3/testsuite/std/time/weekday/1.cc b/libstdc++-v3/testsuite/std/time/weekday/1.cc
index e89fca47d4b..2f0249b28a4 100644
--- a/libstdc++-v3/testsuite/std/time/weekday/1.cc
+++ b/libstdc++-v3/testsuite/std/time/weekday/1.cc
@@ -42,8 +42,20 @@ constexpr_weekday()
   {
     using rep = days::rep;
     using std::numeric_limits;
-    constexpr weekday max{sys_days{days{numeric_limits<rep>::max()}}};
-    constexpr weekday min{sys_days{days{numeric_limits<rep>::min()}}};
+
+    auto constexpr days_min = days{numeric_limits<rep>::min()};
+    auto constexpr weekday_from_sysdays_min   = weekday{sys_days{days_min}};
+    auto constexpr weekday_000_plus_days_min  = weekday{ 0 } + days_min;
+    auto constexpr weekday_255_plus_days_min  = weekday{255} + days_min;
+    auto constexpr weekday_000_minus_days_min = weekday{ 0 } - days_min;
+    auto constexpr weekday_255_minus_days_min = weekday{255} - days_min;
+
+    auto constexpr days_max = days{numeric_limits<rep>::max()};
+    auto constexpr weekday_from_sysdays_max   = weekday{sys_days{days_max}};
+    auto constexpr weekday_000_plus_days_max  = weekday{ 0 } + days_max;
+    auto constexpr weekday_255_plus_days_max  = weekday{255} + days_max;
+    auto constexpr weekday_000_minus_days_max = weekday{ 0 } - days_max;
+    auto constexpr weekday_255_minus_days_max = weekday{255} - days_max;
   }

   static_assert(weekday{sys_days{1900y/January/1}} == Monday);
diff --git a/libstdc++-v3/testsuite/std/time/weekday/2.cc b/libstdc++-v3/testsuite/std/time/weekday/2.cc
new file mode 100644
index 00000000000..924709321e5
--- /dev/null
+++ b/libstdc++-v3/testsuite/std/time/weekday/2.cc
@@ -0,0 +1,32 @@
+// { dg-do run { target c++20 } }
+
+// Class weekday [time.cal.wd]
+
+#include <chrono>
+#include <limits>
+#include <testsuite_hooks.h>
+
+using namespace std::chrono;
+
+void test_extreme_values(days extreme)
+{
+  auto const count = extreme.count();
+  auto const safe  = count < 0 ? count + 7 : count;
+  auto const mod   = safe - 7 * ((safe < 0 ? safe - 6 : safe) / 7);
+
+  for (unsigned d = 0; d < 254; ++d)
+  {
+    auto const weekday_plus_extreme = weekday{d} + extreme;
+    VERIFY(weekday_plus_extreme.c_encoding()  == (d + mod) % 7);
+
+    auto const weekday_minus_extreme = weekday{d} - extreme;
+    VERIFY(weekday_minus_extreme.c_encoding() == (d + 7 - mod) % 7);
+  }
+}
+
+int main()
+{
+  test_extreme_values(days{std::numeric_limits<days::rep>::max()});
+  test_extreme_values(days{std::numeric_limits<days::rep>::min()});
+  return 0;
+}
--
2.41.0

[PATCH v5] libstdc++: Remove UB from month and weekday additions and subtractions.

[Cassio Neri]

The following invoke signed integer overflow (UB) [1]:

  month   + months{MAX} // where MAX is the maximum value of months::rep
  month   + months{MIN} // where MIN is the maximum value of months::rep
  month   - months{MIN} // where MIN is the minimum value of months::rep
  weekday + days  {MAX} // where MAX is the maximum value of days::rep
  weekday - days  {MIN} // where MIN is the minimum value of days::rep

For the additions to MAX, the crux of the problem is that, in libstdc++,
months::rep and days::rep are int64_t. Other implementations use int32_t, cast
operands to int64_t and perform arithmetic operations without risk of
overflowing.

For month + months{MIN}, the implementation follows the Standard's "returns
clause" and evaluates:

   modulo(static_cast<long long>(unsigned{__x}) + (__y.count() - 1), 12);

Overflow occurs when MIN - 1 is evaluated. Casting to a larger type could help
but, unfortunately again, this is not possible for libstdc++.

For the subtraction of MIN, the problem is that -MIN is not representable.

It's fair to say that the intention is for these additions/subtractions to
be performed in modulus (12 or 7) arithmetic so that no overflow is expected.

To fix these UB, this patch implements:

  template <unsigned __d, typename _T>
  unsigned __add_modulo(unsigned __x, _T __y);

  template <unsigned __d, typename _T>
  unsigned __sub_modulo(unsigned __x, _T __y);

which respectively, returns the remainder of Euclidean division of, __x + __y
and __x - __y by __d without overflowing. These functions replace

  constexpr unsigned __modulo(long long __n, unsigned __d);

which also calculates the reminder of __n, where __n is the result of the
addition or subtraction. Hence, these operations might invoke UB before __modulo
is called and thus, __modulo can't do anything to remediate the issue.

In addition to solve the UB issues, __add_modulo and __sub_modulo allow better
codegen (shorter and branchless) on x86-64 and ARM [2].

[1] https://godbolt.org/z/a9YfWdn57
[2] https://godbolt.org/z/Gh36cr7E4

libstdc++-v3/ChangeLog:

	* include/std/chrono: Fix + and - 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.
---
Good for trunk?

Changes with respect to previous versions:
  v5: Fix typos in commit message.
  v4: Remove UB also from operator-.
  v3: Fix screwed up email send with v2.
  v2: Replace _T with _Tp and _U with _Up. Remove copyright+license from test.

 libstdc++-v3/include/std/chrono              | 79 +++++++++++++-------
 libstdc++-v3/testsuite/std/time/month/1.cc   | 19 +++++
 libstdc++-v3/testsuite/std/time/month/2.cc   | 32 ++++++++
 libstdc++-v3/testsuite/std/time/weekday/1.cc | 16 +++-
 libstdc++-v3/testsuite/std/time/weekday/2.cc | 32 ++++++++
 5 files changed, 151 insertions(+), 27 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 e4ba6eafceb..1b7cdb96e1c 100644
--- a/libstdc++-v3/include/std/chrono
+++ b/libstdc++-v3/include/std/chrono
@@ -501,18 +501,47 @@ _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).
+      // Helper to __add_modulo and __sub_modulo.
+      template <unsigned __d, typename _Tp>
+      constexpr auto
+      __modulo_offset()
+      {
+	using _Up = make_unsigned_t<_Tp>;
+	auto constexpr __a = _Up(-1) - _Up(255 + __d - 2);
+	auto constexpr __b = _Up(__d * (__a / __d) - 1);
+	// Notice: b <= a - 1 <= _Up(-1) - (255 + d - 1) and b % d = d - 1.
+	return _Up(-1) - __b; // >= 255 + d - 1
+      }
+
+      // 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 with a shift in [0, d - 1] and __y is a duration count.
+      template <unsigned __d, typename _Tp>
+      constexpr unsigned
+      __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 subtract from _Up(__y) an __offset >=
+	// 255 + d - 1 to make room for the addition to __x and shift the modulo
+	// to the correct value.
+	auto const __offset = __y >= 0 ? _Up(0) : __modulo_offset<__d, _Tp>();
+	return (__x + _Up(__y) - __offset) % __d;
+      }
+
+      // Similar to __add_modulo but for __x - __y.
+      template <unsigned __d, typename _Tp>
       constexpr unsigned
-      __modulo(long long __n, unsigned __d)
+      __sub_modulo(unsigned __x, _Tp __y)
       {
-	if (__n >= 0)
-	  return __n % __d;
-	else
-	  return (__d + (__n % __d)) % __d;
+	using _Up = make_unsigned_t<_Tp>;
+	auto const __offset = __y <= 0 ? _Up(0) : __modulo_offset<__d, _Tp>();
+	return (__x - _Up(__y) - __offset) % __d;
       }

       inline constexpr unsigned __days_per_month[12]
@@ -704,8 +733,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       friend constexpr month
       operator+(const month& __x, const months& __y) noexcept
       {
-	auto __n = static_cast<long long>(unsigned{__x}) + (__y.count() - 1);
-	return month{__detail::__modulo(__n, 12) + 1};
+	// modulo(x + (y - 1), 12) = modulo(x + (y - 1) + 12, 12)
+	//                         = modulo((x + 11) + y    , 12)
+	return month{1 + __detail::__add_modulo<12>(
+	  unsigned{__x} + 11, __y.count())};
       }

       friend constexpr month
@@ -714,7 +745,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION

       friend constexpr month
       operator-(const month& __x, const months& __y) noexcept
-      { return __x + -__y; }
+      {
+	// modulo(x + (-y - 1), 12) = modulo(x + (-y - 1) + 12, 12)
+	//                          = modulo((x + 11) - y     , 12)
+	return month{1 + __detail::__sub_modulo<12>(
+	  unsigned{__x} + 11, __y.count())};
+      }

       friend constexpr months
       operator-(const month& __x,  const month& __y) noexcept
@@ -934,15 +970,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       static constexpr weekday
       _S_from_days(const days& __d)
       {
-	using _Rep = days::rep;
-	using _URep = make_unsigned_t<_Rep>;
-	const auto __n = __d.count();
-	const auto __m = static_cast<_URep>(__n);
-
-	// 1970-01-01 (__n =  0, __m = 0        ) -> Thursday (4)
-	// 1969-31-12 (__n = -1, __m = _URep(-1)) -> Wednesday (3)
-	const auto __offset = __n >= 0 ? _URep(4) : 3 - _URep(-1) % 7 - 7;
-	return weekday((__m + __offset) % 7);
+	return weekday{__detail::__add_modulo<7>(4, __d.count())};
       }

     public:
@@ -1032,8 +1060,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       friend constexpr weekday
       operator+(const weekday& __x, const days& __y) noexcept
       {
-	auto __n = static_cast<long long>(__x._M_wd) + __y.count();
-	return weekday{__detail::__modulo(__n, 7)};
+	return weekday{__detail::__add_modulo<7>(__x._M_wd, __y.count())};
       }

       friend constexpr weekday
@@ -1042,7 +1069,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION

       friend constexpr weekday
       operator-(const weekday& __x, const days& __y) noexcept
-      { return __x + -__y; }
+      {
+	return weekday{__detail::__sub_modulo<7>(__x._M_wd, __y.count())};
+      }

       friend constexpr days
       operator-(const weekday& __x, const weekday& __y) noexcept
diff --git a/libstdc++-v3/testsuite/std/time/month/1.cc b/libstdc++-v3/testsuite/std/time/month/1.cc
index 773f772bf07..1b3612f27e3 100644
--- a/libstdc++-v3/testsuite/std/time/month/1.cc
+++ b/libstdc++-v3/testsuite/std/time/month/1.cc
@@ -20,6 +20,7 @@
 // Class template day [time.cal.month]

 #include <chrono>
+#include <limits>

 constexpr void
 constexpr_month()
@@ -34,6 +35,24 @@ constexpr_month()
   dm += months{3};
   dm -= months{3};

+  // Test for UB (overflow).
+  {
+    using rep = months::rep;
+    using std::numeric_limits;
+
+    auto constexpr months_min = months{numeric_limits<rep>::min()};
+    auto constexpr month_000_plus_months_min  = month{ 0 } + months_min;
+    auto constexpr month_255_plus_months_min  = month{255} + months_min;
+    auto constexpr month_000_minus_months_min = month{ 0 } - months_min;
+    auto constexpr month_255_minus_months_min = month{255} - months_min;
+
+    auto constexpr months_max = months{numeric_limits<rep>::max()};
+    auto constexpr month_000_plus_months_max  = month{ 0 } + months_max;
+    auto constexpr month_255_plus_months_max  = month{255} + months_max;
+    auto constexpr month_000_minus_months_max = month{ 0 } - months_max;
+    auto constexpr month_255_minus_months_max = month{255} - months_max;
+  }
+
   static_assert(February + months{11} == January);
   static_assert(January + months{1200} == January);
   static_assert(January + months{1201} == February);
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..3bcefa60003
--- /dev/null
+++ b/libstdc++-v3/testsuite/std/time/month/2.cc
@@ -0,0 +1,32 @@
+// { dg-do run { target c++20 } }
+
+// Class month [time.cal.month]
+
+#include <chrono>
+#include <limits>
+#include <testsuite_hooks.h>
+
+using namespace std::chrono;
+
+void test_extreme_values(months extreme)
+{
+  auto const count = extreme.count();
+  auto const safe  = count < 0 ? count + 12 : count;
+  auto const mod   = safe - 12 * ((safe < 0 ? safe - 11 : safe) / 12);
+
+  for (unsigned m = 0; m < 256; ++m)
+  {
+    auto const month_plus_extreme = month{m} + extreme;
+    VERIFY(unsigned{month_plus_extreme } == (m + 11 + mod) % 12 + 1);
+
+    auto const month_minus_extreme = month{m} - extreme;
+    VERIFY(unsigned{month_minus_extreme} == (m + 11 - mod) % 12 + 1);
+  }
+}
+
+int main()
+{
+  test_extreme_values(months{std::numeric_limits<months::rep>::max()});
+  test_extreme_values(months{std::numeric_limits<months::rep>::min()});
+  return 0;
+}
diff --git a/libstdc++-v3/testsuite/std/time/weekday/1.cc b/libstdc++-v3/testsuite/std/time/weekday/1.cc
index e89fca47d4b..2f0249b28a4 100644
--- a/libstdc++-v3/testsuite/std/time/weekday/1.cc
+++ b/libstdc++-v3/testsuite/std/time/weekday/1.cc
@@ -42,8 +42,20 @@ constexpr_weekday()
   {
     using rep = days::rep;
     using std::numeric_limits;
-    constexpr weekday max{sys_days{days{numeric_limits<rep>::max()}}};
-    constexpr weekday min{sys_days{days{numeric_limits<rep>::min()}}};
+
+    auto constexpr days_min = days{numeric_limits<rep>::min()};
+    auto constexpr weekday_from_sysdays_min   = weekday{sys_days{days_min}};
+    auto constexpr weekday_000_plus_days_min  = weekday{ 0 } + days_min;
+    auto constexpr weekday_255_plus_days_min  = weekday{255} + days_min;
+    auto constexpr weekday_000_minus_days_min = weekday{ 0 } - days_min;
+    auto constexpr weekday_255_minus_days_min = weekday{255} - days_min;
+
+    auto constexpr days_max = days{numeric_limits<rep>::max()};
+    auto constexpr weekday_from_sysdays_max   = weekday{sys_days{days_max}};
+    auto constexpr weekday_000_plus_days_max  = weekday{ 0 } + days_max;
+    auto constexpr weekday_255_plus_days_max  = weekday{255} + days_max;
+    auto constexpr weekday_000_minus_days_max = weekday{ 0 } - days_max;
+    auto constexpr weekday_255_minus_days_max = weekday{255} - days_max;
   }

   static_assert(weekday{sys_days{1900y/January/1}} == Monday);
diff --git a/libstdc++-v3/testsuite/std/time/weekday/2.cc b/libstdc++-v3/testsuite/std/time/weekday/2.cc
new file mode 100644
index 00000000000..924709321e5
--- /dev/null
+++ b/libstdc++-v3/testsuite/std/time/weekday/2.cc
@@ -0,0 +1,32 @@
+// { dg-do run { target c++20 } }
+
+// Class weekday [time.cal.wd]
+
+#include <chrono>
+#include <limits>
+#include <testsuite_hooks.h>
+
+using namespace std::chrono;
+
+void test_extreme_values(days extreme)
+{
+  auto const count = extreme.count();
+  auto const safe  = count < 0 ? count + 7 : count;
+  auto const mod   = safe - 7 * ((safe < 0 ? safe - 6 : safe) / 7);
+
+  for (unsigned d = 0; d < 254; ++d)
+  {
+    auto const weekday_plus_extreme = weekday{d} + extreme;
+    VERIFY(weekday_plus_extreme.c_encoding()  == (d + mod) % 7);
+
+    auto const weekday_minus_extreme = weekday{d} - extreme;
+    VERIFY(weekday_minus_extreme.c_encoding() == (d + 7 - mod) % 7);
+  }
+}
+
+int main()
+{
+  test_extreme_values(days{std::numeric_limits<days::rep>::max()});
+  test_extreme_values(days{std::numeric_limits<days::rep>::min()});
+  return 0;
+}
--
2.41.0

ping: [PATCH v5] libstdc++: Remove UB from month and weekday additions and subtractions.

[Cassio Neri]

[-- Attachment #1: Type: text/plain, Size: 14413 bytes --]

ping.

On Sat, 25 Nov 2023 at 13:52, Cassio Neri <cassio.neri@gmail.com> wrote:

> The following invoke signed integer overflow (UB) [1]:
>
>   month   + months{MAX} // where MAX is the maximum value of months::rep
>   month   + months{MIN} // where MIN is the maximum value of months::rep
>   month   - months{MIN} // where MIN is the minimum value of months::rep
>   weekday + days  {MAX} // where MAX is the maximum value of days::rep
>   weekday - days  {MIN} // where MIN is the minimum value of days::rep
>
> For the additions to MAX, the crux of the problem is that, in libstdc++,
> months::rep and days::rep are int64_t. Other implementations use int32_t,
> cast
> operands to int64_t and perform arithmetic operations without risk of
> overflowing.
>
> For month + months{MIN}, the implementation follows the Standard's "returns
> clause" and evaluates:
>
>    modulo(static_cast<long long>(unsigned{__x}) + (__y.count() - 1), 12);
>
> Overflow occurs when MIN - 1 is evaluated. Casting to a larger type could
> help
> but, unfortunately again, this is not possible for libstdc++.
>
> For the subtraction of MIN, the problem is that -MIN is not representable.
>
> It's fair to say that the intention is for these additions/subtractions to
> be performed in modulus (12 or 7) arithmetic so that no overflow is
> expected.
>
> To fix these UB, this patch implements:
>
>   template <unsigned __d, typename _T>
>   unsigned __add_modulo(unsigned __x, _T __y);
>
>   template <unsigned __d, typename _T>
>   unsigned __sub_modulo(unsigned __x, _T __y);
>
> which respectively, returns the remainder of Euclidean division of, __x +
> __y
> and __x - __y by __d without overflowing. These functions replace
>
>   constexpr unsigned __modulo(long long __n, unsigned __d);
>
> which also calculates the reminder of __n, where __n is the result of the
> addition or subtraction. Hence, these operations might invoke UB before
> __modulo
> is called and thus, __modulo can't do anything to remediate the issue.
>
> In addition to solve the UB issues, __add_modulo and __sub_modulo allow
> better
> codegen (shorter and branchless) on x86-64 and ARM [2].
>
> [1] https://godbolt.org/z/a9YfWdn57
> [2] https://godbolt.org/z/Gh36cr7E4
>
> libstdc++-v3/ChangeLog:
>
>         * include/std/chrono: Fix + and - 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.
> ---
> Good for trunk?
>
> Changes with respect to previous versions:
>   v5: Fix typos in commit message.
>   v4: Remove UB also from operator-.
>   v3: Fix screwed up email send with v2.
>   v2: Replace _T with _Tp and _U with _Up. Remove copyright+license from
> test.
>
>  libstdc++-v3/include/std/chrono              | 79 +++++++++++++-------
>  libstdc++-v3/testsuite/std/time/month/1.cc   | 19 +++++
>  libstdc++-v3/testsuite/std/time/month/2.cc   | 32 ++++++++
>  libstdc++-v3/testsuite/std/time/weekday/1.cc | 16 +++-
>  libstdc++-v3/testsuite/std/time/weekday/2.cc | 32 ++++++++
>  5 files changed, 151 insertions(+), 27 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 e4ba6eafceb..1b7cdb96e1c 100644
> --- a/libstdc++-v3/include/std/chrono
> +++ b/libstdc++-v3/include/std/chrono
> @@ -501,18 +501,47 @@ _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).
> +      // Helper to __add_modulo and __sub_modulo.
> +      template <unsigned __d, typename _Tp>
> +      constexpr auto
> +      __modulo_offset()
> +      {
> +       using _Up = make_unsigned_t<_Tp>;
> +       auto constexpr __a = _Up(-1) - _Up(255 + __d - 2);
> +       auto constexpr __b = _Up(__d * (__a / __d) - 1);
> +       // Notice: b <= a - 1 <= _Up(-1) - (255 + d - 1) and b % d = d - 1.
> +       return _Up(-1) - __b; // >= 255 + d - 1
> +      }
> +
> +      // 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 with a shift in [0, d - 1] and __y is a duration
> count.
> +      template <unsigned __d, typename _Tp>
> +      constexpr unsigned
> +      __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 subtract from _Up(__y) an __offset >=
> +       // 255 + d - 1 to make room for the addition to __x and shift the
> modulo
> +       // to the correct value.
> +       auto const __offset = __y >= 0 ? _Up(0) : __modulo_offset<__d,
> _Tp>();
> +       return (__x + _Up(__y) - __offset) % __d;
> +      }
> +
> +      // Similar to __add_modulo but for __x - __y.
> +      template <unsigned __d, typename _Tp>
>        constexpr unsigned
> -      __modulo(long long __n, unsigned __d)
> +      __sub_modulo(unsigned __x, _Tp __y)
>        {
> -       if (__n >= 0)
> -         return __n % __d;
> -       else
> -         return (__d + (__n % __d)) % __d;
> +       using _Up = make_unsigned_t<_Tp>;
> +       auto const __offset = __y <= 0 ? _Up(0) : __modulo_offset<__d,
> _Tp>();
> +       return (__x - _Up(__y) - __offset) % __d;
>        }
>
>        inline constexpr unsigned __days_per_month[12]
> @@ -704,8 +733,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>        friend constexpr month
>        operator+(const month& __x, const months& __y) noexcept
>        {
> -       auto __n = static_cast<long long>(unsigned{__x}) + (__y.count() -
> 1);
> -       return month{__detail::__modulo(__n, 12) + 1};
> +       // modulo(x + (y - 1), 12) = modulo(x + (y - 1) + 12, 12)
> +       //                         = modulo((x + 11) + y    , 12)
> +       return month{1 + __detail::__add_modulo<12>(
> +         unsigned{__x} + 11, __y.count())};
>        }
>
>        friend constexpr month
> @@ -714,7 +745,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>
>        friend constexpr month
>        operator-(const month& __x, const months& __y) noexcept
> -      { return __x + -__y; }
> +      {
> +       // modulo(x + (-y - 1), 12) = modulo(x + (-y - 1) + 12, 12)
> +       //                          = modulo((x + 11) - y     , 12)
> +       return month{1 + __detail::__sub_modulo<12>(
> +         unsigned{__x} + 11, __y.count())};
> +      }
>
>        friend constexpr months
>        operator-(const month& __x,  const month& __y) noexcept
> @@ -934,15 +970,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>        static constexpr weekday
>        _S_from_days(const days& __d)
>        {
> -       using _Rep = days::rep;
> -       using _URep = make_unsigned_t<_Rep>;
> -       const auto __n = __d.count();
> -       const auto __m = static_cast<_URep>(__n);
> -
> -       // 1970-01-01 (__n =  0, __m = 0        ) -> Thursday (4)
> -       // 1969-31-12 (__n = -1, __m = _URep(-1)) -> Wednesday (3)
> -       const auto __offset = __n >= 0 ? _URep(4) : 3 - _URep(-1) % 7 - 7;
> -       return weekday((__m + __offset) % 7);
> +       return weekday{__detail::__add_modulo<7>(4, __d.count())};
>        }
>
>      public:
> @@ -1032,8 +1060,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>        friend constexpr weekday
>        operator+(const weekday& __x, const days& __y) noexcept
>        {
> -       auto __n = static_cast<long long>(__x._M_wd) + __y.count();
> -       return weekday{__detail::__modulo(__n, 7)};
> +       return weekday{__detail::__add_modulo<7>(__x._M_wd, __y.count())};
>        }
>
>        friend constexpr weekday
> @@ -1042,7 +1069,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>
>        friend constexpr weekday
>        operator-(const weekday& __x, const days& __y) noexcept
> -      { return __x + -__y; }
> +      {
> +       return weekday{__detail::__sub_modulo<7>(__x._M_wd, __y.count())};
> +      }
>
>        friend constexpr days
>        operator-(const weekday& __x, const weekday& __y) noexcept
> diff --git a/libstdc++-v3/testsuite/std/time/month/1.cc
> b/libstdc++-v3/testsuite/std/time/month/1.cc
> index 773f772bf07..1b3612f27e3 100644
> --- a/libstdc++-v3/testsuite/std/time/month/1.cc
> +++ b/libstdc++-v3/testsuite/std/time/month/1.cc
> @@ -20,6 +20,7 @@
>  // Class template day [time.cal.month]
>
>  #include <chrono>
> +#include <limits>
>
>  constexpr void
>  constexpr_month()
> @@ -34,6 +35,24 @@ constexpr_month()
>    dm += months{3};
>    dm -= months{3};
>
> +  // Test for UB (overflow).
> +  {
> +    using rep = months::rep;
> +    using std::numeric_limits;
> +
> +    auto constexpr months_min = months{numeric_limits<rep>::min()};
> +    auto constexpr month_000_plus_months_min  = month{ 0 } + months_min;
> +    auto constexpr month_255_plus_months_min  = month{255} + months_min;
> +    auto constexpr month_000_minus_months_min = month{ 0 } - months_min;
> +    auto constexpr month_255_minus_months_min = month{255} - months_min;
> +
> +    auto constexpr months_max = months{numeric_limits<rep>::max()};
> +    auto constexpr month_000_plus_months_max  = month{ 0 } + months_max;
> +    auto constexpr month_255_plus_months_max  = month{255} + months_max;
> +    auto constexpr month_000_minus_months_max = month{ 0 } - months_max;
> +    auto constexpr month_255_minus_months_max = month{255} - months_max;
> +  }
> +
>    static_assert(February + months{11} == January);
>    static_assert(January + months{1200} == January);
>    static_assert(January + months{1201} == February);
> 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..3bcefa60003
> --- /dev/null
> +++ b/libstdc++-v3/testsuite/std/time/month/2.cc
> @@ -0,0 +1,32 @@
> +// { dg-do run { target c++20 } }
> +
> +// Class month [time.cal.month]
> +
> +#include <chrono>
> +#include <limits>
> +#include <testsuite_hooks.h>
> +
> +using namespace std::chrono;
> +
> +void test_extreme_values(months extreme)
> +{
> +  auto const count = extreme.count();
> +  auto const safe  = count < 0 ? count + 12 : count;
> +  auto const mod   = safe - 12 * ((safe < 0 ? safe - 11 : safe) / 12);
> +
> +  for (unsigned m = 0; m < 256; ++m)
> +  {
> +    auto const month_plus_extreme = month{m} + extreme;
> +    VERIFY(unsigned{month_plus_extreme } == (m + 11 + mod) % 12 + 1);
> +
> +    auto const month_minus_extreme = month{m} - extreme;
> +    VERIFY(unsigned{month_minus_extreme} == (m + 11 - mod) % 12 + 1);
> +  }
> +}
> +
> +int main()
> +{
> +  test_extreme_values(months{std::numeric_limits<months::rep>::max()});
> +  test_extreme_values(months{std::numeric_limits<months::rep>::min()});
> +  return 0;
> +}
> diff --git a/libstdc++-v3/testsuite/std/time/weekday/1.cc
> b/libstdc++-v3/testsuite/std/time/weekday/1.cc
> index e89fca47d4b..2f0249b28a4 100644
> --- a/libstdc++-v3/testsuite/std/time/weekday/1.cc
> +++ b/libstdc++-v3/testsuite/std/time/weekday/1.cc
> @@ -42,8 +42,20 @@ constexpr_weekday()
>    {
>      using rep = days::rep;
>      using std::numeric_limits;
> -    constexpr weekday max{sys_days{days{numeric_limits<rep>::max()}}};
> -    constexpr weekday min{sys_days{days{numeric_limits<rep>::min()}}};
> +
> +    auto constexpr days_min = days{numeric_limits<rep>::min()};
> +    auto constexpr weekday_from_sysdays_min   =
> weekday{sys_days{days_min}};
> +    auto constexpr weekday_000_plus_days_min  = weekday{ 0 } + days_min;
> +    auto constexpr weekday_255_plus_days_min  = weekday{255} + days_min;
> +    auto constexpr weekday_000_minus_days_min = weekday{ 0 } - days_min;
> +    auto constexpr weekday_255_minus_days_min = weekday{255} - days_min;
> +
> +    auto constexpr days_max = days{numeric_limits<rep>::max()};
> +    auto constexpr weekday_from_sysdays_max   =
> weekday{sys_days{days_max}};
> +    auto constexpr weekday_000_plus_days_max  = weekday{ 0 } + days_max;
> +    auto constexpr weekday_255_plus_days_max  = weekday{255} + days_max;
> +    auto constexpr weekday_000_minus_days_max = weekday{ 0 } - days_max;
> +    auto constexpr weekday_255_minus_days_max = weekday{255} - days_max;
>    }
>
>    static_assert(weekday{sys_days{1900y/January/1}} == Monday);
> diff --git a/libstdc++-v3/testsuite/std/time/weekday/2.cc
> b/libstdc++-v3/testsuite/std/time/weekday/2.cc
> new file mode 100644
> index 00000000000..924709321e5
> --- /dev/null
> +++ b/libstdc++-v3/testsuite/std/time/weekday/2.cc
> @@ -0,0 +1,32 @@
> +// { dg-do run { target c++20 } }
> +
> +// Class weekday [time.cal.wd]
> +
> +#include <chrono>
> +#include <limits>
> +#include <testsuite_hooks.h>
> +
> +using namespace std::chrono;
> +
> +void test_extreme_values(days extreme)
> +{
> +  auto const count = extreme.count();
> +  auto const safe  = count < 0 ? count + 7 : count;
> +  auto const mod   = safe - 7 * ((safe < 0 ? safe - 6 : safe) / 7);
> +
> +  for (unsigned d = 0; d < 254; ++d)
> +  {
> +    auto const weekday_plus_extreme = weekday{d} + extreme;
> +    VERIFY(weekday_plus_extreme.c_encoding()  == (d + mod) % 7);
> +
> +    auto const weekday_minus_extreme = weekday{d} - extreme;
> +    VERIFY(weekday_minus_extreme.c_encoding() == (d + 7 - mod) % 7);
> +  }
> +}
> +
> +int main()
> +{
> +  test_extreme_values(days{std::numeric_limits<days::rep>::max()});
> +  test_extreme_values(days{std::numeric_limits<days::rep>::min()});
> +  return 0;
> +}
> --
> 2.41.0
>
>

[PING,PATCH v5] libstdc++: Remove UB from month and weekday additions and subtractions.

[Cassio Neri]

The following invoke signed integer overflow (UB) [1]:

  month   + months{MAX} // where MAX is the maximum value of months::rep
  month   + months{MIN} // where MIN is the maximum value of months::rep
  month   - months{MIN} // where MIN is the minimum value of months::rep
  weekday + days  {MAX} // where MAX is the maximum value of days::rep
  weekday - days  {MIN} // where MIN is the minimum value of days::rep

For the additions to MAX, the crux of the problem is that, in libstdc++,
months::rep and days::rep are int64_t. Other implementations use int32_t, cast
operands to int64_t and perform arithmetic operations without risk of
overflowing.

For month + months{MIN}, the implementation follows the Standard's "returns
clause" and evaluates:

   modulo(static_cast<long long>(unsigned{__x}) + (__y.count() - 1), 12);

Overflow occurs when MIN - 1 is evaluated. Casting to a larger type could help
but, unfortunately again, this is not possible for libstdc++.

For the subtraction of MIN, the problem is that -MIN is not representable.

It's fair to say that the intention is for these additions/subtractions to
be performed in modulus (12 or 7) arithmetic so that no overflow is expected.

To fix these UB, this patch implements:

  template <unsigned __d, typename _T>
  unsigned __add_modulo(unsigned __x, _T __y);

  template <unsigned __d, typename _T>
  unsigned __sub_modulo(unsigned __x, _T __y);

which respectively, returns the remainder of Euclidean division of, __x + __y
and __x - __y by __d without overflowing. These functions replace

  constexpr unsigned __modulo(long long __n, unsigned __d);

which also calculates the reminder of __n, where __n is the result of the
addition or subtraction. Hence, these operations might invoke UB before __modulo
is called and thus, __modulo can't do anything to remediate the issue.

In addition to solve the UB issues, __add_modulo and __sub_modulo allow better
codegen (shorter and branchless) on x86-64 and ARM [2].

[1] https://godbolt.org/z/a9YfWdn57
[2] https://godbolt.org/z/Gh36cr7E4

libstdc++-v3/ChangeLog:

	* include/std/chrono: Fix + and - 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.
---

Ping.

Good for trunk?

Changes with respect to previous versions:
  v5: Fix typos in commit message.
  v4: Remove UB also from operator-.
  v3: Fix screwed up email send with v2.
  v2: Replace _T with _Tp and _U with _Up. Remove copyright+license from test.

 libstdc++-v3/include/std/chrono              | 79 +++++++++++++-------
 libstdc++-v3/testsuite/std/time/month/1.cc   | 19 +++++
 libstdc++-v3/testsuite/std/time/month/2.cc   | 32 ++++++++
 libstdc++-v3/testsuite/std/time/weekday/1.cc | 16 +++-
 libstdc++-v3/testsuite/std/time/weekday/2.cc | 32 ++++++++
 5 files changed, 151 insertions(+), 27 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 e4ba6eafceb..1b7cdb96e1c 100644
--- a/libstdc++-v3/include/std/chrono
+++ b/libstdc++-v3/include/std/chrono
@@ -501,18 +501,47 @@ _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).
+      // Helper to __add_modulo and __sub_modulo.
+      template <unsigned __d, typename _Tp>
+      constexpr auto
+      __modulo_offset()
+      {
+	using _Up = make_unsigned_t<_Tp>;
+	auto constexpr __a = _Up(-1) - _Up(255 + __d - 2);
+	auto constexpr __b = _Up(__d * (__a / __d) - 1);
+	// Notice: b <= a - 1 <= _Up(-1) - (255 + d - 1) and b % d = d - 1.
+	return _Up(-1) - __b; // >= 255 + d - 1
+      }
+
+      // 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 with a shift in [0, d - 1] and __y is a duration count.
+      template <unsigned __d, typename _Tp>
+      constexpr unsigned
+      __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 subtract from _Up(__y) an __offset >=
+	// 255 + d - 1 to make room for the addition to __x and shift the modulo
+	// to the correct value.
+	auto const __offset = __y >= 0 ? _Up(0) : __modulo_offset<__d, _Tp>();
+	return (__x + _Up(__y) - __offset) % __d;
+      }
+
+      // Similar to __add_modulo but for __x - __y.
+      template <unsigned __d, typename _Tp>
       constexpr unsigned
-      __modulo(long long __n, unsigned __d)
+      __sub_modulo(unsigned __x, _Tp __y)
       {
-	if (__n >= 0)
-	  return __n % __d;
-	else
-	  return (__d + (__n % __d)) % __d;
+	using _Up = make_unsigned_t<_Tp>;
+	auto const __offset = __y <= 0 ? _Up(0) : __modulo_offset<__d, _Tp>();
+	return (__x - _Up(__y) - __offset) % __d;
       }

       inline constexpr unsigned __days_per_month[12]
@@ -704,8 +733,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       friend constexpr month
       operator+(const month& __x, const months& __y) noexcept
       {
-	auto __n = static_cast<long long>(unsigned{__x}) + (__y.count() - 1);
-	return month{__detail::__modulo(__n, 12) + 1};
+	// modulo(x + (y - 1), 12) = modulo(x + (y - 1) + 12, 12)
+	//                         = modulo((x + 11) + y    , 12)
+	return month{1 + __detail::__add_modulo<12>(
+	  unsigned{__x} + 11, __y.count())};
       }

       friend constexpr month
@@ -714,7 +745,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION

       friend constexpr month
       operator-(const month& __x, const months& __y) noexcept
-      { return __x + -__y; }
+      {
+	// modulo(x + (-y - 1), 12) = modulo(x + (-y - 1) + 12, 12)
+	//                          = modulo((x + 11) - y     , 12)
+	return month{1 + __detail::__sub_modulo<12>(
+	  unsigned{__x} + 11, __y.count())};
+      }

       friend constexpr months
       operator-(const month& __x,  const month& __y) noexcept
@@ -934,15 +970,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       static constexpr weekday
       _S_from_days(const days& __d)
       {
-	using _Rep = days::rep;
-	using _URep = make_unsigned_t<_Rep>;
-	const auto __n = __d.count();
-	const auto __m = static_cast<_URep>(__n);
-
-	// 1970-01-01 (__n =  0, __m = 0        ) -> Thursday (4)
-	// 1969-31-12 (__n = -1, __m = _URep(-1)) -> Wednesday (3)
-	const auto __offset = __n >= 0 ? _URep(4) : 3 - _URep(-1) % 7 - 7;
-	return weekday((__m + __offset) % 7);
+	return weekday{__detail::__add_modulo<7>(4, __d.count())};
       }

     public:
@@ -1032,8 +1060,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       friend constexpr weekday
       operator+(const weekday& __x, const days& __y) noexcept
       {
-	auto __n = static_cast<long long>(__x._M_wd) + __y.count();
-	return weekday{__detail::__modulo(__n, 7)};
+	return weekday{__detail::__add_modulo<7>(__x._M_wd, __y.count())};
       }

       friend constexpr weekday
@@ -1042,7 +1069,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION

       friend constexpr weekday
       operator-(const weekday& __x, const days& __y) noexcept
-      { return __x + -__y; }
+      {
+	return weekday{__detail::__sub_modulo<7>(__x._M_wd, __y.count())};
+      }

       friend constexpr days
       operator-(const weekday& __x, const weekday& __y) noexcept
diff --git a/libstdc++-v3/testsuite/std/time/month/1.cc b/libstdc++-v3/testsuite/std/time/month/1.cc
index 773f772bf07..1b3612f27e3 100644
--- a/libstdc++-v3/testsuite/std/time/month/1.cc
+++ b/libstdc++-v3/testsuite/std/time/month/1.cc
@@ -20,6 +20,7 @@
 // Class template day [time.cal.month]

 #include <chrono>
+#include <limits>

 constexpr void
 constexpr_month()
@@ -34,6 +35,24 @@ constexpr_month()
   dm += months{3};
   dm -= months{3};

+  // Test for UB (overflow).
+  {
+    using rep = months::rep;
+    using std::numeric_limits;
+
+    auto constexpr months_min = months{numeric_limits<rep>::min()};
+    auto constexpr month_000_plus_months_min  = month{ 0 } + months_min;
+    auto constexpr month_255_plus_months_min  = month{255} + months_min;
+    auto constexpr month_000_minus_months_min = month{ 0 } - months_min;
+    auto constexpr month_255_minus_months_min = month{255} - months_min;
+
+    auto constexpr months_max = months{numeric_limits<rep>::max()};
+    auto constexpr month_000_plus_months_max  = month{ 0 } + months_max;
+    auto constexpr month_255_plus_months_max  = month{255} + months_max;
+    auto constexpr month_000_minus_months_max = month{ 0 } - months_max;
+    auto constexpr month_255_minus_months_max = month{255} - months_max;
+  }
+
   static_assert(February + months{11} == January);
   static_assert(January + months{1200} == January);
   static_assert(January + months{1201} == February);
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..3bcefa60003
--- /dev/null
+++ b/libstdc++-v3/testsuite/std/time/month/2.cc
@@ -0,0 +1,32 @@
+// { dg-do run { target c++20 } }
+
+// Class month [time.cal.month]
+
+#include <chrono>
+#include <limits>
+#include <testsuite_hooks.h>
+
+using namespace std::chrono;
+
+void test_extreme_values(months extreme)
+{
+  auto const count = extreme.count();
+  auto const safe  = count < 0 ? count + 12 : count;
+  auto const mod   = safe - 12 * ((safe < 0 ? safe - 11 : safe) / 12);
+
+  for (unsigned m = 0; m < 256; ++m)
+  {
+    auto const month_plus_extreme = month{m} + extreme;
+    VERIFY(unsigned{month_plus_extreme } == (m + 11 + mod) % 12 + 1);
+
+    auto const month_minus_extreme = month{m} - extreme;
+    VERIFY(unsigned{month_minus_extreme} == (m + 11 - mod) % 12 + 1);
+  }
+}
+
+int main()
+{
+  test_extreme_values(months{std::numeric_limits<months::rep>::max()});
+  test_extreme_values(months{std::numeric_limits<months::rep>::min()});
+  return 0;
+}
diff --git a/libstdc++-v3/testsuite/std/time/weekday/1.cc b/libstdc++-v3/testsuite/std/time/weekday/1.cc
index e89fca47d4b..2f0249b28a4 100644
--- a/libstdc++-v3/testsuite/std/time/weekday/1.cc
+++ b/libstdc++-v3/testsuite/std/time/weekday/1.cc
@@ -42,8 +42,20 @@ constexpr_weekday()
   {
     using rep = days::rep;
     using std::numeric_limits;
-    constexpr weekday max{sys_days{days{numeric_limits<rep>::max()}}};
-    constexpr weekday min{sys_days{days{numeric_limits<rep>::min()}}};
+
+    auto constexpr days_min = days{numeric_limits<rep>::min()};
+    auto constexpr weekday_from_sysdays_min   = weekday{sys_days{days_min}};
+    auto constexpr weekday_000_plus_days_min  = weekday{ 0 } + days_min;
+    auto constexpr weekday_255_plus_days_min  = weekday{255} + days_min;
+    auto constexpr weekday_000_minus_days_min = weekday{ 0 } - days_min;
+    auto constexpr weekday_255_minus_days_min = weekday{255} - days_min;
+
+    auto constexpr days_max = days{numeric_limits<rep>::max()};
+    auto constexpr weekday_from_sysdays_max   = weekday{sys_days{days_max}};
+    auto constexpr weekday_000_plus_days_max  = weekday{ 0 } + days_max;
+    auto constexpr weekday_255_plus_days_max  = weekday{255} + days_max;
+    auto constexpr weekday_000_minus_days_max = weekday{ 0 } - days_max;
+    auto constexpr weekday_255_minus_days_max = weekday{255} - days_max;
   }

   static_assert(weekday{sys_days{1900y/January/1}} == Monday);
diff --git a/libstdc++-v3/testsuite/std/time/weekday/2.cc b/libstdc++-v3/testsuite/std/time/weekday/2.cc
new file mode 100644
index 00000000000..924709321e5
--- /dev/null
+++ b/libstdc++-v3/testsuite/std/time/weekday/2.cc
@@ -0,0 +1,32 @@
+// { dg-do run { target c++20 } }
+
+// Class weekday [time.cal.wd]
+
+#include <chrono>
+#include <limits>
+#include <testsuite_hooks.h>
+
+using namespace std::chrono;
+
+void test_extreme_values(days extreme)
+{
+  auto const count = extreme.count();
+  auto const safe  = count < 0 ? count + 7 : count;
+  auto const mod   = safe - 7 * ((safe < 0 ? safe - 6 : safe) / 7);
+
+  for (unsigned d = 0; d < 254; ++d)
+  {
+    auto const weekday_plus_extreme = weekday{d} + extreme;
+    VERIFY(weekday_plus_extreme.c_encoding()  == (d + mod) % 7);
+
+    auto const weekday_minus_extreme = weekday{d} - extreme;
+    VERIFY(weekday_minus_extreme.c_encoding() == (d + 7 - mod) % 7);
+  }
+}
+
+int main()
+{
+  test_extreme_values(days{std::numeric_limits<days::rep>::max()});
+  test_extreme_values(days{std::numeric_limits<days::rep>::min()});
+  return 0;
+}
--
2.41.0

Re: [PATCH v5] libstdc++: Remove UB from month and weekday additions and subtractions.

[Jonathan Wakely]

On Sat, 25 Nov 2023 at 13:52, Cassio Neri wrote:
>
> The following invoke signed integer overflow (UB) [1]:
>
>   month   + months{MAX} // where MAX is the maximum value of months::rep
>   month   + months{MIN} // where MIN is the maximum value of months::rep
>   month   - months{MIN} // where MIN is the minimum value of months::rep
>   weekday + days  {MAX} // where MAX is the maximum value of days::rep
>   weekday - days  {MIN} // where MIN is the minimum value of days::rep
>
> For the additions to MAX, the crux of the problem is that, in libstdc++,
> months::rep and days::rep are int64_t. Other implementations use int32_t, cast
> operands to int64_t and perform arithmetic operations without risk of
> overflowing.
>
> For month + months{MIN}, the implementation follows the Standard's "returns
> clause" and evaluates:
>
>    modulo(static_cast<long long>(unsigned{__x}) + (__y.count() - 1), 12);
>
> Overflow occurs when MIN - 1 is evaluated. Casting to a larger type could help
> but, unfortunately again, this is not possible for libstdc++.
>
> For the subtraction of MIN, the problem is that -MIN is not representable.
>
> It's fair to say that the intention is for these additions/subtractions to
> be performed in modulus (12 or 7) arithmetic so that no overflow is expected.
>
> To fix these UB, this patch implements:
>
>   template <unsigned __d, typename _T>
>   unsigned __add_modulo(unsigned __x, _T __y);
>
>   template <unsigned __d, typename _T>
>   unsigned __sub_modulo(unsigned __x, _T __y);
>
> which respectively, returns the remainder of Euclidean division of, __x + __y
> and __x - __y by __d without overflowing. These functions replace
>
>   constexpr unsigned __modulo(long long __n, unsigned __d);
>
> which also calculates the reminder of __n, where __n is the result of the
> addition or subtraction. Hence, these operations might invoke UB before __modulo
> is called and thus, __modulo can't do anything to remediate the issue.
>
> In addition to solve the UB issues, __add_modulo and __sub_modulo allow better
> codegen (shorter and branchless) on x86-64 and ARM [2].
>
> [1] https://godbolt.org/z/a9YfWdn57
> [2] https://godbolt.org/z/Gh36cr7E4
>
> libstdc++-v3/ChangeLog:
>
>         * include/std/chrono: Fix + and - 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.
> ---
> Good for trunk?
>
> Changes with respect to previous versions:
>   v5: Fix typos in commit message.
>   v4: Remove UB also from operator-.
>   v3: Fix screwed up email send with v2.
>   v2: Replace _T with _Tp and _U with _Up. Remove copyright+license from test.
>
>  libstdc++-v3/include/std/chrono              | 79 +++++++++++++-------
>  libstdc++-v3/testsuite/std/time/month/1.cc   | 19 +++++
>  libstdc++-v3/testsuite/std/time/month/2.cc   | 32 ++++++++
>  libstdc++-v3/testsuite/std/time/weekday/1.cc | 16 +++-
>  libstdc++-v3/testsuite/std/time/weekday/2.cc | 32 ++++++++
>  5 files changed, 151 insertions(+), 27 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 e4ba6eafceb..1b7cdb96e1c 100644
> --- a/libstdc++-v3/include/std/chrono
> +++ b/libstdc++-v3/include/std/chrono
> @@ -501,18 +501,47 @@ _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).
> +      // Helper to __add_modulo and __sub_modulo.
> +      template <unsigned __d, typename _Tp>
> +      constexpr auto

I think this can be consteval. We only use it in C++20 code.

Otherwise this looks good, so I'll make that change and push to trunk. Thanks.

P.S. for some targets we *could* do the arithmetic using 128-bit
integers, but we'd still need this code for targets that don't support
that type. So I think to keep things simpler we might as well just use
this code everywhere. If using 128-bit integers would produce
significantly better codegen we can consider that later.


> +      __modulo_offset()
> +      {
> +       using _Up = make_unsigned_t<_Tp>;
> +       auto constexpr __a = _Up(-1) - _Up(255 + __d - 2);
> +       auto constexpr __b = _Up(__d * (__a / __d) - 1);
> +       // Notice: b <= a - 1 <= _Up(-1) - (255 + d - 1) and b % d = d - 1.
> +       return _Up(-1) - __b; // >= 255 + d - 1
> +      }
> +
> +      // 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 with a shift in [0, d - 1] and __y is a duration count.
> +      template <unsigned __d, typename _Tp>
> +      constexpr unsigned
> +      __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 subtract from _Up(__y) an __offset >=
> +       // 255 + d - 1 to make room for the addition to __x and shift the modulo
> +       // to the correct value.
> +       auto const __offset = __y >= 0 ? _Up(0) : __modulo_offset<__d, _Tp>();
> +       return (__x + _Up(__y) - __offset) % __d;
> +      }
> +
> +      // Similar to __add_modulo but for __x - __y.
> +      template <unsigned __d, typename _Tp>
>        constexpr unsigned
> -      __modulo(long long __n, unsigned __d)
> +      __sub_modulo(unsigned __x, _Tp __y)
>        {
> -       if (__n >= 0)
> -         return __n % __d;
> -       else
> -         return (__d + (__n % __d)) % __d;
> +       using _Up = make_unsigned_t<_Tp>;
> +       auto const __offset = __y <= 0 ? _Up(0) : __modulo_offset<__d, _Tp>();
> +       return (__x - _Up(__y) - __offset) % __d;
>        }
>
>        inline constexpr unsigned __days_per_month[12]
> @@ -704,8 +733,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>        friend constexpr month
>        operator+(const month& __x, const months& __y) noexcept
>        {
> -       auto __n = static_cast<long long>(unsigned{__x}) + (__y.count() - 1);
> -       return month{__detail::__modulo(__n, 12) + 1};
> +       // modulo(x + (y - 1), 12) = modulo(x + (y - 1) + 12, 12)
> +       //                         = modulo((x + 11) + y    , 12)
> +       return month{1 + __detail::__add_modulo<12>(
> +         unsigned{__x} + 11, __y.count())};
>        }
>
>        friend constexpr month
> @@ -714,7 +745,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>
>        friend constexpr month
>        operator-(const month& __x, const months& __y) noexcept
> -      { return __x + -__y; }
> +      {
> +       // modulo(x + (-y - 1), 12) = modulo(x + (-y - 1) + 12, 12)
> +       //                          = modulo((x + 11) - y     , 12)
> +       return month{1 + __detail::__sub_modulo<12>(
> +         unsigned{__x} + 11, __y.count())};
> +      }
>
>        friend constexpr months
>        operator-(const month& __x,  const month& __y) noexcept
> @@ -934,15 +970,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>        static constexpr weekday
>        _S_from_days(const days& __d)
>        {
> -       using _Rep = days::rep;
> -       using _URep = make_unsigned_t<_Rep>;
> -       const auto __n = __d.count();
> -       const auto __m = static_cast<_URep>(__n);
> -
> -       // 1970-01-01 (__n =  0, __m = 0        ) -> Thursday (4)
> -       // 1969-31-12 (__n = -1, __m = _URep(-1)) -> Wednesday (3)
> -       const auto __offset = __n >= 0 ? _URep(4) : 3 - _URep(-1) % 7 - 7;
> -       return weekday((__m + __offset) % 7);
> +       return weekday{__detail::__add_modulo<7>(4, __d.count())};
>        }
>
>      public:
> @@ -1032,8 +1060,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>        friend constexpr weekday
>        operator+(const weekday& __x, const days& __y) noexcept
>        {
> -       auto __n = static_cast<long long>(__x._M_wd) + __y.count();
> -       return weekday{__detail::__modulo(__n, 7)};
> +       return weekday{__detail::__add_modulo<7>(__x._M_wd, __y.count())};
>        }
>
>        friend constexpr weekday
> @@ -1042,7 +1069,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>
>        friend constexpr weekday
>        operator-(const weekday& __x, const days& __y) noexcept
> -      { return __x + -__y; }
> +      {
> +       return weekday{__detail::__sub_modulo<7>(__x._M_wd, __y.count())};
> +      }
>
>        friend constexpr days
>        operator-(const weekday& __x, const weekday& __y) noexcept
> diff --git a/libstdc++-v3/testsuite/std/time/month/1.cc b/libstdc++-v3/testsuite/std/time/month/1.cc
> index 773f772bf07..1b3612f27e3 100644
> --- a/libstdc++-v3/testsuite/std/time/month/1.cc
> +++ b/libstdc++-v3/testsuite/std/time/month/1.cc
> @@ -20,6 +20,7 @@
>  // Class template day [time.cal.month]
>
>  #include <chrono>
> +#include <limits>
>
>  constexpr void
>  constexpr_month()
> @@ -34,6 +35,24 @@ constexpr_month()
>    dm += months{3};
>    dm -= months{3};
>
> +  // Test for UB (overflow).
> +  {
> +    using rep = months::rep;
> +    using std::numeric_limits;
> +
> +    auto constexpr months_min = months{numeric_limits<rep>::min()};
> +    auto constexpr month_000_plus_months_min  = month{ 0 } + months_min;
> +    auto constexpr month_255_plus_months_min  = month{255} + months_min;
> +    auto constexpr month_000_minus_months_min = month{ 0 } - months_min;
> +    auto constexpr month_255_minus_months_min = month{255} - months_min;
> +
> +    auto constexpr months_max = months{numeric_limits<rep>::max()};
> +    auto constexpr month_000_plus_months_max  = month{ 0 } + months_max;
> +    auto constexpr month_255_plus_months_max  = month{255} + months_max;
> +    auto constexpr month_000_minus_months_max = month{ 0 } - months_max;
> +    auto constexpr month_255_minus_months_max = month{255} - months_max;
> +  }
> +
>    static_assert(February + months{11} == January);
>    static_assert(January + months{1200} == January);
>    static_assert(January + months{1201} == February);
> 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..3bcefa60003
> --- /dev/null
> +++ b/libstdc++-v3/testsuite/std/time/month/2.cc
> @@ -0,0 +1,32 @@
> +// { dg-do run { target c++20 } }
> +
> +// Class month [time.cal.month]
> +
> +#include <chrono>
> +#include <limits>
> +#include <testsuite_hooks.h>
> +
> +using namespace std::chrono;
> +
> +void test_extreme_values(months extreme)
> +{
> +  auto const count = extreme.count();
> +  auto const safe  = count < 0 ? count + 12 : count;
> +  auto const mod   = safe - 12 * ((safe < 0 ? safe - 11 : safe) / 12);
> +
> +  for (unsigned m = 0; m < 256; ++m)
> +  {
> +    auto const month_plus_extreme = month{m} + extreme;
> +    VERIFY(unsigned{month_plus_extreme } == (m + 11 + mod) % 12 + 1);
> +
> +    auto const month_minus_extreme = month{m} - extreme;
> +    VERIFY(unsigned{month_minus_extreme} == (m + 11 - mod) % 12 + 1);
> +  }
> +}
> +
> +int main()
> +{
> +  test_extreme_values(months{std::numeric_limits<months::rep>::max()});
> +  test_extreme_values(months{std::numeric_limits<months::rep>::min()});
> +  return 0;
> +}
> diff --git a/libstdc++-v3/testsuite/std/time/weekday/1.cc b/libstdc++-v3/testsuite/std/time/weekday/1.cc
> index e89fca47d4b..2f0249b28a4 100644
> --- a/libstdc++-v3/testsuite/std/time/weekday/1.cc
> +++ b/libstdc++-v3/testsuite/std/time/weekday/1.cc
> @@ -42,8 +42,20 @@ constexpr_weekday()
>    {
>      using rep = days::rep;
>      using std::numeric_limits;
> -    constexpr weekday max{sys_days{days{numeric_limits<rep>::max()}}};
> -    constexpr weekday min{sys_days{days{numeric_limits<rep>::min()}}};
> +
> +    auto constexpr days_min = days{numeric_limits<rep>::min()};
> +    auto constexpr weekday_from_sysdays_min   = weekday{sys_days{days_min}};
> +    auto constexpr weekday_000_plus_days_min  = weekday{ 0 } + days_min;
> +    auto constexpr weekday_255_plus_days_min  = weekday{255} + days_min;
> +    auto constexpr weekday_000_minus_days_min = weekday{ 0 } - days_min;
> +    auto constexpr weekday_255_minus_days_min = weekday{255} - days_min;
> +
> +    auto constexpr days_max = days{numeric_limits<rep>::max()};
> +    auto constexpr weekday_from_sysdays_max   = weekday{sys_days{days_max}};
> +    auto constexpr weekday_000_plus_days_max  = weekday{ 0 } + days_max;
> +    auto constexpr weekday_255_plus_days_max  = weekday{255} + days_max;
> +    auto constexpr weekday_000_minus_days_max = weekday{ 0 } - days_max;
> +    auto constexpr weekday_255_minus_days_max = weekday{255} - days_max;
>    }
>
>    static_assert(weekday{sys_days{1900y/January/1}} == Monday);
> diff --git a/libstdc++-v3/testsuite/std/time/weekday/2.cc b/libstdc++-v3/testsuite/std/time/weekday/2.cc
> new file mode 100644
> index 00000000000..924709321e5
> --- /dev/null
> +++ b/libstdc++-v3/testsuite/std/time/weekday/2.cc
> @@ -0,0 +1,32 @@
> +// { dg-do run { target c++20 } }
> +
> +// Class weekday [time.cal.wd]
> +
> +#include <chrono>
> +#include <limits>
> +#include <testsuite_hooks.h>
> +
> +using namespace std::chrono;
> +
> +void test_extreme_values(days extreme)
> +{
> +  auto const count = extreme.count();
> +  auto const safe  = count < 0 ? count + 7 : count;
> +  auto const mod   = safe - 7 * ((safe < 0 ? safe - 6 : safe) / 7);
> +
> +  for (unsigned d = 0; d < 254; ++d)
> +  {
> +    auto const weekday_plus_extreme = weekday{d} + extreme;
> +    VERIFY(weekday_plus_extreme.c_encoding()  == (d + mod) % 7);
> +
> +    auto const weekday_minus_extreme = weekday{d} - extreme;
> +    VERIFY(weekday_minus_extreme.c_encoding() == (d + 7 - mod) % 7);
> +  }
> +}
> +
> +int main()
> +{
> +  test_extreme_values(days{std::numeric_limits<days::rep>::max()});
> +  test_extreme_values(days{std::numeric_limits<days::rep>::min()});
> +  return 0;
> +}
> --
> 2.41.0
>