Add some more implementation details

1 files changed, 506 insertions, 6 deletions

diff --git a/tpu.c b/tpu.c
index 13a082f..3fb88bc 100644
--- a/tpu.c
+++ b/tpu.c
@@ -1,27 +1,527 @@
 #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_add_inst(struct tpu *tpu, enum tpu_inst_type inst,
+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, uint8_t *up, uint8_t *right,
-	uint8_t *down, uint8_t *left)
+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_deinit(struct tpu *tpu)
+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;
 }