6
\$\begingroup\$

My best languages are Python and Rust, but I want to improve my C++ skills, so I decided to try my hand at Advent of Code 2019 in C++. So far I have not encountered any major issues, but I want to know what I am doing that is subtly (or not so subtly) wrong.

The following program is my solution to the Day 9 problem. It's essentially an interpreter for a contrived machine language called Intcode. The Intcode specification is spread among Day 2, Day 5, and Day 9. The Day 7 problems had additional constraints that may explain some of my architecture decisions.

Here are some properties of the Intcode language:

  • Intcode programs may assume shared instruction and data memory, and most or all of the example programs make use of this.
  • An Intcode computer has two registers: the instruction pointer, which I called the program counter (_pc), and the relative base, which I called the stack pointer (_sp). Both are defined to initialize to 0.
  • Intcode instructions are of variable size, and the program counter has to be incremented by the width of the current instruction each cycle.
  • Intcode instructions support arguments with three different addressing modes: immediate, "positional" (that is, direct addressing) and "relative" (that is, stack-relative addressing). The addressing modes of all the arguments of an instruction are encoded into the high digits of its opcode.
  • To solve certain problems, it's necessary to start multiple Intcode computers, connect their inputs and outputs and run them concurrently (although not literally at the same time).
  • I created mnemonics for each of the Intcode instruction opcodes as I encountered them and invented an assembly language for debugging purposes; these are not part of the specification but you can observe them by uncommenting the appropriate lines.
  • The memory size is unspecified, but all memory locations are initially zero. In my code, the memory starts at the size of the input program and increases whenever an out-of-bounds write occurs.

My code passes all the tests on the site. I'm more concerned about eradicating bad habits and avoiding pitfalls than whether the Intcode logic itself is right.

#include <fstream>
#include <iomanip>
#include <iostream>
#include <optional>
#include <sstream>
#include <stdexcept>
#include <vector>

using Int = long;

enum Opcode {
    ADD = 1,
    MUL = 2,
    INPUT = 3,
    OUTPUT = 4,
    JNZ = 5,
    JZ = 6,
    TESTLT = 7,
    TESTEQ = 8,
    ADDSP = 9,
    HALT = 99,
};

enum class Mode {
    Pos/*ition*/ = 0,
    Imm/*ediate*/ = 1,
    Rel/*ative*/ = 2,
};

class Argument {
public:
    Argument(Mode mode, Int value) : _mode(mode), _value(value) {}

    Mode mode() const {
        return _mode;
    }

    Int value() const {
        return _value;
    }

private:
    Mode _mode;
    Int _value;
    friend std::ostream& operator<<(std::ostream& os, const Argument& self);
};

std::ostream& operator<<(std::ostream& os, const Argument& self) {
    switch (self._mode) {
        case Mode::Imm:
            return os << self._value;
        default:
            std::cerr << "Warning: unknown addressing mode" << std::endl;
            [[fallthrough]];
        case Mode::Pos:
            return os << "[" << self._value << "]";
        case Mode::Rel:
            if (self._value < 0) {
                return os << "[sp - " << -self._value << "]";
            } else if (self._value > 0) {
                return os << "[sp + " << self._value << "]";
            } else {
                return os << "[sp]";
            }
    }
}

class Instruction {
public:
    Instruction(const Int* mem) {
        if (mem[0] < 0) {
            throw std::runtime_error("negative opcode");
        }
        _opcode = (Opcode)(mem[0] % 100); // the last two digits are the opcode
        Int addr_modes = mem[0] / 100;
        // parse arguments:
        for (size_t a = 1; a < length(); ++a) {
            auto mode = static_cast<Mode>(addr_modes % 10);
            _args.emplace_back(mode, mem[a]);
            addr_modes /= 10;
        }
        if (addr_modes > 0) {
            std::cerr << "Warning: unused addressing flags";
        }
    }

    Opcode opcode() const {
        return _opcode;
    }

    const Argument& arg(size_t n) const {
        return _args[n];
    }

