# 2.3.5 补码乘法

范围在 -2^w-1 ≤ x, y ≤ 2^w-1 - 1 内的整数 x 和 y 可以被表示为 w 位的补码数字，但是它们的乘积 x · y 的取值范围为 -2^w-1 · (2^w-1 - 1) = -2^2w-2 + 2^w-1 到 -2^w-1 · -2^w-1 = 2^2w-2 之间。要想用补码来表示这个乘积，可能需要 2w 位。然而，C 语言中的有符号乘法是通过将 2w 位的乘积截断为 w 位来实现的。我们将这个数值表示为 x *^t_w y。将一个补码数截断为 w 位相当于先计算该值模 2^w，再把无符号数转换为补码，得到：

原理：补码乘法

对满足 TMin_w ≤ x, y ≤ TMax_w 的 x 和 y 有：

x *^t_w y = U2T_w((x · y) mod 2^w)　（2.17）

我们认为对于无符号和补码乘法来说，乘法运算的位级表示都是一样的，并用如下原理说明：

原理：无符号和补码乘法的位级等价性

给定长度为 w 的位向量 x⃗ 和 y⃗，用补码形式的位向量表示来定义整数 x 和 y：x = B2T_w(x⃗)，y = B2T_w(y⃗)。用无符号形式的位向量表示来定义非负整数 x' 和 y'：x' = B2U_w(x⃗)，y' = B2U_w(y⃗)。则

T2B_w(x *^t_w y) = U2B_w(x' *^u_w y')

推导：无符号和补码乘法的位级等价性

根据等式（2.6），我们有 x' = x + x_w-12^w 和 y' = y + y_w-12^w。计算这些值的乘积模 2^w 得到以下结果：

(x' · y') mod 2^w

= [(x + x_w-12^w) · (y + y_w-12^w)] mod 2^w

= [x · y + (x_w-1y + y_w-1x)2^w + x_w-1y_w-12^2w] mod 2^w

= (x · y) mod 2^w　（2.18）

由于模运算符，所有带有权重 2^w 和 2^2w 的项都丢掉了。根据等式（2.17），我们有 x *^t_w y = U2T_w((x · y) mod 2^w)。对等式两边应用操作 T2U_w 有：

T2U_w(x *^t_w y)

= T2U_w(U2T_w((x · y) mod 2^w))

= (x · y) mod 2^w

将上述结果与式（2.16）和式（2.18）结合起来得到

T2U_w(x *^t_w y)

= (x' · y') mod 2^w

= x' *^u_w y'

然后对这个等式的两边应用 U2B_w，得到

U2B_w(T2U_w(x *^t_w y))

= T2B_w(x *^t_w y)

= U2B_w(x' *^u_w y')

■

作为说明，图 2-27 给出了不同 3 位数字的乘法结果。对于每一对位级运算数，我们执行无符号和补码乘法，得到 6 位的乘积，然后再把这些乘积截断到 3 位。无符号的截断后的乘积总是等于 x · y mod 8。虽然无符号和补码两种乘法乘积的 6 位表示不同，但是截断后的乘积的位级表示都相同。

模式	x	y	x · y	截断的 x · y
无符号	5 [101]	3 [011]	15 [001111]	7 [111]
补码	-3 [101]	3 [011]	-9 [110111]	-1 [111]
无符号	4 [100]	7 [111]	28 [011100]	4 [100]
补码	-4 [100]	-1 [111]	4 [000100]	-4 [100]
无符号	3 [011]	3 [011]	9 [001001]	1 [001]
补码	3 [011]	3 [011]	9 [001001]	1 [001]

图 2-27　3 位无符号和补码乘法示例。虽然完整的乘积的位级表示可能会不同，但是截断后乘积的位级表示是相同的

练习题 2.34 按照图 2-27 的风格填写下表，说明不同的 3 位数字乘法的结果。

模式	x	y
无符号	[100]	[101]
补码	[100]	[101]
无符号	[010]	[111]
补码	[010]	[111]
无符号	[110]	[110]
补码	[110]	[110]

练习题 2.35 给你一个任务，开发函数 tmult_ok 的代码，该函数会判断两个参数相乘是否会产生溢出。下面是你的解决方案：

/* Determine whether arguments can be multiplied without overflow */
int tmult_ok(int x, int y) {
    int p = x*y;
    /* Either x is zero, or dividing p by x gives y */
    return !x || p/x == y;
}

