| Message ID | 20200224201623.765972-1-ppalka@redhat.com |
|---|---|
| State | New |
| Headers | show |
| Series | libstdc++: Implement integer-class types as defined in [iterator.concept.winc] | expand |
On Mon, 24 Feb 2020, Patrick Palka wrote: > This implements signed and unsigned integer-class types, whose width is one bit > larger than the widest native signed and unsigned integral type respectively. > In our case this is either __int128 and unsigned __int128, or long long and > unsigned long long. > > Internally, the two integer-class types are represented as a largest native > unsigned integral type plus one extra bit. The signed integer-class type is > represented in two's complement form with the extra bit acting as the sign bit. > > libstdc++-v3/ChangeLog: > > * include/bits/iterator_concepts.h (ranges::__detail::__max_diff_type): > Remove definition, replace with forward declaration of class > __max_diff_type. > (ranges::__detail::__max_size_type): Remove definition, replace with > forward declaration of class __max_size_type. > (__detail::__is_integer_like): Accept __int128 and unsigned __int128. > (__detail::__is_signed_integer_like): Accept __int128. > * include/bits/range_access.h (__detail::__max_size_type): New class. > (__detail::__max_diff_type): New class. > (__detail::__max_size_type::__max_size_type): Define this constructor > out-of-line to break the cycle. > (__detail::__to_unsigned_like): New function. > (numeric_limits<__detail::__max_size_type>): New explicit specialization. > (numeric_limits<__detail::__max_diff_type>): New explicit specialization. > * testsuite/std/ranges/iota/differenc_type.cc: New test. Here's v2 of the patch that splits out __max_size_type and __max_diff_type into a dedicated header, along with other misc improvements and fixes. -- >8 -- Subject: [PATCH] libstdc++: Implement integer-class types as defined in [iterator.concept.winc] This implements signed and unsigned integer-class types, whose width is one bit larger than the widest native signed and unsigned integral type respectively. In our case this is either __int128 and unsigned __int128, or long long and unsigned long long. Internally, the two integer-class types are represented as a largest native unsigned integral type plus one extra bit. The signed integer-class type is represented in two's complement form with the extra bit acting as the sign bit. libstdc++-v3/ChangeLog: * include/Makefile.am (bits_headers): Add new header <bits/max_size_type.h>. * include/Makefile.in: Regenerate. * include/bits/iterator_concepts.h (ranges::__detail::__max_diff_type): Remove definition, replace with forward declaration of class __max_diff_type. (ranges::__detail::__max_size_type): Remove definition, replace with forward declaration of class __max_size_type. (__detail::__is_integer_like): Accept __int128 and unsigned __int128. (__detail::__is_signed_integer_like): Accept __int128. * include/bits/max_size_type.h: New header. * include/bits/range_access.h: Include <bits/max_size_type.h>. (__detail::__to_unsigned_like): Two new overloads. * testsuite/std/ranges/iota/difference_type.cc: New test. --- libstdc++-v3/include/Makefile.am | 1 + libstdc++-v3/include/Makefile.in | 1 + libstdc++-v3/include/bits/iterator_concepts.h | 15 +- libstdc++-v3/include/bits/max_size_type.h | 736 ++++++++++++++++++ libstdc++-v3/include/bits/range_access.h | 11 + .../std/ranges/iota/difference_type.cc | 379 +++++++++ 6 files changed, 1136 insertions(+), 7 deletions(-) create mode 100644 libstdc++-v3/include/bits/max_size_type.h create mode 100644 libstdc++-v3/testsuite/std/ranges/iota/difference_type.cc diff --git a/libstdc++-v3/include/Makefile.am b/libstdc++-v3/include/Makefile.am index 80aeb3f8959..a1460b98247 100644 --- a/libstdc++-v3/include/Makefile.am +++ b/libstdc++-v3/include/Makefile.am @@ -144,6 +144,7 @@ bits_headers = \ ${bits_srcdir}/locale_facets_nonio.tcc \ ${bits_srcdir}/localefwd.h \ ${bits_srcdir}/mask_array.h \ + ${bits_srcdir}/max_size_type.h \ ${bits_srcdir}/memoryfwd.h \ ${bits_srcdir}/move.h \ ${bits_srcdir}/node_handle.h \ diff --git a/libstdc++-v3/include/Makefile.in b/libstdc++-v3/include/Makefile.in index eb437ad8d8d..dd317fa0178 100644 --- a/libstdc++-v3/include/Makefile.in +++ b/libstdc++-v3/include/Makefile.in @@ -489,6 +489,7 @@ bits_headers = \ ${bits_srcdir}/locale_facets_nonio.tcc \ ${bits_srcdir}/localefwd.h \ ${bits_srcdir}/mask_array.h \ + ${bits_srcdir}/max_size_type.h \ ${bits_srcdir}/memoryfwd.h \ ${bits_srcdir}/move.h \ ${bits_srcdir}/node_handle.h \ diff --git a/libstdc++-v3/include/bits/iterator_concepts.h b/libstdc++-v3/include/bits/iterator_concepts.h index 08e622259b4..6eff0b82feb 100644 --- a/libstdc++-v3/include/bits/iterator_concepts.h +++ b/libstdc++-v3/include/bits/iterator_concepts.h @@ -482,20 +482,21 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION namespace ranges::__detail { -#if __SIZEOF_INT128__ - using __max_diff_type = __int128; - using __max_size_type = unsigned __int128; -#else - using __max_diff_type = long long; - using __max_size_type = unsigned long long; -#endif + class __max_diff_type; + class __max_size_type; template<typename _Tp> concept __is_integer_like = integral<_Tp> +#if __SIZEOF_INT128__ + || same_as<_Tp, __int128> || same_as<_Tp, unsigned __int128> +#endif || same_as<_Tp, __max_diff_type> || same_as<_Tp, __max_size_type>; template<typename _Tp> concept __is_signed_integer_like = signed_integral<_Tp> +#if __SIZEOF_INT128__ + || same_as<_Tp, __int128> +#endif || same_as<_Tp, __max_diff_type>; } // namespace ranges::__detail diff --git a/libstdc++-v3/include/bits/max_size_type.h b/libstdc++-v3/include/bits/max_size_type.h new file mode 100644 index 00000000000..8797645c70d --- /dev/null +++ b/libstdc++-v3/include/bits/max_size_type.h @@ -0,0 +1,736 @@ +// <max_size_type.h> -*- C++ -*- + +// Copyright (C) 2019-2020 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. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// <http://www.gnu.org/licenses/>. + +/** @file bits/max_size_type.h. + * This is an internal header file, included by other library headers. + * Do not attempt to use it directly. @headername{iterator} + */ + +#ifndef _GLIBCXX_MAX_SIZE_TYPE_H +#define _GLIBCXX_MAX_SIZE_TYPE_H 1 + +#pragma GCC system_header + +#if __cplusplus > 201703L && __cpp_lib_concepts +#include <bits/int_limits.h> + +namespace std _GLIBCXX_VISIBILITY(default) +{ +_GLIBCXX_BEGIN_NAMESPACE_VERSION + +template<typename _Tp> + struct numeric_limits; + +// Unsigned and signed integer-class types (as per [iterator.concept.winc]) that +// are one bit wider than the largest native integer type. + +namespace ranges +{ + namespace __detail + { + class __max_size_type + { + public: + __max_size_type() = default; + + template<integral _Tp> + constexpr + __max_size_type(_Tp __i) noexcept + : _M_val(__i), _M_msb(__i < 0) + { } + + constexpr explicit + __max_size_type(const __max_diff_type& __d) noexcept; + + template<integral _Tp> + constexpr explicit operator _Tp() const noexcept + { return _M_val; } + + constexpr explicit + operator bool() const noexcept + { return _M_val != 0 || _M_msb != 0; } + + constexpr __max_size_type + operator+() const noexcept + { return *this; } + + constexpr __max_size_type + operator~() const noexcept + { return __max_size_type{~_M_val, !_M_msb}; } + + constexpr __max_size_type + operator-() const noexcept + { return operator~() + 1; } + + constexpr __max_size_type& + operator+=(const __max_size_type& __r) noexcept + { + const auto __sum = _M_val + __r._M_val; + const bool __overflow = (__sum < _M_val); + _M_msb = _M_msb ^ __r._M_msb ^ __overflow; + _M_val = __sum; + return *this; + } + + constexpr __max_size_type& + operator-=(const __max_size_type& __r) noexcept + { return *this += -__r; } + + constexpr __max_size_type& + operator*=(__max_size_type __r) noexcept + { + const bool __lsb = _M_val & 1; + const bool __rlsb = __r._M_val & 1; + + constexpr auto __threshold = __rep(1) << (__rep_bits / 2 - 1); + if (!_M_msb && !__r._M_msb + && _M_val < __threshold && __r._M_val < __threshold) [[likely]] + _M_val = _M_val * __r._M_val; + else + { + *this >>= 1; + __r >>= 1; + _M_val = (2 * _M_val * __r._M_val + + _M_val * __rlsb + __r._M_val * __lsb); + *this <<= 1; + *this += __rlsb * __lsb; + } + + return *this; + } + + constexpr __max_size_type& + operator/=(const __max_size_type& __r) noexcept + { + __glibcxx_assert(__r != 0); + + if (!_M_msb && !__r._M_msb) [[likely]] + _M_val /= __r._M_val; + else if (_M_msb && __r._M_msb) + { + _M_val = (_M_val >= __r._M_val); + _M_msb = 0; + } + else if (!_M_msb && __r._M_msb) + _M_val = 0; + else if (_M_msb && !__r._M_msb) + { + const auto __orig = *this; + *this >>= 1; + _M_val /= __r._M_val; + *this <<= 1; + if (__orig - *this * __r >= __r) + ++_M_val; + } + return *this; + } + + constexpr __max_size_type& + operator%=(const __max_size_type& __r) noexcept + { + if (!_M_msb && !__r._M_msb) [[likely]] + _M_val %= __r._M_val; + else + *this -= (*this / __r) * __r; + return *this; + } + + constexpr __max_size_type& + operator<<=(const __max_size_type& __r) noexcept + { + __glibcxx_assert(__r <= __rep_bits); + if (__r == 0) + return *this; + if (_M_val & (__rep(1) << (__rep_bits - __r._M_val))) + _M_msb = 1; + else + _M_msb = 0; + if (__r._M_val == __rep_bits) [[unlikely]] + _M_val = 0; + else + _M_val <<= __r._M_val; + return *this; + } + + constexpr __max_size_type& + operator>>=(const __max_size_type& __r) noexcept + { + __glibcxx_assert(__r <= __rep_bits); + if (__r == 0) + return *this; + if (__r._M_val == __rep_bits) [[unlikely]] + _M_val = 0; + else + _M_val >>= __r._M_val; + if (_M_msb) [[unlikely]] + { + _M_val |= __rep(1) << (__rep_bits - __r._M_val); + _M_msb = 0; + } + return *this; + } + + constexpr __max_size_type& + operator&=(const __max_size_type& __r) noexcept + { + _M_val &= __r._M_val; + _M_msb &= __r._M_msb; + return *this; + } + + constexpr __max_size_type& + operator|=(const __max_size_type& __r) noexcept + { + _M_val |= __r._M_val; + _M_msb |= __r._M_msb; + return *this; + } + + constexpr __max_size_type& + operator^=(const __max_size_type& __r) noexcept + { + _M_val ^= __r._M_val; + _M_msb ^= __r._M_msb; + return *this; + } + + template<integral _Tp> + friend constexpr _Tp& + operator+=(_Tp& a, const __max_size_type& b) noexcept + { return (a = static_cast<_Tp>(a + b)); } + + template<integral _Tp> + friend constexpr _Tp& + operator-=(_Tp& a, const __max_size_type& b) noexcept + { return (a = static_cast<_Tp>(a - b)); } + + template<integral _Tp> + friend constexpr _Tp& + operator*=(_Tp& a, const __max_size_type& b) noexcept + { return (a = static_cast<_Tp>(a * b)); } + + template<integral _Tp> + friend constexpr _Tp& + operator/=(_Tp& a, const __max_size_type& b) noexcept + { return (a = static_cast<_Tp>(a / b)); } + + template<integral _Tp> + friend constexpr _Tp& + operator%=(_Tp& a, const __max_size_type& b) noexcept + { return (a = static_cast<_Tp>(a % b)); } + + template<integral _Tp> + friend constexpr _Tp& + operator&=(_Tp& a, const __max_size_type& b) noexcept + { return (a = static_cast<_Tp>(a & b)); } + + template<integral _Tp> + friend constexpr _Tp& + operator|=(_Tp& a, const __max_size_type& b) noexcept + { return (a = static_cast<_Tp>(a | b)); } + + template<integral _Tp> + friend constexpr _Tp& + operator^=(_Tp& a, const __max_size_type& b) noexcept + { return (a = static_cast<_Tp>(a ^ b)); } + + template<integral _Tp> + friend constexpr _Tp& + operator<<=(_Tp& a, const __max_size_type& b) noexcept + { return (a = static_cast<_Tp>(a << b)); } + + template<integral _Tp> + friend constexpr _Tp& + operator>>=(_Tp& a, const __max_size_type& b) noexcept + { return (a = static_cast<_Tp>(a >> b)); } + + friend constexpr __max_size_type + operator+(__max_size_type __l, const __max_size_type& __r) noexcept + { + __l += __r; + return __l; + } + + friend constexpr __max_size_type + operator-(__max_size_type __l, const __max_size_type& __r) noexcept + { + __l -= __r; + return __l; + } + + friend constexpr __max_size_type + operator*(__max_size_type __l, const __max_size_type& __r) noexcept + { + __l *= __r; + return __l; + } + + friend constexpr __max_size_type + operator/(__max_size_type __l, const __max_size_type& __r) noexcept + { + __l /= __r; + return __l; + } + + friend constexpr __max_size_type + operator%(__max_size_type __l, const __max_size_type& __r) noexcept + { + __l %= __r; + return __l; + } + + friend constexpr __max_size_type + operator<<(__max_size_type __l, const __max_size_type& __r) noexcept + { + __l <<= __r; + return __l; + } + + friend constexpr __max_size_type + operator>>(__max_size_type __l, const __max_size_type& __r) noexcept + { + __l >>= __r; + return __l; + } + + friend constexpr __max_size_type + operator&(__max_size_type __l, const __max_size_type& __r) noexcept + { + __l &= __r; + return __l; + } + + friend constexpr __max_size_type + operator|(__max_size_type __l, const __max_size_type& __r) noexcept + { + __l |= __r; + return __l; + } + + friend constexpr __max_size_type + operator^(__max_size_type __l, const __max_size_type& __r) noexcept + { + __l ^= __r; + return __l; + } + + friend constexpr bool + operator==(const __max_size_type& __l, const __max_size_type& __r) noexcept + { return __l._M_val == __r._M_val && __l._M_msb == __r._M_msb; } + + friend constexpr bool + operator!=(const __max_size_type& __l, const __max_size_type& __r) noexcept + { return !(__l == __r); } + + friend constexpr bool + operator<(const __max_size_type& __l, const __max_size_type& __r) noexcept + { + if (__l._M_msb == __r._M_msb) + return __l._M_val < __r._M_val; + else + return __r._M_msb; + } + + friend constexpr bool + operator>(const __max_size_type& __l, const __max_size_type& __r) noexcept + { return __r < __l; } + + friend constexpr bool + operator<=(const __max_size_type& __l, const __max_size_type& __r) noexcept + { return !(__l > __r); } + + friend constexpr bool + operator>=(const __max_size_type& __l, const __max_size_type& __r) noexcept + { return __r <= __l; } + +#if __SIZEOF_INT128__ + using __rep = unsigned __int128; +#else + using __rep = unsigned long long; +#endif + static constexpr size_t __rep_bits = sizeof(__rep) * __CHAR_BIT__; + private: + __rep _M_val = 0; + unsigned _M_msb:1 = 0; + + constexpr explicit + __max_size_type(__rep __val, int __msb) noexcept + : _M_val(__val), _M_msb(__msb) + { } + + friend __max_diff_type; + friend std::numeric_limits<__max_size_type>; + friend std::numeric_limits<__max_diff_type>; + }; + + // A signed integer-class type as per [iterator.concept.winc]. + class __max_diff_type + { + public: + __max_diff_type() = default; + + template<integral _Tp> + constexpr + __max_diff_type(_Tp __i) noexcept + : _M_rep(__i) + { } + + constexpr explicit + __max_diff_type(const __max_size_type& __d) noexcept + : _M_rep(__d) + { } + + template<integral _Tp> + constexpr explicit operator _Tp() const noexcept + { return static_cast<_Tp>(_M_rep); } + + constexpr explicit + operator bool() const noexcept + { return _M_rep != 0; } + + constexpr __max_diff_type + operator+() const noexcept + { return *this; } + + constexpr __max_diff_type + operator-() const noexcept + { return __max_diff_type(-_M_rep); } + + constexpr __max_diff_type + operator~() const noexcept + { return __max_diff_type(~_M_rep); } + + constexpr __max_diff_type& + operator+=(const __max_diff_type& __r) noexcept + { + _M_rep += __r._M_rep; + return *this; + } + + constexpr __max_diff_type& + operator-=(const __max_diff_type& __r) noexcept + { + _M_rep -= __r._M_rep; + return *this; + } + + constexpr __max_diff_type& + operator*=(const __max_diff_type& __r) noexcept + { + _M_rep *= __r._M_rep; + return *this; + } + + constexpr __max_diff_type& + operator/=(const __max_diff_type& __r) noexcept + { + __glibcxx_assert (__r != 0); + const bool __neg = *this < 0; + const bool __rneg = __r < 0; + if (!__neg && !__rneg) + _M_rep = _M_rep / __r._M_rep; + else if (__neg && __rneg) + _M_rep = -_M_rep / -__r._M_rep; + else + _M_rep = -((__neg ? -_M_rep : _M_rep) + / (__rneg ? -__r._M_rep : __r._M_rep)); + return *this ; + } + + constexpr __max_diff_type& + operator%=(const __max_diff_type& __r) noexcept + { + __glibcxx_assert (__r != 0); + if (*this >= 0 && __r > 0) + _M_rep %= __r._M_rep; + else + *this -= (*this / __r) * __r; + return *this; + } + + constexpr __max_diff_type& + operator<<=(const __max_diff_type& __r) noexcept + { + _M_rep.operator<<=(__r._M_rep); + return *this; + } + + constexpr __max_diff_type& + operator>>=(const __max_diff_type& __r) noexcept + { + const auto __msb = _M_rep._M_msb; + _M_rep >>= __r._M_rep; + _M_rep._M_msb |= __msb; + return *this; + } + + constexpr __max_diff_type& + operator&=(const __max_diff_type& __r) noexcept + { + _M_rep &= __r._M_rep; + return *this; + } + + constexpr __max_diff_type& + operator|=(const __max_diff_type& __r) noexcept + { + _M_rep |= __r._M_rep; + return *this; + } + + constexpr __max_diff_type& + operator^=(const __max_diff_type& __r) noexcept + { + _M_rep ^= __r._M_rep; + return *this; + } + + template<integral _Tp> + friend constexpr _Tp& + operator+=(_Tp& a, const __max_diff_type& b) noexcept + { return (a = static_cast<_Tp>(a + b)); } + + template<integral _Tp> + friend constexpr _Tp& + operator-=(_Tp& a, const __max_diff_type& b) noexcept + { return (a = static_cast<_Tp>(a - b)); } + + template<integral _Tp> + friend constexpr _Tp& + operator*=(_Tp& a, const __max_diff_type& b) noexcept + { return (a = static_cast<_Tp>(a * b)); } + + template<integral _Tp> + friend constexpr _Tp& + operator/=(_Tp& a, const __max_diff_type& b) noexcept + { return (a = static_cast<_Tp>(a / b)); } + + template<integral _Tp> + friend constexpr _Tp& + operator%=(_Tp& a, const __max_diff_type& b) noexcept + { return (a = static_cast<_Tp>(a % b)); } + + template<integral _Tp> + friend constexpr _Tp& + operator&=(_Tp& a, const __max_diff_type& b) noexcept + { return (a = static_cast<_Tp>(a & b)); } + + template<integral _Tp> + friend constexpr _Tp& + operator|=(_Tp& a, const __max_diff_type& b) noexcept + { return (a = static_cast<_Tp>(a | b)); } + + template<integral _Tp> + friend constexpr _Tp& + operator^=(_Tp& a, const __max_diff_type& b) noexcept + { return (a = static_cast<_Tp>(a ^ b)); } + + template<integral _Tp> + friend constexpr _Tp& + operator<<=(_Tp& a, const __max_diff_type& b) noexcept + { return (a = static_cast<_Tp>(a << b)); } + + template<integral _Tp> + friend constexpr _Tp& + operator>>=(_Tp& a, const __max_diff_type& b) noexcept + { return (a = static_cast<_Tp>(a >> b)); } + + friend constexpr __max_diff_type + operator+(__max_diff_type __l, const __max_diff_type& __r) noexcept + { + __l += __r; + return __l; + } + + friend constexpr __max_diff_type + operator-(__max_diff_type __l, const __max_diff_type& __r) noexcept + { + __l -= __r; + return __l; + } + + friend constexpr __max_diff_type + operator*(__max_diff_type __l, const __max_diff_type& __r) noexcept + { + __l *= __r; + return __l; + } + + friend constexpr __max_diff_type + operator/(__max_diff_type __l, const __max_diff_type& __r) noexcept + { + __l /= __r; + return __l; + } + + friend constexpr __max_diff_type + operator%(__max_diff_type __l, const __max_diff_type& __r) noexcept + { + __l %= __r; + return __l; + } + + friend constexpr __max_diff_type + operator<<(__max_diff_type __l, const __max_diff_type& __r) noexcept + { + __l <<= __r; + return __l; + } + + friend constexpr __max_diff_type + operator>>(__max_diff_type __l, const __max_diff_type& __r) noexcept + { + __l >>= __r; + return __l; + } + + friend constexpr __max_diff_type + operator&(__max_diff_type __l, const __max_diff_type& __r) noexcept + { + __l &= __r; + return __l; + } + + friend constexpr __max_diff_type + operator|(__max_diff_type __l, const __max_diff_type& __r) noexcept + { + __l |= __r; + return __l; + } + + friend constexpr __max_diff_type + operator^(__max_diff_type __l, const __max_diff_type& __r) noexcept + { + __l ^= __r; + return __l; + } + + friend constexpr bool + operator==(const __max_diff_type& __l, const __max_diff_type& __r) noexcept + { return __l._M_rep == __r._M_rep; } + + friend constexpr bool + operator!=(const __max_diff_type& __l, const __max_diff_type& __r) noexcept + { return !(__l == __r); } + + constexpr bool + operator<(const __max_diff_type& __r) const noexcept + { + const auto __lsign = _M_rep._M_msb; + const auto __rsign = __r._M_rep._M_msb; + if (__lsign ^ __rsign) + return __lsign; + else + return _M_rep < __r._M_rep; + } + + friend constexpr bool + operator>(const __max_diff_type& __l, const __max_diff_type& __r) noexcept + { return __r < __l; } + + friend constexpr bool + operator<=(const __max_diff_type& __l, const __max_diff_type& __r) noexcept + { return !(__r < __l); } + + friend constexpr bool + operator>=(const __max_diff_type& __l, const __max_diff_type& __r) noexcept + { return !(__l < __r); } + + private: + __max_size_type _M_rep = 0; + + friend class __max_size_type; + }; + + constexpr + __max_size_type::__max_size_type(const __max_diff_type& __d) noexcept + : __max_size_type(__d._M_rep) + { } + + } // namespace __detail +} // namespace ranges + + template<> + struct numeric_limits<ranges::__detail::__max_size_type> + { + using _Sp = ranges::__detail::__max_size_type; + static constexpr bool is_specialized = true; + static constexpr bool is_signed = false; + static constexpr bool is_integer = true; + static constexpr bool is_exact = true; +#if __SIZEOF_INT128__ + static_assert(same_as<_Sp::__rep, unsigned __int128>); + static constexpr int digits = 129; +#else + static_assert(same_as<_Sp::__rep, unsigned long long>); + static constexpr int digits + = __detail::__int_limits<unsigned long long>::digits + 1; +#endif + static constexpr int digits10 + = static_cast<int>(digits * 0.30102); + // = static_cast<int>(digits * log10(2)) + + static constexpr _Sp + min() noexcept + { return 0; } + + static constexpr _Sp + max() noexcept + { return _Sp(static_cast<_Sp::__rep>(-1), 1); } + + static constexpr _Sp + lowest() noexcept + { return min(); } + }; + + template<> + struct numeric_limits<ranges::__detail::__max_diff_type> + { + using _Dp = ranges::__detail::__max_diff_type; + using _Sp = ranges::__detail::__max_size_type; + static constexpr bool is_specialized = true; + static constexpr bool is_signed = true; + static constexpr bool is_integer = true; + static constexpr bool is_exact = true; + static constexpr int digits = numeric_limits<_Sp>::digits - 1; + static constexpr int digits10 = static_cast<int>(digits * 0.301); + + static constexpr _Dp + min() noexcept + { return _Dp(_Sp(0, 1)); } + + static constexpr _Dp + max() noexcept + { return _Dp(_Sp(static_cast<_Sp::__rep>(-1), 0)); } + + static constexpr _Dp + lowest() noexcept + { return min(); } + }; + +_GLIBCXX_END_NAMESPACE_VERSION +} // namespace + +#endif // C++20 && library concepts +#endif // _GLIBCXX_MAX_SIZE_TYPE_H diff --git a/libstdc++-v3/include/bits/range_access.h b/libstdc++-v3/include/bits/range_access.h index 8b276fd6625..c814694623c 100644 --- a/libstdc++-v3/include/bits/range_access.h +++ b/libstdc++-v3/include/bits/range_access.h @@ -36,6 +36,9 @@ #include <initializer_list> #include <bits/iterator_concepts.h> #include <bits/int_limits.h> +#if __cplusplus > 201703L +#include <bits/max_size_type.h> +#endif namespace std _GLIBCXX_VISIBILITY(default) { @@ -351,6 +354,14 @@ namespace ranges namespace __detail { + constexpr __max_size_type + __to_unsigned_like(__max_size_type __t) noexcept + { return __t; } + + constexpr __max_size_type + __to_unsigned_like(__max_diff_type __t) noexcept + { return __max_size_type(__t); } + template<integral _Tp> constexpr make_unsigned_t<_Tp> __to_unsigned_like(_Tp __t) noexcept diff --git a/libstdc++-v3/testsuite/std/ranges/iota/difference_type.cc b/libstdc++-v3/testsuite/std/ranges/iota/difference_type.cc new file mode 100644 index 00000000000..c37c88467bb --- /dev/null +++ b/libstdc++-v3/testsuite/std/ranges/iota/difference_type.cc @@ -0,0 +1,379 @@ +// Copyright (C) 2020 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 +// <http://www.gnu.org/licenses/>. + +// { dg-options "-std=gnu++2a" } +// { dg-do run { target c++2a } } + +#include <limits> +#include <ranges> +#include <testsuite_hooks.h> + +void +test01() +{ + using I = unsigned long long; + auto imax = std::numeric_limits<I>::max(); + std::ranges::iota_view<I, I> i(0, imax); + auto begin = i.begin(); + static_assert( std::input_or_output_iterator<decltype(begin)> ); + auto size = std::ranges::end(i) - std::ranges::begin(i); + VERIFY( size > 0 ); + VERIFY( size == imax ); +} + +void +test02() +{ +#if __SIZEOF_INT128__ + using I = unsigned __int128; + auto imax = std::numeric_limits<I>::max(); + std::ranges::iota_view<I, I> i(0, imax); + auto begin = i.begin(); + static_assert( std::input_or_output_iterator<decltype(begin)> ); + auto size = std::ranges::end(i) - std::ranges::begin(i); + VERIFY( size > 0 ); + VERIFY( size == imax ); +#endif +} + +// The following are correctness tests for the arithmetic operations on +// __max_size_type and __max_diff_type. + +using max_size_t = std::ranges::__detail::__max_size_type; +using max_diff_t = std::ranges::__detail::__max_diff_type; +using rep_t = max_size_t::__rep; + +static_assert(sizeof(max_size_t) == sizeof(max_diff_t)); + +static_assert(std::regular<max_size_t>); +static_assert(std::totally_ordered<max_size_t>); + +static_assert(std::regular<max_diff_t>); +static_assert(std::totally_ordered<max_diff_t>); + +void +test03() +{ + static_assert(max_size_t(7) % 3 == 1); + static_assert(max_size_t(7) % 4 == 3); + + static_assert(-max_diff_t(1) == max_diff_t(-1)); + static_assert(max_diff_t(3) % 2 == 1); + static_assert(max_diff_t(-3) / 2 == -1); + static_assert(max_diff_t(-3) % 2 == -1); + static_assert(max_diff_t(3) % -2 == 1); + static_assert(max_diff_t(-3) << 1 == -6); + static_assert(max_diff_t(-3) >> 1 == -2); + static_assert(max_diff_t(3) >> 1 == 1); + static_assert(max_diff_t(3) >> 2 == 0); + + static_assert(max_diff_t(-5) / 3 == -1); + static_assert(max_diff_t(5) / -3 == -1); + static_assert(max_diff_t(-5) / -3 == 1); + static_assert(max_diff_t(5) / 3 == 1); + + static_assert(max_diff_t(-6) / 3 == -2); + static_assert(max_diff_t(6) / -3 == -2); + static_assert(max_diff_t(-6) / -3 == 2); + static_assert(max_diff_t(6) / 3 == 2); + + static_assert(~max_size_t(-3) == 2); + static_assert(~max_diff_t(-3) == 2); + + static_assert(max_diff_t(1) < max_diff_t(3)); + static_assert(max_diff_t(-1) < max_diff_t(3)); + static_assert(max_diff_t(1) > max_diff_t(-3)); + static_assert(max_diff_t(-1) > max_diff_t(-3)); + + constexpr max_size_t mu = std::numeric_limits<rep_t>::max(); + + static_assert(max_diff_t(mu)/-1 == -max_diff_t(mu)); + static_assert(-max_diff_t(mu)/1 == -max_diff_t(mu)); + static_assert(max_diff_t(mu)>>1 == max_diff_t(mu)/2); + static_assert(-max_diff_t(mu+1) == max_diff_t(mu+1)); + static_assert(-(mu+1) == mu+1); + static_assert((mu+1)<<1 == 0); + static_assert(max_diff_t(mu+1)<<1 == 0); + static_assert(max_diff_t(mu+1)>>1 < 0); + + static_assert(int(max_diff_t(mu+1)) == 0); + static_assert(rep_t(max_diff_t(mu+1)) == 0); + static_assert(int(max_diff_t(mu)) == -1); + static_assert(rep_t(max_diff_t(mu)) == rep_t(-1)); + + static_assert(2*mu+1 > 2*mu); + static_assert(~(2*mu+1) == 0); + static_assert(mu/mu == 1); + static_assert(2*mu > mu); + static_assert(2*mu-mu == mu); + static_assert((2*mu)/mu == 2); + static_assert((2*mu+1)/mu == 2); + static_assert((2*mu-1)/(mu-1) == 2); + static_assert((2*mu-1)/mu == 1); + static_assert((2*mu+-1)/mu == 1); + static_assert(2*mu-1 < 2*mu); + static_assert(2*mu-1 <= 2*mu); + static_assert(2*mu+1 > 2*mu); + static_assert(2*mu+1 >= 2*mu); + static_assert((2*mu)/1 == 2*mu); + static_assert(mu/mu-1 == 0); + static_assert(mu*0 == 0); + static_assert((2*mu-1)*0 == 0); + static_assert((2*mu-1)>>1 == mu-1); + static_assert(mu+-1+1 == mu); + static_assert(mu+1+-1 == mu); + static_assert(mu+1); + static_assert((2*mu)/2 == mu); + static_assert((2*mu)>>1 == mu); + static_assert((mu<<1)>>1 == mu); + static_assert(1/mu == 0); + static_assert(mu/1 == mu); + static_assert(((mu+1)|mu) == -1); + static_assert((mu+1)+(mu+1) < mu+1); + + constexpr max_size_t ou = 1; + constexpr max_diff_t ns = -1; + + static_assert(max_size_t(ns) == -1); + static_assert(-max_diff_t(ou) == -1); + static_assert(-max_diff_t(-ou) == 1); + static_assert(max_size_t(-max_diff_t(-ou)) == 1); + static_assert(ns*ns == max_diff_t(ou)); + static_assert(max_size_t(ns)*max_size_t(ns) == ou); + static_assert(-max_diff_t(0) == max_diff_t(0)); + static_assert(-ou-ou == -2*ou); + + static_assert(int(ns) == -1); + static_assert(rep_t(ns) == rep_t(-1)); + + static_assert(max_size_t() == 0); + static_assert(max_diff_t() == 0); + + auto f = [] (auto a) { a /= a; return a; }; + static_assert(f(max_size_t(5)) == 1); + static_assert(f(max_size_t(-5)) == 1); + static_assert(f(max_diff_t(5)) == 1); + + auto g = [] (auto a) { a >>= a; return a; }; + static_assert(g(max_size_t(5)) == 0); + static_assert(g(max_diff_t(5)) == 0); + + auto h = [] (auto a) { a <<= a; return a; }; + static_assert(h(max_size_t(3)) == 24); + static_assert(h(max_diff_t(3)) == 24); +} + +template<bool signed_p, bool shorten_p> +void +test04() +{ + using hw_type = std::conditional_t<signed_p, signed rep_t, rep_t>; + using max_type = std::conditional_t<signed_p, max_diff_t, max_size_t>; + using shorten_type = std::conditional_t<shorten_p, hw_type, max_type>; + const int hw_type_bit_size = sizeof(hw_type) * __CHAR_BIT__; + const int limit = 1000; + const int log2_limit = 10; + static_assert((1 << log2_limit) >= limit); + const int min = (signed_p ? -limit : 0); + const int max = limit; + for (hw_type i = min; i <= max; i++) + { + bool ok = true; + if (signed_p || shorten_p) + { + ok &= (~i == shorten_type(~max_type(i))); + ok &= (-i == shorten_type(-max_type(i))); + } + for (hw_type j = min; j <= max; j++) + { + ok &= (i*j == shorten_type(max_type(i)*j)); + ok &= (i+j == shorten_type(max_type(i)+j)); + if (j != 0) + { + ok &= (i/j == shorten_type(max_type(i)/j)); + ok &= (i%j == shorten_type(max_type(i)%j)); + } + if (signed_p || shorten_p) + ok &= (i-j == shorten_type(max_type(i)-j)); + ok &= ((i&j) == shorten_type(max_type(i)&j)); + ok &= ((i|j) == shorten_type(max_type(i)|j)); + ok &= ((i^j) == shorten_type(max_type(i)^j)); + if (j >= 0 && j < hw_type(hw_type_bit_size) + && (shorten_p || j < hw_type(hw_type_bit_size) - log2_limit)) + { + ok &= ((i>>j) == shorten_type(max_type(i)>>j)); + ok &= ((i<<j) == shorten_type(max_type(i)<<j)); + } + ok &= (i>j) == (max_type(i) > j); + ok &= (i<j) == (max_type(i) < j); + ok &= (i>=j) == (max_type(i) >= j); + ok &= (i<=j) == (max_type(i) <= j); + ok &= (i==j) == (max_type(i) == j); + ok &= (i!=j) == (max_type(i) != j); + if (!ok) + { + fprintf(stderr, + "Inconsistency found: %d %d %lld %lld\n", + signed_p, shorten_p, (long long)i, (long long)j) ; + VERIFY(0); + } + } + } +} + +template<bool signed_p, bool toggle_base_p> +void +test05() +{ + using hw_type = std::conditional_t<signed_p, signed rep_t, rep_t>; + using max_type = std::conditional_t<signed_p, max_diff_t, max_size_t>; + using base_type = std::conditional_t<toggle_base_p, hw_type, max_type>; + constexpr int hw_type_bit_size = sizeof(hw_type) * __CHAR_BIT__; + constexpr int limit = 1000; + constexpr int log2_limit = 10; + static_assert((1 << log2_limit) >= limit); + const int min = (signed_p ? -limit : 0); + const int max = limit; + for (hw_type i = min; i <= max; i++) + { + bool ok = true; + base_type k; + for (hw_type j = min; j <= max; j++) + { + k = i; k *= j; + ok &= (k == (max_type(i)*j)); + k = i; k += j; + ok &= (k == (max_type(i)+j)); + if (j != 0) + { + k = i; k /= j; + ok &= (k == (max_type(i)/j)); + k = i; k %= j; + ok &= (k == (max_type(i)%j)); + } + if (signed_p) + { + k = i; k -= j; + ok &= (k == (max_type(i)-j)); + } + k = i; k &= j; + ok &= (k == (max_type(i)&j)); + k = i; k |= j; + ok &= (k == (max_type(i)|j)); + k = i; k ^= j; + ok &= (k == (max_type(i)^j)); + if (j >= 0 && j < hw_type(hw_type_bit_size) + && (!toggle_base_p || j < hw_type(hw_type_bit_size) - log2_limit)) + { + k = i; k >>= j; + ok &= (k == (max_type(i)>>j)); + k = i; k <<= j; + ok &= (k == (max_type(i)<<j)); + } + if (!ok) + { + fprintf(stderr, + "Inconsistency found: %d %d %lld %lld\n", + signed_p, toggle_base_p, (long long)i, (long long)j) ; + VERIFY(0); + } + } + } +} + +void +test06() +{ + constexpr max_size_t mu = std::numeric_limits<rep_t>::max(); + const int limit = 1000; + for (int i = -limit; i <= limit; i++) + { + VERIFY( -max_size_t(-i) == i ); + for (int j = i; j <= limit; j++) + { + VERIFY( max_size_t(-i) * max_size_t(-j) == i*j ); + VERIFY( max_size_t(-j) * max_size_t(-i) == j*i ); + VERIFY( rep_t(((mu+1)+i)*((mu+1)+j)) == rep_t(i*j) ); + VERIFY( rep_t(((mu+1)+j)*((mu+1)+i)) == rep_t(j*i) ); + if (i >= 0 && j > 0) + { + auto r = (mu+i)-((mu+i)/j)*j; + VERIFY( r >= 0 && r < j ); + VERIFY( r == (mu+i)%j ); + } + } + } +} + +using std::numeric_limits; + +static_assert(numeric_limits<max_size_t>::is_specialized); +static_assert(!numeric_limits<max_size_t>::is_signed); +static_assert(numeric_limits<max_size_t>::is_integer); +static_assert(numeric_limits<max_size_t>::is_exact); +static_assert(numeric_limits<max_size_t>::digits + == numeric_limits<rep_t>::digits + 1); +// XXX: not quite.. +static_assert(numeric_limits<max_size_t>::digits10 + == numeric_limits<rep_t>::digits10); +static_assert(numeric_limits<max_size_t>::min() == 0); +static_assert(numeric_limits<max_size_t>::max() + == max_size_t(-1)); +static_assert(numeric_limits<max_size_t>::max() + == 2*max_size_t(numeric_limits<rep_t>::max())+1); +static_assert((numeric_limits<max_size_t>::max() + >> (numeric_limits<max_size_t>::digits-1)) == 1); +static_assert(numeric_limits<max_size_t>::lowest() + == numeric_limits<max_size_t>::min()); + +static_assert(numeric_limits<max_diff_t>::is_specialized); +static_assert(numeric_limits<max_diff_t>::is_signed); +static_assert(numeric_limits<max_diff_t>::is_integer); +static_assert(numeric_limits<max_diff_t>::is_exact); +static_assert(numeric_limits<max_diff_t>::digits + == numeric_limits<rep_t>::digits); +static_assert(numeric_limits<max_diff_t>::digits10 + == numeric_limits<rep_t>::digits10); +static_assert(numeric_limits<max_diff_t>::min() + == -max_diff_t(numeric_limits<rep_t>::max())-1); +static_assert(numeric_limits<max_diff_t>::max() + == numeric_limits<rep_t>::max()); +static_assert(numeric_limits<max_diff_t>::lowest() + == numeric_limits<max_diff_t>::min()); +static_assert(max_diff_t(max_size_t(1) + << (numeric_limits<max_size_t>::digits-1)) + == numeric_limits<max_diff_t>::min()); + +int +main() +{ + test01(); + test02(); + test03(); + + test04<false,false>(); + test04<false,true>(); + test04<true,false>(); + test04<true,true>(); + + test05<false,false>(); + test05<false,true>(); + test05<true,false>(); + test05<true,true>(); + + test06(); +}
On Mon, 24 Feb 2020, Patrick Palka wrote: > On Mon, 24 Feb 2020, Patrick Palka wrote: > > > This implements signed and unsigned integer-class types, whose width is one bit > > larger than the widest native signed and unsigned integral type respectively. > > In our case this is either __int128 and unsigned __int128, or long long and > > unsigned long long. > > > > Internally, the two integer-class types are represented as a largest native > > unsigned integral type plus one extra bit. The signed integer-class type is > > represented in two's complement form with the extra bit acting as the sign bit. > > > > libstdc++-v3/ChangeLog: > > > > * include/bits/iterator_concepts.h (ranges::__detail::__max_diff_type): > > Remove definition, replace with forward declaration of class > > __max_diff_type. > > (ranges::__detail::__max_size_type): Remove definition, replace with > > forward declaration of class __max_size_type. > > (__detail::__is_integer_like): Accept __int128 and unsigned __int128. > > (__detail::__is_signed_integer_like): Accept __int128. > > * include/bits/range_access.h (__detail::__max_size_type): New class. > > (__detail::__max_diff_type): New class. > > (__detail::__max_size_type::__max_size_type): Define this constructor > > out-of-line to break the cycle. > > (__detail::__to_unsigned_like): New function. > > (numeric_limits<__detail::__max_size_type>): New explicit specialization. > > (numeric_limits<__detail::__max_diff_type>): New explicit specialization. > > * testsuite/std/ranges/iota/differenc_type.cc: New test. > > Here's v2 of the patch that splits out __max_size_type and > __max_diff_type into a dedicated header, along with other misc > improvements and fixes. > > -- >8 -- Here's v3 of the patch. Changes from v2: * The arithmetic tests in difference_type.cc have been split out to a separate file. * The arithmetic tests now run successfully in strict ANSI mode. The issue was that __int128 does not model the integral concept in strict ANSI mode, which we use to make operations on this type behave as integer operations do. But for that we need to always treat __int128 as an integer type in this API. So a new concept __integralish which is always modelled by __int128 is introduced and used in the API instead. * Comments have been added explaining why __int128 is always used as the underlying type even when the widest integer type in strict ANSI mode is long long. * New tests, some minor code clean-ups, and added comments to the unsigned division and multiplication routines. Tested on x86_64-pc-linux-gnu in both strict and GNU compilation modes, with and without -U__SIZEOF_INT128__. -- >8 -- This implements signed and unsigned integer-class types, whose width is one bit larger than the widest supported signed and unsigned integral type respectively. In our case this is either __int128 and unsigned __int128, or long long and unsigned long long. Internally, the two integer-class types are represented as a largest native unsigned integral type plus one extra bit. The signed integer-class type is represented in two's complement form with the extra bit acting as the sign bit. libstdc++-v3/ChangeLog: * include/Makefile.am (bits_headers): Add new header <bits/max_size_type.h>. * include/Makefile.in: Regenerate. * include/bits/iterator_concepts.h (ranges::__detail::__max_diff_type): Remove definition, replace with forward declaration of class __max_diff_type. (ranges::__detail::__max_size_type): Remove definition, replace with forward declaration of class __max_size_type. (__detail::__is_integer_like): Accept __int128 and unsigned __int128. (__detail::__is_signed_integer_like): Accept __int128. * include/bits/max_size_type.h: New header. * include/bits/range_access.h: Include <bits/max_size_type.h>. (__detail::__to_unsigned_like): Two new overloads. * testsuite/std/ranges/iota/difference_type.cc: New test. * testsuite/std/ranges/iota/max_size_type.cc: New test. --- libstdc++-v3/include/Makefile.am | 1 + libstdc++-v3/include/Makefile.in | 1 + libstdc++-v3/include/bits/iterator_concepts.h | 15 +- libstdc++-v3/include/bits/max_size_type.h | 764 ++++++++++++++++++ libstdc++-v3/include/bits/range_access.h | 11 + .../std/ranges/iota/difference_type.cc | 57 ++ .../std/ranges/iota/max_size_type.cc | 376 +++++++++ 7 files changed, 1218 insertions(+), 7 deletions(-) create mode 100644 libstdc++-v3/include/bits/max_size_type.h create mode 100644 libstdc++-v3/testsuite/std/ranges/iota/difference_type.cc create mode 100644 libstdc++-v3/testsuite/std/ranges/iota/max_size_type.cc diff --git a/libstdc++-v3/include/Makefile.am b/libstdc++-v3/include/Makefile.am index 80aeb3f8959..a1460b98247 100644 --- a/libstdc++-v3/include/Makefile.am +++ b/libstdc++-v3/include/Makefile.am @@ -144,6 +144,7 @@ bits_headers = \ ${bits_srcdir}/locale_facets_nonio.tcc \ ${bits_srcdir}/localefwd.h \ ${bits_srcdir}/mask_array.h \ + ${bits_srcdir}/max_size_type.h \ ${bits_srcdir}/memoryfwd.h \ ${bits_srcdir}/move.h \ ${bits_srcdir}/node_handle.h \ diff --git a/libstdc++-v3/include/Makefile.in b/libstdc++-v3/include/Makefile.in index eb437ad8d8d..dd317fa0178 100644 --- a/libstdc++-v3/include/Makefile.in +++ b/libstdc++-v3/include/Makefile.in @@ -489,6 +489,7 @@ bits_headers = \ ${bits_srcdir}/locale_facets_nonio.tcc \ ${bits_srcdir}/localefwd.h \ ${bits_srcdir}/mask_array.h \ + ${bits_srcdir}/max_size_type.h \ ${bits_srcdir}/memoryfwd.h \ ${bits_srcdir}/move.h \ ${bits_srcdir}/node_handle.h \ diff --git a/libstdc++-v3/include/bits/iterator_concepts.h b/libstdc++-v3/include/bits/iterator_concepts.h index 08e622259b4..6eff0b82feb 100644 --- a/libstdc++-v3/include/bits/iterator_concepts.h +++ b/libstdc++-v3/include/bits/iterator_concepts.h @@ -482,20 +482,21 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION namespace ranges::__detail { -#if __SIZEOF_INT128__ - using __max_diff_type = __int128; - using __max_size_type = unsigned __int128; -#else - using __max_diff_type = long long; - using __max_size_type = unsigned long long; -#endif + class __max_diff_type; + class __max_size_type; template<typename _Tp> concept __is_integer_like = integral<_Tp> +#if __SIZEOF_INT128__ + || same_as<_Tp, __int128> || same_as<_Tp, unsigned __int128> +#endif || same_as<_Tp, __max_diff_type> || same_as<_Tp, __max_size_type>; template<typename _Tp> concept __is_signed_integer_like = signed_integral<_Tp> +#if __SIZEOF_INT128__ + || same_as<_Tp, __int128> +#endif || same_as<_Tp, __max_diff_type>; } // namespace ranges::__detail diff --git a/libstdc++-v3/include/bits/max_size_type.h b/libstdc++-v3/include/bits/max_size_type.h new file mode 100644 index 00000000000..cf6adcaf80a --- /dev/null +++ b/libstdc++-v3/include/bits/max_size_type.h @@ -0,0 +1,764 @@ +// <max_size_type.h> -*- C++ -*- + +// Copyright (C) 2019-2020 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. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// <http://www.gnu.org/licenses/>. + +/** @file bits/max_size_type.h. + * This is an internal header file, included by other library headers. + * Do not attempt to use it directly. @headername{iterator} + */ + +#ifndef _GLIBCXX_MAX_SIZE_TYPE_H +#define _GLIBCXX_MAX_SIZE_TYPE_H 1 + +#pragma GCC system_header + +#if __cplusplus > 201703L && __cpp_lib_concepts +#include <bits/int_limits.h> +#include <numbers> + +// This header implements unsigned and signed integer-class types (as per +// [iterator.concept.winc]) that are one bit wider than the largest supported +// integer type. The set of integer types we consider includes __int128 and +// unsigned __int128 (when they exist), even though they are integer types only +// in GNU mode. This is to obtain a consistent ABI for these types across both +// strict mode and GNU mode. + +namespace std _GLIBCXX_VISIBILITY(default) +{ +_GLIBCXX_BEGIN_NAMESPACE_VERSION + +template<typename _Tp> + struct numeric_limits; + +namespace ranges +{ + namespace __detail + { + // In strict mode, __int128 does not model integral but we still always + // want to accept this type wherever we expect an integral type in the rest + // of the API. To that end, we use the following concept instead. + template<typename _Tp> + concept __integralish +#if __SIZEOF_INT128__ + = (integral<_Tp> + || same_as<_Tp, unsigned __int128> + || same_as<_Tp, __int128>); +#else + = integral<_Tp>; +#endif + + class __max_size_type + { + public: + __max_size_type() = default; + + template<__integralish _Tp> + constexpr + __max_size_type(_Tp __i) noexcept + : _M_val(__i), _M_msb(__i < 0) + { } + + constexpr explicit + __max_size_type(const __max_diff_type& __d) noexcept; + + template<__integralish _Tp> + constexpr explicit operator _Tp() const noexcept + { return _M_val; } + + constexpr explicit + operator bool() const noexcept + { return _M_val != 0 || _M_msb != 0; } + + constexpr __max_size_type + operator+() const noexcept + { return *this; } + + constexpr __max_size_type + operator~() const noexcept + { return __max_size_type{~_M_val, !_M_msb}; } + + constexpr __max_size_type + operator-() const noexcept + { return operator~() + 1; } + + constexpr __max_size_type& + operator+=(const __max_size_type& __r) noexcept + { + const auto __sum = _M_val + __r._M_val; + const bool __overflow = (__sum < _M_val); + _M_msb = _M_msb ^ __r._M_msb ^ __overflow; + _M_val = __sum; + return *this; + } + + constexpr __max_size_type& + operator-=(const __max_size_type& __r) noexcept + { return *this += -__r; } + + constexpr __max_size_type& + operator*=(__max_size_type __r) noexcept + { + constexpr __max_size_type __threshold + = __rep(1) << (_S_rep_bits / 2 - 1); + if (_M_val < __threshold && __r < __threshold) [[likely]] + // When both operands are below this threshold then the multiplication + // can be safely computed in the base precision. + _M_val = _M_val * __r._M_val; + else + { + // Otherwise, perform the multiplication in four steps, by + // decomposing the LHS and the RHS into 2*x+a and 2*y+b + // respectively and computing 4*x*y + 2*x*b + 2*y*a + a*b. + const bool __lsb = _M_val & 1; + const bool __rlsb = __r._M_val & 1; + *this >>= 1; + __r >>= 1; + _M_val = (2 * _M_val * __r._M_val + + _M_val * __rlsb + __r._M_val * __lsb); + *this <<= 1; + *this += __rlsb * __lsb; + } + + return *this; + } + + constexpr __max_size_type& + operator/=(const __max_size_type& __r) noexcept + { + __glibcxx_assert(__r != 0); + + if (!_M_msb && !__r._M_msb) [[likely]] + _M_val /= __r._M_val; + else if (_M_msb && __r._M_msb) + { + _M_val = (_M_val >= __r._M_val); + _M_msb = 0; + } + else if (!_M_msb && __r._M_msb) + _M_val = 0; + else if (_M_msb && !__r._M_msb) + { + // The non-trivial case: the dividend has its MSB set and the + // divisor doesn't. In this case we compute ((LHS/2)/RHS)*2 in + // the base precision. This quantity is either the true quotient or + // one less than the true quotient. + const auto __orig = *this; + *this >>= 1; + _M_val /= __r._M_val; + *this <<= 1; + if (__orig - *this * __r >= __r) + ++_M_val; + } + return *this; + } + + constexpr __max_size_type& + operator%=(const __max_size_type& __r) noexcept + { + if (!_M_msb && !__r._M_msb) [[likely]] + _M_val %= __r._M_val; + else + *this -= (*this / __r) * __r; + return *this; + } + + constexpr __max_size_type& + operator<<=(const __max_size_type& __r) noexcept + { + __glibcxx_assert(__r <= _S_rep_bits); + if (__r != 0) + { + _M_msb = (_M_val >> (_S_rep_bits - __r._M_val)) & 1; + + if (__r._M_val == _S_rep_bits) [[unlikely]] + _M_val = 0; + else + _M_val <<= __r._M_val; + } + return *this; + } + + constexpr __max_size_type& + operator>>=(const __max_size_type& __r) noexcept + { + __glibcxx_assert(__r <= _S_rep_bits); + if (__r != 0) + { + if (__r._M_val == _S_rep_bits) [[unlikely]] + _M_val = 0; + else + _M_val >>= __r._M_val; + + if (_M_msb) [[unlikely]] + { + _M_val |= __rep(1) << (_S_rep_bits - __r._M_val); + _M_msb = 0; + } + } + return *this; + } + + constexpr __max_size_type& + operator&=(const __max_size_type& __r) noexcept + { + _M_val &= __r._M_val; + _M_msb &= __r._M_msb; + return *this; + } + + constexpr __max_size_type& + operator|=(const __max_size_type& __r) noexcept + { + _M_val |= __r._M_val; + _M_msb |= __r._M_msb; + return *this; + } + + constexpr __max_size_type& + operator^=(const __max_size_type& __r) noexcept + { + _M_val ^= __r._M_val; + _M_msb ^= __r._M_msb; + return *this; + } + + template<__integralish _Tp> + friend constexpr _Tp& + operator+=(_Tp& a, const __max_size_type& b) noexcept + { return (a = static_cast<_Tp>(a + b)); } + + template<__integralish _Tp> + friend constexpr _Tp& + operator-=(_Tp& a, const __max_size_type& b) noexcept + { return (a = static_cast<_Tp>(a - b)); } + + template<__integralish _Tp> + friend constexpr _Tp& + operator*=(_Tp& a, const __max_size_type& b) noexcept + { return (a = static_cast<_Tp>(a * b)); } + + template<__integralish _Tp> + friend constexpr _Tp& + operator/=(_Tp& a, const __max_size_type& b) noexcept + { return (a = static_cast<_Tp>(a / b)); } + + template<__integralish _Tp> + friend constexpr _Tp& + operator%=(_Tp& a, const __max_size_type& b) noexcept + { return (a = static_cast<_Tp>(a % b)); } + + template<__integralish _Tp> + friend constexpr _Tp& + operator&=(_Tp& a, const __max_size_type& b) noexcept + { return (a = static_cast<_Tp>(a & b)); } + + template<__integralish _Tp> + friend constexpr _Tp& + operator|=(_Tp& a, const __max_size_type& b) noexcept + { return (a = static_cast<_Tp>(a | b)); } + + template<__integralish _Tp> + friend constexpr _Tp& + operator^=(_Tp& a, const __max_size_type& b) noexcept + { return (a = static_cast<_Tp>(a ^ b)); } + + template<__integralish _Tp> + friend constexpr _Tp& + operator<<=(_Tp& a, const __max_size_type& b) noexcept + { return (a = static_cast<_Tp>(a << b)); } + + template<__integralish _Tp> + friend constexpr _Tp& + operator>>=(_Tp& a, const __max_size_type& b) noexcept + { return (a = static_cast<_Tp>(a >> b)); } + + friend constexpr __max_size_type + operator+(__max_size_type __l, const __max_size_type& __r) noexcept + { + __l += __r; + return __l; + } + + friend constexpr __max_size_type + operator-(__max_size_type __l, const __max_size_type& __r) noexcept + { + __l -= __r; + return __l; + } + + friend constexpr __max_size_type + operator*(__max_size_type __l, const __max_size_type& __r) noexcept + { + __l *= __r; + return __l; + } + + friend constexpr __max_size_type + operator/(__max_size_type __l, const __max_size_type& __r) noexcept + { + __l /= __r; + return __l; + } + + friend constexpr __max_size_type + operator%(__max_size_type __l, const __max_size_type& __r) noexcept + { + __l %= __r; + return __l; + } + + friend constexpr __max_size_type + operator<<(__max_size_type __l, const __max_size_type& __r) noexcept + { + __l <<= __r; + return __l; + } + + friend constexpr __max_size_type + operator>>(__max_size_type __l, const __max_size_type& __r) noexcept + { + __l >>= __r; + return __l; + } + + friend constexpr __max_size_type + operator&(__max_size_type __l, const __max_size_type& __r) noexcept + { + __l &= __r; + return __l; + } + + friend constexpr __max_size_type + operator|(__max_size_type __l, const __max_size_type& __r) noexcept + { + __l |= __r; + return __l; + } + + friend constexpr __max_size_type + operator^(__max_size_type __l, const __max_size_type& __r) noexcept + { + __l ^= __r; + return __l; + } + + friend constexpr bool + operator==(const __max_size_type& __l, const __max_size_type& __r) noexcept + { return __l._M_val == __r._M_val && __l._M_msb == __r._M_msb; } + + friend constexpr bool + operator!=(const __max_size_type& __l, const __max_size_type& __r) noexcept + { return !(__l == __r); } + + friend constexpr bool + operator<(const __max_size_type& __l, const __max_size_type& __r) noexcept + { + if (__l._M_msb == __r._M_msb) + return __l._M_val < __r._M_val; + else + return __r._M_msb; + } + + friend constexpr bool + operator>(const __max_size_type& __l, const __max_size_type& __r) noexcept + { return __r < __l; } + + friend constexpr bool + operator<=(const __max_size_type& __l, const __max_size_type& __r) noexcept + { return !(__l > __r); } + + friend constexpr bool + operator>=(const __max_size_type& __l, const __max_size_type& __r) noexcept + { return __r <= __l; } + +#if __SIZEOF_INT128__ + using __rep = unsigned __int128; +#else + using __rep = unsigned long long; +#endif + static constexpr size_t _S_rep_bits = sizeof(__rep) * __CHAR_BIT__; + private: + __rep _M_val = 0; + unsigned _M_msb:1 = 0; + + constexpr explicit + __max_size_type(__rep __val, int __msb) noexcept + : _M_val(__val), _M_msb(__msb) + { } + + friend __max_diff_type; + friend std::numeric_limits<__max_size_type>; + friend std::numeric_limits<__max_diff_type>; + }; + + class __max_diff_type + { + public: + __max_diff_type() = default; + + template<__integralish _Tp> + constexpr + __max_diff_type(_Tp __i) noexcept + : _M_rep(__i) + { } + + constexpr explicit + __max_diff_type(const __max_size_type& __d) noexcept + : _M_rep(__d) + { } + + template<__integralish _Tp> + constexpr explicit operator _Tp() const noexcept + { return static_cast<_Tp>(_M_rep); } + + constexpr explicit + operator bool() const noexcept + { return _M_rep != 0; } + + constexpr __max_diff_type + operator+() const noexcept + { return *this; } + + constexpr __max_diff_type + operator-() const noexcept + { return __max_diff_type(-_M_rep); } + + constexpr __max_diff_type + operator~() const noexcept + { return __max_diff_type(~_M_rep); } + + constexpr __max_diff_type& + operator+=(const __max_diff_type& __r) noexcept + { + _M_rep += __r._M_rep; + return *this; + } + + constexpr __max_diff_type& + operator-=(const __max_diff_type& __r) noexcept + { + _M_rep -= __r._M_rep; + return *this; + } + + constexpr __max_diff_type& + operator*=(const __max_diff_type& __r) noexcept + { + _M_rep *= __r._M_rep; + return *this; + } + + constexpr __max_diff_type& + operator/=(const __max_diff_type& __r) noexcept + { + __glibcxx_assert (__r != 0); + const bool __neg = *this < 0; + const bool __rneg = __r < 0; + if (!__neg && !__rneg) + _M_rep = _M_rep / __r._M_rep; + else if (__neg && __rneg) + _M_rep = -_M_rep / -__r._M_rep; + else if (__neg && !__rneg) + _M_rep = -(-_M_rep / __r._M_rep); + else + _M_rep = -(_M_rep / -__r._M_rep); + return *this ; + } + + constexpr __max_diff_type& + operator%=(const __max_diff_type& __r) noexcept + { + __glibcxx_assert (__r != 0); + if (*this >= 0 && __r > 0) + _M_rep %= __r._M_rep; + else + *this -= (*this / __r) * __r; + return *this; + } + + constexpr __max_diff_type& + operator<<=(const __max_diff_type& __r) noexcept + { + _M_rep.operator<<=(__r._M_rep); + return *this; + } + + constexpr __max_diff_type& + operator>>=(const __max_diff_type& __r) noexcept + { + // Arithmetic right shift. + const auto __msb = _M_rep._M_msb; + _M_rep >>= __r._M_rep; + _M_rep._M_msb |= __msb; + return *this; + } + + constexpr __max_diff_type& + operator&=(const __max_diff_type& __r) noexcept + { + _M_rep &= __r._M_rep; + return *this; + } + + constexpr __max_diff_type& + operator|=(const __max_diff_type& __r) noexcept + { + _M_rep |= __r._M_rep; + return *this; + } + + constexpr __max_diff_type& + operator^=(const __max_diff_type& __r) noexcept + { + _M_rep ^= __r._M_rep; + return *this; + } + + template<__integralish _Tp> + friend constexpr _Tp& + operator+=(_Tp& a, const __max_diff_type& b) noexcept + { return (a = static_cast<_Tp>(a + b)); } + + template<__integralish _Tp> + friend constexpr _Tp& + operator-=(_Tp& a, const __max_diff_type& b) noexcept + { return (a = static_cast<_Tp>(a - b)); } + + template<__integralish _Tp> + friend constexpr _Tp& + operator*=(_Tp& a, const __max_diff_type& b) noexcept + { return (a = static_cast<_Tp>(a * b)); } + + template<__integralish _Tp> + friend constexpr _Tp& + operator/=(_Tp& a, const __max_diff_type& b) noexcept + { return (a = static_cast<_Tp>(a / b)); } + + template<__integralish _Tp> + friend constexpr _Tp& + operator%=(_Tp& a, const __max_diff_type& b) noexcept + { return (a = static_cast<_Tp>(a % b)); } + + template<__integralish _Tp> + friend constexpr _Tp& + operator&=(_Tp& a, const __max_diff_type& b) noexcept + { return (a = static_cast<_Tp>(a & b)); } + + template<__integralish _Tp> + friend constexpr _Tp& + operator|=(_Tp& a, const __max_diff_type& b) noexcept + { return (a = static_cast<_Tp>(a | b)); } + + template<__integralish _Tp> + friend constexpr _Tp& + operator^=(_Tp& a, const __max_diff_type& b) noexcept + { return (a = static_cast<_Tp>(a ^ b)); } + + template<__integralish _Tp> + friend constexpr _Tp& + operator<<=(_Tp& a, const __max_diff_type& b) noexcept + { return (a = static_cast<_Tp>(a << b)); } + + template<__integralish _Tp> + friend constexpr _Tp& + operator>>=(_Tp& a, const __max_diff_type& b) noexcept + { return (a = static_cast<_Tp>(a >> b)); } + + friend constexpr __max_diff_type + operator+(__max_diff_type __l, const __max_diff_type& __r) noexcept + { + __l += __r; + return __l; + } + + friend constexpr __max_diff_type + operator-(__max_diff_type __l, const __max_diff_type& __r) noexcept + { + __l -= __r; + return __l; + } + + friend constexpr __max_diff_type + operator*(__max_diff_type __l, const __max_diff_type& __r) noexcept + { + __l *= __r; + return __l; + } + + friend constexpr __max_diff_type + operator/(__max_diff_type __l, const __max_diff_type& __r) noexcept + { + __l /= __r; + return __l; + } + + friend constexpr __max_diff_type + operator%(__max_diff_type __l, const __max_diff_type& __r) noexcept + { + __l %= __r; + return __l; + } + + friend constexpr __max_diff_type + operator<<(__max_diff_type __l, const __max_diff_type& __r) noexcept + { + __l <<= __r; + return __l; + } + + friend constexpr __max_diff_type + operator>>(__max_diff_type __l, const __max_diff_type& __r) noexcept + { + __l >>= __r; + return __l; + } + + friend constexpr __max_diff_type + operator&(__max_diff_type __l, const __max_diff_type& __r) noexcept + { + __l &= __r; + return __l; + } + + friend constexpr __max_diff_type + operator|(__max_diff_type __l, const __max_diff_type& __r) noexcept + { + __l |= __r; + return __l; + } + + friend constexpr __max_diff_type + operator^(__max_diff_type __l, const __max_diff_type& __r) noexcept + { + __l ^= __r; + return __l; + } + + friend constexpr bool + operator==(const __max_diff_type& __l, const __max_diff_type& __r) noexcept + { return __l._M_rep == __r._M_rep; } + + friend constexpr bool + operator!=(const __max_diff_type& __l, const __max_diff_type& __r) noexcept + { return !(__l == __r); } + + constexpr bool + operator<(const __max_diff_type& __r) const noexcept + { + const auto __lsign = _M_rep._M_msb; + const auto __rsign = __r._M_rep._M_msb; + if (__lsign ^ __rsign) + return __lsign; + else + return _M_rep < __r._M_rep; + } + + friend constexpr bool + operator>(const __max_diff_type& __l, const __max_diff_type& __r) noexcept + { return __r < __l; } + + friend constexpr bool + operator<=(const __max_diff_type& __l, const __max_diff_type& __r) noexcept + { return !(__r < __l); } + + friend constexpr bool + operator>=(const __max_diff_type& __l, const __max_diff_type& __r) noexcept + { return !(__l < __r); } + + private: + __max_size_type _M_rep = 0; + + friend class __max_size_type; + }; + + constexpr + __max_size_type::__max_size_type(const __max_diff_type& __d) noexcept + : __max_size_type(__d._M_rep) + { } + + } // namespace __detail +} // namespace ranges + + template<> + struct numeric_limits<ranges::__detail::__max_size_type> + { + using _Sp = ranges::__detail::__max_size_type; + static constexpr bool is_specialized = true; + static constexpr bool is_signed = false; + static constexpr bool is_integer = true; + static constexpr bool is_exact = true; +#if __SIZEOF_INT128__ + static_assert(same_as<_Sp::__rep, unsigned __int128>); + static constexpr int digits = 129; +#else + static_assert(same_as<_Sp::__rep, unsigned long long>); + static constexpr int digits + = __detail::__int_limits<unsigned long long>::digits + 1; +#endif + static constexpr int digits10 + = static_cast<int>(digits * numbers::ln2 / numbers::ln10); + + static constexpr _Sp + min() noexcept + { return 0; } + + static constexpr _Sp + max() noexcept + { return _Sp(static_cast<_Sp::__rep>(-1), 1); } + + static constexpr _Sp + lowest() noexcept + { return min(); } + }; + + template<> + struct numeric_limits<ranges::__detail::__max_diff_type> + { + using _Dp = ranges::__detail::__max_diff_type; + using _Sp = ranges::__detail::__max_size_type; + static constexpr bool is_specialized = true; + static constexpr bool is_signed = true; + static constexpr bool is_integer = true; + static constexpr bool is_exact = true; + static constexpr int digits = numeric_limits<_Sp>::digits - 1; + static constexpr int digits10 + = static_cast<int>(digits * numbers::ln2 / numbers::ln10); + + static constexpr _Dp + min() noexcept + { return _Dp(_Sp(0, 1)); } + + static constexpr _Dp + max() noexcept + { return _Dp(_Sp(static_cast<_Sp::__rep>(-1), 0)); } + + static constexpr _Dp + lowest() noexcept + { return min(); } + }; + +_GLIBCXX_END_NAMESPACE_VERSION +} // namespace + +#endif // C++20 && library concepts +#endif // _GLIBCXX_MAX_SIZE_TYPE_H diff --git a/libstdc++-v3/include/bits/range_access.h b/libstdc++-v3/include/bits/range_access.h index 8b276fd6625..c814694623c 100644 --- a/libstdc++-v3/include/bits/range_access.h +++ b/libstdc++-v3/include/bits/range_access.h @@ -36,6 +36,9 @@ #include <initializer_list> #include <bits/iterator_concepts.h> #include <bits/int_limits.h> +#if __cplusplus > 201703L +#include <bits/max_size_type.h> +#endif namespace std _GLIBCXX_VISIBILITY(default) { @@ -351,6 +354,14 @@ namespace ranges namespace __detail { + constexpr __max_size_type + __to_unsigned_like(__max_size_type __t) noexcept + { return __t; } + + constexpr __max_size_type + __to_unsigned_like(__max_diff_type __t) noexcept + { return __max_size_type(__t); } + template<integral _Tp> constexpr make_unsigned_t<_Tp> __to_unsigned_like(_Tp __t) noexcept diff --git a/libstdc++-v3/testsuite/std/ranges/iota/difference_type.cc b/libstdc++-v3/testsuite/std/ranges/iota/difference_type.cc new file mode 100644 index 00000000000..4a342deae74 --- /dev/null +++ b/libstdc++-v3/testsuite/std/ranges/iota/difference_type.cc @@ -0,0 +1,57 @@ +// Copyright (C) 2020 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 +// <http://www.gnu.org/licenses/>. + +// { dg-options "-std=gnu++2a" } +// { dg-do run { target c++2a } } + +#include <ranges> +#include <testsuite_hooks.h> + +void +test01() +{ + using I = unsigned long long; + auto imax = std::numeric_limits<I>::max(); + std::ranges::iota_view<I, I> i(0, imax); + auto begin = i.begin(); + static_assert( std::input_or_output_iterator<decltype(begin)> ); + auto size = std::ranges::end(i) - std::ranges::begin(i); + VERIFY( size > 0 ); + VERIFY( size == imax ); +} + +void +test02() +{ +#if __SIZEOF_INT128__ + using I = unsigned __int128; + auto imax = std::numeric_limits<I>::max(); + std::ranges::iota_view<I, I> i(0, imax); + auto begin = i.begin(); + static_assert( std::input_or_output_iterator<decltype(begin)> ); + auto size = std::ranges::end(i) - std::ranges::begin(i); + VERIFY( size > 0 ); + VERIFY( size == imax ); +#endif +} + +int +main() +{ + test01(); + test02(); +} diff --git a/libstdc++-v3/testsuite/std/ranges/iota/max_size_type.cc b/libstdc++-v3/testsuite/std/ranges/iota/max_size_type.cc new file mode 100644 index 00000000000..7aa8e5969b2 --- /dev/null +++ b/libstdc++-v3/testsuite/std/ranges/iota/max_size_type.cc @@ -0,0 +1,376 @@ +// Copyright (C) 2020 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 +// <http://www.gnu.org/licenses/>. + +// { dg-options "-std=gnu++2a" } +// { dg-do run { target c++2a } } + +#include <limits> +#include <ranges> +#include <testsuite_hooks.h> + +using max_size_t = std::ranges::__detail::__max_size_type; +using max_diff_t = std::ranges::__detail::__max_diff_type; +using rep_t = max_size_t::__rep; + +static_assert(sizeof(max_size_t) == sizeof(max_diff_t)); + +static_assert(std::regular<max_size_t>); +static_assert(std::totally_ordered<max_size_t>); + +static_assert(std::regular<max_diff_t>); +static_assert(std::totally_ordered<max_diff_t>); + +// XXX: We can't use numeric_limits<rep_t>::max() here because __int128 is an +// integral type only in GNU mode. +constexpr max_size_t mu = max_size_t(~rep_t(0)); +constexpr max_size_t ou = 1; +constexpr max_diff_t ns = -1; + +void +test01() +{ + static_assert(max_size_t(7) % 3 == 1); + static_assert(max_size_t(7) % 4 == 3); + + static_assert(-max_diff_t(1) == max_diff_t(-1)); + static_assert(max_diff_t(3) % 2 == 1); + static_assert(max_diff_t(-3) / 2 == -1); + static_assert(max_diff_t(-3) % 2 == -1); + static_assert(max_diff_t(3) % -2 == 1); + static_assert(max_diff_t(-3) << 1 == -6); + static_assert(max_diff_t(-3) >> 1 == -2); + static_assert(max_diff_t(3) >> 1 == 1); + static_assert(max_diff_t(3) >> 2 == 0); + + static_assert(max_diff_t(-5) / 3 == -1); + static_assert(max_diff_t(5) / -3 == -1); + static_assert(max_diff_t(-5) / -3 == 1); + static_assert(max_diff_t(5) / 3 == 1); + + static_assert(max_diff_t(-6) / 3 == -2); + static_assert(max_diff_t(6) / -3 == -2); + static_assert(max_diff_t(-6) / -3 == 2); + static_assert(max_diff_t(6) / 3 == 2); + + static_assert(~max_size_t(-3) == 2); + static_assert(~max_diff_t(-3) == 2); + + static_assert(max_diff_t(1) < max_diff_t(3)); + static_assert(max_diff_t(-1) < max_diff_t(3)); + static_assert(max_diff_t(1) > max_diff_t(-3)); + static_assert(max_diff_t(-1) > max_diff_t(-3)); + + static_assert(max_diff_t(mu)/-1 == -max_diff_t(mu)); + static_assert(-max_diff_t(mu)/1 == -max_diff_t(mu)); + static_assert(max_diff_t(mu)>>1 == max_diff_t(mu)/2); + static_assert(-max_diff_t(mu+1) == max_diff_t(mu+1)); + static_assert(-(mu+1) == mu+1); + static_assert((mu+1)<<1 == 0); + static_assert(max_diff_t(mu+1)<<1 == 0); + static_assert(max_diff_t(mu+1)>>1 < 0); + + static_assert(int(max_diff_t(mu+1)) == 0); + static_assert(rep_t(max_diff_t(mu+1)) == 0); + static_assert(int(max_diff_t(mu)) == -1); + static_assert(rep_t(max_diff_t(mu)) == rep_t(-1)); + + static_assert(2*mu+1 > 2*mu); + static_assert(~(2*mu+1) == 0); + static_assert(mu/mu == 1); + static_assert(2*mu > mu); + static_assert(2*mu-mu == mu); + static_assert((2*mu)/mu == 2); + static_assert((2*mu+1)/mu == 2); + static_assert((2*mu-1)/(mu-1) == 2); + static_assert((2*mu-1)/mu == 1); + static_assert((2*mu+-1)/mu == 1); + static_assert(2*mu-1 < 2*mu); + static_assert(2*mu-1 <= 2*mu); + static_assert(2*mu+1 > 2*mu); + static_assert(2*mu+1 >= 2*mu); + static_assert((2*mu)/1 == 2*mu); + static_assert(mu/mu-1 == 0); + static_assert(mu*0 == 0); + static_assert((2*mu-1)*0 == 0); + static_assert((2*mu-1)>>1 == mu-1); + static_assert(mu+-1+1 == mu); + static_assert(mu+1+-1 == mu); + static_assert(mu+1); + static_assert((2*mu)/2 == mu); + static_assert((2*mu)>>1 == mu); + static_assert((mu<<1)>>1 == mu); + static_assert(1/mu == 0); + static_assert(mu/1 == mu); + static_assert(((mu+1)|mu) == -1); + static_assert((mu+1)+(mu+1) < mu+1); + + static_assert(max_size_t(ns) == -1); + static_assert(-max_diff_t(ou) == -1); + static_assert(-max_diff_t(-ou) == 1); + static_assert(max_size_t(-max_diff_t(-ou)) == 1); + static_assert(ns*ns == max_diff_t(ou)); + static_assert(max_size_t(ns)*max_size_t(ns) == ou); + static_assert(-max_diff_t(0) == max_diff_t(0)); + static_assert(-ou-ou == -2*ou); + + static_assert(int(ns) == -1); + static_assert(rep_t(ns) == rep_t(-1)); + + static_assert(max_size_t() == 0); + static_assert(max_diff_t() == 0); + + auto f = [] (auto a) { a /= a; return a; }; + static_assert(f(max_size_t(5)) == 1); + static_assert(f(max_size_t(-5)) == 1); + static_assert(f(max_diff_t(5)) == 1); + + auto g = [] (auto a) { a >>= a; return a; }; + static_assert(g(max_size_t(5)) == 0); + static_assert(g(max_diff_t(5)) == 0); + + auto h = [] (auto a) { a <<= a; return a; }; + static_assert(h(max_size_t(3)) == 24); + static_assert(h(max_diff_t(3)) == 24); +} + +template<bool signed_p, bool shorten_p> +void +test02() +{ + using hw_type = std::conditional_t<signed_p, signed rep_t, rep_t>; + using max_type = std::conditional_t<signed_p, max_diff_t, max_size_t>; + using shorten_type = std::conditional_t<shorten_p, hw_type, max_type>; + const int hw_type_bit_size = sizeof(hw_type) * __CHAR_BIT__; + const int limit = 1000; + const int log2_limit = 10; + static_assert((1 << log2_limit) >= limit); + const int min = (signed_p ? -limit : 0); + const int max = limit; + for (hw_type i = min; i <= max; i++) + { + bool ok = true; + if (signed_p || shorten_p) + { + ok &= (~i == shorten_type(~max_type(i))); + ok &= (-i == shorten_type(-max_type(i))); + } + for (hw_type j = min; j <= max; j++) + { + ok &= (i*j == shorten_type(max_type(i)*j)); + ok &= (i+j == shorten_type(max_type(i)+j)); + if (j != 0) + { + ok &= (i/j == shorten_type(max_type(i)/j)); + ok &= (i%j == shorten_type(max_type(i)%j)); + } + if (signed_p || shorten_p) + ok &= (i-j == shorten_type(max_type(i)-j)); + ok &= ((i&j) == shorten_type(max_type(i)&j)); + ok &= ((i|j) == shorten_type(max_type(i)|j)); + ok &= ((i^j) == shorten_type(max_type(i)^j)); + if (j >= 0 && j < hw_type(hw_type_bit_size) + && (shorten_p || j < hw_type(hw_type_bit_size) - log2_limit)) + { + ok &= ((i>>j) == shorten_type(max_type(i)>>j)); + ok &= ((i<<j) == shorten_type(max_type(i)<<j)); + } + ok &= (i>j) == (max_type(i) > j); + ok &= (i<j) == (max_type(i) < j); + ok &= (i>=j) == (max_type(i) >= j); + ok &= (i<=j) == (max_type(i) <= j); + ok &= (i==j) == (max_type(i) == j); + ok &= (i!=j) == (max_type(i) != j); + if (!ok) + { + fprintf(stderr, + "Inconsistency found: %d %d %lld %lld\n", + signed_p, shorten_p, (long long)i, (long long)j) ; + VERIFY(0); + } + } + } +} + +template<bool signed_p, bool toggle_base_p> +void +test03() +{ + using hw_type = std::conditional_t<signed_p, signed rep_t, rep_t>; + using max_type = std::conditional_t<signed_p, max_diff_t, max_size_t>; + using base_type = std::conditional_t<toggle_base_p, hw_type, max_type>; + constexpr int hw_type_bit_size = sizeof(hw_type) * __CHAR_BIT__; + constexpr int limit = 1000; + constexpr int log2_limit = 10; + static_assert((1 << log2_limit) >= limit); + const int min = (signed_p ? -limit : 0); + const int max = limit; + for (hw_type i = min; i <= max; i++) + { + bool ok = true; + base_type k; + for (hw_type j = min; j <= max; j++) + { + k = i; k *= j; + ok &= (k == (max_type(i)*j)); + k = i; k += j; + ok &= (k == (max_type(i)+j)); + if (j != 0) + { + k = i; k /= j; + ok &= (k == (max_type(i)/j)); + k = i; k %= j; + ok &= (k == (max_type(i)%j)); + } + if (signed_p) + { + k = i; k -= j; + ok &= (k == (max_type(i)-j)); + } + k = i; k &= j; + ok &= (k == (max_type(i)&j)); + k = i; k |= j; + ok &= (k == (max_type(i)|j)); + k = i; k ^= j; + ok &= (k == (max_type(i)^j)); + if (j >= 0 && j < hw_type(hw_type_bit_size) + && (!toggle_base_p || j < hw_type(hw_type_bit_size) - log2_limit)) + { + k = i; k >>= j; + ok &= (k == (max_type(i)>>j)); + k = i; k <<= j; + ok &= (k == (max_type(i)<<j)); + } + if (!ok) + { + fprintf(stderr, + "Inconsistency found: %d %d %lld %lld\n", + signed_p, toggle_base_p, (long long)i, (long long)j) ; + VERIFY(0); + } + } + } +} + +void +test04() +{ + constexpr int limit = 1000; + for (int i = -limit; i <= limit; i++) + { + VERIFY( -max_size_t(-i) == i ); + for (int j = i; j <= limit; j++) + { + VERIFY( max_size_t(-i) * max_size_t(-j) == i*j ); + VERIFY( max_size_t(-j) * max_size_t(-i) == j*i ); + VERIFY( rep_t(((mu+1)+i)*((mu+1)+j)) == rep_t(i*j) ); + VERIFY( rep_t(((mu+1)+j)*((mu+1)+i)) == rep_t(j*i) ); + if (i >= 0 && j > 0) + { + auto r = (mu+i)-((mu+i)/j)*j; + VERIFY( r >= 0 && r < j ); + VERIFY( r == (mu+i)%j ); + } + } + } +} + +void +test05() +{ +#if __SIZEOF_INT128__ + max_size_t x = 0; + x = static_cast<__int128>(0); + x = static_cast<unsigned __int128>(0); + + max_diff_t y = 0; + y = static_cast<__int128>(0);; + y = static_cast<unsigned __int128>(0); +#endif +} + +using std::numeric_limits; + +static_assert(numeric_limits<max_size_t>::is_specialized); +static_assert(!numeric_limits<max_size_t>::is_signed); +static_assert(numeric_limits<max_size_t>::is_integer); +static_assert(numeric_limits<max_size_t>::is_exact); +// XXX: We can't unconditionally use numeric_limits here because __int128 is an +// integral type only in GNU mode. +#if __SIZEOF_INT128__ +static_assert(numeric_limits<max_size_t>::digits == 129); +static_assert(numeric_limits<max_size_t>::digits10 == 38); +static_assert(numeric_limits<max_size_t>::max() + == 2*max_size_t(~rep_t(0)) + 1); +#else +static_assert(numeric_limits<max_size_t>::digits + == numeric_limits<rep_t>::digits + 1); +static_assert(numeric_limits<max_size_t>::digits10 + == numeric_limits<rep_t>::digits10); +static_assert(numeric_limits<max_size_t>::max() + == 2*max_size_t(numeric_limits<rep_t>::max())+1); +#endif +static_assert(numeric_limits<max_size_t>::min() == 0); +static_assert(numeric_limits<max_size_t>::max() + == max_size_t(-1)); +static_assert((numeric_limits<max_size_t>::max() + >> (numeric_limits<max_size_t>::digits-1)) == 1); +static_assert(numeric_limits<max_size_t>::lowest() + == numeric_limits<max_size_t>::min()); + +static_assert(numeric_limits<max_diff_t>::is_specialized); +static_assert(numeric_limits<max_diff_t>::is_signed); +static_assert(numeric_limits<max_diff_t>::is_integer); +static_assert(numeric_limits<max_diff_t>::is_exact); +static_assert(numeric_limits<max_diff_t>::digits + == numeric_limits<max_size_t>::digits - 1); +static_assert(numeric_limits<max_diff_t>::digits10 + == numeric_limits<max_size_t>::digits10); +// XXX: We can't unconditionally use numeric_limits here because __int128 is an +// integral type only in GNU mode. +#if __SIZEOF_INT128__ +static_assert(numeric_limits<max_diff_t>::min() == -max_diff_t(~rep_t(0))-1); +static_assert(numeric_limits<max_diff_t>::max() == ~rep_t(0)); +#else +static_assert(numeric_limits<max_diff_t>::min() + == -max_diff_t(numeric_limits<rep_t>::max())-1); +static_assert(numeric_limits<max_diff_t>::max() + == numeric_limits<rep_t>::max()); +#endif +static_assert(numeric_limits<max_diff_t>::lowest() + == numeric_limits<max_diff_t>::min()); +static_assert(max_diff_t(max_size_t(1) + << (numeric_limits<max_size_t>::digits-1)) + == numeric_limits<max_diff_t>::min()); + +int +main() +{ + test01(); + + test02<false,false>(); + test02<false,true>(); + test02<true,false>(); + test02<true,true>(); + + test03<false,false>(); + test03<false,true>(); + test03<true,false>(); + test03<true,true>(); + + test04(); + test05(); +}
On Mon, 2 Mar 2020, Patrick Palka wrote: > On Mon, 24 Feb 2020, Patrick Palka wrote: > > > On Mon, 24 Feb 2020, Patrick Palka wrote: > > > > > This implements signed and unsigned integer-class types, whose width is one bit > > > larger than the widest native signed and unsigned integral type respectively. > > > In our case this is either __int128 and unsigned __int128, or long long and > > > unsigned long long. > > > > > > Internally, the two integer-class types are represented as a largest native > > > unsigned integral type plus one extra bit. The signed integer-class type is > > > represented in two's complement form with the extra bit acting as the sign bit. > > > > > > libstdc++-v3/ChangeLog: > > > > > > * include/bits/iterator_concepts.h (ranges::__detail::__max_diff_type): > > > Remove definition, replace with forward declaration of class > > > __max_diff_type. > > > (ranges::__detail::__max_size_type): Remove definition, replace with > > > forward declaration of class __max_size_type. > > > (__detail::__is_integer_like): Accept __int128 and unsigned __int128. > > > (__detail::__is_signed_integer_like): Accept __int128. > > > * include/bits/range_access.h (__detail::__max_size_type): New class. > > > (__detail::__max_diff_type): New class. > > > (__detail::__max_size_type::__max_size_type): Define this constructor > > > out-of-line to break the cycle. > > > (__detail::__to_unsigned_like): New function. > > > (numeric_limits<__detail::__max_size_type>): New explicit specialization. > > > (numeric_limits<__detail::__max_diff_type>): New explicit specialization. > > > * testsuite/std/ranges/iota/differenc_type.cc: New test. > > > > Here's v2 of the patch that splits out __max_size_type and > > __max_diff_type into a dedicated header, along with other misc > > improvements and fixes. > > > > -- >8 -- > > Here's v3 of the patch. Changes from v2: > > * The arithmetic tests in difference_type.cc have been split out to a > separate file. > > * The arithmetic tests now run successfully in strict ANSI mode. The > issue was that __int128 does not model the integral concept in strict > ANSI mode, which we use to make operations on this type behave as > integer operations do. But for that we need to always treat __int128 as > an integer type in this API. So a new concept __integralish which is > always modelled by __int128 is introduced and used in the API instead. > > * Comments have been added explaining why __int128 is always used as the > underlying type even when the widest integer type in strict ANSI mode is > long long. > > * New tests, some minor code clean-ups, and added comments to the > unsigned division and multiplication routines. > > Tested on x86_64-pc-linux-gnu in both strict and GNU compilation modes, > with and without -U__SIZEOF_INT128__. Ping (now that stage 1 is open). Here's the latest rebased of version of the patch: -- >8 -- Subject: [PATCH] libstdc++: integer-class types as per [iterator.concept.winc] This implements signed and unsigned integer-class types, whose width is one bit larger than the widest supported signed and unsigned integral type respectively. In our case this is either __int128 and unsigned __int128, or long long and unsigned long long. Internally, the two integer-class types are represented as a largest supported unsigned integral type plus one extra bit. The signed integer-class type is represented in two's complement form with the extra bit acting as the sign bit. libstdc++-v3/ChangeLog: * include/Makefile.am (bits_headers): Add new header <bits/max_size_type.h>. * include/Makefile.in: Regenerate. * include/bits/iterator_concepts.h (ranges::__detail::__max_diff_type): Remove definition, replace with forward declaration of class __max_diff_type. (__detail::__max_size_type): Remove definition, replace with forward declaration of class __max_size_type. (__detail::__is_unsigned_int128, __is_signed_int128, __is_int128): New concepts. (__detail::__is_integer_like): Accept __int128 and unsigned __int128. (__detail::__is_signed_integer_like): Accept __int128. * include/bits/max_size_type.h: New header. * include/bits/range_access.h: Include <bits/max_size_type.h>. (__detail::__to_unsigned_like): Two new overloads. * testsuite/std/ranges/iota/difference_type.cc: New test. * testsuite/std/ranges/iota/max_size_type.cc: New test. --- libstdc++-v3/include/Makefile.am | 1 + libstdc++-v3/include/Makefile.in | 1 + libstdc++-v3/include/bits/iterator_concepts.h | 24 +- libstdc++-v3/include/bits/max_size_type.h | 753 ++++++++++++++++++ libstdc++-v3/include/bits/range_access.h | 11 + .../std/ranges/iota/difference_type.cc | 57 ++ .../std/ranges/iota/max_size_type.cc | 376 +++++++++ 7 files changed, 1219 insertions(+), 4 deletions(-) create mode 100644 libstdc++-v3/include/bits/max_size_type.h create mode 100644 libstdc++-v3/testsuite/std/ranges/iota/difference_type.cc create mode 100644 libstdc++-v3/testsuite/std/ranges/iota/max_size_type.cc diff --git a/libstdc++-v3/include/Makefile.am b/libstdc++-v3/include/Makefile.am index 80aeb3f8959..a1460b98247 100644 --- a/libstdc++-v3/include/Makefile.am +++ b/libstdc++-v3/include/Makefile.am @@ -144,6 +144,7 @@ bits_headers = \ ${bits_srcdir}/locale_facets_nonio.tcc \ ${bits_srcdir}/localefwd.h \ ${bits_srcdir}/mask_array.h \ + ${bits_srcdir}/max_size_type.h \ ${bits_srcdir}/memoryfwd.h \ ${bits_srcdir}/move.h \ ${bits_srcdir}/node_handle.h \ diff --git a/libstdc++-v3/include/Makefile.in b/libstdc++-v3/include/Makefile.in index eb437ad8d8d..dd317fa0178 100644 --- a/libstdc++-v3/include/Makefile.in +++ b/libstdc++-v3/include/Makefile.in @@ -489,6 +489,7 @@ bits_headers = \ ${bits_srcdir}/locale_facets_nonio.tcc \ ${bits_srcdir}/localefwd.h \ ${bits_srcdir}/mask_array.h \ + ${bits_srcdir}/max_size_type.h \ ${bits_srcdir}/memoryfwd.h \ ${bits_srcdir}/move.h \ ${bits_srcdir}/node_handle.h \ diff --git a/libstdc++-v3/include/bits/iterator_concepts.h b/libstdc++-v3/include/bits/iterator_concepts.h index e221ec70367..0472b4ac707 100644 --- a/libstdc++-v3/include/bits/iterator_concepts.h +++ b/libstdc++-v3/include/bits/iterator_concepts.h @@ -502,20 +502,36 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION namespace ranges::__detail { + class __max_diff_type; + class __max_size_type; + + template<typename _Tp> + concept __is_signed_int128 #if __SIZEOF_INT128__ - using __max_diff_type = __int128; - using __max_size_type = unsigned __int128; + = same_as<_Tp, __int128>; #else - using __max_diff_type = long long; - using __max_size_type = unsigned long long; + = false; #endif + template<typename _Tp> + concept __is_unsigned_int128 +#if __SIZEOF_INT128__ + = same_as<_Tp, unsigned __int128>; +#else + = false; +#endif + + template<typename _Tp> + concept __is_int128 = __is_signed_int128<_Tp> || __is_unsigned_int128<_Tp>; + template<typename _Tp> concept __is_integer_like = integral<_Tp> + || __is_int128<_Tp> || same_as<_Tp, __max_diff_type> || same_as<_Tp, __max_size_type>; template<typename _Tp> concept __is_signed_integer_like = signed_integral<_Tp> + || __is_signed_int128<_Tp> || same_as<_Tp, __max_diff_type>; } // namespace ranges::__detail diff --git a/libstdc++-v3/include/bits/max_size_type.h b/libstdc++-v3/include/bits/max_size_type.h new file mode 100644 index 00000000000..4199dd7bd2a --- /dev/null +++ b/libstdc++-v3/include/bits/max_size_type.h @@ -0,0 +1,753 @@ +// <max_size_type.h> -*- C++ -*- + +// Copyright (C) 2019-2020 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. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// <http://www.gnu.org/licenses/>. + +/** @file bits/max_size_type.h. + * This is an internal header file, included by other library headers. + * Do not attempt to use it directly. @headername{iterator} + */ + +#ifndef _GLIBCXX_MAX_SIZE_TYPE_H +#define _GLIBCXX_MAX_SIZE_TYPE_H 1 + +#pragma GCC system_header + +#if __cplusplus > 201703L && __cpp_lib_concepts +#include <bits/int_limits.h> +#include <numbers> + +// This header implements unsigned and signed integer-class types (as per +// [iterator.concept.winc]) that are one bit wider than the widest supported +// integer type. +// +// The set of integer types we consider includes __int128 and unsigned __int128 +// (when they exist), even though they are really integer types only in GNU +// mode. This is to obtain a consistent ABI for these integer-class types +// across strict mode and GNU mode. + +namespace std _GLIBCXX_VISIBILITY(default) +{ +_GLIBCXX_BEGIN_NAMESPACE_VERSION + +template<typename _Tp> + struct numeric_limits; + +namespace ranges +{ + namespace __detail + { + class __max_size_type + { + public: + __max_size_type() = default; + + template<typename _Tp> requires integral<_Tp> || __is_int128<_Tp> + constexpr + __max_size_type(_Tp __i) noexcept + : _M_val(__i), _M_msb(__i < 0) + { } + + constexpr explicit + __max_size_type(const __max_diff_type& __d) noexcept; + + template<typename _Tp> requires integral<_Tp> || __is_int128<_Tp> + constexpr explicit operator _Tp() const noexcept + { return _M_val; } + + constexpr explicit + operator bool() const noexcept + { return _M_val != 0 || _M_msb != 0; } + + constexpr __max_size_type + operator+() const noexcept + { return *this; } + + constexpr __max_size_type + operator~() const noexcept + { return __max_size_type{~_M_val, !_M_msb}; } + + constexpr __max_size_type + operator-() const noexcept + { return operator~() + 1; } + + constexpr __max_size_type& + operator+=(const __max_size_type& __r) noexcept + { + const auto __sum = _M_val + __r._M_val; + const bool __overflow = (__sum < _M_val); + _M_msb = _M_msb ^ __r._M_msb ^ __overflow; + _M_val = __sum; + return *this; + } + + constexpr __max_size_type& + operator-=(const __max_size_type& __r) noexcept + { return *this += -__r; } + + constexpr __max_size_type& + operator*=(__max_size_type __r) noexcept + { + constexpr __max_size_type __threshold + = __rep(1) << (_S_rep_bits / 2 - 1); + if (_M_val < __threshold && __r < __threshold) [[likely]] + // When both operands are below this threshold then the + // multiplication can be safely computed in the base precision. + _M_val = _M_val * __r._M_val; + else + { + // Otherwise, perform the multiplication in four steps, by + // decomposing the LHS and the RHS into 2*x+a and 2*y+b, + // respectively, and computing 4*x*y + 2*x*b + 2*y*a + a*b. + const bool __lsb = _M_val & 1; + const bool __rlsb = __r._M_val & 1; + *this >>= 1; + __r >>= 1; + _M_val = (2 * _M_val * __r._M_val + + _M_val * __rlsb + __r._M_val * __lsb); + *this <<= 1; + *this += __rlsb * __lsb; + } + + return *this; + } + + constexpr __max_size_type& + operator/=(const __max_size_type& __r) noexcept + { + __glibcxx_assert(__r != 0); + + if (!_M_msb && !__r._M_msb) [[likely]] + _M_val /= __r._M_val; + else if (_M_msb && __r._M_msb) + { + _M_val = (_M_val >= __r._M_val); + _M_msb = 0; + } + else if (!_M_msb && __r._M_msb) + _M_val = 0; + else if (_M_msb && !__r._M_msb) + { + // The non-trivial case: the dividend has its MSB set and the + // divisor doesn't. In this case we compute ((LHS/2)/RHS)*2 + // in the base precision. This quantity is either the true + // quotient or one less than the true quotient. + const auto __orig = *this; + *this >>= 1; + _M_val /= __r._M_val; + *this <<= 1; + if (__orig - *this * __r >= __r) + ++_M_val; + } + return *this; + } + + constexpr __max_size_type& + operator%=(const __max_size_type& __r) noexcept + { + if (!_M_msb && !__r._M_msb) [[likely]] + _M_val %= __r._M_val; + else + *this -= (*this / __r) * __r; + return *this; + } + + constexpr __max_size_type& + operator<<=(const __max_size_type& __r) noexcept + { + __glibcxx_assert(__r <= _S_rep_bits); + if (__r != 0) + { + _M_msb = (_M_val >> (_S_rep_bits - __r._M_val)) & 1; + + if (__r._M_val == _S_rep_bits) [[unlikely]] + _M_val = 0; + else + _M_val <<= __r._M_val; + } + return *this; + } + + constexpr __max_size_type& + operator>>=(const __max_size_type& __r) noexcept + { + __glibcxx_assert(__r <= _S_rep_bits); + if (__r != 0) + { + if (__r._M_val == _S_rep_bits) [[unlikely]] + _M_val = 0; + else + _M_val >>= __r._M_val; + + if (_M_msb) [[unlikely]] + { + _M_val |= __rep(1) << (_S_rep_bits - __r._M_val); + _M_msb = 0; + } + } + return *this; + } + + constexpr __max_size_type& + operator&=(const __max_size_type& __r) noexcept + { + _M_val &= __r._M_val; + _M_msb &= __r._M_msb; + return *this; + } + + constexpr __max_size_type& + operator|=(const __max_size_type& __r) noexcept + { + _M_val |= __r._M_val; + _M_msb |= __r._M_msb; + return *this; + } + + constexpr __max_size_type& + operator^=(const __max_size_type& __r) noexcept + { + _M_val ^= __r._M_val; + _M_msb ^= __r._M_msb; + return *this; + } + + template<typename _Tp> requires integral<_Tp> || __is_int128<_Tp> + friend constexpr _Tp& + operator+=(_Tp& a, const __max_size_type& b) noexcept + { return (a = static_cast<_Tp>(a + b)); } + + template<typename _Tp> requires integral<_Tp> || __is_int128<_Tp> + friend constexpr _Tp& + operator-=(_Tp& a, const __max_size_type& b) noexcept + { return (a = static_cast<_Tp>(a - b)); } + + template<typename _Tp> requires integral<_Tp> || __is_int128<_Tp> + friend constexpr _Tp& + operator*=(_Tp& a, const __max_size_type& b) noexcept + { return (a = static_cast<_Tp>(a * b)); } + + template<typename _Tp> requires integral<_Tp> || __is_int128<_Tp> + friend constexpr _Tp& + operator/=(_Tp& a, const __max_size_type& b) noexcept + { return (a = static_cast<_Tp>(a / b)); } + + template<typename _Tp> requires integral<_Tp> || __is_int128<_Tp> + friend constexpr _Tp& + operator%=(_Tp& a, const __max_size_type& b) noexcept + { return (a = static_cast<_Tp>(a % b)); } + + template<typename _Tp> requires integral<_Tp> || __is_int128<_Tp> + friend constexpr _Tp& + operator&=(_Tp& a, const __max_size_type& b) noexcept + { return (a = static_cast<_Tp>(a & b)); } + + template<typename _Tp> requires integral<_Tp> || __is_int128<_Tp> + friend constexpr _Tp& + operator|=(_Tp& a, const __max_size_type& b) noexcept + { return (a = static_cast<_Tp>(a | b)); } + + template<typename _Tp> requires integral<_Tp> || __is_int128<_Tp> + friend constexpr _Tp& + operator^=(_Tp& a, const __max_size_type& b) noexcept + { return (a = static_cast<_Tp>(a ^ b)); } + + template<typename _Tp> requires integral<_Tp> || __is_int128<_Tp> + friend constexpr _Tp& + operator<<=(_Tp& a, const __max_size_type& b) noexcept + { return (a = static_cast<_Tp>(a << b)); } + + template<typename _Tp> requires integral<_Tp> || __is_int128<_Tp> + friend constexpr _Tp& + operator>>=(_Tp& a, const __max_size_type& b) noexcept + { return (a = static_cast<_Tp>(a >> b)); } + + friend constexpr __max_size_type + operator+(__max_size_type __l, const __max_size_type& __r) noexcept + { + __l += __r; + return __l; + } + + friend constexpr __max_size_type + operator-(__max_size_type __l, const __max_size_type& __r) noexcept + { + __l -= __r; + return __l; + } + + friend constexpr __max_size_type + operator*(__max_size_type __l, const __max_size_type& __r) noexcept + { + __l *= __r; + return __l; + } + + friend constexpr __max_size_type + operator/(__max_size_type __l, const __max_size_type& __r) noexcept + { + __l /= __r; + return __l; + } + + friend constexpr __max_size_type + operator%(__max_size_type __l, const __max_size_type& __r) noexcept + { + __l %= __r; + return __l; + } + + friend constexpr __max_size_type + operator<<(__max_size_type __l, const __max_size_type& __r) noexcept + { + __l <<= __r; + return __l; + } + + friend constexpr __max_size_type + operator>>(__max_size_type __l, const __max_size_type& __r) noexcept + { + __l >>= __r; + return __l; + } + + friend constexpr __max_size_type + operator&(__max_size_type __l, const __max_size_type& __r) noexcept + { + __l &= __r; + return __l; + } + + friend constexpr __max_size_type + operator|(__max_size_type __l, const __max_size_type& __r) noexcept + { + __l |= __r; + return __l; + } + + friend constexpr __max_size_type + operator^(__max_size_type __l, const __max_size_type& __r) noexcept + { + __l ^= __r; + return __l; + } + + friend constexpr bool + operator==(const __max_size_type& __l, const __max_size_type& __r) noexcept + { return __l._M_val == __r._M_val && __l._M_msb == __r._M_msb; } + + friend constexpr bool + operator!=(const __max_size_type& __l, const __max_size_type& __r) noexcept + { return !(__l == __r); } + + friend constexpr bool + operator<(const __max_size_type& __l, const __max_size_type& __r) noexcept + { + if (__l._M_msb == __r._M_msb) + return __l._M_val < __r._M_val; + else + return __r._M_msb; + } + + friend constexpr bool + operator>(const __max_size_type& __l, const __max_size_type& __r) noexcept + { return __r < __l; } + + friend constexpr bool + operator<=(const __max_size_type& __l, const __max_size_type& __r) noexcept + { return !(__l > __r); } + + friend constexpr bool + operator>=(const __max_size_type& __l, const __max_size_type& __r) noexcept + { return __r <= __l; } + +#if __SIZEOF_INT128__ + using __rep = unsigned __int128; +#else + using __rep = unsigned long long; +#endif + static constexpr size_t _S_rep_bits = sizeof(__rep) * __CHAR_BIT__; + private: + __rep _M_val = 0; + unsigned _M_msb:1 = 0; + + constexpr explicit + __max_size_type(__rep __val, int __msb) noexcept + : _M_val(__val), _M_msb(__msb) + { } + + friend __max_diff_type; + friend std::numeric_limits<__max_size_type>; + friend std::numeric_limits<__max_diff_type>; + }; + + class __max_diff_type + { + public: + __max_diff_type() = default; + + template<typename _Tp> requires integral<_Tp> || __is_int128<_Tp> + constexpr + __max_diff_type(_Tp __i) noexcept + : _M_rep(__i) + { } + + constexpr explicit + __max_diff_type(const __max_size_type& __d) noexcept + : _M_rep(__d) + { } + + template<typename _Tp> requires integral<_Tp> || __is_int128<_Tp> + constexpr explicit operator _Tp() const noexcept + { return static_cast<_Tp>(_M_rep); } + + constexpr explicit + operator bool() const noexcept + { return _M_rep != 0; } + + constexpr __max_diff_type + operator+() const noexcept + { return *this; } + + constexpr __max_diff_type + operator-() const noexcept + { return __max_diff_type(-_M_rep); } + + constexpr __max_diff_type + operator~() const noexcept + { return __max_diff_type(~_M_rep); } + + constexpr __max_diff_type& + operator+=(const __max_diff_type& __r) noexcept + { + _M_rep += __r._M_rep; + return *this; + } + + constexpr __max_diff_type& + operator-=(const __max_diff_type& __r) noexcept + { + _M_rep -= __r._M_rep; + return *this; + } + + constexpr __max_diff_type& + operator*=(const __max_diff_type& __r) noexcept + { + _M_rep *= __r._M_rep; + return *this; + } + + constexpr __max_diff_type& + operator/=(const __max_diff_type& __r) noexcept + { + __glibcxx_assert (__r != 0); + const bool __neg = *this < 0; + const bool __rneg = __r < 0; + if (!__neg && !__rneg) + _M_rep = _M_rep / __r._M_rep; + else if (__neg && __rneg) + _M_rep = -_M_rep / -__r._M_rep; + else if (__neg && !__rneg) + _M_rep = -(-_M_rep / __r._M_rep); + else + _M_rep = -(_M_rep / -__r._M_rep); + return *this ; + } + + constexpr __max_diff_type& + operator%=(const __max_diff_type& __r) noexcept + { + __glibcxx_assert (__r != 0); + if (*this >= 0 && __r > 0) + _M_rep %= __r._M_rep; + else + *this -= (*this / __r) * __r; + return *this; + } + + constexpr __max_diff_type& + operator<<=(const __max_diff_type& __r) noexcept + { + _M_rep.operator<<=(__r._M_rep); + return *this; + } + + constexpr __max_diff_type& + operator>>=(const __max_diff_type& __r) noexcept + { + // Arithmetic right shift. + const auto __msb = _M_rep._M_msb; + _M_rep >>= __r._M_rep; + _M_rep._M_msb |= __msb; + return *this; + } + + constexpr __max_diff_type& + operator&=(const __max_diff_type& __r) noexcept + { + _M_rep &= __r._M_rep; + return *this; + } + + constexpr __max_diff_type& + operator|=(const __max_diff_type& __r) noexcept + { + _M_rep |= __r._M_rep; + return *this; + } + + constexpr __max_diff_type& + operator^=(const __max_diff_type& __r) noexcept + { + _M_rep ^= __r._M_rep; + return *this; + } + + template<typename _Tp> requires integral<_Tp> || __is_int128<_Tp> + friend constexpr _Tp& + operator+=(_Tp& a, const __max_diff_type& b) noexcept + { return (a = static_cast<_Tp>(a + b)); } + + template<typename _Tp> requires integral<_Tp> || __is_int128<_Tp> + friend constexpr _Tp& + operator-=(_Tp& a, const __max_diff_type& b) noexcept + { return (a = static_cast<_Tp>(a - b)); } + + template<typename _Tp> requires integral<_Tp> || __is_int128<_Tp> + friend constexpr _Tp& + operator*=(_Tp& a, const __max_diff_type& b) noexcept + { return (a = static_cast<_Tp>(a * b)); } + + template<typename _Tp> requires integral<_Tp> || __is_int128<_Tp> + friend constexpr _Tp& + operator/=(_Tp& a, const __max_diff_type& b) noexcept + { return (a = static_cast<_Tp>(a / b)); } + + template<typename _Tp> requires integral<_Tp> || __is_int128<_Tp> + friend constexpr _Tp& + operator%=(_Tp& a, const __max_diff_type& b) noexcept + { return (a = static_cast<_Tp>(a % b)); } + + template<typename _Tp> requires integral<_Tp> || __is_int128<_Tp> + friend constexpr _Tp& + operator&=(_Tp& a, const __max_diff_type& b) noexcept + { return (a = static_cast<_Tp>(a & b)); } + + template<typename _Tp> requires integral<_Tp> || __is_int128<_Tp> + friend constexpr _Tp& + operator|=(_Tp& a, const __max_diff_type& b) noexcept + { return (a = static_cast<_Tp>(a | b)); } + + template<typename _Tp> requires integral<_Tp> || __is_int128<_Tp> + friend constexpr _Tp& + operator^=(_Tp& a, const __max_diff_type& b) noexcept + { return (a = static_cast<_Tp>(a ^ b)); } + + template<typename _Tp> requires integral<_Tp> || __is_int128<_Tp> + friend constexpr _Tp& + operator<<=(_Tp& a, const __max_diff_type& b) noexcept + { return (a = static_cast<_Tp>(a << b)); } + + template<typename _Tp> requires integral<_Tp> || __is_int128<_Tp> + friend constexpr _Tp& + operator>>=(_Tp& a, const __max_diff_type& b) noexcept + { return (a = static_cast<_Tp>(a >> b)); } + + friend constexpr __max_diff_type + operator+(__max_diff_type __l, const __max_diff_type& __r) noexcept + { + __l += __r; + return __l; + } + + friend constexpr __max_diff_type + operator-(__max_diff_type __l, const __max_diff_type& __r) noexcept + { + __l -= __r; + return __l; + } + + friend constexpr __max_diff_type + operator*(__max_diff_type __l, const __max_diff_type& __r) noexcept + { + __l *= __r; + return __l; + } + + friend constexpr __max_diff_type + operator/(__max_diff_type __l, const __max_diff_type& __r) noexcept + { + __l /= __r; + return __l; + } + + friend constexpr __max_diff_type + operator%(__max_diff_type __l, const __max_diff_type& __r) noexcept + { + __l %= __r; + return __l; + } + + friend constexpr __max_diff_type + operator<<(__max_diff_type __l, const __max_diff_type& __r) noexcept + { + __l <<= __r; + return __l; + } + + friend constexpr __max_diff_type + operator>>(__max_diff_type __l, const __max_diff_type& __r) noexcept + { + __l >>= __r; + return __l; + } + + friend constexpr __max_diff_type + operator&(__max_diff_type __l, const __max_diff_type& __r) noexcept + { + __l &= __r; + return __l; + } + + friend constexpr __max_diff_type + operator|(__max_diff_type __l, const __max_diff_type& __r) noexcept + { + __l |= __r; + return __l; + } + + friend constexpr __max_diff_type + operator^(__max_diff_type __l, const __max_diff_type& __r) noexcept + { + __l ^= __r; + return __l; + } + + friend constexpr bool + operator==(const __max_diff_type& __l, const __max_diff_type& __r) noexcept + { return __l._M_rep == __r._M_rep; } + + friend constexpr bool + operator!=(const __max_diff_type& __l, const __max_diff_type& __r) noexcept + { return !(__l == __r); } + + constexpr bool + operator<(const __max_diff_type& __r) const noexcept + { + const auto __lsign = _M_rep._M_msb; + const auto __rsign = __r._M_rep._M_msb; + if (__lsign ^ __rsign) + return __lsign; + else + return _M_rep < __r._M_rep; + } + + friend constexpr bool + operator>(const __max_diff_type& __l, const __max_diff_type& __r) noexcept + { return __r < __l; } + + friend constexpr bool + operator<=(const __max_diff_type& __l, const __max_diff_type& __r) noexcept + { return !(__r < __l); } + + friend constexpr bool + operator>=(const __max_diff_type& __l, const __max_diff_type& __r) noexcept + { return !(__l < __r); } + + private: + __max_size_type _M_rep = 0; + + friend class __max_size_type; + }; + + constexpr + __max_size_type::__max_size_type(const __max_diff_type& __d) noexcept + : __max_size_type(__d._M_rep) + { } + + } // namespace __detail +} // namespace ranges + + template<> + struct numeric_limits<ranges::__detail::__max_size_type> + { + using _Sp = ranges::__detail::__max_size_type; + static constexpr bool is_specialized = true; + static constexpr bool is_signed = false; + static constexpr bool is_integer = true; + static constexpr bool is_exact = true; +#if __SIZEOF_INT128__ + static_assert(same_as<_Sp::__rep, unsigned __int128>); + static constexpr int digits = 129; +#else + static_assert(same_as<_Sp::__rep, unsigned long long>); + static constexpr int digits + = __detail::__int_limits<unsigned long long>::digits + 1; +#endif + static constexpr int digits10 + = static_cast<int>(digits * numbers::ln2 / numbers::ln10); + + static constexpr _Sp + min() noexcept + { return 0; } + + static constexpr _Sp + max() noexcept + { return _Sp(static_cast<_Sp::__rep>(-1), 1); } + + static constexpr _Sp + lowest() noexcept + { return min(); } + }; + + template<> + struct numeric_limits<ranges::__detail::__max_diff_type> + { + using _Dp = ranges::__detail::__max_diff_type; + using _Sp = ranges::__detail::__max_size_type; + static constexpr bool is_specialized = true; + static constexpr bool is_signed = true; + static constexpr bool is_integer = true; + static constexpr bool is_exact = true; + static constexpr int digits = numeric_limits<_Sp>::digits - 1; + static constexpr int digits10 + = static_cast<int>(digits * numbers::ln2 / numbers::ln10); + + static constexpr _Dp + min() noexcept + { return _Dp(_Sp(0, 1)); } + + static constexpr _Dp + max() noexcept + { return _Dp(_Sp(static_cast<_Sp::__rep>(-1), 0)); } + + static constexpr _Dp + lowest() noexcept + { return min(); } + }; + +_GLIBCXX_END_NAMESPACE_VERSION +} // namespace + +#endif // C++20 && library concepts +#endif // _GLIBCXX_MAX_SIZE_TYPE_H diff --git a/libstdc++-v3/include/bits/range_access.h b/libstdc++-v3/include/bits/range_access.h index 82d9e2180c5..bd37ac42fbb 100644 --- a/libstdc++-v3/include/bits/range_access.h +++ b/libstdc++-v3/include/bits/range_access.h @@ -36,6 +36,9 @@ #include <initializer_list> #include <bits/iterator_concepts.h> #include <bits/int_limits.h> +#if __cplusplus > 201703L +#include <bits/max_size_type.h> +#endif namespace std _GLIBCXX_VISIBILITY(default) { @@ -352,6 +355,14 @@ namespace ranges namespace __detail { + constexpr __max_size_type + __to_unsigned_like(__max_size_type __t) noexcept + { return __t; } + + constexpr __max_size_type + __to_unsigned_like(__max_diff_type __t) noexcept + { return __max_size_type(__t); } + template<integral _Tp> constexpr make_unsigned_t<_Tp> __to_unsigned_like(_Tp __t) noexcept diff --git a/libstdc++-v3/testsuite/std/ranges/iota/difference_type.cc b/libstdc++-v3/testsuite/std/ranges/iota/difference_type.cc new file mode 100644 index 00000000000..4a342deae74 --- /dev/null +++ b/libstdc++-v3/testsuite/std/ranges/iota/difference_type.cc @@ -0,0 +1,57 @@ +// Copyright (C) 2020 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 +// <http://www.gnu.org/licenses/>. + +// { dg-options "-std=gnu++2a" } +// { dg-do run { target c++2a } } + +#include <ranges> +#include <testsuite_hooks.h> + +void +test01() +{ + using I = unsigned long long; + auto imax = std::numeric_limits<I>::max(); + std::ranges::iota_view<I, I> i(0, imax); + auto begin = i.begin(); + static_assert( std::input_or_output_iterator<decltype(begin)> ); + auto size = std::ranges::end(i) - std::ranges::begin(i); + VERIFY( size > 0 ); + VERIFY( size == imax ); +} + +void +test02() +{ +#if __SIZEOF_INT128__ + using I = unsigned __int128; + auto imax = std::numeric_limits<I>::max(); + std::ranges::iota_view<I, I> i(0, imax); + auto begin = i.begin(); + static_assert( std::input_or_output_iterator<decltype(begin)> ); + auto size = std::ranges::end(i) - std::ranges::begin(i); + VERIFY( size > 0 ); + VERIFY( size == imax ); +#endif +} + +int +main() +{ + test01(); + test02(); +} diff --git a/libstdc++-v3/testsuite/std/ranges/iota/max_size_type.cc b/libstdc++-v3/testsuite/std/ranges/iota/max_size_type.cc new file mode 100644 index 00000000000..cb9444074fc --- /dev/null +++ b/libstdc++-v3/testsuite/std/ranges/iota/max_size_type.cc @@ -0,0 +1,376 @@ +// Copyright (C) 2020 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 +// <http://www.gnu.org/licenses/>. + +// { dg-options "-std=gnu++2a" } +// { dg-do run { target c++2a } } + +#include <limits> +#include <ranges> +#include <testsuite_hooks.h> + +using max_size_t = std::ranges::__detail::__max_size_type; +using max_diff_t = std::ranges::__detail::__max_diff_type; +using rep_t = max_size_t::__rep; + +static_assert(sizeof(max_size_t) == sizeof(max_diff_t)); + +static_assert(std::regular<max_size_t>); +static_assert(std::totally_ordered<max_size_t>); + +static_assert(std::regular<max_diff_t>); +static_assert(std::totally_ordered<max_diff_t>); + +// We can't use numeric_limits<rep_t>::max() here because __int128 is an +// integral type only in GNU mode. +constexpr max_size_t mu = max_size_t(~rep_t(0)); +constexpr max_size_t ou = 1; +constexpr max_diff_t ns = -1; + +void +test01() +{ + static_assert(max_size_t(7) % 3 == 1); + static_assert(max_size_t(7) % 4 == 3); + + static_assert(-max_diff_t(1) == max_diff_t(-1)); + static_assert(max_diff_t(3) % 2 == 1); + static_assert(max_diff_t(-3) / 2 == -1); + static_assert(max_diff_t(-3) % 2 == -1); + static_assert(max_diff_t(3) % -2 == 1); + static_assert(max_diff_t(-3) << 1 == -6); + static_assert(max_diff_t(-3) >> 1 == -2); + static_assert(max_diff_t(3) >> 1 == 1); + static_assert(max_diff_t(3) >> 2 == 0); + + static_assert(max_diff_t(-5) / 3 == -1); + static_assert(max_diff_t(5) / -3 == -1); + static_assert(max_diff_t(-5) / -3 == 1); + static_assert(max_diff_t(5) / 3 == 1); + + static_assert(max_diff_t(-6) / 3 == -2); + static_assert(max_diff_t(6) / -3 == -2); + static_assert(max_diff_t(-6) / -3 == 2); + static_assert(max_diff_t(6) / 3 == 2); + + static_assert(~max_size_t(-3) == 2); + static_assert(~max_diff_t(-3) == 2); + + static_assert(max_diff_t(1) < max_diff_t(3)); + static_assert(max_diff_t(-1) < max_diff_t(3)); + static_assert(max_diff_t(1) > max_diff_t(-3)); + static_assert(max_diff_t(-1) > max_diff_t(-3)); + + static_assert(max_diff_t(mu)/-1 == -max_diff_t(mu)); + static_assert(-max_diff_t(mu)/1 == -max_diff_t(mu)); + static_assert(max_diff_t(mu)>>1 == max_diff_t(mu)/2); + static_assert(-max_diff_t(mu+1) == max_diff_t(mu+1)); + static_assert(-(mu+1) == mu+1); + static_assert((mu+1)<<1 == 0); + static_assert(max_diff_t(mu+1)<<1 == 0); + static_assert(max_diff_t(mu+1)>>1 < 0); + + static_assert(int(max_diff_t(mu+1)) == 0); + static_assert(rep_t(max_diff_t(mu+1)) == 0); + static_assert(int(max_diff_t(mu)) == -1); + static_assert(rep_t(max_diff_t(mu)) == rep_t(-1)); + + static_assert(2*mu+1 > 2*mu); + static_assert(~(2*mu+1) == 0); + static_assert(mu/mu == 1); + static_assert(2*mu > mu); + static_assert(2*mu-mu == mu); + static_assert((2*mu)/mu == 2); + static_assert((2*mu+1)/mu == 2); + static_assert((2*mu-1)/(mu-1) == 2); + static_assert((2*mu-1)/mu == 1); + static_assert((2*mu+-1)/mu == 1); + static_assert(2*mu-1 < 2*mu); + static_assert(2*mu-1 <= 2*mu); + static_assert(2*mu+1 > 2*mu); + static_assert(2*mu+1 >= 2*mu); + static_assert((2*mu)/1 == 2*mu); + static_assert(mu/mu-1 == 0); + static_assert(mu*0 == 0); + static_assert((2*mu-1)*0 == 0); + static_assert((2*mu-1)>>1 == mu-1); + static_assert(mu+-1+1 == mu); + static_assert(mu+1+-1 == mu); + static_assert(mu+1); + static_assert((2*mu)/2 == mu); + static_assert((2*mu)>>1 == mu); + static_assert((mu<<1)>>1 == mu); + static_assert(1/mu == 0); + static_assert(mu/1 == mu); + static_assert(((mu+1)|mu) == -1); + static_assert((mu+1)+(mu+1) < mu+1); + + static_assert(max_size_t(ns) == -1); + static_assert(-max_diff_t(ou) == -1); + static_assert(-max_diff_t(-ou) == 1); + static_assert(max_size_t(-max_diff_t(-ou)) == 1); + static_assert(ns*ns == max_diff_t(ou)); + static_assert(max_size_t(ns)*max_size_t(ns) == ou); + static_assert(-max_diff_t(0) == max_diff_t(0)); + static_assert(-ou-ou == -2*ou); + + static_assert(int(ns) == -1); + static_assert(rep_t(ns) == rep_t(-1)); + + static_assert(max_size_t() == 0); + static_assert(max_diff_t() == 0); + + auto f = [] (auto a) { a /= a; return a; }; + static_assert(f(max_size_t(5)) == 1); + static_assert(f(max_size_t(-5)) == 1); + static_assert(f(max_diff_t(5)) == 1); + + auto g = [] (auto a) { a >>= a; return a; }; + static_assert(g(max_size_t(5)) == 0); + static_assert(g(max_diff_t(5)) == 0); + + auto h = [] (auto a) { a <<= a; return a; }; + static_assert(h(max_size_t(3)) == 24); + static_assert(h(max_diff_t(3)) == 24); +} + +template<bool signed_p, bool shorten_p> +void +test02() +{ + using hw_type = std::conditional_t<signed_p, signed rep_t, rep_t>; + using max_type = std::conditional_t<signed_p, max_diff_t, max_size_t>; + using shorten_type = std::conditional_t<shorten_p, hw_type, max_type>; + const int hw_type_bit_size = sizeof(hw_type) * __CHAR_BIT__; + const int limit = 1000; + const int log2_limit = 10; + static_assert((1 << log2_limit) >= limit); + const int min = (signed_p ? -limit : 0); + const int max = limit; + for (hw_type i = min; i <= max; i++) + { + bool ok = true; + if (signed_p || shorten_p) + { + ok &= (~i == shorten_type(~max_type(i))); + ok &= (-i == shorten_type(-max_type(i))); + } + for (hw_type j = min; j <= max; j++) + { + ok &= (i*j == shorten_type(max_type(i)*j)); + ok &= (i+j == shorten_type(max_type(i)+j)); + if (j != 0) + { + ok &= (i/j == shorten_type(max_type(i)/j)); + ok &= (i%j == shorten_type(max_type(i)%j)); + } + if (signed_p || shorten_p) + ok &= (i-j == shorten_type(max_type(i)-j)); + ok &= ((i&j) == shorten_type(max_type(i)&j)); + ok &= ((i|j) == shorten_type(max_type(i)|j)); + ok &= ((i^j) == shorten_type(max_type(i)^j)); + if (j >= 0 && j < hw_type(hw_type_bit_size) + && (shorten_p || j < hw_type(hw_type_bit_size) - log2_limit)) + { + ok &= ((i>>j) == shorten_type(max_type(i)>>j)); + ok &= ((i<<j) == shorten_type(max_type(i)<<j)); + } + ok &= (i>j) == (max_type(i) > j); + ok &= (i<j) == (max_type(i) < j); + ok &= (i>=j) == (max_type(i) >= j); + ok &= (i<=j) == (max_type(i) <= j); + ok &= (i==j) == (max_type(i) == j); + ok &= (i!=j) == (max_type(i) != j); + if (!ok) + { + fprintf(stderr, + "Inconsistency found: %d %d %lld %lld\n", + signed_p, shorten_p, (long long)i, (long long)j) ; + VERIFY(0); + } + } + } +} + +template<bool signed_p, bool toggle_base_p> +void +test03() +{ + using hw_type = std::conditional_t<signed_p, signed rep_t, rep_t>; + using max_type = std::conditional_t<signed_p, max_diff_t, max_size_t>; + using base_type = std::conditional_t<toggle_base_p, hw_type, max_type>; + constexpr int hw_type_bit_size = sizeof(hw_type) * __CHAR_BIT__; + constexpr int limit = 1000; + constexpr int log2_limit = 10; + static_assert((1 << log2_limit) >= limit); + const int min = (signed_p ? -limit : 0); + const int max = limit; + for (hw_type i = min; i <= max; i++) + { + bool ok = true; + base_type k; + for (hw_type j = min; j <= max; j++) + { + k = i; k *= j; + ok &= (k == (max_type(i)*j)); + k = i; k += j; + ok &= (k == (max_type(i)+j)); + if (j != 0) + { + k = i; k /= j; + ok &= (k == (max_type(i)/j)); + k = i; k %= j; + ok &= (k == (max_type(i)%j)); + } + if (signed_p) + { + k = i; k -= j; + ok &= (k == (max_type(i)-j)); + } + k = i; k &= j; + ok &= (k == (max_type(i)&j)); + k = i; k |= j; + ok &= (k == (max_type(i)|j)); + k = i; k ^= j; + ok &= (k == (max_type(i)^j)); + if (j >= 0 && j < hw_type(hw_type_bit_size) + && (!toggle_base_p || j < hw_type(hw_type_bit_size) - log2_limit)) + { + k = i; k >>= j; + ok &= (k == (max_type(i)>>j)); + k = i; k <<= j; + ok &= (k == (max_type(i)<<j)); + } + if (!ok) + { + fprintf(stderr, + "Inconsistency found: %d %d %lld %lld\n", + signed_p, toggle_base_p, (long long)i, (long long)j) ; + VERIFY(0); + } + } + } +} + +void +test04() +{ + constexpr int limit = 1000; + for (int i = -limit; i <= limit; i++) + { + VERIFY( -max_size_t(-i) == i ); + for (int j = i; j <= limit; j++) + { + VERIFY( max_size_t(-i) * max_size_t(-j) == i*j ); + VERIFY( max_size_t(-j) * max_size_t(-i) == j*i ); + VERIFY( rep_t(((mu+1)+i)*((mu+1)+j)) == rep_t(i*j) ); + VERIFY( rep_t(((mu+1)+j)*((mu+1)+i)) == rep_t(j*i) ); + if (i >= 0 && j > 0) + { + auto r = (mu+i)-((mu+i)/j)*j; + VERIFY( r >= 0 && r < j ); + VERIFY( r == (mu+i)%j ); + } + } + } +} + +void +test05() +{ +#if __SIZEOF_INT128__ + max_size_t x = 0; + x = static_cast<__int128>(0); + x = static_cast<unsigned __int128>(0); + + max_diff_t y = 0; + y = static_cast<__int128>(0);; + y = static_cast<unsigned __int128>(0); +#endif +} + +using std::numeric_limits; + +static_assert(numeric_limits<max_size_t>::is_specialized); +static_assert(!numeric_limits<max_size_t>::is_signed); +static_assert(numeric_limits<max_size_t>::is_integer); +static_assert(numeric_limits<max_size_t>::is_exact); +// We can't unconditionally use numeric_limits here because __int128 is an +// integral type only in GNU mode. +#if __SIZEOF_INT128__ +static_assert(numeric_limits<max_size_t>::digits == 129); +static_assert(numeric_limits<max_size_t>::digits10 == 38); +static_assert(numeric_limits<max_size_t>::max() + == 2*max_size_t(~rep_t(0)) + 1); +#else +static_assert(numeric_limits<max_size_t>::digits + == numeric_limits<rep_t>::digits + 1); +static_assert(numeric_limits<max_size_t>::digits10 + == numeric_limits<rep_t>::digits10); +static_assert(numeric_limits<max_size_t>::max() + == 2*max_size_t(numeric_limits<rep_t>::max())+1); +#endif +static_assert(numeric_limits<max_size_t>::min() == 0); +static_assert(numeric_limits<max_size_t>::max() + == max_size_t(-1)); +static_assert((numeric_limits<max_size_t>::max() + >> (numeric_limits<max_size_t>::digits-1)) == 1); +static_assert(numeric_limits<max_size_t>::lowest() + == numeric_limits<max_size_t>::min()); + +static_assert(numeric_limits<max_diff_t>::is_specialized); +static_assert(numeric_limits<max_diff_t>::is_signed); +static_assert(numeric_limits<max_diff_t>::is_integer); +static_assert(numeric_limits<max_diff_t>::is_exact); +static_assert(numeric_limits<max_diff_t>::digits + == numeric_limits<max_size_t>::digits - 1); +static_assert(numeric_limits<max_diff_t>::digits10 + == numeric_limits<max_size_t>::digits10); +// We can't unconditionally use numeric_limits here because __int128 is an +// integral type only in GNU mode. +#if __SIZEOF_INT128__ +static_assert(numeric_limits<max_diff_t>::min() == -max_diff_t(~rep_t(0))-1); +static_assert(numeric_limits<max_diff_t>::max() == ~rep_t(0)); +#else +static_assert(numeric_limits<max_diff_t>::min() + == -max_diff_t(numeric_limits<rep_t>::max())-1); +static_assert(numeric_limits<max_diff_t>::max() + == numeric_limits<rep_t>::max()); +#endif +static_assert(numeric_limits<max_diff_t>::lowest() + == numeric_limits<max_diff_t>::min()); +static_assert(max_diff_t(max_size_t(1) + << (numeric_limits<max_size_t>::digits-1)) + == numeric_limits<max_diff_t>::min()); + +int +main() +{ + test01(); + + test02<false,false>(); + test02<false,true>(); + test02<true,false>(); + test02<true,true>(); + + test03<false,false>(); + test03<false,true>(); + test03<true,false>(); + test03<true,true>(); + + test04(); + test05(); +}
On Thu, 7 May 2020, Patrick Palka wrote: > On Mon, 2 Mar 2020, Patrick Palka wrote: > > > On Mon, 24 Feb 2020, Patrick Palka wrote: > > > > > On Mon, 24 Feb 2020, Patrick Palka wrote: > > > > > > > This implements signed and unsigned integer-class types, whose width is one bit > > > > larger than the widest native signed and unsigned integral type respectively. > > > > In our case this is either __int128 and unsigned __int128, or long long and > > > > unsigned long long. > > > > > > > > Internally, the two integer-class types are represented as a largest native > > > > unsigned integral type plus one extra bit. The signed integer-class type is > > > > represented in two's complement form with the extra bit acting as the sign bit. > > > > > > > > libstdc++-v3/ChangeLog: > > > > > > > > * include/bits/iterator_concepts.h (ranges::__detail::__max_diff_type): > > > > Remove definition, replace with forward declaration of class > > > > __max_diff_type. > > > > (ranges::__detail::__max_size_type): Remove definition, replace with > > > > forward declaration of class __max_size_type. > > > > (__detail::__is_integer_like): Accept __int128 and unsigned __int128. > > > > (__detail::__is_signed_integer_like): Accept __int128. > > > > * include/bits/range_access.h (__detail::__max_size_type): New class. > > > > (__detail::__max_diff_type): New class. > > > > (__detail::__max_size_type::__max_size_type): Define this constructor > > > > out-of-line to break the cycle. > > > > (__detail::__to_unsigned_like): New function. > > > > (numeric_limits<__detail::__max_size_type>): New explicit specialization. > > > > (numeric_limits<__detail::__max_diff_type>): New explicit specialization. > > > > * testsuite/std/ranges/iota/differenc_type.cc: New test. > > > > > > Here's v2 of the patch that splits out __max_size_type and > > > __max_diff_type into a dedicated header, along with other misc > > > improvements and fixes. > > > > > > -- >8 -- > > > > Here's v3 of the patch. Changes from v2: > > > > * The arithmetic tests in difference_type.cc have been split out to a > > separate file. > > > > * The arithmetic tests now run successfully in strict ANSI mode. The > > issue was that __int128 does not model the integral concept in strict > > ANSI mode, which we use to make operations on this type behave as > > integer operations do. But for that we need to always treat __int128 as > > an integer type in this API. So a new concept __integralish which is > > always modelled by __int128 is introduced and used in the API instead. > > > > * Comments have been added explaining why __int128 is always used as the > > underlying type even when the widest integer type in strict ANSI mode is > > long long. > > > > * New tests, some minor code clean-ups, and added comments to the > > unsigned division and multiplication routines. > > > > Tested on x86_64-pc-linux-gnu in both strict and GNU compilation modes, > > with and without -U__SIZEOF_INT128__. > > Ping (now that stage 1 is open). Here's the latest rebased of version > of the patch: Here's the patch rebased against today's trunk. Compared to the previous version, this version resolves some trivial merge conflicts in include/bits/{iterator_concepts.h,range_access.h} and it replaces the use of the removed trait __detail::__int_limits<unsigned long long>::digits with __gnu_cxx::__int_traits<unsigned long long>::__digits. Tested with and without -U__SIZEOF_INT128__, and in both strict and GNU c++20 modes. -- >8 -- Subject: [PATCH] libstdc++: integer-class types as per [iterator.concept.winc] This implements signed and unsigned integer-class types, whose width is one bit larger than the widest supported signed and unsigned integral type respectively. In our case this is either __int128 and unsigned __int128, or long long and unsigned long long. Internally, the two integer-class types are represented as a largest supported unsigned integral type plus one extra bit. The signed integer-class type is represented in two's complement form with the extra bit acting as the sign bit. libstdc++-v3/ChangeLog: * include/Makefile.am (bits_headers): Add new header <bits/max_size_type.h>. * include/Makefile.in: Regenerate. * include/bits/iterator_concepts.h (ranges::__detail::__max_diff_type): Remove definition, replace with forward declaration of class __max_diff_type. (__detail::__max_size_type): Remove definition, replace with forward declaration of class __max_size_type. (__detail::__is_unsigned_int128, __is_signed_int128, __is_int128): New concepts. (__detail::__is_integer_like): Accept __int128 and unsigned __int128. (__detail::__is_signed_integer_like): Accept __int128. * include/bits/max_size_type.h: New header. * include/bits/range_access.h: Include <bits/max_size_type.h>. (__detail::__to_unsigned_like): Two new overloads. * testsuite/std/ranges/iota/difference_type.cc: New test. * testsuite/std/ranges/iota/max_size_type.cc: New test. --- libstdc++-v3/include/Makefile.am | 1 + libstdc++-v3/include/Makefile.in | 1 + libstdc++-v3/include/bits/iterator_concepts.h | 24 +- libstdc++-v3/include/bits/max_size_type.h | 753 ++++++++++++++++++ libstdc++-v3/include/bits/range_access.h | 11 + .../std/ranges/iota/difference_type.cc | 57 ++ .../std/ranges/iota/max_size_type.cc | 376 +++++++++ 7 files changed, 1219 insertions(+), 4 deletions(-) create mode 100644 libstdc++-v3/include/bits/max_size_type.h create mode 100644 libstdc++-v3/testsuite/std/ranges/iota/difference_type.cc create mode 100644 libstdc++-v3/testsuite/std/ranges/iota/max_size_type.cc diff --git a/libstdc++-v3/include/Makefile.am b/libstdc++-v3/include/Makefile.am index e131ce04f8c..1dff3862e35 100644 --- a/libstdc++-v3/include/Makefile.am +++ b/libstdc++-v3/include/Makefile.am @@ -143,6 +143,7 @@ bits_headers = \ ${bits_srcdir}/locale_facets_nonio.tcc \ ${bits_srcdir}/localefwd.h \ ${bits_srcdir}/mask_array.h \ + ${bits_srcdir}/max_size_type.h \ ${bits_srcdir}/memoryfwd.h \ ${bits_srcdir}/move.h \ ${bits_srcdir}/node_handle.h \ diff --git a/libstdc++-v3/include/Makefile.in b/libstdc++-v3/include/Makefile.in index c0b71e13a32..16371015071 100644 --- a/libstdc++-v3/include/Makefile.in +++ b/libstdc++-v3/include/Makefile.in @@ -489,6 +489,7 @@ bits_headers = \ ${bits_srcdir}/locale_facets_nonio.tcc \ ${bits_srcdir}/localefwd.h \ ${bits_srcdir}/mask_array.h \ + ${bits_srcdir}/max_size_type.h \ ${bits_srcdir}/memoryfwd.h \ ${bits_srcdir}/move.h \ ${bits_srcdir}/node_handle.h \ diff --git a/libstdc++-v3/include/bits/iterator_concepts.h b/libstdc++-v3/include/bits/iterator_concepts.h index aad6c2dcd91..5033f2bddc3 100644 --- a/libstdc++-v3/include/bits/iterator_concepts.h +++ b/libstdc++-v3/include/bits/iterator_concepts.h @@ -511,12 +511,23 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION namespace ranges::__detail { + class __max_diff_type; + class __max_size_type; + + template<typename _Tp> + concept __is_signed_int128 #if __SIZEOF_INT128__ - using __max_diff_type = __int128; - using __max_size_type = unsigned __int128; + = same_as<_Tp, __int128>; #else - using __max_diff_type = long long; - using __max_size_type = unsigned long long; + = false; +#endif + + template<typename _Tp> + concept __is_unsigned_int128 +#if __SIZEOF_INT128__ + = same_as<_Tp, unsigned __int128>; +#else + = false; #endif template<typename _Tp> @@ -525,12 +536,17 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template<typename _Tp> concept __integral_nonbool = integral<_Tp> && !__cv_bool<_Tp>; + template<typename _Tp> + concept __is_int128 = __is_signed_int128<_Tp> || __is_unsigned_int128<_Tp>; + template<typename _Tp> concept __is_integer_like = __integral_nonbool<_Tp> + || __is_int128<_Tp> || same_as<_Tp, __max_diff_type> || same_as<_Tp, __max_size_type>; template<typename _Tp> concept __is_signed_integer_like = signed_integral<_Tp> + || __is_signed_int128<_Tp> || same_as<_Tp, __max_diff_type>; } // namespace ranges::__detail diff --git a/libstdc++-v3/include/bits/max_size_type.h b/libstdc++-v3/include/bits/max_size_type.h new file mode 100644 index 00000000000..951cd6e93a8 --- /dev/null +++ b/libstdc++-v3/include/bits/max_size_type.h @@ -0,0 +1,753 @@ +// <max_size_type.h> -*- C++ -*- + +// Copyright (C) 2019-2020 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. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// <http://www.gnu.org/licenses/>. + +/** @file bits/max_size_type.h. + * This is an internal header file, included by other library headers. + * Do not attempt to use it directly. @headername{iterator} + */ + +#ifndef _GLIBCXX_MAX_SIZE_TYPE_H +#define _GLIBCXX_MAX_SIZE_TYPE_H 1 + +#pragma GCC system_header + +#if __cplusplus > 201703L && __cpp_lib_concepts +#include <ext/numeric_traits.h> +#include <numbers> + +// This header implements unsigned and signed integer-class types (as per +// [iterator.concept.winc]) that are one bit wider than the widest supported +// integer type. +// +// The set of integer types we consider includes __int128 and unsigned __int128 +// (when they exist), even though they are really integer types only in GNU +// mode. This is to obtain a consistent ABI for these integer-class types +// across strict mode and GNU mode. + +namespace std _GLIBCXX_VISIBILITY(default) +{ +_GLIBCXX_BEGIN_NAMESPACE_VERSION + +template<typename _Tp> + struct numeric_limits; + +namespace ranges +{ + namespace __detail + { + class __max_size_type + { + public: + __max_size_type() = default; + + template<typename _Tp> requires integral<_Tp> || __is_int128<_Tp> + constexpr + __max_size_type(_Tp __i) noexcept + : _M_val(__i), _M_msb(__i < 0) + { } + + constexpr explicit + __max_size_type(const __max_diff_type& __d) noexcept; + + template<typename _Tp> requires integral<_Tp> || __is_int128<_Tp> + constexpr explicit operator _Tp() const noexcept + { return _M_val; } + + constexpr explicit + operator bool() const noexcept + { return _M_val != 0 || _M_msb != 0; } + + constexpr __max_size_type + operator+() const noexcept + { return *this; } + + constexpr __max_size_type + operator~() const noexcept + { return __max_size_type{~_M_val, !_M_msb}; } + + constexpr __max_size_type + operator-() const noexcept + { return operator~() + 1; } + + constexpr __max_size_type& + operator+=(const __max_size_type& __r) noexcept + { + const auto __sum = _M_val + __r._M_val; + const bool __overflow = (__sum < _M_val); + _M_msb = _M_msb ^ __r._M_msb ^ __overflow; + _M_val = __sum; + return *this; + } + + constexpr __max_size_type& + operator-=(const __max_size_type& __r) noexcept + { return *this += -__r; } + + constexpr __max_size_type& + operator*=(__max_size_type __r) noexcept + { + constexpr __max_size_type __threshold + = __rep(1) << (_S_rep_bits / 2 - 1); + if (_M_val < __threshold && __r < __threshold) [[likely]] + // When both operands are below this threshold then the + // multiplication can be safely computed in the base precision. + _M_val = _M_val * __r._M_val; + else + { + // Otherwise, perform the multiplication in four steps, by + // decomposing the LHS and the RHS into 2*x+a and 2*y+b, + // respectively, and computing 4*x*y + 2*x*b + 2*y*a + a*b. + const bool __lsb = _M_val & 1; + const bool __rlsb = __r._M_val & 1; + *this >>= 1; + __r >>= 1; + _M_val = (2 * _M_val * __r._M_val + + _M_val * __rlsb + __r._M_val * __lsb); + *this <<= 1; + *this += __rlsb * __lsb; + } + + return *this; + } + + constexpr __max_size_type& + operator/=(const __max_size_type& __r) noexcept + { + __glibcxx_assert(__r != 0); + + if (!_M_msb && !__r._M_msb) [[likely]] + _M_val /= __r._M_val; + else if (_M_msb && __r._M_msb) + { + _M_val = (_M_val >= __r._M_val); + _M_msb = 0; + } + else if (!_M_msb && __r._M_msb) + _M_val = 0; + else if (_M_msb && !__r._M_msb) + { + // The non-trivial case: the dividend has its MSB set and the + // divisor doesn't. In this case we compute ((LHS/2)/RHS)*2 + // in the base precision. This quantity is either the true + // quotient or one less than the true quotient. + const auto __orig = *this; + *this >>= 1; + _M_val /= __r._M_val; + *this <<= 1; + if (__orig - *this * __r >= __r) + ++_M_val; + } + return *this; + } + + constexpr __max_size_type& + operator%=(const __max_size_type& __r) noexcept + { + if (!_M_msb && !__r._M_msb) [[likely]] + _M_val %= __r._M_val; + else + *this -= (*this / __r) * __r; + return *this; + } + + constexpr __max_size_type& + operator<<=(const __max_size_type& __r) noexcept + { + __glibcxx_assert(__r <= _S_rep_bits); + if (__r != 0) + { + _M_msb = (_M_val >> (_S_rep_bits - __r._M_val)) & 1; + + if (__r._M_val == _S_rep_bits) [[unlikely]] + _M_val = 0; + else + _M_val <<= __r._M_val; + } + return *this; + } + + constexpr __max_size_type& + operator>>=(const __max_size_type& __r) noexcept + { + __glibcxx_assert(__r <= _S_rep_bits); + if (__r != 0) + { + if (__r._M_val == _S_rep_bits) [[unlikely]] + _M_val = 0; + else + _M_val >>= __r._M_val; + + if (_M_msb) [[unlikely]] + { + _M_val |= __rep(1) << (_S_rep_bits - __r._M_val); + _M_msb = 0; + } + } + return *this; + } + + constexpr __max_size_type& + operator&=(const __max_size_type& __r) noexcept + { + _M_val &= __r._M_val; + _M_msb &= __r._M_msb; + return *this; + } + + constexpr __max_size_type& + operator|=(const __max_size_type& __r) noexcept + { + _M_val |= __r._M_val; + _M_msb |= __r._M_msb; + return *this; + } + + constexpr __max_size_type& + operator^=(const __max_size_type& __r) noexcept + { + _M_val ^= __r._M_val; + _M_msb ^= __r._M_msb; + return *this; + } + + template<typename _Tp> requires integral<_Tp> || __is_int128<_Tp> + friend constexpr _Tp& + operator+=(_Tp& a, const __max_size_type& b) noexcept + { return (a = static_cast<_Tp>(a + b)); } + + template<typename _Tp> requires integral<_Tp> || __is_int128<_Tp> + friend constexpr _Tp& + operator-=(_Tp& a, const __max_size_type& b) noexcept + { return (a = static_cast<_Tp>(a - b)); } + + template<typename _Tp> requires integral<_Tp> || __is_int128<_Tp> + friend constexpr _Tp& + operator*=(_Tp& a, const __max_size_type& b) noexcept + { return (a = static_cast<_Tp>(a * b)); } + + template<typename _Tp> requires integral<_Tp> || __is_int128<_Tp> + friend constexpr _Tp& + operator/=(_Tp& a, const __max_size_type& b) noexcept + { return (a = static_cast<_Tp>(a / b)); } + + template<typename _Tp> requires integral<_Tp> || __is_int128<_Tp> + friend constexpr _Tp& + operator%=(_Tp& a, const __max_size_type& b) noexcept + { return (a = static_cast<_Tp>(a % b)); } + + template<typename _Tp> requires integral<_Tp> || __is_int128<_Tp> + friend constexpr _Tp& + operator&=(_Tp& a, const __max_size_type& b) noexcept + { return (a = static_cast<_Tp>(a & b)); } + + template<typename _Tp> requires integral<_Tp> || __is_int128<_Tp> + friend constexpr _Tp& + operator|=(_Tp& a, const __max_size_type& b) noexcept + { return (a = static_cast<_Tp>(a | b)); } + + template<typename _Tp> requires integral<_Tp> || __is_int128<_Tp> + friend constexpr _Tp& + operator^=(_Tp& a, const __max_size_type& b) noexcept + { return (a = static_cast<_Tp>(a ^ b)); } + + template<typename _Tp> requires integral<_Tp> || __is_int128<_Tp> + friend constexpr _Tp& + operator<<=(_Tp& a, const __max_size_type& b) noexcept + { return (a = static_cast<_Tp>(a << b)); } + + template<typename _Tp> requires integral<_Tp> || __is_int128<_Tp> + friend constexpr _Tp& + operator>>=(_Tp& a, const __max_size_type& b) noexcept + { return (a = static_cast<_Tp>(a >> b)); } + + friend constexpr __max_size_type + operator+(__max_size_type __l, const __max_size_type& __r) noexcept + { + __l += __r; + return __l; + } + + friend constexpr __max_size_type + operator-(__max_size_type __l, const __max_size_type& __r) noexcept + { + __l -= __r; + return __l; + } + + friend constexpr __max_size_type + operator*(__max_size_type __l, const __max_size_type& __r) noexcept + { + __l *= __r; + return __l; + } + + friend constexpr __max_size_type + operator/(__max_size_type __l, const __max_size_type& __r) noexcept + { + __l /= __r; + return __l; + } + + friend constexpr __max_size_type + operator%(__max_size_type __l, const __max_size_type& __r) noexcept + { + __l %= __r; + return __l; + } + + friend constexpr __max_size_type + operator<<(__max_size_type __l, const __max_size_type& __r) noexcept + { + __l <<= __r; + return __l; + } + + friend constexpr __max_size_type + operator>>(__max_size_type __l, const __max_size_type& __r) noexcept + { + __l >>= __r; + return __l; + } + + friend constexpr __max_size_type + operator&(__max_size_type __l, const __max_size_type& __r) noexcept + { + __l &= __r; + return __l; + } + + friend constexpr __max_size_type + operator|(__max_size_type __l, const __max_size_type& __r) noexcept + { + __l |= __r; + return __l; + } + + friend constexpr __max_size_type + operator^(__max_size_type __l, const __max_size_type& __r) noexcept + { + __l ^= __r; + return __l; + } + + friend constexpr bool + operator==(const __max_size_type& __l, const __max_size_type& __r) noexcept + { return __l._M_val == __r._M_val && __l._M_msb == __r._M_msb; } + + friend constexpr bool + operator!=(const __max_size_type& __l, const __max_size_type& __r) noexcept + { return !(__l == __r); } + + friend constexpr bool + operator<(const __max_size_type& __l, const __max_size_type& __r) noexcept + { + if (__l._M_msb == __r._M_msb) + return __l._M_val < __r._M_val; + else + return __r._M_msb; + } + + friend constexpr bool + operator>(const __max_size_type& __l, const __max_size_type& __r) noexcept + { return __r < __l; } + + friend constexpr bool + operator<=(const __max_size_type& __l, const __max_size_type& __r) noexcept + { return !(__l > __r); } + + friend constexpr bool + operator>=(const __max_size_type& __l, const __max_size_type& __r) noexcept + { return __r <= __l; } + +#if __SIZEOF_INT128__ + using __rep = unsigned __int128; +#else + using __rep = unsigned long long; +#endif + static constexpr size_t _S_rep_bits = sizeof(__rep) * __CHAR_BIT__; + private: + __rep _M_val = 0; + unsigned _M_msb:1 = 0; + + constexpr explicit + __max_size_type(__rep __val, int __msb) noexcept + : _M_val(__val), _M_msb(__msb) + { } + + friend __max_diff_type; + friend std::numeric_limits<__max_size_type>; + friend std::numeric_limits<__max_diff_type>; + }; + + class __max_diff_type + { + public: + __max_diff_type() = default; + + template<typename _Tp> requires integral<_Tp> || __is_int128<_Tp> + constexpr + __max_diff_type(_Tp __i) noexcept + : _M_rep(__i) + { } + + constexpr explicit + __max_diff_type(const __max_size_type& __d) noexcept + : _M_rep(__d) + { } + + template<typename _Tp> requires integral<_Tp> || __is_int128<_Tp> + constexpr explicit operator _Tp() const noexcept + { return static_cast<_Tp>(_M_rep); } + + constexpr explicit + operator bool() const noexcept + { return _M_rep != 0; } + + constexpr __max_diff_type + operator+() const noexcept + { return *this; } + + constexpr __max_diff_type + operator-() const noexcept + { return __max_diff_type(-_M_rep); } + + constexpr __max_diff_type + operator~() const noexcept + { return __max_diff_type(~_M_rep); } + + constexpr __max_diff_type& + operator+=(const __max_diff_type& __r) noexcept + { + _M_rep += __r._M_rep; + return *this; + } + + constexpr __max_diff_type& + operator-=(const __max_diff_type& __r) noexcept + { + _M_rep -= __r._M_rep; + return *this; + } + + constexpr __max_diff_type& + operator*=(const __max_diff_type& __r) noexcept + { + _M_rep *= __r._M_rep; + return *this; + } + + constexpr __max_diff_type& + operator/=(const __max_diff_type& __r) noexcept + { + __glibcxx_assert (__r != 0); + const bool __neg = *this < 0; + const bool __rneg = __r < 0; + if (!__neg && !__rneg) + _M_rep = _M_rep / __r._M_rep; + else if (__neg && __rneg) + _M_rep = -_M_rep / -__r._M_rep; + else if (__neg && !__rneg) + _M_rep = -(-_M_rep / __r._M_rep); + else + _M_rep = -(_M_rep / -__r._M_rep); + return *this ; + } + + constexpr __max_diff_type& + operator%=(const __max_diff_type& __r) noexcept + { + __glibcxx_assert (__r != 0); + if (*this >= 0 && __r > 0) + _M_rep %= __r._M_rep; + else + *this -= (*this / __r) * __r; + return *this; + } + + constexpr __max_diff_type& + operator<<=(const __max_diff_type& __r) noexcept + { + _M_rep.operator<<=(__r._M_rep); + return *this; + } + + constexpr __max_diff_type& + operator>>=(const __max_diff_type& __r) noexcept + { + // Arithmetic right shift. + const auto __msb = _M_rep._M_msb; + _M_rep >>= __r._M_rep; + _M_rep._M_msb |= __msb; + return *this; + } + + constexpr __max_diff_type& + operator&=(const __max_diff_type& __r) noexcept + { + _M_rep &= __r._M_rep; + return *this; + } + + constexpr __max_diff_type& + operator|=(const __max_diff_type& __r) noexcept + { + _M_rep |= __r._M_rep; + return *this; + } + + constexpr __max_diff_type& + operator^=(const __max_diff_type& __r) noexcept + { + _M_rep ^= __r._M_rep; + return *this; + } + + template<typename _Tp> requires integral<_Tp> || __is_int128<_Tp> + friend constexpr _Tp& + operator+=(_Tp& a, const __max_diff_type& b) noexcept + { return (a = static_cast<_Tp>(a + b)); } + + template<typename _Tp> requires integral<_Tp> || __is_int128<_Tp> + friend constexpr _Tp& + operator-=(_Tp& a, const __max_diff_type& b) noexcept + { return (a = static_cast<_Tp>(a - b)); } + + template<typename _Tp> requires integral<_Tp> || __is_int128<_Tp> + friend constexpr _Tp& + operator*=(_Tp& a, const __max_diff_type& b) noexcept + { return (a = static_cast<_Tp>(a * b)); } + + template<typename _Tp> requires integral<_Tp> || __is_int128<_Tp> + friend constexpr _Tp& + operator/=(_Tp& a, const __max_diff_type& b) noexcept + { return (a = static_cast<_Tp>(a / b)); } + + template<typename _Tp> requires integral<_Tp> || __is_int128<_Tp> + friend constexpr _Tp& + operator%=(_Tp& a, const __max_diff_type& b) noexcept + { return (a = static_cast<_Tp>(a % b)); } + + template<typename _Tp> requires integral<_Tp> || __is_int128<_Tp> + friend constexpr _Tp& + operator&=(_Tp& a, const __max_diff_type& b) noexcept + { return (a = static_cast<_Tp>(a & b)); } + + template<typename _Tp> requires integral<_Tp> || __is_int128<_Tp> + friend constexpr _Tp& + operator|=(_Tp& a, const __max_diff_type& b) noexcept + { return (a = static_cast<_Tp>(a | b)); } + + template<typename _Tp> requires integral<_Tp> || __is_int128<_Tp> + friend constexpr _Tp& + operator^=(_Tp& a, const __max_diff_type& b) noexcept + { return (a = static_cast<_Tp>(a ^ b)); } + + template<typename _Tp> requires integral<_Tp> || __is_int128<_Tp> + friend constexpr _Tp& + operator<<=(_Tp& a, const __max_diff_type& b) noexcept + { return (a = static_cast<_Tp>(a << b)); } + + template<typename _Tp> requires integral<_Tp> || __is_int128<_Tp> + friend constexpr _Tp& + operator>>=(_Tp& a, const __max_diff_type& b) noexcept + { return (a = static_cast<_Tp>(a >> b)); } + + friend constexpr __max_diff_type + operator+(__max_diff_type __l, const __max_diff_type& __r) noexcept + { + __l += __r; + return __l; + } + + friend constexpr __max_diff_type + operator-(__max_diff_type __l, const __max_diff_type& __r) noexcept + { + __l -= __r; + return __l; + } + + friend constexpr __max_diff_type + operator*(__max_diff_type __l, const __max_diff_type& __r) noexcept + { + __l *= __r; + return __l; + } + + friend constexpr __max_diff_type + operator/(__max_diff_type __l, const __max_diff_type& __r) noexcept + { + __l /= __r; + return __l; + } + + friend constexpr __max_diff_type + operator%(__max_diff_type __l, const __max_diff_type& __r) noexcept + { + __l %= __r; + return __l; + } + + friend constexpr __max_diff_type + operator<<(__max_diff_type __l, const __max_diff_type& __r) noexcept + { + __l <<= __r; + return __l; + } + + friend constexpr __max_diff_type + operator>>(__max_diff_type __l, const __max_diff_type& __r) noexcept + { + __l >>= __r; + return __l; + } + + friend constexpr __max_diff_type + operator&(__max_diff_type __l, const __max_diff_type& __r) noexcept + { + __l &= __r; + return __l; + } + + friend constexpr __max_diff_type + operator|(__max_diff_type __l, const __max_diff_type& __r) noexcept + { + __l |= __r; + return __l; + } + + friend constexpr __max_diff_type + operator^(__max_diff_type __l, const __max_diff_type& __r) noexcept + { + __l ^= __r; + return __l; + } + + friend constexpr bool + operator==(const __max_diff_type& __l, const __max_diff_type& __r) noexcept + { return __l._M_rep == __r._M_rep; } + + friend constexpr bool + operator!=(const __max_diff_type& __l, const __max_diff_type& __r) noexcept + { return !(__l == __r); } + + constexpr bool + operator<(const __max_diff_type& __r) const noexcept + { + const auto __lsign = _M_rep._M_msb; + const auto __rsign = __r._M_rep._M_msb; + if (__lsign ^ __rsign) + return __lsign; + else + return _M_rep < __r._M_rep; + } + + friend constexpr bool + operator>(const __max_diff_type& __l, const __max_diff_type& __r) noexcept + { return __r < __l; } + + friend constexpr bool + operator<=(const __max_diff_type& __l, const __max_diff_type& __r) noexcept + { return !(__r < __l); } + + friend constexpr bool + operator>=(const __max_diff_type& __l, const __max_diff_type& __r) noexcept + { return !(__l < __r); } + + private: + __max_size_type _M_rep = 0; + + friend class __max_size_type; + }; + + constexpr + __max_size_type::__max_size_type(const __max_diff_type& __d) noexcept + : __max_size_type(__d._M_rep) + { } + + } // namespace __detail +} // namespace ranges + + template<> + struct numeric_limits<ranges::__detail::__max_size_type> + { + using _Sp = ranges::__detail::__max_size_type; + static constexpr bool is_specialized = true; + static constexpr bool is_signed = false; + static constexpr bool is_integer = true; + static constexpr bool is_exact = true; +#if __SIZEOF_INT128__ + static_assert(same_as<_Sp::__rep, unsigned __int128>); + static constexpr int digits = 129; +#else + static_assert(same_as<_Sp::__rep, unsigned long long>); + static constexpr int digits + = __gnu_cxx::__int_traits<unsigned long long>::__digits + 1; +#endif + static constexpr int digits10 + = static_cast<int>(digits * numbers::ln2 / numbers::ln10); + + static constexpr _Sp + min() noexcept + { return 0; } + + static constexpr _Sp + max() noexcept + { return _Sp(static_cast<_Sp::__rep>(-1), 1); } + + static constexpr _Sp + lowest() noexcept + { return min(); } + }; + + template<> + struct numeric_limits<ranges::__detail::__max_diff_type> + { + using _Dp = ranges::__detail::__max_diff_type; + using _Sp = ranges::__detail::__max_size_type; + static constexpr bool is_specialized = true; + static constexpr bool is_signed = true; + static constexpr bool is_integer = true; + static constexpr bool is_exact = true; + static constexpr int digits = numeric_limits<_Sp>::digits - 1; + static constexpr int digits10 + = static_cast<int>(digits * numbers::ln2 / numbers::ln10); + + static constexpr _Dp + min() noexcept + { return _Dp(_Sp(0, 1)); } + + static constexpr _Dp + max() noexcept + { return _Dp(_Sp(static_cast<_Sp::__rep>(-1), 0)); } + + static constexpr _Dp + lowest() noexcept + { return min(); } + }; + +_GLIBCXX_END_NAMESPACE_VERSION +} // namespace + +#endif // C++20 && library concepts +#endif // _GLIBCXX_MAX_SIZE_TYPE_H diff --git a/libstdc++-v3/include/bits/range_access.h b/libstdc++-v3/include/bits/range_access.h index 3919183c5b4..3eb1f2fd272 100644 --- a/libstdc++-v3/include/bits/range_access.h +++ b/libstdc++-v3/include/bits/range_access.h @@ -36,6 +36,9 @@ #include <initializer_list> #include <bits/iterator_concepts.h> #include <ext/numeric_traits.h> +#if __cplusplus > 201703L +#include <bits/max_size_type.h> +#endif namespace std _GLIBCXX_VISIBILITY(default) { @@ -352,6 +355,14 @@ namespace ranges namespace __detail { + constexpr __max_size_type + __to_unsigned_like(__max_size_type __t) noexcept + { return __t; } + + constexpr __max_size_type + __to_unsigned_like(__max_diff_type __t) noexcept + { return __max_size_type(__t); } + template<integral _Tp> constexpr make_unsigned_t<_Tp> __to_unsigned_like(_Tp __t) noexcept diff --git a/libstdc++-v3/testsuite/std/ranges/iota/difference_type.cc b/libstdc++-v3/testsuite/std/ranges/iota/difference_type.cc new file mode 100644 index 00000000000..4a342deae74 --- /dev/null +++ b/libstdc++-v3/testsuite/std/ranges/iota/difference_type.cc @@ -0,0 +1,57 @@ +// Copyright (C) 2020 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 +// <http://www.gnu.org/licenses/>. + +// { dg-options "-std=gnu++2a" } +// { dg-do run { target c++2a } } + +#include <ranges> +#include <testsuite_hooks.h> + +void +test01() +{ + using I = unsigned long long; + auto imax = std::numeric_limits<I>::max(); + std::ranges::iota_view<I, I> i(0, imax); + auto begin = i.begin(); + static_assert( std::input_or_output_iterator<decltype(begin)> ); + auto size = std::ranges::end(i) - std::ranges::begin(i); + VERIFY( size > 0 ); + VERIFY( size == imax ); +} + +void +test02() +{ +#if __SIZEOF_INT128__ + using I = unsigned __int128; + auto imax = std::numeric_limits<I>::max(); + std::ranges::iota_view<I, I> i(0, imax); + auto begin = i.begin(); + static_assert( std::input_or_output_iterator<decltype(begin)> ); + auto size = std::ranges::end(i) - std::ranges::begin(i); + VERIFY( size > 0 ); + VERIFY( size == imax ); +#endif +} + +int +main() +{ + test01(); + test02(); +} diff --git a/libstdc++-v3/testsuite/std/ranges/iota/max_size_type.cc b/libstdc++-v3/testsuite/std/ranges/iota/max_size_type.cc new file mode 100644 index 00000000000..cb9444074fc --- /dev/null +++ b/libstdc++-v3/testsuite/std/ranges/iota/max_size_type.cc @@ -0,0 +1,376 @@ +// Copyright (C) 2020 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 +// <http://www.gnu.org/licenses/>. + +// { dg-options "-std=gnu++2a" } +// { dg-do run { target c++2a } } + +#include <limits> +#include <ranges> +#include <testsuite_hooks.h> + +using max_size_t = std::ranges::__detail::__max_size_type; +using max_diff_t = std::ranges::__detail::__max_diff_type; +using rep_t = max_size_t::__rep; + +static_assert(sizeof(max_size_t) == sizeof(max_diff_t)); + +static_assert(std::regular<max_size_t>); +static_assert(std::totally_ordered<max_size_t>); + +static_assert(std::regular<max_diff_t>); +static_assert(std::totally_ordered<max_diff_t>); + +// We can't use numeric_limits<rep_t>::max() here because __int128 is an +// integral type only in GNU mode. +constexpr max_size_t mu = max_size_t(~rep_t(0)); +constexpr max_size_t ou = 1; +constexpr max_diff_t ns = -1; + +void +test01() +{ + static_assert(max_size_t(7) % 3 == 1); + static_assert(max_size_t(7) % 4 == 3); + + static_assert(-max_diff_t(1) == max_diff_t(-1)); + static_assert(max_diff_t(3) % 2 == 1); + static_assert(max_diff_t(-3) / 2 == -1); + static_assert(max_diff_t(-3) % 2 == -1); + static_assert(max_diff_t(3) % -2 == 1); + static_assert(max_diff_t(-3) << 1 == -6); + static_assert(max_diff_t(-3) >> 1 == -2); + static_assert(max_diff_t(3) >> 1 == 1); + static_assert(max_diff_t(3) >> 2 == 0); + + static_assert(max_diff_t(-5) / 3 == -1); + static_assert(max_diff_t(5) / -3 == -1); + static_assert(max_diff_t(-5) / -3 == 1); + static_assert(max_diff_t(5) / 3 == 1); + + static_assert(max_diff_t(-6) / 3 == -2); + static_assert(max_diff_t(6) / -3 == -2); + static_assert(max_diff_t(-6) / -3 == 2); + static_assert(max_diff_t(6) / 3 == 2); + + static_assert(~max_size_t(-3) == 2); + static_assert(~max_diff_t(-3) == 2); + + static_assert(max_diff_t(1) < max_diff_t(3)); + static_assert(max_diff_t(-1) < max_diff_t(3)); + static_assert(max_diff_t(1) > max_diff_t(-3)); + static_assert(max_diff_t(-1) > max_diff_t(-3)); + + static_assert(max_diff_t(mu)/-1 == -max_diff_t(mu)); + static_assert(-max_diff_t(mu)/1 == -max_diff_t(mu)); + static_assert(max_diff_t(mu)>>1 == max_diff_t(mu)/2); + static_assert(-max_diff_t(mu+1) == max_diff_t(mu+1)); + static_assert(-(mu+1) == mu+1); + static_assert((mu+1)<<1 == 0); + static_assert(max_diff_t(mu+1)<<1 == 0); + static_assert(max_diff_t(mu+1)>>1 < 0); + + static_assert(int(max_diff_t(mu+1)) == 0); + static_assert(rep_t(max_diff_t(mu+1)) == 0); + static_assert(int(max_diff_t(mu)) == -1); + static_assert(rep_t(max_diff_t(mu)) == rep_t(-1)); + + static_assert(2*mu+1 > 2*mu); + static_assert(~(2*mu+1) == 0); + static_assert(mu/mu == 1); + static_assert(2*mu > mu); + static_assert(2*mu-mu == mu); + static_assert((2*mu)/mu == 2); + static_assert((2*mu+1)/mu == 2); + static_assert((2*mu-1)/(mu-1) == 2); + static_assert((2*mu-1)/mu == 1); + static_assert((2*mu+-1)/mu == 1); + static_assert(2*mu-1 < 2*mu); + static_assert(2*mu-1 <= 2*mu); + static_assert(2*mu+1 > 2*mu); + static_assert(2*mu+1 >= 2*mu); + static_assert((2*mu)/1 == 2*mu); + static_assert(mu/mu-1 == 0); + static_assert(mu*0 == 0); + static_assert((2*mu-1)*0 == 0); + static_assert((2*mu-1)>>1 == mu-1); + static_assert(mu+-1+1 == mu); + static_assert(mu+1+-1 == mu); + static_assert(mu+1); + static_assert((2*mu)/2 == mu); + static_assert((2*mu)>>1 == mu); + static_assert((mu<<1)>>1 == mu); + static_assert(1/mu == 0); + static_assert(mu/1 == mu); + static_assert(((mu+1)|mu) == -1); + static_assert((mu+1)+(mu+1) < mu+1); + + static_assert(max_size_t(ns) == -1); + static_assert(-max_diff_t(ou) == -1); + static_assert(-max_diff_t(-ou) == 1); + static_assert(max_size_t(-max_diff_t(-ou)) == 1); + static_assert(ns*ns == max_diff_t(ou)); + static_assert(max_size_t(ns)*max_size_t(ns) == ou); + static_assert(-max_diff_t(0) == max_diff_t(0)); + static_assert(-ou-ou == -2*ou); + + static_assert(int(ns) == -1); + static_assert(rep_t(ns) == rep_t(-1)); + + static_assert(max_size_t() == 0); + static_assert(max_diff_t() == 0); + + auto f = [] (auto a) { a /= a; return a; }; + static_assert(f(max_size_t(5)) == 1); + static_assert(f(max_size_t(-5)) == 1); + static_assert(f(max_diff_t(5)) == 1); + + auto g = [] (auto a) { a >>= a; return a; }; + static_assert(g(max_size_t(5)) == 0); + static_assert(g(max_diff_t(5)) == 0); + + auto h = [] (auto a) { a <<= a; return a; }; + static_assert(h(max_size_t(3)) == 24); + static_assert(h(max_diff_t(3)) == 24); +} + +template<bool signed_p, bool shorten_p> +void +test02() +{ + using hw_type = std::conditional_t<signed_p, signed rep_t, rep_t>; + using max_type = std::conditional_t<signed_p, max_diff_t, max_size_t>; + using shorten_type = std::conditional_t<shorten_p, hw_type, max_type>; + const int hw_type_bit_size = sizeof(hw_type) * __CHAR_BIT__; + const int limit = 1000; + const int log2_limit = 10; + static_assert((1 << log2_limit) >= limit); + const int min = (signed_p ? -limit : 0); + const int max = limit; + for (hw_type i = min; i <= max; i++) + { + bool ok = true; + if (signed_p || shorten_p) + { + ok &= (~i == shorten_type(~max_type(i))); + ok &= (-i == shorten_type(-max_type(i))); + } + for (hw_type j = min; j <= max; j++) + { + ok &= (i*j == shorten_type(max_type(i)*j)); + ok &= (i+j == shorten_type(max_type(i)+j)); + if (j != 0) + { + ok &= (i/j == shorten_type(max_type(i)/j)); + ok &= (i%j == shorten_type(max_type(i)%j)); + } + if (signed_p || shorten_p) + ok &= (i-j == shorten_type(max_type(i)-j)); + ok &= ((i&j) == shorten_type(max_type(i)&j)); + ok &= ((i|j) == shorten_type(max_type(i)|j)); + ok &= ((i^j) == shorten_type(max_type(i)^j)); + if (j >= 0 && j < hw_type(hw_type_bit_size) + && (shorten_p || j < hw_type(hw_type_bit_size) - log2_limit)) + { + ok &= ((i>>j) == shorten_type(max_type(i)>>j)); + ok &= ((i<<j) == shorten_type(max_type(i)<<j)); + } + ok &= (i>j) == (max_type(i) > j); + ok &= (i<j) == (max_type(i) < j); + ok &= (i>=j) == (max_type(i) >= j); + ok &= (i<=j) == (max_type(i) <= j); + ok &= (i==j) == (max_type(i) == j); + ok &= (i!=j) == (max_type(i) != j); + if (!ok) + { + fprintf(stderr, + "Inconsistency found: %d %d %lld %lld\n", + signed_p, shorten_p, (long long)i, (long long)j) ; + VERIFY(0); + } + } + } +} + +template<bool signed_p, bool toggle_base_p> +void +test03() +{ + using hw_type = std::conditional_t<signed_p, signed rep_t, rep_t>; + using max_type = std::conditional_t<signed_p, max_diff_t, max_size_t>; + using base_type = std::conditional_t<toggle_base_p, hw_type, max_type>; + constexpr int hw_type_bit_size = sizeof(hw_type) * __CHAR_BIT__; + constexpr int limit = 1000; + constexpr int log2_limit = 10; + static_assert((1 << log2_limit) >= limit); + const int min = (signed_p ? -limit : 0); + const int max = limit; + for (hw_type i = min; i <= max; i++) + { + bool ok = true; + base_type k; + for (hw_type j = min; j <= max; j++) + { + k = i; k *= j; + ok &= (k == (max_type(i)*j)); + k = i; k += j; + ok &= (k == (max_type(i)+j)); + if (j != 0) + { + k = i; k /= j; + ok &= (k == (max_type(i)/j)); + k = i; k %= j; + ok &= (k == (max_type(i)%j)); + } + if (signed_p) + { + k = i; k -= j; + ok &= (k == (max_type(i)-j)); + } + k = i; k &= j; + ok &= (k == (max_type(i)&j)); + k = i; k |= j; + ok &= (k == (max_type(i)|j)); + k = i; k ^= j; + ok &= (k == (max_type(i)^j)); + if (j >= 0 && j < hw_type(hw_type_bit_size) + && (!toggle_base_p || j < hw_type(hw_type_bit_size) - log2_limit)) + { + k = i; k >>= j; + ok &= (k == (max_type(i)>>j)); + k = i; k <<= j; + ok &= (k == (max_type(i)<<j)); + } + if (!ok) + { + fprintf(stderr, + "Inconsistency found: %d %d %lld %lld\n", + signed_p, toggle_base_p, (long long)i, (long long)j) ; + VERIFY(0); + } + } + } +} + +void +test04() +{ + constexpr int limit = 1000; + for (int i = -limit; i <= limit; i++) + { + VERIFY( -max_size_t(-i) == i ); + for (int j = i; j <= limit; j++) + { + VERIFY( max_size_t(-i) * max_size_t(-j) == i*j ); + VERIFY( max_size_t(-j) * max_size_t(-i) == j*i ); + VERIFY( rep_t(((mu+1)+i)*((mu+1)+j)) == rep_t(i*j) ); + VERIFY( rep_t(((mu+1)+j)*((mu+1)+i)) == rep_t(j*i) ); + if (i >= 0 && j > 0) + { + auto r = (mu+i)-((mu+i)/j)*j; + VERIFY( r >= 0 && r < j ); + VERIFY( r == (mu+i)%j ); + } + } + } +} + +void +test05() +{ +#if __SIZEOF_INT128__ + max_size_t x = 0; + x = static_cast<__int128>(0); + x = static_cast<unsigned __int128>(0); + + max_diff_t y = 0; + y = static_cast<__int128>(0);; + y = static_cast<unsigned __int128>(0); +#endif +} + +using std::numeric_limits; + +static_assert(numeric_limits<max_size_t>::is_specialized); +static_assert(!numeric_limits<max_size_t>::is_signed); +static_assert(numeric_limits<max_size_t>::is_integer); +static_assert(numeric_limits<max_size_t>::is_exact); +// We can't unconditionally use numeric_limits here because __int128 is an +// integral type only in GNU mode. +#if __SIZEOF_INT128__ +static_assert(numeric_limits<max_size_t>::digits == 129); +static_assert(numeric_limits<max_size_t>::digits10 == 38); +static_assert(numeric_limits<max_size_t>::max() + == 2*max_size_t(~rep_t(0)) + 1); +#else +static_assert(numeric_limits<max_size_t>::digits + == numeric_limits<rep_t>::digits + 1); +static_assert(numeric_limits<max_size_t>::digits10 + == numeric_limits<rep_t>::digits10); +static_assert(numeric_limits<max_size_t>::max() + == 2*max_size_t(numeric_limits<rep_t>::max())+1); +#endif +static_assert(numeric_limits<max_size_t>::min() == 0); +static_assert(numeric_limits<max_size_t>::max() + == max_size_t(-1)); +static_assert((numeric_limits<max_size_t>::max() + >> (numeric_limits<max_size_t>::digits-1)) == 1); +static_assert(numeric_limits<max_size_t>::lowest() + == numeric_limits<max_size_t>::min()); + +static_assert(numeric_limits<max_diff_t>::is_specialized); +static_assert(numeric_limits<max_diff_t>::is_signed); +static_assert(numeric_limits<max_diff_t>::is_integer); +static_assert(numeric_limits<max_diff_t>::is_exact); +static_assert(numeric_limits<max_diff_t>::digits + == numeric_limits<max_size_t>::digits - 1); +static_assert(numeric_limits<max_diff_t>::digits10 + == numeric_limits<max_size_t>::digits10); +// We can't unconditionally use numeric_limits here because __int128 is an +// integral type only in GNU mode. +#if __SIZEOF_INT128__ +static_assert(numeric_limits<max_diff_t>::min() == -max_diff_t(~rep_t(0))-1); +static_assert(numeric_limits<max_diff_t>::max() == ~rep_t(0)); +#else +static_assert(numeric_limits<max_diff_t>::min() + == -max_diff_t(numeric_limits<rep_t>::max())-1); +static_assert(numeric_limits<max_diff_t>::max() + == numeric_limits<rep_t>::max()); +#endif +static_assert(numeric_limits<max_diff_t>::lowest() + == numeric_limits<max_diff_t>::min()); +static_assert(max_diff_t(max_size_t(1) + << (numeric_limits<max_size_t>::digits-1)) + == numeric_limits<max_diff_t>::min()); + +int +main() +{ + test01(); + + test02<false,false>(); + test02<false,true>(); + test02<true,false>(); + test02<true,true>(); + + test03<false,false>(); + test03<false,true>(); + test03<true,false>(); + test03<true,true>(); + + test04(); + test05(); +}
On 11/08/20 11:38 -0400, Patrick Palka via Libstdc++ wrote: >Subject: [PATCH] libstdc++: integer-class types as per [iterator.concept.winc] > >This implements signed and unsigned integer-class types, whose width is >one bit larger than the widest supported signed and unsigned integral >type respectively. In our case this is either __int128 and unsigned >__int128, or long long and unsigned long long. > >Internally, the two integer-class types are represented as a largest >supported unsigned integral type plus one extra bit. The signed >integer-class type is represented in two's complement form with the >extra bit acting as the sign bit. > >libstdc++-v3/ChangeLog: > > * include/Makefile.am (bits_headers): Add new header > <bits/max_size_type.h>. > * include/Makefile.in: Regenerate. > * include/bits/iterator_concepts.h > (ranges::__detail::__max_diff_type): Remove definition, replace > with forward declaration of class __max_diff_type. > (__detail::__max_size_type): Remove definition, replace with > forward declaration of class __max_size_type. > (__detail::__is_unsigned_int128, __is_signed_int128, > __is_int128): New concepts. According to GNU changelog conventions you should close the parens at the end of the first line and reopen them on the next i.e. (__detail::__is_unsigned_int128, __is_signed_int128) (__is_int128): New concepts. See the paragraph beginning "Break long lists of function names" at https://www.gnu.org/prep/standards/html_node/Style-of-Change-Logs.html#Style-of-Change-Logs Apart from that, this looks great. Please push, thanks!
diff --git a/libstdc++-v3/include/bits/iterator_concepts.h b/libstdc++-v3/include/bits/iterator_concepts.h index 08e622259b4..6eff0b82feb 100644 --- a/libstdc++-v3/include/bits/iterator_concepts.h +++ b/libstdc++-v3/include/bits/iterator_concepts.h @@ -482,20 +482,21 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION namespace ranges::__detail { -#if __SIZEOF_INT128__ - using __max_diff_type = __int128; - using __max_size_type = unsigned __int128; -#else - using __max_diff_type = long long; - using __max_size_type = unsigned long long; -#endif + class __max_diff_type; + class __max_size_type; template<typename _Tp> concept __is_integer_like = integral<_Tp> +#if __SIZEOF_INT128__ + || same_as<_Tp, __int128> || same_as<_Tp, unsigned __int128> +#endif || same_as<_Tp, __max_diff_type> || same_as<_Tp, __max_size_type>; template<typename _Tp> concept __is_signed_integer_like = signed_integral<_Tp> +#if __SIZEOF_INT128__ + || same_as<_Tp, __int128> +#endif || same_as<_Tp, __max_diff_type>; } // namespace ranges::__detail diff --git a/libstdc++-v3/include/bits/range_access.h b/libstdc++-v3/include/bits/range_access.h index 8b276fd6625..08140b5e77d 100644 --- a/libstdc++-v3/include/bits/range_access.h +++ b/libstdc++-v3/include/bits/range_access.h @@ -351,6 +351,628 @@ namespace ranges namespace __detail { + // An unsigned integer-class type as per [iterator.concept.winc]. + class __max_size_type + { + public: + __max_size_type() = default; + + template<integral _Tp> + constexpr + __max_size_type(_Tp __i) noexcept + : _M_val(__i), _M_msb(__i < 0) + { } + + constexpr explicit + __max_size_type(const __max_diff_type& __d) noexcept; + + template<integral _Tp> + constexpr explicit operator _Tp() const noexcept + { return _M_val; } + + constexpr explicit + operator bool() const noexcept + { return _M_val != 0 || _M_msb != 0; } + + constexpr __max_size_type + operator+() const noexcept + { return *this; } + + constexpr __max_size_type + operator~() const noexcept + { return __max_size_type{~_M_val, !_M_msb}; } + + constexpr __max_size_type + operator-() const noexcept + { return operator~() + 1; } + + constexpr __max_size_type& + operator+=(const __max_size_type& __r) noexcept + { + const auto __sum = _M_val + __r._M_val; + const bool __overflow = (__sum < _M_val); + _M_msb = _M_msb ^ __r._M_msb ^ __overflow; + _M_val = __sum; + return *this; + } + + constexpr __max_size_type& + operator-=(const __max_size_type& __r) noexcept + { return *this += -__r; } + + constexpr __max_size_type& + operator*=(__max_size_type __r) noexcept + { + const bool __lsb = _M_val & 1; + const bool __rlsb = __r._M_val & 1; + + constexpr auto __threshold = __rep(1) << (__rep_bits / 2 - 1); + if (!_M_msb && !__r._M_msb + && _M_val < __threshold && __r._M_val < __threshold) [[likely]] + _M_val = _M_val * __r._M_val; + else + { + *this >>= 1; + __r >>= 1; + _M_val = (2 * _M_val * __r._M_val + + _M_val * __rlsb + __r._M_val * __lsb); + *this <<= 1; + *this += __rlsb * __lsb; + } + + return *this; + } + + constexpr __max_size_type& + operator/=(const __max_size_type& __r) noexcept + { + __glibcxx_assert(__r != 0); + + if (!_M_msb && !__r._M_msb) [[likely]] + _M_val /= __r._M_val; + else if (_M_msb && __r._M_msb) + { + _M_val = (_M_val >= __r._M_val); + _M_msb = 0; + } + else if (!_M_msb && __r._M_msb) + _M_val = 0; + else if (_M_msb && !__r._M_msb) + { + const auto __orig = *this; + *this >>= 1; + _M_val /= __r._M_val; + *this <<= 1; + if (__orig - *this * __r >= __r) + ++_M_val; + } + return *this; + } + + constexpr __max_size_type& + operator%=(const __max_size_type& __r) noexcept + { + if (!_M_msb && !__r._M_msb) [[likely]] + _M_val %= __r._M_val; + else + *this -= (*this / __r) * __r; + return *this; + } + + constexpr __max_size_type& + operator<<=(const __max_size_type& __r) noexcept + { + __glibcxx_assert(__r < __rep_bits); + if (__r == 0) + return *this; + if (_M_val & (__rep(1) << (__rep_bits - __r._M_val))) + _M_msb = 1; + else + _M_msb = 0; + _M_val <<= __r._M_val; + return *this; + } + + constexpr __max_size_type& + operator>>=(const __max_size_type& __r) noexcept + { + __glibcxx_assert(__r < __rep_bits); + if (__r == 0) + return *this; + _M_val >>= __r._M_val; + if (_M_msb) [[unlikely]] + { + _M_val |= __rep(1) << (__rep_bits - __r._M_val); + _M_msb = 0; + } + return *this; + } + + constexpr __max_size_type& + operator&=(const __max_size_type& __r) noexcept + { + _M_val &= __r._M_val; + _M_msb &= __r._M_msb; + return *this; + } + + constexpr __max_size_type& + operator|=(const __max_size_type& __r) noexcept + { + _M_val |= __r._M_val; + _M_msb |= __r._M_msb; + return *this; + } + + constexpr __max_size_type& + operator^=(const __max_size_type& __r) noexcept + { + _M_val ^= __r._M_val; + _M_msb ^= __r._M_msb; + return *this; + } + + template<integral _Tp> + friend constexpr _Tp& + operator+=(_Tp& a, const __max_size_type& b) noexcept + { return (a = static_cast<_Tp>(a + b)); } + + template<integral _Tp> + friend constexpr _Tp& + operator-=(_Tp& a, const __max_size_type& b) noexcept + { return (a = static_cast<_Tp>(a - b)); } + + template<integral _Tp> + friend constexpr _Tp& + operator*=(_Tp& a, const __max_size_type& b) noexcept + { return (a = static_cast<_Tp>(a * b)); } + + template<integral _Tp> + friend constexpr _Tp& + operator/=(_Tp& a, const __max_size_type& b) noexcept + { return (a = static_cast<_Tp>(a / b)); } + + template<integral _Tp> + friend constexpr _Tp& + operator%=(_Tp& a, const __max_size_type& b) noexcept + { return (a = static_cast<_Tp>(a % b)); } + + template<integral _Tp> + friend constexpr _Tp& + operator&=(_Tp& a, const __max_size_type& b) noexcept + { return (a = static_cast<_Tp>(a & b)); } + + template<integral _Tp> + friend constexpr _Tp& + operator|=(_Tp& a, const __max_size_type& b) noexcept + { return (a = static_cast<_Tp>(a | b)); } + + template<integral _Tp> + friend constexpr _Tp& + operator^=(_Tp& a, const __max_size_type& b) noexcept + { return (a = static_cast<_Tp>(a ^ b)); } + + template<integral _Tp> + friend constexpr _Tp& + operator<<=(_Tp& a, const __max_size_type& b) noexcept + { return (a = static_cast<_Tp>(a << b)); } + + template<integral _Tp> + friend constexpr _Tp& + operator>>=(_Tp& a, const __max_size_type& b) noexcept + { return (a = static_cast<_Tp>(a >> b)); } + + friend constexpr __max_size_type + operator+(__max_size_type __l, const __max_size_type& __r) noexcept + { + __l += __r; + return __l; + } + + friend constexpr __max_size_type + operator-(__max_size_type __l, const __max_size_type& __r) noexcept + { + __l -= __r; + return __l; + } + + friend constexpr __max_size_type + operator*(__max_size_type __l, const __max_size_type& __r) noexcept + { + __l *= __r; + return __l; + } + + friend constexpr __max_size_type + operator/(__max_size_type __l, const __max_size_type& __r) noexcept + { + __l /= __r; + return __l; + } + + friend constexpr __max_size_type + operator%(__max_size_type __l, const __max_size_type& __r) noexcept + { + __l %= __r; + return __l; + } + + friend constexpr __max_size_type + operator<<(__max_size_type __l, const __max_size_type& __r) noexcept + { + __l <<= __r; + return __l; + } + + friend constexpr __max_size_type + operator>>(__max_size_type __l, const __max_size_type& __r) noexcept + { + __l >>= __r; + return __l; + } + + friend constexpr __max_size_type + operator&(__max_size_type __l, const __max_size_type& __r) noexcept + { + __l &= __r; + return __l; + } + + friend constexpr __max_size_type + operator|(__max_size_type __l, const __max_size_type& __r) noexcept + { + __l |= __r; + return __l; + } + + friend constexpr __max_size_type + operator^(__max_size_type __l, const __max_size_type& __r) noexcept + { + __l ^= __r; + return __l; + } + + friend constexpr bool + operator==(const __max_size_type& __l, const __max_size_type& __r) noexcept + { return __l._M_val == __r._M_val && __l._M_msb == __r._M_msb; } + + friend constexpr bool + operator!=(const __max_size_type& __l, const __max_size_type& __r) noexcept + { return !(__l == __r); } + + friend constexpr bool + operator<(const __max_size_type& __l, const __max_size_type& __r) noexcept + { + if (__l._M_msb == __r._M_msb) + return __l._M_val < __r._M_val; + else + return __r._M_msb; + } + + friend constexpr bool + operator>(const __max_size_type& __l, const __max_size_type& __r) noexcept + { return __r < __l; } + + friend constexpr bool + operator<=(const __max_size_type& __l, const __max_size_type& __r) noexcept + { return !(__l > __r); } + + friend constexpr bool + operator>=(const __max_size_type& __l, const __max_size_type& __r) noexcept + { return __r <= __l; } + +#ifdef __SIZEOF_INT128__ + using __rep = unsigned __int128; +#else + using __rep = unsigned long long; +#endif + static constexpr size_t __rep_bits = sizeof(__rep) * __CHAR_BIT__; + private: + __rep _M_val = 0; + unsigned _M_msb:1 = 0; + + constexpr explicit + __max_size_type(__rep __val, int __msb) noexcept + : _M_val(__val), _M_msb(__msb) + { } + + friend __max_diff_type; + friend std::numeric_limits<__max_size_type>; + friend std::numeric_limits<__max_diff_type>; + }; + + // A signed integer-class type as per [iterator.concept.winc]. + class __max_diff_type + { + public: + __max_diff_type() = default; + + template<integral _Tp> + constexpr + __max_diff_type(_Tp __i) noexcept + : _M_rep(__i) + { } + + constexpr explicit + __max_diff_type(const __max_size_type& __d) noexcept + : _M_rep(__d) + { } + + template<integral _Tp> + constexpr explicit operator _Tp() const noexcept + { return static_cast<_Tp>(_M_rep); } + + constexpr explicit + operator bool() const noexcept + { return _M_rep != 0; } + + constexpr __max_diff_type + operator+() const noexcept + { return *this; } + + constexpr __max_diff_type + operator-() const noexcept + { return __max_diff_type(-_M_rep); } + + constexpr __max_diff_type + operator~() const noexcept + { return __max_diff_type(~_M_rep); } + + constexpr __max_diff_type& + operator+=(const __max_diff_type& __r) noexcept + { + _M_rep += __r._M_rep; + return *this; + } + + constexpr __max_diff_type& + operator-=(const __max_diff_type& __r) noexcept + { + _M_rep -= __r._M_rep; + return *this; + } + + constexpr __max_diff_type& + operator*=(const __max_diff_type& __r) noexcept + { + _M_rep *= __r._M_rep; + return *this; + } + + constexpr __max_diff_type& + operator/=(const __max_diff_type& __r) noexcept + { + __glibcxx_assert (__r != 0); + const bool __neg = *this < 0; + const bool __rneg = __r < 0; + if (!__neg && !__rneg) + _M_rep = _M_rep / __r._M_rep; + else if (__neg && __rneg) + _M_rep = -_M_rep / -__r._M_rep; + else + _M_rep = -((__neg ? -_M_rep : _M_rep) + / (__rneg ? -__r._M_rep : __r._M_rep)); + return *this ; + } + + constexpr __max_diff_type& + operator%=(const __max_diff_type& __r) noexcept + { + __glibcxx_assert (__r != 0); + if (*this >= 0 && __r > 0) + _M_rep %= __r._M_rep; + else + *this -= (*this / __r) * __r; + return *this; + } + + constexpr __max_diff_type& + operator<<=(const __max_diff_type& __r) noexcept + { + _M_rep.operator<<=(__r._M_rep); + return *this; + } + + constexpr __max_diff_type& + operator>>=(const __max_diff_type& __r) noexcept + { + const auto __msb = _M_rep._M_msb; + _M_rep >>= __r._M_rep; + _M_rep._M_msb |= __msb; + return *this; + } + + constexpr __max_diff_type& + operator&=(const __max_diff_type& __r) noexcept + { + _M_rep &= __r._M_rep; + return *this; + } + + constexpr __max_diff_type& + operator|=(const __max_diff_type& __r) noexcept + { + _M_rep |= __r._M_rep; + return *this; + } + + constexpr __max_diff_type& + operator^=(const __max_diff_type& __r) noexcept + { + _M_rep ^= __r._M_rep; + return *this; + } + + template<integral _Tp> + friend constexpr _Tp& + operator+=(_Tp& a, const __max_diff_type& b) noexcept + { return (a = static_cast<_Tp>(a + b)); } + + template<integral _Tp> + friend constexpr _Tp& + operator-=(_Tp& a, const __max_diff_type& b) noexcept + { return (a = static_cast<_Tp>(a - b)); } + + template<integral _Tp> + friend constexpr _Tp& + operator*=(_Tp& a, const __max_diff_type& b) noexcept + { return (a = static_cast<_Tp>(a * b)); } + + template<integral _Tp> + friend constexpr _Tp& + operator/=(_Tp& a, const __max_diff_type& b) noexcept + { return (a = static_cast<_Tp>(a / b)); } + + template<integral _Tp> + friend constexpr _Tp& + operator%=(_Tp& a, const __max_diff_type& b) noexcept + { return (a = static_cast<_Tp>(a % b)); } + + template<integral _Tp> + friend constexpr _Tp& + operator&=(_Tp& a, const __max_diff_type& b) noexcept + { return (a = static_cast<_Tp>(a & b)); } + + template<integral _Tp> + friend constexpr _Tp& + operator|=(_Tp& a, const __max_diff_type& b) noexcept + { return (a = static_cast<_Tp>(a | b)); } + + template<integral _Tp> + friend constexpr _Tp& + operator^=(_Tp& a, const __max_diff_type& b) noexcept + { return (a = static_cast<_Tp>(a ^ b)); } + + template<integral _Tp> + friend constexpr _Tp& + operator<<=(_Tp& a, const __max_diff_type& b) noexcept + { return (a = static_cast<_Tp>(a << b)); } + + template<integral _Tp> + friend constexpr _Tp& + operator>>=(_Tp& a, const __max_diff_type& b) noexcept + { return (a = static_cast<_Tp>(a >> b)); } + + friend constexpr __max_diff_type + operator+(__max_diff_type __l, const __max_diff_type& __r) noexcept + { + __l += __r; + return __l; + } + + friend constexpr __max_diff_type + operator-(__max_diff_type __l, const __max_diff_type& __r) noexcept + { + __l -= __r; + return __l; + } + + friend constexpr __max_diff_type + operator*(__max_diff_type __l, const __max_diff_type& __r) noexcept + { + __l *= __r; + return __l; + } + + friend constexpr __max_diff_type + operator/(__max_diff_type __l, const __max_diff_type& __r) noexcept + { + __l /= __r; + return __l; + } + + friend constexpr __max_diff_type + operator%(__max_diff_type __l, const __max_diff_type& __r) noexcept + { + __l %= __r; + return __l; + } + + friend constexpr __max_diff_type + operator<<(__max_diff_type __l, const __max_diff_type& __r) noexcept + { + __l <<= __r; + return __l; + } + + friend constexpr __max_diff_type + operator>>(__max_diff_type __l, const __max_diff_type& __r) noexcept + { + __l >>= __r; + return __l; + } + + friend constexpr __max_diff_type + operator&(__max_diff_type __l, const __max_diff_type& __r) noexcept + { + __l &= __r; + return __l; + } + + friend constexpr __max_diff_type + operator|(__max_diff_type __l, const __max_diff_type& __r) noexcept + { + __l |= __r; + return __l; + } + + friend constexpr __max_diff_type + operator^(__max_diff_type __l, const __max_diff_type& __r) noexcept + { + __l ^= __r; + return __l; + } + + friend constexpr bool + operator==(const __max_diff_type& __l, const __max_diff_type& __r) noexcept + { return __l._M_rep == __r._M_rep; } + + friend constexpr bool + operator!=(const __max_diff_type& __l, const __max_diff_type& __r) noexcept + { return !(__l == __r); } + + constexpr bool + operator<(const __max_diff_type& __r) const noexcept + { + const auto __lsign = _M_rep._M_msb; + const auto __rsign = __r._M_rep._M_msb; + if (__lsign ^ __rsign) + return __lsign; + else + return _M_rep < __r._M_rep; + } + + friend constexpr bool + operator>(const __max_diff_type& __l, const __max_diff_type& __r) noexcept + { return __r < __l; } + + friend constexpr bool + operator<=(const __max_diff_type& __l, const __max_diff_type& __r) noexcept + { return !(__r < __l); } + + friend constexpr bool + operator>=(const __max_diff_type& __l, const __max_diff_type& __r) noexcept + { return !(__l < __r); } + + private: + __max_size_type _M_rep = 0; + + friend class __max_size_type; + }; + + constexpr + __max_size_type::__max_size_type(const __max_diff_type& __d) noexcept + : __max_size_type(__d._M_rep) + { } + + constexpr __max_size_type + __to_unsigned_like(__max_size_type __t) noexcept + { return __t; } + + constexpr __max_size_type + __to_unsigned_like(__max_diff_type __t) noexcept + { return __max_size_type(__t); } + template<integral _Tp> constexpr make_unsigned_t<_Tp> __to_unsigned_like(_Tp __t) noexcept @@ -359,13 +981,67 @@ namespace ranges template<typename _Tp, bool _MaxDiff = same_as<_Tp, __max_diff_type>> using __make_unsigned_like_t = conditional_t<_MaxDiff, __max_size_type, make_unsigned_t<_Tp>>; + } // namespace __detail +} // namespace ranges + + template<> + struct numeric_limits<ranges::__detail::__max_size_type> + { + using _Sp = ranges::__detail::__max_size_type; + static constexpr bool is_specialized = true; + static constexpr bool is_signed = false; + static constexpr bool is_integer = true; + static constexpr bool is_exact = true; + static constexpr int digits = numeric_limits<_Sp::__rep>::digits + 1; + static constexpr int digits10 = numeric_limits<_Sp::__rep>::digits10; + + static constexpr _Sp + min() noexcept + { return 0; } + + static constexpr _Sp + max() noexcept + { return _Sp(numeric_limits<_Sp::__rep>::max(), 1); } + + static constexpr _Sp + lowest() noexcept + { return min(); } + }; + + template<> + struct numeric_limits<ranges::__detail::__max_diff_type> + { + using _Dp = ranges::__detail::__max_diff_type; + using _Sp = ranges::__detail::__max_size_type; + static constexpr bool is_specialized = true; + static constexpr bool is_signed = true; + static constexpr bool is_integer = true; + static constexpr bool is_exact = true; + static constexpr int digits = numeric_limits<_Sp>::digits - 1; + static constexpr int digits10 = numeric_limits<_Sp>::digits10; + + static constexpr _Dp + min() noexcept + { return _Dp(_Sp(0, 1)); } + + static constexpr _Dp + max() noexcept + { return _Dp(_Sp(numeric_limits<_Sp::__rep>::max(), 0)); } + + static constexpr _Dp + lowest() noexcept + { return min(); } + }; +namespace ranges +{ + namespace __detail + { // Part of the constraints of ranges::borrowed_range template<typename _Tp> concept __maybe_borrowed_range = is_lvalue_reference_v<_Tp> || enable_borrowed_range<remove_cvref_t<_Tp>>; - } // namespace __detail namespace __cust_access diff --git a/libstdc++-v3/testsuite/std/ranges/iota/difference_type.cc b/libstdc++-v3/testsuite/std/ranges/iota/difference_type.cc new file mode 100644 index 00000000000..ef671a4a21b --- /dev/null +++ b/libstdc++-v3/testsuite/std/ranges/iota/difference_type.cc @@ -0,0 +1,379 @@ +// Copyright (C) 2020 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 +// <http://www.gnu.org/licenses/>. + +// { dg-options "-std=gnu++2a" } +// { dg-do run { target c++2a } } + +#include <ranges> +#include <testsuite_hooks.h> + +void +test01() +{ + using I = unsigned long long; + auto imax = std::numeric_limits<I>::max(); + std::ranges::iota_view<I, I> i(0, imax); + auto begin = i.begin(); + static_assert( std::input_or_output_iterator<decltype(begin)> ); + auto size = std::ranges::end(i) - std::ranges::begin(i); + VERIFY( size > 0 ); + VERIFY( size == imax ); +} + +void +test02() +{ +#if __SIZEOF_INT128__ + using I = unsigned __int128; + auto imax = std::numeric_limits<I>::max(); + std::ranges::iota_view<I, I> i(0, imax); + auto begin = i.begin(); + static_assert( std::input_or_output_iterator<decltype(begin)> ); + auto size = std::ranges::end(i) - std::ranges::begin(i); + VERIFY( size > 0 ); + VERIFY( size == imax ); +#endif +} + +// The following are correctness tests for the arithmetic operations on +// __max_size_type and __max_diff_type. + +using max_size_t = std::ranges::__detail::__max_size_type; +using max_diff_t = std::ranges::__detail::__max_diff_type; +using rep_t = max_size_t::__rep; + +static_assert(sizeof(max_size_t) == sizeof(max_diff_t)); + +static_assert(std::regular<max_size_t>); +static_assert(std::totally_ordered<max_size_t>); + +static_assert(std::regular<max_diff_t>); +static_assert(std::totally_ordered<max_diff_t>); + +void +test03() +{ + static_assert(max_size_t(7) % 3 == 1); + static_assert(max_size_t(7) % 4 == 3); + + static_assert(-max_diff_t(1) == max_diff_t(-1)); + static_assert(max_diff_t(3) % 2 == 1); + static_assert(max_diff_t(-3) / 2 == -1); + static_assert(max_diff_t(-3) % 2 == -1); + static_assert(max_diff_t(3) % -2 == 1); + static_assert(max_diff_t(-3) << 1 == -6); + static_assert(max_diff_t(-3) >> 1 == -2); + static_assert(max_diff_t(3) >> 1 == 1); + static_assert(max_diff_t(3) >> 2 == 0); + + static_assert(max_diff_t(-5) / 3 == -1); + static_assert(max_diff_t(5) / -3 == -1); + static_assert(max_diff_t(-5) / -3 == 1); + static_assert(max_diff_t(5) / 3 == 1); + + static_assert(max_diff_t(-6) / 3 == -2); + static_assert(max_diff_t(6) / -3 == -2); + static_assert(max_diff_t(-6) / -3 == 2); + static_assert(max_diff_t(6) / 3 == 2); + + static_assert(~max_size_t(-3) == 2); + static_assert(~max_diff_t(-3) == 2); + + static_assert(max_diff_t(1) < max_diff_t(3)); + static_assert(max_diff_t(-1) < max_diff_t(3)); + static_assert(max_diff_t(1) > max_diff_t(-3)); + static_assert(max_diff_t(-1) > max_diff_t(-3)); + + constexpr max_size_t mu = std::numeric_limits<rep_t>::max(); + + static_assert(max_diff_t(mu)/-1 == -max_diff_t(mu)); + static_assert(-max_diff_t(mu)/1 == -max_diff_t(mu)); + static_assert(max_diff_t(mu)>>1 == max_diff_t(mu)/2); + static_assert(-max_diff_t(mu+1) == max_diff_t(mu+1)); + static_assert(-(mu+1) == mu+1); + static_assert((mu+1)<<1 == 0); + static_assert(max_diff_t(mu+1)<<1 == 0); + static_assert(max_diff_t(mu+1)>>1 < 0); + + static_assert(int(max_diff_t(mu+1)) == 0); + static_assert(rep_t(max_diff_t(mu+1)) == 0); + static_assert(int(max_diff_t(mu)) == -1); + static_assert(rep_t(max_diff_t(mu)) == rep_t(-1)); + + static_assert(2*mu+1 > 2*mu); + static_assert(~(2*mu+1) == 0); + static_assert(mu/mu == 1); + static_assert(2*mu > mu); + static_assert(2*mu-mu == mu); + static_assert((2*mu)/mu == 2); + static_assert((2*mu+1)/mu == 2); + static_assert((2*mu-1)/(mu-1) == 2); + static_assert((2*mu-1)/mu == 1); + static_assert((2*mu+-1)/mu == 1); + static_assert(2*mu-1 < 2*mu); + static_assert(2*mu-1 <= 2*mu); + static_assert(2*mu+1 > 2*mu); + static_assert(2*mu+1 >= 2*mu); + static_assert((2*mu)/1 == 2*mu); + static_assert(mu/mu-1 == 0); + static_assert(mu*0 == 0); + static_assert((2*mu-1)*0 == 0); + static_assert((2*mu-1)>>1 == mu-1); + static_assert(mu+-1+1 == mu); + static_assert(mu+1+-1 == mu); + static_assert(mu+1); + static_assert((2*mu)/2 == mu); + static_assert((2*mu)>>1 == mu); + static_assert((mu<<1)>>1 == mu); + static_assert(1/mu == 0); + static_assert(mu/1 == mu); + static_assert(((mu+1)|mu) == -1); + static_assert((mu+1)+(mu+1) < mu+1); + + constexpr max_size_t ou = 1; + constexpr max_diff_t ns = -1; + + static_assert(max_size_t(ns) == -1); + static_assert(-max_diff_t(ou) == -1); + static_assert(-max_diff_t(-ou) == 1); + static_assert(max_size_t(-max_diff_t(-ou)) == 1); + static_assert(ns*ns == max_diff_t(ou)); + static_assert(max_size_t(ns)*max_size_t(ns) == ou); + static_assert(-max_diff_t(0) == max_diff_t(0)); + static_assert(-ou-ou == -2*ou); + + static_assert(int(ns) == -1); + static_assert(rep_t(ns) == rep_t(-1)); + + static_assert(max_size_t() == 0); + static_assert(max_diff_t() == 0); + + auto f = [] (auto a) { a /= a; return a; }; + static_assert(f(max_size_t(5)) == 1); + static_assert(f(max_size_t(-5)) == 1); + static_assert(f(max_diff_t(5)) == 1); + + auto g = [] (auto a) { a >>= a; return a; }; + static_assert(g(max_size_t(5)) == 0); + static_assert(g(max_diff_t(5)) == 0); + + auto h = [] (auto a) { a <<= a; return a; }; + static_assert(h(max_size_t(3)) == 24); + static_assert(h(max_diff_t(3)) == 24); +} + +template<bool signed_p, bool shorten_p> +void +test04() +{ + using hw_type = std::conditional_t<signed_p, signed rep_t, rep_t>; + using max_type = std::conditional_t<signed_p, max_diff_t, max_size_t>; + using shorten_type = std::conditional_t<shorten_p, hw_type, max_type>; + const int hw_type_bit_size = sizeof(hw_type) * __CHAR_BIT__; + const int limit = 1000; + const int log2_limit = 10; + static_assert((1 << log2_limit) >= limit); + const int min = (signed_p ? -limit : 0); + const int max = limit; + for (hw_type i = min; i <= max; i++) + { + bool ok = true; + if (signed_p || shorten_p) + { + ok &= (~i == shorten_type(~max_type(i))); + ok &= (-i == shorten_type(-max_type(i))); + } + for (hw_type j = min; j <= max; j++) + { + ok &= (i*j == shorten_type(max_type(i)*j)); + ok &= (i+j == shorten_type(max_type(i)+j)); + if (j != 0) + { + ok &= (i/j == shorten_type(max_type(i)/j)); + ok &= (i%j == shorten_type(max_type(i)%j)); + } + if (signed_p || shorten_p) + ok &= (i-j == shorten_type(max_type(i)-j)); + ok &= ((i&j) == shorten_type(max_type(i)&j)); + ok &= ((i|j) == shorten_type(max_type(i)|j)); + ok &= ((i^j) == shorten_type(max_type(i)^j)); + if (j >= 0 && j < hw_type(hw_type_bit_size) + && (shorten_p || j < hw_type(hw_type_bit_size) - log2_limit)) + { + ok &= ((i>>j) == shorten_type(max_type(i)>>j)); + ok &= ((i<<j) == shorten_type(max_type(i)<<j)); + } + ok &= (i>j) == (max_type(i) > j); + ok &= (i<j) == (max_type(i) < j); + ok &= (i>=j) == (max_type(i) >= j); + ok &= (i<=j) == (max_type(i) <= j); + ok &= (i==j) == (max_type(i) == j); + ok &= (i!=j) == (max_type(i) != j); + if (!ok) + { + fprintf(stderr, + "Inconsistency found: %d %d %lld %lld\n", + signed_p, shorten_p, (long long)i, (long long)j) ; + VERIFY(0); + } + } + } +} + +template<bool signed_p, bool toggle_base_p> +void +test05() +{ + using hw_type = std::conditional_t<signed_p, signed rep_t, rep_t>; + using max_type = std::conditional_t<signed_p, max_diff_t, max_size_t>; + using base_type = std::conditional_t<toggle_base_p, hw_type, max_type>; + constexpr int hw_type_bit_size = sizeof(hw_type) * __CHAR_BIT__; + constexpr int limit = 1000; + constexpr int log2_limit = 10; + static_assert((1 << log2_limit) >= limit); + const int min = (signed_p ? -limit : 0); + const int max = limit; + for (hw_type i = min; i <= max; i++) + { + bool ok = true; + base_type k; + for (hw_type j = min; j <= max; j++) + { + k = i; k *= j; + ok &= (k == (max_type(i)*j)); + k = i; k += j; + ok &= (k == (max_type(i)+j)); + if (j != 0) + { + k = i; k /= j; + ok &= (k == (max_type(i)/j)); + k = i; k %= j; + ok &= (k == (max_type(i)%j)); + } + if (signed_p) + { + k = i; k -= j; + ok &= (k == (max_type(i)-j)); + } + k = i; k &= j; + ok &= (k == (max_type(i)&j)); + k = i; k |= j; + ok &= (k == (max_type(i)|j)); + k = i; k ^= j; + ok &= (k == (max_type(i)^j)); + if (j >= 0 && j < hw_type(hw_type_bit_size) + && (!toggle_base_p || j < hw_type(hw_type_bit_size) - log2_limit)) + { + k = i; k >>= j; + ok &= (k == (max_type(i)>>j)); + k = i; k <<= j; + ok &= (k == (max_type(i)<<j)); + } + if (!ok) + { + fprintf(stderr, + "Inconsistency found: %d %d %lld %lld\n", + signed_p, toggle_base_p, (long long)i, (long long)j) ; + VERIFY(0); + } + } + } +} + +void +test06() +{ + constexpr max_size_t mu = std::numeric_limits<rep_t>::max(); + const int limit = 1000; + for (int i = -limit; i <= limit; i++) + { + VERIFY( -max_size_t(-i) == i ); + for (int j = i; j <= limit; j++) + { + VERIFY( max_size_t(-i) * max_size_t(-j) == i*j ); + VERIFY( max_size_t(-j) * max_size_t(-i) == j*i ); + VERIFY( rep_t(((mu+1)+i)*((mu+1)+j)) == rep_t(i*j) ); + VERIFY( rep_t(((mu+1)+j)*((mu+1)+i)) == rep_t(j*i) ); + if (i >= 0 && j > 0) + { + auto r = (mu+i)-((mu+i)/j)*j; + VERIFY( r >= 0 && r < j ); + VERIFY( r == (mu+i)%j ); + } + } + } +} + +using std::numeric_limits; + +static_assert(numeric_limits<max_size_t>::is_specialized); +static_assert(!numeric_limits<max_size_t>::is_signed); +static_assert(numeric_limits<max_size_t>::is_integer); +static_assert(numeric_limits<max_size_t>::is_exact); +#if __SIZEOF_INT128__ +static_assert(numeric_limits<max_size_t>::digits == 129); +static_assert(numeric_limits<max_size_t>::digits10 == 38); +#else +static_assert(numeric_limits<max_size_t>::digits == 65); +static_assert(numeric_limits<max_size_t>::digits == 19); +#endif +static_assert(numeric_limits<max_size_t>::min() == 0); +static_assert(numeric_limits<max_size_t>::max() == max_size_t(-1)); +static_assert(numeric_limits<max_size_t>::lowest() + == numeric_limits<max_size_t>::min()); + +static_assert(numeric_limits<max_diff_t>::is_specialized); +static_assert(numeric_limits<max_diff_t>::is_signed); +static_assert(numeric_limits<max_diff_t>::is_integer); +static_assert(numeric_limits<max_diff_t>::is_exact); +#if __SIZEOF_INT128__ +static_assert(numeric_limits<max_diff_t>::digits == 128); +static_assert(numeric_limits<max_diff_t>::digits10 == 38); +static_assert(numeric_limits<max_diff_t>::min() + == -max_diff_t(numeric_limits<unsigned __int128>::max())-1); +static_assert(numeric_limits<max_diff_t>::max() + == numeric_limits<unsigned __int128>::max()); +#else +static_assert(numeric_limits<max_diff_t>::digits == 64); +static_assert(numeric_limits<max_diff_t>::digits == 19); +static_assert(numeric_limits<max_diff_t>::min() + == -max_diff_t(numeric_limits<int64_t>::max())-1); +static_assert(numeric_limits<max_diff_t>::max() + == numeric_limits<int64_t>::max()); +#endif +static_assert(numeric_limits<max_diff_t>::lowest() + == numeric_limits<max_diff_t>::min()); + +int +main() +{ + test01(); + test02(); + test03(); + + test04<false,false>(); + test04<false,true>(); + test04<true,false>(); + test04<true,true>(); + + test05<false,false>(); + test05<false,true>(); + test05<true,false>(); + test05<true,true>(); + + test06(); +}