Re: ANSI portable overflow detection

upton@quip.eecs.umich.edu (Michael Upton)
Fri, 13 May 1994 14:08:11 GMT

          From comp.compilers

Related articles
ANSI portable overflow detection davids@ICSI.Berkeley.EDU (1994-05-12)
Re: ANSI portable overflow detection upton@quip.eecs.umich.edu (1994-05-13)
Re: ANSI portable overflow detection hbaker@netcom.com (1994-05-13)
Re: ANSI portable overflow detection Roger@natron.demon.co.uk (1994-05-18)
| List of all articles for this month |

Newsgroups: comp.compilers
From: upton@quip.eecs.umich.edu (Michael Upton)
Keywords: arithmetic
Organization: University of Michigan EECS Dept.
References: 94-05-039
Date: Fri, 13 May 1994 14:08:11 GMT

David Petrie Stoutamire <davids@ICSI.Berkeley.EDU> wrote:
>[for a compiler that translates into C, is there a reasonably efficient
>and portable way to check for overflow on an integer multiply?]


An N bit multiply can be performed using 4 N/2 bit multiplies.




A * B = ??


                      A
                    *B
-----------------
                    YZ


for 2's comp arithmetic you want Y to be all 0s or all 1's.




A and B can be represented by 2 N/2 bit halfs:
A= jk
B= lm


A * B =
jk*lm =


                    jk
                  *lm
---------------
                    km
                  jm0
                  kl0
              +jl00
----------------
                pqrs


Z = rs
Y=pq
C= carry out of Z into Y
Z = k*m + (((j*m)+(k*l))<< N/2)
Y = (l*j) + (((j*m)+(k*l))>> N/2) + C


C = ((((k*m) >> N/2) + (j*m) + (k*l)) >> N/2) - (Z>>N/2)
Y should be all 1's or all 0's




You will probably want to convert A and B to positive before
creating jk and lm. If you do this then the msb of l and j will be 0,
and thus the msb of (j*m) and the msb of (k*l) will be 0.


I think the C term is correct, but you would want to derive this
over yourself.




mike
--


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.