Wasm Builders

Bernard Kolobara
Bernard Kolobara

Posted on

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

Welcome to day 3! Let's get started.

Part 1

You can read the full problem statement here.

Let's start out once again by transforming the input into hexadecimal values so we can embed them inside of the module's memory:

00100          04
11110          1e
10110    ->    16
10111          17
10101          15
...
Enter fullscreen mode Exit fullscreen mode

Looking the the input file, the numbers have up to 12 bits. This means that we need to reserver at least 2 bytes (16 bits) to fit the input. Because we deal with more than 1 byte, we need to encode the values as little endian inside the WebAssembly memory. This is how they are represented inside of WAT:

(module
  (memory 1)
  (data (i32.const 0) "\04\00\1e\00\16\00..."))
Enter fullscreen mode Exit fullscreen mode

We need to count all of the bits in each column. To keep track of the count we could introduce local variables, but to avoid limiting our solution to an exact number of bits (local variables) we can store the count inside of the memory.

Let's move our input 16 * 4 bytes inside the memory and leave the memory locations from 0 to 64 free so we can store up to 16 i32 values inside of them.

(module
  (memory 1)
  (data (i32.const 64) "\04\00\1e\00\16\00..."))
Enter fullscreen mode Exit fullscreen mode

To make our life a bit easier, let's create also a few helper functions that can increment the location of a particular bit or give us back the count:

;; ...
  ;; Load i32 value at position 4 * $bit in memory, add 1
  ;; to it and store the value back at the same position.
  (func $inc (param $bit i32)
    (local $location i32)

    local.get $bit
    i32.const 4
    i32.mul
    local.tee $location
    local.get $location
    i32.load
    i32.const 1
    i32.add
    i32.store)

  ;; Return i32 value at position 4 * $bit in memory.
  (func $count (param $bit i32) (result i32)
    local.get $bit
    i32.const 4
    i32.mul
    i32.load)
;; ...
Enter fullscreen mode Exit fullscreen mode

The local.tee instruction is similar to local.set. It sets the value of a local, but it doesn't remove it from the stack. If it's followed by local.get it simulates a "duplicate top of the stack" operation. WebAssembly doesn't have a dedicated instruction to duplicate the top value on the stack, but there is one for dropping the top value: drop.

The next step is to loop through all values. This code is similar to the previous two days. The only difference is that we start looping from memory position 64 instead of 0. Because we reserve the first 64 bytes for counters:

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

    ;; Start looping from position 64 in memory
    i32.const 64
    local.set $i
    (block $loop_break
      (loop $loop
        ;; increase $i by 2 (bytes)
        local.get $i
        i32.const 2
        i32.add
        local.tee $i
        ;; Load the memory location at $i
        i32.load16_u
        local.tee $value
        ;; Check if it's equal 0 (reached end of the input)
        i32.const 0
        i32.eq
        br_if $loop_break

        br $loop)))
;; ...
Enter fullscreen mode Exit fullscreen mode

We stop the loop as soon as we run into a memory location with the value 0. This could be an issue if our input actually contained values that are 0, but luckily it doesn't and we don't need to deal for now with this edge case.

The recently explained instruction local.tee is used again to temporarily store the value inside of the $value local.

The next step is to loop again through all bits (16 times) for each $value:

;; ...
  (func (export "part_1")
    (local $i i32)
    (local $j i32)
    ;; ...
    (block $loop_break
      (loop $loop
        ;; ...
        br_if $loop_break

        ;; Reset $j to 0
        i32.const 0
        local.set $j
        (block $loop_bits_break
          (loop $loop_bits
            ;; increase $j by 1 and stop when 16 is reached
            local.get $j
            i32.const 1
            i32.add
            local.tee $j
            i32.const 16
            i32.eq
            br_if $loop_bits_break
            br $loop_bits))

        br $loop)))
;; ...
Enter fullscreen mode Exit fullscreen mode

I spent a lot of time on this loop because I kept running into an infinite loop scenario. The issue was that I forgot resetting $j to 0 before each loop. With the introduction of multiple locals it gets really hard to keep a mental model of the whole application in your head and at this low level it's super easy to run into such issues. I generally try to write the code in small increments and test my assumptions by introducing helper local variables to print out some information deeply nested into the program structure. It may help to use a "real" debugger once the problems get more complicated.

Now let's count each bit:

;; ...
        ;; Reset $j to 0
        i32.const 0
        local.set $j
        (block $loop_bits_break
          (loop $loop_bits
            ;; If bit $j is set inside of $value
            ;; increment the counter
            i32.const 1
            local.get $j
            i32.shl
            local.get $value
            i32.and
            i32.const 0
            i32.ne
            (if (then
                  local.get $j
                  call $inc))

            ;; increase $j by 1 and stop when 16 is reached
;; ...
Enter fullscreen mode Exit fullscreen mode

To check if a bit $j is set inside of $value we first create a number with just this bit set using the i32.shl (shift left) instruction.

Let's look at an example how i32.shl works:

i32.const 1 ;; 0...00001
i32.const 4
i32.shl     ;; moves all bits inside of 1 (2nd value
            ;; on the stack) to the left for 4 places
            ;; (the top most value on the stack).
;; This leaves only 0...10000 (16) on the stack.
Enter fullscreen mode Exit fullscreen mode

If we now perform a binary and operation between $value and the left shifted number, the result is going to be either:

  • 0 if the bit is not set inside of $value
  • not 0 if it is set

If it's not 0, we increment the counter for the bit $j. For this we can use the call instruction and the earlier defined $inc function.

Now that we know how many times each bit is repeated, we just need to divide each counter with the number of iterations (($i - 64 offset) / 4 bytes) to determine if the bit 1 shows up more times than 0 (> 0.5). If yes, we add this bit to the local $gamma

Epsilon can be calculated as $gamma xor 0b1111.... The binary value needs to be adjusted, depending how many bits are present in the input values. In the example we had 5 bits (decimal value of 31 => 11111). For the input file it was 12 bits for me (decimal value of 4095).

Here is the whole final loop:

;; ...
      ;; Reset $j to 0
      i32.const 0
      local.set $j
      (block $loop_bits_break
        (loop $loop_bits
          ;; If bit $j is set more times than the number
          ;; of iterations add it to $gamma.
          local.get $j
          call $count
          ;; Convert the value to a f32
          f32.convert_i32_u
          ;; ($i - 64 offset) / 4 bytes
          local.get $i
          i32.const 64
          i32.sub
          i32.const 2
          i32.div_u
          f32.convert_i32_u
          f32.div
          ;; If the division is greater than 0.5 set the bit
          f32.const 0.5
          f32.gt
          (if (then
                ;; Get a number with just the bit $j set
                i32.const 1
                local.get $j
                i32.shl
                local.get $gamma
                i32.add
                local.set $gamma))

          ;; Increase $j by 1 and stop when 16 is reached
          local.get $j
          i32.const 1
          i32.add
          local.tee $j
          i32.const 16
          i32.eq
          br_if $loop_bits_break
          br $loop_bits))
    ;; Calculate epsilon
    local.get $gamma
    i32.const 31 ;; 32 -> 11111
    i32.xor
    local.get $gamma
    i32.mul)
;; ...
Enter fullscreen mode Exit fullscreen mode

We reuse the local $j for the final loop. There are a few new instructions here, like f32.convert_i32_u that converts an i32 value to a f32, so we can do floating point math. Most other operations, like f32.div and f32.gt behave similar to their i32 counterpart, but work with the 32 bit floating point type.

That's it, we are done with the first part of day 3! 🎉

You can see the full code for the solution on GitHub.

End of the series

As you probably noticed, it's getting fairly complicated to hand craft solutions in WebAssembly for the problems. It's starting to take away too much of my time and I will be declaring defeat for now 😊. I would gladly accept PRs if someone manages to solve any of the other days.

I hope you had as much fun following along as I had solving the problems in hand written WebAssembly. Until next time!

Discussion (0)