FF2 の 45階層バグ

昨夜 twitter で簡単に書きましたが、表現能力に限界があるのでこちらに書き直します。

バグの概要

FF1 から 4 までは城やダンジョンのフロアの切り替えを履歴として持ち、デジョンやテレポで戻ることができます。履歴はスタックとして持ち、出口が1カ所のダンジョンでは「戻る」と積まれたスタックも「戻り」ます。出口が複数のダンジョンは「戻る」の概念がないのでスタックは「進み」ます。

FF1, FF2 ではスタックという概念をもつデータ領域ではなく、 CPU が Stack Pointer として使う本当のスタックに積まれます。*1

FF3 は未調査、 FF4 はスタックという概念をもつデータ領域です。

FF2 では出口が複数のダンジョンでの矛盾を解消するために、デジョンやテレポの使用を禁じ、 stack のあふれを防ぐ方法として、移動数を制限してます(自分は回数を数えてないがこれが45らしい)。
この移動数の上限の設定は不適切で、この状態で戦闘を起こすとスタックがさらに積まれて、先頭の $0100 を越え、1周して末尾の $01ff も破壊することになります。
破壊された stack では CPU の正常な動作は続けられずプログラムは暴走します。

stack の先頭と NMI ベクタ

NMI ベクタは NMI 割り込み(=vblank割り込み)が発生したときに実行するアドレスで $ffa0 に格納されています。普通は ROM のプログラムを実行するのですが、FF2 のプログラムは RAM のプログラム $0100 を実行します。

スタック領域は基本 $01ff から上へ積まれ、特殊なプログラムを組まない限り、半分ぐらいは使わないので、RAM 領域がが少ないファミコンではスタックの先頭を普通の変数として利用することが多々あります。

このため、 $0100 を NMI ベクタとして利用したと考えられます。

(デバッガでの表示, CPU が $0100 に書かれたプログラムを実行している)

FF2 のプログラムを見ると、この $0100 には場合によって処理する命令を動的に変更しています。*2 基本的に書かれる命令は RTI (0x40) か JMP xxxx (0x4c) です。


(プログラムが $0100 に動的に命令を設定している)

stack 溢れと NMI からの任意のプログラム実行の可能性

前述のように特定のダンジョンで過度にフロアの切り替えを行うと、CPU の Stack がどんどん積まれていき、ソフトで設定された上限の状態で S レジスタ (stack pointer)が移動画面で $011d になります。

ここでステータスメニューを開くと S: $0117, 戦闘では S:$0113 になります。この状態でゲームプログラム上で何段もスタックを積ませるとベクタアドレスの $0102, $0101, $0100 にプログラムとしては不正な値を書き込むことができます。

(戦闘の入力待ちの状態、SPの値が $0100 に接近する)

スタックが溢れたときにベクタに書かれる「不正な値」を操作することができれば、任意のプログラムが実行できることになります。

stack にはなにが書き込まれるか

通常、CPU stack 操作として書き込まれるデータは下記です。

  • 割り込み発生時のステータスレジスタと PC (CPU が強制的に書き込む)
  • 割り込み発生後のレジスタの待避 (A,X,Yレジスタ) (ソフトが任意に書く)
  • jsr 実行 (rts 実行時の復帰 PC の保存)
  • 通常の処理のデータ退避としての push

ここまでの基本をみて FF2 でベクタデータとしてなにが書き込まれるかをみていると大半は jsr 実行でのアドレスの PUSH です。これは ROM になるので任意コードの実行では使い物にならないと思います。


($0101が jsr 命令によって書き込まれた例, $9b3d の jsr $9b56 の時点で S が $0100 となり、復帰アドレスの $9b3f が $0101 へ書き込まれる)


(NMI が発生したあとの jmp 先は不正な値なので暴走する)

任意の命令の実行は実現できるのか

簡単に試してみたところ、暴走はキャラクタが行動を起こす途中にスタックが多く積まれ、その中で NMI が発生するようです。私が予想するに、任意のアドレスに jmp させるには相当な研究が必要なようです。 (例として名前欄の $6100 台) いくつかの点を上げてみます。

  • 発生条件が不安定に見える
  • jsr で push するのは ROM アドレス
  • アクションゲームと異なり、自由度が低い

発生条件の不安定は手でいれてみたところ、xxxxがxxxの魔法を使ったときに停まるということが決まっておらず、不具合発生時のベクタの値も何通りかありました。発生条件はいまのところ不安定ですが、1つの戦闘を正常に終わらせることはできませんでした。

フロア移動を上限値とした場合、S は奇数となるので $0101 からの2バイトがかかれ、これが JMP 先となります。JSR の場合は必ず ROM address が書かれるので任意の命令の実行としては都合が悪いです。
これを避けるには $0101 と $0102 を分離させて書かせ、 $0102 にデータ 0x61 や 0x00 を書かせるほうがよいでしょう。分離させるには S を偶数にするか、1 byte push を起こさせる必要があります。フロア移動の上限値の1つ前は偶数ですが、$0102を破壊できる可能性は下がります。
$0100 の jmp を利用することに限界があれば、別の方法でなんとかして PC を 自由度が高い RAM に飛ばす必要があります。

最後の点は、敵キャラが激しく動いたりしないのでプログラムに負荷をかけづらかったり、変数の調整範囲が少ないということです。つまり敵の Y 座標を命令として埋め込むという方法がとりづらいということです。

*1:ファミコンの CPU ではスタックはメモリアドレス $0100-$01ff に固定されています。

*2:普通はこんなことをしないので、Nasir はすごい人だという話に尾ひれがついていったと思います。