diff options
| -rw-r--r-- | .gitignore | 4 | ||||
| -rw-r--r-- | Makefile | 17 | ||||
| -rw-r--r-- | bfinter.c | 385 |
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); +} |