#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <unistd.h>
#include <errno.h>
#include <assert.h>

typedef unsigned char byte;

int roundup2power(int n){
	if(n&(n-1)){
		n&=n-1;
		while(n&(n-1))n&=n-1;
		n<<=1;
	}
	return n;
}

typedef struct Tape{
	byte *buf;
	int sz;
	int maxidx;
} Tape;

Tape* tape_make(int sz){
	Tape *tape=malloc(sizeof(Tape));
	assert(tape);
	tape->buf=calloc(sz,1);
	assert(tape->buf);
	tape->sz=sz;
	tape->maxidx=0;
	return tape;
}

void tape_set(Tape *tape,int idx,byte val){
	/*static int max=-1,min=0x7fffffff;
	if(idx>max){
		max=idx;
		printf("max=%d\n",idx);
	}
	if(idx<min){
		min=idx;
		printf("min=%d\n",idx);
	}*/
	if(idx>tape->maxidx)tape->maxidx=idx;
	assert(idx>=0);
	if(idx>=tape->sz){
		int newsz=roundup2power(idx+1);
		fprintf(stderr,"newsz=%d\n",newsz);
		byte *newbuf=realloc(tape->buf,newsz);
		assert(newbuf);
		memset(newbuf+tape->sz,0,newsz-tape->sz);
		tape->buf=newbuf;
		tape->sz=newsz;
	}
	tape->buf[idx]=(val%256+256)%256;
}

byte tape_get(const Tape *tape,int idx){
	if(idx<0||idx>=tape->sz)return 0;
	return tape->buf[idx];
}

// pass curidx=-1 for no highlight
void tape_print(const Tape *tape,int curidx){
	for(int i=0;i<=tape->maxidx;i++){
		if(i==curidx)printf("\x1B[4m");
		printf("%3d ",tape->buf[i]);
		if(i==curidx)printf("\x1B[0m");
	}
	putchar('\n');
}


typedef struct Jumpmap{
	int *tg; //targets
} Jumpmap;

void jm_fill(Jumpmap *jm,const char *source,int len){
	int *stack,stacksz=16,stackp=0;
	stack=malloc(stacksz*sizeof(int));
	assert(stack);

	for(int i=0;i<len;i++){
		if(source[i]=='['){
			if(stackp==stacksz-1){
				stacksz*=2;
				int *newstack=realloc(stack,stacksz*sizeof(int));
				assert(newstack);
				stack=newstack;
			}
			stack[stackp++]=i;
		} else if(source[i]==']'){
			assert(stackp>0);
			stackp--;
			jm->tg[i]=stack[stackp];
			jm->tg[stack[stackp]]=i;
		}
	}
}

Jumpmap* jm_make(const char *source,int len){
	Jumpmap *jm=malloc(sizeof(Jumpmap));
	assert(jm);
	jm->tg=malloc(len*sizeof(int));
	assert(jm->tg);
	jm_fill(jm,source,len);
	return jm;
}

void jm_destroy(Jumpmap *jm){
	free(jm->tg);
	free(jm);
}

int jm_get(const Jumpmap *jm,int idx){
	return jm->tg[idx];
}


int readfile(FILE *f,char **bufp){
	int bufsz=256,cursor=0;
	char *buf=malloc(bufsz);
	assert(buf);
	
	while(true){
		int nr=fread(buf+cursor,1,bufsz-cursor-1,f);
		cursor+=nr;
		if(ferror(f)){
			perror("fread");
			exit(1);
		}
		if(feof(f))break;
		if(cursor>=bufsz-1){
			bufsz*=2;
			char *newbuf=realloc(buf,bufsz);
			assert(newbuf);
			buf=newbuf;
		}
	}
	*bufp=buf;
	return cursor;
}


void interpret(const char *source,const int sourcelen,const Jumpmap *jm){
	Tape *tape=tape_make(1024);
	for(int ip=0,mp=0;ip<sourcelen;ip++){
		switch(source[ip]){
			case '+': tape_set(tape,mp,tape_get(tape,mp)+1); break;
			case '-': tape_set(tape,mp,tape_get(tape,mp)-1); break;
			case '>': mp++; break;
			case '<': mp--; break;
			case '.': putchar(tape_get(tape,mp)); fflush(stdout); break;
			case ',': tape_set(tape,mp,(byte)getchar()); break;
			case '[': if(!tape_get(tape,mp))ip=jm_get(jm,ip); break;
			case ']': if(tape_get(tape,mp))ip=jm_get(jm,ip); break;
			case '#': tape_print(tape,mp); break;

			case '0': tape_set(tape,mp,0); break;
			case '^': ip++; tape_set(tape,mp,tape_get(tape,mp)+(byte)source[ip]); break;
			case '@': ip++; mp+=(char)source[ip]; break;
			case 'T':{
				ip++;
				int nplaces=(byte)source[ip++];
				int cond=tape_get(tape,mp);
				if(cond==0){
					ip+=2*nplaces-1;
					break;
				}
				int locs[nplaces],incrs[nplaces];
				//fprintf(stderr,"TRANS(=%d,%d){",tape_get(tape,mp),nplaces);
				for(int l=0;l<nplaces;l++){
					locs[l]=(char)source[ip++];
					incrs[l]=(unsigned char)source[ip++];
					//fprintf(stderr,"%d+=%d,",locs[l],incrs[l]);
				}
				ip--;
				//fprintf(stderr,"}\n");
				tape_set(tape,mp,0);
				if(cond)for(int l=0;l<nplaces;l++){
					tape_set(tape,mp+locs[l],tape_get(tape,mp+locs[l])+incrs[l]*cond);
				}
				break;
			}
		}
	}
}

