/*	c2g12.c

	C-to-Gates by H. Dietz, Fall 2006
	Revised, Spring 2012

	Compile this by:

	cc c2g12.c -o c2g

	This version supports either textual or dot (graphviz) output.
	To get human-readable text output:

	./c2g <input |dot -Txlib

	To see the dot output as a graph in an X window,
	install graphviz and do:

	./c2g - <input |dot -Txlib

	Dot has other options; -Tps makes a postscript file
*/

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

/*	Token type definitions */
#define	WORD	'W'
#define	NUMBER	'N'
#define	MYEOF	'E'
#define	KINPUT	'I'
#define	KOUTPUT	'O'
#define	KSIGNAL	'S'
#define	INPUTVAR	(KINPUT+('a'-'A'))
#define	OUTPUTVAR	(KOUTPUT+('a'-'A'))
#define	SIGNALVAR	(KSIGNAL+('a'-'A'))

#define	MAXLEX	32		/* Length of maximum lexeme */
#define	MAXFREE	(1024*1024)	/* Size of free char pool */
#define	MAXSYMS	1024		/* Size of symbol table */

#define	MAXGATES (1024*1024)	/* Size of gate pool */
#define	BUSWIDTH 8		/* Bus width */

typedef struct {
	int	arg0, arg1;
	char	op;
	char	needed;
} gate_t;

typedef struct {
	int	wire[BUSWIDTH];
} bus_t;

int	nextt = ' ';
char	lexeme[MAXLEX];
int	lexval;
int	lexsym;
int	nextc = ' ';
int	lineno = 0;

typedef struct {
	int	lexdex;		/* Lexeme index in freec */
	int	typ;		/* Token type */
	bus_t	bus;		/* Bus holding value */
} symtyp;

char	freec[MAXFREE];
int	freecsp = 0;
symtyp	symtab[MAXSYMS];
int	symsp = 0;

int	labno = 0;
int	sp = 0;
int	args = 0;

gate_t	gate[MAXGATES];
int	gatesp = 0;
bus_t	zero = { 0, 0, 0, 0, 0, 0, 0, 0 };

int	dotout = 0;		/* Generate dot output? */

/*	Output stuff
*/

int
mkgate(register int arg0,
register int arg1,
register char op)
{
	/* Make new gate or find old one */
	register int i;

	/* Normalize operand order */
	if (arg0 > arg1) {
		register int t = arg0;
		arg0 = arg1;
		arg1 = t;
	}

	/* Find old one */
	for (i=0; i<gatesp; ++i) {
		if ((gate[i].op == op) &&
		    (gate[i].arg0 == arg0) &&
		    (gate[i].arg1 == arg1)) {
			return(i);
		}
	}

	/* Make new one */
	++gatesp;
	gate[i].op = op;
	gate[i].arg0 = arg0;
	gate[i].arg1 = arg1;
	gate[i].needed = 0;
	return(i);
}

int
and(register int a,
register int b)
{
	/* Simplifications */
	if (a == b) return(a);
	if (a == 0) return(0);
	if (a == 1) return(b);
	if (b == 0) return(0);
	if (b == 1) return(a);

	return(mkgate(a, b, '&'));
}

int
or(register int a,
register int b)
{
	/* Simplifications */
	if (a == b) return(a);
	if (a == 0) return(b);
	if (a == 1) return(1);
	if (b == 0) return(a);
	if (b == 1) return(1);

	return(mkgate(a, b, '|'));
}

int
xor(register int a,
register int b)
{
	/* Simplifications */
	if (a == b) return(0);
	if (a == 0) return(b);
	if (b == 0) return(a);

	return(mkgate(a, b, '^'));
}

#define	not(a)		mkgate(a,1,'^')

bus_t
noter(bus_t a)
{
	register int i;
	bus_t r;

	for (i=0; i<BUSWIDTH; ++i) {
		r.wire[i] = not(a.wire[i]);
	}
	return(r);
}

bus_t
adder(int carry,
bus_t a,
bus_t b)
{
	register int i, x;
	bus_t r;

	/* Add, without carry out */
	for (i=0; i<(BUSWIDTH-1); ++i) {
		x = xor(a.wire[i], b.wire[i]);
		r.wire[i] = xor(carry, x);
		carry = or(and(carry, x), and(a.wire[i], b.wire[i]));
	}
	x = xor(a.wire[i], b.wire[i]);
	r.wire[i] = xor(carry, x);

	return(r);
}

