|
From: | Domingo Alvarez Duarte |
Subject: | Re: Function overflow relies on undefined behavior |
Date: | Wed, 15 Dec 2021 16:37:01 +0100 |
User-agent: | Mozilla/5.0 (X11; Linux x86_64; rv:78.0) Gecko/20100101 Thunderbird/78.14.0 |
Hello Caio !
Thank you for your discovery !
I can confirm what you've found, here is small C program to test it:
====
#include <stdio.h>
#include <limits.h>
static int overflow2(int u, int v)
{ /* check for integer overflow on computing u + v */
if (u > 0 && v > INT_MAX - u) return 1;
if (u < 0 && v < INT_MIN - u) return 1;
return 0;
}
static int overflow(int u, int v)
{ /* check for integer overflow on computing u + v */
if (u > 0 && v > 0 && u + v < 0)
return 1;
if (u < 0 && v < 0 && u + v > 0)
return 1;
return 0;
}
int main() {
int max_u = 10;
for(int u= 0, v = 0; u< max_u; ++u, ++v)
printf("== %d : %d : %d : %d\n", u, v, overflow(u,v),
overflow2(u,v));
for(int u= 0, v = INT_MAX-max_u; u < max_u; ++u, ++v)
printf(":::: %d : %d : %d : %d\n", u, v, overflow(u,v),
overflow2(u,v));
return 0;
}
====
Output without optimization:
====
gcc -o overflow overflow.c
./overflow
== 0 : 0 : 0 : 0
== 1 : 1 : 0 : 0
== 2 : 2 : 0 : 0
== 3 : 3 : 0 : 0
== 4 : 4 : 0 : 0
== 5 : 5 : 0 : 0
== 6 : 6 : 0 : 0
== 7 : 7 : 0 : 0
== 8 : 8 : 0 : 0
== 9 : 9 : 0 : 0
:::: 0 : 2147483637 : 0 : 0
:::: 1 : 2147483638 : 0 : 0
:::: 2 : 2147483639 : 0 : 0
:::: 3 : 2147483640 : 0 : 0
:::: 4 : 2147483641 : 0 : 0
:::: 5 : 2147483642 : 0 : 0
:::: 6 : 2147483643 : 1 : 1
:::: 7 : 2147483644 : 1 : 1
:::: 8 : 2147483645 : 1 : 1
:::: 9 : 2147483646 : 1 : 1
====
Output without optimization:
====
gcc -O2 -o overflow2 overflow.c
./overflow2
== 0 : 0 : 0 : 0
== 1 : 1 : 0 : 0
== 2 : 2 : 0 : 0
== 3 : 3 : 0 : 0
== 4 : 4 : 0 : 0
== 5 : 5 : 0 : 0
== 6 : 6 : 0 : 0
== 7 : 7 : 0 : 0
== 8 : 8 : 0 : 0
== 9 : 9 : 0 : 0
:::: 0 : 2147483637 : 0 : 0
:::: 1 : 2147483638 : 0 : 0
:::: 2 : 2147483639 : 0 : 0
:::: 3 : 2147483640 : 0 : 0
:::: 4 : 2147483641 : 0 : 0
:::: 5 : 2147483642 : 0 : 0
:::: 6 : 2147483643 : 0 : 1 <<< always 0
:::: 7 : 2147483644 : 0 : 1 <<< always 0
:::: 8 : 2147483645 : 0 : 1 <<< always 0
:::: 9 : 2147483646 : 0 : 1 <<< always 0
====
Cheers !
Greetings,
Files src/misc/okalg.c and src/api/mcfrelax.c define the following function:
static int overflow(int u, int v)
{ /* check for integer overflow on computing u + v */
if (u > 0 && v > 0 && u + v < 0) return 1;
if (u < 0 && v < 0 && u + v > 0) return 1;
return 0;
}
It contains integer overflow, which is undefined behavior by the C standard.
As I tested, both GCC 11.1.0 and clang 13.0.0 make this function always return 0 from optimization level O1 onwards.
Particularly function glp_mincost_relax4 appears to have received ad-hoc patches on the places this function is used.
I propose, instead, the following:
#include <limits.h>
static int overflow(int u, int v)
{ /* check for integer overflow on computing u + v */
return (u > 0 && v > INT_MAX - u) return 1;
if (u < 0 && v < INT_MIN - u) return 1;
return 0;
}
Best regards,--
[Prev in Thread] | Current Thread | [Next in Thread] |