LlosLab Software Development Blog面向 PDF、Delphi 和文档软件开发者的工程笔记

技术文章

纯 Pascal PDF 解码器实现 JBIG2 自定义 Huffman 表

Delphi PDF Library

PDFlibPas 3.539.22 原生解码 JBIG2 自定义 Huffman 表：PDFlibJBIG2.pas 里这个纯 Pascal 解码器解析 Tables 段（类型 53），按 ITU-T T.88 附录 B.3 的要求以表行顺序分配规范前缀码，按选择符顺序为符号字典和文本区域消费自定义表引用，并让每一次读取都以声明的段长度为界，而不是以后面碰巧跟着的字节为界

逼出这项工作的那个文件表面上看平平无奇。一份扫描合同，用 Huffman 符号编码而不是常见得多的算术编码做 JBIG2 压缩，而且编码器自带码表，没有用标准的 B.1 到 B.15。两个独立解码器在它的 refinement 像素上意见不一致，而当时的 PDFlibPas 解码器产出的文字像是被碎纸机过了一遍：字形碎片偏移几个像素，每个字符都缺一列。没有任何东西报错。这正是那种能活好几年的 bug 形态，因为拒收文件的解码器会换来一张支持工单，而渲染得稍微有点错的解码器换来的是一个认定扫描件本来就不清楚的客户

JBIG2 的 Tables 段里到底装了什么？

一个 Tables 段是一张 Huffman 表的紧凑描述：一个 flags 字节、两个有符号 32 位边界值，然后是一串（前缀长度，范围长度）对，把两个边界之间的区间分割开，布局见 T.88 §7.4.13 和附录 B.2。flags 字节的第 0 位是 HTOOB，说明这张表有没有带外码。第 1 到 3 位加一得到 HTPS，也就是写入每个前缀长度所用的位数；第 4 到 6 位加一得到 HTRS，也就是每个范围长度字段的宽度。第 7 位保留，PDFlibPas 一旦发现它被置位就拒绝该段，而不是去猜未来的修订版想用它表达什么。HTLOW 和 HTHIGH 紧接着作为有符号 32 位整数出现，这是解码器第一个能搞错的地方：把它们当无符号读，会让一张低边界为负的表看起来从四十亿开始，而对增量编码的符号宽度来说负的低边界完全正常。每个字段都经过本地的 ReadField 助手，它在碰读取器之前先把请求跟段数据结束所在的位位置做比对，因为一张读过自己段末尾的表，会把下一个段头当成前缀长度吃掉

PDFlibPas 中 JBIG2 自定义 Huffman 解码背后的 Tables 段布局示意图：一个 flags 字节携带 HTOOB、HTPS 和 HTRS 以及一个被拒绝的保留位，有符号的 HTLOW 与 HTHIGH 边界，一串前缀长度与范围长度对，以及转义行 jbig2HuffmanLOW、一条固定 32 位的高端行和可选的 jbig2HuffmanOOB
段的每个字段都经过带边界检查的助手读取，因为一张读过声明末尾的表会把下一个段头当成前缀长度吃掉，而那些哨兵转义行与内置标准表保持一致
// TCodeTableSegment.readSegment, PDFlibJBIG2.pas
EndBit := (Int64(decoder.reader.bytePointer) +
  segmentHeader.getSegmentDataLength) * 8;
Flags := ReadField(8);
if (Flags and $80) <> 0 then
  raise EJBIG2DecodeError.Create('reserved custom Huffman table flag');
PrefixBits := ((Flags shr 1) and 7) + 1;   // HTPS
RangeBits  := ((Flags shr 4) and 7) + 1;   // HTRS
LowValue   := Integer(ReadField(32));      // 有符号 HTLOW
HighValue  := Integer(ReadField(32));      // 有符号 HTHIGH
if LowValue >= HighValue then
  raise EJBIG2DecodeError.Create('invalid custom Huffman range bounds');