    /* The code size of this instruction. The amount by which the program
     * counter should be incremented after executing it. */
    size_t length() const {
        switch (_opcode) {
            case ADD:
            case MUL:
            case TESTLT:
            case TESTEQ:
                return 4;
            case JNZ:
            case JZ:
                return 3;
            case INPUT:
            case OUTPUT:
            case ADDSP:
                return 2;
            case HALT:
                return 1;
            default:
                throw std::logic_error("bad opcode in Instruction::length");
        }
    }

private:
    std::vector<Argument> _args;
    Opcode _opcode;
    friend std::ostream& operator<<(std::ostream& os, const Instruction& self);

    /* The number of input arguments this instruction has. Input arguments are
     * distinguished from output arguments because they may be immediate. In
     * the Intcode machine language, input arguments always precede output
     * arguments. */
    size_t inputs() const {
        switch (_opcode) {
            case ADD:
            case MUL:
            case JNZ:
            case JZ:
            case TESTLT:
            case TESTEQ:
                return 2;
            case OUTPUT:
            case ADDSP:
                return 1;
            case INPUT:
            case HALT:
                return 0;
            default:
                throw std::logic_error("bad opcode in Instruction::inputs");
        }
    }
};

std::ostream& operator<<(std::ostream& os, const Instruction& self) {
    constexpr const char *opcode_names[] = {
        NULL, "ADD", "MUL", "INPUT", "OUTPUT", "JNZ", "JZ", "TESTLT", "TESTEQ",
        "ADDSP", NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
        NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
        NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
        NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
        NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
        NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
        NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
        NULL, NULL, NULL, NULL, NULL, NULL, NULL, "HALT"};
    os << opcode_names[self._opcode];
    for (auto& arg: self._args) {
        os << " " << arg;
    }
    return os;
}

class Cpu {
public:
    Cpu(std::ostream& out = std::cout, std::istream& in = std::cin)
        : _pc(0), _sp(0), _out(out), _in(in) {}

    /* for debugging purposes
    void set_name(std::string name) {
        _name = name;
    }
    */

    /* Populates this cpu's memory with data read from a file.
     * Also resets the program counter and stack pointer to 0. */
    void load(const std::string& file_name)
    {
        _mem.clear();
        _pc = 0;
        _sp = 0;
        auto fp = std::ifstream(file_name);
        if (!fp.is_open()) {
            throw std::runtime_error("failed to open input file");
        }
        std::string line;
        Int arg;
        while (fp >> arg) {
            _mem.emplace_back(arg);
            char comma;
            if (!(fp >> comma)) {
                break;
            } else if (comma != ',') {
                throw std::runtime_error("expected ','");
            }
        }
        fp.close();
    }

    /* Runs this Cpu until it halts or stops to wait for input. */
    void run() {
        while (true) {
            Instruction inst(&_mem[_pc]);

            //debug() << std::setw(7) << inst << std::endl;
            auto pc_nxt = execute(inst);
            if (pc_nxt) {
                _pc = *pc_nxt;
            } else {
                break;
            }
        }
    }

    /* Returns true if the program is halted, false if it is blocked waiting
     * for input. */
    bool is_halted() {
        return _mem[_pc]%100 == HALT;
    }

private:
    std::vector<Int> _mem;
    size_t _pc;
    size_t _sp;
    std::ostream& _out = std::cout;
    std::istream& _in = std::cin;
    //std::optional<std::string> _name;

    /* Returns a (reference to a) value in memory. */
    Int& lvalue(const Argument& arg) {
        size_t i;
        switch (arg.mode()) {
            case Mode::Imm:
                throw std::logic_error("immediate mode is not available for lvalues");
            default:
                std::cerr << "Warning: unknown addressing mode" << std::endl;
                [[fallthrough]];
            case Mode::Pos:
                i = arg.value();
                break;
            case Mode::Rel:
                i = _sp + arg.value();
                break;
        }
        // resize _mem so i is in range
        if (i >= _mem.size()) {
            _mem.resize(i + 1);
        }
        return _mem[i];
    }

