summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--.gitignore4
-rw-r--r--Makefile17
-rw-r--r--bfinter.c385
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);
+}