WebAssembly（wat）を手書きする

Tweet

このAdvent Calendarを口実にWebAssemblyを勉強するつもりが気がつけば当日、どころか娘の寝かしつけからの寝かしつけられカウンターが発動し、気がつけば当日23時を過ぎていました。とりあえずプレースホルダー的なエントリを投稿した後で気合で何かでっちあげて翌日AM4時にソースコードのみを追記、そして翌週である本日18日にこの文章を書いています。誠に申し訳ありません。カブクでは主にthree.js周りを担当しているあんどうです。

やったこと

みんなだいすきGame of Lifeのハンドアセンブルをがんばりました。

勉強目的とは言え時間がなく、ツールを覚える時間どころかインストールする時間も惜しいので、テキスト形式のWebAssembryを手書きしました。とても勉強になるし、とりあえず動かすだけなら意外と簡単なのでおすすめです。ライフゲームは「簡単に書けて少しは見て楽しいもの」という基準でなんとなく選んだだけで、特に意味はありません。

準備

テキスト形式のWebAssemblyはバイナリ形式に変換しないと動作を確認できません。まずはそのためのツールをインストールしておきます。インストールに使う時間も惜しいと先ほど書いたばかりですがここはしょうがない。

• https://github.com/WebAssembly/wabt

ここに書かれてあるとおり、git cloneしてmakeします。MacユーザーでCMakeが入っていない場合は先に入れておきましょう。

$ git clone --recursive https://github.com/WebAssembly/wabt
$ cd wabt
$ make

makeが完了したらとりあえず動作確認します。面倒くさいのでパスは通してません。

$ cat 42.wat
(module
  (func $i (import "imports" "imported_func") (param i32))
  (func (export "exported_func")
    i32.const 42
    call $i
  )
)
$ wabt/out/clang/Debug/wat2wasm 42.wat
$ ls -lh 42.*
-rw-r--r--  1 yasushiando  staff   435B 12 15 14:27 42.html
-rw-r--r--  1 yasushiando  staff    78B 12 18 11:02 42.wasm
-rw-r--r--  1 yasushiando  staff   135B 12 15 11:37 42.wat

ドキュメントにあったコードを取ってきてコンパイルしたら動きました。

WebAssemblyの基本

時間もないので基本サンプルコードを見て「あっ・・・（察し）」というスタンスで作業を進めています。ここに書いていることに嘘があったら教えてください。Advent Calendarを口実に勉強するはずだったのに、すでに大事なものを見失っていますが、大義はまず生き残ってから、歴史は勝者が作るのです。

• WebAssemblyのテキスト形式はS式で表現されます。S式がよく分からなければLISPだと思ってください。LISPがよく分からなければサンプルコードから「あっ・・・（察し）」してください。
• WebAssemblyはスタックマシンです。引数的なものをスタックにプッシュして、関数呼び出しに必要なものが揃ったところでcallを呼び出すと処理が実行されます。察してください。
• ローカル変数が使えます。便利。

元にするコード

WebAssemblyを手書きすると言っても何もないところから書き始めるのはハードルが高すぎるので、後でハンドアセンブルすることを前提にまずはJavaScriptで対象の関数を作成します。その際気をつけたことは以下のとおりです。

• WebAssemblyにないのでイテレータは使いません。ループはfor文のみ。
• ハマりたくないので負数は使いません。今回はJavaScriptのUint32ArrayとWebAssemblyのi32で全てまかないます。
• WebAssemblyで使えるデータ構造は1次元配列であるMemoryと連想配列であるTableだけです。しかも現時点ではモジュールごとにそれぞれひとつずつしか持つことができません。そのためデータはすべて1次元配列に入れます。今回はmemoryという一次元配列に以下のようにデータを詰め込んでいます。

  インデックス0

  ライフゲームの世代

  インデックス1〜width*height

  偶数世代のときの盤面

  インデックスwidth*height+1〜2*width*height

  奇数世代のときの盤面

ライフゲーム

一応書いておくとライフゲームは2次元格子で構成される世界で以下のルールに従ってセルが黒くなったり（生）白くなったり（死）する小宇宙です。心が疲れているときには何時間でも眺めていられます。

誕生

死んでいるセルに隣接する生きたセルがちょうど3つあれば、次の世代が誕生する。

生存

生きているセルに隣接する生きたセルが2つか3つならば、次の世代でも生存する。

過疎

生きているセルに隣接する生きたセルが1つ以下ならば、過疎により死滅する。

過密

生きているセルに隣接する生きたセルが4つ以上ならば、過密により死滅する。

ソースコード（JavaScript）

先ほどのルールをそのままコードに落とすと以下のようになりました。2次元のグリッドを1次元の配列に収めていることと、偶数世代と奇数世代でオフセットを切り替えていることに注意すれば特に難しいところはないはずです。

ちなみに当初はmemory[0]に世代数をそのまま格納してモジュロ演算でオフセットを求めるようにしていましたが、WebAssemblyにはモジュロ演算命令がなさそうだったので後で条件文で0と1を交互に収めるように変更しました。

function nextStep() {
  let offset = memory[0] === 0 ? 1 : width * height + 1;
  let nextOffset = memory[0] === 1 ? 1 : width * height + 1;
  for (let y = 1; y < height - 1; y++) {
    for (let x = 1; x < width - 1; x++) {
      let neighbors = 0;
      for (let dy = 0; dy <= 2; dy++) {
        for (let dx = 0; dx <= 2; dx++) {
          if (memory[offset + x + dx - 1 + (y + dy - 1) * width] === 1) {
            neighbors += 1;
          }
        }
      }
      if (memory[offset + x + y * width] === 0) {
        if (neighbors === 3) {
          memory[nextOffset + x + y * width] = 1;
        }
        else {
          memory[nextOffset + x + y * width] = 0;
        }
      }
      else {
        if (neighbors <= 2 || 5 <= neighbors) {
          memory[nextOffset + x + y * width] = 0;
        }
        else {
          memory[nextOffset + x + y * width] = 1;
        }
      }
    }
  }
  memory[0] = memory[0] === 0 ? 1 : 0;
}

ハンドアセンブル

先ほどのJavaScriptのソースコードを機械的にWebAssemblyに置き換えていきます。置き換えに必要なものは一に根性ですが、それ以外に必要なWebAssemblyの仕様とルールは以下の通り。なお今回は変数の型としてi32しか使用しないので、型を指定する部分はすべてi32と直接記述しています。

コメント

;; <コメント>

定数をスタックにプッシュ

(i32.const <値>)

ローカル変数宣言

(local <変数名> i32)

ローカル変数に値を設定

(i32.const <値>)
(set_local <変数名>)

上記は以下のように書くこともできます。

(set_local <変数名> (i32.const <値>))

ローカル変数の値をスタックにプッシュ

(get_local <変数名>)

JavaScriptから呼び出される関数の定義

(func (export <関数名>) (param <引数名> i32) (param <引数名> i32) ...
  <定義>

)

メモリから値を取得

(i32.const <メモリのインデックス>)
(i32.load)

または

(i32.load (i32.const <メモリのインデックス>))

現時点ではメモリはモジュール内にひとつしか存在しないので、使用するモジュールを指定する必要はありません。

メモリに値を設定

(i32.const <メモリのインデックス>)
(i32.const <値>)
(i32.store)

または

(i32.store (i32.const <メモリのインデックス>) (i32.const <値>))

if文

if (cond === 0) {
  <処理>
}
else {
  <処理>
}

上記のようなfor文は以下のように置き換えられます。

(if (i32.eqz (get_local $cond))
  (then
    <処理>
  )
  (else
    <処理>
  )
)

if式の第一引数はもちろん条件式で、i32.eqz以外にもさまざまな式が利用できます。今回利用しているのは以下の5つです。

• i32.eq: スタックの一番上の値と2番目の値が等しい
• i32.eqz: スタックの一番上の値がゼロ
• i32.ge_u: スタックの一番上の値と2番目の値より大きいか等しい
• i32.gt_u: スタックの一番上の値と2番目の値より大きい
• i32.le_u: スタックの一番上の値と2番目の値より小さいか等しい

for文

for (let i = 0; i < max; i++) {
  <処理>
}

上記のようなfor文は以下のように置き換えられます。

(local $i i32)
(local $max i32)
(set_local $i (i32.const 0))
(block $block (loop $loop
  (br_if $block (i32.ge_u (get_local $i) (get_local $max)))

  <処理>

  (br $loop)
))

$block、$loopなどはそれぞれブロック名、ループ名で、br_if式でブロックを脱出できることと、br文でループを繰り返せることを理解しておけばなんとなく察せられるはずです。

JavaScriptから受け取る値の利用

(import <オブジェクト名> <プロパティ名> <型>)

WebAssemblyで定義した関数をJavaScriptからどのように利用するかについては後ほど説明します。

ソースコード（WebAssembly）

上記の仕様とルールに基づいてJavaScriptを気合で書き直すと以下のようになります。コメントで対応するJavaScriptのコードを追記しているので、ゆっくり読めば「あっ・・・」できると思いますが、無駄に長いので別に読む必要はありません。がんばったね、と言いながらTwitterやFacebookでシェアしてくれればそれで十分です。むしろシェアだけしてくれてもいいくらいです。

(module
  (import "console" "log" (func $log (param i32)))
  (import "js" "mem" (memory 1))
  (func (export "nextStep") (param $width i32) (param $height i32)
    (local $step i32)
    (local $offset i32)
    (local $nextOffset i32)
    (local $x i32)
    (local $y i32)
    (local $dx i32)
    (local $dy i32)
    (local $neighbors i32)
    (local $temp1 i32)
    (local $temp2 i32)
    (local $temp3 i32)

    ;; let offset = memory[0] === 0 ? 1 : width * height + 1;
    (set_local $step (i32.load (i32.const 0)))
    (if (i32.eqz (get_local $step))
      (then
        (set_local $offset (i32.const 1))
      )
      (else
        (set_local $offset (i32.add (i32.mul (get_local $width) (get_local $height)) (i32.const 1)))
      )
    )

    ;; let nextOffset = memory[0] === 1 ? 1 : width * height + 1;
    (if (i32.eq (get_local $step) (i32.const 1))
      (then
        (set_local $nextOffset (i32.const 1))
      )
      (else
        (set_local $nextOffset (i32.add (i32.mul (get_local $width) (get_local $height)) (i32.const 1)))
      )
    )

    ;; for (let y = 1; y < height - 1; y++) {
    (set_local $y (i32.const 1))
    (block $yblock (loop $yloop
      (br_if $yblock (i32.ge_u (get_local $y) (i32.sub (get_local $height) (i32.const 1))))

      ;; for (let x = 1; x < width - 1; x++) {
      (set_local $x (i32.const 1))
      (block $xblock (loop $xloop
        (br_if $xblock (i32.ge_u (get_local $x) (i32.sub (get_local $width) (i32.const 1))))

        ;; let neighbors = 0;
        (set_local $neighbors (i32.const 0))

        ;; for (let dy = 0; dy <= 2; dy++) {
        (set_local $dy (i32.const 0))
        (block $dyblock (loop $dyloop
          (br_if $dyblock (i32.gt_u (get_local $dy) (i32.const 2)))

          ;; for (let dx = 0; dx <= 2; dx++) {
          (set_local $dx (i32.const 0))
          (block $dxblock (loop $dxloop
            (br_if $dxblock (i32.gt_u (get_local $dx) (i32.const 2)))

            ;; if (memory[offset + x + dx - 1 + (y + dy - 1) * width] === 1) {
            (set_local $temp1 (i32.sub (i32.add (get_local $x) (get_local $dx)) (i32.const 1))) ;; x + dx - 1
            (set_local $temp2 (i32.sub (i32.add (get_local $y) (get_local $dy)) (i32.const 1))) ;; y + dy - 1
            (set_local $temp3 (i32.add (i32.add (get_local $offset) (get_local $temp1)) (i32.mul (get_local $temp2) (get_local $width))))
            (if (i32.eq (i32.load (i32.mul (get_local $temp3) (i32.const 4))) (i32.const 1)) (then
              ;; neighbors += 1;
              (set_local $neighbors (i32.add (get_local $neighbors) (i32.const 1)))
            ))

            (set_local $dx (i32.add (get_local $dx) (i32.const 1)))
            (br $dxloop)
          ))
          (set_local $dy (i32.add (get_local $dy) (i32.const 1)))
          (br $dyloop)
        ))

        ;; if (memory[offset + x + y * width] === 0) {
        (set_local $temp1 (i32.add (i32.add (get_local $offset) (get_local $x)) (i32.mul (get_local $y) (get_local $width))))
        (if (i32.eqz (i32.load (i32.mul (get_local $temp1) (i32.const 4))))
          (then
            ;; if (neighbors === 3) {
            (if (i32.eq (get_local $neighbors) (i32.const 3))
              (then
                ;; memory[nextOffset + x + y * width] = 1;
                (set_local $temp1 (i32.add (i32.add (get_local $nextOffset) (get_local $x)) (i32.mul (get_local $y) (get_local $width))))
                (i32.store (i32.mul (get_local $temp1) (i32.const 4)) (i32.const 1))
              )
              (else
                ;; memory[nextOffset + x + y * width] = 0;
                (set_local $temp1 (i32.add (i32.add (get_local $nextOffset) (get_local $x)) (i32.mul (get_local $y) (get_local $width))))
                (i32.store (i32.mul (get_local $temp1) (i32.const 4)) (i32.const 0))
              )
            )
          )
          (else
            ;; if (neighbors <= 2 || 5 <= neighbors) {
            (if (i32.le_u (get_local $neighbors) (i32.const 2))
              (then
                ;; memory[nextOffset + x + y * width] = 0;
                (set_local $temp1 (i32.add (i32.add (get_local $nextOffset) (get_local $x)) (i32.mul (get_local $y) (get_local $width))))
                (i32.store (i32.mul (get_local $temp1) (i32.const 4)) (i32.const 0))
              )
              (else
                (if (i32.le_u (i32.const 5) (get_local $neighbors))
                  (then
                    ;; memory[nextOffset + x + y * width] = 0;
                    (set_local $temp1 (i32.add (i32.add (get_local $nextOffset) (get_local $x)) (i32.mul (get_local $y) (get_local $width))))
                    (i32.store (i32.mul (get_local $temp1) (i32.const 4)) (i32.const 0))
                  )
                  (else
                    ;; memory[nextOffset + x + y * width] = 1;
                    (set_local $temp1 (i32.add (i32.add (get_local $nextOffset) (get_local $x)) (i32.mul (get_local $y) (get_local $width))))
                    (i32.store (i32.mul (get_local $temp1) (i32.const 4)) (i32.const 1))
                  )
                )
              )
            )
          )
        )

        (set_local $x (i32.add (get_local $x) (i32.const 1)))
        (br $xloop)
      ))
      (set_local $y (i32.add (get_local $y) (i32.const 1)))
      (br $yloop)
    ))

    ;; memory[0] = memory[0] === 0 ? 1 : 0;
    (if (i32.eqz (i32.load (i32.const 0)))
      (then
        (i32.store (i32.const 0) (i32.const 1))
      )
      (else
        (i32.store (i32.const 0) (i32.const 0))
      )
    )
  )
)

こんなに長くなっちゃって何が嬉しいんだと思うかもしれませんが、バイナリ（wasm）に変換すればサイズはちゃんとJSの25%ほどになっています。実行速度は分かりませんが、ファイルダウンロード後に実行を開始するまでの時間も短くなっているはずです。

$ wabt/out/clang/Debug/wat2wasm gol.wat
$ ls -lhS gol.*
-rw-r--r--  1 yasushiando  staff   5.4K 12 16 04:18 gol.wat
-rw-r--r--  1 yasushiando  staff   1.7K 12 16 03:18 gol.js
-rw-r--r--  1 yasushiando  staff   486B 12 16 04:14 gol.wasm

実行

WebAssemblyの関数を実行するにはJavaScriptから呼び出す必要があります。JavaScript側のソースコードは以下のとおりです。

const width = 18;
const height = 11;
const memory = new WebAssembly.Memory({initial:1});
const cells = new Uint32Array(memory.buffer, 0, width * height * 2 + 1);
// cellsに初期状態を設定（省略）

// コンソールに結果を表示
function show() {
  const mem = new Uint32Array(memory.buffer);
  const offset = mem[0] === 0 ? 1 : width * height + 1;
  let world = '\n';
  for (let y = 0; y < height; y++) {
    let line = '';
    for (let x = 0; x < width; x++) {
      line += mem[offset + x + y * width] === 1 ? '*' : ' ';
    }
    world += line + '\n';
  }
  console.log(world);
}

// WebAssemblyに受け渡す処理とメモリ
var importObject = {
  console: {
    log: console.log
  },
  js: {
    mem: memory
  }
};

// wasmの取得、コンパイル、関数呼び出し
fetch('gol.wasm').then(response =>
  response.arrayBuffer()
).then(bytes =>
  WebAssembly.instantiate(bytes, importObject)
).then(results => {
  const nextStep = results.instance.exports.nextStep;
  setInterval(() => {
    nextStep(width, height);
    show();
  }, 1000);
});

WebAssembly.instantiate関数でwasmをコンパイルできます。この関数の第二引数はWebAssembly内でimportされるオブジェクトです。余談ですが、ここで{console: {log: console.log}}を渡しておくとWebAssembly側の変数をコンソールに表示できてプリントデバッグがはかどります。

instance.exports.nextStepなどとしてWebAssemblyの公開関数を取り出して利用できます。

WebAssembly.instantiateの代わりにWebAssembly.instantiateStreamingを使用すると読み込みとインスタンス化を同時に行えるはずですが、ファイルのmimetypeを設定する必要があり、今回は簡易の開発サーバーでホストしていたので使用しませんでした。

デモ

デモはこちらです。結果はコンソールに表示されます。

https://technohippy.github.io/wasmgol/

さいごに

JavaScriptからWebAssemblyへの置き換えは考えていたよりもずっと簡単でした。WebAssemblyにコンパイルできるオレオレウェブ言語を作成してみても面白いかもしれません。ていうか多分やる。

株式会社カブクではWebGLやWebAssemblyを業務で使用したいメンバーを募集しています。