*To*: sstrickl@resnet.gatech.edu*Cc*: debian-devel@lists.debian.org*Subject*: Re: Rolldice 1.1*From*: Colin Plumb <colin@nyx.net>*Date*: Wed, 27 Jan 1999 03:19:27 -0700 (MST)*Message-id*: <199901271019.DAA29046@nyx10.nyx.net>

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; }

**Follow-Ups**:**Re: Rolldice 1.1***From:*Peter Makholm <peter@makholm.net>

- Prev by Date:
**Re: Hardcore baby!!! Yeah!!!!** - Next by Date:
**Re: Rolldice 1.1** - Previous by thread:
**Re: Hardcore baby!!! Yeah!!!!** - Next by thread:
**Re: Rolldice 1.1** - Index(es):