void cleanup(char *source,int *sourcelen){
	int i,j;
	const int len=*sourcelen;
	for(i=0,j=0;i<len;i++){
		if(strchr("+-><.,[]#",source[i])!=NULL){
			if(j<i)source[j]=source[i];
			j++;
		}
	}
	if(j<*sourcelen)source[j]=0;
	*sourcelen=j;
}

void optimise(char *source,int *sourcelen){
	int i,j;
	const int len=*sourcelen;
	int plus=0,shift=0;
	for(i=0,j=0;i<len;i++){
		if(plus&&source[i]!='+'&&source[i]!='-'){
			//fprintf(stderr,"plus: %d\n",plus);
			if(plus==-1)source[j++]='-';
			else if(plus==1)source[j++]='+';
			else {
				source[j++]='^';
				source[j++]=(plus%256+256)%256;
			}
			plus=0;
		}

		if(shift&&source[i]!='>'&&source[i]!='<'){
			//fprintf(stderr,"shift: %d\n",shift);
			if(shift==-1)source[j++]='<';
			else if(shift==1)source[j++]='>';
			else {
				//fprintf(stderr,"shift=%d\n",shift);
				while(shift>127){
					source[j++]='@';
					source[j++]=127;
					shift-=127;
				}
				if(shift==1){
					source[j++]='>';
					shift=0;
				}
				if(shift>0){
					source[j++]='@';
					source[j++]=shift;
					shift=0;
				}
				while(shift<-128){
					source[j++]='@';
					source[j++]=-128;
					shift+=128;
				}
				if(shift==-1){
					source[j++]='<';
					shift=0;
				}
				if(shift<0){
					source[j++]='@';
					source[j++]=shift;
					shift=0;
				}
			}
			shift=0;
		}

		if(source[i]=='+'||source[i]=='-'){
			plus+=2*(source[i]=='+')-1;
			continue;
		}

		if(source[i]=='>'||source[i]=='<'){
			shift+=2*(source[i]=='>')-1;
			continue;
		}

		if(i<=len-3&&memcmp(source+i,"[-]",3)==0){
			//fprintf(stderr,"zero\n");
			source[j++]='0';
			i+=2;
			continue;
		}
		if(source[i]=='['){
			int k;
			for(k=i+1;k<len;k++){
				if(source[k]==']')break;
				if(strchr("><+-",source[k])==NULL){
					k=-1;
					break;
				}
			}
			if(k==-1){
				if(j<i)source[j]=source[i];
				j++;
				continue;
			}
			int endidx=k;

			//fprintf(stderr,"transferloop: index=%d\n",i);
			int nplaces=0;
			for(k=i+1;source[k]!=']';k++){
				nplaces+=source[k]=='+'||source[k]=='-';
			}
			int locs[nplaces],incrs[nplaces];
			nplaces=0;
			int position=0,l;
			for(k=i+1;source[k]!=']';k++){
				if(source[k]=='>'||source[k]=='<'){
					position+=2*(source[k]=='>')-1;
					if(position>127||position<-128){
						k=-1;
						break;
					}
				} else {
					for(l=0;l<nplaces;l++)if(locs[l]==position)break;
					if(l==nplaces){
						nplaces++;
						locs[l]=position;
						incrs[l]=0;
					}
					incrs[l]=((incrs[l]+2*(source[k]=='+')-1)%256+256)%256;
				}
			}
			//fprintf(stderr,"TL: original: ");
			//fwrite(source+i,1,endidx-i+1,stderr);
			//fputc('\n',stderr);
			//fprintf(stderr,"TL: "); for(l=0;l<nplaces;l++)fprintf(stderr,"%d+=%d ",locs[l],incrs[l]); fputc('\n',stderr);
			if(k==-1||nplaces<=1||nplaces>256||position!=0){
				//fprintf(stderr,"TL: nplaces=%d invalid, or position=%d invalid or not zero\n",nplaces,position);
				if(j<i)source[j]=source[i];
				j++;
				continue;
			}

			for(l=0;l<nplaces;l++){
				if(locs[l]==0)break;
			}
			if(l==nplaces||incrs[l]!=255){
				//fprintf(stderr,"TL: increment on condition cell not -1\n");
				if(j<i)source[j]=source[i];
				j++;
				continue;
			}

			source[j++]='T';
			source[j++]=(unsigned char)(nplaces-1);
			for(l=0;l<nplaces;l++){
				if(locs[l]==0)continue;
				source[j++]=(char)locs[l];
				source[j++]=(unsigned char)incrs[l];
			}
			i=endidx;
			continue;
		}

		//fprintf(stderr,"copy '%c'\n",source[i]);
		if(j<i)source[j]=source[i];
		j++;
	}
	*sourcelen=j;
}


int main(int argc,char **argv){
	char *source;
	int sourcelen;

	if(argc==1||strcmp(argv[1],"-")==0){
		sourcelen=readfile(stdin,&source);
	} else {
		FILE *f=fopen(argv[1],"rb");
		if(!f){
			perror("fopen");
			return 1;
		}
		sourcelen=readfile(f,&source);
		fclose(f);
	}

	//cleanup() necessary to remove the special optimiser
	//chars that might be present in the original source
	cleanup(source,&sourcelen);
	optimise(source,&sourcelen); //may be omitted if desired

#if 0
	fwrite(source,1,sourcelen,stdout);
	fflush(stdout);
	return 0;
#endif

	Jumpmap *jm=jm_make(source,sourcelen);

	clearerr(stdin);
	interpret(source,sourcelen,jm);
	
	jm_destroy(jm);
	free(source);
}