path: root/tpu.c

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

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

/* NOTES:
 * do two passes (one with only movs) for 'async' ports, result is the same
 */

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_init(struct tpu *tpu)
{
	size_t i;

	tpu->x = 0;
	tpu->y = 0;
	tpu->last = -1;
	tpu->acc = 0;
	tpu->bak = 0;
	tpu->inst_cnt = 0;
	tpu->pc = 0;
	label_map_init(&tpu->labels);
	for (i = 0; i < 4; i++) {
		tpu->ports[i].attached = false;
		tpu->ports[i].dst_port = NULL;
		tpu->ports[i].dst_tpu = NULL;
		tpu->ports[i].read = false;
		tpu->ports[i].write = false;
		tpu->ports[i].type = PORT_BIDI;
		tpu->ports[i].val = 0;
	}
}

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

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)
{
	struct tpu_inst *inst;

	inst = calloc(1, sizeof(struct tpu_inst));
	if (!inst) die("malloc:");
	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[1].type == OP_LIT) return false;
		break;
	}

	return true;
}

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

	for (i = 0; i < 4; i++) {
		tpu->ports[i].read = false;
		tpu->ports[i].write = false;
	}
}

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

	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:
		port = &tpu->ports[op_to_dir(op->type)];
		port->read = true;
		if (!port->attached || !port->dst_port->write)
			return -1;
		tpu->last = (int) op_to_dir(op->type);
		lit = port->dst_port->val;
		break;
	case OP_ANY:
		for (i = 0; i < 4; i++) {
			port = &tpu->ports[i];
			port->read = true;
			if (port->attached && port->dst_port->write) {
				tpu->last = i;
				lit = port->dst_port->val;
				break;
			}
		}
		if (i == 4) return -1;
		break;
	case OP_LAST:
		if (tpu->last < 0) return 0;
		port = &tpu->ports[tpu->last];
		port->read = true;
		if (!port->attached || !port->dst_port->write)
			return -1;
		lit = port->dst_port->val;
		break;
	case OP_LIT:
		lit = op->lit;
		break;
	default:
		abort();
	}

	tpu_ports_clear(tpu);

	return (int) lit;
}

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

	switch (op->type) {
	case OP_BAK:
		tpu->bak = lit;
		break;
	case OP_NIL:
		break;
	case OP_LEFT: case OP_RIGHT: case OP_UP: case OP_DOWN:
		port = &tpu->ports[op_to_dir(op->type)];
		port->write = true;
		if (!port->attached || !port->dst_port->write)
			return false;
		lit = port->dst_port->val;
		tpu->last = (int) op_to_dir(op->type);
		break;
	case OP_ANY:
		for (i = 0; i < 4; i++) {
			port = &tpu->ports[i];
			port->write = true;
			if (port->attached && port->dst_port->write) {
				port->dst_port->val = lit;
				tpu->last = i;
				break;
			}
		}
		if (i == 4) return false;
		break;
	case OP_LAST:
		if (tpu->last < 0) break;
		port = &tpu->ports[tpu->last];
		port->write = true;
		if (!port->attached || !port->dst_port->write)
			return false;
		break;
	default:
		abort();
	}

	tpu_ports_clear(tpu);

	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[0], (uint8_t) lit))
		return STATUS_WRITE;

	tpu->pc += 1;
	return STATUS_RUN;
}

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

	switch (inst->type) {
	case INST_NOP:
		tpu->pc += 1;
		return STATUS_RUN;
	case INST_MOV:
		return tpu_exec_mov(tpu, inst);
	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->pc = label_map_get(&tpu->labels, inst->ops[0].label);
		if (tpu->pc >= TPU_MAX_INST) abort();
		return STATUS_RUN;
	case INST_JEZ:
		if (tpu->acc == 0) {
			tpu->pc = label_map_get(&tpu->labels,
				inst->ops[0].label);
			if (tpu->pc >= TPU_MAX_INST) abort();
		} else {
			tpu->pc += 1;
		}
		return STATUS_RUN;
	case INST_JNZ:
		if (tpu->acc != 0) {
			tpu->pc = label_map_get(&tpu->labels,
				inst->ops[0].label);
			if (tpu->pc >= TPU_MAX_INST) abort();
		} else {
			tpu->pc += 1;
		}
		return STATUS_RUN;
	case INST_JGZ:
		if (tpu->acc > 0) {
			tpu->pc = label_map_get(&tpu->labels,
				inst->ops[0].label);
			if (tpu->pc >= TPU_MAX_INST) abort();
		} else {
			tpu->pc += 1;
		}
		return STATUS_RUN;
	case INST_JLZ:
		if (tpu->acc < 0) {
			tpu->pc = label_map_get(&tpu->labels,
				inst->ops[0].label);
			if (tpu->pc >= TPU_MAX_INST) abort();
		} 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();
	}
}

void
tpu_step(struct tpu *tpu)
{
	if (tpu->pc >= tpu->inst_cnt) return;
	tpu_exec(tpu, &tpu->insts[tpu->pc]);
	if (tpu->pc >= tpu->inst_cnt) tpu->pc = 0;
}

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