背景

コンピュータ・サイエンスのバックグラウンドを持たない者として、私は常々もっと低いレベルでプログラムのしくみを理解したい、そこに多くのエネルギーを費やしたいと考えてきました。

そこで、まずは基本を身につけるためにプログラミングの入門書である『 Programming from the Ground Up 』を入手したのですが、なかなか学習を始められずにいました。そんな時、ちょうどブラジルまでの11時間にも及ぶフライトが予定されており、それがこの本を読み始めるにはもってこいの機会となったのです。

読んでみると、この本がすっかり気に入ってしまいました。ただ、事例がLinux x86 GNUアセンブリ言語で書かれていたのです。私は64ビットのMac OS Xユーザでした…。アセンブラ、リンカフラグの例や、 i386 と x86_64 間のシンタックスを理解するのにはインターネットが欠かせないほど悪戦苦闘しました…。

（ i386 では、 exit システムコールへの戻り値は %ebx にではなく、スタックに格納されなければなりません。また、 x86_64 では、システムコール番号に 0x2000000 のオフセットを考慮する必要があることや、レジスタが異なること、 int $0x80 ではなく syscall を使わなくてはいけないことなどが分かりました…。こうしたことは、アセンブリ言語から始めた場合、いずれも容易なことではありません）。

そのあたりは一旦考えないことにしようと思いましたが、やはりそうもいかず、とりあえずダミーとなるx86のパーサを書き始めることにしました。PCのバッテリーが切れるまでに、手始めとして行うにはちょうど良かったのです（機内では電源が使えないこと以上に不便なことはないですね）。

数ヶ月後、英チェルシーのスタジアムでFacebookのハッカソンが予定されていたのですが、その機会に、実際にバイナリがどう実行されるのかを理解するため、x86エミュレータを実装してみようと思いました。

このプロジェクトに取り組んでもらうため、関係者を説得するのは容易ではありませんでした。私がおかしくなったわけではないということ、そして私自身、正しいエミュレータを書くことがいかに難しいかを当然承知した上で言っているのだということを分かってもらうには時間がかかりました。さらに、あくまで 楽しみ のためだけにエミュレータを書くこと、非常に基本的なケースのみを対象にするつもりだということを説明するのにも苦労しました。それでも、最終的にはUri Baghinに参加できることになったのです。

目標

初期の目標は、x86の最もシンプルなプログラムを実行することでした。それは、単にコード 0 でプログラムを終了することです。

# program.s

 .section __TEXT,__text
  .globl start
start:
  mov $0x1, %eax
  push $0x0
  call _syscall

_syscall:
  int $0x80

Mac OS Xで上記のプログラムをビルドする方法は以下の通りです。

$ as -static -arch i386 -o program.o program.s
$ ld -static -arch i386 -o program program.o

テストするために、次のコマンドで実行と終了コードの確認ができます。

$ ./program
$ echo $?

そこで、私たちは問題を2つに分けることにしました。バイナリで実際のアセンブリ命令を見つけることと、それを実行することです。

Mach-Oバイナリフォーマット

バイナリには単なるアセンブリコードよりも多くの情報が含まれています。レイアウトやアーキテクチャのサポート、仮想メモリへのロード、シンボルなどに関する情報です。

注釈： バイナリのレイアウトをよりよく可視化するために、 MachOView をお勧めします。これは、バイナリ自体を調べるときに非常に便利です。

バイナリのアセンブリコードを見つけるためには、ロードコマンドを読み取る必要があります。具体的には LC_SEGMENT ロードコマンドです。これにはバイナリのセグメントを仮想メモリにマップするための情報が含まれているのです。

LC_SEGMENT ロードコマンドには、いくつかのフィールドがあります。

• コマンド（この場合は LC_SEGMENT ）
• コマンドサイズ
• セグメント名（例えば __TEXT ）
• 仮想マシン（VM）アドレス（セグメントがコピーされる仮想メモリの場所）
• VMサイズ（セグメントが使用する仮想メモリのサイズ）
• ファイルオフセット（バイナリにおけるセグメントの位置）
• ファイルサイズ（バイナリにおけるセグメントのサイズ）
• VMプロテクションの最大値（VMに許された最大の保護レベル）
• VMプロテクションの初期値（VMに対する初期の保護レベル）
• セクション数（セグメントに含まれるセクションの数）
• フラグ（フラグの一覧は mach-o/loader.h の struct segment_command の直後のコードで確認できます）

