NES 基礎知識 - CPU

NES

今回は CPU について扱います。NES の PPU や APU はかなり複雑ですが、CPU は単純なので理解は容易です。CPU さえ理解しておけば乱数などの「目に見えない値」を探したり、ダメージ計算などの内部ロジックを追うには十分です。

ロジックを追う際は別にアセンブリ全体を読む必要はなく、デバッガで適当にブレークを仕掛けてその周辺を読む程度で大抵は事足ります。NES ゲームは大半がアセンブラ直書きだと思われるので、人間には読めないようなコードはそうそう出てこないはずです。PPU や APU を扱うコードを除けばそんなに凝ったアルゴリズムも使われていない様子です。

NES の CPU は 6502 カスタムの 2A03 です。オリジナル 6502 からの変更点は:

  • Decimal mode (10進演算)の削除
  • サウンド、DMA, コントローラ制御機能追加

といったところですが、コードを読むだけなら 6502 と同様に扱えます(以下、特に区別する必要がなければ 2A03 ではなく 6502 と書いてしまいます)。

まず 6502 の基本事項をまとめておきます:

  • 命令長は 1~3 バイト
  • スタックは上位アドレスから下位アドレスへ伸びる
  • ポインタはリトルエンディアン
  • 負数は 2 の補数で表す

プログラム側でのエンディアンは特に CPU に合わせなくても不都合は生じないので、16bit数をビッグエンディアンで管理したりしているゲームもあります。ただ全体的にはリトルエンディアンで統一しているゲームの方が多いようです。負数は 2 の補数を採用しているゲームが多く、その方が便利だと思いますが、たまに符号ビット+絶対値方式などを採用しているゲームもあります(『アストロロボSASA』など)。

レジスタ

6502 には以下のレジスタがあります:

名前 サイズ 用途
PC 16bit プログラムカウンタ。実行中アドレスを指す
A 8bit アキュムレータ。演算用
X 8bit インデックス。配列アクセスやその他雑用
Y 8bit X とほぼ同じ
S 8bit スタックポインタ
P 8bit ステータスレジスタ。後述

プログラム中で明示的に扱うのはほぼ A, X, Y のみです。PC はジャンプ命令などで暗黙的に変更されます。S は大抵 RESET ハンドラ先頭で初期設定され、以降は意識することはありません。P は主に分岐命令で暗黙的に参照されます。

ステータスレジスタ

ステータスレジスタ P は主に条件分岐用で、ビットレイアウトは以下の通りです(実質 6bit)*1:

bit 76543210
    NV..DIZC
bit 内容
N ネガティブフラグ。値が負(最上位ビットが立っている)なら 1, さもなくば 0
V オーバーフローフラグ。符号付きオーバフローが発生したら 1, さもなくば 0
D デシマルフラグ。2A03 には decimal mode がないので無意味
I IRQ 割り込み禁止フラグ。1 で禁止、0 で許可
Z ゼロフラグ。値が 0 なら 1, さもなくば 0
C キャリーフラグ。符号なしオーバーフローが発生したら 1, さもなくば 0

最もよく使われるのは N, Z フラグで、これらは大抵の命令において処理した値に応じて変化します。次によく使われるのが C フラグで、主に加減算とビットシフト/ローテート用です。とりあえず以上の 3 つだけ覚えておけば大体事足ります。

NES ゲームでは符号付き数はそこまで多用されないので V フラグはあまり使われません。I フラグは IRQ 割り込みを使わないゲーム(結構多い)では意識する必要はありません。

命令

本来はここでアドレッシングモードの説明を入れるところですが、具体例がないとわかりにくいので後回しにします。ここでは基本的に absolute アドレッシングモード(要するに 16bit アドレス指定)のみを使います。

ここでは非公式命令は扱いません。ほとんどの商用ゲームは非公式命令を使っていないので、普通は意識する必要はないはずです。暴走系のバグ技を使うなどの理由で必要な場合は NesDevWiki の資料などを参照。

リファレンス形式の資料としては http://obelisk.me.uk/6502/reference.html などがあります。また、たまに機械語の読み書きが必要になることがあるので http://www.oxyron.de/html/opcodes02.html のオペコード表の存在も覚えておくと便利かもしれません。

