Schnelles Zusammenführen von PDFs in Delphi: Ref-Shifting auf Byte-Ebene

Das Zusammenführen von PDFs klingt so, als sollte es günstig sein. Der Seiteninhalt ist bereits gestaltet, die Schriftarten sind bereits eingebettet, die Bilder sind bereits komprimiert. Im Prinzip ist ein Zusammenführen nur Buchhaltung: Umnummerierung der Objekte, damit die Nummerierungsräume zweier Dateien nicht mehr kollidieren, Zusammenheften der Seitenbäume, Korrektur der Querverweistabelle und Schreiben. In der Praxis wirft der meiste Zusammenführungscode diese Kostengünstigkeit weg. Für jedes Objekt in jeder Eingabedatei wird ein vollständiges Parsen in einen tokenisierten Objektbaum durchgeführt, einige indirekte Referenzen verändert und der Baum dann wieder in Bytes serialisiert. Das Parsen und das Reserialisieren sind die teuren Hälften, und für die überwiegende Mehrheit der Objekte erzeugen sie eine Byte-Sequenz, die fast identisch mit der eingegebenen ist

PDFlibPas ist eine native Object-Pascal-PDF-Engine für Delphi und C++Builder, und ihr schneller Zusammenführungspfad existiert, um diesen Rundtrip überall dort zu überspringen, wo es nachweislich sicher ist. Die Idee ist speziell, aber sie zahlt sich über ganze Dokumentsätze hinweg aus: Für ein unverändertes Nicht-Stream-Objekt werden die ursprünglichen Quell-Bytes wörtlich übernommen und eine einzige Umschreibung der darin enthaltenen indirekten Referenzen auf Byte-Ebene durchgeführt, wodurch jedes N G R in (N+Offset) G R umgewandelt wird. Kein Tokenizer, kein Objektbaum, kein Serialisierer. Dieser Artikel zeigt auf, wo diese Abkürzung zulässig ist, beschreibt die Parser-Zustandsmaschine, die das Umschreiben der Bytes ohne Beschädigung durchführt, erklärt, warum das Zusammenführen von Lesezeichen einen völlig anderen Mechanismus erforderte, und zeigt, wie der normale Zusammenführungspfad gleichzeitig von quadratisch auf linear umgebaut wurde

Warum die Objektumnummerierung die eigentlichen Kosten einer Zusammenführung ausmacht

Jede PDF-Datei enthält ihren eigenen Objektnummerierungsraum. Datei A hat Objekt 1, Objekt 2 usw.; Datei B hat ihr eigenes Objekt 1, Objekt 2 usw. Sie können die Objekte von B nicht unverändert in die Datei von A einfügen, da die Nummern kollidieren würden und jede indirekte Referenz in B nun auf das falsche Objekt verweisen würde. Die Lösung ist ein Offset: Wenn A mit der Objektanzahl Offset endet, wird das Objekt N von B in der Ausgabe zum Objekt N+Offset, und jede Referenz N G R, die irgendwo in den Objekten von B vorkommt, muss auf (N+Offset) G R verschoben werden, um zu passen

Diese Verschiebung ist die gesamte semantische Aufgabe beim Zusammenführen des Rumpfes. Die Anpassungen des Seitenbaums und die Zusammenführung von AcroFormen sind kleine, begrenzte Bearbeitungen an einer Handvoll Objekten. Die Hauptarbeit besteht darin, Referenzen über Tausende von Objekten hinweg umzuschreiben, und der naive Weg besteht darin, jedes Objekt zu parsen, um die Referenzen strukturell zu finden. MergeFileListFast von PDFlibPas vertritt die gegenteilige Ansicht: Die Referenzen sind auch in den rohen Bytes auffindbar, wenn man vorsichtig mit den Kontexten umgeht, in denen eine Ziffer-Leerzeichen-Ziffer-Leerzeichen-R-Sequenz keine Referenz ist. Überspringen Sie das Parsen, verschieben Sie an Ort und Stelle, und die Kosten pro Objekt reduzieren sich auf einen einzigen linearen Scan von Bytes, die Sie sowieso kopiert hätten

Wann die Wiederverwendung von Quell-Bytes nachweislich sicher ist

Der Byte-Pfad wird nur genommen, wenn alle drei Bedingungen für das aus einem nachfolgenden Dokument kopierte Objekt erfüllt sind. Wenn auch nur eine davon fehlschlägt, wird das Objekt wieder über den vollständigen Dekodierungs- und Reserialisierungsweg geschickt, sodass die Korrektheit immer über die Geschwindigkeit siegt:

• Doc2.IsChangedObject(X) ist False. Wenn die Zusammenführungs-Engine das Objekt bereits im Speicher geändert hat (z. B. ein Seitenobjekt, dessen /Parent neu verknüpft wurde), ist der speicherinterne Baum die Quelle der Wahrheit und die ursprünglichen Bytes sind veraltet. Nur unveränderte Objekte sind qualifiziert
• Die Quell-Bytes enthalten kein stream-Schlüsselwort. Der Rumpf eines Stream-Objekts besteht aus binären Daten, die von stream/endstream umschlossen sind. Ein naiver Referenz-Scan über komprimierte oder verschlüsselte Stream-Daten würde bereitwillig Byte-Muster „finden“ und beschädigen, die wie Referenzen aussehen. Stream-Objekte behalten den ursprünglichen Stream-bewussten Pfad bei
• Die Quell-Bytes enthalten weder /StructTreeRoot noch /StructElem. Im schnellen Profil wird der Strukturbaum der taggten PDF verworfen und nicht zusammengeführt. Daher müssen diese Objekte den Dekodierungspfad durchlaufen, in dem die Engine sie gezielt nullen kann

Die Entscheidung fällt in der Kopierschleife pro Objekt. Wenn alle drei Prüfungen bestanden sind, gehen die Bytes des Objekts direkt an ShiftIndRefsInSource und dann an den Writer; andernfalls werden die Bytes verworfen und das Objekt wird mit GetObject neu aufgebaut, mit ShiftIndRef verschoben und serialisiert. Die Struktur dieses Zweigs ist sehenswert, da die Nr. der Prüfungen die Sicherheit gewährleistet:

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;

Ein leeres ObjectData ist das Signal, dass der Byte-Pfad das Objekt abgelehnt hat. Dieser einzelne Wächter verhindert, dass der schnelle und der langsame Weg auseinanderdriften: Es gibt genau eine Stelle, die entscheidet, und genau einen Fallback

Die Referenzverschiebungs-Zustandsmaschine und ihre Randfälle

Ein Byte-Umschreiben indirekter Referenzen ist täuschend leicht falsch zu machen, da R und Ziffernfolgen überall in einem PDF-Objekt in Kontexten vorkommen, die keine Referenzen sind. ShiftIndRefsInSource ist a kleiner handgeschriebener Scanner, der die Bytes einmal durchläuft und eine Zahl nur dann umschreibt, wenn ihr, getrennt durch PDF-Whitespace zwischen den Tokens, eine weitere Zahl und dann ein R-Trennzeichen folgen. Die schnellen Ausstiege kommen zuerst: Wenn das Offset Null oder die Quelle leer ist, werden die Bytes unberührt zurückgegeben, ohne dass der Scanner überhaupt betreten wird

Die Korrektheit des Scanners beruht auf dem Erkennen der Kontexte, in denen eine referenzförmige Sequenz in Ruhe gelassen werden muss. Dies sind die am leichtesten zu übersehenden Grenzen, und jede davon wird explizit behandelt:

• Zeichenfolgenliterale, die durch ( und ) begrenzt sind, werden wortgetreu kopiert, wobei die Verschachtelungstiefe verfolgt und das Backslash-Escape-Zeichen berücksichtigt wird, damit eine maskierte Klammer die Tiefenzählung nicht verfälscht. Eine Zeichenfolge wie (see object 3 0 R for details) enthält ein klassisches Referenzmuster, das in Wirklichkeit nur Fließtext ist, und muss Byte für Byte erhalten bleiben
• Hexadezimalzeichenfolgen, die durch < und > begrenzt sind, werden ohne Interpretation durchgelassen. Die Bytes 52 in einer Hex-Zeichenfolge sind der ASCII-Code für R, und ein Scanner, der Hex-Nutzdaten als Text behandelt, könnte eine Phantomreferenz erzeugen. Das öffnende << eines Dictionarys wird zuerst erkannt, damit ein Dictionary nicht mit einer Hex-Zeichenfolge verwechselt wird
• Namensobjekte, die mit / beginnen, werden im Ganzen verarbeitet, vom Schrägstrich bis zum nächsten Whitespace oder Trennzeichen. Ohne dies könnte ein Name wie /R (ein häufiger Ressourcenschlüssel) als das R einer Referenz gelesen werden
• Kommentare, die mit % eingeleitet werden, laufen bis zum Zeilenende und werden als opaker Text übersprungen
• Der Test „Zahl-dann-R“ ist streng. Eine Referenz wird nur als N Whitespace G Whitespace R erkannt, wobei das R durch Whitespace, ein Trennzeichen oder das Ende der Eingabe abgeschlossen sein muss. Wenn die Generationsnummer fehlt oder auf ein R ein Buchstabe folgt, werden die Ziffern unverändert ausgegeben. Dies schützt die Ganzzahl in /Length 1234 und die vier Zahlen einer MediaBox davor, stillschweigend erhöht zu werden

Der Kern dieses strengen Tests liest sich fast genau so, wie es der Spezifikationssatz beschreibt:

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;

Nur die Objektnummer wird umgeschrieben; die Generationsnummer und the exakte ursprüngliche Whitespace zwischen den Tokens werden durchkopiert, sodass die Ausgabe bis auf die eine Ganzzahl, die geändert werden musste, Byte-identisch mit der Eingabe ist. Diese Präzision ist der springende Punkt — sie macht die Wiederverwendung von Quell-Bytes äquivalent zu einer vollständigen Reserialisierung, nicht nur nah dran. Das Verhalten wird durch einen gezielten Satz von Unit-Tests abgedeckt, die nackte Referenzen, Referenzen innerhalb von Arrays, Nicht-Referenz-Zahlen, Zeichenfolgenliterale, Hex-Zeichenfolgen und von Null verschiedene Generationsnummern mit angewendetem Offset testen

Warum Lesezeichen nicht AppendOutline wiederverwenden konnten

Das Zusammenführen der Lesezeichen mehrerer Dokumente in einen Gliederungsbaum sieht nach einer Aufgabe für den vorhandenen Hilfsdienst AppendOutline aus, der bereits weiß, wie man die Lesezeichen der obersten Ebene eines Dokuments auf ein anderes pfropft. Es ist hier das falsche Werkzeug, und der Grund ist eine subtile Schichtungsdiskrepanz. AppendOutline lokalisiert das aktuell letzte Lesezeichen der obersten Ebene, indem es den Reader über die ursprünglichen Dateibytes laufen lässt. Die schnelle Zusammenführung führt ihre Änderungen jedoch über ChangeObject in einem Puffer für neue Objekte durch; der Reader sieht diese Änderungen nie. Verkettet man drei oder mehr Dokumente, zeigt jedes Anhängen des ursprünglichen letzten Lesezeichens des ersten Dokuments wieder auf das neueste Dokument, sodass alle Lesezeichen der dazwischen liegenden Dokumente aus der Kette herausfallen — nur der kumulative /Count bleibt korrekt, was den Fehler leicht übersehbar macht, bis jemand das Lesezeichen-Panel öffnet

