Day 21 - More machine code analysis

Continuing the theme from days 16 and 19, we are explicitly asked to figure out how the new program works.

Here's my take on the input I was given. The table is annotated with colours, If you are looking at this notebook on Github, you may want to switch to the Jupyter notebook viewer instead.

My input marks register #1 as the IP:

label i opcode op1 op2 reg interpretation
0 seti 123 5 r5 = 123
ANDTEST 1 bani 5 456 5 r5 &= 456
2 eqri 5 72 5
if r5 != 72:
    jmp 1 (ANDTEST)
3 addr 5 1 1
4 seti 0 1
5 seti 0 5 r5 = 0
OUTER 6 bori 5 65536 4 r4 = r5 | 65536 (sets bit 17, 0x10000
7 seti 13431073 5 r5 = 13431073 (product of 2 primes)
INNER 8 bani 4 255 3 r5 += r4 & 255(bottom byte of r4 added to r5)
9 addr 5 3 5
10 bani 5 16777215 5 r5 &= 16777215 (masking r5 to 24 bits, 0xFFFFFF)
11 multi 5 65899 5 r5 *= 65899 (another prime)
12 bani 5 16777215 5 r5 &= 16777215 (masking r5 to 24 bits, 0xFFFFFF)
13 gtir 256 4 3
if r4 < 256:
    jmp 28 (BREAK)
14 addr 3 1 1
15 addr 1 1 1
16 seti 27 1
17 seti 0 3 r3 = 0
DIV256 18 addi 3 1 2 r2 = r3 + 1
19 muli 2 256 2 r2 *= 256
20 gtrr 2 4 2
if r2 > r4:
    jmp 26 (DONEDIV)
21 addr 2 1 1
22 addi 1 1 1
23 seti 25 1
24 addi 3 1 3 r3 += 1
25 seti 17 1 jmp 18 (DIV256)
DONEDIV 26 setr 3 4 r4 = r3
27 seti 7 1 jmp 8 (INNER)
BREAK 28 eqrr 5 0 3
if r5 != r0:
    jmp 6 (OUTER)
29 addr 3 1 1
30 seti 5 0 1

The DIV256 loop effectively divides r4 by 256, the same thing as shifting the register to the right by 8 bits.

Converted to Python code, the above becomes:

# ANDTEST
while True:
    r5 = 123
    r5 &= 456
    if r5 == 72:
        break

r5 = 0
# OUTER
while True:
    r4 = r5 | 0x10000  # sets bit 17
    r5 = 13431073    # a 24-bit value, product of 2 primes, 647 and 20759

    # INNER
    while r4:
        r5 += r4 & 0xFF
        r5 &= 0xFFFFFF  # 24 bit mask
        r5 *= 65899     # another prime
        r5 &= 0xFFFFFF  # 24 bit mask
        r4 >>= 8        # the DIV256 as a right-shift operation

    if r5 == r0:
        break

If we ignore the ANDTEST portion (Python is strictly typed, there are no string-as-numbers issues that the test guards against), then to solve Part 1 all we need to do is set register 0 to the outcome of the OUTER loop run once.

In [1]:
def loop(input: int = 0, init: int = 13431073, perturb: int = 65899):
    # init is the product of 2 primes, 647 and 20759
    # perturb is another prime
    bytes = input | 0x10000 # sets bit 33
    hash = init
    while bytes:
        hash += bytes & 0xFF
        hash &= 0xFFFFFF
        hash *= perturb
        hash &= 0xFFFFFF
        bytes >>= 8
    return hash
In [2]:
print('Part 1:', loop())
Part 1: 3115806

Part 2

Now we need to repeatedly execute the loop until we see the value of r5 repeat, tracking how many operations have been executed for each loop operation.

We don't need an exact operation count however, we just need to count how many times the variable part, the DIV256 loop, runs. That loop is run twice, where it counts up to r4 divided by 256, so r4 // 256 iterations.

In [3]:
i = 0
count = 0
counts = {}
while True:
    count += (i << 8) + (i << 16)  # two >>= 8 loops
    i = loop(i)
    if i in counts:
        break
    counts[i] = count

print('Part 2:', max(counts, key=counts.get))
Part 2: 13959373