Lecture 3: 机器级编程 I——基础、算术与逻辑运算 (Machine Programming I: Basics, Arithmetic and Logic)

目录 · ← l2 · l4 →

Lecture 3: 机器级编程 I——基础、算术与逻辑运算 (Machine Programming I: Basics, Arithmetic and Logic)

讲义对应：CMU 15-213 Lecture 3 — Machine Programming I: Basics（素材：F25-03-machine-alpha.txt；课堂活动：machine-control-soln.txt） 教材对应：CS:APP3e 第 3 章 3.1–3.6（History of Intel processors、Program Encodings、Data Formats、Accessing Information、Arithmetic and Logical Operations、Control） 关联 Lab：L0 C Programming / L2 Bomb Lab（反汇编与 GDB 前置知识）

3.1 概述

前两讲停留在”信息的表示”层面：我们讨论位与补码，但程序仍是一行行 C 语句。本讲第一次把视线下沉到机器级（machine level）：编译器究竟把 x = y + 1 变成了什么？答案是指令序列（instruction sequence）——一种 CPU 能直接执行的、极其朴素的”动词 + 名词”语言。

本讲引入三组只有机器级程序员才关心的体系结构可见状态（architecturally visible state）：程序计数器 %rip、16 个 64 位整数寄存器、四个条件码（condition codes）以及按字节寻址的内存。围绕这些状态，我们学习 x86-64 的数据传送（mov/movz/movs/movabsq/leaq）、算术与逻辑运算（add/sub/imul/sal/sar/xor/and/or/inc/dec/neg/not）以及条件码的设置与读取（cmp/test/setX）。

本讲是后续三讲的基石：Lecture 4 用它讲控制流，Lecture 5 讲过程调用与栈帧，Lecture 6 讲数组、结构体与浮点。它同时是 Bomb Lab 的入场券——拆弹时做的第一件事，就是把 objdump -d 的输出翻译回 C 的”伪代码”。

3.2 核心概念与底层机制图解

3.2.1 体系结构、微体系结构与指令集（Architecture vs. Microarchitecture vs. ISA）

• 定义与目的：体系结构（architecture），又称指令集体系结构（ISA, Instruction Set Architecture），是”为了写汇编/机器码所必须理解的那部分处理器设计”——指令集规范、寄存器集合、寻址方式。微体系结构（microarchitecture）是它的具体实现——缓存多大、主频多高、流水线几级。前者是程序员与编译器面对的契约，后者是硬件工程师的自由空间。
• 直观解释（”它是什么？”）：ISA 像交通法规与路牌，微体系结构像具体某款车的发动机。路牌不变，换辆车照样到达目的地——同一份 x86-64 机器码能在 Intel Core i7 和 AMD Ryzen 上跑，因为二者实现了同一套 ISA。
• 底层机制图解：

   高层视角（程序员 / 编译器）          低层视角（硬件工程师）
   +--------------------------+   +---------------------------------+
   | ISA（体系结构）          |   | 微体系结构（microarchitecture） |
   |  - 指令集规范            |   |  - 流水线深度 / 乱序执行        |
   |  - 寄存器集合（16 x 64） |   |  - 缓存大小 / 组相联度          |
   |  - 寻址模式 / 条件码     |   |  - 核心频率 / 功耗              |
   +--------------------------+   +---------------------------------+
         |                                    |
   同一份机器码在两个实现上都能跑   换实现不改代码
   （体系结构不变）                 （实现可变）

   +---------------------------------------------------------------+
   | 代码的三种形态                                                |
   |  机器码 (machine code)  : CPU 直接执行的字节级程序   48 89 03 |
   |  汇编码 (assembly code) : 机器码的文本表示   movq %rax,(%rbx) |
   |  C 代码                 : 与 ISA 无关的高级描述   *dest = t;  |
   +---------------------------------------------------------------+

• 与机器码/硬件的对应：movq %rax, (%rbx) 的机器码是三字节 48 89 03：48 是 REX 前缀（标志 64 位操作数），89 是 mov 的操作码（opcode），03 是 ModRM 字节。执行给字节赋予了类型：同一段字节 48 89 03 若被当数据读出就只是三个整数，只有 %rip 指向它时才是”存储指令”。

CISC 与 RISC，以及 x86 的”怪异性”。x86 属于复杂指令集计算机（CISC）：指令多、格式杂；对照的 RISC（如 ARM、RISC-V） 指令定长、格式规整。x86 的两大怪异之处正源于此：

1. 变长指令（variable-length instructions）：一条指令占 1、3、5 甚至 15 字节。讲义中 sumstore 的 6 条指令共 14 字节。这让解码器远比 RISC 复杂，也是”从任意偏移开始反汇编会得到垃圾”的根源。
2. 复杂寻址模式（complex addressing modes）：一条 mov 就能完成”基址 + 变址×比例 + 位移”的三项计算并访存，RISC 通常需三到四条指令。

x86 的历史是演化式（evolutionary）的：1978 年 8086（16 位、1 MB 地址空间）→ 1985 年 386（首个 32 位 Intel 处理器，即 IA32，引入平坦寻址）→ 2004 年 Pentium 4E（首个 64 位 x86，即 x86-64）。2001 年 Intel 试图用全新的 IA64/Itanium 取代 IA32 但性能令人失望；2003 年 AMD 以演化式方案 x86-64（今称 AMD64）胜出，2004 年 Intel 以几乎相同的 EM64T 跟进。向后兼容一直到 8086，正是今天各种”怪异性”的成因。本课程只讲 x86-64（教材另有一套简化教学指令集 Y86-64，本讲幻灯片未涉及，故不展开）。

3.2.2 机器级代码的两种视角（Two Views: Assembly Programmer vs. Machine）