CurrentValue := LowValue;
while CurrentValue < HighValue do
begin
  PrefixLength := ReadField(PrefixBits);
  RangeLength  := ReadField(RangeBits);
  if RangeLength > 32 then
    raise EJBIG2DecodeError.Create('invalid custom Huffman range length');
  AddLine(CurrentValue, PrefixLength, RangeLength);
  Inc(CurrentValue, Int64(1) shl RangeLength);
end;
AddLine(LowValue - 1, ReadField(PrefixBits), jbig2HuffmanLOW);
AddLine(HighValue,   ReadField(PrefixBits), 32);
if (Flags and 1) <> 0 then
  AddLine(0, ReadField(PrefixBits), jbig2HuffmanOOB);

循环之后追加的那两行是附录 B.2 里的转义行：低端范围行从 HTLOW 减一开始并向下计数，高端范围行从 HTHIGH 开始并带一个固定的 32 位范围，可选的 OOB 行则完全没有值。PDFlibPas 用哨兵范围长度 jbig2HuffmanLOW（$FFFFFFFD）和 jbig2HuffmanOOB（$FFFFFFFE）标记它们，这正是它那十五张内置标准表用的同一套约定，所以解码循环不关心一张表是来自规范还是来自文件

为什么前缀码必须按表行顺序分配？

因为编码器从来不写码字。一个 JBIG2 Tables 段只携带前缀长度，两边都用附录 B.3 的规范流程重建真正的位模式：先数每种长度各有多少行，先分配长度为 1 的码，然后左移继续，而在同一种长度内部按各行出现的顺序发码。任何偏离这个顺序的做法都会悄悄产出一张不同的表。解码器不会察觉，因为它生成的每一个位模式仍然是合法前缀码，只不过不是编码器用的那个，而输出就是一张用错符号拼出来的、看上去还挺像样的位图

PDFlibPas JBIG2 解码器中的规范前缀码分配示意图：段里只传来前缀长度，对 Counts、Starts 和 Positions 做稳定计数排序以在每种长度内保持声明顺序，长度为 1 的码先发出去，随后按长度左移，超额分配由 Kraft 检查拒绝
编码器从不写位模式，所以任何偏离表行顺序的做法都会悄悄构建出另一个合法前缀码，输出看上去还挺像样；长度为零的行按未使用处理被丢掉，超过 32 位的前缀一律拒绝
// THuffmanDecoder.buildTable, PDFlibJBIG2.pas
FillChar(Counts, SizeOf(Counts), 0);
for I := 0 to length - 1 do
begin
  if table[I].prefixLen > 32 then
    raise EJBIG2DecodeError.Create(
      'Huffman prefixes longer than 32 bits are not supported');
  Inc(Counts[table[I].prefixLen]);
end;
Active := 0;
Code := 0;
for Bits := 1 to 32 do
begin
  Starts[Bits]    := Active;
  Positions[Bits] := Active;
  Inc(Active, Counts[Bits]);
  if Code + UInt64(Counts[Bits]) > (UInt64(1) shl Bits) then
    raise EJBIG2DecodeError.Create('oversubscribed Huffman prefix codes');
  Code := (Code + UInt64(Counts[Bits])) shl 1;
end;
SetLength(Result, Active + 1);
for I := 0 to length - 1 do            // 稳定排序：保持原始顺序
  if table[I].prefixLen > 0 then       // 在每种前缀长度内部
  begin
    Result[Positions[table[I].prefixLen]] := table[I];
    Inc(Positions[table[I].prefixLen]);
  end;
Code := 0;
for Bits := 1 to 32 do
begin
  for I := Starts[Bits] to Positions[Bits] - 1 do
  begin
    Result[I].prefix := Cardinal(Code);
    Inc(Code);
  end;
  Code := Code shl 1;
end;
Result[Active].rangeLen := jbig2HuffmanEOT;

