数独ソルバーで使うことでEmscriptenの仕組みを調べてみた

Cで実装したバックトラック型数独ソルバーを、[Emscripten](http://kripken.github.io/emscripten-site/)を使ってJavaScript環境で実行させることから、Emscriptenの仕組みを調べていった、という話です。

# Emscriptenとは

emscriptenは、[LLVM/Clang](http://llvm.org/)を使って、CやC++のプログラムをブラウザや[nodejs](https://nodejs.org/)/[iojs](https://iojs.org/)といったJavaScript環境で実行できるようにするシステムです。

C/C++のソースをコンパイルしたLLVMのバイトコードを元に、JavaScript上で実行させるための**変換プログラムとそれを実行するためのランタイム環境の部分**と、gccやmake等と互換性を高めた[`emcc`](https://github.com/kripken/emscripten/blob/master/emcc)や[`emmake`](https://github.com/kripken/emscripten/blob/master/emmake)などの**コマンドライン群**を提供しています。前者はnodejsによって、後者は[python](https://www.python.org/)によって実行するようになっています。

[libc](http://www.gnu.org/software/libc/)等のC/C++で利用する**ランタイムライブラリ(の関数)は、JavaScript側でエミュレートする**ようになっています。コンソールへの標準出力、[SDL](https://www.libsdl.org/)/[OpenGL](https://www.opengl.org/)等の描画などをnodejs/iojs環境やブラウザ上で実現するJS実装、等が、emscriptenには標準添付されています(たとえばlibcのエミュレート実装は、[`/usr/local/opt/emscripten/libexec/src/library.js`](https://github.com/kripken/emscripten/blob/master/src/library.js)で記述されています)。

# Emscriptenの環境設定

OSX環境では、[homebrew](http://brew.sh/)によってemscriptenをインストールしました(`brew install emscripten`)。

emscriptenを入れると、`emcc`(gcc/clang互換のコマンド)等のコマンドが追加され、初回にそのコマンドを実行する時、環境が設定された`~/.emscripten`ファイルが作られます。

しかし、OSXだと現状のシステム添付の`clang`コマンドを使うなど、その内容はただしく反映されません。そこで以下のように編集しなおします。

```py3
# ~/.emscripten
EMSCRIPTEN_ROOT = os.path.expanduser(
    os.getenv('EMSCRIPTEN') or 
    '/usr/local/opt/emscripten/libexec')
LLVM_ROOT = os.path.expanduser(
    os.getenv('LLVM') or 
    '/usr/local/opt/emscripten/libexec/llvm/bin')

NODE_JS = os.path.expanduser(
    os.getenv('NODE') or 
    '/usr/local/opt/node/bin/node')

TMP_DIR = '/tmp'
COMPILER_ENGINE = NODE_JS
JS_ENGINES = [NODE_JS]
```

このようにhomebrewのパッケージのもを指定しておけくことで、homebrewのupgradeによってインストールされているemscriptenやnodejsのパッケージがバージョンアップしても、毎回の再設定せずに実行できるようになります。

この設定で`emcc`コマンドを空実行すると、正しく設定されていていれば以下の結果になります。

```bash
$ emcc
WARNING  root: (Emscripten: settings file has changed, clearing cache)
INFO     root: (Emscripten: Running sanity checks)
WARNING  root: no input files
```

# C言語(C11)で数独ソルバーを書く

はじめに[C11仕様](http://en.wikipedia.org/wiki/C11_%28C_standard_revision%29)でバックトラック型の9x9マスの数独ソルバーを記述します。あとでライブラリだけで利用できるよう、コードのライブラリ部分と`main`部分とでファイルを分けて記述します。

```c
// libsudoku.c
#include <stdio.h>

// helpers for board data
static inline unsigned masks(unsigned i) {return i ? 1 << (i - 1) : 0;}
static inline unsigned row(unsigned i) {return i / 9;}
static inline unsigned col(unsigned i) {return i % 9;}
static inline unsigned blk(unsigned i) {return i / 27 * 3 + i % 9 / 3;}
extern void output(unsigned board[])
{
  char buffer[(9 + 3) * (9 + 3)];
  char* cur = buffer;
  for (unsigned y = 0; y < 9; y++) {
    for (unsigned x = 0; x < 9; x++) {
      *cur++ = board[y * 9 + x] > 0 ? board[y * 9 + x] + '0' : '.';
      if (x % 3 == 2) *cur++ = x == 8 ? '\n' : '|';
    }
    if (y == 8) {
      *cur++ = '\0';
    } else if (y % 3 == 2) {
      for (unsigned i = 0; i < 11; i++) *cur++ = i % 4 == 3 ? '+' : '-';
      *cur++ = '\n';
    }
  }
  puts(buffer);
}

// sudoku solver
typedef void (*sudoku_cb)(unsigned board[]);
typedef struct {
  unsigned board[81];
  unsigned rows[9], cols[9], blks[9];
  sudoku_cb callback;
} sudoku_t;

static void sudoku_init(sudoku_t* s, unsigned board[])
{
  for (unsigned i = 0; i < 81; i++) {
    const unsigned mask = masks(board[i]);
    s->rows[row(i)] |= mask, s->cols[col(i)] |= mask, s->blks[blk(i)] |= mask;
    s->board[i] = board[i];
  }
}

static void sudoku_solve(sudoku_t* s, unsigned i)
{
  if (i == 81) {
    s->callback(s->board);
  } else if (s->board[i] != 0) {
    sudoku_solve(s, i + 1);
  } else {
    const unsigned r = row(i), c = col(i), b = blk(i);
    const unsigned used = s->rows[r] | s->cols[c] | s->blks[b];
    for (unsigned v = 1; v <= 9; v++) {
      const unsigned mask = masks(v);
      if (used & mask) continue;
      s->board[i] = v;
      s->rows[r] |= mask, s->cols[c] |= mask, s->blks[b] |= mask;
      sudoku_solve(s, i + 1);
      s->rows[r] &= ~mask, s->cols[c] &= ~mask, s->blks[b] &= ~mask;
      s->board[i] = 0;
    }
  }
}

extern void sudoku(unsigned board[], sudoku_cb callback)
{
  sudoku_t s = {
    .board = {0}, .rows = {0}, .cols = {0}, .blks = {0}, .callback = callback};
  sudoku_init(&s, board);
  sudoku_solve(&s, 0);
}
```

```c
// sudoku-main.c

#include <stdio.h>

extern void output(unsigned board[]);
typedef void (*sudoku_cb)(unsigned board[]);
extern void sudoku(unsigned board[], sudoku_cb callback);

// example problem from http://rosettacode.org/wiki/Sudoku
static unsigned problem[] = {
  8, 5, 0, 0, 0, 2, 4, 0, 0,
  7, 2, 0, 0, 0, 0, 0, 0, 9,
  0, 0, 4, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 1, 0, 7, 0, 0, 2,
  3, 0, 5, 0, 0, 0, 9, 0, 0,
  0, 4, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 8, 0, 0, 7, 0,
  0, 1, 7, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 3, 6, 0, 4, 0
};

extern int main(int argc, char* argv[])
{
  if (argc <= 1) {
    puts("[problem]");
    output(problem);
    puts("[solutions]");
    sudoku(problem, output);
  } else {
    for (int i = 1; i < argc; i++) {
      char ch = -1;
      for (int c = 0; c < 81; c++) {
        if (ch == '\0') {
          problem[c] = 0;
        } else {
          ch = argv[i][c];
          problem[c] = '0' <= ch && ch <= '9' ? ch - '0' : 0;
        }
      }
      puts("[problem]");
      output(problem);
      puts("[solution]");
      sudoku(problem, output);
    }
  }
  return 0;
}
```

このコードは、以下のようにgcc/clangで普通にコンパイル/実行可能なプログラムになっています。

```bash
$ clang -std=c11 -Wall -Wextra libsudoku.c sudoku-main.c -o sudoku
$ ./sudoku 
[problem]
85.|..2|4..
72.|...|..9
..4|...|...
---+---+---
...|1.7|..2
3.5|...|9..
.4.|...|...
---+---+---
...|.8.|.7.
.17|...|...
...|.36|.4.

[solutions]
859|612|437
723|854|169
164|379|528
---+---+---
986|147|352
375|268|914
241|593|786
---+---+---
432|981|675
617|425|893
598|736|241

```

# EmscriptenでCのプログラムをコンパイルし、iojsで実行する

上記ビルドでの`clang`の部分を`emcc`に変え、**出力ファイル名に`.js`をつける**だけでJavaScriptコードにコンパイルできます。
生成されたjsファイルは、それ**単体でnodejs/iojs上で実行可能**になっています。

```bash
$ emcc -std=c11 -Wall -Wextra libsudoku.c sudoku-main.c -o sudoku.js
$ iojs sudoku.js 
[problem]
85.|..2|4..
72.|...|..9
..4|...|...
---+---+---
...|1.7|..2
3.5|...|9..
.4.|...|...
---+---+---
...|.8.|.7.
.17|...|...
...|.36|.4.

[solutions]
859|612|437
723|854|169
164|379|528
---+---+---
986|147|352
375|268|914
241|593|786
---+---+---
432|981|675
617|425|893
598|736|241


```

# Emscriptenでコンパイルしたライブラリの関数を、JavaScriptコードから呼び出す

Emscriptenで生成したコードは、(CoffeeScript等のトランスレータのような)**普通のJavaScript関数として使えるJSコードではありません**。生成されるのは、(C言語実行モデルを前提とする)LLVMバイトコードとその実行環境が合わさったものです。例えば、HEAPのような定量のメモリ領域の管理機構がJSコード中に存在しています。

これは生成するのがライブラリであっても同じで、ライブラリがもつ`extern`な関数というのは、あくまで**Cの関数としてのバイトコードを、ライブラリ内に組み込んだ実行環境上で実行させるもの**となっています。

そのためEmscriptenで生成したコードを、JavaScript用のライブラリとして使うには、所々で少し工夫が必要になります。公式ドキュメントの、[Interacting with code](http://kripken.github.io/emscripten-site/docs/porting/connecting_cpp_and_javascript/Interacting-with-code.html)には、このために必要な情報は記述してありますが、これらが**ライブラリ内のCプログラム実行環境へのアクセス手段**である、という大本の違いを認識していないとハマることになります。

## nodejs/iojsライブラリとしてコンパイルする

`libsudoku.c`からnodejs/iojs上のライブラリとして使う`libsudoku.js`を生成するには、以下のように付属のオプション`-s EXPORTED_FUNCTIONS`と`-s RESERVED_FUNCTION_POINTERS`の２つを指定する必要があります。

```bash
$ emcc -Wall -Wextra -std=c11 libsudoku.c -o libsudoku.js \
      -s EXPORTED_FUNCTIONS="['_sudoku','_output']" \
      -s RESERVED_FUNCTION_POINTERS=20
```

前者の`EXPORTED_FUNCTIONS`では、JavaScript側で呼び出すために、Cでの`extern`な関数名を指定します。ただし、Cの関数名そのままではなく、**頭に`_`をつけた名前**を列挙します。

後者の`RESERVED_FUNCTION_POINTERS`は、`sudoku(board, callback)`関数のような、**コールバック関数のポインタを渡す関数をJavaScript側から呼び出す必要があるとき**に必要な変数です。ここで、JavaScriptの`function`をコールバックさせるために、バイトコード実行環境上に設定できる関数ポインタの数を確保します。`libsudoku.js`は並列実行されないので、libsudoku.jsの場合は`1`あればよいですが、ここでは`20`を指定しました。

## Emscriptenライブラリを呼び出すJavaScriptコードを書く

ドキュメントでは、`ccall`や`cwrap`を使えとありますが、載せてあるのはやりとりするのが単純な`number`の値ときのみであって、引数で配列や関数を使うために生成されたコードを解析したりして試行錯誤しました。

### `ccall`で配列を引数に渡して呼び出す方法

まず、`libsudoku.c`の`void output(unsigned board[])`を呼び出すラッパーは以下のようになりました。

```js
var libsudoku = require("./libsudoku.js");

// use ccall to call emscripten C function
var output = function (board) {
    // unsigned[] as Uint8Array view of Uint32Array
    var unsignedBoard = new Uint8Array(new Uint32Array(board).buffer);
    // ccall(cfuncname, return_type, argument_types, arguments)
    // type: "string", "number", "array" or undefined as return type
    return libsudoku.ccall("output", undefined, ["array"], [unsignedBoard]);
};
```

ここでは、JavaScriptの`Array`を、Emscriptenのarray値として`ccall`を呼び出します。引数は、`library.ccall(関数名, 戻り値型, 引数型リスト, 引数値リスト)`です。この関数名は、コンパイルオプションのではなく、**頭の`_`なしのCでの関数名**になります。

戻り値は`void`の場合`undefined`を指定します。引数の型は`"number"`か`"string"`か`"array"`のどれかになります。この型指定は、Cの関数宣言での型ではなく、呼び出して実行させる時に実際に渡す**JavaScript値の型**になります。

`output()`の引数のポインタの型は`unsigned (int)`ですが、**Emscriptenでは、`int`型は32bit整数**として扱われるようです。そして**バイトオーダーは、`TypedArray`のCPU環境依存性をそのまま継承している**ようです(生成コード内でCPU依存な`new Uint32Array(buffer)`などが記述されている)。

C言語上で扱うのが32bit配列だろうと、`ccall`で呼び出すときの**`"array"`型の引数は、8bitの`Int8Array`や`Uint8Array`である**必要があります。ライブラリ内の`ccall`実装を見ると、呼び出しで渡す引数は、その値を**ライブラリ内のメモリ領域にコピーしてバイトコード実行**させます。`"string"`とか`"array"`とかいうのは、そのコピー手段を指定するものになっています。`"array"`の場合は、`HEAP8[...] = array[i]`でコピーするので、`Uint32Array`等をそのまま`ccall`に渡すと8bitに切り詰められてしまいます。ちなみに`"string"`はCへはUTF8な`char`文字列になって渡ります。

### 関数ポインタを渡す関数を呼び出す方法

`sudoku(board, callback)`へのラッパーを、もう一つの`cwrap`を使って実装したのが、以下のコードになります。`ccall(関数名, 戻り値型、引数型リスト、引数値リスト)`は、`cwrap(関数名, 戻り値型, 引数型リスト)(引数値リスト)`と等価です。emscriptenの関数を何度も呼び出す場合には`cwrap`が返す関数をキャッシュしておいて、引数だけ渡して呼び出すほうがよいでしょう。

ここでのポイントは、JavaScriptのコールバック関数は、バイトコード実行環境にセットし、そのポインタ値を`"number"`として`cwrap`で作った関数の引数に渡す点です。

```js
// use cwrap to call emscripten C function with callback
var sudoku = function sudoku(board, callback) {
    // NOTE: For using addFunction(),
    //    emcc option "-s REQUIRED_FUNCTION_POINTERS=10" (more than 1) required
    var callbackPtr = libsudoku.Runtime.addFunction(function (resultPtr) {
        var r = new Uint32Array(libsudoku.HEAPU8.buffer, resultPtr, 81);
        // NOTE: copy memory value as array for async use in callback(like IO)
        callback([].slice.call(r));
    });
    var unsignedBoard = new Uint8Array(new Uint32Array(board).buffer);
    sudoku._cfunc(unsignedBoard, callbackPtr);
    libsudoku.Runtime.removeFunction(callbackPtr);
};
// pointer as a "number"
sudoku._cfunc = libsudoku.cwrap("sudoku", undefined, ["array", "number"]);
```

`ptr = library.Runtime.addFunction(function)`を使い、JavaScript `function`をバイトコード環境にセットし、そのポインタ値を受け取ります。
コンパイル時の引数の`RESERVED_FUNCTION_POINTERS`の数は、同時に`addFunction`で登録できるJavaScript関数の数を指します。

コールバックで呼び出される関数に渡される引数は、(`ccall`等のでの値ではなく)実行環境上での数値そのままです。**ポインタの場合は、ランタイムのHEAP(`library.HEAPU8`等)のオフセット値として使う**ことになります。これを隠ぺいするためには**コールバック関数もまたラッパーが必要**になります。このコールバックラッパーの中でメモリオフセットから通常の`Array`を作って実際のコールバックを呼び出します。

```js
var callbackPtr = libsudoku.Runtime.addFunction(function (resultPtr) {
    var r = new Uint32Array(libsudoku.HEAPU8.buffer, resultPtr, 81);
    callback([].slice.call(r));
});
```

コールバックで渡される`result`はC上で`unsigned [81]`なので、HEAPから81個の32bit整数の配列を`Uint32Array`で切り出し、それを普通の`Array`に変換してコールバック関数を呼び出すようにしています。`ccall`や`cwrap`は、中でこういったHEAPアクセスを行ってJavaScriptオブジェクトとメモリ値との相互変換をしています。

`library.Runtime.addFunction(f)`が返す関数ポインタに限らず、ポインタ値は、`"number"`として`ccall`や`cwrap`の関数の引数に渡します。

関数呼び出しが終わったあとは、`library.Runtime.removeFunction(ptr)`で削除し、`addFunction`できる場所を開けてやります。Emscriptenなライブラリでは、Cと同様にこういった**リソース管理を手動で行う**必要があります。

### main部分と実行

上述のラッパーを用いた、`sudoku-main.c`と同様の処理を行うコードが以下になります。

```js
// sudoku-call-libsudoku.js 
var libsudoku = require("./libsudoku.js");

var output = function (board) {
    var unsignedBoard = new Uint8Array(new Uint32Array(board).buffer);
    return libsudoku.ccall("output", undefined, ["array"], [unsignedBoard]);
};

var sudoku = function sudoku(board, callback) {
    var callbackPtr = libsudoku.Runtime.addFunction(function (resultPtr) {
        var r = new Uint32Array(libsudoku.HEAPU8.buffer, resultPtr, 81);
        callback([].slice.call(r));
    });
    var unsignedBoard = new Uint8Array(new Uint32Array(board).buffer);
    sudoku._cfunc(unsignedBoard, callbackPtr);
    libsudoku.Runtime.removeFunction(callbackPtr);
};
sudoku._cfunc = libsudoku.cwrap("sudoku", undefined, ["array", "number"]);

// main
if (process.argv.length <= 2) {
    // example problem from http://rosettacode.org/wiki/Sudoku
    var problem = [
        8, 5, 0, 0, 0, 2, 4, 0, 0,
        7, 2, 0, 0, 0, 0, 0, 0, 9,
        0, 0, 4, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 1, 0, 7, 0, 0, 2,
        3, 0, 5, 0, 0, 0, 9, 0, 0,
        0, 4, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 8, 0, 0, 7, 0,
        0, 1, 7, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 3, 6, 0, 4, 0
    ];
    console.log("[problem]");
    output(problem);
    console.log("[solution]");
    sudoku(problem, output);
} else {
    for (var i = 2; i < process.argv.length; i++) {
        var problem = Array(81);
        for (var j = 0; j < 81; j++) {
            var ch = process.argv[i].charCodeAt(j);
            problem[j] = 0 <= ch && ch <= 9 ? v : 0;
        }
        console.log("[problem]");
        output(problem);
        console.log("[solution]");
        sudoku(problem, output);
    }
}
```

以下のように、`main`を含めてをコンパイルした時と同様に、**外部ライブラリ不要**でそのままで実行できます。

```bash
$ iojs sudoku-call-libsudoku.js
[problem]
85.|..2|4..
72.|...|..9
..4|...|...
---+---+---
...|1.7|..2
3.5|...|9..
.4.|...|...
---+---+---
...|.8.|.7.
.17|...|...
...|.36|.4.

[solution]
859|612|437
723|854|169
164|379|528
---+---+---
986|147|352
375|268|914
241|593|786
---+---+---
432|981|675
617|425|893
598|736|241

```

# 実行速度の分析

ネイティブ実行の`sudoku`、Cコード全部を変換した`sudoku.js`、ライブラリ`libsudoku.js`を利用する`sudoku-call-libsudoku.js`の実行時間は以下のようになりました。

```
$ time ./sudoku
real	0m0.020s
user	0m0.015s
sys	0m0.002s
```

```
$ time iojs sudoku-call-libsudoku.js
real	0m0.355s
user	0m0.313s
sys	0m0.037s
```

```
$ time iojs sudoku.js
real	0m0.888s
user	0m0.312s
sys	0m0.045s
```

Cでmainを実装するより、ライブラリ利用だけにしたほうが速いようです(外部ライブラリ関数は`printf`等を避け`puts()`のみを使うようにしたのですが)。

ちなみに、[JavaScriptでバックトラック実装したコード](https://gist.github.com/bellbind/2415a53ff67b28233d94)での実行時間は、

```
$ time iojs sudoku-backtrack.js
real	0m0.723s
user	0m0.684s
sys	0m0.030s
```

となりました。

盤面を1回解くだけならCコード全部を変換したものより速いのですが、これはmain部分のコストが大きく影響しているからでしょう。ライブラリ利用なものからは、倍の時間がかかっており、ソルバー部分はEmscriptenで倍速になったといえます。

# 疑問: `ccall`での`struct`値渡しの方法

`ccall`や`cwrap`では、たとえば`float`4つが入った`vec4`のような**(ポインタ渡しにしない)`struct`値を渡す手段がない**ように見えます。

# 参考: Emscriptenの最適化及びデバッグオプション

gcc/clangと同様に最適化及びデバッグのオプションには、O0-3とg1-4がありますが、その意味は別物でEmscripten固有の意味を持っています。

- O0: 最適化なし(デフォルト)
- O1: デバッグコードが削除される
- O2: 出力がminifyされる(`.js.mem`ファイルが生成される)
- O3: さらなる最適化をする(O2より若干ファイルが小さくなる)

O2やO3で同時に生成される`.js.mem`ファイルは生成した`.js`コードを実行するのに必須なファイルになります。

デバッグオプションは、**O2以降の最適化オプションと併用してminify化を抑制**するものになっています。

- g1: 空白を保存
- g2: 関数名を保存
- g3: 変数名を保存
- g4: ソースマップ(.mapファイル)を生成

# ソースコードへのリンク

完全なソースコードは、`Makefile`をつけてgistに置いてあります。

- https://gist.github.com/bellbind/64786335e8760e9c9756