[Scummvm-git-logs] scummvm master -> 0992fa9c3b8f68e5affa93308ff6dafe9d77ac78

[bluegr]

This automated email contains information about 1 new commit which have been
pushed to the 'scummvm' repo located at https://github.com/scummvm/scummvm .

Summary:
0992fa9c3b COMMON: Change PRNG Function to Xorshift* (#3341)


Commit: 0992fa9c3b8f68e5affa93308ff6dafe9d77ac78
    https://github.com/scummvm/scummvm/commit/0992fa9c3b8f68e5affa93308ff6dafe9d77ac78
Author: TehGelly (itsmanofpopsicle at gmail.com)
Date: 2021-09-09T21:46:08+03:00

Commit Message:
COMMON: Change PRNG Function to Xorshift* (#3341)

The old RNG method had non-standard periods, ranging from some seeds looping on themselves (seed = 1184201285) to some seeds having periods as low as 11 or 48, as listed in https://github.com/scummvm/scummvm/pull/3340. This is a problem even for games that run the RNG once a frame, as the possibilities for random events is greatly reduced should the initial seed be in one of these sets of small periods.

Xorshift* is a standard, fast, non-cryptographic PRNG with academic backing that has period 2^32-1 (all seeds lead to another seed except 0, which is excluded from the initial seeds).  Many different flavors are possible, as listed in the paper, but the choice implemented in this pull request uses only a single 32-bit integer as a state, like the old PRNG.

Co-authored-by: Thierry Crozat <criezy at scummvm.org>
Co-authored-by: Filippos Karapetis <bluegr at gmail.com>

Changed paths:
    common/random.cpp
    common/random.h


diff --git a/common/random.cpp b/common/random.cpp
index 5da2f67337..2f0d070dc7 100644
--- a/common/random.cpp
+++ b/common/random.cpp
@@ -48,21 +48,20 @@ RandomSource::RandomSource(const String &name) {
 }
 
 void RandomSource::setSeed(uint32 seed) {
+	if (seed == 0)
+		seed++;
 	_randSeed = seed;
 }
 
 uint RandomSource::getRandomNumber(uint max) {
-	_randSeed = 0xDEADBF03 * (_randSeed + 1);
-	_randSeed = (_randSeed >> 13) | (_randSeed << 19);
-
+	scrambleSeed();
 	if (max == UINT_MAX)
-		return _randSeed;
-	return _randSeed % (max + 1);
+		return (_randSeed * 0xDEADBF03);
+	return (_randSeed * 0xDEADBF03) % (max + 1);
 }
 
 uint RandomSource::getRandomBit() {
-	_randSeed = 0xDEADBF03 * (_randSeed + 1);
-	_randSeed = (_randSeed >> 13) | (_randSeed << 19);
+	scrambleSeed();
 	return _randSeed & 1;
 }
 
@@ -73,5 +72,13 @@ uint RandomSource::getRandomNumberRng(uint min, uint max) {
 int RandomSource::getRandomNumberRngSigned(int min, int max) {
 	return getRandomNumber(max - min) + min;
 }
+		
+inline void RandomSource::scrambleSeed() {
+	//marsaglia's paper says that any of 81 triplets are feasible
+	//(11,21,13) was chosen, with (cba) and (>>,<<,>>)
+	_randSeed ^= _randSeed >> 13;
+	_randSeed ^= _randSeed << 21;
+	_randSeed ^= _randSeed >> 11;
+}
 
 } // End of namespace Common
diff --git a/common/random.h b/common/random.h
index e67183ed64..57b666d41e 100644
--- a/common/random.h
+++ b/common/random.h
@@ -39,7 +39,7 @@ namespace Common {
 class String;
 
 /**
- * Simple random number generator. Although it is definitely not suitable for
+ * Xorshift* random number generator. Although it is definitely not suitable for
  * cryptographic purposes, it serves our purposes just fine.
  */
 class RandomSource {
@@ -90,6 +90,14 @@ public:
 	 * @return	a random number in the interval [min, max]
 	 */
 	int getRandomNumberRngSigned(int min, int max);
+	
+	/**
+	* Scrambles the seed in order to get a new result.
+	* Code is shared between getRandomNumber and getRandomBit,
+	* so it is split off for clarity.
+	*/
+private:
+	inline void scrambleSeed();
 };
 
 /** @} */