path: root/tpu.c

#include "tpu.h"
#include "util.h"

#include <stdio.h>
#include <stdbool.h>
#include <stddef.h>
#include <string.h>

const char *dir_reprs[] = {
	"LEFT", "RIGHT", "UP", "DOWN"
};

const char *status_reprs[] = {
	"IDLE", "RUN", "READ", "WRITE"
};

const char *inst_reprs[] = {
	"NOP", "MOV", "SWP", "SAV", "ADD", "SUB",
	"NEG", "JMP", "JEZ", "JNZ", "JGZ", "JLZ", "JRO"
};

const char *op_reprs[] = {
	"ACC", "BAK", "NIL", "LEFT", "RIGHT",
	"UP", "DOWN", "ANY", "LAST", "LIT", "<NAME>"
};

static enum tpu_port_dir
op_to_dir(enum tpu_inst_op_type op)
{
	return op - OP_LEFT;
}

static enum tpu_port_dir
opposite_dir(enum tpu_port_dir dir)
{
	switch (dir) {
	case DIR_UP:
		return DIR_DOWN;
	case DIR_DOWN:
		return DIR_UP;
	case DIR_LEFT:
		return DIR_RIGHT;
	case DIR_RIGHT:
		return DIR_LEFT;
	}
}

static uint32_t
djb_hash(const char *str)
{
	uint32_t hash;
	const char *c;

	hash = 5381;
	for (c = str; *c; c++)
		hash = 33 * hash + (uint8_t) *c;

	return hash;
}

void
label_map_init(struct label_map *map)
{
	memset(map->buckets, 0, sizeof(void *) * LABEL_MAP_BUCKETS);
}

void
label_map_deinit(struct label_map *map)
{
	struct label_map_link *link, *next;
	size_t i;

	for (i = 0; i < LABEL_MAP_BUCKETS; i++) {
		link = map->buckets[i];
		while (link) {
			next = link->next;
			free(link->label);
			free(link);
			link = next;
		}
	}
}

static struct label_map_link **
label_map_link_pos(struct label_map *map, const char *name)
{
	struct label_map_link **link;

	link = &map->buckets[djb_hash(name) % LABEL_MAP_BUCKETS];
	while (*link && strcmp((*link)->label, name))
		link = &(*link)->next;

	return link;
}

bool
label_map_add(struct label_map *map, const char *name, size_t pc)
{
	struct label_map_link **pos, *link;

	pos = label_map_link_pos(map, name);
	if (*pos) return false;

	*pos = link = malloc(sizeof(struct label_map_link));
	if (!link) die("malloc:");
	link->label = strdup(name);
	if (!link->label) die("strdup:");
	link->pc = pc;
	link->next = NULL;

	return true;
}

size_t
label_map_get(struct label_map *map, const char *name)
{
	struct label_map_link **link;

	link = label_map_link_pos(map, name);
	if (!*link) return TPU_MAX_INST;

	return (*link)->pc;
}

void
tpu_port_init(struct tpu_port *port)
{
	port->attached = false;
	port->dst_port = NULL;
	port->dst_tpu = NULL;
	port->type = PORT_BIDI;
	port->clr_post_run = false;
	port->reading = false;
	port->writing = false;
	port->in = -1;
	port->out = -1;
}

void
tpu_port_deinit(struct tpu_port *port)
{
	/* empty */
}

void
tpu_init(struct tpu *tpu)
{
	size_t i;

	tpu->status = STATUS_IDLE;

	tpu->x = 0;
	tpu->y = 0;

	tpu->steps = 0;
	tpu->idle_steps = 0;

	tpu->pc = 0;
	tpu->acc = 0;
	tpu->bak = 0;
	tpu->inst_cnt = 0;
	label_map_init(&tpu->labels);

	tpu->last = -1;
	tpu->io_port = -1;
	for (i = 0; i < 4; i++)
		tpu_port_init(&tpu->ports[i]);
}

void
tpu_deinit(struct tpu *tpu)
{
	int i;

	label_map_deinit(&tpu->labels);
	for (i = 0; i < TPU_MAX_INST; i++) {
		if (tpu->insts[i].ops[0].type == OP_LABEL)
			free(tpu->insts[i].ops[0].label);
	}
}

struct tpu_inst *
tpu_current_inst(struct tpu *tpu)
{
	if (tpu->pc >= tpu->inst_cnt)
		return NULL;
	return &tpu->insts[tpu->pc];
}

