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

技術記事

Delphi で高速 PDF マージ: バイトレベル参照シフト

Delphi PDF Library

PDF の連結は安く済みそうに思えます。ページ内容はすでに配置済みで、フォントは埋め込み済み、画像も圧縮済みです。原理的にはマージは帳尻合わせにすぎません。2 つのファイルの番号空間が衝突しないようオブジェクト番号を振り直し、ページツリーをつなぎ、xref テーブルを直して書き出せば済みます。ところが実際の多くのマージコードは、この安さを自ら捨てています。各入力ファイルの各オブジェクトについて、完全に解析してトークン化されたオブジェクトツリーへ落とし込み、いくつかの間接参照を変更し、そのツリーを再びバイト列へシリアライズします。高くつくのは解析と再シリアライズであり、大半のオブジェクトでは、その結果得られるバイト列は元とほとんど変わりません

PDFlibPas は Delphi と C++Builder 向けのネイティブ Object Pascal PDF エンジンであり、その高速マージ経路は、安全だと証明できる限りこの往復を飛ばすために存在します。発想は限定的ですが、文書集合全体で効いてきます。変更されていない非ストリームオブジェクトについては、元のソースバイトをそのまま使い、その中に含まれる間接参照だけをバイトレベルで 1 回書き換えます。つまりすべての N G R12 0 R(N+Offset) G R12+Offset 0 R

オブジェクト番号の振り直しが、実はマージの主コストです

どの PDF も独自のオブジェクト番号空間を持っています。ファイル A には object 1、object 2 があり、ファイル B にも別の object 1、object 2 があります。B のオブジェクトをそのまま A に落とし込むことはできません。番号が衝突し、B 内のすべての間接参照が誤ったオブジェクトを指すことになるからです。解決策はオフセットです。A のオブジェクト数が Offset まで埋まっているなら、B の object N は出力内で object N+Offset になり、B のオブジェクト内部のどこかに現れる参照 N G RN 0 R(N+Offset) G RN+Offset 0 R

へすべてシフトしなければなりません。MergeFileListFastMergeDocumentsFastではない 参照であるコンテキストに注意すれば、生バイトの中からでも参照は見つけられるという立場を取ります。解析を飛ばし、その場でシフトすれば、オブジェクトごとのコストは、どうせコピーするはずだったバイト列を 1 回線形走査するだけに落ちます

ソースバイトの再利用が安全だと証明できる条件

バイト経路が使われるのは、後続文書からコピーするオブジェクトについて 3 条件すべてが成り立つ場合だけです。どれか 1 つでも外れれば、正しさを優先して完全な decode と reserialize の経路へ戻ります

  • Doc2.IsChangedObject(X)Modified/Parent/Parent
  • streamstreamstreamstreamendstreamendstream や圧縮・暗号化されたストリームデータ上で素朴に参照スキャンをすると、参照に見えるバイト列を見つけて壊してしまうからです。ストリームオブジェクトは従来のストリーム対応経路を維持します
  • /StructTreeRoot/StructTreeRoot/StructParent/StructElem高速プロファイルではタグ付き PDF の構造ツリーをマージせず削除するため、これらのオブジェクトは decode 経路を通して、エンジンが意図的に null 化できるようにしなければなりません

ShiftObjectRefsInRawBytesShiftIndRefsInSourceSerializeObjectExGetObjectShiftAllIndirectRefsShiftIndRefその分岐の構造を見る価値があります。安全性を保っているのは、このチェック順だからです

ObjectData := '';
if not Doc2.IsChangedObject(X) then
begin
  ObjectData := FastMergeObjectSource(Reader2, X);
  if (PLPos('stream', ObjectData) > 0) or
     ((not PreserveStructTree) and (PLPos('/StructTreeRoot', ObjectData) > 0)) or
     ((not PreserveStructTree) and (PLPos('/StructElem', ObjectData) > 0)) then
    ObjectData := ''                                  // fall back to decode
  else
    ObjectData := ShiftIndRefsInSource(ObjectData, Offset);
end;

if ObjectData <> '' then
  Writer.AddObject(X + Offset, Doc2.GetGenNum(X), ObjectData)
else
begin
  Obj := Doc2.GetObject(X, TempStruct);              // full parse path
  // ... null out struct-tree objects, ShiftIndRef, Obj.Output ...
end;

RawBytesObjectData が空であることが、バイト経路がそのオブジェクトを見送った合図です。この 1 つのセンチネルにより、高速経路と低速経路が乖離しません。判断箇所は 1 か所、フォールバックも 1 か所です

参照シフト状態機械とその境界ケース

間接参照をバイト書き換えする処理は、見た目以上に間違えやすいものです。RRShiftIndRefsInSourceShiftObjectRefsInRawBytesRR

スキャナの正しさは、「参照のように見えても触れてはいけないコンテキスト」を見分けることにかかっています。見落としやすい境界はどれも明示的に扱われています

  • リテラル文字列(())(see 12 0 R for details)(see object 3 0 R for details) のような文字列には典型的な参照パターンが含まれますが、実際にはただの文章です。バイト単位で完全に保存されなければなりません
  • 16 32 48 32 8216 32 48 32 82<<>>5212 0 RRASCII の <<<
  • 名前オブジェクト///R12/R12Rコメント
  • %コメント%行末までを不透明テキストとして飛ばします
  • 数値 + R の判定は厳密です。数値N数値GRRRRInteger 12RRRectangle [12 0 200 50]/Length 1234/RectMediaBoxこの厳密な判定の核心は、仕様文の記述をほぼそのままコードにしたものです

オブジェクト番号だけを書き換え、生成番号とトークン間の元の空白はそのまま通します。そのため、入力と出力は変更が必要だった 1 個の整数を除いてバイト単位で一致します。ここが核心です。これにより、ソースバイトの再利用は「だいたい近い」ではなく、完全な再シリアライズと等価になります。挙動は、素の参照、配列内参照、参照ではない数値、リテラル文字列、16 進文字列、非ゼロ生成番号にオフセットを適用した場合を含む、集中的なユニットテスト群でカバーされています

if (P <= N) and (Source[P] = 'R') and
   ((P = N) or PLIsPdfWhite(Source[P + 1]) or PLIsPdfDelimiter(Source[P + 1])) then
  Obj1 := PLStrToIntDef(PLCopy(Source, I, E1 - I), -1);

if Obj1 >= 0 then
begin
  AppendStr(PLIntToStr(Obj1 + Offset));   // shifted object number
  AppendBytes(E1, P - E1);                 // original whitespace + generation
  AppendBytes(P, 1);                       // the 'R'
end;

ブックマークが AppendOutline を再利用できなかった理由

複数文書のブックマークを 1 つのアウトラインツリーへ統合するのは、既存の

AppendOutlineAppendOutline ヘルパーの仕事に見えます。これは一方の文書のトップレベルブックマークをもう一方へ接ぎ木する方法をすでに知っています。しかし、ここでは不適切です。理由は、層のミスマッチが微妙だからです。AppendOutlineAppendOutlineChangeObjectFNewObjects/Count/Count

だけは正しいので、誰かがブックマークパネルを開くまでバグが見逃されやすくなります。/Count/Count/Parent/Parent/Prev/Prev/Next/Next/Count/First/Last/Last/Next/Next

それらを結び付けるオフセット整列の不変条件

後続文書へ注入される参照は 対象のグローバルオブジェクト番号 - その文書の Offset として書かれます。そうしておくと、そのオブジェクトが後で ShiftIndRef(Offset)OffsetOffset = 0Offset = 0

MergePagesAddPagesMergeAcroFormAddFieldsMergeOutlinesAddFieldFonts は第 1 文書の既存オブジェクトを変更するだけで、新しいオブジェクトは追加しません。したがって第 1 文書のオブジェクト数はページマージ段階を通して変わらず、各後続文書のオフセット（それ以前の全ドキュメントのオブジェクト数の総和）は、注入時から書き出し時まで安定します。ここを破り、マージ途中で新しいオブジェクトを作る段階を入れると、その後のすべてのページ参照とブックマーク参照が、追加したオブジェクト数だけずれてしまいます。この不変条件は静かですが、構造を支えています

1 つのエンジンに対する 3 つの入口

高速経路はマージコードのフォークではありません。同じ流れの中で、バイトレベルエンジンは単一の内部ルーチン MergeFileListInternal(ListName, OutputFileName, PreserveStructTree, StrictMode)InternalMergeDocuments

  • MergeFileListFast に整理され、公開 API は 2 つのフラグを選ぶ薄いラッパーになりました
  • MergeFileListMergeDocumentsFast
  • MergeFileListStrict は構造ツリー保存をオフにしてエンジンを呼び出します。もっとも軽い経路であり、タグ付き PDF ツリーを落とすため、バイト経路が最大数のオブジェクトへ適用されます

MergeDocuments は保存をオンにして呼び出し、構造ツリーを生かしたまま、結果を利用可能な tagged PDF として残します。この通常経路は多文書のブックマークおよびフォームマージも受け継ぎます。MergeDocumentsStrictMergeFilesO(N²)MergeStreams ループから、各入力を 1 回だけ開く単一の線形パスへ組み直すこともできました。昔からある 2 ファイル版と 2 ストリーム版の入口、

MergeTwoPDFs/StructTreeRootMergeTwoPDFStreams/StructTreeRoot はそのまま残っており、本当にペアワイズマージが必要な呼び出し側は引き続き使えます

構造ツリーの挙動については、正直に 1 点述べておくべきです。テストスイートもここで引っかかりました。高速経路の「drop」は完全削除ではありません。第 1 文書のカタログから

/StructTreeRoot への参照は外しますが、構造ツリーオブジェクト自体は孤児のまま書き出されます。したがって高速出力のバイト列にも /StructTreeRoot 文字列自体は残ります。文字列検索だけでは高速出力と通常出力を区別できません。本当の違いは、カタログからまだ構造ツリーへ到達できるかどうかであり、それがファイルが依然としてナビゲート可能な tagged PDF かを決めます。どの経路をいつ使うか

バイト経路は、タグ付き PDF の構造ツリーを保持する必要がない多数文書の組み立てに向くスループット最適化です。レポート束ね、明細書の連結、バッチ結合といった用途です。中規模から大規模の入力集合を繰り返しマージして測定すると、オブジェクト構成に応じて壁時計時間をおよそ 4% から 13% 削減しました。小さい入力や壊れた入力で新しい失敗は増えていません。スキャナが安全だと証明できないオブジェクトはすべて完全解析へフォールバックするからです。アクセシビリティのために構造ツリーを保ちたいなら、通常の tagged PDF マージ経路を使ってください。こちらは構造ツリーを保持します。そして、扱うのが多数入力ではなく非常に大きい単一ファイルなら、関連稿