Spärlicher Lazy-PDF-Objektindex in Delphi mit PDFiumPas

Man will ein einziges Dictionary aus einer 2-GB-PDF, und das Werkzeug faltet zuerst die komplette Cross-Reference-Tabelle in ein Array auf, dessen Größe der Trailer über /Size vorgibt. PDFiumPas ersetzt diesen Schritt durch einen spärlichen lazy Objektindex: Er behält nur die Xref-Abschnittsdeskriptoren, löst eine einzelne Objektnummer bei Bedarf durch begrenzte Fenster auf und cached genau die Einträge, die man tatsächlich berührt hat

Die alte Gestalt dieses Codes in FPdfCompress war ehrlich, aber teuer. ApplyDefaultOpenAction las die komplette Datei in ein einziges TBytes und allozierte dann ein dichtes TPdfActiveXrefEntries-Array mit einem Slot je Objektnummer bis hinauf zu /Size. Bei Skalierung gingen zwei Dinge schief. Die Lesekosten wuchsen linear mit der Dokumentgröße, selbst wenn der Aufrufer vier Dictionarys wollte, und das dichte Array kollidierte mit dem Parser-Budget: TPdfParserResourceBudget.Default setzt MaxObjects auf 4.000.000, also wurde eine völlig valide Datei, deren höchste Objektnummer über dieser Grenze liegt, mit einem Speicher- statt einem Korrektheitsargument abgelehnt

Warum beantwortet die öffentliche PDFium-API diese Frage nicht?

Weil die Information zwar in PDFium existiert, aber nie über die C-Grenze kommt. CPDF_Parser pflegt die Cross-Reference-Tabelle, die Objektstream-Zugehörigkeit und die Revisions-Präzedenz intern, doch die veröffentlichten Header legen keinen Einsprungpunkt offen, der eine Objektnummer nimmt und ihren Rohversatz, ihre Generation, welche Revision gewonnen hat oder in welchem ObjStm sie lebt, zurückgibt. Die Speicherseite ist genauso geschlossen: FPDF_SaveAsCopy und FPDF_SaveWithVersion reichen nur einen sequenziellen Schreib-Callback heraus. Jeder Byte-Patch am Catalog nach einem nativen Speichern muss daher in der Pascal-Schicht gebaut werden, weshalb PDFiumPas diese Strukturen selbst parst, statt die DLL wiederzuverwenden

Was behält der spärliche Index tatsächlich im Speicher?

Deskriptoren, keine Einträge. Für eine klassische Tabelle (ISO 32000-1 §7.5.4) speichert ein TPdfSparseXrefSubsection die erste Objektnummer, die Objektanzahl, den Byte-Versatz, an dem die Eintragszeilen beginnen, und die gemessene Eintragsbreite. Die Einträge selbst bleiben in der Datei. Die Breite wird an der ersten Zeile gemessen, nicht als 20 Bytes angenommen, weil sich die Erzeuger über Zeilenenden uneinig sind; PDFiumPas akzeptiert 18 bis 64 und weist alles außerhalb dieses Bandes zurück, dazu jede Subsection, deren deklarierte Anzahl über das Stream-Ende hinausliefe. Für einen Cross-Reference-Stream (§7.5.8) hält der Abschnitt die drei /W-Feldbreiten, jeweils auf 0 bis 8 begrenzt, die abgeflachten /Index-Paare und die dekodierten Eintragsbytes, deren erwartete Länge aus /W und /Index berechnet wird, bevor ein einziges Byte aufgeblasen wird

Der ganze Index wird von Initialize aus einem Endfenster von höchstens 1 MiB gebaut, in dem startxref gefunden wird, und jeder folgende Objektlesevorgang benutzt ein 1-MiB-Objektfenster. Die Roh-Stream-Obergrenze liegt bei 64 MiB, und eine einzelne Xref-Zeile darf 1024 Bytes nicht überschreiten. Wer unsere Notiz über das Validieren von Objekt- und Cross-Reference-Streams mit PDFiumPas gelesen hat, erkennt dieselbe Feldbreiten-Disziplin wieder, nur dass sie hier dazu dient, einen einzelnen Eintrag zu adressieren statt eine ganze Tabelle zu prüfen

