[PATCH] libstdc++: Optimize chrono year::is_leap

[Francisco Muniz]

Use Falk Hueffner's leap-year test for year::is_leap after shifting
the valid std::chrono::year range by a multiple of 400. The shift
preserves divisibility by 4, 100, and 400, and the unsigned conversion
gives the intended modulo 2^32 arithmetic.

Idea by Cassio Neri: add 32800, which is 82 * 400, to shift the signed
year range into the supported non-negative range.

Tested on x86_64-pc-linux-gnu:
  make -j$(nproc) all-gcc
  make -j$(nproc) all-target-libstdc++-v3
  make check RUNTESTFLAGS='conformance.exp=std/time/year/1.cc'
  make check RUNTESTFLAGS='conformance.exp=std/time/year/2.cc'

libstdc++-v3/ChangeLog:

        * include/std/chrono (year::is_leap): Use Hueffner leap-year
        test after biasing the year by a multiple of 400.

Signed-off-by: Francisco Muniz <munizfco@gmail.com>
---
 libstdc++-v3/include/std/chrono | 31 ++++++++-----------------------
 1 file changed, 8 insertions(+), 23 deletions(-)

diff --git a/libstdc++-v3/include/std/chrono b/libstdc++-v3/include/std/chrono
index 692fd6025e7..4483914c08b 100644
--- a/libstdc++-v3/include/std/chrono
+++ b/libstdc++-v3/include/std/chrono
@@ -904,29 +904,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       constexpr bool
       is_leap() const noexcept
       {
-	// Testing divisibility by 100 first gives better performance [1], i.e.,
-	//     return _M_y % 100 == 0 ? _M_y % 400 == 0 : _M_y % 16 == 0;
-	// Furthermore, if _M_y % 100 == 0, then _M_y % 400 == 0 is equivalent
-	// to _M_y % 16 == 0, so we can simplify it to
-	//     return _M_y % 100 == 0 ? _M_y % 16 == 0 : _M_y % 4 == 0.  // #1
-	// Similarly, we can replace 100 with 25 (which is good since
-	// _M_y % 25 == 0 requires one fewer instruction than _M_y % 100 == 0
-	// [2]):
-	//     return _M_y % 25 == 0 ? _M_y % 16 == 0 : _M_y % 4 == 0.  // #2
-	// Indeed, first assume _M_y % 4 != 0.  Then _M_y % 16 != 0 and hence,
-	// _M_y % 4 == 0 and _M_y % 16 == 0 are both false.  Therefore, #2
-	// returns false as it should (regardless of _M_y % 25.) Now assume
-	// _M_y % 4 == 0.  In this case, _M_y % 25 == 0 if, and only if,
-	// _M_y % 100 == 0, that is, #1 and #2 are equivalent.  Finally, #2 is
-	// equivalent to
-	//     return (_M_y & (_M_y % 25 == 0 ? 15 : 3)) == 0.
-
-	// References:
-	// [1] https://github.com/cassioneri/calendar
-	// [2] https://godbolt.org/z/55G8rn77e
-	// [3] https://gcc.gnu.org/pipermail/libstdc++/2021-June/052815.html
-
-	return (_M_y & (_M_y % 25 == 0 ? 15 : 3)) == 0;
+	// Shift into the range supported by Falk Hueffner's leap-year test:
+	// hueffner.de/falk/blog/a-leap-year-check-in-three-instructions.html
+	// Adding a multiple of 400 preserves divisibility by 4, 100, and 400.
+	// Idea by Cassio Neri: add 32800 (82 * 400).
+	// The conversion to uint32_t gives the algorithm's intended modulo 2^32
+	// arithmetic.
+	const auto __y = static_cast<uint32_t>(_M_y) + 32800u;
+	return ((__y * 1073750999u) & 3221352463u) <= 126976u;
       }
 
       explicit constexpr
-- 
2.47.3