Is it possible to catch overflow in long long multiply ?

Is it possible to catch overflow in long long multiply ?

[Victor STINNER]

Hi,

I'm using gcc "long long" type for my calculator. I have to check
integer overflow. I'm using sign compare to check overflow, but it
doesn't work for 10^16 * 10^4 :
  10000000000000000 * 10000

Here you have my code to check overflow :
  long long produit = a * b; // a,b: long long
  bool ok;
  if (0 < a) {
    if (0 < b)
      ok = (produit > 0);  // (+)*(+) -> (+) ?
    else if (b == 0)
      ok = true;
    else
      ok = (produit < 0);  // (+)*(-) -> (-) ?
  } else if (a == 0) {
    ok = true;
  } else {
    if (0 < b)
      ok = (produit < 0);  // (-)*(+) -> (-) ?
    else if (b == 0)
      ok = true;
    else
      ok = (produit > 0);  // (-)*(-) -> (+) ?
  }

The problem is that "10000000000000000 * 10000" give
7766279631452241920. It's not the "expected result".

I know that GMP is the best solution, but I don't want to use it, I
prefer to just use long long.

I search in gcc code, but I didn't found the __multi3 function. I just
found #define __muldi3 __multi3 in gcc/libgcc2.h.

Any idea ?

Bye, Haypo

Re: Is it possible to catch overflow in long long multiply ?

[Geert Bosch]

On May 30, 2005, at 02:57, Victor STINNER wrote:
> I'm using gcc "long long" type for my calculator. I have to check
> integer overflow. I'm using sign compare to check overflow, but it
> doesn't work for 10^16 * 10^4 :
>   10000000000000000 * 10000

I see your question went unanswered, however I do think it is
relevant to the development of (not with) GCC. The ongoing
discussion regarding "Ada front-end depends on signed overflow"
focuses on Ada, but the same issues are true for C and C++ as well.

I think this may be an other case where GCC's increased reasoning
from the notion that signed integer overflow invokes undefined
behavior is harmful. True, your program invokes undefined behavior
according to the C standard, and as a result the behavior of the
code in presence of overflow is conforming to the C standard.

However, this case also shows how much 2s-complement arithmetic
is ingrained in our brains. Your real-world example, highlights
the fact that allowing GCC to reason from absence of overflows
breaks useful code, in effect removing the overflow detection
code, just like it removes Ada range checks.

Defaulting to -fwrapv for all compilations in order to get the
expected wraparound behavior significantly increases the quality
of the compiler in my opinion.

Propagating the assumption that  overflow cannot occur, and removing
checks based on that,  unnecessarily breaks code that otherwise,
with wraparound semantics, would be well-defined and correct.

   -Geert

Re: Is it possible to catch overflow in long long multiply ?

[Robert Dewar]

I definitely think that -fwrapv should be the default for
Ada.

Re: Is it possible to catch overflow in long long multiply ?

[Joe Buck]

On Fri, Jun 03, 2005 at 03:26:19PM -0400, Bradley Lucier wrote:
> Assuming that overflow of signed integer arithmetic wraps (and what gcc  
> flag do I have to set to assume this?) then here is the algorithm to  
> multiply x and y with overflow detection.

Cast to unsigned; we are guaranteed that unsigned arithmetic wraps.

Re: Is it possible to catch overflow in long long multiply ?

[Bradley Lucier]

This is the wrong list to ask such a question, but I'll answer it  
anyway since the answer might be of general interest.

There is a wonderful book "Hacker's Delight" by Henry S. Warren Jr.,

http://www.awprofessional.com/bookstore/product.asp? 
isbn=0201914654&redir=1&rl=1

In some ways it can be thought of as building on the HAKMEM memos of  
MIT; it has a Forward by Guy Steele.  The book has a lot of fast  
bit-twiddling (unbelievably, "twiddling" just passed my Mac's  
spell-checker) algorithms for operating at the machine word level and  
gives the answer to your question in Chapter 1.

Assuming that overflow of signed integer arithmetic wraps (and what gcc  
flag do I have to set to assume this?) then here is the algorithm to  
multiply x and y with overflow detection.

if y = 0 then
    result = 0
else if y = -1 then
   if x = the_minimum_negative_value then
       result = overflow
   else
       result = -x
else
   let z = x * y;
      if z / y = x then
         result = z
      else
         result = overflow

Brad