Embedded Template Library 1.0
random.h
Go to the documentation of this file.
1
2
3/******************************************************************************
4The MIT License(MIT)
5
6Embedded Template Library.
7https://github.com/ETLCPP/etl
8https://www.etlcpp.com
9
10Copyright(c) 2017 John Wellbelove
11
12Permission is hereby granted, free of charge, to any person obtaining a copy
13of this software and associated documentation files(the "Software"), to deal
14in the Software without restriction, including without limitation the rights
15to use, copy, modify, merge, publish, distribute, sublicense, and / or sell
16copies of the Software, and to permit persons to whom the Software is
17furnished to do so, subject to the following conditions :
18
19The above copyright notice and this permission notice shall be included in all
20copies or substantial portions of the Software.
21
22THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
23IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
24FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.IN NO EVENT SHALL THE
25AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
26LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
27OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
28SOFTWARE.
29******************************************************************************/
30
31#ifndef ETL_RANDOM_INCLUDED
32#define ETL_RANDOM_INCLUDED
33
34#include "platform.h"
35#include "binary.h"
36
37#include <stdint.h>
38
39namespace etl
40{
41#if defined(ETL_POLYMORPHIC_RANDOM)
42 //***************************************************************************
44 //***************************************************************************
45 class random
46 {
47 public:
48
49 virtual ~random()
50 {
51 }
52
53 virtual void initialise(uint32_t seed) = 0;
54 virtual uint32_t operator()() = 0;
55 virtual uint32_t range(uint32_t low, uint32_t high) = 0;
56 };
57#else
58 //***************************************************************************
61 //***************************************************************************
62 class random
63 {
64 protected:
65 random()
66 {
67 }
68
69 ~random()
70 {
71 }
72 };
73#endif
74
75 //***************************************************************************
79 //***************************************************************************
80 class random_xorshift : public random
81 {
82 public:
83
84 //***************************************************************************
87 //***************************************************************************
89 {
90 // An attempt to come up with a unique non-zero seed,
91 // based on the address of the instance.
92 uintptr_t n = reinterpret_cast<uintptr_t>(this);
93 uint32_t seed = static_cast<uint32_t>(n);
94 initialise(seed);
95 }
96
97 //***************************************************************************
100 //***************************************************************************
101 random_xorshift(uint32_t seed)
102 {
103 initialise(seed);
104 }
105
106 //***************************************************************************
109 //***************************************************************************
110 void initialise(uint32_t seed)
111 {
112 // Add the first four primes to ensure that the seed isn't zero.
113 state[0] = seed + 3;
114 state[1] = seed + 5;
115 state[2] = seed + 7;
116 state[3] = seed + 11;
117 }
118
119 //***************************************************************************
121 //***************************************************************************
122 uint32_t operator()()
123 {
124 uint32_t n = state[3];
125 n ^= n << 11U;
126 n ^= n >> 8U;
127 state[3] = state[2];
128 state[2] = state[1];
129 state[1] = state[0];
130 n ^= state[0];
131 n ^= state[0] >> 19U;
132 state[0] = n;
133
134 return n;
135 }
136
137 //***************************************************************************
139 //***************************************************************************
140 uint32_t range(uint32_t low, uint32_t high)
141 {
142 uint32_t r = high - low + 1UL;
143 uint32_t n = operator()();
144 n %= r;
145 n += low;
146
147 return n;
148 }
149
150 private:
151
152 uint32_t state[4];
153 };
154
155 //***************************************************************************
159 //***************************************************************************
160 class random_lcg : public random
161 {
162 public:
163
164 //***************************************************************************
167 //***************************************************************************
169 {
170 // An attempt to come up with a unique non-zero seed,
171 // based on the address of the instance.
172 uintptr_t n = reinterpret_cast<uintptr_t>(this);
173 uint32_t seed = static_cast<uint32_t>(n);
174 initialise(seed);
175 }
176
177 //***************************************************************************
180 //***************************************************************************
181 random_lcg(uint32_t seed)
182 {
183 initialise(seed);
184 }
185
186 //***************************************************************************
189 //***************************************************************************
190 void initialise(uint32_t seed)
191 {
192 seed = (seed == 0) ? 1 : seed;
193 value = (seed > m) ? m : seed;
194 }
195
196 //***************************************************************************
198 //***************************************************************************
199 uint32_t operator()()
200 {
201 value = (a * value) % m;
202
203 return value;
204 }
205
206 //***************************************************************************
208 //***************************************************************************
209 uint32_t range(uint32_t low, uint32_t high)
210 {
211 uint32_t r = high - low + 1UL;
212 uint32_t n = operator()();
213 n %= r;
214 n += low;
215
216 return n;
217 }
218
219 private:
220
221 static ETL_CONSTANT uint32_t a = 40014U;
222 static ETL_CONSTANT uint32_t m = 2147483563UL;
223
224 uint32_t value;
225 };
226
227 //***************************************************************************
231 //***************************************************************************
232 class random_clcg : public random
233 {
234 public:
235
236 //***************************************************************************
239 //***************************************************************************
241 {
242 // An attempt to come up with a unique non-zero seed,
243 // based on the address of the instance.
244 uintptr_t n = reinterpret_cast<uintptr_t>(this);
245 uint32_t seed = static_cast<uint32_t>(n);
246 initialise(seed);
247 }
248
249 //***************************************************************************
252 //***************************************************************************
253 random_clcg(uint32_t seed)
254 {
255 initialise(seed);
256 }
257
258 //***************************************************************************
261 //***************************************************************************
262 void initialise(uint32_t seed)
263 {
264 seed = (seed == 0) ? 1 : seed;
265 value1 = (seed > m1) ? m1 : seed;
266 value2 = (seed > m1) ? m1 : seed;
267 }
268
269 //***************************************************************************
271 //***************************************************************************
272 uint32_t operator()()
273 {
274 static ETL_CONSTANT uint32_t m = ((m1 > m2) ? m1 : m2);
275
276 value1 = (a1 * value1) % m1;
277 value2 = (a2 * value2) % m2;
278
279 return (value1 + value2) % m;
280 }
281
282 //***************************************************************************
284 //***************************************************************************
285 uint32_t range(uint32_t low, uint32_t high)
286 {
287 uint32_t r = high - low + 1UL;
288 uint32_t n = operator()();
289 n %= r;
290 n += low;
291
292 return n;
293 }
294
295 private:
296
297 static ETL_CONSTANT uint32_t a1 = 40014U;
298 static ETL_CONSTANT uint32_t m1 = 2147483563UL;
299
300 static ETL_CONSTANT uint32_t a2 = 40692U;
301 static ETL_CONSTANT uint32_t m2 = 2147483399UL;
302
303 uint32_t value1;
304 uint32_t value2;
305 };
306
307 //***************************************************************************
312 //***************************************************************************
313 class random_lsfr : public random
314 {
315 public:
316
317 //***************************************************************************
320 //***************************************************************************
322 {
323 // An attempt to come up with a unique non-zero seed,
324 // based on the address of the instance.
325 uintptr_t n = reinterpret_cast<uintptr_t>(this);
326 uint32_t seed = static_cast<uint32_t>(n);
327 initialise(seed);
328 }
329
330 //***************************************************************************
333 //***************************************************************************
334 random_lsfr(uint32_t seed)
335 {
336 initialise(seed);
337 }
338
339 //***************************************************************************
342 //***************************************************************************
343 void initialise(uint32_t seed)
344 {
345 value = seed;
346 }
347
348 //***************************************************************************
350 //***************************************************************************
351 uint32_t operator()()
352 {
353 static ETL_CONSTANT uint32_t polynomial = 0x80200003UL;
354
355 value >>= 1U;
356
357 if ((value & 1UL) == 1UL)
358 {
359 value ^= polynomial;
360 }
361
362 return value;
363 }
364
365 //***************************************************************************
367 //***************************************************************************
368 uint32_t range(uint32_t low, uint32_t high)
369 {
370 uint32_t r = high - low + 1UL;
371 uint32_t n = operator()();
372 n %= r;
373 n += low;
374
375 return n;
376 }
377
378 private:
379
380 uint32_t value;
381 };
382
383 //***************************************************************************
386 //***************************************************************************
387 class random_mwc : public random
388 {
389 public:
390
391 //***************************************************************************
394 //***************************************************************************
396 {
397 // An attempt to come up with a unique non-zero seed,
398 // based on the address of the instance.
399 uintptr_t n = reinterpret_cast<uintptr_t>(this);
400 uint32_t seed = static_cast<uint32_t>(n);
401 initialise(seed);
402 }
403
404 //***************************************************************************
407 //***************************************************************************
408 random_mwc(uint32_t seed)
409 {
410 initialise(seed);
411 }
412
413 //***************************************************************************
416 //***************************************************************************
417 void initialise(uint32_t seed)
418 {
419 value1 = seed;
420 value2 = seed;
421 }
422
423 //***************************************************************************
425 //***************************************************************************
426 uint32_t operator()()
427 {
428 value1 = 36969UL * (value1 & 0xFFFFUL) + (value1 >> 16U);
429 value2 = 18000UL * (value2 & 0xFFFFUL) + (value2 >> 16U);
430
431 return (value1 << 16U) + value2;
432 }
433
434 //***************************************************************************
436 //***************************************************************************
437 uint32_t range(uint32_t low, uint32_t high)
438 {
439 uint32_t r = high - low + 1UL;
440 uint32_t n = operator()();
441 n %= r;
442 n += low;
443
444 return n;
445 }
446
447 private:
448
449 uint32_t value1;
450 uint32_t value2;
451 };
452
453#if ETL_USING_64BIT_TYPES
454 //***************************************************************************
458 //***************************************************************************
459 class random_pcg : public random
460 {
461 public:
462
463 random_pcg()
464 {
465 // An attempt to come up with a unique non-zero seed,
466 // based on the address of the instance.
467 uintptr_t n = reinterpret_cast<uintptr_t>(this);
468 value = static_cast<uint64_t>(n);
469 }
470
471 //***************************************************************************
474 //***************************************************************************
475 random_pcg(uint32_t seed)
476 {
477 initialise(seed);
478 }
479
480 //***************************************************************************
483 //***************************************************************************
484 void initialise(uint32_t seed)
485 {
486 value = uint64_t(seed) | (uint64_t(seed) << 32U);
487 }
488
489 //***************************************************************************
491 //***************************************************************************
492 uint32_t operator()()
493 {
494 uint64_t x = value;
495 unsigned count = (unsigned)(value >> 59U);
496
497 value = (x * multiplier) + increment;
498 x ^= x >> 18U;
499 return etl::rotate_right((uint32_t)(x >> 27U), count);
500 }
501
502 //***************************************************************************
504 //***************************************************************************
505 uint32_t range(uint32_t low, uint32_t high)
506 {
507 uint32_t r = high - low + 1UL;
508 uint32_t n = operator()();
509 n %= r;
510 n += low;
511
512 return n;
513 }
514
515 private:
516
517 static ETL_CONSTANT uint64_t multiplier = 6364136223846793005ULL;
518 static ETL_CONSTANT uint64_t increment = 1ULL;
519
520 uint64_t value;
521 };
522#endif
523
524#if ETL_USING_8BIT_TYPES
525 //***************************************************************************
529 //***************************************************************************
530 template <typename THash>
531 class random_hash : public random
532 {
533 public:
534
535 random_hash()
536 {
537 // An attempt to come up with a unique non-zero seed,
538 // based on the address of the instance.
539 uintptr_t n = reinterpret_cast<uintptr_t>(this);
540 value = static_cast<uint32_t>(n);
541 }
542
543 //***************************************************************************
546 //***************************************************************************
547 random_hash(uint32_t seed)
548 {
549 initialise(seed);
550 }
551
552 //***************************************************************************
555 //***************************************************************************
556 void initialise(uint32_t seed)
557 {
558 value = seed;
559 }
560
561 //***************************************************************************
563 //***************************************************************************
564 uint32_t operator()()
565 {
566 ++value;
567 hash.add(value);
568 return hash.value();
569 }
570
571 //***************************************************************************
573 //***************************************************************************
574 uint32_t range(uint32_t low, uint32_t high)
575 {
576 uint32_t r = high - low + 1UL;
577 uint32_t n = operator()();
578 n %= r;
579 n += low;
580
581 return n;
582 }
583
584 private:
585
586 THash hash;
587 uint8_t value;
588 };
589#endif
590}
591
592#endif
Definition: random.h:233
random_clcg()
Definition: random.h:240
void initialise(uint32_t seed)
Definition: random.h:262
random_clcg(uint32_t seed)
Definition: random.h:253
uint32_t range(uint32_t low, uint32_t high)
Get the next random_clcg number in a specified inclusive range.
Definition: random.h:285
uint32_t operator()()
Get the next random_clcg number.
Definition: random.h:272
Definition: random.h:161
random_lcg(uint32_t seed)
Definition: random.h:181
random_lcg()
Definition: random.h:168
void initialise(uint32_t seed)
Definition: random.h:190
uint32_t operator()()
Get the next random_clcg number.
Definition: random.h:199
uint32_t range(uint32_t low, uint32_t high)
Get the next random_clcg number in a specified inclusive range.
Definition: random.h:209
Definition: random.h:314
random_lsfr(uint32_t seed)
Definition: random.h:334
random_lsfr()
Definition: random.h:321
void initialise(uint32_t seed)
Definition: random.h:343
uint32_t range(uint32_t low, uint32_t high)
Get the next random_lsfr number in a specified inclusive range.
Definition: random.h:368
uint32_t operator()()
Get the next random_lsfr number.
Definition: random.h:351
Definition: random.h:388
random_mwc()
Definition: random.h:395
uint32_t range(uint32_t low, uint32_t high)
Get the next random_lsfr number in a specified inclusive range.
Definition: random.h:437
uint32_t operator()()
Get the next random_lsfr number.
Definition: random.h:426
random_mwc(uint32_t seed)
Definition: random.h:408
void initialise(uint32_t seed)
Definition: random.h:417
Definition: random.h:460
random_pcg(uint32_t seed)
Definition: random.h:475
void initialise(uint32_t seed)
Definition: random.h:484
uint32_t operator()()
Get the next random_lsfr number.
Definition: random.h:492
uint32_t range(uint32_t low, uint32_t high)
Get the next random_lsfr number in a specified inclusive range.
Definition: random.h:505
Definition: random.h:81
uint32_t operator()()
Get the next random_xorshift number.
Definition: random.h:122
random_xorshift(uint32_t seed)
Definition: random.h:101
random_xorshift()
Definition: random.h:88
uint32_t range(uint32_t low, uint32_t high)
Get the next random_xorshift number in a specified inclusive range.
Definition: random.h:140
void initialise(uint32_t seed)
Definition: random.h:110
Definition: random.h:63
ETL_CONSTEXPR14 T rotate_right(T value)
Definition: binary.h:161
bitset_ext
Definition: absolute.h:38