符号付き算術演算のオーバーフロー検出アルゴリズム

インテル8080にオーバーフローフラグが無い

2017年6月、35年ぶりにインテル8080マイクロプロセッサのアセンブラを書いています。

CP/Mシミュレータで懐かしのインテル8080アセンブラを使う

信号処理などでは、サチュレート(飽和)演算を使うことがあります。サチュレート演算とは、演算結果が上限を超えたら上限値に、下限を超えたら下限値にするものです。すなわち、オーバーフローを検出して演算結果を補正するわけです。

信号処理を得意とするDSP(Digital Signal Processor)では、命令セットにサチュレート演算があります。また、マルチメディア対応のSIMD(Single Instruction Multiple Data)命令にも、サチュレート演算命令があります。

しかし、1974年に登場したインテル8080マイクロプロセッサには、残念ながらサチュレート演算命令は存在しません。その上、オーバーフローを検出するオーバーフローフラグもありませんでした。

そこで、ソフトウェアでオーバーフロー検出するアルゴリズムを整理しました。

数値の表現方法

コンピュータ内部は、数値を2進数で格納しています。説明を簡単にするために、ここでは4ビットで説明します。

4ビットの場合、16種類の0と1の組み合わせがあります。

  • 符号なし整数 : 0~15を表します
  • 符号つき整数 : 0~7、-1~-8を表します
4ビット 2進10進数対応表

4ビット 2進10進数対応表

符号つき整数の場合、マイナスの値は「2の補数表現」を使います。「2の補数表現」では、最上位ビット(MSB : Most Significant Bit)が「1」のときマイナス数値を表します。
2進数のマイナス数値は、2進数ビット列を反転して+1を加算したものです。

たとえば、

  • 「-1」: 「1 (0001)」を反転した「1110」に+1を加算 → (1111)
  • 「-6」: 「6 (0110)」を反転した「1001」に+1を加算 → (1010)

もっと簡単な手順は、最下位ビットから(右→左へ)順にビット複写して、ビット値1を複写した後はビット反転したものです。

負の数 作成方法

負の数 作成方法

 


2進数のマイナス数値を「2の補数表現」とすることにより、2進数の加算で減算を行うことができます。
たとえば、「6-2」の計算は「6」と「-2」を加算します。「6(0110)」と「-2(1110)」を加算すると「10100」となります。最上位ビットからはみ出した「1」は、キャリービットと呼び無視します。その結果、計算結果は「4(0100)」となります。

2進数の加算

2進数の加算

 

サチュレート(飽和)演算とは

サチュレート演算とは演算結果がオーバーフローしたら上限値または下限値に補正する演算です。オーバーフローとは、2の補数で表現可能な範囲に収まらないことを言います。

4ビットで説明します。2の補数で表現可能な数値は、最大値は+7で最小値は-8です。

  • 最大値(+7)を上回ったら、上限値(+7)に補正
  • 最小値(-8)を下回ったら、下限値(-8)に補正

 

(+5)+(+1) 0101+0001 = 0 0110 +6
(+5)+(+4) 0101+0100 = 0 1001 オーバーフロー +7
(-5)+(-1) 1011+1111 = 1 1010 -6
(-5)+(-4) 1011+1100 = 1 0111 オーバーフロー -8

 

オーバーフローの検出方法

さて、オーバーフローはどのように検出したらよいか考えてみます。

2の補数表現

4ビット符号つき整数(2の補数表現)のビットパターンと10進数数値を下記のように円形で示します。

4ビット符号つき整数

4ビット符号つき整数

  • 「0(0000)」から右回りがプラス方向です。+1~+7。
  • 「0(0000)」から左回りがマイナス方向です。-1~-8。

「+7(0111)」と「-8(1000)」の間は、連続性が無く円が途切れます。この部分で円弧を切断して、直線状に延ばして計算尺に見立てます。

数値の加算

数値Bと数値Cを加算します。

下記図で、中央に示した計算尺の数値Bと、上または下に示した直線の数値Cを加算するとします。

4ビット2進数の加算とオーバーフロー

4ビット2進数の加算とオーバーフロー

正の数+正の数

2+5は、中央の計算尺の(+2)と数値(+5)を加算して(0111)となります。しかし、2+6は正の最大値(0111)を上回りオーバーフローします。

