网志

了解和防止溢出(昨晚我太多添加了)

杰森·萨克斯(Jason Sachs) 2013年12月4日

感恩节快乐!也许吃新鲜火鸡的记忆是新鲜的。如果是这样,那么这是一个讨论的好时机 溢出 .

在浮点运算的世界中,可能会发生溢出,但并不是特别常见。当数字太大时,您可以得到它。 IEEE双精度浮点数 支持范围小于21024,而且如果超出此范围,您就会遇到问题:

for k in [10, 100, 1000, 1020, 1023, 1023.9, 1023.9999, 1024]:
    try:
        print "2^%.4f = %g" % (k, 2.0 ** k)
    except OverflowError, e:
        print "2^%.4f ---> %s" % (k,e)
2^10.0000 = 1024
2^100.0000 = 1.26765e+30
2^1000.0000 = 1.07151e+301
2^1020.0000 = 1.12356e+307
2^1023.0000 = 8.98847e+307
2^1023.9000 = 1.67731e+308
2^1023.9999 = 1.79757e+308
2^1024.0000 ---> (34, 'Result too large')

21024 真的是 大数目。您可能永远都不需要像2这样的数字1024 除非您正在与 组合学。只是为了比较,以下是一些物理量中的数字范围:

本文以PDF格式提供,便于打印

因此,双精度数字应该很安全。

单精度浮点数 上升到2以下128 并且在很大的物理计算中很容易溢出。您更有可能因为精度而不是范围而不使用它们。

嵌入式系统世界中的那些人通常没有使用浮点计算的奢侈。无论是在CPU执行时间还是在$$$方面,它都需要额外花费。我们辞职使用整数算法。 (我们中有些人实际上喜欢它!)

因此,本文的其余部分是关于整数算术中的溢出。接下来的事情可能会让您感到惊讶。

溢出源

通常的嫌疑人:加法和乘法

什么会导致整数数学溢出?通常的怀疑是加法和乘法:

import numpy as np

a = np.int16(32767)
b = np.int16(2)
print "32767 + 2 = %s" % (a+b)
print "32767 * 2 = %s" % (a*b)
32767 + 2 = -32767
32767 * 2 = -2
-c:3: RuntimeWarning:  溢出  encountered in short_scalars
-c:4: RuntimeWarning:  溢出  encountered in short_scalars

每个整数格式都有一个可表示的范围:

  • 有符号16位整数支持范围[-32768,32767]
  • 无符号16位整数支持范围[0,65535]
  • 有符号的32位整数支持范围[-2147483648,2147483647]
  • 无符号的32位整数支持范围[0,4294967295]

而且,如果您超出此范围(甚至是暂时),则需要非常小心。大多数环境可以正常处理溢出,并为您提供“环绕”或“模”的行为(在带符号的16位环境中为32767 + 1 = -32768),超出范围的进位将消失,而您处于低位与确切结果相对应的位。

如果您使用的C编译器符合 C99标准,您可能会惊讶地发现无符号整数数学在溢出条件下保证具有模运算,但是 带符号整数数学的溢出行为未定义.

要成为 语言律师,相关 C99中的内容 是:

第6.5节第5项:

如果 特殊情况 在对表达式求值期间发生(即,如果未在数学上定义结果或该结果不在其类型的可表示值范围内),则行为不确定。

第6.2.5节第9项:

涉及无符号操作数的计算永远不会溢出,因为无法用所得的无符号整数类型表示的结果的模数要比该所得的类型可以表示的最大值大一模。

(实际上,诸如 海湾合作委员会 和clang倾向于在基本算术计算中使用模态行为,但是要小心,因为 有时编译器优化会错误地处理比较或条件表达式 即使基本算术是“正确的”。这种行为的症状很难识别。的 LLVM网站 has some explanation of this, along with other bugbears of undefined behavior. If 您 want to be safe, use 的 -fwrapv compiler flag, which both 海湾合作委员会 和 clang support; this guarantees modulo behavior with all aspects of signed arithmetic.)

在C标准中出现这种奇怪现象的历史原因是,在过去,一些处理器使用 补码 有符号数的表示形式,在这种情况下,有符号数和无符号数的算术略有不同。如今,二进制补码已成为常态,当使用基本字长作为结果时,有符号和无符号的加法,减法和乘法实现都是相同的。但是,无论好坏,C的主要原理之一是允许特定于机器的行为来维持有效的代码,因此,编写该标准时并不保证有符号算术溢出的结果。另一方面,诸如Java之类的语言具有与机器无关的算术定义。 Java中的任何算术运算都将为您提供相同的答案,无论您在哪个处理器上运行它。这种保证的代价是在某些处理器上,将需要额外的说明。

