/*
 * Six function calculator with random intput (dice expressions).
 *
 * Dan Cross <net!gajendra!cross>
 */

#include <ctype.h>
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

/*
 * The grammar:
 *
 * d20 := expression
 * expression := term | term '+' expression | term '-' expression
 * term := factor | factor '*' term | factor '/' term | factor '^' factor
 * factor := die | number | '(' expression ')' | 'r' factor | '+' factor | '-' factor
 * die  := number? 'd' sides
 * number := [1-9][0-9]*
 * sides := number > 1
 */

enum Op {
	OpNONE,
	OpADD,
	OpSUB,
	OpMUL,
	OpDIV,
	OpEXP,
	OpROOT
};

enum TokenType {
	TkEOF = '\0',
	TkLPAREN = '(',
	TkRPAREN = ')',
	TkPLUS = '+',
	TkMINUS = '-',
	TkSTAR = '*',
	TkSLASH = '/',
	TkCIRC = '^',
	TkD = 'd',
	TkR = 'r',

	TkNUMBER = 256
};

typedef struct Factor Factor;
typedef unsigned int D;
typedef struct Die Die;
typedef struct Expr Expr;
typedef enum Op Op;
typedef struct State State;
typedef struct Term Term;
typedef struct Token Token;
typedef enum TokenType TokenType;
typedef long long vlong;

Expr *expression(State *state);
Term *term(State *state);
Factor *factor(State *state);
Die *dice(State *state);
Token scan(State *state);
vlong eval(Expr *expr);

struct Die {
	D sides;
	int rolls;
};

struct Expr {
	Term *left;
	Expr *right;
	Op op;
};

struct Factor {
	vlong number;
	Die *die;
	Expr *expression;
	Op unaryop;
};

struct State {
	char *input;
	char *begin;
	char *end;
};

struct Term {
	Term *term;
	Factor *factor;
	Op op;
};

struct Token {
	TokenType type;
	char *begin;
	char *end;
};

void
fatal(const char *msg)
{
	fprintf(stderr, "%s\n", msg);
	exit(EXIT_FAILURE);
}

void
reset(State *state, char *input)
{
	state->input = input;
	state->begin = input;
	state->end = input;
}

int
peekc(State *state)
{
	return(*state->end);
}

int
advance(State *state)
{
	int value;

	value = *state->end;
	if (value != '\0')
		state->end++;

	return(value);
}

void
consume(State *state)
{
	state->begin = state->end;
}

Token
next(State *state, TokenType type)
{
	Token token;

	token.type = type;
	token.begin = state->begin;
	token.end = state->end;
	consume(state);

	return(token);
}

void
backup(State *state, Token token)
{
	state->begin = token.begin;
	state->end = token.begin;
}

int
spaces(int c)
{
	return(c == ' ' || c == '\t');
}

int
digits(int c)
{
	return(isdigit(c));
}

void
span(State *state, int (*pred)(int))
{
	while (pred(peekc(state)))
		advance(state);
}

const Token fail;

Token
scan(State *state)
{

	span(state, spaces);
	consume(state);
	if (isdigit(peekc(state))) {
		span(state, digits);
		if (peekc(state) == TkD) {
			advance(state);
			span(state, digits);
			return(next(state, TkD));
		}
		return(next(state, TkNUMBER));
	}
	switch (advance(state)) {
	case TkEOF:
		return(next(state, TkEOF));
	case TkLPAREN:
		return(next(state, TkLPAREN));
	case TkRPAREN:
		return(next(state, TkRPAREN));
	case TkPLUS:
		return(next(state, TkPLUS));
	case TkMINUS:
		return(next(state, TkMINUS));
	case TkSTAR:
		return(next(state, TkSTAR));
	case TkSLASH:
		return(next(state, TkSLASH));
	case TkCIRC:
		return(next(state, TkCIRC));
	case TkD:
		span(state, digits);
		return(next(state, TkD));
	case TkR:
		return(next(state, TkR));
	default:
		break;
	}

	fatal("d20: lexical error.\n");
	return fail;
}

