c - 如何在C中实现包装signed int加法

Question

这是对问题的完全重写。希望现在更清楚了。

我想在 C 中实现一个执行 signed int 加法的函数s 带包装以防溢出。

我想主要针对 x86-64 架构，但当然实现越便携越好。我还主要关心通过 gcc、clang、icc 以及 Windows 上使用的任何东西生成体面的汇编代码。

目标是双重的:

编写不落入未定义行为黑洞的正确 C 代码；

编写被编译为体面的机器代码的代码。

体面的机器代码是指单个 leal或单个 addl在 native 支持操作的机器上的指令。

我能够满足这两个要求中的任何一个，但不能同时满足。

尝试 1

想到的第一个实现是

int add_wrap(int x, int y) {
    return (unsigned) x + (unsigned) y;
}

这似乎适用于 gcc , clang和 icc .但是，据我所知，C 标准没有指定来自 unsigned int 的类型转换。至 signed int ，让实现自由(另见 here )。

Otherwise, if the new type is signed and the value cannot be represented in it; either the result is implementation-defined or an implementation-defined signal is raised.

我相信大多数(所有？)主要编译器都会从 unsigned 进行预期的转换至 int ，这意味着它们采用正确的代表模数 2^N，其中 N 是位数，但它不是标准规定的，因此不能依赖(愚蠢的 C 标准再次命中)。此外，虽然这是在二进制补码机上做的最简单的事情，但在补码机上是不可能的，因为有一个类是不可表示的:2^(N/2)。

尝试 2

根据 clang docs , 可以使用 __builtin_add_overflow像这样

int add_wrap(int x, int y) {
    int res;
    __builtin_add_overflow(x, y, &res);
    return res;
}

这应该可以用clang解决问题，因为文档清楚地说

If possible, the result will be equal to mathematically-correct result and the builtin will return 0. Otherwise, the builtin will return 1 and the result will be equal to the unique value that is equivalent to the mathematically-correct result modulo two raised to the k power, where k is the number of bits in the result type.

问题是在 GCC docs他们说

These built-in functions promote the first two operands into infinite precision signed type and perform addition on those promoted operands. The result is then cast to the type the third pointer argument points to and stored there.

据我所知，投自 long int至 int是特定于实现的，所以我没有看到任何保证这会导致包装行为。

正如你所看到的 [here][godbolt]，GCC 也会生成预期的代码，但我想确定这不是偶然的，并且确实是 __builtin_add_overflow 规范的一部分。 .

icc似乎也产生了一些合理的东西。

这产生了不错的汇编，但依赖于内在函数，因此它不是真正符合标准的 C。

尝试 3

听从 SEI CERT C Coding Standard 那些学究气的家伙的建议.

在他们的 CERT INT32-C建议他们解释了如何提前检查潜在的溢出。以下是根据他们的建议得出的结论:

#include <limits.h>

int add_wrap(int x, int y) {
    if ((x > 0) && (y > INT_MAX - x))
        return (x + INT_MIN) + (y + INT_MIN);
    else if ((x < 0) && (y < INT_MIN - x))
        return (x - INT_MIN) + (y - INT_MIN);
    else
        return x + y;
}

代码执行正确的检查并编译为 leal与 gcc ，但不是 clang或 icc .

整个 CERT INT32-C 建议完全是垃圾，因为它试图通过强制程序员执行检查来将 C 转换为“安全”语言，这些检查应该首先成为语言定义的一部分。这样做也迫使程序员编写编译器无法再优化的代码，那么再使用 C 的原因是什么？!

编辑

对比在于生成的程序集的兼容性和体面性。

例如，同时使用 gcc和 clang以下两个应该执行相同操作的函数被编译为不同的程序集。 f在这两种情况下都不好， g在这两种情况下都很好( addl + jo 或 addl + cmovnol )。不知道是不是 jo优于 cmovnol , 但函数 g始终优于 f .

#include <limits.h>

signed int f(signed int si_a, signed int si_b) {
  signed int sum;
  if (((si_b > 0) && (si_a > (INT_MAX - si_b))) ||
      ((si_b < 0) && (si_a < (INT_MIN - si_b)))) {
    return 0;
  } else {
    return si_a + si_b;
  }
}

signed int g(signed int si_a, signed int si_b) {
  signed int sum;
  if (__builtin_add_overflow(si_a, si_b, &sum)) {
    return 0;
  } else {
    return sum;
  }
}

Answer 1

I'm not so sure because of the rules for casting from unsigned to signed

你完全引用了规则。如果从无符号值转换为有符号值，则结果是实现定义的或引发信号。简而言之，将发生的事情由您的编译器描述。
例如 gcc9.2.0 编译器在 it's documentation about implementation defined behavior of integers 中有以下内容:

The result of, or the signal raised by, converting an integer to a signed integer type when the value cannot be represented in an object of that type (C90 6.2.1.2, C99 and C11 6.3.1.3).

For conversion to a type of width N, the value is reduced modulo 2^N to be within range of the type; no signal is raised.