• 定义与目的：汇编程序员视角关注”我能看见并操纵什么状态”；机器视角关注”这些状态在硬件上由什么部件实现”。
• 直观解释（”它是什么？”）：把 CPU 想成一张工作台。寄存器是台面上随手可取的小零件盒（快、少、贵）；内存是墙上的大货架（慢、多、便宜）；%rip 是你手指指着的那一行说明书；条件码是台面上一盏指示灯，刚做完运算就亮一下，告诉你结果是零、是负还是溢出了。
• 底层机制图解：

        x86-64 机器级程序员可见状态（Programmer-Visible State）
  +-----------------------------------------------------------------------------+
  | %rip  程序计数器 (Program Counter, PC) —— 指向下一条要执行的指令的地址      |
  | 寄存器文件 (Register File)：16 个 64 位整数寄存器（不是内存，也不属于缓存） |
  |   %rax %rbx %rcx %rdx %rsi %rdi %rbp %rsp                                   |
  |   %r8  %r9  %r10 %r11 %r12 %r13 %r14 %r15                                   |
  | 条件码 (Condition Codes)：CF  ZF  SF  OF  各 1 位                           |
  | 向量寄存器 (Vector Registers)：%xmm0-%xmm15 / %ymm0-%ymm15（详见 Lecture 6）|
  | 内存 (Memory)：按字节寻址的线性数组                                         |
  | +----------+---------------+-------------+----------+                       |
  | | 代码 text | 用户数据 data | 栈 stack   | 堆 heap  |                       |
  | +----------+---------------+-------------+----------+                       |
  | 高地址 <----------------------------------> 低地址                          |
  | 栈向低地址增长，%rsp 指向栈顶                                               |
  +-----------------------------------------------------------------------------+

• 与机器码/硬件的对应：编译器必须把语句、表达式、过程调用翻译成上述状态的读写序列。寄存器文件是 CPU 内部多端口存储体；条件码是 ALU 输出端的标志触发器，由进位链与零检测电路驱动。

3.2.3 x86-64 整数寄存器与数据格式（Integer Registers & Data Formats）

• 定义与目的：16 个 64 位通用寄存器是机器级编程的”名词表”，可用不同宽度的别名访问低 8/16/32 位，以支持不同尺寸的 C 类型。
• 直观解释（”它是什么？”）：寄存器像可分段取用的水杯：整杯是 %rax，只留 4 字节是 %eax，再只留 2 字节是 %ax，最后 1 字节是 %al。

   x86-64 整数寄存器文件（16 x 64 bit，讲义 reference 页）
   +-----------+-------------+-------------+-------------+----------------------------+
   | 64 位     | 32 位       | 16 位       | 8 位        | 约定用途                   |
   +-----------+-------------+-------------+-------------+----------------------------+
   | %rax      | %eax        | %ax         | %al         | 返回值 (return value)      |
   | %rbx      | %ebx        | %bx         | %bl         | 被调用者保存               |
   | %rcx      | %ecx        | %cx         | %cl         | 第 4 个整型参数            |
   | %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-%r15 | %r10d-%r15d | %r10w-%r15w | %r10b-%r15b | 调用者保存                 |
   +-----------+-------------+-------------+-------------+----------------------------+

三条必须背下来的约定：

1. 参数寄存器顺序 %rdi, %rsi, %rdx, %rcx, %r8, %r9，返回值在 %rax。
2. 调用者保存（caller-saved）vs 被调用者保存（callee-saved）：%rax %rcx %rdx %rsi %rdi %r8-%r11 属于调用者保存——被调用函数可以随意破坏，调用者若还需要就自己先存好；%rbx %rbp %r12-%r15 属于被调用者保存——被调用函数若要用，必须先保存、返回前恢复。%rsp 特殊：它由硬件与调用约定共同维护，任何时刻它都指向栈顶。
3. 写 32 位子寄存器会清零高 32 位：写 %eax 使 %rax 高 32 位变 0（x86-64 硬件规定）；而写 %ax/%al/%ah 不会改变高位。这个不对称是很多汇编谜题的答案。

C 数据类型到 x86-64 尺寸的映射与指令后缀见下表。后缀 b/w/l/q 分别表示 1/2/4/8 字节；浮点用 s（single，4 字节）、l（long/double，8 字节）、ss/sd（标量单/双精度）。

  +--------+--------+----------+--------------------+
  | C 类型 | 字节数 | 汇编后缀 | 说明               |
  +--------+--------+----------+--------------------+
  | char   | 1      | b        | 字符；8 位         |
  | short  | 2      | w        | 16 位              |
  | int    | 4      | l        | 32 位              |
  | long   | 8      | q        | 64 位（LP64 模型） |
  | char * | 8      | q        | 指针也是 8 字节    |
  | float  | 4      | s        | 单精度浮点         |
  | double | 8      | l / sd   | 双精度浮点         |
  +--------+--------+----------+--------------------+

值得注意：double 的后缀也是 l（因为它是”long word”），CS:APP 特别指出 movl 这个助记符因此有两种含义——操作整数时是 32 位传送，操作浮点时是 64 位传送，靠操作数类型区分。

3.2.4 操作数形式与寻址模式（Operand Forms & Addressing Modes）

• 定义与目的：x86-64 的指令操作数只有三种来源：立即数（immediate）、寄存器（register）、内存（memory）。内存操作数支持最一般形式 D(Rb, Ri, S)。
• 直观解释（”它是什么？”）：D(Rb, Ri, S) 像快递地址的三个部分：Rb 是”小区大门”（基址），Ri 是”楼栋号”（变址），S 是”楼间步长”（比例 1/2/4/8），D 是”进大门后再走几步”（位移）。圆括号永远表示”要算出一个内存地址”。
• 底层机制图解：

   +---------------------------------------------------+
   | 一般形式：  D(Rb, Ri, S)                          |
   |                                                   |
   | 有效地址 = Reg[Rb] + S * Reg[Ri] + D              |
   |                                                   |
   |   D  位移 displacement  1/2/4 字节有符号常量      |
   |   Rb 基址 base          任意 16 个整数寄存器      |
   |   Ri 变址 index         任意寄存器，但不能是 %rsp |
   |   S  比例 scale         只能是 1、2、4、8         |
   |                                                   |
   | 缺省即单位元：省掉 D 相当于 +0；省掉 S 相当于 *1  |
   +---------------------------------------------------+

     指令编码字段                寄存器文件
   +-----------------+     +------------------+
   | Rb 基址寄存器   |---->|     Reg[Rb]      |-----------+
   +-----------------+     +------------------+           |
   +-----------------+     +------------------+           |
   | Ri 变址寄存器   |---->|     Reg[Ri]      |--( * S )--+
   +-----------------+     +------------------+           |
   +-----------------+                                   v
   | S  比例 1/2/4/8 |-------------> +-----------------------------+
   +-----------------+               |  Reg[Rb] + S*Reg[Ri] + D    |
   +-----------------+               +-----------------------------+
   | D  位移         |----------------------------> |
   +-----------------+                              v
                                           送 MMU（有效地址）

