Tag: code

My best languages ​​are Python and Rust, but I want to improve my knowledge of C ++, so I decided to try the Advent of Code 2019 in C ++. I haven't encountered too many problems so far, but I want to know what I'm doing, which is subtly (or not so subtly) wrong.

The following program is my solution for the 9th day problem. It is essentially an interpreter for an invented machine language called intcode. The intcode specification is spread across day 2, day 5 and day 9. The day 7 issues had additional limitations that may explain some of my architectural decisions.

It is not my intention to summarize the entire Intcode specification, but here are some key points about the Intcode language and the computer:

• Intcode programs require common command and data storage, and most or all of the sample programs use it.
• An intcode computer has two registers: the command pointer, which I have called the program counter (_pc) and the relative base that I called the stack pointer (_sp). Both are defined to be initialized to zero.
• Intcode instructions have a variable size and the program counter must be increased by the width of the current instruction in each cycle.
• Intcode statements support arguments with three different addressing modes: immediate, "positional" (ie direct addressing) and "relative" (ie batch-related addressing). The addressing modes of all arguments of an instruction are encoded in the high digits of its opcode.
• To solve certain problems, you must start several Intcode computers, connect their inputs and outputs, and run them simultaneously (though not literally at the same time).
• I created mnemonics for each of the intcode instruction opcodes when I came across them and invented an assembly language for debugging purposes. these are not part of the specification, but you can observe them by commenting out the relevant lines.

My code passes all tests on the website. It's more about eradicating bad habits and avoiding pitfalls than whether the Intcode logic itself is right.

#include 
#include 
#include 
#include 
#include 
#include 
#include 

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(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 _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 _mem;
    size_t _pc;
    size_t _sp;
    std::ostream& _out = std::cout;
    std::istream& _in = std::cin;
    //std::optional _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 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 is prone to error, buggy, or just "strange" to an experienced C ++ programmer. I've seen and selected different C ++ styles in action, which makes sense to me, but that does not mean that they make sense overall.

Some specific things that seem a bit awkward are:

• Cpu::run() Returns either when the program stops or waiting for input. (The customer can call Cpu::is_halted To distinguish these cases.) When the program was waiting for the input, I had to call _in.clear() Within execute to clear the EOF flag from the stream. This seemed a little risky to me because I may be deleting an error flag instead. I suppose I could test for EOF or errors separately, but it just seems a bit cumbersome. Is there a better way to structure the input that I wasn't thinking about?

• I tried to find a way to write one value Function that interprets an argument contextually as input or output, 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 the immediate addressing mode is not allowed), while arguments 1 and 0 would be parsed as input parameters (for which any addressing mode is allowed). Maybe that was a stupid idea; anyway i thought it would be possible to send it via the constness of thisbut I couldn't find a way to do it. Still, if 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 use enum for opcodes and enum class for addressing modes, not really rhyme or reason. I should have used enum class or enum for both? With enum class It seems that you have to give them all explicit values ​​if you want to static_cast work consistently. I did not find much information about this topic online.

• friend ostream& operator<<: Is this a good way to create a debugable output format?

• is const std::string& a good way to accept a string argument if you don't need to mutate or copy it? I tried std::string_view but apparently you can not make a from a char *,

• One of the mistakes I made was as follows: lvalueWhen I tested whether the size of the memory needed to be changed, I used > instead of >=, This caused a subtle error that was only triggered if the address to be written was exactly one after the end of the vector. Valgrind could not detect this error (at least not with standard options). Is there a compiler switch that I can enable, or another tool that makes it easy for me to detect out-of-range index errors while debugging?

• The vectors for Arguments in Instruction seem a bit extra. I want to save them in a row Instruction, and save on the assignment, since the maximum size is only 3. Is there a typical solution to this type of problem? The only thing I could imagine was an array of 3 optionals and that seemed difficult.

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 be printed after stdout (but with line breaks instead of commas).