detecting integer overflow

[Thomas Mitchell]

In article <67688 at sgi.sgi.com> karsh at trifolium.sgi.com (Bruce Karsh) writes:
* In article <GLOBUS.90Aug21114837 at wk208.nas.nasa.gov> globus at nas.nasa.gov (Al Globus) writes:
* >I have a program that can potentially generate an integer overflow.
* >I'd like to detect this when it happens and deal with it.  According
* >to SGI's Hotline folks, no can do. 

Well not in 'c' without testing the values as Ted and Bruce pointed out.
This in effect doubles the amount of work that needs to be done
on each operation.

* > The OS catches the interrupt
* >and then allows the process to go on its merry way with no mechanism
* >to detect the overflow.


* Well, our illustrious Hotline crew is usually gives perfectly reliable
* information, but I think they may have missed this time.  Here's the
* straight scoop:

Perhaps we got caught by the simple answer to a simple question.
But there are multiple solutions to this problem.

* The MIPS CPU will generate an integer overflow exception for signed 
* arithmetic instructions, but not unsigned ones.  So if the MIPS ADD
* instruction overflows, a SIGFPE signal is posted, while if an ADDU
* instruction overflows, there's no interrupt and hence, no signal is posted.
* In fact, this is the only difference between the operation of the ADD and
* ADDU instructions.
* 
* The MIPS C compiler generates unsigned arithmetic instructions.  This is
* the right thing for it to do since most C compilers do not treat 2's
* complement overflow as an error and some programs even depend on this.


Exactly -- this is what 'C' does.  Other languages need to do 
things differently.  Other languages..... Hmmm what is coming here?
 
* I think similar considerations would apply to the Fortran compiler, but
* I haven't looked.
* 
* >Is there really no way?  There's good mechanisms for floating point
* >exceptions, why not for integer exceptions?
 
There are goo ways  and good reasons -- 'C' just does not care.

If you want a portable test at the expense of extra work. Pre-test:
* There is a pretty good way if you know the operation which can potentially
* overflow.  If a and b are added, then this test will detect whether c, their
* sum, has overflowed.


      if( (~a^b &  a^c) < 0) handle_overflow();
      I.e., a single &.

      Thanks Ted W.  yet we are solving the problem multiple times.

There is an experimental language "Icon" with its roots in 
Snobol IV.  This University of Arizona language project 
had to deal with exactly this integer overflow problem.
Unlike 'c' Icon cares about overflow.

Below is some MIPS assemble language  which addresses the 
problem.  The contributer of of this code to the Icon language
project is:

        David Bacon
        Center for Advanced Research in Biotechnology
        Washington, D.C.

The below is from the machine specific portions of the Icon
Language interpreter.  The distribution has code for 45
flavors of machines (yea, this is a common problem).  The
Icon Language not to be confused with them little pictures
in the corner.

The user must provide an entry point for " jal     fatalerr"
so he can handle the error stuff.  Note how an error code is
passed to the handler.  Perhaps the best thing to do after looking 
at the following code is to dis-assemble (or capture '-S')
the code generated by the compiler and compare.

------------ snip the leading X ----------------------
X 	.text	
X 	.align	2
X 	.globl	ckadd
X  #   1	#define negative(a) ((unsigned)(a) < (unsigned)(0)) /* test sign bit */
X  #   2	long ckadd(x,y)
X  #   3	long x,y;
X  #   4	{
X 	.ent	ckadd
X ckadd:
X 	subu	$sp, 24
X 	sw	$31, 20($sp)
X 	.mask	0x80000000, -4
X 	.frame	$sp, 24, $31
X  #   5		long r;
X  #   6		r = x + y;
X 	addu	$3, $4, $5
X  #   7		if negative(x ^ y) {
X 	xor	$14, $4, $5
X 	bltz	$14, $33
X  #   8			/* signs are different - sum is safe */
X  #   9			return (r);
X  #  10		} else {
X  #  11			/* signs are the same - caution is needed */
X  #  12			if negative(x ^ r) {
X 	xor	$15, $4, $3
X 	bgez	$15, $33
X  #  13				/* result sign differs from operand sign */
X  #  14				fatalerr (-203, 0); /* overflow */
X 	li	$4, -203
X 	move	$5, $0
X 	jal	fatalerr
X 	move	$2,$0   # return 0 if fatalerr returns
X 	b	$34
X  #  15			} else {
X $33:
X  #  16				return (r);
X 	move	$2, $3
X $34:
X 	lw	$31, 20($sp)
X 	addu	$sp, 24
X 	j	$31
X 	.end	ckadd
X 	.text	
X 	.align	2
X 	.globl	cksub
X  #  23	{
X 	.ent	cksub
X cksub:
X 	subu	$sp, 24
X 	sw	$31, 20($sp)
X 	.mask	0x80000000, -4
X 	.frame	$sp, 24, $31
X  #  24		long r;
X  #  25		r = x - y;
X 	subu	$3, $4, $5
X  #  26		if negative(x ^ y) {
X 	xor	$14, $4, $5
X 	bgez	$14, $35
X  #  27			/* signs are different - caution is needed */
X  #  28			if negative(x ^ r) {
X 	xor	$15, $4, $3
X 	bgez	$15, $35
X  #  29				/* x and r have different signs - overflow */
X  #  30				fatalerr (-203, 0);
X 	li	$4, -203
X 	move	$5, $0
X 	jal	fatalerr
X 	move	$2,$0   # return 0 if fatalerr returns
X 	b	$37
X  #  31			} else {
X $35:
X  #  32				return (r);
X  #  33			}
X  #  34		} else {
X  #  35			/* signs are the same - difference is safe */
X  #  36			return (r);
X 	move	$2, $3
X  #  37		}
X  #  38	}
X $37:
X 	lw	$31, 20($sp)
X 	addu	$sp, 24
X 	j	$31
X 	.end	cksub
X 	.text	
X 	.align	2
X 	.globl	ckmul
X  #  39	
X  #  40	long ckmul(x,y)
X  #  41	long x,y;
X  #  42	{
X 	.ent	ckmul
X ckmul:
X 	subu	$sp, 24
X 	sw	$31, 20($sp)
X 	.mask	0x80000000, -4
X 	.frame	$sp, 24, $31
X 	mult	$4,$5  # 64-bit product
X 	mfhi	$3     # hi part (should be 0 or -1 for no overflow)
X 	mflo	$2     # lo part
X 	move	$8,$2  # copy of lo part
X 	sra	$8,31  # propagate lo's sign bit thru whole word
X 	beq	$8,$3,$38  # no overflow if this matches hi part
X 	li	$4, -203
X 	move	$5, $0
X 	jal	fatalerr
X $38:
X 	lw	$31, 20($sp)
X 	addu	$sp, 24
X 	j	$31
X 	.end	ckmul
X 
X 
--
--
  Thomas P. Mitchell   --  mitch at sgi.com  or mitch%relay.csd at sgi.com
	"All things in moderation; including moderation."