diff options
| author | singler <singler@138bc75d-0d04-0410-961f-82ee72b054a4> | 2009-10-28 10:04:03 +0000 |
|---|---|---|
| committer | singler <singler@138bc75d-0d04-0410-961f-82ee72b054a4> | 2009-10-28 10:04:03 +0000 |
| commit | 0958f2243324358c2658f74a8a870c55c20d3f10 (patch) | |
| tree | 64e54bb79d451d3556a6bdfea473a74a179f613c /libstdc++-v3 | |
| parent | 12df6aa86fd79a985a9d755e708f552d160aa1ae (diff) | |
| download | gcc-0958f2243324358c2658f74a8a870c55c20d3f10.tar.gz | |
2009-10-28 Johannes Singler <singler@kit.edu>
PR libstdc++/40852
* include/parallel/multiseq_selection.h
(multiseq_partition, multiseq_selection): Avoid intermediate
values exceeding the integer type range for very large inputs.
git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@153648 138bc75d-0d04-0410-961f-82ee72b054a4
Diffstat (limited to 'libstdc++-v3')
| -rw-r--r-- | libstdc++-v3/ChangeLog | 7 | ||||
| -rw-r--r-- | libstdc++-v3/include/parallel/multiseq_selection.h | 28 |
2 files changed, 14 insertions, 21 deletions
diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index daeb4393081..8abe9b9e38f 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,3 +1,10 @@ +2009-10-28 Johannes Singler <singler@kit.edu> + + PR libstdc++/40852 + * include/parallel/multiseq_selection.h + (multiseq_partition, multiseq_selection): Avoid intermediate + values exceeding the integer type range for very large inputs. + 2009-10-26 Paolo Carlini <paolo.carlini@oracle.com> * include/std/chrono (duration<>::duration(const duration<>&)): Fix diff --git a/libstdc++-v3/include/parallel/multiseq_selection.h b/libstdc++-v3/include/parallel/multiseq_selection.h index fdce872c5a1..ac06385b44b 100644 --- a/libstdc++-v3/include/parallel/multiseq_selection.h +++ b/libstdc++-v3/include/parallel/multiseq_selection.h @@ -187,9 +187,6 @@ namespace __gnu_parallel // 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 @@ namespace __gnu_parallel __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,15 +262,11 @@ namespace __gnu_parallel __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) { @@ -442,9 +435,6 @@ namespace __gnu_parallel // 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 @@ namespace __gnu_parallel __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 @@ namespace __gnu_parallel __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) { |