Brainf*ck interpreter 安全化

http://d.hatena.ne.jp/janus_wel/20100920/1284988462 の続きのようであまり関係ないハナシ。 brainf*ck は仕様どおりに実装すると食わせる script によっては memory access violation しちゃったりするのでそこらへん直そうかとか。

• http://github.com/januswel/brainf_ck/blob/d1a75ff5d958a60db2645dec55ba93959f37d00c/interpreter/cpp/brainf_ck.hpp
• http://github.com/januswel/brainf_ck/blob/d1a75ff5d958a60db2645dec55ba93959f37d00c/interpreter/cpp/main.cpp

前回からの変更点は 2 点。いや厳密には 3 点なんだけどもうひとつはしょうもない bug fix なので無視で。

• [ と ] がちゃんと対応してるかどうかを check する。
  • これ一応仕様の範囲内、なのかな。それぞれの挙動の説明に「対応する」とか書いてあるので余分に [ の書いてある script は弾くようにしないといけないんだろう。
  • 前回 '[' と ']' の対応関係を stack でアレコレしていたのでその stack の状態を調べればちゃんと対応してるかわかる。具体的に ']' がきた時点で stack が一段以上積まれてないとダメ、ってのと全 script をなめた後に stack に何か残ってたらダメ、という rule 。
• 確保された memory の外に access しようとしたら実行を中止する。
  • 例えば <+ みたいな script をそのまま実行すると何も言わずに落ちたり memory dump をでろでろ吐いたりするので memory 外に pointer が移動した時点で実行を中止しましょう、ってことにした。
  • これ <[>-] みたいな code 受け付けなくしちゃうんだけどまぁそんなもん書く方が悪いということで。
  • ここらへんを parse の時点で検出できるかと思ったんだけど brainf*ck 自体 Turing-complete なわけで要は実際に動かしてみるまで pointer がどんな動きするかわからないんだよね。

さて、で実行時に pointer が valid な範囲内にあるかどうかの check を加えたので前回より遅くなってるはず。というわけでやっぱり mandelbrot 集合を描画させて時間をはかると約 2 秒遅くなってる。これくらいなら問題ないんじゃないかなー。

./a.out ../../scripts/mandelbrot.bf  26.82s user 0.11s system 98% cpu 27.210 total