home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / comp / programm / 2430 < prev    next >
Encoding:
Internet Message Format  |  1992-08-22  |  4.7 KB
  1. Path: sparky!uunet!gatech!mailer.cc.fsu.edu!sun13!sun13.scri.fsu.edu!hudgens
  2. From: hudgens@SCRI.FSU.EDU (Jim Hudgens)
  3. Newsgroups: comp.programming
  4. Subject: Re: Detecting Integer Overflow/Underflow
  5. Message-ID: <HUDGENS.92Aug22113851@sun13.SCRI.FSU.EDU>
  6. Date: 22 Aug 92 15:38:51 GMT
  7. References: <1992Aug21.182206.15853@progress.com>
  8. Sender: hudgens@sun13.scri.fsu.edu
  9. Organization: SCRI, Florida State University
  10. Lines: 133
  11. In-reply-to: erf@progress.COM's message of 21 Aug 92 18:22:06 GMT
  12.  
  13.  
  14. In article <1992Aug21.182206.15853@progress.com> erf@progress.COM (Eric Feigenson) writes:
  15.  
  16.    I'm sure this is a solved problem, I just haven't been able to solve
  17.    it :-)
  18.  
  19.    Given: Two numbers (integers) of the same bit-width (e.g., they're
  20.    both stored as 16-bit integers), and writing in "C" (with no access to
  21.    the assembly language of the machine; it must be portable!) is it
  22.    possible to write code to detect whether the result of adding,
  23.    substracting or multiplying the two numbers will result in overflow or
  24.    underflow?  The detection can be done either before or after the
  25.    operation.  It should, of course, be as efficient as possible, but any
  26.    solutions are welcome.
  27.  
  28. I based my solution on the definition of overflow in Crawford and
  29. Gelsinger's "Programming the 80386" (damn good book, by the way).
  30. Sample code for adding two 16 bit integers and setting the overflow
  31. flag based on the result (it's part of an 8086 emulator) follows.
  32. Included is the pertinent comment in the source describing the
  33. process.  Basically, once you have the result, and both operands, then
  34. you can calculate the overflow based on bit operations.
  35.  
  36. The result is exact and has been tested pretty well. 
  37. It's pretty grimy code when all the macros are expanded, but
  38. not as bad as some of the other operations (rcl, etc).  
  39.  
  40. But there has *got* to be a better (i.e. faster) way.  This is one
  41. of the major reasons I can't get >PC/XT speeds running on a Sun SS1.
  42.  
  43. Anyone have a better method?
  44.  
  45. JHH
  46.  
  47. ---
  48.  
  49. /* CARRY CHAIN CALCULATION.
  50.    This represents a somewhat expensive calculation which is 
  51.    apparently required to emulate the setting of the OF and 
  52.    AF flag.  The latter is not so important, but the former is.
  53.    The overflow flag is the XOR of the top two bits of the 
  54.    carry chain for an addition (similar for subtraction).
  55.    Since we do not want to simulate the addition in a bitwise
  56.    manner, we try to calculate the carry chain given the 
  57.    two operands and the result.  
  58.  
  59.    So, given the following table, which represents the
  60.    addition of two bits, we can derive a formula for 
  61.    the carry chain.
  62.  
  63.        a   b   cin   r     cout
  64.        0   0   0     0     0
  65.        0   0   1     1     0
  66.        0   1   0     1     0
  67.        0   1   1     0     1 
  68.        1   0   0     1     0
  69.        1   0   1     0     1
  70.        1   1   0     0     1  
  71.        1   1   1     1     1
  72.  
  73.     Construction of Karnough table for cout:
  74.  
  75.                ab 
  76.          r  \  00   01   11  10 
  77.             |------------------
  78.          0  |   0    1    1   1
  79.          1  |   0    0    1   0
  80.  
  81.     By inspection, one gets:  cc = ab +  r'(a + b)
  82.  
  83.     That represents alot of operations, but NO CHOICE.... 
  84.  
  85. BORROW CHAIN CALCULATION.
  86.    The following table represents the
  87.    subtraction of two bits, from which we can derive a formula for 
  88.    the borrow chain.
  89.  
  90.        a   b   bin   r     bout
  91.        0   0   0     0     0
  92.        0   0   1     1     1
  93.        0   1   0     1     1
  94.        0   1   1     0     1 
  95.        1   0   0     1     0
  96.        1   0   1     0     0
  97.        1   1   0     0     0  
  98.        1   1   1     1     1
  99.  
  100.     Construction of table for cout:
  101.  
  102.                ab 
  103.          r  \  00   01   11  10 
  104.             |------------------
  105.          0  |   0    1    0   0
  106.          1  |   1    1    1   0
  107.  
  108.     By inspection, one gets:  bc = a'b +  r(a' + b)
  109.  
  110.  */
  111.  
  112. /* d,s are the operands.  m holds the flags */
  113.  
  114. u_int16 add_word(PC_ENV *m ,u_int16 d ,u_int16 s)
  115.  {
  116.     register u_int32 res;         /* all operands in native machine order */
  117.     register u_int32 cc;
  118.     
  119.     res = d + s;
  120.     
  121.     /* set the carry flag to be bit 16 */
  122.     CONDITIONAL_SET_FLAG(res & 0x10000, m, F_CF);
  123.  
  124.     CONDITIONAL_SET_FLAG((res&0xffff)==0, m, F_ZF);
  125.     CONDITIONAL_SET_FLAG(res & 0x8000, m, F_SF);
  126.     CONDITIONAL_SET_FLAG(parity_tab[res&0xff], m, F_PF);
  127.  
  128.     /* calculate the carry chain  SEE NOTE AT TOP.*/
  129.     cc =  (s & d) | ((~res) & (s | d));
  130.  
  131.     /* calculate overflow as the XOR of the two top bits of the carry
  132.        chain.  This macro expands to:
  133.        if (xor_tab[(cc>>14)&0x3]) SET_FLAG(m,F_OF); else CLEAR_FLAG(m,F_OF);
  134.     */
  135.     CONDITIONAL_SET_FLAG(xor_tab[(cc>>14)&0x3], m, F_OF);
  136.     CONDITIONAL_SET_FLAG(cc&0x8, m, F_AF);
  137.     
  138.     return res;
  139.  }    
  140.  
  141. ----
  142. --
  143. Jim Hudgens             Supercomputer Computations Research Institute
  144. hudgens@sun13.scri.fsu.edu      
  145.  
  146.