[ /////////////////////// // Brainf**k library // /////////////////////// by igor (with the original idea and some code stolen from http://esoteric.sange.fi/brainfuck/bf-source/lib/VARIA.BF) LAST MODIFIED: October 25, 2004 WTF IS THIS? This is a library of useful functions for a serious Brainf**ker (or "Brainf**k Software Engineer"). The goal is to write enough functions to make it easy to code anything in Brainf**k. See http://www.muppetlabs.com/~breadbox/bf/ for the language reference. WHY?! I will not answer stupid questions. I will just say that I wish the Theory of Computing class I took had covered Brainf**k instead of Turing machine programming - it is so much cleaner! PARAMETER PASSING CONVENTIONS: All functions operate on a stack. Parameters are pushed in the left-to-right order. The pointer points to the last parameter. Everything to the right of the pointer is zero (each function specifies exactly how many cells have to be zero). For example, to call ADD(x, y), pick two adjacent registers, put x in the left one, y in the right one and make sure the pointer is pointing to y. Execute the code for ADD(x, y) listed below. x+y will appear in place of x, y will be zero and the pointer will be pointing to the sum. This is indicated by the string ADD( x, y* ):( x+y*, 0 ) The asterisk shows the pointer position before and after. EFFICIENCY: All of the functions should be optimal (or nearly so) in terms of running time and memory usage. If you find a better implementation of something, I would love to know about it. CONTENTS: 1. GENERAL - LOAD: Load a binary number - DUP: Duplicate [y = x] - SWAP: Swap [x ^= y ^= x ^= y] 2. ARITHMETIC - ADD: Addition [x + y] - SUB: Subtraction [x - y] - MUL: Multiplication [x * y] - DIV: Division [x / y, x % y] 3. BOOLEANS - BOOL: Cast to boolean [!!x] - NEG: Negation [!x] - AND: And (for integers) [x && y] - OR: Or (for integers) [x || y] - XOR: Xor (boolean only!) [!!x ^ !!y] 4. COMPARISON - LESS: Less than [x < y] - EQ: Equality [x == y] 5. STRINGS - READLN: Read a line [gets()] - STRDUP: Duplicate string [strcpy()] ] [ +------------+ | 1. GENERAL | +------------+ ] [--------------- Load a binary number ---------------] LOAD( b0, b1, b2, b3, b4, b5, b6, b7*, 0 ):( x*, 0, 0, 0, 0, 0, 0, 0 ), where x = b0 + 2*b1 + 4*b2 + ... + 128*b7 You can keep as many lines as you need (n-1 for n bits). [>++<-]>[<<+>>-]<< [>++<-]>[<<+>>-]<< [>++<-]>[<<+>>-]<< [>++<-]>[<<+>>-]<< [>++<-]>[<<+>>-]<< [>++<-]>[<<+>>-]<< [>++<-]>[<<+>>-]<< [--------------- Duplicate [y = x] ---------------] DUP( x*, 0, 0 ):( x, x*, 0 ) [>+>+<<-] >>[<<+>>-]< [--------------- Swap [x ^= y ^= x ^= y] ---------------] SWAP( x, y*, 0 ):( y, x*, 0 ) [>+<-] <[>+<-]> >[<<+>>-]< [ +---------------+ | 2. ARITHMETIC | +---------------+ ] [--------------- Addition [x + y] ---------------] ADD( x, y* ):( x+y*, 0 ) [<+>-]< [--------------- Subtraction [x - y] ---------------] SUB( x, y* ):( x-y*, 0 ) [<->-]< [--------------- Multiplication [x * y] ---------------] MUL( x, y*, 0, 0 ):( xy, y*, 0, 0 ) <[>[>+>+<<-] >[<+>-]<< -] >>>[<<<+>>>-]<< [--------------- Division [x / y, x % y] ---------------] DIV( x, y*, 0, 0, 0, 0, 0, 0 ):( x%y, x/y*, 0, 0, 0, 0, 0, 0 ) Dividing by 0 causes an infinite loop. Algorithm: state:( x, q, y, t, ... ) y = q; q = 0; t = !( x < y ); while( t ) { x -= y; q++; t = !( x < y ); } [>+>>+<<<-] <[>+>>+<<<-] >[<+>-] >>> >+< [ <[>>>+>+<<<<-] >>>>[<<<<+>>>>-]< [[-]<+<-<->>>] <- >+< [>->+<<-] >>[<<+>>-]< [<<[-]>>[-]]<< ] <[-]+ >>[<<->>-]<< [>+<-]+ >[<->-]< [ - <[>+>+<<<<->>-] >[<+>-] <<+ <[>>>+>>+<<<<<-] >>>>>[<<<<<+>>>>>-]< >+< [ <[>>>+>+<<<<-] >>>>[<<<<+>>>>-]< [[-]<+<-<->>>] <- >+< [>->+<<-] >>[<<+>>-]< [<<[-]>>[-]]<< ] <[-]+ >>[<<->>-]<< [>+<-]+ >[<->-]< ] <[-]< [ +-------------+ | 3. BOOLEANS | +-------------+ ] [--------------- Cast to boolean [!!x] ---------------] BOOL( x*, 0 ):( 1*, 0 ) if x != 0 BOOL( 0*, 0 ):( 0*, 0 ) [[-]>+<] >[<+>-]< [--------------- Negation [!x] ---------------] NEG( x*, 0 ):( 0*, 0 ) if x != 0 NEG( 0*, 0 ):( 1*, 0 ) [[-]>+<]+ >[<->-]< [--------------- And (for integers) [x && y] ---------------] AND( x, y*, 0 ):( x&&y*, 0, 0 ) <[[-]>[[-]>+<]<] >[-] >[<<+>>-]<< [--------------- Or (for integers) [x || y] ---------------] OR( x, y*, 0 ):( x||y*, 0, 0 ) <[>>[-]+<<[-]] >[>[-]+<[-]] >[<<+>>-]<< [--------------- Xor (boolean only!) [!!x ^ !!y] ---------------] XOR( x, y*, 0 ):( x^y*, 0, 0 ) [[-]>+<] <[[-]>+<] >[<+>->[<<->>-]<] >[<<+>>-]<< [ +---------------+ | 4. COMPARISON | +---------------+ ] [--------------- Less than [x < y] ---------------] LESS( x, y*, 0, 0, 0 ):( 1*, 0, 0, 0, 0 ) iff x < y Algorithm: state: (x, y, r, t, u) r = 1; while( y ) { t = u = x; x = 0; x = u; u = 0; while( t ) { t = 0; x--; y--; r++; } r--; t = 1 - r; while( t ) t = y = 0; } x = 1; while( r ) { r--; x--; } >+< [ <[>>>+>+<<<<-] >>>>[<<<<+>>>>-]< [[-]<+<-<->>>] <- >+< [>->+<<-] >>[<<+>>-]< [<<[-]>>[-]]<< ] <[-]+ >>[<<->>-]<< [--------------- Equality [x == y] ---------------] EQ( x, y*, 0, 0, 0 ):( 1*, 0, 0, 0, 0 ) iff x == y Algorithm: state: (x, y, cx, cy, t) cx = x; cy = y; cx = ( cx && cy ); while( cx ) { cx = 0; x--; y--; cx = x; cy = y; cx = ( cx && cy ); } x = ( x || y ); x = !x; < [>>+>+<<<-] >>>[<<<+>>>-]<< [>>+>+<<<-] >>>[<<<+>>>-]< <[[-]>[[-]>+<]<] >[-] >[<<+>>-]<< [ -<-<-> < [>>+>+<<<-] >>>[<<<+>>>-]<< [>>+>+<<<-] >>>[<<<+>>>-]< <[[-]>[[-]>+<]<] >[-] >[<<+>>-]<< ] < <[>>[-]+<<[-]] >[>[-]+<[-]] >[<<+>>-]<< [[-]>+<]+ >[<->-]< [ +------------+ | 5. STRINGS | +------------+ Notation: Capital letters represent character strings (sequences of non-zero bytes). Most functions need the strings to be null-delimited on both ends, but the zeros are not part of the string. Formally, "*S" means "c0*, c1, ..., cn". "S*" means "c0, c1, ..., cn*". "|S|" means "size of S, in bytes". ] [--------------- Read a line [gets()] ---------------] READLN( 0*, 0, ... ):( 0, S*, 0, 0, 0, 0, 0 ) >+[ , [>+>+<<-] >>[<<+>>-] >++[<+++++>-]< < [>>+>+<<<-] >>>[<<<+>>>-]<< [>>+>+<<<-] >>>[<<<+>>>-]< <[[-]>[[-]>+<]<] >[-] >[<<+>>-]<< [ -<-<-> < [>>+>+<<<-] >>>[<<<+>>>-]<< [>>+>+<<<-] >>>[<<<+>>>-]< <[[-]>[[-]>+<]<] >[-] >[<<+>>-]<< ] < <[>>[-]+<<[-]] >[>[-]+<[-]] >[<<+>>-]<< ] <[-]< [--------------- Duplicate string [strcpy()] ---------------] STRDUP( 0, S*, 0, ... ):( 0, S, 0, S*, 0, 0, 0, 0 ) Algorithm: state: (0, S*, 0, ...) shift S right by 2 places (0, 0, 0, *S, 0, ...) shift S back and copy it (0, S, 0, 0, 0*, S, 0) shift the copy left by 2 (0, S, 0, S*, 0, 0, 0) [ [>>+<<-] <] >>> [ [>]>[>]+[<]<[<] <+>>- [<<+>> [>]>[>]<+[<]<[<]> -] > ] > [ [<<+>>-] >] <<<