From patchwork Sat Apr 14 22:32:16 2012
Content-Type: text/plain; charset="utf-8"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Subject: [v3] libstdc++/52699
From: Paolo Carlini <paolo.carlini@oracle.com>
X-Patchwork-Id: 152571
Message-Id: <4F89FAF0.6020200@oracle.com>
To: "gcc-patches@gcc.gnu.org" <gcc-patches@gcc.gnu.org>
Cc: libstdc++ <libstdc++@gcc.gnu.org>
Date: Sun, 15 Apr 2012 00:32:16 +0200

Hi,

this is what I'm going to commit to mainline (and likely 4.7.1 too) to 
solve a number of issues affecting the implementation of 
independent_bits_engine::operator()() as originally contributed: 
essentially we want to be very careful with overflows (+ other lesser 
issues and small optimizations). Many thanks to Marc Glisse for off-line 
reviewing and helping over the last day or so!!

Tested x86_64-linux multilib.

Paolo.

////////////////////////
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.


Index: include/bits/stl_algobase.h
===================================================================
--- include/bits/stl_algobase.h	(revision 186448)
+++ include/bits/stl_algobase.h	(working copy)
@@ -989,14 +989,26 @@
   __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 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 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
Index: include/bits/random.tcc
===================================================================
--- include/bits/random.tcc	(revision 186448)
+++ include/bits/random.tcc	(working copy)
@@ -730,40 +730,65 @@
     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;
-	  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)
 	{
-	  result_type __u;
+	  __ctype __u;
 	  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)
 	{
-	  result_type __u;
+	  __ctype __u;
 	  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;
     }
@@ -840,12 +865,11 @@
       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::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();