As I care passionately about random numbers, I wrote a version which generates *perfect* results.
As per feature requests, it accepts d% as an alias for d100, and interprets a base % as a request for the RoleMaster d100 re-rolling rules as I understand them from the description given. Someone who knows the game please check the code to make sure I got it right. Just "roll" by itself (name subject to change) prints help. The help is, um, for the technically minded. This is, of course, GPLed. -- -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. */ #include <stdio.h> #include <assert.h> #include <unistd.h> /* For read() */ #include <fcntl.h> /* For open(), O_RDONLY */ #include <stdlib.h> /* For exit() */ /* "Unsigned" is assumed to be at least a 32-bit type. */ typedef unsigned word32; /* * 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. */ unsigned rand_mod(int randfd, unsigned n) { static word32 x = 0; static word32 lim = 1; unsigned y; unsigned char c; assert(n <= 65536); /* Larger risks arithmetic overflow */ assert(n > 0); while (x < lim % n) { lim %= n; if (read(randfd, &c, 1) != 1) { perror("Unable to read from /dev/urandom"); exit(1); } x = (x<<8) + c; lim <<= 8; } y = x % n; x = (x / n) - (y < lim%n); lim /= n; return y; } /* * Parse a die-rolling string and return the total. This does not * bother checking for overflow, although limiting the numbers to * 65536 pervents most situations. * * This bombs out with an error message and exit(1) on error. */ int roll_string(char const *s, int randfd) { unsigned n, d; /* Roll n dice of size d */ char const *p = s; int total = 0; /* Value of entire string */ int part; /* Value of current component */ int sign = 0; /* 1 for - */ int sign_required = 0; /* Simple hand-rolled parsing loop */ do { 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 */ fprintf(stderr, "%s: I don't understand that.\n", s); exit(1); } sign_required = 1; if (*p == 'd') { n = 1; /* Number of dice defaults to 1 if omitted. */ } else if (*p == '%') { /* Special RoleMaster "critical" roll */ part = rand_mod(randfd, 100)+1; if (part <= 5) { do { part -= d = rand_mod(randfd, 100)+1; } while (d >= 96); } else if (part >= 96) { do { part += d = rand_mod(randfd, 100)+1; } while (d >= 96); } p++; goto got_component; } else if (*p >= '1' && *p <= '9') { n = 0; do { n = n*10 + (*p++-'0'); if (n > 65536) { fprintf(stderr, "%s: I can't count that high.\n", s); exit(1); } } while (*p >= '0'&& *p <= '9'); } else { fprintf(stderr, "%s: I don't understand that.\n", s); exit(1); } /* Now the "d" part */ if (*p != 'd') { d = 1; } else if (*++p == '%') { d = 100; } else { /* Note that the grammar here disallows d0 */ if (*p < '1' || *p > '9') { fprintf(stderr, "%s: What kind of dice are those?\n", s); exit(1); } d = 0; do { d = d*10 + (*p++-'0'); if (d > 65536) { fprintf(stderr, "%s: I don't have dice that big.\n", s); exit(1); } } while (*p >= '0'&& *p <= '9'); } /* Now add NdD to the total */ part = n; if (d > 1) { while (n--) part += rand_mod(randfd, d); } got_component: if (sign) total -= part; else total += part; } while (*p); return total; } /* The main parsing loop. */ int main(int argc, char **argv) { int randfd; int i; randfd = open("/dev/urandom", O_RDONLY); if (randfd < 0) { perror("/dev/urandom"); exit(1); } 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 = %d\n", argv[i], roll_string(argv[i], randfd)); /* randfd is closed automatically */ return 0; }