[PATCH][libstdc++-v3 parallel mode] PR 40852 Avoid overflow for very large inputs

[Johannes Singler-2]

Tested x86_64-unknown-linux-gnu: No regressions

Approved and committed for mainline and gcc-4_4-branch.

2009-10-28  Johannes Singler  <singler@...>

        PR libstdc++/40852
        * include/parallel/multiseq_selection.h
        (multiseq_partition, multiseq_selection):  Avoid intermediate
        values exceeding the integer type range for very large inputs.

Johannes

Index: include/parallel/multiseq_selection.h
===================================================================
--- include/parallel/multiseq_selection.h (revision 153548)
+++ include/parallel/multiseq_selection.h (working copy)
@@ -183,9 +183,6 @@
       // equality iff nmax = 2^k - 1.
       l = (1ULL << r) - 1;
 
-      // From now on, including padding.
-      N = l * m;
-
       for (int i = 0; i < m; i++)
  {
   a[i] = 0;
@@ -210,7 +207,7 @@
  if (n >= ns[i]) //sequence too short, conceptual infinity
   sample.push_back(std::make_pair(S(i)[0] /*dummy element*/, i));
 
-      difference_type localrank = rank * m / N ;
+      difference_type localrank = rank / l;
 
       int j;
       for (j = 0; j < localrank && ((n + 1) <= ns[sample[j].second]); ++j)
@@ -258,15 +255,11 @@
  b[i] -= n + 1;
     }
 
-  difference_type leftsize = 0, total = 0;
+  difference_type leftsize = 0;
   for (int i = 0; i < m; i++)
-    {
       leftsize += a[i] / (n + 1);
-      total += l / (n + 1);
-    }
   
-  difference_type skew = static_cast<difference_type>
-    (static_cast<uint64>(total) * rank / N - leftsize);
+  difference_type skew = rank / (n + 1) - leftsize;
 
   if (skew > 0)
     {
@@ -429,9 +422,6 @@
       // equality iff nmax = 2^k - 1
       l = pow2(r) - 1;
 
-      // From now on, including padding.
-      N = l * m;
-
       for (int i = 0; i < m; ++i)
  {
   a[i] = 0;
@@ -458,7 +448,7 @@
  if (n >= ns[i])
   sample.push_back(std::make_pair(S(i)[0] /*dummy element*/, i));
 
-      difference_type localrank = rank * m / N ;
+      difference_type localrank = rank / l;
 
       int j;
       for (j = 0; j < localrank && ((n + 1) <= ns[sample[j].second]); ++j)
@@ -496,15 +486,11 @@
  b[i] -= n + 1;
     }
 
-  difference_type leftsize = 0, total = 0;
+  difference_type leftsize = 0;
   for (int i = 0; i < m; ++i)
-    {
       leftsize += a[i] / (n + 1);
-      total += l / (n + 1);
-    }
 
-  difference_type skew = ((unsigned long long)total * rank / N
-  - leftsize);
+  difference_type skew = rank / (n + 1) - leftsize;
 
   if (skew > 0)
     {

Index: include/parallel/multiseq_selection.h
===================================================================
--- include/parallel/multiseq_selection.h (revision 152895)
+++ include/parallel/multiseq_selection.h (working copy)
@@ -187,9 +187,6 @@
       // equality iff __nmax = 2^__k - 1.
       __l = (1ULL << __r) - 1;
 
-      // From now on, including padding.
-      __N = __l * __m;
-
       for (int __i = 0; __i < __m; __i++)
         {
           __a[__i] = 0;
@@ -215,7 +212,7 @@
           __sample.push_back(
             std::make_pair(__S(__i)[0] /*__dummy element*/, __i));
 
-      _DifferenceType __localrank = __rank * __m / __N ;
+      _DifferenceType __localrank = __rank / __l;
 
       int __j;
       for (__j = 0;
@@ -265,16 +262,12 @@
                 __b[__i] -= __n + 1;
             }
 
-          _DifferenceType __leftsize = 0, __total = 0;
+          _DifferenceType __leftsize = 0;
           for (int __i = 0; __i < __m; __i++)
-            {
               __leftsize += __a[__i] / (__n + 1);
-              __total += __l / (__n + 1);
-            }
-          
-          _DifferenceType __skew = static_cast<_DifferenceType>
-            (static_cast<uint64_t>(__total) * __rank / __N - __leftsize);
 
+          _DifferenceType __skew = __rank / (__n + 1) - __leftsize;
+
           if (__skew > 0)
             {
               // Move to the left, find smallest.
@@ -442,9 +435,6 @@
       // equality iff __nmax = 2^__k - 1
       __l = pow2(__r) - 1;
 
-      // From now on, including padding.
-      __N = __l * __m;
-
       for (int __i = 0; __i < __m; ++__i)
         {
           __a[__i] = 0;
@@ -472,7 +462,7 @@
           __sample.push_back(
             std::make_pair(__S(__i)[0] /*__dummy element*/, __i));
 
-      _DifferenceType __localrank = __rank * __m / __N ;
+      _DifferenceType __localrank = __rank / __l;
 
       int __j;
       for (__j = 0;
@@ -513,15 +503,11 @@
                 __b[__i] -= __n + 1;
             }
 
-          _DifferenceType __leftsize = 0, __total = 0;
+          _DifferenceType __leftsize = 0;
           for (int __i = 0; __i < __m; ++__i)
-            {
               __leftsize += __a[__i] / (__n + 1);
-              __total += __l / (__n + 1);
-            }
 
-          _DifferenceType __skew = ((unsigned long long)__total * __rank / __N
-                                  - __leftsize);
+          _DifferenceType __skew = __rank / (__n + 1) - __leftsize;
 
           if (__skew > 0)
             {