LlosLabソフトウェア開発ブログPDF、Delphi、およびドキュメントソフトウェア開発者向けのエンジニアリングノート。

技術記事

純粋PascalのPDFデコーダでJBIG2カスタムHuffmanテーブルを解読

Delphi PDF Library

PDFlibPas 3.539.22はJBIG2のカスタムHuffmanテーブルをネイティブにデコードします。PDFlibJBIG2.pasの純粋PascalデコーダがTablesセグメント（タイプ53）を解析し、ITU-T T.88 Annex B.3の要求どおりにテーブル行の順序で正準プレフィックスコードを割り当て、シンボルディクショナリとテキストリージョンに対してセレクタ順にカスタムテーブル参照を消費し、そしてすべての読み取りを、たまたま後ろにあるバイトではなく宣言されたセグメント長で境界付けます

この作業を強いられたファイルは、見た目には何の変哲もないものでした。スキャンした契約書で、ずっと一般的な算術符号化ではなくHuffmanシンボル符号化でJBIG2圧縮され、しかもエンコーダが標準のB.1〜B.15ではなく自前のコードテーブルを同梱していました。2つの独立したデコーダが、そのリファインメント画素について食い違っていました。そして当時のPDFlibPasのデコーダは、シュレッダーにかけたようなテキストを出力していました。グリフの断片が数ピクセルずれ、すべての文字で1列が欠けているのです。エラーは何も上がりません。これが何年も生き延びるバグの形です。ファイルを拒否するデコーダならサポートチケットが来ますが、少しだけ間違って描画するデコーダには、スキャンが悪かったのだと思い込む顧客が付くだけです

JBIG2のTablesセグメントには実際何が入っているのか

Tablesセグメントは1つのHuffmanテーブルの簡潔な記述です。1バイトのflags、2つの符号付き32ビット境界、そしてその境界の間の区間を分割する（プレフィックス長、レンジ長）の組の並びで、T.88 §7.4.13とAnnex B.2に定められたとおりです。flagsバイトのビット0はHTOOBで、そのテーブルにout-of-bandコードがあるかどうかを示します。ビット1〜3に1を足したものがHTPSで、各プレフィックス長を書くのに使うビット数です。ビット4〜6に1を足したものがHTRSで、各レンジ長フィールドの幅です。ビット7は予約されており、PDFlibPasはこれが立っていれば、将来の改訂が何を意味したのかを推測するのではなく、セグメントを拒否します。続いてHTLOWとHTHIGHが符号付き32ビット整数として並びます。ここがデコーダが最初に間違えうる場所です。符号なしとして読むと、下限が負のテーブル――デルタ符号化されたシンボル幅ではごく普通のことです――が40億から始まるように見えてしまいます。すべてのフィールドはローカルのReadFieldヘルパーを通ります。このヘルパーは、リーダーに触れる前に、要求をセグメントデータが終わるビット位置と突き合わせて検査します。セグメントを越えて読むテーブルは、次のセグメントヘッダをプレフィックス長として食ってしまうからです

PDFlibPasのJBIG2カスタムHuffmanデコードを支えるTablesセグメントのレイアウト。HTOOB・HTPS・HTRSを持つ1バイトのflagsと、立っていれば拒否される予約ビット、符号付きの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);

ループの後に追加される2行はAnnex B.2のエスケープ行です。下限側のレンジ行はHTLOW−1から下向きに数え、上限側のレンジ行はHTHIGHから固定32ビットのレンジで始まり、省略可能なOOB行は値をもちません。PDFlibPasはこれらを、番兵のレンジ長jbig2HuffmanLOW（$FFFFFFFD）とjbig2HuffmanOOB（$FFFFFFFE）で印付けます。15個の内蔵標準テーブルが使っているのと同じ規約なので、デコードループは、そのテーブルが規格から来たのかファイルから来たのかを気にしません

プレフィックスコードはなぜテーブル行の順序で割り当てなければならないのか