void
tpu_init_ports(struct tpu *tpu, struct tpu_map *map)
{
	struct tpu *neighbor;
	enum tpu_port_dir odir;
	size_t x, y;
	int i;

	for (i = 0; i < 4; i++) {
		switch (i) {
		case DIR_LEFT:
			x = tpu->x - 1;
			y = tpu->y;
			break;
		case DIR_RIGHT:
			x = tpu->x + 1;
			y = tpu->y;
			break;
		case DIR_UP:
			x = tpu->x;
			y = tpu->y - 1;
			break;
		case DIR_DOWN:
			x = tpu->x;
			y = tpu->y + 1;
			break;
		}

		neighbor = tpu_map_get(map, x, y);
		if (neighbor) {
			tpu->ports[i].attached = true;
			tpu->ports[i].dst_tpu = neighbor;
			odir = opposite_dir((enum tpu_port_dir) i);
			tpu->ports[i].dst_port = &neighbor->ports[odir];
		}
	}
}

void
tpu_update_ports(struct tpu *tpu)
{
	struct tpu_port *port;
	int i;

	for (i = 0; i < 4; i++) {
		port = &tpu->ports[i];
		if (!port->attached) continue;
		if (port->out >= 0 && port->dst_port->in < 0) {
			port->dst_port->reading = false;
			port->dst_port->in = port->out;
			port->writing = false;
			port->out = -1;
		}
		if (port->dst_port->out >= 0 && port->in < 0) {
			port->reading = false;
			port->in = port->dst_port->out;
			port->dst_port->writing = false;
			port->dst_port->out = -1;
		}
		if (tpu->status == STATUS_RUN && port->clr_post_run) {
			port->in = -1;
			port->clr_post_run = false;
		}
	}
}

bool
tpu_set_inst(struct tpu *tpu, uint8_t pc, enum tpu_inst_type inst_type,
	int op1, uint8_t op1_lit, int op2, uint8_t op2_lit)
{
	struct tpu_inst *inst;

	inst = &tpu->insts[pc];
	inst->type = inst_type;

	if (op2 >= 0) {
		inst->ops[1].type = (enum tpu_inst_op_type) op2;
		inst->ops[1].lit = op2_lit;
		inst->ops[0].type = (enum tpu_inst_op_type) op1;
		inst->ops[0].lit = op1_lit;
		inst->opcnt = 2;
	} else if (op1 >= 0) {
		inst->ops[0].type = (enum tpu_inst_op_type) op1;
		inst->ops[0].lit = op1_lit;
		inst->opcnt = 1;
	} else {
		inst->opcnt = 0;
	}

	switch (inst->type) {
	case INST_NOP: case INST_SAV:
	case INST_SWP: case INST_NEG:
		return inst->opcnt == 0;
	case INST_ADD: case INST_SUB:
		return inst->opcnt == 1;
	case INST_JMP: case INST_JEZ: case INST_JNZ:
	case INST_JGZ: case INST_JLZ: case INST_JRO:
		if (inst->opcnt != 1) return false;
		if (inst->ops[0].type != OP_LABEL) return false;
		break;
	case INST_MOV:
		if (inst->opcnt != 2) return false;
		if (inst->ops[0].type == OP_LABEL) return false;
		if (inst->ops[1].type == OP_LABEL) return false;
		if (inst->ops[1].type == OP_LIT) return false;
		break;
	}

	return true;
}

bool
tpu_add_inst(struct tpu *tpu, enum tpu_inst_type inst_type,
	int op1, uint8_t op1_lit, int op2, uint8_t op2_lit)
{
	if (tpu->inst_cnt == TPU_MAX_INST)
		die("tpu_add_inst: tpu X%lu Y%lu, too many instructions",
			tpu->x, tpu->y);
	return tpu_set_inst(tpu, (uint8_t) tpu->inst_cnt++, inst_type,
		op1, op1_lit, op2, op2_lit);
}

/* tpu can always write to an empty port (->out), but only
 * read values if there is a writer attached and offering a value
 * (->dst_port->out) -- the read value (->in) is cleared at the end of
 * an instruction step */

static int
tpu_port_read(struct tpu *tpu, enum tpu_port_dir dir)
{
	struct tpu_port *port;

	port = &tpu->ports[dir];
	port->clr_post_run = true;
	if (port->in < 0) {
		port->reading = true;
		return -1;
	}
	return port->in;
}

