You fixed the colours of the bags yesterday) and security allowed you to leave the baggage section and go get your ice cream before you board your next flight. On the flight the kid next to you recognizes you as the great hacker you are, and asks you to fix a problem with the handheld game console. Go and hack the bootloader while no documentation is available because the mobile internet is off. Turns out someone coded an infinite loop into the bootloader, and missed that fact during testing. What testing, do you ask? Well, let’s not jump too deep into details, you have to hack a bootloader and make a kid happy. It’s Christmas soon, after all! And your cocktail is waiting!
Task 1: The assembler instructions are easy to read, to make the kid happy you just have to figure out the state of the accumulator before the bootloader repeats its set of instructions into another great infinite loop. Not sure how that fixes the problem, but ok.
Task 2: The instruction list is corrupt. But not in the way you think. The code is supposed to produce a buffer overrun, jump outside of the instruction list and stop. Modern operating systems would prevent this and abort the program, here that is “normal termination”. Change exactly one
jmp into a
nop or vice versa, but do not change the operand. Whichever change aborts the program by jumping outside the code - the accumulator state is what we are looking for. Hopefully the number is high enough to pay for all the cocktails!
Verify that I have data:
In order to do something useful with the input, I need to split the instructions into opcode and operator. That’s easy, they are always separated by a space. A similar way was used yesterday to split the text into parts.
The CTE is similar to what I used yesterday: loop over the data in the table, and split it by the space. The
_day8_split_data CTE does the split, the
day8_split_data extracts the data from the array and presents a clean result. Again, that can be combined into a single query, but this way the processing is better shown, The resulting data:
The instruction set reminds me when I first started programming, a 6502 CPU in a CBM Model 4032. Basic was too slow, but assembler documentation for the 6502 CPU was available (mostly for the C64 though, but the 6502 and 6510 CPUs are almost identical). Using the one accumulator and two index registers along with the program counter was quite a thing back then. And it was fast, compared to the basic programs on the same machine!
The task at hand is to find out when the next iteration of an infinite loop starts. For this I need to know how many instructions are in the list:
And then “emulate” what the CPU is doing. There are only three commands in the list:
- nop: No Op - does nothing
- jmp: Jump forward or backward, depending on the operand
- acc: Add or deduct to/from the accumulator, depending on the operand
The “nop” command can be ignored. The
jmp command then changes the program counter, and the
acc program the state of the accumulator. What’s not checked here: out of bound. The
jmp command could possibly jump to a position before the start, or after the end of the list. And the accumulator could overrun or underrun its data type. These are typical scenarious for buffer overflow errors, and modern systems should detect this and then abort.
The funny thing: nothing ever happens, at all. The accumulator is changed, but there are no checks, or other instructions. It’s just shifting bits around in the accumulator.
Above code starts at position
1, with the accumulator set to
0. It then uses the
jmp commands to modify the program counter and the accumulator.
Pour all of this together, keep a state for the
program_counter, which is the position which was “executed” in the list. Once it repeats the job is done and
accumulator holds the result:
This loops quite a few times, but only the first run is what we are looking for:
Let’s do opcode switching on the fly, because, you know, emulating a CPU in another CPU …
When I encounter a
jmp or a
nop I switch them. Otherwise the
run CTE function for task 2 is pretty much similar to task 1. I need to run recursive over the instructions to find the missing one, the INNER JOIN changes into a LEFT OUTER JOIN for that. And the “other” instruction is stored in
$new_opcode. The first part of the CTE also excludes
acc instructions from evaluation by listing the two opcodes which should be switched.
$outside is a flag which shows if the program counter goes outside of the instruction list. According to the instructions there is only one possibility for this.
The accumulator state once the code overruns: