LoginSignup
1
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 1 year has passed since last update.

@hiro4669

キャリー・ボロー，オーバーフロー判定と実装

Last updated at Posted at 2023-09-22

概要

X86系CPUのエミュレータを実装するに当たり，ステータスレジスタのうち，キャリー/ボロー，オーバーフロー，ゼロ，マイナス，を判定する必要があるため，これらの基本概念と実装をまとめておく

前提

これらフラグの判定は，演算の種類によって判定の仕方が異なる．特に，キャリー/ボローとオーバーフローは，加算，減算，比較演算(e.g., cmp)などの演算で状態が変化する．乗算や除算でも変化するが，これらの演算でどう判定するかはIntelの仕様書に細かく書いてあるので，今回は加算と減算のみ考える(比較演算は減算の一種だと考えられる)

基礎概念

キャリー/ボローとオーバーフローは違いがわかりにくいので，まずはこの２つの基本的な説明と違いについて理解する．

キャリー/ボロー

キャリーとボローは，符号なし演算を考えるときの概念である．そして，キャリーは加算，ボローは減算で必要となる概念となる．なお，減算もボローを使わずにキャリーを使って考える事もできるが，これについては補足する．

加算におけるキャリー

簡単のため，unsgined char(符号なし1バイト)同士の計算を考える．1バイト符号無しで表せる数は0~255で，2進数で表すと00000000 ~ 11111111となる．ここで，255+1をやってみる

(255): 11111111
(1  ): 00000001
----------------
    (1)00000000

となり，8ビット目に1が繰り上がって1バイトの分だけみたら0になる．これは実際の結果(=256)と合わなくなる．そのため，桁上りしたことを覚えておく必要があり，このときにキャリーフラグが1となる．

減算におけるボロー

加算と同様に，符号なし1バイト同士の計算で，10-20を考える．10-20 = 10+(-20)と考えられ，負の数は2の補数表現を取ることで得られるので，最終的には加算で処理する

(20) : 00010100
(-20): 11101011 // 1の補数
              1
----------------
       11101100 // 2の補数

よって，

(10) : 00001010
(-20): 11101100
-----------------
       11110110 // 10進数で246

この結果，得られた答えは246となり，正解の-10とはならない．なお，これを符号あり，で考えると-10であうのだが，今は符号なしで考えているので，符号ありで考えてはならない．
結果的に計算は合わなくなるが，この辻褄を合わせるにはどうすればよいか，と考えた時登場するのが「ボロー」，という概念．(src) - (dst)という演算を考えた時，絶対値でdstのほうが大きければ，当然結果がマイナスになり，これは符号なしで考えている場合，マイナスを表せないので計算結果がおかしくなるのは当然といえば当然．この辻褄を合わせるには，srcの8ビット目に1があったと仮定して，計算することである．具体的には

266: (1)00001010
-20:    11101100
-----------------
        11110110 // -> 246

これで辻褄があう．このようなときにボローフラグが1となる

このように，符号なしで固定長のバイトで演算を行った結果，結果がおかしい，ということをCPUが判定できるために，キャリーやボローフラグが存在する．

減算でのキャリー

これは補足説明なので，混乱を避けるために呼び飛ばしたほうが良いかもしれないが，備忘録を兼ねて書いておく．
符号なし1バイトで10-2を考える

10  : 00001010
(-2): 11111110
--------------
   (1)00001000 // 10進で8

この例では，1バイト符号無しで結果が8なので合っている．しかし，桁上りが発生してキャリーフラグも立っている．CPUは，符号なし計算で結果が正しいのか，正しくないのかを判定したいので，減算でキャリーを使うのであれば，減算ではキャリーフラグが立っている時計算結果は正しい，反対に，キャリーフラグが立たない時計算結果は間違っている，とも考えられる．ボローの例では，計算の結果キャリーフラグが立っていないことに注目すること．
つまり，明示的にボローフラグを使うのか，キャリーで代用するのかはCPUのポリシー次第，ということになる．大事なことは，減算でキャリーとボローが同時に起こるなんてことはない，ということである．

オーバーフロー

オーバーフローは，符号あり演算を考えるときの概念である．キャリー/ボローと同様に，加算と減算でオーバーフローになるケースが異なる．
オーバーフローは，演算の結果，本来の正解と符号が異なるケースで発生する．

減算でのオーバーフロー

符号あり1バイト同士の計算を考える．符号あり1バイトの表せる範囲は，-128~127である．例えば，-1-128の演算を考える．

