# 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.