Last active
May 20, 2025 18:46
Revisions
-
rdebath created this gist
Oct 29, 2014 .There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -0,0 +1,73 @@ This archive contains the following programs: bfc The compiler for the 'brainfuck' language (240 bytes!) bfc.asm Source for the compiler bfi The interpreter for the 'brainfuck' language bfi.c Source for the interpreter (portable) src/ Some example programs in 'brainfuck' src/atoi.b Reads a number from stdin src/div10.b Divides the number under the pointer by 10 src/hello.b The ubiquitous "Hello World!" src/mul10.b Multiplies the number under the pointer by 10 src/prime.b Computes the primes up the a variable limit src/varia.b Small program elements like SWAP, DUP etc. WHATS NEW ========= Yes, I squeezed another ridiculous 56 bytes out of the compiler. They have their price, though: The new compiler requires OS 2.0, operates on a byte array instead of longwords, and generates executables that are always 64K in size. Apart from that the language hasn't changed. Again: *** OS 2.0 *required* for the compiler and the compiled programs *** The interpreter works fine under any OS version. And yes, thanks to Chris Schneider for his ideas how to make the compiler shorter. THE LANGUAGE ============ The language 'brainfuck' knows the following commands: Cmd Effect Equivalent in C --- ------ --------------- + Increases element under pointer array[p]++; - Decrases element under pointer array[p]--; > Increases pointer p++; < Decreases pointer p--; [ Starts loop, counter under pointer while(array[p]) { ] Indicates end of loop } . Outputs ASCII code under pointer putchar(array[p]); , Reads char and stores ASCII under ptr array[p]=getchar(); All other characters are ignored. The 30000 array elements and p are being initialized to zero at the beginning. Now while this seems to be a pretty useless language, it can be proven that it can compute every solvable mathematical problem (if we ignore the array size limit and the executable size limit). THE COMPILER ============ The compiler does not check for balanced brackets; they better be. It reads the source from stdin and writes the executable to stdout. Note that the executable is always 65536 bytes long, and usually won't be executable if brackets aren't balanced. OS 2.0 required for the compiler and the compiled program. THE INTERPRETER =============== For debugging, there's also an interpreter. It expects the name of the program to interpret on the command line and accepts an additional command: Whenever a '#' is met in the source and a second argument was passwd to the interpreter, the first few elements of the array are written to stdout as numbers Enjoy -Urban Mueller <[email protected]> Binary file not shown.This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -0,0 +1,150 @@ EXEOBJ OUTPUT bfc OBJSIZE EQU 65536 CODSIZE EQU 32000 read EQU -$2a write EQU -$30 input EQU -$36 output EQU -$3c closlib EQU -$19e ; d0 ; d1 len ; d2 ; d3 1 ; d4 byte ; d5 offset ; d6 ; d7 ; a0 ; a1 ; a2 stack ; a3 cdptr ; a4 4 ; a5 code ; a6 initcode: dc.l $3f3,0,1,0,0,OBJSIZE/4-9,$3e9,OBJSIZE/4-9 lea (CODSIZE,pc),a5 moveq #4,d0 move.l d0,a4 move.l (a4),a6 jsr -810(a6) move.l d0,a6 moveq #1,d3 initcode2: clrmem move.l a5,a2 moveq #-1,d5 .. clr.b (a2)+ dbra d5,.. move.w #$3f2,-(a2) move.l a5,a2 move.b d3,(a5) mainloop move.b (a5),d4 lea (code,pc),a3 .. move.b (a3)+,d5 move.b (a3)+,d1 cmp.b (a3)+,d4 blo.b .. bne.b advance add.l d5,a3 copy move.b (a3)+,(a5)+ subq.b #1,d1 bne.b copy addq.b #8,d5 bcc.s noloop move.l a5,-(a2) noloop addq.b #3,d5 bne.s noendl move.l (a2)+,a0 move.l a0,d0 sub.l a5,d0 move.w d0,(a5)+ neg.w d0 subq.w #4,d0 move.w d0,-(a0) noendl advance clr.b (a5) readbyte jsr input(a6) move.l d0,d1 move.l a5,d2 jsr read(a6) readbyte2 tst.b d4 bne.s mainloop move.l a2,a5 swap d3 writebyte jsr output(a6) move.l d0,d1 move.l a5,d2 jsr write(a6) writebyte2 cleanup move.l a6,a1 move.l (a4),a6 jsr closlib(a6) moveq #0,d0 rts cleanup2 rightcode: addq.l #1,a5 leftcode: subq.l #1,a5 endwcode addcode: addq.b #1,(a5) subcode: subq.b #1,(a5) dc.w $6600 endwcode2 whilecode: dc.w $6000 whilecode2 code: endw: dc.b endwcode-endw-3,6,']' while: dc.b whilecode-while-3,4,'[' right: dc.b rightcode-right-3,2,'>' left: dc.b leftcode-left-3,2,'<' out: dc.b writebyte-out-3,writebyte2-writebyte,'.' sub: dc.b subcode-sub-3,2,'-' in: dc.b readbyte-in-3,readbyte2-readbyte,',' add: dc.b addcode-add-3,2,'+' beg: dc.b (initcode-beg-3)&$FF,initcode2-initcode,1 end: dc.b cleanup-end-3,cleanup2-cleanup,0 dx.b OBJSIZE+CODSIZE END Binary file not shown.This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -0,0 +1,59 @@ #include <stdio.h> int p, r, q; char a[5000], f[5000], b, o, *s=f; void interpret(char *c) { char *d; r++; while( *c ) { //if(strchr("<>+-,.[]\n",*c))printf("%c",*c); switch(o=1,*c++) { case '<': p--; break; case '>': p++; break; case '+': a[p]++; break; case '-': a[p]--; break; case '.': putchar(a[p]); fflush(stdout); break; case ',': a[p]=getchar();fflush(stdout); break; case '[': for( b=1,d=c; b && *c; c++ ) b+=*c=='[', b-=*c==']'; if(!b) { c[-1]=0; while( a[p] ) interpret(d); c[-1]=']'; break; } case ']': puts("UNBALANCED BRACKETS"), exit(0); case '#': if(q>2) printf("%2d %2d %2d %2d %2d %2d %2d %2d %2d %2d\n%*s\n", *a,a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8],a[9],3*p+2,"^"); break; default: o=0; } if( p<0 || p>100) puts("RANGE ERROR"), exit(0); } r--; chkabort(); } main(int argc,char *argv[]) { FILE *z; q=argc; if(z=fopen(argv[1],"r")) { while( (b=getc(z))>0 ) *s++=b; *s=0; interpret(f); } } This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -0,0 +1,39 @@ ==== ==== ==== cont digi num ==== ==== ==== + [ - cont=0 >, ======SUB10====== ---------- [ not 10 <+> cont=1 =====SUB38====== ---------- ---------- ---------- -------- > =====MUL10======= [>+>+<<-]>>[<<+>>-]< dup >>>+++++++++ [ <<< [>+>+<<-]>>[<<+>>-]< dup [<<+>>-] >>- ] <<<[-]< ======RMOVE1====== < [>+<-] ] < ] >>[<<+>>-]<< # This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -0,0 +1,16 @@ ==== ==== ==== ==== ==== num ten tmp bool div ==== ==== ==== ==== ==== >+++++++++< [ >>>+<< bool= 1 [>+>[-]<<-] bool= ten==0 >[<+>-] ten = tmp >[<<++++++++++>>>+<-] if ten=0 ten=10 inc div <<- dec ten <- dec num ] >>>>[<<<<+>>>>-]<<<< copy div to num >[-]< clear ten This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -0,0 +1,4 @@ >+++++++++[<++++++++>-]<.>+++++++[<++++>-]<+.+++++++..+++.[-]>++++++++[<++++>-] <.#>+++++++++++[<+++++>-]<.>++++++++[<+++>-]<.+++.------.--------.[-]>++++++++[ <++++>-]<+.[-]++++++++++. This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -0,0 +1,10 @@ =====MUL10======= [>+<-]> ; move num one right ie num2=num >>++++++++++ ; load 10 into fourth element [ <<[<+>>+<-] ; add num2 to first and third element >[<+>-]> ; num2=third element - ; loop ten times ] <<[-]< ; clear num2 # This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -0,0 +1,221 @@ =================================================================== ======================== OUTPUT STRING ============================ =================================================================== >++++++++[<++++++++>-]<++++++++++++++++.[-] >++++++++++[<++++++++++>-]<++++++++++++++.[-] >++++++++++[<++++++++++>-]<+++++.[-] >++++++++++[<++++++++++>-]<+++++++++.[-] >++++++++++[<++++++++++>-]<+.[-] >++++++++++[<++++++++++>-]<+++++++++++++++.[-] >+++++[<+++++>-]<+++++++.[-] >++++++++++[<++++++++++>-]<+++++++++++++++++.[-] >++++++++++[<++++++++++>-]<++++++++++++.[-] >+++++[<+++++>-]<+++++++.[-] >++++++++++[<++++++++++>-]<++++++++++++++++.[-] >++++++++++[<++++++++++>-]<+++++++++++.[-] >+++++++[<+++++++>-]<+++++++++.[-] >+++++[<+++++>-]<+++++++.[-] =================================================================== ======================== INPUT NUMBER ============================ =================================================================== + cont=1 [ - cont=0 >, ======SUB10====== ---------- [ not 10 <+> cont=1 =====SUB38====== ---------- ---------- ---------- -------- > =====MUL10======= [>+>+<<-]>>[<<+>>-]< dup >>>+++++++++ [ <<< [>+>+<<-]>>[<<+>>-]< dup [<<+>>-] >>- ] <<<[-]< ======RMOVE1====== < [>+<-] ] < ] >>[<<+>>-]<< =================================================================== ======================= PROCESS NUMBER =========================== =================================================================== ==== ==== ==== ==== numd numu teid teiu ==== ==== ==== ==== >+<- [ >+ ======DUP====== [>+>+<<-]>>[<<+>>-]< >+<-- >>>>>>>>+<<<<<<<< isprime=1 [ >+ <- =====DUP3===== <[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<<< =====DUP2===== >[>>+>+<<<-]>>>[<<<+>>>-]<<< < >>> ====DIVIDES======= [>+>+<<-]>>[<<+>>-]< DUP i=div << [ >>>>>+ bool=1 <<< [>+>+<<-]>>[<<+>>-]< DUP [>>[-]<<-] IF i THEN bool=0 >> [ IF i=0 <<<< [>+>+<<-]>>[<<+>>-]< i=div >>> - bool=0 ] <<< - DEC i << - ] +>>[<<[-]>>-]<< >[-]< CLR div =====END DIVIDES==== [>>>>>>[-]<<<<<<-] if divides then isprime=0 << >>[-]>[-]<<< ] >>>>>>>> [ - <<<<<<<[-]<< [>>+>+<<<-]>>>[<<<+>>>-]<<< >> =================================================================== ======================== OUTPUT NUMBER =========================== =================================================================== [>+<-]> [ ======DUP====== [>+>+<<-]>>[<<+>>-]< ======MOD10==== >+++++++++< [ >>>+<< bool= 1 [>+>[-]<<-] bool= ten==0 >[<+>-] ten = tmp >[<<++++++++++>>-] if ten=0 ten=10 <<- dec ten <- dec num ] +++++++++ num=9 >[<->-]< dec num by ten =======RROT====== [>+<-] < [>+<-] < [>+<-] >>>[<<<+>>>-] < =======DIV10======== >+++++++++< [ >>>+<< bool= 1 [>+>[-]<<-] bool= ten==0 >[<+>-] ten = tmp >[<<++++++++++>>>+<-] if ten=0 ten=10 inc div <<- dec ten <- dec num ] >>>>[<<<<+>>>>-]<<<< copy div to num >[-]< clear ten =======INC1========= <+> ] < [ =======MOVER========= [>+<-] =======ADD48======== +++++++[<+++++++>-]<-> =======PUTC======= <.[-]> ======MOVEL2======== >[<<+>>-]< <- ] >++++[<++++++++>-]<.[-] =================================================================== =========================== END FOR =============================== =================================================================== >>>>>>> ] <<<<<<<< >[-]< [-] <<- ] ======LF======== ++++++++++.[-] This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -0,0 +1,11 @@ [ most of these require the the numbers to the right of the pointer to be 0 CLR = [-] ADD = [<+>-]< DUP = [>+>+<<-]>>[<<+>>-] SWAP = [>+<-]<[>+<-]>>[<<+>>-]< MUL = >[-]>[-]<< <[>[>+>+<<-] >[<+>-] <-] >>>[<<<+>>>-]<<< IF = >[-]<[>[-]+<-]> (your program here) < ]