各组合形式与常见 C 对应：

   +--------------+---------------------+----------------------------------+
   | 形式         | 地址计算            | C 语言典型出处                   |
   +--------------+---------------------+----------------------------------+
   | Imm          | Imm（不是地址！）   | 常量 5、0x4                      |
   | %rax         | Reg[rax]            | 局部变量 / 参数                  |
   | (%rb)        | Reg[rb]             | *p                               |
   | D(%rb)       | Reg[rb] + D         | 结构体字段 s->c                  |
   | (rb, ri)     | Reg[rb] + Reg[ri]   | 二维数组 A[i][j] 的基址部分      |
   | D(rb, ri)    | Reg[rb]+Reg[ri]+D   | 数组 + 偏移                      |
   | (rb, ri, S)  | Reg[rb]+S*Reg[ri]   | x[i]，元素宽 S 字节              |
   | D(rb, ri, S) | Reg[rb]+S*Reg[ri]+D | A[i][j] + 字段偏移               |
   | (, ri, S)    | S*Reg[ri]           | 纯比例（讲义 jmp *.L4(,%rdi,8)） |
   +--------------+---------------------+----------------------------------+

三条硬约束：$S \in \{1, 2, 4, 8\}$（其他值无法编码）；变址 Ri 不能是 %rsp（该编码字段被占用）；位移 D 只能是 1、2 或 4 字节有符号常量。教材的地址计算练习——设 %rdx = 0xf000、%rcx = 0x0100，则 0x8(%rdx) = 0xf008、(%rdx,%rcx) = 0xf100、(%rdx,%rcx,4) = 0xf400、0x80(,%rdx,2) = 0x1e080。

3.2.5 数据传送指令族：mov / movz / movs / movabsq / leaq

• 定义与目的：mov 系列在寄存器与内存之间搬运数据；movz/movs 搬运的同时做零扩展（zero extension）或符号扩展（sign extension）；movabsq 专门搬运 64 位立即数；leaq 只算地址、不访存。
• 直观解释（”它是什么？”）：mov 是搬运工，movz/movs 是”搬运并补零/补符号”的搬运工，leaq 则是拿着地址清单算账的会计——它甚至不去仓库（内存）看一眼。
• 底层机制图解：后缀是”三段式” mov X Y Z，X ∈ {s, z}、Y 是源宽度、Z 是目的宽度；两位时省略 X（如 movq）。

   例：movzbl %al, %eax      z=零扩展  b=源 1 字节  l=目的 4 字节
        源 %al             目的 %eax
       +--------+   +-------------------------------------+
       | 0x80   |-->| 00000000 00000000 00000000 10000000 |
       +--------+   +-------------------------------------+
        补 0                 高 24 位清零

   例：movslq %edi, %rax     s=符号扩展  l=源 4 字节  q=目的 8 字节
        源 %edi             目的 %rax
       +------------+   +--------------------------------------+
       | 0xFFFFFFFF |-->| 11111111 11111111 11111111 11111111 …|
       +------------+   +--------------------------------------+
        复制符号位                    = -1

⚠️ 一条不可动摇的规则：x86-64 不允许”内存→内存”的单条 mov。 必须用两条指令（内存→寄存器→内存）中转。讲义 movq Operand Combinations 表中 Src/Dest 的 3×3 组合里，Mem→Mem 格子是空的。实测验证：

$ printf '\t.text\n\t.globl f\nf:\n\tmovq (%%rdi), (%%rsi)\n\tret\n' > mem2mem.s
$ as mem2mem.s -o mem2mem.o
mem2mem.s:4: Error: too many memory references for `movq'

movabsq 是为 64 位立即数准备的：任何 64 位常量都必须用它的完整 8 字节形式，而不能用 movq。实测 long big(void){ return 0x123456789abcdef0L; } 得到：

big:
	movabsq	$1311768467463790320, %rax
	ret

objdump -d -M intel 显示为 movabs rax,0x123456789abcdef0，机器码 48 b8 f0 de bc 9a 78 56 34 12——这是 x86 中少见的 10 字节长指令。

leaq 是”地址计算器”，不是加载指令。 leaq Src, Dst 把 Src 这个地址表达式的值放进 Dst，全程不访问内存、也不改变条件码。它有两个用途：一是翻译 p = &x[i]（拿地址）；二是做算术——任何形如 $x + k\cdot y$（$k \in \{1,2,4,8\}$）的表达式，一条 leaq 就能算完。教材的经典例子是 long m12(long x) { return x*12; }，编译为：

m12:
	leaq	(%rdi,%rdi,2), %rax   # t = x + 2*x  = 3x
	salq	$2, %rax              # t << 2      = 12x
	ret

3.2.6 算术与逻辑运算、条件码（Arithmetic, Logic, and Condition Codes）

• 定义与目的：算术逻辑指令直接读写寄存器或内存；同时，除 mov 与 leaq 之外的多数指令都会隐式更新四个条件码，为后续的 jX/setX/cmovX 提供依据。
• 直观解释（”它是什么？”）：条件码是运算后顺手亮起的四盏指示灯，每盏灯回答一个问题：

   +----+------------------------------------------------------------+
   | CF | 进位标志 Carry Flag  —— 无符号溢出（最左一对位产生了进位） |
   | ZF | 零标志 Zero Flag     —— 运算结果为 0                       |
   | SF | 符号标志 Sign Flag   —— 结果为负（最高位为 1）             |
   | OF | 溢出标志 Overflow Flag —— 有符号溢出（两操作数符号相同，   |
   |    | 结果符号与之相反）                                         |
   +----+------------------------------------------------------------+

• 底层机制图解：

   双操作数指令：  addq Src,Dest   Dest = Dest + Src
                  subq Src,Dest   Dest = Dest - Src
                  imulq Src,Dest  Dest = Dest * Src
                  salq/shlq Src,Dest  Dest = Dest << Src   （左移，等价 *2^k）
                  sarq Src,Dest   Dest = Dest >> Src 算术  （补符号位，等价 /2^k）
                  shrq Src,Dest   Dest = Dest >> Src 逻辑  （补 0）
                  xorq/andq/orq Src,Dest  按位运算

   单操作数指令：  incq Dest  Dest += 1        decq Dest  Dest -= 1
                  negq Dest  Dest = -Dest      notq Dest  Dest = ~Dest

   只设置条件码、不写目的：
        cmpq a, b   —— 计算 b - a（和 sub 一样），设置 CF/ZF/SF/OF，但不改变 b
        testq a, b  —— 计算 b & a（和 and 一样），但只设置 SF 和 ZF，不改变 b
                       最常见用法：testq %rX, %rX  （判断 %rX 是否为零/正负）

cmp 与 test 的”只设置不写回”是关键设计：它们是专门用来提问的指令。cmp a, b 的顺序要牢记——算的是 $b-a$，所以 cmpq %rsi, %rdi 是拿 %rdi 减 %rsi（对应 C 的 x > y，其中 x 在 %rdi）。test a, b 算 $b \& a$；由于 x & x == x，test %rX, %rX 就等价于”拿 %rX 本身设置条件码”，因此 test 永远清空 CF（按位与不可能产生进位），这解释了课堂活动的结论：CMOVC 接在 TEST 后永不触发。

3.2.7 读取条件码：setX 与 movzbl 收尾

• 定义与目的：setX 按条件码组合，把目的寄存器的低 1 字节置为 0 或 1。
• 直观解释（”它是什么？”）：cmp 提问，setX 把”是/否”抄成 0/1，movzbl 再把这张纸补齐成规范的 32 位整数。

   setX 的目的只写低 8 位：            随后必须清零其余 7 字节：
     cmpq %rsi, %rdi      # x : y         setg  %al        # 只动 %al
     setg  %al            # x > y ?       movzbl %al, %eax # 高 24 位清零

   +----------------------------+        +-------------------------+
   | %rax  高 56 位【脏数据】   |        | %rax  高 32 位全 0      |
   |       ...      | %al = 0/1 |        |   0000...0000  | 0/1    |
   +----------------------------+        +-------------------------+
       setg 之后（高位未定义）              movzbl 之后（规范的 int）

常用 setX：sete（等于）、setne（不等）、setg/setge/setl/setle（有符号比较）、seta/setb（无符号 above/below）。为什么必须补 movzbl？因为 return x > y; 要求返回规范的 int（值域 $\{0,1\}$），而 setg %al 只承诺低字节正确，高 56 位是上一轮的残留；不清零则调用者可能看到 0x...0101 这类”非零但不止 1”的垃圾。教材示例：

gt:
	cmpq	%rsi, %rdi
	setg	%al
	movzbl	%al, %eax
	ret

3.3 代码示例与底层机制分析

本节所有汇编均在本机（GCC 12.2.0，x86-64）用 gcc -g -Wall -std=c11 -Og -S 与 objdump -d 实际生成并核对，不是凭空编写。

3.3.1 示例一：swap——把汇编读回 C

代码 (C)：

/* swap.c —— 讲义 "Understanding Swap()" 的完整可编译版本 */
#include <stdio.h>

void swap(long *xp, long *yp)
{
    long t0 = *xp;
    long t1 = *yp;
    *xp = t1;
    *yp = t0;
}

int main(void)
{
    long a = 123, b = 456;
    printf("before: a=%ld b=%ld\n", a, b);
    swap(&a, &b);
    printf("after : a=%ld b=%ld\n", a, b);
    return 0;
}

【代码做什么？】

1. main 在栈上放两个 long：a = 123、b = 456，打印初值。
2. 取 &a 放入 %rdi、&b 放入 %rsi，调用 swap（%rdi 是第 1 参数，%rsi 是第 2 参数）。
3. swap 先用 %rax、%rdx 两个临时寄存器把两个值都读出来，再写回去——必须先读两次、后写两次，否则会丢失数据。
4. 返回后 main 打印交换结果。

【底层机制透视】 这个函数揭示一个重要事实：“交换”必须经过寄存器中转，因为 x86-64 不允许内存到内存的直接传送。%rdi/%rsi 是”指针变量”，(%rdi)/(%rsi) 才是指向的对象。写成伪 C 只需把寄存器换成变量名：%rdi → xp、%rsi → yp、%rax → t0、%rdx → t1。

【内存布局 / 数据结构图解】（沿用讲义的具体地址）：

            初始状态                            执行完成后
    寄存器          内存                    寄存器          内存
  寄存器    内存                      寄存器    内存
  +-------+  +-------------+          +-------+  +-------------+
  | %rdi  |  | 0x120: 123  |          | %rdi  |  | 0x120: 456  |
  | 0x120 |  | 0x118:      |          | 0x120 |  | 0x118:      |
  | %rsi  |  | 0x110:      |          | %rsi  |  | 0x110:      |
  | 0x100 |  | 0x108:      |          | 0x100 |  | 0x108:      |
  | %rax  |  | 0x100: 456  |          | %rax  |  | 0x100: 123  |
  |  123  |  +-------------+          |  456  |  +-------------+
  | %rdx  |                           | %rdx  |
  |  456  |                           |  123  |
  +-------+                           +-------+

【与汇编 / 硬件的对应】 gcc -Og -S 的真实输出（已略去 .loc/.cfi 伪指令）：

swap:
	movq	(%rdi), %rax      # t0 = *xp
	movq	(%rsi), %rdx      # t1 = *yp
	movq	%rdx, (%rdi)      # *xp = t1
	movq	%rax, (%rsi)      # *yp = t0
	ret

【实测验证】 objdump -d 的两种语法对比（AT&T 与 Intel 的顺序正好相反，是新手最常见的困惑源）：

$ objdump -d swap              # AT&T: 源在前、目的在后
0000000000401126 <swap>:
  401126:	48 8b 07             	mov    (%rdi),%rax
  401129:	48 8b 16             	mov    (%rsi),%rdx
  40112c:	48 89 17             	mov    %rdx,(%rdi)
  40112f:	48 89 06             	mov    %rax,(%rsi)
  401132:	c3                   	retq

$ objdump -d -M intel swap      # Intel: 目的在前、源在后
0000000000401126 <swap>:
  401126:	48 8b 07             	mov    rax,QWORD PTR [rdi]
  401129:	48 8b 16             	mov    rdx,QWORD PTR [rsi]
  40112c:	48 89 17             	mov    QWORD PTR [rdi],rdx
  40112f: 48 89 06              mov    QWORD PTR [rsi],rax
  401132: c3                   	ret

AT&T 语法是课程与 gcc -S 的默认，务必在脑内建立”src, dst“的条件反射：看到 mov %rdx,(%rdi) 应读成”把 %rdx 的值写进 %rdi 指向的内存”，而不是反过来。

3.3.2 示例二：arith——编译期优化后的乘加算术（leaq 的算术用途）

代码 (C)：

/* arith.c —— 讲义 Arithmetic Expression Example 的完整可编译版本 */
#include <stdio.h>

long arith(long x, long y, long z)
{
    long t1 = x + y;
    long t2 = z + t1;
    long t3 = x + 4;
    long t4 = y * 48;
    long t5 = t3 + t4;
    long rval = t2 * t5;
    return rval;
}

int main(void)
{
    printf("%ld\n", arith(1, 2, 3));   /* 输出 606 */
    return 0;
}

【代码做什么？】 按书写顺序约需 7 次运算。但编译器只用 6 条指令完成，且一次访存都没有。

【底层机制透视】 关键在 y * 48：48 不是 2 的幂，但 $48 = 3 \times 16$，而 $3y = y + 2y$ 可交给 leaq 的 (%rsi,%rsi,2) 一次算完，再 salq $4（左移 4 位 = 乘 16）。这就是 strength reduction（强度削减）：用更便宜的移位与 leaq 替换昂贵的乘法。全函数只保留一次 imulq，因为 t2 * t5 的两个乘数都是运行时才知的变量，没有代数捷径。

【与汇编 / 硬件的对应】 真实编译结果（gcc -Og -S arith.c）：

arith:
	leaq	(%rdi,%rsi), %rax   # t1 = x + y        （一条 leaq 完成加法）
	addq	%rdx, %rax          # t2 = z + t1
	leaq	(%rsi,%rsi,2), %rdx #     y + 2*y = 3y
	salq	$4, %rdx            # t4 = 3y * 16 = 48y
	leaq	4(%rdi,%rdx), %rdx  # t5 = (x+4) + t4   （一条 leaq 完成加+加）
	imulq	%rdx, %rax          # rval = t2 * t5
	ret

注意 leaq 4(%rdi,%rdx), %rdx：它一条指令同时完成了 +4（位移字段）、+ t4（变址）、+ x（基址）三次加法。这里 leaq 完全没有访问内存——%rdi 里存的是整数 x，不是地址；leaq 只是把这个”看起来像地址”的表达式算出来。

【实测验证】 寄存器分配表（讲义原表）：

   +--------+--------------------------------+
   | 寄存器 | 用途                           |
   +--------+--------------------------------+
   | %rdi   | 参数 x                         |
   | %rsi   | 参数 y                         |
   | %rdx   | 参数 z，随后复用为 t4          |
   | %rax   | t1 → t2 → rval                 |
   | %rcx   | t5（不同 GCC 版本可能用 %rdx） |
   +--------+--------------------------------+

./arith 输出 606，与手算 $t_2 = 3 + 3 = 6$、$t_5 = 5 + 96 = 101$、$6 \times 101 = 606$ 一致。

3.3.3 示例三：leaq 用于地址计算——数组、二维数组与结构体

代码 (C)：

/* expr.c —— leaq 的地址计算用途与三操作数乘加 */
#include <stdio.h>
#include <stddef.h>

long *addr_of(long *x, long i) { return &x[i]; }        /* p = &x[i]      */
int get2d(int (*A)[8], long i, long j) { return A[i][j]; } /* 二维数组      */
struct S { int a; int b; long c; };
long *field_c(struct S *s, long k) { return &s[k].c; }  /* 结构体字段偏移  */
long muladd(long x, long y) { return x + 5*y + 7; }     /* 三操作数乘加    */

int main(void)
{
    long x[4] = {10, 20, 30, 40};
    int  A[2][8] = {{0}};
    struct S s[2] = {{0}};
    A[1][3] = 99;
    printf("addr_of(x,2)  -> %ld\n", *addr_of(x, 2));       /* 30            */
    printf("get2d         -> %d\n",  get2d(A, 1, 3));       /* 99            */
    printf("field_c 偏移   = %zu\n", (size_t)((char*)&s[1].c - (char*)s)); /* 24 */
    printf("muladd(3,4)   = %ld\n", muladd(3, 4));          /* 30            */
    return 0;
}

【代码做什么？】 四个函数分别把 leaq 用在四类经典场景：一维数组取址、二维数组索引、结构体数组字段取址、纯算术乘加。

【底层机制透视】 这四条汇编是”寻址模式如何映射 C 表达式”的模板：

addr_of:                       # long *addr_of(long *x, long i)
	leaq	(%rdi,%rsi,8), %rax  # x + 8*i   ← 比例因子 8 = sizeof(long)

get2d:                         # int get2d(int (*A)[8], long i, long j)
	salq	$5, %rsi             # i * 32    ← 行宽 8 个 int = 32 字节
	addq	%rsi, %rdi           # A + 32*i
	movl	(%rdi,%rdx,4), %eax  # 再加 4*j 后【访存】取 int

field_c:                       # long *field_c(struct S *s, long k)
	salq	$4, %rsi             # k * 16    ← sizeof(struct S) = 4+4+8 = 16
	leaq	8(%rsi,%rdi), %rax   # s + 16*k + 8  ← 字段 c 的偏移是 8

muladd:                        # long muladd(long x, long y)
	leaq	(%rsi,%rsi,4), %rax  # 5*y       ← y + 4y
	leaq	7(%rax,%rdi), %rax   # 5*y + 7 + x
	ret

对比 addr_of（只有 leaq，没有访存，返回的是地址）与 get2d（leaq/salq 算完地址后跟一条 movl 真的访存）。这是 leaq 与”带内存操作数的 mov“最本质的区别：leaq 只借用寻址模式的算术能力，不借用它的访存能力。

【实测验证】 struct S 的 sizeof 为 16（int a 占 0–3，int b 占 4–7，long c 因 8 字节对齐而放在偏移 8 处），s[1].c 相对 s 的偏移实测为 24 = 16（跨过第一个元素）+ 8（字段偏移），与 leaq 8(%rsi,%rdi) 中 k=1 时算出的地址完全吻合。

3.3.4 示例四：条件码与 setX —— 有符号 vs 无符号

代码 (C)：

/* opdemo.c —— cmp + setX + movzbl 全流程 */
#include <stdio.h>
#include <stdint.h>

int gt(long x, long y) { return x > y; }
int ge(long x, long y) { return x >= y; }
int lt(long x, long y) { return x < y; }
int le(long x, long y) { return x <= y; }
int eq(long x, long y) { return x == y; }
int ne(long x, long y) { return x != y; }

/* 无符号比较 */
int above(uint32_t a, uint32_t b) { return a > b; }
int below(uint32_t a, uint32_t b) { return a < b; }

int main(void)
{
    printf("gt(5,3)=%d ge(5,3)=%d lt(5,3)=%d le(5,3)=%d eq(5,3)=%d ne(5,3)=%d\n",
           gt(5,3), ge(5,3), lt(5,3), le(5,3), eq(5,3), ne(5,3));
    /* 关键差别演示：-1 的位模式是全 1 */
    printf("above(-1,1)=%d  below(-1,1)=%d\n",
           above((uint32_t)-1, 1u), below((uint32_t)-1, 1u));
    return 0;
}

【代码做什么？】 六组有符号与两组无符号比较，全部编译成 cmp + setX + movzx 模板。

【与汇编 / 硬件的对应】 objdump -d -M intel opdemo 的真实片段：

0000000000401126 <gt>:
  401126:	48 39 f7             	cmp    rdi,rsi
  401129:	0f 9f c0             	setg   al
  40112c:	0f b6 c0             	movzx  eax,al
0000000000401130 <ge>:
  401130:	48 39 f7             	cmp    rdi,rsi
  401133:	0f 9d c0             	setge  al
000000000040113a <lt>:
  40113a:	48 39 f7             	cmp    rdi,rsi
  40113d:	0f 9c c0             	setl   al
0000000000401144 <le>:
  401144:	48 39 f7             	cmp    rdi,rsi
  401147:	0f 9e c0             	setle  al
000000000040114e <eq>:
  40114e:	48 39 f7             	cmp    rdi,rsi
  401151:	0f 94 c0             	sete   al
0000000000401158 <ne>:
  401158:	48 39 f7             	cmp    rdi,rsi
  40115b:	0f 95 c0             	setne  al
0000000000401162 <above>:
  401162:	39 fe                	cmp    esi,edi
  401164:	0f 92 c0             	setb   al
000000000040116b <below>:
  40116b:	39 f7                	cmp    edi,esi
  40116d:	0f 92 c0             	setb   al

【底层机制透视】 两个细节值得深挖。

其一，同一个无符号比较，只需交换 cmp 的操作数顺序，就能用一条 setb 表示两种语义。换成与课件一致的 AT&T 语法看得最清楚：

above:                          # int above(uint32_t a, uint32_t b) → a > b
	cmpl	%edi, %esi         # 计算 %esi - %edi = b - a
	setb	%al                # CF=1 ⟺ 无符号下 b < a ⟺ a > b
	movzbl	%al, %eax
	ret

below:                          # int below(uint32_t a, uint32_t b) → a < b
	cmpl	%esi, %edi         # 计算 %edi - %esi = a - b
	setb	%al                # CF=1 ⟺ 无符号下 a < b
	movzbl	%al, %eax
	ret

两者都用 setb，GCC 只交换了两个 cmp 操作数，就把”大于”改写成了”小于”。它偏爱 setb 是因为无符号 below 恰好等价于单个标志 CF=1，而 seta 要求复合条件 $\sim CF \,\&\, \sim ZF$。注意两类”同名”事实不同：setb/setc 是同一条机器指令（实测都编码为 0f 92，cmovb/cmovc 都是 48 0f 42），而 seta（0f 97）与 setb 是两条不同指令。这说明：条件码本身不知道有符号无符号，语义由 cmp 的操作数顺序与后续 setX/jX 的选择共同决定。

above((uint32_t)-1, 1u) 实测返回 1：(uint32_t)-1 的位模式是 0xffffffff，当作无符号看确实大于 1；而同一个 -1 若按有符号解释则小于 1。同一个位模式，两种解释，相反结论。

其二，有符号/无符号的分野在条件传送（cmov）上表现得更直接。实测 long max_signed(long a,long b){return a>b?a:b;} 与 uint32_t max_unsigned(...)：

max_signed:                      max_unsigned:
	cmpq	%rdi, %rsi               cmpl	%edi, %esi
	movq	%rdi, %rax               movl	%edi, %eax
	cmovge	%rsi, %rax               cmovae	%esi, %eax   # 即 cmovnb
	ret                              ret

cmovge（有符号）与 cmovae/cmovnb（无符号）来自同一套条件码、不同的条件组合：ge 判 $SF = OF$，ae 判 $CF = 0$。

【实测验证】

$ ./opdemo
gt(5,3)=1 ge(5,3)=1 lt(5,3)=0 le(5,3)=0 eq(5,3)=0 ne(5,3)=1
above(-1,1)=1  below(-1,1)=0  (注意实参被转成 uint32_t)
$ ./signedness
max_signed(-1,1)=1
max_unsigned(0xffffffff,1)=4294967295

3.3.5 示例五：不同宽度的加载与扩展（movzbl / movsbq / movslq）

代码 (C)：

/* extend.c —— 扩展指令对照 */
#include <stdio.h>

long zero_extend_byte(char *p)   { return (unsigned char)*p; }  /* movzbl  */
long sign_extend_byte(char *p)   { return *p; }                 /* movsbq  */
long sign_extend_short(short *p) { return *p; }                 /* movswq  */
long sign_extend_int(int *p)     { return *p; }                 /* movslq  */
unsigned long zero_extend_int(unsigned *p) { return *p; }       /* movl    */

int main(void)
{
    char  c = (char)0x80;
    int   i = -1;
    short s = (short)0x8000;
    printf("ze_byte=0x%lx se_byte=%ld se_short=%ld se_int=%ld ze_int=0x%lx\n",
           (unsigned long)zero_extend_byte(&c), sign_extend_byte(&c),
           sign_extend_short(&s), sign_extend_int(&i),
           zero_extend_int((unsigned *)&i));
    return 0;
}

【与汇编 / 硬件的对应】 五个函数恰好覆盖了全部扩展路径：

zero_extend_byte:                  # (unsigned char)*p  -> 零扩展
	movzbl	(%rdi), %eax
	ret
sign_extend_byte:                  # *p（char 为 signed） -> 符号扩展
	movsbq	(%rdi), %rax
	ret
sign_extend_short:                 # *p（short） -> 符号扩展
	movswq	(%rdi), %rax
	ret
sign_extend_int:                   # *p（int） -> 符号扩展
	movslq	(%rdi), %rax
	ret
zero_extend_int:                   # 无符号 int -> 高位自动清零
	movl	(%rdi), %eax
	ret

【底层机制透视】 最后一条最巧妙：zero_extend_int 没有用任何 movz，只写了一条 movl (%rdi), %eax。原因是 3.2.3 节那条规则——写 32 位子寄存器 %eax 会自动把 %rax 的高 32 位清零。所以”无符号 32 位零扩展为 64 位”是免费的。相反，int → long 需要真正的符号扩展（movslq 或 cltq），因为目标的高 32 位必须复制源的第 31 位。

【实测验证】 ./extend 输出 ze_byte=0x80 se_byte=-128 se_short=-32768 se_int=-1 ze_int=0xffffffff。0x80 零扩展得 128，符号扩展得 -128；0x8000 符号扩展得 -32768；-1 的位模式 0xffffffff 零扩展后按无符号看即 4294967295。同一段位、不同扩展方式，数值完全不同——这是 CS:APP 第 2 章”位级表示与类型解释”在机器级的延续。

3.4 实验关联

L0 C Programming 是本讲的前置：你已经会写 C、会编译、会读错误信息，本讲把工具链推进到 -S 与 objdump。建议在 L0 阶段就养成用 gcc -Og -S -fno-asynchronous-unwind-tables 观察自己代码的习惯（该选项去掉 .cfi_* 伪指令，让输出更干净）。

L2 Bomb Lab 是本讲与后续两讲的直接应用。 标准拆弹工作流与本讲内容严格对应：

1. 读反汇编：objdump -d bomb > bomb.asm。Bomb 用 -Og 编译，优化不激进，寄存器与源码变量基本一一对应——这正是课堂活动 loops.o 中”用 -Og 才找得到循环计数器 i“的提醒。
2. 识别关键指令：本讲学到的 cmpq/testq/movzbl/leaq 每一关都会出现。phase_1 通常是 callq strings_not_equal；后续关卡出现 cmp + setX 组合——正是 3.3.4 节的模板，反过来读即可还原 C 里的比较式。
3. GDB 单步与断点（活动讲义重点，也适用于 Bomb）：

$ gdb ./bomb
(gdb) b phase_1            # 在函数入口下断点
(gdb) run                  # 运行到断点
(gdb) disassemble          # 看当前函数反汇编
(gdb) x/8xb $rdi           # 检查第 1 参数指向的 8 个字节
(gdb) info registers rdi rsi rax rip
(gdb) stepi                # 单条指令步进（汇编级）
(gdb) x/14xb sumstore      # 直接观察机器码字节（讲义演示）

1. 两个必踩的坑：
   • ⛔ 不要在 Bomb Lab / Attack Lab 里用 gdb 的 call 命令。活动讲义脚注明确警告：”Do not do this in bomb lab or attack lab.” 因为 call 会真正执行被调用函数，explode_bomb 一旦触发就扣分。
   • 不要中途退出：服务端记录爆炸次数，每次爆炸扣 1/2 分（上限 6 次）。拆弹前先想清楚再运行。
2. 从 cmp 反推 C 表达式的对照表（本讲的核心技能，也是 Bomb Lab 每一关都在做的事）：

   +-------------------------+--------------------+
   | 反汇编片段              | 等价 C 表达式      |
   +-------------------------+--------------------+
   | cmpq %rsi,%rdi / setg   | x > y   （有符号） |
   | cmpq %rsi,%rdi / setl   | x < y   （有符号） |
   | cmpl %esi,%edi / setb   | a < b   （无符号） |
   | testq %rdi,%rdi / sete  | x == 0             |
   | testq %rdi,%rdi / js    | x < 0              |
   | leaq (%rdi,%rdi,4),%rax | 5*x                |
   | leaq 7(%rax,%rdi),%rax  | 5*y + 7 + x        |
   +-------------------------+--------------------+

3.5 常见错误与调试技巧

• 把 AT&T 操作数顺序读反：movq %rax,(%rbx) 是”把 %rax 存进 %rbx 指向的内存”。调试：用 gcc -Og -S（AT&T，src, dst）与 objdump -d -M intel（Intel，dst, src）对照着看。口诀”括号里是地址，逗号左边是源“。
• 以为 leaq 会访问内存：leaq (%rdi), %rax 只是把 %rdi 的值搬到 %rax，一次访存都没有。调试：凡对应 &x[i]、a + k*b 的地方编译器就用 leaq；若真在访存，必然跟着 movX。
• setX 后忘记清零高位：setg %al 只改 1 字节，高 56 位是脏数据。调试：gdb 中 p/x $rax 看完整 64 位；机器生成的代码里必紧跟 movzbl %al, %eax，若缺失即为 bug。
• 记错 cmp 的操作数方向：cmpl %esi, %edi 算的是 %edi - %esi。搞反会使条件跳转方向全错（Bomb Lab 的经典死因）。调试：gdb 里停在 cmp 后的 jX 上，info registers eflags 看 CF/ZF/SF/OF。EFLAGS 位序：CF=0、PF=2、ZF=6、SF=7、OF=11。
• 用错有符号/无符号的条件助记符：把 jl 当 jb 用。-1 < 1（有符号）但 0xffffffff > 1（无符号），结论相反。调试：回到 C 源码确认类型；gdb 里 p (int)x 与 p (unsigned)x 各看一遍。
• 试图一条 mov 完成内存到内存 / 混淆 movl 的双重含义：前者 as 会报 Error: too many memory references for 'movq'，须拆成两条经寄存器中转；后者在操作整数时是 32 位传送、操作浮点时却是 64 位传送。调试：objdump -d -M intel 会明确显示 DWORD PTR 或 QWORD PTR，PTR 前的尺寸最权威。
• 误以为 -Og 下汇编与源码一一对应：-Og 保留调试友好性，但仍会做强度削减与寄存器复用（见 arith 中 %rdx 先存 z 后存 t4）。调试：用 gcc -Og -g 编译，gdb 中 disassemble /m 可把源码行与汇编交错显示。

3.6 关键要点

1. 机器级程序的状态只有五类：%rip、16 个 64 位整数寄存器、条件码 CF/ZF/SF/OF、向量寄存器、按字节寻址的内存——掌握它们的读写就掌握了全部”名词”。
2. leaq 不是加载指令，而是”不访存的地址算术器”。它同时承担”取地址”（p = &x[i]）与”常量乘加”（$x + k \cdot y$，$k \in \{1,2,4,8\}$）两种角色，是编译器强度削减的主力。
3. mov/leaq 不改条件码，其余算术逻辑指令都改；cmp 与 test 是”只设置条件码、不写目的”的纯提问指令，cmp a,b 算 $b-a$，test a,b 算 $b \& a$。
4. AT&T 语法是课程与 gcc -S 的口径：操作数 src, dst、寄存器加 %、立即数加 $、宽度后缀 b/w/l/q（浮点用 s/l/ss/sd）。读反操作数顺序是最高频的错误来源。
5. 有符号与无符号共享同一套位运算，只靠条件码组合区分：setg/jl 判 $SF \oplus OF$，setb/jb 判 CF。同一条 cmp 后跟不同的 setX，得到的 C 语义可能完全相反。
6. 写 32 位寄存器会清零高 32 位，写 8/16 位不会。这条 x86-64 的硬件规定让”无符号 int → long”零扩展变成零开销（一条 movl），也是 movzbl %al, %eax 这一固定收尾动作存在的理由。

3.7 思考题（带答案）

题 1（汇编推演题） 下面这段汇编是一个 long 类型的单参数函数（参数在 %rdi，返回值在 %rax），请写出等价的 C 代码，并说明 gcc 用了哪些优化：

mystery:
	leaq	(%rdi,%rdi,4), %rax   # 
	leaq	(%rax,%rax,2), %rdx   # 
	leaq	1(%rdi,%rdx), %rax    # 
	ret

答：逐步代入。设 x = %rdi： 第一步 %rax = x + 4x = 5x； 第二步 %rdx = %rax + 2*%rax = 3 * 5x = 15x； 第三步 %rax = 1 + x + 15x = 16x + 1。 所以等价 C 是 long mystery(long x) { return 16*x + 1; }。可验证：x = 1 得 17。 优化手法有两条：(1) 强度削减——$16x$ 本可用 salq $4，但编译器把它与 +1 合并进一条 leaq 的位移字段，一条指令完成”乘加”，省掉一次独立加法；(2) leaq 当加法器用——三条 leaq 无一访存，全部只做算术。这体现了 leaq 的三操作数能力（基址 + 变址×比例 + 位移）在常系数线性表达式上的威力。

题 2（计算/推演题） 设 %rdx = 0xf000、%rcx = 0x0100，请计算下列寻址表达式的有效地址（十六进制）：0x8(%rdx)、(%rdx,%rcx)、(%rdx,%rcx,4)、0x80(,%rdx,2)、0x10(%rdx,%rcx,8)。

答：按 $Reg[rb] + S \cdot Reg[ri] + D$ 逐个代入：

注意最后一题的比例因子 8 与位移 0x10 是相加而非相乘，且三项缺省即单位元（省 D 是 +0，省 S 是 *1）。前四行与讲义 Address Computation Examples 完全一致。

题 3（”直观但错误的想法”） 有同学说：”leaq (%rdi,%rsi,4), %rax 就是 %rax = %rdi + 4 * *(%rsi)，所以 leaq 会解引用 %rsi。” 这个想法错在哪？

答：错在把”寻址模式里的寄存器值”当成了”指针解引用”。寻址模式里的 Rb/Ri 只是寄存器中的整数值，leaq 把它们代入表达式算出一个数，整个过程不访问内存。正确读法是 %rax = Reg[rdi] + 4 * Reg[rsi]（纯值运算）。要发生解引用，必须让该内存操作数出现在会访存的指令里——例如 movq (%rdi,%rsi,4), %rax 才会真正读 Mem[Reg[rdi] + 4*Reg[rsi]]。区分方法：看指令名——lea 只算不算，mov/add/imul/cmp 带括号操作数时才访存。这也是 3.3.3 节 addr_of（只有 leaq，返回地址）与 get2d（leaq 之后跟 movl，真的取值）的差别。

题 4（推演题） 下面两个函数编译出的汇编只有一个字节不同（setg vs setb、cmovge vs cmovae），请解释为什么 fail_signed 与 fail_unsigned 在输入 (-1, 1) 时给出相反的结果；并说明如果把 fail_unsigned 改成 int 参数会怎样。

int fail_signed(long a, long b)        { return a > b; }
int fail_unsigned(unsigned a, unsigned b){ return a > b; }

答：-1 作为 64 位 long 的位模式是 0xffff...ffff，作为 32 位 unsigned 的位模式是 0xffffffff。

• fail_signed(-1, 1)：cmp 置 SF=1、OF=0，故 $SF \oplus OF = 1$，setg 判 $\sim(SF \oplus OF) \& \sim ZF = 0$，返回 0。
• fail_unsigned(0xffffffffu, 1u)：0xffffffff - 1 需借位，故 CF=1，setb 判定为”above”，返回 1。 同一段位模式、同一套条件码，结论相反，差别完全来自 C 类型赋予它的解释（这正是实测 above(-1,1)=1 的原因）。若把参数改为 int，gcc 会改用 setg，(-1, 1) 下返回 0，与 fail_signed 一致。