Brainf*ckを、直接実行可能バイナリにコンパイルした話
なんとなくカレンダーを埋めたいという衝動に駆られるので記事を書きます。
おととい書いたELFを書く話によって、僕らは事実上任意の機械語列をELFにすることができるようになりました。次は、当然任意のBrainf*ckで書かれたプログラムをコンパイルできるようになるべきです。
つまり今度の目標は、「与えられたBrainf*ckのプログラムを実行可能なELFに変換する」ということになります。
コンパイラというと、実際は、機械語を直接吐き出すのではなく、一度アセンブリ言語やなんらかの中間言語を生成して、そのあとでアセンブラ等によって機械語を吐き出すという形なものが書きやすく一般的（一般性を十分担保できるほど僕はコンパイラの実装を読んでいないが）な気がしますが、今回は、bfのコードを受け取って直接機械語に翻訳してみようと思います。
というのも課題の指定がそうなので。課題ではコンパイラそのものもアセンブリ言語で書く必要がありますが、とりあえず方針を立てる意味でもPythonで書いてみようと思います。またPowerPCではなくx86-64上のLinuxで動くプログラムについて考えます（なのでこの記事は課題そのものではないです）。
keystone engine
そうはいっても、吐き出す機械語をマニュアルを読んで生成するのはさすがに億劫なので、keystone engineという、CTFしているとたまに見かけるAssembly Frameworkの力を借ります。実際これで遊んでみたのを記録にしようと思っただけという話でもあります。
Keystoneを使うと次のように、アセンブリを対応する機械語に変換してくれます。
In [2]: from keystone import *
In [3]: ks = Ks(KS_ARCH_X86, KS_MODE_64)
In [4]: def asm(code):
...: c, _ = ks.asm(code)
...: return ''.join([chr(x) for x in c])
...:
In [5]: asm("mov rax, 1")
Out[5]: 'H\xc7\xc0\x01\x00\x00\x00'
In [6]: asm("nop")
Out[6]: '\x90'
In [7]: asm("jmp 0")
Out[7]: '\xeb\xfe'
書いたもの
現状はこんな感じで書いています。bfの仕様としては、とりあえず、めんどいのでメモリは100000バイトの領域を0x900000からmmapで確保するという適当なことをしてはいます。当然領域外へ出たら壊れます。 ここらへんちゃんとELF上に書いておけばいい話ではあるんですが、それをやるよりmmapした方が（書くのが）速いし、全体のサイズが小さいという話があるので、まぁ気が向いたらみたいなところが強い
あとはこれをアセンブリで書き出すだけではありますが、面倒なので気合いが出ればやろうという感じ
実行
せっかくなので、いくつかのbfのコードを実際にコンパイルしてみました。例えば、先日のesolangのCodeGolf大会で、@satosさんが書いた「与えられた2進数が三角数かどうか判定」するプログラムを実際に実行してみました（回答自体はTSGのGithubからみられます）。
ubuntu@ubuntu-xenial:~/ctf/experiment$ ./bf 00000011 00110111 10100101 00011111 01011001 10010100 00111100 01101000 11001000 01011011 10001000 10111110 01000010 01110011 10011001 10101100 00001010 01101001 00101101 11111101 11100111 00001000 00001111 10101011 00110010 11110111 00011100 11110110 00000000 10110001 01111000 00100011 01001110 10010000 00000110 00000001 00110011 00010101 10000101 11010010 00010101 01111101 00100001 01011010 00101110 11001010 11100000 00100100 10111110 00111110 11000000011110101111101100101010101101011000000110
一応正しく動いていそうです。
ちなみにコンパイルしたあとのバイナリをディスアセンブルすると、
こんな感じになります。Rev問だったら地獄ですね？
実際、同じ処理をペタペタ貼り付けているだけなので、ここらへんもう少し効率化とかすると楽しいかもしれません。
