セキュリティ系の勉強、その他開発メモとか雑談. GithubはUnity触っていた頃ものがメイン Twitterフォローもよろしくです

Signed Int加算減算のオーバーフロー判定について

//

はじめに

Rustファミコンエミュレータを写経していた時のお話です。CPUの実装で加算・減算の命令実装時に、オーバーフローの判定を挟むのですが何やっているのか分からず悩んだので、ここに自分なりの解釈を書いておきます。もっと良い考え方があれば教えてください。

問題の箇所

このリポジトリのこの箇所です。

pub fn adc_imm<T: CpuRegisters>(operand: Word, registers: &mut T) {
    let computed = (operand as u16) + registers.get_A() as u16 +
                   bool_to_u8(registers.get_carry()) as u16;
    let acc = registers.get_A();
    registers
        .set_overflow(!(((acc ^ (operand as Data)) & 0x80) != 0) &&
                      (((acc ^ computed as Data) & 0x80)) != 0) //  ココ
        .update_negative_by(computed as Data)
        .update_zero_by(computed as Data)
        .set_carry(computed > 0xFF)
        .set_A(computed as Data);
}

// [引用] https://github.com/bokuweb/rustynes/blob/f213881554e20054c7ea7adafe511195c25f8cb7/src/nes/cpu/instructions.rs#L147

github.com


前提知識

ざっくりまとめると

  • ファミコンでは演算時に値をSigned Intとして扱っているはずである。
  • このメソッドはu8operandaccの2つの変数の足し算。(正確には1か0のcarry_flagも足している)
  • ファミコンにおいてもし結果がオーバーフローしていたらそれを検知する必要がある。
  • !(((acc ^ (operand as Data)) & 0x80) != 0) && (((acc ^ computed as Data) & 0x80)) != 0trueなら、オーバーフローしてる判定らしい


オーバーフロー検知

分解

まず判定式を2つに分けてみます。

  1. !(((acc ^ (operand as Data)) & 0x80) != 0)
  2. (((acc ^ computed as Data) & 0x80)) != 0

1では1つ目の変数と2つ目の変数をxorした後に、0x80ANDを取っています。よく分からないので更に分解してみます。xorとandで分配則が成り立つはずなので、分解します。ついでに先頭の!も取ります。
- (acc & 0x80) ^ (operand & 0x80)==0

http://markun.cs.shinshu-u.ac.jp/learn/logic/logic3/html/jp/fnd4-j.html

判定

  • 0x80andをとることで、8bit目が1かどうか判定してます。これにより値の正負を判定できます。(正なら0x80, 負なら0x00)
  • 上の結果をxorすることにより、元の2変数の正負が同じであった場合のみ0が算出されます。(正:0x80 ^ 負:0x00 = 0x80, 正^正= 0x00)
  • つまり1では、足した2変数が同じ符号であったかを見てます。



これらを踏まえると2では、変数1と演算結果が違う値かを判定していることになると思います。

つまり?

足し算なのに結果の正負が変わることはないよ。変わっていたら、お前オーバーフローしてね?ってことだと思います。 f:id:thinline196:20200301184235p:plain

減算も見てみる

手短に引き算も見ます。

pub fn sbc_imm<T: CpuRegisters>(operand: Word, registers: &mut T) {
    let computed = registers.get_A() as i16 - (operand as i16) -
                   bool_to_u8(!registers.get_carry()) as i16;
    let acc = registers.get_A();
    registers
        .set_overflow((((acc ^ (operand as Data)) & 0x80) != 0) &&
                      (((acc ^ computed as Data) & 0x80)) != 0) // ココ
        .update_negative_by(computed as Data)
        .update_zero_by(computed as Data)
        .set_carry(computed >= 0 as i16)
        .set_A(computed as Data);
}

// 引用: https://github.com/bokuweb/rustynes/blob/f213881554e20054c7ea7adafe511195c25f8cb7/src/nes/cpu/instructions.rs#L174

rustynes/instructions.rs at f213881554e20054c7ea7adafe511195c25f8cb7 · bokuweb/rustynes · GitHub


日本語に直すと、変数1と変数2の符号が違っているのに変数1と演算結果も符号が違うとなりそうです。これは式が

  • A - (B) = C

であることに注意すれば、足し算と同じように理解できそうです。