static bool
tpu_port_write(struct tpu *tpu, enum tpu_port_dir dir, uint8_t lit)
{
	struct tpu_port *port;

	port = &tpu->ports[dir];
	if (port->out >= 0) {
		port->writing = true;
		return false;
	}
	port->out = lit;
	return true;
}

static void
tpu_jmp_label(struct tpu *tpu, const char *label)
{
	size_t pc;

	pc = label_map_get(&tpu->labels, label);
	if (pc >= TPU_MAX_INST) abort();
	tpu->pc = (uint8_t) pc;
}

int
tpu_exec_get(struct tpu *tpu, struct tpu_inst_op *op)
{
	uint8_t lit;
	int i, v;

	switch (op->type) {
	case OP_ACC:
		lit = tpu->acc;
		break;
	case OP_BAK:
		lit = tpu->bak;
		break;
	case OP_NIL:
		lit = 0;
		break;
	case OP_LEFT: case OP_RIGHT: case OP_UP: case OP_DOWN:
		return tpu_port_read(tpu, op_to_dir(op->type));
	case OP_ANY:
		for (i = 0; i < 4; i++) {
			v = tpu_port_read(tpu, (enum tpu_port_dir) i);
			if (v >= 0) {
				tpu->last = i;
				break;
			}
		}
		if (i == 4) return -1;
		lit = (uint8_t) v;
		break;
	case OP_LAST:
		if (tpu->last < 0) return 0;
		return tpu_port_read(tpu, (enum tpu_port_dir) tpu->last);
	case OP_LIT:
		lit = op->lit;
		break;
	case OP_LABEL:
		abort();
	}

	return (int) lit;
}

bool
tpu_exec_put(struct tpu *tpu, struct tpu_inst_op *op, uint8_t lit)
{
	int i;

	switch (op->type) {
	case OP_ACC:
		tpu->acc = lit;
		break;
	case OP_BAK:
		tpu->bak = lit;
		break;
	case OP_NIL:
		break;
	case OP_LEFT: case OP_RIGHT: case OP_UP: case OP_DOWN:
		return tpu_port_write(tpu, op_to_dir(op->type), lit);
	case OP_ANY:
		for (i = 0; i < 4; i++) {
			if (tpu_port_write(tpu, (enum tpu_port_dir) i, lit)) {
				tpu->last = i;
				break;
			}
		}
		if (i == 4) return false;
		break;
	case OP_LAST:
		if (tpu->last < 0) break;
		return tpu_port_write(tpu, (enum tpu_port_dir) tpu->last, lit);
	case OP_LABEL:
	case OP_LIT:
		abort();
	}

	return true;
}

enum tpu_status
tpu_exec_mov(struct tpu *tpu, struct tpu_inst *inst)
{
	int lit;

	if (inst->type != INST_MOV) abort();

	lit = tpu_exec_get(tpu, &inst->ops[0]);
	if (lit < 0) return STATUS_READ;

	if (!tpu_exec_put(tpu, &inst->ops[1], (uint8_t) lit))
		return STATUS_WRITE;

	return STATUS_RUN;
}

enum tpu_status
tpu_exec(struct tpu *tpu, struct tpu_inst *inst)
{
	enum tpu_status status;
	uint8_t lit;
	int val;

	switch (inst->type) {
	case INST_NOP:
		tpu->pc += 1;
		return STATUS_RUN;
	case INST_MOV:
		status = tpu_exec_mov(tpu, inst);
		if (status == STATUS_RUN)
			tpu->pc += 1;
		return status;
	case INST_SWP:
		lit = tpu->acc;
		tpu->acc = tpu->bak;
		tpu->bak = lit;
		tpu->pc += 1;
		return STATUS_RUN;
	case INST_SAV:
		tpu->bak = tpu->acc;
		tpu->pc += 1;
		return STATUS_RUN;
	case INST_ADD:
		val = tpu_exec_get(tpu, &inst->ops[0]);
		if (val < 0) return STATUS_READ;
		tpu->acc += (uint8_t) val;
		tpu->pc += 1;
		return STATUS_RUN;
	case INST_SUB:
		val = tpu_exec_get(tpu, &inst->ops[0]);
		if (val < 0) return STATUS_READ;
		tpu->acc -= (uint8_t) val;
		tpu->pc += 1;
		return STATUS_RUN;
	case INST_NEG:
		tpu->acc = -tpu->acc;
		tpu->pc += 1;
		return STATUS_RUN;
	case INST_JMP:
		tpu_jmp_label(tpu, inst->ops[0].label);
		return STATUS_RUN;
	case INST_JEZ:
		if (tpu->acc == 0)
			tpu_jmp_label(tpu, inst->ops[0].label);
		else
			tpu->pc += 1;
		return STATUS_RUN;
	case INST_JNZ:
		if (tpu->acc != 0)
			tpu_jmp_label(tpu, inst->ops[0].label);
		else
			tpu->pc += 1;
		return STATUS_RUN;
	case INST_JGZ:
		if (tpu->acc > 0)
			tpu_jmp_label(tpu, inst->ops[0].label);
		else
			tpu->pc += 1;
		return STATUS_RUN;
	case INST_JLZ:
		if (tpu->acc < 0)
			tpu_jmp_label(tpu, inst->ops[0].label);
		else
			tpu->pc += 1;
		return STATUS_RUN;
	case INST_JRO:
		tpu->pc += inst->ops[0].lit;
		if (tpu->pc >= tpu->inst_cnt) tpu->pc = 0;
		return STATUS_RUN;
	default:
		abort();
	}
}

