/*
 * UM.c
 *
 * New UM Implemtation, fast
 * Jeff Craig <foxxtrot@foxxtrot.net> 
 *
 * 9/27/06
 *
 * Unix Time Stats: (AMD Athlon64 3400+, 1GB RAM)
 *  real    2m18.756s
 *  user    1m53.715s
 *  sys     0m0.480s
 */
#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>

// Defines //////////////////////////////////

#define NUM_REGISTERS 8
#define NUM_ARRAYS 131072

#define OP_CMOVE 	0x00000000
#define OP_ARRINDEX	0x10000000
#define OP_ARRAMEND	0x20000000
#define OP_ADD 		0x30000000
#define OP_MULT 	0x40000000
#define OP_DIV 		0x50000000
#define OP_NAND 	0x60000000
#define OP_HALT 	0x70000000
#define OP_ALLOC 	0x80000000
#define OP_ABAND 	0x90000000
#define OP_OUTPUT 	0xa0000000
#define OP_INPUT 	0xb0000000
#define OP_LOADP 	0xc0000000
#define OP_ORTH 	0xd0000000

#define UM_EOF		0xFFFFFFFF

// Globals //////////////////////////////////

unsigned int regs[NUM_REGISTERS];

unsigned int *arrays[NUM_ARRAYS];
long arrsize[NUM_ARRAYS];

unsigned int *program;  // Pointer to current execution array
unsigned int ef;

// Track Free Arrays

int af[NUM_ARRAYS];
int a_begin, a_end;


// Macros ///////////////////////////////////

#define ARG_A_INDEX(oper) (oper >> 6) & 0x7
#define ARG_B_INDEX(oper) (oper >> 3) & 0x7
#define ARG_C_INDEX(oper) oper & 0x7

#define IMMEDIATE(oper) oper & 0x1FFFFFF
#define ORT_A_INDEX(oper) (oper >> 25) & 0x7

#define INSTRUCTION(oper) (oper & 0xF0000000)

#define A(oper) regs[ARG_A_INDEX(oper)]
#define B(oper) regs[ARG_B_INDEX(oper)]
#define C(oper) regs[ARG_C_INDEX(oper)]

// Functions /////////////////////////////////

void
err (char *msg)
{
	unsigned int i, op;
	fprintf(stderr,"ERROR: %s\n",msg);
#ifdef DEBUG
	op = program[ef-1];
	fprintf(stderr,"DEBUG: ef=%i  OP=0x%x\n",ef-1,op);
	fprintf(stderr,"DEBUG: IN=0x%x, A=0x%x, B=0x%x, C=0x%x\n",INSTRUCTION(op), ARG_A_INDEX(op),ARG_B_INDEX(op),ARG_C_INDEX(op));
	fprintf(stderr,"DEBUG: r0=%i, r1=%i, r2=%i, r3=%i, r4=%i, r5=%i, r6=%i, r7=%i\n",regs[0],regs[1],regs[2],regs[3],regs[4],regs[5],regs[6],regs[7]);
#endif
	for (i = 0 ; i < NUM_ARRAYS ; ++i) {
		if (-1 != arrsize[i]) {
			free(arrays[i]);
		}
	}
	exit(-1);
}

unsigned int
get_free_index()
{
	unsigned int index;
	if (a_begin == a_end) { err("No Available Array Indices"); }
	index = af[a_begin++];
	if (NUM_ARRAYS == a_begin) { a_begin = 0; }
	
	return index;
}

void
put_free_index(unsigned int index)
{
	af[a_end++] = index;
	if (NUM_ARRAYS == a_end) { a_end = 0; }
}

int
is_valid_index(unsigned int array, unsigned int index)
{
	if ( NULL == arrays[array] ) {
		err("Trying to index Invalid Array.");
	}else if ( index >= arrsize[array]) {
		err("Array Index Out of Bounds.");
	}
	return 1;
}

void
initialize()
{
	unsigned int i;
	for (i = 0 ; i < NUM_ARRAYS ; ++i) {
		arrays[i] = NULL;
		arrsize[i] = -1;
		af[i] = i;
	}
	a_begin = 0; a_end = NUM_ARRAYS-1;
	
	for(i = 0 ; i < NUM_REGISTERS ; ++i) {
		regs[i] = 0;
	}

	ef = 0;
	program = NULL;
	
}