bus_t
muler(bus_t a,
bus_t b)
{
	register int i, j;
	bus_t r;

	for (i=0; i<BUSWIDTH; ++i) {
		r.wire[i] = 0;
	}
	for (i=0; i<BUSWIDTH; ++i) {
		/* Add r += a if b */
		if (b.wire[i] == 1) {
			r = adder(0, r, a);
		} else if (b.wire[i] != 0) {
			bus_t a2;
			for (j=0; j<BUSWIDTH; ++j) {
				a2.wire[j] = and(a.wire[j], b.wire[i]);
			}
			r = adder(0, r, a2);
		}

		/* Shift a <<= 1 */
		for (j=BUSWIDTH-1; j>0; --j) {
			a.wire[j] = a.wire[j-1];
		}
		a.wire[0] = 0;
	}

	return(r);
}

bus_t
lt(bus_t a,
bus_t b)
{
	register int i, x, same;
	bus_t r;

	x = 0;
	same = 1;
	for (i=(BUSWIDTH-1); i>=0; --i) {
		x = or(x, and(same, and(b.wire[i], not(a.wire[i]))));
		same = and(same, not(xor(a.wire[i], b.wire[i])));
	}
	for (i=0; i<BUSWIDTH; ++i) {
		r.wire[i] = x;
	}
	return(r);
}

/*	Error/warning stuff
*/

void
warn(char *mesg)
{
	fprintf(stderr, "Warning near line %d: %s\n", lineno, mesg);
}

void
error(char *mesg)
{
	fprintf(stderr, "Error near line %d: %s\n", lineno, mesg);
	exit(1);
}

/*	Symbol table
*/

int
enter(char *lexeme,
int typ)
{
	register int i;

	if (symsp >= MAXSYMS) {
		error("No space in symbol table");
	}

	symtab[symsp].lexdex = freecsp;
	do {
		if (freecsp >= MAXFREE) {
			error("No space in string table");
		}
		freec[freecsp++] = *lexeme;
	} while (*(lexeme++));

	symtab[symsp].typ = typ;
	for (i=0; i<BUSWIDTH; ++i) {
		/* Make-up unique names for signals here */
		symtab[symsp].bus.wire[i] = -(i + (symsp * BUSWIDTH));
	}
	return(symsp++);
}

int
lookup(char *lexeme)
{
	register int i = symsp-1;

	while (i >= 0) {
		if (strcmp(lexeme, &(freec[ symtab[i].lexdex ])) == 0) {
			return(i);
		}
		--i;
	}

	return(enter(lexeme, WORD));
}

/*	Lexical analyzer
*/

int
advance(void)
{
	if (nextc != EOF) {
		nextc = getchar();
		if (nextc == '\n') ++lineno;
	}
	return(nextc);
}

int
lex(void)
{
more:
	/* At EOF? */
	if ((nextt == MYEOF) || (nextc == EOF)) {
		return(nextt = MYEOF);
	}

	/* Recognize non-tokens */
	if (nextc <= ' ') {
		advance();
		goto more;
	}
	if (nextc == '#') {
		while ((nextc != '\n') && (nextc != EOF)) {
			advance();
		}
		goto more;
	}

	/* Recognize a word */
	if (((nextc <= 'Z') && (nextc >= 'A')) ||
	    ((nextc <= 'z') && (nextc >= 'a')) ||
	    (nextc == '_')) {
		register int i = 0;

		do {
			if (i < MAXLEX) {
				lexeme[i++] = nextc;
			}
			advance();
		} while (((nextc <= 'Z') && (nextc >= 'A')) ||
			 ((nextc <= 'z') && (nextc >= 'a')) ||
			 ((nextc <= '9') && (nextc >= '0')) ||
			 (nextc == '_'));
		lexeme[i] = 0;
		nextt = WORD;
		if ((lexsym = lookup(&(lexeme[0]))) != -1) {
			nextt = symtab[lexsym].typ;
		}
		return(nextt);
	}

	/* Recognize a number */
	if ((nextc <= '9') && (nextc >= '0')) {
		lexval = 0;
		do {
			lexval *= 10;
			lexval += (nextc - '0');
			advance();
		} while ((nextc <= '9') && (nextc >= '0'));
		return(nextt = NUMBER);
	}

	/* Punctuation is all that's left */
	nextt = nextc;
	advance();
	return(nextt);
}

/*	SWAGAC Parser
*/

