💻 CSC3060 Week 3-4 More about Computer System Fundamentals

程序员：→ “距离上一次发生整数溢出已经有” 4294967295 “天啦 😊”

(绝对不是没检测下界所以对 0u 自减了呢)


Week 3 Process of Data

整数运算 (Integer Arithmetics)

由于 C 语言家族的时代和奠基性，其数据类型不是 Python 那样动态存储的，由于运算 “溢出” 导致的严重问题层出不穷。

⚠️ n-bit 有符号数的溢出：“wraparound”——$u = (a + b)\bmod 2^n \quad$

  • 上溢：超过上界就减去 2n，绕到负区间
  • 下溢：低于下界就加上 2n，绕到正区间

2 补码数溢出的检测：

int32_t sign(int32_t x) {
    return (uint32_t)x >> 31;
}
bool add_overFlow(int32_t a, int32_t b, int32_t r) {
    return ((~(sign(a) ^ sign(b))) & (sign(a) ^ sign(r))) != 0;
}

不会在硬件层面上用 trap 捕捉溢出 (比如用 CPU 逻辑门限制)，否则会产生巨大的效率损失，而且有些领域 (如哈希加密) 需要用到溢出 —— 故一般用软件处理。

精确异常：由于计算机执行指令有可能乱序执行，部分较快的运算会先完成 —— 快指令先把结果写进寄存器，一旦前面某条慢指令异常，状态就会乱。为了乱序执行下仍满足 “Precise Exception”，CPU 必须做很多额外的复杂机制：机器内部可以乱跑，但对外必须 “看起来” 是顺序的。


1-bit 全加器和加减法

加法进位有两个构成：propagate (传递进位) 和 generate (产生进位)

对于两个二进制数 A 和 B，其某一位 i 受到上一位 i-1 的进位 Cin ，其加法结果是：Si = Ai ^ Bi ^ Cin

当前位是否产生进位：Cout = (Ai & Bi) | (Cin & (Ai ^ Bi))

具体的 cpp 实现方法——利用位移运算 CLA：

static uint32_t add(uint32_t a, int32_t b) {
    uint32_t p = a ^ b;
    int32_t g = a & b;
  
    g = g | (p & (g << 1));
    p = p & (p << 1); 
    // carry look-ahead: 重复翻倍检测进位 <<1, <<2, <<4 ... 直到覆盖位宽
    return (a ^ b) ^ (g << 1);
}

类似的，减法很容易实现，因为 A - B 等价于 A + (~B+1)。


乘法器

类似于十进制数乘法，两个数相乘等于 “第一个数乘上第二个数的各位及其维权的和”。在二进制 无符号数中，这相当于：$a \times m = \sum_{i=0}^{n} m_i (a « i)$，类似于小学生做乘法每乘一位往左移一次，我们也用左移表示 “增加位权”。

       0010       A  
     × 1011       B            C = 0u
-------------------------------------- "Shift and Add Method"
       0010   if(B & 1u) C += (A << 0)
      0010    if(B & 2u) C += (A << 1)
     0000     if(B & 4u) C += (A << 2)
    0010      if(B & 8u) C += (A << 3)
--------------------------------------
 = 00010110       C

至于有符号整数，我们只关心结果的符号等于 A ^ B 即可。


除法器

小学生式做二进制除法的本质是 ：从被除数最高位开始取位，尝试能不能减除数，能减就把新取的那位在商中记作 1，减去除数后继续尝试……

具体逻辑：利用一个掩码 1u«31，循环把它逻辑右移一位，通过 AND 操作可以逐位取出被除数，并存到一个临时变量中（左移一位并添加到最低位），每取一位把这个变量减一次除数，若结果不是负数，就往 ”商“ 加上当前的掩码。



浮点数和浮点数运算

相比整数，浮点数是对数字 ”不精确的估计“。复习之前提到的 IEEE 的单/双精度浮点数表达：

type sizeof(～) composition composition size
float 4 Byte sign, exponent + 127, fraction 1b + 8b + 23b
double 8 Byte sign, exponent + 1023, fraction 1b + 11b + 52b

⚠️ Bias (指数偏移量)：为了表示负指数，我们将指数加上 2小数位宽-1-1。

以单精度数为例，有两种指数情况：

  • 若 e ≠ 0000…0 或 1111…1 (规格化 normaliaed)：$$x = (-1)^s \times (1+\frac{f}{2^{23}})\times 2^{(e-127)}\ \ (s:sign, f:fraction, e:exponent)$$
  • 若 e = 00000000 (非规格化 denormalized)，当 f = 0 时表示 0：$$x = (-1)^s \times \left(\frac{f}{2^{23}}\right)\times 2^{-126}$$
  • 若 e = 11111111 (非规格化 denormalized)：$$F=0: \pm\infty,\ \ F ≠ 0: NaN$$

⚠️ 注意：在 denormalized 情况下，指数恒为 +126，不存在 ”偏离量 +127“，比如 “0 00000000 1000…” 就是 2-126x(222/223) = 2-127。


何为浮点数？

⚠️ 核心：表达范围与精确性不可兼得！根据等比例缩放，巨大数的精确性不如 0 附近的小数重要。⚠️ 具体的，规格化单精度浮点数在每个 2e~2e+1区间上间隔 (步长) 为 2e-23 (e ≥ -126)；非规格化步长固定为 2-149。

非规格化区段的意义：将 -127 这个最小指数直接借给部分 -1 到 1 之间的极小数。从 2-149 (smallest denormalized) 到 2-126 (smallest normalized) 之间人为制造出有一段稠密的可表示数，间隔固定。如此，实现渐进下溢：小正数在 rounding 时一步步接近 0，而不是断崖式被下溢到 0。(在乘除法中，0 和 2-149 有很大区别)

如此，我们牺牲了大数的精度，只在接近 0 的地方精确 (如上图)。这种 ”可精确表达点的浮动“ 换来更大的表达范围，故得名 ”浮点数“。


二进制展开

我们通过将一个十进制数的小数部分循环反复 ”乘二并取 1 的余“可以得到转化为二进制浮点数：

  • 标准二进制展开法：1、分离整数小数部分；2、小数部分循环进行 x 2 并 mod 1，直到找出规律

Rounding (近似)

IEEE 有四种 rounding 模式: Round-to-even, Round-towards-0, Round down, Round up。最常用的默认方法是偶数近似。浮点数强转换到整数时则会用 Round-towards-0，即，大于 224 时整数不再全部有精确表示，这时强转换会导致下溢。


浮点数运算

  • 加法/乘法交换律存在，但结合律不存在：(2 + 2100) - 2100 ≠ 2 + (2100 - 2100) 左侧估计右侧精确。
  • int32_t 强转换 float 是精确的，反之很可能发生近似，因为 float 的表达范围比 int32_t 大，甚至可能溢出。
  • FPA：align (对齐指数), add (小数相加), normalize (移到小数的整数位为 1), round&renormalize (处理精度溢出，可能需要重新调整)



Week 4 Machine-level Programming

通过汇编看机器级语言

  • x86 是一大类源自 Intel 8086 的 CPUISA家族。我们以 x86-64 (AMD64) 为例，是 x86 的 64-bit 扩展。前者指代寄存器为 %eax, %ebx…；后者为 %rax, %rbx…。PC 的地址是 %rip，命令被移到 PC 就会被执行。x86 是 2-operand 机。
  • ISA (指令集架构) 是“软件看到的 CPU 规格说明书”。不同 CPU 生态，不同 ISA —— e.g. 硬件复杂软件简单的 CISC (x86) vs 硬件精简软件复杂的 RISC (ARM、RISC-V)。
  • 机器真正执行的是“字节序列”——十六进制字节，每一段对应一条指令；meanwhile 机器对源码 (变量名、数据类型等) 几乎一无所知。
  • 汇编语言就是某个 ISA 中机器级程序的的人类可读写法。查看机器码常用两条路：
    1. 编译时强制输出汇编文件：gcc -Og -S xxx.c
    2. 用 反汇编器 把字节序列 “翻译” 得类似于汇编：objdump -d xxx.o (Linux)
  • 反汇编输出通常含：地址/偏移、字节、等价汇编。
  • x86-64 的一个重要特性：指令长度可变 (1–15 字节)，常用/操作数少的更短。
  • 反汇编是“从字节推回指令”，不需要源代码；而且反汇编器在指令命名、后缀省略上可能与 GCC 输出略有差别。


x86-64 (可选)

访问信息——寄存器

64 位 CPU 有 1 个指令寄存器 PC (%rip) 和 16 个通用寄存器(%rax, %rbx…)。每个通用寄存器有灵活的用途，最特殊的是 %rsp 固定为栈指针。

  • 16 个寄存器都属于 64 位整数寄存器，即，来存储整数数据和指针。
  • 多少 bit 的 CPU 其寄存器就是对应 bit 的。可以通过 b, w, l, q 控制一次访问 8、16、32 还是 64 位，下文会展开说明。

x86-64 常见汇编指令

  1. 数据搬运 / 地址
  • mov a, b：从 a 拷贝数据到 b，根据传递数据的位宽分为 movb = 8b, movw = 16b, movl = 32b, movq = 64b (比如 64 位机器的地址/指针/栈都是 q，所有机器中整数是 l)。这四种后缀在类似命令，如 call, ret, pop 等也适用，实际中经常省略。
  • lea：取地址/做地址计算（常用于指针运算、乘加组合，比 mov 不同，它不读内存）
  1. 栈
  • pushq a：把栈顶指针往 “更低虚拟地址” 拓宽 8B，即 %rsp -= 8，然后把 a 的值压栈。
  • popq a：从栈顶取出到 a (寄存器/内存)，即 %rsp += 8。
  1. 算术
  • add / sub / neg：加 / 减 / 取反。
  • imul：乘 (有多种形式)；idiv：除 (配合 rdx:rax 作为被除数)。
  • inc / dec：+1 / -1（常被 add/sub $1 替代）。
  • and / or / xor / not：与 / 或 / 异或 / 非。
  • shl / shr：逻辑左移/逻辑右移；sar：算术右移 (有符号)。
  1. 函数调用
  • call a：把返回地址 (下一个指令) push 入栈，然后跳到目标执行，即 mov a, %rip。
  • ret：从栈弹出返回地址并跳回去，即 movq %rsp, %rip, %rsp += 8。

x86-64 操作数与寻址

操作数 (operand) 三大类:

  • 立即数：常量，在 AT&T 语法中用 $ 引导 (比如 $1, $0x42)。
  • 寄存器：如 %rax、%rbx 等。
  • 内存引用：用“地址表达式”算出有效地址，再访问该地址处的内存。

内存寻址格式：Imm(rb, ri, s)

  • 有效地址由四部分组成：位移 Imm、基址寄存器 rb、变址寄存器 ri、伸缩因子 s。
  • 计算为： M[Imm + R[Rb] + R[ri]·s]。其中 R 表示寄存器数组中对应的指，M 表示内存数组中对应的值。
  • 伸缩因子 s 必须是 1/2/4/8，这正好覆盖了常见基本类型大小，方便“数组下标 × 元素大小”的地址计算。
  • 一些例子：$0x42 的寻址结果是 0x42，0x42 结果是这个内存位置对应的数据，%rax 是这个寄存器中的值，(%rax) 是寄存器值指向内存位置对应的数据。


RISC-V

x86 ISA 实在是太邪门了，就像一群计算机学生中混了个既不玩明日方舟也不是男娘的家伙，还是来看看我们的 RISC 吧。

RV32I (RISC-V32I) 是 RISC-V 架构中最基础、强制性的 32 位整数指令集。它采用 Load/Store 架构，拥有 32 个 32-bit 通用寄存器 (x0~x31，x0 强制固定为 0) 、个 32-bit PC 以及一些 CSR (控制状态寄存器)，是所有 RISC-V 处理器实现的基础。

RV32I 的关键特性与组成：

  • RV32I 中 的 “I” 是基础整数指令集 (base integer)，此外有另一种实现 E：嵌入式裁剪版 (例如只有 16 个寄存器) 。以及更多的扩展，M：乘除扩展 (mul/div) 、A：原子内存指令、C：压缩扩展 (16 位指令)、F/D：单/双精度浮点、V：向量扩展…… 可以组合出比如 “RV64EMAFDCV” 这样的复杂 ISA。

  • 在非扩展机器上运行扩展命令 (如在 RV32I 运行 mul) 会报 illegal instruction exception。

  • 扩展 RV32I 时，FMA 对 F/D 扩展很重要，它一反 RISC 的 3-operand 常态，是 4-操作数运算。优点：聚合加法与乘法，方便非常常见的矩阵/向量乘法运算。

  • 指令分类： 包含 R型 (寄存器-寄存器)、I型 (立即数/Load)、S型 (Store)、B型 (分支)、U型 (长立即数)、J型 (跳转) 共 6 种指令格式。

  • RISC 是 3-operand (3-操作数) 的，意思是命令格式为 A = B op C，比如 ADD x6, x0, x7 (x6 = x0 + x7)。

  • Load/Store 架构： 内存访问仅通过 load 和 store 指令实现，其他运算在寄存器间进行。

  • 不包含乘法/除法 (属于 M 扩展) 也不包含浮点运算 (属于 F/D 扩展)。

  • x0 永远是 0，因为 0 很常用，e.g. negate: sub x9, x0, x8; copy: add x9 x0 x8。

  • 寄存器不是越多越好。pipeline 更高效，但同时指令必须加长，访问时间也会变长。


RV32I 指令分类

按功能分类：

  • ALU（寄存器-寄存器、寄存器-立即数）
  • Control-Flow 控制流（分支 B、跳转 J）
  • 内存访问（Load & Store）
  • CSR 指令（与特权/异常相关，常是 read-modify-write）
  • 特权指令（操作系统/内核态才能执行）

⚠️ 按编码格式分类：

在 RV32I 的 32 位指令中，地址从大到小存储，其信息结构是固定的六种情况 (RISBUJ)。其中：

  • opcode 是 7 位操作码，它告诉 CPU 当前指令属于哪个大类。
  • rd 表示 Register Destination，如果输出到寄存器就需要在这个 5-bit 字段声明目标是 x1~x31 中的哪个。
  • rs 表示 Register Source，表示从哪个寄存器读取数据，显然也是 5b。
  • funct3/7 是更详细的操作分类，比如 funct3 区分 add vs sub、srl vs sra；funct7 区分 add vs srl。
  • imm 是立即数，有时用于计算，在储存/加载内存时表示 “偏移量”，在跳转命令中表示跳转多远。

⚠️ 命令的六大类：**R / I / B / J **(常见)，以及 store 用 S、上位立即数用 U：

  • R：无立即数，比如各种寄存器运算 (opcode 0110011)： add, sub, and, sll (逻辑左移)…
  • I：12 位立即数，比如各种寄存器-立即数运算 (0010011)：addi, andi… 以及 ⚠️ 所有 Load 命令 (0000011)：lw, lb, lh…
  • B：12 位立即数，分支类命令，没有 rd，比如 beq (相等跳转), bne (不等跳转)…
  • J：20 位立即数，比如 jal (跳转并链接)…
  • S：储存到内存，没有 rd，比如 sw, sb, sh…

ALU 指令

R-type：对两个寄存器数据进行计算并返回到寄存器—— OP: rd ← rs1 (funct3, funct7) rs2

  • 比如 sub: 0100000 00000 00110 000 00110 0110011 表示将 x6 的值变成其相反数然后存回 x6；

  • add: 0000000 00000 00110 000 00111 0110011 表示将 x6 的值复制到 x7。

I-type：对一个寄存器和 12-bit 立即数计算并返回到寄存器—— OP-IMM: rd ← rs1 (funct3) I-imm

  • 比如 addi: 010000000000 00110 000 00111 0010011 表示将 x6 加上 1024 后存到 x7。
  • 移位立即数指令也是 I-type，但为了区分逻辑/算数， imm 不再是一个 12 位有符号数；它的低位是 “shamt” (RV32I: 5b, RV64I: 6b)，高位 (含一个标记位 inst[30]) 用来区分 SRLI (0) 和 SRAI (1)。OP-IMM: rd ← rs1 (funct3, inst[30]) I-imm[4:0]
  • 再比如 “取非 x1” 就是 xori x1, x1, -1 。

Load 指令

I-type：用寄存器表示基值+立即数表示偏移，表示内存地址，并将其取出到寄存器—— LOAD: rd ← memory[rs1 + I-imm]

  • 比如 lw: 111111111001 00110 010 00111 0000011 表示从地址为 [x6]-7 的内存取 4 个字节到 x7。12 位有符号 IMM 可以表示偏移量 [-2048, +2047]。偏差 I-imm 常用于访问数组 (或其它容器类) 的某一位。
  • 更具体的，假设一个图片的像素数组：Struct Color {int r, int g, int b} pixelArray[]，若数组基地址存储在 x1，访问其第 100 位的绿值就是 lb x2, 1204(x1)。
  • lb 读 1 字节，lh 读 2 字节；RV64I 还有 ld 读 8 字节。

Store 指令

S-type：将一个寄存器的值存到 (寄存器+立即数表示地址) 内存中—— STORE: mem[rs1 + S-imm] ← rs2

  • 比如 sw: 0011111 00110 00111 010 00001 0100011 表示将 x6 的全部字存到地址为 [x7]+1 的内存中。S 类的立即数只有 5-bit。

⚠️ 坑 —— 数据对齐：Store n 字节的数据时，地址一定是 n 的倍数，比如 sw / lw 的操作地址一定是 4 的倍数。RISC-V 本身并不强制数据对齐，但编译器会，故大部分 RISC 机，比如 ARM 都是数据对齐的。数据对齐可以防止超出 “页”、“cache line” 或者其他存储单位。

例题：

  • 各元素分别要对齐：4, 8, 1, 4, 4，所以 count 之前需要 padding(空余) 4B，red 之前需要空余 3B，结构体整体对齐 = 最大字段对齐 = 8B。故每个结构体内存开销为：white, 4, count, c, 3, red, blue, 4 共 32b，第 100 个 red 的偏差就是 32x100+4+4+8+1+3 = 3220。

Branch 指令

SB-type：比较两个寄存器数据，判断并选择其中一个执行，比如 beq。

  • 在 S-type 中, 偏差是相对于基地址的，以 B 计量；在 SB-type 中, 偏差相对于 PC，以 half word (2B) 计量。两者都是用 S-Imm 表示偏差，但 SB-type 的前 7 位也属于偏差，故可以表示 ±211 范围的偏差。总而言之，branch 可以“够到” ±210x32b (±4 KB) 的指令。

  • 至于无条件的跳转，就用 J-type 的 jal，可以延展到 ±219 (±1 MB) 的指令，或者 I-type 的 jalr (4 GB)。(Jump 指令后续展开讲)

  • RV32I 有 ≥ 和 < (bge、 blt)，没有 > 和 ≤ (bgt、ble)，同时也有 bgeu 和bltu (无符号比较)。特殊的，对于越界检测，如 0 <= x < y 可以把 x 视为无符号，用一次 bgeu x, y 就能同时排除负数与上界越界。

那么，Branch 被执行：PC += imm x 4；未被执行：PC += 4


LUI & AUIPC 指令

U-type：用超大立即数访问更远的内存地址。(超出 ±1MB)

LUI：将 20-bit U-imm 放在寄存器中，然后左移 12 位并低位补零：rd = U-imm << 12

AUIPC：构造相对 PC 的大范围地址基址：rd = PC + (U-imm << 12)

  • 比如：将 32 位整数 0x12345 放进进存器：lui x1, 0x12345，然后 addi x1, x1, 0x678。

    ⚠️ 坑 —— 当你要拼的 32 位常数的 低 12 位 ≥ 0x800 时，用 LUI + ADDI(低12位) 会出错，因为 ADDI 的 12 位立即数是有符号数，会发生符号扩展。(这时需要改为减去低 12 位)

  • 可以直接用伪指令 li x0 0x12345800，交给汇编器处理。


Jump 指令

Jump 在逻辑上近似于 “没有条件的 Branch”。

J-type：特指无条件跳转并连接 jal —— JAL: rd ← pc + 4; pc ← pc + J-Imm

  • J-type 完全没用到 rd，但并未改利用为 Imm 域，这是因为这么做需要新增一种指令格式，解码/ISA 更复杂，违背了 “R”ISC 的初衷。如果要跳更远，完全可以用下面的 JALR。

I-type：特指无条件间接跳转 jalr —— JALR: rd ← pc + 4; pc ← (rs1 + I-Imm) & ~0x01

  • ⚠️ 对于 return：rd ← pc + 4; pc ← (rs1) & ~0x01。判断某行是返回：如果看到 JALR 的基址寄存器是 x1，并且偏移是 0 或很小，可以猜它是 return，比如 jalr x0, 0(x1)。⚠️ 这个猜测有可能错误，因为 x1 功能不是固定用于返回的！

  • 两者的最低位都是 0 (偶数化)，为了支持 16-bit 指令对齐。

  • JALR 的本质是先用 Register AUIPC 组装出基址，然后借助其间接跳转，可以覆盖全部 32 位虚拟地址空间—— 0x00000000 ～ 0xFFFFFFFF (4GB)。


CSR 指令

系统指令，使用特殊寄存器 CSR，管理程序运行（异常、中断、性能计算、定时器等）


Exception Handling

硬件的两件事情：

  1. 记录异常，比如三个最重要的 CSR 信息：

  • mepc – PC 上异常的指令

  • mcause – 异常原因

  • mstatus.mpp – 异常时处于哪个 privilege mode (特权级)，用于事后恢复

  1. 交给软件处理：CPU 读 mtvec (trap handler)，把 PC 设置到那里，并切换到更高特权级。

软件 (Exception Handler)

一般设计为：Common Handler (CH) + 多个 Interrupt/Exception Handler (IH)

CH (通用入口)：用汇编写，负责“脏活累活”

  1. 保存所有 GPR（通用寄存器）
  2. 准备好参数，调用某个 C 函数 IH
  3. IH 返回后决定 mepc 怎么改（+4 或 +2）
  4. 恢复所有 GPR
  5. 执行 ERET（在 RISC-V 里通常叫 mret）

IH (具体处理)：用 C 写，按 mcause 分发：

  • illegal instruction → illegal_inst_ih

  • timer interrupt → timer_ih

  • external interrupt → ext_ih

  • ……



RV32I ABI

ABI = Application Binary Interface (应用二进制接口)，它规定编译出来的二进制程序之间如何协作。

如果不同汇编器对于寄存器有不同使用规则，必然乱套。故，以 RISC-V ABI (ILP32) 为例：

寄存器基本没有硬件层强制限制，但在 ABI 协议上指定其用途。

  • Caller-saved (调用者保存)：t0–t6、a0–a7、ra。意思是：caller 如果在调用函数前还想保留这些寄存器的值，你自己先存栈里；被调用函数（callee）可以随便改它们，常拿来当“临时/传参”。a0/a1 还常用于保存函数返回值。

  • Callee-saved (被调用者保存)：s0–s11 (特殊的， sp 必须隔离维护)。**callee 如果要用这些寄存器，必须先保存旧值，返回前恢复。**这样 caller 可以放心把 “长期变量” 放在 s 寄存器里跨函数调用保持不变。

comments powered by Disqus