check integer overflow with GCC 4.5.2

S

sailer

Hi,

I have the following code which was used to check whether the result
of (a * b) is larger than the maximum integer value.

ovf(int a, int b, int *r, int *v)
{
*r = a * b;
if (b == 0 || a == *r / b)
*v = 0;
else
*v = 1;
}

int main()
{
int words;
int bytes;
int overflow;

//... whatever
ovf(words, sizeof(int), &bytes, &overflow);
if (overflow)
printf("overflow");
}

It doesn't work with GCC 4.5.2 if enabling -O2 or -O3, asm code
generated by GCC is as follows, call to ovf is eliminated, seems that
GCC evaluates (a == *r/b) to TRUE at compile time, is there anyway to
revise ovf to let it satisfy GCC? thanks in advance.

main:
pushl %ebp #
xorl %eax, %eax #
movl %esp, %ebp #,
popl %ebp #
ret
.size main, .-main
.ident "GCC: (GNU) 4.5.2"
.section .note.GNU-stack,"",@progbits
 
S

sailer

How about maybe:

#include <limits.h>

if (b == 0 || INT_MAX / b >= a)

Hi Pete,

Thanks for replying, I tried but no luck, call to ovf is still removed
by GCC.
 
S

sailer

sailer ha scritto:> Hi,
I have the following code which was used to check whether  the result
of (a * b)  is larger than the maximum integer value.
ovf(int a, int b, int *r, int *v)
{
         *r = a * b;
         if (b == 0 || a == *r / b)
                 *v = 0;
         else
                 *v = 1;
}

[...]

Since you are concerned with "signed int"s you should check against
both INT_MAX and INT_MIN. I just wrote the following function "overflow()"
(sorry for the poor choice of its name), that should do the trick
(it takes the two factors and returns 1 if an overflow will occur, 0 if
not):

#include <stdio.h>
#include <limits.h>

int overflow(int a, int b)
{
   if( b > 0 ) {
     if( (a > 0 && b <= INT_MAX / a) ||
         (a <= 0 && a >= INT_MIN / b) )
       return 0;
     else return 1;
   } else { /* b <= 0 */
     if( (a > 0 && b >= INT_MIN / a) ||
         (a <= 0 && (b == 0 || a >= INT_MAX / b)) )
       return 0;
     else return 1;
   }

}

void result(int a, int b)
{
   printf("\na = %d, b = %d\n", a, b), overflow(a, b) ?
   printf("[overflow detected]\n") :
   printf("[result = %d]\n", a * b);

}

int main(void)
{
   printf("INT_MAX = %d, INT_MIN = %d\n", INT_MAX, INT_MIN);
   result(INT_MAX, INT_MAX);
   result(INT_MIN, INT_MIN);
   result(INT_MIN, INT_MAX);
   result(4000000, -80000);
   result(20000, 20000);
   result(0, 4);
   result(3, 0);
   result(0, 0);
   return 0;

}

Thanks all for your help, currently I'm using "__attribute__
((noinline))" to bypass the issue.
 
P

Philip Lantz

Thanks for replying, I tried but no luck, call to ovf is still removed
by GCC.

Perhaps this is because ovf still had undefined behavior in the case
where you would want overflow to be set. If you use Pete's suggestion
*before* doing the multiplication (and avoid performing the multiplication
when it indicates overflow), I suspect it will work.

Philip
 
P

Philip Lantz

sailer ha scritto:> Hi,
I have the following code which was used to check whether the result
of (a * b) is larger than the maximum integer value.
ovf(int a, int b, int *r, int *v)
{
*r = a * b;
if (b == 0 || a == *r / b)
*v = 0;
else
*v = 1;
}

[...]

Since you are concerned with "signed int"s you should check against
both INT_MAX and INT_MIN. I just wrote the following function
"overflow()"
(sorry for the poor choice of its name), that should do the trick
(it takes the two factors and returns 1 if an overflow will occur, 0 if
not):

#include <stdio.h>
#include <limits.h>