    /* Evaluates an argument to an instruction, either immediate or from memory
     * according to the addressing mode of the argument. */
    Int rvalue(const Argument& arg) const {
        size_t i;
        switch (arg.mode()) {
            case Mode::Imm:
                return arg.value();
            default:
                std::cerr << "Warning: unknown addressing mode" << std::endl;
                [[fallthrough]];
            case Mode::Pos:
                i = arg.value();
                break;
            case Mode::Rel:
                i = _sp + arg.value();
                break;
        }
        // return 0 for out of range
        if (i >= _mem.size()) {
            return 0;
        }
        return _mem[i];
    }

    /* Executes a single instruction, modifying memory and the stack pointer
     * but not the program counter. */
    std::optional<size_t> execute(const Instruction& inst) {
        auto arg = [&](size_t n) { return rvalue(inst.arg(n)); };
        switch (inst.opcode()) {
            case ADD:
                lvalue(inst.arg(2)) = arg(1) + arg(0);
                break;
            case MUL:
                lvalue(inst.arg(2)) = arg(1) * arg(0);
                break;
            case INPUT:
                if (_in >> lvalue(inst.arg(0))) {
                    //debug() << "input = " << arg(0) << std::endl;
                    break;
                } else {
                    _in.clear(); // clear the eof state
                    //debug() << "waiting for input" << std::endl;
                    return std::nullopt;
                }
            case OUTPUT:
                _out << arg(0) << std::endl;
                //debug() << "output = " << arg(0) << std::endl;
                break;
            case JNZ:
                if (0 != arg(0)) {
                    return arg(1);
                }
                break;
            case JZ:
                if (0 == arg(0)) {
                    return arg(1);
                }
                break;
            case TESTLT:
                lvalue(inst.arg(2)) = arg(0) < arg(1);
                break;
            case TESTEQ:
                lvalue(inst.arg(2)) = arg(0) == arg(1);
                break;
            case ADDSP:
                _sp += arg(0);
                break;
            case HALT:
                return std::nullopt;
            default:
                throw std::logic_error("bad opcode in execute");
        }
        return _pc + inst.length();
    }

    /*
    std::ostream& debug() {
        if (_name) {
            std::cerr << std::setw(10) << *_name << ": ";
        }
        return std::cerr;
    }
    */
};

int main() {
    Cpu cpu;
    cpu.load("day09.in");
    cpu.run();
}

I am most interested in knowing what about my code is error-prone, buggy, or just kind of "weird" to an experienced C++ programmer. I've seen several C++ styles in use and I picked what made sense to me, but that doesn't mean they make sense collectively.

Some specific things that seem a little awkward are:

  • Cpu::run() returns either when the program halts or when it is waiting for input. (The client can call Cpu::is_halted to distinguish these cases.) When the program stops to wait for input, I had to call _in.clear() inside execute to clear the EOF flag from the stream. This seemed a little risky to me, because I might be clearing an error flag instead. I suppose I could test for EOF or error separately, but it just seems a bit awkward. Is there some better way of structuring the input that I haven't thought of?

  • I tried to find a way to write a value function that would contextually interpret an argument as input or output, so instead of

    lvalue(inst.arg(2)) = arg(1) + arg(0);
    

    I would be able to write

    value(2) = value(1) + value(0);
    

    and argument 2 would be parsed as an output parameter (for which immediate addressing mode is not allowed) while arguments 1 and 0 would be parsed as input parameters (for which any addressing mode is allowed). Possibly this was a silly idea; anyway, I thought it would be possible by dispatching on the constness of this, but I could not find a way to do it. Still, if it's possible, I'd like to know how.

  • There seems to be a difference between enum and enum class when it comes to how integer values are assigned. I used enum for opcodes and enum class for addressing modes, not really with any rhyme or reason. Should I have used enum class or enum for both? With enum class it seems you have to give them all explicit values if you want static_cast to work consistently. I did not find much information about this online.

  • friend ostream& operator<<: is this a good way to create a debug-ready output format?

  • Is const std::string& a good way to accept a string argument when you don't need to mutate or copy it? I tried std::string_view but it seems you can't make one from a char *.

  • One of the mistakes I made was as follows: in lvalue, when testing whether the memory needed to be resized, I used > instead of >=. This caused a subtle bug that only triggered when the address being written was exactly one beyond the end of the vector. Valgrind could not detect this bug (at least, not with default options). Is there some compiler switch I can turn on, or another tool I could use to easily detect index-out-of-range errors while debugging?

  • The vectors for Arguments in Instruction seem a bit extra. I would like to store them in-line in Instruction, and save on allocation, since the maximum size is only 3. Is there a typical solution to this kind of problem? The only thing I could think of was to have an array of 3 optional<Argument>s and that seemed tricky.

