標準ライブラリ無しのWebAssemblyでDOOMを動かす実験

以前、 [ClangだけでWASMバイナリを作る記事で、ヘッダが無いので使えない的な事を書いた](https://qiita.com/okuoku/items/c86738b9195dfb429064) 。今回、 `malloc` とか `fopen` を用意して実際にDOOMを動かしてみた。

![SnapCrab_NoName_2020-2-11_20-8-1_No-00.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/67446/47da568b-7a0a-52b4-49f1-3d18b91bd9ed.png)

動画: https://www.youtube.com/watch?v=EBF7E6_qkn8

今回インタプリタとしてはwabt( https://github.com/WebAssembly/wabt )付属のものを使用した。wabtはCygwinで上手く動作しなかったが、修正して [PRを出している](https://github.com/WebAssembly/wabt/pull/1332) 。

結果としてある程度動くものはできた。ちょっとプレイには厳しいものがあるが、今回の成果を元にSDKとして環境をまとめて行きたい。

# もくてき

[前回の記事](https://qiita.com/okuoku/items/c86738b9195dfb429064) に書いたように、LLVM8以降のclangは標準でWASMターゲットをサポートしていて、単体で `.c` ファイルをWASMに変換することができる。今回は、この機能だけを使って、つまり **EmscriptenとWebブラウザを使わずに** WebAssemblyで出力したゲームを遊ぶ環境を考えたい。

[以前紹介したWASM3のように](https://qiita.com/okuoku/items/ed52f48ce871f429759e) 、ブラウザ以外でWebAssemblyを実行できる環境はそれなりに増えつつあるので、WebAssemblyを移植層として使ってポータブルなゲーム実行環境が作れると良いんじゃないかと思っている。

# 作戦 (用語の説明)

やっていることの性質上、用語が激烈に独特なのでちょっと説明。個人的に本業がカーネル開発者だった時期があるのでOSカーネル風の実装方針を取っている。

## ホスト / ターゲット

今回のプロジェクトでは **2種類のC言語環境を同時に使う** ことになる。それぞれをホスト(host)とターゲット(target)と呼ぶ。

**ホスト** はWASMの用語ではembedderと呼ばれることもある。ネイティブのOSとCPUに向けたツールチェーンを使用する。今回の場合はWindows上のCygwin64ということになる。ホスト向けのコンパイラやlibcは、環境付属のものをそのまま使用し、wabtやlibvncserverはホストのツールチェーンでビルドすることになる。

embedderのためのAPIとして、WASM C-API( https://github.com/WebAssembly/wasm-c-api )が開発中となっている。このAPIに準拠したWASM実行環境では共通してこのAPIを使用できるため、今回使ったwabtのインタプリタをV8に入れかえることも(原理的には)可能となっている。

ホスト側のコードは、libvncserverによる画面表示とかファイルI/Oを担当する。

**ターゲット** はClang 9.0のWASMターゲットを使った。Clangにはfreestanding環境のためのヘッダ(`stdint.h`や`stdarg.h`など)が付属してきていて、これはそのまま使用できる。

当然、Clangのコンパイラドライバは今回作成した "DOOM専用libc" のことなんか知らないので、専用のCMake Platformを定義し、それを指定してDOOMや今回作成したlibc等のターゲット向コードをコンパイルすることになる。

- https://github.com/okuoku/freestandoom/blob/9150923c78a169d1563100fbc85a1302c0bab5df/cmake/Modules/Platform/Yuniwarp.cmake -- 作成したPlatformファイル
- https://github.com/okuoku/freestandoom/blob/9150923c78a169d1563100fbc85a1302c0bab5df/configure.cmake - 作成したPlatformファイルを使用してconfigureするためのCMakeスクリプト

ターゲット側のコードは、DOOMのゲームロジックやソフトウェアレンダリングを担当する。

## copyin / copyout

今回のプロジェクトで重要なのは、ホストとターゲットでABI、特にポインタの解釈が異なることと言える。つまり、ホストではポインタのサイズは64bitあるが、ターゲットであるWASMでは、ポインタのサイズは32bitになる。このため、 **ホストとターゲットは独立したメモリ空間を持つ** ことになる。

実際にレンダリングされたDOOM画面はターゲットのメモリ空間に存在するため、描画するためにはホスト側にコピーしてくる必要がある。このためのコピーをUNIXに倣って `copyin` と呼ぶ。逆に、ホストに移譲されたI/Oの結果はターゲット側のメモリ空間にコピーする必要があるため、これを `copyout` と呼ぶ。

`copyin` / `copyout` の各APIは、WASM C-APIのインターフェースを使って以下のように実装できる:

- https://github.com/okuoku/freestandoom/blob/9150923c78a169d1563100fbc85a1302c0bab5df/host-common/callwasm.c#L16

```c
int
iopkt_copyin32(uint32_t addr, void* dest, uint32_t len){
    void* x;
    if(!addr){
        fprintf(stderr, "Trying to read from addr 0\n");
    }
    // ★ WASM C-APIのインターフェース wasm_memory_data でホストのポインタに変換
    x = wasm_memory_data(export_memory); 
    // ★ ホストのmemcpyで実際のコピーを実施する
    memcpy(dest, x + addr, len); 
    return 0;
}
```

stdioの `fread` のように、ホスト側でその処理を行う必要のあるAPIはパラメタや結果の受け渡しに、この `copyin` や `copyout` APIを使う必要がある。

C言語のAPIでは、null-terminateされた文字列を引数として使うケースが頻出なため、 [BSDのような `copyinstr` も実装している](https://github.com/okuoku/freestandoom/blob/9150923c78a169d1563100fbc85a1302c0bab5df/host-common/callwasm.c#L41) 。`copyinstr`は指定されたポインタからNUL文字までをコピーする。

# DOOMのビルド

今回は移植性の高いChocolate DOOMを元に制作されたと見られるDOOM Generic( https://github.com/ozkl/doomgeneric )をベースにしている。

DOOMはかなり素直なCコードで実装されているため、単に [今回制作したヘッダ類](https://github.com/okuoku/freestandoom/tree/9150923c78a169d1563100fbc85a1302c0bab5df/proxylibc/sysroot/include) をsysrootに設定してビルドすればそのままビルド可能となっている。

ただ、ごく僅かに機種依存部があるため、その実装とWebブラウザでの実行を想定して多少の改造をしている(後述)。

ビルドしたDOOMをwabtで逆アセンブルすると、

```scheme:逆アセンブルしたWASM.wat
...
  (import "env" "proxylibc_memcpy" (func $proxylibc_memcpy (type 0)))
  (import "env" "proxylibc_memset" (func $proxylibc_memset (type 0)))
  (import "env" "proxylibc_exit" (func $proxylibc_exit (type 3)))
  (import "env" "iopkt_req32" (func $iopkt_req32 (type 2)))
  (import "env" "memcpy" (func $memcpy (type 0))) 
...
```

のようになり、今回作成したヘッダを使うことで、ホストからはこの5つの関数さえ提供すればDOOMは動作することがわかる。

# C ライブラリの実装

普段空気のように存在する `<stdio.h>` とか `<stdlib.h>` も、誰かが実装しないと使えない。常識的な環境ではOSがこれを提供しているが、今回はマジで何もないため手で実装してやる必要がある。

- https://github.com/okuoku/freestandoom/blob/81109ded72f40a413f0e5a1dbdcad869250c9872/proxylibc/sysroot/include - 今回作成したヘッダ
- https://github.com/okuoku/freestandoom/tree/81109ded72f40a413f0e5a1dbdcad869250c9872/target - WASM側で完結するランタイムライブラリ
- https://github.com/okuoku/freestandoom/tree/81109ded72f40a413f0e5a1dbdcad869250c9872/iopkt/target - WASM側で実装される、ホストにI/O要求を発行するライブラリ

今回はDOOMの実行に必要な最小限だけ実装している。

## memcpy / memmove / memset

GNUコンパイラにおいて、 `memcpy` `memmove` `memset` と `memcmp` の4関数は **freestanding(ライブラリを使用しない環境)でも必須** となっている。これにより、C言語フロントエンドが自動的にこれらの関数呼び出しを生成する可能性がある。

- https://gcc.gnu.org/onlinedocs/gcc/Standards.html

> Most of the compiler support routines used by GCC are present in libgcc, but there are a few exceptions. GCC requires the freestanding environment provide memcpy, memmove, memset and memcmp. Finally, if __builtin_trap is used, and the target does not implement the trap pattern, then GCC emits a call to abort. 

今回の実装範囲では、libgccに含まれるような関数(64bit除算等)と `memcmp` は不要となっている。また、WASMには [bulk-memory操作](https://github.com/WebAssembly/bulk-memory-operations) として将来的に専用命令が追加される見込みで、これらの実装も不要になる可能性はある。

DOOMをビルドすると、 `memcpy` が埋め込まれていることがわかる。

```scheme:逆アセンブルにはmemcpyのimportが2つ存在する.wat
  (import "env" "proxylibc_memcpy" (func $proxylibc_memcpy (type 0)))
;; ★ Cソースから直接呼ばれているものは proxylibc_memcpy になっている
  (import "env" "memcpy" (func $memcpy (type 0))) 
```

これらの関数はWASM側で実装することもできるが、たぶんホスト側で実行した方が高速なのでホスト側で実行することにした。これはcopyin/outと同じように実装できる。

- https://github.com/okuoku/freestandoom/blob/81109ded72f40a413f0e5a1dbdcad869250c9872/host-common/callwasm.c#L68

```c
static wasm_trap_t*
cb_memcpy(const wasm_val_t* args, wasm_val_t* results){ // 3_1
    uint32_t arg0;
    uint32_t arg1;
    uint32_t arg2;
    char* x;

    x = wasm_memory_data(export_memory);
    arg0 = args[0].of.i32; // ★ to
    arg1 = args[1].of.i32; // ★ from
    arg2 = args[2].of.i32; // ★ len

    // ★ data + オフセットでホストでのアドレスが判るので、それを引数に "ホストの" memcpyを呼ぶ
    memcpy(&x[arg0], &x[arg1], arg2);

    results[0].kind = WASM_I32;
    results[0].of.i32 = arg0; // ★ to のアドレスを返す 
    return NULL;
}
```

FIXME: ホスト側から触ったメモリをVMに教える必要は無いんだろうか

## TLSFによるmallocの実装

mallocは要するに巨大な配列を確保し、それを管理する関数を提供すれば良い。今回は組込むのが簡単なTLSFライブラリ( https://github.com/mattconte/tlsf/ )を使用している。これはBSDLなのでパブリックドメインなdlmallocなり自作なりに置き換えた方が良いかもしれない。

WASMの命令には、自身を実行しているメモリを追加するための専用の命令が存在し、これを呼び出すことで巨大な配列を簡単に確保できる。ただし、これらの命令は [WASM3のIssue 33で触れられている](https://qiita.com/okuoku/items/ed52f48ce871f429759e#wasm%E3%83%A2%E3%82%B8%E3%83%A5%E3%83%BC%E3%83%AB%E3%81%8C16mib%E3%82%82%E3%81%AE%E3%83%A1%E3%83%A2%E3%83%AA%E3%82%92%E5%8F%96%E3%82%8B%E3%81%AE%E3%81%AF%E4%BD%95%E6%95%85%E3%81%8B) ように64KiB単位で動作することに注意する。

これらの命令をC言語プログラムから使用するには、builtinの `__builtin_wasm_memory_size` と `__builtin_wasm_memory_grow` を使用する。つまり、

- https://github.com/okuoku/freestandoom/blob/9150923c78a169d1563100fbc85a1302c0bab5df/target/heap.c#L12

```c
void
heap_init(void){
    int r;
    /* Find last page */
    heap = (uint8_t*)((uintptr_t)__builtin_wasm_memory_size(0) * 64 * 1024);
    /* grow memory */
    r = __builtin_wasm_memory_grow(0, HEAP_PAGES);
    if(r<0){
        for(;;); // ★ エラー時はとりあえず無限loopにしとく
    }
    heap_ctx = tlsf_create_with_pool(heap, HEAPSIZE);
}
```

1. `__builtin_wasm_memory_size` で、現在のWASMコードがアドレス可能なページ数を取得する
2. `__builtin_wasm_memory_grow` で、アドレス可能なページ数を拡張する
3. TLSFライブラリの `tlsf_create_with_pool` で増やした分を管理するコンテキストを用意する

という方法でmalloc/freeができる領域を用意できる。malloc/freeは単にTLSFライブラリの呼び出しとなる:

- https://github.com/okuoku/freestandoom/blob/81109ded72f40a413f0e5a1dbdcad869250c9872/target/heap.c#L16
 
```c
void*
malloc(size_t size){
    return tlsf_malloc(heap_ctx, size);
}

void
free(void* ptr){
    tlsf_free(heap_ctx, ptr);
}
```

元々は [巨大な配列を直接Cソースコードに宣言してTLSFに管理させていたが、動的に確保する方向に切り替えた](https://github.com/okuoku/freestandoom/commit/9150923c78a169d1563100fbc85a1302c0bab5df) 。これは現在(LLVM9.0)のLLDが.bssセクションを最適化せず、単にall-0のデータとして扱ってしまうことのワークアラウンドで、本来はここまでする必要は無いかもしれない。

ちなみに、 [clangのテストにbuiltinの一覧があるものの](https://github.com/llvm-mirror/clang/blob/837a96eec129835f1c498b92c33037704a13bd91/test/CodeGen/builtins-wasm.c) 、今のところbuiltinの標準化については特に議論が無いようだ。

## stdioの実装

- https://github.com/okuoku/freestandoom/blob/81109ded72f40a413f0e5a1dbdcad869250c9872/iopkt/target/stdio_iopkt.c -- 実装したstdio
- https://github.com/okuoku/freestandoom/blob/81109ded72f40a413f0e5a1dbdcad869250c9872/iopkt/host/host-cstdio.c#L275 -- ホスト側

今回のstdioはWASMとホストのインターフェースとして単一の `iopkt_req32` APIだけを用意し、それを `syscall` 命令やAPIのように使っている。

```c
void iopkt_req32(uint32_t* req, uint32_t* res);
```

`iopkt_req32` は `uint32_t` の配列をAPIのパラメタと結果をホスト/ターゲットでやりとりするのに使用する。CのAPIではAPIの戻り値は通常1つのみだが、 `iopkt_req32` では複数の戻り値を返却できるようになっている。例えば `READ` 操作の場合、

```c
// [READ, zone, id_L, id_H, off_L, off_H, buf, len] => [res, len]
#define IOPKT_FILE_OP_READ IOPKT_REQID(FILE,2)
```

操作の結果 `res` と実際に転送したバイト数 `len` の2値を返却している。 この方法を取ることで、エラー番号として正負両方の値が使用できるようになる。POSIXの `read` syscallでは、 `-1` をエラーとして返却して別途 `errno` 変数から発生したエラーを取得するようになっているが、エラーの値域が限定される(負値しか使用できない)。OSのエラーコードは一般に正負どちらかの番号を取るため、その逆側を今回実装したlibcに固有のエラーコードとして使用できる。

全てのI/O関数は `iopkt_req32` の呼び出しとして実装できる。例えば、 `fread` は、

- https://github.com/okuoku/freestandoom/blob/81109ded72f40a413f0e5a1dbdcad869250c9872/iopkt/target/stdio_iopkt.c#L167

```c
size_t
fread(void* restrict ptr, size_t size, size_t nmemb, FILE* restrict stream){
    uint32_t req[IOPKT_REQ_MAX];
    uint32_t res[IOPKT_RES_MAX];
    uint64_t totalsize;
    totalsize = size;
    totalsize *= nmemb;

    req[0] = IOPKT_FILE_OP_READ; // ★ req パケットの作成
    req[1] = stream->zone;
    req[2] = stream->handle_l;
    req[3] = stream->handle_h;
    req[4] = (uint32_t)stream->pos; // ★ WASM側でトラックしている読み取り位置を渡す
    req[5] = (stream->pos >> 32ULL);
    req[6] = (uintptr_t)ptr;
    req[7] = totalsize;

    // ★ 実際の I/O
    iopkt_req32(req, res);

    // ★ res パケットの解釈
    if(res[0]){ 
        return 0; // res[0]が非ゼロならエラー
    }
    if(stream->limit >= 0){
        // ★ WASM側でトラックしている読み取り位置を更新
        stream->pos += res[1];
        if(stream->limit < stream->pos){
            // ★ WASM側でトラックしているファイルサイズを更新
            stream->limit = stream->pos;
        }
    }
    return res[1] / size; // ★ 実際にreadできた数を返却
}

```

stdioはDOOMを動かすのに必要最低限しか実装していないが、それでもファイルI/Oやseek類が必要になっている。将来RAM上にファイルの実体を置くことを見越してseek類はWASM側でエミュレーションする実装とした。


## stb_sprintf.hによるprintfの実装

C言語の可変長引数関数は実際に指定された引数を検出する方法が無いため、ホストに移譲する良い方法が存在しない。こういう場合に、

1. 可変長引数マクロを使って関数呼び出しを分解し、引数の数も同時に渡す
2. 可変長引数の処理はターゲットで済ませる

といった方法があるが、今回は簡単のために後者を選択した。

stb_sprintf.h https://github.com/nothings/stb/blob/master/stb_sprintf.h はパブリックドメインのsprintf実装で、これを使用すると簡単にvsprintfやvfprintfを実装できる。

- https://github.com/okuoku/freestandoom/blob/81109ded72f40a413f0e5a1dbdcad869250c9872/target/prf_stb.c#L5

```c
// ★ stb_sprintfに渡すコールバック
static char*
cb_outstream(char const* buf, void* u, int len){
    FILE* fp = (FILE *)u;
    fwrite(buf, len, 1, fp);
    return (char *)buf; /* Deconst */
}

// ★ 単に stb_sprintf のAPIを呼ぶだけ
int
vfprintf(FILE* stream, const char* format, va_list arg){
    char buf[STB_SPRINTF_MIN];
    return stbsp_vsprintfcb(cb_outstream, stream, buf, format, arg);
}
```

出力をメモリ上に行うvsprintf以外に、ファイルストリームに行うvfprintfも同様に実装できる。そして、通常の `printf` 等は、これらの関数を `<stdarg.h>` の各種マクロを使用して呼び出すことでそのまま実装できる。

- https://github.com/okuoku/freestandoom/blob/81109ded72f40a413f0e5a1dbdcad869250c9872/target/prf.c

```c
int
printf(const char *format, ...){
    int r;
    va_list ap;

    va_start(ap, format);
    r = vfprintf(stdout, format, ap); // ★ stdout を指定してvfprintfを呼ぶだけ
    va_end(ap);
    return r;
}
```

ちなみに、 [`scanf` はバカみてぇな実装](https://github.com/okuoku/freestandoom/blob/9150923c78a169d1563100fbc85a1302c0bab5df/target/dummy_sscanf.c) をしている。(実際には使われない)

# DOOMの改造

Webブラウザ上での実行を考えると、 "ホスト側がターゲット側の画面更新関数を繰り返し呼ぶ" 形のプログラムになっている方が望ましいが、残念ながらDOOMはそのような形にはなっていないので改造が必要になる。

- https://github.com/okuoku/freestandoom/commit/2b6dc6d9ead96c5c666c6751912b734283a5f082
  - 実際の分割を行ったコミット

ここでは、

1. `D_DoomMain` は初期化だけやって呼び出し元に戻るように変更
2. `D_DoomLoop` は画面の表示状態を `int` で返すように変更
3. `RX_DoomLoopStep` 関数を追加し、画面更新を1フレーム分やって返るように変更

の各種改造をしたうえで、DOOMの処理を2つのC言語関数 `init` と `step` に集約している。

- https://github.com/okuoku/freestandoom/blob/9150923c78a169d1563100fbc85a1302c0bab5df/module.c#L25

```c
__attribute__((__visibility__("default"))) // ★ WASMのexportに関数を載せるために必要
uintptr_t
init(void) {
    // ★ libcの初期化処理
    heap_init();
    stdio_init();

    state = 0;
    // ★ DOOMの初期化処理
    M_FindResponseFile();
    dg_Create();
    D_DoomMain();

    printf("DoomMain returned\n");
    my_framecount = 1;

    printf("Screen Buffer = %x\n", (uintptr_t)DG_ScreenBuffer);

    // ★ DOOMの画面の先頭アドレスを返却する
    return (uintptr_t)DG_ScreenBuffer;
}

__attribute__((__visibility__("default")))
void
step(int buttons){
    global_buttonbitmap = buttons;
    // ★ DOOMの描画内容を更新
    state = RX_DoomLoopStep(state);
    my_framecount++;
}
```

... この改造を既にやってあるDOOMは探せばあるんだろうけど面倒なので手でやってしまった。

# かんそう

流石にインタプリタでソフトウェアレンダリングなゲームを動かすのは厳しいものがあるようだが、もっと高速なインタプリタやAoTコンパイラを使用することで実用的な速度でゲームを動作させることは十分可能だと思う。

ゲーム配布のプラットフォームとしては。。たぶんWebランタイムと開発環境の質次第というところだろう。WASIはかなりPOSIX指向でFFIのための良い考察が今のところ無いため、それなりのニッチが存在する。例えば、CMakeとかClangがWeb上で動作できれば、 **GitHub上から直接ゲームをビルドして起動する** のをWebブラウザ上で完結できるかもしれない。

## ライブラリ配布環境としての可能性

今回全ての libc APIは一旦 `proxylibc_` のプレフィックスを付けて実装した。これは、 **"C言語ソースをプリプロセスしたソースを配布するだけのパッケージマネージャ" が作れないか** という考えによるもので、ホストのlibcとターゲットのlibcが単一の実行ファイル内で安全に共存できることを意識している。(シンボルvisibilityでの共存は開発支援ツールとの食べ合せが悪い)

個人的には、パッケージマネージャの機能はビルド環境の抽象化に集約できると考えていて、ビルド済のバイナリを配布することは実はそこまで大きなrequirementでは無いのではないかという気がしている。

実際には `typedef` される型のサイズ、要するにポインタのサイズが一致しない可能性があるのでそこまで上手くはいかないが、移植性の観点で言えば、今回のように一旦WASM32を経由する必要性は実は無い。例えば、proxylibcのヘッダを使ってDOOMのソースコードをプリプロセスし、それを単純にランタイムと連結してしてコンパイルすることでfreestanding環境で動作するDOOMを得られるのではないだろうか。

もっとも、C++にはどうやっても対応できないし、現実問題として殆どのプログラムはC++で書かれるため、一旦WASMにコンパイルしてWASM2CでC言語に変換する方が良好な結果を得られるだろう。