Re: ANSI portable overflow detection

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

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