From abcd2d84c8b9442d5fa5c9dcc03f1d4bad298d6d Mon Sep 17 00:00:00 2001 From: Dan Albert Date: Tue, 10 Sep 2019 21:52:53 -0700 Subject: Fix bug in random. Test: ./run_test.py --bitness 32 Test: ./run_test.py --bitness 64 Test: ./run_test.py --bitness 64 --host Bug: https://bugs.chromium.org/p/chromium/issues/detail?id=994957 Bug: http://b/139690488 Change-Id: I71708114d7fc8ed90c30b4d32b01d3f3aef7600b (cherry picked from commit a1d1caa3d831030ce802ed335a9743180911d553) (cherry picked from commit 819e8133bd777d2270ba19d54fd8fa8ac933a417) --- include/random | 45 ++++++++------- .../rand.dist.bern.geo/eval.pass.cpp | 15 +++++ .../rand.dist.pois.poisson/eval.pass.cpp | 64 ++++++++++++++++++++++ 3 files changed, 103 insertions(+), 21 deletions(-) diff --git a/include/random b/include/random index 724bd0fc2..9b29e14a6 100644 --- a/include/random +++ b/include/random @@ -4593,7 +4593,10 @@ public: template poisson_distribution<_IntType>::param_type::param_type(double __mean) - : __mean_(__mean) + // According to the standard `inf` is a valid input, but it causes the + // distribution to hang, so we replace it with the maximum representable + // mean. + : __mean_(isinf(__mean) ? numeric_limits::max() : __mean) { if (__mean_ < 10) { @@ -4611,7 +4614,7 @@ poisson_distribution<_IntType>::param_type::param_type(double __mean) { __s_ = _VSTD::sqrt(__mean_); __d_ = 6 * __mean_ * __mean_; - __l_ = static_cast(__mean_ - 1.1484); + __l_ = std::trunc(__mean_ - 1.1484); __omega_ = .3989423 / __s_; double __b1_ = .4166667E-1 / __mean_; double __b2_ = .3 * __b1_ * __b1_; @@ -4628,12 +4631,12 @@ template _IntType poisson_distribution<_IntType>::operator()(_URNG& __urng, const param_type& __pr) { - result_type __x; + double __tx; uniform_real_distribution __urd; if (__pr.__mean_ < 10) { - __x = 0; - for (double __p = __urd(__urng); __p > __pr.__l_; ++__x) + __tx = 0; + for (double __p = __urd(__urng); __p > __pr.__l_; ++__tx) __p *= __urd(__urng); } else @@ -4643,19 +4646,19 @@ poisson_distribution<_IntType>::operator()(_URNG& __urng, const param_type& __pr double __u; if (__g > 0) { - __x = static_cast(__g); - if (__x >= __pr.__l_) - return __x; - __difmuk = __pr.__mean_ - __x; + __tx = std::trunc(__g); + if (__tx >= __pr.__l_) + return std::__clamp_to_integral(__tx); + __difmuk = __pr.__mean_ - __tx; __u = __urd(__urng); if (__pr.__d_ * __u >= __difmuk * __difmuk * __difmuk) - return __x; + return std::__clamp_to_integral(__tx); } exponential_distribution __edist; for (bool __using_exp_dist = false; true; __using_exp_dist = true) { double __e; - if (__using_exp_dist || __g < 0) + if (__using_exp_dist || __g <= 0) { double __t; do @@ -4665,31 +4668,31 @@ poisson_distribution<_IntType>::operator()(_URNG& __urng, const param_type& __pr __u += __u - 1; __t = 1.8 + (__u < 0 ? -__e : __e); } while (__t <= -.6744); - __x = __pr.__mean_ + __pr.__s_ * __t; - __difmuk = __pr.__mean_ - __x; + __tx = std::trunc(__pr.__mean_ + __pr.__s_ * __t); + __difmuk = __pr.__mean_ - __tx; __using_exp_dist = true; } double __px; double __py; - if (__x < 10) + if (__tx < 10 && __tx >= 0) { const double __fac[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880}; __px = -__pr.__mean_; - __py = _VSTD::pow(__pr.__mean_, (double)__x) / __fac[__x]; + __py = _VSTD::pow(__pr.__mean_, (double)__tx) / __fac[static_cast(__tx)]; } else { - double __del = .8333333E-1 / __x; + double __del = .8333333E-1 / __tx; __del -= 4.8 * __del * __del * __del; - double __v = __difmuk / __x; + double __v = __difmuk / __tx; if (_VSTD::abs(__v) > 0.25) - __px = __x * _VSTD::log(1 + __v) - __difmuk - __del; + __px = __tx * _VSTD::log(1 + __v) - __difmuk - __del; else - __px = __x * __v * __v * (((((((.1250060 * __v + -.1384794) * + __px = __tx * __v * __v * (((((((.1250060 * __v + -.1384794) * __v + .1421878) * __v + -.1661269) * __v + .2000118) * __v + -.2500068) * __v + .3333333) * __v + -.5) - __del; - __py = .3989423 / _VSTD::sqrt(__x); + __py = .3989423 / _VSTD::sqrt(__tx); } double __r = (0.5 - __difmuk) / __pr.__s_; double __r2 = __r * __r; @@ -4709,7 +4712,7 @@ poisson_distribution<_IntType>::operator()(_URNG& __urng, const param_type& __pr } } } - return __x; + return std::__clamp_to_integral(__tx); } template diff --git a/test/std/numerics/rand/rand.dis/rand.dist.bern/rand.dist.bern.geo/eval.pass.cpp b/test/std/numerics/rand/rand.dis/rand.dist.bern/rand.dist.bern.geo/eval.pass.cpp index 6e6072a4f..3c726a1db 100644 --- a/test/std/numerics/rand/rand.dis/rand.dist.bern/rand.dist.bern.geo/eval.pass.cpp +++ b/test/std/numerics/rand/rand.dis/rand.dist.bern/rand.dist.bern.geo/eval.pass.cpp @@ -29,6 +29,20 @@ sqr(T x) return x * x; } +struct Eng : std::mt19937 { + using Base = std::mt19937; + using Base::Base; +}; + +void test_small_inputs() { + Eng engine; + std::geometric_distribution distribution(5.45361e-311); + for (auto i=0; i < 1000; ++i) { + volatile auto res = distribution(engine); + ((void)res); + } +} + void test1() { @@ -295,4 +309,5 @@ int main() test4(); test5(); test6(); + test_small_inputs(); } diff --git a/test/std/numerics/rand/rand.dis/rand.dist.pois/rand.dist.pois.poisson/eval.pass.cpp b/test/std/numerics/rand/rand.dis/rand.dist.pois/rand.dist.pois.poisson/eval.pass.cpp index 12fcfa354..e7127d773 100644 --- a/test/std/numerics/rand/rand.dis/rand.dist.pois/rand.dist.pois.poisson/eval.pass.cpp +++ b/test/std/numerics/rand/rand.dis/rand.dist.pois/rand.dist.pois.poisson/eval.pass.cpp @@ -29,6 +29,68 @@ sqr(T x) return x * x; } +void test_bad_ranges() { + // Test cases where the mean is around the largest representable integer for + // `result_type`. These cases don't generate valid poisson distributions, but + // at least they don't blow up. + std::mt19937 eng; + + { + std::poisson_distribution distribution(32710.9); + for (int i=0; i < 1000; ++i) { + volatile std::int16_t res = distribution(eng); + ((void)res); + } + } + { + std::poisson_distribution distribution(std::numeric_limits::max()); + for (int i=0; i < 1000; ++i) { + volatile std::int16_t res = distribution(eng); + ((void)res); + } + } + { + std::poisson_distribution distribution( + static_cast(std::numeric_limits::max()) + 10); + for (int i=0; i < 1000; ++i) { + volatile std::int16_t res = distribution(eng); + ((void)res); + } + } + { + std::poisson_distribution distribution( + static_cast(std::numeric_limits::max()) * 2); + for (int i=0; i < 1000; ++i) { + volatile std::int16_t res = distribution(eng); + ((void)res); + } + } + { + // We convert `INF` to `DBL_MAX` otherwise the distribution will hang. + std::poisson_distribution distribution(std::numeric_limits::infinity()); + for (int i=0; i < 1000; ++i) { + volatile std::int16_t res = distribution(eng); + ((void)res); + } + } + { + std::poisson_distribution distribution(0); + for (int i=0; i < 1000; ++i) { + volatile std::int16_t res = distribution(eng); + ((void)res); + } + } + { + // We convert `INF` to `DBL_MAX` otherwise the distribution will hang. + std::poisson_distribution distribution(-100); + for (int i=0; i < 1000; ++i) { + volatile std::int16_t res = distribution(eng); + ((void)res); + } + } +} + + int main() { { @@ -148,4 +210,6 @@ int main() assert(std::abs((skew - x_skew) / x_skew) < 0.01); assert(std::abs((kurtosis - x_kurtosis) / x_kurtosis) < 0.01); } + + test_bad_ranges(); } -- cgit v1.2.3