1 /*************************************************************************/
2 /* random_pcg.h */
3 /*************************************************************************/
4 /* This file is part of: */
5 /* GODOT ENGINE */
6 /* https://godotengine.org */
7 /*************************************************************************/
8 /* Copyright (c) 2007-2020 Juan Linietsky, Ariel Manzur. */
9 /* Copyright (c) 2014-2020 Godot Engine contributors (cf. AUTHORS.md). */
10 /* */
11 /* Permission is hereby granted, free of charge, to any person obtaining */
12 /* a copy of this software and associated documentation files (the */
13 /* "Software"), to deal in the Software without restriction, including */
14 /* without limitation the rights to use, copy, modify, merge, publish, */
15 /* distribute, sublicense, and/or sell copies of the Software, and to */
16 /* permit persons to whom the Software is furnished to do so, subject to */
17 /* the following conditions: */
18 /* */
19 /* The above copyright notice and this permission notice shall be */
20 /* included in all copies or substantial portions of the Software. */
21 /* */
22 /* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */
23 /* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */
24 /* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.*/
25 /* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */
26 /* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */
27 /* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */
28 /* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */
29 /*************************************************************************/
30
31 #ifndef RANDOM_PCG_H
32 #define RANDOM_PCG_H
33
34 #include <math.h>
35
36 #include "core/math/math_defs.h"
37
38 #include "thirdparty/misc/pcg.h"
39
40 #if defined(__GNUC__) || (_llvm_has_builtin(__builtin_clz))
41 #define CLZ32(x) __builtin_clz(x)
42 #elif defined(_MSC_VER)
43 #include "intrin.h"
__bsr_clz32(uint32_t x)44 static int __bsr_clz32(uint32_t x) {
45 unsigned long index;
46 _BitScanReverse(&index, x);
47 return 31 - index;
48 }
49 #define CLZ32(x) __bsr_clz32(x)
50 #else
51 #endif
52
53 #if defined(__GNUC__) || (_llvm_has_builtin(__builtin_ldexp) && _llvm_has_builtin(__builtin_ldexpf))
54 #define LDEXP(s, e) __builtin_ldexp(s, e)
55 #define LDEXPF(s, e) __builtin_ldexpf(s, e)
56 #else
57 #include "math.h"
58 #define LDEXP(s, e) ldexp(s, e)
59 #define LDEXPF(s, e) ldexp(s, e)
60 #endif
61
62 class RandomPCG {
63 pcg32_random_t pcg;
64 uint64_t current_seed; // seed with this to get the same state
65 uint64_t current_inc;
66
67 public:
68 static const uint64_t DEFAULT_SEED = 12047754176567800795U;
69 static const uint64_t DEFAULT_INC = PCG_DEFAULT_INC_64;
70 static const uint64_t RANDOM_MAX = 0xFFFFFFFF;
71
72 RandomPCG(uint64_t p_seed = DEFAULT_SEED, uint64_t p_inc = DEFAULT_INC);
73
seed(uint64_t p_seed)74 _FORCE_INLINE_ void seed(uint64_t p_seed) {
75 current_seed = p_seed;
76 pcg32_srandom_r(&pcg, current_seed, current_inc);
77 }
get_seed()78 _FORCE_INLINE_ uint64_t get_seed() { return current_seed; }
79
80 void randomize();
rand()81 _FORCE_INLINE_ uint32_t rand() {
82 current_seed = pcg.state;
83 return pcg32_random_r(&pcg);
84 }
85
86 // Obtaining floating point numbers in [0, 1] range with "good enough" uniformity.
87 // These functions sample the output of rand() as the fraction part of an infinite binary number,
88 // with some tricks applied to reduce ops and branching:
89 // 1. Instead of shifting to the first 1 and connecting random bits, we simply set the MSB and LSB to 1.
90 // Provided that the RNG is actually uniform bit by bit, this should have the exact same effect.
91 // 2. In order to compensate for exponent info loss, we count zeros from another random number,
92 // and just add that to the initial offset.
93 // This has the same probability as counting and shifting an actual bit stream: 2^-n for n zeroes.
94 // For all numbers above 2^-96 (2^-64 for floats), the functions should be uniform.
95 // However, all numbers below that threshold are floored to 0.
96 // The thresholds are chosen to minimize rand() calls while keeping the numbers within a totally subjective quality standard.
97 // If clz or ldexp isn't available, fall back to bit truncation for performance, sacrificing uniformity.
randd()98 _FORCE_INLINE_ double randd() {
99 #if defined(CLZ32)
100 uint32_t proto_exp_offset = rand();
101 if (unlikely(proto_exp_offset == 0)) {
102 return 0;
103 }
104 uint64_t significand = (((uint64_t)rand()) << 32) | rand() | 0x8000000000000001U;
105 return LDEXP((double)significand, -64 - CLZ32(proto_exp_offset));
106 #else
107 #pragma message("RandomPCG::randd - intrinsic clz is not available, falling back to bit truncation")
108 return (double)(((((uint64_t)rand()) << 32) | rand()) & 0x1FFFFFFFFFFFFFU) / (double)0x1FFFFFFFFFFFFFU;
109 #endif
110 }
randf()111 _FORCE_INLINE_ float randf() {
112 #if defined(CLZ32)
113 uint32_t proto_exp_offset = rand();
114 if (unlikely(proto_exp_offset == 0)) {
115 return 0;
116 }
117 return LDEXPF((float)(rand() | 0x80000001), -32 - CLZ32(proto_exp_offset));
118 #else
119 #pragma message("RandomPCG::randf - intrinsic clz is not available, falling back to bit truncation")
120 return (float)(rand() & 0xFFFFFF) / (float)0xFFFFFF;
121 #endif
122 }
123
randfn(double p_mean,double p_deviation)124 _FORCE_INLINE_ double randfn(double p_mean, double p_deviation) {
125 return p_mean + p_deviation * (cos(Math_TAU * randd()) * sqrt(-2.0 * log(randd()))); // Box-Muller transform
126 }
randfn(float p_mean,float p_deviation)127 _FORCE_INLINE_ float randfn(float p_mean, float p_deviation) {
128 return p_mean + p_deviation * (cos(Math_TAU * randf()) * sqrt(-2.0 * log(randf()))); // Box-Muller transform
129 }
130
131 double random(double p_from, double p_to);
132 float random(float p_from, float p_to);
random(int p_from,int p_to)133 real_t random(int p_from, int p_to) { return (real_t)random((real_t)p_from, (real_t)p_to); }
134 };
135
136 #endif // RANDOM_PCG_H
137