Γρήγορη συγχώνευση PDF στο Delphi: μετατόπιση αναφορών σε επίπεδο byte

Η συγχώνευση PDF ακούγεται σαν κάτι που θα έπρεπε να είναι φθηνό. Το περιεχόμενο των σελίδων είναι ήδη τοποθετημένο, οι γραμματοσειρές είναι ήδη ενσωματωμένες, οι εικόνες είναι ήδη συμπιεσμένες. Κατ' αρχήν, μια συγχώνευση είναι απλώς λογιστική: ξαναρίθμησε τα αντικείμενα ώστε να σταματήσουν να συγκρούονται οι χώροι αρίθμησης των δύο αρχείων, ένωσε τα page trees, διόρθωσε τον cross-reference πίνακα και γράψε το αποτέλεσμα. Στην πράξη, όμως, ο περισσότερος κώδικας συγχώνευσης πετάει αυτή την ευκολία. Για κάθε αντικείμενο σε κάθε αρχείο εισόδου κάνει πλήρη ανάλυση σε δέντρο αντικειμένων με tokens, αλλάζει μερικές έμμεσες αναφορές και μετά σειριοποιεί ξανά το δέντρο σε bytes. Η ανάλυση και η επανασειριοποίηση είναι τα ακριβά μισά, και για τη συντριπτική πλειονότητα των αντικειμένων παράγουν μια ακολουθία bytes σχεδόν ίδια με αυτή που μπήκε

Το PDFlibPas είναι μια εγγενής μηχανή PDF σε Object Pascal για Delphi και C++Builder, και η γρήγορη διαδρομή συγχώνευσης υπάρχει για να παρακάμπτει αυτό το πέρασμα όπου είναι αποδεδειγμένα ασφαλές. Η ιδέα είναι στενή, αλλά αποδίδει σε ολόκληρα σύνολα εγγράφων: για ένα αμετάβλητο μη ροής αντικείμενο, πάρε τα αρχικά bytes του πηγαίου αρχείου αυτούσια και κάνε μία μόνο επεξεργασία σε επίπεδο byte στις έμμεσες αναφορές που περιέχουν, μετατρέποντας κάθε N G R σε (N+Offset) G R. Το άρθρο αυτό εξηγεί πού είναι νόμιμη αυτή η συντόμευση, τη state machine του parser που κάνει την επανεγγραφή των bytes χωρίς να αλλοιώνει τίποτα, γιατί η συγχώνευση των σελιδοδεικτών χρειάστηκε εντελώς διαφορετικό μηχανισμό και πώς η συνηθισμένη διαδρομή συγχώνευσης ξαναχτίστηκε ταυτόχρονα από τετραγωνική σε γραμμική

Γιατί η επαναρίθμηση αντικειμένων είναι το πραγματικό κόστος μιας συγχώνευσης

Κάθε PDF έχει τον δικό του χώρο αρίθμησης αντικειμένων. Το αρχείο A έχει αντικείμενο 1, αντικείμενο 2 κ.ο.κ., ενώ το αρχείο B έχει τον δικό του αντικείμενο 1, αντικείμενο 2 κ.ο.κ. Δεν μπορείς να ρίξεις τα αντικείμενα του B στο αρχείο του A χωρίς αλλαγές, επειδή οι αριθμοί θα συγκρούονταν και κάθε έμμεση αναφορά μέσα στο B θα κατέληγε να δείχνει στο λάθος αντικείμενο. Η λύση είναι μια μετατόπιση: αν το A τελειώνει με πλήθος αντικειμένων Offset, τότε το αντικείμενο N του B γίνεται αντικείμενο N+Offset στην έξοδο, και κάθε αναφορά N G R που εμφανίζεται οπουδήποτε μέσα στα αντικείμενα του B πρέπει να μετατοπιστεί σε (N+Offset) G R ώστε να ταιριάξει

