An improved rolldice utility
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;
}
Reply to: