Advent of Code '21 in hand written WebAssembly: Day 1

Part 1

The first problem of Day 1 requires us to go through a list of numbers and count how many times the value increases.

You can read the full problem statement here.

Attempt 1 (Input on the stack)

My first idea here was just to manually insert the input values onto the stack by embedding them into the module with a i32.const prefix. Something like this:

(module
  (func (export "puzzle_1") (result i32)
    i32.const 0xFFFFFF
    i32.const 199
    i32.const 200
    i32.const 208
    i32.const 210
    ;; ...

    ;; Now pop them one by one and count increases until
    ;; the sentinel value of 0xFFFFFF is reached.
    )))

The first issue here would be that the values come in the opposite order when we pop them from the stack, but this doesn't actually matter because we could count the increases (decreases) even in the opposite order.

The bigger issue is that the WebAssembly security model doesn't allow us to generate such a module. It wouldn't be valid WebAssembly.

Each WebAssembly function must have a deterministic stack depth. We can't write a function that sometimes leaves 2 values on the stack, but sometimes just 1. This would automatically be changing the return type of the function too. Because the number of loop iterations is unknown before execution time, the number of arguments left on the stack is unknown too and this makes the generated module invalid.

I already prepared a nice regex (s/^/i32.const /g) in my editor to prefix the input file that I now had no use for anymore 😢.

If we can't embed the input values onto the stack, lets try to put them inside of a memory.

Attempt 2 (Input inside of a Memory)

A WebAssembly module can have 0 or more memories. You define a memory by giving it a minimum and optionally a maximum size of wasm pages (1 wasm page = 64Kb).

(module
  ;; A memory with a minimum size of 10 * 64 Kb
  (memory 10))

You can also predefine some data inside the memory using the data segments:

(module
  (memory 10)
  (data (i32.const 0) "Some value \01\02"))

The data segments requires an offset (here set to 0) where the data will start inside of the memory; and a value in form of a string. The string characters will be turned into equivalent utf8 values and stored inside the memory. If an escape sequence prefixed with a \ character appears inside of the string, it represents a raw integer hexadecimal value (1 byte).

The biggest value inside of our input set is 3770. This means that all the numbers could fit inside of a 2 bytes space. However, to be future proof we are going to expand all numbers to 4 bytes and use the 4 byte memory load instruction (i32.load).

WebAssembly is a little endian system, meaning that the lower bytes are stored at a lower memory address.

This requires us also to revers the byte order inside of our input. To summarise the transformations performed on the input here:

1. Convert decimal values to hexadecimal (e.g 3770 -> eba)
2. Add padding to expend value to 4 bytes (e.g. eba -> 00000eba)
3. Turn into little endian memory order (e.g. 00000eba -> ba0e0000)
4. Add \ in front of each byte (e.g. ba0e0000 -> \ba\0e\00\00)

We finally have all the values inside of our module:

(module
  ;; 64Kb is enough to fit all the input values
  (memory 1)
  ;; Pre-initialise memory with the input values
  (data (i32.const 0) "\ba\0e\00\00..."))

The next step is to loop through them:

;; ...
(func (export "part_1")
    (local $i i32)

    (block $loop_break
      (loop $loop
        ;; increase $i by 4 (bytes)
        local.get $i
        i32.const 4
        i32.add
        local.set $i

        ;; Load the memory location at $i
        local.get $i
        i32.load

        ;; Check if it's equal 0 (reached end of the input)
        i32.const 0
        i32.eq
        br_if $loop_break

        ;; Jump to beginning of the loop
        br $loop)))
;; ...

Let's break down the code to take a closer look at what's happening here.

WebAssembly functions can hold local variables (local $i i32). We can use them to temporarily store the top most stack value into them (local.set) or push their content onto the stack (local.get).

You will also notice that the code is really verbose. Just to increment a local value you need to execute 4 instructions:

;; Put the value onto the stack
local.get $i
;; Add 1 onto the stack
i32.const 1
;; Add the top stack values together
;; The result is going to end up on the stack
i32.add
;; Take the result from the stack and write it
;; into the local variable $i
local.set $i

