100MB 的指纹——从 60 秒到 424 毫秒
旦阅诞生记 · 第 5 篇。上一篇说到 BookKey 的归一化口径：去 BOM、行尾统一、首尾裁剪。口径定了，新问题立刻浮出水面——这个指纹怎么算得动。本文所有代码取自
eggBookServer-wb/eggBookWin-wb/eggBookApp-wb三个工程的真实实现。
一、先算一笔账
txt 小说动辄几十上百 MB。假设我们在手机端用最直觉的方式算指纹：
- 把整个文件读成一个字符串；
- 归一化（行尾替换、去首尾空白）；
- 对归一化结果求 MD5。
每一步的代价都可以算出来：
| 步骤 | 100MB 文件的代价 |
|---|---|
| 读成 JS/UTS 字符串 | UTF-16 存储，内存占用 ≈ 200MB |
replace(/\r\n/g, "\n") |
再生成一份归一化副本，≈ 又是 200MB |
| 纯 JS 实现的 MD5 | 比原生慢 10~50 倍 |
| 合计 | 10~60 秒，低端机直接 OOM |
一部 4GB 内存的手机，光算个指纹就吃掉 400MB——这不是优化问题，是方案本身不成立。所以流式实现的目标从一开始就定了三条：
- 单趟：文件只顺序读一遍，不回头、不整串；
- O(1) 内存：额外内存与文件大小无关；
- 逐字节等价：结果必须和整串路径算出来的一模一样，一个字节都不能差。
第三条最容易被轻视，也最重要——流式和整串各算各的、结果差一个 bit，两台设备就永远认不出彼此。
二、流水线：三段各管一段
归一化在字节流上拆成三层，每层只做一件事：
原始 UTF-8 字节流
│
▼
① 行尾归一：CRLF → LF、孤立 CR → LF（字节级状态机）
│
▼
② 首尾裁剪：丢首部空白；暂存疑似尾部空白（不能边读边吐）
│
▼
③ 增量哈希：每段确定的字节 TransformBlock 进 MD5
为什么不先把行尾归一写回一个"中转流"、再从头读一遍做裁剪？因为那就不是单趟了。三层必须在同一次遍历里串联，任何一层都不能要求"看全量"。
三、行尾归一：一个只能装 1 bit 的状态机
服务端参考实现 Services/BookKeyUtil.cs 里的 NormalizeInto，核心是这个 Feed 闭包：
public static void NormalizeInto(Stream source, HashAlgorithm hasher, int bufferSize = DefaultBufferSize)
{
if (bufferSize < 8) bufferSize = 8;
var sink = new NormalizedSink(hasher);
var pendingCr = false;
// 统一处理「已读入的一段字节」：先做 CRLF/CR → LF，再交给裁剪 sink
void Feed(ReadOnlySpan<byte> span)
{
foreach (var b in span)
{
if (pendingCr)
{
pendingCr = false;
sink.Push(0x0A); // 上一个 CR 补一个 LF
if (b == 0x0A) continue; // CRLF：当前字节已被消费
}
if (b == 0x0D) { pendingCr = true; continue; }
sink.Push(b);
}
}
// 1) 开头的 UTF-8 BOM（EF BB BF）需要先剔除
var head = new byte[3];
var headLen = ReadFull(source, head, head.Length);
var offset = (headLen == 3 && head[0] == 0xEF && head[1] == 0xBB && head[2] == 0xBF) ? 3 : 0;
Feed(head.AsSpan(offset, headLen - offset));
// 2) 顺序读余下内容
var buffer = new byte[bufferSize];
int read;
while ((read = source.Read(buffer, 0, buffer.Length)) > 0)
Feed(buffer.AsSpan(0, read));
// 3) 末尾孤立的 CR 也要补成 LF（随后会被尾部裁剪丢弃）
if (pendingCr) sink.Push(0x0A);
sink.Finish();
}
整个状态机的全部状态就是一个 bool pendingCr：上一个字节是不是 CR。遇到 0x0D 先不吐，攒着；下一个字节来了再裁决——是 0x0A 就两个一起消费成一个 LF，不是就先补一个 LF 再处理当前字节。
这个"攒一下"是被迫的。CR 和 LF 是两个独立字节，而分块读取的边界可能恰好切在它们中间——CR 落在块尾，LF 在下一个块的开头。如果读到块尾就把 CR 当孤立 CR 处理掉，CRLF 就被错算成了两个换行，归一化结果和整串路径直接分叉。状态机只有 1 bit，但这 1 bit 必须跨块存活。
流末尾还有一个对称的收尾：如果文件最后一个字节是 CR，pendingCr 还挂着，要补吐一个 LF——虽然它接下来会被尾部裁剪丢掉，但"丢"是裁剪层的职责，行尾归一层必须先把语义补完整。分层的好处就在这里：每层只保证自己的语义正确，不替下一层偷懒。
四、尾部裁剪：不能边读边吐
裁剪的规则看起来人畜无害：去掉首尾的空格、制表、换行。首部好办——吐出第一个非空白字节之前，见一个丢一个。尾部麻烦在你读到空白时，不知道它是不是"真正的结尾"：
private sealed class NormalizedSink(HashAlgorithm hasher)
{
private const byte Space = 0x20, Tab = 0x09, Lf = 0x0A;
private readonly byte[] _emit = new byte[64 * 1024]; // 待喂给哈希器的缓冲
private int _emitLen;
private byte[] _pending = new byte[256]; // 暂存的「可能是尾部空白」的一段
private int _pendingLen;
private bool _started;
private static bool IsTrim(byte b) => b == Space || b == Tab || b == Lf;
public void Push(byte b)
{
if (!_started)
{
if (IsTrim(b)) return; // 首部裁剪：丢掉
_started = true;
Emit(b);
return;
}
if (IsTrim(b))
{
if (_pendingLen == _pending.Length) Array.Resize(ref _pending, _pendingLen * 2);
_pending[_pendingLen++] = b;
return;
}
FlushPending(); // 后面还有正文 → 之前暂存的空白其实是正文的一部分
Emit(b);
}
public void Finish()
{
_pendingLen = 0; // 真正的尾部空白：丢弃
FlushEmit();
}
}
策略：空白先暂存进 _pending；一旦后面出现非空白字节，说明那段空白是正文中间的空行，整串吐出去；直到 Finish() 还没被吐走的，才是真正的尾部空白，丢弃。
这个设计的额外内存是 O(尾部连续空白的长度)。正常小说结尾就几十个字节；测试用例里专门放了"300 个换行结尾"的极端情况——也就 300 字节，无关痛痒。唯一会爆炸的场景是"文件 99% 都是尾部空白"，那不属于阅读器的世界。
五、按字节裁剪，为什么切不坏汉字
细心的读者会注意到：裁剪是在字节层做的，没有解码成字符。凭什么安全？
答案藏在编码里。裁剪集合只有三个 ASCII 字符：
- 空格
0x20 - 制表
0x09 - 换行
0x0A
而 UTF-8 的设计保证：多字节字符（汉字等）的每个续字节都 ≥ 0x80，首字节也 ≥ 0x80。也就是说，0x00~0x7F 范围内的字节只可能是 ASCII 字符本身，绝不可能是某个汉字的组成部分。按字节匹配这三个值，永远不会误伤"寒""文"这样的双字节字符。
这是 UTF-8 自洽性送给我们的礼物：字节流在这一点上可以当字符流用，省掉了整个解码环节。顺带说一句，这也是为什么裁剪集合刻意不含全角空格（U+3000）——它不是 ASCII，字节层就够不着它了；想裁它就得解码，代价立刻回来。单元测试里专门锁了这条：" \u3000正文\u3000 " 归一化后必须保留全角空格。
六、桌面端多做的那一点：顺带数出字符数
桌面端 EggBook.Core 用的是 .NET 的 IncrementalHash，同样的 Feed 状态机，但它的 sink 在吐字节给哈希器的同时，还要数出归一化后的字符数——进度定位要用全书绝对字符下标，这个总数得有人提供：
private sealed class NormalizedSink
{
private readonly IncrementalHash _hasher;
private readonly Decoder _decoder = new UTF8Encoding(false, false).GetDecoder();
private readonly char[] _chars = new char[64 * 1024];
private readonly byte[] _emit = new byte[64 * 1024];
// ... 与服务端相同的 Push / Finish ...
private void FlushEmit()
{
if (_emitLen == 0) return;
_hasher.AppendData(_emit, 0, _emitLen);
CharCount += _decoder.GetChars(_emit.AsSpan(0, _emitLen), _chars, false);
_emitLen = 0;
}
}
字节→字符的换算用 Decoder 增量解码：汉字三个字节可能跨两次 FlushEmit，Decoder 会把不完整的尾巴握在手里，等下一批拼上再计一次数。Finish() 里有个耐人寻味的注释：
public void Finish()
{
_pendingLen = 0; // 真正的尾部空白：丢弃
FlushEmit();
// 说明：不必再 flush Decoder —— 只有「末尾被截断的多字节序列」会被它握在手里，
// 那种情况本来就属于文件末尾的脏字节，丢弃即可。
}
不 flush 是故意的：文件末尾如果真有半个残缺的汉字，那属于损坏数据，扔掉比补出来更正确。这个决定和编码探测层的"过度编码报错"是同一个哲学——脏数据宁可丢弃，不可脑补。
七、手机端换了一条等价路线
安卓端没有照抄字节级状态机。UTS 插件（x-reader-native）的 BookKeyHasher 走的是按行处理：
function hashStreamInto(hasher : BookKeyHasher, input : InputStream, encoding : string) : void {
const reader = new BufferedReader(new InputStreamReader(input, Charset.forName(encoding)), 65536)
let line = reader.readLine()
while (line != null) {
const nxt = reader.readLine()
hasher.feedLine(line, nxt != null) // needLf：这行后面还有没有下一行
line = nxt
}
reader.close()
}
这里有个一石三鸟的选择：Java 的 BufferedReader.readLine() 天然把 \r\n、\r、\n 都当行分隔符，行内容里不含任何换行。于是：
- CRLF → LF 的归一化 = 行与行之间补
\n，不用自己写跨块回看； - 逐字节状态机在 UTS 里写起来啰嗦（
number装箱、字节数组操作都是坑），字符串 API 反而自然； - 首尾裁剪可以放在字符域做——反正裁剪集合是 ASCII，字符层字节层结果一致。
代价是需要一个 needLf 前瞻：要知道"这行是不是最后一行"，得先读出下一行。所以循环里始终持有两行。裁剪逻辑集中在 feedLine：
feedLine(s : string, needLf : boolean) : void {
// BOM 只在「整段文本的第一个字符」处才算 BOM（与服务端 Normalize 一致）。
// 极易写错：若用「还没开始正文」当判据，那么「前导空白 + BOM」的串会被多剥一次，
// 手机端与电脑端算出的 key 就对不上了（服务端单元测试专门锁了这条）。
let base = 0
if (this.isFirstLine && s.length > 0 && s.charCodeAt(0) == 0xFEFF) base = 1
this.isFirstLine = false
// 找本行最后一个「非裁剪字符」
let last = s.length - 1
while (last >= base && isTrimChar(s.charCodeAt(last)!)) last = last - 1
if (last < base) {
// 整行都是裁剪字符（空行 / 纯空白行 / 只有 BOM 的行）
if (this.started) {
this.pending = this.pending + s.substring(base)
if (needLf) this.pending = this.pending + "\n"
}
return // 首部还没开始：直接丢
}
// ... 省略：首部裁剪、pending 回吐、emit 正文、行尾空白进 pending
}
哈希的"边编码边喂"借了 Java 标准库的组合技：
// DigestOutputStream 会在字节写入前先喂给 MessageDigest；
// 底下的 sink 只是个「垃圾桶」，定期 reset 以控制内存
this.writer = new OutputStreamWriter(new DigestOutputStream(sink, md), Charset.forName("UTF-8"))
归一化后的字符写进 OutputStreamWriter → 编码成 UTF-8 字节 → DigestOutputStream 截获并喂给 MessageDigest → 丢进一个定期 reset 的"垃圾桶"。字符从进入 hasher 到变成哈希，全程不构造整串。
注意这条路线和字节级路线输入不同：手机端直接对原文件按探测出的编码读（GBK 也能算），桌面端/服务端对已转 UTF-8 的字节流算。殊途同归的前提是归一化口径一致——这就是上一篇说的"参考实现 + 契约测试"存在的意义。
八、等价性不是"我觉得一致"，是测出来的
三条流水线，两套范式（字节级 vs 行级），靠什么保证逐字节等价？服务端测试套件里三类测试分工明确：
① 极端分块。用一个每次只肯吐 N 字节的假 Stream，逼着状态机在最刁钻的边界上工作：
[Theory]
[MemberData(nameof(ChunkSizes))] // 包含 chunkSize = 1
public void 流式与整串结果一致(int chunkSize)
{
foreach (var raw in Cases)
{
var expected = BookKeyUtil.Compute(raw);
var actual = BookKeyUtil.ComputeStreamed(
new ChunkedStream(ToUtf8Bytes(raw), chunkSize), BookKeyUtil.DefaultAlgo, chunkSize);
Assert.Equal(expected, actual);
}
}
ChunkSizes 里故意放了 1：每次读一个字节，pendingCr、_pending、_emit 每一处状态跨越都被逼到极限。1 字节分块都对，256KB 更不会错。
② 黄金值契约。归一化口径一旦被谁"顺手优化"，黄金值当场红：
// md5("abc")
Assert.Equal("md5:900150983cd24fb0d6963f7d28e17f72", BookKeyUtil.Compute("\uFEFF abc \r\n\r\n"));
// md5("")
Assert.Equal("md5:d41d8cd98f00b204e9800998ecf8427e", BookKeyUtil.Compute(" \r\n\t "));
// 流式路径必须给出同样的值
Assert.Equal("md5:900150983cd24fb0d6963f7d28e17f72",
BookKeyUtil.ComputeStreamed(new MemoryStream(ToUtf8Bytes("\uFEFF abc \r\n\r\n")), "md5", 1));
③ 真实文件三方交叉。42MB 的真实小说，手机端、桌面端、服务端各自算一遍，三个 key 必须逐字符相同。这一步锁的是"三份独立实现 vs 同一个真实世界"。
九、实测
台式机，100MB、CRLF 行尾、混合汉字：
文件大小: 100.0 MB
流式 BookKey : md5:8fc243f7f9f4fd1e957d5d5bf0462e5f
流式耗时 : 424 ms ≈ 236 MB/s
整串 BookKey : md5:8fc243f7f9f4fd1e957d5d5bf0462e5f 与流式一致=True
读盘 + 归一化 + MD5 合计 236 MB/s——瓶颈基本在 MD5 本身，归一化几乎白送。手机端按同口径折算（ARM 单核 MD5 约 150~300MB/s，存储读 100~300MB/s），100MB 约 1~2.5 秒，低端机 3~5 秒。
对比一下起点：从 10~60 秒 + 400MB 峰值内存，到 424 毫秒 + 256KB 缓冲区。而且这是一次性成本——导入流程本来就要整文件读一遍做编码探测，BookKey 挂在同一趟读取上，等于零额外 I/O。算完缓存进书籍记录，之后打开书永不重算（缓存的设计下一篇细说）。
十、为什么不走捷径：抽样指纹
写到这里一定会有人问：算指纹何必读全文件？头尾各取 1MB，秒出。我们认真评估过，否决，理由有两个，且都是致命的：
- 按原始字节偏移取样，CRLF 文件比 LF 文件多出的字节会把取样点推到不同位置——同一本书换个来源，取的"中间片段"内容不同，key 不同，同步直接失效；
- 想按"归一化后的字符位置"取样，就得先知道归一化总长——而知道总长需要全量扫一遍，绕回了原点。
抽样只在"所有设备文件字节完全一致"时安全，而 BookKey 的存在意义恰恰是容忍来源差异。目标和方法互斥，没有折中。
顺带一提：MD5 在这里只当内容指纹，不涉及安全；真介意碰撞可把 hashAlgo 换成 sha256——字段从第一天就留着，切换不用改表结构。
小结
| 整串方案 | 流式方案 | |
|---|---|---|
| 文件读取 | 一次性载入 | 单趟顺序 |
| 额外内存 | ≈ 400MB（100MB 书） | O(1)，缓冲区 256KB |
| 耗时（100MB） | 10~60 秒或 OOM | 424ms（台式）/ 1~2.5s（手机折算） |
| 等价性保证 | —（它就是基准） | 1 字节分块 + 黄金值 + 三方交叉 |
流式版本最深的体会：性能问题的答案往往不是"更快的算法"，而是"更少的数据搬运"。MD5 一毫秒都没变快，我们只是不再让它等 400MB 的字符串到位。