C++ 中的签名溢出和未定义行为 (UB)
Signed overflow in C++ and undefined behaviour (UB)
我想知道如何使用如下代码
int result = 0;
int factor = 1;
for (...) {
result = ...
factor *= 10;
}
return result;
如果循环迭代 n 次，则 factor 正好乘以 10 次 n 次。但是，factor 仅在乘以 10 总共 n-1 次后才被使用。如果我们假设 factor 除了在循环的最后一次迭代之外永远不会溢出，但可能会在循环的最后一次迭代时溢出，那么这样的代码应该是可以接受的吗？在这种情况下，factor 的值将在溢出发生后被证明永远不会被使用。
我正在争论是否应该接受这样的代码。可以将乘法放在 if 语句中，并且在循环可能溢出时不在循环的最后一次迭代中执行乘法。缺点是它会使代码混乱并添加一个不必要的分支，需要检查所有先前的循环迭代。我还可以少迭代一次循环并在循环后复制一次循环体，同样，这会使代码复杂化。
有问题的实际代码用在一个紧密的内部循环中，在实时图形应用程序中消耗了总 CPU 时间的很大一部分。
int 溢出的行为未定义。
如果在循环体之外读到factor也没关系；如果到那时它已经溢出，那么你的代码在之前、之后以及有点自相矛盾的行为是未定义的。
保留此代码可能会出现的一个问题是编译器在优化方面变得越来越积极。特别是他们正在养成一种习惯，他们假设未定义的行为永远不会发生。为此，他们可能会完全删除 for 循环。
你不能为 factor 使用 unsigned 类型吗？尽管那样你需要担心在包含这两个的表达式中 int 到 unsigned 的意外转换？
编译器假定有效的 C++ 程序不包含 UB。考虑例如：
if (x == nullptr) {
*x = 3;
} else {
*x = 5;
}
If x == nullptr 然后取消引用它并赋值是 UB。因此，这可以在有效程序中结束的唯一方法是 x == nullptr 永远不会产生 true 并且编译器可以假设在 as if 规则下，以上等同于：
*x = 5;
现在在您的代码中
int result = 0;
int factor = 1;
for (...) { // Loop until factor overflows but not more
result = ...
factor *= 10;
}
return result;
factor 的最后一次乘法不能在有效程序中发生（有符号溢出未定义）。因此，对 result 的赋值也不会发生。由于无法在最后一次迭代之前进行分支，因此之前的迭代也不会发生。最终，正确的代码部分（即没有发生未定义的行为）是：
// nothing :(
任何有符号整数溢出都会导致未定义的行为，无论是否读取或可能读取溢出的值。
也许在您的用例中，您可以将第一个迭代从循环中移除，将这个
int result = 0;
int factor = 1;
for (int n = 0; n < 10; ++n) {
result += n + factor;
factor *= 10;
}
// factor "is" 10^10 > INT_MAX, UB
进入这个
int factor = 1;
int result = 0 + factor; // first iteration
for (int n = 1; n < 10; ++n) {
factor *= 10;
result += n + factor;
}
// factor is 10^9 < INT_MAX
启用优化后，编译器可能会将上面的第二个循环展开为一个条件跳转。
如果你能容忍循环中有一些额外的汇编指令，而不是
int factor = 1;
for (int j = 0; j < n; ++j) {
...
factor *= 10;
}
你可以写：
int factor = 0;
for (...) {
factor = 10 * factor + !factor;
...
}
避免最后的乘法。 !factor不会引入分支：
xor ebx, ebx
L1:
xor eax, eax
test ebx, ebx
lea edx, [rbx+rbx*4]
sete al
add ebp, 1
lea ebx, [rax+rdx*2]
mov edi, ebx
call consume(int)
cmp r12d, ebp
jne .L1
这个代码
int factor = 0;
for (...) {
factor = factor ? 10 * factor : 1;
...
}
优化后也会产生无分支装配：
mov ebx, 1
jmp .L1
.L2:
lea ebx, [rbx+rbx*4]
add ebx, ebx
.L1:
mov edi, ebx
add ebp, 1
call consume(int)
cmp r12d, ebp
jne .L2
（使用 GCC 8.3.0 编译 -O3）
考虑现实世界的优化器可能很有见地。循环展开是一种已知技术。循环展开的基本思想是
for (int i = 0; i != 3; ++i)
foo()
在幕后实施可能会更好，因为
foo()
foo()
foo()
这是简单的情况，具有固定的界限。但是现代编译器也可以做到这一点
对于变量边界：
for (int i = 0; i != N; ++i)
foo();
变成
__RELATIVE_JUMP(3-N)
foo();
foo();
foo();
显然这只有在编译器知道 N<=3 时才有效。这就是我们回到最初问题的地方：
int result = 0;
int factor = 1;
for (...) {
result = ...
factor *= 10;
}
return result;
因为编译器知道不会发生有符号溢出，它知道循环在32位架构上最多可以执行9次。 10^10 > 2^32。因此它可以进行 9 次迭代循环展开。 但预期的最大值是 10 次迭代！。
可能发生的情况是，您得到一个相对跳转至汇编指令 (9-N)，其中 N==10，因此偏移量为 -1，即跳转指令本身。哎呀。这是针对定义明确的 C++ 的完全有效的循环优化，但给出的示例变成了一个紧密的无限循环。
考虑函数：
unsigned mul_mod_65536(unsigned short a, unsigned short b)
{
return (a*b) & 0xFFFFu;
}
根据已发布的基本原理，标准的作者预计，如果在（例如）带有参数 0xC000 和 0xC000 的普通 32 位计算机上调用此函数，则提升 [=11= 的操作数] 到 signed int 会导致计算产生 -0x10000000，当转换为 unsigned 时会产生 0x90000000u——与他们让 unsigned short 提升为 [ 的答案相同=13=]。尽管如此，gcc 有时会以在发生溢出时表现荒谬的方式优化该函数。 任何输入组合可能导致溢出的代码都必须使用 -fwrapv 选项进行处理，除非允许故意畸形输入的创建者执行他们选择的任意代码是可以接受的。
这是UB；在 ISO C++ 术语中，对于 最终 命中 UB 的执行，整个程序的整个行为是完全未指定的。经典的例子就是 C++ 标准所关心的，它可以让恶魔从你的鼻子里飞出来。 （我建议不要使用真正有可能出现鼻腔恶魔的实现）。有关详细信息，请参阅其他答案。
编译器可以 "cause trouble" 在编译时找到他们可以看到的执行路径，从而导致编译时可见的 UB，例如假设这些基本块永远不会到达。
另请参阅 What Every C Programmer Should Know About Undefined Behavior（LLVM 博客）。正如那里所解释的那样，有符号溢出 UB 让编译器证明 for(... i <= n ...) 循环不是无限循环，即使对于未知的 n 也是如此。它还允许它们 "promote" int 循环计数器指针宽度而不是重做符号扩展。 （因此，在这种情况下，UB 的结果可能是访问数组的低 64k 或 4G 元素之外，如果您期望将 i 签名包装到其值范围内。）
在某些情况下，编译器会发出一条非法指令，如 x86 ud2 用于一个块，该块如果被执行，可证明会导致 UB。 （请注意，一个函数可能 not 永远不会被调用，所以编译器通常不能发狂并破坏其他函数，甚至不能通过一个不命中 UB 的函数的可能路径。即它编译的机器代码必须仍然适用于所有不导致 UB 的输入。）
可能最有效的解决方案是手动剥离最后一次迭代，从而避免不需要的 factor*=10。
int result = 0;
int factor = 1;
for (... i < n-1) { // stop 1 iteration early
result = ...
factor *= 10;
}
result = ... // another copy of the loop body, using the last factor
// factor *= 10; // and optimize away this dead operation.
return result;
或者如果循环体很大，考虑简单地使用无符号类型 factor。 然后你可以让无符号乘法溢出，它会很好-定义为 2 的某个幂（无符号类型中的值位数）。
即使您将它与 有符号类型一起使用也很好，尤其是当您的无符号->有符号转换永远不会溢出时。
无符号和有符号 2 的补码之间的转换是免费的（所有值的位模式相同）； C++ 标准指定的 int -> unsigned 的模换行简化为仅使用相同的位模式，这与 one's complement 或 sign/magnitude.
不同
而 unsigned->signed 同样微不足道，尽管它是为大于 INT_MAX 的值而定义的实现。如果您没有使用 上次迭代的巨大无符号结果，则无需担心。但如果你是，请将 Is conversion from unsigned to signed undefined?. The value-doesn't-fit case is implementation-defined, which means that an implementation must pick some behaviour; sane ones just truncate (if necessary) the unsigned bit pattern and use it as signed, because that works for in-range values the same way with no extra work. And it's definitely not UB. So big unsigned values can become negative signed integers. e.g. after int x = u; gcc and clang don't optimize away x>=0 视为始终为真，即使没有 -fwrapv，因为它们定义了行为。
您没有显示 for 语句括号中的内容，但我假设它是这样的：
for (int n = 0; n < 10; ++n) {
result = ...
factor *= 10;
}
您可以简单地将计数器增量和循环终止检查移动到正文中：
for (int n = 0; ; ) {
result = ...
if (++n >= 10) break;
factor *= 10;
}
循环中的汇编指令数将保持不变。
灵感来自 Andrei Alexandrescu 的演讲 "Speed Is Found In The Minds of People"。
为什么不是这个：
int result = 0;
int factor = 10;
for (...) {
factor *= 10;
result = ...
}
return result;
未定义行为有很多不同的面孔，可接受的取决于用法。
tight inner-loop that consumes a large chunk of the total CPU time in a real-time graphics application
就其本身而言，这有点不寻常，但不管怎样......如果确实如此，那么 UB 很可能在领域内 "allowable, acceptable"。图形编程因黑客和丑陋的东西而臭名昭著。只要它 "works" 并且产生一帧的时间不超过 16.6ms，通常，没人在乎。但是，请注意调用 UB 的含义。
首先是标准。从这个角度来看，没有什么可讨论的，也没有办法证明，你的代码根本就是无效的。没有 ifs 或 whens，它只是不是有效代码。从你的角度来看，你也可以说这是中指，而且 95-99% 的时间你都可以去。
接下来是硬件方面。在一些 不常见的、奇怪的 架构中，这是一个问题。我说 "uncommon, weird" 因为在 一个 架构上占所有计算机的 80%（或者 两个 架构一起构成了所有计算机的 95%）溢出是硬件级别的 "yeah, whatever, don't care" 事情。你确实得到了一个垃圾（尽管仍然是可预测的）结果，但没有坏事发生。
那是不是每个体系结构的情况，你很可能会在溢出时遇到陷阱（尽管看到你如何谈论图形应用程序，在这种奇怪的体系结构上的机会相当小的）。便携性是个问题吗？如果是，您可能想弃权。
最后，是compiler/optimizer方面。溢出未定义的原因之一是简单地将其保留在以前最容易处理硬件的地方。但另一个原因是，例如x+1 保证 总是大于 x，compiler/optimizer 可以利用这一知识。现在，对于前面提到的情况，确实知道编译器会以这种方式操作并简单地删除完整的块（几年前存在 Linux 漏洞，它基于编译器已经删除了一些验证代码，因为就是这个）。
对于你的情况，我会严重怀疑编译器是否做了一些特殊的、奇怪的优化。然而，你懂什么，我懂什么。如有疑问，尝试一下。如果有效，你就可以开始了。
（最后，当然还有代码审计，如果你运气不好，你可能不得不浪费时间与审计员讨论这个问题。）
我想知道如何使用如下代码
int result = 0;
int factor = 1;
for (...) {
result = ...
factor *= 10;
}
return result;
如果循环迭代 n 次，则 factor 正好乘以 10 次 n 次。但是，factor 仅在乘以 10 总共 n-1 次后才被使用。如果我们假设 factor 除了在循环的最后一次迭代之外永远不会溢出，但可能会在循环的最后一次迭代时溢出，那么这样的代码应该是可以接受的吗？在这种情况下，factor 的值将在溢出发生后被证明永远不会被使用。
我正在争论是否应该接受这样的代码。可以将乘法放在 if 语句中，并且在循环可能溢出时不在循环的最后一次迭代中执行乘法。缺点是它会使代码混乱并添加一个不必要的分支，需要检查所有先前的循环迭代。我还可以少迭代一次循环并在循环后复制一次循环体，同样，这会使代码复杂化。
有问题的实际代码用在一个紧密的内部循环中，在实时图形应用程序中消耗了总 CPU 时间的很大一部分。
int 溢出的行为未定义。
如果在循环体之外读到factor也没关系；如果到那时它已经溢出，那么你的代码在之前、之后以及有点自相矛盾的行为是未定义的。
保留此代码可能会出现的一个问题是编译器在优化方面变得越来越积极。特别是他们正在养成一种习惯，他们假设未定义的行为永远不会发生。为此，他们可能会完全删除 for 循环。
你不能为 factor 使用 unsigned 类型吗？尽管那样你需要担心在包含这两个的表达式中 int 到 unsigned 的意外转换？
编译器假定有效的 C++ 程序不包含 UB。考虑例如：
if (x == nullptr) {
*x = 3;
} else {
*x = 5;
}
If x == nullptr 然后取消引用它并赋值是 UB。因此，这可以在有效程序中结束的唯一方法是 x == nullptr 永远不会产生 true 并且编译器可以假设在 as if 规则下，以上等同于：
*x = 5;
现在在您的代码中
int result = 0;
int factor = 1;
for (...) { // Loop until factor overflows but not more
result = ...
factor *= 10;
}
return result;
factor 的最后一次乘法不能在有效程序中发生（有符号溢出未定义）。因此，对 result 的赋值也不会发生。由于无法在最后一次迭代之前进行分支，因此之前的迭代也不会发生。最终，正确的代码部分（即没有发生未定义的行为）是：
// nothing :(
任何有符号整数溢出都会导致未定义的行为，无论是否读取或可能读取溢出的值。
也许在您的用例中，您可以将第一个迭代从循环中移除，将这个
int result = 0;
int factor = 1;
for (int n = 0; n < 10; ++n) {
result += n + factor;
factor *= 10;
}
// factor "is" 10^10 > INT_MAX, UB
进入这个
int factor = 1;
int result = 0 + factor; // first iteration
for (int n = 1; n < 10; ++n) {
factor *= 10;
result += n + factor;
}
// factor is 10^9 < INT_MAX
启用优化后，编译器可能会将上面的第二个循环展开为一个条件跳转。
如果你能容忍循环中有一些额外的汇编指令，而不是
int factor = 1;
for (int j = 0; j < n; ++j) {
...
factor *= 10;
}
你可以写：
int factor = 0;
for (...) {
factor = 10 * factor + !factor;
...
}
避免最后的乘法。 !factor不会引入分支：
xor ebx, ebx
L1:
xor eax, eax
test ebx, ebx
lea edx, [rbx+rbx*4]
sete al
add ebp, 1
lea ebx, [rax+rdx*2]
mov edi, ebx
call consume(int)
cmp r12d, ebp
jne .L1
这个代码
int factor = 0;
for (...) {
factor = factor ? 10 * factor : 1;
...
}
优化后也会产生无分支装配：
mov ebx, 1
jmp .L1
.L2:
lea ebx, [rbx+rbx*4]
add ebx, ebx
.L1:
mov edi, ebx
add ebp, 1
call consume(int)
cmp r12d, ebp
jne .L2
（使用 GCC 8.3.0 编译 -O3）
考虑现实世界的优化器可能很有见地。循环展开是一种已知技术。循环展开的基本思想是
for (int i = 0; i != 3; ++i)
foo()
在幕后实施可能会更好，因为
foo()
foo()
foo()
这是简单的情况，具有固定的界限。但是现代编译器也可以做到这一点 对于变量边界：
for (int i = 0; i != N; ++i)
foo();
变成
__RELATIVE_JUMP(3-N)
foo();
foo();
foo();
显然这只有在编译器知道 N<=3 时才有效。这就是我们回到最初问题的地方：
int result = 0;
int factor = 1;
for (...) {
result = ...
factor *= 10;
}
return result;
因为编译器知道不会发生有符号溢出，它知道循环在32位架构上最多可以执行9次。 10^10 > 2^32。因此它可以进行 9 次迭代循环展开。 但预期的最大值是 10 次迭代！。
可能发生的情况是，您得到一个相对跳转至汇编指令 (9-N)，其中 N==10，因此偏移量为 -1，即跳转指令本身。哎呀。这是针对定义明确的 C++ 的完全有效的循环优化，但给出的示例变成了一个紧密的无限循环。
考虑函数：
unsigned mul_mod_65536(unsigned short a, unsigned short b)
{
return (a*b) & 0xFFFFu;
}
根据已发布的基本原理，标准的作者预计，如果在（例如）带有参数 0xC000 和 0xC000 的普通 32 位计算机上调用此函数，则提升 [=11= 的操作数] 到 signed int 会导致计算产生 -0x10000000，当转换为 unsigned 时会产生 0x90000000u——与他们让 unsigned short 提升为 [ 的答案相同=13=]。尽管如此，gcc 有时会以在发生溢出时表现荒谬的方式优化该函数。 任何输入组合可能导致溢出的代码都必须使用 -fwrapv 选项进行处理，除非允许故意畸形输入的创建者执行他们选择的任意代码是可以接受的。
这是UB；在 ISO C++ 术语中，对于 最终 命中 UB 的执行，整个程序的整个行为是完全未指定的。经典的例子就是 C++ 标准所关心的，它可以让恶魔从你的鼻子里飞出来。 （我建议不要使用真正有可能出现鼻腔恶魔的实现）。有关详细信息，请参阅其他答案。
编译器可以 "cause trouble" 在编译时找到他们可以看到的执行路径，从而导致编译时可见的 UB，例如假设这些基本块永远不会到达。
另请参阅 What Every C Programmer Should Know About Undefined Behavior（LLVM 博客）。正如那里所解释的那样，有符号溢出 UB 让编译器证明 for(... i <= n ...) 循环不是无限循环，即使对于未知的 n 也是如此。它还允许它们 "promote" int 循环计数器指针宽度而不是重做符号扩展。 （因此，在这种情况下，UB 的结果可能是访问数组的低 64k 或 4G 元素之外，如果您期望将 i 签名包装到其值范围内。）
在某些情况下，编译器会发出一条非法指令，如 x86 ud2 用于一个块，该块如果被执行，可证明会导致 UB。 （请注意，一个函数可能 not 永远不会被调用，所以编译器通常不能发狂并破坏其他函数，甚至不能通过一个不命中 UB 的函数的可能路径。即它编译的机器代码必须仍然适用于所有不导致 UB 的输入。）
可能最有效的解决方案是手动剥离最后一次迭代，从而避免不需要的 factor*=10。
int result = 0;
int factor = 1;
for (... i < n-1) { // stop 1 iteration early
result = ...
factor *= 10;
}
result = ... // another copy of the loop body, using the last factor
// factor *= 10; // and optimize away this dead operation.
return result;
或者如果循环体很大，考虑简单地使用无符号类型 factor。 然后你可以让无符号乘法溢出，它会很好-定义为 2 的某个幂（无符号类型中的值位数）。
即使您将它与 有符号类型一起使用也很好，尤其是当您的无符号->有符号转换永远不会溢出时。
无符号和有符号 2 的补码之间的转换是免费的（所有值的位模式相同）； C++ 标准指定的 int -> unsigned 的模换行简化为仅使用相同的位模式，这与 one's complement 或 sign/magnitude.
不同而 unsigned->signed 同样微不足道，尽管它是为大于 INT_MAX 的值而定义的实现。如果您没有使用 上次迭代的巨大无符号结果，则无需担心。但如果你是，请将 Is conversion from unsigned to signed undefined?. The value-doesn't-fit case is implementation-defined, which means that an implementation must pick some behaviour; sane ones just truncate (if necessary) the unsigned bit pattern and use it as signed, because that works for in-range values the same way with no extra work. And it's definitely not UB. So big unsigned values can become negative signed integers. e.g. after int x = u; gcc and clang don't optimize away x>=0 视为始终为真，即使没有 -fwrapv，因为它们定义了行为。
您没有显示 for 语句括号中的内容，但我假设它是这样的：
for (int n = 0; n < 10; ++n) {
result = ...
factor *= 10;
}
您可以简单地将计数器增量和循环终止检查移动到正文中：
for (int n = 0; ; ) {
result = ...
if (++n >= 10) break;
factor *= 10;
}
循环中的汇编指令数将保持不变。
灵感来自 Andrei Alexandrescu 的演讲 "Speed Is Found In The Minds of People"。
为什么不是这个：
int result = 0;
int factor = 10;
for (...) {
factor *= 10;
result = ...
}
return result;
未定义行为有很多不同的面孔，可接受的取决于用法。
tight inner-loop that consumes a large chunk of the total CPU time in a real-time graphics application
就其本身而言，这有点不寻常，但不管怎样......如果确实如此，那么 UB 很可能在领域内 "allowable, acceptable"。图形编程因黑客和丑陋的东西而臭名昭著。只要它 "works" 并且产生一帧的时间不超过 16.6ms，通常，没人在乎。但是，请注意调用 UB 的含义。
首先是标准。从这个角度来看，没有什么可讨论的，也没有办法证明，你的代码根本就是无效的。没有 ifs 或 whens，它只是不是有效代码。从你的角度来看，你也可以说这是中指，而且 95-99% 的时间你都可以去。
接下来是硬件方面。在一些 不常见的、奇怪的 架构中，这是一个问题。我说 "uncommon, weird" 因为在 一个 架构上占所有计算机的 80%（或者 两个 架构一起构成了所有计算机的 95%）溢出是硬件级别的 "yeah, whatever, don't care" 事情。你确实得到了一个垃圾（尽管仍然是可预测的）结果，但没有坏事发生。
那是不是每个体系结构的情况，你很可能会在溢出时遇到陷阱（尽管看到你如何谈论图形应用程序，在这种奇怪的体系结构上的机会相当小的）。便携性是个问题吗？如果是，您可能想弃权。
最后，是compiler/optimizer方面。溢出未定义的原因之一是简单地将其保留在以前最容易处理硬件的地方。但另一个原因是，例如x+1 保证 总是大于 x，compiler/optimizer 可以利用这一知识。现在，对于前面提到的情况，确实知道编译器会以这种方式操作并简单地删除完整的块（几年前存在 Linux 漏洞，它基于编译器已经删除了一些验证代码，因为就是这个）。
对于你的情况，我会严重怀疑编译器是否做了一些特殊的、奇怪的优化。然而，你懂什么，我懂什么。如有疑问，尝试一下。如果有效，你就可以开始了。
（最后，当然还有代码审计，如果你运气不好，你可能不得不浪费时间与审计员讨论这个问题。）