# 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)
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)
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)
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)
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)
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