ファミコンエミュレーターのキャリーとオーバーフロー
ファミコンエミュレーター (NES エミュレーター) を作るにあたり、低レベルプログラミング初級者が直面する壁の一つがキャリーとオーバーフローの違いです (断言) 。ファミコンの CPU である 6502 のステータスレジスタのフラグにはキャリーとオーバーフローがあります。これらのフラグは主に整数同士の演算でセットされます。キャリーはわかる、でもオーバーフローがわからないという方は多いのではないでしょうか。かく言う私もその一人でした。レジスタやステータスフラグについては知っているものとし、ここではファミコンエミュレーターの実装に必要な範囲でのみ説明します。より詳しく知りたい場合は 独習アセンブラ をお勧めします。
2 進数のススメ
実装に高水準言語を使うのであれば、整数同士の演算はごく簡単です。符号を考慮してくれるし、サイズも気にする必要がありません。小難しそうなビット演算を無視すれば低レベルプログラミング初級者でも実装を進めやすいでしょう。ですが、高水準言語の便利な整数型に頼りきってしまうとキャリーとオーバーフローの理解が難しくなると思います。どちらもビット演算の結果で変化するフラグであり、最初から符号なしの 2 進数で考えたほうが理解が早かったりします。気後れするかもしれませんがいざやってみるとそう難しいものでもないので、ぜひ 2 進数メインで進めてみてください。
キャリーとオーバーフローの違い
キャリーとオーバーフローの大きな違いは 符号の有無 です。 符号なし・符号つき整数のどちらの演算結果も表すフラグがキャリー で、 符号つき整数の演算結果を表すフラグがオーバーフロー です。ここで重要なのは、 符号の有無は人間だけに意味があり、コンピュータから見ればすべて符号なしの計算になる 、ということです。人間がどうやって符号を識別するのかと言うと、整数を表すビット列の最上位ビットで符号を判断します。 8 ビットで表される整数の場合 (6502 は 8 ビット CPU) 、最上位の 7 ビット目 (0 から数えます) が 0 であれば正の整数、 1 であれば負の整数とみなします。負の整数の場合はネガティブフラグがセットされます。
算術演算の種類
6502 の算術演算は、符号なし整数の加算と減算のみです。乗算と除算、符号つき整数の算術演算はありません。
符号つき整数の演算は符号なし整数の算術演算で行われます。符号つきの場合の特別な処理はなく、符号を表す 7 ビット目も含めて計算します。符号つき整数同士でも符号なし整数同士として計算し、計算結果を符号の有無で解釈してキャリーフラグとオーバーフローフラグをセットします。
加算
符号なし整数同士の演算 (キャリー)
計算結果が 8 ビットで表せる数を超えてしまう場合にキャリーが発生します。たとえば 8 ビットの 0xFF に 0x01 を足すと 9 ビットになります。
11111111 = 0xFF = 255
+ 00000001 = 0x01 = 1
-------------------------
+ 100000000 = 0x100 = 256
加算により 7 ビット目 (ビットの位置は 0 から数えるので念のため) が繰り上がると 8 ビット目が 1 になります。 6502 は 8 ビット CPU なので、 9 ビット以上の整数は (工夫をしないと) 扱えません。となると 8 ビット目の 1 は捨てるしかないので残りの 8 ビットしか使えず、 0xFF + 0x01 の結果は 0x00 になってしまいます。ファミコンのゲームのバグや裏技は 255 や 256 といった数字が絡むことが多々ありますが、桁あふれのビットの切り捨てが関係するからですね。
11111111 = 0xFF = 255
+ 00000001 = 0x01 = 1
---------------------------
= (1) 00000000 = 0x00 = 0
このとき、 桁あふれの発生を示すために使われるのがキャリーフラグです。 オーバーフローフラグは符号なし整数同士の演算では登場しません。演算後にキャリーフラグがセットされていれば、結果が 0xFF (255) が超えてしまったのかどうかを簡単に判別できます。
符号つき整数同士の演算 (キャリー、オーバーフロー)
符号つき整数同士でも加算は簡単です。符号が正負のどちらであろうが、符号なしと同様の方法で計算できます。ただし、問題となる状況が 2 つあります。
- 計算結果が 8 ビットで表せる数を超えてしまう場合
- 計算結果の符号と、正解であるはずの符号が異なる場合
1 番目は符号なし整数同士の加算と同じです。対応も同じで、キャリーフラグがセットされます。
2 番目がポイントです。計算結果と正解であるはずの符号が異なる場合とは、「正の同士の加算結果が負の整数になる」などといった状態です。なぜそんなことになるのか？次の計算を見てください。 (※ fuwasegu さんのご指摘を受けて例を修正・変更しました)
01111111 = 0x7F = 127
+ 00000010 = 0x02 = 2
---------------------------
= 10000001 = 0x81 = -127
普通に考えれば 127 + 2 の結果は 129 のはずです。ところが符号つき整数として計算すると -127 になってしまいます。計算結果は 8 ビット内に納まっているので桁あふれによるビットの切り捨てはありません。符号の正負を表す 7 ビット目が 1 になってしまうので、負の整数として扱われることになってしまいます。このとき、 本来正解であるはずの符号が逆になってしまったことを表すのがオーバーフローフラグです。 ただし、オーバーフローはバグではありません。人間が望む計算結果にならなかったことを示すためにオーバーフローフラグが使われます。
計算時の符号の組み合わせは 4 つあります。
- 正 + 正
- 負 + 負
- 正 + 負
- 負 + 正
このうち「正 + 正」と「負 + 負」の同じ符号同士でのみオーバーフローが発生します。「正 + 負」と「負 + 正」では 7 ビット目が変化しても問題なく、計算結果は符号つき 8 ビット整数の範囲に納まります (最小値 -128 から最大値 127 までのどの組み合わせを加算しても -127 以上 126 以下に納まります) 。加算時のオーバーフローは 同じ符号同士の加算で、計算結果の符号が元の符号と異なる場合 に発生します。
一方、キャリーは「負 + 負」または「正 + 負」「負 + 正」で発生します。「正 + 正」では発生しません。要はどちらかの 7 ビット目がセットされていれば繰り上がる可能性があります。まとめると、符号の組み合わせとフラグの変化は以下のようになります。
- 正 + 正 (オーバーフロー)
- 負 + 負 (キャリー、オーバーフロー)
- 正 + 負 (キャリー)
- 負 + 正 (キャリー)
減算
次に減算ですが、引く数の 2 の補数表現を使って加算で表せます。 0 以上の正の整数の 2 の補数は、すべてのビットを反転して 1 を加えることで求められます。 2 の補数表現とはつまり負の整数です。「正 - 正」の減算は「正 + 負」として考えられます。
2 の補数を求めるビット演算子を ~ とすると、 A - B は次の式で表せます。加算と同じく、符号があってもなくてもこの式で計算します。引く数が 0 であっても同じです。
A - B = A + ~B + 1
10 進数で処理するコードを書くと「符号なし整数型に変換して〜」とか「負の数をビット列にするには〜」とか「負の数になった場合のキャリーとオーバーフローの検出は〜」とかいちいち悩めて余計面倒臭いので 2 の補数表現で加算で考えるのがお勧めです (実際遠回りし過ぎた) 。
符号なし整数同士の演算 (キャリー)
次に例を示します。
00000011 - 00000010
10 進法だとそれぞれ 3 と 2 です。引く数 00000010 の 2 の補数表現を使うと次の加算式に変換できます。
00000011
+ 11111101 // 00000010 の 2 の補数
+ 00000001 // 2 の補数 + 1
--------------------------
= 1 00000001 = 0x01 = 1
計算結果は 1 です。加算でも減算と同じ結果になりましたが、 7 ビット目が繰り上がって桁があふれるのでキャリーが発生します。「正しいのにキャリーが発生するのか？」などと考える必要はありません。キャリーが発生するからキャリーフラグがセットされるだけのことです。
計算結果が負の数になる場合も見てみましょう。
01111111 - 10110000
10 進法だとそれぞれ 127 と 176 です。符号つきであれば計算結果は -49 になるはずですが、符号なしだとどうなるでしょうか。 176 の 2 の補数表現を使って加算式に変換します。
01111111
+ 01001111 // 10110000 の 2 の補数
+ 00000001 // 2 の補数 + 1
----------------------------------
= 11001111 = 0xCF = 207 = -49 (符号あり)
計算結果の 11001111 は符号つき整数だと -49 ですが、符号なし整数だと 207 になります。おかしな数値ですが、 7 ビット目の繰り上がりがないのでキャリーは発生しません。加算とは逆に、「 6502 の」減算ではキャリーの発生が (符号ありで考えた場合の) 正しい計算結果を示すことになります。減算とキャリーフラグの扱いは CPU によって異なるので注意してください。
符号つき整数同士の演算 (キャリー、オーバーフロー)
オーバーフローの条件が加算と異なる点に注意です。加算時のオーバーフローフラグは、計算対象の 2 つの数値の符号と計算結果の符号が異なる場合にセットされますが、符号つき整数同士の演算では異なります。次の例を見てください。
01111110 - 01111111
10 進数にすると 126 - 127 = -1 です。
加算に変換します。
01111110
+ 10000000 // 01111111 の 2 の補数
+ 00000001 // 2 の補数 + 1
----------------------------------
= 11111111 = -1
正と正の整数同士の計算結果が負の整数になったので、これが加算であればオーバーフローになります。しかし符号つき整数同士の場合、この計算結果は正解です。減算では計算対象の整数の符号と計算結果の符号が違ってもオーバーフローにはなりません。今度は計算結果が符号つき 8 ビット整数の範囲を超える例を見てみます。
01111111 - 10110000
10 進数だとそれぞれ 127 と -80 なので、正しい計算結果は 127 - (-80) = 207 になります。しかし符号つき 8 ビット整数で表せる範囲 (-128 から 127) を超えているので、 8 ビット整数で計算した結果は別の数値になります。
01111111
+ 01011111 // 10100000 の 2 の補数
+ 00000001 // 2 の補数 + 1
----------------------------------
= 11001111 = -49
結果は 11001111 、 10 進数だと -49 になりました。 6 ビット目の繰り上がりが発生して 7 ビット目が 1 になりますが、 7 ビット目は符号を表すのに使われるため数値として使えません。この例は「正 + 負」ですが、今度は数値を入れ替えて「負 + 正」を見てみます。
10110000 - 01111111
正しい結果は -80 - 127 = -207 になります。こちらも符号つき 8 ビット整数で表せる範囲を超えるので結果が異なります。
10110000
+ 10000000 // 01111111 の 2 の補数
+ 00000001 // 2 の補数 + 1
----------------------------------
= 1 00110001 = 49
7 ビット目が繰り上がってキャリーが発生し、さらに 7 ビット目が期待される負の符号と逆の正の符号になりました。減算のオーバーフローフラグはこのときにセットされます。 異なる符号同士の減算で、計算結果の符号が 1 つ目の整数の符号と異なる場合 に発生します。言葉で説明するとややこしいですね。他にも言いようはあるんですが、実装を考えるとこの説明がコードに落としやすいのではないかと思います。
まとめ
以上をまとめると、キャリーとオーバーフローの条件は以下の通りです。これで ADC 命令と SBC 命令の実装はばっちりですね！
| 演算 | 符号 | キャリー | オーバーフロー |
|---|---|---|---|
| 加算 | なし | 桁あふれ | なし |
| 加算 | あり | 同上 | 同じ符号同士の演算かつ計算結果の符号が元の符号と異なる |
| 減算 | なし | 同上 | なし |
| 減算 | あり | 同上 | 異なる符号同士の演算かつ計算結果の符号が 1 つ目の整数の符号と異なる |
いかがでしたか？ 10 進数だけを見ているとキャリーとオーバーフローの理屈がわからないのではないでしょうか。幸か不幸かソースコードが公開されているファミコンエミュレーターの実装は山ほどあるのでコピペでも済んでしまいますが、どうせ作るなら 2 進数に慣れたほうが自分のためになると思います。
サポートお待ちしています！
Discussion