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

技術記事

HotPDFによるDelphiでのPDF Predictor・LZWDecodeデコード

HotPDF Component

/Predictor 12と記されたストリームは、すべての行がPNGフィルタ2を使うという意味ではない。DelphiとC++Builder向けのネイティブVCL PDFコンポーネントであるHotPDFは、10から15までのpredictor値を1つの系統として扱う:実際のフィルタタグ(0から4)は各エンコード済み行の先頭バイトであり、HPDFDecodePredictorはそのタグを行ごとに読み取り検証する。この区別は、PDFのこの領域におけるほぼすべてのバグの形そのものである。間違えても何も例外が上がらないからだ。フィルタチェーンは走り、ラスタは期待どおりのサイズになり、それでいて画像は斜めのノイズか、走査線ごとにどんどんずれていくグラデーションとして出てくる。/DecodeParms(ISO 32000-1 §7.4.4)の5つの数値は、多くの場合バイト列の長さではなく意味を変えてしまうため、値を間違えるとエラーではなくもっともらしいガベージが生まれる

なぜ/Predictor 12はすべての行がPNGフィルタ2という意味にならないのか

predictor番号は「PNG予測が使われている」ということだけを示し、どのフィルタかは示さないからだ。PNGエンコーダは走査線ごとにフィルタを選び、PDFのフィルタはそれを引き継ぐため、predictor値の10(None)、11(Sub)、12(Up)、13(Average)、14(Paeth)、15(Optimum)はすべて同じようにデコードされる:デコーダが従うべきなのは各行の先頭にあるタグバイトだ。このレイアウトの帰結は、意味論と同じくらい重要である。エンコードされた各行は1 + RowBytesバイトの長さであり、入力は行数の分だけ出力を上回る。したがって長さがRowBytes + 1の整数倍でないストリームは、定義上切り詰められている。HotPDFはバイトに触れる前にこの境界をチェックし、4を超えるタグをInvalid PNG predictor row tagで拒否し、二次元の行配列を実体化するのではなく単一の出力バッファから前の行を直接読み取る。フィルタ1と3は現在の行の中でBytesPerPixelだけ遡り、フィルタ2は真上を読み、フィルタ4は左・上・左上に対してPaethの選択を実行する——そしてこの4つすべてはすでに再構築済みの出力に対して動作する。だからこそ上の行はフィルタ済みの入力であってはならず、デコード済みの行でなければならない

uses
  HPDFPredictor;

var
  Filtered, Raster: AnsiString;
  ErrorText: string;
begin
  // /DecodeParms << /Predictor 12 /Colors 3 /BitsPerComponent 8 /Columns 1024 >>
  if HPDFTryDecodePredictor(Filtered, 12, 3, 8, 1024,
       Int64(1024) * 3 * 8192, Raster, ErrorText) then
    ConsumeRaster(Raster)
  else
    LogStreamDefect('predictor', ErrorText);   // no exception, no partial raster
end;

MaxOutputBytes引数は飾りではない。predictorの段階は解凍段階の変装であり、悪意ある、あるいは単に壊れた/Columns値は、わずか数キロバイトの入力を数ギガバイト規模の確保要求に変えてしまう。HotPDFはまず1行あたりのビット数、1行あたりのバイト数、ラスタ全体のサイズをInt64で計算し、オーバーフローするジオメトリを拒否し、呼び出し側が指定した上限を尊重する。画像辞書から導いた実際の上限を渡せば、この失敗モードは顧客のマシンでのメモリ不足ダイアログではなく、ログに残るメッセージになる

なぜTIFF Predictor 2は4ビット画像を破壊するのか

Predictor 2はバイト単位ではなくサンプル単位の水平差分化であり、1、2、4ビットの各成分では複数のサンプルが1バイトを共有するからだ。よくある実装はバイトN-ColorsをバイトNに加算する。これは1成分あたり8ビットのときにはたまたま正しく、それ以外では静かに間違っている。8ビットRGBのスキャンは完璧にデコードされ、そして同じコードが本番環境で4ビットのインデックス画像に初めて出会った瞬間にそれを破壊する

