[libgens] CrazyEffect: Improved performance by using a faster RNG.
authorDavid Korth <gerbilsoft@gerbilsoft.com>
Thu, 3 Sep 2015 04:54:57 +0000 (00:54 -0400)
committerDavid Korth <gerbilsoft@gerbilsoft.com>
Thu, 3 Sep 2015 04:54:57 +0000 (00:54 -0400)
Xorshift+ is significantly faster than both glibc's and MSVC 2010's
rand() function. On my ThinkPad T60p, the Linux rand() version usually
runs at around 45-50 fps if something else is running, but the new
Xorshift+ version runs at 56-60 fps.

This version also helps to reduce the CPU load a bit.

TODO: Cache the upper bits of Xorshift+'s result so we can get
at least two 15-bit values out of a single iteration.

src/libgens/Effects/CrazyEffect.cpp
src/libgens/Effects/CrazyEffect.hpp

index 4c4fb3c..a772227 100644 (file)
@@ -32,6 +32,7 @@
 #include <cmath>
 #include <cstring>
 #include <cstdio>
+#include <ctime>
 
 namespace LibGens {
 
@@ -39,31 +40,22 @@ namespace LibGens {
 
 /**
  * Get a random number in the range [0,0x7FFF].
- * This uses the internal random number
- * cache if it's available.
+ * Based on Xorshift+:
+ * - https://en.wikipedia.org/wiki/Xorshift#Xorshift.2B
  * @return Random number.
  */
 unsigned int CrazyEffect::getRand(void)
 {
-       // TODO: Faster rand() implementation, e.g. Mersenne Twister?
-       unsigned int ret;
-#if RAND_MAX >= 0x3FFFFFFF
-       if (rand_cache <= 0x7FFF) {
-               // rand_cache is valid.
-               ret = rand_cache;
-               rand_cache = ~0;
-               return ret;
-       }
-#endif
-
-       // Get a random number.
-       ret = rand();
-#if RAND_MAX >= 0x3FFFFFFF
-       // Cache the high bits as a second random number.
-       rand_cache = (ret >> 15) & 0x7FFF;
-       ret &= 0x7FFF;
-#endif
-       return ret;
+       uint64_t x = rng_state.q[0];
+       uint64_t const y = rng_state.q[1];
+       rng_state.q[0] = y;
+       x ^= x << 23; // a
+       x ^= x >> 17; // b
+       x ^= y ^ (y >> 26); // c
+       rng_state.q[1] = x;
+
+       // TODO: Cache upper bits?
+       return (x + y) & 0x7FFF;
 }
 
 /**
@@ -79,7 +71,7 @@ inline pixel CrazyEffect::adj_color(pixel px, pixel mask)
 {
        pixel add = 1 << add_shift;
        px &= mask;
-       if ((getRand() & 0x7FFF) > 0x2C00) {
+       if (getRand() > 0x2C00) {
                if ((mask - add) <= px) {
                        px = mask;
                } else {
@@ -161,10 +153,21 @@ inline void CrazyEffect::T_doCrazyEffect(pixel *outScreen)
 
 CrazyEffect::CrazyEffect()
        : m_colorMask(CM_WHITE)
-#if RAND_MAX >= 0x3FFFFFFF
-       , rand_cache(~0)
-#endif
-{ }
+{
+       // Initialize the RNG state.
+       // FIXME: Move this srand() call somewhere else.
+       srand((unsigned int)time(nullptr));
+
+       // RAND_MAX is at least 0x7FFF, so we need to
+       // call rand() multiple times. We'll use xor
+       // instead of simple assignment so systems where
+       // RAND_MAX > 0x7FFF get an extra bit of randomness.
+       for (int i = 0; i < 4; i++) {
+               rng_state.d[i]  =  rand();
+               rng_state.d[i] ^= (rand() << 15);
+               rng_state.d[i] ^= (rand() << 30);
+       }
+}
 
 /**
  * Run the "Crazy" effect.
index 797806f..37518f3 100644 (file)
@@ -96,13 +96,11 @@ class CrazyEffect
                template<typename pixel, uint8_t add_shift>
                inline pixel adj_color(pixel px, pixel mask);
 
-#if RAND_MAX >= 0x3FFFFFFF
-               // Random number cache.
-               // glibc's RAND_MAX is 0x7FFFFFFF, so we can
-               // get two random numbers from [0,0x7FFF]
-               // with a single call to rand().
-               unsigned int rand_cache;
-#endif
+               // Xorshift+ RNG state.
+               union {
+                       uint32_t d[4];
+                       uint64_t q[2];
+               } rng_state;
 };
 
 inline CrazyEffect::ColorMask CrazyEffect::colorMask(void) const