Αυτή η μετατόπιση είναι ολόκληρη η σημασιολογική δουλειά της συγχώνευσης του σώματος. Οι διορθώσεις στο page tree και η συγχώνευση του AcroForm είναι μικρές, περιορισμένες επεμβάσεις σε λίγα αντικείμενα. Η κύρια εργασία είναι η επανεγγραφή αναφορών σε χιλιάδες αντικείμενα, και ο αφελής τρόπος να γίνει είναι να αναλύσεις κάθε αντικείμενο ώστε να βρεις τις αναφορές δομικά. Η MergeFileListFast παίρνει την αντίθετη θέση: οι αναφορές μπορούν να εντοπιστούν και στα raw bytes, αν είσαι προσεκτικός με τα συμφραζόμενα όπου μια ακολουθία digit-space-digit-space-R είναι not μια αναφορά. Παράλειψε την ανάλυση, μετατόπισε επιτόπου και το κόστος ανά αντικείμενο καταρρέει σε μία γραμμική σάρωση bytes που έτσι κι αλλιώς θα αντέγραφες

Πότε η επαναχρησιμοποίηση των bytes της πηγής είναι αποδεδειγμένα ασφαλής

Η διαδρομή με τα bytes χρησιμοποιείται μόνο όταν ισχύουν και οι τρεις συνθήκες για το αντικείμενο που αντιγράφεται από ένα ακόλουθο έγγραφο. Αν αποτύχει έστω και μία, το αντικείμενο επιστρέφει μέσω της πλήρους διαδρομής αποκωδικοποίησης και επανασειριοποίησης, οπότε η ορθότητα πάντα υπερισχύει της ταχύτητας:

• Doc2.IsChangedObject(X) είναι False. Αν η μηχανή συγχώνευσης έχει ήδη τροποποιήσει το αντικείμενο στη μνήμη, για παράδειγμα ένα page object του οποίου το /Parent ήταν επαναστοχευμένο, το δέντρο στη μνήμη είναι η πηγή αλήθειας και τα αρχικά bytes είναι παλιά. Μόνο τα αμετάβλητα αντικείμενα πληρούν τις προϋποθέσεις
• Τα bytes της πηγής δεν περιέχουν το streamstreamstream/endstreamLength
• Τα bytes της πηγής δεν περιέχουν ούτε /StructTreeRootStructTreeRoot/StructElemMarkInfo

Η απόφαση ζει στον βρόχο αντιγραφής ανά αντικείμενο. Όταν περνούν και οι τρεις έλεγχοι, τα bytes του αντικειμένου πηγαίνουν κατευθείαν στο ShiftIndRefsInSourcewriterGetObject, μετατοπισμένα με ShiftIndRef, και μετά σειριοποιούνται. Η δομή αυτού του κλάδου αξίζει να τη δεις, επειδή η σειρά των ελέγχων είναι αυτό που τον κρατά ασφαλή

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;

Ένα κενό ObjectData είναι το σήμα ότι η διαδρομή με τα bytes απέρριψε το αντικείμενο. Αυτό το μοναδικό sentinel κρατά τις γρήγορες και αργές διαδρομές συγχρονισμένες: υπάρχει ακριβώς ένα σημείο που αποφασίζει και ακριβώς μία εναλλακτική

Η μηχανή καταστάσεων μετατόπισης αναφορών και οι ακραίες περιπτώσεις της

Μια επανεγγραφή σε bytes των έμμεσων αναφορών είναι παραπλανητικά εύκολο να γίνει λάθος, επειδή R και ακολουθίες ψηφίων εμφανίζονται παντού σε ένα αντικείμενο PDF σε συμφραζόμενα που δεν είναι αναφορές. ShiftIndRefsInSource είναι ένας μικρός, χειρόγραφος σαρωτής που διατρέχει τα bytes μία φορά και ξαναγράφει έναν αριθμό μόνο όταν ακολουθείται, με κενά PDF ανάμεσα στα tokens, από έναν άλλον αριθμό και στη συνέχεια από έναν R οριοθέτη. Οι φτηνές έξοδοι έρχονται πρώτες: αν η μετατόπιση είναι μηδέν ή η πηγή είναι κενή, τα bytes επιστρέφονται αμετάβλητα χωρίς καν να μπει ο σαρωτής

