aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authorPaul Oliver <contact@pauloliver.dev>2024-02-29 02:29:13 +0100
committerPaul Oliver <contact@pauloliver.dev>2024-02-29 02:29:13 +0100
commitca118555214a176728b9aab87849391344306d6d (patch)
tree833cffdd4066a7114b1d79d6eeaa2e0152408fc8 /src
Initial commit.
Diffstat (limited to 'src')
-rw-r--r--src/common.c72
-rw-r--r--src/evolver.c132
-rw-r--r--src/instset.c39
-rw-r--r--src/memory.c325
-rw-r--r--src/process.c1488
-rw-r--r--src/salis.c109
6 files changed, 2165 insertions, 0 deletions
diff --git a/src/common.c b/src/common.c
new file mode 100644
index 0000000..3653252
--- /dev/null
+++ b/src/common.c
@@ -0,0 +1,72 @@
+#include <assert.h>
+#include <fcntl.h>
+#include <sys/stat.h>
+#include <unistd.h>
+#include "types.h"
+#include "instset.h"
+#include "common.h"
+
+static boolean g_is_init;
+static int g_file_desc;
+
+void _sal_comm_init(string pipe)
+{
+ /* Initialize the common pipe. This module is the only one on Salis that
+ makes use of Linux specific headers and types. If you want, feel free to
+ port this code into other platforms (should be easy). If you do so, let me
+ know and we can incorporate it into the Salis repository.
+ */
+ assert(!g_is_init);
+ mkfifo(pipe, 0666);
+ g_is_init = TRUE;
+
+ /* It's important to open the FIFO file in non-blocking mode, or else the
+ simulators might halt if the pipe becomes empty.
+ */
+ g_file_desc = open(pipe, O_RDWR | O_NONBLOCK);
+ assert(g_file_desc != -1);
+}
+
+void _sal_comm_quit(void)
+{
+ /* Close the common pipe FIFO file from within this instance. An empty pipe
+ file will remain unless it gets manually deleted.
+ */
+ assert(g_is_init);
+ close(g_file_desc);
+ g_is_init = FALSE;
+ g_file_desc = 0;
+}
+
+void _sal_comm_send(uint8 inst)
+{
+ /* Send a single byte (instruction) to the common pipe. This function is
+ called by processes that execute the SEND instruction. Hopefully, some of
+ them 'learn' to use this as an advantage.
+
+ In the future, I want to make the common pipe able to communicate across
+ local networks (LANs) and over the Internet.
+ */
+ assert(g_is_init);
+ assert(sal_is_inst(inst));
+ write(g_file_desc, &inst, 1);
+}
+
+uint8 _sal_comm_receive(void)
+{
+ /* Receive a single byte (instruction) from the common pipe. This function
+ is called by processes that execute the RCVE instruction. If the pipe is
+ empty, this function returns the NOP0 instruction.
+ */
+ uint8 inst;
+ ssize_t res;
+ assert(g_is_init);
+ res = read(g_file_desc, &inst, 1);
+
+ if (res) {
+ assert(sal_is_inst(inst));
+ return inst;
+ } else {
+ return NOP0;
+ }
+}
diff --git a/src/evolver.c b/src/evolver.c
new file mode 100644
index 0000000..e3b6ef7
--- /dev/null
+++ b/src/evolver.c
@@ -0,0 +1,132 @@
+#include <assert.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <time.h>
+#include "types.h"
+#include "getter.h"
+#include "instset.h"
+#include "memory.h"
+#include "evolver.h"
+
+static boolean g_is_init;
+static uint32 g_last_changed_address;
+static uint32 g_calls_on_last_cycle;
+static uint32 g_state[4];
+
+void _sal_evo_init(void)
+{
+ /* Start up the evolver module. We simply set the 128 bits into a random
+ state by calling 'rand()'.
+ */
+ assert(!g_is_init);
+ srand((uint32)time(NULL));
+ g_state[0] = rand();
+ g_state[1] = rand();
+ g_state[2] = rand();
+ g_state[3] = rand();
+ g_is_init = TRUE;
+}
+
+void _sal_evo_quit(void)
+{
+ /* Quit the evolver module. Reset everything back to zero.
+ */
+ assert(g_is_init);
+ g_is_init = FALSE;
+ g_last_changed_address = 0;
+ g_calls_on_last_cycle = 0;
+ memset(g_state, 0, sizeof(uint32) * 4);
+}
+
+void _sal_evo_load_from(FILE *file)
+{
+ /* Load evolver state from a binary file.
+ */
+ assert(!g_is_init);
+ assert(file);
+ fread(&g_is_init, sizeof(boolean), 1, file);
+ fread(&g_last_changed_address, sizeof(uint32), 1, file);
+ fread(&g_calls_on_last_cycle, sizeof(uint32), 1, file);
+ fread(&g_state, sizeof(uint32), 4, file);
+}
+
+void _sal_evo_save_into(FILE *file)
+{
+ /* Save evolver state into a binary file.
+ */
+ assert(g_is_init);
+ assert(file);
+ fwrite(&g_is_init, sizeof(boolean), 1, file);
+ fwrite(&g_last_changed_address, sizeof(uint32), 1, file);
+ fwrite(&g_calls_on_last_cycle, sizeof(uint32), 1, file);
+ fwrite(&g_state, sizeof(uint32), 4, file);
+}
+
+/* Getter methods for the evolver module.
+*/
+UINT32_GETTER(evo, last_changed_address)
+UINT32_GETTER(evo, calls_on_last_cycle)
+
+uint32 sal_evo_get_state(uint8 state_index)
+{
+ /* Get part of the evolver's internal state (32 bits of 128 total bits) as
+ an unsigned int.
+ */
+ assert(g_is_init);
+ assert(state_index < 4);
+ return g_state[state_index];
+}
+
+static uint32 generate_random_number(void)
+{
+ /* Generate a single 32 bit random number. This module makes use of the
+ XOR-Shift pseudo-rng. We use XOR-Shift because it's extremely lightweight
+ and fast, while providing quite good results. Find more info about it here:
+ >>> https://en.wikipedia.org/wiki/Xorshift
+ */
+ uint32 tmp1;
+ uint32 tmp2;
+ assert(g_is_init);
+ tmp2 = g_state[3];
+ tmp2 ^= tmp2 << 11;
+ tmp2 ^= tmp2 >> 8;
+ g_state[3] = g_state[2];
+ g_state[2] = g_state[1];
+ g_state[1] = tmp1 = g_state[0];
+ tmp2 ^= tmp1;
+ tmp2 ^= tmp1 >> 19;
+ g_state[0] = tmp2;
+ g_calls_on_last_cycle++;
+ return tmp2;
+}
+
+void _sal_evo_randomize_at(uint32 address)
+{
+ /* Place a random instruction into a given address.
+ */
+ uint8 inst;
+ assert(g_is_init);
+ assert(sal_mem_is_address_valid(address));
+ inst = generate_random_number() % INST_COUNT;
+ g_last_changed_address = address;
+ sal_mem_set_inst(address, inst);
+}
+
+void _sal_evo_cycle(void)
+{
+ /* During each simulation cycle, a random 32 bit integer is generated. If
+ this integer represents a 'valid' address in memory
+ (i.e. new_rand < memory_size), this address becomes hit by a cosmic ray
+ (randomized). This simple mutation scheme is enough to drive evolution in
+ Salis.
+ */
+ uint32 address;
+ assert(g_is_init);
+ g_calls_on_last_cycle = 0;
+ address = generate_random_number();
+
+ if (sal_mem_is_address_valid(address)) {
+ _sal_evo_randomize_at(address);
+ }
+}
diff --git a/src/instset.c b/src/instset.c
new file mode 100644
index 0000000..2ab127a
--- /dev/null
+++ b/src/instset.c
@@ -0,0 +1,39 @@
+#include <assert.h>
+#include "types.h"
+#include "instset.h"
+
+boolean sal_is_inst(uint32 word)
+{
+ /* Test if a given 32 bit integer contains a valid Salis instruction.
+ */
+ return word < INST_COUNT;
+}
+
+static boolean is_in_between(uint32 inst, uint32 low, uint32 hi)
+{
+ /* Test whether a Salis instruction lies within a given range. This is
+ useful for identifying template instructions and/or register modifiers.
+ */
+ assert(sal_is_inst(inst));
+ assert(sal_is_inst(low));
+ assert(sal_is_inst(hi));
+ return (inst >= low) && (inst <= hi);
+}
+
+boolean sal_is_template(uint32 inst)
+{
+ /* Test whether a given instruction is a template element
+ (i.e. NOP0 or NOP1).
+ */
+ assert(sal_is_inst(inst));
+ return is_in_between(inst, NOP0, NOP1);
+}
+
+boolean sal_is_mod(uint32 inst)
+{
+ /* Test whether a given instruction is a register modifier
+ (i.e. MODA, MODB, MODC or MODD).
+ */
+ assert(sal_is_inst(inst));
+ return is_in_between(inst, MODA, MODD);
+}
diff --git a/src/memory.c b/src/memory.c
new file mode 100644
index 0000000..c586eb0
--- /dev/null
+++ b/src/memory.c
@@ -0,0 +1,325 @@
+#include <assert.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include "types.h"
+#include "getter.h"
+#include "instset.h"
+#include "memory.h"
+
+#define MAX_ZOOM 0x10000
+
+static boolean g_is_init;
+static uint32 g_order;
+static uint32 g_size;
+static uint32 g_ip_count;
+static uint32 g_block_start_count;
+static uint32 g_allocated_count;
+static uint32 g_capacity;
+static uint32 g_inst_counter[INST_COUNT];
+static uint8_p g_memory;
+
+void _sal_mem_init(uint32 order)
+{
+ /* Set memory module to its initial state. We calculate memory size based
+ on its order (size = 1 << order) and allocate an array of such size. We
+ also initialize the array completely to zero.
+ */
+ assert(!g_is_init);
+ assert(order < 32);
+ g_is_init = TRUE;
+ g_order = order;
+ g_size = 1 << g_order;
+ g_capacity = g_size / 2;
+ g_inst_counter[0] = g_size;
+ g_memory = calloc(g_size, 1);
+ assert(g_memory);
+}
+
+void _sal_mem_quit(void)
+{
+ /* Reset memory module entirely back to zero. That way, we can load several
+ simulations without restarting the application entirely.
+ */
+ assert(g_is_init);
+ free(g_memory);
+ g_is_init = FALSE;
+ g_order = 0;
+ g_size = 0;
+ g_ip_count = 0;
+ g_block_start_count = 0;
+ g_allocated_count = 0;
+ g_capacity = 0;
+ memset(g_inst_counter, 0, sizeof(uint32) * INST_COUNT);
+ g_memory = NULL;
+}
+
+void _sal_mem_load_from(FILE *file)
+{
+ /* Load memory state from a binary file.
+ */
+ assert(!g_is_init);
+ assert(file);
+ fread(&g_is_init, sizeof(boolean), 1, file);
+ fread(&g_order, sizeof(uint32), 1, file);
+ fread(&g_size, sizeof(uint32), 1, file);
+ fread(&g_ip_count, sizeof(uint32), 1, file);
+ fread(&g_block_start_count, sizeof(uint32), 1, file);
+ fread(&g_allocated_count, sizeof(uint32), 1, file);
+ fread(&g_capacity, sizeof(uint32), 1, file);
+ fread(g_inst_counter, sizeof(uint32), INST_COUNT, file);
+ g_memory = calloc(g_size, sizeof(uint8));
+ assert(g_memory);
+ fread(g_memory, sizeof(uint8), g_size, file);
+}
+
+void _sal_mem_save_into(FILE *file)
+{
+ /* Save memory state to a binary file.
+ */
+ assert(g_is_init);
+ assert(file);
+ fwrite(&g_is_init, sizeof(boolean), 1, file);
+ fwrite(&g_order, sizeof(uint32), 1, file);
+ fwrite(&g_size, sizeof(uint32), 1, file);
+ fwrite(&g_ip_count, sizeof(uint32), 1, file);
+ fwrite(&g_block_start_count, sizeof(uint32), 1, file);
+ fwrite(&g_allocated_count, sizeof(uint32), 1, file);
+ fwrite(&g_capacity, sizeof(uint32), 1, file);
+ fwrite(g_inst_counter, sizeof(uint32), INST_COUNT, file);
+ fwrite(g_memory, sizeof(uint8), g_size, file);
+}
+
+/* Getter methods for the memory module.
+*/
+UINT32_GETTER(mem, order)
+UINT32_GETTER(mem, size)
+UINT32_GETTER(mem, ip_count)
+UINT32_GETTER(mem, block_start_count)
+UINT32_GETTER(mem, allocated_count)
+UINT32_GETTER(mem, capacity)
+
+uint32 sal_mem_get_inst_count(uint8 inst)
+{
+ /* Return number of times a certain instruction appears in memory. The
+ instruction counter gets updated dynamically during each cycle.
+ */
+ assert(g_is_init);
+ assert(sal_is_inst(inst));
+ return g_inst_counter[inst];
+}
+
+boolean sal_mem_is_over_capacity(void)
+{
+ /* Check if memory is filled above 50%. If so, old organisms will be popped
+ out of the reaper queue!
+ */
+ assert(g_is_init);
+ return g_allocated_count > g_capacity;
+}
+
+boolean sal_mem_is_address_valid(uint32 address)
+{
+ /* Check if given address is valid.
+ */
+ assert(g_is_init);
+ return address < g_size;
+}
+
+/* We declare a standard macro to test whether a specific FLAG is set on a given
+byte. Remember, a Salis byte contains a 5 bit instruction (of 32 possible) plus
+3 flags: IP, BLOCK_START and ALLOCATED. These flags help organisms identify
+where there is free memory space to reproduce on, and tell the python printer
+module how to color each byte.
+*/
+#define FLAG_TEST(name, flag) \
+boolean sal_mem_is_##name(uint32 address) \
+{ \
+ assert(g_is_init); \
+ assert(sal_mem_is_address_valid(address)); \
+ return !!(g_memory[address] & flag); \
+}
+
+FLAG_TEST(ip, IP_FLAG)
+FLAG_TEST(block_start, BLOCK_START_FLAG)
+FLAG_TEST(allocated, ALLOCATED_FLAG)
+
+/* We define a standard macro for 'setting' one of the 3 FLAGS into a given
+memory address.
+*/
+#define FLAG_SETTER(name, flag) \
+void _sal_mem_set_##name(uint32 address) \
+{ \
+ assert(g_is_init); \
+ assert(sal_mem_is_address_valid(address)); \
+\
+ if (!sal_mem_is_##name(address)) { \
+ g_memory[address] ^= flag; \
+ g_##name##_count++; \
+ } \
+}
+
+FLAG_SETTER(ip, IP_FLAG)
+FLAG_SETTER(block_start, BLOCK_START_FLAG)
+FLAG_SETTER(allocated, ALLOCATED_FLAG)
+
+/* We define a standard macro for 'unsetting' one of the 3 FLAGS into a given
+memory address.
+*/
+#define FLAG_UNSETTER(name, flag) \
+void _sal_mem_unset_##name(uint32 address) \
+{ \
+ assert(g_is_init); \
+ assert(sal_mem_is_address_valid(address)); \
+\
+ if (sal_mem_is_##name(address)) { \
+ g_memory[address] ^= flag; \
+ g_##name##_count--; \
+ } \
+}
+
+FLAG_UNSETTER(ip, IP_FLAG)
+FLAG_UNSETTER(block_start, BLOCK_START_FLAG)
+FLAG_UNSETTER(allocated, ALLOCATED_FLAG)
+
+uint8 sal_mem_get_flags(uint32 address)
+{
+ /* Get FLAG bits currently set on a specified address (byte). These may be
+ queried by using a bitwise 'and' operator against the returned byte.
+ */
+ assert(g_is_init);
+ assert(sal_mem_is_address_valid(address));
+ return g_memory[address] & ~INSTRUCTION_MASK;
+}
+
+uint8 sal_mem_get_inst(uint32 address)
+{
+ /* Get instruction currently set on a specified address (byte), with the
+ FLAG bits turned off.
+ */
+ assert(g_is_init);
+ assert(sal_mem_is_address_valid(address));
+ return g_memory[address] & INSTRUCTION_MASK;
+}
+
+void sal_mem_set_inst(uint32 address, uint8 inst)
+{
+ /* Set instruction at given address. This is useful when performing manual
+ memory manipulations (like compiling organism genomes).
+ */
+ assert(g_is_init);
+ assert(sal_mem_is_address_valid(address));
+ assert(sal_is_inst(inst));
+ g_inst_counter[sal_mem_get_inst(address)]--;
+ g_memory[address] &= ~INSTRUCTION_MASK;
+ g_memory[address] |= inst;
+ g_inst_counter[inst]++;
+}
+
+uint8 sal_mem_get_byte(uint32 address)
+{
+ /* Get unadulterated byte at given address. This could be used, for
+ example, to render nice images of the memory state.
+ */
+ assert(g_is_init);
+ assert(sal_mem_is_address_valid(address));
+ return g_memory[address];
+}
+
+void sal_mem_render_image(
+ uint32 origin, uint32 cell_size, uint32 buff_size, uint8_p buffer
+) {
+ /* Render a 1D image of a given section of memory, at a given resolution
+ (zoom) and store it in a pre-allocated 'buffer'.
+
+ On the Salis python handler we draw memory as a 1D 'image' on the WORLD
+ page. If we were to render this image directly on python, it would be
+ excruciatingly slow, as we have to iterate over large areas of memory!
+ Therefore, this memory module comes with a built-in, super fast renderer.
+ */
+ uint32 i;
+ assert(g_is_init);
+ assert(sal_mem_is_address_valid(origin));
+ assert(cell_size);
+ assert(cell_size <= MAX_ZOOM);
+ assert(buff_size);
+ assert(buffer);
+
+ /* We make use of openmp for multi-threaded looping. This allows even
+ faster render times, wherever openmp is supported.
+ */
+ #pragma omp parallel for
+ for (i = 0; i < buff_size; i++) {
+ uint32 j;
+ uint32 flag_sum = 0;
+ uint32 inst_sum = 0;
+ uint32 cell_addr = origin + (i * cell_size);
+
+ for (j = 0; j < cell_size; j++) {
+ uint32 address = j + cell_addr;
+
+ if (sal_mem_is_address_valid(address)) {
+ flag_sum |= sal_mem_get_flags(address);
+ inst_sum += sal_mem_get_inst(address);
+ }
+ }
+
+ buffer[i] = (uint8)(inst_sum / cell_size);
+ buffer[i] |= (uint8)(flag_sum);
+ }
+}
+
+static boolean inst_count_is_correct(void)
+{
+ /* Check that the instruction counter is in a valid state
+ (i.e. SUM inst_counter[0..(INST_COUNT - 1)] == memory_size).
+ */
+ uint32 i;
+ uint32 sum = 0;
+ assert(g_is_init);
+
+ for (i = 0; i < INST_COUNT; i++) {
+ assert(g_inst_counter[i] <= sal_mem_get_size());
+ sum += g_inst_counter[i];
+ }
+
+ return sum == g_size;
+}
+
+static boolean module_is_valid(void)
+{
+ /* Check for validity of memory module. This function only gets called when
+ Salis is running in debug mode. It makes Salis **very** slow in comparison
+ to when running optimized, but it is also **very** useful for debugging!
+ */
+ uint32 bidx;
+ uint32 ip_count = 0;
+ uint32 block_start_count = 0;
+ uint32 allocated_count = 0;
+ assert(g_is_init);
+ assert(g_capacity <= g_size / 2);
+ assert(inst_count_is_correct());
+
+ /* Iterate through all memory, counting the flags set on each address. We
+ then compare the sum to the flag counters to assert module validity.
+ */
+ for (bidx = 0; bidx < g_size; bidx++) {
+ if (sal_mem_is_ip(bidx)) ip_count++;
+ if (sal_mem_is_block_start(bidx)) block_start_count++;
+ if (sal_mem_is_allocated(bidx)) allocated_count++;
+ }
+
+ assert(ip_count == g_ip_count);
+ assert(block_start_count == g_block_start_count);
+ assert(allocated_count == g_allocated_count);
+ return TRUE;
+}
+
+void _sal_mem_cycle(void)
+{
+ /* Cycle memory module. Simply assert validity when running in debug mode.
+ When running optimized, this function does nothing.
+ */
+ assert(g_is_init);
+ assert(module_is_valid());
+}
diff --git a/src/process.c b/src/process.c
new file mode 100644
index 0000000..8d500ae
--- /dev/null
+++ b/src/process.c
@@ -0,0 +1,1488 @@
+#include <assert.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include "types.h"
+#include "getter.h"
+#include "instset.h"
+#include "memory.h"
+#include "evolver.h"
+#include "common.h"
+#include "process.h"
+
+static boolean g_is_init;
+static uint32 g_count;
+static uint32 g_capacity;
+static uint32 g_first;
+static uint32 g_last;
+static uint32 g_instructions_executed;
+static Process *g_procs;
+
+void _sal_proc_init(void)
+{
+ /* Initialize process module to its initial state. We initialize the reaper
+ queue with a capacity of 1. 'First' and 'last' organism pointers are
+ initialized to (uint32)-1 (to indicate they point to no organism, as no
+ organism exists yet).
+ */
+ assert(!g_is_init);
+ g_is_init = TRUE;
+ g_capacity = 1;
+ g_first = UINT32_MAX;
+ g_last = UINT32_MAX;
+ g_procs = calloc(g_capacity, sizeof(Process));
+ assert(g_procs);
+}
+
+void _sal_proc_quit(void)
+{
+ /* Reset process module back to zero; free up the process queue.
+ */
+ assert(g_is_init);
+ free(g_procs);
+ g_is_init = FALSE;
+ g_count = 0;
+ g_capacity = 0;
+ g_first = 0;
+ g_last = 0;
+ g_instructions_executed = 0;
+ g_procs = NULL;
+}
+
+void _sal_proc_load_from(FILE *file)
+{
+ /* Load process module state from a binary file.
+ */
+ assert(!g_is_init);
+ assert(file);
+ fread(&g_is_init, sizeof(boolean), 1, file);
+ fread(&g_count, sizeof(uint32), 1, file);
+ fread(&g_capacity, sizeof(uint32), 1, file);
+ fread(&g_first, sizeof(uint32), 1, file);
+ fread(&g_last, sizeof(uint32), 1, file);
+ fread(&g_instructions_executed, sizeof(uint32), 1, file);
+ g_procs = calloc(g_capacity, sizeof(Process));
+ assert(g_procs);
+ fread(g_procs, sizeof(Process), g_capacity, file);
+}
+
+void _sal_proc_save_into(FILE *file)
+{
+ /* Save process module state to a binary file.
+ */
+ assert(g_is_init);
+ assert(file);
+ fwrite(&g_is_init, sizeof(boolean), 1, file);
+ fwrite(&g_count, sizeof(uint32), 1, file);
+ fwrite(&g_capacity, sizeof(uint32), 1, file);
+ fwrite(&g_first, sizeof(uint32), 1, file);
+ fwrite(&g_last, sizeof(uint32), 1, file);
+ fwrite(&g_instructions_executed, sizeof(uint32), 1, file);
+ fwrite(g_procs, sizeof(Process), g_capacity, file);
+}
+
+/* Getter methods for the process module.
+*/
+UINT32_GETTER(proc, count)
+UINT32_GETTER(proc, capacity)
+UINT32_GETTER(proc, first)
+UINT32_GETTER(proc, last)
+UINT32_GETTER(proc, instructions_executed)
+
+boolean sal_proc_is_free(uint32 proc_id)
+{
+ /* In Salis, the reaper queue is implemented as a circular queue. Thus, at
+ any given time, a process ID (which actually denotes a process 'address'
+ or, more correctly, a process 'container address') might contain a living
+ process or be empty. This function checks for the 'living' state of a given
+ process ID.
+ */
+ assert(g_is_init);
+ assert(proc_id < g_capacity);
+
+ if (!g_procs[proc_id].mb1s) {
+ /* When running in debug mode, we make sure that non-living processes
+ are completely set to zero, as this is the expected state.
+ */
+ #ifndef NDEBUG
+ Process dummy_proc;
+ memset(&dummy_proc, 0, sizeof(Process));
+ assert(!memcmp(&dummy_proc, &g_procs[proc_id], sizeof(Process)));
+ #endif
+
+ return TRUE;
+ }
+
+ return FALSE;
+}
+
+Process sal_proc_get_proc(uint32 proc_id)
+{
+ /* Get a **copy** (not a reference) of the process with the given ID. Note,
+ this might be a non-living process.
+ */
+ assert(g_is_init);
+ assert(proc_id < g_capacity);
+ return g_procs[proc_id];
+}
+
+void sal_proc_get_proc_data(uint32 proc_id, uint32_p buffer)
+{
+ /* Get a **copy** (not a reference) of the process with the given ID
+ (represented as a string of 32 bit integers) written into the given buffer.
+ The buffer must be pre-allocated to a large enough size
+ (i.e. malloc(sizeof(Process))). Note, copied process might be in a
+ non-living state.
+ */
+ assert(g_is_init);
+ assert(proc_id < g_capacity);
+ assert(buffer);
+ memcpy(buffer, &g_procs[proc_id], sizeof(Process));
+}
+
+static boolean block_is_free_and_valid(uint32 address, uint32 size)
+{
+ /* Iterate all addresses in the given memory block and check that they lie
+ within memory bounds and have the ALLOCATED flag unset.
+ */
+ uint32 offset;
+
+ for (offset = 0; offset < size; offset++) {
+ uint32 off_addr = offset + address;
+ if (!sal_mem_is_address_valid(off_addr)) return FALSE;
+ if (sal_mem_is_allocated(off_addr)) return FALSE;
+
+ /* Deallocated addresses must have the BLOCK_START flag unset as well.
+ */
+ assert(!sal_mem_is_block_start(off_addr));
+ }
+
+ return TRUE;
+}
+
+static void realloc_queue(uint32 queue_lock)
+{
+ /* Reallocate reaper queue into a new circular queue with double the
+ capacity. This function gets called whenever the reaper queue fills up
+ with new organisms.
+
+ A queue_lock parameter may be provided, which 'centers' the reallocation on
+ a given process ID. This means that, after reallocating the queue, the
+ process with that ID will keep still have the same ID on the new queue.
+ */
+ uint32 new_capacity;
+ Process *new_queue;
+ uint32 fwrd_idx;
+ uint32 back_idx;
+ assert(g_is_init);
+ assert(g_count == g_capacity);
+ assert(queue_lock < g_capacity);
+ new_capacity = g_capacity * 2;
+ new_queue = calloc(new_capacity, sizeof(Process));
+ assert(new_queue);
+ fwrd_idx = queue_lock;
+ back_idx = (queue_lock - 1) % new_capacity;
+
+ /* Copy all organisms that lie forward from queue lock.
+ */
+ while (TRUE) {
+ uint32 old_idx = fwrd_idx % g_capacity;
+ memcpy(&new_queue[fwrd_idx], &g_procs[old_idx], sizeof(Process));
+
+ if (old_idx == g_last) {
+ g_last = fwrd_idx;
+ break;
+ } else {
+ fwrd_idx++;
+ }
+ }
+
+ /* Copy all organisms that lie backwards from queue lock, making sure to
+ loop around the queue (with modulo '%') whenever the process index goes
+ below zero.
+ */
+ if (queue_lock != g_first) {
+ while (TRUE) {
+ uint32 old_idx = back_idx % g_capacity;
+ memcpy(&new_queue[back_idx], &g_procs[old_idx], sizeof(Process));
+
+ if (old_idx == g_first) {
+ g_first = back_idx;
+ break;
+ } else {
+ back_idx--;
+ back_idx %= new_capacity;
+ }
+ }
+ }
+
+ /* Free old reaper queue and re-link global pointer to new queue.
+ */
+ free(g_procs);
+ g_capacity = new_capacity;
+ g_procs = new_queue;
+}
+
+static uint32 get_new_proc_from_queue(uint32 queue_lock)
+{
+ /* Retrieve an unoccupied process ID from the reaper queue. This function
+ gets called whenever a new organism is generated (born).
+ */
+ assert(g_is_init);
+
+ /* If reaper queue is full, reallocate to double its current size.
+ */
+ if (g_count == g_capacity) {
+ realloc_queue(queue_lock);
+ }
+
+ g_count++;
+
+ if (g_count == 1) {
+ g_first = 0;
+ g_last = 0;
+ return 0;
+ } else {
+ g_last++;
+ g_last %= g_capacity;
+ return g_last;
+ }
+}
+
+static void proc_create(
+ uint32 address, uint32 size, uint32 queue_lock,
+ boolean set_ip, boolean allocate
+) {
+ /* Give birth to a new process! We must specify the address and size of the
+ new organism.
+ */
+ uint32 pidx;
+ assert(g_is_init);
+ assert(sal_mem_is_address_valid(address));
+ assert(sal_mem_is_address_valid(address + size - 1));
+
+ /* When organisms are generated manually (by an user), we must set the IP
+ flag on the first byte of its owned memory. When organisms replicate by
+ themselves, we don't set the flag, as it gets set at the end of the module
+ cycle. Take a look at the '_sal_proc_cycle()' function for more info.
+ */
+ if (set_ip) {
+ _sal_mem_set_ip(address);
+ }
+
+ /* When organisms are generated manually (by an user), we must explicitly
+ allocate its entire memory block. When organisms replicate by themselves,
+ we assume they have already allocated the child's memory, so we don't need
+ to do it here.
+ */
+ if (allocate) {
+ uint32 offset;
+ assert(block_is_free_and_valid(address, size));
+ _sal_mem_set_block_start(address);
+
+ for (offset = 0; offset < size; offset++) {
+ uint32 off_addr = offset + address;
+ _sal_mem_set_allocated(off_addr);
+ }
+ }
+
+ /* Get a new process ID for the child process. Also, set initial state of
+ the child process data structure.
+ */
+ pidx = get_new_proc_from_queue(queue_lock);
+ g_procs[pidx].mb1a = address;
+ g_procs[pidx].mb1s = size;
+ g_procs[pidx].ip = address;
+ g_procs[pidx].sp = address;
+}
+
+void sal_proc_create(uint32 address, uint32 mb1s)
+{
+ /* API function to create a new process. Memory address and size of new
+ process must be provided.
+ */
+ assert(g_is_init);
+ assert(block_is_free_and_valid(address, mb1s));
+ proc_create(address, mb1s, 0, TRUE, TRUE);
+}
+
+static void free_memory_block(uint32 address, uint32 size)
+{
+ /* Deallocate a memory block. This includes unsetting the BLOCK_START flag
+ on the first byte.
+ */
+ uint32 offset;
+ assert(sal_mem_is_address_valid(address));
+ assert(sal_mem_is_address_valid(address + size - 1));
+ assert(sal_mem_is_block_start(address));
+ assert(size);
+ _sal_mem_unset_block_start(address);
+
+ for (offset = 0; offset < size; offset++) {
+ /* Iterate all addresses in block and unset the ALLOCATED flag in them.
+ */
+ uint32 off_addr = offset + address;
+ assert(sal_mem_is_allocated(off_addr));
+ assert(!sal_mem_is_block_start(off_addr));
+ _sal_mem_unset_allocated(off_addr);
+ }
+}
+
+static void free_memory_owned_by(uint32 pidx)
+{
+ /* Free memory specifically owned by the process with the given ID.
+ */
+ assert(g_is_init);
+ assert(pidx < g_capacity);
+ assert(!sal_proc_is_free(pidx));
+ free_memory_block(g_procs[pidx].mb1a, g_procs[pidx].mb1s);
+
+ if (g_procs[pidx].mb2s) {
+ /* If process owns a child memory block, free it as well.
+ */
+ free_memory_block(g_procs[pidx].mb2a, g_procs[pidx].mb2s);
+ }
+}
+
+static void proc_kill(boolean reset_ips)
+{
+ /* Kill process on bottom of reaper queue (the oldest process).
+ */
+ assert(g_is_init);
+ assert(g_count);
+ assert(g_first != UINT32_MAX);
+ assert(g_last != UINT32_MAX);
+ assert(!sal_proc_is_free(g_first));
+
+ /* When called manually by an user, we must clear and reset the IP flags of
+ all processes in order to preserve module validity.
+ */
+ if (reset_ips) {
+ _sal_mem_unset_ip(g_procs[g_first].ip);
+ }
+
+ /* Free up owned memory and reset process data structure back to zero.
+ */
+ free_memory_owned_by(g_first);
+ memset(&g_procs[g_first], 0, sizeof(Process));
+ g_count--;
+
+ if (g_first == g_last) {
+ g_first = UINT32_MAX;
+ g_last = UINT32_MAX;
+ } else {
+ g_first++;
+ g_first %= g_capacity;
+ }
+
+ /* Reset IP flags of all living processes. We use openmp to do this faster.
+ */
+ if (reset_ips) {
+ uint32 pidx;
+
+ #pragma omp parallel for
+ for (pidx = 0; pidx < g_capacity; pidx++) {
+ if (!sal_proc_is_free(pidx)) {
+ _sal_mem_set_ip(g_procs[pidx].ip);
+ }
+ }
+ }
+}
+
+void sal_proc_kill(void)
+{
+ /* API function to kill a process. Make sure that at least one process is
+ alive, or 'assert()' will fail.
+ */
+ assert(g_is_init);
+ assert(g_count);
+ assert(g_first != UINT32_MAX);
+ assert(g_last != UINT32_MAX);
+ assert(!sal_proc_is_free(g_first));
+ proc_kill(TRUE);
+}
+
+static boolean block_is_allocated(uint32 address, uint32 size)
+{
+ /* Assert that a given memory block is fully allocated.
+ */
+ uint32 offset;
+ assert(g_is_init);
+
+ for (offset = 0; offset < size; offset++) {
+ uint32 off_addr = offset + address;
+ assert(sal_mem_is_address_valid(off_addr));
+ assert(sal_mem_is_allocated(off_addr));
+ }
+
+ return TRUE;
+}
+
+static boolean proc_is_valid(uint32 pidx)
+{
+ /* Assert that the process with the given ID is in a valid state. This
+ means that all of its owned memory must be allocated and that the proper
+ flags are set in place. IP and SP must be located in valid addresses.
+ */
+ assert(g_is_init);
+ assert(pidx < g_capacity);
+
+ if (!sal_proc_is_free(pidx)) {
+ assert(sal_mem_is_address_valid(g_procs[pidx].ip));
+ assert(sal_mem_is_address_valid(g_procs[pidx].sp));
+ assert(sal_mem_is_block_start(g_procs[pidx].mb1a));
+ assert(sal_mem_is_ip(g_procs[pidx].ip));
+ assert(block_is_allocated(g_procs[pidx].mb1a, g_procs[pidx].mb1s));
+
+ if (g_procs[pidx].mb2s) {
+ assert(sal_mem_is_block_start(g_procs[pidx].mb2a));
+ assert(block_is_allocated(g_procs[pidx].mb2a, g_procs[pidx].mb2s));
+ }
+ }
+
+ return TRUE;
+}
+
+static boolean module_is_valid(void)
+{
+ /* Check for validity of process module. This function only gets called
+ when Salis is running in debug mode. It makes Salis **very** slow in
+ comparison to when running optimized, but it is also **very** useful for
+ debugging!
+ */
+ uint32 pidx;
+ uint32 alloc_count = 0;
+ uint32 block_count = 0;
+ assert(g_is_init);
+ assert(g_count >= sal_mem_get_ip_count());
+
+ /* Check that each individual process is in a valid state. We can do this
+ in a multi-threaded way.
+ */
+ #pragma omp parallel for
+ for (pidx = 0; pidx < g_capacity; pidx++) {
+ assert(proc_is_valid(pidx));
+ }
+
+ /* Iterate all processes, counting their memory blocks and adding up their
+ memory block sizes. At the end, we compare the sums to the flag counters of
+ the memory module.
+ */
+ for (pidx = 0; pidx < g_capacity; pidx++) {
+ if (!sal_proc_is_free(pidx)) {
+ alloc_count += g_procs[pidx].mb1s;
+ block_count++;
+
+ if (g_procs[pidx].mb2s) {
+ assert(g_procs[pidx].mb1a != g_procs[pidx].mb2a);
+ alloc_count += g_procs[pidx].mb2s;
+ block_count++;
+ }
+ }
+ }
+
+ assert(block_count == sal_mem_get_block_start_count());
+ assert(alloc_count == sal_mem_get_allocated_count());
+ return TRUE;
+}
+
+static void toggle_ip_flag(void (*toggler)(uint32 address))
+{
+ /* At the start of each process module cycle, all memory addresses with the
+ IP flag set get their IP flag turned off. Once all processes finish
+ executing, the IP flags are turned on again on all addresses pointed by
+ 'g_procs[pidx].ip'. I've found this is the easiest way to preserve
+ correctness, given that more than one process can have their IPs pointed to
+ the same address.
+
+ This function simply iterates through all processes, setting the IP flag on
+ or off on the address pointed to by their IP.
+ */
+ uint32 pidx;
+ assert(g_is_init);
+
+ for (pidx = 0; pidx < g_capacity; pidx++) {
+ if (!sal_proc_is_free(pidx)) {
+ toggler(g_procs[pidx].ip);
+ }
+ }
+}
+
+static void on_fault(uint32 pidx)
+{
+ /* Organisms get punished whenever they execute an invalid instruction
+ (commit a 'fault') by having the halt one simulation cycle.
+ */
+ assert(g_is_init);
+ assert(pidx < g_capacity);
+ assert(!sal_proc_is_free(pidx));
+ g_procs[pidx].punish = 1;
+}
+
+static void increment_ip(uint32 pidx)
+{
+ /* After executing each instruction, increment the given organism's IP to
+ the next valid address.
+ */
+ assert(g_is_init);
+ assert(pidx < g_capacity);
+ assert(!sal_proc_is_free(pidx));
+
+ if (sal_mem_is_address_valid(g_procs[pidx].ip + 1)) {
+ g_procs[pidx].ip++;
+ }
+
+ /* Wherever IP goes, SP follows. :P
+ */
+ g_procs[pidx].sp = g_procs[pidx].ip;
+}
+
+static boolean are_templates_complements(uint32 source, uint32 complement)
+{
+ /* Check whether 2 templates are complements. Templates are introduced in
+ Salis-2.0 and they function in the same way as templates in the original
+ Tierra. They consist of string of NOP0 and NOP1 instructions.
+
+ We say that templates are complements whenever one is a 'negation' of
+ another (i.e. they are reverse copies of each other). So, on the following
+ example, the top template would be the complement of the bottom template.
+
+ >>> NOP0 - NOP1 - NOP1
+ >>> NOP1 - NOP0 - NOP0
+
+ This function looks into 2 given addresses in memory and checks whether
+ there are complementing templates on those addresses.
+ */
+ assert(g_is_init);
+ assert(sal_mem_is_address_valid(source));
+ assert(sal_mem_is_address_valid(complement));
+ assert(sal_is_template(sal_mem_get_inst(source)));
+
+ while (
+ sal_mem_is_address_valid(source) &&
+ sal_is_template(sal_mem_get_inst(source))
+ ) {
+ /* Iterate address by address, checking complementarity on each
+ consecutive byte pair.
+ */
+ uint8 inst_src;
+ uint8 inst_comp;
+
+ /* If complement head moves to an invalid address, complementarity
+ fails.
+ */
+ if (!sal_mem_is_address_valid(complement)) {
+ return FALSE;
+ }
+
+ inst_src = sal_mem_get_inst(source);
+ inst_comp = sal_mem_get_inst(complement);
+ assert(inst_src == NOP0 || inst_src == NOP1);
+
+ if (inst_src == NOP0 && inst_comp != NOP1) {
+ return FALSE;
+ }
+
+ if (inst_src == NOP1 && inst_comp != NOP0) {
+ return FALSE;
+ }
+
+ source++;
+ complement++;
+ }
+
+ /* If we get to the end of a template in the source head, and target has
+ been complementary all the way through, we consider these blocks of memory
+ 'complements'.
+ */
+ return TRUE;
+}
+
+static void increment_sp(uint32 pidx, boolean forward)
+{
+ /* Increment or decrement SP to the next valid address. This function gets
+ called by organisms during jumps, searches, etc. (i.e. whenever the seeker
+ pointer gets sent on a 'mission').
+ */
+ assert(g_is_init);
+ assert(pidx < g_capacity);
+ assert(!sal_proc_is_free(pidx));
+
+ if (forward && sal_mem_is_address_valid(g_procs[pidx].sp + 1)) {
+ g_procs[pidx].sp++;
+ }
+
+ if (!forward && sal_mem_is_address_valid(g_procs[pidx].sp - 1)) {
+ g_procs[pidx].sp--;
+ }
+}
+
+static boolean jump_seek(uint32 pidx, boolean forward)
+{
+ /* Search (via the seeker pointer) for template to jump into. This gets
+ called by organisms each cycle during a JMP instruction. Only when a valid
+ template is found, will this function return TRUE. Otherwise it will return
+ FALSE, signaling the calling process that a template has not yet been
+ found.
+ */
+ uint32 next_addr;
+ uint8 next_inst;
+ assert(g_is_init);
+ assert(pidx < g_capacity);
+ assert(!sal_proc_is_free(pidx));
+ next_addr = g_procs[pidx].ip + 1;
+
+ /* This function causes a 'fault' when there is no template right in front
+ of the caller organism's instruction pointer.
+ */
+ if (!sal_mem_is_address_valid(next_addr)) {
+ on_fault(pidx);
+ increment_ip(pidx);
+ return FALSE;
+ }
+
+ next_inst = sal_mem_get_inst(next_addr);
+
+ if (!sal_is_template(next_inst)) {
+ on_fault(pidx);
+ increment_ip(pidx);
+ return FALSE;
+ }
+
+ /* Check for complementarity. Increment seeker pointer if template has not
+ been found yet.
+ */
+ if (are_templates_complements(next_addr, g_procs[pidx].sp)) {
+ return TRUE;
+ }
+
+ increment_sp(pidx, forward);
+ return FALSE;
+}
+
+static void jump(uint32 pidx)
+{
+ /* This gets called when an organism has finally found a template to jump
+ into (see function above). Only when in debug mode, we make sure that the
+ entire jump operation has been performed in a valid way.
+ */
+ #ifndef NDEBUG
+ uint32 next_addr;
+ uint8 next_inst;
+ uint8 sp_inst;
+ assert(g_is_init);
+ assert(pidx < g_capacity);
+ assert(!sal_proc_is_free(pidx));
+ next_addr = g_procs[pidx].ip + 1;
+ assert(sal_mem_is_address_valid(next_addr));
+ next_inst = sal_mem_get_inst(next_addr);
+ sp_inst = sal_mem_get_inst(g_procs[pidx].sp);
+ assert(sal_is_template(next_inst));
+ assert(sal_is_template(sp_inst));
+ assert(are_templates_complements(next_addr, g_procs[pidx].sp));
+ #endif
+
+ g_procs[pidx].ip = g_procs[pidx].sp;
+}
+
+static boolean addr_seek(uint32 pidx, boolean forward)
+{
+ /* Search (via the seeker pointer) for template address in memory. This
+ gets called by organisms each cycle during a ADR instruction. Only when a
+ valid template is found, will this function return TRUE. Otherwise it will
+ return FALSE, signaling the calling process that a template has not yet
+ been found. */
+ uint32 next1_addr;
+ uint32 next2_addr;
+ uint8 next1_inst;
+ uint8 next2_inst;
+ assert(g_is_init);
+ assert(pidx < g_capacity);
+ assert(!sal_proc_is_free(pidx));
+ next1_addr = g_procs[pidx].ip + 1;
+ next2_addr = g_procs[pidx].ip + 2;
+
+ /* This function causes a 'fault' when there is no register modifier right
+ in front of the caller organism's instruction pointer, and a template just
+ after that.
+ */
+ if (
+ !sal_mem_is_address_valid(next1_addr) ||
+ !sal_mem_is_address_valid(next2_addr)
+ ) {
+ on_fault(pidx);
+ increment_ip(pidx);
+ return FALSE;
+ }
+
+ next1_inst = sal_mem_get_inst(next1_addr);
+ next2_inst = sal_mem_get_inst(next2_addr);
+
+ if (
+ !sal_is_mod(next1_inst) ||
+ !sal_is_template(next2_inst)
+ ) {
+ on_fault(pidx);
+ increment_ip(pidx);
+ return FALSE;
+ }
+
+ /* Check for complementarity. Increment seeker pointer if template has not
+ been found yet.
+ */
+ if (are_templates_complements(next2_addr, g_procs[pidx].sp)) {
+ return TRUE;
+ }
+
+ increment_sp(pidx, forward);
+ return FALSE;
+}
+
+static boolean get_register_pointers(
+ uint32 pidx, uint32_p *regs, uint32 reg_count
+) {
+ /* This function is used to get pointers to a calling organism registers.
+ Specifically, registers returned are those that will be used when executing
+ the caller organism's current instruction.
+ */
+ uint32 ridx;
+ assert(g_is_init);
+ assert(pidx < g_capacity);
+ assert(!sal_proc_is_free(pidx));
+ assert(regs);
+ assert(reg_count);
+ assert(reg_count < 4);
+
+ /* Iterate 'reg_count' number of instructions forward from the IP, noting
+ down all found register modifiers. If less than 'reg_count' modifiers are
+ found, this function returns FALSE (triggering a 'fault').
+ */
+ for (ridx = 0; ridx < reg_count; ridx++) {
+ uint32 mod_addr = g_procs[pidx].ip + 1 + ridx;
+
+ if (
+ !sal_mem_is_address_valid(mod_addr) ||
+ !sal_is_mod(sal_mem_get_inst(mod_addr))
+ ) {
+ return FALSE;
+ }
+
+ switch (sal_mem_get_inst(mod_addr)) {
+ case MODA:
+ regs[ridx] = &g_procs[pidx].rax;
+ break;
+ case MODB:
+ regs[ridx] = &g_procs[pidx].rbx;
+ break;
+ case MODC:
+ regs[ridx] = &g_procs[pidx].rcx;
+ break;
+ case MODD:
+ regs[ridx] = &g_procs[pidx].rdx;
+ break;
+ }
+ }
+
+ return TRUE;
+}
+
+static void addr(uint32 pidx)
+{
+ /* This gets called when an organism has finally found a template and is
+ ready to store its address. Only when in debug mode, we make sure that the
+ entire search operation has been performed in a valid way.
+ */
+ uint32_p reg;
+
+ #ifndef NDEBUG
+ uint32 next2_addr;
+ uint8 next2_inst;
+ uint8 sp_inst;
+ assert(g_is_init);
+ assert(pidx < g_capacity);
+ assert(!sal_proc_is_free(pidx));
+ next2_addr = g_procs[pidx].ip + 2;
+ assert(sal_mem_is_address_valid(next2_addr));
+ next2_inst = sal_mem_get_inst(next2_addr);
+ sp_inst = sal_mem_get_inst(g_procs[pidx].sp);
+ assert(sal_is_template(next2_inst));
+ assert(sal_is_template(sp_inst));
+ assert(are_templates_complements(next2_addr, g_procs[pidx].sp));
+ #endif
+
+ /* Store address of complement into the given register.
+ */
+ if (!get_register_pointers(pidx, &reg, 1)) {
+ on_fault(pidx);
+ increment_ip(pidx);
+ return;
+ }
+
+ *reg = g_procs[pidx].sp;
+ increment_ip(pidx);
+}
+
+static void free_child_block_of(uint32 pidx)
+{
+ /* Free only the 'child' memory block (mb2) of the caller organism.
+ */
+ assert(g_is_init);
+ assert(pidx < g_capacity);
+ assert(!sal_proc_is_free(pidx));
+ assert(g_procs[pidx].mb2s);
+ free_memory_block(g_procs[pidx].mb2a, g_procs[pidx].mb2s);
+ g_procs[pidx].mb2a = 0;
+ g_procs[pidx].mb2s = 0;
+}
+
+static void alloc(uint32 pidx, boolean forward)
+{
+ /* Allocate a 'child' memory block of size stored in the first given
+ register, and save its address into the second given register. This
+ function is the basis of Salisian reproduction. It's a fairly complicated
+ function (as the seeker pointer must function in a procedural way), so it's
+ divided into a series of steps, documented below.
+ */
+ uint32_p regs[2];
+ uint32 block_size;
+ assert(g_is_init);
+ assert(pidx < g_capacity);
+ assert(!sal_proc_is_free(pidx));
+
+ /* For this function to work, we need at least two register modifiers.
+ Then, we check for all possible error conditions. If any error conditions
+ are found, the instruction faults and returns.
+ */
+ if (!get_register_pointers(pidx, regs, 2)) {
+ on_fault(pidx);
+ increment_ip(pidx);
+ return;
+ }
+
+ block_size = *regs[0];
+
+ /* ERROR 1: requested child block is of size zero.
+ */
+ if (!block_size) {
+ on_fault(pidx);
+ increment_ip(pidx);
+ return;
+ }
+
+ /* ERROR 2: seeker pointer not adjacent to existing child block.
+ */
+ if (g_procs[pidx].mb2s) {
+ uint32 exp_addr;
+
+ if (forward) {
+ exp_addr = g_procs[pidx].mb2a + g_procs[pidx].mb2s;
+ } else {
+ exp_addr = g_procs[pidx].mb2a - 1;
+ }
+
+ if (g_procs[pidx].sp != exp_addr) {
+ on_fault(pidx);
+ increment_ip(pidx);
+ return;
+ }
+ }
+
+ /* No errors were detected. We thus handle all correct conditions.
+ * CONDITION 1: allocation was successful.
+ */
+ if (g_procs[pidx].mb2s == block_size) {
+ increment_ip(pidx);
+ *regs[1] = g_procs[pidx].mb2a;
+ return;
+ }
+
+ /* CONDITION 2: seeker pointer has collided with allocated space. We free
+ child memory block and just continue searching.
+ */
+ if (sal_mem_is_allocated(g_procs[pidx].sp)) {
+ if (g_procs[pidx].mb2s) {
+ free_child_block_of(pidx);
+ }
+
+ increment_sp(pidx, forward);
+ return;
+ }
+
+ /* CONDITION 3: no collision detected; enlarge child memory block and
+ increment seeker pointer. Also, correct position of BLOCK_START bit flag.
+ */
+ _sal_mem_set_allocated(g_procs[pidx].sp);
+
+ if (!g_procs[pidx].mb2s) {
+ g_procs[pidx].mb2a = g_procs[pidx].sp;
+ _sal_mem_set_block_start(g_procs[pidx].sp);
+ } else if (!forward) {
+ _sal_mem_unset_block_start(g_procs[pidx].mb2a);
+ g_procs[pidx].mb2a = g_procs[pidx].sp;
+ _sal_mem_set_block_start(g_procs[pidx].mb2a);
+ }
+
+ g_procs[pidx].mb2s++;
+ increment_sp(pidx, forward);
+}
+
+static void swap(uint32 pidx)
+{
+ /* Swap parent and child memory blocks. This function is the basis of
+ Salisian metabolism.
+ */
+ assert(g_is_init);
+ assert(pidx < g_capacity);
+ assert(!sal_proc_is_free(pidx));
+
+ if (g_procs[pidx].mb2s) {
+ uint32 addr_temp = g_procs[pidx].mb1a;
+ uint32 size_temp = g_procs[pidx].mb1s;
+ g_procs[pidx].mb1a = g_procs[pidx].mb2a;
+ g_procs[pidx].mb1s = g_procs[pidx].mb2s;
+ g_procs[pidx].mb2a = addr_temp;
+ g_procs[pidx].mb2s = size_temp;
+ } else {
+ on_fault(pidx);
+ }
+
+ increment_ip(pidx);
+}
+
+static void split(uint32 pidx)
+{
+ /* Split child memory block into a new organism. A new baby is born. :-)
+ */
+ assert(g_is_init);
+ assert(pidx < g_capacity);
+ assert(!sal_proc_is_free(pidx));
+
+ if (g_procs[pidx].mb2s) {
+ proc_create(
+ g_procs[pidx].mb2a, g_procs[pidx].mb2s, pidx, FALSE, FALSE
+ );
+ g_procs[pidx].mb2a = 0;
+ g_procs[pidx].mb2s = 0;
+ } else {
+ on_fault(pidx);
+ }
+
+ increment_ip(pidx);
+}
+
+static void one_reg_op(uint32 pidx, uint8 inst)
+{
+ /* Here we group all 1-register operations. These include incrementing,
+ decrementing, placing zero or one on a register, and the negation
+ operation.
+ */
+ uint32_p reg;
+ assert(g_is_init);
+ assert(pidx < g_capacity);
+ assert(!sal_proc_is_free(pidx));
+ assert(sal_is_inst(inst));
+
+ if (!get_register_pointers(pidx, &reg, 1)) {
+ on_fault(pidx);
+ increment_ip(pidx);
+ return;
+ }
+
+ switch (inst) {
+ case INCN:
+ (*reg)++;
+ break;
+ case DECN:
+ (*reg)--;
+ break;
+ case ZERO:
+ (*reg) = 0;
+ break;
+ case UNIT:
+ (*reg) = 1;
+ break;
+ case NOTN:
+ (*reg) = !(*reg);
+ break;
+ default:
+ assert(FALSE);
+ }
+
+ increment_ip(pidx);
+}
+
+static void if_not_zero(uint32 pidx)
+{
+ /* Conditional operator. Like in most programming languages, this
+ instruction is needed to allow organism execution to branch into different
+ execution streams.
+ */
+ uint32_p reg;
+ assert(g_is_init);
+ assert(pidx < g_capacity);
+ assert(!sal_proc_is_free(pidx));
+
+ if (!get_register_pointers(pidx, &reg, 1)) {
+ on_fault(pidx);
+ increment_ip(pidx);
+ return;
+ }
+
+ if (!(*reg)) {
+ increment_ip(pidx);
+ }
+
+ increment_ip(pidx);
+ increment_ip(pidx);
+}
+
+static void three_reg_op(uint32 pidx, uint8 inst)
+{
+ /* Here we group all 3-register arithmetic operations. These include
+ addition, subtraction, multiplication and division.
+ */
+ uint32_p regs[3];
+ assert(g_is_init);
+ assert(pidx < g_capacity);
+ assert(!sal_proc_is_free(pidx));
+ assert(sal_is_inst(inst));
+
+ if (!get_register_pointers(pidx, regs, 3)) {
+ on_fault(pidx);
+ increment_ip(pidx);
+ return;
+ }
+
+ switch (inst) {
+ case SUMN:
+ *regs[0] = *regs[1] + *regs[2];
+ break;
+ case SUBN:
+ *regs[0] = *regs[1] - *regs[2];
+ break;
+ case MULN:
+ *regs[0] = *regs[1] * *regs[2];
+ break;
+ case DIVN:
+ /* Division by 0 is not allowed and causes a fault. */
+ if (!(*regs[2])) {
+ on_fault(pidx);
+ increment_ip(pidx);
+ return;
+ }
+
+ *regs[0] = *regs[1] / *regs[2];
+ break;
+ default:
+ assert(FALSE);
+ }
+
+ increment_ip(pidx);
+}
+
+static void load(uint32 pidx)
+{
+ /* Load an instruction from a given address into a specified register. This
+ is used by organisms during their reproduction cycle.
+ */
+ uint32_p regs[2];
+ assert(g_is_init);
+ assert(pidx < g_capacity);
+ assert(!sal_proc_is_free(pidx));
+
+ if (
+ !get_register_pointers(pidx, regs, 2) ||
+ !sal_mem_is_address_valid(*regs[0])
+ ) {
+ on_fault(pidx);
+ increment_ip(pidx);
+ return;
+ }
+
+ if (g_procs[pidx].sp < *regs[0]) {
+ increment_sp(pidx, TRUE);
+ } else if (g_procs[pidx].sp > *regs[0]) {
+ increment_sp(pidx, FALSE);
+ } else {
+ *regs[1] = sal_mem_get_inst(*regs[0]);
+ increment_ip(pidx);
+ }
+}
+
+static boolean is_writeable_by(uint32 pidx, uint32 address)
+{
+ /* Check whether an organisms has writing rights on a specified address.
+ Any organism may write to any valid address that is either self owned or
+ not allocated.
+ */
+ assert(g_is_init);
+ assert(pidx < g_capacity);
+ assert(!sal_proc_is_free(pidx));
+ assert(sal_mem_is_address_valid(address));
+
+ if (!sal_mem_is_allocated(address)) {
+ return TRUE;
+ } else {
+ uint32 lo1 = g_procs[pidx].mb1a;
+ uint32 lo2 = g_procs[pidx].mb2a;
+ uint32 hi1 = lo1 + g_procs[pidx].mb1s;
+ uint32 hi2 = lo2 + g_procs[pidx].mb2s;
+ return (
+ (address >= lo1 && address < hi1) ||
+ (address >= lo2 && address < hi2)
+ );
+ }
+}
+
+static void write(uint32 pidx)
+{
+ /* Write instruction on a given register into a specified address. This is
+ used by organisms during their reproduction cycle.
+ */
+ uint32_p regs[2];
+ assert(g_is_init);
+ assert(pidx < g_capacity);
+ assert(!sal_proc_is_free(pidx));
+
+ if (
+ !get_register_pointers(pidx, regs, 2) ||
+ !sal_mem_is_address_valid(*regs[0]) ||
+ !sal_is_inst(*regs[1])
+ ) {
+ on_fault(pidx);
+ increment_ip(pidx);
+ return;
+ }
+
+ if (g_procs[pidx].sp < *regs[0]) {
+ increment_sp(pidx, TRUE);
+ } else if (g_procs[pidx].sp > *regs[0]) {
+ increment_sp(pidx, FALSE);
+ } else if (is_writeable_by(pidx, *regs[0])) {
+ sal_mem_set_inst(*regs[0], *regs[1]);
+ increment_ip(pidx);
+ } else {
+ on_fault(pidx);
+ increment_ip(pidx);
+ }
+}
+
+static void send(uint32 pidx)
+{
+ /* Send instruction on given register into the common pipe.
+ */
+ uint32_p reg;
+ assert(g_is_init);
+ assert(pidx < g_capacity);
+ assert(!sal_proc_is_free(pidx));
+
+ if (!get_register_pointers(pidx, &reg, 1)) {
+ on_fault(pidx);
+ increment_ip(pidx);
+ return;
+ }
+
+ if (!sal_is_inst(*reg)) {
+ on_fault(pidx);
+ increment_ip(pidx);
+ return;
+ }
+
+ _sal_comm_send((uint8)(*reg));
+ increment_ip(pidx);
+}
+
+static void receive(uint32 pidx)
+{
+ /* Receive a single instruction from the common pipe and store it into a
+ specified register. In case the common pipe is empty, it will return the
+ NOP0 instruction.
+ */
+ uint32_p reg;
+ assert(g_is_init);
+ assert(pidx < g_capacity);
+ assert(!sal_proc_is_free(pidx));
+
+ if (!get_register_pointers(pidx, &reg, 1)) {
+ on_fault(pidx);
+ increment_ip(pidx);
+ return;
+ }
+
+ *reg = _sal_comm_receive();
+ assert(sal_is_inst(*reg));
+ increment_ip(pidx);
+}
+
+static void push(uint32 pidx)
+{
+ /* Push value on register into the stack. This is useful as a secondary
+ memory resource.
+ */
+ uint32_p reg;
+ uint32 sidx;
+ assert(g_is_init);
+ assert(pidx < g_capacity);
+ assert(!sal_proc_is_free(pidx));
+
+ if (!get_register_pointers(pidx, &reg, 1)) {
+ on_fault(pidx);
+ increment_ip(pidx);
+ return;
+ }
+
+ for (sidx = 7; sidx; sidx--) {
+ g_procs[pidx].stack[sidx] = g_procs[pidx].stack[sidx - 1];
+ }
+
+ g_procs[pidx].stack[0] = *reg;
+ increment_ip(pidx);
+}
+
+static void
+pop(uint32 pidx)
+{
+ /* Pop value from the stack into a given register.
+ */
+ uint32_p reg;
+ uint32 sidx;
+ assert(g_is_init);
+ assert(pidx < g_capacity);
+ assert(!sal_proc_is_free(pidx));
+
+ if (!get_register_pointers(pidx, &reg, 1)) {
+ on_fault(pidx);
+ increment_ip(pidx);
+ return;
+ }
+
+ *reg = g_procs[pidx].stack[0];
+
+ for (sidx = 1; sidx < 8; sidx++) {
+ g_procs[pidx].stack[sidx - 1] = g_procs[pidx].stack[sidx];
+ }
+
+ g_procs[pidx].stack[7] = 0;
+ increment_ip(pidx);
+}
+
+static boolean eat_seek(uint32 pidx, boolean forward)
+{
+ /* Search (via the seeker pointer) for an identical copy of the memory
+ stream right in front of the calling organism's IP. This function gets
+ called by organisms each cycle during an EAT instruction. Only when a valid
+ copy is found, this function will return TRUE. */
+ uint32 next_addr;
+ uint8 next_inst;
+ uint8 sp_inst;
+ assert(g_is_init);
+ assert(pidx < g_capacity);
+ assert(!sal_proc_is_free(pidx));
+ next_addr = g_procs[pidx].ip + 1;
+
+ if (!sal_mem_is_address_valid(next_addr)) {
+ on_fault(pidx);
+ increment_ip(pidx);
+ return FALSE;
+ }
+
+ if (g_procs[pidx].sp == next_addr) {
+ increment_sp(pidx, forward);
+ return FALSE;
+ }
+
+ next_inst = sal_mem_get_inst(next_addr);
+ sp_inst = sal_mem_get_inst(g_procs[pidx].sp);
+
+ if (next_inst == sp_inst) {
+ return TRUE;
+ }
+
+ increment_sp(pidx, forward);
+ return FALSE;
+}
+
+static void eat(uint32 pidx)
+{
+ /* Salisian organisms may 'eat' information. They eat by searching for
+ 'copies' of the code in front of their IPs during the EAT instruction. When
+ a valid copy is found, an organism gets rewarded by setting their 'reward'
+ field to the length of the measured copy. Each cycle, organisms execute
+ 'reward' number of instructions plus one, thus, eating a larger stream
+ produces a larger advantage for an organism.
+
+ However, whenever an organism eats, the detected copy of the source code
+ gets destroyed (randomized). The main idea of the EAT instruction is to
+ turn 'information' into a valuable resource in Salis.
+ */
+ uint32 source;
+ uint32 target;
+ assert(g_is_init);
+ assert(pidx < g_capacity);
+ assert(!sal_proc_is_free(pidx));
+ source = g_procs[pidx].ip + 1;
+ target = g_procs[pidx].sp;
+ assert(sal_mem_is_address_valid(source));
+ assert(sal_mem_get_inst(source) == sal_mem_get_inst(target));
+ g_procs[pidx].reward = 0;
+
+ while (
+ sal_mem_is_address_valid(source) &&
+ sal_mem_is_address_valid(target) &&
+ sal_mem_get_inst(source) == sal_mem_get_inst(target)
+ ) {
+ g_procs[pidx].reward++;
+ _sal_evo_randomize_at(target);
+ source++;
+ target++;
+ }
+
+ increment_ip(pidx);
+}
+
+static void proc_cycle(uint32 pidx)
+{
+ /* Cycle a process once. During each process cycle, several things may
+ happen. For example, if a process is being punished (for committing a
+ fault), it will have to wait until the next simulation cycle to be able to
+ execute.
+
+ Non-punished organisms execute at least one instruction per simulation
+ cycle. If they are being rewarded, they execute one, plus the number on
+ their 'reward' field, number of instructions each cycle.
+ */
+ uint32 cycles;
+ assert(g_is_init);
+ assert(pidx < g_capacity);
+ assert(!sal_proc_is_free(pidx));
+
+ /* Organism is being punished. Clear its 'punish' field and return without
+ executing.
+ */
+ if (g_procs[pidx].punish) {
+ g_procs[pidx].punish = 0;
+ return;
+ }
+
+ /* Execute one instruction per number of 'reward' points awarded to this
+ organism. Switch case associates each instruction to its corresponding
+ instruction handler. Process module keeps track of the total number of
+ instructions executed (by all organisms) per simulation cycle.
+ */
+ for (cycles = 0; cycles < g_procs[pidx].reward + 1; cycles++) {
+ uint8 inst = sal_mem_get_inst(g_procs[pidx].ip);
+ g_instructions_executed++;
+
+ switch (inst) {
+ case JMPB:
+ if (jump_seek(pidx, FALSE)) jump(pidx);
+ break;
+ case JMPF:
+ if (jump_seek(pidx, TRUE)) jump(pidx);
+ break;
+ case ADRB:
+ if (addr_seek(pidx, FALSE)) addr(pidx);
+ break;
+ case ADRF:
+ if (addr_seek(pidx, TRUE)) addr(pidx);
+ break;
+ case MALB:
+ alloc(pidx, FALSE);
+ break;
+ case MALF:
+ alloc(pidx, TRUE);
+ break;
+ case SWAP:
+ swap(pidx);
+ break;
+ case SPLT:
+ split(pidx);
+ break;
+ case INCN:
+ case DECN:
+ case ZERO:
+ case UNIT:
+ case NOTN:
+ one_reg_op(pidx, inst);
+ break;
+ case IFNZ:
+ if_not_zero(pidx);
+ break;
+ case SUMN:
+ case SUBN:
+ case MULN:
+ case DIVN:
+ three_reg_op(pidx, inst);
+ break;
+ case LOAD:
+ load(pidx);
+ break;
+ case WRTE:
+ write(pidx);
+ break;
+ case SEND:
+ send(pidx);
+ break;
+ case RECV:
+ receive(pidx);
+ break;
+ case PSHN:
+ push(pidx);
+ break;
+ case POPN:
+ pop(pidx);
+ break;
+ case EATB:
+ if (eat_seek(pidx, FALSE)) eat(pidx);
+ break;
+ case EATF:
+ if (eat_seek(pidx, TRUE)) eat(pidx);
+ break;
+ default:
+ increment_ip(pidx);
+ }
+ }
+}
+
+void _sal_proc_cycle(void)
+{
+ /* The process module cycle consists of a series of steps, which are needed
+ to preserve overall correctness.
+ */
+ assert(g_is_init);
+ assert(module_is_valid());
+ g_instructions_executed = 0;
+
+ /* Iterate through all organisms in the reaper queue. First organism to
+ execute is the one pointed to by 'g_last' (the one on top of the queue).
+ Last one to execute is 'g_first'. We go around the circular queue, making
+ sure to modulo (%) around when iterator goes below zero.
+ */
+ if (g_count) {
+ uint32 pidx = g_last;
+
+ /* Turn off all IP flags in memory and cycle 'g_last'. Then, continue
+ with all other organisms until we reach 'g_first'.
+ */
+ toggle_ip_flag(_sal_mem_unset_ip);
+ assert(!sal_mem_get_ip_count());
+ proc_cycle(pidx);
+
+ while (pidx != g_first) {
+ pidx--;
+ pidx %= g_capacity;
+ proc_cycle(pidx);
+ }
+
+ /* Kill oldest processes whenever memory gets filled over capacity.
+ */
+ while (sal_mem_get_allocated_count() > sal_mem_get_capacity()) {
+ proc_kill(FALSE);
+ }
+
+ /* Finally, turn IP flags back on. Keep in mind that IP flags exist
+ for visualization purposes only. They are actually not really needed.
+ */
+ toggle_ip_flag(_sal_mem_set_ip);
+ }
+}
diff --git a/src/salis.c b/src/salis.c
new file mode 100644
index 0000000..1aae1fa
--- /dev/null
+++ b/src/salis.c
@@ -0,0 +1,109 @@
+#include <assert.h>
+#include <stdio.h>
+#include "getter.h"
+#include "salis.h"
+
+static boolean g_is_init;
+static uint32 g_cycle;
+static uint32 g_epoch;
+
+void sal_main_init(uint32 order, string pipe)
+{
+ /* Initialize all Salis modules to their initial states. We pass along any
+ arguments to their respective modules.
+ */
+ assert(!g_is_init);
+ _sal_mem_init(order);
+ _sal_comm_init(pipe);
+ _sal_evo_init();
+ _sal_proc_init();
+ g_is_init = TRUE;
+}
+
+void sal_main_quit(void)
+{
+ /* Reset Salis and all of its modules back to zero. We may, thus, shutdown
+ Salis and re-initialize it with different parameters without having to
+ reload the library (useful, for example, when running data gathering
+ scripts that must iterate through many save files).
+ */
+ assert(g_is_init);
+ _sal_proc_quit();
+ _sal_evo_quit();
+ _sal_comm_quit();
+ _sal_mem_quit();
+ g_is_init = FALSE;
+ g_cycle = 0;
+ g_epoch = 0;
+}
+
+void sal_main_load(string file_name, string pipe)
+{
+ /* Load simulation state from file. This file must have been created by
+ 'sal_main_save()'. File name of common pipe must also be provided.
+ */
+ FILE *file;
+ assert(!g_is_init);
+ assert(file_name);
+ file = fopen(file_name, "rb");
+ assert(file);
+ fread(&g_is_init, sizeof(boolean), 1, file);
+ fread(&g_cycle, sizeof(uint32), 1, file);
+ fread(&g_epoch, sizeof(uint32), 1, file);
+ _sal_mem_load_from(file);
+ _sal_evo_load_from(file);
+ _sal_proc_load_from(file);
+ fclose(file);
+ _sal_comm_init(pipe);
+}
+
+void sal_main_save(string file_name)
+{
+ /* Save simulation state to a file. This file may later be re-loaded with
+ 'sal_main_load()'. We save in binary format (to save space), which means
+ save files might not be entirely portable.
+ */
+ FILE *file;
+ assert(g_is_init);
+ assert(file_name);
+ file = fopen(file_name, "wb");
+ assert(file);
+ fwrite(&g_is_init, sizeof(boolean), 1, file);
+ fwrite(&g_cycle, sizeof(uint32), 1, file);
+ fwrite(&g_epoch, sizeof(uint32), 1, file);
+ _sal_mem_save_into(file);
+ _sal_evo_save_into(file);
+ _sal_proc_save_into(file);
+ fclose(file);
+}
+
+boolean sal_main_is_init(void)
+{
+ /* Check if Salis is currently initialized/running.
+ */
+ return g_is_init;
+}
+
+/* Getter methods for the Salis main module.
+*/
+UINT32_GETTER(main, cycle)
+UINT32_GETTER(main, epoch)
+
+void sal_main_cycle(void)
+{
+ /* Cycle the Salis simulator once. The combination of a cycle * epoch
+ counter allows us to track simulations for an insane period of time
+ (2^64 cycles).
+ */
+ g_cycle++;
+
+ if (!g_cycle) {
+ g_epoch++;
+ }
+
+ /* Cycle all of the Salis modules.
+ */
+ _sal_mem_cycle();
+ _sal_evo_cycle();
+ _sal_proc_cycle();
+}