From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-lj1-x229.google.com (mail-lj1-x229.google.com [IPv6:2a00:1450:4864:20::229]) by sourceware.org (Postfix) with ESMTPS id DD8E83858D20; Fri, 17 Nov 2023 01:34:25 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org DD8E83858D20 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=gmail.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org DD8E83858D20 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=2a00:1450:4864:20::229 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1700184868; cv=none; b=U5ZqBupr3m8gmLtxtjb0RSVPgDWhhZxNq0OJA1FvIa/NMypOlSuSjqHmSi0yzAYV/vqmDcw/tNM9YJbds7KykVpTAqSF80IcAAmpf1KoTb3dWpzdqPf2edR5s6597JcYTh11GOjEJP9nj2MgLGhQbSg7i6Xg4UodOCN7BHS9hdc= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1700184868; c=relaxed/simple; bh=klm5NbRuslJTqlB0SwM488YNVc2AUaIz/XaTQdU3+iU=; h=DKIM-Signature:From:To:Subject:Date:Message-ID:MIME-Version; b=pNEdE2hqE2YgNoA0AiMKiBLXU/38vvUw2RPvQ6AkYabJQjGbqa8AAWhbK1v6yNwN56BRTZYJdPUyiYb5rpo+doAeQ/oAN9cZ8Je/27dD/PS0yeHJkss98+VWP6mSK27ZFQKmkTehlX2+U0bUQnQVODBnCwrojX27QYDuHnA4hHY= ARC-Authentication-Results: i=1; server2.sourceware.org Received: by mail-lj1-x229.google.com with SMTP id 38308e7fff4ca-2c6b30aca06so19042511fa.3; Thu, 16 Nov 2023 17:34:25 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1700184864; x=1700789664; darn=gcc.gnu.org; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:from:to:cc:subject:date:message-id:reply-to; bh=AkTJpL8tEkWaIsMLOWiDanWZZt+ccGFr3JuIsAIcSuw=; b=nHYMT0jTCkh4TUgONislt/hiuEx5kP6v5jJshDwvLHYHL2RYlWMLBNSLu0TIKpzE9L vt0Q4cjnR2US7lU1Ws0GR9n+xqoOltEZc8GpMOfWU1VbdqccPp9cx9VwLZW7enMnlJUY ZLr7/RYGdl48OBvg+iH95bgBhjPiX1YlK8W8UiEIab+2k8G5/Hw3cZg54/i2jpwypCSn V9q1aQ7SIZ+mW82aAf+HjD6IKUZwliunQqzfq3hLoh0Xqu+jZM/I4EBDW1FAjtBWC2AD dsObU1DbuXMLMfqg5TaYDr+raRbgm9u+QDJM6Xidf3C96WDj/9J5bARl89eK9/VLDst3 XJjA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1700184864; x=1700789664; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=AkTJpL8tEkWaIsMLOWiDanWZZt+ccGFr3JuIsAIcSuw=; b=BstxyVNjtvhjNRlpJpXpt+0cJACy82QtJldQYPFgJlTf8mqIzNHLbQwr3DhPO0DEvy 8NjZFL4B0njKuEQsK3q4WGxCprC8PIHFIt7V/UWBv9M2b6MT6a/7goskmC2WGShQkctb mfYkYYT7R5ZYiIKKSTUCTqWPZmQKrVzO8KkmOgnDrJusojwiT3MhxBL6GjUbsYvZeyE/ Jodxql/1jHRoGrBJkQN0Rys1FxAIr/HYa3882xK5Gi7jk6QN/g973kPC4qj5ixHj7VD3 LYzb+vit833OQB1ZoFreOsPiseHcw7Wal42VjHTfsojV0MLLqPkPeTNG9+16FGMzlHk+ Xysw== X-Gm-Message-State: AOJu0YwhAgfk5fy5el/Wz1uZhD8tLTvcBriqxXkImvhtwaOtQhqkxt3O upgDPESGcUiK1UjhqVzmpUyJ0GHhK7w= X-Google-Smtp-Source: AGHT+IE0fbactd2scgpJMr/Y8EA8uGgVWBJyveeWPFXw/owmNVoCGJx6oEL7xz7Hrkd3aoSjbLJ8Jg== X-Received: by 2002:a2e:b0e8:0:b0:2c7:fa5:6db9 with SMTP id h8-20020a2eb0e8000000b002c70fa56db9mr6993160ljl.48.1700184863356; Thu, 16 Nov 2023 17:34:23 -0800 (PST) Received: from othello.cust.communityfibre.co.uk ([2a02:6b64:8086:0:f9dd:28dd:c9b9:d8f4]) by smtp.gmail.com with ESMTPSA id x7-20020a1c7c07000000b0040684abb623sm5229296wmc.24.2023.11.16.17.34.22 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 16 Nov 2023 17:34:22 -0800 (PST) From: Cassio Neri To: libstdc++@gcc.gnu.org, gcc-patches@gcc.gnu.org Cc: Cassio Neri Subject: [PATCH] libstdc++: Remove UB from operator+ of months and weekdays. Date: Fri, 17 Nov 2023 01:34:13 +0000 Message-ID: <20231117013413.10805-1-cassio.neri@gmail.com> X-Mailer: git-send-email 2.41.0 MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Spam-Status: No, score=-11.9 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,FREEMAIL_FROM,GIT_PATCH_0,KAM_SHORT,RCVD_IN_DNSWL_NONE,SPF_HELO_NONE,SPF_PASS,TXREP,T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org List-Id: 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(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(unsigned{__x}) + (__y.count() - 1), 12); Hence, overflow occurs when __y.count() is the minimum value of its type. When long long is larger than months::rep, this is a fix: modulo(static_cast(unsigned{__x}) + 11 + __y.count(), 12); Again, this is not possible for libstdc++. To fix these UB, this patch implements: template unsigned __add_modulo(unsigned __x, _T __y); which returns the remainder of Euclidean division of __x +__y by __d without overflowing. This function replaces constexpr unsigned __modulo(long long __n, unsigned __d); 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(unsigned{x}) + (y.count() - 1), 12) + 1. + // + // Since y.count() is a 64-bits signed value the subtraction y.count() - 1 + // or the addition of this value with static_cast(unsigned{x}) + // might overflow. This function can be used to avoid this problem: + // __add_modulo<12>(unsigned{x} + 11, y.count()) + 1; + // (More details in the implementation of operator+(month, months).) + template constexpr unsigned - __modulo(long long __n, unsigned __d) - { - if (__n >= 0) - return __n % __d; - else - return (__d + (__n % __d)) % __d; + __add_modulo(unsigned __x, _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(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(__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 +#include 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::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::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 +// . + +// Class month [time.cal.month] + +#include +#include +#include + +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::max()}); + test_extreme_values(months{std::numeric_limits::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::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::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 +// . + +// Class weekday [time.cal.wd] + +#include +#include +#include + +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::max()}); + test_extreme_values(days{std::numeric_limits::min()}); + return 0; +} -- 2.41.0