PDFlibPas JBIG2ハーフトーングリッド：HSKIPと負のオフセット

PDFlibPasは、ネイティブJBIG2ハーフトーンリージョンデコーダーの独立した2つの不具合を修正しました。v3.539.37では、HSKIPスキップマスクがITU-T T.88 §6.6.5.1の定義どおりHSKIP[ng, mg]としてインデックスされるようになり、v3.539.38では、負のHGXやHGY、あるいは回転によって負の座標に達するグリッドが、真のフロアシフトで配置されるようになりました。それらのリリースより前は、該当するハーフトーンリージョンがエラーなしで、崩れたりずれたりして出力されていました。2つのバグはともに、たまたま対称だったり非負だったりするテストデータの陰に隠れていました。しかも2つ目は、JBIG2を遥かに越えて噛みつくDelphiとFree Pascalの性質に根ざしています。符号付き整数へのshrは論理シフトであって、標準が想定する算術の>>ではないのです

ハーフトーンリージョンはJBIG2のリージョンタイプの中で最も稀です。だからデコーダーは、網点化された写真が1つエンコードされてやって来る前に、何千ものスキャン文書を処理できてしまいます。いざ来たときの失敗は厄介です。ファイルはパースされ、セグメント長は合計が合い、ページは正しいサイズで、そしてリージョンがゴミになる

JBIG2ハーフトーンリージョンは実際に何をデコードするのか

JBIG2ハーフトーンリージョンは、パターン辞書から選んだ小さなビットマップのグリッドです。デコーダーの本当の仕事は、すべてのグリッドセルのインデックスと、そのセルが着地するピクセル位置の計算です。パターン辞書はHPW×HPHピクセルのパターンをHNUMPATS個保持します。ハーフトーンリージョンセグメントは続いて、HGW列×HGH行のグリッドと、同じサイズのグレースケール画像、Gray符号化ビットプレーンとしてコードされたものを記述します。各ビットプレーンはHGW×HGHビットマップ上でジェネリックリージョン手順により、最上位プレーンから順にデコードされ、プレーン群が合わさって各セルにパターンインデックスを与えます

セル配置は8ビット分数を持つ固定小数点演算を使います。グリッド原点HGX、HGYは32ビット値のペアで、グリッドベクトルHRX、HRYは隣接セル間のステップを記述します。これが回転グリッドを可能にします。グリッド行mg、グリッド列ngに対し、T.88 §6.6.5はピクセル位置を次のように計算します：

• x = (HGX + mg × HRY + ng × HRX) >> 8
• y = (HGY + mg × HRX − ng × HRY) >> 8

スキップマスクはオプションのHENABLESKIPフラグを通して登場します。フラグが立っているとき、§6.6.5.1はHGW×HGHビットマップのHSKIPを組み立て、パターンが完全にリージョンの外側にあるセル——x + HPW <= 0、x >= HBW、y + HPH <= 0、y >= HBHのいずれかを満たすセル——すべてについてHSKIP[ng, mg]を1にセットします。グレースケールビットプレーンは、そのマスクをジェネリックリージョンのスキップビットマップとしてデコードされます。だから算術デコーダーは、スキップされたセルのコンテキストを読みませんし、更新もしません。デコーダーとエンコーダーはHSKIPの1ビット1ビットまで合意しなければなりません。さもないと2つの算術コーダーの同期が崩れます

転置されたHSKIPマスクが正方形でないグリッドしか壊さなかった理由

スキップマスクは座標を入れ替えたまま書き込まれていました。それを露呈させるのが正方形でないグリッドだけだったのは、正方形のグリッドでは入れ替わった座標がどれもマスク内に収まるからです。PDFlibPasはビットマップを(column, row)のピクセルアクセサーで保存していて、マスクを組み立てるコードは(mg, ng)と、行を先に渡していました。グレースケールビットプレーンのデコーダーはマスクを(ng, mg)と正しく読みます。パターン配置ループはそれをビルダーの入れ替わった順序で読み戻したため、2者は一致していて、配置ロジックだけのレビューなら素通しです。命名の罠がそれに拍車をかけました。配置ループではcolという名前の変数がグリッド行を、Rowがグリッド列を回ります

