From 3afec4b3b76bf994b581b28c3a9aeba6bcef0bf7 Mon Sep 17 00:00:00 2001 From: jakob Date: Thu, 16 Mar 2017 20:02:38 -0400 Subject: Implemented support for i686 compilation. --- .gitignore | 2 + Makefile | 5 +- README.md | 8 ++- examples/hello_world.bf | 1 + examples/hello_world_commented.bf | 33 ++++++++++ examples/rot13.bf | 1 + examples/rot13_commented.bf | 28 ++++++++ skullfuck.c | 132 +++++++++++++++++++++++++------------- test/hello_world.bf | 1 - test/hello_world_commented.bf | 33 ---------- 10 files changed, 162 insertions(+), 82 deletions(-) create mode 100644 examples/hello_world.bf create mode 100644 examples/hello_world_commented.bf create mode 100644 examples/rot13.bf create mode 100644 examples/rot13_commented.bf delete mode 100644 test/hello_world.bf delete mode 100644 test/hello_world_commented.bf diff --git a/.gitignore b/.gitignore index 6d5fd39..92436a3 100644 --- a/.gitignore +++ b/.gitignore @@ -1 +1,3 @@ skullfuck +test +test.c diff --git a/Makefile b/Makefile index 7260145..ac2a6ff 100644 --- a/Makefile +++ b/Makefile @@ -1,12 +1,13 @@ CC := gcc -CFLAGS = -Wall -Wextra -Os -std=c99 -pedantic +CFLAGS = -Wall -Os -std=c99 -pedantic +MACROS = -D$(shell uname -m) -DAS=\"$(shell which as)\" -DLD=\"$(shell which ld)\" all: skullfuck skullfuck: skullfuck.c - $(CC) $(CFLAGS) -o skullfuck skullfuck.c + $(CC) $(CFLAGS) $(MACROS) -o skullfuck skullfuck.c clean: skullfuck rm -f skullfuck diff --git a/README.md b/README.md index c09b1c6..0f8dc25 100644 --- a/README.md +++ b/README.md @@ -7,7 +7,13 @@ 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 ---- -* Target 32-bit x86 and *BSD. +* *BSD targeted binaries. * Automate test compilation/running. +* Static analysis to warn when undefined behavior has been detected. diff --git a/examples/hello_world.bf b/examples/hello_world.bf new file mode 100644 index 0000000..ea2b641 --- /dev/null +++ b/examples/hello_world.bf @@ -0,0 +1 @@ +++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++. \ No newline at end of file diff --git a/examples/hello_world_commented.bf b/examples/hello_world_commented.bf new file mode 100644 index 0000000..fff532c --- /dev/null +++ b/examples/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/examples/rot13.bf b/examples/rot13.bf new file mode 100644 index 0000000..e9e82be --- /dev/null +++ b/examples/rot13.bf @@ -0,0 +1 @@ +-,+[-[>>++++[>++++++++<-]<+<-[>+>+>-[>>>]<[[>+<-]>>+>]<<<<<-]]>>>[-]+>--[-[<->+++[-]]]<[++++++++++++<[>-[>+>>]>[+[<+>-]>+>>]<<<<<-]>>[<+>-]>[-[-<<[-]>>]<<[<<->>-]>>]<<[<<+>>-]]<[-]<.[-]<-,+] \ No newline at end of file diff --git a/examples/rot13_commented.bf b/examples/rot13_commented.bf new file mode 100644 index 0000000..85a97fa --- /dev/null +++ b/examples/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 diff --git a/skullfuck.c b/skullfuck.c index e98ea56..0f58198 100644 --- a/skullfuck.c +++ b/skullfuck.c @@ -25,32 +25,80 @@ #include -/* Constants specific to the target architecture. */ -#ifndef MAX_CELLS -#define MAX_CELLS 30000 +#ifdef x86_64 +#define INC_DATA_PTR "\tincq %rsi\n" +#define DEC_DATA_PTR "\tdecq %rsi\n" +#define INC_DATA "\tincb (%rsi)\n" +#define DEC_DATA "\tdecb (%rsi)\n" +#define PRINT_DATA "\tmovq $0x01, %rax\n" \ + "\tmovq $0x01, %rdi\n" \ + "\tsyscall\n" +#define READ_DATA "\tmovq $0x00, %rax\n" \ + "\tmovq $0x00, %rdi\n" \ + "\tsyscall\n" +#define DATA_IS_ZERO "\tmovb (%rsi), %cl\n" \ + "\ttestb %cl, %cl\n" +#define JMP_END "\tjz E%d\n" +#define JMP_START "\tjnz S%d\n" + +#define PRELUDE "\t.section .bss\n" \ + "\t.comm mem, %d\n" \ + "\t.section .text\n" \ + "\t.globl _start\n" \ + "_start:\n" \ + "\tmovq $mem, %%rsi\n" \ + "\tmovq $0x01, %%rdx\n" + +#define EXIT "\tmovq $0x3c, %rax\n" \ + "\tmovq $0x00, %rdi\n" \ + "\tsyscall\n" #endif -#ifndef MAX_LOOP_DEPTH -#define MAX_LOOP_DEPTH 64 + +#ifdef i686 +#define INC_DATA_PTR "\tincl %ecx\n" +#define DEC_DATA_PTR "\tdecl %ecx\n" +#define INC_DATA "\tincb (%ecx)\n" +#define DEC_DATA "\tdecb (%ecx)\n" +#define PRINT_DATA "\tmovl $0x04, %eax\n" \ + "\tmovl $0x01, %ebx\n" \ + "\tint $0x80\n" +#define READ_DATA "\tmovl $0x03, %eax\n" \ + "\tmovl $0x00, %ebx\n" \ + "\tint $0x80\n" +#define DATA_IS_ZERO "\tmovb (%ecx), %al\n" \ + "\ttestb %al, %al\n" +#define JMP_END "\tjz E%d\n" +#define JMP_START "\tjnz S%d\n" + +#define PRELUDE "\t.section .bss\n" \ + "\t.comm mem, %d\n" \ + "\t.section .text\n" \ + "\t.globl _start\n" \ + "_start:\n" \ + "\tmovl $mem, %%ecx\n" \ + "\tmovl $0x01, %%edx\n" + +#define EXIT "\tmovl $0x01, %eax\n" \ + "\tmovl $0x00, %ebx\n" \ + "\tint $0x80\n" #endif +#ifndef AS +#define AS /bin/as +#endif -/* Constants for general usage. */ -#define EXIT_SUCCESS 0 -#define EXIT_FAILURE 1 +#ifndef LD +#define LD /bin/ld +#endif -#define VERSION "0.1.0" +#define MAX_CELLS 30000 +#define MAX_LOOP_DEPTH 64 +#define SKULLFUCK_VERSION "0.2.0" -/* Boilerplate assembly to initialize a memory region on the .bss - segment, and load registers with some constant values. */ -#define PRELUDE "\t.section .bss\n" \ - "\t.comm mem, %d\n" \ - "\t.section .text\n" \ - "\t.globl _start\n" \ - "_start:\n" \ - "\tmovq $mem, %%rsi\n" \ - "\tmovq $0x01, %%rdx\n" +#define EXIT_SUCCESS 0 +#define EXIT_FAILURE 1 @@ -90,48 +138,40 @@ static void write_instructions(FILE *out, char *in) { for (int i = 0; in[i] != '\0'; i++) { switch (in[i]) { case '>': - fputs("\tincq %rsi\n", out); + fputs(INC_DATA_PTR, out); break; case '<': - fputs("\tdecq %rsi\n", out); + fputs(DEC_DATA_PTR, out); break; case '+': - fputs("\tincb (%rsi)\n", out); + fputs(INC_DATA, out); break; case '-': - fputs("\tdecb (%rsi)\n", out); + fputs(DEC_DATA, out); break; case '.': - fputs("\tmovq $0x01, %rax\n", out); - fputs("\tmovq $0x01, %rdi\n", out); - fputs("\tsyscall\n", out); + fputs(PRINT_DATA, out); break; case ',': - fputs("\tmovq $0x00, %rax\n", out); - fputs("\tmovq $0x00, %rdi\n", out); - fputs("\tsyscall\n", out); + fputs(READ_DATA, out); break; case '[': cur_loop = next_loop; push_loop_index(loops, next_loop++); fprintf(out, "S%d:\n", cur_loop); - fputs("\tmovb (%rsi), %cl\n", out); - fputs("\tcmpb $0x00, %cl\n", out); - fprintf(out, "\tje E%d\n", cur_loop); + fputs(DATA_IS_ZERO, out); + fprintf(out, JMP_END, cur_loop); break; case ']': cur_loop = pop_loop_index(loops); fprintf(out, "E%d:\n", cur_loop); - fputs("\tmovb (%rsi), %cl\n", out); - fputs("\tcmpb $0x00, %cl\n", out); - fprintf(out, "\tjne S%d\n", cur_loop); + fputs(DATA_IS_ZERO, out); + fprintf(out, JMP_START, cur_loop); break; } } - fputs("\tmovq $0x3c, %rax\n", out); - fputs("\tmovq $0x00, %rdi\n", out); - fputs("\tsyscall\n", out); + fputs(EXIT, out); free(loops); } @@ -144,12 +184,12 @@ static void panic(char *msg) { } -/* Attempts to create a new file at `path`, and writes a generic prelude - to initialize memory sections. If `path` is NULL, a temporary file - will be created. A FILE pointer will be returned, or NULL if the file +/* Attempts to create a new file at `path`, and writes a boilerplate + prelude to initialize memory segments and load some registers with + constant values. A FILE pointer will be returned, or NULL if the file could not be created. */ static FILE *out_init(char *path) { - FILE *fp = path == NULL ? tmpfile() : fopen(path, "w+"); + FILE *fp = fopen(path, "w+"); if (fp == NULL) return fp; fprintf(fp, PRELUDE, MAX_CELLS); return fp; @@ -179,13 +219,15 @@ static void create_binary(struct params p) { if ((pid = fork()) == -1) { panic("fork"); } else if (pid == 0) { - execv("/bin/as", as_argv); + execv(AS, as_argv); } else { wait(NULL); if ((pid = fork()) == -1) { panic("fork"); } else if (pid == 0) { - execv("/bin/ld", ld_argv); + execv(LD, ld_argv); + } else { + wait(NULL); } } } @@ -221,8 +263,8 @@ static struct params parse_args(int argc, char **argv) { "\t-o file\t\tPlace the output in file.\n"); exit(EXIT_SUCCESS); case 'v': - printf("Skullfuck compiler version %s\nProgrammed by Jakob " - "\n", VERSION); + printf("Skullfuck compiler for Brainfuck, version %s.\nMade " + "by Jakob. \n", SKULLFUCK_VERSION); exit(EXIT_SUCCESS); case 'S': p.compile_only = true; diff --git a/test/hello_world.bf b/test/hello_world.bf deleted file mode 100644 index ea2b641..0000000 --- a/test/hello_world.bf +++ /dev/null @@ -1 +0,0 @@ -++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++. \ No newline at end of file diff --git a/test/hello_world_commented.bf b/test/hello_world_commented.bf deleted file mode 100644 index fff532c..0000000 --- a/test/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 -- cgit v1.3