FC 『カイの冒険』 デバッグモード

デバッグモードと思われる未使用コードを見つけました。

$C2FF-$C300 を NOP で潰すことで未使用コードが有効になり、以下の機能が使えるようになります:

  • タイトルで1コンの AB を押しつつ NORMAL START を選ぶことで面セレクトができる
  • 面セレクト画面から普通に抜けると、その後2コンでメモリ書き換えができる
  • 面セレクト画面を抜ける際に2コンの A を押していると、メモリ書き換えができなくなる代わりに2コンの A を押している間自機が無敵になる

面セレクトとメモリ書き換えのスクリーンショット:

面セレクト メモリ書き換え

当該未使用コードは $C301- にあります。また、ROM自体を書き換えなくても、チートで $017F を非0にするとメモリ書き換えができ、$015F を非0にすると2コン無敵が使えるようになります。

6502逆アセンブラに関する考察 その3

前回、アドレス単位のコード解析について考察しました。今回はその結果を元に制御フローを考慮したコード判定を行うことを考えます。

このパスは誤判定を避けるため、極力保守的な方針で解析を行います。まずは6502の制御フローについて再確認します。

制御フロー命令

6502の大半の命令は直線的に実行されます(実行後にプログラムカウンタが直後のアドレスを指す)。こうならない可能性があるのは以下の命令です:

  • BRK
  • KIL (12種類)
  • 分岐命令 (8種類)
  • JSR
  • RTI
  • RTS
  • JMP abs
  • JMP ind

これらを「制御フロー命令」と呼ぶことにします。

ただし、割り込みを考慮すると任意の命令実行後にプログラムカウンタが書き換わる可能性があります(例えば、読み書きすると即座に割り込みを発生するようなI/Oレジスタを考えることができる。また、BRK が割り込みハイジャックによりNMIルーチンへ飛ぶケースなどもありうる)。とはいえこれは特殊ケースなので当面は無視します。

全ての制御フロー命令について、実行後の飛び先(割り込みは無視する)を考えると:

命令 飛び先の数 特定可?
KIL 0
JSR 1 可
JMP abs 1 可
BRK 1 割り込みベクタがわかれば可
JMP ind 1 基本的に不可
RTS 1 基本的に不可
RTI 1 基本的に不可
分岐 2 (or 1) 可

「特定可」とは、飛び先の具体的なアドレスがわかるかどうかということです。今回はポインタ値やスタック状態の追跡までは行わない(一般的には不可能なケースもある)ので、JMP ind, RTS, RTI の飛び先は特定不可としています。

なお、JSR/RTS は必ずしも対になっているとは限らず、RTS があっても JSR の直後のアドレスに戻ってくるとは限りません(NESプログラムでは変則的なスタック操作がしばしば行われており、既に一つのテクニックと化しています)。また、分岐命令は実際には無条件分岐(飛び先がどちらか1通りのみ)だったり、2つの分岐先が一致するケース(かなり稀でしょうけど)もありえます。

制御フローを考慮したコード判定

制御フローを追うことでなるべく多くのアドレスを非 UNKNOWN 状態にすることを考えます。

CODE 状態のアドレスは順方向に影響を及ぼします。つまり、CODE 状態のアドレスからの制御フローは基本的に全て CODE となります。

NOTCODE 状態のアドレスは逆方向に影響を及ぼします。つまり、NOTCODE 状態のアドレスに到達する制御フローは基本的に全て NOTCODE となります。

分岐のない直線的な制御フローの場合について図示すると:

CODE-UNKNOWN-UNKNOWN-UNKNOWN-...    -> CODE-CODE-CODE-CODE-...

...-UNKNOWN-UNKNOWN-UNKNOWN-NOTCODE -> ...-NOTCODE-NOTCODE-NOTCODE-NOTCODE

このように変換できるということです。

割り込みなど特殊な事情があると以下のように衝突が生じるケースも考えられます:

CODE-UNKNOWN-UNKNOWN-NOTCODE

この場合、途中の UNKNOWN が CODE, NOTCODE どちらになるかという問題が生じますが、この優先順位については後述します。

制御フローの探索自体は全て順方向に行い、UNKNOWN または CODE 状態のアドレスから開始します。UNKNOWN 状態のアドレスから開始するものを UNKNOWN 探索、CODE 状態のアドレスから開始するものを CODE 探索と呼ぶことにします。

