/*
 * sf2tab.c
 * Smallfuck to lookup-table compiler.
 * By Chris Pressey, Cat's Eye Technologies, circa 2005.
 * + bug fix, Aug 2015: record tape head position as part of state
 *
 * SPDX-FileCopyrightText: Chris Pressey, the original author of this work, has dedicated it to the public domain.
 * For more information, please refer to <https://unlicense.org/>
 * SPDX-License-Identifier: Unlicense
 */

/*
 * This compiler takes programs written in the Smallfuck programming language
 * and converts them to equivalent lookup tables.  This was written mainly to
 * demonstrate what happens when your language is defined over a finite
 * state-space: every program can be run in O(n) time!
 *
 * Some Smallfuck programs that can be used as testcases:
 *     [*>]
 *     []*[]
 *     *[*>[*>]]
 */

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

int prog_size = 256;
int tape_size = 8;
int debug_level = 0;

enum result {
	HALT,
	HANG,
	OFF_LEFT,
	OFF_RIGHT
};

struct state_bucket {
	struct state_bucket *next;
	int hd;                         /* tape head position */
	char *t;			/* tape contents */
};

struct state_bucket **state = NULL;	/* array of bucket ptrs */

void
clear_state(void)
{
	int i;

	/* init state if this is first access */
	if (state == NULL) {
		state = malloc(prog_size * sizeof(struct state_bucket *));
		for (i = 0; i < prog_size; i++) {
			state[i] = NULL;
		}
	}

	for (i = 0; i < prog_size; i++) {
		struct state_bucket *b = state[i];
		while (b != NULL) {
			struct state_bucket *t = b;
			b = b->next;
			free(t->t);	/* free tape contents */
			free(t);	/* free bucket itself */
		}
		state[i] = NULL;
	}
}

void
save_state(int pc, int hd, char *t)
{
	struct state_bucket *b;

	if (debug_level >= 2) {
		fprintf(stderr, "saving state (%d, %d, '%s')\n", pc, hd, t);
	}

	b = malloc(sizeof(struct state_bucket));
	b->hd = hd;
	b->t = strdup(t);
	b->next = state[pc];
	state[pc] = b;
}

int
check_state(int pc, int hd, char *t)
{
	struct state_bucket *b = state[pc];

	while (b != NULL) {
		if (hd == b->hd && memcmp(t, b->t, tape_size) == 0)
			return 1;	/* yes, deja vu */
		b = b->next;
	}

	return 0;			/* no, this is fresh */
}

enum result
run(char *p, char *t)
{
	int hd = 0, pc = 0, bc = 0;

	clear_state();
	for (;;) {
		save_state(pc, hd, t);		/* record our state */

		if (debug_level >= 3 && p[pc] != '\0') {
			fprintf(stderr, "executing '%c'\n", p[pc]);
		}

		switch (p[pc]) {		/* dispatch on instr */
		case '\0':
			return HALT;

		case '>':
			hd++;
			if (hd > tape_size - 1)
				return OFF_RIGHT; /* ran off end of tape */
			break;
		case '<':
			hd--;
			if (hd < 0)
				return OFF_LEFT; /* ran off beg of tape */
			break;

		case '*':
			if (t[hd] == ' ')
				t[hd] = '*';
			else
				t[hd] = ' ';
			break;

		case '[':
			if (t[hd] == ' ') {
				bc = 1;
				while (bc > 0) {
					pc++;
					if (p[pc] == '[') {
						bc++;
					} else if (p[pc] == ']') {
						bc--;
					}
				}
			}
			break;
			
		case ']':
			bc = 1;
			while (bc > 0) {
				pc--;
				if (p[pc] == '[') {
					bc--;
				} else if (p[pc] == ']') {
					bc++;
				}
			}
			pc--;
			break;

		default:
			break;
		}

		pc++;
		if (check_state(pc, hd, t))	/* total deja vu? */
			return HANG;
	}
}

void
load(char *filename, char *p)
{
	FILE *f;
	int pi = 0;
	char c;

	f = fopen(filename, "r");
	if (f == NULL) {
		fprintf(stderr, "Error: can't open '%s'\n", filename);
		exit(1);
	}

	for (;;) {
		if (feof(f) || pi == (prog_size - 1))
			break;
		c = (char)fgetc(f);
		if (c == '*' || c == '<' || c == '>' || c == '[' || c == ']')
			p[pi++] = c;
	}
	p[pi] = '\0';

	if (debug_level >= 2) {
		fprintf(stderr, "loaded program: '%s'\n", p);
	}
}

void
usage(void)
{
	fprintf(stderr, "Usage: sf2tab [-d] [-p progsize] [-t tapesize] filename\n");
	exit(1);
}

int
main(int argc, char **argv)
{
	char *p;		/* program */
	char *t, *b;		/* tape and backup tape */
	int r = 1;		/* run # */
	int h;			/* halt flag */
	int i;			/* misc counter */
	int done = 0;		/* all runs done flag */
	int ch;			/* getopt character */

	/* get cmdline args */
	while ((ch = getopt(argc, argv, "dp:t:")) != -1) {
		switch ((char)ch) {
		case 'd':
			debug_level++;
			break;
		case 'p':
			prog_size = atoi(optarg);
			break;
		case 't':
			tape_size = atoi(optarg);
			break;
		case '?':
		default:
			usage();
		}
	}
	argv += optind;
	argc -= optind;

	if (argc <= 0)
		usage();

	/* set up program */
	p = malloc(prog_size);
	load(argv[0], p);

	/* set up tape and backup tape */
	t = malloc(tape_size + 1);
	b = malloc(tape_size + 1);
	memset(t, ' ', tape_size);
	memset(b, ' ', tape_size);
	t[tape_size] = '\0';
	b[tape_size] = '\0';
	
	while (!done) {
		/* back up tape, run program, print result */
		memcpy(b, t, tape_size);
		if (debug_level >= 1) {
			fprintf(stderr, "run #%d, using tape '%s'\n", r, t);
		}
		h = run(p, t);
		printf("{ \"%s\", %d, \"%s\" },\n", b, h, t);
		fflush(stdout);

		/* restore tape backup and get next tape */
		memcpy(t, b, tape_size);
		i = tape_size - 1;
		
	loop:	if (t[i] == ' ') {
			t[i] = '*';
		} else {
			t[i] = ' ';
			i--;
			if (i >= 0)
				goto loop;
			else
				done = 1;
		}
		r++;
	}

	exit(0);
}