diff options
| -rwxr-xr-x | bootstrap.sh | 3 | ||||
| -rw-r--r-- | out/redo.do | 2 | ||||
| -rw-r--r-- | src/build.c | 13 | ||||
| -rw-r--r-- | src/pcg.c | 116 | ||||
| -rw-r--r-- | src/pcg.h | 78 | ||||
| -rw-r--r-- | src/redo.c | 18 | ||||
| -rw-r--r-- | src/util.c | 12 | ||||
| -rw-r--r-- | src/util.h | 2 |
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 @@ -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); @@ -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; +} @@ -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 |