THuffmanDecoder.buildTable 用计数排序而不是比较排序，理由只有一个：对 Counts、Starts 和 Positions 走一遍计数天然就是稳定的，于是前缀长度相同的行会按声明顺序落到结果里，而这正是附录 B.3 分配码字所依据的顺序。前缀长度为零的行在分配码字之前被丢掉，因为 B.3 把它们定义为未使用，而不是一位码。同一个循环里坐着两道守卫。超额检查抓的是这样一种表：它的长度声明了比该深度前缀码所能容纳的更多码字，也就是用整数比较表达的 Kraft 不等式；没有它，一张恶意表会产出能匹配两行的码，而解码器挑中先扫到的那行。32 位上限的存在是因为 prefix 是 Cardinal，而 decodeInt 里的匹配器把位累积进一个 Cardinal。T.88 纸面上允许更长的前缀，PDFlibPas 点名拒绝它们，而现实中还没见过哪个编码器发出来过。值的算术需要和码的算术一样小心：THuffmanTable.val 是 Int64，而低端范围行被解码成 val - readBits(32)，也就是从 HTLOW 减一里减去一个 32 位无符号偏移。用 Integer 做中间量，这个减法会回绕，而回绕后的值随后被当成一个合法的符号宽度接受。64 位路径算出真值，拿它对有符号 32 位范围做检查，装不下就抛错，把一次静默损坏变成一次显式拒绝

为什么 3.539.22 之前自定义表从来没生效过？

两个缺陷彼此掩护。第一个是一行 setter bug：TTextRegionHuffmanFlags.setFlags 接收的参数和它要存进去的字段同名，于是 Self.flagsAsInt := flagsAsInt 把未初始化的字段赋给自己，每个选择符读回来都是零，这就把要自定义表的文本区域送去了标准表 F、H 和 K。第二个缺陷意味着只修第一个照样会产出损坏的符号。当一个 Huffman 符号字典把符号存成未压缩的集合位图时，每一行的最后一个字节是残缺的，而旧的复制循环把保存有效位数的 padding 当成了最低有效位的位置；一行 63 像素宽的行因此从最后一个字节里只复制了一个位，而不是七个。修好后的循环跑 for bitPointer := 7 downto ((8 - padding) and 7)，而 7 位和 9 位宽度的合成夹具把字节边界两侧都钉住了。选择符读对之后，表就按规范列出的顺序发放，T.88 §7.4.3.1.2 对文本区域固定下来的顺序是 FS、DS、DT、RDW、RDH、RDX、RDY 和 RSIZE，§7.4.2.1.1 对符号字典固定下来的顺序是 DH、DW、BMSIZE 和 AGGINST。每个两位选择符表示标准表 0 或 1、在只有两张标准表的字段上保留给 2、以及 3 表示自定义，而每一次自定义选择都会按引用顺序消费被引用段中的下一个 Tables 段。NextCustomHuffmanTable 做的正是这趟遍历，并在某个区域引用的表比它的选择符所要求的少时抛出 missing custom Huffman table reference。还有一行属于同一个修法：一个 Huffman 符号字典在输入符号和新符号加起来等于一时，用 log2 公式算出的符号码长度是零，而这个格式的 Huffman 变体给每个符号 ID 至少写一个位，所以 TSymbolDictionarySegment 里的 if sdHuffman and (symbolCodeLength = 0) then symbolCodeLength := 1 让 refinement 和 aggregate 路径不至于每个符号 ID 读零个位

段边界保证了什么？

