https://gcc.gnu.org/g:0bc36c00b8f06d158da9153d8a913ff705b85f50
commit r17-6047-g0bc36c00b8f06d158da9153d8a913ff705b85f50 Author: Jakub Jelinek <[email protected]> Date: Mon Nov 9 09:56:47 2026 +0100 libstdc++: Implement non-simd part of P3642R7 - Carry-less product: std::clmul The following patch attempts to implement P3642R7 - Carry-less product: std::clmul paper (which is not approved yet). I have committed it with a FTM of 202610, so surely lower than the Buzios meeting. If the paper is approved during that meeting, we can just bump the FTM by 1. 2026-11-09 Jakub Jelinek <[email protected]> * include/bits/version.def (clmul): New FTM. * include/std/numeric (__glibcxx_want_clmul): Define before including bits/version.h. (std::wide_result): New class template. (std::widening_clmul, std::clmul): New function templates. * src/c++23/std.cc.in (std::wide_result, std::widening_clmul, std::clmul): Export for C++29. * testsuite/26_numerics/clmul/1.cc: New test. * include/bits/version.h: Regenerate. Reviewed-by: Jonathan Wakely <[email protected]> Diff: --- libstdc++-v3/include/bits/version.def | 8 + libstdc++-v3/include/bits/version.h | 10 ++ libstdc++-v3/include/std/numeric | 82 +++++++++++ libstdc++-v3/src/c++23/std.cc.in | 5 + libstdc++-v3/testsuite/26_numerics/clmul/1.cc | 205 ++++++++++++++++++++++++++ 5 files changed, 310 insertions(+) diff --git a/libstdc++-v3/include/bits/version.def b/libstdc++-v3/include/bits/version.def index 340ef4203e11..555a43f4dcbf 100644 --- a/libstdc++-v3/include/bits/version.def +++ b/libstdc++-v3/include/bits/version.def @@ -2709,6 +2709,14 @@ ftms = { }; }; +ftms = { + name = clmul; + values = { + v = 202610; + cxxmin = 29; + }; +}; + // Standard test specifications. stds[97] = ">= 199711L"; stds[03] = ">= 199711L"; diff --git a/libstdc++-v3/include/bits/version.h b/libstdc++-v3/include/bits/version.h index 3175bc1b65b4..8e3e190466e5 100644 --- a/libstdc++-v3/include/bits/version.h +++ b/libstdc++-v3/include/bits/version.h @@ -2991,4 +2991,14 @@ #endif /* !defined(__cpp_lib_hardened_view_interface) */ #undef __glibcxx_want_hardened_view_interface +#if !defined(__cpp_lib_clmul) +# if (__cplusplus > 202603L) +# define __glibcxx_clmul 202610L +# if defined(__glibcxx_want_all) || defined(__glibcxx_want_clmul) +# define __cpp_lib_clmul 202610L +# endif +# endif +#endif /* !defined(__cpp_lib_clmul) */ +#undef __glibcxx_want_clmul + #undef __glibcxx_want_all diff --git a/libstdc++-v3/include/std/numeric b/libstdc++-v3/include/std/numeric index f9b1d1eb9472..a54449ca4936 100644 --- a/libstdc++-v3/include/std/numeric +++ b/libstdc++-v3/include/std/numeric @@ -90,6 +90,7 @@ #define __glibcxx_want_parallel_algorithm #define __glibcxx_want_ranges_iota #define __glibcxx_want_saturation_arithmetic +#define __glibcxx_want_clmul #include <bits/version.h> #if __glibcxx_ranges_iota >= 202202L // C++ >= 23 @@ -765,6 +766,87 @@ namespace ranges } // namespace ranges #endif // __glibcxx_ranges_iota +#if __glibcxx_clmul >= 202610L // C++29 + template<typename _Tp> + class wide_result { + public: + static_assert(__is_unsigned_integer<_Tp>::value); + constexpr _Tp high() const noexcept { return _M_high; } + constexpr _Tp low() const noexcept { return _M_low; } + + friend constexpr bool operator==(const wide_result&, + const wide_result&) = default; +#if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__ + constexpr wide_result(_Tp __high, _Tp __low) noexcept + : _M_low(__low), _M_high(__high) {} + friend constexpr strong_ordering operator<=>(const wide_result& __x, + const wide_result& __y) + noexcept + { + if (auto __r = __x._M_high <=> __y._M_high; __r != 0) + return __r; + return __x._M_low <=> __y._M_low; + } + private: + _Tp _M_low, _M_high; +#else + constexpr wide_result(_Tp __high, _Tp __low) noexcept + : _M_high(__high), _M_low(__low) {} + friend constexpr strong_ordering operator<=>(const wide_result& __x, + const wide_result& __y) + noexcept = default; + private: + _Tp _M_high, _M_low; +#endif + }; + + template<__unsigned_integer _Tp> + [[nodiscard]] constexpr wide_result<_Tp> + widening_clmul(_Tp __x, _Tp __y) noexcept + { + _Tp __high, __low; +#if _GLIBCXX_USE_BUILTIN_TRAIT(__builtin_clmulg) + __low = __builtin_clmulg(__x, __y, &__high); + return wide_result<_Tp>(__high, __low); +#elif _GLIBCXX_USE_BUILTIN_TRAIT(__builtin_elementwise_clmul) \ + && _GLIBCXX_USE_BUILTIN_TRAIT(__builtin_bitreverseg) + __low = __builtin_elementwise_clmul(__x, __y); + __high = __builtin_elementwise_clmul(__builtin_bitreverseg(__x), + __builtin_bitreverseg(__y)); + return wide_result<_Tp>(__builtin_bitreverseg(__high) >> 1, __low); +#else + constexpr auto _Nd = __gnu_cxx::__int_traits<_Tp>::__digits; + __high = 0; + __low = (__y & _Tp(1)) ? __x : 0; + for (int __i = 1; __i < _Nd; ++__i) + if ((__y >> __i) & _Tp(1)) + { + __low ^= __x << __i; + __high ^= __x >> (_Nd - __i); + } + return wide_result<_Tp>(__high, __low); +#endif + } + + template<__unsigned_integer _Tp> + [[nodiscard]] constexpr _Tp + clmul(_Tp __x, _Tp __y) noexcept + { +#if _GLIBCXX_USE_BUILTIN_TRAIT(__builtin_clmulg) + return __builtin_clmulg(__x, __y); +#elif _GLIBCXX_USE_BUILTIN_TRAIT(__builtin_elementwise_clmul) + return __builtin_elementwise_clmul(__x, __y); +#else + _Tp __res = 0; + constexpr auto _Nd = __gnu_cxx::__int_traits<_Tp>::__digits; + for (int __i = 0; __i < _Nd; ++__i) + if ((__y >> __i) & _Tp(1)) + __res ^= __x << __i; + return __res; +#endif + } +#endif // C++29 + _GLIBCXX_END_NAMESPACE_VERSION } // namespace std diff --git a/libstdc++-v3/src/c++23/std.cc.in b/libstdc++-v3/src/c++23/std.cc.in index d05902466d97..15349adf1be0 100644 --- a/libstdc++-v3/src/c++23/std.cc.in +++ b/libstdc++-v3/src/c++23/std.cc.in @@ -2483,6 +2483,11 @@ export namespace std using std::saturating_div; using std::saturating_cast; #endif +#if __cpp_lib_clmul + using std::wide_result; + using std::widening_clmul; + using std::clmul; +#endif } // <optional> diff --git a/libstdc++-v3/testsuite/26_numerics/clmul/1.cc b/libstdc++-v3/testsuite/26_numerics/clmul/1.cc new file mode 100644 index 000000000000..f1490d52a572 --- /dev/null +++ b/libstdc++-v3/testsuite/26_numerics/clmul/1.cc @@ -0,0 +1,205 @@ +// { dg-do run { target c++29 } } + +#include <numeric> + +#ifndef __cpp_lib_clmul +# error "Feature-test macro for clmul missing in <numeric>" +#elif __cpp_lib_clmul != 202610L +# error "Feature-test macro for clmul has wrong value in <numeric>" +#endif + +#include <testsuite_hooks.h> + +static_assert(std::wide_result<unsigned>(42U, 43U).low() == 43); +static_assert(std::wide_result<unsigned>(42U, 43U).high() == 42); +static_assert(std::wide_result<unsigned>(42U, 43U) + == std::wide_result<unsigned>(42U, 43U)); +static_assert(std::wide_result<unsigned>(42U, 43U) + != std::wide_result<unsigned>(42U, 44U)); +static_assert(std::wide_result<unsigned>(42U, 43U) + != std::wide_result<unsigned>(43U, 43U)); +static_assert(std::wide_result<unsigned>(42U, 45U) + < std::wide_result<unsigned>(43U, 43U)); +static_assert(std::wide_result<unsigned>(42U, 43U) + < std::wide_result<unsigned>(42U, 44U)); +static_assert(std::wide_result<unsigned>(42U, 43U) + > std::wide_result<unsigned>(41U, 44U)); +static_assert(std::wide_result<unsigned>(42U, 43U) + > std::wide_result<unsigned>(42U, 42U)); +static_assert(std::is_same<decltype(std::widening_clmul((unsigned char) 0, + (unsigned char) 0)), + std::wide_result<unsigned char>>::value); +static_assert(std::is_same<decltype(std::widening_clmul((unsigned short) 0, + (unsigned short) 0)), + std::wide_result<unsigned short>>::value); +static_assert(std::is_same<decltype(std::widening_clmul(0U, 0U)), + std::wide_result<unsigned int>>::value); +static_assert(std::is_same<decltype(std::widening_clmul(0UL, 0UL)), + std::wide_result<unsigned long>>::value); +static_assert(std::is_same<decltype(std::widening_clmul(0ULL, 0ULL)), + std::wide_result<unsigned long long>>::value); +#if __CHAR_BIT__ == 8 +static_assert(std::clmul((unsigned char) 0x7e, + (unsigned char) 0x9c) == 0xe8); +static_assert(std::widening_clmul((unsigned char) 0x7e, + (unsigned char) 0x9c).low() == 0xe8); +static_assert(std::widening_clmul((unsigned char) 0x7e, + (unsigned char) 0x9c).high() == 0x3a); +#if __SIZEOF_SHORT__ == 2 +static_assert(std::clmul((unsigned short) 0xc8aa, + (unsigned short) 0x7616) == 0xa55c); +static_assert(std::widening_clmul((unsigned short) 0xc8aa, + (unsigned short) 0x7616) + == std::wide_result<unsigned short>(0x2508, 0xa55c)); +#endif +#if __SIZEOF_INT__ == 4 +static_assert(std::clmul(0x9f330680U, 0x4e157eadU) == 0xb23fb880U); +static_assert(std::widening_clmul(0x9f330680U, 0x4e157eadU) + == std::wide_result<unsigned>(0x207cd974U, 0xb23fb880U)); +static_assert(std::clmul(0x11111111U, 0x11111111U) == 0x1010101U); +static_assert(std::widening_clmul(0x11111111U, 0x11111111U) + == std::wide_result<unsigned>(0x1010101U, 0x1010101U)); +static_assert(std::clmul(~0U, ~0U) == 0x55555555U); +static_assert(std::widening_clmul(~0U, ~0U) + == std::wide_result<unsigned>(0x55555555U, 0x55555555U)); +#endif +#if __SIZEOF_LONG__ == 4 +static_assert(std::clmul(0xcd63e2c1UL, 0xab176a37UL) == 0x2f053277UL); +static_assert(std::widening_clmul(0xcd63e2c1UL, 0xab176a37UL) + == std::wide_result<unsigned long>(0x782faf0eUL, 0x2f053277UL)); +#elif __SIZEOF_LONG__ == 8 +static_assert(std::clmul(0x43e13a77bec666afUL, 0x39c165e2ed3f98f7UL) + == 0xe8465657c87e7a1dUL); +static_assert(std::widening_clmul(0x43e13a77bec666afUL, 0x39c165e2ed3f98f7UL) + == std::wide_result<unsigned long>(0xe2f8ec31f25371bUL, + 0xe8465657c87e7a1dUL)); +#endif +#if __SIZEOF_LONG_LONG__ == 8 +static_assert(std::clmul(0xe38ebed3ef3cc8deULL, 0x75224424100f8096ULL) + == 0xfaf0ddab7a75024ULL); +static_assert(std::widening_clmul(0xe38ebed3ef3cc8deULL, 0x75224424100f8096ULL) + == std::wide_result<unsigned long long>(0x29daaa7ee7cd2860ULL, + 0xfaf0ddab7a75024ULL)); +static_assert(std::clmul(0x11111111ULL, 0x11111111ULL) + == 0x101010101010101ULL); +static_assert(std::widening_clmul(0x11111111ULL, 0x11111111ULL) + == std::wide_result<unsigned long long>(0ULL, + 0x101010101010101ULL)); +static_assert(std::clmul(0x1111111111111111ULL, 0x1111111111111111ULL) + == 0x101010101010101ULL); +static_assert(std::widening_clmul(0x1111111111111111ULL, 0x1111111111111111ULL) + == std::wide_result<unsigned long long>(0x101010101010101ULL, + 0x101010101010101ULL)); +static_assert(std::clmul(~0ULL, ~0ULL) + == 0x5555555555555555ULL); +static_assert(std::widening_clmul(~0ULL, ~0ULL) + == std::wide_result<unsigned long long>(0x5555555555555555ULL, + 0x5555555555555555ULL)); +#endif +#if __SIZEOF_INT128__ == 16 +static_assert(std::clmul((((unsigned __int128) 0x983a442a106b8a83ULL) << 64) + | 0x1866ccfa2e2b382cULL, + (((unsigned __int128) 0xe9abf4d856d535c3ULL) << 64) + | 0x58708f117a52c14cULL) + == ((((unsigned __int128) 0xd3ae65b0bac566b2ULL) << 64) + | 0xdd6b33f9bb8606d0ULL)); +static_assert(std::widening_clmul((((unsigned __int128) 0x983a442a106b8a83ULL) + << 64) | 0x1866ccfa2e2b382cULL, + (((unsigned __int128) 0xe9abf4d856d535c3ULL) + << 64) | 0x58708f117a52c14cULL) + == std::wide_result<unsigned __int128>((((unsigned __int128) + 0x7d17129902648920ULL) + << 64) + | 0xfdb34e3b7c058047ULL, + (((unsigned __int128) + 0xd3ae65b0bac566b2ULL) + << 64) + | 0xdd6b33f9bb8606d0ULL)); +#endif +#endif + +template<typename T> +[[gnu::noipa]] std::wide_result<T> +myclmul(T x, T y) +{ + auto r = std::widening_clmul(x, y); + VERIFY( std::clmul(x, y) == r.low() ); + return r; +} + +template<typename T> +using W = std::wide_result<T>; + +void +test01() +{ +#if __CHAR_BIT__ == 8 + VERIFY( myclmul((unsigned char) 0x7e, (unsigned char) 0x9c) + == W<unsigned char>(0x3a, 0xe8) ); +#if __SIZEOF_SHORT__ == 2 + VERIFY( myclmul((unsigned short) 0xc8aa, (unsigned short) 0x7616) + == W<unsigned short>(0x2508, 0xa55c) ); +#endif +#if __SIZEOF_INT__ == 4 + VERIFY( myclmul(0x9f330680U, 0x4e157eadU) + == W<unsigned>(0x207cd974U, 0xb23fb880U) ); + VERIFY( myclmul(0x11111111U, 0x11111111U) + == W<unsigned>(0x1010101U, 0x1010101U) ); + VERIFY( myclmul(~0U, ~0U) + == W<unsigned>(0x55555555U, 0x55555555U) ); +#endif +#if __SIZEOF_LONG__ == 4 + VERIFY( myclmul(0xcd63e2c1UL, 0xab176a37UL) + == W<unsigned long>(0x782faf0eUL, 0x2f053277UL) ); +#elif __SIZEOF_LONG__ == 8 + VERIFY( myclmul(0x43e13a77bec666afUL, 0x39c165e2ed3f98f7UL) + == W<unsigned long>(0xe2f8ec31f25371bUL, 0xe8465657c87e7a1dUL) ); +#endif +#if __SIZEOF_LONG_LONG__ == 8 + VERIFY( myclmul(0xe38ebed3ef3cc8deULL, 0x75224424100f8096ULL) + == W<unsigned long long>(0x29daaa7ee7cd2860ULL, + 0xfaf0ddab7a75024ULL) ); + VERIFY( myclmul(0x11111111ULL, 0x11111111ULL) + == W<unsigned long long>(0ULL, 0x101010101010101ULL) ); + VERIFY( myclmul(0x1111111111111111ULL, 0x1111111111111111ULL) + == W<unsigned long long>(0x101010101010101ULL, + 0x101010101010101ULL) ); + VERIFY( myclmul(~0ULL, ~0ULL) + == W<unsigned long long>(0x5555555555555555ULL, + 0x5555555555555555ULL) ); +#endif +#if __SIZEOF_INT128__ == 16 + VERIFY( myclmul((((unsigned __int128) 0x983a442a106b8a83ULL) << 64) + | 0x1866ccfa2e2b382cULL, + (((unsigned __int128) 0xe9abf4d856d535c3ULL) << 64) + | 0x58708f117a52c14cULL) + == W<unsigned __int128>((((unsigned __int128) 0x7d17129902648920ULL) + << 64) + | 0xfdb34e3b7c058047ULL, + (((unsigned __int128) 0xd3ae65b0bac566b2ULL) + << 64) + | 0xdd6b33f9bb8606d0ULL) ); +#endif +#endif +} + +template<typename T> +void +test02() +{ + VERIFY( myclmul(T(), T()) == W<T>(T(), T()) ); +} + +int +main() +{ + test01(); + test02<unsigned char>(); + test02<unsigned short>(); + test02<unsigned int>(); + test02<unsigned long>(); + test02<unsigned long long>(); +#ifdef __SIZEOF_INT128__ + test02<unsigned __int128>(); +#endif +}