レジスタへのロード

LDA, LDX, LDY 命令で A, X, Y レジスタへ値をロードできます。"LOAD A", “LOAD X”, “LOAD Y” と覚えるといいです。

lda $0700 ; A = mem[0x0700]

ロード命令は N, Z フラグを書き換えます:

  • N: ロードした値の最上位ビット
  • Z: ロードした値が 0 であるか

メモリへのストア

STA, STX, STY 命令で A, X, Y レジスタの値をメモリへ書き込めます。"STORE A", “STORE X”, “STORE Y” と覚えるといいです。

sta $0700 ; mem[0x0700] = A

ストア命令はフラグを変更しません。

レジスタ間コピー

T** 命令でレジスタ間コピーができます。"Transfer A to X" のように覚えるといいです。

  • TAX: A -> X
  • TAY: A -> Y
  • TXA: X -> A
  • TXS: X -> S
  • TYA: Y -> A
  • TSX: S -> X

スタックポインタ S の設定/取得は TXS, TSX 命令を用いて X レジスタ経由で行うことになります。

TXS はフラグを変更しません。その他の命令は N, Z フラグを書き換えます:

  • N: コピーした値の最上位ビット
  • Z: コピーした値が 0 であるか

スタック操作

PHA, PHP で A, P レジスタをスタックへ push します。"PUSH A", “PUSH P” と覚えるといいです。
PLA, PLP で A, P レジスタをスタックから pop します。"PULL A", “PULL P” と覚えるといいです。

PLA は N, Z フラグを書き換えます:

  • N: pop した値の最上位ビット
  • Z: pop した値が 0 であるか

A, P 以外のレジスタやメモリ上の値は直接 push/pop できないので、いったん A へコピーしてから push/pop します:

; PUSH(X)
txa
pha

...

; X = POP()
pla
tax

6502 はスタックサイズが小さいため、これらの命令で明示的にスタックを操作することはあまりありません。ただし NMI/IRQ 割り込みハンドラでは割り込みから正しく復帰するために A, X, Y レジスタを push/pop するのが普通です。

フラグ操作

V, D, I, C フラグはプログラムから明示的に操作できます。V, D, I は割とどうでもいいですが、C の操作は頻出するので覚えておく必要があります。"SET C", “CLEAR C” のように覚えるといいです。

  • SEC: C = 1
  • CLC: C = 0
  • SEI: I = 1
  • CLI: I = 0
  • SED: D = 1
  • CLD: D = 0
  • CLV: V = 0

インクリメント/デクリメント

メモリ上の値に対しては INC, DEC を使います。
X レジスタに対しては INX, DEX を使います。
Y レジスタに対しては INY, DEY を使います。

これら全ての命令は N, Z フラグを書き換えます(加減算命令と異なり、V, C フラグは変化しないことに注意):

  • N: 演算結果の最上位ビット
  • Z: 演算結果が 0 であるか

A レジスタに対するインクリメント/デクリメント命令は存在しないので、加減算命令で代用します。

加算

ADC 命令でキャリー付き加算ができます。"ADD with Carry" と覚えるといいです。

これは A に対象を加算し、さらにキャリーフラグ C を加算します。ここでは「キャリー」=「繰り上がり」と考えるとわかりやすいです。要するに繰り上がりがあればさらに 1 を加えるというだけです。

通常の(キャリーなし)加算がしたければ、事前に C フラグをクリアしておく必要があります:

; A += mem[0x0700]
clc
adc $0700

ADC 命令は N, V, Z, C フラグを書き換えます:

  • N: 加算結果の最上位ビット
  • V: 符号付きオーバーフローが発生したか(同符号の値を加算した結果符号が変わったら真)
  • Z: 加算結果が 0 であるか
  • C: 繰り上がりが発生したら 1, さもなくば 0

キャリー付き加算は多倍長演算のためにあります。例えば、16bit 値 $0700 にもう 1 つの 16bit 値 $0702 を加えるには以下のようにします(リトルエンディアンを仮定):

; 下位バイトを加算(キャリーなし)
lda $0700
clc
adc $0702 ; ここで繰り上がりがあれば C = 1, さもなくば C = 0 となる
sta $0700
; 上位バイトを加算(キャリー付き)
lda $0701
adc $0703 ; 繰り上がりがあればさらに 1 加える(clc を行っていないことに注意)
sta $0701

24bit や 32bit の値なら更にキャリー付き加算を繰り返すだけです。この形のコードは頻出するので、慣れれば一目で「これは 16bit 値だな」などとわかるようになります。つまりサブピクセルなどが探しやすくなるわけです。

なお、他の CPU と異なり、キャリーなし加算を行う専用の命令はありません。

減算

SBC 命令でキャリー付き減算ができます。"SUBTRACT with Carry" と覚えるといいです。

これは A から対象を減算し、さらにキャリーフラグ C の否定を減算します。これだと少しわかりにくいので、「ボロー」という概念を導入すると理解しやすいです。「ボロー」は「キャリー」の反対、つまり繰り下がりです。要するに繰り下がりがあればさらに 1 を引くというだけです。

通常の(ボローなし)減算がしたければ、事前に C フラグをセットしておく必要があります(ADC の時とは逆):

; A -= mem[0x0700]
sec
sbc $0700

SBC 命令は N, V, Z, C フラグを書き換えます:

  • N: 減算結果の最上位ビット
  • V: 符号付きオーバーフローが発生したか(異符号の値を減算した結果符号が変わったら真)
  • Z: 減算結果が 0 であるか
  • C: 繰り下がりが発生したら 0, さもなくば 1

ADC の時と同様に、ボロー付き減算によって多倍長演算ができます:

; 下位バイトを減算(ボローなし)
lda $0700
sec
sbc $0702 ; ここで繰り下がりがあれば C = 0, さもなくば C = 1 となる
sta $0700
; 上位バイトを減算(ボロー付き)
lda $0701
sbc $0703 ; 繰り下がりがあればさらに 1 を引く(sec を行っていないことに注意)
sta $0701

ADC 同様、ボローなし減算を行う専用の命令はありません。

比較

CMP, CPX, CPY 命令で A, X, Y レジスタと対象の比較ができます。指定レジスタから対象を(ボローなし)減算し、結果を捨ててフラグだけ更新していると考えるとわかりやすいかもしれません。

これらの命令は N, Z, C フラグを書き換えます(V は変化なし):

  • N: 減算結果の最上位ビット
  • Z: 減算結果が 0 であるか
  • C: 減算で繰り下がりが発生したら 0, さもなくば 1

普通は Z, C フラグのみを用いて大小関係を判定します。例えば CMP 命令の場合:

  • Z == 0 ならば A == (対象)
  • C == 1 ならば A >= (対象)
  • C == 0 ならば A < (対象)

ビット演算

AND, ORA, EOR で and, or, xor 演算ができます。

  • AND: A &= (対象)
  • ORA: A |= (対象)
  • EOR: A ^= (対象)

これらの命令は N, Z フラグを書き換えます:

  • N: 演算結果の最上位ビット
  • Z: 演算結果が 0 であるか

not 演算を行う命令はありませんが、EOR で代用できます:

eor #$FF ; A ^= 0xFF, つまり A = ~A

ビットシフト

ASL で左シフトができます(空いた部分には 0 が入る)。"Arithmetic Shift Left" です。
LSR で右シフトができます(空いた部分には 0 が入る)。"Logical Shift Right" です。

これらの命令は A またはメモリ上の値が対象です。A をシフトする場合、オペランドを省略します:

asl       ; A <<= 1
lsr $0700 ; mem[0x0700] >>= 1

これらの命令は N, Z, C フラグを書き換えます:

  • N: 結果の最上位ビット
  • Z: 結果が 0 であるか
  • C: はみ出たビット

6502 には乗除算命令がないので、シフトを用いて定数乗除算を行うコードは頻出します。

シフト回数は 1 で固定です。回数指定シフト命令はありません。

ビットローテート

C フラグを含めた 9bit ローテートができます。

ROL で左ローテートができます(左シフトを行い、空いた部分に C が入る)。"ROTATE Left" です。
ROR で右ローテートができます(右シフトを行い、空いた部分に C が入る)。"ROTATE Right" です。

これらの命令は N, Z, C フラグを書き換えます:

  • N: 結果の最上位ビット
  • Z: 結果が 0 であるか
  • C: はみ出たビット

シフトとローテートを組み合わせることで多倍長シフトができます。例えば、16bit 値 $0700 (リトルエンディアン)を 1 回右シフトするには:

; 上位バイトを右シフト
lsr $0701 ; はみ出たビットが C に入る
; 下位バイトを C フラグ込みで右ローテート
ror $0700

ジャンプ

JMP 命令で無条件ジャンプができます。例えば jmp $8000 とすると $8000 へジャンプします。ポインタ経由の間接ジャンプもできますが、これはアドレッシングモードの項で述べます。

JMP 命令はフラグを変更しません。

分岐

N, V, Z, C フラグに基づく分岐ができます。分岐先オフセットは符号付き 8bit なので、範囲は [-128, 127] に制限されます。この範囲外へ飛びたい場合は JMP 命令などを併用する必要があります。

  • BMI: N == 1 なら分岐。"Branch if MINUS"
  • BPL: N == 0 なら分岐。"Branch if PLUS" (0 も正とみなす)
  • BVS: V == 1 なら分岐。"Branch if oVerflow Set"
  • BVC: V == 0 なら分岐。"Branch if oVerflow Clear"
  • BEQ: Z == 1 なら分岐。"Branch if EQUAL" (等しい <-> 減算結果が 0)
  • BNE: Z == 0 なら分岐。"Branch if Not Equal" (等しくない <-> 減算結果が非 0)
  • BCS: C == 1 なら分岐。"Branch if Carry Set"
  • BCC: C == 0 なら分岐。"Branch if Carry Clear"

分岐命令はフラグを変更しません。

いくつか例を見てみます:

; VBLANK を待つ。頻出
wait_vblank:
        lda $2002       ; VBLANK フラグが立っていれば最上位ビットが 1 になる
        bpl wait_vblank
; if(mem[0x0700] >= mem[0x0780])
;   ...
        lda $0700
        cmp $0780
        bcc less  ; mem[0x0700] < mem[0x0780] ならば less へ飛ぶ
        ...
less:
        ...
; 典型的ループ。頻出

; for(X = 5; X != 0; --X)
;   ...
        ldx #$05  ; X = 5 (即値ロード。アドレッシングモードの項で述べる)
loop:
        ...
        dex
        bne loop

分岐命令を if や for といった擬似コードに置き換えるのは多少慣れが必要ですが、内容的には難しくないので地道に考えれば問題ないと思います。あまりにも長大なコードだったり、分岐がスパゲッティ化していると多少しんどいですが…。慣れるまではいったん機械的に goto に置き換え、それを goto なしのコードに書き換えるようにするのも良いでしょう。

サブルーチン呼び出し

JSR 命令でサブルーチンを呼び出せます。"Jump to SubRoutine" です。

建前上は JSR で呼び出したサブルーチンからは必ず RTS で復帰するということになっていますが、実際には変則的なスタック操作を行っているゲームが普通に存在するため、この仮定は必ずしも成り立ちません。よって、内部的にどのようなスタック操作が行われるのか把握しておく必要があります。

JSR 命令が実行されると、JSR 命令のアドレス に 2 を加えたアドレス(これを「戻りアドレス」と呼ぶ)をスタックに push した後、オペランドのアドレスへジャンプします。例えば、

C000 : jsr $8000 ; JSR 命令は 3 バイト
C003 : ...

というコードは、0xC002 を push し、$8000 へジャンプします。大抵はこの後ルーチン $8000 が RTS で復帰して $C003 から実行が継続されますが、ルーチン $8000 内で変則的なスタック操作が行われている場合、$C003 に戻ってこないケースもありえます。

JSR 命令はフラグを変更しません。

サブルーチンからの復帰

RTS 命令でサブルーチンから復帰します。"RETURN from Subroutine" です。

建前上は JSR からの復帰に使うということになっていますが、実際には自分で戻りアドレスをスタックに積んでそこへジャンプする、などといった使い方もあります(RTS Trick)。

RTS 命令が実行されると、戻りアドレスを pop し、そのアドレスに 1 を加えたアドレスへジャンプします。

RTS 命令はフラグを変更しません。

割り込みハンドラからの復帰

RTI 命令で NMI/IRQ 割り込みハンドラから復帰します。"RETURN from Interrupt" です。

これに関しても一応内部的なスタック操作を把握しておく方がいいです。

  • NMI/IRQ 割り込みが発生すると、割り込み完了後に復帰すべきアドレスそのもの(JSR と異なり、1 を引かない)を push し、さらにステータスレジスタ P を push し、割り込みハンドラへジャンプします。
  • RTI 命令が実行されると、ステータスレジスタ P を pop し、復帰すべきアドレスを pop し、そのアドレスへジャンプします。

ビットテスト

BIT 命令でビットテストを行えます。レジスタを破壊せずに値を読めるので VBLANK 待ちなどでたまに使われますが、使用頻度は低いです。

BIT 命令は N, V, Z フラグを書き換えます:

  • N: 対象の bit7
  • V: 対象の bit6
  • Z: A と対象を and した結果が 0 であるか

BIT 命令のオペランド内に別の命令を埋め込んでおき、命令の途中へジャンプするというテクニックが稀に使われることがあります。

NOP

NOP は何もせずサイクルのみ消費する命令です。タイミング制御などで稀に使われます。不可解な NOP があったらハードウェア(PPU/APU など)周りの事情が関係している可能性があるかもしれません。

NOP はプログラムにパッチを当てる際に便利です。例えば、分岐命令を NOP で潰して分岐しないようにしてみる、などといったことができます。

アドレッシングモード

ここまでは基本的に 16bit アドレス指定のみを使ってきましたが、別の形式でオペランドを指定することもできます。これを「アドレッシングモード」と呼びます。

全ての命令で全てのアドレッシングモードが使えるわけではありませんが、大体不便なく使えるようにはなっています(この概念を「命令セットの直交性」と言うようです)。

オペランドなし (Implied / Accumulator)

CLC など、そもそもオペランドをとらない命令もあります。また、ASL などはオペランドを省略すると A レジスタが対象となります。一応公式的には前者を “Implied”, 後者を “Accumulator” と呼んで区別していますが、実用上は「オペランドなし」でまとめて覚えてしまって問題ありません。

Immediate

「即値」モードです。つまり、アドレスでなく値そのものを対象とします。例えば:

lda #$FF ; A = 0xFF

Zeropage

ゼロページアドレスを対象とするモードです。例えば:

lda $FF ; A = mem[0xFF]

Zeropage,X

ゼロページアドレスにインデックス X を加えたアドレスを対象とするモードです。加算結果がページ境界をまたぐ場合、ゼロページ内でループします。例えば:

ldx #$05  ; X = 5
lda $00,X ; A = mem[0x00+X],          ここでは $05 を読み取る
lda $FF,X ; A = mem[(0xFF+X) & 0xFF], ここでは $04 を読み取る

Zeropage,Y

Zeropage,X と同様ですが、インデックスとして X の代わりに Y を使うモードです。LDX, STX 命令でのみ使えます。

Absolute

16bit アドレスを対象とするモードです。例えば:

lda $0700 ; A = mem[0x0700]
lda $0000 ; ゼロページを指定しても構わない(が、コードサイズとサイクル数の無駄)

Absolute,X

16bit アドレスにインデックス X を加えたアドレスを対象とするモードです。加算結果がページ境界をまたいでも構いません。例えば:

ldx #$05    ; X = 5
lda $0600,X ; A = mem[0x0600+X], ここでは $0605 を読み取る
lda $06FF,X ; A = mem[0x06FF+X], ここでは $0704 を読み取る

Absolute,Y

Absolute,X と同様ですが、インデックスとして X の代わりに Y を使うモードです。

(Indirect,X)

ゼロページアドレスにインデックス X を加えたアドレスからポインタを取得し、それが指すアドレスを対象とするモードです。ポインタ取得時にページ境界をまたぐ場合、ゼロページ内でループします。例えば:

; X   = 5
; ptr = mem[0x00+X] | (mem[0x00+X+1] << 8), ここでは mem[0x05] | (mem[0x06] << 8)
; A   = mem[ptr]
ldx #$05
lda ($00,X)

このモードは大して便利でもなく、滅多に使われないので忘れてしまっても構いません。