Control flow inside of WebAssembly is also handled in an interesting way. There is no program counter, WebAssembly chooses structured control flow instead. The bytecode only allows jumps to specific points in the program. This eliminates a whole set of security issues, but also makes the life for us a bit more complicated.

You need to define blocks of code where you can jump to; and you also need to specify the exact amount of stack slots that the block expects on entrance and the number of slots that the block leaves on exit:

(block (param i64) (param i64) (result i32)
  ...

The same is true for loops. This is a consequence of the earlier mentioned characteristic that the stack depth needs to be deterministic even before execution. In this code we didn't need to worry about this, as we are not returning a value out of the loop.

At this point you may ask yourself, what's the difference between jumping to a block or loop label? I think this StackOverflow answer explains it perfectly:

A br to a block label jumps to the end of the contained instruction sequence -- it is a behaves like a break statement in C.

A br to a loop label jumps to the start of the contained instruction sequence -- it behaves like a continue statement in C.

The former enables a forward jump, the latter a backwards jump. Neither can express the other.

That's why we wrap a loop with a block in the code, to be able to jump out of the loop.

Another characteristic of WebAssembly is that locals, globals and the memory is pre-initialised to 0. We use this fact to determine the end of our loop. Once our loop reaches a value in memory of 0, we stop it. The variable $i is incremented by 4 on each loop iteration, because we use i32 values (4 bytes) in memory for each number.

The only thing left now is to count the increases:

;; ...
  (func (export "part_1") (result i32)
    (local $i i32)
    (local $previous i32)
    (local $increases i32)

    ;; Load first value onto the stack
    i32.const 0
    i32.load
    ;; Save it inside the $previous local
    local.set $previous

    (block $loop_break
      (loop $loop
        ;; increase $i by 4 (bytes)
        local.get $i
        i32.const 4
        i32.add
        local.set $i

        ;; Load the memory location at $i
        local.get $i
        i32.load
        ;; Check if it's equal 0 (reached end of the input)
        i32.const 0
        i32.eq
        br_if $loop_break

        ;; Load again the memory location at $i
        local.get $i
        i32.load
        ;; Compare if it's bigger than the $previous value
        local.get $previous
        i32.gt_u ;; Greater than unsigned
        (if 
          (then
            ;; Increment $increases
            local.get $increases
            i32.const 1
            i32.add
            local.set $increases))

        ;; Load once again the memory location at $i and
        ;; save it under $previous for the next iteration
        local.get $i
        i32.load
        local.set $previous
        ;; Jump to beginning of the loop
        br $loop))

    ;; Return the value inside the $increases local
    local.get $increases)
;; ...

If we run the module through wasmtime we get the solution, in my case it's 1581.

There are some optimisations that can be performed on our solution. For example, we load 3 times each value from the memory. First to compare it to 0, then to compare it to the $previous value and in the end to store it inside of $previous. We could only load it once into a local to save some of the work. I will leave this optimisation as an exercise to the reader.

This was fun! Let's try to solve the second part.

Part 2

For the second part we can reuse most of the first solution, but instead of loading one number at a time, we want to load a sum of 3 numbers. However, we will still incrementing the $i variable by 4 (one 32 bit integer) to get a sliding window.

Instead of starting out by loading the first memory location into $previous, we can just load the sum of the first 3:

;; Load first value onto the stack
i32.const 0
i32.load
;; Load second value onto the stack
i32.const 4
i32.load
;; Load third value onto the stack
i32.const 8
i32.load
;; Add them together
i32.add
i32.add
;; Save it inside the $previous local
local.set $previous

The rest of the solution also just changes slightly. Instead of dealing with the next memory location, we first load the sum of the next 3 into the $current local and treat it as the next memory location:

;; increase $i by 4 (bytes)
local.get $i
i32.const 4
i32.add
local.set $i
;; Add values at $i, $i+4 & $i+8 together
;; and save them inside of current
local.get $i
i32.load
;; $i+4
local.get $i
i32.const 4
i32.add
i32.load
;; $i+8
local.get $i
i32.const 8
i32.add
i32.load

i32.add
i32.add
local.set $current

The majority of the rest of the code stays the same. And we are done 🎉! This wasn't too hard.

You can check out the full code for both problems on GitHub!

Now let's do Day 2.