Η ορθότητα του σαρωτή βασίζεται στην αναγνώριση των συμφραζομένων όπου μια ακολουθία που μοιάζει με αναφορά πρέπει να αφεθεί ως έχει. Αυτά είναι τα όρια που είναι πιο εύκολο να παραλειφθούν, και το καθένα χειρίζεται ρητά:

• Λεκτικές συμβολοσειρές που οριοθετούνται από ( και ) αντιγράφονται κατά λέξη, με παρακολούθηση του βάθους εμφώλευσης και σεβασμό της διαφυγής με ανάστροφη κάθετο, ώστε μια διαφυγμένη παρένθεση να μην χαλάσει την καταμέτρηση του βάθους. Μια συμβολοσειρά όπως (see object 3 0 R for details) περιέχει ένα κλασικό μοτίβο αναφοράς που στην πραγματικότητα είναι απλός πεζός λόγος, και πρέπει να επιβιώσει byte προς byte
• Εξαδικές συμβολοσειρές που οριοθετούνται από < και > περνούν χωρίς ερμηνεία. Τα bytes 52 μέσα σε μια εξαδική συμβολοσειρά είναι ο κωδικός ASCII για R, και ένας σαρωτής που αντιμετώπιζε το ωφέλιμο φορτίο hex ως κείμενο θα μπορούσε να κατασκευάσει μια φανταστική αναφορά. Η αρχική << του λεξικού ανιχνεύεται πρώτα, ώστε ένα λεξικό να μην εκληφθεί ως εξαδική συμβολοσειρά
• Αντικείμενα ονομάτων που αρχίζουν με / καταναλώνονται ολόκληρα, από την κάθετο μέχρι το επόμενο κενό ή οριοθέτη. Χωρίς αυτό, ένα όνομα όπως /R (ένα συνηθισμένο κλειδί πόρου) θα μπορούσε να διαβαστεί ως το R μιας αναφοράς
• Σχόλια που εισάγονται από % εκτείνονται μέχρι το τέλος της γραμμής και παραλείπονται ως αδιαφανές κείμενο
• Το τεστ αριθμού-και-μετά-R είναι αυστηρό. Μια αναφορά αναγνωρίζεται μόνο ως N κενό G κενό R με το R να τερματίζεται από κενό, οριοθέτη ή το τέλος της εισόδου. Αν λείπει ο αριθμός γενιάς, ή ένα R ακολουθείται από γράμμα, τα ψηφία εκπέμπονται αμετάβλητα. Αυτό είναι που προστατεύει τον ακέραιο στο /Length 1234 και τους τέσσερις αριθμούς ενός MediaBox από το να αυξηθούν αθόρυβα

Ο πυρήνας αυτού του αυστηρού τεστ διαβάζεται σχεδόν ακριβώς όπως το περιγράφει η φράση των προδιαγραφών:

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;

Μόνο ο αριθμός αντικειμένου ξαναγράφεται· ο αριθμός γενιάς και το ακριβές αρχικό κενό ανάμεσα στα tokens αντιγράφονται αυτούσια, έτσι ώστε η έξοδος να είναι byte-identical με την είσοδο, εκτός από τον έναν ακέραιο που έπρεπε να αλλάξει. Αυτή η ακρίβεια είναι όλο το νόημα - είναι αυτό που κάνει την επαναχρησιμοποίηση των bytes της πηγής ισοδύναμη με μια πλήρη επανασειριοποίηση, όχι απλώς κοντινή σε αυτήν. Η συμπεριφορά καλύπτεται από ένα στοχευμένο σύνολο unit tests που ασκούν γυμνές αναφορές, αναφορές μέσα σε πίνακες, αριθμούς που δεν είναι αναφορές, λεκτικές συμβολοσειρές, εξαδικές συμβολοσειρές και μη μηδενικούς αριθμούς γενιάς με εφαρμοσμένη μετατόπιση

