#include <stdio.h>
#include <string.h>
#include <ctype.h>
#if	linux
# include <getopt.h>
#endif

#define	MEMSIZE		(1 << 16)	/* 65536 or 2^16 */
#define	MAX_LINE_LEN	256

#define	BRANCH_ON_ZERO		0
#define	BRANCH_ON_NON_NEG	1

const int branch_cond =		BRANCH_ON_NON_NEG;

/*
 * One-Instruction Computer simulator.
 *
 * Bennet S Yee, Oct 97.  bsy@cs.ucsd.edu.
 * Modified, Sep 98.  bsy@cs.ucsd.edu.  Instead of equality to zero,
 * we branch when at least zero.
 *
 * This simulates an one-instruction computer, where the only instruction
 * is
 *	subz a,b,c
 * the semantics of which is
 *	mem[a] = mem[a] - mem[b];
 *	if (mem[a] >= 0) pc = c;
 *	else pc++;
 *
 * The simulator takes -v for verbose execution, -e addr for entry point
 * address, and -s start_addr and -c count to dump out the memory array
 * when the program "terminates".  Termination of the program occurs when
 * the code (intentionally) goes into a tight infinite loop, i.e., an
 * instruction that jumps to itself.
 *
 * Each program file argument is loaded in sequence into memory.  Comments
 * are started with a semicolon.  The first non-comment line of a program
 * file is the starting address into which the instructions from the
 * program file is to be loaded.  The remainder non-comment lines should
 * contain 16-bit triples.  All numbers may be in decimal, octal, or
 * hexidecimal.
 */

typedef	unsigned short	uint16;
typedef int		int32;

/*
 * One-Instruction Computer memory array -- 48 bit words, 64K words.
 */
struct mem {
	uint16	a, b, dst;
} mem[MEMSIZE];

int		verbose = 0;
uint16		max_prog_pc = 0;
int		start_pc = 0;
int		dump_in_decimal = 0;
int		break_addr = -1;	/* illegal address */
unsigned int	max_steps = ~0U;
int		separate_fields = 0;

int	fancyatoi(char	**numpp)
{
	char	*nump = *numpp;
	int	base = 10;
	int	v = 0;
	int	seen_digit = 0;

	while (isspace(*nump))
		++nump;
	if (*nump == '0') {
		if (*++nump == 'x' || *nump == 'X') {
			base = 16;
			++nump;
		} else {
			base = 8;
			seen_digit = 1;
		}
	}
	while (1) {
		switch (*nump) {
		case '8': case '9':
			if (base == 8) return v;
			/* fall through */
		case '0': case '1': case '2': case '3':
		case '4': case '5': case '6': case '7':
			v = v * base;
			v += *nump - '0';
			seen_digit = 1;
			break;
		case 'a': case 'b': case 'c': case 'd':
		case 'e': case 'f':
			if (base != 16) return v;
			v = v * base;
			v += *nump - 'a' + 10;
			seen_digit = 1;
			break;
		case 'A': case 'B': case 'C': case 'D':
		case 'E': case 'F':
			if (base != 16) return v;
			v += *nump - 'A' + 10;
			seen_digit = 1;
			break;
		default:
			if (!seen_digit) return -1;
			*numpp = nump;
			return v;
		}
		++nump;
	}
}

int	lineno;

char	*ignore_comment_fgets(char	*buf,
			      int	buf_size,
			      FILE	*iop)
{
	char	*rv, *semi, *last;

	do {
		rv = fgets(buf,buf_size,iop);
		if (rv == 0) return 0;
		++lineno;
		if (verbose > 3) {
			fprintf(stderr,"Input line %d: \"%s\"\n",lineno,buf);
		}
		semi = strchr(buf,';');
		if (semi) *semi = 0;	/* ignore comments */
		/* strip trailing spaces */
		last = strchr(buf,'\0') - 1;
		while (last >= buf) {
			if (!isspace(*last)) break;
			--last;
		}
		*++last = 0;
	} while (last == buf);	/* if all gone, get next line */
	if (verbose > 2) {
		fprintf(stderr,"Returning line %d: \"%s\"\n",lineno,buf);
	}

	return buf;
}

/*
 * The first line of each file contains the starting PC for the first
 * instruction in the file.  This is like an ORG statement.
 */
uint16	read_program(FILE	*iop,
		     char	*fname)
{
	int	a,b,dst;
	char	line[MAX_LINE_LEN], *p;
	uint16	pc;

	lineno = 0;
	if (!ignore_comment_fgets(line,sizeof line,iop)) {
		fprintf(stderr,"Program \"%s\" had format error at line %d -- address missing\n",fname,lineno);
		exit(1);
	}
	p = line;
	a = fancyatoi(&p);
	if (a == -1) {
		fprintf(stderr,"Program \"%s\" had improper formatted starting address on line %d\n",fname,lineno);
		exit(1);
	}
	pc = a;
	while (ignore_comment_fgets(line,sizeof line,iop)) {
		if (separate_fields) {
			p = line;
			a = fancyatoi(&p);
			b = fancyatoi(&p);
			dst = fancyatoi(&p);
			if (a == -1 || b == -1 || dst == -1) {
				fprintf(stderr,"Program \"%s\" had format error at line %d\n",fname,lineno);
				exit(1);
			}
		} else {
			p = line;
			while (*p && isspace(*p)) ++p;
			if (!strncmp(p,"0x",2)) p += 2;
			if (sscanf(p,"%4x%4x%4x",&a,&b,&dst) != 3) {
				fprintf(stderr,"Program \"%s\" had format error at line %d\n",fname,lineno);
				exit(1);
			}
		}
		mem[pc].a = a;
		mem[pc].b = b;
		mem[pc].dst = dst;
		++pc;
	}
	if (!feof(iop)) {
		fprintf(stderr,"Program \"%s\" had format error at line %d\n",fname,lineno);
		exit(1);
	}
	return pc;
}

/*
 * Just do it!  We simulate the one-instruction computer, terminating
 * when we reach an instruction that jumps to itself, breakpoint, or
 * maximum number of instructions executed.
 */
unsigned int	run_program(void)
{
	uint16		pc = start_pc;
	uint16		lastpc = max_prog_pc + 1;	/* illegal PC */
	uint16		v, v2;
	int		borrow, borrow2;
	uint16		a,b,dst;
	unsigned int	steps = 0;

	while (1) {
		if (verbose) {
			if (dump_in_decimal)
				printf("pc = %d:  subz %d, %d, %d\n",pc,mem[pc].a,mem[pc].b,mem[pc].dst);
			else
				printf("pc = %04x:  subz %04x, %04x, %04x\n",pc,mem[pc].a,mem[pc].b,mem[pc].dst);
		}
		a = mem[pc].a; b = mem[pc].b; dst = mem[pc].dst;
		borrow = borrow2 = 0;
		/* mem[a] = mem[a] - mem[b] */
		v = mem[a].dst - mem[b].dst;
		borrow = (v > mem[a].dst);
		mem[a].dst = v;

		v = mem[a].b - mem[b].b;
		borrow2 = (v > mem[a].b);
		v2 = v - borrow;
		borrow2 |= (v2 > v);
		mem[a].b = v2;

		v = mem[a].a - mem[b].a - borrow2;
		mem[a].a = v;

		if (verbose) {
			if (dump_in_decimal)
				printf("mem[%d] = %d %d %d\n",a,mem[a].a,mem[a].b,mem[a].dst);
			else
				printf("mem[%04x] = %04x %04x %04x\n",a,mem[a].a,mem[a].b,mem[a].dst);
		}

		if ((branch_cond == BRANCH_ON_ZERO &&
		     mem[a].a == 0 &&
		     mem[a].b == 0 &&
		     mem[a].dst == 0) ||
		    (branch_cond == BRANCH_ON_NON_NEG &&
		     ((mem[a].a & (1 << 15)) == 0))) {
			pc = dst;
		} else {
			++pc;
		}
		if (pc == lastpc) {
			printf("End-of-program infinite loop at %d\n",pc);
			break;
		}
		if (pc == break_addr) {
			printf("Breakpoint address reached\n");
			break;
		}
		++steps;
		if (steps == max_steps) {
			printf("Maximum number of steps reached\n");
			break;
		}
		lastpc = pc;
	}
	return steps;
}

void	dump_mem(uint16	addr,
		int	memcount)
{
	while (--memcount >= 0) {
		if (dump_in_decimal) {
			printf("%5d: %5d %5d %5d\n",addr,mem[addr].a,mem[addr].b,mem[addr].dst);
		} else {
			printf("%04x: %04x %04x %04x\n",addr,mem[addr].a,mem[addr].b,mem[addr].dst);
		}
		++addr;
	}
}

int	main(int	ac,
	     char	**av)
{
	int		opt;
	int		memcount = 0x0, startaddr = 0x0;
	unsigned int	icount;
	uint16		pc_max = 0, pc;

	while ((opt = getopt(ac,av,"b:c:de:fm:s:v")) != EOF) switch (opt) {
	case 'b':	break_addr = fancyatoi(&optarg);	break;
	case 'c':	memcount = fancyatoi(&optarg);		break;
	case 'd':	dump_in_decimal = 1;			break;
	case 'e':	start_pc = fancyatoi(&optarg);		break;
	case 'f':	separate_fields = 1;			break;
	case 'm':	max_steps = fancyatoi(&optarg);		break;
	case 's':	startaddr = fancyatoi(&optarg);		break;
	case 'v':	verbose++;				break;
	default:
		fprintf(stderr,"Usage: oic [-s start-dump-addr] [-c dump-count] [-e entry-pt] [-b breakpt-addr] [-m maxsteps] [-dfv] program...\n");
		fprintf(stderr,
			" d - decimal dumps\n"
			" f - allow separate input fields\n"
			" v - incr verbosity level\n");
		exit(1);
	}
	memset(mem,0,sizeof mem);
	if (optind == ac) {
		max_prog_pc = read_program(stdin, "<<standard-input>>");
	} else {
		FILE	*iop;

		for (; optind < ac; optind++) {
			iop = fopen(av[optind],"r");
			if (!iop) {
				perror("oic");
				fprintf(stderr,"oic: could not read program file \"%s\".\n",av[optind]);
				exit(1);
			}
			pc = read_program(iop,av[optind]);
			if (pc > pc_max) pc_max = pc;
			(void) close(iop);
		}
		if (pc_max > max_prog_pc)
			max_prog_pc = pc_max;
	}
	if (verbose > 1) {
		dump_mem(0,max_prog_pc);
	}
	printf("Starting program at PC = %d (0x%04x)\n",start_pc,start_pc);
	icount = run_program();
	dump_mem(startaddr,memcount);
	printf("Program completed in %u (0x%x) steps\n",icount,icount);
	exit(0);
}