VP 24: Assembly Code (15 pts + 10 extra)

Background

This project uses a very simplified form of assembly code, which resembles the sort of code found in early 8-bit microprocessors.

What You Need

Any computer with Python 3. You can also use an online Python environment, such as https://colab.research.google.com

Our Assembly Code

There are only three instructions in this assembly code:

nop +0 -- no operation. Do nothing and proceed to the next instruction. The parameter doesn't matter.
acc +1 -- change the accumulator value. This instruction adds one to the accumulator. The parameter can be any positive or negative integer, so acc -3 would subtract 3 from the accumulator.
jmp +4 -- skips to a new instruction. The parameter can be any positive or negative integer, so jmp -3 would move back three instructions.

For example, consider this program:

nop +0 acc +1 jmp +4 acc +3 jmp -3 acc -99 acc +1 jmp -4 acc +6

These instructions are visited in this order, explained below the code:

nop +0 | 1 acc +1 | 2, 8(!) jmp +4 | 3 acc +3 | 6 jmp -3 | 7 acc -99 | acc +1 | 4 jmp -4 | 5 acc +6 |

The accumulator starts at zero.

nop does nothing and proceeds to the next instruction.
acc +1 increases the accumulator from 0 to 1
jmp +4 skips ahead 4 instructions
acc +1 increases the accumulator from 1 to 2
jmp -4 skips back 4 instructions
acc +3 increases the accumulator from 2 to 5
jmp -3 skips back 3 instructions

After these instructions, the program repeats the second instruction. This means it's stuck in an endless loop.

Problem Statement

Given an assembly language program, execute it until it repeats an instruction.

The result is the value of the accumulator when the first instruction repeats. In the example above, the result is 5.

VP 24.1: Result (15 pts)
Use the program in this file:
https://samsclass.info/COMSC132/proj/VP24b
Hint: to see how to read data from a file, see project VP 22.
Run the program until the first repeated instruction.
The accumulator value at that point is the flag.

Fixing the Program

The program should not endlessly loop. Instead, it should execute instructions until it moves to one instruction below the code provided to you.

To fix the program, only one command needs to be changed.

Somewhere in the program, either a jmp is supposed to be a nop, or a nop is supposed to be a jmp. No acc instructions should be changed.

The program is supposed to terminate by attempting to execute an instruction immediately after the last instruction in the file. By changing exactly one jmp or nop, you can repair the boot code and make it terminate correctly.

For example, consider the same program from above:

nop +0 acc +1 jmp +4 acc +3 jmp -3 acc -99 acc +1 jmp -4 acc +6

If you change the first instruction from nop +0 to jmp +0, it would create a single-instruction infinite loop, never leaving that instruction. If you change almost any of the jmp instructions, the program will still eventually find another jmp instruction and loop forever.

However, if you change the second-to-last instruction (from jmp -4 to nop -4), the program terminates! The instructions are visited in this order:

nop +0 | 1 acc +1 | 2 jmp +4 | 3 acc +3 | jmp -3 | acc -99 | acc +1 | 4 nop -4 | 5 acc +6 | 6

After the last instruction (acc +6), the program terminates by attempting to run the instruction below the last instruction in the file. With this change, after the program terminates, the accumulator contains the value 8 (acc +1, acc +1, acc +6).

VP 23.2: Fixed Code (10 pts)
Use the program from the previous flag.
Fix the program so that it terminates normally by changing exactly one jmp (to nop) or nop (to jmp).
Find the value of the accumulator after the program terminates. That's the flag.

Source

Adapted from the Advent of Code.

Posted 9-6-24
Hint and video added 9-11-24