From 3083284c797fc8fc267144b05c8a58395e4583e3 Mon Sep 17 00:00:00 2001 From: Kimplul Date: Sat, 9 Aug 2025 16:06:43 +0300 Subject: add 1d mesh node and refactor 2d mesh node + Seems to decrease performance a little bit, presumably due to extra register copy, but simplifies code a lot and opens up more genericism so I'll consider it an upgrade for now. Copying packets around is rather slow though, might in the future move to some kind of pointer based packet handling --- src/mesh/node.c | 164 ---------------------------- src/mesh/node1d.c | 307 +++++++++++++++++++++++++++++++++++++++++++++++++++++ src/mesh/node2d.c | 281 ++++++++++++++++++++++++++++++++++++++++++++++++ src/mesh/source.mk | 2 +- 4 files changed, 589 insertions(+), 165 deletions(-) delete mode 100644 src/mesh/node.c create mode 100644 src/mesh/node1d.c create mode 100644 src/mesh/node2d.c (limited to 'src/mesh') diff --git a/src/mesh/node.c b/src/mesh/node.c deleted file mode 100644 index 2ac921a..0000000 --- a/src/mesh/node.c +++ /dev/null @@ -1,164 +0,0 @@ -#include - -struct reg { - struct packet pkt; - bool busy; -}; - -struct node { - struct component component; - uint16_t x, y; - - uint64_t timestamp; - - struct component *n, *s, *e, *w, *l; - - struct reg n_in, s_in, e_in, w_in, l_in; -}; - -enum order { - N, S, E, W, L -}; - -static inline void maybe_pick(struct reg *output[5], enum order d, struct reg *r) -{ - if (output[d] && output[d]->pkt.timestamp < r->pkt.timestamp) - return; - - output[d] = r; -} - -static stat node_clock(struct node *node) -{ - node->timestamp++; - - struct reg *output[5] = {NULL, NULL, NULL, NULL, NULL}; - struct reg *input[5] = { - &node->n_in, - &node->s_in, - &node->e_in, - &node->w_in, - &node->l_in - }; - - uint8_t X = node->x, Y = node->y; - for (size_t i = 0; i < 5; ++i) { - struct reg *r = input[i]; - if (!r->busy) - continue; - - uint16_t x, y; - addr_mesh(r->pkt.to, &x, &y, NULL); - if (x < X) { - maybe_pick(output, W, r); - continue; - } - - if (x > X) { - maybe_pick(output, E, r); - continue; - } - - if (y < Y) { - maybe_pick(output, S, r); - continue; - } - - if (y > Y) { - maybe_pick(output, N, r); - continue; - } - - maybe_pick(output, L, r); - } - - struct component *target[7] = { - node->n, - node->s, - node->e, - node->w, - node->l - }; - - for (size_t i = 0; i < 5; ++i) { - if (!output[i]) - continue; - - if (!target[i]) { - /* for now, should send packet back with an error or something */ - abort(); - } - - stat ret = SEND(node, target[i], output[i]->pkt); - if (ret == EBUSY) - continue; - - assert(ret == OK); - output[i]->busy = false; - } - - return OK; -} - -static stat reg_receive(struct reg *r, struct packet pkt) -{ - if (r->busy) - return EBUSY; - - r->pkt = pkt; - r->busy = true; - return OK; -} - -static stat node_receive(struct node *node, struct component *from, struct packet pkt) -{ - if (from == node->l) { - /* add time when packet entered network */ - pkt.timestamp = node->timestamp; - return reg_receive(&node->l_in, pkt); - } - - if (from == node->n) - return reg_receive(&node->n_in, pkt); - - if (from == node->s) - return reg_receive(&node->s_in, pkt); - - if (from == node->e) - return reg_receive(&node->e_in, pkt); - - if (from == node->w) - return reg_receive(&node->w_in, pkt); - - abort(); - return OK; -} - -struct component *create_mesh_node(uint16_t x, uint16_t y) -{ - struct node *node = calloc(1, sizeof(struct node)); - if (!node) - return NULL; - - node->component.receive = (receive_callback)node_receive; - node->component.clock = (clock_callback)node_clock; - node->x = x; - node->y = y; - return (struct component *)node; -} - -stat mesh_node_connect(struct component *node, - struct component *n, - struct component *s, - struct component *e, - struct component *w, - struct component *l) -{ - struct node *nod = (struct node *)node; - nod->n = n; - nod->s = s; - nod->e = e; - nod->w = w; - nod->l = l; - return OK; -} diff --git a/src/mesh/node1d.c b/src/mesh/node1d.c new file mode 100644 index 0000000..23ba2ca --- /dev/null +++ b/src/mesh/node1d.c @@ -0,0 +1,307 @@ +#include + +#define left_port(n) (n)->ports[(n)->elems + 0] +#define right_port(n) (n)->ports[(n)->elems + 1] + +#define left_in(n) (n)->in[(n)->elems + 0] +#define right_in(n) (n)->in[(n)->elems + 1] + +#define left_out(n) (n)->out[(n)->elems + 0] +#define right_out(n) (n)->out[(n)->elems + 1] + +struct reg { + struct packet pkt; + bool busy; +}; + +struct node1d { + struct component component; + uint16_t cluster; + uint16_t elems; + + uint64_t timestamp; + + struct reg *in; /* countedby[elems + 2] */ + struct reg *out; /* countedby[elems + 2] */ + struct component **ports; /* countedby[elems + 2] */ +}; + +static void node1d_destroy(struct node1d *n) +{ + free(n->in); + free(n->out); + free(n->ports); +} + +static stat reg_busy(struct reg *r, struct packet pkt) +{ + bool busy = r->busy; + if (!busy) { + r->pkt = pkt; + r->busy = true; + } + + return busy ? EBUSY : OK; +} + +static void copy_reg(struct reg *r, struct reg *s) +{ + assert(s->busy); + if (r->busy) + return; + + r->pkt = s->pkt; + r->busy = true; + s->busy = false; +} + +static stat node1d_receive(struct node1d *n, struct component *from, struct packet pkt) +{ + for (int i = 0; i < n->elems + 2; ++i) { + /* add timestamp to packets that originate with us */ + if (i < n->elems) + pkt.timestamp = n->timestamp; + + if (from == n->ports[i]) + return reg_busy(&n->in[i], pkt); + } + + /* shouldn't be possible */ + abort(); + return OK; +} + +static void clock_outputs(struct node1d *n) +{ + for (int i = 0; i < n->elems + 2; ++i) { + if (!n->out[i].busy) + continue; + + stat ret = SEND(n, n->ports[i], n->out[i].pkt); + if (ret == EBUSY) + continue; + + n->out[i].busy = false; + } +} + +static void propagate_left(struct node1d *n, struct reg *a, struct reg *b) +{ + struct reg *sel_a = NULL, *sel_b = NULL; + if (a && a->busy) { + uint16_t cluster = 0; + addr_mesh1d(a->pkt.to, &cluster, NULL, NULL); + + if (cluster > n->cluster) + sel_a = a; + } + + if (b && b->busy) { + uint16_t cluster = 0; + addr_mesh1d(b->pkt.to, &cluster, NULL, NULL); + + if (cluster > n->cluster) + sel_b = b; + } + + if (!sel_a && !sel_b) + return; + + if (sel_a && !sel_b) { + copy_reg(&left_out(n), sel_a); + return; + } + + if (!sel_a && sel_b) { + copy_reg(&left_out(n), sel_b); + return; + } + + /* both available, select older */ + if (sel_a->pkt.timestamp < sel_b->pkt.timestamp) + copy_reg(&left_out(n), sel_a); + else + copy_reg(&left_out(n), sel_b); +} + +static void propagate_right(struct node1d *n, struct reg *a, struct reg *b) +{ + struct reg *sel_a = NULL, *sel_b = NULL; + if (a && a->busy) { + uint16_t cluster = 0; + addr_mesh1d(a->pkt.to, &cluster, NULL, NULL); + + if (cluster < n->cluster) + sel_a = a; + } + + if (b && b->busy) { + uint16_t cluster = 0; + addr_mesh1d(b->pkt.to, &cluster, NULL, NULL); + + if (cluster < n->cluster) + sel_b = b; + } + + if (!sel_a && !sel_b) + return; + + if (sel_a && !sel_b) { + copy_reg(&right_out(n), sel_a); + return; + } + + if (!sel_a && sel_b) { + copy_reg(&right_out(n), sel_b); + return; + } + + /* both available, select older */ + if (sel_a->pkt.timestamp < sel_b->pkt.timestamp) + copy_reg(&right_out(n), sel_a); + else + copy_reg(&right_out(n), sel_b); +} + +static void propagate(struct node1d *n, int elem, struct reg *a, struct reg *b, struct reg *c) +{ + + struct reg *sel_a = NULL, *sel_b = NULL, *sel_c = NULL; + if (a && a->busy) { + uint16_t cluster = 0, element = 0; + addr_mesh1d(a->pkt.to, &cluster, &element, NULL); + + if (cluster == n->cluster && element == elem) + sel_a = a; + } + + if (b && b->busy) { + uint16_t cluster = 0, element = 0; + addr_mesh1d(b->pkt.to, &cluster, &element, NULL); + + if (cluster == n->cluster && element == elem) + sel_b = b; + } + + if (c && c->busy) { + uint16_t cluster = 0, element = 0; + addr_mesh1d(c->pkt.to, &cluster, &element, NULL); + + if (cluster == n->cluster && element == elem) + sel_c = c; + } + + struct reg *sel_0 = NULL, *sel_1 = NULL; + if (sel_a && sel_b) + sel_0 = sel_a->pkt.timestamp < sel_b->pkt.timestamp ? sel_a : sel_b; + else + sel_0 = sel_a ? sel_a : sel_b; + + if (sel_b && sel_c) + sel_1 = sel_b->pkt.timestamp < sel_c->pkt.timestamp ? sel_b : sel_c; + else + sel_1 = sel_b ? sel_b : sel_c; + + struct reg *sel = NULL; + if (sel_0 && sel_1) + sel = sel_0->pkt.timestamp < sel_1->pkt.timestamp ? sel_0 : sel_1; + else + sel = sel_0 ? sel_0 : sel_1; + + if (!sel) + return; + + copy_reg(&n->out[elem], sel); +} + +static stat node1d_clock(struct node1d *n) +{ + n->timestamp++; + + clock_outputs(n); + + /* select oldest packet to process */ + struct reg *r = NULL; + for (int i = 0; i < n->elems; ++i) { + if (!n->in[i].busy) + continue; + + if (!r || r->pkt.timestamp > n->in[i].pkt.timestamp) + r = &n->in[i]; + } + + propagate_left(n, r, &right_in(n)); + propagate_right(n, r, &left_in(n)); + for (int i = 0; i < n->elems; ++i) + propagate(n, i, r, &right_in(n), &left_in(n)); + + return OK; +} + +stat mesh_node1d_connect(struct component *c, struct component *e, uint16_t elem) +{ + struct node1d *n = (struct node1d *)c; + if (elem >= n->elems) + return ENOSUCH; + + if (n->ports[elem]) + return EEXISTS; + + n->ports[elem] = e; + return OK; +} + +stat mesh_node1d_connect_left(struct component *c, struct component *e) +{ + struct node1d *n = (struct node1d *)c; + if (left_port(n)) + return EEXISTS; + + left_port(n) = e; + return OK; +} + +stat mesh_node1d_connect_right(struct component *c, struct component *e) +{ + struct node1d *n = (struct node1d *)c; + if (right_port(n)) + return EEXISTS; + + right_port(n) = e; + return OK; +} + +struct component *create_mesh_node1d(uint16_t cluster, uint16_t elems) +{ + struct node1d *n = (struct node1d *)calloc(1, sizeof(struct node1d)); + if (!n) + return NULL; + + n->in = (struct reg *)calloc(elems + 2, sizeof(struct reg)); + if (!n->in) { + free(n); + return NULL; + } + + n->out = (struct reg *)calloc(elems + 2, sizeof(struct reg)); + if (!n->out) { + free(n->in); + free(n); + return NULL; + } + + n->ports = (struct component **)calloc(elems + 2, sizeof(struct component *)); + if (!n->ports) { + free(n->out); + free(n->in); + free(n); + return NULL; + } + + n->component.destroy = (destroy_callback)node1d_destroy; + n->component.receive = (receive_callback)node1d_receive; + n->component.clock = (clock_callback)node1d_clock; + n->cluster = cluster; + n->elems = elems; + return (struct component *)n; +} diff --git a/src/mesh/node2d.c b/src/mesh/node2d.c new file mode 100644 index 0000000..81ef8dc --- /dev/null +++ b/src/mesh/node2d.c @@ -0,0 +1,281 @@ +#include + +#define north_port(n) (n)->ports[(n)->elems + 0] +#define east_port(n) (n)->ports[(n)->elems + 1] +#define south_port(n) (n)->ports[(n)->elems + 2] +#define west_port(n) (n)->ports[(n)->elems + 3] + +#define north_in(n) (n)->in[(n)->elems + 0] +#define east_in(n) (n)->in[(n)->elems + 1] +#define south_in(n) (n)->in[(n)->elems + 2] +#define west_in(n) (n)->in[(n)->elems + 3] + +#define north_out(n) (n)->out[(n)->elems + 0] +#define east_out(n) (n)->out[(n)->elems + 1] +#define south_out(n) (n)->out[(n)->elems + 2] +#define west_out(n) (n)->out[(n)->elems + 3] + +struct reg { + struct packet pkt; + bool busy; +}; + +struct node2d { + struct component component; + uint16_t elems; + uint16_t x, y; + + uint64_t timestamp; + + struct reg *in; /* countedby[elems + 4] */ + struct reg *out; /* countedby[elems + 4] */ + struct component **ports; /* countedby[elems + 4] */ +}; + +static void clock_outputs(struct node2d *n) +{ + for (int i = 0; i < n->elems + 4; ++i) { + if (!n->out[i].busy) + continue; + + stat ret = SEND(n, n->ports[i], n->out[i].pkt); + if (ret == EBUSY) + continue; + + n->out[i].busy = false; + } +} + +static void copy_reg(struct reg *r, struct reg *s) +{ + assert(s->busy); + if (r->busy) + return; + + r->pkt = s->pkt; + r->busy = true; + s->busy = false; +} + +static void propagate(struct reg *out, + size_t count, struct reg *in[static count], + bool (*sel)(struct reg *r, void *data), void *data) +{ + struct reg *r = NULL; + for (size_t i = 0; i < count; ++i) { + if (!in[i] || !in[i]->busy) + continue; + + if (!sel(in[i], data)) + continue; + + if (!r || r->pkt.timestamp > in[i]->pkt.timestamp) + r = in[i]; + } + + if (!r) + return; + + copy_reg(out, r); +} + +struct sel_helper { + uint8_t x, y; + uint16_t elem; +}; + +static bool north_sel(struct reg *r, void *data) +{ + uint8_t y = 0; + struct sel_helper *helper = data; + addr_mesh2d(r->pkt.to, NULL, &y, NULL, NULL); + return y > helper->y; +} + +static bool south_sel(struct reg *r, void *data) +{ + uint8_t y = 0; + struct sel_helper *helper = data; + addr_mesh2d(r->pkt.to, NULL, &y, NULL, NULL); + return y < helper->y; +} + +static bool east_sel(struct reg *r, void *data) +{ + uint8_t x = 0, y = 0; + struct sel_helper *helper = data; + addr_mesh2d(r->pkt.to, &x, &y, NULL, NULL); + return y == helper->y && x > helper->x; +} + +static bool west_sel(struct reg *r, void *data) +{ + uint8_t x = 0, y = 0; + struct sel_helper *helper = data; + addr_mesh2d(r->pkt.to, &x, &y, NULL, NULL); + return y == helper->y && x < helper->x; +} + +static bool elem_sel(struct reg *r, void *data) +{ + uint16_t elem = 0; + uint8_t x = 0, y = 0; + struct sel_helper *helper = data; + addr_mesh2d(r->pkt.to, &x, &y, &elem, NULL); + return x == helper->x && y == helper->y && elem == helper->elem; +} + +static stat node2d_clock(struct node2d *n) +{ + n->timestamp++; + clock_outputs(n); + + /* select oldest packet to process */ + struct reg *r = NULL; + for (int i = 0; i < n->elems; ++i) { + if (!n->in[i].busy) + continue; + + if (!r || r->pkt.timestamp > n->in[i].pkt.timestamp) + r = &n->in[i]; + } + + struct sel_helper helper = { + .elem = 0, + .x = n->x, + .y = n->y, + }; + + struct reg *north[] = {r, &east_in(n), &south_in(n), &west_in(n)}; + struct reg *east[] = {r, &north_in(n), &south_in(n), &west_in(n)}; + struct reg *south[] = {r, &north_in(n), &east_in(n), &west_in(n)}; + struct reg *west[] = {r, &north_in(n), &east_in(n), &south_in(n)}; + + propagate(&north_out(n), 4, north, north_sel, &helper); + propagate(&east_out(n), 4, east, east_sel, &helper); + propagate(&south_out(n), 4, south, south_sel, &helper); + propagate(&west_out(n), 4, west, west_sel, &helper); + + struct reg *all[] = {r, &north_in(n), &east_in(n), &south_in(n), &west_in(n)}; + for (int i = 0; i < n->elems; ++i) { + helper.elem = i; + propagate(&n->out[i], 5, all, elem_sel, &helper); + } + + return OK; +} + +static stat reg_busy(struct reg *r, struct packet pkt) +{ + bool busy = r->busy; + if (!busy) { + r->pkt = pkt; + r->busy = true; + } + + return busy ? EBUSY : OK; +} + +static stat node2d_receive(struct node2d *n, struct component *from, struct packet pkt) +{ + for (int i = 0; i < n->elems + 4; ++i) { + if (from != n->ports[i]) + continue; + + if (i < n->elems) + pkt.timestamp = n->timestamp; + + return reg_busy(&n->in[i], pkt); + } + + abort(); + return OK; +} + +struct component *create_mesh_node2d(uint8_t x, uint8_t y, uint16_t elems) +{ + struct node2d *n = calloc(1, sizeof(struct node2d)); + if (!n) + return NULL; + + n->in = calloc(elems + 4, sizeof(struct reg)); + if (!n->in) { + free(n); + return NULL; + } + + n->out = calloc(elems + 4, sizeof(struct reg)); + if (!n->out) { + free(n->in); + free(n); + return NULL; + } + + n->ports = calloc(elems + 4, sizeof(struct component *)); + if (!n->ports) { + free(n->out); + free(n->in); + free(n); + return NULL; + } + + n->component.receive = (receive_callback)node2d_receive; + n->component.clock = (clock_callback)node2d_clock; + n->elems = elems; + n->x = x; + n->y = y; + return (struct component *)n; +} + +stat mesh_node2d_connect(struct component *c, struct component *e, uint16_t elem) +{ + struct node2d *n = (struct node2d *)c; + if (elem >= n->elems) + return ENOSUCH; + + if (n->ports[elem]) + return EEXISTS; + + n->ports[elem] = e; + return OK; +} + +stat mesh_node2d_connect_north(struct component *c, struct component *e) +{ + struct node2d *n = (struct node2d *)c; + if (north_port(n)) + return EEXISTS; + + north_port(n) = e; + return OK; +} + +stat mesh_node2d_connect_east(struct component *c, struct component *e) +{ + struct node2d *n = (struct node2d *)c; + if (east_port(n)) + return EEXISTS; + + east_port(n) = e; + return OK; +} + +stat mesh_node2d_connect_south(struct component *c, struct component *e) +{ + struct node2d *n = (struct node2d *)c; + if (south_port(n)) + return EEXISTS; + + south_port(n) = e; + return OK; +} + +stat mesh_node2d_connect_west(struct component *c, struct component *e) +{ + struct node2d *n = (struct node2d *)c; + if (west_port(n)) + return EEXISTS; + + west_port(n) = e; + return OK; +} diff --git a/src/mesh/source.mk b/src/mesh/source.mk index 55a7d03..23d6014 100644 --- a/src/mesh/source.mk +++ b/src/mesh/source.mk @@ -1 +1 @@ -SOURCES += src/mesh/node.c src/mesh/node3d.c +SOURCES += src/mesh/node1d.c src/mesh/node2d.c src/mesh/node3d.c -- cgit v1.3