http://www.nicovideo.jp/watch/sm26713886
わずかながらですがピロ彦さんに協力させていただきました。なるほどわからんとおっしゃる方にはさらにわからない説明をいたします。
デジョンの魔法とスタック構造
FF1 から FF4 までは街やダンジョンでどのフロアを通っていたかという経路情報を保存しています。移動画面でのデジョンの魔法で通った場所へ戻るために使っているようです。
このデータの保存する形式が下から上へと積み上げるスタック方式というものを採用しています。
スタックのため push と pop があり、フロア移動で進むと push, 戻ると pop されます。これは出口が1つの街やダンジョンでは有効ですが、出口が2つになったり例外的な分岐があると、戻りが簡単に識別出来ないので全部進む扱いとして push してしまいます。
全て進むダンジョンでは矛盾をごまかすためにデジョンやテレポが使えない場合が多いです。ゲーム上は特殊なフィールドでワープができないと書いてます。
ここまでは FF1 から FF4 まで全ての共通事項で, FF1 と FF4 ではこれを有効に活用した TAS がすでに存在しています。 FF3 も活用はできるようですが他のバグを使った方が早いとのことで積極的に調べられていません。遅くても良ければ FF3 でも使えると思います。
FF2 ではこの経路情報をすべて push してしまう建物が結構あるのですが候補としてあがった場所を記載します。
- アルテアのアジト: ゲーム最初の開始場所と街からの入り口が2カ所ある
- バフスクの洞窟: 街側と大戦艦側で入り口が2カ所ある
- ディストの洞窟: 橋で落ちる場所があり分岐が複雑になる
(そもそも push 自体をしなければこんなバグがおきないないわけですが...)
スタックと NMI ベクタ
FF2 での移動向けスタックの特長は下記があります。
- CPU が実行する stack pointer を介す (FF3 まで同じ)
- stack の上限には NMI ベクタアドレスが書かれている
現状のプログラミングライブラリでは stack 構造, queue 構造, vector 構造などの概念を持つデータクラスを使っていますが、FF2 ではCPU が直接実行管理する stack pointer を使用しております。 (FF4 は stack 構造をもつデータ)
つまり、 JSR 命令のサブルーチンの実行や PHA 命令のような一時的な変数の保存や割り込み発生時のデータ保存でも stack は push され、役割を終えると stack は pop されています。
このように CPU が使う stack pointer では一時的な管理に使われることが普通で、平坦なプログラムを書く場合は上限付近は普段は使われることがありません。よってRAM 容量が少ないファミコンソフトではこの辺りを普通の変数として使うことがよくあります。ファミコンソフトではスタックの積みが多いと見なせる状態は半分ぐらいではないでしょうか。
FF2 の場合は NMI 割り込みのプログラムコードをソフトで動的に管理しながら実行するというとても特殊な実装で、伝説のプログラマ NASIR を裏付ける証拠なのは間違いないでしょう。
NMI ベクタにおける JMP 命令
動画での重要な点はディストの洞窟でソフトとして移動の上限に達した場合での戦闘です。
stack は CPU address $0100-$01ff の領域で $0100 が上限, $01ff が下限です。上限の $0100 には通常 jmp $fea1, jmp $fa31, rti の命令が状況に応じて書かえられます。
stack pointer のだいたいの位置:
- 移動の上限に達した場合は $011d
- さらにそこで戦闘を発生させると $010f
- さらにそこでダメージなどの計算をさせると $0101 とか、上限をループして下限付近の $01fe に到達
問題なのが $0100-$0102 に記載された jmp/rti 命令の領域を jsr 命令や push 命令で上書きしてしまう状況で上書きした場合はプログラムは正常に動かなくなって大半は止まります。
ここまでは以前からよく知られていたことですが、これを有用に活用する方法が発見されず、私を含め大半の人が放置していました。今回、ピロ彦さんが偶然にも名前欄に書かれた命令を実行することに成功したのが TAS の完成につながりました。
実際の命令手順
- ランドタートルへ攻撃するために計算する
- ランドタートルの回避率は高いのでここで再帰的に計算する
- この時点で jsr 命令によって $0101 と $0102 が上書きされる
- 計算途中に割り込みが発生し, 不正な jmp 命令が実行される
- 実行された不正な jmp 命令は一通り進み、 rts 命令によってある程度スタックは戻る
- 割り込み発生時点での命令までスタックが正常にもどるが、 rti ではなく rts 命令を実行するので PC が想定外の値に飛ぶ
- 不正なまま偶然 jsr $6785 という命令が実行される ($6785 はセーブデータ#3 の3人目の名前欄4文字目)
- 名前欄に書かれたデータを命令として実行しエンディング処理へ jmp
トレースログはすごく長いので要点だけ抽出します。
stack pointer 02 のときに jsr $9b4a が実行されて $0101 と $0102 に不正な jump address $9b4c が書き込まれる.
S:02 $9B4A:20 B6 9B JSR $9BB6 S:00 <- Sが0になることは異常 $9BB6:A5 C4 LDA $00C4 = #$FF S:00 $9BB8:C9 FF CMP #$FF S:00 $9BBA:D0 01 BNE $9BBD S:00 $9BBC:60 RTS (from $9BB6) --------------------------- S:02 $9B4D:E6 C5 INC $00C5 = #$01
再帰的な回避率の計算は一通り終わって、 stack は結構戻っている状態で NMI 割り込みが発生。 ROR 命令は別の命令の一部なので本来は実行されない。
S:11 $FC98:A2 10 LDX #$10 S:11 $FC9A:A9 00 LDA #$00 S:11 $FC9C:85 05 STA $0005 = #$EE S:11 $FC9E:85 04 STA $0004 = #$00 (割り込み発生のため stack に status register と PC の 3byte を push) S:0E $0100:4C 4C 9B JMP $9B4C S:0E $9B4C:6A ROR S:0E $9B4D:A9 23 LDA #$23 S:0E $9B4F:85 6B STA $006B = #$22
この計算も一通り終わるが割り込みの復帰のstackで rti ではなく rts を実行するので PC が $A028 となり、これが不正な命令となる。 $A042 で jsr $6785 ($20 $85 $67) を引く. これは本来は lda #$20 ($a9 $20); sta <$67 ($85 $67)となるはずの命令。
S:0E $9B84:60 RTS (jsr からの復帰ではないので from 表示がない) (割り込み発生前のstatus register と PC 下位 byte が PC に入る) S:10 $A028:04 UNDEFINED S:10 $A02A:66 A9 ROR $00A9 = #$76 S:10 $A02C:15 85 ORA $85,X @ $0088 = #$02 S:10 $A02E:67 UNDEFINED S:10 $A030:2F UNDEFINED S:10 $A033:05 85 ORA $0085 = #$11 S:10 $A035:66 A9 ROR $00A9 = #$BB S:10 $A037:69 85 ADC #$85 S:10 $A039:67 UNDEFINED S:10 $A03B:2F UNDEFINED S:10 $A03E:06 85 ASL $0085 = #$11 S:10 $A040:66 A9 ROR $00A9 = #$5D S:10 $A042:20 85 67 JSR $6785
長いので一旦ここまでにします。
