lib94/include/lib94/lib94.hpp

#ifndef LIB94_LIB94_HPP
#define LIB94_LIB94_HPP

#include <optional>
#include <cstdint>
#include <string>
#include <vector>
#include <deque>
#include <mpi.h>
#include <set>

#ifndef LIB94_CORE_SIZE
#define LIB94_CORE_SIZE 8000
#endif

#ifndef LIB94_MAX_PROCESSES
#define LIB94_MAX_PROCESSES 16000
#endif

namespace lib94 {

  //this type is used to represent values inside the core.
  //it has to be at least big enough to represent LIB94_CORE_SIZE squared,
  //since it is used as an intermediate for all of the instructions,
  //including in particular MUL.
  typedef int32_t number_t;
  #define LIB94_MPI_NUMBER_T MPI_INT32_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;

    //the org of the warrior, as an index into the instructions vector
    number_t org;

    //the instructions of the warrior at the start of a round
    std::vector<instruction> instructions;
  };

  //serialize a warrior in such a way that it can be read back by deserialize_warrior.
  //does not consider name and author.
  void serialize_warrior(const warrior *the_warrior, std::vector<uint8_t> &into);

  //deserialize a warrior that has been serialized by serialize_warrior.
  //no error checking is performed.
  //does not consider name and author.
  warrior *deserialize_warrior(const uint8_t *from);

  //this seeds the prng used to place warriors into the core at the start of a round
  //if this is never called, 0 is used as a seed and the placements are deterministic.
  void seed_prng(uint_fast64_t seed);

  //converts an instruction to a string representation like
  //  dat.f $0, $0
  std::string instruction_to_string(const instruction &instr);

  //this exception is thrown by any error that occurs in the compile_warrior function,
  //including a malformed instruction, a non-existent label being referenced, a division
  //division by zero in a compile-time expression, a failed ;assert comment, etc.
  struct compiler_exception : public std::exception {
    unsigned source_line_number;
    std::string message;
  };

  //takes a string with the full source code of a warrior. on success, returns a pointer
  //to a warrior struct representing the compiled warrior (which you must delete when
  //you are done with it). on failure, throws a compiler_exception as defined above.
  warrior *compile_warrior(std::string source);

  //fills the core with the supplied instruction; does not effect the address sets.
  void clear_core(const instruction &background);

  //fills the core with random instructions chosen from a uniform distribution;
  //does not effect the address sets.
  void clear_core_random();

  //clears the address sets, places the supplied warriors into the core, and starts one
  //process for each supplied warrior at its org. the count parameter specifies the number
  //of warriors in the array. each of the warriors in the array must not be deleted for
  //the duration of the round, but the array itself may be deleted after this function
  //returns. if the offsets parameter is not null, it specifies where in the core the first
  //instruction of each warrior is put. if it is null, the warriors are placed at random
  //non-overlapping locations, respecting the order that they appear in the array. if
  //shuffle is true, the warriors' turn order is decided randomly. if shuffle is false,
  //the turn order is the order that they appear in the warriors array. on success, this
  //function returns true. on failure (i.e. when offsets is null and the warriors do not
  //all fit into the core), this function returns false. note that this function does not
  //clear the core before placing the warriors, so you may want to call clear_core or
  //clear_core_random before calling this. note also that if you are passing null for
  //offsets or setting shuffle to true, you probably want to call seed_prng, for example
  //with the current time, before the first time you call this.
  bool init_round(const warrior *const *warriors, size_t count, const number_t *offsets, bool shuffle);

  void remove_all_warriors();

  //returns the number of warriors who have at least one process
  size_t alive_warrior_count();

  //returns a pointer to the warrior whose turn it will be during the next call
  //to single_step. makes an assertion that there is such a warrior, so check
  //alive_warrior_count first if you are not sure.
  const warrior *get_next_warrior();

  //gets the program counter queue for the specified warrior. fails an assertion if this
  //pointer was not one of the pointers in the array passed to init_round. it's okay if
  //this warrior has no processes left; in that case this returns an empty deque.
  const std::deque<number_t> &get_processes(const warrior *for_warrior);

  //the addresses written to since the last call to init_round or clear_address_sets
  const std::set<number_t> &get_written_addresses();

  //the addresses read from since the last call to init_round or clear_address_sets
  const std::set<number_t> &get_read_addresses();

  //the addresses executed since the last call to init_round or clear_address_sets
  const std::set<number_t> &get_executed_addresses();

  void clear_address_sets();

  //the instruction at the specified address of the core
  const instruction &get_instruction(number_t address);

  //does one step of the simulation. assumes that there is at least one warrior with at
  //least one alive process, so check alive_warrior_count first if you aren't sure.
  //if the warrior whose turn it is has only one process, and that process dies during
  //this step, the pointer to that warrior is returned. otherwise, a null pointer is
  //returned. the update_address_sets template parameter controls whether to update the
  //sets returned by get_*_addresses. this is provided so that you can improve the
  //performance of the simulation if you do not need that information.
  template <bool update_address_sets>
  const warrior *single_step();

  //convenience method - reads the contents of a file and then calls compile_warrior.
  //if the file cannot be read, returns a null pointer. see comment on compile_warrior.
  warrior *compile_warrior_from_file(std::string path);

  //convenience method - calls clear_core(background), then init_round(warriors, count,
  //offsets, shuffle), then single_step<false> until either one warrior remains or that
  //has been called steps_to_tie times. if one warrior remains, returns the pointer to
  //that warrior. if a tie is reached, returns a null pointer. this asserts that the call
  //to init_round returns true. see comment on init_round.
  const warrior *do_round(const instruction &background, const warrior *const *warriors, size_t count, const number_t *offsets, bool shuffle, long steps_to_tie);

  //runs every possible offset and turn order using do_round.
  //asserts that total length is not more than core size.
  //should be called from everyone in a communicator.
  //assumes comm ranks go from 0 to comm size - 1.
  template <bool print_progress>
  void tabulate_mpi(const instruction &background, const warrior *w1, const warrior *w2, long steps_to_tie, int &w1_wins_out, int &w2_wins_out, int &rounds_out, MPI_Comm communicator);

}

#endif