Here is a simple Intcode quine to test the code with (day09.in):

109,1,204,-1,1001,100,1,100,1008,100,16,101,1006,101,0,99

It should print itself to stdout (but with newlines instead of commas).

\$\endgroup\$
2
+100
\$\begingroup\$

I agree with everything in Kunal's answer. I'd like to add:

Consider using fmtlib for formatting strings

Fmtlib is an excellent library for formatting strings, and part of it will become standard in C++20. The library itself supports printing to a std::ostream directly, so you can write something like:

#include <fmt/ostream.h>
...
fmt::print(os, "[sp - {}]", -self._value);

Use (static) asserts

It is always good to put the assumptions you have in the code, so these assumptions can be checked at compile- and/or runtime. For example, in your overload of operator<<(), it is easy to add a NULL too little or too many in the array, and if you ever add a new opcode, but forget to append it to opcode_names[], the program might crash when trying to format the opcode. So here you could add:

assert(self._opcode < sizeof opcode_names / sizeof *opcode_names);
static_assert(opcode_names[Opcode::HALT]);

If you can use C++17, the first assert can be written as:

assert(self._opcode < std::size(opcode_names));

Some basic rules:

  • static_assert() is safe to use anywhere, but it only works for things the compiler can check.
  • assert() should be used for anything that should really never happen, but you want to check for it in debug builds, but not pay the price for it in release builds.
  • For things that should not but might happen, like malformed input, return an error or throw an exception. You are already doing this, great!

Use nullptr instead of NULL

The main reason is that NULL is implicitly convertible to integral types. Good compilers will warn about them, but if you use nullptr it becomes an error.

When initializing pointers, you can also write Sometype *ptr = {} to ensure it is zeroed. This would also work in the initialization of arrays like opcode_names[].

Member variable initialization

When initializing member variables to a constant value, prefer doing this at the point you declare the member variable, rather than in the constructor. For example:

class Cpu {
    Cpu(std::ostream& out = std::cout, std::istream& in = std::cin)
        : _out(out), _in(in) {}
    ...
private:
    size_t _pc = 0;
    size_t _sp = 0;
    std::ostream &out;
    std::istream &in;
    ...
};

Note that since you don't initialize out and in with constants, adding a default for those member variables' declarations is useless.

Always check the state of std::ifstream when you reached the end of the input

A loop like:

while (fp >> arg) {
    ...
}

Will exit when the end of the file is reached, but also when any error condition is encountered. So before closing the file, check its state and return an error if it's not as expected:

if (fp.fail()) {
    throw std::runtime_error("error parsing input file");
}

Use a class hierarchy

Your program currently declares all types in the global namespace, even ones with very generic names like Mode and Argument. You can use the namespace keyword to put everything into its own namespace, but you can also nest classes. For example, an Instruction is specific to a Cpu, so you could declare class Instruction inside class Cpu. Going further, Opcode and Argument are part of Instruction, and Mode is something specific to Arguments.

Another issue is that your Cpu handles both the execution of instructions, as well as the memory. However, memory is normally something that is separate from a CPU, so it might be an idea to create a class Memory to represent the memory, and somehow pass a reference to the memory to Cpu.

Finally, everything together forms a computer, so you could use that as the outermost class, so you can have multiple instances of an Intcode computer in your C++ program. Here's a proposed sketch:

class IntcodeMachine {
  using Int = long;

  class Memory {
    std::vector<Int> data;
    ...
    public:
    Int &operator[](size_t pc) {
      return data[pc];
    }

    void load(const std::string &file_name) {
      ...
    }
  };

  class Cpu {
    class Instruction {
      enum Opcode {...};
      class Argument {
        enum Mode {...};
      };
    };