Γιατί οι σελιδοδείκτες δεν μπορούσαν να επαναχρησιμοποιήσουν το AppendOutline

Η συγχώνευση των σελιδοδεικτών πολλών εγγράφων σε ένα ενιαίο δέντρο περιγράμματος μοιάζει με δουλειά για το υπάρχον AppendOutline βοηθητικό, το οποίο ήδη ξέρει πώς να προσαρτά τους σελιδοδείκτες ανώτατου επιπέδου ενός εγγράφου πάνω σε εκείνους ενός άλλου. Είναι το λάθος εργαλείο εδώ, και ο λόγος είναι μια λεπτή αναντιστοιχία επιπέδων.AppendOutline εντοπίζει τον τρέχοντα τελευταίο σελιδοδείκτη κορυφαίου επιπέδου περνώντας τον αναγνώστη πάνω από τα αρχικά bytes του αρχείου. Όμως η γρήγορη συγχώνευση αποθηκεύει τις αλλαγές της σε buffer νέων αντικειμένων μέσω ChangeObject; ο αναγνώστης δεν βλέπει ποτέ αυτές τις αλλαγές. Αν αλυσιδώσεις τρία ή περισσότερα έγγραφα, κάθε προσάρτηση επανασυνδέει τον αρχικό τελευταίο σελιδοδείκτη του πρώτου εγγράφου με το νεότερο έγγραφο, έτσι ώστε όλοι οι ενδιάμεσοι σελιδοδείκτες των εγγράφων να πέφτουν έξω από την αλυσίδα - μόνο το σωρευτικό /Count μένει σωστό, κάτι που κάνει το σφάλμα εύκολο να περάσει απαρατήρητο μέχρι να ανοίξει κάποιος τον πίνακα σελιδοδεικτών

Η γρήγορη διαδρομή το λύνει με μια εισαγωγή δύο φάσεων, βασισμένη σε μεταδεδομένα, που δεν ξαναπερνά ποτέ τον αναγνώστη. Ένα πρώτο πέρασμα σε όλες τις εισόδους συλλέγει, ανά έγγραφο, το αντικείμενο-ρίζα του περιγράμματος και τους αριθμούς γενιάς, τους αριθμούς του πρώτου και του τελευταίου σελιδοδείκτη κορυφαίου επιπέδου, και τον /Count. Από αυτή τη σύνοψη ο κώδικας υπολογίζει τους καθολικούς αριθμούς αντικειμένων για κάθε σύνδεσμο που πρέπει να στήσει - κάθε εγγράφου τον κορυφαίο /Parent προς τη κοινή ρίζα, τον πρώτο σελιδοδείκτη /Prev προς τον τελευταίο του προηγούμενου εγγράφου, και τον τελευταίο σελιδοδείκτη /Next προς τον πρώτο του επόμενου - χρησιμοποιώντας καθαρή αριθμητική των αριθμών αντικειμένων. Πίσω από αυτό υπάρχει ένας περιορισμός στη σειρά εγγραφής: τα αντικείμενα του πρώτου εγγράφου γράφονται πριν ακόμη ανοιχτεί οποιοδήποτε επόμενο έγγραφο, οπότε όλες οι αλλαγές περιγράμματος του πρώτου εγγράφου (ρίζας /Count και /Last, και του παλιού τελευταίου σελιδοδείκτη /Next) πρέπει να μπορούν να εκφραστούν ως αριθμητικές πράξεις που δεν χρειάζονται κανένα μεταγενέστερο έγγραφο διαθέσιμο. Οι αλλαγές κάθε επόμενου εγγράφου εφαρμόζονται επιτόπου αφού ανοιχτεί αλλά πριν γραφτεί, οπότε περνούν μέσα από την ίδια διαδρομή αλλαγής αντικειμένου

Η αμετάβλητη ιδιότητα ευθυγράμμισης των offsets που τα συνδέει όλα