uses
  FPdfCompress;

var
  Source: TFileStream;
  Revision: TPdfSparseRevisionInfo;
begin
  Source := TFileStream.Create(FileName, fmOpenRead or fmShareDenyWrite);
  try
    { durchläuft nur startxref, die /Prev-Kette und das Catalog }
    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;

Wie erreicht eine Suche ein einzelnes Objekt?

Durch Arithmetik, in beiden Layouts. Eine klassische Subsection hat Zeilen fester Breite, also ist die Adresse eines Eintrags der Subsection-Anfang plus der Objektversatz mal der gemessenen Breite; PDFiumPas liest dann diese eine Zeile, parst den zehnstelligen Versatz und die fünfstelligen Generation, prüft die Generation gegen die 65535-Grenze aus §7.5.4 und stuft das abschließende Schlüsselwort als axkDirect oder axkFree ein. Ein Cross-Reference-Stream braucht einen weiteren Schritt, weil die /Index-Subsections im dekodierten Byte-Run aneinanderhängen, also akkumuliert der Index die Anzahlen der vorhergehenden Subsections, bevor er mit der summierten /W-Breite multipliziert. Typ 1 liefert einen Versatz, Typ 2 eine Objektstream-Nummer und einen Member-Index, und alles andere wird axkUnknown statt einer Vermutung

{ klassische Tabelle, ISO 32000-1 Abschnitt 7.5.4 }
EntryOffset := Subsection.EntryOffset +
  Int64(ObjectNumber - Subsection.FirstObject) * Subsection.EntryWidth;

{ Cross-Reference-Stream, ISO 32000-1 Abschnitt 7.5.8 }
EntryWidth := Section.Widths[0] + Section.Widths[1] + Section.Widths[2];
EntryPosition := Integer((PriorCount + ObjectNumber -
  Section.IndexValues[I]) * EntryWidth);

Nichts in beiden Pfaden ist proportional zu /Size. Das ist der ganze Sinn der Neufassung: Der Trailer-Größenwert wird als Metadatum weitergereicht und beim Schreiben der inkrementellen Revision benutzt, treibt aber nie eine Allokation. Die Regressionssuite nagelt das mit einer Fixture fest, deren Seitenbaum bei den Objekten 1.000.000.000 und 1.000.000.001 unter einem Trailer liegt, der /Size 1000000002 deklariert. Die alte dichte Implementierung lehnte diese Datei ab; der spärliche Index löst beide Referenzen auf und bewahrt die deklarierte Größe im Ausgabe-Trailer

Hybride Revisionen, /Prev-Ketten und die Wachen darum

An der Revisions-Präzedenz geht ein naiver lazy Index schief. PDFiumPas läuft die Kette ab startxref in Neueste-zuerst-Reihenfolge ab und stoppt eine Suche an dem ersten Abschnitt, der antwortet, was die Präzedenzregel reproduziert, ohne eine zusammengeführte Tabelle zu materialisieren. Hybrid-Referenz-Dateien (§7.5.8.4) werden im klassischen Zweig behandelt: Trägt der Trailer ein /XRefStm, wird der ergänzende Stream-Abschnitt vor der klassischen Sektion registriert, die ihn nannte, sodass komprimierte Objekte, die der schlichten Tabelle unsichtbar sind, trotzdem gefunden werden, während die klassischen Einträge ihren Rang behalten. Ältere Revisionen werden danach über /Prev verfolgt

Zwei Wachen begrenzen diesen Lauf, und beide zählen bei beschädigten Dateien. Jeder besuchte Versatz wird vermerkt, also terminiert ein /Prev, der zurück in die Kette zeigt, statt sich zu drehen, und die Traversierungstiefe ist durch MaxRecursionDepth gedeckelt, das standardmäßig 1024 beträgt. Das Verschlüsselungs-Flag wird über die gesamte Kette akkumuliert statt nur aus dem neuesten Trailer gelesen, denn ein Dokument, dessen letzter Trailer /Encrypt weglässt, kann weiter hinten trotzdem verschlüsselt sein; Aufrufer, die Revisionen anhängen, verlassen sich auf dieses Flag, um zu verweigern, Klartext-Objekte in eine verschlüsselte Datei zu schreiben

Typ-2-Einträge: warum der Objektstream wartet

Ein Typ-2-Eintrag nennt einen Objektstream, und PDFiumPas rührt diesen Stream nicht an, bis ein Aufrufer nach einem seiner Member fragt. Wenn es so weit ist, wird /Type /ObjStm verifiziert, /N gegen das Objektbudget geprüft und /First gegen die Dekodierbytes-Grenze, und /N wird gegen /First auf Plausibilität geprüft, denn jedes Header-Paar braucht mindestens vier Bytes. Erst dann wird der Stream aufgeblasen, und der Header-Scan stoppt beim angeforderten Member und seinem Nachfolger, statt eine volle Member-Tabelle zu bauen. Genau ein dekodierter Objektstream wird gleichzeitig vorgehalten, was der richtige Kompromiss ist, wenn ein Seitenbaum-Ast in einem einzigen ObjStm klumpt; unser Beitrag über Objektstream- und Predictor-Dekodierung in Delphi deckt ab, was innerhalb dieses Inflate-Schritts passiert (§7.5.7)

var
  Reader: TPdfSparseDictionaryReader;
  Generation: Integer;
  Dict: AnsiString;
begin
  { ein vorgehaltener Index, viele generationsbewusste Lesevorgänge }
  Reader := TPdfSparseDictionaryReader.Create(Source);
  try
    if Reader.Valid and
       Reader.ReadLatestDictionary(PageObjectNumber, Generation, Dict) then
      HandlePage(PageObjectNumber, Generation, Dict);
  finally
    Reader.Free;  { die Quelle bleibt Eigentum des Aufrufers }
  end;
end;

Wo der Cache aufhört, Versprechen zu geben

Der Index ist ein Schnappschuss, und es lohnt sich, darüber klar zu sprechen. Abschnitte werden einmal in Initialize geparst; wird der zugrunde liegende Stream danach verändert, ist jeder gecachte Eintrag veraltet, und die Klasse wird es nicht bemerken. TPdfSparseDictionaryReader hält den Index über die vom Aufrufer bestimmte Lebensdauer der Quelle, was genau das ist, was ein rekursiver Lauf über einen Seitenbaum will, und genau das, was man über ein Umschreiben hinweg niemals tun darf. Der Eintrags-Cache ist ein flaches Array mit linearer Suche, das auch negative Ergebnisse speichert, also sind ein paar hundert Suchen billig und ein paar hunderttausend nicht. ReadDictionary verlangt eine exakte Generationsübereinstimmung, während ReadLatestDictionary die aktive auflöst, und dieser Unterschied ist absichtlich: Referenzauflösung braucht das erste, Catalog-Inspektion das zweite. Wo diese Grenzen nicht eingehalten werden können, fallen die umgebenden Units auf den Legacy-Ganzdatei-Parser zurück, statt die Menge der funktionierenden Dateien zu schmälern — ein Muster, das wir auch für bedarfsgesteuertes Streaming großer PDFs benutzen

Cross-Compiler-Regressionen decken dasselbe Verhalten auf allen drei Toolchains ab, einschließlich einer Behauptung, dass eine 2-MiB-Quelle nie einen einzigen Lesevorgang über 1 MiB sieht. Wer Delphi-, C++Builder- oder Lazarus-Code pflegt, der PDF-Struktur direkt anfasst, und es leid ist, Ganzdatei-Parse-Kosten für vier Dictionarys zu zahlen, findet den spärlichen Index und die öffentliche Naht darum in der PDFiumPas-Delphi-PDFium-Komponente