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

技術記事

DelphiのPDFiumPasで疎な遅延PDFオブジェクトインデックス

PDFium Component

2 GBのPDFから1つの辞書が欲しいのに、ツールはまずトレーラの/Sizeで寸法を決めた配列へ相互参照テーブル全体を展開します。PDFiumPasはこのステップを疎な遅延オブジェクトインデックスに置き換えます。xrefセクション記述子だけを保持し、1つのオブジェクト番号を有界なウィンドウを通してオンデマンドで解決し、実際に触れたエントリだけをキャッシュします

FPdfCompressにおけるこのコードの旧形は誠実でしたが、高くつきました。ApplyDefaultOpenActionはファイル全体を1つのTBytesへ読み込み、それから/Sizeまでのオブジェクト番号ごとに1スロットの密なTPdfActiveXrefEntries配列を割り当てます。大規模では2つが壊れました。呼び出し側が4つの辞書を欲しいだけでも、読み取りコストは文書サイズに線形に増える。そして密な配列はパーサ予算と衝突します。TPdfParserResourceBudget.DefaultはMaxObjectsを4,000,000に設定するので、最高オブジェクト番号がその上限の上に位置する完全に有効なファイルが、正しさではなくメモリの議論で拒否されていました

DelphiにおけるPDFiumPasの疎な遅延オブジェクトインデックスと密な相互参照配列の比較。密な経路はファイル全体を読みトレーラサイズまでのオブジェクト番号ごとに1スロットを割り当て、疎な経路はセクション記述子だけを保持する
メモリに残るのは記述子だけ、エントリはファイルに残り、すべての読み取りは有界な1 MiBウィンドウを通ります

PDFiumの公開APIはなぜこの問いに答えないのか

情報はPDFiumの内側に存在するのに、C境界を越えてこないからです。CPDF_Parserは相互参照テーブル、オブジェクトストリームの所属、リビジョンの優先順位を内部的に保守しますが、公開ヘッダは、オブジェクト番号を受け取りその生のオフセット、ジェネレーション、どのリビジョンが勝ったか、どのObjStmに住むかを返すエントリポイントを露出していません。保存側も同じく閉じています。FPDF_SaveAsCopyとFPDF_SaveWithVersionが渡すのは逐次書き込みコールバックだけです。したがってネイティブ保存後のカタログへのバイト単位のパッチはPascal層で作るしかなく、PDFiumPasがDLLを再利用せずこれらの構造を自前で解析する理由です

疎なインデックスは実際に何をメモリに保持するのか

エントリではなく記述子です。クラシックテーブル（ISO 32000-1 §7.5.4）では、TPdfSparseXrefSubsectionが最初のオブジェクト番号、オブジェクト数、エントリ行が始まるバイトオフセット、実測されたエントリ幅を保存します。エントリ自体はファイルに残ります。幅は20バイトと仮定せず最初の行から実測します。作成者の間で行末が一致しないからです。PDFiumPasは18から64を受け入れ、その帯域の外は何であれ拒否します。宣言された数がストリームの終端を走り抜けるサブセクションも同様です。相互参照ストリーム（§7.5.8）では、セクションは3つの/Wフィールド幅（それぞれ0から8に制約）、フラット化した/Indexペア、デコード済みエントリバイトを保持します。その期待長は、1バイトも展開する前に/Wと/Indexから計算されます

インデックス全体はInitializeによって、最大1 MiBの末尾ウィンドウ——startxrefが見つかる場所——から構築され、以降のオブジェクト読み取りはすべて1 MiBのオブジェクトウィンドウを使います。生ストリームの上限は64 MiBで、1つのxref行は1024バイトを超えられません。PDFiumPasでのオブジェクトストリームと相互参照ストリームの検証のノートを読んだことがあるなら、同じフィールド幅の規律がここでも適用されます。ただし今度はテーブル全体の監査ではなく、1つのエントリのアドレス指定に使われます