Και η μετατόπιση αναφορών και η εισαγωγή σελιδοδεικτών βασίζονται σε μία αριθμητική αμετάβλητη ιδιότητα, και αυτή είναι η πιο εύθραυστη υπόθεση σε ολόκληρο τον σχεδιασμό. Μια αναφορά που εισάγεται σε επόμενο έγγραφο γράφεται ως αριθμός καθολικού αντικειμένου-στόχου μείον το Offset εκείνου του εγγράφου, ώστε όταν το αντικείμενο μετατοπιστεί αργότερα κατά ShiftIndRef(Offset) η τιμή να καταλήξει στον επιθυμητό καθολικό αριθμό. Το πρώτο έγγραφο παίρνει Offset = 0 και χρησιμοποιεί απευθείας καθολικούς αριθμούς. Για να είναι σωστή αυτή η αφαίρεση, η ακολουθία των offsets που τρέχει κατά την εισαγωγή πρέπει να ταιριάζει με την ακολουθία των offsets που χρησιμοποιείται όταν τα αντικείμενα γράφονται τελικά

Ισχύει, λόγω ενός χαρακτηριστικού του τρόπου που λειτουργούν οι συγχωνεύσεις σελίδων και φορμών: AddPages, AddFields, και AddFieldFonts τροποποιούν μόνο τα υπάρχοντα αντικείμενα του πρώτου εγγράφου - δεν προσθέτουν ποτέ καινούρια. Έτσι ο αριθμός αντικειμένων του πρώτου εγγράφου μένει αμετάβλητος σε όλο το στάδιο συγχώνευσης σελίδων, και το offset κάθε επόμενου εγγράφου (το άθροισμα των αριθμών αντικειμένων όλων των προηγούμενων εγγράφων) μένει σταθερό από την εισαγωγή ως την τελική εγγραφή. Σπάσε αυτό - εισήγαγε ένα στάδιο που δημιουργεί νέο αντικείμενο στη μέση της συγχώνευσης - και κάθε αναφορά σελίδας και σελιδοδείκτη παρακάτω θα είχε απόκλιση ίση με τον αριθμό των αντικειμένων που πρόσθεσες. Η αμετάβλητη ιδιότητα είναι σιωπηλή, αλλά στηρίζει όλο το σύστημα

Τρία σημεία εισόδου πάνω σε μία μηχανή

Η γρήγορη διαδρομή δεν είναι παρακλάδι του κώδικα συγχώνευσης. Στην ίδια γραμμή εργασίας, η μηχανή επιπέδου byte απομονώθηκε σε μία ενιαία εσωτερική ρουτίνα, MergeFileListInternal(ListName, OutputFileName, PreserveStructTree, StrictMode), και τα δημόσια API έγιναν λεπτά περιβλήματα που επιλέγουν δύο flags:

• MergeFileListFast καλεί τη μηχανή με τη διατήρηση του δέντρου δομής απενεργοποιημένη - η πιο λιτή διαδρομή, που απομακρύνει το δέντρο tagged PDF ώστε η διαδρομή byte να εφαρμόζεται στα περισσότερα αντικείμενα
• MergeFileList την καλεί με τη διατήρηση ενεργοποιημένη, ώστε το δέντρο δομής να επιβιώσει και το αποτέλεσμα να παραμείνει ένα χρήσιμο tagged PDF. Αυτή η συνηθισμένη διαδρομή κληρονομεί επίσης τη συγχώνευση σελιδοδεικτών και φορμών για πολλά έγγραφα
• MergeFileListStrict ενεργοποιεί αυστηρή λειτουργία: το πρώτο πέρασμα μεταδεδομένων σταματά στο πρώτο input που δεν αναφέρει καθαρή συγχώνευση, έτσι ώστε να περιλαμβάνονται μόνο τα έγγραφα που είχαν συλλεχθεί πριν από το κακό αρχείο, αντί να παραλείπεται το κακό αρχείο και να συνεχίζει

