From cf48c255197fb4aae6bc1acc2eba31f13a3f44b3 Mon Sep 17 00:00:00 2001 From: Marc Glisse Date: Mon, 30 Apr 2012 01:36:09 +0200 Subject: [PATCH] re PR libstdc++/51795 (linear_congruential_engine doesn't work correctly) 2012-04-29 Marc Glisse Paolo Carlini PR libstdc++/51795 * include/bits/stl_algobase.h (__lg<>(_Size)): Remove. (__lg(int), __lg(unsigned), __lg(long), __lg(unsigned long), __lg(long long), __lg(unsigned long long)): Define constexpr. * include/bits/random.h (_Mod<>): Overcome Schrage's algorithm limitations. (__mod): Adjust. (linear_congruential): Remove FIXME static_assert. * include/bits/random.tcc (_Mod<>): Adjust. * testsuite/26_numerics/random/linear_congruential_engine/operators/ 51795.cc: New. Co-Authored-By: Paolo Carlini From-SVN: r186948 --- libstdc++-v3/ChangeLog | 15 ++++ libstdc++-v3/include/bits/random.h | 78 ++++++++++++++++--- libstdc++-v3/include/bits/random.tcc | 78 ++++++++----------- libstdc++-v3/include/bits/stl_algobase.h | 22 ++---- .../operators/51795.cc | 45 +++++++++++ 5 files changed, 165 insertions(+), 73 deletions(-) create mode 100644 libstdc++-v3/testsuite/26_numerics/random/linear_congruential_engine/operators/51795.cc diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index 53d94d5e13db..99be46799d29 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,3 +1,18 @@ +2012-04-29 Marc Glisse + Paolo Carlini + + PR libstdc++/51795 + * include/bits/stl_algobase.h (__lg<>(_Size)): Remove. + (__lg(int), __lg(unsigned), __lg(long), __lg(unsigned long), + __lg(long long), __lg(unsigned long long)): Define constexpr. + * include/bits/random.h (_Mod<>): Overcome Schrage's algorithm + limitations. + (__mod): Adjust. + (linear_congruential): Remove FIXME static_assert. + * include/bits/random.tcc (_Mod<>): Adjust. + * testsuite/26_numerics/random/linear_congruential_engine/operators/ + 51795.cc: New. + 2012-04-29 Jonathan Wakely * include/std/functional (function::function(F)): LWG 2132: Disable diff --git a/libstdc++-v3/include/bits/random.h b/libstdc++-v3/include/bits/random.h index 8f6bf4f7bd5e..4361296bca00 100644 --- a/libstdc++-v3/include/bits/random.h +++ b/libstdc++-v3/include/bits/random.h @@ -76,15 +76,78 @@ _GLIBCXX_END_NAMESPACE_VERSION struct _Shift<_UIntType, __w, true> { static const _UIntType __value = _UIntType(1) << __w; }; - template - struct _Mod; + template + struct _Select_uint_least_t + { + static_assert(__which < 0, /* needs to be dependent */ + "sorry, would be too much trouble for a slow result"); + }; + + template + struct _Select_uint_least_t<__s, 4> + { typedef unsigned int type; }; + + template + struct _Select_uint_least_t<__s, 3> + { typedef unsigned long type; }; + + template + struct _Select_uint_least_t<__s, 2> + { typedef unsigned long long type; }; + +#ifdef _GLIBCXX_USE_INT128 + template + struct _Select_uint_least_t<__s, 1> + { typedef unsigned __int128 type; }; +#endif + + // Assume a != 0, a < m, c < m, x < m. + template= __m - 1), + bool __schrage_ok = __m % __a < __m / __a> + struct _Mod + { + typedef typename _Select_uint_least_t::type _Tp2; + static _Tp + __calc(_Tp __x) + { return static_cast<_Tp>((_Tp2(__a) * __x + __c) % __m); } + }; + + // Schrage. + template + struct _Mod<_Tp, __m, __a, __c, false, true> + { + static _Tp + __calc(_Tp __x); + }; + + // Special cases: + // - for m == 2^n or m == 0, unsigned integer overflow is safe. + // - a * (m - 1) + c fits in _Tp, there is no overflow. + template + struct _Mod<_Tp, __m, __a, __c, true, __s> + { + static _Tp + __calc(_Tp __x) + { + _Tp __res = __a * __x + __c; + if (__m) + __res %= __m; + return __res; + } + }; - // Dispatch based on modulus value to prevent divide-by-zero compile-time - // errors when m == 0. template inline _Tp __mod(_Tp __x) - { return _Mod<_Tp, __m, __a, __c, __m == 0>::__calc(__x); } + { return _Mod<_Tp, __m, __a, __c>::__calc(__x); } /* * An adaptor class for converting the output of any Generator into @@ -174,11 +237,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION static_assert(__m == 0u || (__a < __m && __c < __m), "template argument substituting __m out of bounds"); - // XXX FIXME: - // _Mod::__calc should handle correctly __m % __a >= __m / __a too. - static_assert(__m % __a < __m / __a, - "sorry, not implemented yet: try a smaller 'a' constant"); - public: /** The type of the generated random value. */ typedef _UIntType result_type; diff --git a/libstdc++-v3/include/bits/random.tcc b/libstdc++-v3/include/bits/random.tcc index 5da353f8bd49..f7064c4e224c 100644 --- a/libstdc++-v3/include/bits/random.tcc +++ b/libstdc++-v3/include/bits/random.tcc @@ -41,58 +41,42 @@ namespace std _GLIBCXX_VISIBILITY(default) { _GLIBCXX_BEGIN_NAMESPACE_VERSION - // General case for x = (ax + c) mod m -- use Schrage's algorithm to - // avoid integer overflow. - // - // Because a and c are compile-time integral constants the compiler - // kindly elides any unreachable paths. + // General case for x = (ax + c) mod m -- use Schrage's algorithm + // to avoid integer overflow. // // Preconditions: a > 0, m > 0. // - // XXX FIXME: as-is, only works correctly for __m % __a < __m / __a. - // - template - struct _Mod - { - static _Tp - __calc(_Tp __x) - { - if (__a == 1) - __x %= __m; - else - { - static const _Tp __q = __m / __a; - static const _Tp __r = __m % __a; - - _Tp __t1 = __a * (__x % __q); - _Tp __t2 = __r * (__x / __q); - if (__t1 >= __t2) - __x = __t1 - __t2; - else - __x = __m - __t2 + __t1; - } - - if (__c != 0) - { - const _Tp __d = __m - __x; - if (__d > __c) - __x += __c; - else - __x = __c - __d; - } - return __x; - } - }; - - // Special case for m == 0 -- use unsigned integer overflow as modulo - // operator. + // Note: only works correctly for __m % __a < __m / __a. template - struct _Mod<_Tp, __m, __a, __c, true> + _Tp + _Mod<_Tp, __m, __a, __c, false, true>:: + __calc(_Tp __x) { - static _Tp - __calc(_Tp __x) - { return __a * __x + __c; } - }; + if (__a == 1) + __x %= __m; + else + { + static const _Tp __q = __m / __a; + static const _Tp __r = __m % __a; + + _Tp __t1 = __a * (__x % __q); + _Tp __t2 = __r * (__x / __q); + if (__t1 >= __t2) + __x = __t1 - __t2; + else + __x = __m - __t2 + __t1; + } + + if (__c != 0) + { + const _Tp __d = __m - __x; + if (__d > __c) + __x += __c; + else + __x = __c - __d; + } + return __x; + } template diff --git a/libstdc++-v3/include/bits/stl_algobase.h b/libstdc++-v3/include/bits/stl_algobase.h index 1ccf8604f5f8..a48cf9ada6db 100644 --- a/libstdc++-v3/include/bits/stl_algobase.h +++ b/libstdc++-v3/include/bits/stl_algobase.h @@ -975,37 +975,27 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION /// This is a helper function for the sort routines and for random.tcc. // Precondition: __n > 0. - template - inline _Size - __lg(_Size __n) - { - _Size __k; - for (__k = 0; __n != 0; __n >>= 1) - ++__k; - return __k - 1; - } - - inline int + inline _GLIBCXX_CONSTEXPR int __lg(int __n) { return sizeof(int) * __CHAR_BIT__ - 1 - __builtin_clz(__n); } - inline unsigned + inline _GLIBCXX_CONSTEXPR unsigned __lg(unsigned __n) { return sizeof(int) * __CHAR_BIT__ - 1 - __builtin_clz(__n); } - inline long + inline _GLIBCXX_CONSTEXPR long __lg(long __n) { return sizeof(long) * __CHAR_BIT__ - 1 - __builtin_clzl(__n); } - inline unsigned long + inline _GLIBCXX_CONSTEXPR unsigned long __lg(unsigned long __n) { return sizeof(long) * __CHAR_BIT__ - 1 - __builtin_clzl(__n); } - inline long long + inline _GLIBCXX_CONSTEXPR long long __lg(long long __n) { return sizeof(long long) * __CHAR_BIT__ - 1 - __builtin_clzll(__n); } - inline unsigned long long + inline _GLIBCXX_CONSTEXPR unsigned long long __lg(unsigned long long __n) { return sizeof(long long) * __CHAR_BIT__ - 1 - __builtin_clzll(__n); } diff --git a/libstdc++-v3/testsuite/26_numerics/random/linear_congruential_engine/operators/51795.cc b/libstdc++-v3/testsuite/26_numerics/random/linear_congruential_engine/operators/51795.cc new file mode 100644 index 000000000000..a626df0eae39 --- /dev/null +++ b/libstdc++-v3/testsuite/26_numerics/random/linear_congruential_engine/operators/51795.cc @@ -0,0 +1,45 @@ +// { dg-options "-std=gnu++11" } +// { dg-require-cstdint "" } +// +// Copyright (C) 2012 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 +// . + +// 26.5.3.1 class template linear_congruential_engine [rand.eng.lcong] + +#include +#include + +void test01() +{ + bool test __attribute__((unused)) = true; + + typedef std::linear_congruential_engine engine; + engine eng(1103527590ULL); + + for (unsigned it = 0; it < 1000; ++it) + { + std::uint64_t num = eng(); + VERIFY( (num >= eng.min() && num <= eng.max()) ); + } +} + +int main() +{ + test01(); + return 0; +} -- 2.39.5