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



/* Configure some constants: */   /* {{{ */

/* Size of "code matrix" (width and height) */
#define MAX_W 256
#define MAX_H 1024

/* Size of "memory array" */
#define MEMORY 65536

/* Size of "call stack" */
#define STACK  8192

/* Show step-by-step debugging info (lots of output at stderr) */
#define STEP_BY_STEP 0

/* Show extra info */
#define PRINT_MEMORY_OVERFLOW  1
#define PRINT_MEMORY_UNDERFLOW 1
#define PRINT_STACK_OVERFLOW   1
#define PRINT_STACK_UNDERFLOW  0

/* }}} */



/* Some typedefs and structs */   /* {{{ */

/* The "internal" state */   /* {{{ */

#define DIR_RIGHT 0
#define DIR_DOWN  1
#define DIR_LEFT  2
#define DIR_UP    3
typedef unsigned char Direction;

typedef struct State {
	short int x,y;  /* Instruction Pointer */
	Direction d;
	long int data;  /* Memory Pointer */
} State;   /* }}} */


/* The call stack */   /* {{{ */

typedef struct StackFrame {  /* Only Instruction Pointer is pushed in stack. */
	short int x,y;
	Direction d;
} StackFrame;   /* }}} */

/* }}} */

/* Global variables: code matrix, memory array and call stack. */   /* {{{ */

unsigned char code[MAX_H][MAX_W];  /* code[y][x] */

unsigned char mem[MEMORY];

long int stack_top;
StackFrame stack[STACK];

/* }}} */



/* Reading code and initializing functions */

int remove_newline(char *s)   /* {{{ */
/* 
  This will remove the CRLF, CR or LF character(s) from end of string.
  Will return 0 if no EOL characters removed (because they were not found).
*/
{
	while(*s) s++;
	s--;
	if(*s=='\n' && *(s-1)=='\r')
	{
		*(s-1)='\0';
		return 1;
	}
	else if(*s=='\n' || *s=='\r')
	{
		*s='\0';
		return 1;
	}
	return 0;
}   /* }}} */

void reset_state(State *s)   /* {{{ */
/* 
  This will reset the state, zeroing all values and setting direction to RIGHT.
*/
{
	if(s)
	{
		s->x = s->y = s->data = 0;
		s->d = DIR_RIGHT;
	}
}   /* }}} */

void read_code(FILE *f, State *state)   /* {{{ */
/*
   This function reads the code matrix from given file.
   If "state" paramater is not NULL, then it will receive the coordinates
   of initial instruction ('$').
*/
{
	register int i,j;
	char s[MAX_W+2];
	char initial_found;

	memset(code,' ',sizeof(code));
	i=j=0;

	reset_state(state);
	initial_found=0;

	while(fgets(s,MAX_W+2,f))
	{
		if(!remove_newline(s))
		{
			fprintf(stderr,"Warning! No newline found at line %d. Current maximum line width is %d.\n",i+1,MAX_W);
		}

		/* Copying the readed line to code matrix. */
		for(j=0; s[j]; j++)
		{
			code[i][j]=s[j];
			if(!initial_found && state!=NULL && s[j]=='$')
			{
				state->x=j;
				state->y=i;
				initial_found=1;
			}
		}
		i++;
	}
}   /* }}} */



/* Debugging function */

void print_state(const State *s)   /* {{{ */
/*
   A simple "state dump", that will print current state. Only useful for debugging.
*/
{
	fprintf(stderr,"x=%4hd\ty=%4hd\top=%c\td=%d\tdata=%5ld\t[data]=%hd\n",s->x,s->y,code[s->y][s->x],s->d,s->data,mem[s->data]);
}   /* }}} */



/* Interpreter functions */

int move(State *s)   /* {{{ */
/*
   Will "move" current Instruction Pointer according current Direction.
   Returns 1 if move "out of code matrix bounds".
   Prints a message and returns 2 if Direction is not known (never should happen).
*/
{
	switch(s->d)
	{
		case DIR_RIGHT:
			if(s->x+1<MAX_W) s->x++;
			else return 1;
			break;
		case DIR_DOWN:
			if(s->y+1<MAX_H) s->y++;
			else return 1;
			break;
		case DIR_LEFT:
			if(s->x>0) s->x--;
			else return 1;
			break;
		case DIR_UP:
			if(s->y>0) s->y--;
			else return 1;
			break;
		default:
			fprintf(stderr,"Unknown direction! x=%hd; y=%hd; d=%d; data=%ld\n",s->x,s->y,s->d,s->data);
			return 2;
	}
	return 0;
}   /* }}} */