しかし、とりあえずはVMプロテクションとフラグを無視して、単に File Offset から File Offset + File Size までのバイナリのコンテンツを、 VM Address から VM Address + VM Size までの仮想メモリ（このケースではシンプルな ArrayBuffer として実装されている）にコピーします。

次は、 LC_UNIXTHREAD ロードコマンドです。これにより、プログラムのメインスレッドの実行についての初期状態が分かります。

ここで重要なことは、 %eip （命令ポインタ）の初期値です。これにより、最初のプログラム命令の仮想メモリにおける位置、つまりコードが実際に開始される位置が分かります（注釈：サンプルのコードでは、レジスタをシミュレートするのではなくPCと呼ばれるグローバル変数を使っています）。

バイナリの実行

さて、仮想メモリにプログラムコードをマップできて、コードの初めにポインタを合わせるところまで来たので、あとは ただ 実行する必要があります。面白いのは、x86には可変サイズの命令があることです。そのため、どのくらいのバイトになるのか、最初にオペコードを読まなければなりません。

“KISS”（Keep It Simple, Stupid）の原則に従い、生成されたバイナリを objdump で逆アセンブルしました。 objdump は binutils パッケージと共にインストールすることができるCLIです。すると次のようになります。

$ brew install binutils # if you don't have it installed yet
$ gobjdump -d program

Disassembly of section .text:

00001ff2 <start>:
    1ff2:       b8 01 00 00 00          mov    $0x1,%eax
    1ff7:       6a 00                   push   $0x0
    1ff9:       e8 00 00 00 00          call   1ffe <_syscall>

00001ffe <_syscall>:
    1ffe:       cd 80                   int    $0x80

機能を全て整えたエミュレータを実装しようとは思っていなかったため、とりあえず必要なオペコードのシンタックスを探したところ、x86向けの適切なリファレンス http://ref.x86asm.net/coder.html が見つかりました。

そこで、オペコードから関数へのマップ（本当にプレーンなJavaScriptオブジェクトで実装しました）を作成しました。関数は、オペコードにより必要となれば、より多くのデータを読み取るための役割を担います。例えば次のようなものがあります。

var Functions = {};
Functions[0x6a] = function () {
  // Push one byte
  push(read(1));
};

読み込んだオペコードが実はオペコードの接頭語だった場合は、次のバイトにある実際のオペコードを読み取らなければなりません。

var Fn0x0f = {
  // jge
  0x8d: function () {
    var dist = read(4);
    if (!NG) {
      PC += dist;
    }
  },
  // ...
};

Functions[0x0f] = function () {
  // Call the actual function inside the prefix
  var fn = read(1);
  Fn0x0f[fn]();
};

最後に取り上げたいのは、システムコールです。実際にシミュレートする必要があるため、システムコール番号から関数へのマップをもう一つ使います。

var Syscalls = {};
Syscalls[0x01] = function () {
  // Fake exit, since there's no OS
  console.log('Program returned %s', Stack[Registers[ESP + 1]]);
  PC = -1; // Mark the program as ended by setting the program counter to -1
};

バイナリのロードには、 File API を使いました。htmlのページは、バイナリをドロップする input があるエントリーポイントであり、そのアウトプットはコンソールに表示されます。

サンプルコード

ハッカソンの結果として出来上がったコードは、この gist で見ることができます。ここには、説明の通り3つのファイルがあります。ローダー（ mach-o.js ）、オペコードのロジック（ x86.js ）、そしてエントリーポイントとして機能する index.html です。このコードは基本的なアセンブリ言語とC言語を実行させることができます。

注釈：libcを実行させることはできませんので、C言語は -static –nostdlib でコンパイルし、カスタムアセンブリのブートストラップを提供する必要があります。

なお、このコードは全てハッカソンの機会に書かれた、非常にシンプルなものだということを改めてご認識ください。そのため、もっと読みやすいものにする（または、そうした点をより良くする）というところにはあまり注力されておらず、それ以上の書き直しということもしていないものになっています。

それでも、 C言語 で書いて clang -O3 でコンパイルした fibonacci(40) を実行するには十分でした。 9分47秒 という驚異的な実行時間を叩き出しましたが。

追記： HackerNews で こちらのコメント を読み、 DataView を Uint8Array と交換したところ、今や fibonacci(40) は 1分53秒 と、断然速くなりました。 こちらの比較 によれば、 Perl や ruby 1.8 よりも速いものになったようです。