#include <stdio.h>
#include <stdarg.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <inttypes.h>
#include <fcntl.h>
#include <assert.h>
#include <sys/stat.h>

typedef int8_t i8;
typedef uint8_t u8;
typedef int64_t i64;

__attribute__((noreturn))
static void dieperror(const char *func){
	perror(func);
	exit(1);
}

__attribute__((noreturn,format(printf,1,2)))
static void die(const char *format,...){
	va_list ap;
	va_start(ap,format);
	vfprintf(stderr,format,ap);
	va_end(ap);
	exit(1);
}


static int gcd(int a,int b){
	while(b!=0){
		int t=a%b;
		a=b;
		b=t;
	}
	return a;
}


static char* readfile(const char *fname,i64 *length){
	int fd=open(fname,O_RDONLY);
	if(fd<0)dieperror("open");
	struct stat statbuf;
	if(fstat(fd,&statbuf)<0)dieperror("fstat");
	*length=statbuf.st_size;
	FILE *f=fdopen(fd,"r");
	assert(f);
	char *mem=malloc(*length+1);
	assert(mem);
	if((i64)fread(mem,1,*length,f)<*length)die("Invalid file length");
	fclose(f);
	return mem;
}

enum instype {
	IADD,
	ISET,
	ISLIDE,
	ILOOP1,
	ILOOP2,
	IINPUT,
	IOUTPUT,
	IDEBUG,
};

struct ins {
	enum instype type;
	int off;
	u8 value;
};

struct program {
	struct ins *ins;
	i64 len,cap;
};

static struct program p_make(void){
	struct program p;
	p.cap=16;
	p.len=0;
	p.ins=malloc(p.cap*sizeof(struct ins));
	assert(p.ins);
	return p;
}

static void p_ensure(struct program *p,i64 len){
	if(len>p->cap){
		p->cap=len+16;
		p->ins=realloc(p->ins,p->cap*sizeof(struct ins));
		assert(p->ins);
	}
}

static void p_insert(struct program *p,i64 i,struct ins ins){
	p_ensure(p,p->len+1);
	memmove(p->ins+i+1,p->ins+i,(p->len-i)*sizeof(struct ins));
	p->ins[i]=ins;
	p->len++;
}

static void p_append(struct program *p,struct ins ins){
	p_ensure(p,p->len+1);
	p->ins[p->len]=ins;
	p->len++;
}

static void p_erase(struct program *p,i64 i){
	memmove(p->ins+i,p->ins+i+1,(p->len-i)*sizeof(struct ins));
	p->len--;
}

static void p_dump(const struct program p,FILE *f){
	for(i64 i=0;i<p.len;i++){
		switch(p.ins[i].type){
			case IADD:
				fprintf(f,"+%d,%d ",
						p.ins[i].off,(int)(i8)p.ins[i].value);
				break;
			case ISET:
				fprintf(f,"S%d,%d ",
						p.ins[i].off,(int)(i8)p.ins[i].value);
				break;
			case ISLIDE:
				fprintf(f,"%c%d ",
						p.ins[i].off<0?'<':'>',p.ins[i].off);
				break;
			case IINPUT:
				fprintf(f,"I%d ",p.ins[i].off);
				break;
			case IOUTPUT:
				fprintf(f,"O%d ",p.ins[i].off);
				break;
			case ILOOP1:
				fprintf(f,"[%d ",p.ins[i].off);
				break;
			case ILOOP2:
				fprintf(f,"] ");
				break;
			case IDEBUG:
				fprintf(f,"# ");
				break;
		}
	}
	fputc('\n',f);
}

static void p_run(const struct program p){
	i64 *jm=calloc(p.len,sizeof(i64));
	assert(jm);
	{
		i64 cap=16,len=0;
		i64 *stk=malloc(cap*sizeof(i64));
		for(i64 i=0;i<p.len;i++){
			if(p.ins[i].type==ILOOP1){
				if(len==cap){
					cap*=2;
					stk=realloc(stk,cap*sizeof(i64));
					assert(stk);
				}
				stk[len++]=i;
			} else if(p.ins[i].type==ILOOP2){
				if(len==0)die("Jm: mismatched loops");
				jm[stk[len-1]]=i;
				jm[i]=stk[len-1];
				len--;
			}
		}
		free(stk);
	}

	const i64 memsize=60000,startidx=30000;
	u8 *mem=calloc(memsize,1);
	assert(mem);
	for(i64 ip=0,mp=startidx;ip<p.len;ip++){
		switch(p.ins[ip].type){
			case IADD: mem[mp+p.ins[ip].off]+=p.ins[ip].value; break;
			case ISET: mem[mp+p.ins[ip].off]=p.ins[ip].value; break;
			case ISLIDE: mp+=p.ins[ip].off; break;
			case IINPUT: mem[mp+p.ins[ip].off]=getchar(); break;
			case IOUTPUT: putchar(mem[mp+p.ins[ip].off]); break;
			case ILOOP1: if(!mem[mp+p.ins[ip].off])ip=jm[ip]; break;
			case ILOOP2: if(mem[mp+p.ins[ip].off])ip=jm[ip]; break;
			case IDEBUG: {
				int low=0,high=memsize-1;
				while(low<startidx&&mem[low]==0)low++;
				while(high>startidx&&mem[high]==0)high--;
				for(int i=low;i<=high;i++){
					fprintf(stderr,"%3u ",(unsigned)mem[i]);
				}
				fputc('\n',stderr);
				break;
			}
		}
	}

	free(jm);
	free(mem);
}

static struct program parse(const char *source,i64 length){
	struct program p=p_make();
	int offset=0;
	u8 addc=0;
	i64 depth=0;
	for(i64 i=0;i<length;i++){
		if(strchr("+-><,.[]#",source[i])==NULL)continue;
		if(source[i]=='+'){addc++; continue;}
		if(source[i]=='-'){addc--; continue;}
		if(addc!=0)p_append(&p,(struct ins){IADD,offset,addc});
		addc=0;
		if(source[i]=='>'){offset++; continue;}
		if(source[i]=='<'){offset--; continue;}
		if(source[i]==','){
			p_append(&p,(struct ins){IINPUT,offset,0});
			continue;
		}
		if(source[i]=='.'){
			p_append(&p,(struct ins){IOUTPUT,offset,0});
			continue;
		}
		if(offset!=0)p_append(&p,(struct ins){ISLIDE,offset,0});
		offset=0;
		if(source[i]=='['){
			depth++;
			p_append(&p,(struct ins){ILOOP1,offset,0});
			continue;
		}
		if(source[i]==']'){
			if(depth==0)die("Parse: mismatched loops");
			depth--;
			p_append(&p,(struct ins){ILOOP2,0,0});
			continue;
		}
		if(source[i]=='#'){
			p_append(&p,(struct ins){IDEBUG,0,0});
			continue;
		}
	}
	return p;
}


int main(int argc,char **argv){
	if(argc!=2){
		die("Usage: %s <file.bf>\n",argv[0]);
	}
	i64 length;
	char *source=readfile(argv[1],&length);
	struct program p=parse(source,length);
	// p_dump(p,stdout);
	p_run(p);
}