# 第 45 章实验：动手实现四种校验和

对应页面：`chapters/45-data-integrity.html`

## 做什么

`csum.c` 实现了原书 45.3 节介绍的几种校验和（checksum）：

| 函数 | 说明 |
|---|---|
| `xor32` | 把数据看成 32 位字（大端，和原书"每行 4 字节"的排法一致），逐列异或 |
| `xor64_fast` | XOR 的 8 字节一次版本，只用于测速 |
| `add32` | 32 位二进制补码加法，忽略溢出 |
| `fletcher_naive` | 原书定义：`s1 = (s1 + d_i) mod 255`，`s2 = (s2 + s1) mod 255`，每个字节都取模 |
| `fletcher_fast` | 结果与上面完全相同，但把取模推迟到每 4096 字节一次 |
| `crc32_bitwise` | CRC32（IEEE，反射多项式 0xEDB88320）逐位做"模 2 长除法" |
| `crc32_table` | CRC32 查表法，一次一个字节 |

程序分三段：

1. **自检**：原书示例 `365e c4cd ba14 8a92 ecef 2c3a 40be f666` 的 XOR 必须是 `0x201b9403`；
   `CRC32("123456789")` 必须是标准测试值 `0xCBF43926`。
2. **测速**：对 64 MB 随机数据反复计算，输出 MB/s。
3. **检测率**：随机生成 4 KB 数据块，施加各种损坏（随机 1/2/3 比特翻转、同一列的两个比特翻转、交换两个 4 字节字），
   统计每种校验和"发现了损坏"（校验和变了）的比例。

## 怎么跑

```bash
cd labs/45-data-integrity
make
./csum            # 默认每种损坏试 100000 次，约 10 秒
./csum 1000       # 试验次数少一点，跑得快
```

## 该观察到什么、为什么

- **速度**：XOR 和加法最快（每字节一两条指令，且可以一次处理多个字节）；Fletcher 若每个字节都做 `% 255` 会慢很多，
  把取模推迟后能快好几倍；CRC32 逐位版最慢，查表版快数倍，但仍明显慢于 XOR。
  这就是原书说的"没有免费的午餐"：越强的校验和通常越贵。
- **单比特翻转**：四种校验和都能 100% 发现。
- **同一列的两个比特翻转**：XOR 完全发现不了（0%），这正是原书指出的 XOR 弱点；加法约一半能发现
  （两个翻转方向相同时会产生进位，方向相反则互相抵消）。
- **交换两个字**：XOR 和加法都满足交换律，顺序变了结果不变，所以 0%；Fletcher 的 `s2` 与位置相关，大多能发现；CRC32 全部发现。
- **Fletcher 在 4 KB 块上偶尔漏掉双比特错误**：按字节模 255 的 Fletcher 在数据不超过 255 字节时能发现所有双比特错误；
  块更长时，若两个相距 255 字节整数倍的字节、同一个比特位一个 0→1 一个 1→0，`s1`、`s2` 的变化都恰好是 255 的倍数，就漏掉了。
- **奇数个比特翻转**：XOR 一定能发现（至少有一列翻转了奇数次）。

测速数字受 CPU、编译器和机器负载影响很大，你的结果会不同；检测率由固定种子产生，应当与页面上的输出一致或非常接近。