エンコーダがコードを一切書かないからです。JBIG2のTablesセグメントが運ぶのはプレフィックス長だけであり、両側がAnnex B.3の正準手順で実際のビットパターンを再構成します。各長さを持つ行がいくつあるかを数え、長さ1のコードを最初に割り当て、次に左シフトしながら続け、同じ長さの中では行が現れる順にコードを配ります。この順序から少しでも外れると、黙って別のテーブルが出来上がります。デコーダは気づきません。生成されるビットパターンはどれも依然として妥当なプレフィックスコードで、ただエンコーダが使ったものではないだけです。そして出力は、間違ったシンボルから組み立てられた、いかにもそれらしいビットマップになります

PDFlibPasのJBIG2デコーダにおける正準プレフィックスコードの割り当て。セグメントにはプレフィックス長だけが届き、Counts・Starts・Positionsを使った安定な計数ソートが各長さの中で宣言順を保ち、長さ1のコードから配られ、長さごとにコードが左シフトされます。過剰割り当てはKraftの検査で拒否します
エンコーダはビットパターンを一切書かないため、テーブル行の順序から外れると、別物ながら妥当なプレフィックスコードが黙って組み上がり、出力はいかにもそれらしくなります。長さ0の行は未使用として落ち、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が比較ソートではなく計数ソートなのは理由が1つあります。Counts、Starts、Positionsを使った計数の走査は構造上安定なので、同じプレフィックス長の行は宣言された順のまま結果に並びます。これはまさに、Annex B.3がコードを割り当てる順序です。プレフィックス長0の行はコード割り当ての前に落とします。B.3がそれらを1ビットコードではなく未使用と定義しているからです。同じループにはガードが2つ入っています。過剰割り当ての検査は、その深さのプレフィックスコードが保持できる以上のコードを長さが主張しているテーブルを捕まえます。これはKraftの不等式を整数比較として表したものです。これがないと、敵対的なテーブルが2つの行に一致するコードを生成し、デコーダは先に走査したほうを選んでしまいます。32ビットの上限があるのは、prefixがCardinalで、decodeIntのマッチャがビットを1つに蓄積するからです。T.88は紙の上ではもっと長いプレフィックスを許していますが、PDFlibPasはそれを名前を付けて拒否しますし、実際にそれを出力するエンコーダも見たことがありません。値の演算にも同じ注意が要ります。THuffmanTable.valはInt64で、下限側のレンジ行はval - readBits(32)としてデコードされます。つまりHTLOW−1から32ビットの符号なしオフセットを引く形です。Integerを中間値にするとこの減算はラップし、ラップした値がそのままシンボル幅として受け入れられてしまいます。64ビットの経路は真の値を計算し、符号付き32ビットの範囲と突き合わせ、収まらなければ送出します。これで静かな破損が明示的な拒否に変わります

3.539.22より前はなぜカスタムテーブルが一度も使われなかったのか

2つの不具合が互いを隠していました。1つ目は1行のsetterのバグでした。TTextRegionHuffmanFlags.setFlagsが、格納先のフィールドと同じ名前で引数を受け取っていたため、Self.flagsAsInt := flagsAsIntは未初期化のフィールドを自分自身に代入し、どのセレクタも0として読み戻されました。その結果、カスタムテーブルを要求するテキストリージョンは、代わりに標準テーブルF、H、Kを通っていました。2つ目の不具合のせいで、1つ目だけを直してもシンボルは壊れたままでした。Huffmanシンボルディクショナリがシンボルを非圧縮のcollective bitmapとして格納する場合、各行の最後のバイトは部分的です。ところが古いコピーループは、有効ビット数を持つpaddingを、最下位の有効ビットの位置として扱っていました。幅63ピクセルの行は、最後のバイトから7ビットではなく1ビットしかコピーしていなかったのです。修正後のループは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と定めています。各2ビットセレクタは、標準テーブルの0または1を意味し、標準テーブルが2つしかないフィールドでは2が予約、3がカスタムです。そしてカスタムを選ぶたびに、参照先セグメントの中から次のTablesセグメントを参照順に消費します。NextCustomHuffmanTableがまさにその走査を行い、リージョンが参照するテーブルがセレクタの要求より少ない場合はmissing custom Huffman table referenceを送出します。もう1行、同じ修正に属するものがあります。入力シンボルと新規シンボルの合計が1であるHuffmanシンボルディクショナリは、log2の式からシンボルコード長0を計算してしまいます。しかしこの形式のHuffman版は、どのシンボルIDも最低1ビットで書きます。そこでTSymbolDictionarySegmentのif sdHuffman and (symbolCodeLength = 0) then symbolCodeLength := 1が、リファインメントと集約の経路でシンボルIDあたり0ビットを読んでしまうのを防ぎます

セグメント境界は何を保証するのか

PDFlibPasは、すべてのヘッダのセグメントデータ長を、両方向が守らなければならない契約として扱います。セグメントは宣言された終端を越えて読んではならず、また途中で終わって次のヘッダを予測できないオフセットに置き去りにしてもいけません。この契約から導かれる規則は、1つ1つは小さなものです。ビット31が立ったデータ長はT.88 §7.2.7の長さ不明マーカーであり、handleSegmentDataLengthはそれを負の値に対応付け、readSegmentsは終端を前方スキャンするのではなく、その場で拒否します。参照先のセグメント番号はすべて、現在のセグメント番号より小さく、かつすでに存在していなければなりません。したがって前方参照やぶら下がり参照は、どのリージョンが解決を試みるよりも前に失敗します。END_OF_PAGEとEND_OF_FILEはデータ0バイトを宣言しなければなりません。Profilesセグメント（タイプ52）は32ビットのカウントと、それに続く同数の32ビット識別子を運び、画素は一切もちません。そこで4＋4×カウントとして宣言長と突き合わせて検査し、スキップし、後のセグメントが番号で参照できるようにするためだけにセグメントリストへ残します。未知のプロファイル識別子は未知の符号化ではありません。それを未知の符号化として扱うと、まったく問題なくデコードできるファイルを拒否してしまいます

// 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リファインメントはどこでビットマップサイズを読むのか

算術デコーダが始まる前、しかもHuffmanモードにしか存在しないフィールドからです。テキストリージョンのインスタンスがリファインメントを持ち（RIが非ゼロ）、かつSBHUFFが立っている場合、T.88 §6.4.11はデコーダにこう求めます。まずRDW、RDH、RDX、RDYをそれぞれ選択されたテーブルで読み、次にBMSIZEをRSIZEテーブルで読み、それからバイト境界に整列し、その後ではじめて、ちょうどBMSIZEバイトに対して汎用のリファインメントデコードを実行します。算術モードのテキストリージョンにはこのフィールドがありません。両モードで1つのコードパスを共有するデコーダはこれを飛ばしてしまい、算術デコーダを2バイト以上早く開始し、すべてのシンボルをゴミに対してリファインしてしまいます。REFAGGと単一のリファインメントインスタンスを使うシンボルディクショナリの経路も、§6.5.8.2.2に記述されており、同じBMSIZEフィールドと同じ帰結を持ちます。PDFlibPasでは、このサイズの上限はTStreamReader.SegmentEnd、つまりreadSegmentsが設定した現在のセグメントの終端であり、ストリーム全体の終端ではありません。次のセグメントからバイトを借りなければ満たせないBMSIZEは不正であり、それをストリーム長と突き合わせて検証すると、算術デコーダが次のヘッダへ読み込めてしまうからです。下限の2バイトは、算術デコーダが必ず消費する先頭のバイト対を反映しています。そしてリファインメントの後、リーダーは算術デコーダがどれだけ先読みしたかに関係なくRefinementEndへジャンプします。算術デコーダの最終位置は、次にHuffman符号化されたフィールドの位置ではないからです

PDFlibPasのJBIG2デコーダにおけるHuffmanモードのリファインメント境界。RDW、RDH、RDX、RDYはそれぞれのテーブルからデコードされ、BMSIZEはRSIZEテーブルからデコードされてバイト整列され、その後算術デコーダがRefinementEndとSegmentEndの間に収まるちょうどBMSIZEバイトをリファインします。2バイト未満やセグメント境界を越えるサイズは拒否します
下限の2バイトは算術デコーダが必ず消費する先頭の対を反映し、上限はストリーム全体ではなく現在のセグメントです。そしてリファインメントの後、リーダーは先読み量に関係なくRefinementEndへジャンプします
// TJBIG2Bitmapのテキストリージョンデコード、Huffmanリファインメント経路
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;

何を検証し、何をいまだに拒否するのか

発端となったサンプル、つまりカスタムテーブルとHuffmanリファインメントを使った500×473ピクセルのJBIG2画像は、いまや独立したデコーダと比べて差分画素ゼロのビットマップにデコードされます。7ビット幅と9ビット幅の合成collective bitmapフィクスチャも、両方で期待どおりの行を生成します。元のサンプルで食い違っていた2つの独立したデコーダは、いまも互いに食い違っています。PDFlibPasはそのうち片方と一致します。正直に言えば、ネイティブの出力が一致するのは、独立した1つの実装と、読み解いたかぎりの仕様に対してであり、世界じゅうのあらゆるデコーダと一致するわけではありません。スイートの不正入力側がカバーするのは次のとおりです

  • 予約されたフラグビット、または予約されたセレクタ値
  • 行の途中で切り詰められたテーブル
  • 過剰割り当てのプレフィックス長と、32ビットを超えるプレフィックス
  • セレクタが参照数より多くカスタムテーブルを要求するリージョン
  • デコード失敗後に古い出力がクリアされ、呼び出し側が結果と取り違えるような形で残らないことの確認

3つの制限は意図的に残しています。すべてのセグメントヘッダがすべてのセグメントデータより前に並ぶランダムアクセス構成は、ファイルヘッダのフラグを読んだ時点でJBIG2 random-access organisation is not supportedを送出します。検証に使える代表的なサンプルが存在せず、中途半端に実装された経路は名前の付いた拒否より悪いからです。カスタムテーブルは65,536行と32ビットのプレフィックスを上限とします。そして公開デコードエントリTPLJBIG2Decoder.LoadFromByteArrayは、ページアソシエーション0を引くのではなく、getPageAsJBIG2Bitmap(0)を通じてストリーム順で最初のページビットマップ、つまり最初に出会ったpage informationセグメントを返します。PDFに埋め込まれたストリームは、その唯一のページに1番を振るのが普通で、アソシエーションでページ0を要求しても何も見つからないからです。失敗のテキストは、障害のセグメント番号・タイプ・バイトオフセットを保持するデコーダ内部の診断情報TPLJBIG2Decoder.LastErrorに入ります。ライブラリレベルのTPDFlib.LastErrorCodeとは別物です。ここまでの話は符号化側には一切触れていません。それについてはJBIG2エンコーダのバックエンドとそのリンク方法の記録にあります。読み取り経路は、他人のエンコーダが出すと決めたものを受け入れなければなりません。そしてそのルールは画像スタックの残りと共有しています。内蔵TIFFデコーダと、そのBigTIFFおよびタイル配置の拒否も同じです。名前を付けて拒否する、宣言された境界を越えてバイトを借りない、そして演算幅を十分に広く保ち、桁あふれした中間値が妥当な答えのふりをできないようにする。これがすべてです。DelphiやC++Builder向けのネイティブなJBIG2読み取り経路を検討しているなら、デコーダとその他の画像処理についてはPDF Library for Delphiのページにまとめてあります