Use the proper RNG called PCG instead of rand()

Fixes #7.

8 files changed, 231 insertions, 13 deletions

diff --git a/bootstrap.sh b/bootstrap.sh
index 5bf204d..1bc45fa 100755
--- a/bootstrap.sh
+++ b/bootstrap.sh
@@ -16,8 +16,9 @@ $CC $CFLAGS -o out/filepath.o -c src/filepath.c
 $CC $CFLAGS -o out/sha1.o -c src/sha1.c
 $CC $CFLAGS -o out/DSV.o -c src/DSV.c
 $CC $CFLAGS -o out/redo.o -c src/redo.c
+$CC $CFLAGS -o out/pcg.o -c src/pcg.c
 $CC -o out/redo out/redo.o out/util.o out/build.o out/filepath.o out/sha1.o \
-       out/DSV.o $LDFLAGS
+       out/DSV.o out/pcg.o $LDFLAGS
 )
 
 ln -sf redo out/redo-ifchange
diff --git a/out/redo.do b/out/redo.do
index ee098a0..fd4536a 100644
--- a/out/redo.do
+++ b/out/redo.do
@@ -1,5 +1,5 @@
 . ./config.sh
 
-DEPS="redo.o build.o util.o filepath.o sha1.o DSV.o"
+DEPS="redo.o build.o util.o filepath.o sha1.o DSV.o pcg.o"
 redo-ifchange $DEPS config.sh
 $CC -o $3 $DEPS $LDFLAGS
diff --git a/src/build.c b/src/build.c
index 19628cf..83a8a7b 100644
--- a/src/build.c
+++ b/src/build.c
@@ -17,6 +17,7 @@
 #include <sys/stat.h>
 #include <fcntl.h>
 #include <time.h>
+#include <inttypes.h>
 
 #include <libgen.h> /* dirname(), basename() */
 
@@ -394,6 +395,14 @@ void add_prereq_path(const char *target, const char *parent, int ident) {
 	free(reltarget);
 }
 