UNKNOWN 探索では UNKNOWN -> NOTCODE の変化のみが起こります。CODE 探索では UNKNOWN -> CODE の変化のみが起こります。

簡単のため、まず UNKNOWN 探索を収束するまで行い、次に CODE 探索を収束するまで行います(これにより先に述べた優先順位が決まります)。なお、この順番が逆だと全体として収束しないことがありえます(後述)。

探索中、例えば JMP ind 命令などが現れて次アドレスが特定できなくなったり、次アドレスが入力ファイルの範囲外となることがあります。このような特定不可アドレスや範囲外アドレスが現れたらそれ以上制御フローを追跡できないので、そこで探索を打ち切ります。ただし範囲外アドレスについてはコード判定は通常通り付加します。

UNKNOWN 探索

各アドレスについて探索済みか否かのフラグを管理し、未探索アドレスがなくなるまで全ての UNKNOWN アドレスから探索を行います(探索中のループは前述のフラグで検出され、自動で探索が打ち切られます)。

現在見ているアドレスを orig とし、ここからの飛び先の数(0,1,2)によって処理を分けます。

飛び先が0通り (KIL 命令) の場合、単に探索を打ち切ります。

飛び先が1通りの場合、次アドレスを next とし、以下のように処理します:

orig next 結果
UNKNOWN UNKNOWN 探索続行
UNKNOWN CODE 探索打ち切り
UNKNOWN NOTCODE orig を NOTCODE に。探索打ち切り

飛び先が2通り(分岐命令)の場合、2通りの次アドレスを next1, next2 とし、以下のように処理します:

orig next1 next2 結果
UNKNOWN UNKNOWN UNKNOWN next1, next2 から探索し、両方 NOTCODE なら orig を NOTCODE に。探索打ち切り
UNKNOWN UNKNOWN CODE 探索打ち切り
UNKNOWN UNKNOWN NOTCODE 次アドレスを next1 として探索続行
UNKNOWN CODE * 探索打ち切り
UNKNOWN NOTCODE NOTCODE orig を NOTCODE に。探索打ち切り

探索は順方向ですが、NOTCODE への変化は逆方向に起こるので、実際には探索時に制御フローを記録しておき、NOTCODE への変更は一括で行う必要があります。

CODE 探索

各アドレスについて探索済みか否かのフラグを管理し、未探索アドレスがなくなるまで全ての CODE アドレスから探索を行います(探索中のループは前述のフラグで検出され、自動で探索が打ち切られます)。

現在見ているアドレスを orig とし、ここからの飛び先の数(0,1,2)によって処理を分けます。

飛び先が0通り (KIL 命令) の場合、単に探索を打ち切ります。

飛び先が1通りの場合、次アドレスを next とし、以下のように処理します:

orig next 結果
CODE UNKNOWN next を CODE に。探索続行
CODE CODE 探索続行
CODE NOTCODE 探索打ち切り(割り込みなど特殊な事情があるとみなす)

飛び先が2通り(分岐命令)の場合、2通りの次アドレスを next1, next2 とし、以下のように処理します:

orig next1 next2 結果
CODE UNKNOWN UNKNOWN 探索打ち切り
CODE UNKNOWN CODE 探索打ち切り
CODE UNKNOWN NOTCODE 次アドレスを next1 として探索続行
CODE CODE * 探索打ち切り
CODE NOTCODE NOTCODE 探索打ち切り(割り込みなど特殊な事情があるとみなす)

CODE 探索より UNKNOWN 探索を先に行うのはここの分岐命令の処理のためです(CODE 探索が先だとここで UNKNOWN 探索が必要になってしまう)。

出力フェーズ

これは解析結果を参照しつつ入力ファイルを先頭から逆アセンブルしていくだけです。非公式命令については、CODE ならコード、UNKNOWN ならデータとして出力するのが妥当なところでしょう。

以上の処理を Python で実装したもの を置いておきます(ドキュメント未整備)。一応以前うまく行かなかったケースは改善されたっぽいですが、あんまりテストしてないのでまだ見落としなどがあるかもしれません^^;

アドレスラベルやコメントなどについても検討中ですが、これらについてはそもそもインタラクティブに操作できるUIがないと辛いものがあるんですよね(IDA はその点が有利なのは認めざるを得ない)。radare2 という解析ツールにちょっと期待してたりするんですが、これはレトロCPUはあまり眼中にないようで、6502モードだと命令の区切りがおかしくなったりするので今のところ微妙です。

