Αραιό ευρετήριο αντικειμένων PDF σε Delphi με PDFiumPas

Θέλετε ένα λεξικό από ένα PDF 2 GB και το εργαλείο πρώτα αναπτύσσει όλο τον πίνακα σταυροαναφορών σε έναν πίνακα μεγέθους βάσει του /Size του trailer. Το PDFiumPas αντικαθιστά αυτό το βήμα με ένα αραιό lazy ευρετήριο αντικειμένων: κρατά μόνο τους περιγραφείς των τμημάτων xref, επιλύει έναν αριθμό αντικειμένου κατ' απαίτηση μέσα από οριοθετημένα παράθυρα και αποθηκεύει στην κρυφή μνήμη μόνο τις εγγραφές που όντως αγγίξατε

Η παλιά μορφή αυτού του κώδικα στο FPdfCompress ήταν ειλικρινής αλλά ακριβή. Το ApplyDefaultOpenAction διάβαζε ολόκληρο το αρχείο σε ένα TBytes και μετά δεσμέυε έναν πυκνό πίνακα TPdfActiveXrefEntries με μία θέση ανά αριθμό αντικειμένου έως το /Size. Σε μεγάλη κλίμακα δύο πράγματα πήγαιναν στραβά. Το κόστος ανάγνωσης μεγάλωνε γραμμικά με το μέγεθος του εγγράφου ακόμη κι όταν ο καλών ήθελε τέσσερα λεξικά, και ο πυκνός πίνακας συγκρουόταν με τον προϋπολογισμό του parser: το TPdfParserResourceBudget.Default ορίζει το MaxObjects σε 4.000.000, οπότε ένα απολύτως έγκυρο αρχείο του οποίου ο μεγαλύτερος αριθμός αντικειμένου βρίσκεται πάνω από αυτό το όριο απορριπτόταν με επιχείρημα μνήμης και όχι ορθότητας

Γιατί το δημόσιο API του PDFium δεν απαντά σε αυτή την ερώτηση;

Επειδή η πληροφορία υπάρχει μέσα στο PDFium αλλά δεν διασχίζει ποτέ το όριο της C. Το CPDF_Parser διατηρεί εσωτερικά τον πίνακα σταυροαναφορών, τη συμμετοχή στα object streams και την προτεραιότητα των αναθεωρήσεων, ωστόσο τα δημοσιευμένα headers δεν εκθέτουν κανένα σημείο εισόδου που να δέχεται έναν αριθμό αντικειμένου και να επιστρέφει το ακατέργαστο offset του, τη γενιά του, ποια αναθεώρηση κέρδισε ή σε ποιο ObjStm κατοικεί. Η πλευρά της αποθήκευσης είναι εξίσου κλειστή: τα FPDF_SaveAsCopy και FPDF_SaveWithVersion σας δίνουν μόνο ένα διαδοχικό callback εγγραφής. Κάθε διόρθωση σε επίπεδο byte σε έναν κατάλογο μετά από εγγενή αποθήκευση πρέπει επομένως να χτίζεται στο στρώμα Pascal, γι' αυτό το PDFiumPas αναλύει μόνο του αυτές τις δομές αντί να επαναχρησιμοποιεί τη DLL

Τι κρατά πράγματι στη μνήμη το αραιό ευρετήριο;

Περιγραφείς, όχι εγγραφές. Για έναν κλασικό πίνακα (ISO 32000-1 §7.5.4) ένα TPdfSparseXrefSubsection αποθηκεύει τον πρώτο αριθμό αντικειμένου, το πλήθος των αντικειμένων, τη μετατόπιση byte όπου ξεκινούν οι γραμμές εγγραφών και το μετρημένο πλάτος εγγραφής. Οι ίδιες οι εγγραφές μένουν στο αρχείο. Το πλάτος μετριέται από την πρώτη γραμμή αντί να θεωρείται δεδομένο στα 20 bytes, επειδή οι παραγωγοί διαφωνούν για τα line endings· το PDFiumPas δέχεται από 18 έως 64 και απορρίπτει οτιδήποτε εκτός αυτού του εύρους, μαζί με κάθε υποενότητα της οποίας ο δηλωμένος αριθμός θα ξεπερνούσε το τέλος της ροής. Για ένα cross-reference stream (§7.5.8) η ενότητα κρατά τα τρία πλάτη πεδίων του /W, καθένα περιορισμένο από 0 έως 8, τα πεπλατυσμένα ζεύγη του /Index και τα αποκωδικοποιημένα bytes των εγγραφών, των οποίων το αναμενόμενο μήκος υπολογίζεται από το /W και το /Index πριν αποσυμπιεστεί έστω ένα byte

Όλο το ευρετήριο χτίζεται από το Initialize μέσα από ένα παράθυρο ουράς έως 1 MiB, όπου βρίσκεται το startxref, και κάθε επόμενη ανάγνωση αντικειμένου χρησιμοποιεί ένα παράθυρο αντικειμένου 1 MiB. Το ανώτατο όριο της ακατέργαστης ροής είναι 64 MiB και μία γραμμή xref δεν μπορεί να ξεπερνά τα 1024 bytes. Αν έχετε διαβάσει τη σημείωσή μας για την επικύρωση object και cross-reference streams με PDFiumPas, η ίδια πειθαρχία πλάτους πεδίων ισχύει και εδώ, απλώς τώρα χρησιμοποιείται για να διευθυνσιοδοτήσει μία εγγραφή αντί να ελέγξει έναν ολόκληρο πίνακα