(-1)  : 11111111
(-128): 10000000
----------------
     (1)01111111 // 符号あり1バイトで127

正解は-129であるが，符号あり1バイトの範囲では127になってしまう．この時オーバーフローとなる(※2バイトまで拡張して考えると，結果は1111111101111111となり，-129で正しい)．

減算のパターンとして

  1. 正-正
  2. 正-負
  3. 負-正
  4. 負-負

の4ターンがあるが，正負が同じ演算の場合，絶対にオーバーフローは起こらない．例えば正の最も小さい数である0から127を引いてみると，

0 - 127 = -127 > -128
127 - 0 = 127 <= 127

となり，符号あり1バイトの範囲に収まる．反対に，負の最も小さい-128，最も大きい-1同士の演算は

-1 - (-128) = 127 <= 127
-128 - (-1) = -127 > -128

となり，やはり符号あり1バイトの範囲に収まる．よって，減算でオーバーフローが起こるのは(2)と(3)の場合に限られる．つまり

  • オペランドの符号が反対であること(※最初の例では，-1と128)
  • 結果の符号と第1引数の符号が異なる(※最初の例では，結果127，第一引数−1)

ときに減算のオーバーフローがセットされる．

加算でのオーバーフロー

減算と同様に符号あり1バイト同士の計算を考える．

加算のパターンとして

  1. 正+正
  2. 正+負
  3. 負+正
  4. 負+負

があるが，減算と反対で，加算では同符号の演算でオーバーフローが起きる．例えば，127+2=129であるが，

(127): 01111111
(2)  : 00000010
---------------
       10000001 // 符号ありで-127

で，-127になる．
よって，加算でオーバーフローが起きるのは(1)と(4)に限られる．つまり

  • オペランドが同符号であること
  • 結果の符号オペランドの符号が異なる

となる

実装(C言語)

キャリー/ボロー，オーバーフローの意味や違いが理解できたら，次はこれらの演算と判定をどうやるのか，について書いていく．加算と減算で判定方法が異なるので，加算の場合，減算の場合それぞれキャリー/ボロー，オーバーフロー判定の実装を書いていく．なお，X86系はボロー判定をしてキャリーフラグを使うので，減算ではボローを判定する．

加算

キャリー判定

キャリーは，2つのオペランドを符号なしとして扱い，結果が桁あふれを起こすかどうか調べれば良い．よって

uint16_t src, dst
if (src + dst) >= 0x10000 {/* キャリービットON */} else {/* キャリービットOFF */}

で判定できる．

オーバーフロー判定

オーバーフローは符号ありで計算したときに符号が逆転することを判定すればよい．よって

int16_t val16;
int32_t val32;
val16 = val32 = (int16_t)src + (int16_t)dst;
if (val16 != val32) {/* オーバーフローあり */ } else {/* オーバーフローなし */}

ポイントは，符号ありで計算して4バイト幅の符号あり変数に結果が代入され，そこから2バイト幅の符号あり変数に代入してそれらの結果を比べているところ．符号ありにしているので，結果がマイナスの場合は符号拡張されて正しい値がval32に入る．一方，その値を2バイトに縮めてval16に入れているので，オーバーフローが起きているならval16の値は正解のval32とは異なるはずである．

減算

ボロー判定

ボローは，オペランドを符号なしで扱った時，src-dstの場合，src < dstのときに起こる(上位から値を借りなければ減算できない)．よって，

uint16_t src, dst
if (src < dst) {/* ボローあり */} else {/* ボローなし */}

これで判定できる．

オーバーフロー判定

加算同様，減算でのオーバーフロー判定も加算と同じ方法でできる．結局符号ありで計算した時，符号が反転することを確認すれば良いから，である．よって実装も加算の場合と同じ

int16_t val16;
int32_t val32;
val16 = val32 = (int16_t)src - (int16_t)dst;
if (val16 != val32) {/* オーバーフローあり */ } else {/* オーバーフローなし */}
実装例
#include <stdio.h>
#include <stdint.h>