enum tpu_status
tpu_step(struct tpu *tpu)
{
	if (tpu->pc < tpu->inst_cnt) {
		tpu->status = tpu_exec(tpu, &tpu->insts[tpu->pc]);
		if (tpu->pc >= tpu->inst_cnt) tpu->pc = 0;
	} else {
		tpu->status = STATUS_IDLE;
	}

	tpu->steps += 1;
	if (tpu->status != STATUS_RUN)
		tpu->idle_steps += 1;

	return tpu->status;
}

void
tpu_map_init(struct tpu_map *map)
{
	memset(map->buckets, 0, sizeof(void *) * TPU_MAP_BUCKETS);
}

void
tpu_map_deinit(struct tpu_map *map)
{
	struct tpu_map_link *link, *next;
	size_t i;

	for (i = 0; i < TPU_MAP_BUCKETS; i++) {
		link = map->buckets[i];
		while (link) {
			next = link->next;
			tpu_deinit(link->tpu);
			free(link->tpu);
			free(link);
			link = next;
		}
	}
}

static struct tpu_map_link **
tpu_map_link_pos(struct tpu_map *map, size_t x, size_t y)
{
	struct tpu_map_link **link;
	size_t i;

	i = (x + y) % TPU_MAP_BUCKETS;
	link = &map->buckets[i];
	while (*link && !((*link)->x == x && (*link)->y == y))
		link = &(*link)->next;

	return link;
}

void
tpu_map_add(struct tpu_map *map, struct tpu *tpu)
{
	struct tpu_map_link **pos, *link;

	pos = tpu_map_link_pos(map, tpu->x, tpu->y);
	*pos = link = malloc(sizeof(struct tpu_map_link));
	if (!link) die("malloc:");
	link->tpu = tpu;
	link->x = tpu->x;
	link->y = tpu->y;
	link->next = NULL;
}

struct tpu *
tpu_map_get(struct tpu_map *map, size_t x, size_t y)
{
	struct tpu_map_link **link;

	if (x < 0 || y < 0) return NULL;

	link = tpu_map_link_pos(map, x, y);
	if (!*link) return NULL;

	return (*link)->tpu;
}

void
tis_init(struct tis *tis)
{
	tpu_map_init(&tis->tpu_map);
	tpu_port_init(&tis->stdin_port);
	tpu_port_init(&tis->stdout_port);
}

void
tis_deinit(struct tis *tis)
{
	tpu_map_deinit(&tis->tpu_map);
	tpu_port_deinit(&tis->stdin_port);
	tpu_port_deinit(&tis->stdout_port);
}

bool
tis_step(struct tis *tis)
{
	struct tpu_map_link *link;
	bool running;
	size_t i;

	running = false;
	for (i = 0; i < TPU_MAP_BUCKETS; i++) {
		link = tis->tpu_map.buckets[i];
		for (; link; link = link->next)
			running |= (tpu_step(link->tpu) == STATUS_RUN);
	}

	for (i = 0; i < TPU_MAP_BUCKETS; i++) {
		link = tis->tpu_map.buckets[i];
		for (; link; link = link->next)
			tpu_update_ports(link->tpu);
	}

	return running;
}