91

乍一看,这个问题似乎与如何检测整数溢出?,但实际上有很大不同。

我发现虽然检测无符号整数溢出非常简单,但检测 C/C++ 中的有符号溢出实际上比大多数人想象的要困难。

最明显但最幼稚的方法是:

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; 
}

问题在于,根据 C 标准,有符号整数溢出是未定义的行为。 换句话说,根据标准,一旦您甚至导致有符号溢出,您的程序就如同取消引用空指针一样无效。所以你不能导致未定义的行为,然后在事后尝试检测溢出,如上面的后置条件检查示例。

尽管上述检查可能适用于许多编译器,但您不能指望它。事实上,因为 C 标准说有符号整数溢出是未定义的,所以一些编译器(如 GCC)会在设置优化标志时优化掉上述检查,因为编译器假定有符号溢出是不可能的。这完全破坏了检查溢出的尝试。

因此,检查溢出的另一种可能方法是:

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;
}

这似乎更有希望,因为我们实际上不会将两个整数相加,直到我们事先确保执行这样的相加不会导致溢出。因此,我们不会导致任何未定义的行为。

但是,不幸的是,此解决方案的效率比初始解决方案低很多,因为您必须执行减法运算才能测试您的加法运算是否有效。即使你不关心这个(小)性能损失,我仍然不完全相信这个解决方案是足够的。该表达式lhs <= INT_MIN - rhs看起来与编译器可能优化掉的那种表达式完全一样,认为有符号溢出是不可能的。

那么这里有更好的解决方案吗?保证 1) 不会导致未定义的行为,以及 2) 不会为编译器提供优化溢出检查的机会?我在想可能有一些方法可以通过将两个操作数都转换为无符号数,并通过滚动你自己的二进制补码算术来执行检查,但我不确定如何做到这一点。

4

13 回答 13

40

不,您的第二个代码不正确,但您很接近:如果您设置

int half = INT_MAX/2;
int half1 = half + 1;

加法的结果是INT_MAX。(INT_MAX始终是奇数)。所以这是有效的输入。但在你的日常生活中,你会拥有INT_MAX - half == half1并且你会中止。误报。

可以通过在两个检查中放置<而不是修复此错误。<=

但是,您的代码也不是最佳的。以下会做:

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;
}

要确定这是有效的,您必须lhs在不等式的两侧进行符号相加,这会准确地为您提供结果超出范围的算术条件。

于 2010-10-16T06:41:18.590 回答
28

您的减法方法是正确且定义明确的。编译器无法优化它。

如果您有更大的整数类型可用,另一种正确的方法是在较大的类型中执行算术,然后在将其转换回时检查结果是否适合较小的类型

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;
}

一个好的编译器应该将整个加法和if语句转换为一个大小的int加法和一个有条件的溢出跳转,并且从不实际执行更大的加法。

编辑:正如斯蒂芬指出的那样,我在获得一个(不太好的)编译器 gcc 来生成健全的 asm 时遇到了麻烦。它生成的代码不是很慢,但肯定不是最理想的。如果有人知道此代码的变体将使 gcc 做正确的事情,我很乐意看到它们。

于 2010-10-15T17:57:06.370 回答
18

对于 gcc 案例,从gcc 5.0 Release notes我们可以看到它现在还提供了一个__builtin_add_overflow用于检查溢出的功能:

添加了一组新的内置函数,用于具有溢出检查的算术:__builtin_add_overflow、__builtin_sub_overflow 和 __builtin_mul_overflow,并与 clang 以及其他变体兼容。这些内置函数有两个整数参数(不需要具有相同的类型),参数扩展为无限精度有符号类型,+、- 或 * 对它们执行,结果存储在指向的整数变量中通过最后一个论点。如果存储的值等于无限精度结果,则内置函数返回 false,否则返回 true。将保存结果的整数变量的类型可能与前两个参数的类型不同。

例如:

__builtin_add_overflow( rhs, lhs, &result )

我们可以从 gcc 文档Built-in Functions to Perform Arithmetic with Overflow Checking中看到:

