>Number:         6586
>Category:       c
>Synopsis:       -ftrapv doesn't catch multiplication overflow
>Confidential:   no
>Severity:       serious
>Priority:       medium
>Responsible:    unassigned
>State:          open
>Class:          sw-bug
>Submitter-Id:   net
>Arrival-Date:   Mon May 06 13:06:01 PDT 2002
>Closed-Date:
>Last-Modified:
>Originator:     Bruno Haible
>Release:        3.1 20020423 (prerelease)
>Organization:
GNU hackers
>Environment:
System: Linux linuix 2.4.18-4GB #1 Wed Mar 27 13:57:05 UTC 2002 i686 unknown
Architecture: i686

	
host: i686-pc-linux-gnu
build: i686-pc-linux-gnu
target: i686-pc-linux-gnu
configured with: ../configure --prefix=/packages/gnu-snapshot --enable-shared --enable-version-specific-runtime-libs --enable-nls
>Description:


Multiplication overflow is not caught by -ftrapv in 50% of the cases, on
average.

$ cat foo.c
int foo (int x, int y)
{
  return x * y;
}

int main ()
{
  foo(600000000,1024);
  return 0;
}

$ gcc -v
Lecture des spécification à partir de /packages/gnu-snapshot/lib/gcc-lib/i686-pc-linux-gnu/3.1/specs
Configuré avec: ../configure --prefix=/packages/gnu-snapshot --enable-shared --enable-version-specific-runtime-libs --enable-nls
Modèle de thread: single
version gcc 3.1 20020423 (prerelease)

$ gcc -ftrapv foo.c
$ ./a.out 
$ echo $?
0

The reason is simply a broken __mulvsi3 implementation in libgcc2.c.
Other -ftrapv helper functions are broken as well:
- __subvsi3 may not behave correctly if b = -0x80000000.
- __subvdi3 has an obvious typo that could cause wrong results.
- __mulvsi3 has a wrong overflow check.
- __absvdi2 has an obvious typo that could cause wrong results.
- __mulvdi3 has a wrong overflow check.

>How-To-Repeat:

See above

>Fix:

Here is a patch.


2002-05-04  Bruno Haible  <bruno@clisp.org>

	* libgcc2.c (__subvsi3): Remove simplification that would not work
	when subtracting -0x80000000.
	(__subvdi3): Remove simplification that would return a wrong result.
	(__mulvsi3): Fix overflow check.
	(__absvdi2): Fix simplification that would return a wrong result.
	(__mulvdi3): Fix overflow check.

*** libgcc2.c.bak	2002-04-03 06:20:51.000000000 +0200
--- libgcc2.c	2002-05-04 23:24:22.000000000 +0200
***************
*** 1,7 ****
  /* More subroutines needed by GCC output code on some machines.  */
  /* Compile this one with gcc.  */
  /* Copyright (C) 1989, 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999,
!    2000, 2001  Free Software Foundation, Inc.
  
  This file is part of GCC.
  
--- 1,7 ----
  /* More subroutines needed by GCC output code on some machines.  */
  /* Compile this one with gcc.  */
  /* Copyright (C) 1989, 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999,
!    2000, 2001, 2002  Free Software Foundation, Inc.
  
  This file is part of GCC.
  
***************
*** 98,106 ****
  Wtype
  __subvsi3 (Wtype a, Wtype b)
  {
- #ifdef L_addvsi3
-   return __addvsi3 (a, (-b));
- #else
    DWtype w;
  
    w = a - b;
--- 98,103 ----
***************
*** 109,115 ****
      abort ();
  
    return w;
- #endif
  }
  #endif
  
--- 106,111 ----
***************
*** 117,125 ****
  DWtype
  __subvdi3 (DWtype a, DWtype b)
  {
- #ifdef L_addvdi3
-   return (a, (-b));
- #else
    DWtype w;
  
    w = a - b;
--- 113,118 ----
***************
*** 128,146 ****
      abort ();
  
    return w;
- #endif
  }
  #endif
  
  #ifdef L_mulvsi3
  Wtype
  __mulvsi3 (Wtype a, Wtype b)
  {
    DWtype w;
  
!   w = a * b;
  
!   if (((a >= 0) == (b >= 0)) ? w < 0 : w > 0)
      abort ();
  
    return w;
--- 121,141 ----
      abort ();
  
    return w;
  }
  #endif
  
  #ifdef L_mulvsi3
+ #define WORD_SIZE (sizeof (Wtype) * BITS_PER_UNIT)
  Wtype
  __mulvsi3 (Wtype a, Wtype b)
  {
    DWtype w;
  
!   w = (DWtype) a * (DWtype) b;
  
!   if (((a >= 0) == (b >= 0))
!       ? (UDWtype) w > (UDWtype) (((DWtype) 1 << (WORD_SIZE - 1)) - 1)
!       : (UDWtype) w < (UDWtype) ((DWtype) -1 << (WORD_SIZE - 1)))
      abort ();
  
    return w;
***************
*** 204,211 ****
     DWtype w = a;
  
     if (a < 0)
! #ifdef L_negvsi2
!      w = __negvsi2 (a);
  #else
       w = -a;
  
--- 199,206 ----
     DWtype w = a;
  
     if (a < 0)
! #ifdef L_negvdi2
!      w = __negvdi2 (a);
  #else
       w = -a;
  
***************
*** 218,234 ****
  #endif
  
  #ifdef L_mulvdi3
  DWtype
  __mulvdi3 (DWtype u, DWtype v)
  {
!    DWtype w;
  
!   w = u * v;
  
!   if (((u >= 0) == (v >= 0)) ? w < 0 : w > 0)
!     abort ();
  
!   return w;
  }
  #endif
  
--- 213,344 ----
  #endif
  
  #ifdef L_mulvdi3
+ #define WORD_SIZE (sizeof (Wtype) * BITS_PER_UNIT)
  DWtype
  __mulvdi3 (DWtype u, DWtype v)
  {
!   /* The unchecked multiplication needs 3 Wtype x Wtype multiplications, but
!      the checked multiplication needs only 2 Wtype x Wtype multiplications.  */
!   DWunion uu, vv;
  
