Stevie Strickland wrote:
> Because not all Debian GNU/Linux systems have /dev/urandom (at least
> I, personally, had to mknod c 1 9 /dev/urandom myself), and I want
> this running on any basic system... eventually, when I had more time
> (like this weekend), I was going to add a command line option to allow
> usage of this device, as well as /dev/random... which would knock out
> the sleep delay (yay!), but introduce the delay of the kernel gathering
> entropy (oh, well, can't win all the time, I guess ;)...
Well, here's a modified version, with a good RNG (a variant of George
Marsaglia's highly-regarded KISS generator) stuck in for the cases
where /dev/urandom isn't available. It's seeded with gettimeofday(),
getpid() and getppid().
It also prints out the numbers it's summing to get the final result.
For example, roll %-%-3d6+12 might print
%-%-3d6+12 = (98+90)-(01-62)-4-2-1+12 = 254
d100 are printed out with "%02d" format; other numbers are printed with
%d format. I realize that "00" is conventional for 100 on d%, but I'm
printing it as 100 to minimuze confusion.
The sum is printed without spaces to make it easy to extract the result
in a shell script with "cut -d' ' -f5".
--
-Colin
/*
* roll.c - FRP die-rolling utility.
* This uses Linux /dev/random for the highest-quality possible random
* numbers. It avoids using any more entropy than necessary (e.g. rolling
* 3d6 has 216 possibilities and requires 1 byte of entropy in the common
* case), and goes to pains to make sure that the results it produces
* are completely free of bias, so the chance of rolling 1 on d6 is
* precisely 1/6.
*
* It also has a (fairly good) emergency backup pseudo-random number
* generator if /dev/urandom isn't available for some reason.
*
* Output is of the form "3d6 = 1+2+3 = 6", so the sum can be picked
* out with "cut -d' ' -f5".
*/
#include <stdio.h>
#include <assert.h>
#include <unistd.h> /* For read(), gettimeofday() */
#include <fcntl.h> /* For open(), O_RDONLY */
#include <stdlib.h> /* For exit() */
#include <sys/time.h> /* For struct timeval */
#include <limits.h> /* For Uxxx_MAX */
#if ULONG_MAX == 0xffffffff
typedef unsigned long word32;
#elif UINT_MAX == 0xffffffff
typedef unsigned word32;
#elif USHRT_MAX == 0xffffffff
typedef unsigned short word32;
#elif UCHAR_MAX == 0xffffffff
typedef unsigned char word32;
#else
#error No 32-bit type available!
#endif
struct random_state {
int randfd; /* /dev/urandom. If >= 0, the rest is ignored. */
word32 w, x, y, z;
};
/*
* Emergency backup RNG, returns a byte.
* Based on George Marsaglia's KISS generator, except that the two
* MWC components are added together rather than concatenated, since
* this only returns a byte. It also uses the high half of the CONG
* generator and returns the high half of the 16-bit sum.
* is returned.
*
* The period of w is 18000*2^15-1 = 589823999, a prime.
* The period of x is 2^32 = 4294967296
* The period of y is 2^32-1 = 4294967295
* The period of z is 36969*2^15-1 = 1211400191, a prime
* Thus, the total period is 13180436693658741103741078002865274880,
* 1.318e37, a bit over 2^123.
*/
static unsigned
random_kiss(struct random_state *r)
{
/* cycle the generators */
r->w = 18000*(r->w & 65535) + (r->w >> 16); /* Mult with carry */
r->x = 69069*r->x + 1234567; /* Linear congruential */
r->y ^= r->y << 17; /* Shift register generator */
r->y ^= r->y >> 13;
r->y ^= r->y << 5;
r->z = 36969*(r->z & 65535) + (r->z >> 16); /* Mult with carry */
/* Join them all together to return. */
return ((((r->w - (r->x>>16)) ^ r->y) + r->z) >> 8) & 255;
}
/*
* Bob Jenkins' mixing function for 32-bit words.
* Note that this is reversible, and maps zero
* to zero, so it maps non-zero to non-zero.
*/
#define mix(a,b,c) \
{ \
a -= b; a -= c; a ^= (c>>13); \
b -= c; b -= a; b ^= (a<<8); \
c -= a; c -= b; c ^= (b>>13); \
a -= b; a -= c; a ^= (c>>12); \
b -= c; b -= a; b ^= (a<<16); \
c -= a; c -= b; c ^= (b>>5); \
a -= b; a -= c; a ^= (c>>3); \
b -= c; b -= a; b ^= (a<<10); \
c -= a; c -= b; c ^= (b>>15); \
}
/* Start up the random state */
static void
random_init(struct random_state *r)
{
word32 w, x, y, z;
struct timeval tv;
r->randfd = open("/dev/urandom", O_RDONLY);
/* Emergency backup seeding, in case /dev/urandom doesn't work. */
/* Backup seed, good enough for government work. */
gettimeofday(&tv, (struct timezone *)0);
w = tv.tv_sec;
x = tv.tv_usec;
z = ((word32)getppid() << 16) + (word32)getpid();
mix(w, x, z); /* Shuffle the seed values non-destructively */
/*
* Now ensure that seed constraints are met.
* w should be between 1 and 589823999.
* x can be anything between 0 and 2^32-1.
* y should be between 1 and 2^32-1.
* z should be between 1 and 1211400191.
*/
r->w = w % 589823999 + 1;
r->x = x;
r->z = z % 1211400191 + 1;
/*
* Finally, we initialize y. Since the range desired for y,
* 2^32-1, exactly divides the range available from the
* triple-width number wxz, 2^96-1, the remainder modulo 2^32-1
* will be uniformly distributed. Fortunately, due to the special
* form of the modulus, this computation is easy.
* Since tv_sec never returns 0, and mix() preserves
* non-zeroness, the full value wxz here is never 0, so the
* result computed here is never 0.
*/
y = w+x;
y += y<x; /* End-around carry */
y += z;
y += y<z; /* End-around carry */
r->y = y;
}
/* Return a random byte 0..255 */
static unsigned
random_byte(struct random_state *r)
{
unsigned char c = 0;
if (r->randfd >= 0 && read(r->randfd, &c, 1) != 1) {
perror("Unable to read from /dev/urandom");
r->randfd = -1;
}
/* Add backup generator in case /dev/urandom is missing or broken */
return c ^ random_kiss(r);
}
/*
* This ingenious function returns perfectly uniformly distributed
* random numbers between 0 and n-1 using a minimum of input from
* /dev/urandom. The truly macho should try to understand it without
* the comments.
*
* At all times, x is a random number uniformly distributed between 0
* and lim-1. We increase lim by a factor of 256 by appending a byte
* onto x (x = (x<<8) + random_byte) whenever necessary.
*
* The value of x%n has at least floor(lim/n) ways of generating each
* possible value from 0..n-1, but it has an additional way
* (ceiling(lim/n)) of generating values less than lim%n. (Consider
* lim = 4 or 5 and n = 3.)
*
* To produce perfectly uniform numbers, if x < lim%n, we add another
* byte rather than returning x%n. Becasue we only do this if x < lim%n,
* taking the branch means that lim %= n.
*
* Once we have x >= lim%n, then y = x%n is the desired random number.
* x/n is "unused" and can be saved for next time, with a lim of lim/n.
* There is a small correction that has to be added to deal with the fact
* that x/n can be == lim, which is illegal.
*/
static unsigned
rand_mod(struct random_state *r, unsigned n)
{
static word32 x = 0;
static word32 lim = 1;
unsigned y;
assert(n <= 65536); /* Larger risks arithmetic overflow */
assert(n > 0);
while (x < lim % n) {
lim %= n;
x = (x<<8) + random_byte(r);
lim <<= 8;
}
y = x % n;
x = (x / n) - (y < lim%n);
lim /= n;
return y;
}
#if __GNUC__ >= 2
static void fatal() __attribute__ ((noreturn));
#endif
/* Flush stdout, then print erro message and quit. */
static void
fatal(char const *s1, char const *s2)
{
putchar('\n');
fflush(stdout);
fputs(s1, stderr);
fputs(": ", stderr);
fputs(s2, stderr);
putc('\n', stderr);
exit(1);
}
/*
* Parse a die-rolling string and return the total. This does not
* bother checking for overflow, although limiting the numbers to
* 65536 prevents most situations. It also prints the individual
* parts of the sum. d100 is printed in %02ld format by convention.
* (However, 100 is printed as "100" not "00", unless someone feels
* that is really important.)
*
* This bombs via fatal() on a parsing error.
*/
long
roll_string(char const *s, struct random_state *r)
{
unsigned n, d; /* Roll n dice of size d */
char const *p = s;
long total = 0; /* Value of entire string */
long part; /* Value of current component */
long x;
int sign = 0; /* 1 for - */
int sign_required = 0; /* Is a leading + optional? */
/* Simple hand-rolled parsing loop */
do {
/* Parse one component at a time */
sign = 0;
/* Optional leading sign */
if (*p == '+') {
p++;
} else if (*p == '-') {
sign = 1;
p++;
} else if (sign_required) {
/* Without this test, d6d8 would mean d6+d8 */
fatal(s, "I don't understand that.");
}
sign_required |= sign;
if (*p == 'd') {
n = 1; /* Number of dice defaults to 1 if omitted. */
} else if (*p == '%') {
/* Special RoleMaster "critical" roll rules */
if (sign_required)
putchar("+-"[sign]);
part = rand_mod(r, 100)+1;
if (part <= 5) {
printf("(%02ld", part);
do {
part -= x = rand_mod(r, 100)+1;
printf("-%02ld", x);
} while (x >= 96);
putchar(')');
} else if (part >= 96) {
printf("(%02ld", part);
do {
part += x = rand_mod(r, 100)+1;
printf("+%02ld", x);
} while (x >= 96);
putchar(')');
} else {
printf("%02ld", part);
}
p++;
goto got_component;
} else if (*p >= '1' && *p <= '9') {
n = 0;
do {
n = n*10 + (*p++-'0');
if (n > 65536)
fatal(s, "I can't count that high.");
} while (*p >= '0'&& *p <= '9');
} else {
fatal(s, "I don't understand that.");
}
/* Now the "d" part */
if (*p != 'd') {
d = 1;
} else if (*++p == '%') {
d = 100;
p++;
} else {
/* Note that the grammar here disallows d0 */
if (*p < '1' || *p > '9')
fatal(s, "I don't have that kind of dice.");
d = 0;
do {
d = d*10 + (*p++-'0');
if (d > 65536)
fatal(s, "I don't have dice that big.");
} while (*p >= '0'&& *p <= '9');
}
/* Now add NdD to the total */
if (d > 1) {
part = 0;
while (n--) {
if (sign_required)
putchar("+-"[sign]);
x = rand_mod(r, d) + 1;
part += x;
if (d == 100)
printf("%02ld", x);
else
printf("%ld", x);
sign_required = 1;
}
} else {
part = n;
if (sign_required)
putchar("+-"[sign]);
printf("%u", n);
}
got_component:
if (sign)
total -= part;
else
total += part;
sign_required = 1;
} while (*p);
return total;
}
/* The main argument-processing loop. */
int
main(int argc, char **argv)
{
int i;
struct random_state r;
random_init(&r);
if (argc <= 1) {
printf("Usage %s roll_spec [...]\n"
"roll_spec is a standrd FRP diece specification, of the form 3d6, d8+12,\n"
"5+d100, etc. To be precise, it's:\n\t"
"nzdigit ::= '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'\n\t"
"digit ::= '0' | nzdigit\n\t"
"number ::= nzdigit | number digit\n\t"
"die_spec = 'd' number | 'd' '%%'\n\t"
"component ::= number | die_spec | number die_spec | '%%'\n\t"
"sign ::= '+' | '-'\n\t"
"roll_spec ::= component | sign component | roll_spec sign component\n"
"dN neans an N-sided die, with values from 1..N. 2dN = dN+dN is the sum of\n"
"two N-sided dice. A bare N is just a constant, so 3d6-3 is from 0..15.\n"
"d%% is an alias for d100. The magic component '%%' stands for d100 with the\n"
"extra RoleMaster \"critical\" rules, where if you roll 96..100, you roll\n"
"again and add the result, repeating until you roll <= 95. If you roll\n"
"1..5, you likewise roll again and subtract the result, again repeating until\n"
"you roll <= 95.\n",
argv[0]);
exit(1);
}
for (i = 1; i < argc; i++) {
printf("%s = ", argv[i]);
printf(" = %ld\n", roll_string(argv[i], &r));
}
/* randfd is closed automatically */
return 0;
}
