Created
November 17, 2014 19:28
-
-
Save joesavage/1ac51554b91b4368fa92 to your computer and use it in GitHub Desktop.
Brainfuck Compiler/Interpreter
This file contains 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 characters
// A small, and relatively primitive, C-style Brainfuck compiler/interpreter. | |
// Written by Joe Savage, 2014 | |
#include <stdlib.h> | |
#include <unistd.h> | |
#include <stdio.h> | |
#include <limits.h> | |
#define STACK_SIZE 512 | |
#define DATA_SIZE 65535 | |
typedef enum { | |
INC_DPTR, | |
DEC_DPTR, | |
INC_DVAL, | |
DEC_DVAL, | |
INPUT, | |
OUTPUT, | |
LOOP_BEGIN, | |
LOOP_END | |
} OperationType; | |
typedef struct { | |
OperationType command; | |
unsigned short operand; | |
} Operation; | |
void usage(void) { | |
fprintf(stderr, "usage: brainfuck [-v] [-o outfile] infile\n"); | |
exit(2); | |
} | |
bool parse(unsigned char *ch, unsigned int filesize, Operation *operations, bool verbose) { | |
unsigned int stack[STACK_SIZE] = {0}; // TODO: Change to dynamic stack size? | |
unsigned int sptr = 0; | |
if (verbose) printf("Parsing...\n"); | |
unsigned int addr = 0; | |
for (unsigned int pos = 0; pos < filesize; pos++) { | |
addr++; | |
switch (*ch) { | |
case '>': | |
operations[addr].command = INC_DPTR; | |
break; | |
case '<': | |
operations[addr].command = DEC_DPTR; | |
break; | |
case '+': | |
operations[addr].command = INC_DVAL; | |
break; | |
case '-': | |
operations[addr].command = DEC_DVAL; | |
break; | |
case ',': | |
operations[addr].command = INPUT; | |
break; | |
case '.': | |
operations[addr].command = OUTPUT; | |
break; | |
case '[': | |
{ | |
operations[addr].command = LOOP_BEGIN; | |
if (sptr == STACK_SIZE) { | |
printf("fatal error: stack overflow at position %d\n", addr); | |
return false; | |
} | |
stack[sptr++] = addr; | |
} | |
break; | |
case ']': | |
{ | |
if (sptr == 0) { | |
printf("fatal error: stack underflow at position %d\n", addr); | |
return false; | |
} | |
unsigned int ret = stack[--sptr]; | |
operations[addr].command = LOOP_END; | |
operations[addr].operand = ret; | |
operations[ret].operand = addr; | |
} | |
break; | |
case ' ': | |
case '\t': | |
case '\n': | |
// This character doesn't correspond to an operation address in the final opcode composition | |
addr--; | |
break; | |
default: | |
printf("fatal error: unrecognised character '%c' at position %d\n", *ch, addr + 1); | |
return false; | |
} | |
ch++; | |
} | |
if (sptr != 0) { | |
printf("fatal error: expected ']' to match character %d\n", stack[sptr]); | |
return false; | |
} | |
// Note: Could perform some optimisation here. (Though in statically compiled | |
// mode, I assume the C compiler does a pretty good job with this anyway) | |
return true; | |
} | |
void compile(Operation *operations, unsigned int length, char *outfile, bool verbose) { | |
if (verbose) printf("Compiling...\n\n"); | |
int indent = 0; | |
FILE *output = fopen(outfile, "w"); | |
if (!output) { | |
perror("brainfuck: cannot open output file"); | |
exit(2); | |
} | |
fprintf(output, "#include <stdio.h>\n\n"); | |
fprintf(output, "int main(int argc, char *argv[]) {\n"); | |
fprintf(output, "\tunsigned short data[%d] = {0};\n", DATA_SIZE); | |
fprintf(output, "\tunsigned short *dptr = data;\n\n"); | |
indent++; | |
for (unsigned int addr = 0; addr < length; addr++) { | |
for(int i = 0; i < indent; i++) | |
fprintf(output, "\t"); | |
switch (operations[addr].command) { | |
case INC_DPTR: | |
fprintf(output, "++dptr;\n"); | |
break; | |
case DEC_DPTR: | |
fprintf(output, "--dptr;\n"); | |
break; | |
case INC_DVAL: | |
fprintf(output, "++*dptr;\n"); | |
break; | |
case DEC_DVAL: | |
fprintf(output, "--*dptr;\n"); | |
break; | |
case INPUT: | |
fprintf(output, "*dptr = (unsigned short)getchar();\n"); | |
break; | |
case OUTPUT: | |
fprintf(output, "putchar(*dptr);\n"); | |
break; | |
case LOOP_BEGIN: | |
// Note: We don't use the command operand for loops as C handles these perfectly fine for us. | |
fprintf(output, "while(*dptr) {\n"); | |
indent++; | |
break; | |
case LOOP_END: | |
if (indent > 0) fseek(output, -1, SEEK_CUR); | |
fprintf(output, "}\n"); | |
indent--; | |
break; | |
default: | |
printf("fatal runtime error: unrecognised internal command %d\n", operations[addr].command); | |
fprintf(output, "/* fatal runtime error: unrecognised internal command */\n"); | |
exit(2); | |
} | |
} | |
fprintf(output, "}\n"); | |
fclose(output); | |
} | |
void execute(Operation *operations, unsigned int length, bool verbose) { | |
unsigned short data[DATA_SIZE] = {0}; | |
unsigned short *dptr = data; | |
if (verbose) printf("Executing...\n\n"); | |
for (unsigned int addr = 0; addr < length; addr++) { | |
switch (operations[addr].command) { | |
case INC_DPTR: | |
++dptr; | |
break; | |
case DEC_DPTR: | |
--dptr; | |
break; | |
case INC_DVAL: | |
++*dptr; | |
break; | |
case DEC_DVAL: | |
--*dptr; | |
break; | |
case INPUT: | |
*dptr = (unsigned short)getchar(); | |
break; | |
case OUTPUT: | |
putchar(*dptr); | |
break; | |
case LOOP_BEGIN: | |
if (!*dptr) | |
addr = operations[addr].operand; | |
break; | |
case LOOP_END: | |
if (*dptr) | |
addr = operations[addr].operand; | |
break; | |
default: | |
printf("fatal runtime error: unrecognised internal command %d", operations[addr].command); | |
exit(2); | |
} | |
} | |
} | |
int main(int argc, char *argv[]) { | |
extern char *optarg; | |
extern int optind; | |
int ch; | |
bool verbose = false, | |
compilation = false; | |
char *outfile; | |
// TODO: Could add options for custom data array size, and cell size. | |
while ((ch = getopt(argc, argv, "vo:")) != EOF) { | |
switch(ch) { | |
case 'v': | |
verbose = true; | |
break; | |
case 'o': | |
compilation = true; | |
outfile = optarg; | |
break; | |
case '?': | |
default: | |
usage(); | |
break; | |
} | |
} | |
argc -= optind; | |
argv += optind; | |
if (argc != 1) | |
usage(); | |
char *infile = *argv; | |
FILE *file; | |
unsigned char *input; | |
unsigned int filesize; | |
file = fopen(infile, "r"); | |
if (!file) { | |
perror("brainfuck: cannot open file"); | |
exit(2); | |
} | |
fseek(file, 0, SEEK_END); | |
filesize = ftell(file); | |
fseek(file, 0, SEEK_SET); | |
if (filesize >= UINT_MAX) { | |
printf("brainfuck: input file too large"); | |
exit(2); | |
} | |
input = (unsigned char *)malloc(filesize); | |
if (!input) { | |
perror("brainfuck: out of memory"); | |
exit(2); | |
} | |
fread(input, filesize, 1, file); | |
fclose(file); | |
Operation *operations = (Operation *)calloc(filesize + 1, sizeof(Operation)); | |
if (!operations) { | |
perror("brainfuck: out of memory"); | |
exit(2); | |
} | |
if (!parse(input, filesize, operations, verbose)) | |
exit(2); | |
if (compilation) | |
compile(operations, filesize, outfile, verbose); | |
else | |
execute(operations, filesize, verbose); | |
free(operations); | |
free(input); | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment