Replace the existing PRNG (Xorshift31) with (minimal) PCG (XSH-RR variant with 32-bit output, 64-bit state).

PCG is better than many alternatives by many metrics (see www.pcg-random.org) including statistical quality with good speed.

4 files changed, 45 insertions, 16 deletions

diff --git a/core/math/math_funcs.cpp b/core/math/math_funcs.cpp
index 8353aa0ebe..ef8c1ec539 100644
--- a/core/math/math_funcs.cpp
+++ b/core/math/math_funcs.cpp
@@ -31,8 +31,9 @@
 #include "core/os/os.h"
 
 #include "float.h"
-uint32_t Math::default_seed=1;
+#include "pcg.h"
 
+pcg32_random_t Math::default_pcg = {1, PCG_DEFAULT_INC_64};
 
 #define PHI 0x9e3779b9
 
@@ -40,28 +41,26 @@ uint32_t Math::default_seed=1;
 static uint32_t Q[4096];
 #endif
 
-uint32_t Math::rand_from_seed(uint32_t *seed) {
-	// Xorshift31 PRNG
-	if ( *seed == 0 ) *seed = Math::RANDOM_MAX;
-	(*seed) ^= (*seed) << 13;
-	(*seed) ^= (*seed) >> 17;
-	(*seed) ^= (*seed) << 5;
-	return (*seed) & Math::RANDOM_MAX;
+// TODO: we should eventually expose pcg.inc too
+uint32_t Math::rand_from_seed(uint64_t *seed) {
+	pcg32_random_t pcg = {*seed, PCG_DEFAULT_INC_64};
+	uint32_t r = pcg32_random_r(&pcg);
+	*seed = pcg.state;
+	return r;
 }
 
-void Math::seed(uint32_t x) {
-	default_seed=x;
+void Math::seed(uint64_t x) {
+	default_pcg.state=x;
 }
 
 void Math::randomize() {
 
 	OS::Time time = OS::get_singleton()->get_time();
-	seed(OS::get_singleton()->get_ticks_usec()*(time.hour+1)*(time.min+1)*(time.sec+1)*rand()); /* *OS::get_singleton()->get_time().sec); // windows doesn't have get_time(), returns always 0 */
+	seed(OS::get_singleton()->get_ticks_usec()*(time.hour+1)*(time.min+1)*(time.sec+1)*rand()); // TODO: can be simplified.
 }
 
 uint32_t Math::rand() {
-
-	return rand_from_seed(&default_seed);
+	return pcg32_random_r(&default_pcg);
 }
 
 double Math::randf() {
diff --git a/core/math/math_funcs.h b/core/math/math_funcs.h
index 8ce59224ff..e81646b1ca 100644
--- a/core/math/math_funcs.h
+++ b/core/math/math_funcs.h
@@ -31,6 +31,7 @@
 
 #include "typedefs.h"
 #include "math_defs.h"
+#include "pcg.h"
 
 #ifndef NO_MATH_H
 #include <math.h>
@@ -41,8 +42,8 @@
 
 class Math {
 
+	static pcg32_random_t default_pcg;
 
-	static uint32_t default_seed;
 public:
 	Math() {} // useless to instance
 
@@ -150,12 +151,12 @@ public:
 	}
 
 
-	static uint32_t rand_from_seed(uint32_t *seed);
+	static uint32_t rand_from_seed(uint64_t *seed);
 
 	static double ease(double p_x, double p_c);
 	static int step_decimals(double p_step);
 	static double stepify(double p_value,double p_step);
-	static void seed(uint32_t x=0);
+	static void seed(uint64_t x=0);
 	static void randomize();
 	static uint32_t larger_prime(uint32_t p_val);
 	static double dectime(double p_value,double p_amount, double p_step);
diff --git a/core/math/pcg.cpp b/core/math/pcg.cpp
new file mode 100644
index 0000000000..eac3b36d36
--- /dev/null
+++ b/core/math/pcg.cpp
@@ -0,0 +1,15 @@
+// *Really* minimal PCG32 code / (c) 2014 M.E. O'Neill / pcg-random.org
+// Licensed under Apache License 2.0 (NO WARRANTY, etc. see website)
+
+#include "pcg.h"
+
+uint32_t pcg32_random_r(pcg32_random_t* rng)
+{
+    uint64_t oldstate = rng->state;
+    // Advance internal state
+    rng->state = oldstate * 6364136223846793005ULL + (rng->inc|1);
+    // Calculate output function (XSH RR), uses old state for max ILP
+    uint32_t xorshifted = ((oldstate >> 18u) ^ oldstate) >> 27u;
+    uint32_t rot = oldstate >> 59u;
+    return (xorshifted >> rot) | (xorshifted << ((-rot) & 31));
+}
diff --git a/core/math/pcg.h b/core/math/pcg.h
new file mode 100644
index 0000000000..81f4c9770e
--- /dev/null
+++ b/core/math/pcg.h
@@ -0,0 +1,14 @@
+// *Really* minimal PCG32 code / (c) 2014 M.E. O'Neill / pcg-random.org
+// Licensed under Apache License 2.0 (NO WARRANTY, etc. see website)
+
+#ifndef RANDOM_H
+#define RANDOM_H
+
+#include "typedefs.h"
+
+#define PCG_DEFAULT_INC_64 1442695040888963407ULL
+
+typedef struct { uint64_t state;  uint64_t inc; } pcg32_random_t;
+uint32_t pcg32_random_r(pcg32_random_t* rng);
+
+#endif // RANDOM_H