PDFlibPas 把每个头里的段数据长度当作两个方向都必须遵守的契约：一个段不能读过它声明的末尾，也不能提前结束、把下一个头留在不可预测的偏移上。由这个契约派生出的规则单看每一条都很小。数据长度第 31 位置位是 T.88 §7.2.7 的未知长度标记，handleSegmentDataLength 把它映射成一个负值，readSegments 直接拒绝，而不是向前扫描找终止符。每个被引用段号都必须小于当前段号，并且必须已经存在，于是前向引用或悬空引用在任何区域试图解析它之前就失败。END_OF_PAGE 和 END_OF_FILE 必须声明零字节数据。Profiles 段（类型 52）携带一个 32 位计数，后面跟着同样多的 32 位标识符，完全没有像素，所以它按 4 加 4 倍计数对声明长度做检查、跳过，并且只为了后面那些段还能按编号引用它而留在段列表里。一个未知的 profile 标识符不等于一种未知编码，把它当成未知编码会拒收那些解码得完全正常的文件

// TJBIG2StreamDecoder.readSegments, PDFlibJBIG2.pas
DataLength := segmentHeader.getSegmentDataLength;
if DataLength < 0 then
  raise EJBIG2DecodeError.Create(Context +
    'unknown or oversized segment length is not supported');
if DataLength > Length(reader.Data) - reader.bytePointer then
  raise EJBIG2DecodeError.Create(Context + 'truncated segment data');
DataEnd := reader.bytePointer + DataLength;
for I := 0 to noOfReferredToSegments - 1 do
  if (referredToSegments[I] >= segmentHeader.getSegmentNumber) or
     (findSegment(referredToSegments[I]) = nil) then
    raise EJBIG2DecodeError.Create(Context + 'invalid segment reference');
// ... 按该类型创建段对象 ...
reader.SegmentEnd := DataEnd;
segment.readSegment;
if reader.bytePointer > DataEnd then
  raise EJBIG2DecodeError.Create(Context +
    'decoded data exceeds declared segment length');
if reader.bytePointer < DataEnd then
begin
  reader.bytePointer := DataEnd;   // MMR 可能没读到 EOFB
  reader.bitPointer := 7;
end;

那个循环的尾部正是解码器早期版本在 MMR 编码区域上出错的地方。MMR 解码器在最后一行最后一个像素产出时就知道自己完成了，而这可能发生在它消费掉 T.88 §6.2.5.7 放在数据末尾的 EOFB 终止符之前。旧代码假定读取器已经停在下一个头上，于是剩下的终止符字节被解析成一个段号，流在几个字节之后带着一条误导性的错误失败。现在声明的末尾说了算：读过它是错误，提前停下是正常的，读取器被移到 DataEnd 并把位指针重置，好让下一个头从文件所说的位置读起。同一套纪律出现在 PDFlibPas 解析不可信 PDF 结构的每一处：声明的长度就是边界，解码器不会去找一个更好说话的边界

Huffman refinement 从哪里读它的位图大小？

在算术解码器启动之前，而且读的是一个只在 Huffman 模式下存在的字段。当一个文本区域实例带 refinement（RI 非零）且 SBHUFF 置位时，T.88 §6.4.11 要求解码器用各自选定的表读 RDW、RDH、RDX 和 RDY，然后用 RSIZE 表读 BMSIZE，再对齐到字节边界，之后才对恰好 BMSIZE 个字节跑通用的 refinement 解码。算术模式的文本区域没有这个字段，而把两种模式共用一条代码路径的解码器会跳过它，提前两个或更多字节启动算术解码器，然后拿垃圾去 refine 每一个符号。符号字典里带 REFAGG 和单个 refinement 实例的那条路径（§6.5.8.2.2 有描述）有同样的 BMSIZE 字段和同样的后果。在 PDFlibPas 里这个大小的上界是 TStreamReader.SegmentEnd，也就是 readSegments 设定的当前段末尾，而不是整个流的末尾，因为一个只有从后一个段借字节才能满足的 BMSIZE 本身就是畸形的，而拿流长度去校验它会让算术解码器读进下一个头。两字节的下界反映的是算术解码器总要消费的初始字节对，而 refinement 之后读取器一律跳到 RefinementEnd，不管算术解码器提前读到了多远，因为它的结束位置不是下一个 Huffman 编码字段的位置