    public:
    void run(Memory &memory) {...}
    bool is_halted() {...}
  };

  Memory memory;
  Cpu cpu;

public:
  void load(const std::string &file_name) {
    memory.load(file_name);
  }

  void run() {
    cpu.run(memory);
  }

  bool is_halted() {
    return cpu.is_halted();
  }
};

int main() {
   IntcodeMachine machine;
   machine.load("day09.in");
   machine.run();
}

Storing Arguments in an Instruction

There are various ways to optimize the storage of small arrays. You could indeed use the suggested std::basic_string<Argument> and rely on its small-string optimization, however it will not win any beauty contests. You could also use a std::array<> sized to hold the maximum possible number of arguments, and add another integer variable to track the actual number of arguments. The proper solution would be something like the proposed std::dynarray<>, but unfortunately it never made it into the standard.

If performance is not yet a concern, I suggest you keep using std::vector<>. If performance is an issue, then try out the alternatives and benchmark them to see which one is best for you.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ It was a hard decision which answer to checkmark, but I feel this one was the most helpful! Thanks for your review. \$\endgroup\$ – trentcl Dec 22 '19 at 0:01
3
\$\begingroup\$

code is error-prone, buggy, or just kind of "weird"

  • const Int* mem instead of a range (pair of iterators to check for out of bounds access)
  • Using C style casts (even for calculations, they can cause issues with signed operations, unexpected casts and silent dynamic casts), but your usage is fine since it's restricted code, not a generic code
  • Using an array of struct for OpCode -> (InputLength, OutputLength, String) conversion would put all details in one place, outside of "logic"
  • Using getline for reading from file would have made more sense to me
  • Edit: read one statement wrong and reviewed: "Applying [[fallthrough]] insonsistently". My bad
  • Yoda conditions (tools and even compilers warn of assignment inside checks, so it is kinda irrelevant now)

Is there some better way of structuring the input that I haven't thought of?

Sadly, the input needs to be in the execute loop. Checking for EOF is straightforward and can be done before clearing the error flags.

Still, if v(2) = v(1) + v(0) is possible, I'd like to know how.

This is very much possible. Lots of libraries use Expression Templates (like Eigen v3) but the use-case is usually extreme performance. Essentially, you overload the operator+ to result in something that is assignable to the output of operator() which is itself a different overload as compared to operator() const. In your case, 2 operator(): one const (and essentially the rvalue function) and one non-const (the lvalue function) would resolve your issue, but that's not possible with lambdas (AFAIK). You'd need to create a class that has the possible overloads (and lambdas are technically syntactic sugar, check cppinsights.io)

Should I have used enum class or enum for both?

I'd say yes to enum class, because it protects from silly errors like assigning to and from integers, among the enums, etc. Strong type system usually make code self-documenting. But people complain about needing casts everywhere.

friend ostream& operator<<: is this a good way to create a debug-ready output format?

Usually, this is a good idea, but it lacks fine-grain control. For large projects, people use logging libraries with to classify what details they'd prefer (and more functions to dump extra info for debugging vs status reports). For your use-case, perfectly fine choice.

I tried std::string_view but it seems you can't make one from a char *

string_view allows creation from char* if the size is provided. Not many people will complain about your usage of const std::string&

Is there some compiler switch I can turn on, or another tool I could use to easily detect index-out-of-range errors while debugging?

There are multiple sanitizers (available for both Clang and GCC) called ASan, MemSan, TSan, UBSan, TySan, etc. and which check for errors at runtime (some can report issues at compile time too). There's clang-tidy which is really nice tool for refactoring and automatic fixing errors. There are some tools associated with MISRA-C++ too but I don't know (rather never bothered to find) any that are free. Using the vector.at operator instead of index access will throw for bad access.

I would like to store them in-line in Instruction, and save on allocation, since the maximum size is only 3. Is there a typical solution to this kind of problem?

Use std::basic_string<Type> to get small_vector_optimization for free. More seriously, there are several header only classes that create a vector on the stack of a max size and keep track of the used size providing a std::vector like API and a std::array like allocation pattern.

Use C++ ecosystem