uses
  FPdfCompress;

var
  Source: TFileStream;
  Revision: TPdfSparseRevisionInfo;
begin
  Source := TFileStream.Create(FileName, fmOpenRead or fmShareDenyWrite);
  try
    { startxref、/Prevチェーン、カタログだけを歩く }
    if ReadPdfSparseRevisionInfo(Source, Revision) then
    begin
      Writeln('root      ', Revision.RootObjectNumber, ' ',
        Revision.RootGeneration);
      Writeln('max obj   ', Revision.MaximumObjectNumber);
      Writeln('xref str  ', Revision.UsesXrefStream);
      Writeln('encrypted ', Revision.HasEncrypt);
      Writeln(string(Revision.CatalogDictionary));
    end;
  finally
    Source.Free;
  end;
end;

1回のルックアップはどうやって1つのオブジェクトに届くのか

両方のレイアウトで、算術によってです。クラシックサブセクションは固定幅の行を持つので、エントリのアドレスはサブセクション開始＋オブジェクトオフセット×実測幅です。PDFiumPasはその1行を読み、10桁のオフセットと5桁のジェネレーションを解析し、§7.5.4の65535上限に対してジェネレーションを検査し、後続のキーワードをaxkDirectかaxkFreeに分類します。相互参照ストリームはもう1ステップ要ります。/Indexサブセクションがデコード済みバイト列に連結されているからです。インデックスは合計/W幅を掛ける前に先行サブセクションのカウントを累積します。タイプ1はオフセットを生み、タイプ2はオブジェクトストリーム番号とメンバーインデックスを生み、その他は推測ではなくaxkUnknownになります

{ クラシックテーブル、ISO 32000-1 セクション 7.5.4 }
EntryOffset := Subsection.EntryOffset +
  Int64(ObjectNumber - Subsection.FirstObject) * Subsection.EntryWidth;

{ 相互参照ストリーム、ISO 32000-1 セクション 7.5.8 }
EntryWidth := Section.Widths[0] + Section.Widths[1] + Section.Widths[2];
EntryPosition := Integer((PriorCount + ObjectNumber -
  Section.IndexValues[I]) * EntryWidth);

どちらの経路でも、/Sizeに比例するものは何もありません。それがこの書き直しの要点です。トレーラのサイズ値はメタデータとして持ち越され、インクリメンタルリビジョンの書き込み時に使われますが、割り当てを駆動することは決してありません。回帰スイートはこれを、ページツリーがオブジェクト1,000,000,000と1,000,000,001にあり、トレーラが/Size 1000000002を宣言するフィクスチャで固定します。旧密実装はそのファイルを拒否しました。疎インデックスは両方の参照を解決し、出力トレーラに宣言されたサイズを保持します

DelphiでPDFiumPasが1つのオブジェクト番号を解決する方法。クラシック相互参照テーブルは実測行幅を掛け、相互参照ストリームは/W配列の合計フィールド幅を掛ける前に先行サブセクションのカウントを累積する
どちらのルックアップも純粋な算術です。だからトレーラで宣言されたオブジェクト数に比例することはありません

ハイブリッドリビジョン、/Prevチェーンとその周りのガード

リビジョンの優先順位は、素朴な遅延インデックスが間違える場所です。PDFiumPasはstartxrefから新→旧の順にチェーンを歩き、答える最初のセクションでルックアップを止めます。これがマージされたテーブルを実体化せずに優先規則を再現します。ハイブリッド参照ファイル（§7.5.8.4）はクラシック分岐の内側で処理されます。トレーラが/XRefStmを運ぶとき、補助ストリームセクションはそれを参照するクラシックセクションより先に登録されます。だから素のテーブルには見えない圧縮オブジェクトがまだ見つかり、クラシックエントリはその地位を保ちます。より古いリビジョンはその後/Prevを通して追跡されます

2つのガードがその歩行を拘束し、どちらも破損ファイルで効きます。訪れたオフセットはすべて記録されるので、チェーンの中へ逆指す/Prevは回る代わりに終端します。そして走査の深さはMaxRecursionDepth——デフォルト1024——で上限が付けられます。暗号化フラグは最新トレーラだけから読むのではなくチェーン全体にわたって累積されます。最新トレーラが/Encryptを省いていても、より後ろでまだ暗号化されている文書があり得るからです。リビジョンを追記する呼び出し側は、そのフラグに頼って暗号化ファイルへの平文オブジェクトの書き込みを拒否します

DelphiでPDFiumPasがハイブリッドPDFリビジョンチェーンを歩く方法。セクションはstartxrefから新しい順に登録され、補助XRefStmセクションはそれを名指したクラシックテーブルの前に入り、/Prevの歩行は訪問済みオフセットと深さ上限で拘束される
ルックアップは答える最初のセクションで止まります。これがマージテーブルを一度も実体化せずにリビジョン優先を再現します

タイプ2エントリ: オブジェクトストリームが待つ理由

タイプ2エントリはオブジェクトストリームを名指し、PDFiumPasは呼び出し側がそのメンバーを求めるまでそのストリームに触れません。ついに触れるとき、/Type /ObjStmが検証され、/Nはオブジェクト予算に対して、/Firstはデコードバイト上限に対して検査され、各ヘッダペアが最低4バイト要るため/Nは/Firstに対してサニティ検査されます。その後に初めてストリームが展開され、ヘッダ走査は完全なメンバーテーブルを作らず、要求されたメンバーとその後継で止まります。デコード済みオブジェクトストリームは一度に1つだけ保持されます。ページツリーの分岐が1つのObjStmに固まるとき、それが正しいトレードです。展開ステップの内側で何が起きるかは（§7.5.7）、Delphiでのオブジェクトストリームと予測子デコードの稿が扱います

var
  Reader: TPdfSparseDictionaryReader;
  Generation: Integer;
  Dict: AnsiString;
begin
  { 1つの保持インデックス、多数のジェネレーション対応読み取り }
  Reader := TPdfSparseDictionaryReader.Create(Source);
  try
    if Reader.Valid and
       Reader.ReadLatestDictionary(PageObjectNumber, Generation, Dict) then
      HandlePage(PageObjectNumber, Generation, Dict);
  finally
    Reader.Free;  { Source は呼び出し側のまま }
  end;
end;

キャッシュが約束をやめる場所

インデックスはスナップショットであり、それについて率直である価値があります。セクションはInitializeで一度だけ解析されます。基礎ストリームがその後修正されたら、キャッシュされたエントリはすべて古く、クラスは気づきません。TPdfSparseDictionaryReaderはソースの呼び出し側所有ライフタイムの間インデックスを保持します。ページツリー上の再帰歩行がまさに欲しいものであり、リライトの間にしてはならないことでもあります。エントリキャッシュは線形探索するフラット配列で、否定的な結果も保存します。数百のルックアップは安く、数十万はそうではありません。ReadDictionaryは正確なジェネレーション一致を要求し、ReadLatestDictionaryはアクティブなものを解決します。差は意図的です。参照解決には前者が、カタログ検査には後者が必要です。これらの境界が守れない場所では、周囲のユニットは、まだ動くファイルの集合を狭める代わりに旧来のファイル全体パーサへフォールバックします。大きなPDFのオンデマンドストリーミングでも使うパターンです

クロスコンパイラ回帰は3つのツールチェーンすべてで同じ挙動をカバーします。2 MiBのソースが1 MiBを超える単一の読み取りを決して見ないというアサーションも含みます。PDF構造を直接扱うDelphi、C++Builder、Lazarusコードを保守していて、4つの辞書のためにファイル全体の解析コストを払うのにうんざりしているなら、疎インデックスとその周りの公開シームはPDFiumPas Delphi PDFium Componentに同梱されて出荷されます