Η σελίδα 1 ενός PDF δεν είναι το αντικείμενο 1. Αυτή η διάκριση είναι η πιο συνηθισμένη πηγή σφαλμάτων εξαγωγής λανθασμένης σελίδας (wrong-page-extracted bugs) στους αναλυτές PDF, και η λύση είναι η ανάγνωση των προδιαγραφών αντί των byte του αρχείου
Αντικείμενα, αναφορές και ο κατάλογος
Ένα αρχείο PDF είναι μια συλλογή αριθμημένων αντικειμένων. Καθένα φέρει έναν μοναδικό αριθμό αντικειμένου και έναν αριθμό γενιάς, γραμμένο ως N G obj, όπου το G είναι σχεδόν πάντα 0 σε αρχεία που δεν έχουν ενημερωθεί σταδιακά. Τα αντικείμενα αναφέρονται το ένα στο άλλο με τον συμβολισμό N G R, επομένως το 3 0 R σημαίνει "η τρέχουσα έκδοση του αντικειμένου 3". Το τρέιλερ δείχνει σε ένα ριζικό αντικείμενο καταλόγου (catalog) του οποίου η καταχώριση /Pages οδηγεί στο δέντρο σελίδων. Οτιδήποτε μπορεί να πλοηγηθεί σε ένα PDF ξεκινά από αυτήν τη ρίζα, όχι από το πρώτο byte του σώματος του αρχείου
Ο πίνακας διασταυρούμενων αναφορών (ή η ροή διασταυρούμενων αναφορών στο PDF 1.5+) αντιστοιχίζει αριθμούς αντικειμένων σε μετατοπίσεις αρχείων (file offsets). Η δουλειά του είναι η τυχαία πρόσβαση, όχι η ταξινόμηση. Ένας συγγραφέας που χτίζει ένα έγγραφο σταδιακά μπορεί να προσαρτήσει νέα αντικείμενα στο τέλος με υψηλότερους αριθμούς, ενώ αυτά τα αντικείμενα λογικά προηγούνται των υπαρχόντων στην ακολουθία της σελίδας. Αυτό δεν είναι ελάττωμα· είναι από τον σχεδιασμό (by design)
Το δέντρο σελίδων (ISO 32000-1 §7.7.3)
Η σειρά των σελίδων ζει στο δέντρο σελίδων. Ο ριζικός κατάλογος περιέχει μια αναφορά /Pages που δείχνει σε έναν κόμβο τύπου /Pages. Ο πίνακας /Kids αυτού του κόμβου παραθέτει τα παιδιά του με σειρά ανάγνωσης. Κάθε παιδί είναι είτε ένας κόμβος-φύλλο τύπου /Page είτε ένας άλλος ενδιάμεσος κόμβος /Pages που περιέχει τα δικά του /Kids. Η Σελίδα 1 είναι το πρώτο φύλλο στο οποίο φτάνει κανείς με μια "κατά βάθος, από αριστερά προς τα δεξιά" (depth-first left-to-right) διάσχιση των πινάκων Kids. Η καταχώριση /Count σε κάθε ενδιάμεσο κόμβο αποθηκεύει προσωρινά τον συνολικό αριθμό των απόγονων σελίδων-φύλλων, ώστε ένας αναγνώστης να μπορεί να μεταβεί στη σελίδα 500 χωρίς να διασχίσει ολόκληρο το δέντρο
Εδώ είναι πώς μοιάζει ένα ελάχιστο δέντρο τριών σελίδων σε ακατέργαστη (raw) σύνταξη PDF:
16 0 obj
<<
/Type /Pages
/Count 3
/Kids [20 0 R 1 0 R 4 0 R]
/MediaBox [0 0 612 792]
>>
endobj
20 0 obj
<< /Type /Page /Parent 16 0 R /Contents 21 0 R /Resources 22 0 R >>
endobj
1 0 obj
<< /Type /Page /Parent 16 0 R /Contents 2 0 R /Resources 3 0 R >>
endobj
4 0 obj
<< /Type /Page /Parent 16 0 R /Contents 5 0 R /Resources 6 0 R >>
endobjΟ πίνακας Kids διαβάζει [20 0 R, 1 0 R, 4 0 R]. Η λογική σελίδα 1 είναι το αντικείμενο 20, η λογική σελίδα 2 είναι το αντικείμενο 1, η λογική σελίδα 3 είναι το αντικείμενο 4. Κάθε κώδικας που επαναλαμβάνει τους αριθμούς αντικειμένων από το 1 και πάνω θα τους συναντήσει με τη σειρά 1, 4, 20 και θα παραγάγει την ακολουθία σελίδα-2, σελίδα-3, σελίδα-1. Το έγγραφο που προκύπτει αποδίδεται σε μια ανακατεμένη σειρά που μπορεί να φαίνεται απολύτως φυσιολογική σε ένα πρόγραμμα προβολής που ακολουθεί το δέντρο, και καταστροφικά λάθος σε ένα που δεν το κάνει
Κληρονομικότητα
Οι ενδιάμεσοι κόμβοι μπορούν να φέρουν ιδιότητες που κληρονομούν οι απόγονοί τους. Οι πιο συνηθισμένες κληρονομημένες καταχωρίσεις είναι τα /MediaBox (διαστάσεις σελίδας), /CropBox, /Resources (γραμματοσειρές και εικόνες), και /Rotate. Μια σελίδα-φύλλο που παραλείπει το /MediaBox δεν είναι χαλασμένη· παίρνει την τιμή από τον πλησιέστερο πρόγονο κόμβο που τον ορίζει. Μια σελίδα που ορίζει το /MediaBox παρακάμπτει (overrides) ό,τι λέει ο γονέας, μόνο για αυτήν τη σελίδα
Αυτό έχει σημασία για την ανάλυση. Η ανάγνωση ενός αντικειμένου /Page μεμονωμένα και η υπόθεση ότι οι ιδιότητές του είναι πλήρεις θα αναφέρει εσφαλμένα τις διαστάσεις για οποιαδήποτε σελίδα βασίζεται στην κληρονομικότητα. Ένας σωστός αναγνώστης περπατά την αλυσίδα /Parent, συλλέγοντας ιδιότητες που δεν έχει δει ακόμα, σταματώντας στη ρίζα
Ένθετα δέντρα
Τίποτα στην προδιαγραφή δεν περιορίζει το δέντρο σε ένα μόνο επίπεδο. Ένα μεγάλο έγγραφο μπορεί να ομαδοποιήσει σελίδες κάτω από ενδιάμεσους κόμβους που αντιστοιχούν χαλαρά σε κεφάλαια:
2 0 obj % root Pages node, Count = 8
<< /Type /Pages /Count 8 /Kids [3 0 R 4 0 R] >>
endobj
3 0 obj % first chapter, 5 pages
<< /Type /Pages /Parent 2 0 R /Count 5
/Kids [10 0 R 11 0 R 12 0 R 13 0 R 14 0 R]
/MediaBox [0 0 612 792] >>
endobj
4 0 obj % second chapter, 3 pages
<< /Type /Pages /Parent 2 0 R /Count 3
/Kids [20 0 R 21 0 R 22 0 R]
/MediaBox [0 0 612 792] >>
endobjΟ αλγόριθμος διάσχισης είναι ο ίδιος: επισκεφτείτε τα Kids με τη σειρά, κάντε αναδρομή σε οποιονδήποτε κόμβο /Pages, συλλέξτε κόμβους-φύλλα /Page. Οι τιμές /Count επιτρέπουν σε έναν αναγνώστη να παραλείψει ένα ολόκληρο υποδέντρο όταν πηδά σε μια σελίδα που βρίσκεται πέρα από αυτό, γι' αυτό αυτοί οι αριθμοί πρέπει να είναι ακριβείς. Ορισμένοι επεξεργαστές PDF από τα τέλη της δεκαετίας του 1990 και τις αρχές της δεκαετίας του 2000 δεν τους υπολόγιζαν ξανά μετά από επιτόπιες (in-place) επεξεργασίες, επομένως ένας αμυντικός αναλυτής επαληθεύει το /Count έναντι του πραγματικού αριθμού φύλλων (leaf count) αντί να το εμπιστεύεται για την εκχώρηση του πίνακα (array allocation)
Fan-out ως απόφαση απόδοσης
Ένα επίπεδο /Pages με χιλιάδες αναφορές στο /Kids είναι έγκυρο, αλλά ένα ισορροπημένο δέντρο με fan-out περίπου 32 επιτρέπει τυχαία πρόσβαση σε χρόνο O(log n). Ο αναγνώστης συγκρίνει τα συσσωρευμένα /Count και ανοίγει λίγους μικρούς ενδιάμεσους κόμβους αντί να αναλύσει ολόκληρο έναν τεράστιο πίνακα. Η ίδια δομή μειώνει και το κόστος incremental updates, επειδή επανεγγράφεται μόνο η διαδρομή από το νέο φύλλο έως τη ρίζα
Τι συμβαίνει όταν το /Count λέει ψέματα
Το /Count είναι λογιστική πληροφορία και πρέπει να ισούται με τα φύλλα του υποδέντρου, αλλά η μορφή PDF δεν το επιβάλλει. Ένας incremental update μπορεί να ενημερώσει τον άμεσο γονέα και να αφήσει τη ρίζα με παλιό count, ενώ αρνητικές, μηδενικές ή υπερβολικά μεγάλες τιμές μπορεί να προέρχονται από καταστροφή ή fuzzing. Ένας αμυντικός parser χρησιμοποιεί το /Count μόνο ως υπόδειξη και επιβεβαιώνει πάντα την τιμή με πλήρη διάσχιση πριν από κατανομή μνήμης
Πού εμφανίζεται αυτό στην πράξη
Το σφάλμα (bug) σειράς σελίδων εμφανίζεται πιο συχνά σε δύο σενάρια. Το πρώτο είναι ένας προσαρμοσμένος (custom) αναλυτής που σαρώνει για αντικείμενα τύπου /Page αντί να ακολουθεί το δέντρο. Βρίσκει κάθε σελίδα, αλλά με σειρά αριθμού αντικειμένου, όχι με σειρά ανάγνωσης. Η διόρθωση είναι πάντα η ίδια: ξεκινήστε από το τρέιλερ, επιλύστε τον ριζικό κατάλογο, ακολουθήστε τα /Pages και διασχίστε τους πίνακες Kids
Το δεύτερο σενάριο είναι ένα αρχείο σταδιακής ενημέρωσης. Όταν ένας επεξεργαστής PDF προσαρτά αλλαγές χωρίς να ξαναγράψει ολόκληρο το αρχείο, τα νέα αντικείμενα σελίδας αποκτούν υψηλούς αριθμούς αντικειμένων, ενώ ο πίνακας Kids στο αρχικό δέντρο εξακολουθεί να ελέγχει τη λογική τους θέση. Μια σελίδα που αρχικά ήταν το αντικείμενο 5 αντικαθίσταται από ένα νέο αντικείμενο 143, αλλά ο πίνακας Kids τώρα παραπέμπει στο 143 εκεί που παλιά παρέπεμπε στο 5, επομένως η λογική σειρά διατηρείται. Η περιήγηση βάσει του αριθμού του αντικειμένου θα έβαζε τη σελίδα αντικατάστασης σε λάθος θέση στην ακολουθία
Τα γραμμικοποιημένα PDF (βελτιστοποιημένα για το web) προσθέτουν μια τρίτη παραλλαγή: το αρχείο αναδιατάσσεται φυσικά, έτσι ώστε το περιεχόμενο της πρώτης σελίδας να εμφανίζεται κοντά στην αρχή του αρχείου για γρήγορη εμφάνιση σε μια αργή σύνδεση. Η δομή του δέντρου σελίδων παραμένει έγκυρη (authoritative) για τη σειρά, αλλά ο πίνακας διασταυρούμενων αναφορών αντιστοιχεί στις αναδιαταγμένες μετατοπίσεις (rearranged offsets). Ένας αναλυτής που βασίζεται στη θέση του αρχείου αντί στον πίνακα xref, θα διαβάσει λάθος ακόμη και την πρώτη σελίδα ενός γραμμικοποιημένου αρχείου
Το HotPDF Component χειρίζεται τη διάσχιση του δέντρου σελίδων, την επίλυση κληρονομικότητας και τη συγχώνευση xref των σταδιακών ενημερώσεων εσωτερικά. Η απευθείας εργασία με τα αντικείμενα σελίδας του (page objects) σημαίνει ότι η διάταξη του πίνακα Kids έχει ήδη εφαρμοστεί· οι δείκτες σελίδας (page indices) αντιστοιχίζονται σε λογικές σελίδες, όχι σε αριθμούς αντικειμένων