int overflow(int a, int b)
{
if( b > 0 ) {
if( (a > 0 && b <= INT_MAX / a) ||
(a <= 0 && a >= INT_MIN / b) )
return 0;
else return 1;
} else { /* b <= 0 */
if( (a > 0 && b >= INT_MIN / a) ||
(a <= 0 && (b == 0 || a >= INT_MAX / b)) )
return 0;
else return 1;
}

}

void result(int a, int b)
{
printf("\na = %d, b = %d\n", a, b), overflow(a, b) ?
printf("[overflow detected]\n") :
printf("[result = %d]\n", a * b);

}

int main(void)
{
printf("INT_MAX = %d, INT_MIN = %d\n", INT_MAX, INT_MIN);
result(INT_MAX, INT_MAX);
result(INT_MIN, INT_MIN);
result(INT_MIN, INT_MAX);
result(4000000, -80000);
result(20000, 20000);
result(0, 4);
result(3, 0);
result(0, 0);
return 0;

}

Thanks all for your help, currently I'm using "__attribute__
((noinline))" to bypass the issue.

I doubt that this avoids the undefined behavior in ovf, so you still
may find that it does not work reliably.

Philip
 
G

gwowen

It doesn't work with GCC 4.5.2 if enabling -O2 or -O3, asm code
generated by GCC is as follows, call to ovf is eliminated, seems that
GCC evaluates (a == *r/b) to TRUE at compile time, is there anyway to
revise ovf to let it satisfy GCC? thanks in advance.

Not quite the question you asked, but ...