(Indirect),Y

ゼロページアドレスからポインタを取得し、それが指すアドレスにインデックス Y を加えたアドレスを対象とするモードです。ページ境界については、

  • ポインタ取得時にページ境界をまたぐ場合、ゼロページ内でループします。
  • Y を加算した結果はページ境界をまたいでも構いません。

例えば:

; ptr = mem[0x00] | (mem[0x01] << 8)
; A   = mem[ptr]
; X   = mem[ptr+1]
ldy #$00
lda ($00),y
iny
ldx ($00),y

このモードは構造体アクセスやメモリコピーなどでよく使われるので慣れておくべきです。

Relative

分岐命令専用のモードです。機械語では符号付き 8bit の分岐オフセットがオペランドとなりますが、アセンブリ上ではアドレスまたはラベルで表記されるのが普通です。

(Indirect)

間接 JMP 命令専用のモードです。16bit アドレスからポインタを取得し、それが指すアドレスにジャンプします。例えば:

; ptr = mem[0x0700] | (mem[0x0701] << 8)
; jmp(ptr)
jmp ($0700)

次回は実際のゲームで使われる 6502 コードをいくつか読んでいきます。

*1:bit5, bit4 は物理的に存在せず、P がスタックに積まれたときにのみ目に見える形で現れます。これについては NesDevWiki に 解説がありますが、NES ゲームで BRK 命令が使われているのは見たことがないので特に意識する必要はないと思います

NES 基礎知識 - メモリ

NES

何回かに分けて NES に関する基礎知識を書いていこうと思います。簡単なリバースエンジニアリングができるようになる程度の内容を予定しています(ゲーム自作までは扱いません、というか扱えません)。ほとんど NesDevWiki に書いてあることばかりなので、ガチ勢の方にとっては特に目新しい内容はないと思います。ツールは好きなものを使えば良いと思いますが、一応 FCEUX を推奨しておきます。

今回はメモリについて扱います。自機座標やHPなどといった「目に見える値」のアドレスを探すだけならこれを知っていれば十分です。

NES の CPU 論理アドレス空間は16bit, 即ち $0000-$FFFF です。大まかなレイアウトは以下のようになっています(NESは memory-mapped I/O なので、I/O レジスタも含まれます):

アドレス 内容
$0000-$07FF RAM
$0800-$1FFF RAM ミラー
$2000-$2007 PPU I/O レジスタ
$2008-$3FFF PPU I/O レジスタ ミラー
$4000-$4017 APU/OAMDMA/コントローラ I/O レジスタ
$4018-$401F 没機能レジスタ (通常は無効)
$4020-$FFFF カートリッジ側で構成

RAM ($0000-$07FF)

$00-$FF, $0100-$01FF といった 256 バイトの塊を「ページ」と呼びます。

カートリッジ側で拡張 RAM が提供されることもあります。その場合、拡張 RAM はアドレス $4020-$FFFF 内のどこかにマップされます(マッパーによるが、$6000-$7FFF になることが多い)。拡張 RAM はバッテリーバックアップ機能などを除けば通常の RAM と同等に扱えます。この項では内蔵 RAM についてのみ述べます。

なお、電源投入時の RAM の状態は一応不定という建前になっていますが、全ビットが独立してランダムというわけではないようです(参考: TASVideos forum の Nach 氏の post)。ただ初代ファミコンとニューファミコンでも違いがあったりするので、乱数などを除けば基本的に RAM の初期値に依存するプログラムは書くべきではありません。

ゲーム起動後に特定の値のパターンを RAM へ書き込んでおき、RESET 割り込みハンドラでそのパターンをチェックすることでハードリセットとソフトリセットの(確率的な)判別ができます。これは商用ゲームでもよく使われているテクニックです。

ゼロページ

$00-$FF は「ゼロページ」と呼ばれ、他のページより短いコードサイズで高速にアクセスできます。準レジスタ的な存在といえます。ゼロページには作業用変数や頻繁にアクセスされる変数が置かれることが多いです。また、間接アクセス用のポインタが置かれることがあります(CPU のアドレッシングモードの関係)。

スタック

