--- /dev/null
+#define _GNU_SOURCE
+#include<assert.h>
+#include<sched.h>
+#include<signal.h>
+#include<stdio.h>
+#include<stdlib.h>
+#include<time.h>
+#include<unistd.h>
+#include<sys/wait.h>
+
+#include<pthread.h>
+
+/* magic value to indicate upstream is dead */
+#define UART_DEAD 2
+
+/* only relevant instructions */
+#define INSTR_NOP 0
+#define INSTR_ROUTE 4
+
+/* Doing nothing, waiting for an instruction */
+#define STATE_IDLE 0
+#define STATE_READ_INSTRUCTION 10
+#define STATE_READ_NEWS_ADDRESS 20
+#define STATE_READ_NEWS_DATA 30
+/* Propagating the last received instruction
+ (or waiting for neighbour to be ready so I can propagate) */
+#define STATE_PROPAGATE 1
+#define STATE_PROPAGATE2 11
+/* Executing some instruction */
+#define STATE_EXECUTE 2
+/* Sending NEWS to neighbour
+ (or waiting for neighbour to be ready so I can send) */
+#define STATE_NEWS 3
+#define STATE_NEWS2 13
+#define STATE_NEWS3 23
+
+// UART encoding is: to send the byte [b] we write [b * 2 + 1] in the
+// given location, then on the next cycle we write 0.
+
+static void wait_cycles(int cycles) {
+ struct timespec ts;
+ long millis = 200;
+ millis += (long)(rand() % 100 - 50);
+ millis *= cycles;
+ ts.tv_sec = millis / 1000;
+ ts.tv_nsec = (millis % 1000) * 100000;
+ nanosleep(&ts, NULL);
+}
+
+/* sleep for 150-250ms */
+static void wait_one_cycle(void) {
+ wait_cycles(1);
+}
+
+#define BLOG_THREAD_STARTED 0
+#define BLOG_UART_BAD_KIND 1
+#define BLOG_READ_INSTRUCTION 2
+#define BLOG_READ_NEWS_ADDRESS 3
+#define BLOG_READ_NEWS_DATA 4
+#define BLOG_BECAME_NOT_READY 5
+#define BLOG_INVALID_STATE 6
+#define BLOG_EXECUTED_INSTR 7
+#define BLOG_MANUFACTURED_INSTRUCTION 8
+#define BLOG_READ_KIND 9
+#define BLOG_TRY_SENDING_NEWS 10
+#define BLOG_DONE_SENDING_NEWS 11
+
+const char *blog_what[] = {
+ "thread started",
+ "uart bad kind",
+ "read instruction",
+ "read news address",
+ "read news data",
+ "ERROR: downstream became not ready!",
+ "ERROR: invalid state",
+ "executed instruction",
+ "manufactured instruction",
+ "read kind from uart",
+ "trying to send news",
+ "finished sending news",
+};
+
+struct blog {
+ int who;
+ int what;
+ int data;
+};
+
+static volatile struct blog blog[1000];
+static volatile int blog_n = 0;
+
+void display_post(int i) {
+ printf("\033[3%dm%d: %s (%d)\033[0m\n", blog[i].who + 1, blog[i].who, blog_what[blog[i].what], blog[i].data);
+}
+
+void post(int who, int what, int data) {
+ int idx = blog_n++;
+ blog[idx].who = who;
+ blog[idx].what = what;
+ blog[idx].data = data;
+ display_post(idx);
+}
+
+#define POST(what, data) post(id, what, data)
+
+int uart_data(int x) {
+ return 2 * x + 1;
+}
+
+static void tx(volatile int *uart_tx, int data) {
+ *uart_tx = data;
+ wait_cycles(5);
+// assert(*uart_tx == 0);
+}
+
+#define TX(data) tx(uart_tx, uart_data(data))
+#define KILL_UART() tx(uart_tx, 2)
+
+static int rx(volatile int *uart_rx) {
+ int read = *uart_rx;
+ *uart_rx = 0;
+ return read;
+}
+
+#define RX() rx(uart_rx)
+
+void worker(int id, volatile int *uart_tx, volatile int *uart_rx, volatile int *ready_out, volatile const int *ready_in){
+ int current_instr = 0;
+
+ int state = STATE_IDLE;
+ *ready_out = 1;
+ *uart_tx = 0;
+ POST(BLOG_THREAD_STARTED, 0);
+
+ int read, kind, instruction, address, data;
+
+ while(1) {
+ switch(state) {
+ case STATE_IDLE:
+ read = RX();
+ wait_one_cycle();
+ if(read == 2) { // upstream dead!
+ KILL_UART();
+ return;
+ }
+ if(!read) /* nothing on uart */
+ break;
+ kind = read >> 1;
+ POST(BLOG_READ_KIND, kind);
+ if(kind == 1)
+ state = STATE_READ_INSTRUCTION;
+ else if(kind == 2)
+ state = STATE_READ_NEWS_ADDRESS;
+ else
+ POST(BLOG_UART_BAD_KIND, kind);
+ break;
+
+ case STATE_READ_INSTRUCTION:
+ read = RX();
+ wait_one_cycle();
+ if(!read) /* nothing on uart */
+ break;
+ instruction = read >> 1;
+ current_instr = instruction;
+ *ready_out = 0;
+ POST(BLOG_READ_INSTRUCTION, instruction);
+ state = STATE_PROPAGATE;
+ break;
+
+ case STATE_READ_NEWS_ADDRESS:
+ read = RX();
+ wait_one_cycle();
+ if(!read) /* nothing on uart */
+ break;
+ address = read >> 1;
+ current_instr = address;
+ POST(BLOG_READ_NEWS_ADDRESS, address);
+ state = STATE_READ_NEWS_DATA;
+ break;
+
+ case STATE_READ_NEWS_DATA:
+ read = RX();
+ wait_one_cycle();
+ if(!read) /* nothing on uart */
+ break;
+ data = read >> 1;
+ /* we now have the address in [current_instr] and data in [data].
+ We write a NOP instruction because we have no memory. */
+ current_instr = INSTR_NOP;
+ *ready_out = 0;
+ POST(BLOG_READ_NEWS_DATA, data);
+ state = STATE_EXECUTE;
+ break;
+
+ case STATE_PROPAGATE:
+ if(!*ready_in)
+ break;
+ TX(1); /* we're writing an instruction */
+ state = STATE_PROPAGATE2;
+ break;
+
+ case STATE_PROPAGATE2:
+ if(!*ready_in) {
+ POST(BLOG_BECAME_NOT_READY, state);
+ state = STATE_PROPAGATE;
+ break;
+ }
+ TX(current_instr);
+ state = STATE_EXECUTE;
+ break;
+
+ case STATE_EXECUTE:
+ wait_one_cycle(); // execution takes time! (not really)
+ if(current_instr == INSTR_ROUTE) {
+ state = STATE_NEWS;
+ POST(BLOG_EXECUTED_INSTR, current_instr);
+// POST(BLOG_TRY_SENDING_NEWS, 0);
+ } else {
+ state = STATE_IDLE;
+ *ready_out = 1;
+ POST(BLOG_EXECUTED_INSTR, current_instr);
+ }
+ break;
+
+ case STATE_NEWS:
+ if(!*ready_in)
+ break;
+ TX(2);
+ state = STATE_NEWS2;
+ break;
+
+ case STATE_NEWS2:
+ if(!*ready_in) {
+ POST(BLOG_BECAME_NOT_READY, state);
+ state = STATE_NEWS;
+ break;
+ }
+ TX(rand() & 0xFF);
+ state = STATE_NEWS3;
+ break;
+
+ case STATE_NEWS3:
+ if(!*ready_in) {
+ POST(BLOG_BECAME_NOT_READY, state);
+ state = STATE_NEWS;
+ break;
+ }
+ TX(rand() & 0xFF);
+ state = STATE_IDLE;
+ *ready_out = 1;
+// POST(BLOG_DONE_SENDING_NEWS, 0);
+ break;
+
+ default:
+ POST(BLOG_INVALID_STATE, state);
+ break;
+ }
+ wait_one_cycle();
+ }
+}
+
+#define MASTER_SEND_INSTRUCTION 0
+#define MASTER_SEND_INSTRUCTION2 10
+#define MASTER_WAIT_FOR_NEWS 1
+#define MASTER_READ_NEWS_ADDRESS 11
+#define MASTER_READ_NEWS_DATA 21
+#define MASTER_WAIT_FOR_PROPAGATE 2
+#define MASTER_WAIT_FOR_PROPAGATE2 12
+
+void master(volatile int *uart_tx, volatile int *uart_rx, volatile int *ready_out, volatile const int *ready_in){
+ int instructions_left = 10;
+ int state = MASTER_SEND_INSTRUCTION;
+ int ignore_next_rx = 0;
+ const int id = 0;
+ int read, kind, instruction, data, rnd;
+
+ *uart_tx = 0;
+ *ready_out = 1;
+ POST(BLOG_THREAD_STARTED, 0);
+
+ while(1) {
+ switch(state) {
+ case MASTER_SEND_INSTRUCTION:
+ if(!instructions_left) { /* done! */
+ KILL_UART();
+ return;
+ }
+ if(!*ready_in)
+ break;
+ TX(1);
+ state = MASTER_SEND_INSTRUCTION2;
+ break;
+
+ case MASTER_SEND_INSTRUCTION2:
+ if(!*ready_in) {
+ POST(BLOG_BECAME_NOT_READY, state);
+ state = MASTER_SEND_INSTRUCTION;
+ break;
+ }
+ /* manufacture an instruction */
+ rnd = rand() & 7;
+ if(rnd <= 4)
+ instruction = INSTR_NOP;
+ else if(rnd <= 6)
+ instruction = INSTR_ROUTE;
+ else
+ instruction = INSTR_ROUTE; /* actually READ */
+
+ POST(BLOG_MANUFACTURED_INSTRUCTION, rnd);
+ TX(instruction);
+ instructions_left--;
+
+ if(instruction == INSTR_ROUTE)
+ state = MASTER_WAIT_FOR_NEWS;
+ else
+ state = MASTER_WAIT_FOR_PROPAGATE;
+ break;
+
+ case MASTER_WAIT_FOR_PROPAGATE:
+ read = RX();
+ wait_one_cycle();
+ if(!read) /* nothing on uart */
+ break;
+ kind = read >> 1;
+ if(kind == 1)
+ state = MASTER_WAIT_FOR_PROPAGATE2;
+ else /* kind == 2 is also bad here */
+ POST(BLOG_UART_BAD_KIND, kind);
+ break;
+
+ case MASTER_WAIT_FOR_PROPAGATE2:
+ read = RX();
+ wait_one_cycle();
+ if(!read) /* nothing on uart */
+ break;
+ instruction = read >> 1; /* we don't care about this */
+ state = MASTER_SEND_INSTRUCTION;
+ break;
+
+ case MASTER_WAIT_FOR_NEWS:
+ read = RX();
+ wait_one_cycle();
+ if(!read) /* nothing on uart */
+ break;
+ kind = read >> 1;
+ if(ignore_next_rx)
+ ignore_next_rx = 0;
+ else if(kind == 1) /* propagation, ignore next byte */
+ ignore_next_rx = 1;
+ else if(kind == 2) { /* ka-ching! */
+ state = MASTER_READ_NEWS_ADDRESS;
+ } else
+ POST(BLOG_UART_BAD_KIND, kind);
+ break;
+
+ case MASTER_READ_NEWS_ADDRESS:
+ read = RX();
+ wait_one_cycle();
+ if(!read) /* nothing on uart */
+ break;
+ /* we do not care about the address, we go read the data */
+ state = MASTER_READ_NEWS_DATA;
+ break;
+
+ case MASTER_READ_NEWS_DATA:
+ read = RX();
+ wait_one_cycle();
+ if(!read) /* nothing on uart */
+ break;
+ data = read >> 1;
+ POST(BLOG_READ_NEWS_DATA, data);
+ state = MASTER_SEND_INSTRUCTION;
+ break;
+
+ default:
+ POST(BLOG_INVALID_STATE, state);
+ break;
+ }
+ wait_one_cycle();
+ }
+ KILL_UART();
+}
+
+static int uarts[5];
+static int ready[5];
+static pthread_t threads[5];
+
+void* spawn_thread(void* index) {
+ switch((long)index) {
+ case 0:
+ master(uarts + 0, uarts + 4, ready + 4, ready + 0);
+ break;
+ case 1:
+ worker(1, uarts + 1, uarts + 0, ready + 0, ready + 1);
+ break;
+ case 2:
+ worker(2, uarts + 2, uarts + 1, ready + 1, ready + 2);
+ break;
+ case 3:
+ worker(3, uarts + 3, uarts + 2, ready + 2, ready + 3);
+ break;
+ case 4:
+ worker(4, uarts + 4, uarts + 3, ready + 3, ready + 4);
+ break;
+ default:
+ printf("Spawned bad thread %ld\n", (long)index);
+ }
+ return NULL;
+}
+
+int main(void){
+ for(long i = 0 ; i < 5 ; i++)
+ pthread_create(threads + i, NULL, spawn_thread, (void*)i);
+ for(int i = 0 ; i < 5 ; i++)
+ pthread_join(threads[i], NULL);
+// for(int i = 0; i < blog_n; i++)
+// display_post(i);
+ return 0;
+}