route127の日記: チューリング完全なmov 2
先週いわゆるバカ発見器を眺めてたらx86のmovはチューリング完全で、実際にmovのみで出力するコンパイラの実装がなされたとの話を聞いた。
正直元の論文見てもよく分からないけれど具体的な手順が載っていたので試してみたがSegmentation faultが出た。
よくわからず手を出したのでまあそんなもんかと思うけれど取り合えずコンパイラの出力でmovがずらりと並ぶところが見られたのでひとまず気が済んだ(あのバイナリはきっと酸っぱい)。
32bit版windows上のCygwin環境で以下を試した。
配布されているコンパイラはBFを受け付けてx86のアセンブリを出力(インテル記法)するので、まずBFで書かれたプログラムを用意する。
1. BFBASICのインストールとソースファイルの作成
例文集から適当にコピペするなら2.へ。
今回は配布元の手順どおりBFBASICでBASICからBFを生成する。
BFBASIC1.41を解凍すると分かるのだがjava製のトランスレータなので、付属のシェルスクリプトを利用することになる。
wget http://brainfuck.cvs.sourceforge.net/viewvc/brainfuck/bfbasic/1.41/bfbasic-1.41.zip
unzip bfbasic-1.41.zip
echo 'PRINT "Hello world!"' > 01.bas
./bfbasic.sh 01.bas > 02.bf
02.bf
[ BF Code Produced by BFBASIC 1.41 ]
>+[>[-]+[>++++++++++++++[>+++++>+++++++>++++++++>++++.>+++.>----..+++.>++++.>+.[-]>-]
2. 生成されたBFを一応検証する
Language::BFを利用して以下のPerlスクリプトを作成し生成したBFを確かめた。
03.pluse strict;
use warnings;
use Language::BF;my $bf = Language::BF->new(+[>[-]+[>++++++++++++++[>+++++>+++++++>++++++++>++++.>+++.>----..+++.>++++.>+.[-]>-]run;
print $bf->output;3. movfascatorの入手とインストールに続いてBFのコンパイル
git cloneとかやるべきなんだろうがいまいちgitを良く分かっておらずwgetでしのいでいる。wget --no-check-certificate https://github.com/xoreaxeaxeax/movfuscator/blob/master/movfuscator.c
gcc movfuscator.c -o movfuscator
movfuscator 04.s
wc -l 04.sBFBASICからBFへの変換で22Bから212Bへとおよそファイルサイズが10倍になるがmovfascatorの出力は29KBとBFの100倍程度、2051行のアセンブリファイルになった。
4. アセンブリを眺める
tail -1500 04.s | head -20
mov eax, 0
mov al, [ebx+edx]
mov al, [incb+eax]
mov [ebx+edx], al
mov eax, [on]
mov ebx, [s_ms+eax]
mov edx, [dp]
mov eax, 0
mov al, [ebx+edx]
mov al, [incb+eax]
mov [ebx+edx], al
mov eax, [on]
mov ebx, [s_ms+eax]
mov edx, [dp]
mov eax, 0
mov al, [ebx+edx]
mov al, [incb+eax]
mov [ebx+edx], almovfascatorに--mmioオプションつけても特に出力は変わらなかった。
mov以外に結構eq、neq、and、notなんかがあるけどこれはいいのか?5. アセンブルとリンク
アセンブリを眺めていてインテル構文なのだと見当がついたので、nasmでアセンブルする前に.intel_syntax擬似命令使えばgccでアセンブルできるんじゃないかと思ったけれど、実際やってみたら失敗した。
仕方なくapt-cygでnasmをインストールした。
また、nasmの-fオプションをどうするか悩むが最初winでやってうまく行かずcoffとかas86も試すがうまく行かず。apt-cyg install nasm
nasm -fwin 04.s -o 05.o
file 05.o
ld 05.o -o 06.exe
file 06.exe-fにobjを指定するとnasmがwarning出す。
-fにas86を指定するとldがオブジェクトファイルをリンクに失敗する。
6. 実行./06.exe
Segmentation fault
某C++エヴァンジェリストのblogでも書いたが (スコア:0)
movがチューリング完全というよりjmpがチューリング完全なのだ。高級言語で言えばwhile文なのだからほとんど自明。
Re:某C++エヴァンジェリストのblogでも書いたが (スコア:1)
これか
http://cpplover.blogspot.jp/2015/06/x86mov.html [blogspot.jp]