how to test the overflow

[starffly]

In my program, the caculated value is supposed to be no more than the
constant named MAXINT,otherwise, overflow error will be
informed.however, I cannot test if the value exceeds MAXINT within the
integer scope smaller than MAXINT,so I want to seek a measure to test
the excess without the value's comparing to MAXINT. Please let me know
if you have a good idea.
THX.

[Eric Sosman]

st******@gmail.com wrote:

In my program, the caculated value is supposed to be no more than the
constant named MAXINT,otherwise, overflow error will be
informed.however, I cannot test if the value exceeds MAXINT within the
integer scope smaller than MAXINT,so I want to seek a measure to test
the excess without the value's comparing to MAXINT. Please let me know
if you have a good idea.

I'll assume that `MAXINT' is equivalent to `INT_MAX',
defined in <limits.h>: The largest possible value of an
`int' variable.

The C language does not define what happens when a
calculation's "mathematical" result would be outside the
range of its type. This means that a strategy of allowing
overflow to occur and then detecting it after the fact is
not reliable, because once the overflow has taken place the
state of your program is unknown. Instead, you must avoid
the overflow by testing the operands before calculating.

Such tests are not complicated, but they are cumbersome.
Rather than writing test after test after test, people usually
follow one of three strategies:

0: Just ignore the possibility of overflow and hope for
the best. Marginally acceptable in some settings, out
of the question in others.

1: Let overflow occur and try to detect it afterward. This
isn't perfectly safe, but a great many machines do produce
a predictable "wrap-around" for `int' overflow. For those
that do, overflow occurred in z = x+y iff z < x && z < y.
This is about as cumbersome than pre-testing x and y, but
sometimes you can make several unchecked calculations and
then inspect the final result to check them all at once.

2: Calculate in a wider type that you are sure will not have
overflow (for the values you're using), and then check the
final result before converting it to `int'. The wider type
might be `long' or `long long' or even an extended-precision
"bignum" package. In some cases, it may be feasible to do
the calculation in floating-point before converting back to
`int', but this approach requires considerable caution. In
some cases you can use unsigned integers, whose behavior on
"overflow" is well-defined by C.

Back in the Stone Age when I first learned to program, the
computers I used did something very useful on integer overflow:
The hardware generated an error condition and notified the program
that something untoward had happened. Because strategies #0 and #1
above have become so widespread I see little chance of this helpful
behavior being resurrected as people build new machines; a computer
maker's goal is to run as many programs as possible, not to detect
errors in the bad ones. This eases things for sloppy programmers,
but unfortunately it makes things quite difficult for careful coders
like you.

--
Eric Sosman
es*****@acm-dot-org.invalid

[Eric Sosman]

Eric Sosman wrote On 08/14/06 08:50,:

[...] a great many machines do produce
a predictable "wrap-around" for `int' overflow. For those
that do, overflow occurred in z = x+y iff z < x && z < y.

Memo to self: Don't post before the coffee takes hold.
If x == -1 and y == -2, then z = x+y == -3 and z < x and
z < y, yet no overflow has occurred. Doh!

--
Er*********@sun.com

[Ancient_Hacker]

In many cases you can check for overflow this way:

write this code in Pascal, Delphi, or Fortran

{$OverflowChecking ON // ot whatever compiler option to turn on
overflow checking}
program divulgecode;
var x,y,z: integer;

begin
x := 1; y := 2;
z := x + y; z := x - y; z := x * y; z := x / y;
end.

//FORTRAN:
OPTION NOOPTIMIZE, CHECKOVERFLOW ! Or whatever
INTEGER X,Y, Z
z = x + y
z = x - y
z = x * y
z = x / y;
end

.... then look at the geneated code, it's likely to look a lot like
this:

; Z = X + Y
mov eax,[X] // puts X into the eax
register
add eax,[Y] // adds Y to it and sets
flags
jno @@1 // jumps if no overflow
happened

call _Math_Err_1 // calls RTL overflow
reporting function

@@1:

.... and similarly for sub, mul, and div

..... then write these functions

inttype add( inttype a, b ) { inttype Ans;
__asm {
mov eax,[X]
add eax,[Y]
jno @@1

mov eax,80000000 // was call
_Math_Err_1

@@1: mov [Ans],eax
}
return Ans
}

