JavaScript で WebAssembly のバイナリを直接書き出してみた

# はじめに

趣味の自作言語で WebAssembly を吐いてみようかなと思いました。が、WebAssembly の仕様書を読むだけで理解するのは困難です。そこで手を動かしながら仕様書を少しずつ追いかけていくことで理解しようと思いました。せっかくなので誰か（主に数週間後の自分）の役に立てばなあ、と思い思考の記録を取った次第です。

# 参考文献

* [WebAssembly Specification](https://webassembly.github.io/spec/core/index.html)
  * 仕様書です

# WASM のバイナリの構造

WASM のバイナリは module です(これは正確な言い回しではないかもしれません。[Overview の Modules](https://webassembly.github.io/spec/core/intro/overview.html#module)をよんで)。module の binary encoding は[Modules](https://webassembly.github.io/spec/core/binary/modules.html#binary-module)に書いてあります。

ごちゃっとしていて圧倒されますが、以下の3点を押さえると読みやすくなると思います。

* module は magic -- version -- sections の構造になっている
* section には様々な種類があるが、並び順は決まっている
* ただし customsec はどこにでも差し込めるようになっている

# 最小の例

とりあえず最小の module を作ってみます。よく読むと module に必須の要素は magic と version だけです。というわけで magic('\0asm') と version(1000) だけからなるバイト列を渡してみましょう。

```javascript
const bufferSource = Uint8Array.of(0x00, 0x61, 0x73, 0x6d, 0x01, 0x00, 0x00, 0x00);
const importObject = {};
WebAssembly.instantiate(bufferSource, importObject).then(x => {
    console.log(x)
});
```

```shell-session
> node gen-wasm-bin.js
{ instance: Instance {}, module: Module {} }
```

instance ができました。
export された関数が一つもないので何もできませんが、とりあえず正しく instance を作成できました。

[++ ここまでのソース ++](https://github.com/usm-takl/gen-wasm-bin.js/blob/fed5e52d87d2fce6c4f7d1725317ee1361cbdf34/gen-wasm-bin.js)

# makeMagic と makeVersion

`Uint8Array.of` に直書きしていくのも何ですので、関数化しておきましょう。

```javascript
function makeMagic() {
    return [ 0x00, 0x61, 0x73, 0x6d ]; // '\0asm'
}

function makeVersion() {
    return [ 0x01, 0x00, 0x00, 0x00 ];
}
```

```javascript
const bufferSource = Uint8Array.from(makeMagic().concat(makeVersion()));
const importObject = {};
WebAssembly.instantiate(bufferSource, importOject).then(x => console.log(x))
```

```shell-session
> node gen-wasm-bin.js
{ instance: Instance {}, module: Module {} }
```

[++ ここまでのソース ++](https://github.com/usm-takl/gen-wasm-bin.js/blob/fedaba00dab96457eb5526d8e58110ce5bdfc3f4/gen-wasm-bin.js)

# typesec を作成

次は section を作ります。様々な section がありますが、仕様書を眺めてみて一番簡単そうな section から作っていきましょう。
ざっと見ると typesec がよさそうです。typesec は関数の型を登録する section です。他の section への参照も持たないので、試しに作ってみるにはうってつけでしょう。
定義は[ここ](https://webassembly.github.io/spec/core/binary/modules.html#binary-typesec)です。とりあえず引数0個・返却値0個の関数型のみを持つ typesec を作ってみましょう。

```javascript
function makeTypeSec() {
    return [
        0x01, // section id: type section
        0x04, // section size
        0x01, // length of vector
        0x60, // this type is a function
        0x00, //   that takes no parameters
        0x00, //   that returns no results
    ]
}

const bufferSource = Uint8Array.from(makeMagic().concat(makeVersion()).concat(makeTypeSec()));
const importObject = {};
WebAssembly.instantiate(bufferSource, importObject).then(x => {
    console.log(x)
});
```

概要としては、

* 1行目は section id
  * 0x01 は typesec の id
* 2行目は section の本体のサイズ(バイト数)
  * section のヘッダ部分は含まない
* 3行目以降は functype の vec
  * 3行目は vec の要素数(今回は1)
  * 4行目以降は functype
    * functype は 0x60 - 引数のvec(今回は長さ0) - 返却値のvec(今回は長さ0)

という感じです。
というわけで実行してみましょう。

```shell-session
> node gen-wasm-bin.js
{ instance: Instance {}, module: Module {} }
```

型を登録しただけで何もできませんが、とりあえず instance の作成はできます。

# tree

typesec の構造ですが、明らかにネスト構造が見られます。
他の section も同様です。
次のように書けると嬉しそうです。

```javascript
function makeTypeSec() {
    return [
        0x01, // section id: type section
        0x04, // section size
        [
            0x01, // length of vector
            [ 0x60, 0x00, 0x00 ] // function type
        ]
    ]
}
```

というわけでツリー状の配列を Uint8Array にする関数を作っておきましょう。

```javascript
function countLeaves(body) {
    let length = 0;
    for (b of body) {
        if (b instanceof Array) length += countLeaves(b);
        else length += 1;
    }
    return length;
}

function u8tree2u8array(tree) {
    const a = new Uint8Array(countLeaves(tree));
    function emit(node, i) {
        for (child of node) {
            if (child instanceof Array) i = emit(child, i);
            else a[i++] = child;
        }
        return i;
    }
    emit(tree, 0);
    return a;
}
```

なんのことはない、普通の再帰関数です。試しに動かしてみましょう。

```shell-session
> node gen-wasm-bin.js
{ instance: Instance {}, module: Module {} }
```

instance ができました。

[++ ここまでのソース ++](https://github.com/usm-takl/gen-wasm-bin.js/blob/fedaba00dab96457eb5526d8e58110ce5bdfc3f4/gen-wasm-bin.js)

# 最小の関数を定義する

型が定義できたので、その型を使った最小の関数を定義します。「引数も返却値もなく何もしない関数」です。だいたい次のポイントを押さえるといいと思います。

* 関数を定義するには funcsec と codesec の両方が必用です。
* funcsec は関数と型を結びつける役割を持っています。
* codesec は関数のコード本体を書きます。
* funcsec の要素と codesec の要素を結びつけるのは section 内での並び順です
  * funcsec の 0 番目の関数と codesec の 0 番目のコードが結びつく
  * funcsec の 1 番目の関数と codesec の 1 番目のコードが結びつく
  * :

細かいところはノリで読んでください。
というわけでざっと定義します。

```javascript
function makeFuncSec(a) {
    return [
        0x03, // section id: function section
        0x02, // section size
        [
            0x01, // length of vector
            [
                0x00, // typeidx of this function
            ]
        ]
    ];
}

function makeCodeSec(a) {
    return [
        0x0a, // section id: code section
        0x04, // section size
        [
            0x01, // length of vector
            [
                0x02, // size of function body
                0x00, // count of local decl
                0x0b, // end
            ]
        ]
    ];
}
```

```javascript
const bufferSource = u8tree2u8array([
    makeMagic(),
    makeVersion(),
    makeTypeSec()
]);

const importObject = {};
WebAssembly.instantiate(bufferSource, importObject).then(x => {
    console.log(x)
});
```

```shell-session
> node gen-wasm-bin.js
{ instance: Instance {}, module: Module {} }
```

instance ができました。

とりあえず `WebAssembly.instantiate()` は成功します。
export された関数がないので結局何も確認できませんが、関数は定義できているはずです。

[++ ここまでのソース ++](https://github.com/usm-takl/gen-wasm-bin.js/blob/fedaba00dab96457eb5526d8e58110ce5bdfc3f4/gen-wasm-bin.js)

# export

定義した関数を `a` という名前で export してみましょう。export section を加えるだけです。だいたい次の2点を把握すればわかると思います。

* 文字列は「文字数 - 文字列本体」の構造です
* export のエントリと関数は index で結びつきます

```javascript
function makeExportSec(a) {
    return [
        0x07, // section id: export section
        0x05, // section size
        [
            0x01, // length of vector
            [
                [
                    0x01, // length of string(name)
                    0x61, // 'a'
                ], // "a"
                0x00, // a function is exported
                0x00, // index of exported function
            ]
        ]
    ]
}
```

```javascript
const bufferSource = u8tree2u8array([
    makeMagic(),
    makeVersion(),
    makeTypeSec(),
    makeFuncSec(),
    makeExportSec(),
    makeCodeSec()
]);

const importObject = {};

WebAssembly.instantiate(bufferSource, importObject).then(x => {
    console.log(x.instance.exports.a())
});
```

```shell-session
$ node gen-wasm-bin.js
undefined
```

クラッシュしないので、呼び出せているようです。

[++ ここまでのソース ++](https://github.com/usm-takl/gen-wasm-bin.js/blob/560d119e8dab2fbea5f4fe1fcfbfeb033cef11e8/gen-wasm-bin.js)

# vec と string の作成の汎用化

vec と string はちょくちょく出てきます。数を数えるのも面倒ですので、関数化しましょう。

```javascript
function makeVec(v) {
    return [ v.length, v ];
}

function makeString(s) {
    return [ s.length, Array.from(s, ch => ch.charCodeAt(0))]
}
```

例えば exportsec はこんなふうに書けます。

```javascript
function makeExportSec(a) {
    return [
        0x07, // section id: export section
        0x05, // section size
        makeVec([[makeString("a"), 0x00, 0x00]])
    ]
}
```

だいぶすっきりします。

[++ ここまでのソース ++](https://github.com/usm-takl/gen-wasm-bin.js/blob/6c180e1f97068008d9b812f776c4f12597e38407/gen-wasm-bin.js)

# section 出力の汎用化

同じく section はたくさん出てきますし、section size を手書きするのは面倒なので、汎用化しておきましょう。section は `section id -- size of body -- body` という構造をしているので、次のようにかけます。そのまんまですね。

```javascript
function makeSection(id, body) {
    return [id, countLeaves(body), body];
}
```

これを使えば各 section は次のように書けます。

```javascript
function makeTypeSec() {
    const body = makeVec([[ 0x60, 0x00, 0x00 ]]);
    return makeSection(0x01, body);
}

function makeFuncSec(a) {
    const body = makeVec([[0x00]]);
    return makeSection(0x03, body);
}

function makeExportSec(a) {
    const body = makeVec([[makeString("a"), 0x00, 0x00]]);
    return makeSection(0x07, body);
}

function makeCodeSec(a) {
    const body = makeVec([[0x02, 0x00, 0x0b]]);
    return makeSection(0x0a, body);
}
```

だいぶすっきりしました。

[++ ここまでのソース ++](https://github.com/usm-takl/gen-wasm-bin.js/blob/ded45824d9a48440f398197a645ffe398849f9ab/gen-wasm-bin.js)

# functions

関数を定義するには複数の section に手をいれなければなりません。これはめんどくさいです。こんな感じで定義できるとうれしいですよね。

```javascript
const functions = [
    {
        exported: true,
        name: "aa",
        params: [],
        result: [],
        local: [],
        code: []
    },
    {
        exported: true,
        name: "bb",
        params: [],
        result: [],
        local: [],
        code: []
    }
]
```

というわけで `functions` を引数に取ってそれを出力するようにしましょう。現行の定数べた書きのものと同じ動きをするよう、まず次のような `functions` からはじめます。

```javascript
const functions = [
    {
        exported: true,
        name: "a",
        params: [],
        result: [],
        local: [],
        code: []
    }
]
```

まずは `makeTypeSec` から改修。

```javascript
function makeFuncType(f) {
    return [ 0x60, makeVec(f.param), makeVec(f.result) ];
}

function makeTypeSec(fs) {
    const body = makeVec(fs.map(makeFuncType));
    return makeSection(0x01, body);
}
```

動かしてみて上手く行ったら次に行きましょう。
次は `makeExportSec` です。

```javascript
function makeExport(name, typeid, index) {
    return [makeString(name), typeid, index ];
}

function makeFuncExport(name, index) {
    return makeExport(name, 0x00, index)
}

function makeExportSec(fs) {
    const body = makeVec(fs.map((f, i) => f.exported ? makeFuncExport(f.name, i) : null).filter(x => x));
    return makeSection(0x07, body);
}
```

次に `makeFuncSec` 。

```javascript
function makeFuncSec(fs) {
    const body = makeVec(fs.map((_, i) => i));
    return makeSection(0x03, body);
}
```

次に `makeCodeSec` 。

```javascript
function makeCode(f) {
    const locals = makeVec(f.locals);
    const body = [f.code, 0x0b];
    return [ countLeaves(locals) + countLeaves(body), locals, body];
}

function makeCodeSec(fs) {
    const body = makeVec(fs.map(makeCode));
    return makeSection(0x0a, body)
}
```

全部置き換わりました。

[++ ここまでのソース ++](https://github.com/usm-takl/gen-wasm-bin.js/blob/3c07efbb6c6a702ce7fc9d78f4ef0866a71d0f65/gen-wasm-bin.js)

というわけで試してみましょう。

```javascript
const functions = [
    {
        exported: true,
        name: "aa",
        param: [],
        result: [0x7f], // (result i32)
        locals: [],
        code: [0x41, 0x01] // (i32.const 1)
    },
    {
        exported: true,
        name: "bb",
        param: [0x7f], // (param i32)
        result: [0x7f], // (result i32)
        locals: [],
        code: [0x20, 0x00] // (local.get 0)
    }
]
```

```javascript
WebAssembly.instantiate(bufferSource, importObject).then(x => {
    console.log(x.instance.exports.aa())
    console.log(x.instance.exports.bb(11))
});
```

```shell-session
$ node gen-wasm-bin.js
1
11
```

WebAssembly側に値を渡したり、JavaScript側に値を返したりできるようになりました。

[++ ここまでのソース ++](https://github.com/usm-takl/gen-wasm-bin.js/blob/0237c8b0279c3345912ccca3856cf589e9d1c39b/gen-wasm-bin.js)

# LEB128

次のような 255 を返すような関数を考えましょう。

```javascript
    {
        exported: true,
        name: "aa",
        param: [],
        result: [0x7f], // (result i32)
        locals: [],
        code: [0x41, 0xff] // (i32.const 255) ?
    }
```

これはコンパイルが通りません。この整数は LEB128 というやり方でエンコードしなければならないからです。
というわけで整数を LEB128 にエンコードする関数を書きましょう。定義は[仕様書にかいてある](https://webassembly.github.io/spec/core/binary/values.html#integers)ので書き下すだけです。

```javascript
function makeI32(i) {
    if (i < 0) {
        if (-0x00000040 <= i) return i & 0x7f;
        if (-0x00002000 <= i) return [0x80 | (i & 0x7f), (i >> 7) & 0x7f];
        if (-0x00100000 <= i) return [0x80 | (i & 0x7f), 0x80 | ((i >> 7) & 0x7f), (i >> 14) & 0x7f];
        if (-0x08000000 <= i) return [0x80 | (i & 0x7f), 0x80 | ((i >> 7) & 0x7f), 0x80 | ((i >> 14) & 0x7f), (i >> 21) & 0x7f];
        return [0x80 | (i & 0x7f), 0x80 | ((i >> 7) & 0x7f), 0x80 | ((i >> 14) & 0x7f), 0x80 | ((i >> 21) & 0x7f), (i >> 28) & 0x7f];
    } else {
        if (i < 0x00000040) return i;
        if (i < 0x00002000) return [0x80 | (i & 0x7f), i >> 7];
        if (i < 0x00100000) return [0x80 | (i & 0x7f), 0x80 | ((i >> 7) & 0x7f), i >> 14];
        if (i < 0x08000000) return [0x80 | (i & 0x7f), 0x80 | ((i >> 7) & 0x7f), 0x80 | ((i >> 14) & 0x7f), i >> 21];
        return [0x80 | (i & 0x7f), 0x80 | ((i >> 7) & 0x7f), 0x80 | ((i >> 14) & 0x7f), 0x80 | ((i >> 21) & 0x7f), i >> 28 ];
    }
}

function makeU32(i) {
    if (i < 0x00000080) return i;
    if (i < 0x00004000) return [0x80 | (i & 0x7f), i >> 7];
    if (i < 0x00200000) return [0x80 | (i & 0x7f), 0x80 | ((i >> 7) & 0x7f), i >> 14];
    if (i < 0x10000000) return [0x80 | (i & 0x7f), 0x80 | ((i >> 7) & 0x7f), 0x80 | ((i >> 14) & 0x7f), i >> 21];
    return [0x80 | (i & 0x7f), 0x80 | ((i >> 7) & 0x7f), 0x80 | ((i >> 14) & 0x7f), 0x80 | ((i >> 21) & 0x7f), i >> 28 ];
}
```

修正しましょう。

```javascript
    {
        exported: true,
        name: "aa",
        param: [],
        result: [0x7f], // (result i32)
        locals: [],
        code: [0x41, makeI32(0xff)] // (i32.const 255)
    }
```

```shell-session
$ node node gen-wasm-bin.js
255
11
```

いけます。

[++ ここまでのソース ++](https://github.com/usm-takl/gen-wasm-bin.js/blob/27e4d01bdb9d63992a8218d2c9a7e391c53759ea/gen-wasm-bin.js)

# more LEB128

vec, string, section の長さも実は leb128 でエンコードしておかなければならなかったので、こちらも修正します。

```javascript
function makeVec(v) {
    return [ makeU32(v.length), v ];
}

function makeString(s) {
    return [ makeU32(s.length), Array.from(s, ch => ch.charCodeAt(0))]
}

function makeSection(id, body) {
    return [id, makeU32(countLeaves(body)), body];
}
```

# Import

JavaScript の関数を WebAssembly から呼び出したいことがあります。そのようなときは importsec を使います。

`functions` に次のようなものを追加したら `x.y` を import できるようにしましょうか。

```javascript
    {
        module: "x",
        name: "y",
        param: [],
        result: []
    },
```

import された関数の funcidx はどうなるかといいますと、 funcsec で定義された関数と共通です。つまり importsec に関数が2つ、 funcsec に関数が2つあたら、

* funcidx 0, funcidx 1 は import された関数
* funcidx 2, funcidx 3 は funcsec で定義された関数

になります。
今回の定義方法では、「`functions` のエントリに `module` があったら `import`、 そうでなかったら関数定義」という若干ダサいやりかたです。しかしこうすると typeidx と、funcidx と `functions` 内の index とが一致するので都合が良いのです。
というわけでやりましょう。

```javascript
function makeFuncSec(fs) {
    const body = makeVec(fs.map((f, i) => f.module ? null : [i]).filter(x => x));
    return makeSection(0x03, body);
}

function makeFuncImport(f, typeIndex) {
    return [ makeString(f.module), makeString(f.name), 0x00, typeIndex ];
}

function makeImportSec(fs) {
    const body = makeVec(fs.map((f, i) => f.module ? makeFuncImport(f, i) : null).filter(x => x));
    return makeSection(0x02, body);
}

function makeCodeSec(fs) {
    const body = makeVec(fs.map(f => f.module ? null : makeCode).filter(x => x));
    return makeSection(0x0a, body)
}
```

```javascript
const functions = [
    {
        module: "x",
        name: "y",
        param: [],
        result: []
    },
    {
        exported: true,
        name: "aa",
        param: [],
        result: [0x7f], // (result i32)
        locals: [],
        code: [0x10, makeI32(0xff)] // (i32.const 255)
    }
]

const bufferSource = u8tree2u8array([
    makeMagic(),
    makeVersion(),
    makeTypeSec(functions),
    makeImportSec(functions),
    makeFuncSec(functions),
    makeExportSec(functions),
    makeCodeSec(functions)
]);

const importObject = {
    x: {
        y: () => console.log("OK")
    }
};

WebAssembly.instantiate(bufferSource, importObject).then(x => {
    console.log(x.instance.exports.aa())
});
```

```shell-session
$ node gen-wasm-bin.js
255
```

とりあえずコンパイルは通ります。
では呼び出してみましょう。

```javascript
const functions = [
    {
        module: "x",
        name: "y",
        param: [],
        result: []
    },
    {
        exported: true,
        name: "aa",
        param: [],
        result: [],
        locals: [],
        code: [0x10, 0x00] // (call the 0th function)
    }
]
```

```javascript
const importObject = {
    x: {
        y: () => console.log("OK")
    }
};

WebAssembly.instantiate(bufferSource, importObject).then(x => {
    x.instance.exports.aa()
});
```

```shell-session
$ node gen-wasm-bin.js
OK
```

できました。

[++ ここまでのソース ++](https://github.com/usm-takl/gen-wasm-bin.js/blob/5dd40e6b56a517ff52c24b9b5a4c9e36ce5d1667/gen-wasm-bin.js)

# おわり

ここまで来ればだいたい WASM バイナリの雰囲気はわかると思うので、終わりにします。

何かの役に立てば幸いです。