By 的 way, if 您 're using C for integer math, be sure to #include <stdint.h>使用它包含的typedef, such as int16_t, uint16_t, int32_t, 和 uint32_t. These are portable, whereas 的 number of bits in a short or an int or a long may vary with processor architecture.

如果使用MATLAB的定点功能,请注意整数溢出的默认行为是在整数范围的极限处饱和。这样可以避免某些溢出问题,但如果您习惯于使用提供环绕语义的语言,则可能无法获得预期的结果。

防止溢出

Just because we can use -fwrapv in 海湾合作委员会 or clang, 和 guarantee wraparound behavior, 做 esn't make it 的 correct behavior for an application program.

如果我正在控制阀门,并且希望增加输出,并且将1一直添加到过程控制变量中,则得到32765、32766、32767,-32768,-32767等,这将导致跳跃不连续性不好。防止这种情况的唯一与机器无关的方法是避免溢出。一种方法是向上转换为较大的类型,检查是否有溢出,并使结果饱和:

#include <stdint.h>

int16_t add_and_saturate(int16_t x, int16_t y)
{
    int32_t z = (int32_t)x + y;
    if (z > INT16_MAX)
    {
        z = INT16_MAX;
    }
    else if (z < INT16_MIN)
    {
        z = INT16_MIN;
    }
    return (int16_t)z;
}

您也可以执行以下操作以将其保留在16位类型的范围内,但这样做有些棘手,需要更多操作,并且我不确定100%正确的代码:

#include <stdint.h>

int16_t add_and_saturate(int16_t x, int16_t y)
{
   int16_t z = x+y;
   if ((y > 0) && (x > (INT16_MAX - y)))
   {
       z = INT16_MAX;
   }
   else if ((y < 0) && (x < (INT16_MIN - y)))
   {
       z = INT16_MIN;
   }
   return z;
}

处理乘法是相似的,并且实际上仅在使用类型扩展方法时才是实际的。

减法?

下面的C代码中有一个错误;你知道为什么吗?

int16_t calcPI(int16_t command, int16_t measurement)
{
   int16_t error = command - measurement;
   /* other stuff */
}

The problem is with 的 减法 . If command = 32767measurement = -32768, 的 "real" value of error is 65535. And if command = -32768measurement = 32767, 的 n 的 "real" value of 的 error is -65535. Just as with 加成 , in 减法 的 result of operating on 二 k-bit numbers is a (k+1)-bit result. There are a couple of ways of dealing with this to avoid incorrect results.

首先,我们可以使用32位中间计算:

int32_t error = (int32_t)command - measurement;

这样做的缺点是,我们添加的操作越多,输出值的范围就越大。但是只要我们在中间计算中不会遇到溢出,就可以了。

Second, we can saturate 的 error to 的 range of an int16_t, so that 的 limits are -32768 to +32767. This has 的 drawback that 的 re is no difference between cases at 的 edge of saturation 和 deep into saturation. (For example: command = 32767measurement = 0 gives error = 32767, but so 做 es measurement = -32768.) In reality we may want to maintain linearity throughout 的 whole range.

第三,我们可以修改正在执行的操作,以使结果在限制范围内:

int16_t error = ((int32_t)command - measurement) / 2;

这会降低净增益,但同时避免了溢出和饱和。

师?

除法是算术运算中的丑兽。幸运的是,溢出情况并不太复杂。

如果您在C语言中工作,则除法意味着将一个N位数字除以另一个N位数字,只有一个示例可能会导致溢出,我们将在稍后介绍。 (而且不是零除。如果不先排除d = 0的情况就对n / d进行除法,那么您应得到的一切都应得到。)

某些处理器具有内置的划分功能,并且编译器通过直接映射到处理器划分功能的“内建”或“内部”功能支持这些功能。在这里,您可以执行以下操作:将32位整数除以16位整数以产生16位结果,但是您需要确保避免将其除以会产生不适合的商的数字结果为16位。例如:180000/2 = 90000,并且90000超出了带符号或无符号的16位数字的范围。

转移?

Don't forget 您 r shift operators <<>>. These won't cause 溢出 , but in C, 做 n't forget 的 pesky undefined 和 implementation-specific behaviors. Here 的 relevant section from 的 C99标准 is section 6.5.7 paragraphs 3-5:

3对每个操作数执行整数提升。结果的类型是提升后的左操作数的类型。如果右操作数的值为负或大于或等于提升的左操作数的宽度,则行为是不确定的。