NES以外については今のところあまり考察してませんが、BizHawk の Code/Data Logger がSNESなどに対応しているようなので、これを使えばある程度精度を上げられるかもしれません。

6502逆アセンブラに関する考察 その2

前回述べた前提に基づいて解析フェーズを考えます。

簡単のため、解析はマルチパスで行うことにします。具体的には以下の通り:

  • アドレス単位のコード判定
  • 制御フローを考慮したコード判定(これ自体も複数パス。後述)

以前作ったC++版では解析を1パスで行っていましたが、これだとコードが複雑になる上、たまに致命的な誤判定が生じることがありました。簡単な例を見てみます:

80FF : db $02
8100 : db $60 ; 単独の RTS はデータとみなす(ヒューリスティック)
8101 : db $02

; ...

; ここは本来コードなのだが…
8200 : lda $00
8202 : ldx $01
8204 : ldy $02
8206 : jmp $8100 ; データ領域への JMP なので、ルーチン全体がデータとみなされてしまう!

このようなケースでは $8200- が全てデータとして出力されてしまいます。ここでは単独の RTS をデータとみなすというヒューリスティックが誤っていたためにこうなったわけですが、そうしたヒューリスティックと制御フロー解析が分離されていなかったために、一箇所の誤りが全体に波及し、しかもその修正が難しいという結果になりました。そこで今回は、ヒューリスティックを用いるのはアドレス単位のコード判定のみに限定し、制御フロー解析は誤判定を避けるため極力保守的に行うことにします。

アドレス単位のコード判定

最初のパスとして、制御フローを考慮せずに個々のアドレスに対するコード判定を行います。

といっても、実際にプログラムを動かすことなく100%の精度でコード判定を行うのは不可能です。例えばNESの場合は非公式命令は滅多に使われないだとか、ある範囲のアドレスは普通は読み書きしないなどといった事実からある程度の推測は可能ですが、例外は常にありえます。よって、このパスはハードコードされた基準ではなくユーザ設定に基づいて行います。出力がおかしくなったらここの設定を変えて再試行することになります。

なお、実際にプログラムを動かしたとしても、わかるのはあるアドレスが「コードである」ことだけです。このときあるアドレスが実行されなかったとしても、条件を変えれば実行される可能性があるわけで、あるアドレスが「コードでない」ことを100%保証することはできません。

とはいえ、設定としてある程度妥当なプリセットは考えられるので、それを以下で詳しく見ていきます。

NES用プリセット

最も保守的なものはこんな感じでしょうか:

  • KIL 命令 (12種類) は非コード
  • XAA 命令 (0x8C) は非コード
  • I/Oレジスタ ($2000-$4017) を実行するものは非コード
  • 書き込み専用レジスタ ($2000 など) を読み取るものは非コード
  • 読み込み専用レジスタ ($2002 など) に書き込むものは非コード*1

これは割と信頼できそうです。KIL, XAA はともに非公式命令で、前者はCPUを停止させ、後者はそもそも動作が不安定とされているので、少なくとも商用ゲームではまず使われないでしょう。I/Oレジスタに関しても妥当なところかと思います。

よりアグレッシブに行くなら、以下の条件を加えることが考えられます:

  • 全ての非公式命令は非コード
  • BRK 命令 (0x00) は非コード
  • RAMミラー ($0800-$1FFF) を読み書き/実行するものは非コード
  • PPUレジスタのミラー ($2008-$3FFF) を読み書きするものは非コード

これでも大抵はうまく行くと思いますが、非公式命令を使っている商用ゲームも存在します。BRK を禁止するとデータ領域がかなりきれいに出力されます*2が、これは公式命令で別に禁止されているわけでもないので、使っているゲームがあってもおかしくないと思います(私は見たことがありませんが)。ミラー領域に関してはそもそも仕様の範囲内なのかどうかよくわかりませんが、使っているのを見たことがないのでとりあえず入れてみました。

後はマッパーによっては $4018-$FFFF についても読み/書き/実行を制限できるので、メジャーなマッパーについてだけでもプリセットを作っておくと役立ちそうです。ただしこれにはちょっとした罠があります。例えばマッパー0のゲームは普通 $4018-$7FFF を読み取りませんが、任天堂『ゴルフ』ではオペコード兼オペランドのByteが存在するために $40A9 の読み取りが発生しています。

例外が全くない設定というのはなかなか難しいので、出力がおかしくなった場合は手動でコード判定を行い、残りの部分について自動解析を適用するという形になるかと思います。