[...]这些内置函数对所有参数值都有完全定义的行为。

clang 还提供了一组检查算术内置函数

Clang 提供了一组内置函数,它们以在 C 中快速且易于表达的方式为安全关键应用程序实现检查算法。

在这种情况下,内置将是:

__builtin_sadd_overflow( rhs, lhs, &result )
于 2015-08-31T18:18:15.613 回答
16

恕我直言,处理溢出敏感 C++ 代码的最简单方法是使用SafeInt<T>. 这是托管在 code plex 上的跨平台 C++ 模板,可提供您在此处所需的安全保证。

我发现它使用起来非常直观,因为它提供了许多与正常数值运算相同的使用模式,并通过异常表示溢出和溢出。

于 2010-10-15T17:32:48.977 回答
13

最快的方法是使用 GCC 内置:

int add(int lhs, int rhs) {
    int sum;
    if (__builtin_add_overflow(lhs, rhs, &sum))
        abort();
    return sum;
}

在 x86 上,GCC 将其编译为:

    mov %edi, %eax
    add %esi, %eax
    jo call_abort 
    ret
call_abort:
    call abort

它使用处理器的内置溢出检测。

如果您对使用 GCC 内置函数不满意,下一个最快的方法是对符号位使用位操作。有符号溢出还会在以下情况下发生:

  • 两个操作数具有相同的符号,并且
  • 结果的符号与操作数不同。

~(lhs ^ rhs)如果操作数的符号相同,则 的符号位为lhs ^ sumon,如果结果的符号与操作数的符号不同,则 的符号位为 on。因此,您可以以无符号形式进行加法以避免未定义的行为,然后使用 的符号位~(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;
}

这编译成:

    lea (%rsi,%rdi), %eax
    xor %edi, %esi
    not %esi
    xor %eax, %edi
    test %edi, %esi
    js call_abort
    ret
call_abort:
    call abort

这比在 32 位机器(使用 gcc)上转换为 64 位类型要快得多:

    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
于 2017-06-29T16:35:43.877 回答
11

如果您使用内联汇编程序,您可以检查溢出标志。另一种可能性是您可以使用safeint 数据类型。我建议阅读有关Integer Security的这篇论文。

于 2010-10-15T17:32:31.473 回答
1

您可能会更幸运地转换为 64 位整数并测试类似的条件。例如:

#include <stdint.h>

...

int64_t sum = (int64_t)lhs + (int64_t)rhs;
if (sum < INT_MIN || sum > INT_MAX) {
    // Overflow occurred!
}
else {
    return sum;
}

您可能想仔细看看符号扩展在这里是如何工作的,但我认为这是正确的。

于 2010-10-15T17:31:11.843 回答
1

怎么样:

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);
  }
}

我认为这应该适用于任何合法的INT_MININT_MAX(对称与否);功能如图所示,但如何获得其他行为应该很明显)。

于 2010-10-15T20:47:32.620 回答
1

显而易见的解决方案是转换为无符号,以获得明确定义的无符号溢出行为:

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;  
} 

这用实现定义的有符号和无符号之间的超出范围值的转换替换了未定义的有符号溢出行为,因此您需要检查编译器的文档以确切知道会发生什么,但它至少应该被明确定义,并且应该在任何不会在转换时引发信号的二进制补码机器上做正确的事情,这几乎是过去 20 年中构建的每台机器和 C 编译器。

于 2010-10-15T22:22:32.860 回答
1

你的根本问题是lhs + rhs没有做正确的事情。但是,如果您愿意假设一个二进制补码机器,我们可以解决这个问题。假设您有一个函数以某种方式to_int_modular转换unsigned为 toint的方式,该方式保证与从intto的转换相反unsigned,并且它在运行时优化为无。(参见下文了解如何实现它。)

如果您使用它来修复原始尝试中未定义的行为,并重写条件以避免对 and 进行冗余测试lhs >= 0lhs < 0那么您将得到

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; 
}

这应该优于当前投票最多的答案,因为它具有相似的结构但需要更少的算术运算。

