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
...
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..."))
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..."))
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)
;; ...
The
local.tee
instruction is similar tolocal.set
. It sets the value of a local, but it doesn't remove it from the stack. If it's followed bylocal.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)))
;; ...
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)))
;; ...
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
;; ...
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.
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)
;; ...
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!
Top comments (0)