Der schnelle Pfad löst dies mit einer zweiphasigen, Metadaten-gesteuerten Injektion, die den Reader niemals erneut durchläuft. Ein erster Durchgang über alle Eingaben sammelt pro Dokument das Gliederungswurzelobjekt und die Generationsnummern, die Nummern des ersten und letzten Lesezeichens der obersten Ebene sowie das /Count der Wurzel. Aus dieser Zusammenfassung berechnet der Code die globalen Objektnummern jedes Links, den er schmieden muss — das /Parent der obersten Ebene jedes Dokuments zur gemeinsamen Wurzel, das /Prev des ersten Lesezeichens zum letzten des vorherigen Dokuments, das /Next des letzten Lesezeichens zum ersten des nächsten Dokuments — unter Verwendung reiner Objektnummern-Arithmetik. Dahinter steht eine Einschränkung der Schreibreihenfolge: Die Objekte des ersten Dokuments werden ausgeschrieben, bevor ein nachfolgendes Dokument überhaupt geöffnet wird, sodass alle Gliederungsänderungen des ersten Dokuments (Wurzel /Count und /Last sowie das /Next des alten letzten Lesezeichens) als Arithmetik ausdrückbar sein müssen, die kein späteres Dokument benötigt. Die Änderungen jedes nachfolgenden Dokuments werden nach dem Öffnen, aber vor dem Schreiben an Ort und Stelle angewendet, sodass sie über denselben Change-Object-Pfad herausgehen

Die Offset-Ausrichtungs-Invariante, die alles verbindet

Sowohl die Referenzverschiebung als auch die Lesezeicheninjektion hängen von einer arithmetischen Invariante ab, und das ist die fragilste Annahme im gesamten Entwurf. Eine in ein nachfolgendes Dokument injizierte Referenz wird als globale Zielobjektnummer minus dem Offset dieses Dokuments geschrieben, sodass der Wert bei der späteren Verschiebung des Objekts durch ShiftIndRef(Offset) auf der beabsichtigten globalen Nummer landet. Das erste Dokument erhält Offset = 0 and verwendet globale Nummern direkt. Damit diese Subtraktion korrekt ist, muss die während der Injektion verwendete fortlaufende Offset-Sequenz mit der Offset-Sequenz übereinstimmen, die beim endgültigen Ausschreiben der Objekte verwendet wird

Dies ist der Fall aufgrund einer Eigenschaft der Funktionsweise von Seiten- und Formularzusammenführungen: AddPages, AddFields und AddFieldFonts ändern nur die vorhandenen Objekte des ersten Dokuments — sie fügen niemals neue hinzu. Die Objektanzahl des ersten Dokuments bleibt also über die Phasenzusammenführungsphase hinweg unverändert, und das Offset jedes nachfolgenden Dokuments (die summe der Objektanzahlen aller vorherigen Dokumente) bleibt von der Injektion bis zum Ausschreiben stabil. Bricht man dies — führt man einen Schritt ein, der mitten in der Zusammenführung ein neues Objekt erstellt —, würde jede nachgelagerte Seiten- und Lesezeichenreferenz um die Anzahl der hinzugefügten Objekte verschoben. Die Invariante ist still, aber sie ist tragend

Drei Einstiegspunkte über einer Engine

Der schnelle Pfad ist kein Fork des Zusammenführungscodes. In derselben Arbeit wurde die Engine auf Byte-Ebene in eine einzige interne Routine refaktoriert, MergeFileListInternal(ListName, OutputFileName, PreserveStructTree, StrictMode), und die öffentlichen APIs wurden zu dünnen Wrappern, die zwei Flags wählen:

• MergeFileListFast ruft die Engine auf, bei der die Erhaltung des Strukturbaums deaktiviert ist — der schlankste Pfad, bei dem der Strukturbaum der taggten PDF verworfen wird, sodass die Byte-Route auf die meisten Objekte angewendet werden kann
• MergeFileList ruft sie auf, wobei die Erhaltung aktiviert ist, sodass der Strukturbaum erhalten bleibt und das Ergebnis eine verwendbare taggte PDF bleibt. Dieser normale Pfad erbt auch das Zusammenführen von Lesezeichen und Formularen über mehrere Dokumente hinweg
• MergeFileListStrict schaltet den strengen Modus ein: Der erste Metadatendurchlauf stoppt beim ersten Eingang, der keine saubere Zusammenführung meldet, sodass nur die vor der fehlerhaften Datei gesammelten Dokumente einbezogen werden, anstatt die fehlerhafte Datei zu überspringen und fortzufahren

Das Zusammenlegen der Pfade ermöglichte es auch, die normale Zusammenführung von einer paarweisen O(N²)-Schleife — Datei eins und zwei zusammenführen, dieses Ergebnis mit drei zusammenführen usw., wobei der wachsende Akkumulator bei jedem Schritt neu geparst wird — in einen einzigen linearen Durchgang umzubauen, der jede Eingabe einmal öffnet. Die beiden langjährigen Zwei-Datei- und Zwei-Stream-Einstiegspunkte MergeFiles und MergeStreams bleiben unberührt und stehen weiterhin für Aufrufer zur Verfügung, die tatsächlich eine paarweise Zusammenführung wünschen

Ein ehrlicher Hinweis zum Verhalten des Strukturbaums, da dieser die Testsuite beeinträchtigt hat. Das „Verwerfen“ des schnellen Pfads ist nicht vollständig: Es entfernt die Katalogreferenz des ersten Dokuments auf /StructTreeRoot, aber das Strukturbaumobjekt selbst wird immer noch als Waise ausgeschrieben. Die Bytes der schnellen Ausgabe enthalten also immer noch die Zeichenfolge /StructTreeRoot, und Sie können eine schnelle nicht von einer normalen Ausgabe unterscheiden, indem Sie nach dieser Zeichenfolge suchen — der eigentliche Unterschied besteht darin, ob der Katalog den Strukturbaum noch erreicht, was bestimmt, ob die Datei noch eine navigierbare taggte PDF ist

Wann man welchen Pfad wählen sollte

Der Byte-Pfad ist eine Durchsatzoptimierung für das Zusammenstellen vieler Dokumente, bei denen Sie den Strukturbaum der getaggten PDF nicht erhalten müssen — Berichtsbindung, Kontoauszugsläufe, Batch-Verkettung. Gemessen an wiederholten Zusammenführungen mittlerer bis großer Eingabesätze sparte die Byte-Wiederverwendung je nach Objektmischung etwa vier bis dreizehn Prozent der Echtzeit ein, ohne neue Fehler bei kleinen oder fehlerhaften Eingaben, da jedes Objekt, das der Scanner nicht als sicher beweisen kann, auf den vollständigen Parse zurückfällt. Wenn Sie den Strukturbaum für Barrierefreiheit intakt benötigen, verwenden Sie den normalen getaggten PDF-Zusammenführungspfad, der ihn bewahrt; und wenn Sie eher mit sehr großen einzelnen Dateien statt mit vielen Eingaben arbeiten, gelten die Byte-Kopiertechniken, die im Begleitartikel über Zusammenführen und Aufteilen großer PDF-Dateien mit direktem Dateizugriff beschrieben sind, und dieselbe Philosophie „Bytes kopieren, den vollständigen Objektbaum vermeiden“ auf Dateiebene anwenden

Die Zusammenführungsroutinen und ihre schnellen und strengen Varianten sind Teil der PDFlibPas Delphi-PDF-Bibliothek, deren Dokumentation die vollständige Referenz für die Dateilisten-API und die hier beschriebenen Zusammenführungsoptionen enthält