実行記録の利用

実際にプログラムを実行することで、少なくとも実行された部分はコードだと判定できます。例えば FCEUX には Code/Data Logger (CDL) が付属しています。*3

ただし、FCEUX CDL はオペコードとオペランドを区別しないため、確実にコードと判定できるのはコード領域の先頭のみです。

次のパスでは、これらの手段で得られた結果を元に制御フローを考慮したコード判定を行います。具体的には次回。

*1:2017/03/02 追記: NES版アルカノイドはなぜか $2002 への書き込みを行っているので、これも確実とまではいえないようです。

*2:BRK は実質的に2Byte命令です。

*3:BizHawk の Code/Data Logger はNESには未対応のようです。

6502逆アセンブラに関する考察 その1

tl;dr: taotao54321/td6502

懲りずに6502逆アセンブラについて考えてみます。まあ素直に IDA を買えという話なのかもしれませんが、結構お高いですし、プロプライエタリでない選択肢があってもいいと思うので…。なお、私はNES以外のプラットフォームには詳しくないのでNESの話が多くなると思います。

何が問題か

要はなるべくコードとデータを自動で判別したいということですね。例えば以下のような出力はしてほしくないわけです:

; NES用プログラム(マッパー0とする)

lda $00         ; 不満: 直後がデータなんだから、ここもデータのはず
db $02          ; 非公式命令 (KIL) なのでデータとして出力
jmp ($5555)     ; 不満: $5555 には何も割り当てられてないんだから、普通はデータのはず

それで以前適当な自動判別機能が付いた逆アセンブラを作ってみたのですが、これは対象によってうまく行ったり行かなかったりで微妙だったので、この際きちんと考え直して文書として残しておこうと思ったわけです(大して高度なことではないですが)。

逆アセンブラの機能としては他にもアドレスラベルの処理やコメント付加、出力整形など色々な話題がありますが、ここではコード判定のみに絞って書くことにします。

前提

逆アセンブラを解析と出力の2フェーズに分けて考えます。

解析フェーズではアドレス空間 ($0000-$FFFF) 内の各アドレスについてコード判定を行い、判定結果として以下の3通りの値のうちいずれかを与えます:

  • CODE (コード。厳密にはオペコード)
  • NOTCODE (非コード。厳密には非オペコード)
  • UNKNOWN (不明)

初期状態では全アドレスが UNKNOWN です。ここから解析フェーズでなるべく多くのアドレスを非 UNKNOWN 状態にして(ただし誤判定は極力避ける)、出力フェーズではその結果を利用して出力を行います。

なお、難しくなりすぎるのでバンク切り替えの追跡までは行わないことにします。

次回から解析フェーズを考えていきます。

Python Packaging User Guide を訳してみた

Python

Python Packaging User Guide (PyPUG) を日本語訳してみました。Python のパッケージング周りは変化が激しいのでいつまで役に立つのかはわかりませんが…。

PyCon JP で毎年パッケージング関連の発表があるようなので、とりあえず現状を把握するにはこれを見るのがいいのかな?2016年の発表は YouTube で見られるようです:

Sphinx で日本語改行が空白になる件について

Sphinx日本ユーザ会の「不自然な空白が表示される」にある通り、japanesesupport.py を使うと解消されるようです。ただしこれをそのまま使うと改行だけでなくリンクの前後の空白なども潰されてしまい、英単語が頻繁に混じる文章だとかなりギチギチした見た目になります。Issues に置いてあるパッチ版を使うといい感じになるようです(なぜか issues が放置されてるので、もしかしたら何か問題があってマージされてないのかもしれませんが…)。

この問題って Sphinx だけでなく markdown とか色々なところで(このブログでも)現れてますが、どこも大抵放置してるんですよね。多分皆ブラウザが対応しないのが悪いと思ってるということなんでしょうけど。

FC 『AD&D プールオブレイディアンス』を少し解析してみた

相当手強いのでとりあえず不完全ですが途中結果だけ置いておきます。

今までで一番読みにくいコードだと感じています。バンク切り替えが8K単位になっている上に、同じバンクが異なるアドレスにロードされたりしてややこしいんですよね…。ルーチンの先頭でいちいちレジスタをスタックに退避していることが多かったり、他のゲームではあまり見られない特徴があるので、もしかしたらアセンブラでなく何らかの高級言語で書かれているのかもしれません。