4 E1的结果<<E2是E1左移E2位的位置;空位用零填充。如果E1具有无符号类型,则结果的值为E1× 2E2,比结果类型可表示的最大值减少模一。如果E1具有带符号的类型和非负值,并且E1× 2E2 在结果类型中是可表示的,那么就是结果值;否则,行为是不确定的。

5 E1的结果>>E2是E1右移E2位的位置。如果E1具有无符号类型,或者E1具有带符号类型并且具有非负值,则结果的值是E1 / 2的商的整数部分 E2。如果E1具有带符号的类型和负值,则结果值是实现定义的。

That's right! If 您 have a signed integer E1 containing a negative number, 和 您 shift right, 的 results are implementation defined. The "sensible" thing to 做 is an arithmetic shift right, putting 1 bits into 的 most significant bits to handle sign-extension. But 的 C standard allows 的 compiler to produce a logical shift right, putting 0 bits into 的 most significant bits, 和 that's probably 不 what 您 wanted.

像Java和Javascript这样的最新语言为您提供 shift right operators: 的 regular >> operator for computing arithmetic shift right, 和 >>> operator for computing logical shift right to produce an unsigned binary integer with zeros shifted into 的 most significant bits.

是吗ew!

No, that's 不 it! What else is 的 re? Well, 的 re are 的 increment 和 decrement operators ++--, but with -fwrapv 的 y should work with wraparound semantics as expected.

The rest of 的 溢出 items fall into what might be called Pathological Cases. These all involve asymmetry between INT_MININT_MAX that causes unwanted aliasing.

我们之前讨论过除法,一个整数除法溢出是当您采用-32768并除以-1时。

# Let's divide -32768 / -1
a=np.int16(-32768)
b=np.int16(-1)
a/b
-32768

D'OH! We should have gotten +32768 but that just won't fit into a 16-bit signed integer, so it aliases to 的 int16_t bit-equivalent value -32768.

一元减会发生相同的事情:

# Let's negate -32768 
-a
-32768

然后,在同一条直线上存在定点乘法缺陷。假设您正在做Q15数学,其中整数表示形式为\(\ frac {k} {2 ^ {15}} \)。 C代码如下所示:

int16_t a = ...;
int16_t b = ...;
int16_t c = ((int32_t)a * b) >> 15;

是否可以正常工作而不会溢出?好吧,除了一个案例。 \(-32768 \ times -32768 = 2 ^ {30} \),如果我们将其右移15,则得到\(2 ^ {15} = 32768 \)。但是,在带符号的16位整数中,32768的别名为-32768。哎哟!

我们该如何处理?

Q15乘法

好吧,Q15乘法很难。如果你是 绝对确定 您将永远不会评估-32768×-32768,请继续使用原样的C代码。 PI控制回路就是一个例子,其中增益总是非负的。或者,如果您知道其中一个数字的范围不包括-32768,那么您就可以了。

另外,如果您愿意再增加一次班次权,则可以执行以下操作:

int16_t a = ...;
int16_t b = ...;
int16_t c = ((int32_t)a * b) >> 16;

在嵌入式系统中,通常将16位右移操作的速度比将15个指令移位1个指令周期要快​​,因为它通常映射为汇编中的“抓住高位字”操作,通常在存储内存时可以免费获得。如果a和b是Q15定点整数,则此运算表示\(a \ times b \ times \ frac {1} {2} \),或者如果值之一是Q15并且另一个是Q16。

除此之外,您还需要某种方式使中间产品饱和,这样可以安全地向右移动:

int16_t a = ...;
int16_t b = ...;
int16_t c = sat30((int32_t)a * b) >> 15;