int push(const State *s)   /* {{{ */
/*
   Pushes current state (only Instruction Pointer and Direction) to stack.
*/
{
	if(stack_top+1<STACK)
	{
		stack[stack_top].x=s->x;
		stack[stack_top].y=s->y;
		stack[stack_top].d=s->d;
		stack_top++;
		return 0;
	}
	else
		return 1;
}   /* }}} */

int pop(State *s)   /* {{{ */
/*
   Pops Instruction Pointer and Direction from stack.
*/
{
	if(stack_top>0)
	{
		stack_top--;
		s->x=stack[stack_top].x;
		s->y=stack[stack_top].y;
		s->d=stack[stack_top].d;
		return 0;
	}
	else
		return 1;
}   /* }}} */

void run(State *s)   /* {{{ */
/*
   Does all dirty work.
   Currently, uses a given "cpu" (state) and runs one only thread entirely from that.
   No multi-thread support.
*/
{
	char running=1;

	if(s==NULL)
		return;

	while(running)
	{
		if(STEP_BY_STEP) print_state(s);
		switch(code[s->y][s->x])
		{
			case '+': mem[s->data]++; break;
			case '-': mem[s->data]--; break;
			case '>':
				if(s->data+1<MEMORY) s->data++;
				else{ if(PRINT_MEMORY_OVERFLOW) fprintf(stderr,"Memory overflow!\n"); running=0; }
				break;
			case '<':
				if(s->data>0) s->data--;
				else{ if(PRINT_MEMORY_UNDERFLOW) fprintf(stderr,"Memory underflow!\n"); running=0; }
				break;
			case ',': mem[s->data]=getchar(); break;
			case '.': putchar(mem[s->data]); break;
			case '/':
				if     (s->d==DIR_RIGHT) s->d=DIR_UP   ;
				else if(s->d==DIR_UP   ) s->d=DIR_RIGHT;
				else if(s->d==DIR_LEFT ) s->d=DIR_DOWN ;
				else if(s->d==DIR_DOWN ) s->d=DIR_LEFT ;
				break;
			case '\\':
				if     (s->d==DIR_LEFT ) s->d=DIR_UP   ;
				else if(s->d==DIR_UP   ) s->d=DIR_LEFT ;
				else if(s->d==DIR_RIGHT) s->d=DIR_DOWN ;
				else if(s->d==DIR_DOWN ) s->d=DIR_RIGHT;
				break;
			case '!':
				if(move(s)) running=0;
				break;
			case '?':
				if(!mem[s->data])
					if(move(s)) running=0;
				break;
			case '@':
				if(push(s)){ if(PRINT_STACK_OVERFLOW) fprintf(stderr,"Call stack overflow!\n"); running=0; }
				break;
			case '#':
				if(pop(s)){ if(PRINT_STACK_UNDERFLOW) fprintf(stderr,"Call stack underflow!\n"); running=0; }
				else{ if(move(s)) running=0; }
				break;
		}
		if(move(s)) running=0;
	}
}   /* }}} */



/* Main function */

int main(int argc, char *argv[])   /* {{{ */
{
	FILE *f;
	State cpu;

	if(argc != 2)
	{
		fprintf(stderr,"SNUSP - SNUSP's Not Unix, but a Structured Path\n\n");
		fprintf(stderr,"This is a simple Modular SNUSP interpreter, written in pure ANSI C by\n");
		fprintf(stderr,"Denilson Figueiredo de Sá (nickname CrazyTerabyte) in 2004-11-08.\n\n");
		fprintf(stderr,"Current limitations are:\n");
		fprintf(stderr,"Maximum code width  = %d\n",MAX_W);
		fprintf(stderr,"Maximum code height = %d\n",MAX_H);
		fprintf(stderr,"Memory data size    = %d\n",MEMORY);
		fprintf(stderr,"Call stack size     = %d\n",STACK);
		fprintf(stderr,"\nUsage: %s <snusp source file>\n",argv[0]);
		fprintf(stderr,"\nSee some links about SNUSP language:\n");
		fprintf(stderr,"http://www.c2.com/cgi/wiki?SnuspLanguage\n");
		fprintf(stderr,"http://en.wikipedia.org/wiki/SNUSP_programming_language\n");
		fprintf(stderr,"http://www.deepwood.net/~drlion/snusp/snusp-1.0-spec-wd1.pdf\n");
		return 1;
	}

	f=fopen(argv[1],"r");
	if(f)
	{
		read_code(f,&cpu); /* cpu will have coordinates of initial instruction */
		fclose(f);
	}
	else
	{
		fprintf(stderr,"Could not open \"%s\" file.\n",argv[1]);
		return 2;
	}

	memset(mem,0,sizeof(mem));
	stack_top=0;
	run(&cpu);

	return 0;
}   /* }}} */