From 2fb17d2d901d904479fa22dd01b887ff5bc48248 Mon Sep 17 00:00:00 2001 From: Jonathan Wakely Date: Thu, 30 Aug 2018 16:07:35 +0100 Subject: Avoid undefined shifts in ceil2 operations For values where the result cannot be represented the shift width would be equal to the width of the type, which is undefined. Perform two well-defined shifts instead of one possible undefined shift. * include/bits/hashtable_policy.h (__clp2): Fix calculation for LLP64 targets where sizeof(size_t) > sizeof(long). Avoid undefined shifts of the number of bits in the type. * include/std/bit (__ceil2): Avoid undefined shifts. * testsuite/26_numerics/bit/bit.pow.two/ceil2.cc: Test values with the most signifiant bit set. From-SVN: r263986 --- libstdc++-v3/ChangeLog | 7 +++++++ libstdc++-v3/include/bits/hashtable_policy.h | 7 +++++-- libstdc++-v3/include/std/bit | 6 ++++-- libstdc++-v3/testsuite/26_numerics/bit/bit.pow.two/ceil2.cc | 8 ++++++++ 4 files changed, 24 insertions(+), 4 deletions(-) (limited to 'libstdc++-v3') diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index a198549..9828852 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,5 +1,12 @@ 2018-08-30 Jonathan Wakely + * include/bits/hashtable_policy.h (__clp2): Fix calculation for LLP64 + targets where sizeof(size_t) > sizeof(long). Avoid undefined shifts + of the number of bits in the type. + * include/std/bit (__ceil2): Avoid undefined shifts. + * testsuite/26_numerics/bit/bit.pow.two/ceil2.cc: Test values with + the most signifiant bit set. + * config/abi/pre/gnu.ver: Add missing exports for mingw. * include/ext/pointer.h (_Pointer_adapter): Define operators for diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h index d749771..66fbfbe5 100644 --- a/libstdc++-v3/include/bits/hashtable_policy.h +++ b/libstdc++-v3/include/bits/hashtable_policy.h @@ -511,8 +511,11 @@ namespace __detail // Equivalent to return __n ? std::ceil2(__n) : 0; if (__n < 2) return __n; - return 1ul << (numeric_limits::digits - - __builtin_clzl(__n - 1ul)); + const unsigned __lz = sizeof(size_t) > sizeof(long) + ? __builtin_clzll(__n - 1ull) + : __builtin_clzl(__n - 1ul); + // Doing two shifts avoids undefined behaviour when __lz == 0. + return (size_t(1) << (numeric_limits::digits - __lz - 1)) << 1; } /// Rehash policy providing power of 2 bucket numbers. Avoids modulo diff --git a/libstdc++-v3/include/std/bit b/libstdc++-v3/include/std/bit index 0aebac2..bc2ade7 100644 --- a/libstdc++-v3/include/std/bit +++ b/libstdc++-v3/include/std/bit @@ -195,9 +195,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __ceil2(_Tp __x) noexcept { constexpr auto _Nd = numeric_limits<_Tp>::digits; - if (__x == 0) + if (__x == 0 || __x == 1) return 1; - return (_Tp)1u << (_Nd - std::__countl_zero((_Tp)(__x - 1u))); + const unsigned __n = _Nd - std::__countl_zero((_Tp)(__x - 1u)); + const _Tp __y_2 = (_Tp)1u << (__n - 1u); + return __y_2 << 1u; } template diff --git a/libstdc++-v3/testsuite/26_numerics/bit/bit.pow.two/ceil2.cc b/libstdc++-v3/testsuite/26_numerics/bit/bit.pow.two/ceil2.cc index 65e1569..e41f82c 100644 --- a/libstdc++-v3/testsuite/26_numerics/bit/bit.pow.two/ceil2.cc +++ b/libstdc++-v3/testsuite/26_numerics/bit/bit.pow.two/ceil2.cc @@ -55,6 +55,14 @@ test(UInt x) static_assert( std::ceil2(UInt(3) << 64) == (UInt(4) << 64) ); } + constexpr UInt msb = UInt(1) << (std::numeric_limits::digits - 1); + static_assert( std::ceil2( msb ) == msb ); + // Larger values cannot be represented so the return value is unspecified, + // but must still be valid in constant expressions, i.e. not undefined. + static_assert( std::ceil2( UInt(msb + 1) ) != 77 ); + static_assert( std::ceil2( UInt(msb + 2) ) != 77 ); + static_assert( std::ceil2( UInt(msb + 77) ) != 77 ); + return true; } -- cgit v1.1