正の数+負の数

2+(-8)は、中央の計算尺の(+2)と数値(-8)を加算すると(1010)=(-6)となります。正の数(0~7)に負の数(-1~-8)を加算しても、オーバーフローすることはありません。

負の数+正の数

(-2)+7は、中央の計算尺の(-2)と数値(+7)を加算すると(0101)=(+5)となります。負の数(-1~-8)に正の数(0~7)を加算しても、オーバーフローすることはありません。

負の数+負の数

(-2)+(-6)は、中央の計算尺の(-2)と数値(-6)を加算して(1000)となります。しかし、(-2)+(-7)は負の最大値(1000)を下回りオーバーフローします。

オーバーフロー検出

上記より「正の数+負の数」または「負の数+正の数」の場合、オーバーフローは発生しません。すなわち、ふたつの数値の符号が異なればオーバーフローが発生しません。

D=B+C を求めるとします。

オーバーフローの検出

オーバーフローの検出

BとCの排他的論理和(B xor C)のMSB=1ならば、異符号なのでオーバーフローは発生しません。

「正の数+正の数」の場合、キャリー CYとDの状態は「0|0・・・」か「0|1・・・」となり、後者は符号ビット(MSB)が「0」→「1」となり負の数となるのでオーバーフローしています。

「負の数+負の数」の場合、キャリー CYとDの状態は「1|0・・・」か「1|1・・・」となり、前者は符号ビット(MSB)が「1」→「0」となり正の数となるのでオーバーフローしています。

すなわち、CとDの排他的論理和(C xor D)のMSB=1の場合にオーバーフローが発生します。

整理すると、次のようになります。

(B xor C)のMSB=0 かつ (C xor D)のMSB=1の場合、オーバーフローが発生します。

i8080サチュレート加算コード

インテル8080マイクロプロセッサでオーバーフローを検出してサチュレート加算するコード(SADD8)を下記に示します。

レジスタBとレジスタCをサチュレート加算してレジスタAに結果を求めます。


【SADD8 プログラム説明】

・D ← B + C を算出します
・Flag ← B xor Cを求め、A←D
・Sign Flag ONならば、returnします(RM) …BとCは異符号
・Flag ← D xor Cを求め、A←D
・Sign Flag OFFならば、returnします(RP) …DとCは同符号
・Flag ← Cを求め、A←07FH
・Sign Flag OFFならば、returnします(RP) …Cは正数 : オーバーフロー
・A←A+1 (080H)
・returnします …Cは負数 : オーバーフロー

サチュレート加算テストコード

SADD8をテストするコードを書きます。テストケースを下記に示します。

期待値 備考
+100 +20 +120 + +
+100 +27 +127 + +
+100 +28 +127 + + OV
+100 +29 +127 + + OV
+100 -20 +80 + –
+100 -127 -27 + –
-100 +20 -80 – +
-100 +127 +27 – +
-100 -20 -120 – –
-100 -27 -127 – –
-100 -28 -128 – –
-100 -29 -128 – – OV
-100 -30 -128 – – OV

テストケースをDB(Define Byte)で定義します。DBは、正の数値しか定義できませんので、マイナスの数値は+256して定義します。

  • 最初の0ffhは、FF=実行/00=停止のフラグ
  • 100は、数値B
  • 20は、数値C
  • 120は、数値B+数値Cの期待値
  • 00hは、計算結果を格納する領域

実行結果の確認のため、BとCと期待値と加算結果を16進でダンプします。期待値と加算結果が一致した場合は「=」、不一致の場合は「?」を表示します。

実行結果を下記に示します。

SADDの実行

SADDの実行

テストコードを下記に示します。

最後に

インテル8080マイクロプロセッサで符号つき整数のサチュレート加算するコードを書きました。8080にはオーバーフローフラグがありませんので、ソフトでオーバーフロー検出するアルゴリズムを整理しました。

オーバーフローが発生する状況を整理すると、そんなに複雑ではありませんでした。

 

 

このエントリーをはてなブックマークに追加

符号付き算術演算のオーバーフロー検出アルゴリズム」への1件のフィードバック

  1. ピンバック: 懐かしいインテル8080命令セットのメモ | ある計算機屋さんの手帳

コメントは受け付けていません。