From: hudgens@SCRI.FSU.EDU (Jim Hudgens)
Newsgroups: comp.programming
Subject: Re: Detecting Integer Overflow/Underflow
Date: 22 Aug 92 15:38:51 GMT
Organization: SCRI, Florida State University
In-reply-to: erf@progress.COM's message of 21 Aug 92 18:22:06 GMT


In article <1992Aug21.182206.15853@progress.com> erf@progress.COM (Eric Feigenson) writes:

   I'm sure this is a solved problem, I just haven't been able to solve
   it :-)

   Given: Two numbers (integers) of the same bit-width (e.g., they're
   both stored as 16-bit integers), and writing in "C" (with no access to
   the assembly language of the machine; it must be portable!) is it
   possible to write code to detect whether the result of adding,
   substracting or multiplying the two numbers will result in overflow or
   underflow?  The detection can be done either before or after the
   operation.  It should, of course, be as efficient as possible, but any
   solutions are welcome.

I based my solution on the definition of overflow in Crawford and
Gelsinger's "Programming the 80386" (damn good book, by the way).
Sample code for adding two 16 bit integers and setting the overflow
flag based on the result (it's part of an 8086 emulator) follows.
Included is the pertinent comment in the source describing the
process.  Basically, once you have the result, and both operands, then
you can calculate the overflow based on bit operations.

The result is exact and has been tested pretty well. 
It's pretty grimy code when all the macros are expanded, but
not as bad as some of the other operations (rcl, etc).  

But there has *got* to be a better (i.e. faster) way.  This is one
of the major reasons I can't get >PC/XT speeds running on a Sun SS1.

Anyone have a better method?

JHH

---

/* CARRY CHAIN CALCULATION.
   This represents a somewhat expensive calculation which is 
   apparently required to emulate the setting of the OF and 
   AF flag.  The latter is not so important, but the former is.
   The overflow flag is the XOR of the top two bits of the 
   carry chain for an addition (similar for subtraction).
   Since we do not want to simulate the addition in a bitwise
   manner, we try to calculate the carry chain given the 
   two operands and the result.  

   So, given the following table, which represents the
   addition of two bits, we can derive a formula for 
   the carry chain.
 
       a   b   cin   r     cout
       0   0   0     0     0
       0   0   1     1     0
       0   1   0     1     0
       0   1   1     0     1 
       1   0   0     1     0
       1   0   1     0     1
       1   1   0     0     1  
       1   1   1     1     1

    Construction of Karnough table for cout:

               ab 
         r  \  00   01   11  10 
            |------------------
         0  |   0    1    1   1
         1  |   0    0    1   0

    By inspection, one gets:  cc = ab +  r'(a + b)

    That represents alot of operations, but NO CHOICE.... 

BORROW CHAIN CALCULATION.
   The following table represents the
   subtraction of two bits, from which we can derive a formula for 
   the borrow chain.
 
       a   b   bin   r     bout
       0   0   0     0     0
       0   0   1     1     1
       0   1   0     1     1
       0   1   1     0     1 
       1   0   0     1     0
       1   0   1     0     0
       1   1   0     0     0  
       1   1   1     1     1

    Construction of table for cout:

               ab 
         r  \  00   01   11  10 
            |------------------
         0  |   0    1    0   0
         1  |   1    1    1   0

    By inspection, one gets:  bc = a'b +  r(a' + b)

 */

/* d,s are the operands.  m holds the flags */

u_int16 add_word(PC_ENV *m ,u_int16 d ,u_int16 s)
 {
    register u_int32 res;         /* all operands in native machine order */
    register u_int32 cc;
    
    res = d + s;
    
    /* set the carry flag to be bit 16 */
    CONDITIONAL_SET_FLAG(res & 0x10000, m, F_CF);

    CONDITIONAL_SET_FLAG((res&0xffff)==0, m, F_ZF);
    CONDITIONAL_SET_FLAG(res & 0x8000, m, F_SF);
    CONDITIONAL_SET_FLAG(parity_tab[res&0xff], m, F_PF);

    /* calculate the carry chain  SEE NOTE AT TOP.*/
    cc =  (s & d) | ((~res) & (s | d));

    /* calculate overflow as the XOR of the two top bits of the carry
       chain.  This macro expands to:
       if (xor_tab[(cc>>14)&0x3]) SET_FLAG(m,F_OF); else CLEAR_FLAG(m,F_OF);
    */
    CONDITIONAL_SET_FLAG(xor_tab[(cc>>14)&0x3], m, F_OF);
    CONDITIONAL_SET_FLAG(cc&0x8, m, F_AF);
    
    return res;
 }    

----
--
Jim Hudgens 			Supercomputer Computations Research Institute
hudgens@sun13.scri.fsu.edu