uses
  FPdfCompress;

var
  Source: TFileStream;
  Revision: TPdfSparseRevisionInfo;
begin
  Source := TFileStream.Create(FileName, fmOpenRead or fmShareDenyWrite);
  try
    { περνά μόνο από το startxref, την αλυσίδα /Prev και τον κατάλογο }
    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;

Πώς φτάνει μία αναζήτηση σε ένα αντικείμενο;

Με αριθμητική, και στις δύο διατάξεις. Μια κλασική υποενότητα έχει γραμμές σταθερού πλάτους, οπότε η διεύθυνση μιας εγγραφής είναι η αρχή της υποενότητας συν η μετατόπιση του αντικειμένου επί το μετρημένο πλάτος· το PDFiumPas μετά διαβάζει αυτή τη μία γραμμή, αναλύει το offset δέκα ψηφίων και τη γενιά πέντε ψηφίων, ελέγχει τη γενιά ως προς το ανώτατο όριο 65535 από το §7.5.4 και ταξινομεί την τελική λέξη-κλειδί ως axkDirect ή axkFree. Ένα cross-reference stream χρειάζεται ένα ακόμη βήμα επειδή οι υποενότητες του /Index είναι συνενωμένες στην αποκωδικοποιημένη ακολουθία bytes, οπότε το ευρετήριο αθροίζει τα πλήθη των προηγούμενων υποενοτήτων πριν πολλαπλασιάσει με το συνολικό πλάτος του /W. Ο τύπος 1 δίνει μια μετατόπιση, ο τύπος 2 δίνει έναν αριθμό object stream και ένα ευρετήριο μέλους, και οτιδήποτε άλλο γίνεται axkUnknown αντί για εικασία

{ κλασικός πίνακας, ISO 32000-1 ενότητα 7.5.4 }
EntryOffset := Subsection.EntryOffset +
  Int64(ObjectNumber - Subsection.FirstObject) * Subsection.EntryWidth;

{ cross-reference stream, ISO 32000-1 ενότητα 7.5.8 }
EntryWidth := Section.Widths[0] + Section.Widths[1] + Section.Widths[2];
EntryPosition := Integer((PriorCount + ObjectNumber -
  Section.IndexValues[I]) * EntryWidth);

Τίποτα σε καμία από τις δύο διαδρομές δεν είναι αναλογικό του /Size. Αυτό είναι όλο το νόημα της ανακατασκευής: η τιμή μεγέθους του trailer μεταφέρεται ως μεταδεδομένα και χρησιμοποιείται κατά την εγγραφή της επαυξημένης αναθεώρησης, αλλά δεν οδηγεί ποτέ σε δέσμευση μνήμης. Η σουίτα regressions το καρφώνει με ένα fixture του οποίου το δέντρο σελίδων ζει στα αντικείμενα 1.000.000.000 και 1.000.000.001 κάτω από ένα trailer που δηλώνει /Size 1000000002. Η παλιά πυκνή υλοποίηση αρνιόταν αυτό το αρχείο· το αραιό ευρετήριο επιλύει και τις δύο αναφορές και διατηρεί το δηλωμένο μέγεθος στο trailer εξόδου

Υβριδικές αναθεωρήσεις, αλυσίδες /Prev και οι ασφάλειες γύρω τους

Η προτεραιότητα των αναθεωρήσεων είναι εκεί όπου ένα αφελές lazy ευρετήριο κάνει λάθος. Το PDFiumPas διασχίζει την αλυσίδα από το startxref με σειρά από το νεότερο και σταματά μια αναζήτηση στην πρώτη ενότητα που απαντά, κάτι που αναπαράγει τον κανόνα προτεραιότητας χωρίς να υλοποιεί έναν συγχωνευμένο πίνακα. Τα αρχεία hybrid-reference (§7.5.8.4) χειρίζονται μέσα στον κλασικό κλάδο: όταν το trailer μεταφέρει /XRefStm, η συμπληρωματική ενότητα ροής καταχωρείται πριν από την κλασική ενότητα που την ανέφερε, ώστε τα συμπιεσμένα αντικείμενα αόρατα στον απλό πίνακα να εξακολουθούν να βρίσκονται ενώ οι κλασικές εγγραφές κρατούν τη θέση τους. Οι παλαιότερες αναθεωρήσεις ακολουθούνται στη συνέχεια μέσω /Prev

