Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Brainfuck Compiler/Interpreter
// 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
You can’t perform that action at this time.