itoa (integer to string) in WebAssembly - Eli Bendersky's website

WAT (WebAssembly Text language) code samples that deal with strings and data passing between WASM and the host via memory are hard to find. The module below is a complete, self-contained example: an itoa function that converts an integer into its string representation, the same operation as its C counterpart.

(module
    ;; Logging function imported from the environment; will print a single
    ;; i32.
    (import "env" "log" (func $log (param i32)))

    ;; Declare linear memory and export it to host. The offset returned by
    ;; $itoa is relative to this memory.
    (memory (export "memory") 1)

    ;; Using some memory for a number-->digit ASCII lookup-table, and then the
    ;; space for writing the result of $itoa.
    (data (i32.const 8000) "0123456789")
    (global $itoa_out_buf i32 (i32.const 8010))

    ;; itoa: convert an integer to its string representation. Only supports
    ;; numbers >= 0.
    ;; Parameter: the number to convert
    ;; Result: address and length of string in memory.
    ;; Note: this result is only valid until the next call to $itoa which will
    ;; overwrite it; obviously, this isn't concurrency-safe either.
    (func $itoa (export "itoa") (param $num i32) (result i32 i32)
        (local $numtmp i32)
        (local $numlen i32)
        (local $writeidx i32)
        (local $digit i32)
        (local $dchar i32)

        ;; Count the number of characters in the output, save it in $numlen.
        (i32.lt_s (local.get $num) (i32.const 10))
        if
            (local.set $numlen (i32.const 1))
        else
            (local.set $numlen (i32.const 0))
            (local.set $numtmp (local.get $num))
            (loop $countloop (block $breakcountloop
                (i32.eqz (local.get $numtmp))
                br_if $breakcountloop

                (local.set $numtmp (i32.div_u (local.get $numtmp) (i32.const 10)))
                (local.set $numlen (i32.add (local.get $numlen) (i32.const 1)))
                br $countloop
            ))
        end

        ;; Now that we know the length of the output, we will start populating
        ;; digits into the buffer. E.g. suppose $numlen is 4:
        ;;
        ;;                     _  _  _  _
        ;;
        ;;                     ^        ^
        ;;  $itoa_out_buf -----|        |---- $writeidx
        ;;
        ;;
        ;; $writeidx starts by pointing to $itoa_out_buf+3 and decrements until
        ;; all the digits are populated.
        (local.set $writeidx
            (i32.sub
                (i32.add (global.get $itoa_out_buf) (local.get $numlen))
                (i32.const 1)))

        (loop $writeloop (block $breakwriteloop
            ;; digit <- $num % 10
            (local.set $digit (i32.rem_u (local.get $num) (i32.const 10)))
            ;; set the char value from the lookup table of digit chars
            (local.set $dchar (i32.load8_u offset=8000 (local.get $digit)))

            ;; mem[writeidx] <- dchar
            (i32.store8 (local.get $writeidx) (local.get $dchar))

            ;; num <- num / 10
            (local.set $num (i32.div_u (local.get $num) (i32.const 10)))

            ;; If after writing a number we see we wrote to the first index in
            ;; the output buffer, we're done.
            (i32.eq (local.get $writeidx) (global.get $itoa_out_buf))
            br_if $breakwriteloop

            (local.set $writeidx (i32.sub (local.get $writeidx) (i32.const 1)))
            br $writeloop
        ))

        ;; return (itoa_out_buf, numlen)
        (global.get $itoa_out_buf)
        (local.get $numlen)
    )
)

Design decisions

• itoa relies on the multi-value feature to return more than one value. Hosts support this feature uniformly at this point.
• The string output is written into memory, and the function returns both the address of that string and its length to the host. That address in WASM's linear memory is hard-coded, since WASM has no built-in dynamic memory allocation. Allocation can be implemented — and higher-level languages do implement it — but for an example of this size a fixed address suffices.
• The module exports its linear memory so the host can read back the string itoa produced.
• The algorithm is straightforward and unoptimized. One O(log(N)) loop determines the output size, and a second loop of the same complexity populates the output.

The accompanying host code, along with instructions for compiling and running the module, lives in the GitHub repository. Many other WAT code samples, including this one, are collected in wasm-wat-samples.

Possible extensions

The current itoa has a couple of limitations that are not hard to remove. For anyone learning WAT, they make reasonable exercises:

• Add support for negative numbers.
• Generalize it to other common bases, such as hexadecimal; this requires an extra parameter.