From 31dfaff3b395a19f23bb1010bfcec67452efe02d Mon Sep 17 00:00:00 2001 From: zoecarver Date: Tue, 10 Nov 2020 18:23:22 -0800 Subject: [PATCH] [libc++] Change requirements on linear_congruential_engine. This patch changes how linear_congruential_engine picks its randomization algorithm. It adds two restrictions, `_OverflowOK` and `_SchrageOK`. `_OverflowOK` means that m is a power of two so using the classic `(a * x + c) % m` will create a meaningless overflow. The second checks that Schrage's algorithm will produce results that are in bounds of min and max. This patch fixes https://llvm.org/PR27839. Differential Revision: D65041 --- libcxx/include/random | 19 +++++- .../rand/rand.eng/rand.eng.lcong/alg.pass.cpp | 69 ++++++++++++++++++++++ .../rand/rand.eng/rand.eng.lcong/params.fail.cpp | 31 ++++++++++ 3 files changed, 118 insertions(+), 1 deletion(-) create mode 100644 libcxx/test/std/numerics/rand/rand.eng/rand.eng.lcong/alg.pass.cpp create mode 100644 libcxx/test/std/numerics/rand/rand.eng/rand.eng.lcong/params.fail.cpp diff --git a/libcxx/include/random b/libcxx/include/random index 9ba1693..32f9148 100644 --- a/libcxx/include/random +++ b/libcxx/include/random @@ -1668,7 +1668,23 @@ struct __is_seed_sequence template (_Mp-__c)/__a)> + bool _MightOverflow = (__a != 0 && __m != 0 && __m-1 > (_Mp-__c)/__a), + bool _OverflowOK = ((__m|__m-1) > __m), // m = 2^n + bool _SchrageOK = (__a != 0 && __m != 0 && __m % __a <= __m / __a)> // r <= q +struct __lce_alg_picker +{ + static_assert(__a != 0 || __m != 0 || !_MightOverflow || _OverflowOK || _SchrageOK, + "The current values of a, c, and m cannot generate a number " + "within bounds of linear_congruential_engine."); + + static _LIBCPP_CONSTEXPR const bool __use_schrage = _MightOverflow && + !_OverflowOK && + _SchrageOK; +}; + +template ::__use_schrage> struct __lce_ta; // 64 @@ -1842,6 +1858,7 @@ private: static_assert(__m == 0 || __a < __m, "linear_congruential_engine invalid parameters"); static_assert(__m == 0 || __c < __m, "linear_congruential_engine invalid parameters"); + static_assert(_VSTD::is_unsigned<_UIntType>::value, "_UIntType must be unsigned type"); public: static _LIBCPP_CONSTEXPR const result_type _Min = __c == 0u ? 1u: 0u; static _LIBCPP_CONSTEXPR const result_type _Max = __m - 1u; diff --git a/libcxx/test/std/numerics/rand/rand.eng/rand.eng.lcong/alg.pass.cpp b/libcxx/test/std/numerics/rand/rand.eng/rand.eng.lcong/alg.pass.cpp new file mode 100644 index 0000000..77b7c57 --- /dev/null +++ b/libcxx/test/std/numerics/rand/rand.eng/rand.eng.lcong/alg.pass.cpp @@ -0,0 +1,69 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +// + +// template +// class linear_congruential_engine; + +// result_type operator()(); + +#include +#include + +#include "test_macros.h" + +int main(int, char**) +{ + typedef unsigned long long T; + + // m might overflow, but the overflow is OK so it shouldn't use schrage's algorithm + typedef std::linear_congruential_engine E1; + E1 e1; + // make sure the right algorithm was used + assert(e1() == 25214903918); + assert(e1() == 205774354444503); + assert(e1() == 158051849450892); + // make sure result is in bounds + assert(e1() < (1ull<<48)); + assert(e1() < (1ull<<48)); + assert(e1() < (1ull<<48)); + assert(e1() < (1ull<<48)); + assert(e1() < (1ull<<48)); + + // m might overflow. The overflow is not OK and result will be in bounds + // so we should use shrage's algorithm + typedef std::linear_congruential_engine E2; + E2 e2; + // make sure shrage's algorithm is used (it would be 0s otherwise) + assert(e2() == 4); + assert(e2() == 16); + assert(e2() == 64); + // make sure result is in bounds + assert(e2() < (1ull<<48) + 1); + assert(e2() < (1ull<<48) + 1); + assert(e2() < (1ull<<48) + 1); + assert(e2() < (1ull<<48) + 1); + assert(e2() < (1ull<<48) + 1); + + // m will not overflow so we should not use shrage's algorithm + typedef std::linear_congruential_engine E3; + E3 e3; + // make sure the correct algorithm was used + assert(e3() == 2); + assert(e3() == 3); + assert(e3() == 4); + // make sure result is in bounds + assert(e3() < (1ull<<48)); + assert(e3() < (1ull<<48)); + assert(e3() < (1ull<<48)); + assert(e3() < (1ull<<48)); + assert(e2() < (1ull<<48)); + + return 0; +} \ No newline at end of file diff --git a/libcxx/test/std/numerics/rand/rand.eng/rand.eng.lcong/params.fail.cpp b/libcxx/test/std/numerics/rand/rand.eng/rand.eng.lcong/params.fail.cpp new file mode 100644 index 0000000..c325b77 --- /dev/null +++ b/libcxx/test/std/numerics/rand/rand.eng/rand.eng.lcong/params.fail.cpp @@ -0,0 +1,31 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +// + +// template +// class linear_congruential_engine; + +// requirements on parameters + +#include + +int main(int, char**) +{ + typedef unsigned long long T; + + // expected-error@random:* {{static_assert failed due to requirement '1ULL == 0 || 1ULL < 1ULL' "linear_congruential_engine invalid parameters"}} + std::linear_congruential_engine e2; + // expected-error@random:* {{static_assert failed due to requirement '1ULL == 0 || 1ULL < 1ULL' "linear_congruential_engine invalid parameters"}} + std::linear_congruential_engine e3; + std::linear_congruential_engine e4; + // expected-error@random:* {{static_assert failed due to requirement 'std::__1::is_unsigned::value' "_UIntType must be unsigned type"}} + std::linear_congruential_engine e5; + + return 0; +} \ No newline at end of file -- 2.7.4