int
match(register int t)
{
	if (nextt == t) {
		lex();
		return(1);
	}
	return(0);
}

extern bus_t expr(void);
extern int stat(void);

bus_t
expr4(void)
{
	bus_t bus;
	register int i, j;

	switch (nextt) {
	case NUMBER:
		for (i=0; i<BUSWIDTH; ++i) {
			/* Constants are 0 or 1 for each wire */
			bus.wire[i] = ((lexval & (1 << i)) != 0);
		}
		lex();
		return(bus);
	case WORD:
		/* Really shouldn't happen */
		warn("Undefined symbol assumed to be an INPUT");
		symtab[lexsym].typ = INPUTVAR;
		/* Fall through... */
	case INPUTVAR:
	case SIGNALVAR:
		i = lexsym;
		lex();
		return(symtab[i].bus);
	case OUTPUTVAR:
		error("Cannot use OUTPUT symbol as a source");
	}

	if (match('-')) {
		bus = noter(expr4());
		return(adder(1, bus, zero));
	} else if (match('!')) {
		bus = expr4();
		j = bus.wire[0];
		for (i=1; i<BUSWIDTH; ++i) {
			j = or(j, bus.wire[i]);
		}
		j = not(j);
		for (i=0; i<BUSWIDTH; ++i) {
			bus.wire[i] = j;
		}
		return(bus);
	} else if (match('~')) {
		return(noter(expr4()));
	} else if (match('(')) {
		bus_t t = expr();
		if (!match(')')) warn("missing ) assumed");
		return(t);
	}

	error("ill-formed expression");
}

bus_t
expr3(void)
{
	bus_t t = expr4();
	while (match('*')) {
		t = muler(t, expr4());
	}
	return(t);
}

bus_t
expr2(void)
{
	bus_t t = expr3();
	while ((nextt == '+') || (nextt == '-')) {
		register int n = nextt;

		lex();
		switch (n) {
		case '+': t = adder(0, t, expr3()); break;
		case '-': t = adder(1, t, noter(expr3())); break;
		}
	}
	return(t);
}

bus_t
expr1(void)
{
	bus_t t = expr2();
	while ((nextt == '<') || (nextt == '>')) {
		register int n = nextt;

		lex();
		switch (n) {
		case '<': t = lt(t, expr2()); break;
		case '>': t = lt(expr2(), t); break;
		}
	}
	return(t);
}

bus_t
expr(void)
{
	register int i;
	bus_t t = expr1();
	bus_t t2;
	while ((nextt == '&') || (nextt == '|') || (nextt == '^')) {
		register int n = nextt;

		lex();
		t2 = expr1();
		for (i=0; i<BUSWIDTH; ++i) {
			switch (n) {
			case '&': t.wire[i] = and(t.wire[i], t2.wire[i]); break;
			case '|': t.wire[i] = or(t.wire[i], t2.wire[i]); break;
			case '^': t.wire[i] = xor(t.wire[i], t2.wire[i]); break;
			}
		}
	}
	return(t);
}

int
stat(void)
{
	register int t;

	switch (nextt) {
	case WORD:
	case INPUTVAR:
		symtab[lexsym].typ = SIGNALVAR;
		warn("Made symbol a SIGNAL to allow assignment");
	case OUTPUTVAR:
	case SIGNALVAR:
		t = lexsym;
		lex();
		if (!match('=')) warn("Missing = assumed");
		symtab[t].bus = expr();
		if (!match(';')) warn("Missing ; assumed");
		return(1);
	}
	return(0);
}

int
decl(void)
{
	register int t;

	switch (t = nextt) {
	case KINPUT:
	case KOUTPUT:
	case KSIGNAL:
		lex();
		if (nextt != WORD) error("Missing name");
		symtab[lexsym].typ = t + ('a' - 'A');
		lex();
		if (!match(';')) warn("Missing ; assumed");
		return(1);
	}
	return(0);
}

void
prog(void)
{
	while (decl());
	while (stat());
	if (!match(MYEOF)) {
		warn("Missing EOF assumed; additional input ignored");
	}
}

/*	Main
*/

void
recurmark(register int i)
{
	/* Recursively mark needed vars and gates */
	if (i < 0) return;
	if (++(gate[i].needed) > 1) return;
	recurmark(gate[i].arg0);
	recurmark(gate[i].arg1);
}

