2012-04-14 Paolo Carlini <paolo.carlini@oracle.com>

	PR libstdc++/52699
	* include/bits/random.tcc (independent_bits_engine<>::operator()())
	Avoid various overflows; use common_type on result_type and
	_RandomNumberEngine::result_type; avoid floating point computations;
	other smaller tweaks.

	* include/bits/random.tcc (uniform_int_distribution<>::operator())
	Use common_type; assume _UniformRandomNumberGenerator::result_type
	unsigned; tidy.

	* include/bits/stl_algobase.h (__lg(unsigned), __lg(unsigned long),
	__lg(unsigned long long)): Add.

git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/branches/gcc-4_7-branch@186461 138bc75d-0d04-0410-961f-82ee72b054a4

diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog
index 7355647..bfe1995 100644 (file)
--- a/libstdc++-v3/ChangeLog
+++ b/libstdc++-v3/ChangeLog
@@ -1,3 +1,18 @@
+2012-04-14  Paolo Carlini  <paolo.carlini@oracle.com>
+
+       PR libstdc++/52699
+       * include/bits/random.tcc (independent_bits_engine<>::operator()())
+       Avoid various overflows; use common_type on result_type and
+       _RandomNumberEngine::result_type; avoid floating point computations;
+       other smaller tweaks.
+
+       * include/bits/random.tcc (uniform_int_distribution<>::operator())
+       Use common_type; assume _UniformRandomNumberGenerator::result_type
+       unsigned; tidy.
+
+       * include/bits/stl_algobase.h (__lg(unsigned), __lg(unsigned long),
+       __lg(unsigned long long)): Add.
+

 2012-04-13  Paolo Carlini  <paolo.carlini@oracle.com>
 
        * include/debug/safe_iterator.h (_BeforeBeginHelper<>::
 2012-04-13  Paolo Carlini  <paolo.carlini@oracle.com>
 
        * include/debug/safe_iterator.h (_BeforeBeginHelper<>::

diff --git a/libstdc++-v3/include/bits/random.tcc b/libstdc++-v3/include/bits/random.tcc
index d55b518..5da353f 100644 (file)
--- a/libstdc++-v3/include/bits/random.tcc
+++ b/libstdc++-v3/include/bits/random.tcc
@@ -730,40 +730,65 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     independent_bits_engine<_RandomNumberEngine, __w, _UIntType>::
     operator()()
     {
     independent_bits_engine<_RandomNumberEngine, __w, _UIntType>::
     operator()()
     {

-      const long double __r = static_cast<long double>(_M_b.max())
-                           - static_cast<long double>(_M_b.min()) + 1.0L;
-      const result_type __m = std::log(__r) / std::log(2.0L);
-      result_type __n, __n0, __y0, __y1, __s0, __s1;
+      typedef typename _RandomNumberEngine::result_type _Eresult_type;
+      const _Eresult_type __r
+       = (_M_b.max() - _M_b.min() < std::numeric_limits<_Eresult_type>::max()
+          ? _M_b.max() - _M_b.min() + 1 : 0);
+      const unsigned __edig = std::numeric_limits<_Eresult_type>::digits;
+      const unsigned __m = __r ? std::__lg(__r) : __edig;
+
+      typedef typename std::common_type<_Eresult_type, result_type>::type
+       __ctype;
+      const unsigned __cdig = std::numeric_limits<__ctype>::digits;
+
+      unsigned __n, __n0;
+      __ctype __s0, __s1, __y0, __y1;
+

       for (size_t __i = 0; __i < 2; ++__i)
        {
          __n = (__w + __m - 1) / __m + __i;
          __n0 = __n - __w % __n;
       for (size_t __i = 0; __i < 2; ++__i)
        {
          __n = (__w + __m - 1) / __m + __i;
          __n0 = __n - __w % __n;

-         const result_type __w0 = __w / __n;
-         const result_type __w1 = __w0 + 1;
-         __s0 = result_type(1) << __w0;
-         __s1 = result_type(1) << __w1;
-         __y0 = __s0 * (__r / __s0);
-         __y1 = __s1 * (__r / __s1);
-         if (__r - __y0 <= __y0 / __n)
+         const unsigned __w0 = __w / __n;  // __w0 <= __m
+
+         __s0 = 0;
+         __s1 = 0;
+         if (__w0 < __cdig)
+           {
+             __s0 = __ctype(1) << __w0;
+             __s1 = __s0 << 1;
+           }
+
+         __y0 = 0;
+         __y1 = 0;
+         if (__r)
+           {
+             __y0 = __s0 * (__r / __s0);
+             if (__s1)
+               __y1 = __s1 * (__r / __s1);
+
+             if (__r - __y0 <= __y0 / __n)
+               break;
+           }
+         else

            break;
        }
 
       result_type __sum = 0;
       for (size_t __k = 0; __k < __n0; ++__k)
        {
            break;
        }
 
       result_type __sum = 0;
       for (size_t __k = 0; __k < __n0; ++__k)
        {

-         result_type __u;
+         __ctype __u;

          do
            __u = _M_b() - _M_b.min();
          do
            __u = _M_b() - _M_b.min();

-         while (__u >= __y0);
-         __sum = __s0 * __sum + __u % __s0;
+         while (__y0 && __u >= __y0);
+         __sum = __s0 * __sum + (__s0 ? __u % __s0 : __u);

        }
       for (size_t __k = __n0; __k < __n; ++__k)
        {
        }
       for (size_t __k = __n0; __k < __n; ++__k)
        {

-         result_type __u;
+         __ctype __u;

          do
            __u = _M_b() - _M_b.min();
          do
            __u = _M_b() - _M_b.min();

-         while (__u >= __y1);
-         __sum = __s1 * __sum + __u % __s1;
+         while (__y1 && __u >= __y1);
+         __sum = __s1 * __sum + (__s1 ? __u % __s1 : __u);

        }
       return __sum;
     }
        }
       return __sum;
     }


@@ -840,12 +865,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       operator()(_UniformRandomNumberGenerator& __urng,
                 const param_type& __param)
       {
       operator()(_UniformRandomNumberGenerator& __urng,
                 const param_type& __param)
       {

-       typedef typename std::make_unsigned<typename
-         _UniformRandomNumberGenerator::result_type>::type __urngtype;
+       typedef typename _UniformRandomNumberGenerator::result_type
+         _Gresult_type;

        typedef typename std::make_unsigned<result_type>::type __utype;
        typedef typename std::make_unsigned<result_type>::type __utype;

-       typedef typename std::conditional<(sizeof(__urngtype)
-                                          > sizeof(__utype)),
-         __urngtype, __utype>::type __uctype;
+       typedef typename std::common_type<_Gresult_type, __utype>::type
+         __uctype;

 
        const __uctype __urngmin = __urng.min();
        const __uctype __urngmax = __urng.max();
 
        const __uctype __urngmin = __urng.min();
        const __uctype __urngmax = __urng.max();

diff --git a/libstdc++-v3/include/bits/stl_algobase.h b/libstdc++-v3/include/bits/stl_algobase.h
index a002461..5cee10a 100644 (file)
--- a/libstdc++-v3/include/bits/stl_algobase.h
+++ b/libstdc++-v3/include/bits/stl_algobase.h
@@ -982,14 +982,26 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
   __lg(int __n)
   { return sizeof(int) * __CHAR_BIT__  - 1 - __builtin_clz(__n); }
 
   __lg(int __n)
   { return sizeof(int) * __CHAR_BIT__  - 1 - __builtin_clz(__n); }
 

+  inline unsigned
+  __lg(unsigned __n)
+  { return sizeof(int) * __CHAR_BIT__  - 1 - __builtin_clz(__n); }
+

   inline long
   __lg(long __n)
   { return sizeof(long) * __CHAR_BIT__ - 1 - __builtin_clzl(__n); }
 
   inline long
   __lg(long __n)
   { return sizeof(long) * __CHAR_BIT__ - 1 - __builtin_clzl(__n); }
 

+  inline unsigned long
+  __lg(unsigned long __n)
+  { return sizeof(long) * __CHAR_BIT__ - 1 - __builtin_clzl(__n); }
+

   inline long long
   __lg(long long __n)
   { return sizeof(long long) * __CHAR_BIT__ - 1 - __builtin_clzll(__n); }
 
   inline long long
   __lg(long long __n)
   { return sizeof(long long) * __CHAR_BIT__ - 1 - __builtin_clzll(__n); }
 

+  inline unsigned long long
+  __lg(unsigned long long __n)
+  { return sizeof(long long) * __CHAR_BIT__ - 1 - __builtin_clzll(__n); }
+

 _GLIBCXX_END_NAMESPACE_VERSION
 
 _GLIBCXX_BEGIN_NAMESPACE_ALGO
 _GLIBCXX_END_NAMESPACE_VERSION
 
 _GLIBCXX_BEGIN_NAMESPACE_ALGO