`<chrono>`: integer overflow in `weekday::weekday(sys_days::max())`

[cassioneri]

Brief description

The following code fails to compile due to an int addition overflow:

#include <chrono>

using namespace std::chrono;

constexpr auto wd = weekday(sys_days::max());

https://godbolt.org/z/K6dW7bvYq

Details

The overflow occurs in the evaluation of _Tp + 4 below

        _NODISCARD static constexpr unsigned int _Weekday_from_days(int _Tp) noexcept {
            return static_cast<unsigned int>(_Tp >= -4 ? (_Tp + 4) % 7 : (_Tp + 5) % 7 + 6);
        }

Indeed, this addition overflows whenever _Tp > INT_MAX - 4.

Fixes

Provided that the range of long long int is larger than that of int, the obvious fix is declaring _Tp as long long int and an alternative is this:

        _NODISCARD static constexpr unsigned int _Weekday_from_days(int _Tp) noexcept {
            auto const m = unsigned(_Tp) + (_Tp >= 0 ? 4 : 0);
            auto const w = m % 7;
            __assume(w != 7); // not necessary but improves codegen
            return w;
        }

This alternative is better than the obvious fix and better than the current implementation. Indeed, with this fix the codegen of weekday::weekday(const sys_days&) becomes branch-free and avoids div instructions on x64, x86 and arm64.

Test

The alternative above works as an exhaustive test shows:

int main() {

  unsigned int encoding = weekday(sys_days::min()).c_encoding();
  for (auto s = sys_days::min(); s < sys_days::max(); s += days(1)) {
    assert(weekday_ctr(s).c_encoding() == encoding);
    ++encoding;
    if (encoding == 7)
      encoding = 0;
  }
  // One more to go:
  assert(weekday_ctr(sys_days::max()).c_encoding() == encoding);
  std::puts("Success.");
}

(where weekday_ctr is an impersonation of weekday::weekday(const sys_days&) using the fixed _Weekday_from_days.)

[frederick-vs-ja]

Perhaps __assume in _Weekday_from_days won't be so that helpful, because _Weekday_from_days is only internally used by 2 constructors who don't have any additional branch. Although it might be helpful for optimization to express postconditions of these constructors.

Curiously, when I attempted to simplify the suggestion to just returning (static_cast<unsigned int>(_Tp) + (_Tp >= 0 ? 4U : 0U)) % 7U, MSVC emitted div/udiv instructions even with /O2. The modulo operation can be optimized by MSVC if it is put into a separated statement.

[CaseyCarter]

Curiously, when I attempted to simplify the suggestion to just returning (static_cast<unsigned int>(_Tp) + (_Tp >= 0 ? 4U : 0U)) % 7U, MSVC emitted div/udiv instructions even with /O2. The modulo operation can be optimized by MSVC if it is put into a separated statement.

And here I am being let down that the optimizer doesn't know that some_unsigned_value % 7u is always less than 7u. 🤷‍♂

[cassioneri]

A. Jiang (@frederick-vs-ja)

Perhaps __assume in _Weekday_from_days won't be so that helpful, because _Weekday_from_days is only internally used by 2 constructors who don't have any additional branch. Although it might be helpful for optimization to express postconditions of these constructors.

As Casey Carter (@CaseyCarter) pointed out, it's sad that the compiler cannot figure out that some_unsigned_value % 7 != 7. Hence, the __assume(w != 7). This helps a little bit because the resulting unsigned int feeds the weekday constructor that takes this type of argument and which initializes the field _Weekday as follows:

_Weekday{static_cast<unsigned char>(_Val == 7 ? 0 : _Val)}

By knowing that _Val != 7 (thanks to the __assume clause), the compiler removes the ternary operator altogether. This can be seen in generated x64: when weekday_from_days is as _Weekday_from_days is currently implemented, then just before the two ret instructions in the assembly of weekday_ctr we see a few instructions, notably cmp 7 and cmove, to deal with the ternary operator. My implementation doesn't have that but if you remove the __assume clause, then these instructions will appear.

Having said that, I don't mind if the assume clause is not added but I do believe that my implementation fixes the bug and, although I didn't measure, I also believe it's more efficient than the current one.

I'm sorry I couldn't follow the "normal" process (i.e., checkout, change, add a test, build, run and submit a PR). It would take me long time to learn how to do all that, whereas for a regular STL developer, putting this fix and add a test wouldn't take that much. (FWIW: I did do all that for libstdc++.)

[frederick-vs-ja]

Perhaps the discussion on __assume should be move to another issue.

This helps a little bit because the resulting unsigned int feeds the weekday constructor that takes this type of argument and which initializes the field _Weekday as follows:

_Weekday{static_cast<unsigned char>(_Val == 7 ? 0 : _Val)}

Given the constructors are implemented as below currently:

STL/stl/inc/chrono

Lines 433 to 438 in 5e0ddad

	constexpr explicit weekday(unsigned int _Val) noexcept
	: _Weekday{static_cast<unsigned char>(_Val == 7 ? 0 : _Val)} {}
	constexpr weekday(const sys_days& _Sys_day) noexcept
	: _Weekday{static_cast<unsigned char>(_Weekday_from_days(_Sys_day.time_since_epoch().count()))} {}
	constexpr explicit weekday(const local_days& _Local_day) noexcept
	: _Weekday{static_cast<unsigned char>(_Weekday_from_days(_Local_day.time_since_epoch().count()))} {}

The 2 constructors below are the only callers of weekday_from_days, and IIUC, they aren't delegated to the constructor from unsigned int. So __assume won't improve codegen for these 2 constructors themselves.

However, expressing postconditions may be helpful for callers of weekday constructors.

I'm sorry I couldn't follow the "normal" process (i.e., checkout, change, add a test, build, run and submit a PR). It would take me long time to learn how to do all that, whereas for a regular STL developer, putting this fix and add a test wouldn't take that much. (FWIW: I did do all that for libstdc++.)

I'm now creating a PR and listing you as the co-author. Please double-check it.

[cassioneri]

A. Jiang (@frederick-vs-ja) Oh! You're completely right regarding __assume. (Thanks for the explanation.)

I've made a suggestion in your PR, just in case you wish to support other platforms. Otherwise, the code looks good to me. Thanks for fixing.

[StephanTLavavej]

The overflow occurs in the evaluation of _Tp + 4 below
[...]
Indeed, this addition overflows whenever _Tp > INT_MAX + 4.

Was _Tp > INT_MAX - 4 intended here?

[cassioneri]

Was _Tp > INT_MAX - 4 intended here?

Yes, typo. (Fixed.)