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"

;