v3.539.37がリグレッションケースとして使う、16×8リージョン上の4×4パターンの5×3グリッドを見てください。HRX = 1024、HRY = 0では、グリッド列4はx = 16に、グリッド行2はy = 8に着地し、どちらもリージョンの外です。正しいマスクは7セルに印を付けます。列4の全体と行2の全体です。入れ替わった書き込みは、高さ3行しかないマスクの行インデックス3と4にピクセルを立てようとし、ビットマップセッターはその範囲外の書き込みを静かに無視しました。生き残ったのは列2、行0から2です。その結果、デコーダーはエンコーダーがコードした2セルをスキップし、エンコーダーがスキップした6セルをデコードしました

そうなっても算術デコーダーは失敗しません。後続のセルのビットから余分なピクセルをデコードし、コンテキストは間違った隣人を読み、最初の不一致以降のパターンインデックスはすべてノイズになります。だから症状は、いくつかのずれたセルではなく、崩れたリージョンだったのです。正方形グリッドでは同じバグはしばしば見えません。入れ替わった座標はどれもマスクを出ず、範囲外セルが対角線について対称なとき、たとえば右端と下端に同じ数だけセルがはみ出すグリッドでは、転置マスクはビット単位で正しいマスクと一致します。HENABLESKIPはさらにオプションで、グレースケール画像がMMRコードのときは0でなければならず、エンコーダーが立てることも滅多にありません。バグが表面化する道はほとんどなかったのです。v3.539.37以降、ビルダーはHSKIP[ng, mg]と書き込み、配置ループは同じ順序で読みます

負のハーフトーングリッドオフセットが3層で壊れる理由

リージョンの左や上から始まるハーフトーングリッドは、PDFlibPasの3つの場所を別々に壊し、それぞれの不具合が次の1つを隠しました。T.88はこのジオメトリを意図的に許しています。網点をリージョンでなくページに合わせるエンコーダーや、回転グリッドを使うエンコーダーは、リージョンが切り取る負のセルコーナーを自然に生み出します。v3.539.38は3層すべてを一度に直しました。どれか1つだけ直しても、症状が変わるだけだったからです

層1：符号付きフィールドが符号なしとして読まれる

T.88 §7.4.5.1.2はHGXとHGYを符号付き32ビット値として定義します。ところがデコーダーは、符号なしフィールドに使っていたのと同じ32ビットヘルパーでそれらを読み、そのヘルパーは負の結果をすべて0へクランプしていました。HGX = -900で始まるはずのグリッドは、黙ってリージョン原点へ移動させられます。v3.539.38のリグレッションケースでは、画像全体が2行分低く出ました。このクランプは、他の2つの不具合が長く生き延びた理由も説明します。原点が非負に強制されているかぎり、負の座標はHRY > 0の回転グリッドを通してしか現れ得なかったのです。そこではy = HGY + mg × HRX − ng × HRYが、後のグリッド列でゼロを割ります

層2：shrは>> 8ではない

T.88は>> 8と書いて、マイナス無限大方向へ丸める算術シフトを意味します。デコーダーはそれをshr 8と訳しました。DelphiとFree Pascalでは、符号付き整数へのshrは論理シフトです。符号ビットはゼロとしてシフトインされます。-512を保持するIntegerへのshr 8は、-2の代わりに16777214を返します。y = -2に描かれ下半分に切り詰められるはずだったパターンは、1600万行下へ送られ、リージョン外として捨てられました。クラッシュは何もなく、ハーフトーンの最上行がただ消えました

層3：ピクセルではなく固定小数点を比較する

スキップテストはピクセル位置ではなく固定小数点値を比較していました。分数が非ゼロになった瞬間、この2つは等価ではありません。元のコードは、シフト前の値にxx + HPW × 256 <= 0をテストすることで論理シフトを回避していました。T.88テストの等価物のつもりです。HGX = -900と4ピクセルパターンでは、-900 + 1024 = 124となり、正なのでセルはスキップされません。標準は先にシフトします。floor(-900 / 256) = -4で、-4 + 4 = 0はx + HPW <= 0を満たし、セルは完全に外側にありスキップされなければなりません。エンコーダーはスキップし、デコーダーはデコードし、グレースケール画像は転置マスクのケースとまったく同じように漂いました

v3.539.38のリグレッションケースは、12×10リージョン上のHGX = -900、HGY = -512、HRX = 1024にある4×4パターンの4×3グリッドを使います。グリッド列はx = -4、0、4、8に着地するので、列0は完全に外側でHSKIPに入ります。グリッド行はy = -2、2、6に着地するので、行0は捨てられるのではなく、下の2ピクセル行へ切り詰められなければなりません。層を1つずつ直すと、この積み重ねが再現されます：

修正した不具合	デコードされたリージョン
なし（v3.539.38より前）	グリッドが原点へ引き寄せられ、画像全体が2行分低い
符号付きHGX / HGYの読み取りのみ	最初のグリッド行が欠落し、残りはスキップテストの漂いで崩れる
符号付き読み取り、フロアシフト、ピクセル空間のスキップテスト	T.88 §6.6.5から計算したページとも、2つの独立したリファレンスデコーダーとも、ピクセル単位で同一

修正は1つのヘルパー、HalftoneGridPixelです。スキップマスクビルダーと配置ループが共有します。座標をInt64で蓄積するので、大きなmg × HRXの積がラップすることはなく、256でマイナス無限大方向へ丸めて除算し、±MaxInt div 2へクランプするので、壊れたグリッドが後続のビットマップ演算をオーバーフローさせません。スキップテストは今や、それらのピクセル値をHPW、HPH、HBW、HBHと比較します。§6.6.5.1が述べるとおりにです

Delphiで算術右シフトはどう書くか

Delphiに算術シフト演算子はないので、正しい符号付き右シフトはフロア除算として書くしかなく、素のdivはその除算ではありません。divはゼロ方向へ切り捨てます。非負の値では切り捨てとフロアは一致し、除数の正確な倍数である負の値でも一致します。だから-512 div 256 = -2は手早いテストでは問題なく見えるのです。それ以外ではどこでも食い違います。-900 div 256は-3ですが、フロアは-4。-1 div 256は0ですが、フロアは-1です。分数が非ゼロのJBIG2座標は、まさにdivが間違ったピクセルを返すケースです

DelphiのWin32とWin64コンパイラでは、-512を保持するInteger変数を8右シフトすると16777214になり、-512を保持するInt64では72057594037927934になります。Free Pascalもshrを論理シフトと定義しつつ、算術版としてSystemユニットにSarLongintとSarInt64を同梱しています。ただし、これらの関数はDelphiには存在しないので、2つのコンパイラで共有するコードには独自のヘルパーが要ります：

// フロア除算：AとBの符号にかかわらずマイナス無限大方向へ丸める
// Bは0以外。FloorDiv(Low(Integer), -1)はdivと同様にオーバーフローする
function FloorDiv(A, B: Integer): Integer;
begin
  Result := A div B;
  if (A mod B <> 0) and ((A < 0) <> (B < 0)) then
    Dec(Result);
end;

// 算術右シフト（符号付き値に対するCとT.88の">>"）
// Valueが負でも、not Value = -Value - 1は非負なので、そこでは
// 論理shrは安全で、外側のnotが結果を写像し戻す
function SarInt32(Value: Integer; Shift: Integer): Integer;  // Shiftは0..31
begin
  if Value >= 0 then
    Result := Value shr Shift
  else
    Result := not ((not Value) shr Shift);
end;

function SarInt64(Value: Int64; Shift: Integer): Int64;      // Shiftは0..63
begin
  if Value >= 0 then
    Result := Value shr Shift
  else
    Result := not ((not Value) shr Shift);
end;

notのトリックは負の数を決してシフトしないので、コンパイラが符号ビットをどう扱うかに依存せず、Low(Integer)を含めてオーバーフローもしません。両ヘルパーとも、数百万の値でInt64フロアリファレンスと一致することを確認済みです。0から31までのすべてのシフト、Delphi Win32、Delphi Win64、Free Pascal x86_64でのLow(Integer)とHigh(Integer)のエッジもです。座標に触れるユニットテストなら、どれでも入れておく価値のあるサニティチェックです：

var
  V: Integer;
begin
  V := -900;
  Writeln(V shr 8);           // 16777212  論理シフト、旧バグ
  Writeln(V div 256);         // -3        ゼロ方向への切り捨て
  Writeln(FloorDiv(V, 256));  // -4        T.88が>> 8で意味するもの
  Writeln(SarInt32(V, 8));    // -4
end;

Math.Floor(V / 256)も-4を返します。ただしDoubleへの迂回は、2⁵³を超えるInt64値で精度を失うので、整数ジオメトリは整数のままにしておくべきです

どのPDFlibPas呼び出しがハーフトーンデコーダーを走らせるのか

JBIG2ハーフトーンデコーダーが走るのは、PDFlibPasが組み込みレンダラーでページを描画するときです。描画はピクセルを必要とします。RenderPageToFileもRenderPageToStreamも、ページのJBIG2Decode画像ストリームを通してそこへ届きます。だからハーフトーンページを再描画することが、v3.539.38が出力を変えたことの直接の確認になります。同じデコーダーは他のJBIG2リージョンタイプも扱います。純PascalデコーダーにおけるJBIG2カスタムHuffmanテーブルとDelphiでランダムアクセスJBIG2ファイルをデコードする方法で扱われているものです。そして描画されたビットマップは、PDFページを1ビットモノクロへ描画するような変換へ流れます

uses
  SysUtils, PDFlibrary;

var
  Lib: TPDFlib;
  Page: Integer;
begin
  Lib := TPDFlib.Create;
  try
    if Lib.LoadFromFile('scanned-halftone.pdf', '') <> 1 then
      raise Exception.CreateFmt('Load failed, error %d', [Lib.LastErrorCode]);
    for Page := 1 to Lib.PageCount do
      // レンダリングはすべてのJBIG2リージョンをデコードする。ハーフトーンも含めて
      if Lib.RenderPageToFile(150, Page, PDF_RENDER_PNG,
        Format('page-%.3d.png', [Page])) <> 1 then
        Writeln('Page ', Page, ' was not rendered');
  finally
    Lib.Free;
  end;
end.

画像抽出は通常、別の経路を通ります。GetPageImageListはJBIG2画像をネイティブ形式で返し、SaveImageListItemDataToFileやGetImageListItemDataToStringは、ストリームバイトから組み立てられたスタンドアローンJBIG2ファイルを手渡します。ファイルヘッダー、JBIG2Globalsデータ、ページデータを囲むend-of-fileセグメントです。GetImageListItemIntPropertyのプロパティ400は、その種のアイテムに対して6を報告します。この経路では何もデコードされないので、抽出した.jb2が他のビューアーでは正しく見えるのに、描画されたページにはノイズが出る、というのがこの2つのハーフトーンバグの典型的な兆候でした：

var
  ListID, I: Integer;
begin
  Lib.SelectPage(1);
  ListID := Lib.GetPageImageList(0);
  if ListID = 0 then
    Exit;
  try
    for I := 1 to Lib.GetImageListCount(ListID) do
      if Lib.GetImageListItemIntProperty(ListID, I, 400) = 6 then  // スタンドアローンJBIG2
        Lib.SaveImageListItemDataToFile(ListID, I, 0,
          Format('page1-image%d.jb2', [I]));
  finally
    Lib.ReleaseImageList(ListID);
  end;
end;

マスクや色変換が描画フォールバックを強制するときは、アイテムはデコード済みビットマップとして戻り、ハーフトーンデコーダーはちゃんと走ります。画像リストの詳細は、Delphi PDFテキスト、画像、フォント抽出にあります

クイックリファレンス：JBIG2ハーフトーングリッドのルール

• スキップマスクはHSKIP[ng, mg]とグリッド列を先にインデックスし、セルを配置するどこでも同じ順序で読み戻す（T.88 §6.6.5.1。PDFlibPas v3.539.37で修正）
• ハーフトーンやグリッドのコードは、正方形でないグリッドと非対称な範囲外セルのセットでテストする。正方形グリッドは転置インデックスを完全に隠せます
• HGXとHGYは符号付き32ビット値として読む（T.88 §7.4.5.1.2）。負をクランプする符号なしヘルパー経由では決して読まない
• 標準の>> 8は256によるフロア除算として訳す。shr 8でもdiv 256でもなく
• スキップテストはシフト後のピクセル位置で走らせる。分数が非ゼロのときは固定小数点形式が必ず食い違います。HGX = -900と4ピクセルパターンの例が示すとおりです
• グリッド座標はInt64で蓄積し、ビットマップコードへ渡す前にクランプする。壊れたグリッドがオーバーフローできないように
• 文書にHENABLESKIP付きのハーフトーンリージョン、負のグリッド原点、回転グリッドが含まれるなら、v3.539.38以降へアップグレードする

PDFlibPasは、ハーフトーンスキップマスク、負のグリッド原点、回転グリッドをT.88の指定どおりに扱うネイティブPascal JBIG2デコーダーで、DelphiとC++BuilderからPDF文書を描画、抽出、編集します。機能、エディション、トライアルダウンロードは、PDFlibPas Delphi PDF libraryを参照してください