Detecting signed overflow in C/C++
At first glance, this question may seem like a duplicate of How to detect integer overflow?, however it is actually significantly different.
I've found that while detecting an unsigned integer overflow is pretty trivial, detecting a signed overflow in C/C++ is actually more difficult than most people think.
The most obvious, yet naive, way to do it would be something like:
int add(int lhs, int rhs)
{
int sum = lhs + rhs;
if ((lhs >= 0 && sum < rhs) || (lhs < 0 && sum > rhs)) {
/* an overflow has occurred */
abort();
}
return sum;
}
The problem with this is that according to the C standard, signed integer overflow is undefined behavior. In other words, according to the standard, as soon as you even cause a signed overflow, your program is just as invalid as if you dereferenced a null pointer. So you can't cause undefined behavior, and then try to detect the overflow after the fact, as in the above post-condition check example.
Even though the above check is likely to work on many compilers, you can't count on it. In fact, because the C standard says signed integer overflow is undefined, some compilers (like GCC) will optimize away the above check when optimization flags are set, because the compiler assumes a signed overflow is impossible. This totally breaks the attempt to check for overflow.
So, another possible way to check for overflow would be:
int add(int lhs, int rhs)
{
if (lhs >= 0 && rhs >= 0) {
if (INT_MAX - lhs <= rhs) {
/* overflow has occurred */
abort();
}
}
else if (lhs < 0 && rhs < 0) {
if (lhs <= INT_MIN - rhs) {
/* overflow has occurred */
abort();
}
}
return lhs + rhs;
}
This seems more promising, since we don't actually add the two integers together until we make sure in advance that performing such an add will not result in overflow. Thus, we don't cause any undefined behavior.
However, this solution is unfortunately 开发者_C百科a lot less efficient than the initial solution, since you have to perform a subtract operation just to test if your addition operation will work. And even if you don't care about this (small) performance hit, I'm still not entirely convinced this solution is adequate. The expression lhs <= INT_MIN - rhs seems exactly like the sort of expression the compiler might optimize away, thinking that signed overflow is impossible.
So is there a better solution here? Something that is guaranteed to 1) not cause undefined behavior, and 2) not provide the compiler with an opportunity to optimize away overflow checks? I was thinking there might be some way to do it by casting both operands to unsigned, and performing checks by rolling your own two's-complement arithmetic, but I'm not really sure how to do that.
No, your 2nd code isn't correct, but you are close: if you set
int half = INT_MAX/2;
int half1 = half + 1;
the result of an addition is INT_MAX. (INT_MAX is always an odd number). So this is valid input. But in your routine you will have INT_MAX - half == half1 and you would abort. A false positive.
This error can be repaired by putting < instead of <= in both checks.
But then also your code isn't optimal. The following would do:
int add(int lhs, int rhs)
{
if (lhs >= 0) {
if (INT_MAX - lhs < rhs) {
/* would overflow */
abort();
}
}
else {
if (rhs < INT_MIN - lhs) {
/* would overflow */
abort();
}
}
return lhs + rhs;
}
To see that this is valid, you have to symbolically add lhs on both sides of the inequalities, and this gives you exactly the arithmetical conditions that your result is out of bounds.
Your approach with subtraction is correct and well-defined. A compiler cannot optimize it away.
Another correct approach, if you have a larger integer type available, is to perform the arithmetic in the larger type and then check that the result fits in the smaller type when converting it back
int sum(int a, int b)
{
long long c;
assert(LLONG_MAX>INT_MAX);
c = (long long)a + b;
if (c < INT_MIN || c > INT_MAX) abort();
return c;
}
A good compiler should convert the entire addition and if statement into an int-sized addition and a single conditional jump-on-overflow and never actually perform the larger addition.
Edit: As Stephen pointed out, I'm having trouble getting a (not-so-good) compiler, gcc, to generate the sane asm. The code it generates is not terribly slow, but certainly suboptimal. If anyone knows variants on this code that will get gcc to do the right thing, I'd love to see them.
For the gcc case, from gcc 5.0 Release notes we can see it now provides a __builtin_add_overflow for checking overflow in addition:
A new set of built-in functions for arithmetics with overflow checking has been added: __builtin_add_overflow, __builtin_sub_overflow and __builtin_mul_overflow and for compatibility with clang also other variants. These builtins have two integral arguments (which don't need to have the same type), the arguments are extended to infinite precision signed type, +, - or * is performed on those, and the result is stored in an integer variable pointed to by the last argument. If the stored value is equal to the infinite precision result, the built-in functions return false, otherwise true. The type of the integer variable that will hold the result can be different from the types of the first two arguments.
For example:
__builtin_add_overflow( rhs, lhs, &result )
We can see from the gcc document Built-in Functions to Perform Arithmetic with Overflow Checking that:
[...]these built-in functions have fully defined behavior for all argument values.
clang also provides a set of checked arithmetic builtins:
Clang provides a set of builtins that implement checked arithmetic for security critical applications in a manner that is fast and easily expressable in C.
in this case the builtin would be:
__builtin_sadd_overflow( rhs, lhs, &result )
The fastest possible way is to use the GCC builtin:
int add(int lhs, int rhs) {
int sum;
if (__builtin_add_overflow(lhs, rhs, &sum))
abort();
return sum;
}
On x86, GCC compiles this into:
mov %edi, %eax
add %esi, %eax
jo call_abort
ret
call_abort:
call abort
which uses the processor's built-in overflow detection.
If you're not OK with using GCC builtins, the next fastest way is to use bit operations on the sign bits. Signed overflow in addition occurs when:
- the two operands have the same sign, and
- the result has a different sign than the operands.
The sign bit of ~(lhs ^ rhs) is on iff the operands have the same sign, and the sign bit of lhs ^ sum is on iff the result has a different sign than the operands. So you can do the addition in unsigned form to avoid undefined behavior, and then use the sign bit of ~(lhs ^ rhs) & (lhs ^ sum):
int add(int lhs, int rhs) {
unsigned sum = (unsigned) lhs + (unsigned) rhs;
if ((~(lhs ^ rhs) & (lhs ^ sum)) & 0x80000000)
abort();
return (int) sum;
}
This compiles into:
lea (%rsi,%rdi), %eax
xor %edi, %esi
not %esi
xor %eax, %edi
test %edi, %esi
js call_abort
ret
call_abort:
call abort
which is quite a lot faster than casting to a 64-bit type on a 32-bit machine (with gcc):
push %ebx
mov 12(%esp), %ecx
mov 8(%esp), %eax
mov %ecx, %ebx
sar $31, %ebx
clt
add %ecx, %eax
adc %ebx, %edx
mov %eax, %ecx
add $-2147483648, %ecx
mov %edx, %ebx
adc $0, %ebx
cmp $0, %ebx
ja call_abort
pop %ebx
ret
call_abort:
call abort
IMHO, the eastiest way to deal with overflow sentsitive C++ code is to use SafeInt<T>. This is a cross platform C++ template hosted on code plex which provides the safety guarantees that you desire here.
- https://github.com/dcleblanc/SafeInt
I find it very intuitive to use as it provides the many of the same usage patterns as normal numerical opertations and expresses over and under flows via exceptions.
If you use inline assembler you can check the overflow flag. Another possibility is taht you can use a safeint datatype. I recommend that read this paper on Integer Security.
The obvious solution is to convert to unsigned, to get the well-defined unsigned overflow behavior:
int add(int lhs, int rhs)
{
int sum = (unsigned)lhs + (unsigned)rhs;
if ((lhs >= 0 && sum < rhs) || (lhs < 0 && sum > rhs)) {
/* an overflow has occurred */
abort();
}
return sum;
}
This replaces the undefined signed overflow behavior with the implementation-defined conversion of out-of-range values between signed and unsigned, so you need to check your compiler's documentation to know exactly what will happen, but it should at least be well defined, and should do the right thing on any twos-complement machine that doesn't raise signals on conversions, which is pretty much every machine and C compiler built in the last 20 years.
Your fundamental problem is that lhs + rhs doesn't do the right thing. But if you're willing to assume a two's complement machine, we can fix that. Suppose you have a function to_int_modular that converts unsigned to int in a way that is guaranteed to be the inverse of conversion from int to unsigned, and it optimizes away to nothing at run time. (See below for how to implement it.)
If you use it to fix the undefined behavior in your original attempt, and also rewrite the conditional to avoid the redundant test of lhs >= 0 and lhs < 0, then you get
int add(int lhs, int rhs)
{
int sum = to_int_modular((unsigned)lhs + rhs);
if (lhs >= 0) {
if (sum < rhs)
abort();
} else {
if (sum > rhs)
abort();
}
return sum;
}
which should outperform the current top-voted answer, since it has a similar structure but requires fewer arithmetic operations.
(Reorganizing the if shouldn't be necessary, but in tests on godbolt, ICC and MSVC do eliminate the redundant test on their own, but GCC and Clang surprisingly don't.)
If you prefer to compute the result in a wider size and then bounds check, one way to do the bounds check is
long long sum = (long long)lhs + rhs;
if ((int)sum != sum)
abort();
... except that the behavior is undefined on overflow. But you can fix that with the same helper function:
if (to_int_modular(sum) != sum)
This will probably outperform the current accepted answer on compilers that aren't smart enough to optimize it to a test of the overflow flag.
Unfortunately, testing (visual inspection on godbolt) suggests that GCC, ICC and MSVC do better with the code above than with the code in the accepted answer, but Clang does better with the code in the accepted answer. As usual, nothing is easy.
This approach can only work on architectures where the ranges of int and unsigned are equally large, and the specific implementations below also depend on its being two's complement. Machines not meeting those specs are vanishingly rare, but I'll check for them anyway:
static_assert(INT_MIN + INT_MAX == -1 && UINT_MAX + INT_MIN == INT_MAX);
One way to implement to_int_modular is
inline int to_int_modular(unsigned u) {
int i;
memcpy(&i, &u, sizeof(i));
return i;
}
All major x64 compilers have no trouble optimizing that to nothing, but when optimizations are disabled, MSVC and ICC generate a call to memcpy, which may be a bit slow if you use this function a lot. This implementation also depends on details of the representation of unsigned and int that probably aren't guaranteed by the standard.
Another way is this:
inline int to_int_modular(unsigned u) {
return u <= INT_MAX ? (int)u : (int)(u - INT_MIN) + INT_MIN;
}
All major x64 compilers optimize that to nothing except ICC, which makes an utter mess of it and every variation that I could think of. ICX does fine, and it appears that Intel is abandoning ICC and moving to ICX, so maybe this problem will fix itself.
You may have better luck converting to 64-bit integers and testing similar conditions like that. For example:
#include <stdint.h>
...
int64_t sum = (int64_t)lhs + (int64_t)rhs;
if (sum < INT_MIN || sum > INT_MAX) {
// Overflow occurred!
}
else {
return sum;
}
You may want to take a closer look at how sign extension will work here, but I think it is correct.
How about:
int sum(int n1, int n2)
{
int result;
if (n1 >= 0)
{
result = (n1 - INT_MAX)+n2; /* Can't overflow */
if (result > 0) return INT_MAX; else return (result + INT_MAX);
}
else
{
result = (n1 - INT_MIN)+n2; /* Can't overflow */
if (0 > result) return INT_MIN; else return (result + INT_MIN);
}
}
I think that should work for any legitimate INT_MIN and INT_MAX (symmetrical or not); the function as shown clips, but it should be obvious how to get other behaviors).
In case of adding two long values, portable code can split the long value into low and high int parts (or into short parts in case long has the same size as int):
static_assert(sizeof(long) == 2*sizeof(int), "");
long a, b;
int ai[2] = {int(a), int(a >> (8*sizeof(int)))};
int bi[2] = {int(b), int(b >> (8*sizeof(int))});
... use the 'long' type to add the elements of 'ai' and 'bi'
Using inline assembly is the fastest way if targeting a particular CPU:
long a, b;
bool overflow;
#ifdef __amd64__
asm (
"addq %2, %0; seto %1"
: "+r" (a), "=ro" (overflow)
: "ro" (b)
);
#else
#error "unsupported CPU"
#endif
if(overflow) ...
// The result is stored in variable 'a'
By me, the simpliest check would be checking the signs of the operands and of the results.
Let's examine sum: the overflow could occur in both directions, + or -, only when both operands have the same sign. And, obviosly, the overflow will be when the sign of the result won't be the same as the sign of the operands.
So, a check like this will be enough:
int a, b, sum;
sum = a + b;
if (((a ^ ~b) & (a ^ sum)) & 0x80000000)
detect_oveflow();
Edit: as Nils suggested, this is the correct if condition:
((((unsigned int)a ^ ~(unsigned int)b) & ((unsigned int)a ^ (unsigned int)sum)) & 0x80000000)
And since when the instruction
add eax, ebx
leads to undefined behavior? There is no such thing in the Intel x86 instruction set refference..
I think that this works:
int add(int lhs, int rhs) {
volatile int sum = lhs + rhs;
if (lhs != (sum - rhs) ) {
/* overflow */
//errno = ERANGE;
abort();
}
return sum;
}
Using volatile keeps the compiler from optimizing away the test because it thinks that sum may have changed between the addition and the subtraction.
Using gcc 4.4.3 for x86_64 the assembly for this code does do the addition, the subtraction, and the test, though it stores everything on the stack and of unneeded stack operations. I even tried register volatile int sum = but the assembly was the same.
For a version with only int sum = (no volatile or register) the function did not do the test and did the addition using only one lea instruction (lea is Load Effective Address and is often used to do addition without touching the flags register).
Your version is larger code and has a lot more jumps, but I don't know which would be better.
加载中,请稍侯......
精彩评论