unsigned int swapBytes(unsigned int input)
{
    unsigned int output = 0, temp = 0;

    temp = input & 0xFF000000;
    temp = temp >> 24;
    output = temp | output;
    temp = input & 0xFF0000;
    temp = temp >> 8;
    output = temp | output;
    temp = input & 0xFF00;
    temp = temp << 8;
    output = temp | output;
    temp = input & 0xFF;
    temp = temp << 24;
    output = temp | output;
    return output;
}

void
load_program(char *fname)
{
	int i;
	int fd = open(fname, O_RDONLY);
    if (!fd) {
		err("File Open Failed.\n");
    }
    struct stat sbuf;
    if (fstat(fd, &sbuf)) {
		err("fstat failed.");
    }
    arrsize[0] = sbuf.st_size / 4;
    arrays[0] =
	(unsigned int *) calloc(arrsize[0], sizeof(unsigned int));
	program = arrays[0];
    FILE *fs = fdopen(fd, "r");
    fread(program, 1, sbuf.st_size, fs);
    fclose(fs);
    close(fd);
#ifdef ENDIAN
    for (i = 0; i < arrsize[0]; ++i) {
		program[i] = swapBytes(program[i]);
    }
#endif
    a_begin = 1;
}

int
main (int argv, char **argc)
{
	unsigned int i, *a, *b, size;
	char in;
	if (argv != 2) {
		err("Need to provide UM Code file");
	}
	initialize();
	load_program(argc[1]);
	
	while(1) {
		unsigned int op = program[ef++];
		
#ifdef DEBUG
		fprintf(stderr,"DEBUG: ef=%i, op=0x%8x\n",ef-1,op);
#endif
		switch (INSTRUCTION(op)) {
		case OP_CMOVE:
#ifdef DEBUG
			fprintf(stderr,"DEBUG: OP_CMOVE: r%i=0x%x, r%i=0x%x, r%i=0x%x\n",ARG_A_INDEX(op), A(op), ARG_B_INDEX(op), B(op), ARG_C_INDEX(op), C(op));
#endif
			if(C(op)) { A(op) = B(op); }
			break;
		case OP_ARRINDEX:
#ifdef DEBUG
			fprintf(stderr,"DEBUG: OP_ARRINDEX: r%i=0x%x, r%i=0x%x, r%i=0x%x\n",ARG_A_INDEX(op), A(op), ARG_B_INDEX(op), B(op), ARG_C_INDEX(op), C(op));
			if(!is_valid_index(B(op),C(op))) {
				err("Invalid Array Index.");
			}
#endif
			A(op) = arrays[B(op)][C(op)];
			break;
		case OP_ARRAMEND:
#ifdef DEBUG
			fprintf(stderr,"DEBUG: OP_ARRAMEND: r%i=0x%x, r%i=0x%x, r%i=0x%x\n",ARG_A_INDEX(op), A(op), ARG_B_INDEX(op), B(op), ARG_C_INDEX(op), C(op));
			if(!is_valid_index(A(op),B(op))) {
				err("Invalid Array Index.");
			}
#endif		
			arrays[A(op)][B(op)] = C(op);
			break;
		case OP_ADD:
#ifdef DEBUG
			fprintf(stderr,"DEBUG: OP_ADD: r%i=0x%x, r%i=0x%x, r%i=0x%x\n",ARG_A_INDEX(op), A(op), ARG_B_INDEX(op), B(op), ARG_C_INDEX(op), C(op));
#endif
			A(op) = B(op) + C(op);
			break;
		case OP_MULT:
#ifdef DEBUG
			fprintf(stderr,"DEBUG: OP_MULT: r%i=0x%x, r%i=0x%x, r%i=0x%x\n",ARG_A_INDEX(op), A(op), ARG_B_INDEX(op), B(op), ARG_C_INDEX(op), C(op));
#endif
			A(op) = B(op) * C(op);
			break;
		case OP_DIV:
#ifdef DEBUG
			fprintf(stderr,"DEBUG: OP_DIV: r%i=0x%x, r%i=0x%x, r%i=0x%x\n",ARG_A_INDEX(op), A(op), ARG_B_INDEX(op), B(op), ARG_C_INDEX(op), C(op));
#endif
			A(op) = B(op) / C(op);
			break;
		case OP_NAND:
#ifdef DEBUG
			fprintf(stderr,"DEBUG: OP_NAND: r%i=0x%x, r%i=0x%x, r%i=0x%x\n",ARG_A_INDEX(op), A(op), ARG_B_INDEX(op), B(op), ARG_C_INDEX(op), C(op));
#endif
			A(op) = ~(B(op) & C(op));
			break;
		case OP_HALT:
#ifdef DEBUG
			fprintf(stderr,"DEBUG: OP_HALT\n");
#endif
			printf("Program Terminated\n");
			for (i = 0 ; i < NUM_ARRAYS ; ++i) {
				if (-1 == arrsize[i]) {
					free(arrays[i]);
				}
			}
			exit(0);
		case OP_ALLOC:
#ifdef DEBUG
			fprintf(stderr,"DEBUG: OP_ALLOC: r%i=0x%x, r%i=0x%x, r%i=0x%x\n",ARG_A_INDEX(op), A(op), ARG_B_INDEX(op), B(op), ARG_C_INDEX(op), C(op));
#endif
			i = get_free_index();
			arrays[i] = (unsigned int *)calloc(C(op),sizeof(int));
			arrsize[i] = C(op);
			B(op) = i;
			break;
		case OP_ABAND:
#ifdef DEBUG
			fprintf(stderr,"DEBUG: OP_ABAND: r%i=0x%x, r%i=0x%x, r%i=0x%x\n",ARG_A_INDEX(op), A(op), ARG_B_INDEX(op), B(op), ARG_C_INDEX(op), C(op));
			if(arrays[C(op)] == NULL) {
				err("Abandonment of Unallocated Array");
			}
#endif
			arrsize[C(op)] == -1;
			free(arrays[C(op)]);
			arrays[C(op)] == NULL;
			put_free_index(C(op));
			break;
		case OP_OUTPUT:
#ifdef DEBUG
			fprintf(stderr,"DEBUG: OP_OUTPUT: r%i=0x%x, r%i=0x%x, r%i=0x%x\n",ARG_A_INDEX(op), A(op), ARG_B_INDEX(op), B(op), ARG_C_INDEX(op), C(op));
#endif
			printf("%c",C(op));
			break;
		case OP_INPUT:
#ifdef DEBUG
			fprintf(stderr,"DEBUG: OP_INPUT\n");
#endif
			scanf("%c",&in);
			if (EOF == in) { C(op) = UM_EOF; }
			else { C(op) = in; }
			break;
		case OP_LOADP:
#ifdef DEBUG
			fprintf(stderr,"DEBUG: OP_LOADP: r%i=0x%x, r%i=0x%x, r%i=0x%x\n",ARG_A_INDEX(op), A(op), ARG_B_INDEX(op), B(op), ARG_C_INDEX(op), C(op));
			if(arrsize[B(op)] == -1) {
				err("Attempt to Load Program on invalid Array");
			}
#endif
			if (0 != B(op)) { 
				b = arrays[B(op)];
				size = arrsize[B(op)];
				
				free(program);
				program = (unsigned int *)malloc(sizeof(int)*size);
				arrsize[0] = size;
				arrays[0] = program;
				a = program;
		
				for (i = 0 ; i < size ; ++i) {
					*a++ = *b++;
				}
			}
			ef = C(op);
			break;
		case OP_ORTH:
#ifdef DEBUG
			fprintf(stderr,"DEBUG: OP_ORTH: r%i=0x%x, N=0x%x\n",ORT_A_INDEX(op),regs[ORT_A_INDEX(op)],IMMEDIATE(op));
#endif
			regs[ORT_A_INDEX(op)] = IMMEDIATE(op);
			break;
		default:
			err("Unsupported Operation");
		}
	}
}