-O2 (and higher) turn on `-fstrict-overflow', and, to quote from the
fine manual: "For C (and C++) this means that overflow when doing
arithmetic with signed numbers is undefined, which means that the
compiler may assume that it will not happen. This permits various
optimizations..."

So try, -O2 -fno-strict-overflow to disable this optimization.
 
S

sailer

sailer ha scritto:> Hi,
I have the following code which was used tocheckwhether  the result
of (a * b)  is larger than the maximumintegervalue.
ovf(int a, int b, int *r, int *v)
{
         *r = a * b;
         if (b == 0 || a == *r / b)
                 *v = 0;
         else
                 *v = 1;
}
[...]
Since you are concerned with "signed int"s you shouldcheckagainst
both INT_MAX and INT_MIN. I just wrote the following function
"overflow()"
(sorry for the poor choice of its name), that should do the trick
(it takes the two factors and returns 1 if an overflow will occur, 0 if
not):
#include <stdio.h>
#include <limits.h>
int overflow(int a, int b)
{
   if( b > 0 ) {
     if( (a > 0 && b <= INT_MAX / a) ||
         (a <= 0 && a >= INT_MIN / b) )
       return 0;
     else return 1;
   } else { /* b <= 0 */
     if( (a > 0 && b >= INT_MIN / a) ||
         (a <= 0 && (b == 0 || a >= INT_MAX / b)) )
       return 0;
     else return 1;
   }
}
void result(int a, int b)
{
   printf("\na = %d, b = %d\n", a, b), overflow(a, b) ?
   printf("[overflow detected]\n") :
   printf("[result = %d]\n", a * b);
}
int main(void)
{
   printf("INT_MAX = %d, INT_MIN = %d\n", INT_MAX, INT_MIN);
   result(INT_MAX, INT_MAX);
   result(INT_MIN, INT_MIN);
   result(INT_MIN, INT_MAX);
   result(4000000, -80000);
   result(20000, 20000);
   result(0, 4);
   result(3, 0);
   result(0, 0);
   return 0;
}
Thanks all for your help, currently I'm using "__attribute__
((noinline))" to bypass the issue.

I doubt that this avoids the undefined behavior in ovf, so you still
may find that it does not work reliably.

Philip

Yes, you are right, just found the ovf is still treated by compiler as
undefined.
 
S

sailer

Perhaps this is because ovf still had undefined behavior in the case
where you would want overflow to be set. If you use Pete's suggestion
*before* doing the multiplication (and avoid performing the multiplication
when it indicates overflow), I suspect it will work.

Philip

Here is the c code and asm code of main, call to 'ovf' is elimiated by
compiler :

#include <stdio.h>
#include <limits.h>

void
ovf(int a, int b, int *v)
{
if (b == 0 || (INT_MAX/b >= a))
*v = 0;
else
*v = 1;
}

int main ()
{
int words;
int overflow;

ovf(words, sizeof(int), &overflow);
if (overflow)
printf("overflow\n");

return 0;
}

main:
pushl %ebp
xorl %eax, %eax
movl %esp, %ebp
subl $8, %esp
leave
ret
.size main, .-main
.ident "GCC: (GNU) 4.5.2"
.section .note.GNU-stack,"",@progbits


command line : gcc -O3 -m32 -msse2 a.c -S
 
S

sailer

Hi,

I have the following code which was used tocheckwhether  the result
of (a * b)  is larger than the maximumintegervalue.

ovf(int a, int b, int *r, int *v)
{
        *r = a * b;
        if (b == 0 || a == *r / b)
                *v = 0;
        else
                *v = 1;

}

int main()
{
    int words;
    int bytes;
    intoverflow;

    //... whatever
    ovf(words, sizeof(int), &bytes, &overflow);
    if (overflow)
       printf("overflow");

}

It doesn't work with GCC 4.5.2 if enabling -O2 or -O3, asm code
generated by GCC is as follows, call to ovf is eliminated, seems that
GCC evaluates (a == *r/b) to TRUE at compile time, is there anyway to
revise ovf to let it satisfy GCC? thanks in advance.

main:
        pushl   %ebp    #
        xorl    %eax, %eax      #
        movl    %esp, %ebp      #,
        popl    %ebp    #
        ret
        .size   main, .-main
        .ident  "GCC: (GNU) 4.5.2"
        .section        .note.GNU-stack,"",@progbits

I rewrite the c code to the follows and checking overflow works with
GCC 4.5.2 when enabling -O3,
is it safe enough? thanks.


#include <stdio.h>
#include <limits.h>

void
ovf(int a, int b, int *v, unsigned int *r)
{
*r = a * b;
if (b == 0 || (a = *r/b && *r <= INT_MAX))
*v = 0;
else
*v = 1;
}

int main ()
{
int words;
int bytes;
int overflow;

ovf(words, sizeof(int), &bytes, &overflow);
if (overflow)
printf("overflow\n");

return 0;
}
 
S

sailer

Hi,

I have the following code which was used tocheckwhether  the result
of (a * b)  is larger than the maximumintegervalue.

ovf(int a, int b, int *r, int *v)
{
        *r = a * b;
        if (b == 0 || a == *r / b)
                *v = 0;
        else
                *v = 1;

}

int main()
{
    int words;
    int bytes;
    int overflow;

    //... whatever
    ovf(words, sizeof(int), &bytes, &overflow);
    if (overflow)
       printf("overflow");

}

It doesn't work with GCC 4.5.2 if enabling -O2 or -O3, asm code
generated by GCC is as follows, call to ovf is eliminated, seems that
GCC evaluates (a == *r/b) to TRUE at compile time, is there anyway to
revise ovf to let it satisfy GCC? thanks in advance.

main:
        pushl   %ebp    #
        xorl    %eax, %eax      #
        movl    %esp, %ebp      #,
        popl    %ebp    #
        ret
        .size   main, .-main
        .ident  "GCC: (GNU) 4.5.2"
        .section        .note.GNU-stack,"",@progbits


I rewrite the c code to the follows and checking overflow works with
GCC 4.5.2 when enabling -O3,
is it safe enough? thanks.

#include <stdio.h>
#include <limits.h>

void
ovf(int a, int b, int *v, unsigned int *r)
{
*r = a * b;
if (b == 0 || (a == *r/b && *r <= INT_MAX))
*v = 0;
else
*v = 1;

}

int main ()
{
int words;
int bytes;
int overflow;

ovf(words, sizeof(int), &bytes, &overflow);
if (overflow)
printf("overflow\n");

return 0;
}
 
J

James Kuyper

On 11/28/2011 02:14 AM, sailer wrote:
....
Here is the c code and asm code of main, call to 'ovf' is elimiated by
compiler :

#include <stdio.h>
#include <limits.h>

void
ovf(int a, int b, int *v)
{
if (b == 0 || (INT_MAX/b >= a))
*v = 0;
else
*v = 1;
}

int main ()
{
int words;
int overflow;

ovf(words, sizeof(int), &overflow);

The behavior could be undefined, since 'words' is still uninitialized at
point, and could therefore, in principle, contain a trap representation,
though this is unlikely on most systems.

Even if it didn't have a trap representation, it would contain an
unspecified int value, and could therefore cause ovf() to put either 0
or 1 in overflow. gcc would therefore be within it's rights to assume
that you don't care whether it is a 0 or a 1, and to write code that
assumes whichever value is more convenient for the compiler, which would
be 0, because it allows optimizing away the call to printf(). I don't
know if that's what gcc actually did, but it would be perfectly legal if
it did.
if (overflow)
printf("overflow\n");

return 0;
}

main:
pushl %ebp
xorl %eax, %eax
movl %esp, %ebp
subl $8, %esp
leave
ret
.size main, .-main
.ident "GCC: (GNU) 4.5.2"
.section .note.GNU-stack,"",@progbits


command line : gcc -O3 -m32 -msse2 a.c -S

Even when I change your code to initialize 'words', the result was still
comparably short. There's a simple reason for this: ovf() is called only
once, with only a single fixed set of input arguments. gcc apparently
inlined the code of that function, and determined what it's result would
be with those inputs. It therefore optimized away the code that computed
the result, and replaced it with code that acted as though the result
had already been obtained.

Giving ovf() arguments that depend upon input data from the command
line, or from an input stream, or from a call to rand() would prevent
pre-computation of the results of ovf() like this.

Putting ovf() in a different translation unit would prevent the
in-lining of ovf().
 
K

Keith Thompson

sailer said:
I rewrite the c code to the follows and checking overflow works with
GCC 4.5.2 when enabling -O3,
is it safe enough? thanks.
No.

#include <stdio.h>
#include <limits.h>

void
ovf(int a, int b, int *v, unsigned int *r)
{
*r = a * b;

If the mathematical result of multiplying a and b is outside
the range INT_MIN .. INT_MAX, then the behavior of the above is
undefined. Nothing you do *after* performing the multiplication can
change that. For example, a conforming implementation could cause
your program to terminate as soon as the multiplication is attempted.
if (b == 0 || (a = *r/b && *r <= INT_MAX))
*v = 0;
else
*v = 1;
}

int main ()
{
int words;
int bytes;
int overflow;

ovf(words, sizeof(int), &bytes, &overflow);

And you're passing an uninitialized value to ovf().

And I *think* you've got the 3rd and 4th arguments reversed.
It's hard to tell because you called the parameters "v" and "r"
rather than something legible.
 
I

Ian Collins

And you're passing an uninitialized value to ovf().

And I *think* you've got the 3rd and 4th arguments reversed.
It's hard to tell because you called the parameters "v" and "r"
rather than something legible.

Add to that he is passing the wrong type (pointer to int rather than
pointer to unsigned) which will cause gcc to whinge.
 
N

Noob

sailer said:
Here is the c code and asm code of main, call to 'ovf' is
eliminated by compiler :

#include <stdio.h>
#include <limits.h>

void
ovf(int a, int b, int *v)
{
if (b == 0 || (INT_MAX/b >= a))
*v = 0;
else
*v = 1;
}

int main ()
{
int words;
int overflow;

ovf(words, sizeof(int), &overflow);
if (overflow)
printf("overflow\n");

return 0;
}

main:
pushl %ebp
xorl %eax, %eax
movl %esp, %ebp
subl $8, %esp
leave
ret
.size main, .-main
.ident "GCC: (GNU) 4.5.2"
.section .note.GNU-stack,"",@progbits


command line : gcc -O3 -m32 -msse2 a.c -S

$ cat ovf.c
#include <limits.h>
int mul_overflow(int a, int b)
{
return b && a > INT_MAX/b;
}

$ gcc -S -O3 -Wall -Wextra ovf.c
$ cat ovf.s
.file "ovf.c"
.text
.p2align 4,,15
..globl _mul_overflow
.def _mul_overflow; .scl 2; .type 32; .endef
_mul_overflow:
pushl %ebp
xorl %eax, %eax
movl %esp, %ebp
movl 12(%ebp), %ecx
testl %ecx, %ecx
je L2
movl $2147483647, %eax
movl %eax, %edx
sarl $31, %edx
idivl %ecx
cmpl 8(%ebp), %eax
setl %al
movzbl %al, %eax
L2:
popl %ebp
ret
 
8

88888 Dihedral

$ cat ovf.c
#include <limits.h>
int mul_overflow(int a, int b)
{
return b && a > INT_MAX/b;
}

$ gcc -S -O3 -Wall -Wextra ovf.c
$ cat ovf.s
.file "ovf.c"
.text
.p2align 4,,15
.globl _mul_overflow
.def _mul_overflow; .scl 2; .type 32; .endef
_mul_overflow:
pushl %ebp
xorl %eax, %eax
movl %esp, %ebp
movl 12(%ebp), %ecx
testl %ecx, %ecx
je L2
movl $2147483647, %eax
movl %eax, %edx
sarl $31, %edx
idivl %ecx
cmpl 8(%ebp), %eax
setl %al
movzbl %al, %eax
L2:
popl %ebp
ret

If I know the push down types of all arguments in a function in C in a platform, it is trivial to pick all those well packed arguments in the stack in a rcver after a long or a short jump. That assumes that callers pushes everything right down the stack or the heap.
 
S

sailer

(words) should be initialized
before its value is passed to ovf().

It's a demo code fragment, I checked the asm code to figure out
whether the overflow detection works,
and the type of bytes should be 'unsigned int', it was a typo error
and I tried to post a correction but
failed.
 
S

sailer

Hi,

I have the following code which was used to check whether  the result
of (a * b)  is larger than the maximum integer value.

ovf(int a, int b, int *r, int *v)
{
        *r = a * b;
        if (b == 0 || a == *r / b)
                *v = 0;
        else
                *v = 1;

}

int main()
{
    int words;
    int bytes;
    int overflow;

    //... whatever
    ovf(words, sizeof(int), &bytes, &overflow);
    if (overflow)
       printf("overflow");

}

It doesn't work with GCC 4.5.2 if enabling -O2 or -O3, asm code
generated by GCC is as follows, call to ovf is eliminated, seems that
GCC evaluates (a == *r/b) to TRUE at compile time, is there anyway to
revise ovf to let it satisfy GCC? thanks in advance.

main:
        pushl   %ebp    #
        xorl    %eax, %eax      #
        movl    %esp, %ebp      #,
        popl    %ebp    #
        ret
        .size   main, .-main
        .ident  "GCC: (GNU) 4.5.2"
        .section        .note.GNU-stack,"",@progbits

BTW. Thanks all for helping solving the problem, and sorry that I also
posted the same question to comp.lang.c++ without the knowledge of
cross-post.
 
J

James Kuyper

It's a demo code fragment, I checked the asm code to figure out
whether the overflow detection works,

Let that be a lesson: even "demo code fragments" should have defined
behavior; if they don't, your test becomes meaningless.
 
K

Keith Thompson

James Kuyper said:
Let that be a lesson: even "demo code fragments" should have defined
behavior; if they don't, your test becomes meaningless.

Right. If your code has undefined behavior, an optimizing compiler is
permitted to transform it in ways that depend on the assumption that the
behavior is defined.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,482
Members
44,901
Latest member
Noble71S45

Latest Threads

Top