你用 x 和 y 的很多值来测试这段代码，似乎都工作正常。你的同事挑战你，说：“如果我不能用减法来检验加法是否溢出（参见练习题 2.31），那么你怎么能用除法来检验乘法是否溢出呢？”

按照下面的思路，用数学推导来证明你的方法是对的。首先，证明 x = 0 的情况是正确的。另外，考虑 w 位数字 x（x ≠ 0）、y、p 和 q，这里 p 是 x 和 y 补码乘法的结果，而 q 是 p 除以 x 的结果。

说明 x 和 y 的整数乘积 x · y，可以写成这样的形式：x · y = p + t2^w，其中，t ≠ 0 当且仅当 p 的计算溢出。
说明 p 可以写成这样的形式：p = x · q + r，其中 |r| < |x|。
说明 q = y 当且仅当 r = t = 0。

练习题 2.36 对于数据类型 int 为 32 位的情况，设计一个版本的 tmult_ok 函数（练习题 2.35），使用 64 位精度的数据类型 int64_t，而不使用除法。

旁注：XDR 库中的安全漏洞

2002 年，人们发现 Sun Microsystems 公司提供的实现 XDR 库的代码有安全漏洞，XDR 库是一个广泛使用的、程序间共享数据结构的工具，造成这个安全漏洞的原因是程序会在毫无察觉的情况下产生乘法溢出。

包含安全漏洞的代码与下面所示类似：
/* Illustration of code vulnerability similar to that found in
 * Sun's XDR library.
 */
void* copy_elements(void *ele_src[], int ele_cnt, size_t ele_size) {
    /*
     * Allocate buffer for ele_cnt objects, each of ele_size bytes
     * and copy from locations designated by ele_src
     */
    void *result = malloc(ele_cnt * ele_size);
    if (result == NULL)
        /* malloc failed */
        return NULL;
    void *next = result;
    int i;
    for (i = 0; i < ele_cnt; i++) {
        /* Copy object i to destination */
        memcpy(next, ele_src[i], ele_size);
        /* Move pointer to next memory region */
        next += ele_size;
    }
    return result;
}
函数 copy_elements 设计用来将 ele_cnt 个数据结构复制到第 9 行的函数分配的缓冲区中，每个数据结构包含 ele_size 个字节。需要的字节数是通过计算 ele_cnt * ele_size 得到的。

想象一下，一个怀有恶意的程序员在被编译为 32 位的程序中用参数 ele_cnt 等于 1 048 577（2²⁰ + 1）、ele_size 等于 4096（2¹²）来调用这个函数。然后第 9 行上的乘法会溢出，导致只会分配 4096 个字节，而不是装下这些数据所需要的 4 294 971 392 个字节。从第 15 行开始的循环会试图复制所有的字节，超越已分配的缓冲区的界限，因而破坏了其他的数据结构。这会导致程序崩溃或者行为异常。

几乎每个操作系统都使用了这段 Sun 的代码，像 Internet Explorer 和 Kerberos 验证系统这样使用广泛的程序都用到了它。计算机紧急响应组（Computer Emergency Response Team，CERT），由卡内基-梅隆软件工程协会（Carnegie Mellon Software Engineering Institute）运作的一个追踪安全漏洞或失效的组织，发布了建议“CA-2002-25”，于是许多公司急忙对它们的代码打补丁。幸运的是，还没有由于这个漏洞引起的安全失效的报告。

库函数 calloc 的实现中存在着类似的漏洞。这些已经被修补过了。遗憾的是，许多程序员调用分配函数（如 malloc）时，使用算术表达式作为参数，并且不对这些表达式进行溢出检查。编写 calloc 的可靠版本留作一道练习题（家庭作业 2.76）。

练习题 2.37 现在你有一个任务，当数据类型 int 和 size_t 都是 32 位的，修补上述旁注给出的 XDR 代码中的漏洞。你决定将待分配字节数设置为数据类型 uint64_t，来消除乘法溢出的可能性。你把原来对 malloc 函数的调用（第 9 行）替换如下：

uint64_t asize =
    ele_cnt * (uint64_t) ele_size;
void *result = malloc(asize);

提醒一下，malloc 的参数类型是 size_t。

A. 这段代码对原始的代码有了哪些改进？

B. 你该如何修改代码来消除这个漏洞？

← 2.3.4 无符号乘法 2.3.6 乘以常数 →