正しい演算はビットフィールドの内側で行われる。HotPDFはインデックスColorsからColors * Columns - 1までサンプルを走査し、適切なシフト位置で(1 shl BitsPerComponent) - 1というマスクを使ってサンプルとその同じ成分の左隣を取り出し、そのマスクを法として加算し、同じバイトに詰まっている他のサンプルを乱すことなく結果を書き戻す。末尾も重要だ:行はバイト境界までパディングされるため、最後のサンプルの後のパディングビットは演算に巻き込まれることなく無傷のまま残らなければならない。1成分あたり16ビットでは各サンプルはビッグエンディアンの2バイト組であり、加算はバイトごとに独立して繰り上がるのではなくペアをまたいで$FFFFで折り返す。8ビットでは単純なバイトの漸化式で正しく、Colorsずつ進むことで赤は赤に対して、アルファはアルファに対して積み上がっていく。どの亜種でも、行の最初のピクセルはリテラルであって差分ではなく、漸化式は各行境界で再開する——TIFF予測は決して上の行を読まない。これがPNG系列との全体的な違いである

LZWDecodeにおいてEarlyChangeが実際に制御するもの

それはリーダーがコードサイズを1ビット広げるタイミングであり、1コードでもずれると後続のすべてが破損する。HotPDFはこの規則を単一の不変条件として表現する:辞書エントリを追加した後、NextCodeが(1 shl CodeSize) - Ord(EarlyChange)に達したら次の読み取りで幅を広げる。ISO 32000-1 §7.4.4のデフォルトである/EarlyChange 1では、この切り替えは1コード早く起こる。/EarlyChange 0では境界ちょうどで起こる。実際のファイルにはどちらも現れ、ビットストリームの中にはエンコーダがどちらを使ったかを教えてくれるものは何もない。状態機械の残りの部分も歩調を合わせて動かなければならない:クリアコードはコードサイズ、ビットマスク、次の空きコード、そしてフレーズ格納をまとめてリセットし、情報終端コードはその瞬間の現在の幅で読まれるのであって、初期の9ビットで読まれるのではない。HotPDFはInitialCodeSizeを9から始め、コードサイズの上限を12に、辞書を4096エントリに制限し、FillOrderのデフォルトをfoTopにする。PDFはコードを上位ビット優先で詰めるからだ——そうしないTIFF形式のストリームのためにfoBottomが存在する

uses
  HPDFLZW;

var
  Decoder: TPDFLZWDecompressor;
  Parms: TPDFLZWParms;
  Plain: AnsiString;
begin
  Decoder := TPDFLZWDecompressor.Create;
  try
    Decoder.EarlyChange := True;      // /EarlyChange 1 is the PDF default
    Decoder.FillOrder := foTop;       // high-order bit first
    Decoder.MaxOutputBytes := 256 * 1024 * 1024;
    Decoder.RequireInitialClear := False;
    Decoder.RequireEndOfInformation := False;

    Parms.Predictor := 12;
    Parms.Colors := 3;
    Parms.BitsPerComponent := 8;
    Parms.Columns := 1024;
    Parms.ExpandedTo8Bit := False;
    Parms.ColorSpace := 'DeviceRGB';

    if Decoder.TryDecompress(RawStreamBytes, Parms, Plain) then
      LogDecodeStats(Decoder.PeakCodeSize, Decoder.DictionaryAdds,
        Decoder.KwKwKExpansions, Decoder.OutputBytes)
    else
      LogStreamDefect('lzw', Decoder.LastError);
  finally
    Decoder.Free;
  end;
end;

これらの統計は見栄えのためではなくトリアージのために存在する。ファイルが正しい長さにデコードされるのにピクセルが間違っているとき、PeakCodeSizeとDictionaryAddsは、リーダーがライターと同じ場所で幅を広げたかどうかを即座に教えてくれる。EarlyChangeを反転させて再度デコードし、2つを比較する:数値が動けば、ビットリーダーを1ステップずつ追いかけるのではなく1回の実行で答えが得られる

KwKwK分岐と、ストリームが単純に失敗すべきとき

違法に見える唯一の合法なケースはCode = NextCodeであり、HotPDFはそれを出力する前にエントリを構築することで処理する。エンコーダは、まさに定義している最中のフレーズのコードを同じステップで出力することがある。これは入力がK w K w Kという形のパターンを含むときに常に起こる。デコーダはそのコードを検索できない。まだ存在しないからだ。そのためPrevious + First(Previous)を構築し、それを新しいエントリとして追加し、たった今作ったそのエントリを出力しなければならない。HotPDFはそれらをKwKwKExpansionsでカウントし、追加したコードが要求されたコードと一致することを相互チェックする。NextCodeを超えるものはすべて破損であり、その場合デコーダは即興で対処するのではなく停止するべきだ:HotPDFは、未来のコード、フレーズのアリーナの外を指す辞書プレフィックス、満杯の辞書、そしてリテラルでない最初のコードに対して例外を発生させる。2つの厳格さスイッチ、RequireInitialClearとRequireEndOfInformationは意図的にデフォルトで無効にしてある。数多くの本番PDFが先頭のクリアコードを省略していたり、終端記号なしにデータが尽きていたりするからだ。自分の出力を検証するときはこれらをオンにし、野良のファイルを取り込むときはオフのままにしておくとよい

読み込まれた文書側で実際に/DecodeParmsが読まれる場所

HotPDFは画像ストリーム辞書上の/DecodeParmsあるいはその省略形である/DPを解決し、辞書か配列のどちらかを受け付け、配列の場合は最後の要素を取り、それからPredictor、Colors、BitsPerComponent、Columns、EarlyChangeをラスタ経路へと運ぶ。配列のケースは人々が忘れがちなものだ:[/ASCII85Decode /FlateDecode]でフィルタされたストリームは並行するパラメータ配列を運び、predictorの設定は最初のフィルタではなく最後のフィルタに属する

var
  Pdf: THotPDF;
  Info: THPDFLoadedImageInfo;
  Bmp: TBitmap;
  I: Integer;
begin
  Pdf := THotPDF.Create(nil);
  try
    if Pdf.LoadFromFile('scanned.pdf', '') > 0 then
      for I := 0 to Pdf.GetLoadedImageCount - 1 do
        if Pdf.GetLoadedImageInfo(I, Info) then
        begin
          Bmp := Pdf.ExtractLoadedImage(I);   // nil when the raster is unusable
          if Bmp <> nil then
          try
            Bmp.SaveToFile(Format('image-%d.bmp', [I]));
          finally
            Bmp.Free;
          end;
        end;
  finally
    Pdf.Free;
  end;
end;

この経路にあった過去の不具合を1つ名指しする価値がある。この種のバグは繰り返されるものだからだ。古いパラメータ付きFlateルーチンは解凍ストリームを作成したうえで、元の圧縮済み入力からコピーしていた。そのためpredictorの段階は圧縮済みのバイト列を受け取り、それを律儀に逆predictしていた:常に間違っており、決して例外も上がらなかった。現在のコードは共有predictorに結果を渡す前にデコーダからだけ読み込み、計算されたサイズより短いラスタは、まだ圧縮されたままのバイト列にフォールバックするのではなく拒否する——このフォールバックは以前、デコード失敗を壊れたビットマップに変えてしまっていた。同じpredictorの実装は今ではクロスリファレンスストリームにも使われており、オブジェクトストリームとインクリメンタル更新にも取り組んでいるなら役立つ一貫性である。周辺の抽出の仕組みは読み込まれた画像とそのデコードフィルタの抽出に関する関連記事で扱っている。DCTDecodeやJPXDecodeとして届く画像はそもそもpredictorには到達しない。それらは独自の圧縮ピクセルモデルを運んでいるからだ

スループット:連続したフレーズアリーナ対エントリごとの文字列

エントリごとの文字列辞書を連続したフレーズアリーナに置き換えたところ、病的な入力に対して約1.61倍高速になった:単一の最長フレーズが7,370,880バイトに達するベンチマークで969MiB/sに対し1558MiB/sである。この入力の形がその差を説明する。古典的な実装は2つの悪いトレードオフのどちらかを選んでしまうからだ。AnsiString値の辞書は最大4096エントリのそれぞれに対して新しい文字列を確保しコピーし、新しいエントリごとに親をまるごとコピーする。プレフィックス/サフィックスのスタックはそのメモリを完全に回避するが、各フレーズをチェーンに沿って1バイトずつ後ろ向きに辿って逆転させることで再構築する。これは普通のテキストなら問題ないが、あるフレーズが数メガバイトにも及ぶと辛くなる。HotPDFは各フレーズを幾何級数的に成長するアリーナに連続して追記し、オフセットと長さでエントリをインデックスし、出力バッファへの単一のMoveでフレーズを出力する。正直に言えばコストはメモリである:すべてのフレーズを丸ごと保持するアリーナは、エントリ数ではなくすべてのフレーズ長の合計によって上限が決まる。だからこそMaxOutputBytesは解凍器とpredictorの両方に存在する。この上限を画像辞書が主張するラスタサイズから導出すれば、嘘をつくストリームは素早く失敗する

ここに示したLZW解凍器、共有predictor、読み込まれた画像の抽出経路は、DelphiとC++Builder向けの標準HotPDF Componentの一部として提供されており、製品ページにはフィルタとDecodeParmsの完全なリファレンスが掲載されている