From patchwork Sun Apr 29 23:37:43 2012 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Paolo Carlini X-Patchwork-Id: 155778 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) by ozlabs.org (Postfix) with SMTP id 8D4B8B702C for ; Mon, 30 Apr 2012 09:38:28 +1000 (EST) Comment: DKIM? See http://www.dkim.org DKIM-Signature: v=1; a=rsa-sha1; c=relaxed/relaxed; d=gcc.gnu.org; s=default; x=1336347509; h=Comment: DomainKey-Signature:Received:Received:Received:Received:Received: Received:Received:Message-ID:Date:From:User-Agent:MIME-Version: To:CC:Subject:Content-Type:Mailing-List:Precedence:List-Id: List-Unsubscribe:List-Archive:List-Post:List-Help:Sender: Delivered-To; bh=ecjftw3uQPgmkR+zFYqcZxs1UG8=; b=oyLOB57BCdIM5mZ pE+ZlbYZrG4zATcvItgUe+zqEuSWmXkVElX5RYRP+9oNqEAz2Q+VFBHo/6YGtrO5 2nICV9s2mKnuTuKR0c9cjgTJlyQweq6o/HPBsou7+7IDDSilmCm1Evn/zRPYdf+B JZHu4k8Jkg7qwtvTZiwLrfbdrR8w= Comment: DomainKeys? See http://antispam.yahoo.com/domainkeys DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=default; d=gcc.gnu.org; h=Received:Received:X-SWARE-Spam-Status:X-Spam-Check-By:Received:Received:Received:Received:Received:Message-ID:Date:From:User-Agent:MIME-Version:To:CC:Subject:Content-Type:X-IsSubscribed:Mailing-List:Precedence:List-Id:List-Unsubscribe:List-Archive:List-Post:List-Help:Sender:Delivered-To; b=fbNoM8sR67LZjtOZ7djHowQuHK9I6ceE1HAMhCDqpnBk7oCCjQRwDx1s53WNnQ VvCinrkkiH1QWQIu8sQI1n5UfST8L95HTywXWABoSn1sM3mhVrr9frYBcbp1RDUR 4+0TZgS4TKICScZrVD5X+5V/DTvcuOZJqhqpINhxEXknU=; Received: (qmail 28232 invoked by alias); 29 Apr 2012 23:38:21 -0000 Received: (qmail 28209 invoked by uid 22791); 29 Apr 2012 23:38:20 -0000 X-SWARE-Spam-Status: No, hits=-6.4 required=5.0 tests=AWL, BAYES_00, KHOP_RCVD_UNTRUST, RCVD_IN_DNSWL_HI, RCVD_IN_HOSTKARMA_NO, RCVD_IN_HOSTKARMA_W, T_RP_MATCHES_RCVD X-Spam-Check-By: sourceware.org Received: from rcsinet15.oracle.com (HELO rcsinet15.oracle.com) (148.87.113.117) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Sun, 29 Apr 2012 23:38:06 +0000 Received: from ucsinet22.oracle.com (ucsinet22.oracle.com [156.151.31.94]) by rcsinet15.oracle.com (Sentrion-MTA-4.2.2/Sentrion-MTA-4.2.2) with ESMTP id q3TNc59N015820 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=OK); Sun, 29 Apr 2012 23:38:06 GMT Received: from acsmt357.oracle.com (acsmt357.oracle.com [141.146.40.157]) by ucsinet22.oracle.com (8.14.4+Sun/8.14.4) with ESMTP id q3TNc4so014556 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO); Sun, 29 Apr 2012 23:38:04 GMT Received: from abhmt104.oracle.com (abhmt104.oracle.com [141.146.116.56]) by acsmt357.oracle.com (8.12.11.20060308/8.12.11) with ESMTP id q3TNc4Tg001836; Sun, 29 Apr 2012 18:38:04 -0500 Received: from [192.168.1.4] (/79.52.240.119) by default (Oracle Beehive Gateway v4.0) with ESMTP ; Sun, 29 Apr 2012 16:38:03 -0700 Message-ID: <4F9DD0C7.909@oracle.com> Date: Mon, 30 Apr 2012 01:37:43 +0200 From: Paolo Carlini User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:12.0) Gecko/20120421 Thunderbird/12.0 MIME-Version: 1.0 To: "gcc-patches@gcc.gnu.org" CC: libstdc++ Subject: [v3] Completely fix libstdc++/51795 in mainline X-IsSubscribed: yes Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Hi, contributed by Marc (thanks Again!) and integrated by me. Tested x86_64-linux, multilib. Committed to mainline. Thanks, Paolo. /////////////////////////// 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. Index: include/bits/stl_algobase.h =================================================================== --- include/bits/stl_algobase.h (revision 186943) +++ include/bits/stl_algobase.h (working copy) @@ -975,37 +975,27 @@ /// 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); } Index: include/bits/random.tcc =================================================================== --- include/bits/random.tcc (revision 186943) +++ include/bits/random.tcc (working copy) @@ -41,59 +41,43 @@ { _GLIBCXX_BEGIN_NAMESPACE_VERSION - // General case for x = (ax + c) mod m -- use Schrage's algorithm to - // avoid integer overflow. + // 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. - // // Preconditions: a > 0, m > 0. // - // XXX FIXME: as-is, only works correctly for __m % __a < __m / __a. - // - template - struct _Mod + // Note: only works correctly for __m % __a < __m / __a. + template + _Tp + _Mod<_Tp, __m, __a, __c, false, true>:: + __calc(_Tp __x) { - static _Tp - __calc(_Tp __x) - { - if (__a == 1) - __x %= __m; - else - { - static const _Tp __q = __m / __a; - static const _Tp __r = __m % __a; + 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; - } + _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; - } - }; + 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. - template - struct _Mod<_Tp, __m, __a, __c, true> - { - static _Tp - __calc(_Tp __x) - { return __a * __x + __c; } - }; - template _OutputIterator Index: include/bits/random.h =================================================================== --- include/bits/random.h (revision 186943) +++ include/bits/random.h (working copy) @@ -76,15 +76,78 @@ 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"); + }; - // Dispatch based on modulus value to prevent divide-by-zero compile-time - // errors when m == 0. + 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; + } + }; + 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 @@ 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; Index: testsuite/26_numerics/random/linear_congruential_engine/operators/51795.cc =================================================================== --- testsuite/26_numerics/random/linear_congruential_engine/operators/51795.cc (revision 0) +++ testsuite/26_numerics/random/linear_congruential_engine/operators/51795.cc (revision 0) @@ -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; +}