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

技術記事

DelphiでのDuplexスキャン丁合: PDFインターリーブ結合

Delphi PDF Library

Delphi用PDFライブラリPDFlibPasのCollateDocumentsExは、複数の開いているドキュメントを1つのインターリーブされたドキュメントへと結合する。各ラウンドで各ソースからGroupSizeページを追加し、ソースごとのページ範囲リストを受け付け、3-1のような降順範囲をそのソースの反転として扱う。1回の呼び出しで、表面のスタックと反転された裏面のスタックが読み順に変わる

このAPIの背後にあるシナリオはありふれていて非常によくある。片面パスしか持たないシートフィードスキャナーは、スタック全体を表向きで一度に流し、その後オペレーターがスタックを裏返してもう一度流す。結果として2つのPDFができる——表面は順番通り、裏面は逆順だ。ユーザーが求める出力は1つのファイルで、1ページ目の表、1ページ目の裏、2ページ目の表、という順序になる。この記事は、その順序の問題と、その下に潜むリソース重複の罠についてのものだ。関心が単純な連結スループットにある場合はバイトレベルの参照シフトによる高速PDF結合を、入力がメモリに収まらないほど大きい場合はダイレクトアクセスによるギガバイト級PDFの結合と分割を参照してほしい

スキャナーが生む2つのスタック、片方は逆順

丁合(collation)はマージではない。マージはページ範囲を連結するだけだが、丁合はそれらをインターリーブし、そのインターリーブのパターンは入力を生み出した物理デバイスの特性によって決まる。パターンを間違えると、ファイルは少しおかしいのではなく、読めなくなる——1ページおきに別の用紙に属することになる。実際のケースのほとんどは3つの変数で説明できる:ローテーションに含まれるソースの数、各ラウンドで各ソースから来るページ数、そしてどれかのソースを逆順に読む必要があるかどうかだ。CollateDocumentsは最初の2つを、ドキュメントハンドルの単純な配列とGroupSize整数でカバーする。CollateDocumentsExは、セミコロン区切りのページ範囲リストを受け付けることで3つ目をカバーする——各セグメントは1ソースに対応し、空のセグメントはそのソースの全ページを意味し、降順範囲はそれを反転する。どちらの関数も現在選択中のドキュメントの末尾に追記し、成功時は1、何らかの拒否があれば0を返す

なぜ素朴な丁合はファイルサイズを何倍にも膨らませるのか

ソースのオブジェクト番号をターゲットのオブジェクト番号にマップするインポートマップが、コピー呼び出しのたびに再構築され、複数のチャンクから到達可能なものはチャンクごとに1回ずつインポートされてしまうからだ。PDFlibPas内部では、TPDFDocument.CopyPagesFromDocが呼び出しのたびにNewIndObjListをリセットする。このリストだけが、コピー処理がすでに何を持ち込んだかを記憶する唯一の手段だ。10ページの範囲を指定して1回呼べば、全10ページで共有されているフォントは1回だけ埋め込まれる。1ページずつ10回呼べば、同じフォントが10回埋め込まれる。これはテキストドキュメントよりもスキャン画像で遥かに深刻な問題になる。なぜならスキャンページは1枚の大きな画像XObjectであり、共有オブジェクトこそが本当に重いものだからだ——埋め込みICCプロファイル、共有された/DecodeParmsチェーン、全用紙に適用されるスタンプや透かしのフォームXObject、OCRテキストレイヤーのフォント。ラウンドロビン式の丁合を書く素直な方法はラウンドに対するループだが、そのループこそがまさに病的なケースだ

// Do not do this. Each CopyPageRanges call rebuilds the import map,
// so anything the two sources share internally is imported once per
// round instead of once per source.
var
  RoundIndex: Integer;
begin
  for RoundIndex := 1 to 12 do
  begin
    PDF.CopyPageRanges(Fronts, IntToStr(RoundIndex));
    PDF.CopyPageRanges(Backs, IntToStr(13 - RoundIndex));
  end;
end;

12ラウンド、2ソース、24回のインポートマップ。何の警告も出ない。ページ順は正しく、すべてのページは正常にレンダリングされ、唯一の症状は入力の合計より何倍も大きいファイルだ。300ページのバッチジョブでは、この倍率は丸め誤差ではなく、保存期間の予算に収まるアーカイブと収まらないアーカイブの違いになる

一度だけインポートし、その後ページツリーを並べ替える

解決策は、素朴なループが融合させてしまった2つの関心事を分離することだ。コピーはターゲットにどのオブジェクトが存在するかを決め、並べ替えはページツリーのどこにページを配置するかを決める。CollateDocumentsExは各ソースを1回のCopyPagesFromDoc呼び出しでそのソースの完全な範囲について正確に1回だけコピーするので、各ソースは1つのインポートマップを持ち、共有リソースは1回だけ書き込まれる。すべてのソースが取り込まれたあとで初めてインターリーブが行われ、それは完全にTPDFPageTree.MovePageを通じて行われる

ここで重要な意味において、ページの移動は無償である。ISO 32000-1 §7.7.3は、ページツリーを/Kids配列が間接参照を保持し、各ノードの/Countがリーフの合計数を運ぶバランス構造として定義している。ページの再配置は、ある/Kids配列から1つの間接参照を取り除き、別の配列に挿入し、両方の/Count値を調整し、ページの/Parentを付け替えることを意味する。コンテンツストリームには一切触れず、リソースは重複せず、オブジェクトも作成されない。ページオブジェクトはオブジェクト番号を保持し続けるため、オブジェクト番号を保持するページ置換で見たのと同じ理由でオブジェクト番号は安定したままになる。素朴なページ移動が誤りがちなもう1点があり、MovePageはそれを間違えない。ISO 32000-1 §7.7.3.4は、/Resources、/MediaBox、/CropBox、/Rotateをページ自体に記載する代わりに祖先ノードから継承することを許している。ノードAからリソースを継承しているページがノードBの下に移動されると、暗黙のうちに別のものを、あるいは何も継承しないことになりかねない。そのためMovePageは再配置の前に継承された値を解決し、ページ辞書に書き込むので、ページは移動をまたいで自分自身の属性を保持し続ける

並べ替えパスは実際には何をしているのか

挿入セマンティクスに対して選択ソートを実行する。目的のブロック相対順序はまず計算される:ローテーション順にソースを巡り、各ソースから最大GroupSize個のインデックスを取り、尽きたソースはスキップし、すべてのページが配置されるまで繰り返す。それが追記されたブロックに対する順列を生む。適用する側は厄介で、MovePageはスワップではなく挿入なので、移動のたびに旧位置と新位置の間にあるものすべてが1つずつずれる

実装では、追記された各ページが現在どこにあるかをモデル化するCurrent配列を保持し、位置Kにあるべきページを前方に走査して見つけ、移動を発行し、その移動がツリーに対して行ったことを反映するよう配列の要素をスライドさせる。配列操作の面ではO(n二乗)だが、オブジェクトコピーはゼロであり、それがこのワークロードにとって正しいトレードオフだ:500ページの丁合は25万回の整数シャッフルであり、画像データの重複コピーは1バイトも発生しない。降順範囲や重複ページはこのパスで特別な扱いを必要としない。なぜならPLParsePageRangeListはソートを無効にし重複を許可した状態で呼ばれるので、要求された順序はパース処理を通じて無傷のまま生き残るからだ

反転範囲と1回呼び出しのduplex結合

反転を範囲として表現すると、フラットベッドの2回パスケースは1回の呼び出しに収まる。表面は自然な順序を望み、裏面は12-1を望み、セミコロンの前の空の最初のセグメントは、最初のソースがその全ページを提供することを意味する

var
  PDF: TPDFlib;
  Target, Fronts, Backs: Integer;
begin
  PDF := TPDFlib.Create;
  try
    Target := PDF.NewDocument;
    if PDF.LoadFromFile('fronts.pdf', '') <> 1 then
      Exit;
    Fronts := PDF.SelectedDocument;
    if PDF.LoadFromFile('backs.pdf', '') <> 1 then
      Exit;
    Backs := PDF.SelectedDocument;
    PDF.SelectDocument(Target);
    // fronts 1..12 in order, backs scanned in reverse: F1 B12 F2 B11 ...
    if PDF.CollateDocumentsEx([Fronts, Backs], ';12-1', 1) = 1 then
      PDF.SaveToFile('duplex.pdf');
  finally
    PDF.Free;
  end;
end;

このスニペットには明示的に述べておく価値のある挙動が2つある。丁合されたページは選択中のドキュメントに追記されるので、NewDocumentで作成されたドキュメントはそれらより前に初期の白紙ページを持ち込むことになり、それが不要なら削除すべきだ。そしてソースの分量が不均一な場合もある:GroupSizeが2で3ページのソースと5ページのソースがあると、ラウンドはA1 A2 B1 B2、続いてAがほぼ尽きた時点でA3 B3 B4、そして最後にB5単独となる。尽きたソースはパディングされるのではなく単純にスキップされるからだ

ロールバック、フォームフィールド、そして持ち越されないもの

あらゆる引数は、ターゲットに手を付ける前に検証される。ドキュメントハンドルの欠落、選択中のドキュメントが自分自身のソースとしてリストされている場合、1未満のGroupSize、ソース数と一致しないセグメント数、そのソースが持っていないページを指定する範囲——これらはすべてターゲットを変更せず0を返す。コピー処理中の失敗はより難しいケースであり、生のPageTree.DeletePagesではなく公開されているDeletePagesを通じて処理される。理由は具体的だ。コピーはMergeFormDataを有効にした状態で実行されるため、後段のソースが失敗する時点で、ソース側のフォームフィールドはすでにターゲットの/AcroForm /Fields配列に追記されている。ページツリーレベルでページを削除すると、ウィジェットのページが取り除かれ、それらのフィールド参照が宙ぶらりんになってしまう。公開されている経路は、ページと並んでフィールド、アウトライン、記事スレッドの参照のリンクも解除する

if PDF.CollateDocumentsEx([Fronts, Backs], ';12-1', 1) = 0 then
  // Nothing was appended and the target is byte-identical to before.
  // 412 is the copy failure; 0 means the arguments were rejected
  // during validation, before any page was touched.
  Log(Format('collate rejected, LastErrorCode=%d', [PDF.LastErrorCode]));

境界について顧客に対して正直であるべきだ。丁合はページと、その注釈とフォームフィールドを運び、AcroFormのフィールドリスト、計算順序の配列、既定のリソース辞書をマージする。ソースのブックマークは運ばない:スキャンされた表面スタックのアウトラインツリーはほとんど常に空なので、duplexのケースでは何も失われないが、著者が作成した2つのドキュメントを丁合する場合、それらのアウトラインは取り残され、ナビゲーションは自分で再構築することになる。ソースカタログにのみ存在していた名前付き宛先も同じ立場にある。顧客に無損失の丁合を約束する前に、これを計画に入れておくべきだ

PDFlibPasは、丁合関数をページ組み立て機能全体の一部として一緒に出荷しており、スキャナーワークフロー、範囲ベースの抽出、大容量ファイルのパスがすべて1つのコンポーネントの下でDelphiとC++Builderから利用できる。完全なAPIリファレンスとトライアルビルドはlosLab Delphi PDFライブラリの製品ページにある