$0100-$01FF はスタック領域です(スタックは上位アドレスから下位アドレスへ伸びます)。必ずしも全体がスタックとして使われるわけではなく、一部を他の用途に使っているゲームも多いです。その場合、レイアウトは大抵以下のいずれかになります:

       (a)         (b)
$0100  ----------  ----------
       変数用      スタック用
       ----------  ----------
       スタック用  変数用
$01FF  ----------  ----------

いずれの場合も、スタックがオーバーフロー/アンダーフローした場合は当然何らかのバグが起こり得ます。なお、スタックへの push/pop によりページ境界をまたぐ場合はページ内でループします($0100 -> $01FF, $01FF -> $0100)。

スタックは最大でも 256 バイトしかないので、ほとんどのゲームは専らサブルーチン呼び出し/復帰用にスタックを使っており、明示的な変数の退避などはあまり行っていません。また再帰レベルがあまり深くならないようなプログラムになっていることが多いです。

スプライトバッファ

ほとんどのゲームでは $0200-$07FF 内のいずれかのページをスプライトバッファとして使います。これは PPU の OAM (Object Attribute Memory) と同じ構造になっており、DMA 機能によって OAM へ転送されます*1。スプライトバッファは 64 個のスプライト構造体の配列です。スプライト構造体は以下の通り(詳細は PPU の項で述べます):

struct Sprite{
    U8 y;    // 座標 y (画面上では +1 した位置に表示される)
    U8 tile; // タイル ID (スプライトサイズ (8x8/8x16) によって意味が異なる)
    U8 attr; // 属性 (パレット、前面/背面、水平/垂直反転)
    U8 x;    // 座標 x
};

NES の画面サイズは 256x240 なので、座標 y が 239 以上のスプライトは非表示となります。

スプライトバッファはページ 2 ($0200-$02FF) に置かれることが比較的多いようですが、他のページに置いているゲームもあります。また、稀ですがスプライトバッファを 2 つ用意して交互に切り替えながら使っているゲームもあります(『怒』など)。どのページがスプライトバッファかを調べるには、デバッガで $4014 への書き込みを捕捉し、書き込まれる値を見ます。その値がスプライトバッファページとなります(例えば、2 が書き込まれていれば $0200-$02FF がスプライトバッファ)。

多くのゲームではオブジェクト座標などの情報はスプライトバッファとは別に管理しており、スプライトバッファはあくまで表示専用としています。このようなゲームではメモリアドレスを調べる際にスプライトバッファ領域を最初から除外して考えることができます。ただし、メモリ節約のためにスプライトバッファ内の座標をそのままオブジェクト座標管理用に使っているゲームも存在します(『ギャラクシアン』など)。

オブジェクト

ゲーム内オブジェクトデータは $0200-$07FF のどこかに置かれることが多いです(ゼロページに全部置くのは容量的に厳しい)。オブジェクトデータの管理方法はゲームにより様々ですが、大まかには以下の 2 種類に分けられます:

1つのオブジェクトが (state, x, y) で表されるとする。

(a) オブジェクト構造体がそのまま配列化されている
| obj[0].state | obj[0].x | obj[0].y | obj[1].state | obj[1].x | obj[1].y | ...

(b) オブジェクト構造体のメンバごとに配列化されている
| obj[0].state | obj[1].state | ... | obj[0].x | obj[1].x | ... | obj[0].y | obj[0].y | ...

場合によっては自機データのみゼロページに置いたり、ボス専用の属性を別個に管理していたりなどの変形もありえます。

アクションゲームなどの場合、座標がピクセル単位だと動きが粗くなりすぎるので、固定小数点方式のサブピクセルを持っていることが多いです。これは RAM Search を使うか、メモリビューアを眺めていればアドレスの見当がつくことも多いですが、CPU の項で述べる加減算命令を知っていればデバッガを使って探すこともできます。

ミラー領域 ($0800-$1FFF, $2008-$3FFF)

「ミラー」とは、「アドレスは違うが実体は同じ」といった意味です。RAM については:

  • $0800 は $0000 と同じ
  • $0801 は $0001 と同じ
  • …
  • $0FFF は $07FF と同じ
  • $1000 は $0000 と同じ
  • …

PPU I/O レジスタについては:

  • $2008 は $2000 と同じ
  • $2009 は $2001 と同じ
  • …
  • $200F は $2007 と同じ
  • $2010 は $2000 と同じ
  • …