Token
peek(State *state)
{
	Token token;

	token = scan(state);
	backup(state, token);

	return(token);
}

void
printtok(Token token)
{
	char *toktypes[] = {
	    [TkEOF]	= "TkEOF",
	    [TkLPAREN]	= "TkLPAREN",
	    [TkRPAREN]	= "TkRPAREN",
	    [TkPLUS]	= "TkPLUS",
	    [TkMINUS]	= "TkMINUS",
	    [TkSTAR]	= "TkSTAR",
	    [TkSLASH]	= "TkSLASH",
	    [TkCIRC]	= "TkCIRC",
	    [TkD]	= "TkD",
	    [TkNUMBER]	= "TkNUMBER"
	};

	printf("Token: Type=%s, contents=%.*s\n",
	    toktypes[token.type],
	    (int)(token.end - token.begin),
	    token.begin);
}

void *
emalloc(size_t size)
{
	void *m;

	m = malloc(size);
	if (m == NULL)
		fatal("malloc failed");
	memset(m, 0, size);

	return(m);
}

Die *
dice(State *state)
{
	Die *d;
	char *pend;
	int sides;
	Token token;

	token = scan(state);
	if (token.type == TkEOF)
		return(NULL);
	if (token.type != TkD)
		fatal("Parse error in dice: Bad token type.");
	d = emalloc(sizeof(*d));
	pend = NULL;
	d->rolls = strtol(token.begin, &pend, 10);
	if (pend == NULL || *pend != 'd')
		fatal("Parse error in dice: bad dice expression.");
	if (token.begin == pend)
		d->rolls = 1;
	sides = strtol(pend + 1, &pend, 10);
	if (pend == NULL || pend != token.end)
		fatal("Parse error in dice: sides are not an integer:");
	if (sides < 2)
		fatal("Parse error in dice: not enough sides.");
	d->sides = sides;

	return(d);
}

Factor *
factor(State *state)
{
	Factor *factor;
	Token token;
	TokenType ttype;

	factor = emalloc(sizeof(*factor));
	do {
		token = scan(state);
		ttype = token.type;
		switch (ttype) {
		case TkEOF:
			free(factor);
			return(NULL);
		case TkLPAREN:
			factor->expression = expression(state);
			token = scan(state);
			if (token.type != TkRPAREN)
				fatal("Unmatched parenthesis parse error");
			break;
		case TkPLUS:
			if (factor->unaryop != OpNONE)
				fatal("factor absolute value error");
			factor->unaryop = OpADD;
			break;
		case TkMINUS:
			if (factor->unaryop != OpNONE)
				fatal("factor negative value error");
			factor->unaryop = OpSUB;
			break;
		case TkR:
			if (factor->unaryop != OpNONE)
				fatal("factor root parse error");
			factor->unaryop = OpROOT;
			break;
		case TkNUMBER:
			factor->number = atoi(token.begin);
			break;
		case TkD:
			backup(state, token);
			factor->die = dice(state);
			break;
		default:
			fatal("Syntax error in factor");
			break;
		}
	} while (ttype == TkPLUS || ttype == TkMINUS || ttype == TkR);

	return(factor);
}

Term *
term(State *state)
{
	Term *trm;
	Token token;

	trm = NULL;
	token = peek(state);
	if (token.type == TkEOF)
		return(NULL);
	trm = emalloc(sizeof(*trm));
	trm->factor = factor(state);
	token = peek(state);
	if (token.type == TkSTAR ||
	    token.type == TkSLASH ||
	    token.type == TkCIRC) {
		token = scan(state);
		switch (token.type) {
		case TkSTAR:
			trm->op = OpMUL;
			break;
		case TkSLASH:
			trm->op = OpDIV;
			break;
		case TkCIRC:
			trm->op = OpEXP;
			break;
		default:
			fatal("bad term expression.");
			break;		/* NOTREACHED */
		}
		trm->term = term(state);
	}

	return(trm);
}

Expr *
expression(State *state)
{
	Expr *x;
	Token token;

	token = peek(state);
	if (token.type == TkEOF)
		return(NULL);
	x = emalloc(sizeof(*x));
	x->left = term(state);
	token = peek(state);
	if (token.type == TkPLUS || token.type == TkMINUS) {
		token = scan(state);
		switch (token.type) {
		case TkPLUS:
			x->op = OpADD;
			break;
		case TkMINUS:
			x->op = OpSUB;
			break;
		default:
			fatal("bad expression operation.");
			break;		/* NOTREACHED */
		}
		x->right = expression(state);
	}

	return(x);
}

Expr *
parse(State *parser)
{
	return(expression(parser));
}

vlong
evalroll(Die *die)
{
	vlong sum;
	int k;

	sum = 0;
	for (k = 0; k < die->rolls; ++k) {
		++sum;
		sum += arc4random_uniform(die->sides);
	}

	return(sum);
}

vlong
iabs(vlong number)
{
	return (number >= 0) ? number : 0 - number;
}

vlong
isqrt(vlong number)
{
	vlong bit, root;

	root = 0;
	bit = (~0ULL >> 1) ^ (~0ULL >> 2);

	while (bit > number)
		bit >>= 2;

	while (bit != 0) {
		if (number < (root + bit))
			root >>= 1;
		else {
			number -= (root + bit);
			root >>= 1;
			root += bit;
		}
		bit >>= 2;
	}

	return(root);
}

int
unaryop(Op op, vlong number)
{
	if (op == OpADD)
		return(iabs(number));
	if (op == OpSUB)
		return(0 - iabs(number));
	if (op == OpROOT)
		return(isqrt(iabs(number)));

	return(number);
}

vlong
evalfactor(Factor *factor)
{
	if (factor->die == NULL && factor->expression == NULL)
		return(unaryop(factor->unaryop, factor->number));
	if (factor->die != NULL)
		return(unaryop(factor->unaryop, evalroll(factor->die)));

	return(unaryop(factor->unaryop, eval(factor->expression)));
}

vlong
iexp(vlong base, int exp)
{
	vlong val;

	if (exp < 0)
		return(-1);	/* Bad exponent. */
	if (exp == 0)
		return(1);
	val = 1LL;
	while (exp > 0) {
		if ((exp % 2) != 0) {
			val *= base;
		}
		base *= base;
		exp /= 2;
	}

	return(val);
}

vlong
evalterm(Term *term)
{
	vlong vfactor, vterm;

	vfactor = 0;
	if (term->factor != NULL)
		vfactor = evalfactor(term->factor);
	if (term->term == NULL)
		return(vfactor);
	vterm = evalterm(term->term);
	if (term->op == OpMUL)
		return(vfactor * vterm);
	if (term->op == OpDIV)
		return(vfactor / vterm);
	if (term->op == OpEXP)
		return(iexp(vfactor, vterm));

	return(-1);
}

vlong
eval(Expr *expr)
{
	vlong left, right;

	left = 0;
	if (expr->left != NULL)
		left = evalterm(expr->left);
	if (expr->right == NULL)
		return(left);
	right = eval(expr->right);
	if (expr->op == OpADD)
		return(left + right);
	if (expr->op == OpSUB)
		return(left - right);

	return(-1);	/* Bad operation. */
}

int
main(int argc, char *argv[])
{
	State s;
	Expr *x;

	if (argc != 2) {
		fprintf(stderr, "Usage: d20 <dice expression>\n");
		return(EXIT_FAILURE);
	}
	reset(&s, strdup(argv[1]));
	x = parse(&s);
	if (x == NULL)
		fatal("Parsing failed!");
	printf("%s = %lld\n", argv[1], eval(x));
	free(s.input);

	return(EXIT_SUCCESS);
}