.... in other words, most CPU's have an "overflow" flag that can be
checked after any math instruction. witha little confidence and a few
lines of assembler you just might be able to kludge up some overflow
checking code.

Goes without saying, it's in no way portable across CPU architectures,
and it's easy to scrozzle things in assembly language unless you know
what you're doing. Using the conmpiler output as a guide is a big
help, but there may be some little loose ends.

[starffly]

Thank you for your particular and careful explanation, and I feel
the overflow really is a problem difficult to grasp. the overflow did
occur in z = x+y iff z < x ||(not &) z < y(x,y>0) and it can be
discovered easily, in my opinion the root reason of the feasibility of
such test is the following:
Assuming x,y,z as the int type and we cannot resort to the wilder type
such as the long type, then even if x plus y exceeds MAXINT, actally
the correct result can be realized pursuant to the result calculated by
the computer and the correct result is MAXINT+(2^15+z). i.e. the
information about the correct result is not lost. however, the result
of x*y may be large enough so that we cannot tell how many MAXINT
should be added and the result of z may be more than x and y again,
then we cannot restore the correct result according to it and test the
overflow, i.e. whether the corrert result can be got through deduce
concerns the feasibility of the test of the overflow.
It is possible to check the overflow by the assembly language, but
what my wanted
is to judge the overflow in standard C language using some algorithm
without resorting to the assembly language within the scope of the int
type.
Eric Sosman 写�：

Eric Sosman wrote On 08/14/06 08:50,:

[...] a great many machines do produce
a predictable "wrap-around" for `int' overflow. For those
that do, overflow occurred in z = x+y iff z < x && z < y.

Memo to self: Don't post before the coffee takes hold.
If x == -1 and y == -2, then z = x+y == -3 and z < x and
z < y, yet no overflow has occurred. Doh!

--
Er*********@sun.com

[Ancient_Hacker]

st******@gmail.com wrote:

>but
what my wanted
is to judge the overflow in standard C language using some algorithm
without resorting to the assembly language within the scope of the int
type.

Nope, the results of a int + int are not defined if overflow happens.

Now you might find that on any reasonable CPU, int + int returns the
bottom bits of the result, but there's no guarantee.

you could try this tho:

z = x + y;

if positive(x) and positive(y) then
if negative(z) then Overflow()
else
if negative(x) and negative(y) then
if positive(z) then Overflow()
else Okay() ; // mixed signs, cant overflow

Do the same thing for subtract, multiply and divide, with the obvious
changes.

[Michael Mair]

Ancient_Hacker schrieb:

st******@gmail.com wrote:

>>but
what my wanted
is to judge the overflow in standard C language using some algorithm
without resorting to the assembly language within the scope of the int
type.

Nope, the results of a int + int are not defined if overflow happens.

Now you might find that on any reasonable CPU, int + int returns the
bottom bits of the result, but there's no guarantee.

you could try this tho:

z = x + y;

if positive(x) and positive(y) then
if negative(z) then Overflow()
else
if negative(x) and negative(y) then
if positive(z) then Overflow()
else Okay() ; // mixed signs, cant overflow

Do the same thing for subtract, multiply and divide, with the obvious
changes.

Your approach is not structurally superior to
if (((x 0) && (INT_MAX-x < y))
|| ((x < 0) && (INT_MIN - x y)))
{
ReportOverflow();
return FAILURE_OVERFLOW;
}
else
{
z = x + y;
}
or
if ((x 0) && (INT_MAX-x < y))
{
/* saturate z to maximum value */
z = INT_MAX;
ReportOverflow();
}
else if ((x < 0) && (INT_MIN - x y))
{
/* saturate z to maximum value */
z = INT_MIN;
ReportOverflow();
}
else
{
z = x + y;
}
or whatever checks can be performed beforehand.
Cheers
Michael
--
E-Mail: Mine is an /at/ gmx /dot/ de address.

[Keith Thompson]

"Ancient_Hacker" <gr**@comcast.netwrites:

st******@gmail.com wrote:

>>but
what my wanted
is to judge the overflow in standard C language using some algorithm
without resorting to the assembly language within the scope of the int
type.

Nope, the results of a int + int are not defined if overflow happens.

Now you might find that on any reasonable CPU, int + int returns the
bottom bits of the result, but there's no guarantee.

you could try this tho:

z = x + y;

if positive(x) and positive(y) then
if negative(z) then Overflow()
else
if negative(x) and negative(y) then
if positive(z) then Overflow()
else Okay() ; // mixed signs, cant overflow

I think that's correct if overflow has the common wraparound
semantics.

Do the same thing for subtract, multiply and divide, with the obvious
changes.

Subtraction is easy enough. I think the only case where division can
overflow is INT_MIN/(-1) -- and, of course, you have to watch out for
division by zero. Multiplication is trickier. You can multiply two
positive numbers and get a truncated result that's still positive.
For example, if int is 16-bit 2's-complement with wraparound
semantics, then 300 * 300 yields 24464 (the 16 low-order bits of the
mathematical result of 90000).

The easiest way to do this would be to do a 32-bit multiplication and
check the value of the result. But if you're already using the
largest integer type available, that's not an option.

"Math is hard" -- Barbie

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[Flash Gordon]

Keith Thompson wrote:

"Ancient_Hacker" <gr**@comcast.netwrites:

>st******@gmail.com wrote:

>>but
what my wanted
is to judge the overflow in standard C language using some algorithm
without resorting to the assembly language within the scope of the int
type.

Nope, the results of a int + int are not defined if overflow happens.

Now you might find that on any reasonable CPU, int + int returns the
bottom bits of the result, but there's no guarantee.

you could try this tho:

z = x + y;

if positive(x) and positive(y) then
if negative(z) then Overflow()
else
if negative(x) and negative(y) then
if positive(z) then Overflow()
else Okay() ; // mixed signs, cant overflow

I think that's correct if overflow has the common wraparound
semantics.

Yes. Although not all processors follow those semantics under all
conditions. Some DSPs implement limiting at min/max at least as an
option because this behaviour can be very useful for signal processing.
If, for example, you are producing a waveform that will be sent to a
speaker then if you wrap the result you can generate a change rapid
enough to physically damage the speaker, so obviously limiting is *far*
superior behaviour for *some* situations.

>Do the same thing for subtract, multiply and divide, with the obvious
changes.

Subtraction is easy enough. I think the only case where division can
overflow is INT_MIN/(-1) -- and, of course, you have to watch out for
division by zero. Multiplication is trickier. You can multiply two
positive numbers and get a truncated result that's still positive.
For example, if int is 16-bit 2's-complement with wraparound
semantics, then 300 * 300 yields 24464 (the 16 low-order bits of the
mathematical result of 90000).

The easiest way to do this would be to do a 32-bit multiplication and
check the value of the result. But if you're already using the
largest integer type available, that's not an option.

If some false positives are acceptable then you could check fairly
easily. Take the absolute value of both numbers, find the highest bit
set numbering the bits from the lsb being 0 as is conventional. Then the
problem is reduced to one of knowing the number of value bits and simple
addition. You can reduce the number of false positives significantly
(probably even eliminate them completely, but I can't be bothered to
prove it) relatively easily. Something like:
int check_for_mult_overflow(int a, int b)
{
int log2a = highest_bit_set(a);
int log2b = highest_bit_set(b);
int a_bits_set = no_bits_set(a);
int b_bits_set = no_bits_set(b);
int limit_log2_result = HIGHEST_BIT_SET_IN_INT_MAX;

if ((INT_MIN < -INT_MAX) &&
(a < 0) && (b < 0) &&
(a_bits_set == 1) && (b_bits_set == 1) &&
(log2a + log2b == limit_log2_result))
return WOULD_NOT_OVERFLOW;

if (a_bits_set 1)
log2a++;
if (b_bits_set 1)
log2b++;
if ((a_bits_set 1) || (b_bits_set 1))
limit_log2_result++;
if (log2a + log2b limit_log2_result)
return WOULD_OVERFLOW;
else
return WOULD_NOT_OVERFLOW;
}

Writing (or obtaining by searching the group) the remaining functions
and the definition of HIGHEST_BIT_SET_IN_MAX is left as an exercise for
the reader (they are relatively easy since we are concerned with value
bits). As is verifying that I have not committed any off-by-one errors.
--
Flash Gordon
Still sigless on this computer.