!   uu.ll = u;
!   vv.ll = v;
  
!   if (__builtin_expect (uu.s.high == uu.s.low >> (WORD_SIZE - 1), 1))
!     {
!       /* u fits into a single Wtype.  */
!       if (__builtin_expect (vv.s.high == vv.s.low >> (WORD_SIZE - 1), 1))
! 	{
! 	  /* v fits into a single Wtype as well.  */
! 	  /* A single multiplication.  No overflow risk.  */
! 	  return (DWtype) uu.s.low * (DWtype) vv.s.low;
! 	}
!       else
! 	{
! 	  /* Two multiplications.  */
! 	  DWunion w0, w1;
  
! 	  w0.ll = (UDWtype) (UWtype) uu.s.low * (UDWtype) (UWtype) vv.s.low;
! 	  w1.ll = (UDWtype) (UWtype) uu.s.low * (UDWtype) (UWtype) vv.s.high;
! 	  if (vv.s.high < 0)
! 	    w1.s.high -= uu.s.low;
! 	  if (uu.s.low < 0)
! 	    w1.ll -= vv.ll;
! 	  w1.ll += (UWtype) w0.s.high;
! 	  if (__builtin_expect (w1.s.high == w1.s.low >> (WORD_SIZE - 1), 1))
! 	    {
! 	      w0.s.high = w1.s.low;
! 	      return w0.ll;
! 	    }
! 	}
!     }
!   else
!     {
!       if (__builtin_expect (vv.s.high == vv.s.low >> (WORD_SIZE - 1), 1))
! 	{
! 	  /* v fits into a single Wtype.  */
! 	  /* Two multiplications.  */
! 	  DWunion w0, w1;
! 
! 	  w0.ll = (UDWtype) (UWtype) uu.s.low * (UDWtype) (UWtype) vv.s.low;
! 	  w1.ll = (UDWtype) (UWtype) uu.s.high * (UDWtype) (UWtype) vv.s.low;
! 	  if (uu.s.high < 0)
! 	    w1.s.high -= vv.s.low;
! 	  if (vv.s.low < 0)
! 	    w1.ll -= uu.ll;
! 	  w1.ll += (UWtype) w0.s.high;
! 	  if (__builtin_expect (w1.s.high == w1.s.low >> (WORD_SIZE - 1), 1))
! 	    {
! 	      w0.s.high = w1.s.low;
! 	      return w0.ll;
! 	    }
! 	}
!       else
! 	{
! 	  /* A few sign checks and a single multiplication.  */
! 	  if (uu.s.high >= 0)
! 	    {
! 	      if (vv.s.high >= 0)
! 		{
! 		  if (uu.s.high == 0 && vv.s.high == 0)
! 		    {
! 		      DWtype w;
! 
! 		      w = (UDWtype) (UWtype) uu.s.low
! 			  * (UDWtype) (UWtype) vv.s.low;
! 		      if (__builtin_expect (w >= 0, 1))
! 			return w;
! 		    }
! 		}
! 	      else
! 		{
! 		  if (uu.s.high == 0 && vv.s.high == (Wtype) -1)
! 		    {
! 		      DWunion ww;
! 
! 		      ww.ll = (UDWtype) (UWtype) uu.s.low
! 			      * (UDWtype) (UWtype) vv.s.low;
! 		      ww.s.high -= uu.s.low;
! 		      if (__builtin_expect (ww.s.high < 0, 1))
! 			return ww.ll;
! 		    }
! 		}
! 	    }
! 	  else
! 	    {
! 	      if (vv.s.high >= 0)
! 		{
! 		  if (uu.s.high == (Wtype) -1 && vv.s.high == 0)
! 		    {
! 		      DWunion ww;
! 
! 		      ww.ll = (UDWtype) (UWtype) uu.s.low
! 			      * (UDWtype) (UWtype) vv.s.low;
! 		      ww.s.high -= vv.s.low;
! 		      if (__builtin_expect (ww.s.high < 0, 1))
! 			return ww.ll;
! 		    }
! 		}
! 	      else
! 		{
! 		  if (uu.s.high == (Wtype) -1 && vv.s.high == (Wtype) -1)
! 		    {
! 		      DWunion ww;
! 
! 		      ww.ll = (UDWtype) (UWtype) uu.s.low
! 			      * (UDWtype) (UWtype) vv.s.low;
! 		      ww.s.high -= uu.s.low;
! 		      ww.s.high -= vv.s.low;
! 		      if (__builtin_expect (ww.s.high >= 0, 1))
! 			return ww.ll;
! 		    }
! 		}
! 	    }
! 	}
!     }
! 
!   /* Overflow.  */
!   abort ();
  }
  #endif
  
>Release-Note:
>Audit-Trail:
>Unformatted: