Zenn
🍉

WebAssembly テキスト形式 (wat) で base64 コマンド作ってみた

2023/12/09に公開
WebAssembly
tech

この記事は WebAssembly Advent Calendar 2023 の4日目の記事です。

今回は軽めの「作ってみた」系記事になります。

WebAssembly にはテキスト形式 (text format) と呼ばれる人間可読な中間表現が用意されています。通常 wasm プログラムは Rust, C などのより高水準な言語からコンパイルして生成されることが多いため、テキスト形式を直接コーディングすることはあまり一般的でないように思います。しかし今回は WebAssembly というビルドターゲットの仕様や特性の理解を深めることを目的に、あえてテキスト形式（拡張子：.wat）で直接コーディングすることでコマンドライン上で実行可能な Base64 エンコーダ／デコーダを実装してみました。

該当のソースコードは下記のリポジトリの wat/ ディレクトリ配下に置いてあります。

https://github.com/etoal83/base64-codec-wasm

またせっかくコマンドラインから実行可能なスタンドアロン wasm プログラムを作ったので、Wasmer registry（旧： WAPM / WebAssembly Package Manager）にも publish してみました。

https://wasmer.io/etoal/base64

Wasmer CLI がインストールしてある環境であれば、以下のようなコマンドで Base64 エンコードをお試しいただけます。

wasmer run etoal/base64 -e encode "Lorem ipsum"
# TG9yZW0gaXBzdW0=

おさらい： Base64 エンコード方式

Base64 は任意のバイト列を印字可能な 64種類の英数記号文字へ変換するエンコード方式です。簡単な例として Hello wasm! という入力文字列を Base64 文字列へエンコードする流れを見てみましょう。

  1. 入力文字列を文字コードに従ってバイト列に変換する
Hello wasm!
↓
|01001000|01100101|01101100|01101100|01101111|00100000|01110111|01100001|01110011|01101101|00100001|
|      H |      e |      l |      l |      o | <SPACE>|      w |      a |      s |      m |      ! |
  1. バイト列を 6 bit ずつに分割する（末尾の 6 bit に満たない部分は 0 で埋める）
|010010|000110|010101|101100|011011|000110|111100|100000|011101|110110|000101|110011|011011|010010|0001 + 00|
|      |      |      |      |      |      |      |      |      |      |      |      |      |      |     ↑末尾が 4 bit しかないので 2 bit 分を 0 で埋める
  1. 変換表 に従って 6 bit を英数字へ 4文字ずつ割り当てる（末尾の 4文字に満たない部分は = で埋める）
|010010|000110|010101|101100| |011011|000110|111100|100000| |011101|110110|000101|110011| |011011|010010|000100|
|    S |    G |    V |    s | |    b |    G |    8 |    g | |    d |    2 |    F |    z | |    b |    S |    E |
↓
SGVs bG8g d2Fz bSE= ← 末尾が3文字しかないので4文字になるよう = で埋める
  1. 連結して Base64 文字列として出力する
SGVsbG8gd2FzbSE=

これで任意のバイト列を印字可能な文字列に変換することができました。デコードの場合は上記の逆の操作をして Base64 文字列からバイト列を復元します。

上記に示したのは Base64 エンコーディングの中でも RFC 4648 に記述されている標準的な変換方式で、この他にも変換後の記号に +, / を含まない URL 安全な文字のみを使用する方式など、いくつかの変形版が存在します。

wat でコーディングする上で苦労したところ

高水準なプログラミング言語であれば前述の Base64 エンコーディング処理を実装するのは言語の組み込みの機能や標準ライブラリで事足りる場合が多いでしょう。一方で、生の WebAssembly は高速性・高可搬性・安全性のトレードオフとして非常に制約が多く、wasm テキスト形式 (wat) 上で使えるデータ型や API は非常に限られています。

ここでは wat でコーディングする上で苦労したところを挙げていきます。

コマンドラインの入出力

WebAssembly 単体では外部との入出力機構を持ちません。入力文字列の受け取りとエンコード結果文字列の出力にはホストとなる wasm ランタイムから入出力用の関数をインポートする必要があります。

今回はブラウザではなくコマンドラインから呼び出せる Base64 エンコーダ／デコーダを作成したかったので、ターミナルの標準入出力とやり取りを行うために WASI (WebAssembly System Interface) の関数を利用しました。

2023年12月現在、WASI は snapshot preview 1 と呼ばれる仕様の API が利用可能です。今回はその中でも以下の 3つの API を利用します。

  • fd_write: ファイルディスクリプタへバイト列を書き込む
  • args_size_get: コマンドライン引数のバイト数を読み取る
  • args_get: コマンドライン引数を線形メモリに読み込む

上記の API の使い方は下記の記事を大いに参考にさせていただきました。

https://qiita.com/Syuparn/items/35fd5e19f50a0a1f7c4e

ビット操作

WebAssembly には高水準言語に組み込まれているような文字列型に相当するデータ型が存在しません。プリミティブなデータ型として利用可能なのは以下の 4つの数値型のみです。

  • i32: 32-bit 整数型
  • i64: 64-bit 整数型
  • f32: 32-bit 浮動小数点数型
  • f64: 64-bit 浮動小数点数型

WASI 経由で取得した文字列は文字コードに従ったバイト列として wasm 内の線形メモリに格納されます。このため、wat プログラム内で文字列を扱うには線形メモリのどのアドレスにどの内容の文字列が格納されているのか、その文字列のバイト数はいくつなのかを常に意識する必要があります。

また、今回実装する Base64 特有の めんどくさいところ 要注意点として、扱う文字列バイトが常に 1バイト = 8 bit とは限らない 点が挙げられます。前述の処理の流れでも見たように、Base64 ではバイト列を 6-bit ずつに分割して処理する工程が含まれるため、ビットマスクとシフト演算を駆使して所望の bit を操作する必要があります。

まず、変換後の Base64 文字列を線形メモリから load できるように、変換表 の順番に従って data セクションに文字列を格納しておきます。

;; Base64 文字列をアドレス[16]以降に格納
(data (i32.const 16) "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/=")

たとえば先程の Hello wasm! を入力文字列として受け取った場合、冒頭の 4 バイトは Hell の4文字分になります。簡単のためにこれらのバイトは線形メモリのアドレス 0 から順番に格納されているとしましょう。

|01001000|01100101|01101100|01101100|
|      H |      e |      l |      l |
|     [0]|     [1]|     [2]|     [3]| ← 線形メモリのアドレス

wat ではこの 4バイトを i32 型整数として読み込み、ビットマスクとの AND 演算で目的の 6-bit を読み取ります。そして、その 6-bit をそのまま Base64 文字が格納されているアドレスを load する引数として使い、変換後の Base64 文字を得ます。例として、最上位の 6-bit から変換後の Base64 文字 1文字を出力用メモリに書き込む処理を抽出すると下記のコードのようになります。

;; 文字列の4バイトを格納する i32 型ローカル変数 $plain_quadbyte を宣言
(local $plain_quadbyte i32) 
;; ビットマスク用の i32 型ローカル変数 $bit_mask を宣言
(local $bit_mask i32)
;; 何文字目の Base64 文字を書き込むかのカウンタ用 i32 型ローカル変数 $i を宣言
(local $i i32)

;; アドレス[0] から4バイト分を $plain_quadbyte に代入
(local.set $plain_quadbyte (i32.load 0))  

;; 上位 6-bit のマスク
(local.set $bit_mask (i32.const 0xfc000000))

;; 変換後の Base64 文字を出力用のメモリアドレスに書き込む
(i32.store8 offset=1024  ;; 書き込み先のアドレス[1024]（メモリレイアウトは自分で決める）
  ;; store 先のアドレス： $i 文字目なので offset + $i バイト
  (local.get &i)
  ;; store するバイトデータ： 線形メモリに格納済みの Base64 文字を load してくる
  (i32.load8_u offset=16
    ;; 読み取った 6-bit を最下位 bit まで桁下げ（右シフト演算）
    (i32.shr_u
      ;; ビットマスクで AND 演算 → 6-bit 読み取り
      (i32.and
        (local.get $quad_plainbyte)
        (local.get $bit_mask))
      (i32.ctz (local.get $bit_mask)))))

上記のコードは $i についてループさせる部分が省略されていますが、実際には入力文字数は可変なので、与えられた文字列のバイトを最後まで処理するようにします。この辺は正直込み入った実装になってしまったので、気になる方は ソースコード の方で詳細をご確認ください。

バイトオーダー

実は先ほど例として挙げた Hello wasm! の冒頭 4バイトですが、これをそのまま i32 型整数として読み取っても 1文字目 H の上位 bit がそのまま i32 の上位 bit として並んでくれるわけではありません。WebAssembly ではリトルエンディアン方式のバイトオーダーを採用しており、バイト列を wat で数値型として扱う際には、バイトオーダーに気をつける必要があります。

バイトオーダーにあまり馴染みのない方向けに軽く例を挙げて説明すると、たとえば 10進数表記で 168_496_141 となる整数があったときに、これを 32-bit（= 4バイト）整数として…

  • ビッグエンディアン方式でメモリに配置 → 0A 0B 0C 0D
  • リトルエンディアン方式でメモリに配置 → 0D 0C 0B 0A

となります。1バイト ＝ 16進数2桁分 をメモリ上での並べ方の単位として、バイトを上位バイトから順に並べる方式がビッグエンディアン、下位バイトから順に並べる方式がリトルエンディアンです。

入力文字列が Hello wasm! の場合、文字列のバイトは下記のように順番に並んでいますが…

|01001000|01100101|01101100|01101100|
|      H |      e |      l |      l |
|     [0]|     [1]|     [2]|     [3]| ← 線形メモリのアドレス

これを i32.load で読み込もうとすると、リトルエンディアン方式でアドレス [3] が上位ビット、アドレス [0] が下位ビットと見なされるため、

  • 期待される値： 0x48656C6C
  • 実際に読み込まれる値： 0x6C6C6548

のように上位ビットと下位ビットが入れ替わった値として読まれてしまいます。

Base64 エンコーディングではバイト列が上記の「期待される値」で並んでいる前提で 6-bit ずつビットマスク処理を行うので、i32.load した後に期待通りのバイトの並びに戻す必要があります。今回は以下のような関数を定義して…

(func $reorder_i32_byte (param $in i32) (result i32)
  ;; 与えられた 4 バイトの入力を、バイト順を逆にして返す
  ;; （※ WebAssembly のバイトオーダーはリトルエンディアンなため）
  ;; e.g. "\0A\0B\0C\0D" --(i32.load)--> 0x0D0C0B0A --($reorder_i32_byte)--> 0x0A0B0C0D
  (i32.or
    (i32.or
      (i32.shr_u (i32.and (local.get $in) (i32.const 0xff000000)) (i32.const 24))
      (i32.shr_u (i32.and (local.get $in) (i32.const 0xff0000)) (i32.const 8))
    )
    (i32.or
      (i32.shl (i32.and (local.get $in) (i32.const 0xff00)) (i32.const 8))
      (i32.shl (i32.and (local.get $in) (i32.const 0xff)) (i32.const 24))
    )
  )
)

バイト列をローカル変数に読み込むときにこの $reorder_i32_byte を通した値を読むことで対応しました。

;; アドレス[0] から4バイト分を $plain_quadbyte に代入
- (local.set $plain_quadbyte (i32.load 0))  
+ (local.set $plain_quadbyte (call $reorder_i32_byte (i32.load 0)))

WebAssembly のバイトオーダーは事前に知識として知ってはいたものの、いざ問題に直面してみると原因がバイトオーダーの考慮漏れということになかなか気づくことができず、入出力の振る舞いから原因究明・問題解決に至るまでに数日要してしまいました…。

まとめ

今回は wat を直接コーディングして Base64 エンコーダ／デコーダを実装してみました。個人的に得られた学びとしては、WebAssembly ターゲットの特性として

  • 外部 I/O の制約と WASI API の使い方
  • 低レベルのビット演算
  • 文字列を扱う際にはバイトオーダーに気をつけること

これらをある程度理解できたことが良い経験になったと思います。

参考書籍

WebAssembly を wat で直接コーディングする入門書としては下記の書籍がとてもオススメです。

https://www.shoeisha.co.jp/book/detail/9784798173597

Discussion