竹下世界塔の計算機よもやま話

アクセスカウンタ

zoom RSS 整数演算のオーバーフロー

<<   作成日時 : 2011/12/08 03:29   >>

ブログ気持玉 0 / トラックバック 1 / コメント 0

 加減算の演算結果が、数値を扱える範囲を超えてしまうことをオーバーフローと呼ぶ。符号なしの加減算によるキャリー/ボロー発生もオーバーフローのうちに入るが、ここでは一般的な符号付き数値である2の補数で考える。8bitの場合-128〜127まで、4bitの場合-8〜7まで扱える。

 4bit幅での2の補数での加算結果とオーバーフローの有無を表にしてみた。→ overflow.awk

例:
+7 (0111) + +1 (0001) = +8 (1000) x
-8 (1000) + -1 (1111) = -9 (0111) x
-8 (1000) + +7 (0111) = -1 (1111) o

このように同符号の演算はオーバーフローする可能性があり、異符号ならオーバーフローはしない。
ここから見ていくと、A+B=Cの場合、オーバーフローはAとBが同符号で、加算の結果Cが異符号の場合に発生する。

書き直すと:
V = (A[MSB] xor C[MSB]) and (B[MSB] xor C[MSB])
このように少しの組み合わせ論理回路でオーバーフローを求めることが出来る。
また、別解ではMSBからキャリーへの桁上がりと、MSB-1からMSBへの桁上がりの排他的論理和で求められる。が、これは加算器の内部に組み込まないと実現できない。

オーバーフローを後で求めようとすると数ステップかかってしまう。また、作業用レジスタも使ってしまう。
例:
XOR A,C,W1
XOR B,C,W2
AND W1,W2,W1
BMI OVERFLOW # W1[MSB]=1ならオーバーフロー処理

ほとんどのプロセッサ:CCR(ConditionCodeRegister)のVフラグが立つ。
System/360:演算でオーバーフローが発生した場合はトラップが発生する。マスク可。
MIPS: 演算でオーバーフローが発生した場合はトラップが発生する。OVFフラグでマスク可 マスク不可。トラップを発生させたくない場合はU付き命令(ADDUなど)を使う。
Alpha:/Vの修飾子でオーバーフローが発生した場合にトラップが発生する。修飾子を付けないとオーバーフローは無視される。
 ADD R1,R2,R3 # トラップは発生しない
 ADD /V R1,R2,R3 # オーバーフロー時トラップ発生

オーバーフローを監視する場合は、演算後にVフラグを見て条件分岐する。無視する場合は省ける。
System/360はトラップが発生する。無視する場合は割込みをマスクする。ただし、マルチタスクの場合は別々のプログラム間でコンテキスト切り替えが発生するのでマスクの状態を保存しなければならない。
Alpha、MIPSもトラップが発生する。
Alphaは命令コード内にオーバーフローによるトラップ発生の有無を埋め込むので、MIPSよりも洗練されている MIPSのADD/ADDU等と同等。


 オーバーフローは言語によっては無視され、値がラップアラウンドされる。C言語はそうだ。
IPA ISEC セキュア・プログラミング講座:C/C++言語編 第10章 著名な脆弱性対策:整数オーバーフロー攻撃対策

ちょっと言語ごとに整数演算のオーバーフローの扱いがどうなっているのか調べてみた。

□無視してラップアラウンドする
・C、FORTH

□整数演算のオーバーフローチェックを行ってる
・C#の /checkedオプション
・Modula-2,Algol68,BASIC等は実装依存

□整数演算のオーバーフローチェックが言語の仕様にある
・PL/I
・COBOLのON SIZE ERROR(ただし2の補数に限らない)

□有限の桁数前提で扱う
・awk 倍精度浮動小数点のdouble型を使う

□整数は多倍長演算に内部で拡張する
・最近のモダンな言語

 整数演算のビット幅が決まっているもののほとんどはオーバーフローを起こすかどうかは実装依存になっている。最強はPL/I。ただし実装≒仕様(実質、汎用機上)。
 最後の多倍長演算を行うものは、以下のような手順で桁数の拡張を行なっている(推測)
(1)最初に代入された整数の範囲で必要なバイト数を確保
(2)加減算の結果、オーバーフローが発生したら以下の様に上位の桁を確保
・正の方向にオーバーフローした場合:上位バイトをすべて'0'にする
・負の方向にオーバーフローした場合:上位バイトをすべて'1'にする

 ラップアラウンドされると、本来正の数の上限を越えたのにマイナスになったりと都合が悪いことがある。
このため飽和演算といってオーバーフロー発生時にはエラーにせず演算結果を上限または下限にしてしまう命令を持つプロセッサがある(V850等)。

コンディションコードに関するまとめ:
Z...ゼロフラグ。ゼロの時に立つ。
N...ネガティブ。MSBそのもの。
C...符号なし加算でキャリー発生、符号なし減算でボロー発生時に立つ。
V...2の補数の符号付き演算でオーバーフロー発生時に立つ。
このうち、Z,Nはすぐわかる。C,Vは演算後でないとわからない。

案外2の補数のオーバーフロー条件に関する資料が見つからなかったのが調査のきっかけ。

Thanks@finalfusion @egtra @takeoka @takashi_hatai @takehiro_t

参考文献など:
コンピュータアーキテクチャ(改訂3版)【AA】
・マイコンピュータ No.6 徹底特集・完全理解6809のすべて CQ出版
Embedded in Academia : How Integers Should Work (In Systems Programming Languages)
ALGOL 68
Modula-2 tutorial: The simple Modula-2 data types
IBM - Enterprise PL/I for z/OS - Library
標準COBOLリファレンス・マニュアル【AA】
MIPS R4000 Microprocessor User’s Manual Second Edition
※p.135 Integer Overflow Exception

テーマ

注目テーマ 一覧


月別リンク

ブログ気持玉

クリックして気持ちを伝えよう!
ログインしてクリックすれば、自分のブログへのリンクが付きます。
→ログインへ

トラックバック(1件)

タイトル (本文) ブログ名/日時
ポストフィックス命令
 既存の命令を拡張するのにプリフィックス命令を考えたが、後ろにくっつけるポストフィックス命令を検討してみた。 ...続きを見る
竹下世界塔の計算機よもやま話
2012/08/22 01:05

トラックバック用URL help


自分のブログにトラックバック記事作成(会員用) help

タイトル
本 文

コメント(0件)

内 容 ニックネーム/日時

コメントする help

ニックネーム
本 文




整数演算のオーバーフロー 竹下世界塔の計算機よもやま話/BIGLOBEウェブリブログ
文字サイズ:       閉じる