PDF-Seitenreihenfolge-Bugs in HotPDF: Physische vs. logische Struktur

Das Symptom trat in einem Seitenkopier-Dienstprogramm auf, das auf der HotPDF-Komponente aufbaute: Wenn man Seite 1 eines dreiseitigen Dokuments anforderte, wurde durchgängig Seite 2 erzeugt. Bei der Überprüfung der Indexierungslogik fand sich kein Fehler. Der Aufruf nutzte einen 0-basierten logischen Index, die Arithmetik war korrekt, die Randbedingungen in Ordnung. Dennoch kam jedes Mal die falsche Seite heraus

Der Bug lag überhaupt nicht im Kopiercode. Er lag darin, wie HotPDF sein internes Seiten-Array beim Laden der Datei aufbaute

Zwei Reihenfolgen, eine Ursache für Verwirrung

Eine PDF-Datei ist eine Sammlung von indirekten Objekten, die jeweils durch eine Objektnummer identifiziert werden. Die Dateistruktur zwingt diese Nummern nicht dazu, die Lesereihenfolge widerzuspiegeln. Objekt 1 kann Seite 2 enthalten; Objekt 20 kann Seite 1 enthalten. Was tatsächlich die Lesereihenfolge definiert, ist der Seitenbaum: eine Hierarchie von /Pages-Wörterbüchern (Dictionaries), deren /Kids-Arrays die Seitenreferenzen in der Sequenz auflisten, wie ein Viewer sie anzeigen sollte (ISO 32000-1 §7.7.3)

Das Dokument, das den Fehler auslöste, hatte folgende Seitenbaum-Struktur:

{ Pages tree root, object 16 }
16 0 obj
<<
  /Type /Pages
  /Count 3
  /Kids [20 0 R   { logical page 1 }
         1 0 R    { logical page 2 }
         4 0 R]   { logical page 3 }
>>
endobj

Zufälligerweise listete die Datei im Bytestrom Objekt 1 und Objekt 4 vor Objekt 20 auf. Jeder Parser, der die indirekten Objekte in der Reihenfolge der Datei durchläuft und sie in ein PageArr einträgt, während er Dictionaries vom Typ "Page" findet, würde bei Objekt 1 an Index 0, Objekt 4 an Index 1 und Objekt 20 an Index 2 enden. Logische Seite 1 sitzt bei PageArr[2]. Fragt man nach dem Seitenindex 0, erhält man stattdessen die logische Seite 2

Genau das taten beide internen Parsing-Pfade von HotPDF. Der traditionelle Pfad, der für PDF 1.3/1.4-Dateien verwendet wird, und der moderne Pfad, der für Dokumente mit Objekt-Streams (PDF 1.5+) verwendet wird, bauten jeweils PageArr auf, indem sie die indirekten Objekte in physischer Dateireihenfolge durchgingen, anstatt der /Kids-Kette zu folgen

Bestätigung der Hypothese

Bevor man eine Lösung anfasst, musste die Diskrepanz bewiesen und nicht nur angenommen werden. Das qpdf-Befehlszeilenwerkzeug macht das ganz einfach:

{ shell }
qpdf --show-pages input.pdf
{ Output reveals Kids order: 20 0 R, then 1 0 R, then 4 0 R }

qpdf --show-object="16 0 R" input.pdf
{ Shows the Pages dictionary with /Kids in reading order }

Das Extrahieren jeder Seite im Einzelnen und das Überprüfen der Dateigrößen bestätigte das Mapping: Das, was PageArr[0] lieferte, war der Inhalt, der zur logischen Seite 2 gehörte, und PageArr[2] enthielt die logische Seite 1. Die zirkuläre Verschiebung war der unumstößliche Beweis. Dies erklärte auch, warum das Problem bei mehreren verschiedenen Quelldokumenten auftrat: Jedes PDF, bei dem die Seitenobjekte zufällig niedrigere Objektnummern als eine frühere logische Seite aufwiesen, löste es aus

Es gibt einen simplen Grund, warum PDFs in diesen Zustand geraten. Inkrementelles Speichern hängt aktualisierte Objekte mit neuen Objektnummern an und belässt die alten Speicherplätze in der Querverweistabelle (Cross-Reference Table) im Nichts. Editoren, die eine Deckseite hinzufügen, fügen diese mit einer hohen Objektnummer ein, unabhängig von ihrer Position im Kids-Array. Einige Generatoren schreiben Seiten einfach in einer Reihenfolge, die für das Content-Streaming günstig ist, statt in der logischen Seitenfolge. Das PDF-Format schreibt ihnen nichts anderes vor

Die Lösung: Dem Kids-Array folgen

Der richtige Ansatz besteht darin, PageArr aufzubauen, indem man die /Kids-Kette vom Katalog-Root abwärts durchgeht, und nicht durch das Scannen von indirekten Objekten. Nachdem beide Parsing-Pfade ihren anfänglichen Durchlauf abgeschlossen haben, löst ein Nachbearbeitungsschritt die logische Reihenfolge auf:

procedure THotPDF.ReorderPageArrByPagesTree;
var
  PagesObj  : THPDFDictionaryObject;
  KidsArray : THPDFArrayObject;
  NewPageArr: array of THPDFDictArrItem;
  I, J, PageIndex, KidsIndex: Integer;
  RefObj    : THPDFLink;
  PageObjNum: Integer;
  Found     : Boolean;
begin
  { Locate root /Pages dictionary via FRootIndex }
  PagesObj := FindPagesRootFromCatalog;
  if PagesObj = nil then Exit;

  KidsIndex := PagesObj.FindValue('Kids');
  if KidsIndex < 0 then Exit;
  KidsArray := THPDFArrayObject(PagesObj.GetIndexedItem(KidsIndex));

  SetLength(NewPageArr, KidsArray.Items.Count);
  PageIndex := 0;

  for I := 0 to KidsArray.Items.Count - 1 do
  begin
    RefObj     := THPDFLink(KidsArray.GetIndexedItem(I));
    PageObjNum := RefObj.Value.ObjectNumber;

    Found := False;
    for J := 0 to Length(PageArr) - 1 do
    begin
      if PageArr[J].PageLink.ObjectNumber = PageObjNum then
      begin
        NewPageArr[PageIndex] := PageArr[J];
        Inc(PageIndex);
        Found := True;
        Break;
      end;
    end;
    { Non-page Kids (intermediate /Pages nodes) produce no match; skip }
  end;

  if PageIndex > 0 then
  begin
    SetLength(PageArr, PageIndex);
    for I := 0 to PageIndex - 1 do
      PageArr[I] := NewPageArr[I];
  end;
end;

Der Aufruf erfolgt am Ende jedes Parsing-Pfads, nachdem alle Objekte katalogisiert wurden, aber bevor eine Seitenoperation bedient wird:

{ Traditional path }
ListExtDictionary(THPDFDictionaryObject(IndirectObjects.Items[I]), FPageslink);
ReorderPageArrByPagesTree;
Break;

{ Modern path (object streams) }
if TryParseModernPDF then
begin
  Result := ModernPageCount;
  ReorderPageArrByPagesTree;
  Exit;
end;

Der Neusortierungsschritt verhält sich wie O(n * m), wobei n die Kids-Anzahl und m die aktuelle PageArr-Länge ist. Für jedes Dokument mit einem flachen Seitenbaum (alle Blätter auf Tiefe 1, was die überwältigende Mehrheit der PDFs in der realen Welt abdeckt) sind beide Werte jedoch identisch und die Kosten vernachlässigbar. Tief verschachtelte Seitenbäume erfordern anstelle des hier gezeigten einstufigen Ansatzes einen rekursiven Durchlauf; die produktive Implementierung behandelt diesen Fall separat

Verwendung von CopyPageFromDocument nach dem Fix

Mit ReorderPageArrByPagesTree an Ort und Stelle funktionieren logische Seitenindizes wie erwartet. Die übergeordnete Funktion CopyPageFromDocument akzeptiert einen 0-basierten logischen Index und kopiert die richtige Seite in das Zieldokument:

var
  Source, Dest: THotPDF;
begin
  Source := THotPDF.Create(nil);
  Dest   := THotPDF.Create(nil);
  try
    Source.LoadFromFile('source.pdf');

    Dest.FileName := 'extracted.pdf';
    Dest.BeginDoc;

    { Copy logical page 0 (first page the user sees) }
    Dest.CopyPageFromDocument(Source, 0, 0);

    Dest.EndDoc;
  finally
    Source.Free;
    Dest.Free;
  end;
end;

CopyPageFromDocument fragt intern die Seitenbaumreihenfolge ab, statt sich auf den rohen PageArr-Index zu verlassen. Dadurch verhält es sich selbst bei Dokumenten, in denen physische und logische Reihenfolge abweichen, korrekt. Für Stapelverarbeitungen (Batch-Operationen) akzeptiert InsertPagesFromDocument ein Array logischer Indizes und kopiert sie in einem Durchgang

Was dies über PDF-Parsing verrät

Die PDF-Spezifikation ist eindeutig: Die logische Seitenreihenfolge wird durch das /Kids-Array des Seitenbaums definiert, nicht durch Objektnummern oder Byte-Offsets (ISO 32000-1 §7.7.3.2). Jeder Parser, der eine andere Reihenfolge als Abkürzung verwendet, wird bei der Mehrheit der Dokumente, die er sieht, richtige Ergebnisse erzielen, weil die meisten Generatoren Seiten in der natürlichen Reihenfolge schreiben und aufeinanderfolgende Objektnummern vergeben. Der Fehler bleibt verborgen, bis jemand ein PDF lädt, das inkrementell bearbeitet, von einem anderen Tool umorganisiert oder von Software generiert wurde, die sich für ein anderes Layout entschieden hat

Tests, die nur gegen selbst generierte PDFs durchgeführt werden, verfehlen diese Fehlerklasse völlig. Der Fix für eine Seitenreihenfolge-Regression erfordert daher einen Korpus von Dokumenten aus unterschiedlichen Quellen: inkrementelles Speichern, gescannte Dokumente mit eingefügten Deckblättern, PDFs, die von Tools produziert wurden, welche den Objektgraphen anders linearisieren oder optimieren. Ein Dokument, das den ursprünglichen Fehler ausgelöst hat, sollte dauerhaft in der Regressions-Suite verbleiben

Die Seite HotPDF Component deckt die vollständige API für Seitenoperationen ab, einschließlich CopyPageFromDocument, InsertPagesFromDocument und MovePage