Brainfuck Compiler/Interpreter

brainfuck.cpp

// 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;
}