diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/common.c | 72 | ||||
| -rw-r--r-- | src/evolver.c | 132 | ||||
| -rw-r--r-- | src/instset.c | 39 | ||||
| -rw-r--r-- | src/memory.c | 325 | ||||
| -rw-r--r-- | src/process.c | 1488 | ||||
| -rw-r--r-- | src/salis.c | 109 |
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, ®, 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, ®, 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, ®, 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, ®, 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, ®, 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, ®, 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, ®, 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(); +} |