文章目录
- 线索栏
- 笔记栏
-
- 1. 补码乘法定义
- 2. 位级等价性原理与推导
-
- 1）原理陈述
- 2）推导概要
- 3. 实例验证：3位乘法表（图2-27）
-
- 练习题2.34
- 4. 补码乘法溢出检测 (tmult_ok)
-
- 1）原理
- 2）检测方法（练习题2.35）
- 3）64位精度实现（练习题2.36）
- 5. 现实安全漏洞：Sun XDR库
-
- 1）漏洞代码
- 2）根本原因
- 3）修复（练习题2.37）
- 总结栏
线索栏
x
∗
w
t
y
x∗_w^ty
x∗wty的数学定义（公式2.17）是什么？
笔记栏
1. 补码乘法定义
（1）数学定义：对于
T
M
i
n
w
≤
x
,
y
≤
T
M
a
x
w
TMin_w≤x,y≤TMax_w
TMinw≤x,y≤TMaxw，w位补码乘法定义为将完整乘积截断（取模）为w位，再将结果解释为补码：
x
∗
w
t
y
=
U
2
T
w
(
(
x
⋅
y
)
m
o
d
2
w
)
x∗_w^t y=U2T_w((x⋅y)mod2^w)
x∗wty=U2Tw((x⋅y)mod2w)(2.17) （2）物理意义：硬件执行与无符号乘法相同的位级运算（计算2w位乘积后截取低w位），然后将该w位结果按补码规则解读。
2. 位级等价性原理与推导
1）原理陈述
给定相同的位向量
x
⃗
\\vec{x}
x
和
y
⃗
\\vec{y}
y
，令其补码解释的整数为
x
x
x,
y
y
y，无符号解释的整数为
x
′
x′
x′,
y
′
y′
y′。则它们截断后的乘积满足位级等价：
T
2
B
w
(
x
∗
w
t
y
)
=
U
2
B
w
(
x
′
∗
w
u
y
′
)
T2B_w(x∗_w^ty)=U2B_w(x′∗_w^uy′)
T2Bw(x∗wty)=U2Bw(x′∗wuy′)即，无论是先解释为补码相乘再截断取位，还是先解释为无符号相乘再截断取位，得到的最终w位模式是相同的。
2）推导概要
（1）利用关系
x
′
=
x
+
x
w
−
1
2
w
x′=x+x_{w−1}2^w
x′=x+xw−12w和
y
′
=
y
+
y
w
−
1
2
w
y′=y+y_{w−1}2^w
y′=y+yw−12w（来自有/无符号转换公式）。 （2）计算
x
′
⋅
y
′
m
o
d
2
w
x′⋅y′mod2^w
x′⋅y′mod2w：
(
x
′
⋅
y
′
)
m
o
d
2
w
=
[
(
x
+
x
w
−
1
2
w
)
⋅
(
y
+
y
w
−
1
2
w
)
]
m
o
d
2
w
(x' \\cdot y') \\bmod 2^w = \\left[ (x + x_{w-1}2^w) \\cdot (y + y_{w-1}2^w) \\right] \\bmod 2^w
(x′⋅y′)mod2w=[(x+xw−12w)⋅(y+yw−12w)]mod2w
=
[
x
⋅
y
+
(
x
w
−
1
y
+
y
w
−
1
x
)
2
w
+
x
w
−
1
y
w
−
1
2
2
w
]
m
o
d
2
w
= \\left[ x \\cdot y + (x_{w-1}y + y_{w-1}x)2^w + x_{w-1}y_{w-1}2^{2w} \\right] \\bmod 2^w
=[x⋅y+(xw−1y+yw−1x)2w+xw−1yw−122w]mod2w
=
(
x
⋅
y
)
m
o
d
2
w
(
因为包含
2
w
及更高幂次的项在模
2
w
下为
0
)
= (x \\cdot y) \\bmod 2^w(因为包含 2w及更高幂次的项在模 2^w下为0)
=(x⋅y)mod2w(因为包含2w及更高幂次的项在模2w下为0) （3）因此，
(
x
⋅
y
)
m
o
d
2
w
=
(
x
′
⋅
y
′
)
m
o
d
2
w
(x⋅y)mod2^w=(x′⋅y′)mod2^w
(x⋅y)mod2w=(x′⋅y′)mod2w。两边分别应用
U
2
T
w
U2T_w
U2Tw 和
U
2
B
w
U2B_w
U2Bw，即得位模式等价。
3. 实例验证：3位乘法表（图2-27）
（1）位模式相同：对于同一对位模式（如101和101），无论按补码（-3*-3）还是无符号（5 * 5）计算，截断后的3位结果模式相同（均为001）。 （2）数值不同：相同的位模式对应不同的数值（补码解释为1，无符号解释为1）。但这不重要，重要的是硬件只需一种乘法器。
练习题2.34
4. 补码乘法溢出检测 (tmult_ok)
1）原理
对于
x
,
y
x,y
x,y，当且仅当
x
⋅
y
x⋅y
x⋅y的数学值超出
[
T
M
i
n
w
,
T
M
a
x
w
]
[TMin_w,TMax_w]
[TMinw,TMaxw]范围时，乘法溢出。
2）检测方法（练习题2.35）
（1）除法检验：计算精确乘积
p
=
x
×
y
p=x×y
p=x×y，检查是否
p
/
x
=
=
y
p/x==y
p/x==y（需处理
x
=
0
x=0
x=0特殊情况）。但除法慢。 （2）高效方法：利用补码运算的不溢出性质。若
x
≠
0
x\\ne0
x=0且乘积 p不溢出，则
p
/
x
=
y
p/x=y
p/x=y。反之，若
p
/
x
≠
y
p/x\\ne y
p/x=y，则溢出。可据此实现 tmult_ok。 
3）64位精度实现（练习题2.36）
对于32位 int，可用64位 int64_t计算精确乘积，然后判断其是否在32位范围内。
int tmult_ok(int x, int y) {
int64_t pll = (int64_t)x * y; // 64位精确乘积
int p = (int)pll; // 截断为32位
return (int64_t)p == pll; // 判断截断前后是否相等
}
5. 现实安全漏洞：Sun XDR库
1）漏洞代码
copy_elements函数中，malloc(ele_cnt * ele_size)。
2）根本原因
ele_cnt和 ele_size均为有符号数（int和 size_t），它们的乘积可能溢出。若溢出产生一个较小的正数，malloc会分配过小的缓冲区，后续的 memcpy会写入越界，导致堆破坏，可利用于执行任意代码。
3）修复（练习题2.37）
（1）A. 乘积计算：应将 ele_cnt转换为 size_t再相乘，并检查是否溢出。可使用 calloc或手动检查。 （2）B. 调用代码修改：在调用 copy_elements前，调用方应确保 ele_cnt非负，且 ele_cnt * ele_size不会溢出（例如，通过比较 ele_cnt <= MAX_BUFFER_SIZE / ele_size）。 
总结栏
本节核心是理解补码乘法的定义、位级本质、溢出检测及其重大安全影响。
x
∗
w
t
y
=
U
2
T
w
(
(
x
⋅
y
)
m
o
d
2
w
)
x∗_w^ty=U2T_w((x⋅y)mod2^w)
x∗wty=U2Tw((x⋅y)mod2w)是根本。
核心启示：理解整数运算的有限精度本质，并在编程中始终保持对溢出的警惕，是写出健壮、安全系统代码的基石。乘法溢出因其潜在的巨大破坏力（直接导致缓冲区溢出），需要给予最高级别的关注。