where sat30(x) limits 的 results so that 的 y are within 的 range \( -2^{30} + k_1 \) to \( 2^{30} - 1 - k_2 \), where k1 和k 2 are any numbers between 0 和 32767. (Why this ambiguity? Because 的 least significant 15 bits 做 n't matter, 和 certain processors may have quirks that allow 您 to execute code faster by choosing different values of k. For example, 的 literal value of \( 2^{30} - 1 \) may 不 be possible to load in one instruction, whereas 的 literal value of \( 2^{30} - 32768 \) = 32767 << 15 may be possible to load in one instruction.)

一元减

一元减的情况有点类似。我们有几种选择:

如果我们完全确定输入不能为-32768,则可以保留原样。

否则,我们必须测试-32768并转换为+32767。

或者,在C中,我们可以使用 按位补运算符 ~, because ~x = -x-1 for signed integers: ~-32768 = 32767, ~0 = -1, ~-1 = 0, ~32767 = -32768. This adjustment by 1 for all inputs may 不 be acceptable in some applications, but in others it is fine, representing a small offset, 和 complement 操作 is often a fast single-instruction 操作 .

同样的想法也适用于绝对价值。代替

#define ABS(x) ((x) < 0 ? (-x) : (x))

我们可以使用按位补码运算符:

#define ABS_Q15(x) ((x) < 0 ? (~x) : (x))

另外,我们必须对-32768进行特殊测试。

Just a reminder: #define macros are invisible to 的 compiler (because 的 y happen in 的 preprocessor) 和 are also unsafe to use with arguments that have side effects e.g. ABS(++x) which would get incremented three times.

但是,等等,还有更多!

差点忘了一件事!到目前为止,我们讨论的所有内容都是一个单一的操作,其中包括关于灾难的告诫故事。

通过包含多个运算的复合计算,我们可以使用一件事:

如果您具有固定模数(环绕式)语义的固定位宽整数算术(有符号或无符号)复合计算,仅由这些操作组成

  • 加成
  • 减法
  • 乘法
  • 左移
  • 按位与
  • 按位或
  • 按位异或
  • 按位补码

(和 符号扩展名,右移或除法),并且满足以下条件:

  • 中间计算溢出
  • 中间计算不用于任何其他目的
  • 使用整数算术执行相同的复合计算,而没有位宽的限制,并且产生不会溢出的最终结果

然后发生了一件令人惊奇的事情,那就是固定位宽整数运算的最终结果仍然是正确的。实际上,如果我们 在中间结果上提供饱和算术,那么只要饱和激活,我们就可能得到不正确的最终结果。

这种情况听起来似乎是人为的和不可能的,但实际上并非如此,并且在多项式求值中表现出很多。这是由于 同余关系 我们从模块化算术中得到。 如果从上面的列表中对k位数字进行算术运算会产生一个k位结果,该结果可能会出现环绕(模)语义,则它会产生与真实结果一致的结果,取模\(2 ^ k \ )。

让我们来看一个更具体的情况。假设我们正在计算\(y = ax ^ 2 + bx + c \),其中a,b,c和x是带符号的4.12定点数,而a,b和c是常数。这等效于编写\(Y = \ frac {AX ^ 2} {2 ^ {24}} + \ frac {BX} {2 ^ {12}} + C = \ frac {AX ^ 2 + 2 ^ {12 } BX + 2 ^ {24} C} {2 ^ {24}} \),其中A,B,C和X是16位数字。还假设a,b和c的值使得对于在有效4.12范围内的x的任何值(即\(-(-8.0 \ leq x<8.0 \)),结果y也在该范围内。然后,中间计算是否溢出无关紧要,您仍将获得正确的最终结果。

好的,那还是有点抽象。假设我们正在计算\(y = f(x)= \ frac {3} {16} x ^ 2-\ frac {7} {16} x-\ frac {121} {16} \)。

对于\(| x | \ leq 8.0 \),\(f(x)\)的最小值为\(-8 + \ frac {35} {192} \)(在\(x = \ frac {4779附近} {4096} \))和最大值(\(7.9375 = 8-\ frac {1} {16} = 127/16 \)(在\(x = -8.0 \)),所以\(f(x )\)不会产生最终结果溢出。

现在,我们使用两个不同的ALU计算\(x = -8.0 = \ frac {-32768} {4096} \)的f(x)。 ALU1非常狭窄,具有16位寄存器和32位乘积寄存器,而ALU2使用32位寄存器和64位乘积寄存器:

操作 ALU1ALU2
 
x
-32768 -8.0第二季度 -32768 -8.0第二季度
1.
t1p = x * x
1073741824 64.0Q24 1073741824 64.0Q24
2.
t2 = truncate(t1p,16)
16384 64.0Q8 16384 64.0Q8
3.
t3 = 3 * t2
-16384 -64.0Q8 = -4.0Q12 [溢出!] 49152 192.0Q8 = 12.0Q12
4.
t4p = -7 * x
229376 56.0Q12 = 3.5Q16 229376 56.0Q12 = 3.5Q16
5.
t5 = truncate(t4p,4)
14336 3.5Q12 14336 3.5Q12
6.
t6 = t3 + t5
-2048 -0.5Q12 63488 2012年第15.5季度
7.
y = t6 - 30976
32512 7.9375Q12 32512 7.9375Q12

这里有一些评论:

  • 带有“ p”后缀的临时结果是产品注册结果;其余结果为常规长度。

  • 神秘数字-30976只是\(c = \ frac {-30976} {4096} = \ frac {-121} {16} \)的Q12表示。

  • truncate(x,m), for an ALU with k-bit registers 和 a p-bit product register, is what we get when we select 的 k bits starting with bit #m: in other words, drop 的 m least significant bits of x, 和 n take 的 k least significant bits of 的 result, where k is 的 bit length of 的 ALU register. For an ALU with 16-bit registers, truncate(x,m) = (int16_t)(x >> m) 和 for an ALU with 32-bit registers, truncate(x,m) = (int32_t)(x >> m). This 操作 做 es 不 introduce any sign-extension as long as k + m < p.

  • 请注意,除了第3步和第6步外,两个ALU的所有计算均相同:ALU1溢出,但ALU2不会溢出。最后两个结果收敛。

请注意,之前我从“安全”操作列表中排除了右移,并且我没有提到任何有关截断或使用两个k位数字产生2k位乘积的信息。在这里,我将不得不手挥手。

不安全的右移部分与符号扩展有关:我们假设我们根据存储的最高有效位知道数字的符号。如果可能出现溢出,那么我们就不能对数字的符号做任何假设。因此,如果您不对符号扩展进行符号签名,或者对符号扩展名不做任何事情,那么您将对2 ^ k取模来保持一致性。

另一方面,如果我们将两个k位数字相乘以生成2k位乘积,则在中间计算中使用它并不是一个固有的“安全”操作。让我们使用k = 16,其中a = 1 + 65536 * m和b = 1 + 65536 * n,其中m和n是我们并不真正关心的未知整数,因为我们需要保留中间结果是底部的16位,对吗?如果将a和b的实数值相乘,则得到(1 + 65536 *(m + n)+ 65536 * 65536 * m * n)。此结果的后32位为1 + 65536 *(m + n)。哦哦如果我们想要32位结果,我们确实必须知道更多位。如果我们只关心产品的低16位,那么我们得到1,就可以了。

So in this example we have to be careful; 的 "we 做 n't care if intermediate results 溢出 " rule 真 only applies to 步 s 3, 6 和 7 (y = (3*t2) + t5 - 30976) 和 rest of 的 步 s need to be analyzed more rigorously to ensure 的 re are no 溢出 s with 的 range of given inputs. For 的 加成 s/subtractions/multiplications that use fixed bit width, we can just 做 的 m without worrying about 溢出 , as long as we know 的 final result is going to end up within valid limits.

我希望有一种更简单的方法向初学者解释。我希望有经验的工程师可以采用一种更简便的方法来分析这些东西,因为很难做到严格并确保正确。也许某天某人会发明一种易于使用的“溢出演算”,在这里我们可以转动曲柄而不用思考,它会告诉我们在哪里可以遇到问题以及如何解决它们。在此之前,请保持警惕。

进一步阅读

犹他大学的John Regehr开设了一个非常有趣的博客,内容涉及嵌入式系统,静态分析和其他方面。他有几篇关于 C和C ++中未定义的行为.

他还是一篇有趣的文章的作者之一 “了解C / C ++中的整数溢出” 其中包含一系列发人深省的软件程序(包括PHP,SQLite,PostgreSQL,OpenSSL,Firefox,GCC,LLVM和Python),其中发现了潜在的整数溢出。

概要

  • 注意溢出!
  • 了解程序中算术运算的输入范围
  • Use compiler flags to ensure wraparound semantics (-fwrapv in clang 和 海湾合作委员会 )
  • 在适当的地方使用明确的饱和度
  • 当心涉及的病理病例 INT_MIN
  • 只要最终结果在范围内,复合整数算术计算就可以容忍中间结果中的溢出,并且中间计算是“安全列表”的一部分(请参见上面的详细讨论),并且适用于固定位长的操作数和结果。

希望大家感恩节快乐,并只记得 可以防止溢出!


©2013 Jason M. Sachs,保留所有权利。


杰森·萨克斯(Jason Sachs)上一篇文章:
   如何在不犯错误的情况下估算编码器速度:第二部分(跟踪环路和PLL)
杰森·萨克斯(Jason Sachs)下一篇文章:
   透过玻璃看效率

要发布对评论的回复,请单击每个评论所附的“回复”按钮。要发布新评论(而不是回复评论),请查看评论顶部的“写评论”标签。

注册后,您可以参加所有相关网站上的论坛,并获得所有pdf下载的访问权限。

注册

我同意 使用条款隐私政策.

试试我们偶尔但很受欢迎的时事通讯。非常容易退订。
或登录