public inbox for gcc-patches@gcc.gnu.org
 help / color / mirror / Atom feed
* [PATCH] libstdc++: Remove UB from operator+ of months and weekdays.
@ 2023-11-17  1:34 Cassio Neri
  2023-11-17 10:15 ` Jonathan Wakely
  0 siblings, 1 reply; 10+ messages in thread
From: Cassio Neri @ 2023-11-17  1:34 UTC (permalink / raw)
  To: libstdc++, gcc-patches; +Cc: 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


^ permalink raw reply	[flat|nested] 10+ messages in thread
end of thread, other threads:[~2023-12-10 13:03 UTC | newest]

Thread overview: 10+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2023-11-17  1:34 [PATCH] libstdc++: Remove UB from operator+ of months and weekdays Cassio Neri
2023-11-17 10:15 ` Jonathan Wakely
2023-11-18  0:06   ` [PATCH v2] The following functions invoke signed integer overflow (UB) for some extreme values of days and months [1]: Cassio Neri
2023-11-18  0:19     ` [PATCH v3] libstdc++: Remove UB from operator+ of months and weekdays Cassio Neri
2023-11-18 11:07       ` Cassio Neri
2023-11-21  2:06       ` [PATCH v4] libstdc++: Remove UB from month and weekday additions and subtractions Cassio Neri
2023-11-25 13:52         ` [PATCH v5] " Cassio Neri
2023-12-01 18:00           ` ping: " Cassio Neri
2023-12-10 11:31           ` [PING,PATCH " Cassio Neri
2023-12-10 13:03           ` [PATCH " Jonathan Wakely

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).