Using the stdlib with C++ will only get you through so far. C++ doesn't come batteries included ala python, so you need to use libraries to fill the gap based on your preferences.

As such, for iterators, you can use Boost.Iterators.function_input_iterator or MS.GSL.span or rangesv3.ranges.view_facade as library helpers for features.

For input/output formatting, I'd recommend using a csv reader (csv::CVSReader or io::CSVReader) and fmtlib for output.

You can use std::pmr::vector with a stack (arena) allocator to still use std::vector or use Boost.Container.static_vector for storing the operands.

For the core logic, you can actually use a grammar parser to do the heavy lifting (PEGTL, Boost.Spirit). This is actually optional based on your aims because it changes the focus from language to library for the main objective.

If you're planning to do regular C++, then go the library route. I'd recommend to use Conan, Build2 (my personal recommendations) or others to manage the libraries. I'd more strongly recommend you to check Awesome C++ which incidentally contains all the major "optional" libraries I tend to use (Boost, Abseil, Catch2, units, date, ranges, coro, Eigen)

Disclaimer: I'm unaffiliated with all these libraries (and links), just use them

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Thanks for your review! I'll be reading these carefully. I originally did try to define Instruction with a pair of iterators, but it was such a pain in the butt because instead of just foo(mem[1]) I had to write auto ptr = start + 1; if (ptr == end) { throw std::out_of_bounds("..."); } foo(*ptr). .at() isn't available unless you have the whole vector. Eventually I just gave up and trusted the input. Is there something I'm missing here or is dealing with iterators just... always like this? I could have used std::span, I guess, but I was compiling under C++17 \$\endgroup\$ – trentcl Dec 16 '19 at 14:18
2
\$\begingroup\$

I'd endorse both of the reviews you've already gotten. I just wanted to add a few points not already mentioned.

Prefer to pass std::istream rather than a file name

Your program could very easily be made a little more useful and general by writing load() to take an already open std::istream& instead of a std::string filename. For instance, it would allow you to pass a std::stringstream for testing.

Use a simple state machine to read input

It seems that your load can be made a bit simpler and more robust by reading a character at a time and using a state machine. Here's one way to do that that also uses the previous suggestion:

void CPU::load(std::istream& in) {
    enum States{sign, digit, error};
    States state{States::sign};
    bool negative{false};
    Int value{0};
    char ch;
    while (in >> ch) {
        switch(state) {
            case States::sign:
                switch(ch) {
                    case '-':
                        negative = true;
                        state = States::digit;
                        break;
                    case '+':
                        negative = false;
                        state = States::digit;
                        break;
                    default:
                        if (std::isdigit(ch)) {
                            value = ch - '0';
                            state = States::digit;
                        } else {
                            state = States::error;
                        }
                }
                break;
            case States::digit:
               if (std::isdigit(ch)) {
                    value = value * 10 + ch - '0';
                } else if (ch == ',') {
                   m.push_back(negative ? -value : value);
                   value = 0;
                   negative = false;
                   state = States::sign;
                } else {
                    state = States::error;
                }
                break;
            case States::error:
                in.setstate(std::ios::failbit);
                return;
        }
    }
    if (state == States::digit) {
       m.push_back(negative ? -value : value);
    }
}

Gather like things together

It was already mentioned that having a Memory class might be a good idea. I'd go a bit further and say that it would make sense to have both a Memory and a Register class. The Register class could contain the pc and sp values and even in and out.

Separate interface from implementation

You may already know this, but in C++, a common idiom is to separate the interface from the implementation. That is, the public interface would go into a header file and the corresponding implementation would go into a .cpp file. The advantage is that with a carefully designed interface, the underlying implementation can be refined and modified without having to recompile the rest of the code. See SF.1 for details.

Gather things together into objects

The Cpu class arguably contains everything required to understand instructions, but it's spread over many places: there are multiple enums, a number of switch statements and finally the operations themselves. We can do better! I would recommend creating an Instruction class. Here's what I wrote:

struct Instruction {
    Int value;
    unsigned len;
    std::string_view mnemonic;
    void (* op )(const Instruction& inst, Regs &r, Mem &m);

    // more functions
};

