/ adventofcode2017

Reversing Advent Of Code Day 23

My favorite question in AoC2017 required reverse engineering of a small machine code snippet. Let's examine the snippet and work on reversing it together.

The Code

Here's the code snippet as published on the site:

 1	set b 65
 2	set c b
 3	jnz a 2
 4	jnz 1 5
 5	mul b 100
 6	sub b -100000
 7	set c b
 8	sub c -17000
 9	set f 1
10	set d 2
11	set e 2
12	set g d
13	mul g e
14	sub g b
15	jnz g 2
16	set f 0
17	sub e -1
18	set g e
19	sub g b
20	jnz g -8
21	sub d -1
22	set g d
23	sub g b
24	jnz g -13
25	jnz f 2
26	sub h -1
27	set g b
28	sub g c
29	jnz g 2
30	jnz 1 3
31	sub b -17
32	jnz 1 -23

The machine which runs this snippet has eight registers (marked 'a'..'h'). Its supported commands include: set a value to a register, sub, which substracts a value from a register, mul which multiplies a register value by a number and jnz which jumps if register is not zero.

If you haven't played it already in the AoC itself, take some moments to try to understand what it does. The best way is to save it to a file and adding comments.

Initial Values

Let's start by identifying the first block. A hint given in the question was that the initial value of a affects the behaviour of the program in some way. We also know that implementing if, for and while in assembly would require a jump.

The relevant lines in the first block (with added line numbers) are:

1. let b = 65
2. let c = b
3. jnz a 2
4. jnz 1 5
5. mul b 100
6. sub b -100000
7. set c b
8. sub c -17000

Lins (3) and (4) work together in a way: When a is zero we'll skip line (4) and perform the block. When a is not zero we'll move on to (4) which will then skip the entire block. In a higer level language this structure would look like an if:

let b = 65; // line 1
let c = b; // also 65, line 2

// lines 3-4 translate to this if statement
if ( a != 0 ) {
    // if true - perform lines 5-8
    b *= 100;
    b += 100000;
    c = b
    c += 17000
}
// end of block

Ok so this starts to make sense: The block sets initial values for registers b and c depending on a. In debug mode (a == 0) they'll have a small equal value, but in the general case their values are much higher. Stating the values explicitly gives us this equivalent JavaScript code:

let b, c;
if ( debug_mode ) {
    [b, c] = [65, 65];
} else {
    [b, c] = [106500, 123500];
}

A Nested For Loop

In this mini-language the only interesting instruction is jnz. And two jnzs draw special attention: Line 20 will jump 8 lines back, and line 24 will jump 13 lines back. Jumping back smells like some kind of a loop.

Here's the outer loop with the inner loop folded:

9	set f 1
10	set d 2
11	set e 2
// 12-20 - hidden
21	sub d -1
22	set g d
23	sub g b
24	jnz g -13

Within a nested loop the inner loop could affect the outer loop index or they can be independent. The end of the outer loop reveals its halting condition is the variable d. Lines 21-24 are just a complex way to say "Jump if ++d != b".

Before the loop d's value is set to 2. And it's easy to see d is not modified within the inner loop (lines 12-20). Therefore it's safe to translate the outer loop to a simple for loop:

let f = 1;

for (let d=2; d != b; d++) {
    // lines 12-20
}

That looks nice! Now to the inner loop. Turns out using the same considerations as above we can translate it to another for loop and get the structure:

let f = 1;

for (let d=2; d != b; d++) {
    for (let e=2; e != b; e++) {
        // lines 12-16
    }
}

The Program Logic

The core of the program hides in lines 12-16. Here's the snippet for reminder:

12	set g d
13	mul g e
14	sub g b
15	jnz g 2
16	set f 0

Remember the above code runs in a double nested for loop with d and e each running from 2 to b. A jnz in line 15 is the hint here. It'll set f to zero ONLY IF g is zero. And g will be zero when d * e == b. So basically this inner loop logic says:

if ( d * e === b ) {
    f = 0;
}

And the full snippet we collected so far is:

let b = 65; // line 1
let c = b; // also 65, line 2

// lines 3-4 translate to this if statement
if ( a != 0 ) {
    // if true - perform lines 5-8
    b *= 100;
    b += 100000;
    c = b
    c += 17000
}

let f = 1;

for (let d=2; d != b; d++) {
    for (let e=2; e != b; e++) {
        if ( d * e === b ) {
            f = 0;
        }
    }
}

So f is set to 1 as an initial value and will be set to 0 to indicate that two numbers whose multiplication is b were found. Since it's a boolean value (0 or 1) we know the program doesn't care about how many pairs it finds, and you'd be right to suggest breaking the loop after the first match.

What is f good for?

But what do you do with f? Let's move on to the next block to figure out:

25  jnz f 2
26  sub h -1

Lines 25-26 should by now be familiar: It's our good old if friend. Translated to JavaScript it becomes:

if ( f == 0 ) {
    h++;
}

Closing The Loop

The program ends with another negative jump, meaning another loop. Hiding all inner loops for clarity gives us:

 9	set f 1
// lines 10-26 hidden
27	set g b
28	sub g c
29	jnz g 2
30	jnz 1 3
31	sub b -17
32	jnz 1 -23

This time the halting condition is more complext than our previous for loops, so as a first step we'll use while instead. Line 30 jumps over the loop itself so in JavaScript we can write it as a break. And lines 27-29 are our old friend if again checking if b == c. Translating everything to JavaScript and we get:

while (true) {
    let f=1;
    // lines 10-26 hidden
    if ( b == c ) {
        break;
    }
    b += 17;
}

Or for clarity in the for form:

for (;b != c; b += 17) {
    let f=1;
    // lines 10-26 hidden
}

Now we finally have the full code translated to JavaScript:

let b = 65; // line 1
let c = b; // also 65, line 2

// lines 3-4 translate to this if statement
if ( a != 0 ) {
    // if true - perform lines 5-8
    b *= 100;
    b += 100000;
    c = b
    c += 17000
}

for (;b != c; b += 17) {
    let f=1;

    for (let d=2; d != b; d++) {
        for (let e=2; e != b; e++) {
            if ( d * e === b ) {
                f = 0;
            }
        }
    }
    if ( f == 0 ) {
        h++;
    }    
}

What does it do? The code counts the number of numbers of the form b + 17i (for i >= 0) that are smaller than c and are not primes.