LlosLab 軟體開發部落格面向 PDF、Delphi 與文件軟體開發者的工程筆記

技術文章

純 Pascal PDF 解碼器中的 JBIG2 自訂 Huffman 表

Delphi PDF Library

PDFlibPas 3.539.22 版原生解碼 JBIG2 自訂 Huffman 表：PDFlibJBIG2.pas 裡的純 Pascal 解碼器會剖析 Tables 區段（type 53）、依 ITU-T T.88 Annex B.3 的要求以表格行序指派標準前綴碼、為符號字典與文字區域按選擇器順序消耗自訂表參照，並以宣告的區段長度而不是後面剛好接著的位元組來限制每一次讀取

逼出這項工作的那個檔案表面上毫不起眼。一份掃描合約，用 JBIG2 壓縮，而且是 Huffman 符號編碼，而非更常見的算術編碼，編碼器還自帶編碼表，而不是用標準的 B.1 到 B.15。兩個獨立解碼器對它的 refinement 像素意見不一致，而當時的 PDFlibPas 解碼器產出的文字像是被碎紙機絞過：字符碎片位移了幾個像素，每個字都少了一直欄。沒有任何地方報錯。這就是那種能存活好幾年的 bug，因為會拒絕檔案的解碼器換來一張客服單，而把檔案渲染得有點錯的解碼器，換來的是以為掃描品質很差的客戶

JBIG2 的 Tables 區段裡到底裝了什麼

Tables 區段是一張 Huffman 表的精簡描述：一個 flags 位元組、兩個帶號 32 位元邊界，接著是一串（前綴長度，範圍長度）配對，把兩個邊界之間的區間分割開來，佈局見 T.88 §7.4.13 與 Annex B.2。flags 位元組的 bit 0 是 HTOOB，說明這張表有沒有 out-of-band 碼。bit 1 到 3 加一得到 HTPS，也就是寫入每個前綴長度所用的位元數；bit 4 到 6 加一得到 HTRS，即每個範圍長度欄位的寬度。bit 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);

迴圈之後追加的那兩行是 Annex B.2 的逃脫行：下界範圍行從 HTLOW 減一往下數，上界範圍行從 HTHIGH 開始、範圍固定 32 位元，而選用的 OOB 行根本沒有值。PDFlibPas 用哨兵範圍長度 jbig2HuffmanLOW（$FFFFFFFD）與 jbig2HuffmanOOB（$FFFFFFFE）標記它們，與它內建的十五張標準表用的是同一套慣例，所以解碼迴圈並不在乎一張表是來自規格還是來自檔案

為什麼前綴碼必須按表格行序指派

因為編碼器從來不寫入碼本身。JBIG2 的 Tables 區段只帶前綴長度，兩邊都用 Annex B.3 的標準程序重建實際的位元樣式：數出每個長度各有幾行、先指派長度一的碼，然後左移繼續，而在同一個長度內，按行出現的順序發碼。任何偏離這個順序的做法都會默默產生另一張表。解碼器不會察覺，因為它生成的每個位元樣式仍然是合法的前綴碼，只是不是編碼器用的那一個，而輸出則是一張看起來很合理的點陣圖，由錯誤的符號拼出來

PDFlibPas JBIG2 解碼器中的標準前綴碼指派：區段裡只送來前綴長度，對 Counts、Starts 與 Positions 做穩定計數排序，讓每個長度內維持宣告順序，長度一的碼先發，每個長度之後碼再左移，而超額訂閱由 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 做一輪計數，在結構上就是穩定的，所以前綴長度相同的行會以宣告順序落進結果，而這正是 Annex B.3 指派碼時所用的順序。前綴長度為零的行在指派碼之前就被剔除，因為 B.3 把它們定義成未使用，而不是一位元的碼。同一個迴圈裡坐著兩個守衛。超額訂閱檢查會抓出長度宣稱的碼數超過該深度前綴碼容量的表，也就是以整數比較表達的 Kraft 不等式；少了它，一張有惡意的表會產出同時匹配兩行的碼，而解碼器會挑它先掃到的那一行。32 位元上限的存在，是因為 prefix 是 Cardinal，而 decodeInt 裡的比對器把位元累積進同一個。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 把每個標頭裡的區段資料長度當成雙方都必須遵守的契約：區段不得讀過它宣告的結尾，也不得提早收工、把下一個標頭留在無法預測的位移上。從這份契約衍生的規則每一條都很小。bit 31 被設起的資料長度是 T.88 §7.2.7 的未知長度標記，handleSegmentDataLength 把它映射成負值，由 readSegments 直接拒絕，而不是往前掃描找終止符。每個被參照的區段編號都必須小於目前區段編號，而且必須已經存在，所以往前指或懸空的參照，在任何區域試著解析它之前就會失敗。END_OF_PAGE 與 END_OF_FILE 必須宣告零位元組的資料。Profiles 區段（type 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 每一個符號。§6.5.8.2.2 所述的符號字典路徑，在 REFAGG 搭配單一 refinement 實例時，有同樣的 BMSIZE 欄位與同樣的後果。在 PDFlibPas 裡，這個大小的上限是 TStreamReader.SegmentEnd，也就是由 readSegments 設定的目前區段結尾，而不是整條串流的結尾，因為一個只能靠向後面的區段借位元組才滿足的 BMSIZE 就是畸形的，而拿串流長度去驗證它，會讓算術解碼器讀進下一段標頭。兩個位元組的下限反映算術解碼器一定會消耗的起始位元組對，而在 refinement 之後，讀取器會直接跳到 RefinementEnd，不管算術解碼器往前讀了多遠，因為它的最終位置並不是下一個 Huffman 編碼欄位的位置

PDFlibPas JBIG2 解碼器中 Huffman 模式的 refinement 邊界：RDW、RDH、RDX 與 RDY 由各自的表解出，BMSIZE 由 RSIZE 表解出並對齊位元組，接著算術解碼器在 RefinementEnd 與 SegmentEnd 之間對恰好 BMSIZE 個位元組做 refinement，小於二或超出區段邊界的大小一律拒絕
兩個位元組的下限反映算術解碼器固定消耗的起始位元組對，上限是目前的區段而非整條串流，而 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 x 473 像素、帶自訂表與 Huffman refinement 的 JBIG2 影像，現在解出的點陣圖與一個獨立解碼器相比差異像素為零，而 7 位元與 9 位元的合成集合點陣圖測試資料在兩邊都產生預期的列。原本在樣本上意見相左的兩個獨立解碼器，至今仍然彼此不一致；PDFlibPas 與其中一個相符，而誠實的說法是原生輸出與一個獨立實作、以及與所讀到的規格相符，不是全世界每個解碼器都同意。測試套件中畸形的那一側涵蓋：

  • 保留的 flag 位元或保留的選擇器值
  • 在一行中途被截斷的表
  • 超額訂閱的前綴長度與超過 32 位元的前綴
  • 選擇器要求的自訂表數量多於它參照的數量的區域
  • 確認解碼失敗後過期的輸出會被清掉，而不是留在原地讓呼叫端誤當成結果

有三個限制是刻意保留的。隨機存取串流組織，也就是所有區段標頭都排在所有區段資料之前的那種，會在檔案標頭 flags 被讀到的瞬間就丟出 JBIG2 random-access organisation is not supported，因為沒有具代表性的樣本可以拿來驗證，而且做一半的路徑比具名的拒絕更糟。自訂表上限為 65,536 行與 32 位元前綴。而公開的解碼入口 TPLJBIG2Decoder.LoadFromByteArray 透過 getPageAsJBIG2Bitmap(0) 回傳串流順序上的第一張頁面點陣圖，也就是遇到的第一個 page-information 區段，而不是去查 page association 零；內嵌的 PDF 串流習慣把它的單一頁編號為 1，用 association 去要第 0 頁會什麼都找不到。失敗訊息會落在 TPLJBIG2Decoder.LastError，那是解碼器內部的診斷，帶著出錯的區段編號、型別與位元組位移，與程式庫層級的 TPDFlib.LastErrorCode 不是同一回事。這些都不涉及編碼那一側，那部分記在JBIG2 編碼器後端與它們如何連結的筆記裡；讀取路徑必須接受別人的編碼器決定送出的任何東西，而它與影像堆疊其餘部分共用規則，包括內建 TIFF 解碼器以及它對 BigTIFF 與分塊佈局的拒絕：點名拒絕、絕不跨越宣告的邊界借位元組，並讓運算寬度足夠到繞回的中間值無法冒充合法答案。如果您正在為 Delphi 或 C++Builder 評估原生 JBIG2 讀取路徑，解碼器與其餘影像處理的說明都在 PDF Library for Delphi 頁面上