The value is the basic opcode value, such as 1 for add and 2 for multiply. The len is the number of bytes for this instruction and mnemonic is the printable name of the instruction such as "ADD" or "MUL". Finally, we have a function pointer to a void function that takes three arguments: a reference to the containing function (equivalent to the this pointer), a reference to the registers and a reference to the memory. Now we can create a static constexpr list of these:

static constexpr std::array<Instruction, 10> instructions {{
    // opcode,  len,  mnemonic,   operation
    { 1, 4, "ADD", [](const Instruction& inst, Regs& r, Mem& m){ 
        inst.c(r, m) = inst.a(r, m) + inst.b(r, m);
        r.pc += inst.len; 
    }},
    { 2, 4, "MUL", [](const Instruction& inst, Regs& r, Mem& m){ 
        inst.c(r, m) = inst.a(r, m) * inst.b(r, m);
        r.pc += inst.len; 
    }},
    { 3, 2, "INPUT", [](const Instruction& inst, Regs& r, Mem& m){
        r.in >> inst.a(r, m);
        r.pc += inst.len; 
    }},
    { 4, 2, "OUTPUT", [](const Instruction& inst, Regs& r, Mem& m){
        r.out << inst.a(r, m) << '\n';
        r.pc += inst.len; 
    }},
    { 5, 3, "JNZ", [](const Instruction& inst, Regs& r, Mem& m){
        r.pc = (inst.a(r, m) == 0 ? r.pc + inst.len : inst.b(r, m));
    }},
    { 6, 3, "JZ", [](const Instruction& inst, Regs& r, Mem& m){
        r.pc = (inst.a(r, m) == 0 ? inst.b(r, m) : r.pc + inst.len);
    }},
    { 7, 4, "TESTLT", [](const Instruction& inst, Regs& r, Mem& m){
        inst.c(r, m) = inst.a(r, m) < inst.b(r, m);
        r.pc += inst.len; 
    }},
    { 8, 4, "TESTEQ", [](const Instruction& inst, Regs& r, Mem& m){
        inst.c(r, m) = inst.a(r, m) == inst.b(r, m);
        r.pc += inst.len; 
    }},
    { 9, 2, "ADDRB", [](const Instruction& inst, Regs& r, Mem& m){
        r.rb += inst.a(r, m);
        r.pc += inst.len; 
    }},
    { 99, 1, "HALT", [](const Instruction& inst, Regs& r, Mem& ){
        r.halted = true;
        r.pc += inst.len; 
    }},
}};

Note that because it's constexpr, all of this is created at compile time and not at runtime. The code relies on a few simple helper functions within the Instruction class:

bool operator==(const Int &a) const { return opcode(a) == value; }
Int& a(Regs &r, Mem &m) const { 
    return param(r, m, 1);
}
Int& b(Regs &r, Mem &m) const { 
    return param(r, m, 2);
}
Int& c(Regs &r, Mem &m) const { 
    return param(r, m, 3);
}

Int& param(Regs &r, Mem &m, unsigned param) const { 
    auto mul = 10;
    for (unsigned i = 0; i < param; ++i) {
        mul *= 10;
    }
    const auto mode = m[r.pc] / mul % 10;
    switch(mode) {
        case 0:  // position
            return m[m[r.pc + param]];
            break;
        case 1:  // immediate
            if (param != 3) {
                return m[r.pc + param];
            }
            break;
        case 2:
            return m[r.rb + m[r.pc + param]];
            break;
    }
    throw std::logic_error("bad destination addressing mode");
}

static Int opcode(const Int& num) { return num % 100; }

Finally, we can easily implement run:

void CPU::run() {
    while (!r.halted) {
        auto inst{std::find(instructions.begin(), instructions.end(), m[r.pc])};
        if (inst != instructions.end()) {
            inst->op(*inst, r, m);
        } else {
            throw std::runtime_error("Invalid instruction");
        }
    }
}

In this code m is the memory structure and r is the register structure. Because all of the instruction logic is encapsulated within each instruction, this loop is very clean and neat. Adding new instructions is now literally as simple as adding new entries to the instructions array.

|improve this answer|||||
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.