Detecting overflow

[Tim McDaniel]

[My earlier article with the same title, <1067 at garcon.cso.uiuc.edu>,
was incomplete.  I intend to cancel it.  Sorry if you see both of
these.]

In article <455 at skye.ed.ac.uk> ken at aiai.UUCP (Ken Johnson) writes:
>Since I posted a C program which detects overflow in int multiplication
>at immense cost in time terms, I received the following solution
>by e-mail:
>
>	if ( b != 0 && (a * b)/b == a) { /* No overflow */ }

As I noted eariler, it doesn't work if overflow on multiply causes a
fatal trap.  (However, if it silently truncates, it's almost correct.
I should have made this a special case in MY immense-cost code.)  By
the way, Ken's code wasn't so bad.  It did have a loop, but it avoided
division, which can be slooooow.

>However, this is not always going to work. Consider the case of
>a = 512 (0x200), b = 64 (0x40). Then in 16-bit arithmetic,

... presumably, 2s-complement, and "*" silently left-truncates on
overflow ...

>	(a * b) = 0x8000 (overflowing)

Yes.  0x8000 == -32768 (where "overflow" means "the result is an
integer, but cannot be represented exactly in the storage provided")

> but 0x8000/0x40 = 0x200

No.  The ANSI C standard requires that -32768/64 == -512.  The
division here (0x8000/0x40 == 0x200) is correct for unsigned, but if
it was unsigned arithmetic, there was no overflow; in unsigned, 0x8000
represents 32768, which is the correct result.  So the test worked in
this case.

>A further example would be 521 * 63 (0x209 * 0x3f).
Same type of result.

>...so I don't think this is guaranteed to work either.

A problem case is actually a = 0x8000 = -32768, b = -1.
        a * b = 0x8000 = -32768
This has overflowed, since the correct answer, 32768, can't be stored
in 16 bits 2s-complement. Then
        -32768 / b = -32768 / -1 = -32768
for the same basic reason.

Here's another, less probable case: suppose that an overflow on "*"
generates INT_MAX (or INT_MIN, depending on the proper sign).  Then
        -1311 * 25 = -32775
This would be reduced to INT_MIN = -32768 (say).
        -32768 / 25 = -1310.72000 = uhhh ....

An ANSI C implementation is permitted to generate either -1310
(truncate) or -1311 (round to -infinity).  If it chooses the latter,
the test fails.

--
"6:20 O Timothy, keep that which is committed to thy trust, avoiding
profane and vain babblings, and oppositions of science falsely so
called: 6:21 Which some professing have erred concerning the faith."

Tim, the Bizarre and Oddly-Dressed Enchanter  |  mcdaniel at uicsrd.csrd.uiuc.edu
            {uunet,convex,pur-ee}!uiucuxc!uicsrd!mcdaniel
            mcdaniel%uicsrd@{uxc.cso.uiuc.edu,uiuc.csnet}