source: mainline/uspace/lib/cpp/include/impl/random.hpp@ 2fe861d

lfn serial ticket/834-toolchain-update topic/msim-upgrade topic/simplify-dev-export
Last change on this file since 2fe861d was 2fe861d, checked in by Dzejrou <dzejrou@…>, 7 years ago

cpp: moved seeding code to the proper function, constructor now calls seed
  • Property mode set to 100644
File size: 14.4 KB
Line 
1/*
2 * Copyright (c) 2018 Jaroslav Jindrak
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 *
9 * - Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * - Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 * - The name of the author may not be used to endorse or promote products
15 * derived from this software without specific prior written permission.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 */
28
29#ifndef LIBCPP_RANDOM
30#define LIBCPP_RANDOM
31
32#include <cstdlib>
33#include <ctime>
34#include <initializer_list>
35#include <internal/builtins.hpp>
36#include <limits>
37#include <type_traits>
38#include <vector>
39
40/**
41 * Note: Variables with one or two lettered
42 * names here are named after their counterparts in
43 * the standard. If one needs to understand their meaning,
44 * they should seek the mentioned standard section near
45 * the declaration of these variables.
46 * Note: There will be a lot of mathematical expressions in this header.
47 * All of these are taken directly from the standard's requirements
48 * and as such won't be commented here, check the appropriate
49 * sections if you need explanation of these forumulae.
50 */
51
52namespace std
53{
54 namespace aux
55 {
56 /**
57 * This is the minimum requirement imposed by the
58 * standard for a type to qualify as a seed sequence
59 * in overloading resolutions.
60 * (This is because the engines have constructors
61 * that accept sequence and seed and without this
62 * minimal requirements overload resolution would fail.)
63 */
64 template<class Sequence, class ResultType>
65 struct is_seed_sequence
66 : aux::value_is<
67 bool, !is_convertible_v<Sequence, ResultType>
68 >
69 { /* DUMMY BODY */ };
70
71 template<class T, class Engine>
72 inline constexpr bool is_seed_sequence_v = is_seed_sequence<T, Engine>::value;
73 }
74
75 /**
76 * 26.5.3.1, class template linear_congruential_engine:
77 */
78
79 template<class UIntType, UIntType a, UIntType c, UIntType m>
80 class linear_congruential_engine
81 {
82 static_assert(m == 0 || (a < m && c < m));
83
84 public:
85 using result_type = UIntType;
86
87 static constexpr result_type multiplier = a;
88 static constexpr result_type increment = c;
89 static constexpr result_type modulus = m;
90
91 static constexpr min()
92 {
93 return c == 0U ? 1U : 0U;
94 }
95
96 static constexpr max()
97 {
98 return m - 1U;
99 }
100
101 static constexpr result_type default_seed = 1U;
102
103 explicit linear_congruential_engine(result_type s = default_seed)
104 : state_{}
105 {
106 seed(s);
107 }
108
109 linear_congruential_engine(const linear_congruential_engine& other)
110 : state_{other.state_}
111 { /* DUMMY BODY */ }
112
113 template<class Seq>
114 explicit linear_congruential_engine(
115 enable_if_t<aux::is_seed_sequence_v<Seq, result_type>, Seq&> q
116 )
117 : state_{}
118 {
119 seed(q);
120 }
121
122 void seed(result_type s = default_seed)
123 {
124 if (c % modulus_ == 0 && s == 0)
125 state_ = 0;
126 else
127 state_ = s;
128 }
129
130 template<class Seq>
131 void seed(
132 enable_if_t<aux::is_seed_sequence_v<Seq, result_type>, Seq&> q
133 )
134 {
135 size_t k = static_cast<size_t>(aux::ceil(aux::log2(modulus_) / 32));
136 auto arr = new result_type[k + 3];
137
138 q.generate(arr, arr + k + 3);
139
140 result_type s{};
141 for (size_t j = 0; j < k; ++j)
142 s += a[j + 3] * aux::pow2(32U * j);
143 s = s % modulus_;
144
145 seed(s);
146 }
147
148 result_type operator()()
149 {
150 return generate_();
151 }
152
153 void discard(unsigned long long z)
154 {
155 for (unsigned long long i = 0ULL; i < z; ++i)
156 transition_();
157 }
158
159 bool operator==(const linear_congruential_engine& rhs) const
160 {
161 return state_ = rhs.state_;
162 }
163
164 bool operator!=(const linear_congruential_engine& rhs) const
165 {
166 return !(*this == rhs);
167 }
168
169 template<class Char, class Traits>
170 basic_ostream<Char, Traits>& operator<<(basic_ostream<Char, Traits>& os) const
171 {
172 auto flags = os.flags();
173 os.flags(ios_base::dec | ios_base::left);
174
175 os << state_;
176
177 os.flags(flags);
178 return os;
179 }
180
181 template<class Char, class Traits>
182 basic_istream<Char, Traits>& operator>>(basic_istream<Char, Traits>& is) const
183 {
184 auto flags = is.flags();
185 is.flags(ios_base::dec);
186
187 result_type tmp{};
188 if (is >> tmp)
189 state_ = tmp;
190 else
191 is.setstate(ios::failbit);
192
193 is.flags(flags);
194 return is;
195 }
196
197 private:
198 result_type state_;
199
200 static constexpr result_type modulus_ =
201 (m == 0) ? (numeric_limits<result_type>::max() + 1) : m;
202
203 void transition_()
204 {
205 state_ = (a * state_ + c) % modulus_;
206 }
207
208 result_type generate_()
209 {
210 transition_();
211
212 return state_;
213 }
214 };
215
216 /**
217 * 26.5.3.2, class template mersenne_twister_engine:
218 */
219
220 template<
221 class UIntType, size_t w, size_t n, size_t m, size_t r,
222 UIntType a, size_t u, UIntType d, size_t s,
223 UIntType b, size_t t, UIntType c, size_t l, UIntType f
224 >
225 class mersenne_twister_engine;
226
227 /**
228 * 26.5.3.3, class template subtract_with_carry_engine:
229 */
230
231 template<class UIntType, size_t w, size_t s, size_t r>
232 class subtract_with_carry_engine;
233
234 /**
235 * 26.5.4.2, class template discard_block_engine:
236 */
237
238 template<class Engine, size_t p, size_t r>
239 class discard_block_engine;
240
241 /**
242 * 26.5.4.3, class template independent_bits_engine:
243 */
244
245 template<class Engine, size_t w, class UIntType>
246 class independent_bits_engine;
247
248 /**
249 * 26.5.4.4, class template shiffle_order_engine:
250 */
251
252 template<class Engine, size_t k>
253 class shuffle_order_engine;
254
255 /**
256 * 26.5.5, engines and engine adaptors with predefined
257 * parameters:
258 * TODO: check their requirements for testing
259 */
260
261 using minstd_rand0 = linear_congruential_engine<uint_fast32_t, 16807, 0, 2147483647>;
262 using minstd_rand = linear_congruential_engine<uint_fast32_t, 48271, 0, 2147483647>;
263 using mt19937 = mersenne_twister_engine<
264 uint_fast32_t, 32, 624, 397, 31, 0x9908b0df, 11, 0xffffffff, 7,
265 0x9d2c5680, 15, 0xefc60000, 18, 1812433253
266 >;
267 using mt19937_64 = mersenne_twister_engine<
268 uint_fast64_t, 64, 312, 156, 31, 0xb5026f5aa96619e9, 29,
269 0x5555555555555555, 17, 0x71d67fffeda60000, 37, 0xfff7eee000000000,
270 43, 6364136223846793005
271 >;
272 using ranlux24_base = subtract_with_carry_engine<uint_fast32_t, 24, 10, 24>;
273 using ranlux48_base = subtract_with_carry_engine<uint_fast64_t, 48, 5, 12>;
274 using ranlux24 = discard_block_engine<ranlux24_base, 223, 23>;
275 using ranlux48 = discard_block_engine<ranlux48_base, 389, 11>;
276 using knuth_b = shuffle_order_engine<minstd_rand0, 256>;
277
278 using default_random_engine = minstd_rand0;
279
280 /**
281 * 26.5.6, class random_device:
282 */
283
284 class random_device
285 {
286 using result_type = unsigned int;
287
288 static constexpr result_type min()
289 {
290 return numeric_limits<result_type>::min();
291 }
292
293 static constexpr result_type max()
294 {
295 return numeric_limits<result_type>::max();
296 }
297
298 explicit random_device(const string& token = "")
299 {
300 /**
301 * Note: token can be used to choose between
302 * random generators, but HelenOS only
303 * has one :/
304 * Also note that it is implementation
305 * defined how this class generates
306 * random numbers and I decided to use
307 * time seeding with C stdlib random,
308 * - feel free to change it if you know
309 * something better.
310 */
311 hel::srandom(hel::time(nullptr));
312 }
313
314 result_type operator()()
315 {
316 return hel::random();
317 }
318
319 double entropy() const noexcept
320 {
321 return 0.0;
322 }
323
324 random_device(const random_device&) = delete;
325 random_device& operator=(const random_device&) = delete;
326 };
327
328 /**
329 * 26.5.7.1, class seed_seq:
330 */
331
332 class seed_seq
333 {
334 public:
335 using result_type = uint_least32_t;
336
337 seed_seq()
338 : vec_{}
339 { /* DUMMY BODY */ }
340
341 template<class T>
342 seed_seq(initializer_list<T> init)
343 : seed_seq(init.begin(), init.end())
344 { /* DUMMY BODY */ }
345
346 template<class InputIterator>
347 seed_seq(InputIterator first, InputIterator last)
348 : vec_{}
349 {
350 while (first != last)
351 vec_.push_back(*first++ % aux::pow2(32));
352 }
353
354 template<class RandomAccessGenerator>
355 void generate(RandomAccessGenerator first,
356 RandomAccessGenerator last)
357 {
358 if (first == last)
359 return;
360
361 // TODO: research this
362 }
363
364 size_t size() const
365 {
366 return vec_.size();
367 }
368
369 template<class OutputIterator>
370 void param(OutputIterator dest) const
371 {
372 for (const auto& x: vec_)
373 *dest++ = x;
374 }
375
376 seed_seq(const seed_seq&) = delete;
377 seed_seq& operator=(const seed_seq&) = delete;
378
379 private:
380 vector<result_type> vec_;
381 };
382
383 /**
384 * 26.5.7.2, function template generate_canonical:
385 */
386
387 template<class RealType, size_t bits, class URNG>
388 RealType generate_canonical(URNG& g);
389
390 /**
391 * 26.5.8.2.1, class template uniform_int_distribution:
392 */
393
394 template<class IntType = int>
395 class uniform_int_distribution;
396
397 /**
398 * 26.5.8.2.2, class template uniform_real_distribution:
399 */
400
401 template<class RealType = double>
402 class uniform_real_distribution;
403
404 /**
405 * 26.5.8.3.1, class bernoulli_distribution:
406 */
407
408 class bernoulli_distribution;
409
410 /**
411 * 26.5.8.3.2, class template binomial_distribution:
412 */
413
414 template<class IntType = int>
415 class binomial_distribution;
416
417 /**
418 * 26.5.8.3.3, class template geometric_distribution:
419 */
420
421 template<class IntType = int>
422 class geometric_distribution;
423
424 /**
425 * 26.5.8.3.4, class template negative_binomial_distribution:
426 */
427
428 template<class IntType = int>
429 class negative_binomial_distribution;
430
431 /**
432 * 26.5.8.4.1, class template poisson_distribution:
433 */
434
435 template<class IntType = int>
436 class poisson_distribution;
437
438 /**
439 * 26.5.8.4.2, class template exponential_distribution:
440 */
441
442 template<class RealType = double>
443 class exponential_distribution;
444
445 /**
446 * 26.5.8.4.3, class template gamma_distribution:
447 */
448
449 template<class RealType = double>
450 class gamma_distribution;
451
452 /**
453 * 26.5.8.4.4, class template weibull_distribution:
454 */
455
456 template<class RealType = double>
457 class weibull_distribution;
458
459 /**
460 * 26.5.8.4.5, class template extreme_value_distribution:
461 */
462
463 template<class RealType = double>
464 class extreme_value_distribution;
465
466 /**
467 * 26.5.8.5.1, class template normal_distribution:
468 */
469
470 template<class RealType = double>
471 class normal_distribution;
472
473 /**
474 * 26.5.8.5.2, class template lognormal_distribution:
475 */
476
477 template<class RealType = double>
478 class lognormal_distribution;
479
480 /**
481 * 26.5.8.5.3, class template chi_squared_distribution:
482 */
483
484 template<class RealType = double>
485 class chi_squared_distribution;
486
487 /**
488 * 26.5.8.5.4, class template cauchy_distribution:
489 */
490
491 template<class RealType = double>
492 class cauchy_distribution;
493
494 /**
495 * 26.5.8.5.5, class template fisher_f_distribution:
496 */
497
498 template<class RealType = double>
499 class fisher_f_distribution;
500
501 /**
502 * 26.5.8.5.6, class template student_t_distribution:
503 */
504
505 template<class RealType = double>
506 class student_t_distribution;
507
508 /**
509 * 26.5.8.6.1, class template discrete_distribution:
510 */
511
512 template<class IntType = int>
513 class discrete_distribution;
514
515 /**
516 * 26.5.8.6.2, class template piecewise_constant_distribution:
517 */
518
519 template<class RealType = double>
520 class piecewise_constant_distribution;
521
522 /**
523 * 26.5.8.6.3, class template piecewise_linear_distribution:
524 */
525
526 template<class RealType = double>
527 class piecewise_linear_distribution;
528}
529
530#endif
Note: See TracBrowser for help on using the repository browser.