+static uint32_t get_magic_number() {
+	uint32_t magic;
+	if (sscanf(getenv("REDO_MAGIC"), "%"SCNu32, &magic) < 1)
+		die("redo: failed to parse REDO_MAGIC (%s)", getenv("REDO_MAGIC"));
+
+	return magic;
+}
+
 /* Update hash & ctime information stored in the given dep_info struct */
 static void update_dep_info(dep_info *dep, const char *target) {
 	FILE *fp = fopen(target, "rb");
@@ -419,10 +428,10 @@ static void write_dep_information(dep_info *dep) {
 	sha1_to_hex(dep->hash, hash);
 	char *flags = (dep->flags & DEP_SOURCE) ? "s" : "l";
 
-	int magic = atoi(getenv("REDO_MAGIC"));
+	uint32_t magic = get_magic_number();
 
 	/* TODO: casting time_t to long long is probably not entirely portable */
-	if (fprintf(fd, "%s:%lld.%.9ld:%010d:%s\n", hash,
+	if (fprintf(fd, "%s:%lld.%.9ld:%"PRIu32":%s\n", hash,
 			(long long)dep->ctime.tv_sec, dep->ctime.tv_nsec, magic, flags) < 0)
 		fatal("redo: failed to write to %s", dep->path);
 
diff --git a/src/pcg.c b/src/pcg.c
new file mode 100644
index 0000000..a245b11
--- /dev/null
+++ b/src/pcg.c
@@ -0,0 +1,116 @@
+/*
+ * PCG Random Number Generation for C.
+ *
+ * Copyright 2014 Melissa O'Neill <oneill@pcg-random.org>
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ *
+ * For additional information about the PCG random number generation scheme,
+ * including its license and other licensing options, visit
+ *
+ *       http://www.pcg-random.org
+ */
+
+/*
+ * This code is derived from the full C implementation, which is in turn
+ * derived from the canonical C++ PCG implementation. The C++ version
+ * has many additional features and is preferable if you can use C++ in
+ * your project.
+ */
+
+#include "pcg.h"
+
+// state for global RNGs
+
+static pcg32_random_t pcg32_global = PCG32_INITIALIZER;
+
+// pcg32_srandom(initstate, initseq)
+// pcg32_srandom_r(rng, initstate, initseq):
+//     Seed the rng.  Specified in two parts, state initializer and a
+//     sequence selection constant (a.k.a. stream id)
+
+void pcg32_srandom_r(pcg32_random_t* rng, uint64_t initstate, uint64_t initseq)
+{
+    rng->state = 0U;
+    rng->inc = (initseq << 1u) | 1u;
+    pcg32_random_r(rng);
+    rng->state += initstate;
+    pcg32_random_r(rng);
+}
+
+void pcg32_srandom(uint64_t seed, uint64_t seq)
+{
+    pcg32_srandom_r(&pcg32_global, seed, seq);
+}
+
+// pcg32_random()
+// pcg32_random_r(rng)
+//     Generate a uniformly distributed 32-bit random number
+
+uint32_t pcg32_random_r(pcg32_random_t* rng)
+{
+    uint64_t oldstate = rng->state;
+    rng->state = oldstate * 6364136223846793005ULL + rng->inc;
+    uint32_t xorshifted = ((oldstate >> 18u) ^ oldstate) >> 27u;
+    uint32_t rot = oldstate >> 59u;
+    return (xorshifted >> rot) | (xorshifted << ((-rot) & 31));
+}
+
+uint32_t pcg32_random()
+{
+    return pcg32_random_r(&pcg32_global);
+}
+
+
+// pcg32_boundedrand(bound):
+// pcg32_boundedrand_r(rng, bound):
+//     Generate a uniformly distributed number, r, where 0 <= r < bound
+
+uint32_t pcg32_boundedrand_r(pcg32_random_t* rng, uint32_t bound)
+{
+    // To avoid bias, we need to make the range of the RNG a multiple of
+    // bound, which we do by dropping output less than a threshold.
+    // A naive scheme to calculate the threshold would be to do
+    //
+    //     uint32_t threshold = 0x100000000ull % bound;
+    //
+    // but 64-bit div/mod is slower than 32-bit div/mod (especially on
+    // 32-bit platforms).  In essence, we do
+    //
+    //     uint32_t threshold = (0x100000000ull-bound) % bound;
+    //
+    // because this version will calculate the same modulus, but the LHS
+    // value is less than 2^32.
+
+    uint32_t threshold = -bound % bound;
+
+    // Uniformity guarantees that this loop will terminate.  In practice, it
+    // should usually terminate quickly; on average (assuming all bounds are
+    // equally likely), 82.25% of the time, we can expect it to require just
+    // one iteration.  In the worst case, someone passes a bound of 2^31 + 1
+    // (i.e., 2147483649), which invalidates almost 50% of the range.  In
+    // practice, bounds are typically small and only a tiny amount of the range
+    // is eliminated.
+    for (;;) {
+        uint32_t r = pcg32_random_r(rng);
+        if (r >= threshold)
+            return r % bound;
+    }
+}
+
+
+uint32_t pcg32_boundedrand(uint32_t bound)
+{
+    return pcg32_boundedrand_r(&pcg32_global, bound);
+}
+
diff --git a/src/pcg.h b/src/pcg.h
new file mode 100644
index 0000000..e2b526a
--- /dev/null
+++ b/src/pcg.h
@@ -0,0 +1,78 @@
+/*
+ * PCG Random Number Generation for C.
+ *
+ * Copyright 2014 Melissa O'Neill <oneill@pcg-random.org>
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ *
+ * For additional information about the PCG random number generation scheme,
+ * including its license and other licensing options, visit
+ *
+ *     http://www.pcg-random.org
+ */
+
+/*
+ * This code is derived from the full C implementation, which is in turn
+ * derived from the canonical C++ PCG implementation. The C++ version
+ * has many additional features and is preferable if you can use C++ in
+ * your project.
+ */
+
+#ifndef PCG_BASIC_H_INCLUDED
+#define PCG_BASIC_H_INCLUDED 1
+
+#include <inttypes.h>
+
+#if __cplusplus
+extern "C" {
+#endif
+
+struct pcg_state_setseq_64 {    // Internals are *Private*.
+    uint64_t state;             // RNG state.  All values are possible.
+    uint64_t inc;               // Controls which RNG sequence (stream) is
+                                // selected. Must *always* be odd.
+};
+typedef struct pcg_state_setseq_64 pcg32_random_t;
+
+// If you *must* statically initialize it, here's one.
+
+#define PCG32_INITIALIZER   { 0x853c49e6748fea9bULL, 0xda3e39cb94b95bdbULL }
+
+// pcg32_srandom(initstate, initseq)
+// pcg32_srandom_r(rng, initstate, initseq):
+//     Seed the rng.  Specified in two parts, state initializer and a
+//     sequence selection constant (a.k.a. stream id)
+
+void pcg32_srandom(uint64_t initstate, uint64_t initseq);
+void pcg32_srandom_r(pcg32_random_t* rng, uint64_t initstate,
+                     uint64_t initseq);
+
+// pcg32_random()
+// pcg32_random_r(rng)
+//     Generate a uniformly distributed 32-bit random number
+
+uint32_t pcg32_random(void);
+uint32_t pcg32_random_r(pcg32_random_t* rng);
+
+// pcg32_boundedrand(bound):
+// pcg32_boundedrand_r(rng, bound):
+//     Generate a uniformly distributed number, r, where 0 <= r < bound
+
+uint32_t pcg32_boundedrand(uint32_t bound);
+uint32_t pcg32_boundedrand_r(pcg32_random_t* rng, uint32_t bound);
+
+#if __cplusplus
+}
+#endif
+
+#endif // PCG_BASIC_H_INCLUDED
diff --git a/src/redo.c b/src/redo.c
index e28f8fa..f753c68 100644
--- a/src/redo.c
+++ b/src/redo.c
@@ -20,11 +20,7 @@
 #include "dbg.h"
 #include "filepath.h"
 
-
-/* Returns the amount of digits a number n has in decimal. */
-static inline unsigned digits(unsigned n) {
-	return n ? 1 + digits(n/10) : n;
-}
+#include "pcg.h"
 
 void prepare_env() {
 	if (getenv("REDO_ROOT") && getenv("REDO_PARENT_TARGET")
@@ -39,9 +35,14 @@ void prepare_env() {
 		fatal("redo: failed to setenv() REDO_ROOT to %s", cwd);
 	free(cwd);
 
+	/* initialize random number generator */
+	int rounds = 73;
+	pcg32_random_t rng;
+	pcg32_srandom_r(&rng, generate_seed(), (intptr_t)&rounds);
+
 	/* set REDO_MAGIC */
-	char magic_str[digits(UINT_MAX) + 1];
-	sprintf(magic_str, "%u", rand());
+	char magic_str[11];
+	sprintf(magic_str, "%"PRIu32, pcg32_random_r(&rng));
 	if (setenv("REDO_MAGIC", magic_str, 0))
 		fatal("redo: failed to setenv() REDO_MAGIC to %s", magic_str);
 }
@@ -49,7 +50,6 @@ void prepare_env() {
 int DBG_LVL;
 
 int main(int argc, char *argv[]) {
-	srand(time(NULL));
 	char *argv_base = xbasename(argv[0]);
 
 	if (!strcmp(argv_base, "redo")) {
@@ -62,7 +62,6 @@ int main(int argc, char *argv[]) {
 		}
 	} else {
 		char ident;
-		char **temp;
 		if      (!strcmp(argv_base, "redo-ifchange"))
 			ident = 'c';
 		else if (!strcmp(argv_base, "redo-ifcreate"))
@@ -89,6 +88,7 @@ int main(int argc, char *argv[]) {
 			add_prereq(parent, parent, ident);
 		else
 			for (int i = 1; i < argc; ++i) {
+				char **temp;
 				do {
 					temp = &argv[rand() % (argc-1) + 1];
 				} while (!*temp);
diff --git a/src/util.c b/src/util.c
index 35db2e3..266cf90 100644
--- a/src/util.c
+++ b/src/util.c
@@ -121,3 +121,15 @@ void hex_to_sha1(const char *s, unsigned char *sha1) {
 		*sha1 = ((strchr(hex, *s) - hex) << 4) + strchr(hex, *(s+1)) - hex;
 }
 
+uint32_t generate_seed() {
+	uint32_t seed;
+	FILE *fp = fopen("/dev/urandom", "rb");
+	if (!fp)
+		fatal("redo: failed to open /dev/urandom");
+
+	if (fread(&seed, 1, 4, fp) < 4)
+		fatal("redo: failed to read from /dev/urandom");
+
+	fclose(fp);
+	return seed;
+}
diff --git a/src/util.h b/src/util.h
index 159626d..64b39e3 100644
--- a/src/util.h
+++ b/src/util.h
@@ -10,6 +10,7 @@
 #define __RUTIL_H__
 
 #include <stddef.h>
+#include <stdint.h>
 #include <stdio.h>
 
 extern void __attribute__((noreturn)) die_(const char *err, ...);
@@ -20,5 +21,6 @@ extern char *concat(size_t count, ...);
 extern unsigned char *hash_file(FILE *fp);
 extern void sha1_to_hex(const unsigned char *sha1, char *buf);
 extern void hex_to_sha1(const char *s, unsigned char *sha1);
+extern uint32_t generate_seed();
 
 #endif