C: How to check the overflow flag?

hydraMax · 02-20-2012, 11:22 PM

I've read that on amd64 arch. there is an integer overflow flag. Is it possible to examine that flag inside a C program, to check for addition/subtraction overflow? Also, does Linux have some kind of API relating to that?

Snark1994 · 02-21-2012, 06:37 AM

http://www.fefe.de/intof.html

"Issue 2" on this page seems to answer the question quite well:

Quote:

Unfortunately, there is no way to access this carry bit from C directly.

There are two ways to get around this:

Cast the numbers to a bigger integer type, then do the addition there, and check if the result is in the right range.
Do the addition normally, then check the result (e.g. if (a+23<23) overflow).
Check before adding whether the number you add can fit (requires knowledge of the maximum value for that data type)

Solution 1 does not work in general, because there might not be a bigger integer type, and solution 2 does not work, because in the C language, when adding a number to a pointer or to a signed integer, overflow is undefined. Unfortunately, gcc as of version 4.1 abuses this and optimizes away checks that would only be true if there was an overflow, in particular checks that check for an overflow. Here is an example program that demonstrates the problem.

That leaves us with approach 3. The general idea is given in the answer to question 20.6b of the C faq. Unfortunately, the example code has several issues:

It only works for ints.
We cannot easily generalize it, because we would need a function that returns INT_MAX for a given type.
It does not catch adding -5 to INT_MIN.

Hope this helps,

hydraMax · 02-21-2012, 12:46 PM

Hmm, thanks for the info, although I must admit I am hesitant to accept that answer. It seems like, in a language that accepts inline assembly, there must be a way. I'll explore this some more when I get more knowledgeable about assembly.

johnsfine · 02-21-2012, 01:40 PM

Quote:

Originally Posted by hydraMax

It seems like, in a language that accepts inline assembly, there must be a way.

I'm pretty sure you can't robustly use inline assembly to check the overflow bit from an add or subtract that was coded in C.

But you can code both the add or subtract and the overflow check together in one chunk of inline asm.

orgcandman · 02-21-2012, 04:03 PM

Quote:

Originally Posted by johnsfine

I'm pretty sure you can't robustly use inline assembly to check the overflow bit from an add or subtract that was coded in C.

But you can code both the add or subtract and the overflow check together in one chunk of inline asm.

What do you mean by this? Portability concern re: compilers? instruction ordering re: optimizers? Maintainability re: hardware instructions?

AFAIK, adding two unsigned will always allow you to detect if there was overflow by comparing if the resulting value is less than either of the arguments (note the keyword is unsigned), but it requires separate unsigned storage.

Additionally, it should be easy to tell a compliant C compiler (for instance, gcc) not to throw away "always true" checks, by saying that they're not always true via the volatile keyword.

I believe the following C code is portable, correct, compliant, and complete to demonstrate, but if I've violated something, INSERT DISCLAIMER HERE.

Code:

#include <assert.h>
#include <stdio.h>

/**
 * \brief Signed version of overflow detection, requiring an additional stack variable which cannot be optimized away.
 */
int signedadd(int a) {
    volatile int b = a;
    assert(b+100 > b);
    printf("%d %d\n",a+100,a);
    return a;
}

/**
 * \brief unsigned version of above. There is no extra stack variable.
 */
unsigned int unsignedadd(unsigned int a)
{
    assert( a + 100 > a );
    printf("%u %u\n",a+100,a);
    return a;
}

int main(int argc, char *argv[]) 
{
    if( argc == 1 )
    { 
        signedadd(100);
        signedadd(0x7fffffff);
    }
    else
    {

        unsignedadd(100);
        unsignedadd(0xffffffff);
    }
    return 0;
}

-Aaron

johnsfine · 02-21-2012, 05:10 PM

Quote:

Originally Posted by orgcandman

What do you mean by this?

Quote:

instruction ordering

Primarily that. It is nearly impossible to make the compiler keep the overflow check in the place you put it.

But also the add or subtract itself might be recoded in some way that doesn't effect the overflow flag (such as an LEA instruction).

Quote:

Originally Posted by orgcandman

Additionally, it should be easy to tell a compliant C compiler (for instance, gcc) not to throw away "always true" checks, by saying that they're not always true via the volatile keyword.

I just read a thread about that, which makes it sound far harder than you think. I'm not an expert on it myself (on when gcc would or wouldn't throw away conditions known or undefined at compile time). But I'm pretty sure you're wrong.

hydraMax · 02-21-2012, 11:18 PM

I have a draft of C99 that states (in section 3.4.3) that integer overflow is an undefined behavior. Furthermore, I know that there are multiple ways of representing integer signs in various architectures. Therefore, checking the result of an addition for an invalid sign change is not portable across architectures.

Of course, checking an overflow flag is not portable either, but my thought was to do some conditional compiling, using the fastest and simplest check method available for each arch.

@johnsfine: You wouldn't happen to know what that inline asm would look like, perchance?

orgcandman · 02-23-2012, 08:32 AM

Quote:

Originally Posted by johnsfine

Primarily that. It is nearly impossible to make the compiler keep the overflow check in the place you put it.

But also the add or subtract itself might be recoded in some way that doesn't effect the overflow flag (such as an LEA instruction).

That's probably true as a general rule, but for GCC, see: http://ibiblio.org/gferg/ldp/GCC-Inl...WTO.html#ss5.4

This, to my knowledeg, is a compiler guarantee that it won't reorder the assembly around the inlined asm. YMMV, and it's true that it isn't portable to other compilers. I'm not sure if it will or will not optimize the surrounding code. My gut says that it shouldn't, but then again my gut is large and filled with beer.

Quote:

I just read a thread about that, which makes it sound far harder than you think. I'm not an expert on it myself (on when gcc would or wouldn't throw away conditions known or undefined at compile time). But I'm pretty sure you're wrong.

Can you point me to the discussion? I'd be interested in reading that.

hydraMax · 02-26-2012, 11:30 PM

After reading the GCC-Inline-Assembly-HOWTO <http://ibiblio.org/gferg/ldp/GCC-Inline-Assembly-HOWTO.html>, and spending some more time in the AMD64 APM, I was able to figure this out. (Or, at least one solution):

Code:

$ cat test.c 
#include <stdio.h>
#include <limits.h>

int main() {
  char carry;
  unsigned long int val = ULONG_MAX - 10;
  while(1) {
    asm("movq %2, %%r9\n\t"
	"addq $1, %%r9\n\t"
	"setc %0\n\t"
	"movq %%r9, %1"
	:"=r"(carry), "=r"(val)
	:"r"(val)
	:"%r9"
	);
    printf("%lu\n", val);
    if(carry) {
      printf("overflow!\n");
      return 0;
    }
  }
}

The special asm syntax (with the colons) is required in order to let GCC know what data is being used for input and output, and what registers are being clobbered, so it doesn't mess up the assembly generation. Basically, I'm moving val into register %r9, adding to it, and then putting the result of the setc instruction into the carry variable. The setc instruction sets a byte operand to 1 or 0 depending on whether the carry flag (CF) is set. Then I go ahead and put the sum back into val.

Code:

$ gcc -O2 test.c -o test
$ ./test 
18446744073709551606
18446744073709551607
18446744073709551608
18446744073709551609
18446744073709551610
18446744073709551611
18446744073709551612
18446744073709551613
18446744073709551614
18446744073709551615
0
overflow!

Of course, you might need to adjust that code for your own situation.

So, anyway, if you think that was a helpful solution, feel free to give me a few rep points.