PDFlibPas JBIG2 解码器中 Huffman 模式的 refinement 边界示意图：RDW、RDH、RDX 和 RDY 从各自的表解码，BMSIZE 从 RSIZE 表解码并对齐到字节，随后算术解码器只对夹在 RefinementEnd 与 SegmentEnd 之间的 BMSIZE 个字节做 refine，小于两字节或越过段边界的大小一律拒绝
两字节的下界反映的是算术解码器总要消费的初始字节对，上界是当前段而不是整个流，而 refinement 之后不管提前读了多少，读取器都会跳到 RefinementEnd
// TJBIG2Bitmap 文本区域解码，Huffman refinement 路径
RefinementSize := huffmanDecoder.decodeInt(huffmanRSizeTable).intResult;
huffmanDecoder.consumeRemainingBits;
if (RefinementSize < 2) or
   (RefinementSize > huffmanDecoder.reader.SegmentEnd -
                     huffmanDecoder.reader.bytePointer) then
  raise EJBIG2DecodeError.Create('invalid refinement bitmap size');
RefinementEnd := huffmanDecoder.reader.bytePointer + RefinementSize;
arithmeticDecoder.start;
// ... readGenericRefinementRegion ...
if huffmanDecoder.reader.bytePointer > RefinementEnd then
  raise EJBIG2DecodeError.Create('refinement data exceeds declared size');
huffmanDecoder.reader.bytePointer := RefinementEnd;
huffmanDecoder.reader.bitPointer := 7;

验证了什么，还有什么依然会被拒绝

引发这一切的那个样本——一张 500 × 473 像素、带自定义表和 Huffman refinement 的 JBIG2 图像——现在解码出的位图与一个独立解码器相比零差异像素，而 7 位和 9 位的合成集合位图夹具在两边都产出预期的行。原先在那个样本上意见不一致的两个独立解码器至今仍然互相不一致；PDFlibPas 与其中一个吻合，而诚实的说法是原生输出与某一个独立实现以及按我们所读的规范一致，不是世界上每个解码器都一致。套件里畸形输入的那一侧覆盖了：

  • 保留的 flag 位或保留的选择符值
  • 在一行中间被截断的表
  • 超额分配的前缀长度和超过 32 位的前缀
  • 选择符要求的自定义表比它实际引用的数量更多的区域
  • 确认一次失败的解码之后陈旧输出被清掉，而不是留在原处让调用方误当成结果

还有三处限制是刻意的。随机访问流组织——所有段头排在所有段数据之前——在读文件头标志时就直接抛 JBIG2 random-access organisation is not supported，因为没有可代表它的样本可以拿来验证，而一条半成品路径比一次点名的拒绝更糟。自定义表上限是 65,536 行和 32 位前缀。而公开的解码入口 TPLJBIG2Decoder.LoadFromByteArray 通过 getPageAsJBIG2Bitmap(0) 返回流顺序里的第一个页面位图，也就是遇到的第一个页面信息段，而不是按 page association 零去查找；内嵌的 PDF 流经常把它们唯一的那页编成 1，按 association 要第 0 页会什么都找不到。失败文本落在 TPLJBIG2Decoder.LastError，这是内部解码器诊断，携带出错的段号、类型和字节偏移，跟库级别的 TPDFlib.LastErrorCode 不是同一个东西。这些都不涉及编码那一侧，编码侧写在JBIG2 编码器后端以及它们如何链接的笔记里；读取路径必须接受别人家编码器决定发出的任何东西，而它的规则与图像栈的其余部分共用，包括内置 TIFF 解码器以及它对 BigTIFF 和分块布局的拒绝：点名拒绝，绝不跨过声明的边界去借字节，并让算术宽度足够大，使一个回绕的中间值不可能冒充合法答案。如果你正在为 Delphi 或 C++Builder 评估一条原生 JBIG2 读取路径，解码器和其余图像处理都记在PDF Library for Delphi 页面上