Add faster interpreter, and some stuff

9 files changed, 372 insertions, 6 deletions

diff --git a/Makefile b/Makefile
index fa4031c..0081677 100644
--- a/Makefile
+++ b/Makefile
@@ -1,17 +1,17 @@
 CC = gcc
-CFLAGS = -Wall -Wextra -O2 -std=c11 -fwrapv
+CFLAGS = -Wall -Wextra -O2 -std=c11 -fwrapv -D_POSIX_C_SOURCE
 
-BIN = bfinter
+TARGETS = bfinter bfinter2
 
 .PHONY: all clean remake
 
-all: $(BIN)
+all: $(TARGETS)
 
 clean:
-	rm -f $(BIN)
+	rm -f $(TARGETS)
 
 remake: clean all
 
 
-$(BIN): $(wildcard *.c *.h)
-	$(CC) $(CFLAGS) $(filter %.c,$^) -o $@
+$(TARGETS): %: %.c
+	$(CC) $(CFLAGS) $^ -o $@
diff --git a/bfinter2 b/bfinter2
new file mode 100755
index 0000000..081d2f3
--- /dev/null
+++ b/bfinter2
diff --git a/bfinter2.c b/bfinter2.c
new file mode 100644
index 0000000..8801090
--- /dev/null
+++ b/bfinter2.c
@@ -0,0 +1,253 @@
+#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);
+}
diff --git a/test/Makefile b/test/Makefile
new file mode 100644
index 0000000..224fc85
--- /dev/null
+++ b/test/Makefile
@@ -0,0 +1,4 @@
+CC = gcc
+CFLAGS = -Wall -Wextra -std=c11 -O2 -fwrapv
+
+all: test brace16
diff --git a/test/brace16 b/test/brace16
new file mode 100755
index 0000000..fb36801
--- /dev/null
+++ b/test/brace16
diff --git a/test/brace16.c b/test/brace16.c
new file mode 100644
index 0000000..58273d3
--- /dev/null
+++ b/test/brace16.c
@@ -0,0 +1,58 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+int expand(char *dst,char ch,int amount){
+#define WRITE(s__) {int l__=strlen(s__); if(dst){memcpy(dst,s__,l__+1); dst+=l__;} written+=l__;}
+#define WGOTO(i__) {while(curpos<i__){WRITE(">"); curpos++;} while(curpos>i__){WRITE("<"); curpos--;}}
+#define WMOVE(i1__,i2__) {int p__=curpos; WGOTO(i1__); WRITE("[-"); WGOTO(i2__); WRITE("+"); WGOTO(i1__); WRITE("]"); WGOTO(p__);}
+	int written=0,curpos=0;
+	switch(str[i]){
+		case '+': //strcpy(p,"+>+[->+<]>[<<->>[-<+>]]<<"); p+=25; break;
+		case '+': //strcpy(p,"+>+[<->[->+<]]>[-<+>]<<"); p+=23; break;
+		case '+':
+			WRITE("+");
+			for(int i=1;i<amount;i++){WGOTO(i); WRITE("+");}
+			for(int i=1;i<amount;i++){
+				WGOTO(i);
+				WRITE("[");
+				WRITE("<->");
+			}
+		case '-': strcpy(p,"->[->+<]>[<<+>>[-<+>]]<-<"); p+=25; break;
+		case '[': strcpy(p,"[->>+>>>+<<<<<]>>>>>[<<<[-<<+>>]+>>>[-]]<<<<[->+>>>+<<<<]>>>>[[-<<<-<+>>>>]<<<+>>>]<<<[[-]<<"); p+=92; break;
+		case ']': strcpy(p,"[->>+>>>+<<<<<]>>>>>[<<<[-<<+>>]+>>>[-]]<<<<[->+>>>+<<<<]>>>>[[-<<<-<+>>>>]<<<+>>>]<<<]<<"); p+=89; break;
+		case '>': strcpy(p,">>>"); p+=3; break;
+		case '<': strcpy(p,"<<<"); p+=3; break;
+		case ',': strcpy(p,"[-]>,<"); p+=6; break;
+		case '.': strcpy(p,">.<"); p+=3; break;
+		default: *(p++)=str[i]; break;
+	}
+	return res;
+#undef WRITE
+#undef WGOTO
+#undef WMOVE
+}
+
+int main(void){
+	int amount=1;
+	char c;
+	while((c=getchar())!=EOF){
+		if(c=='{'){
+			amount++;
+		} else if(c=='}'){
+			amount--;
+			if(amount<=0){
+				fprintf(stderr,"More '}' than '{'\n");
+				return 1;
+			}
+		} else if(amount==1){
+			putchar(c);
+		} else {
+			int len=expand(NULL,c,amount);
+			char *str=malloc(len+1);
+			expand(str,c,amount);
+			printf("%s",str);
+			free(str);
+		}
+	}
+}
diff --git a/test/notes.txt b/test/notes.txt
new file mode 100644
index 0000000..defedd4
--- /dev/null
+++ b/test/notes.txt
@@ -0,0 +1,6 @@
++: +>+[->+<]>[<<->>[-<+>]]<<
+-: ->[->+<]>[<<+>>[-<+>]]<-<
+[: [->>+>>>+<<<<<]>>>>>[<<<[-<<+>>]+>>>[-]]<<<<[->+>>>+<<<<]>>>>[[-<<<-<+>>>>]<<<+>>>]<<<[[-]<<
+]: [->>+>>>+<<<<<]>>>>>[<<<[-<<+>>]+>>>[-]]<<<<[->+>>>+<<<<]>>>>[[-<<<-<+>>>>]<<<+>>>]<<<]<<
+>: >>>
+<: <<<
diff --git a/test/test b/test/test
new file mode 100755
index 0000000..2ea9788
--- /dev/null
+++ b/test/test
diff --git a/test/test.c b/test/test.c
new file mode 100644
index 0000000..bdc11fc
--- /dev/null
+++ b/test/test.c
@@ -0,0 +1,45 @@
+#include <stdio.h>
+#include <stdint.h>
+
+// typedef uint32_t SF;
+// const int ush=24,ssh=31;
+typedef uint16_t SF;
+const int ush=11,ssh=15;
+
+SF mul(SF a,SF b){
+	SF sg=1;
+	if(a>=(1<<ssh)){a=-a; sg*=-1;}
+	if(b>=(1<<ssh)){b=-b; sg*=-1;}
+	return sg*(SF)(((uint64_t)a*(uint64_t)b)>>ush);
+}
+
+SF mk(int i){
+	return i<<ush;
+}
+
+float flt(SF a){
+	float sg=1;
+	if(a>=(1<<ssh)){a=-a; sg*=-1;}
+	return (float)a/(float)(1<<ush)*sg;
+}
+
+int main(void){
+	const SF L=mk(-2),R=mk(1);
+	const SF T=mk(1),B=-(mk(1));
+	for(SF y=T;y!=B-(mk(1)>>4);y-=mk(1)>>4){
+		for(SF x=L;x!=R;x+=mk(1)>>5){
+			int n=0;
+			SF a=x,b=y,a2=mul(a,a),b2=mul(b,b);
+			while(n<26&&a2+b2<mk(4)){
+				b=mul(mk(2),mul(a,b))+y;
+				a=a2-b2+x;
+				a2=mul(a,a);
+				b2=mul(b,b);
+				n++;
+			}
+			if(n==26)putchar(' ');
+			else putchar('A'+n);
+		}
+		putchar('\n');
+	}
+}