(重新组织if应该没有必要,但在Godbolt 上的测试中,ICC 和 MSVC 确实会自行消除冗余测试,但 GCC 和 Clang 出人意料地没有。)

如果您希望以更大的尺寸计算结果然后进行边界检查,那么进行边界检查的一种方法是

 long long sum = (long long)lhs + rhs;
 if ((int)sum != sum)
  abort();

...除了行为在溢出时未定义。但是您可以使用相同的辅助函数来解决这个问题:

 if (to_int_modular(sum) != sum)

这可能会优于当前在编译器上接受的答案,这些编译器不够聪明,无法对其进行优化以测试溢出标志。

不幸的是,测试(对 Godbolt 的目视检查)表明 GCC、ICC 和 MSVC 使用上面的代码比使用已接受答案中的代码做得更好,但 Clang 使用已接受答案中的代码做得更好。像往常一样,没有什么是容易的。


这种方法只适用于int和的范围unsigned同样大的架构,下面的具体实现也依赖于它的二进制补码。不符合这些规格的机器非常罕见,但无论如何我都会检查它们:

static_assert(INT_MIN + INT_MAX == -1 && UINT_MAX + INT_MIN == INT_MAX);

一种实现方式to_int_modular

inline int to_int_modular(unsigned u) {
    int i;
    memcpy(&i, &u, sizeof(i));
    return i;
}

所有主要的 x64 编译器都可以毫无问题地将其优化为无,但是当禁用优化时,MSVC 和 ICC 会生成对 的调用memcpy,如果您经常使用此函数,这可能会有点慢。此实现还取决于标准可能无法保证unsigned的表示的细节。int

另一种方式是这样的:

inline int to_int_modular(unsigned u) {
    return u <= INT_MAX ? (int)u : (int)(u - INT_MIN) + INT_MIN;
}

除了ICC,所有主要的 x64 编译器都对其进行了优化,这使得它和我能想到的每一个变体都变得一团糟。ICX 做得很好,而且似乎英特尔正在放弃 ICC 并转向 ICX,所以也许这个问题会自行解决。

于 2021-10-15T19:08:26.220 回答
0

在添加两个long值的情况下,可移植代码可以将long值分成低部分和高int部分(或者在大小与 相同short的情况下分成部分):longint

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'

如果针对特定 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'
于 2017-06-06T13:18:16.747 回答
-1

对我来说,最简单的检查是检查操作数和结果的符号。

让我们检查一下 sum:溢出可能发生在两个方向,+ 或 -,只有当两个操作数具有相同的符号时。而且,很明显,当结果的符号与操作数的符号不同时,就会发生溢出。

所以,这样的检查就足够了:

int a, b, sum;
sum = a + b;
if  (((a ^ ~b) & (a ^ sum)) & 0x80000000)
    detect_oveflow();

编辑:正如 Nils 所建议的,这是正确的if条件:

((((unsigned int)a ^ ~(unsigned int)b) & ((unsigned int)a ^ (unsigned int)sum)) & 0x80000000)

自从当指令

add eax, ebx 

导致未定义的行为?Intel x86 指令集参考中没有这样的东西。

于 2010-10-15T20:46:35.897 回答
-3

我认为这有效:

int add(int lhs, int rhs) {
   volatile int sum = lhs + rhs;
   if (lhs != (sum - rhs) ) {
       /* overflow */
       //errno = ERANGE;
       abort();
   }
   return sum;
}

使用 volatile 可以防止编译器优化测试,因为它认为sum加法和减法之间可能发生了变化。

使用用于 x86_64 的 gcc 4.4.3,此代码的程序集确实执行加法、减法和测试,尽管它将所有内容存储在堆栈和不需要的堆栈操作中。我什至尝试过register volatile int sum =,但组装是一样的。

对于只有int sum =(没有易失性或寄存器)的版本,该函数没有进行测试,并且仅使用一条lea指令进行了加法(lea加载有效地址,通常用于在不接触标志寄存器的情况下进行加法)。

你的版本是更大的代码并且有更多的跳转,但我不知道哪个会更好

于 2010-10-15T19:39:06.120 回答