といった感じです。ただし、商用ゲームではこれらのミラー領域は基本的に使わないはず(少なくとも私は見たことがない)なので、これを意識する必要があるのは CPU が暴走するようなバグ技を使う場合くらいだと思います。

カートリッジ ($4020-$FFFF)

この領域はカートリッジ側で自由に使えるので、構成はゲームにより様々です。ただしある程度のテンプレ的なものはあり、拡張音源や割り込み機能などを含めたその構成を「マッパー」と呼びます。

どのマッパーであっても $FFFA-$FFFF には共通の役割があり、「割り込みベクタ」と呼ばれます。ここには CPU に対する 3 種類の割り込みを処理するハンドラのアドレスが格納されています:

アドレス 内容
$FFFA NMI 割り込みハンドラのアドレス
$FFFC RESET 割り込みハンドラのアドレス
$FFFE IRQ 割り込みハンドラのアドレス

iNES 形式 (*.nes) の ROM の場合、iNES ヘッダ にマッパー番号が書き込まれています。また、商用ゲームについては NesCartDB にカートリッジデータベースがあります。

マッパー 0

最も基本的なマッパーはマッパー 0 (NROM) で、ファミコン初期のゲームは大体これです。マッパー 0 のメモリマップは以下のようになります:

アドレス 内容
$4020-$7FFF (なし)
$8000-$BFFF PRG-ROM
$C000-$FFFF PRG-ROM

ただし、PRG-ROM が 16KB の場合、ミラーされて $8000-$BFFF と $C000-$FFFF の内容が同じになります。また、『ギャラクシアン』は PRG-ROM が 8KB しかなく、この場合 $8000-$9FFF, $A000-$BFFF, $C000-$DFFF, $E000-$FFFF の内容が全て同じになります。ミラーされたもののうちどれが「本体」かは割り込みベクタを見ればわかります。

後述するバンク切り替え機能がないため、PRG-ROM は 32KB が上限です。

$8000-$FFFF は ROM であり、$4020-$7FFF にはそもそも何も割り当てられていないので、これらの領域に対する書き込みは単に無視されます。

その他のマッパー

大抵のマッパーはマッパー 0 に倣って $8000-$FFFF を PRG-ROM に割り当てています。また、拡張 RAM がある場合は $6000-$7FFF に割り当てられることが多いです。

マッパーによっては「バンク切り替え」という機能があり、これによって $8000-$FFFF 内の一部に割り当てられた PRG-ROM の実体(これを「バンク」と呼ぶ)を動作中に差し替えることができます。これにより 32KB より大きい PRG-ROM を扱えます。ただし、最上位アドレス($FFFA-$FFFF を含む領域)に割り当てられたバンクは基本的に固定です(少なくとも私が見た範囲では)*2。この固定バンクには汎用性の高い重要なルーチンが多く含まれる傾向があります。例えば乱数生成器などは大体固定バンクに置かれていると考えていいでしょう。

例えば、マッパー 1 で拡張 RAM を持つ『ウィザードリィ』のメモリマップは以下のようになっています:

アドレス 内容
$6000-$7FFF 拡張 RAM (バッテリーバックアップ対応)
$8000-$BFFF PRG-ROM (可変)
$C000-$FFFF PRG-ROM (固定)

バンク切り替えの単位はマッパーにより 16KB だったり 8KB だったりまちまちです。同じマッパーでもゲームにより違いがあったりします。

バンク切り替えやその他拡張音源などの機能は、$4020-$FFFF 内に用意された I/O レジスタを読み書きすることでアクセスできます。このレジスタ構成はマッパーごとに異なります。ほとんどのマッパーは NesDevWiki に解説があるので、必要に応じて参照してください。

*1:DMA を使わずソフトウェアで転送することも可能だが、その場合ループを展開しても約 4 倍の時間がかかるため、まず行われない。スプライト数が極端に少ないゲームならありえるかもしれないが…

*2:ユーザがいつリセットボタンを押すかわからないため、割り込みベクタを含む領域を差し替えると対応するバンク全てに割り込みベクタとハンドラを書かなければならないためだと思われる

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 で見られるようです: