/*	c2g07.c

	Code for you to modify... by H. Dietz, Fall 2007

	Your task is to modify this code so that it generates
	all operations as the SAME TYPE OF GATE.  That type
	may be ITE, NAND, or NOR.  Because NAND and NOR are
	binary operators, they are slightly easier than ITEs
	for the current code structure.

	Focus your attention around mkgate().  There are
	currently helper routines that implement and(), or(),
	xor(), and not() by calling mkgate(); think in terms
	of modifying these to generate the equivalent gates
	using only the gate type that you have selected.

	There is also a small part of the main() which might
	need to be modified to print the resulting design.
*/

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

/*	Gate types */
#define	ITE	'?'
#define	NAND	'$'
#define	NOR	'@'

/*	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, arg2;
	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 };


/*	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, '^'));
}

int
not(register int a)
{
	mkgate(a, a, '~');
}

bus_t
noter(bus_t a)
{
	register int i;

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

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()
{
	register int i, j;

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

	/* 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 */
			switch (gate[i].op) {
			case '&':
				printf("AND(");
				printsym(gate[i].arg0);
				printf(", ");
				printsym(gate[i].arg1);
				printf(")");
				break;
			case '|':
				printf("OR(");
				printsym(gate[i].arg0);
				printf(", ");
				printsym(gate[i].arg1);
				printf(")");
				break;
			case '^':
				printf("XOR(");
				printsym(gate[i].arg0);
				printf(", ");
				printsym(gate[i].arg1);
				printf(")");
				break;
			case '~':
				printf("NOT(");
				printsym(gate[i].arg0);
				printf(")");
				break;
			case ITE:
				printf("(");
				printsym(gate[i].arg0);
				printf(" ? ");
				printsym(gate[i].arg1);
				printf(" : ");
				printsym(gate[i].arg2);
				printf(")");
				break;
			case NAND:
				printf("NAND(");
				printsym(gate[i].arg0);
				printf(", ");
				printsym(gate[i].arg1);
				printf(")");
				break;
			case NOR:
				printf("NOR(");
				printsym(gate[i].arg0);
				printf(", ");
				printsym(gate[i].arg1);
				printf(")");
				break;
			default:
				printf("0x%x(", gate[i].op);
				printsym(gate[i].arg0);
				printf(",");
				printsym(gate[i].arg1);
				printf(",");
				printsym(gate[i].arg2);
				printf(")");
				break;
			}

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