OBFI

// Copyright (C) 2020, Jakob Wakeling
// MIT Licence

#include "util/log.h"
#include "util/optget.h"
#include "util/util.h"

#include <errno.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

static inline int cmp(const char *s1, const char *s2);
static inline int run(const char *b, const u64 *c, uptr len);

static const char *const help;
static const char *const version;

int main(int ac, char *av[]) {
	struct opt opt = OPTGET_INIT; opt.str = "l:"; opt.lops = (struct lop[]){
		{ "help",    ARG_NUL, 256 },
		{ "version", ARG_NUL, 257 },
		{ NULL, 0, 0 }
	};

	struct { uptr l; } args = { .l = 30000 };

	for (int o; (o = optget(&opt, av, 1)) != -1;) switch (o) {
	case 'l': {
		register char *s = opt.arg; register int c;
		for (args.l = 0; *s >= '0' && *s <= '9'; s += 1) { c = *s - '0';
			if (args.l > (UPTR_MAX - c) / 10) { break; } args.l = args.l * 10 + c;
		}

		if (*s) { log_fatal(-1, "%s: invalid tape length", opt.arg); } break;
	} break;
	case 256: { fputs(help, stdout);    } return 0;
	case 257: { fputs(version, stdout); } return 0;
	default: {} return -1;
	}

	if (opt.ind == ac) { log_fatal(-1, "missing operand"); }

	/* Open and read source file */
	FILE *file = fopen(av[opt.ind], "r");
	if (!file) { log_fatal(-1, "%s: %s", av[opt.ind], strerror(errno)); }

	fseek(file, 0, SEEK_END); uptr fl = ftell(file); rewind(file);

	/* Instruction operators */
	char *fb = malloc(fl + 1 * sizeof (*fb)); fb[fl] = 0;
	if (!fb) { log_fatal(-1, "%s", strerror(errno)); }

	/* Instruction operands */
	u64 *fc = malloc(fl * sizeof (*fc));
	if (!fc) { log_fatal(-1, "%s", strerror(errno)); }

	fread(fb, 1, fl, file); fclose(file);

	/* Remove comments from instruction buffer */
	register char *p = fb, *q = fb; for (; *p; p += 1) {
		if (strchr("><+-.,[]", *p)) { *q = *p; q += 1; }
	} *q = 0;

	register uptr i, j;
	for (i = 0; fb[i]; i += 1) {
	switch (fb[i]) { /* Generate initial operands */
	case '<': case '-': { fc[i] = -1; break; }
	default:            { fc[i] =  1; break; }
	}
	switch (fb[i]) { /* Standardise instructions */
	case '>': case '<': { fb[i] = '>'; break; }
	case '+': case '-': { fb[i] = '+'; break; }
	}
	}

	/* Compress movement and additive instructions */
	for (i = 0, j = 0; fb[i]; j += 1) {
		fb[j] = fb[i]; fc[j] = fc[i];
		if (strchr(">+", fb[i += 1])) for (; fb[j] == fb[i]; fc[j] += fc[i], i += 1);
	} fb[j] = 0;

	for (i = 0; fb[i]; i += 1) {
		/* Optimise set to zero loops */
		if (cmp(fb + i, "[+]")) { fb[i] = 'Z'; fb[i + 1] = fb[i + 2] = ' '; }

		/* Optimise move to zero loops */
		else if (cmp(fb + i, "[>]")) {
			fb[i] = 'T'; fb[i + 1] = fb[i + 2] = ' '; fc[i] = fc[i + 1];
		}

		/* Optimise backward and forward move to loops */
		else if (cmp(fb + i, "[+>+>]") && fc[i + 1] == -1 && fc[i + 3] == 1 && fc[i + 2] == -fc[i + 4]) {
			fb[i] = 'M';
			fb[i + 1] = fb[i + 2] = fb[i + 3] = fb[i + 4] = fb[i + 5] = ' ';
			fc[i] = fc[i + 2];
		}
		else if (cmp(fb + i, "[>+>+]") && fc[i + 4] == -1 && fc[i + 2] == 1 && fc[i + 1] == -fc[i + 3]) {
			fb[i] = 'M';
			fb[i + 1] = fb[i + 2] = fb[i + 3] = fb[i + 4] = fb[i + 5] = ' ';
			fc[i] = fc[i + 1];
		}
	}

	/* Remove resultant spaces of loop optimisations */
	for (i = 0, j = 0; fb[i]; i += 1) if (fb[i] != ' ') {
		fb[j] = fb[i]; fc[j] = fc[i]; j += 1;
	} fb[j] = 0;

	uptr l = 1024, t = 0, *S = malloc(l * sizeof (*S));
	if (!S) { log_fatal(-1, "%s", strerror(errno)); }

	/* Find and store bracket pairs */
	for (uptr i = 0; fb[i]; i += 1) switch (fb[i]) {
	case '[': { S[t] = i; t += 1; break; }
	case ']': { --t; fc[S[t]] = i - S[t]; fc[i] = S[t] - i; break; }
	}

	if (run(fb, fc, args.l)) { log_fatal(-1, "%s", strerror(errno)); }

	free(S); free(fb); free(fc); return 0;
}

/* Check if s2 is fully matched at the start of s1. */
static inline int cmp(const char *s1, const char *s2) {
	uptr i = 0; for (; s2[i] && s1[i] == s2[i]; i += 1) {} return !s2[i];
}

/* Execute an array of Brainfuck instructions. */
static inline int run(const char *fb, const u64 *fc, uptr len) {
	u8 *M = calloc(len, sizeof (*M)), *p = M + 256; /* Allow slight movement into "negative" memory */
	if (!M) { log_fatal(-1, "%s", strerror(errno)); }

	for (uptr i = 0; fb[i]; i += 1) switch (fb[i]) {
	case '>': { p += fc[i]; } break;
	case '+': { *p += fc[i]; } break;
	case '.': { fputc(*p, stdout); } break;
	case ',': { int c = fgetc(stdin); *p = c != EOF ? c : 0; } break;
	case '[': { i += !*p ? fc[i] : 0; } break;
	case ']': { i +=  *p ? fc[i] : 0; } break;
	case 'Z': { *p = 0; } break;
	case 'T': { for (; *p; p += fc[i]); } break;
	case 'M': { *(p + fc[i]) += *p; *p = 0; } break;
	}

	free(M); return 0;
}

static const char *const help =
	"OBFI - Brainfuck Interpreter\n"
	"Usage:\n"
	"  obfi file\n"
	"Options:\n"
	"  -l length  Set tape length\n"
	"  --help     Display help information\n"
	"  --version  Display version information\n"
;

static const char *const version =
	"OBFI, version " VERSION "\n"
	"Copyright (C) 2020, Jakob Wakeling\n"
	"MIT Licence (https://opensource.org/licenses/MIT)\n"
;