MonoDevelopの練習の一環としてBrainf*ckのGUIシミュレータの作成手順をまとめました。Gtk#とBrainf*ckの両方が一度に勉強できる内容となっています。
Brainf*ckの分岐をJIT
x86の分岐命令は相対アドレス指定のため、分岐元と分岐先のアドレスが決まらなければ相対アドレスを求められません。
Brainf*ckではループの先頭と末尾で分岐が出てきます。相互に分岐しているので少し複雑です。
ループの先頭
loop_begin: cmp byte ptr[esi], 0 # 80 3e 00 jz near loop_end # 0f 84 ?? ?? ?? ??
ループの末尾
jmp near loop_begin # e9 ?? ?? ?? ?? loop_end:
相対アドレスの基点は次の命令の先頭です。これはCPUが命令を読み込んでから実行するため、実行するときにはPCが次の命令に行っているためです。
- jz near loop_end => loop_end - (loop_begin + 9)
- jmp near loop_begin => loop_begin - loop_end
ループの末尾を書き込むときには既に先頭のアドレスが分かっているため、特に問題なく相対アドレスを計算することができます。
問題はループの先頭で、ループの末尾の位置が確定するまで相対アドレスが計算できません。
そのためループの先頭のアドレスをキャッシュして仮にゼロを書き込んでおいて、ループの末尾を書き込むときにループの先頭の分岐も書き込みます。（遅延評価？）
codes = []
begin = []
(中略)
elif cur == "[":
begin += [len(codes)]
codes += [0x80, 0x3e, 0x00] # cmp byte ptr[esi], 0
codes += [0x0f, 0x84, 0, 0, 0, 0] # jz near ????
elif cur == "]":
ad1 = begin.pop()
ad2 = len(codes) + 5
codes[ad1+5:ad1+9] = conv32(ad2 - (ad1 + 9))
codes += [0xe9] + conv32(ad1 - ad2) # jmp near begin
コード全体は以下を参照してください。
Pythonでポインタを扱う方法は以下を参照してください。
相対アドレスの計算については以下でも言及しています。
Brainf*ckでループ展開
第3回 コンパイラ実装会で@uho_iiotokoさんがBrainf*ckのトランスレータを実装されているとき、ちょっと面白いことが起きました。
元はC言語で実装されたBrainf*ckからアセンブラへのトランスレータです。トランスレート対象がC言語でも同じ結果となるため、Pythonで再実装した再現コードを掲載します。
【注】無限ループや入力は想定していません。
インタプリタとトランスレータの両方が実装されています。トランスレータではループ（ [ と ] ）を実装していないにも関わらず、トランスレートされたコードは正常に動作します。
$ ./bf.py helloworld.bf Hello World! $ gcc bf.c $ ./a.exe Hello World!
これはなぜなのか首をひねりました。結論から言うと、インタプリタを実行しながらトランスレートしているため、結果的にループを展開したコードが出力されていました。
例
たとえば次のようなBrainf*ckのコードを変換してみます。
ループを2回繰り返しますが、それが展開されます。
用語
参加者の@furandon_pigさんより、このようなループの展開を loop unrolling と呼ぶことを教えていただきました。調べるとWikipediaにも書いてありました。
最適化でループに細工をするような事例は知っていましたが、用語があることまでは知りませんでした。
Brainf*ckトランスレータ (5) 位置独立コード
前回に引き続きBrainf*ckのトランスレータを見ていきます。
Mac OS Xではデフォルトで位置独立コード（PIC）が要求されます。プログラムがどのアドレスにロードされるか決められないため、グローバル変数のアドレスを即値ではなく、プログラムカウンタからの相対で得たテーブルからポインタを取り出す必要があります。
非PICとPICを比較するため、まずはELFを見てみます。
i386(ELF) 非PIC
PICではないコードでは、オブジェクトコードの段階ではゼロが埋め込まれて、リンク時にアドレスが埋め込まれます。
例としてC言語コードのコンパイルとリンクを追ってみます。テスト環境はNetBSD/amd64で、gcc -m32を指定して32bitのコードを生成しています。
test.c
int mem[1];
int main(void) {
mem[0] = 1;
return 0;
}
C言語と対比するため-gオプションでデバッグ情報を埋め込みます。オブジェクトコードを生成して逆アセンブルします。
$ gcc -m32 -g -c test.c $ objdump -S test.o
main()でグローバル変数が関係するのは以下の部分です。memのアドレスが0になっているのが分かります。
mem[0] = 1; e: c7 05 00 00 00 00 01 movl $0x1,0x0 15: 00 00 00
リンクして逆アセンブルします。
$ gcc -m32 -o test test.o $ objdump -S test
先ほどの部分にmemのアドレスが埋め込まれているのが分かります。
mem[0] = 1; 80486ea: c7 05 d0 98 04 08 01 movl $0x1,0x80498d0 80486f1: 00 00 00
オブジェクトファイルにはリンク時にアドレスを埋め込む場所が記録されています。リンカがこれを見てアドレスを埋め込みます。
$ objdump -x test.o （中略） RELOCATION RECORDS FOR [.text]: OFFSET TYPE VALUE 00000010 R_386_32 mem （後略）
i386(ELF) PIC
PICではコードがどのように変化するか見てみます。リンカによって埋め込まれる値があまりにも多いため、逆アセンブルではなくコンパイラのアセンブリ出力を見ます。
$ gcc -m32 -fPIC -S test.c
memにアクセスしている部分と、関係する部分を抜粋します。
call __i686.get_pc_thunk.cx
addl $_GLOBAL_OFFSET_TABLE_, %ecx
movl mem@GOT(%ecx), %eax
movl $1, (%eax)
__i686.get_pc_thunk.cx:
movl (%esp), %ecx
ret
i386ではプログラムカウンタ（eip）を直接取得することができないため、__i686.get_pc_thunk.cxでcall命令によってスタックに積まれた戻り先アドレスをecxに入れることで、間接的にeipを取得しています。具体的には次のようなことがやりたかったのだと思われます。
movl %eip, %ecx
addl $_GLOBAL_OFFSET_TABLE_, %ecx
movl mem@GOT(%ecx), %eax
movl $1, (%eax)
GOT
ecxに足されている$_GLOBAL_OFFSET_TABLE_は定数ではなく、リンカがプログラムカウンタを考慮して値を埋め込みます。次の例を見ると理解しやすいかもしれません。
got.s
addl $_GLOBAL_OFFSET_TABLE_, %ecx addl $_GLOBAL_OFFSET_TABLE_, %ecx
$ gcc -m32 -nostdlib got.s $ objdump -d a.out （中略） 8048074: 81 c1 0c 10 00 00 add $0x100c,%ecx 804807a: 81 c1 06 10 00 00 add $0x1006,%ecx
ecxに命令のアドレスが入っていれば、計算結果は常に同じアドレスになります。
- 0x8048074 + 0x100c = 0x8049080
- 0x8049080 + 0x1006 = 0x8049080
Global Offset Table（GOT）とは、簡単に言えばグローバル変数や即値のポインタが入っているテーブルです。値そのものではなく、ポインタが入っています。更に間接参照してようやく値に到達できます。
- eip → GOT → ポインタ → 目的の値
GOTに値を入れれば間接参照が1段階減りますが、巨大な配列を定義すればすぐにGOTが埋まってしまうため、それを避けるためにこのような仕様になっていると思われます。プログラムカウンタに$_GLOBAL_OFFSET_TABLE_を足して得られるアドレスは、GOTの先頭ではなく中央です。相対アドレッシングは符号付きで表現されるため、負の値も活用するための仕様です。
ちなみにMIPSやAlphaでは、GOTの中央を指す専用のレジスタ（GP）が存在します。それらのCPUではレジスタが32個と多いため、1つくらいレジスタを割り当ててもほとんど問題にはなりません。
まとめ
まとめると、プログラムカウンタ相対でGOT（ポインタが集まっているテーブル）のアドレスを求めて、そこからポインタを取り出して目的のアドレスにアクセスするわけです。
x86_64(ELF) 非PIC
64bitではプログラムカウンタ（rip）が直接取得できるようになったため、即値は埋め込まずにプログラムカウンタ相対でアドレスを取得します。
$ gcc -S test.c
該当部分を抜粋します。
movl $1, mem(%rip)
逆アセンブルすると以下の通りです。
$ gcc -g test.c
$ objdump -S a.out
（中略）
mem[0] = 1;
400894: c7 05 5a 04 10 00 01 movl $0x1,1049690(%rip) # 500cf8<mem>
40089b: 00 00 00
（後略）
プログラムカウンタは次の命令を指しているため、相対アドレスを計算すると以下の通りとなります。これがコメントの意味です。
- 0x40089e + 1049690 = 0x500cf8
x86_64(ELF) PIC
PICでは32bitと同じようにGOT経由でアクセスします。
$ gcc -fPIC -S test.c
該当部分を抜粋します。
movq mem@GOTPCREL(%rip), %rax
movl $1, (%rax)
たった1命令でGOTからポインタを取得しています。GOTの中心から相対計算せずにいきなり算出しています。32bitと比べて非常に単純になっています。
i386(Mac)
さて、いよいよMac OS Xです。デフォルトでPICとなります。
$ gcc -m32 -S test.c
該当部分を抜粋します。
.comm _mem,4
（中略）
call ___i686.get_pc_thunk.cx
L00000000001$pb:
leal L_mem$non_lazy_ptr-L00000000001$pb(%ecx), %eax
movl (%eax), %eax
movl $1, (%eax)
（中略）
.section __TEXT,__textcoal_nt,coalesced,pure_instructions
.weak_definition ___i686.get_pc_thunk.cx
.private_extern ___i686.get_pc_thunk.cx
___i686.get_pc_thunk.cx:
movl (%esp), %ecx
ret
.section __IMPORT,__pointers,non_lazy_symbol_pointers
L_mem$non_lazy_ptr:
.indirect_symbol _mem
.long 0
.subsections_via_symbols
ELFでの$_GLOBAL_OFFSET_TABLE_に相当する部分が自動ではなく泥臭い表現になっていますが、やっていることはほぼ同じです。
x86_64(Mac)
シンボルにプレフィックスが付いている以外はELFのPICと同じです。
$ gcc -S test.c
該当部分を抜粋します。
movq _mem@GOTPCREL(%rip), %rax
movl $1, (%rax)
おわりに
以上でMac/Win/ELFでBrainf*ckのアセンブリ言語トランスレータの実装に必要な知識の説明は終了です。複数のアーキテクチャを比較したため複雑になりました。しかし自分の使っているアーキテクチャで実装したいというのが人情ですから、ある程度は網羅的な説明になるのは避けられません。
※こうなると収集が付かなくなる恐れがあるので、入り口としてi386-peに的を絞ったのがPE勉強会だったというわけです。
Brainf*ckトランスレータ (4) ループ
前回に引き続きBrainf*ckのトランスレータを見ていきます。
Brainf*ckでは変数の指すメモリの中身が0以外の間だけ回るループがあります。
# while (*(char *)esi) { ... }
start_loop:
cmpb $0, (%esi)
jz end_loop
# ...
jmp start_loop
end_loop:
cmp命令で0と比較して、一致した場合（jz）はend_loopに飛んで抜けます。jmpは無条件でstart_loopに飛びます。
ループが複数ある場合、ラベル（start_loop, end_loop）に別の名前を付ける必要があります。連番を振れば簡単そうですが、ループがネストすると厄介です。
相対ラベル
ラベルを局所化するテクニックとして相対ラベルがあります。数字のみのラベルが相対ラベルとして扱われます。参照元から見て前（f）か後（b）かをラベルの接尾辞に添えて指定します。相対ラベルは重複しても構いません。
※前・後の方向については次のセクションで取り上げます。
0:
cmpb $0, (%esi)
jz 0f # ↓方向に0:を探す
# ...
jmp 0b # ↑方向に0:を探す
0:
前・後
前か後かという表現はパーサの進行方向を基準としています。パーサはプログラムを先頭から見ていくため、画面での下が前に相当します。
後 ↓ ↓ ↓ 前
直感的に判断すると画面での上が前のように思えてしまうため、慣れが必要な表現です。
ネスト
ループがネストする場合、ネストレベルを相対ラベルの値に割り当てます。うまくペアができていることを確認してください。
0:
cmpb $0, (%esi)
jz 0f
1:
cmpb $0, (%esi)
jz 1f
# ...
jmp 1b
1:
jmp 0b
0:
上記では読みやすいようにインデントしています。Pythonとは異なり、インデントに文法的な意味はありません。
Brainf*ckトランスレータ (3) 変数とメモリ
前回に引き続きBrainf*ckのトランスレータを見ていきます。
Brainf*ckには変数が1つあります。トランスレータではこれをレジスタに割り当てます。
ABIにより関数呼び出しで破壊されないレジスタが決められています。保存されるレジスタを使えば、値の破壊を気にせずに変数とほぼ等価に使用できます。今回は32bitではesi、64bitではr12を使用します。
※64bitでesiを使用すると、関数（putcharなど）を呼び出したときに値が破壊される可能性があります。
メモリ
Brainf*ckの仕様では30,000バイトのメモリを持つと定義されています。変数はメモリのアドレスを指すポインタとして使用します。
アセンブリでは.commとしてbssにメモリを確保します。
# char mem[30000]; .comm mem, 30000
初期値
memの指すアドレスをレジスタに入れます。単純にmovするとmemの指すメモリの中身が入ってしまうため、lea命令を使用します。
# i386 .comm mem, 30000 .text leal mem, %esi
※Mac OS XではデフォルトでPIC（位置独立コード）を要求されるため、単純にleaで処理すると警告されます。PICは(5)位置独立コードで説明しています。
mov
leaがどういう命令かを説明する前に、比較対象としてmov命令を見てみます。
レジスタに即値を代入する場合、mov命令を使うのが基本的な方法です。
# eax = 0x1234 movl $0x1234, %eax # AT&T mov eax, 0x1234 # Intel
AT&T記法では$を外すとメモリの中身が対象となります。Intel記法ではアドレスであることを示すブラケットで囲みます。
# eax = *(long *)0x1234 movl 0x1234, %eax # AT&T mov eax, [0x1234] # Intel
メモリが以下の内容であれば、eax=0x12345678となります。
00001230: 00 01 02 03 78 56 34 12 aa bb cc dd 00 00 00 00
メモリから1バイトだけ取って上位をゼロで埋める場合はmovzx命令を使用します。AT&T記法ではmovzblとなりますが、ニーモニックがmovz、ソースのサイズがb、デスティネーション（レジスタ）のサイズがlとなります。
# eax = *(char *)0x1234 movzbl 0x1234, %eax # AT&T movzx eax, [0x1234] # Intel
メモリが先ほど示した内容であれば、eax=0x78となります。
lea
指定したアドレスが指すメモリの内容ではなく、アドレスの値を代入する命令がleaです。メモリの内容は一切関係ありません。
# eax = 0x1234 leal 0x1234, %eax # AT&T lea eax, [0x1234] # Intel
先ほどのmemの例では、memがアドレスとして扱われているため、メモリの中身ではなく、アドレスを値として取り出すのにleaを使用しています。
退避
mainはCRTから呼び出されます。esi/r12は呼び出し元に対して値を保存しなければならないため、mainから抜ける際に元の値に戻す必要があります。そのためmainの最初でpushして、最後でpopします。main自体の戻り値は0とするため、eaxに0をmovしてretします。
mainは通常のC関数と同じ扱いのため、呼び出し規約で必要とされる場合は接頭辞のアンダーバーを付けます。以下では接頭辞が必要ないELFの例を示します。
# i386(ELF)
.comm mem, 30000
.text
.globl main
main:
pushl %esi
leal mem, %esi
# ...
popl %esi
movl $0, %eax
ret
# x86_64(ELF)
.comm mem, 30000
.text
.globl main
main:
pushq %r12
leaq mem, %r12
# ...
popq %r12
movl $0, %eax
ret
増減
本来、変数の値を増減させる際に、変数の指すアドレスがメモリ空間からはみ出さないようにチェックする必要があります。今回は説明を単純化するためチェックは行いません。
Brainf*ckでは変数は1ずつ増減します。x86では1だけ増やす命令がinc、1だけ減らす命令がdecです。
# i386 incl %esi # esi++ decl %esi # esi--
# x86_64 incq %r12 # r12++ decq %r12 # r12--
メモリの増減
Brainf*ckにはメモリの中身を1バイト単位で増減させる命令があります。ニーモニックの接尾辞bでバイト指定にして、オペランドを括弧で囲みます。
# i386 incb (%esi) # (*(char *)esi)++ decb (%esi) # (*(char *)esi)--
# x86_64 incb (%r12) # (*(char *)r12)++ decb (%r12) # (*(char *)r12)--
AT&T記法での括弧は、Intel記法でのブラケットに相当します。AT&T記法での接尾辞がIntel記法ではキーワードとして表記されるため、見た目は長くなります。
# i386 .intel_syntax noprefix inc byte ptr [esi] # (*(char *)esi)++ dec byte ptr [esi] # (*(char *)esi)--
# x86_64 .intel_syntax noprefix inc byte ptr [r12] # (*(char *)r12)++ dec byte ptr [r12] # (*(char *)r12)--
Brainf*ckトランスレータ (2) 呼び出し規約
前回に引き続きBrainf*ckのトランスレータを見ていきます。
今回のトランスレータでは、OSごとの差異を吸収するためシステムコールを直接呼ばずにlibcを呼びます。以下に呼び出し規約をまとめます。
| arch | 引数 | 接頭辞 |
|---|---|---|
| i386(Win) | スタック | あり |
| i386(ELF) | スタック | なし |
| i386(Mac) | スタック（16バイトアラインメント） | あり |
| x86_64(Win) | スタック32バイト予約 + RCX, RDX, R8, R9, スタック | なし |
| x86_64(ELF) | RDI, RSI, RDX, RCX, R8, R9, スタック | なし |
| x86_64(Mac) | ELFと同じ（スタックは16バイトアラインメント） | あり |
これらを具体的に見ていきます。
i386(Win)
引数をスタックに積んでcallします。スタックは呼び出し元で後片付けをします。シンボルに接頭辞としてアンダースコアを付けます。関数の戻り値はeaxで返します。
※この規約はcdeclと呼ばれています。スタックの後片付けが異なるstdcallという規約もありますが、ここでは取り上げません。
AT&T記法とIntel記法を併記します。AT&T記法では命令の後にサイズを示す接尾辞l（long=32bit）が付き、即値の接頭辞として$、レジスタに%が付きます。2オペランド命令の順番が逆になります。
# putchar('A');
pushl $65
calll _putchar
addl $4, %esp
.intel_syntax noprefix
# putchar('A');
push 65
call _putchar
add esp, 4
スタックの効率化
関数の呼び出し後に毎回スタックを片付けると冗長です。最初にスタックを確保して、複数の処理を行ってから、最後に片付ける方法に書き換えます。
# スタックを確保
subl $4, %esp
# putchar('A');
movl $65, (%esp)
calll _putchar
# putchar('B');
movl $66, (%esp)
calll _putchar
# スタックを解放
addl $4, %esp
.intel_syntax noprefix
# スタックを確保
sub esp, 4
# putchar('A');
mov dword ptr [esp], 65
call _putchar
# putchar('B');
mov dword ptr [esp], 66
call _putchar
# スタックを解放
add esp, 4
i386(ELF)
シンボルに接頭辞を付けない以外はWindowsと同じです。AT&T記法のみ示します。
subl $4, %esp movl $65, (%esp) calll putchar addl $4, %esp
i386(Mac)
シンボルには接頭辞が付きます。関数呼び出し時のespは16バイト境界に揃える必要があります。SDKのasはGNU binutilsではなくAT&T記法しか受け付けません。
※nasmなどサードパーティーのアセンブラを使用すればIntel記法も可能ですが、一部文法の違いによりコンパイラが出力したアセンブリを流用するときに修正が必要となります。書き方を調べるのにコンパイラの出力を利用するのが手軽なため、今回はAT&T記法を使用します。
subl $12, %esp movl $65, (%esp) calll _putchar addl $12, %esp
スタックを12バイト確保しているのは、この部分がcallで呼ばれた直後だと仮定しているためです。call命令は戻り先をスタックに積むため、呼ばれた時点で既に4バイトが使用中となります。
このようにアラインメントを揃える必要がある場合、i386(Win)で最初に示した随時pushするやり方では毎回パディングが発生するため、効率がかなり悪くなります。
x86_64(Win)
32bitではレジスタが8個でしたが、64bitでは倍の16個に増えました。レジスタに余裕が出来たため、引数も最初の4つまではレジスタ（RCX, RDX, R8, R9）で渡すようになりました。ただしスタックはその4つのレジスタの分を確保しておく必要があります。呼び出し元でスタックに値を入れる必要はありませんが、呼び出し先で必要に応じて退避するのに使用されます。
シンボルの接頭辞はありません。32bitと64bitで接頭辞の扱いが異なるのは、今回取り上げた中ではWindowsだけです。
subq $32, %rsp movl $65, %ecx callq putchar addq $32, %rsp
ecxを操作するとrcxの上位32bitはクリアされます。そのためrcxではなくecxにmovしてもゴミは残りません。
x86_64(ELF)
Windowsとは呼び出し規約が異なります。引数は最初の6つまでをレジスタ（RDI, RSI, RDX, RCX, R8, R9）で渡して、残りをスタックで渡します。Windowsのようにレジスタ渡しの分までスタックを確保しておく必要はありません。
movl $65, %edi callq putchar
スタックの操作が発生しないため、非常に単純です。
x86_64(Mac)
レジスタの使用方法はx86_64(ELF)と同じです。ただしi386(Mac)と同じようにrspは16バイト境界に揃える必要があります。
subq $8, %rsp movl $65, %edi callq _putchar addq $8, %rsp
i386の例と同じように、callで呼ばれた直後と仮定してrspのアラインメントを揃えています。
