diff options
| -rw-r--r-- | .gitignore | 2 | ||||
| -rw-r--r-- | include/lib94/lib94.hpp | 88 | ||||
| -rw-r--r-- | lib94/core.cpp | 294 | ||||
| -rw-r--r-- | lib94/executors.cpp | 332 | ||||
| -rw-r--r-- | lib94/warrior.cpp | 476 | ||||
| -rw-r--r-- | test/build.sh | 1 | ||||
| -rw-r--r-- | test/dwarf.rc | 10 | ||||
| -rw-r--r-- | test/imp.rc | 4 | ||||
| -rw-r--r-- | test/test.cpp | 85 |
9 files changed, 1292 insertions, 0 deletions
diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..5e3dd03 --- /dev/null +++ b/.gitignore @@ -0,0 +1,2 @@ +.vscode/ +test/test diff --git a/include/lib94/lib94.hpp b/include/lib94/lib94.hpp new file mode 100644 index 0000000..1d061ec --- /dev/null +++ b/include/lib94/lib94.hpp @@ -0,0 +1,88 @@ +#ifndef LIB94_HPP +#define LIB94_HPP + +#include <filesystem> +#include <optional> +#include <variant> +#include <string> +#include <random> +#include <vector> +#include <queue> +#include <set> + +#ifndef CORE_SIZE +#define CORE_SIZE 8000 +#endif + +typedef uint32_t number_t; + +enum opcode : uint8_t { + DAT, MOV, ADD, SUB, + MUL, DIV, MOD, JMP, + JMZ, JMN, DJN, SEQ, + SNE, SLT, SPL, NOP +}; + +enum modifier : uint8_t { + A, B, AB, BA, + F, X, I +}; + +enum mode : uint8_t { + IMMEDIATE, DIRECT, + A_INDIRECT, B_INDIRECT, + A_DECREMENT, B_DECREMENT, + A_INCREMENT, B_INCREMENT +}; + +struct instruction { + opcode op; + modifier mod; + mode amode; + mode bmode; + number_t anumber; + number_t bnumber; +}; + +struct warrior { + std::string name; + std::string author; + + number_t org; + + std::vector<instruction> instructions; +}; + +void seed_prng(uint_fast64_t seed); + +std::variant<warrior *, std::string> compile_warrior(std::string source); +bool save_warrior(const warrior &w, const std::filesystem::path &to); +std::optional<warrior *> load_warrior(const std::filesystem::path &from); + +void clear_core(const instruction &background); +void clear_core_random(); + +//warrior pointers need to remain valid for other +//functions to return valid things during the round +bool init_round(const std::vector<const warrior *> &warriors); + +size_t alive_warrior_count(); + +//asserts that there is a next warrior +const warrior *get_next_warrior(); +const std::queue<number_t> &get_processes(const warrior *for_warrior); +//asserts that there is a next process +number_t get_next_process(const warrior *for_warrior); + +const std::set<number_t> &get_modified_addresses(); +void clear_modified_addresses(); + +const instruction &get_instruction(number_t address); + +//asserts that there is a next warrior +void single_step(); + +const warrior *run_until_warrior_death(); +const warrior *run_until_winner(); + +#endif diff --git a/lib94/core.cpp b/lib94/core.cpp new file mode 100644 index 0000000..4cbd098 --- /dev/null +++ b/lib94/core.cpp @@ -0,0 +1,294 @@ +#include <lib94/lib94.hpp> +#include <functional> +#include <cassert> +#include <random> +#include <queue> +#include <set> + +static std::mt19937_64 prng; +instruction core[CORE_SIZE]; + +void seed_prng(uint_fast64_t seed) { + prng.seed(seed); +} + +void clear_core(const instruction &background) { + for (instruction &i : core) + i = background; +} + +void clear_core_random() { + std::uniform_int_distribution<uint8_t> op(0, 15); + std::uniform_int_distribution<uint8_t> mod(0, 6); + std::uniform_int_distribution<uint8_t> modes(0, 7); + std::uniform_int_distribution<number_t> number(0, CORE_SIZE - 1); + + for (instruction &i : core) + i = { + .op = (opcode)op(prng), + .mod = (modifier)mod(prng), + .amode = (mode)modes(prng), + .bmode = (mode)modes(prng), + .anumber = number(prng), + .bnumber = number(prng) + }; +} + +static std::set<number_t> modified_addresses; + +struct warrior_info { + const warrior *the_warrior; + std::queue<number_t> processes; +}; + +static std::vector<warrior_info> warrior_infos; +std::queue<warrior_info *> alive_warriors; + +bool init_round(const std::vector<const warrior *> &warriors) { + modified_addresses.clear(); + warrior_infos.clear(); + alive_warriors = std::queue<warrior_info *>(); + + std::uniform_int_distribution<number_t> number(0, CORE_SIZE - 1); + std::vector<std::pair<number_t, number_t>> placements; + + for (const warrior *w : warriors) { + unsigned tries = 0; + + new_place_at: + if (tries > 1000) + return false; + ++tries; + + number_t place_at = number(prng); + + for (std::pair<number_t, number_t> &other : placements) + //there has to be a better way + for (number_t i = 0; i < w->instructions.size(); ++i) + if (((place_at + i) % CORE_SIZE >= other.first && (place_at + i) % CORE_SIZE < other.first + other.second) || + ((place_at + i) % CORE_SIZE + CORE_SIZE >= other.first && (place_at + i) % CORE_SIZE + CORE_SIZE < other.first + other.second)) + goto new_place_at; + + placements.push_back(std::make_pair<>(place_at, w->instructions.size())); + + for (number_t i = 0; i < w->instructions.size(); ++i) + core[(place_at + i) % CORE_SIZE] = w->instructions[i]; + + warrior_infos.push_back({}); + warrior_info *wi = &warrior_infos.back(); + wi->the_warrior = w; + wi->processes.push((place_at + w->org) % CORE_SIZE); + } + + std::shuffle(warrior_infos.begin(), warrior_infos.end(), prng); + + for (warrior_info &wi : warrior_infos) + alive_warriors.push(&wi); + + return true; +} + +size_t alive_warrior_count() { + return alive_warriors.size(); +} + +const warrior *get_next_warrior() { + assert(alive_warriors.size() > 0); + return alive_warriors.front()->the_warrior; +} + +const std::queue<number_t> &get_processes(const warrior *for_warrior) { + for (const warrior_info &wi : warrior_infos) + if (wi.the_warrior == for_warrior) + return wi.processes; + assert(false); +} + +number_t get_next_process(const warrior *for_warrior) { + for (const warrior_info &wi : warrior_infos) + if (wi.the_warrior == for_warrior) { + assert(wi.processes.size() > 0); + return wi.processes.front(); + } + assert(false); +} + +const std::set<number_t> &get_modified_addresses() { + return modified_addresses; +} + +void clear_modified_addresses() { + modified_addresses.clear(); +} + +void add_modified_instruction(const instruction *instr) { + modified_addresses.insert(instr - core); +} + +const instruction &get_instruction(number_t address) { + return core[address]; +} + +static const warrior *single_step_return_dead(); + +void single_step() { + single_step_return_dead(); +} + +const warrior *run_until_warrior_death() { + while (true) { + const warrior *w = single_step_return_dead(); + if (w) + return w; + } +} + +const warrior *run_until_winner() { + while (true) { + const warrior *w = single_step_return_dead(); + if (w && alive_warriors.size() == 1) + for (const warrior_info &wi : warrior_infos) + if (wi.processes.size() > 0) + return wi.the_warrior; + } +} + +number_t program_counter; +static instruction instruction_register; + +static number_t a_pointer, b_pointer; +instruction a_instruction, b_instruction; + +instruction *a_instruction_writable; +instruction *b_instruction_writable; + +static void evaluate_operand(mode m, number_t n, number_t &ptr, instruction &instr) { + instruction *secondary; + + switch (m) { + + case IMMEDIATE: + ptr = 0; + instr = core[program_counter]; + break; + + case DIRECT: + ptr = n; + instr = core[(program_counter + n) % CORE_SIZE]; + break; + + case A_INDIRECT: + secondary = core + (program_counter + n) % CORE_SIZE; + ptr = (n + secondary->anumber) % CORE_SIZE; + instr = core[(program_counter + ptr) % CORE_SIZE]; + break; + + case B_INDIRECT: + secondary = core + (program_counter + n) % CORE_SIZE; + ptr = (n + secondary->bnumber) % CORE_SIZE; + instr = core[(program_counter + ptr) % CORE_SIZE]; + break; + + case A_DECREMENT: + secondary = core + (program_counter + n) % CORE_SIZE; + ptr = (n + --secondary->anumber) % CORE_SIZE; + instr = core[(program_counter + ptr) % CORE_SIZE]; + add_modified_instruction(secondary); + break; + + case B_DECREMENT: + secondary = core + (program_counter + n) % CORE_SIZE; + ptr = (n + --secondary->bnumber) % CORE_SIZE; + instr = core[(program_counter + ptr) % CORE_SIZE]; + add_modified_instruction(secondary); + break; + + case A_INCREMENT: + secondary = core + (program_counter + n) % CORE_SIZE; + ptr = (n + secondary->anumber) % CORE_SIZE; + instr = core[(program_counter + ptr) % CORE_SIZE]; + ++secondary->anumber; + add_modified_instruction(secondary); + break; + + case B_INCREMENT: + secondary = core + (program_counter + n) % CORE_SIZE; + ptr = (n + secondary->bnumber) % CORE_SIZE; + instr = core[(program_counter + ptr) % CORE_SIZE]; + ++secondary->bnumber; + add_modified_instruction(secondary); + break; + + } +} + +template<opcode op, modifier mod> +bool execute(); + +#define EXECUTOR_DECL_LINE(mod) \ + extern template bool execute<DAT, mod>(); extern template bool execute<MOV, mod>(); \ + extern template bool execute<ADD, mod>(); extern template bool execute<SUB, mod>(); \ + extern template bool execute<MUL, mod>(); extern template bool execute<DIV, mod>(); \ + extern template bool execute<MOD, mod>(); extern template bool execute<JMP, mod>(); \ + extern template bool execute<JMZ, mod>(); extern template bool execute<JMN, mod>(); \ + extern template bool execute<DJN, mod>(); extern template bool execute<SEQ, mod>(); \ + extern template bool execute<SNE, mod>(); extern template bool execute<SLT, mod>(); \ + extern template bool execute<SPL, mod>(); extern template bool execute<NOP, mod>(); + +EXECUTOR_DECL_LINE(A) +EXECUTOR_DECL_LINE(B) +EXECUTOR_DECL_LINE(AB) +EXECUTOR_DECL_LINE(BA) +EXECUTOR_DECL_LINE(F) +EXECUTOR_DECL_LINE(X) +EXECUTOR_DECL_LINE(I) + +#define EXECUTOR_REF_LINE(mod) \ + &execute<DAT, mod>, &execute<MOV, mod>, \ + &execute<ADD, mod>, &execute<SUB, mod>, \ + &execute<MUL, mod>, &execute<DIV, mod>, \ + &execute<MOD, mod>, &execute<JMP, mod>, \ + &execute<JMZ, mod>, &execute<JMN, mod>, \ + &execute<DJN, mod>, &execute<SEQ, mod>, \ + &execute<SNE, mod>, &execute<SLT, mod>, \ + &execute<SPL, mod>, &execute<NOP, mod> + +static const std::function<bool ()> executors[] = { + EXECUTOR_REF_LINE(A), EXECUTOR_REF_LINE(B), + EXECUTOR_REF_LINE(AB), EXECUTOR_REF_LINE(BA), + EXECUTOR_REF_LINE(F), EXECUTOR_REF_LINE(X), + EXECUTOR_REF_LINE(I) +}; + +static warrior_info *this_warrior; + +void enqueue_process(number_t pc) { + this_warrior->processes.push(pc); +} + +static const warrior *single_step_return_dead() { + this_warrior = alive_warriors.front(); + alive_warriors.pop(); + + program_counter = this_warrior->processes.front(); + this_warrior->processes.pop(); + + instruction_register = core[program_counter]; + + evaluate_operand(instruction_register.amode, instruction_register.anumber, a_pointer, a_instruction); + evaluate_operand(instruction_register.bmode, instruction_register.bnumber, b_pointer, b_instruction); + + a_instruction_writable = core + (program_counter + a_pointer) % CORE_SIZE; + b_instruction_writable = core + (program_counter + b_pointer) % CORE_SIZE; + + bool enqueue_process = executors[instruction_register.op + instruction_register.mod * 16](); + + if (enqueue_process) + this_warrior->processes.push((program_counter + 1) % CORE_SIZE); + + else if (this_warrior->processes.size() == 0) + return this_warrior->the_warrior; + + alive_warriors.push(this_warrior); + return 0; +} diff --git a/lib94/executors.cpp b/lib94/executors.cpp new file mode 100644 index 0000000..1c66243 --- /dev/null +++ b/lib94/executors.cpp @@ -0,0 +1,332 @@ +#include <lib94/lib94.hpp> +#include <functional> +#include <cassert> + +void enqueue_process(number_t pc); + +extern instruction core[CORE_SIZE]; +extern number_t program_counter; +extern instruction a_instruction, b_instruction; +extern instruction *a_instruction_writable; +extern instruction *b_instruction_writable; + +void add_modified_instruction(const instruction *instr); + +struct single_target { + number_t *ptr; + + inline bool assign(const single_target &left, const single_target &right, + std::function<std::optional<number_t> (number_t, number_t)> f) { + + std::optional<number_t> result = f(*left.ptr, *right.ptr); + if (result.has_value()) { + *ptr = result.value(); + return true; + } + return false; + + } + + inline bool is_zero() { + return *ptr == 0; + } + + inline bool dec_not_zero() { + return --*ptr != 0; + } + + inline bool equal_to(const single_target &other) { + return *ptr == *other.ptr; + } + + inline bool less_than(const single_target &other) { + return *ptr < *other.ptr; + } +}; + +struct pair_target { + number_t *ptr1; + number_t *ptr2; + + inline bool assign(const pair_target &left, const pair_target &right, + std::function<std::optional<number_t> (number_t, number_t)> f) { + bool to_return = true; + + std::optional<number_t> result1 = f(*left.ptr1, *right.ptr1); + if (result1.has_value()) + *ptr1 = result1.value(); + else + to_return = false; + + std::optional<number_t> result2 = f(*left.ptr2, *right.ptr2); + if (result2.has_value()) + *ptr2 = result2.value(); + else + to_return = false; + + return to_return; + + } + + inline bool is_zero() { + return *ptr1 == 0 && *ptr2 == 0; + } + + inline bool dec_not_zero() { + --*ptr1; + --*ptr2; + return *ptr1 != 0 || *ptr2 != 0; + } + + inline bool equal_to(const pair_target &other) { + return *ptr1 == *other.ptr1 && + *ptr2 == *other.ptr2; + } + + inline bool less_than(const pair_target &other) { + return *ptr1 < *other.ptr1 && + *ptr2 < *other.ptr2; + } +}; + +struct instruction_target { + instruction *instr; + + inline bool assign(const instruction_target &left, const instruction_target &right, + std::function<std::optional<number_t> (number_t, number_t)> f) { + bool to_return = true; + + std::optional<number_t> result1 = f(left.instr->anumber, right.instr->anumber); + if (result1.has_value()) + instr->anumber = result1.value(); + else + to_return = false; + + std::optional<number_t> result2 = f(left.instr->bnumber, right.instr->bnumber); + if (result2.has_value()) + instr->bnumber = result2.value(); + else + to_return = false; + + return to_return; + + } + + inline bool is_zero() { + return instr->anumber == 0 && instr->bnumber == 0; + } + + inline bool dec_not_zero() { + --instr->anumber; + --instr->bnumber; + return instr->anumber != 0 || instr->bnumber != 0; + } + + inline bool equal_to(const instruction_target &other) { + return instr->op == other.instr->op && + instr->mod == other.instr->mod && + instr->amode == other.instr->amode && + instr->anumber == other.instr->anumber && + instr->bmode == other.instr->bmode && + instr->bnumber == other.instr->bnumber; + } + + inline bool less_than(const instruction_target &other) { + return instr->anumber < other.instr->anumber && + instr->bnumber < other.instr->bnumber; + } +}; + +template<modifier mod> +struct target; + +template<> struct target<A> : single_target {}; +template<> struct target<B> : single_target {}; +template<> struct target<AB> : single_target {}; +template<> struct target<BA> : single_target {}; +template<> struct target<F> : pair_target {}; +template<> struct target<X> : pair_target {}; +template<> struct target<I> : instruction_target {}; + +template<opcode op, modifier mod> +bool execute() { + target<mod> dest_out; + target<mod> dest_in; + target<mod> src_in; + + if constexpr (mod == A) { + dest_out.ptr = &b_instruction_writable->anumber; + dest_in.ptr = &b_instruction.anumber; + src_in.ptr = &a_instruction.anumber; + } + + else if constexpr (mod == B) { + dest_out.ptr = &b_instruction_writable->bnumber; + dest_in.ptr = &b_instruction.bnumber; + src_in.ptr = &a_instruction.bnumber; + } + + else if constexpr (mod == AB) { + dest_out.ptr = &b_instruction_writable->bnumber; + dest_in.ptr = &b_instruction.bnumber; + src_in.ptr = &a_instruction.anumber; + } + + else if constexpr (mod == BA) { + dest_out.ptr = &b_instruction_writable->anumber; + dest_in.ptr = &b_instruction.anumber; + src_in.ptr = &a_instruction.bnumber; + } + + else if constexpr (mod == F) { + dest_out.ptr1 = &b_instruction_writable->anumber; + dest_out.ptr2 = &b_instruction_writable->bnumber; + dest_in.ptr1 = &b_instruction.anumber; + dest_in.ptr2 = &b_instruction.bnumber; + src_in.ptr1 = &a_instruction.anumber; + src_in.ptr2 = &a_instruction.bnumber; + } + + else if constexpr (mod == X) { + dest_out.ptr1 = &b_instruction_writable->anumber; + dest_out.ptr2 = &b_instruction_writable->bnumber; + dest_in.ptr1 = &b_instruction.anumber; + dest_in.ptr2 = &b_instruction.bnumber; + src_in.ptr1 = &a_instruction.bnumber; + src_in.ptr2 = &a_instruction.anumber; + } + + else if constexpr (mod == I) { + dest_out.instr = b_instruction_writable; + dest_in.instr = &b_instruction; + src_in.instr = &a_instruction; + } + + else assert(false); + + if constexpr (op == DAT) + return false; + + else if constexpr (op == MOV) { + add_modified_instruction(b_instruction_writable); + if constexpr (mod == I) { + dest_out.instr->op = src_in.instr->op; + dest_out.instr->mod = src_in.instr->mod; + dest_out.instr->amode = src_in.instr->amode; + dest_out.instr->bmode = src_in.instr->bmode; + } + return dest_out.assign(dest_in, src_in, [](number_t a, number_t b) -> std::optional<number_t> { + return b; + }); + } + + else if constexpr (op == ADD) { + add_modified_instruction(b_instruction_writable); + return dest_out.assign(dest_in, src_in, [](number_t a, number_t b) -> std::optional<number_t> { + return (a + b) % CORE_SIZE; + }); + } + + else if constexpr (op == SUB) { + add_modified_instruction(b_instruction_writable); + return dest_out.assign(dest_in, src_in, [](number_t a, number_t b) -> std::optional<number_t> { + return (a + CORE_SIZE - b) % CORE_SIZE; + }); + } + + else if constexpr (op == MUL) { + add_modified_instruction(b_instruction_writable); + return dest_out.assign(dest_in, src_in, [](number_t a, number_t b) -> std::optional<number_t> { + return (a * b) % CORE_SIZE; + }); + } + + else if constexpr (op == DIV) { + add_modified_instruction(b_instruction_writable); + return dest_out.assign(dest_in, src_in, [](number_t a, number_t b) -> std::optional<number_t> { + if (b == 0) + return {}; + return a / b; + }); + } + + else if constexpr (op == MOD) { + add_modified_instruction(b_instruction_writable); + return dest_out.assign(dest_in, src_in, [](number_t a, number_t b) -> std::optional<number_t> { + if (b == 0) + return {}; + return a % b; + }); + } + + else if constexpr (op == JMP) { + program_counter = (a_instruction_writable - core + CORE_SIZE - 1) % CORE_SIZE; + return true; + } + + else if constexpr (op == JMZ) { + if (dest_in.is_zero()) + program_counter = (a_instruction_writable - core + CORE_SIZE - 1) % CORE_SIZE; + return true; + } + + else if constexpr (op == JMN) { + if (!dest_in.is_zero()) + program_counter = (a_instruction_writable - core + CORE_SIZE - 1) % CORE_SIZE; + return true; + } + + else if constexpr (op == DJN) { + add_modified_instruction(b_instruction_writable); + if (dest_in.dec_not_zero()) + program_counter = (a_instruction_writable - core + CORE_SIZE - 1) % CORE_SIZE; + return true; + } + + else if constexpr (op == SEQ) { + if (src_in.equal_to(dest_in)) + program_counter = (program_counter + 1) % CORE_SIZE; + return true; + } + + else if constexpr (op == SNE) { + if (!src_in.equal_to(dest_in)) + program_counter = (program_counter + 1) % CORE_SIZE; + return true; + } + + else if constexpr (op == SLT) { + if (src_in.less_than(dest_in)) + program_counter = (program_counter + 1) % CORE_SIZE; + return true; + } + + else if constexpr (op == SPL) { + enqueue_process((program_counter + 1) % CORE_SIZE); + program_counter = (a_instruction_writable - core + CORE_SIZE - 1) % CORE_SIZE; + return true; + } + + else if constexpr (op == NOP) + return true; + + else assert(false); +} + +#define EXECUTOR_INST_LINE(mod) \ + template bool execute<DAT, mod>(); template bool execute<MOV, mod>(); \ + template bool execute<ADD, mod>(); template bool execute<SUB, mod>(); \ + template bool execute<MUL, mod>(); template bool execute<DIV, mod>(); \ + template bool execute<MOD, mod>(); template bool execute<JMP, mod>(); \ + template bool execute<JMZ, mod>(); template bool execute<JMN, mod>(); \ + template bool execute<DJN, mod>(); template bool execute<SEQ, mod>(); \ + template bool execute<SNE, mod>(); template bool execute<SLT, mod>(); \ + template bool execute<SPL, mod>(); template bool execute<NOP, mod>(); + +EXECUTOR_INST_LINE(A) +EXECUTOR_INST_LINE(B) +EXECUTOR_INST_LINE(AB) +EXECUTOR_INST_LINE(BA) +EXECUTOR_INST_LINE(F) +EXECUTOR_INST_LINE(X) +EXECUTOR_INST_LINE(I) diff --git a/lib94/warrior.cpp b/lib94/warrior.cpp new file mode 100644 index 0000000..0f100e6 --- /dev/null +++ b/lib94/warrior.cpp @@ -0,0 +1,476 @@ +#include <lib94/lib94.hpp> +#include <functional> +#include <fstream> +#include <cctype> +#include <cstdio> +#include <memory> +#include <map> + +struct number_expr { + virtual std::optional<number_t> to_number(const std::map<std::string, number_t> &label_offsets, number_t this_offset) = 0; +}; + +struct label_number_expr : public number_expr { + std::string label; + + virtual std::optional<number_t> to_number(const std::map<std::string, number_t> &label_offsets, number_t this_offset) { + auto result = label_offsets.find(label); + if (result == label_offsets.end()) + return {}; + return result->second - this_offset; + } +}; + +struct number_number_expr : public number_expr { + number_t value; + + virtual std::optional<number_t> to_number(const std::map<std::string, number_t> &label_offsets, number_t this_offset) { + return value; + } +}; + +struct op_number_expr : public number_expr { + std::unique_ptr<number_expr> left; + std::unique_ptr<number_expr> right; + std::function<std::optional<number_t> (number_t, number_t)> op; + + virtual std::optional<number_t> to_number(const std::map<std::string, number_t> &label_offsets, number_t this_offset) { + std::optional<number_t> left_result = left->to_number(label_offsets, this_offset); + std::optional<number_t> right_result = right->to_number(label_offsets, this_offset); + if (left_result.has_value() && right_result.has_value()) + return op(left_result.value(), right_result.value()); + return {}; + } +}; + +bool valid_label(std::string candidate) { + if (candidate == "") + return false; + + if (!isalpha(candidate[0]) && candidate[0] != '_') + return false; + + for (char ch : candidate) + if (!isalnum(ch) && ch != '_') + return false; + + return true; +} + +size_t find_respecting_parentheses(std::string part, std::string candidates) { + size_t layers = 0; + + for (size_t i = 0; i < part.size(); ++i) + if (layers == 0 && candidates.find(part[i]) != std::string::npos) + return i; + else if (part[i] == '(') + ++layers; + else if (part[i] == ')') + --layers; + + return std::string::npos; +} + +std::optional<std::unique_ptr<number_expr>> to_number_expr(std::string part); + +std::optional<std::unique_ptr<number_expr>> make_op_expr(std::string part, size_t split) { + std::string left = part.substr(0, split); + std::string right = part.substr(split + 1); + + std::optional<std::unique_ptr<number_expr>> left_expr = to_number_expr(left); + std::optional<std::unique_ptr<number_expr>> right_expr = to_number_expr(right); + if (!left_expr.has_value() || !right_expr.has_value()) + return {}; + + auto expr = std::make_unique<op_number_expr>(); + expr->left = std::move(left_expr.value()); + expr->right = std::move(right_expr.value()); + + switch (part[split]) { + case '+': expr->op = [](number_t a, number_t b) {return a + b;}; break; + case '-': expr->op = [](number_t a, number_t b) {return a - b;}; break; + case '*': expr->op = [](number_t a, number_t b) {return a * b;}; break; + case '/': expr->op = [](number_t a, number_t b) {return a / b;}; break; + case '%': expr->op = [](number_t a, number_t b) {return a % b;}; break; + } + + return expr; +} + +std::string trim_spaces(std::string str) { + size_t start = str.find_first_not_of(' '); + size_t end = str.find_last_not_of(' ') + 1; + if (start == std::string::npos) + return ""; + return str.substr(start, end - start); +} + +std::optional<std::unique_ptr<number_expr>> to_number_expr(std::string part) { + part = trim_spaces(part); + if (part == "") + return {}; + + size_t split = find_respecting_parentheses(part, "+-"); + if (split == std::string::npos) + split = find_respecting_parentheses(part, "*/%"); + if (split != std::string::npos) + return make_op_expr(part, split); + + if (part[0] == '(' && part[part.size() - 1] == ')') + return to_number_expr(part.substr(1, part.size() - 2)); + + size_t count; + number_t number = std::stoul(part, &count); + if (count == part.size()) { + std::unique_ptr<number_number_expr> expr = std::make_unique<number_number_expr>(); + expr->value = number; + return expr; + } + + if (valid_label(part)) { + std::unique_ptr<label_number_expr> expr = std::make_unique<label_number_expr>(); + expr->label = part; + return expr; + } + + return {}; +} + +static const std::map<char, mode> mode_symbols = { + {'#', IMMEDIATE}, {'$', DIRECT}, + {'*', A_INDIRECT}, {'@', B_INDIRECT}, + {'{', A_DECREMENT}, {'<', B_DECREMENT}, + {'}', A_INCREMENT}, {'>', B_INCREMENT} +}; + +std::optional<std::pair<mode, std::unique_ptr<number_expr>>> to_field(std::string part) { + if (part == "") + return {}; + + mode m = DIRECT; + + auto result = mode_symbols.find(part[0]); + if (result != mode_symbols.end()) { + m = result->second; + part = trim_spaces(part.substr(1)); + } + + std::optional<std::unique_ptr<number_expr>> expr = to_number_expr(part); + if (expr.has_value()) + return std::make_pair<>(m, std::move(expr.value())); + + return {}; +} + +static const std::map<std::string, opcode> opcode_names = { + {"dat", DAT}, {"mov", MOV}, {"add", ADD}, {"sub", SUB}, + {"mul", MUL}, {"div", DIV}, {"mod", MOD}, {"jmp", JMP}, + {"jmz", JMZ}, {"jmn", JMN}, {"djn", DJN}, {"seq", SEQ}, + {"sne", SNE}, {"slt", SLT}, {"spl", SPL}, {"nop", NOP}, + {"cmp", SEQ} +}; + +struct future_instruction { + size_t source_line; + opcode op; + modifier mod; + mode amode; + mode bmode; + std::unique_ptr<number_expr> anumber; + std::unique_ptr<number_expr> bnumber; +}; + +std::variant<warrior *, std::string> compile_warrior(std::string source) { + for (char &ch : source) + if (ch == '\t' || ch == '\r') + ch = ' '; + + std::unique_ptr<warrior> w = std::make_unique<warrior>(); + + std::vector<future_instruction> instructions; + std::map<std::string, number_t> label_offsets; + std::optional<std::unique_ptr<number_expr>> org = {}; + number_t org_offset; + size_t org_source_line; + + size_t on_line = 0; + + while (true) { + if (source == "") + break; + + ++on_line; + + size_t newline = source.find('\n'); + if (newline == std::string::npos) + newline = source.size(); + + std::string line = source.substr(0, newline); + source = source.substr(newline + 1); + + size_t semicolon = line.find(';'); + + if (semicolon != std::string::npos) { + std::string comment = trim_spaces(line.substr(semicolon + 1)); + line = line.substr(0, semicolon); + + if (comment.starts_with("name ")) + w->name = trim_spaces(comment.substr(5)); + else if (comment.starts_with("author ")) + w->author = trim_spaces(comment.substr(7)); + } + + for (char &ch : line) + ch = tolower(ch); + + while (true) { + size_t colon = line.find(':'); + if (colon == std::string::npos) + break; + + std::string label = line.substr(0, colon); + line = line.substr(colon + 1); + + if (!valid_label(label)) + return std::string("bad label on line ") + std::to_string(on_line); + if (label_offsets.contains(label)) + return std::string("duplicate label on line ") + std::to_string(on_line); + + label_offsets[label] = instructions.size(); + } + + line = trim_spaces(line); + if (line == "") + continue; + + future_instruction instr; + instr.source_line = on_line; + + std::string opcode_str = line.substr(0, 3); + line = trim_spaces(line.substr(3)); + + if (opcode_str == "org") { + if (org.has_value()) + return std::string("duplicate org on line ") + std::to_string(on_line); + + org = to_number_expr(line); + + if (!org.has_value()) + return std::string("bad expression on line ") + std::to_string(on_line); + + org_offset = instructions.size(); + org_source_line = on_line; + continue; + } + + auto opcode_it = opcode_names.find(opcode_str); + + if (opcode_it == opcode_names.end()) + return std::string("unknown opcode on line ") + std::to_string(on_line); + + instr.op = opcode_it->second; + + bool got_mod = false; + + if (line != "" && line[0] == '.') { + line = trim_spaces(line.substr(1)); + + if (line == "") + return std::string("dot with no modifier on line ") + std::to_string(on_line); + + got_mod = true; + + size_t mod_length = 2; + + if (line.starts_with("ab")) + instr.mod = AB; + else if (line.starts_with("ba")) + instr.mod = BA; + else { + + mod_length = 1; + + if (line[0] == 'a') + instr.mod = A; + else if (line[0] == 'b') + instr.mod = B; + else if (line[0] == 'f') + instr.mod = F; + else if (line[0] == 'x') + instr.mod = X; + else if (line[0] == 'i') + instr.mod = I; + + else + return std::string("unknown opcode modifier on line ") + std::to_string(on_line); + + } + + line = trim_spaces(line.substr(mod_length)); + } + + std::optional<std::pair<mode, std::unique_ptr<number_expr>>> afield, bfield; + + if (line == "") { + afield = to_field("0"); + bfield = to_field("0"); + } + + else { + size_t comma = line.find(","); + + if (comma == std::string::npos) { + afield = to_field(line); + bfield = to_field("0"); + } + + else { + std::string apart = trim_spaces(line.substr(0, comma)); + std::string bpart = trim_spaces(line.substr(comma + 1)); + afield = to_field(apart); + bfield = to_field(bpart); + } + } + + if (!afield.has_value() || !bfield.has_value()) + return std::string("bad expression on line ") + std::to_string(on_line); + + instr.amode = afield.value().first; + instr.bmode = bfield.value().first; + instr.anumber = std::move(afield.value().second); + instr.bnumber = std::move(bfield.value().second); + + if (!got_mod) + switch (instr.op) { + + case DAT: + instr.mod = F; + break; + + case MOV: + case SEQ: + case SNE: + if (instr.amode == IMMEDIATE) + instr.mod = AB; + else if (instr.bmode == IMMEDIATE) + instr.mod = B; + else + instr.mod = I; + break; + + case ADD: + case SUB: + case MUL: + case DIV: + case MOD: + if (instr.amode == IMMEDIATE) + instr.mod = AB; + else if (instr.bmode == IMMEDIATE) + instr.mod = B; + else + instr.mod = F; + break; + + case SLT: + if (instr.amode == IMMEDIATE) + instr.mod = AB; + instr.mod = B; + break; + + case JMP: + case JMZ: + case JMN: + case DJN: + case SPL: + case NOP: + instr.mod = B; + break; + + } + + instructions.push_back(std::move(instr)); + } + + if (w->name == "") + return "no name"; + if (w->author == "") + return "no author"; + + if (org.has_value()) { + std::optional<number_t> org_number = org.value()->to_number(label_offsets, org_offset); + if (org_number.has_value()) + w->org = org_number.value() + org_offset; + else + return std::string("bad expression on line ") + std::to_string(org_source_line); + } + + for (int i = 0; i < instructions.size(); ++i) { + const future_instruction &instr = instructions[i]; + std::optional<number_t> anumber = instr.anumber->to_number(label_offsets, i); + std::optional<number_t> bnumber = instr.bnumber->to_number(label_offsets, i); + if (!anumber.has_value() || !bnumber.has_value()) + return std::string("bad expression on line ") + std::to_string(instr.source_line); + w->instructions.push_back({ + .op = instr.op, .mod = instr.mod, .amode = instr.amode, .bmode = instr.bmode, + .anumber = ((anumber.value() % CORE_SIZE) + CORE_SIZE) % CORE_SIZE, + .bnumber = ((bnumber.value() % CORE_SIZE) + CORE_SIZE) % CORE_SIZE + }); + } + + return w.release(); +} + +struct wheader { + size_t name_size; + size_t author_size; + size_t instructions_size; + number_t org; +}; + +bool save_warrior(const warrior &w, const std::filesystem::path &to) { + FILE *f = fopen(to.c_str(), "wb"); + if (!f) + return false; + + wheader wh = { + .name_size = w.name.size(), .author_size = w.author.size(), + .instructions_size = w.instructions.size(), .org = w.org + }; + + fwrite(&wh, sizeof(wheader), 1, f); + fwrite(w.name.c_str(), w.name.size(), 1, f); + fwrite(w.author.c_str(), w.author.size(), 1, f); + fwrite(w.instructions.data(), sizeof(instruction) * w.instructions.size(), 1, f); + + fclose(f); + return true; +} + +std::optional<warrior *> load_warrior(const std::filesystem::path &from) { + FILE *f = fopen(from.c_str(), "rb"); + if (!f) + return {}; + + std::unique_ptr<warrior> w = std::make_unique<warrior>(); + + wheader wh; + fread(&wh, sizeof(wheader), 1, f); + + w->name.resize(wh.name_size); + w->author.resize(wh.author_size); + w->instructions.resize(wh.instructions_size); + w->org = wh.org; + + fread(w->name.data(), wh.name_size, 1, f); + fread(w->author.data(), wh.author_size, 1, f); + fread(w->instructions.data(), wh.instructions_size, 1, f); + + fclose(f); + + for (const instruction &i : w->instructions) + if (i.op > NOP || i.mod > I || i.amode > B_INCREMENT || i.bmode > B_INCREMENT || + i.anumber >= CORE_SIZE || i.bnumber >= CORE_SIZE) + return {}; + + return w.release(); +} diff --git a/test/build.sh b/test/build.sh new file mode 100644 index 0000000..199813d --- /dev/null +++ b/test/build.sh @@ -0,0 +1 @@ +g++ -O2 --std=c++20 -DCORE_SIZE=16 test.cpp ../lib94/*.cpp -I ../include -o test diff --git a/test/dwarf.rc b/test/dwarf.rc new file mode 100644 index 0000000..ff64ddc --- /dev/null +++ b/test/dwarf.rc @@ -0,0 +1,10 @@ +;author Standard +;name Dwarf + +org 1 + +dat 1, 1 ;not 0, 0 so i can see it change + +mov 0-1, 3 +add.ab #4, 0-1 +jmp 0-2 diff --git a/test/imp.rc b/test/imp.rc new file mode 100644 index 0000000..c6415fd --- /dev/null +++ b/test/imp.rc @@ -0,0 +1,4 @@ +;author Standard +;name Imp + +mov 0, 1 diff --git a/test/test.cpp b/test/test.cpp new file mode 100644 index 0000000..b838a02 --- /dev/null +++ b/test/test.cpp @@ -0,0 +1,85 @@ +#include <lib94/lib94.hpp> +#include <iostream> +#include <cassert> +#include <fstream> +#include <chrono> +#include <thread> + +const char *const opcodes[] = { + "dat", "mov", "add", "sub", + "mul", "div", "mod", "jmp", + "jmz", "jmn", "djn", "seq", + "sne", "slt", "spl", "nop" +}; + +const char *const modifiers[] = { + "a ", "b ", "ab", "ba", "f ", "x ", "i " +}; + +const char *modes = "#$*@{<}>"; + +int main(int argc, const char **argv) { + assert(argc > 1); + + seed_prng(time(0)); + + std::vector<const warrior *> ws; + + for (int i = 1; i < argc; ++i) { + std::string source; + std::ifstream f(argv[i]); + std::getline(f, source, '\0'); + f.close(); + + auto result = compile_warrior(source); + if (std::holds_alternative<std::string>(result)) { + std::cout << "Error in " << argv[i] << ": " << std::get<std::string>(result) << std::endl; + return 0; + } + + ws.push_back(std::get<warrior *>(result)); + } + + std::vector<number_t> wps; + wps.resize(ws.size()); + + clear_core({.op = DAT, .mod = F, .amode = DIRECT, .bmode = DIRECT, .anumber = 0, .bnumber = 0}); + init_round(ws); + + while (true) { + for (int i = 0; i < ws.size(); ++i) + if (get_processes(ws[i]).size() == 0) + wps[i] = -1; + else + wps[i] = get_next_process(ws[i]); + + auto mod = get_modified_addresses(); + + printf("\x1b[H\x1b[2J"); + + for (int a = 0; a < CORE_SIZE; ++a) { + const instruction &i = get_instruction(a); + + printf("%d: %s.%s %c%d, %c%d", + a, opcodes[i.op], modifiers[i.mod], + modes[i.amode], i.anumber, + modes[i.bmode], i.bnumber); + + if (mod.contains(a)) + printf(" *"); + + for (int w = 0; w < ws.size(); ++w) + if (a == wps[w]) + printf(" < %s", ws[w]->name.c_str()); + + putchar('\n'); + } + + std::this_thread::sleep_for(std::chrono::milliseconds(250)); + + clear_modified_addresses(); + single_step(); + } + + return 0; +} |