void
printsym(register int a)
{
	if (a < 0) {
		printf("%s_%u",
		       &(freec[ symtab[(-a) / BUSWIDTH].lexdex ]),
		       ((-a) % BUSWIDTH));
	} else if (a < 2) {
		printf("%u", a);
	} else {
		printf("G%u", a);
	}
}

int
main(int argc, char **argv)
{
	register int i, j;

	dotout = (argc > 1);

	enter("INPUT", KINPUT);
	enter("OUTPUT", KOUTPUT);
	enter("SIGNAL", KSIGNAL);

	mkgate(0, 0, '0');
	mkgate(1, 1, '1');

	lineno = 0;
	nextt = (nextc = ' ');
	lex();
	prog();

	/* Mark which gates are really used */
	for (i=0; i<symsp; ++i) {
		if (symtab[i].typ == OUTPUTVAR) {
			for (j=0; j<BUSWIDTH; ++j) {
				recurmark(symtab[i].bus.wire[j]);
			}
		}
	}

	if (dotout) {
		printf("digraph gates {\n"
		       "size=\"6,4\";\n"
		       "ratio=fill;\n"
		       "remincross=true;\n"
		       "ordering=out;\n"
		       "node [fontname=Helvetica];\n");

		/* Output the logic formula for each gate */
		for (i=2; i<gatesp; ++i) {
			if (gate[i].needed) {
				/* Check for not as special case */
				if ((gate[i].op == '^') &&
				    ((gate[i].arg0 == 1) ||
				     (gate[i].arg1 == 1))) {
					printf("G%u [label=\"~\"];\n", i, gate[i].op);
					printsym((gate[i].arg0 == 1) ?
						 gate[i].arg1 :
						 gate[i].arg0);
					printf(" -> G%u;\n", i);
				} else {
					/* It's not not */
					printf("G%u [label=\"%c\"];\n", i, gate[i].op);
					printsym(gate[i].arg0);
					printf(" -> G%u;\n", i);
					printsym(gate[i].arg1);
					printf(" -> G%u;\n", i);
				}
			}
		}

		/* Spit-out needed INPUT definitions */
		printf("{\n"
		       "rank = same;\n");
		for (i=0; i<symsp; ++i) {
			if (symtab[i].typ == INPUTVAR) {
				for (j=0; j<BUSWIDTH; ++j) {
					printsym(-(j+(i*BUSWIDTH)));
					printf(" [label=\"");
					printsym(-(j+(i*BUSWIDTH)));
					printf("\"];\n");
				}
			}
		}
		printf("}\n");

		/* Spit-out needed OUTPUT definitions */
		printf("{\n"
		       "rank = same;\n");
		for (i=0; i<symsp; ++i) {
			if (symtab[i].typ == OUTPUTVAR) {
				for (j=0; j<BUSWIDTH; ++j) {
					printsym(-(j+(i*BUSWIDTH)));
					printf(" [label=\"");
					printsym(-(j+(i*BUSWIDTH)));
					printf("\"];\n");
				}
			}
		}
		printf("}\n");
		for (i=0; i<symsp; ++i) {
			if (symtab[i].typ == OUTPUTVAR) {
				for (j=0; j<BUSWIDTH; ++j) {
					printsym(symtab[i].bus.wire[j]);
					printf(" -> ");
					printsym(-(j+(i*BUSWIDTH)));
					printf(";\n");
				}
			}
		}

		printf("}\n");
	} else {
		/* Output the logic formula for each gate */
		for (i=2; i<gatesp; ++i) {
			if (gate[i].needed) {
				printf("G%u = ", i);

				/* Check for not as special case */
				if ((gate[i].op == '^') &&
				    ((gate[i].arg0 == 1) ||
				     (gate[i].arg1 == 1))) {
					printf("~ ");
					printsym((gate[i].arg0 == 1) ?
						 gate[i].arg1 :
						 gate[i].arg0);
				} else {
					/* It's not not */
					printsym(gate[i].arg0);
					printf(" %c ", gate[i].op);
					printsym(gate[i].arg1);
				}

				printf(";\n");
			}
		}

		/* Spit-out needed OUTPUT definitions */
		for (i=0; i<symsp; ++i) {
			if (symtab[i].typ == OUTPUTVAR) {
				for (j=0; j<BUSWIDTH; ++j) {
					printsym(-(j+(i*BUSWIDTH)));
					printf(" = ");
					printsym(symtab[i].bus.wire[j]);
					printf(";\n");
				}
			}
		}
	}
}