Initial

3 files changed, 406 insertions, 0 deletions

diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..dc06708
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1,4 @@
+bfinter
+*.o
+*.dSYM
+*.bf
diff --git a/Makefile b/Makefile
new file mode 100644
index 0000000..fa4031c
--- /dev/null
+++ b/Makefile
@@ -0,0 +1,17 @@
+CC = gcc
+CFLAGS = -Wall -Wextra -O2 -std=c11 -fwrapv
+
+BIN = bfinter
+
+.PHONY: all clean remake
+
+all: $(BIN)
+
+clean:
+	rm -f $(BIN)
+
+remake: clean all
+
+
+$(BIN): $(wildcard *.c *.h)
+	$(CC) $(CFLAGS) $(filter %.c,$^) -o $@
diff --git a/bfinter.c b/bfinter.c
new file mode 100644
index 0000000..cf4a102
--- /dev/null
+++ b/bfinter.c
@@ -0,0 +1,385 @@
+#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];
+}
+
+void tape_print(const Tape *tape){
+	for(int i=0;i<=tape->maxidx;i++){
+		printf("%3d ",tape->buf[i]);
+	}
+	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); 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);
+
+	interpret(source,sourcelen,jm);
+	
+	jm_destroy(jm);
+	free(source);
+}