Η ενοποίηση των διαδρομών επέτρεψε επίσης να ξαναχτιστεί η συνηθισμένη συγχώνευση από ένα ζεύγος O(N²) βρόχων - συγχώνευσε το αρχείο ένα και δύο, συγχώνευσε το αποτέλεσμα με το τρία, και ούτω καθεξής, ξανακάνοντας parse τον αυξανόμενο συσσωρευτή σε κάθε βήμα - σε ένα μοναδικό γραμμικό πέρασμα που ανοίγει κάθε είσοδο μία φορά. Τα δύο καθιερωμένα σημεία εισόδου για δύο αρχεία και δύο ροές, MergeFiles και MergeStreams, δεν έχουν πειραχτεί και παραμένουν διαθέσιμα για καλούντες που πραγματικά θέλουν συγχώνευση ανά ζεύγη

Μια ειλικρινής σημείωση για τη συμπεριφορά του δέντρου δομής, επειδή χτύπησε τη δοκιμαστική σουίτα. Το "drop" της γρήγορης διαδρομής δεν είναι απόλυτο: αφαιρεί την αναφορά του καταλόγου του πρώτου εγγράφου στο /StructTreeRoot, αλλά το ίδιο το αντικείμενο του δέντρου δομής εξακολουθεί να γράφεται ως ορφανό. Έτσι τα bytes της γρήγορης εξόδου εξακολουθούν να περιέχουν τη συμβολοσειρά /StructTreeRoot string, και δεν μπορείς να ξεχωρίσεις τη γρήγορη από την κανονική έξοδο ψάχνοντας για αυτή τη συμβολοσειρά - η πραγματική διαφορά είναι αν ο κατάλογος φτάνει ακόμη στο δέντρο δομής, κάτι που καθορίζει αν το αρχείο εξακολουθεί να είναι ένα πλοηγήσιμο tagged PDF

Πότε να διαλέξεις ποια διαδρομή

Η διαδρομή byte είναι βελτιστοποίηση απόδοσης για τη συναρμολόγηση πολλών εγγράφων όταν δεν χρειάζεται να διατηρηθεί το δέντρο δομής tagged PDF - ομαδοποίηση αναφορών, σειρές καταστάσεων, μαζική συνένωση. Σε επαναλαμβανόμενες συγχωνεύσεις μεσαίων έως μεγάλων συνόλων εισόδου, η επαναχρησιμοποίηση byte μείωσε τον χρόνο πραγματικής εκτέλεσης κατά περίπου τέσσερα έως δεκατρία τοις εκατό ανάλογα με το μείγμα αντικειμένων, χωρίς νέα σφάλματα σε μικρές ή κακοσχηματισμένες εισόδους, επειδή κάθε αντικείμενο που ο σαρωτής δεν μπορεί να αποδείξει ασφαλές πέφτει πίσω στην πλήρη ανάλυση. Αν χρειάζεσαι το δέντρο δομής άθικτο για λόγους προσβασιμότητας, χρησιμοποίησε τη συνηθισμένη tagged-PDF διαδρομή συγχώνευσης, η οποία το διατηρεί, και αν δουλεύεις με πολύ μεγάλα μεμονωμένα αρχεία αντί για πολλές εισόδους, οι τεχνικές αντιγραφής byte που περιγράφονται στο συνοδευτικό κείμενο για συγχώνευση και διαίρεση μεγάλων PDF με άμεση πρόσβαση στο αρχείο να εφαρμόσετε την ίδια φιλοσοφία «αντιγράψτε bytes, αποφύγετε ολόκληρο το δέντρο αντικειμένων» σε κλίμακα αρχείου

Οι ρουτίνες συγχώνευσης και οι γρήγορες και αυστηρές παραλλαγές τους αποτελούν μέρος του PDFlibPas Delphi PDF Library, της οποίας η τεκμηρίωση περιλαμβάνει την πλήρη αναφορά για το file-list API και τις επιλογές συγχώνευσης που περιγράφονται εδώ