読者です 読者をやめる 読者になる 読者になる

Brainfuck => ShaFuck translator

ShaFuck という言語があります。チューリング完全なのに、難解どころか、プログラムを書くことは不可能だと主張してる言語です。

http://esolangs.org/wiki/ShaFuck

不可能だと主張している理由は、入力として受け取ったコードを SHA1 した結果を BF として実行して、かつ 8 つの BF コマンドでないコードが実行されるとプログラムがエラー終了してしまうからです。

で、今回は Brainfuck から ShaFuck への翻訳機が書けたという話。コレ

http://shinh.skr.jp/obf/bf2sf.rb

shafuck-0.2 で実行可能な hello と cal

http://shinh.skr.jp/obf/hello.sf

http://shinh.skr.jp/obf/cal.sf.gz

どうやったかというと、 20 bytes (=160bits) のうち、 3 bytes くらいは 1/2**24 くらいの確率で狙ったやつが現われるので、先頭 3 bytes か末尾 3 bytes くらいは総当たりぶんまわせば欲しいものが見つかるので、後の 17 bytes をうまいこと無視するような組み合わせで、 Brainfuck の 8 命令を実現すればいい、と。今回私が使ったのは

+ => +>[ (17B)  (18B) ]<
- => ->[ (17B)  (18B) ]<
> => >[  (18B)  (18B) ]>
< => <[  (18B)  (18B) ]<
. => .>[ (17B)  (18B) ]<
, => ,>[ (17B)  (18B) ]<
[ => >[  (18B)  (17B) ]<[
] => >[  (18B)  (17B) ]<]

というような対応。 Brainfuck コマンド 1 つに対して 2 code chunks 、つまり 2048 bytes を消費するという。

http://shinh.skr.jp/obf/sf_find_ops.cc

なにかあれば下記メールアドレスへ。
shinichiro.hamaji _at_ gmail.com
shinichiro.h