Index: uspace/lib/cpp/include/impl/random.hpp =================================================================== --- uspace/lib/cpp/include/impl/random.hpp (revision 08e16de02993b3ffc66faab58fa31c19aca4a691) +++ uspace/lib/cpp/include/impl/random.hpp (revision 08e16de02993b3ffc66faab58fa31c19aca4a691) @@ -0,0 +1,429 @@ +/* + * Copyright (c) 2018 Jaroslav Jindrak + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef LIBCPP_RANDOM +#define LIBCPP_RANDOM + +#include +#include +#include +#include +#include +#include + +/** + * Note: Variables with one or two lettered + * names here are named after their counterparts in + * the standard. If one needs to understand their meaning, + * they should seek the mentioned standard section near + * the declaration of these variables. + */ + +namespace std +{ + namespace aux + { + /** + * This is the minimum requirement imposed by the + * standard for a type to qualify as a seed sequence + * in overloading resolutions. + * (This is because the engines have constructors + * that accept sequence and seed and without this + * minimal requirements overload resolution would fail.) + */ + template + struct is_seed_sequence + : aux::value_is< + bool, !is_convertible_v + > + { /* DUMMY BODY */ }; + + template + inline constexpr bool is_seed_sequence_v = is_seed_sequence::value; + } + + /** + * 26.5.3.1, class template linear_congruential_engine: + */ + + template + class linear_congruential_engine + { + public: + using result_type = UIntType; + + static constexpr result_type multiplier = a; + static constexpr result_type increment = c; + static constexpr result_type modulus = m; + + static constexpr min() + { + return c == 0U ? 1U : 0U; + } + + static constexpr max() + { + return m - 1U; + } + + static constexpr result_type default_seed = 1U; + + explicit linear_congruential_engine(result_type s = default_seed); + + template + explicit linear_congruential_engine( + enable_if_t, Seq&> q + ); + + void seed(result_type s = default_seed); + + template + void seed( + enable_if_t, Seq&> q + ); + + result_type operator()(); + + void discard(unsigned long long z); + }; + + /** + * 26.5.3.2, class template mersenne_twister_engine: + */ + + template< + class UIntType, size_t w, size_t n, size_t m, size_t r, + UIntType a, size_t u, UIntType d, size_t s, + UIntType b, size_t t, UIntType c, size_t l, UIntType f + > + class mersenne_twister_engine; + + /** + * 26.5.3.3, class template subtract_with_carry_engine: + */ + + template + class subtract_with_carry_engine; + + /** + * 26.5.4.2, class template discard_block_engine: + */ + + template + class discard_block_engine; + + /** + * 26.5.4.3, class template independent_bits_engine: + */ + + template + class independent_bits_engine; + + /** + * 26.5.4.4, class template shiffle_order_engine: + */ + + template + class shuffle_order_engine; + + /** + * 26.5.5, engines and engine adaptors with predefined + * parameters: + * TODO: check their requirements for testing + */ + + using minstd_rand0 = linear_congruential_engine; + using minstd_rand = linear_congruential_engine; + using mt19937 = mersenne_twister_engine< + uint_fast32_t, 32, 624, 397, 31, 0x9908b0df, 11, 0xffffffff, 7, + 0x9d2c5680, 15, 0xefc60000, 18, 1812433253 + >; + using mt19937_64 = mersenne_twister_engine< + uint_fast64_t, 64, 312, 156, 31, 0xb5026f5aa96619e9, 29, + 0x5555555555555555, 17, 0x71d67fffeda60000, 37, 0xfff7eee000000000, + 43, 6364136223846793005 + >; + using ranlux24_base = subtract_with_carry_engine; + using ranlux48_base = subtract_with_carry_engine; + using ranlux24 = discard_block_engine; + using ranlux48 = discard_block_engine; + using knuth_b = shuffle_order_engine; + + using default_random_engine = minstd_rand0; + + /** + * 26.5.6, class random_device: + */ + + class random_device + { + using result_type = unsigned int; + + static constexpr result_type min() + { + return numeric_limits::min(); + } + + static constexpr result_type max() + { + return numeric_limits::max(); + } + + explicit random_device(const string& token = "") + { + /** + * Note: token can be used to choose between + * random generators, but HelenOS only + * has one :/ + * Also note that it is implementation + * defined how this class generates + * random numbers and I decided to use + * time seeding with C stdlib random, + * - feel free to change it if you know + * something better. + */ + hel::srandom(hel::time(nullptr)); + } + + result_type operator()() + { + return hel::random(); + } + + double entropy() const noexcept + { + return 0.0; + } + + random_device(const random_device&) = delete; + random_device& operator=(const random_device&) = delete; + }; + + /** + * 26.5.7.1, class seed_seq: + */ + + class seed_seq + { + public: + using result_type = uint_least32_t; + + seed_seq() + : vec_{} + { /* DUMMY BODY */ } + + template + seed_seq(initializer_list init) + : seed_seq(init.begin(), init.end()) + { /* DUMMY BODY */ } + + template + seed_seq(InputIterator first, InputIterator last) + : vec_{} + { + while (first != last) + vec_.push_back(*first++ % aux::pow2(32)); + } + + template + void generate(RandomAccessGenerator first, + RandomAccessGenerator last) + { + if (first == last) + return; + + // TODO: research this + } + + size_t size() const + { + return vec_.size(); + } + + template + void param(OutputIterator dest) const + { + for (const auto& x: vec_) + *dest++ = x; + } + + seed_seq(const seed_seq&) = delete; + seed_seq& operator=(const seed_seq&) = delete; + + private: + vector vec_; + }; + + /** + * 26.5.7.2, function template generate_canonical: + */ + + template + RealType generate_canonical(URNG& g); + + /** + * 26.5.8.2.1, class template uniform_int_distribution: + */ + + template + class uniform_int_distribution; + + /** + * 26.5.8.2.2, class template uniform_real_distribution: + */ + + template + class uniform_real_distribution; + + /** + * 26.5.8.3.1, class bernoulli_distribution: + */ + + class bernoulli_distribution; + + /** + * 26.5.8.3.2, class template binomial_distribution: + */ + + template + class binomial_distribution; + + /** + * 26.5.8.3.3, class template geometric_distribution: + */ + + template + class geometric_distribution; + + /** + * 26.5.8.3.4, class template negative_binomial_distribution: + */ + + template + class negative_binomial_distribution; + + /** + * 26.5.8.4.1, class template poisson_distribution: + */ + + template + class poisson_distribution; + + /** + * 26.5.8.4.2, class template exponential_distribution: + */ + + template + class exponential_distribution; + + /** + * 26.5.8.4.3, class template gamma_distribution: + */ + + template + class gamma_distribution; + + /** + * 26.5.8.4.4, class template weibull_distribution: + */ + + template + class weibull_distribution; + + /** + * 26.5.8.4.5, class template extreme_value_distribution: + */ + + template + class extreme_value_distribution; + + /** + * 26.5.8.5.1, class template normal_distribution: + */ + + template + class normal_distribution; + + /** + * 26.5.8.5.2, class template lognormal_distribution: + */ + + template + class lognormal_distribution; + + /** + * 26.5.8.5.3, class template chi_squared_distribution: + */ + + template + class chi_squared_distribution; + + /** + * 26.5.8.5.4, class template cauchy_distribution: + */ + + template + class cauchy_distribution; + + /** + * 26.5.8.5.5, class template fisher_f_distribution: + */ + + template + class fisher_f_distribution; + + /** + * 26.5.8.5.6, class template student_t_distribution: + */ + + template + class student_t_distribution; + + /** + * 26.5.8.6.1, class template discrete_distribution: + */ + + template + class discrete_distribution; + + /** + * 26.5.8.6.2, class template piecewise_constant_distribution: + */ + + template + class piecewise_constant_distribution; + + /** + * 26.5.8.6.3, class template piecewise_linear_distribution: + */ + + template + class piecewise_linear_distribution; +} + +#endif Index: uspace/lib/cpp/include/random =================================================================== --- uspace/lib/cpp/include/random (revision 08e16de02993b3ffc66faab58fa31c19aca4a691) +++ uspace/lib/cpp/include/random (revision 08e16de02993b3ffc66faab58fa31c19aca4a691) @@ -0,0 +1,29 @@ +/* + * Copyright (c) 2018 Jaroslav Jindrak + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#include