パスワードを忘れた? アカウント作成
12222669 journal
変なモノ

route127の日記: チューリング完全なmov 2

日記 by route127

先週いわゆるバカ発見器を眺めてたら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.pl

   use 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.s

   

   BFBASICから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], al

   

   movfascatorに--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

この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。
typodupeerror

※ただしPHPを除く -- あるAdmin

読み込み中...