Source code can be found on GitHub
Live example on GitHub Pages

WebAssembly and it’s text format

WebAssembly (WASM) is a relatively new (introduced in Chrome in 2017) way to run code on browsers. As MDN puts it:

[…] it is a low-level assembly-like language with a compact binary format that runs with near-native performance and provides languages such as C/C++, C# and Rust with a compilation target so that they can run on the web. It is also designed to run alongside JavaScript, allowing both to work together.

WASM is mainly used only as a compilation target and not something that is written by hand. One of the popular options is emscripten, which provides a toolchain for any language that uses LLVM to be compiled to WASM. Rust also has a very good ecosystem surrounding WASM with tools like wasm-pack and wasm-bindgen which allow close integration between JavaScript and Rust.

WASM uses binary format but it also has text format (WAT) that is used when code has to be read/understood. This is the format that can be seen when debugging .wasm modules in Chrome (and maybe other browsers). Code in either format can be translated to other format (WAT -> WASM, WASM -> WAT) using WebAssembly Binary Toolkit. Using these tools it is possible to write any application in raw WASM (WAT), “compile” it (using wat2wasm) and run it in the browser.

WASM uses a stack-based virtual machine to run it’s instructions. But, it is not a “pure” stack machine as it provides things like locals and globals which can act as regular variables (or registers). These are used (required) for a few things since WASM has no argument support for blocks (e.g. for loops) or stack juggling operations (e.g. pick/dup). For example to duplicate a value on stack, one has to store it in a variable and then read that variable multiple times.

i32.const 34
;; local.tee is equal to local.set and local.get
local.tee $temp
;; load 2 more copies
local.get $temp
local.get $temp
;; stack now has [34, 34, 34]

To get a basic understanding of WASM one can read MDN page about WAT or this “Raw WebAssembly” post. Both cover basic topics required to start writing and understanding most of the WAT code.

Additionally, the best resource for all the available operations, blocks and other pieces of code that can be used is WebAssembly Spec Draft. That document also includes an index with all instructions and hyperlinks to how those instructions are validated and executed. For example i32.shl, which is explained using general “binop” instruction.

FizzBuzz (attempt 1)

Full source can be found on GitHub

If you are not familiar with WASM types and haven’t read articles mentioned before, WASM only has a few types: 4 number types (i[32/64] for 32/64-bit integers and f[32/64] for 32/64-bit floats) and reference types, so writing text (strings) isn’t very straightforward.

On my initial attempt I decided to utilize shared memory and write “fizz” and “buzz” to that memory from JavaScript side. Then provide WASM the addresses of those which it will use when referencing strings. Besides that, WASM function takes memory address parameter where to write the output to and the number parameter until which it should run.

