From d45dbeb48a9da2ccfc1dd3fc0f3baea4c365e086 Mon Sep 17 00:00:00 2001 From: jakob Date: Sat, 18 Mar 2017 18:07:39 -0400 Subject: The compilation process now includes *very* minimal code optimization. --- .gitignore | 4 +-- README.md | 7 +----- examples/hello_world.bf | 1 - examples/hello_world_commented.bf | 33 ------------------------ examples/rot13.bf | 1 - examples/rot13_commented.bf | 28 --------------------- skullfuck.c | 53 +++++++++++++++++++++++++++++++++++---- test/hello_world.bf | 1 + test/hello_world_commented.bf | 33 ++++++++++++++++++++++++ test/rot13.bf | 1 + test/rot13_commented.bf | 28 +++++++++++++++++++++ 11 files changed, 114 insertions(+), 76 deletions(-) delete mode 100644 examples/hello_world.bf delete mode 100644 examples/hello_world_commented.bf delete mode 100644 examples/rot13.bf delete mode 100644 examples/rot13_commented.bf create mode 100644 test/hello_world.bf create mode 100644 test/hello_world_commented.bf create mode 100644 test/rot13.bf create mode 100644 test/rot13_commented.bf diff --git a/.gitignore b/.gitignore index 92436a3..ffee194 100644 --- a/.gitignore +++ b/.gitignore @@ -1,3 +1,3 @@ skullfuck -test -test.c +run_tests +run_tests.c diff --git a/README.md b/README.md index 0f8dc25..ad30ca6 100644 --- a/README.md +++ b/README.md @@ -1,17 +1,12 @@ Skullfuck ========= -Skullfuck is a dead simple, non-optimizing compiler for Brainfuck, contained in a single C source file. It outputs binaries targeting amd64 Linux. +Skullfuck is a dead simple, non-optimizing compiler for Brainfuck, contained in a single C source file. It outputs binaries targeting x86_64 and i686 Linux. It depends on GNU Binutils, or any compatible implementation of `as` and `ld`. A good explanation of the history and design behind the language can be found in [the Wikipedia article.](https://en.wikipedia.org/wiki/Brainfuck) -Undefined Behavior ------------------- -The Brainfuck programming language is extremely limited in its specification, and some operations don't have a defined behavior - specifically, operations on an out-of-bounds data pointer are undefined. UB is allowed, but do not expect it to work equally on all platforms. - - TODO ---- * *BSD targeted binaries. diff --git a/examples/hello_world.bf b/examples/hello_world.bf deleted file mode 100644 index ea2b641..0000000 --- a/examples/hello_world.bf +++ /dev/null @@ -1 +0,0 @@ -++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++. \ No newline at end of file diff --git a/examples/hello_world_commented.bf b/examples/hello_world_commented.bf deleted file mode 100644 index fff532c..0000000 --- a/examples/hello_world_commented.bf +++ /dev/null @@ -1,33 +0,0 @@ -++++++++ Set Cell #0 to 8 -[ - >++++ Add 4 to Cell #1; this will always set Cell #1 to 4 - [ as the cell will be cleared by the loop - >++ Add 2 to Cell #2 - >+++ Add 3 to Cell #3 - >+++ Add 3 to Cell #4 - >+ Add 1 to Cell #5 - <<<<- Decrement the loop counter in Cell #1 - ] Loop till Cell #1 is zero; number of iterations is 4 - >+ Add 1 to Cell #2 - >+ Add 1 to Cell #3 - >- Subtract 1 from Cell #4 - >>+ Add 1 to Cell #6 - [<] Move back to the first zero cell you find; this will - be Cell #1 which was cleared by the previous loop - <- Decrement the loop Counter in Cell #0 -] Loop till Cell #0 is zero; number of iterations is 8 - -The result of this is: -Cell No : 0 1 2 3 4 5 6 -Contents: 0 0 72 104 88 32 8 -Pointer : ^ - ->>. Cell #2 has value 72 which is 'H' ->---. Subtract 3 from Cell #3 to get 101 which is 'e' -+++++++..+++. Likewise for 'llo' from Cell #3 ->>. Cell #5 is 32 for the space -<-. Subtract 1 from Cell #4 for 87 to give a 'W' -<. Cell #3 was set to 'o' from the end of 'Hello' -+++.------.--------. Cell #3 for 'rl' and 'd' ->>+. Add 1 to Cell #5 gives us an exclamation point ->++. And finally a newline from Cell #6 diff --git a/examples/rot13.bf b/examples/rot13.bf deleted file mode 100644 index e9e82be..0000000 --- a/examples/rot13.bf +++ /dev/null @@ -1 +0,0 @@ --,+[-[>>++++[>++++++++<-]<+<-[>+>+>-[>>>]<[[>+<-]>>+>]<<<<<-]]>>>[-]+>--[-[<->+++[-]]]<[++++++++++++<[>-[>+>>]>[+[<+>-]>+>>]<<<<<-]>>[<+>-]>[-[-<<[-]>>]<<[<<->>-]>>]<<[<<+>>-]]<[-]<.[-]<-,+] \ No newline at end of file diff --git a/examples/rot13_commented.bf b/examples/rot13_commented.bf deleted file mode 100644 index 85a97fa..0000000 --- a/examples/rot13_commented.bf +++ /dev/null @@ -1,28 +0,0 @@ --,+[ Read first character and start outer character reading loop - -[ Skip forward if character is 0 - >>++++[>++++++++<-] Set up divisor (32) for division loop - (MEMORY LAYOUT: dividend copy remainder divisor quotient zero zero) - <+<-[ Set up dividend (x minus 1) and enter division loop - >+>+>-[>>>] Increase copy and remainder / reduce divisor / Normal case: skip forward - <[[>+<-]>>+>] Special case: move remainder back to divisor and increase quotient - <<<<<- Decrement dividend - ] End division loop - ]>>>[-]+ End skip loop; zero former divisor and reuse space for a flag - >--[-[<->+++[-]]]<[ Zero that flag unless quotient was 2 or 3; zero quotient; check flag - ++++++++++++<[ If flag then set up divisor (13) for second division loop - (MEMORY LAYOUT: zero copy dividend divisor remainder quotient zero zero) - >-[>+>>] Reduce divisor; Normal case: increase remainder - >[+[<+>-]>+>>] Special case: increase remainder / move it back to divisor / increase quotient - <<<<<- Decrease dividend - ] End division loop - >>[<+>-] Add remainder back to divisor to get a useful 13 - >[ Skip forward if quotient was 0 - -[ Decrement quotient and skip forward if quotient was 1 - -<<[-]>> Zero quotient and divisor if quotient was 2 - ]<<[<<->>-]>> Zero divisor and subtract 13 from copy if quotient was 1 - ]<<[<<+>>-] Zero divisor and add 13 to copy if quotient was 0 - ] End outer skip loop (jump to here if ((character minus 1)/32) was not 2 or 3) - <[-] Clear remainder from first division if second division was skipped - <.[-] Output ROT13ed character from copy and clear it - <-,+ Read next character -] End character reading loop diff --git a/skullfuck.c b/skullfuck.c index 7d9e0a8..b40e903 100644 --- a/skullfuck.c +++ b/skullfuck.c @@ -29,9 +29,13 @@ #define ARCH "x86_64" #define OS "Linux" #define INC_DATA_PTR "\tincq %rsi\n" +#define ADD_DATA_PTR "\taddq $0x%x, %%rsi\n" #define DEC_DATA_PTR "\tdecq %rsi\n" +#define SUB_DATA_PTR "\tsubq $0x%x, %%rsi\n" #define INC_DATA "\tincb (%rsi)\n" +#define ADD_DATA "\taddb $0x%x, (%%rsi)\n" #define DEC_DATA "\tdecb (%rsi)\n" +#define SUB_DATA "\tsubb $0x%x, (%%rsi)\n" #define PRINT_DATA "\tmovq $0x01, %rax\n" \ "\tmovq $0x01, %rdi\n" \ "\tsyscall\n" @@ -58,9 +62,13 @@ #define ARCH "i686" #define OS "Linux" #define INC_DATA_PTR "\tincl %ecx\n" +#define ADD_DATA_PTR "\taddl $0x%x, %%ecx\n" #define DEC_DATA_PTR "\tdecl %ecx\n" +#define SUB_DATA_PTR "\tsubl $0x%x, %%ecx\n" #define INC_DATA "\tincb (%ecx)\n" +#define ADD_DATA "\taddb $0x%x, (%%ecx)\n" #define DEC_DATA "\tdecb (%ecx)\n" +#define SUB_DATA "\tsubb $0x%x, (%%ecx)\n" #define PRINT_DATA "\tmovl $0x04, %eax\n" \ "\tmovl $0x01, %ebx\n" \ "\tint $0x80\n" @@ -121,26 +129,57 @@ static int pop_loop_index(struct loop_stack *s) { } +/* Minor optimization subroutine. Increments the `in` pointer to beyond + the collection of adjacent `op` characters, and returns the number + of operations counted. */ +static int reduce(char **in, char op) { + int i; + for (i = 0; (*in)[i] == op; i++); + *in += i - 1; + return i; +} + + /* Converts the brainfuck instructions read from `in` to assembly instructions and writes them to `out`. `in` is expected to be null-terminated. */ static void write_instructions(FILE *out, char *in) { - int next_loop = 0, cur_loop = 0; + int next_loop = 0, cur_loop = 0, op_count; struct loop_stack *loops = calloc(sizeof(struct loop_stack), 1); for (char *cur = in; *cur != '\0'; cur++) { switch(*cur) { case '>': - fputs(INC_DATA_PTR, out); + op_count = reduce(&cur, '>'); + if (op_count > 1) { + fprintf(out, ADD_DATA_PTR, op_count); + } else { + fputs(INC_DATA_PTR, out); + } break; case '<': - fputs(DEC_DATA_PTR, out); + op_count = reduce(&cur, '<'); + if (op_count > 1) { + fprintf(out, SUB_DATA_PTR, op_count); + } else { + fputs(DEC_DATA_PTR, out); + } break; case '+': - fputs(INC_DATA, out); + op_count = reduce(&cur, '+'); + if (op_count > 1) { + fprintf(out, ADD_DATA, op_count); + } else { + fputs(INC_DATA, out); + } break; case '-': - fputs(DEC_DATA, out); + op_count = reduce(&cur, '-'); + if (op_count > 1) { + fprintf(out, SUB_DATA, op_count); + } else { + fputs(DEC_DATA, out); + } break; case '.': fputs(PRINT_DATA, out); @@ -223,6 +262,10 @@ static void create_binary(struct params p) { wait(NULL); } } + + if (!p.compile_only) + remove("/tmp/skullfuck_tmp.s"); + remove("/tmp/skullfuck_tmp.o"); } diff --git a/test/hello_world.bf b/test/hello_world.bf new file mode 100644 index 0000000..ea2b641 --- /dev/null +++ b/test/hello_world.bf @@ -0,0 +1 @@ +++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++. \ No newline at end of file diff --git a/test/hello_world_commented.bf b/test/hello_world_commented.bf new file mode 100644 index 0000000..fff532c --- /dev/null +++ b/test/hello_world_commented.bf @@ -0,0 +1,33 @@ +++++++++ Set Cell #0 to 8 +[ + >++++ Add 4 to Cell #1; this will always set Cell #1 to 4 + [ as the cell will be cleared by the loop + >++ Add 2 to Cell #2 + >+++ Add 3 to Cell #3 + >+++ Add 3 to Cell #4 + >+ Add 1 to Cell #5 + <<<<- Decrement the loop counter in Cell #1 + ] Loop till Cell #1 is zero; number of iterations is 4 + >+ Add 1 to Cell #2 + >+ Add 1 to Cell #3 + >- Subtract 1 from Cell #4 + >>+ Add 1 to Cell #6 + [<] Move back to the first zero cell you find; this will + be Cell #1 which was cleared by the previous loop + <- Decrement the loop Counter in Cell #0 +] Loop till Cell #0 is zero; number of iterations is 8 + +The result of this is: +Cell No : 0 1 2 3 4 5 6 +Contents: 0 0 72 104 88 32 8 +Pointer : ^ + +>>. Cell #2 has value 72 which is 'H' +>---. Subtract 3 from Cell #3 to get 101 which is 'e' ++++++++..+++. Likewise for 'llo' from Cell #3 +>>. Cell #5 is 32 for the space +<-. Subtract 1 from Cell #4 for 87 to give a 'W' +<. Cell #3 was set to 'o' from the end of 'Hello' ++++.------.--------. Cell #3 for 'rl' and 'd' +>>+. Add 1 to Cell #5 gives us an exclamation point +>++. And finally a newline from Cell #6 diff --git a/test/rot13.bf b/test/rot13.bf new file mode 100644 index 0000000..e9e82be --- /dev/null +++ b/test/rot13.bf @@ -0,0 +1 @@ +-,+[-[>>++++[>++++++++<-]<+<-[>+>+>-[>>>]<[[>+<-]>>+>]<<<<<-]]>>>[-]+>--[-[<->+++[-]]]<[++++++++++++<[>-[>+>>]>[+[<+>-]>+>>]<<<<<-]>>[<+>-]>[-[-<<[-]>>]<<[<<->>-]>>]<<[<<+>>-]]<[-]<.[-]<-,+] \ No newline at end of file diff --git a/test/rot13_commented.bf b/test/rot13_commented.bf new file mode 100644 index 0000000..85a97fa --- /dev/null +++ b/test/rot13_commented.bf @@ -0,0 +1,28 @@ +-,+[ Read first character and start outer character reading loop + -[ Skip forward if character is 0 + >>++++[>++++++++<-] Set up divisor (32) for division loop + (MEMORY LAYOUT: dividend copy remainder divisor quotient zero zero) + <+<-[ Set up dividend (x minus 1) and enter division loop + >+>+>-[>>>] Increase copy and remainder / reduce divisor / Normal case: skip forward + <[[>+<-]>>+>] Special case: move remainder back to divisor and increase quotient + <<<<<- Decrement dividend + ] End division loop + ]>>>[-]+ End skip loop; zero former divisor and reuse space for a flag + >--[-[<->+++[-]]]<[ Zero that flag unless quotient was 2 or 3; zero quotient; check flag + ++++++++++++<[ If flag then set up divisor (13) for second division loop + (MEMORY LAYOUT: zero copy dividend divisor remainder quotient zero zero) + >-[>+>>] Reduce divisor; Normal case: increase remainder + >[+[<+>-]>+>>] Special case: increase remainder / move it back to divisor / increase quotient + <<<<<- Decrease dividend + ] End division loop + >>[<+>-] Add remainder back to divisor to get a useful 13 + >[ Skip forward if quotient was 0 + -[ Decrement quotient and skip forward if quotient was 1 + -<<[-]>> Zero quotient and divisor if quotient was 2 + ]<<[<<->>-]>> Zero divisor and subtract 13 from copy if quotient was 1 + ]<<[<<+>>-] Zero divisor and add 13 to copy if quotient was 0 + ] End outer skip loop (jump to here if ((character minus 1)/32) was not 2 or 3) + <[-] Clear remainder from first division if second division was skipped + <.[-] Output ROT13ed character from copy and clear it + <-,+ Read next character +] End character reading loop -- cgit v1.3