1/**************************************************************************/
2/* random_pcg.h */
3/**************************************************************************/
4/* This file is part of: */
5/* GODOT ENGINE */
6/* https://godotengine.org */
7/**************************************************************************/
8/* Copyright (c) 2014-present Godot Engine contributors (see AUTHORS.md). */
9/* Copyright (c) 2007-2014 Juan Linietsky, Ariel Manzur. */
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 "core/math/math_defs.h"
35
36#include "thirdparty/misc/pcg.h"
37
38#include <math.h>
39
40#if defined(__GNUC__)
41#define CLZ32(x) __builtin_clz(x)
42#elif defined(_MSC_VER)
43#include <intrin.h>
44static 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__)
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
62class RandomPCG {
63 pcg32_random_t pcg;
64 uint64_t current_seed = 0; // The seed the current generator state started from.
65 uint64_t current_inc = 0;
66
67public:
68 static const uint64_t DEFAULT_SEED = 12047754176567800795U;
69 static const uint64_t DEFAULT_INC = PCG_DEFAULT_INC_64;
70
71 RandomPCG(uint64_t p_seed = DEFAULT_SEED, uint64_t p_inc = DEFAULT_INC);
72
73 _FORCE_INLINE_ void seed(uint64_t p_seed) {
74 current_seed = p_seed;
75 pcg32_srandom_r(&pcg, current_seed, current_inc);
76 }
77 _FORCE_INLINE_ uint64_t get_seed() { return current_seed; }
78
79 _FORCE_INLINE_ void set_state(uint64_t p_state) { pcg.state = p_state; }
80 _FORCE_INLINE_ uint64_t get_state() const { return pcg.state; }
81
82 void randomize();
83 _FORCE_INLINE_ uint32_t rand() {
84 return pcg32_random_r(&pcg);
85 }
86 _FORCE_INLINE_ uint32_t rand(uint32_t bounds) {
87 return pcg32_boundedrand_r(&pcg, bounds);
88 }
89
90 // Obtaining floating point numbers in [0, 1] range with "good enough" uniformity.
91 // These functions sample the output of rand() as the fraction part of an infinite binary number,
92 // with some tricks applied to reduce ops and branching:
93 // 1. Instead of shifting to the first 1 and connecting random bits, we simply set the MSB and LSB to 1.
94 // Provided that the RNG is actually uniform bit by bit, this should have the exact same effect.
95 // 2. In order to compensate for exponent info loss, we count zeros from another random number,
96 // and just add that to the initial offset.
97 // This has the same probability as counting and shifting an actual bit stream: 2^-n for n zeroes.
98 // For all numbers above 2^-96 (2^-64 for floats), the functions should be uniform.
99 // However, all numbers below that threshold are floored to 0.
100 // The thresholds are chosen to minimize rand() calls while keeping the numbers within a totally subjective quality standard.
101 // If clz or ldexp isn't available, fall back to bit truncation for performance, sacrificing uniformity.
102 _FORCE_INLINE_ double randd() {
103#if defined(CLZ32)
104 uint32_t proto_exp_offset = rand();
105 if (unlikely(proto_exp_offset == 0)) {
106 return 0;
107 }
108 uint64_t significand = (((uint64_t)rand()) << 32) | rand() | 0x8000000000000001U;
109 return LDEXP((double)significand, -64 - CLZ32(proto_exp_offset));
110#else
111#pragma message("RandomPCG::randd - intrinsic clz is not available, falling back to bit truncation")
112 return (double)(((((uint64_t)rand()) << 32) | rand()) & 0x1FFFFFFFFFFFFFU) / (double)0x1FFFFFFFFFFFFFU;
113#endif
114 }
115 _FORCE_INLINE_ float randf() {
116#if defined(CLZ32)
117 uint32_t proto_exp_offset = rand();
118 if (unlikely(proto_exp_offset == 0)) {
119 return 0;
120 }
121 return LDEXPF((float)(rand() | 0x80000001), -32 - CLZ32(proto_exp_offset));
122#else
123#pragma message("RandomPCG::randf - intrinsic clz is not available, falling back to bit truncation")
124 return (float)(rand() & 0xFFFFFF) / (float)0xFFFFFF;
125#endif
126 }
127
128 _FORCE_INLINE_ double randfn(double p_mean, double p_deviation) {
129 double temp = randd();
130 if (temp < CMP_EPSILON) {
131 temp += CMP_EPSILON; // To prevent generating of INF value in log function, resulting to return NaN value from this function.
132 }
133 return p_mean + p_deviation * (cos(Math_TAU * randd()) * sqrt(-2.0 * log(temp))); // Box-Muller transform.
134 }
135 _FORCE_INLINE_ float randfn(float p_mean, float p_deviation) {
136 float temp = randf();
137 if (temp < CMP_EPSILON) {
138 temp += CMP_EPSILON; // To prevent generating of INF value in log function, resulting to return NaN value from this function.
139 }
140 return p_mean + p_deviation * (cos((float)Math_TAU * randf()) * sqrt(-2.0 * log(temp))); // Box-Muller transform.
141 }
142
143 double random(double p_from, double p_to);
144 float random(float p_from, float p_to);
145 int random(int p_from, int p_to);
146};
147
148#endif // RANDOM_PCG_H
149