int main(void) {
    int32_t result32;
    int16_t result16;
    uint16_t src, dst;
    src = 0x8000; // 符号あり10進で-32768
    dst = 0xf010; // 符号あり10進で-4080

    printf("-------- add -------\n\n");    
    printf("src: %d, dst: %d\n", (int16_t)src, (int16_t)dst);
    printf("unsigned src+dst = %x\n", src+dst); // 符号なしで計算(0x17010)．キャリーが発生する
    printf("signed   src+dst = %x\n", (int16_t)src +(int16_t)dst);  // 符号ありで計算(0xffff7010)．オーバフローが発生
    result16 = result32 = (int16_t)src + (int16_t)dst;

    printf("result16 = %d(0x%04x)\n", result16, result16); // オーバフローが発生するため，結果は0x7010
    printf("result32 = %d(0x%08x)\n", result32, result32); // 上位ビットが使えるのでオーバーフローが発生せず，正しい値(0xffff7010)

    // add
    if (result16 != result32) { //  こちらがマッチ
        printf("overflow on add case\n"); 
    } else {
        printf("overflow off add case\n");
    }
    
    if (src + dst >= 0x10000) { // こちらがマッチ
        printf("add carry on\n");
    } else {
        printf("add carry off\n");
    }

    printf("-------- sub -------\n\n");    
    src = 0x8000; // 符号あり10進で-32768
    dst = 0x4000; // 符号あり10進で16384

    printf("src: %d, dst: %d\n", (int16_t)src, (int16_t)dst);
    result16 = result32 = (int16_t)src - (int16_t)dst;
    printf("result16 = %d(0x%04x)\n", result16, result16); // オーバーフロー発生し，結果は0x4000
    printf("result32 = %d(0x%08x)\n", result32, result32); // 上位ビットが使えるのでオーバーフローが発生せず，正しい値(0xffff4000)

    if (result16 != result32) { // こちらがマッチ
        printf("overflow on sub case\n"); 
    } else {
        printf("overflow off sub case\n");
    }


    if (src < dst) {
        printf("sub borrow on\n");
    } else {                    // こちらがマッチ
        printf("sub borrow off\n");
    }
}

実行結果

-------- add -------

src: -32768, dst: -4080
unsigned src+dst = 17010
signed   src+dst = ffff7010
result16 = 28688(0x7010)
result32 = -36848(0xffff7010)
overflow on add case
add carry on
-------- sub -------

src: -32768, dst: 16384
result16 = 16384(0x4000)
result32 = -49152(0xffff4000)
overflow on sub case
sub borrow off
RUSTでの実装

RUSTでは，演算結果が同じデータ長を超える，つまりキャリーやボロー，オーバーフローが起こる演算を行うとpanicになる(Release用にコンパイルすれば起きないらしい)．そのため，RUSTではオーバーフローする可能性がある計算ようにメソッドを提供している．今回はoverflowing_add, overflowing_subを使用する．
overflowing_xxxは，計算結果と，オーバーフローしたかどうかの判定結果をタプルで返してくれる．そして，符号なし/符号あり，それぞれの型によってキャリー発生やオーバーフロー発生を適切に判断してくれる．

fn main()
{
    let mut src: u16 = 0;
    let mut dst: u16 = 0;

    src = 0x8000;
    dst = 0xf010;

    println!("-------- add ---------\n");

    println!("src: {}, dst: {}", src as i16, dst as i16);    
    println!("unsigned src+dst = {:x}", src as u32 + dst as u32);
    println!("wrap result = {}({:x})", src.wrapping_add(dst), src.wrapping_add(dst)); // 
    let (result, c_flg) = src.overflowing_add(dst);
    if c_flg {
        println!("add carry on {:04x}\n", result);
    } else {
        println!("add carry off {:04x}\n", result);
    }

    println!("src: {}, dst: {}", src as i16, dst as i16);

    let (result, o_flg) = (src as i16).overflowing_add(dst as i16);
    if o_flg {
        println!("add overflow on {:04x}, {}", result, result);
    } else {
        println!("add overflow off {:04x}, {}", result, result);
    }

    println!("-------- sub ---------\n");
    src = 0x8000;
    dst = 0x4000;
    println!("src: {}, dst: {}", src as i16, dst as i16);

    let (result, o_flg) = (src as i16).overflowing_sub(dst as i16);
    println!("result = {}(0x{:04x})", result, result);
    if o_flg {
        println!("overflow on sub case");
    } else {
        println!("overflow off sub case");
    }
    
    let (result, flg) = src.overflowing_sub(dst);
    println!("result = {}(0x{:04x})", result, result);
    if flg {
        println!("sub borrow on");
    } else {
        println!("sub borrow off");
    }
}

実行結果

-------- add ---------

src: -32768, dst: -4080
unsigned src+dst = 17010
wrap result = 28688(7010)
add carry on 7010

src: -32768, dst: -4080
add overflow on 7010, 28688
-------- sub ---------

src: -32768, dst: 16384
result = 16384(0x4000)
overflow on sub case
result = 16384(0x4000)
sub borrow off

C言語での実装と一致する

1
1
1

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?