Δύο ασφάλειες οριοθετούν αυτή τη διαδρομή, και οι δύο μετράνε σε κατεστραμμένα αρχεία. Κάθε offset που επισκέπτεται καταγράφεται, οπότε ένα /Prev που δείχνει πίσω στην αλυσίδα τερματίζει αντί να στριφογυρίζει, και το βάθος διάσχισης περικόπτεται από το MaxRecursionDepth, που από προεπιλογή είναι 1024. Η σημαία κρυπτογράφησης αθροίζεται σε όλη την αλυσίδα αντί να διαβάζεται μόνο από το νεότερο trailer, επειδή ένα έγγραφο του οποίου το τελευταίο trailer παραλείπει το /Encrypt μπορεί ακόμη να είναι κρυπτογραφημένο πιο πίσω· οι καλούντες που προσθέτουν αναθεωρήσεις βασίζονται σε αυτή τη σημαία για να αρνηθούν την εγγραφή αντικειμένων απλού κειμένου σε κρυπτογραφημένο αρχείο

Εγγραφές τύπου 2: γιατί το object stream περιμένει

Μια εγγραφή τύπου 2 ονομάζει ένα object stream, και το PDFiumPas δεν αγγίζει αυτή τη ροή μέχρι ένας καλών να ζητήσει ένα μέλος της. Όταν επιτέλους το κάνει, το /Type /ObjStm επαληθεύεται, το /N ελέγχεται ως προς τον προϋπολογισμό αντικειμένων και το /First ως προς το όριο αποκωδικοποιημένων bytes, και το /N ελέγχεται λογικά έναντι του /First αφού κάθε ζεύγος header χρειάζεται τουλάχιστον τέσσερα bytes. Μόνο τότε η ροή αποσυμπιέζεται, και η σάρωση header σταματά στο ζητούμενο μέλος και στον διάδοχό του αντί να χτίσει έναν πλήρη πίνακα μελών. Ένα αποκωδικοποιημένο object stream κρατείται τη φορά, που είναι το σωστό εμπόριο όταν ένας κλάδος δέντρου σελίδων συγκεντρώνεται σε ένα ενιαίο ObjStm· η ανάλυσή μας για την αποκωδικοποίηση object stream και predictor σε Delphi καλύπτει τι συμβαίνει μέσα σε αυτό το βήμα αποσυμπίεσης (§7.5.7)

var
  Reader: TPdfSparseDictionaryReader;
  Generation: Integer;
  Dict: AnsiString;
begin
  { ένα retained ευρετήριο, πολλές αναγνώσεις με επίγνωση γενιάς }
  Reader := TPdfSparseDictionaryReader.Create(Source);
  try
    if Reader.Valid and
       Reader.ReadLatestDictionary(PageObjectNumber, Generation, Dict) then
      HandlePage(PageObjectNumber, Generation, Dict);
  finally
    Reader.Free;  { το Source μένει δικό σας }
  end;
end;

Εκεί όπου η cache σταματά να δίνει υποσχέσεις

Το ευρετήριο είναι ένα στιγμιότυπο, και αξίζει να το λέμε με απόλυτη ευθύτητα. Οι ενότητες αναλύονται μία φορά στο Initialize· αν η υποκείμενη ροή τροποποιηθεί μετά, κάθε αποθηκευμένη εγγραφή είναι παρωχημένη και η κλάση δεν θα το καταλάβει. Το TPdfSparseDictionaryReader κρατά το ευρετήριο για το διάστημα ζωής της πηγής που κατέχει ο καλών, ακριβώς αυτό που θέλει μια αναδρομική διάσχιση δέντρου σελίδων και ακριβώς αυτό που δεν πρέπει να κάνετε σε μια επανεγγραφή. Η cache εγγραφών είναι ένας επίπεδος πίνακας με γραμμική αναζήτηση και αποθηκεύει και αρνητικά αποτελέσματα, οπότε μερικές εκατοντάδες αναζητήσεις είναι φθηνές και μερικές εκατοντάδες χιλιάδες δεν είναι. Το ReadDictionary απαιτεί ακριβή ταύτιση γενιάς ενώ το ReadLatestDictionary επιλύει την ενεργή, και η διαφορά είναι σκόπιμη: η επίλυση αναφορών χρειάζεται το πρώτο, η εξέταση καταλόγου το δεύτερο. Εκεί όπου αυτά τα όρια δεν μπορούν να τηρηθούν, οι γύρω μονάδες επιστρέφουν στον legacy parser ολόκληρου αρχείου αντί να στενέψουν το σύνολο των αρχείων που εξακολουθούν να δουλεύουν, μοτίβο που χρησιμοποιούμε και για το on-demand streaming μεγάλων PDF

Τα regressions cross-compiler καλύπτουν την ίδια συμπεριφορά και στις τρεις εργαλειοθήκες, μεταξύ άλλων με έναν έλεγχο ότι μια πηγή 2 MiB δεν βλέπει ποτέ μία ανάγνωση μεγαλύτερη από 1 MiB. Αν συντηρείτε κώδικα Delphi, C++Builder ή Lazarus που αγγίζει απευθείας τη δομή PDF και έχετε κουραστεί να πληρώνετε κόστη ανάλυσης ολόκληρου αρχείου για τέσσερα λεξικά, το αραιό ευρετήριο και η δημόσια ραφή γύρω του έρχονται στο PDFiumPas Delphi PDFium component