intcode.awk

# Virtual machine for the Intcode computer architecture featured in
# Advent of Code 2019 (a von Neumann-style computer with unbounded
# memory which stores code and data as integer numbers)
#
# There are three main "user-facing" functions:
#   - read_program    -- reads and parses an Intcode program from a file
#   - execute_program -- executes the program
#   - copy_program    -- makes a copy of the program memory
#   - print_program   -- prints a list of code/data values in the memory
#

BEGIN {
    # assign symbolic name to each opcode value
    OPCODE["ADD"]  = 1
    OPCODE["MULT"] = 2
    OPCODE["INP"]  = 3
    OPCODE["OUTP"] = 4
    OPCODE["JMPT"] = 5
    OPCODE["JMPF"] = 6
    OPCODE["LT"]   = 7
    OPCODE["EQ"]   = 8
    OPCODE["BASE"] = 9
    OPCODE["HALT"] = 99

    # assign the number of arguments expected by each instruction
    ARITY[OPCODE["ADD"]]  = 3
    ARITY[OPCODE["MULT"]] = 3
    ARITY[OPCODE["INP"]]  = 1
    ARITY[OPCODE["OUTP"]] = 1
    ARITY[OPCODE["JMPT"]] = 2
    ARITY[OPCODE["JMPF"]] = 2
    ARITY[OPCODE["LT"]]   = 3
    ARITY[OPCODE["EQ"]]   = 3
    ARITY[OPCODE["BASE"]] = 1
    ARITY[OPCODE["HALT"]] = 0

    # assign name to each argument mode type
    MODE["ADDR"] = 0
    MODE["VAL"] = 1
    MODE["REL"] = 2

    # reverse mapping of opcode names to improve readability of logs
    OPCODE[1]  = "ADD"
    OPCODE[2]  = "MULT"
    OPCODE[3]  = "INP"
    OPCODE[4]  = "OUTP"
    OPCODE[5]  = "JMPT"
    OPCODE[6]  = "JMPF"
    OPCODE[7]  = "LT"
    OPCODE[8]  = "EQ"
    OPCODE[9]  = "BASE"
    OPCODE[99] = "HALT"

    # reverse mapping of argument mode names to improve readability of logs
    MODE[0] = "ADDR"
    MODE[1] = "VAL"
    MODE[2] = "REL"
}

# Execute the program stored in the provided memory block
function execute_program(program, input, state, execution,
                         ___, opcode, pointer, parsed, args, modes, i) {

    # if the VM instance wasn't suspended, initialize the program counter
    if (!("pointer" in state)) state["pointer"] = 0

    # reset state signals
    state["halted"] = 0
    state["consumed"] = 0
    state["produced"] = 0

    if (DEBUG >= 2) {
        print "Initial pointer value:", state["pointer"]
        print "Initial input value:", input
        printf("Initial state of memory: ")
        print_program(program)
        print "====="
    }

    for (;;) {
        delete parsed; delete args; delete modes

        parse_instruction(state["pointer"], program, parsed, args, modes, base)
        opcode = parsed["opcode"]
        pointer = parsed["pointer"]
        
        if (opcode == OPCODE["HALT"]) {

            state["halted"] = 1
            state["pointer"] = pointer
            return

        } else {

            if (opcode == OPCODE["ADD"]) {

                program[get(2, args, modes, program, base, "rhs")] =  \
                          get(0, args, modes, program, base, "lhs") + \
                          get(1, args, modes, program, base, "lhs")

            } else if (opcode == OPCODE["MULT"]) {

                program[get(2, args, modes, program, base, "rhs")] =  \
                          get(0, args, modes, program, base, "lhs") * \
                          get(1, args, modes, program, base, "lhs")

            } else if (opcode == OPCODE["INP"]) {

                if (input == "") {
                    if (DEBUG >= 2) print "\nWaiting for the next input!\n---"
                    return
                }

                program[get(0, args, modes, program, base, "rhs")] = input
                state["consumed"]++
                input = ""

            } else if (opcode == OPCODE["OUTP"]) {

                state["output"] = get(0, args, modes, program, base, "lhs")
                state["produced"]++

                # allow not suspending to keep older Intcode puzzles working
                if (execution == "pause") {
                    if (DEBUG >= 2) print "\nSuspending after producing output!\n---"
                    state["pointer"] = pointer
                    return
                }

            } else if (opcode == OPCODE["JMPT"]) {

                if (get(0, args, modes, program, base, "lhs") != 0) {
                    pointer = get(1, args, modes, program, base, "lhs")
                }

            } else if (opcode == OPCODE["JMPF"]) {

                if (get(0, args, modes, program, base, "lhs") == 0) {
                    pointer = get(1, args, modes, program, base, "lhs")
                }

            } else if (opcode == OPCODE["LT"]) {

                program[get(2, args, modes, program, base, "rhs")] =      \
                          int(get(0, args, modes, program, base, "lhs") < \
                              get(1, args, modes, program, base, "lhs"))

            } else if (opcode == OPCODE["EQ"]) {

                program[get(2, args, modes, program, base, "rhs")] =       \
                          int(get(0, args, modes, program, base, "lhs") == \
                              get(1, args, modes, program, base, "lhs"))

            } else if (opcode == OPCODE["BASE"]) {

                base += get(0, args, modes, program, base, "lhs")

            } else {
                print "Invalid opcode: ", opcode
                exit
            }
        }

        state["pointer"] = pointer

        if (DEBUG >= 2) print "-----"
    }
}

function read_program(program) {
    RS = ","
    while (getline > 0) {
        program[NR - 1] = int($1)
    }
}

function copy_program(program, copy, ___, i) {
    for (i = 0; i < length(program); i++) {
        copy[i] = program[i]
    }
}

function print_program(program, ___, i) {
    if (length(program) == 0) {
        print "Given array does not have any items!"
        return
    }

    for (i = 0; i < length(program); i++) {
        printf("%d ", program[i])
    }
    print ""
}

# Parse the next instruction and its operands starting from the given pointer
# to the current state of the program memory. Return the new pointer and the
# opcode in the 'parsed' array, argument values in the 'args' array, and the
# memory/value modes of the arguments in the 'modes' array.
function parse_instruction(pointer, program, parsed, args, modes, base,
                           ___, value, opcode, arity, i, modes_number, modes_parts, n) {
    # memory modes / opcode value
    value = program[pointer]

    # opcode is in the last two bits
    opcode = value % 100
    arity = ARITY[opcode]

    if (DEBUG >= 2) {
        print "Parsing next instruction block:"
        printf("- program pointer: %d\n", pointer)
        printf("- memory block:")
        for (i = pointer; i < pointer + 1 + arity; i++) {
            printf(" %d", program[i])
        }
    }

    if (opcode == OPCODE["HALT"]) {
        args[0] = "NONE"
        modes[0] = "NONE"
    } else {
        # modes are in the bits before the last two (opcode) bits
        modes_number = int(value / 100)

        # if given, split the modes number into an array of individual bits
        if (modes_number) {
            split(modes_number, modes_parts, "")
            for (i in modes_parts) {
                modes[i - 1] = modes_parts[i]
            }
        }

        # missing modes are automatically assumed to be in ADDR mode so
        # prepend them in front of modes already in the instruction
        if (length(modes) < arity) {
            # first shift modes already given
            n = length(modes)
            for (i = n - 1; i >= 0; i--) {
                modes[(arity - n) + i] = modes[i]
                delete modes[i]
            }

            # then prepend a required number of ADDR modes
            n = length(modes)
            for (i = 0; i < arity - n; i++) {
                modes[i] = MODE["ADDR"]
            }
        }

        # opcodes for 'assignment' instructions will have the mode of the
        # final argument as VAL unless already given as mode REL
        if (modes[0] != MODE["REL"] && (  \
                opcode == OPCODE["ADD"]   \
             || opcode == OPCODE["MULT"]  \
             || opcode == OPCODE["INP"]   \
             || opcode == OPCODE["LT"]    \
             || opcode == OPCODE["EQ"])) {
            modes[0] = MODE["VAL"]
        }

        # get values of arguments given their modes, then reverse the
        # order of the modes as originally specified
        n = length(modes)
        for (i = 0; i < n; i++) {
            args[i] = program[pointer + i + 1]
            if (i < n / 2) {
                tmp = modes[i]
                modes[i] = modes[n - i - 1]
                modes[n - i - 1] = tmp
            }
        }
    }

    parsed["pointer"] = pointer + 1 + arity
    parsed["opcode"] = opcode

    if (DEBUG >= 2) {
        print "\nParsed instruction data:"
        printf("- opcode: %d/%s\n", parsed["opcode"], OPCODE[parsed["opcode"]])
        printf("- arguments: ")
        for (i = 0; i < length(args); i++) {
            printf("(value %d, mode %d/%s) ", args[i], modes[i], MODE[modes[i]])
        }
        printf("\n- updated pointer: %d", parsed["pointer"])
        printf("\n- relative base: %d\n", base)
    }
}

# Extract the value of the i-th argument in the program memory depending
# on its memory mode 
function get(i, args, modes, program, base, type) {
    if      (modes[i] == MODE["VAL"])                  return args[i]
    else if (modes[i] == MODE["ADDR"])                 return program[args[i]]
    else if (modes[i] == MODE["REL"] && type == "rhs") return args[i] + base
    else if (modes[i] == MODE["REL"] && type == "lhs") return program[args[i] + base]
    else {
        printf("Invalid memory mode '%d'!", modes[i])
        exit
    }
}