/* Hack to compensate for the abysmal rand() that is packaged with MingW.

   Usage:

   x86_64-w64-mingw32-gcc -include rand_patch.h input.c -o output.exe

   The hacky bit is that it uses "-include" to force insert a bit of
   code, so that we can get away with patching via command line flags
   and leave the original source files untouched.  There are certainly
   cleaner ways to do this, I was just being lazy since I only need to
   compile a single source file for each executable.

   Motivation:

   rand() with MingW has at least two problems, first of which is that
   the first return value from rand() is highly correlated with seed,
   such that consecutive seed values will result in very predictable
   rand() values.  Consecutive seed values are very common when the seed
   is time(NULL), and the reason why I noticed rand() was so bad was
   because I observed consecutive runs producing very similar outputs.

   There is a trivial workaround for this problem, which is to force
   include a file with these lines:

      #include<stdlib.h>
      #define srand(s) do { srand(s); (void)rand(); } while (0)

   i.e. always throw away the first rand() right after seeding.  This
   works reasonably well, but we run into a second problem, which is
   that the output with MingW's rand() only has 15 bits.  In comparison,
   GCC and Clang on Cygwin both uses rand() that produces 31 bits.

   There is no good way to increase the number of bits, other than
   replacing the random function altogether, which is what this file
   does.  The algorithm chosen here is PCG:
   https://www.pcg-random.org/
   https://en.wikipedia.org/wiki/Permuted_congruential_generator

   PCG comes with Apache license, which is compatible with MIT.
                                                                          */

#include<stdint.h>
#include<stdlib.h>

#undef RAND_MAX
#define RAND_MAX 0x7fffffff

/* Use user supplied SEED if that's defined.  This allows the output
   to be deterministic, which is useful for testing.                 */
#ifdef SEED
   #define srand(ignored)  pcg32_init(SEED)
#else
   #define srand(s)        pcg32_init(s)
#endif

#define rand()   pcg32()

static uint64_t pcg32_state = 0;

static int pcg32(void)
{
   uint64_t oldstate = pcg32_state;
   uint64_t xorshifted, rot;

   pcg32_state = oldstate * 6364136223846793005ULL + 0xda3e39cb94b95bdbULL;
   xorshifted = ((oldstate >> 18u) ^ oldstate) >> 27u;
   rot = oldstate >> 59u;

   /* Unlike the original PCG, we also drop the topmost bit such that
      the return value is always positive.                            */
   return ((xorshifted >> rot) | (xorshifted << ((-rot) & 31))) & RAND_MAX;
}

static void pcg32_init(int seed)
{
   pcg32_state = 0;
   (void)pcg32();
   pcg32_state += seed;
   (void)pcg32();
}