(func $fizzbuzz
  (param $fizzloc i32) ;; address where "fizz" exists in memory
  (param $buzzloc i32) ;; address where "buzz" exists in memory
  (param $outloc i32) ;; address where to start writing output
  (param $range i32) ;; until which number to run
  (result)
  ...

WAT uses S-expressions and these expressions can be written plainly or “folded”. When folded, the stack order goes from right (being top of the stack) to left (being bottom of the stack).

;; ishl(i1, i2) - return the result of shifting i1 left by i2 bits
;; pops from stack as i2, pops from stack as i1
;; shift value of 1 left by 30 bits
i32.const 1
i32.const 30
i32.shl

;; this is equal to above
(i32.shl (i32.const 1) (i32.const 30))

With the function defined, next step is to create a loop which I can use to increment the number. loop is one of the few available control instructions and it is also a block type. Blocks contain a nested sequence of instructions and each block has implicit label that can be used to reference it. Labels start from 0 and increase going outwards. To exit a block (e.g. loop) it is required to branch (br, br_if) out of it to some block label. In case of a loop block, label 0 goes back to the start of the loop acting as continue, in order to exit a loop an outer block has to exist to which I can branch to.

;; local used as iterator since I can't pass stack to block
(local.set $iter (i32.const 1))
(block ;; this has label 1 from inside loop block
  (loop ;; this has label 0 from inside loop block
  ;; branch to 1 if iterator is greater than range
  (br_if 1 (i32.gt_u (local.get $iter) (local.get $range)))

  ...

  ;; increment iterator
  (local.set $iter (i32.add (local.get $iter) (i32.const 1)))

  ;; go back to the start of loop
  br 0
  )
)

Moving to the actual FizzBuzz implementation, I decided to calculate the result of x % 3 == 0 and x % 5 == 0, then encode that using 2 bits and use 3 if’s. Encoding it as 2 bits in i32 it can have these representations:

0b0...00 - not divisible by either 3 or 5
0b0...01 - divisible by only 3
0b0...10 - divisible by only 5
0b0...11 - divisible by both 3 and 5

;; $iter % 3 == 0
(i32.rem_u (local.get $iter) (i32.const 3))
i32.eqz

;; $iter % 5 == 0
(i32.rem_u (local.get $iter) (i32.const 5))
i32.eqz

;; shift result left by 1
i32.const 1
i32.shl

;; bitwise OR on result
i32.or

;; store result in temp and put it back on stack
local.tee $temp

Then for if’s:

  • First one is used to check if its not divisible by 3 or 5 by checking if the result is equal to zero (i32.eqz). If true, stores the value of the number at output address in memory.
  • Second one is used to check if its divisable by 3. This is done with bitwise AND (i32.and) on result and 1 (which is 0b0...01). The result of AND if it is divisible will be 1 (because it’s 0b0...01), which directly satisfies if block condition. If true, stores the value of “fizz” memory address at output address in memory.
  • Third one is used to check if its divisable by 5. This is done by shifting result right by one (i32.shr_u). The result of shifting right if it’s divisible will be 1 (because 0b0...10 -> 0b0...01), which directly satisfies if block condition. If true, stores the value of “buzz” memory address at output address in memory.
;; not divisable by 3 or 5
i32.eqz
(if
  (then
    local.get $outloc
    local.get $iter
    i32.store

    (local.set $outloc (i32.add (local.get $outloc) (i32.const 4)))
  )
)

;; divisable by 3
(i32.and (i32.const 1) (local.get $temp))
(if
  (then
    local.get $outloc
    local.get $fizzloc
    call $addflagaddr
    i32.store

    (local.set $outloc (i32.add (local.get $outloc) (i32.const 4)))
  )
)

;; divisable by 5
(i32.shr_u (local.get $temp) (i32.const 1))
(if
  (then
    local.get $outloc
    local.get $buzzloc
    call $addflagaddr
    i32.store

    (local.set $outloc (i32.add (local.get $outloc) (i32.const 4)))
  )
)

If you’re following along, you might notice that I call a function with fizz/buzz address value called $addflagaddr. This sets a certain bit to 1 indicating that this value should be read as an address and not as a value.

  (func $addflagaddr (param $in i32) (result i32)
    local.get $in
    global.get $flagaddr
    i32.or
  )

;; where $flagaddr is a global
(global.set $flagaddr (i32.shl (i32.const 1) (i32.const 31)))

After all the if’s are evaluated, all that is left is to mark the end of the loop in memory, increment the loop counter and jump back to start of the loop.

;; store value marking the end of the iteration
local.get $outloc
(i32.shl (i32.const 1) (i32.const 30))
i32.store
(local.set $outloc (i32.add (local.get $outloc) (i32.const 4)))

(local.set $iter (i32.add (local.get $iter) (i32.const 1)))

br 0

After function finishes it is now possible to read the memory sequentially and retrieve the result of the fizzbuzz.

To avoid reading memory manually I added an imported function which gets called twice per loop, indicating where memory range of the result starts and where it ends. With this approach I just need to parse the provided slice (though one has to keep in mind that function calls crossing JS/WASM boundry might have some overhead).

(block
  (loop
  (br_if 1 (i32.gt_u (local.get $iter) (local.get $range)))
  (call $markaddr (local.get $outloc))
  ...
  (call $markaddr (local.get $outloc))
  br 0
  )
)

Only thing left is to use JavaScript to read and parse output memory. I will not go into detail about this part, but it can be found here on GitHub.

FizzBuzz (attempt 2)

Full source can be found on GitHub

My first attempt ended up being a bit convoluted, with weird flag bits, around 100 lines of JS code and general lack of clarity. Some parts were just complicated because I made them so, but the general approach wasn’t the most sound either. While finishing up I found out about the data block which allows to initialize a range of memory and WAT allows to use strings instead of raw bytes for this initialization. With this knowledge I decided to take another stab at it, this time trying to make it real simple.

First step was to initialize “fizz” and “buzz” bytes directly in WASM, this is accomplished with mentioned data block.

;; put fizz at memory address 0
(data (i32.const 0) "fizz")
;; put buzz at memory address 0
(data (i32.const 4) "buzz")

The function input this time is a single number, the number until which FizzBuzz should run.

(func $fizzbuzz
  (param $range i32) (result)

I decided to leave result encoding as is. The main change is how output memory is used, instead of having a mix of addresses and numbers, this time it purely is just contiguous memory, where fizz and buzz bytes are just copied to. Though memory.copy instruction required additional flag --enable-bulk-memory to be provided when running wat2wasm.

i32.eqz
(if
  (then
    ;; store number at outloc and increment by 1, limited to 1 byte
    local.get $outloc
    local.get $iter
    i32.store8

    (local.set $outloc (i32.add (local.get $outloc) (i32.const 1)))
  )
)

(i32.and (i32.const 1) (local.get $temp))
(if
  (then
    ;; copy memory range of "fizz" from 0, length 4 to $outloc
    local.get $outloc
    i32.const 0
    i32.const 4
    memory.copy

    (local.set $outloc (i32.add (local.get $outloc) (i32.const 4)))
  )
)

(i32.shr_u (local.get $temp) (i32.const 1))
(if
  (then
    ;; copy memory range of "buzz" from 4, length 4 to $outloc
    local.get $outloc
    i32.const 4
    i32.const 4
    memory.copy

    (local.set $outloc (i32.add (local.get $outloc) (i32.const 4)))
  )
)

One downside in this implementation is that maximum number to which FizzBuzz can run to is limited by Uint8 as the length of “marked data” is used to determine whether it’s a string or a number on JavaScript side.

As with attempt 1, I won’t go into details of JavaScript side, but it can also be found on GitHub. It basically uses length and Uint8Array combined with TextDecoder to read provided memory slices.

With these simple changes size of WAT was reduced by around 10 lines and the JavaScript required to decode is now less than 30 lines in total (excluding WASM setup - 16). Obviously if I were to address the range limitation it would increase a bit, but the overall implementation is a lot more straightforward this time.

Conclusions

Overall I found this to be a fun little challenge. Not just getting familiar with WASM, but also gaining a basic understanding of stack machines and how to work with them without having any registers (lets disregard existance of local’s for time being). While there is still many things to learn and master, I feel like it was good enough foundation to then be able to read, understand WASM and navigate the (draft) spec without many difficulties.

At the end of the day, WASM is not something that is intended to be written by hand, but rather be a compilation target from other higher level languages.