Fusion PDF rapide dans Delphi : décalage des références au niveau des octets

Assembler des PDF semble devoir être bon marché. Le contenu des pages est déjà mis en page, les polices sont déjà intégrées, les images sont déjà compressées. En principe, une fusion n'est qu'une question de tenue des comptes : renuméroter les objets pour que les espaces de numérotation des deux fichiers n'entrent plus en collision, rattacher les arborescences de pages, corriger la table des références croisées et écrire. En pratique, la plupart des codes de fusion abandonnent cette simplicité. Pour chaque objet de chaque fichier d'entrée, ils effectuent une analyse complète en une arborescence d'objets tokenisés, modifient quelques références indirectes, puis sérialisent l'arborescence en octets. L'analyse et la sérialisation de retour sont les parties coûteuses, et pour l'immense majorité des objets, elles produisent une séquence d'octets presque identique à celle d'entrée

PDFlibPas est un moteur PDF natif en Object Pascal pour Delphi et C++Builder, et son chemin de fusion rapide existe pour éviter cet aller-retour partout où c'est prouvablement sûr. L'idée est étroite, mais elle rapporte sur des jeux de documents entiers : pour un objet non flux non modifié, prenez les octets source d'origine tels quels et effectuez une seule réécriture au niveau des octets des références indirectes qu'ils contiennent, en transformant chaque N G R en (N+Offset) G R. Aucun analyseur lexical, aucune arborescence d'objets, aucun sérialiseur. Cet article explique où ce raccourci est autorisé, l'automate d'analyse qui effectue la réécriture binaire sans rien corrompre, pourquoi la fusion des signets avait besoin d'un mécanisme tout à fait différent, et comment le chemin de fusion ordinaire a été reconstruit de quadratique à linéaire dans le même temps

Pourquoi le renommage des objets est le vrai coût d'une fusion

Chaque PDF possède son propre espace de numérotation des objets. Le fichier A a l'objet 1, l'objet 2, et ainsi de suite ; le fichier B a son propre objet 1, objet 2, et ainsi de suite. Vous ne pouvez pas injecter les objets de B dans le fichier A tels quels, parce que les numéros entreraient en collision et que chaque référence indirecte à l'intérieur de B se résoudrait alors vers le mauvais objet. La solution est un décalage : si A se termine au nombre d'objets Offset, alors l'objet N devient l'objet N+Offset dans la sortie, et chaque référence N G R qui apparaît partout dans les objets de B doit être décalée vers (N+Offset) G R pour correspondre

Ce décalage constitue à lui seul le travail sémantique de la fusion du corps du document. Les corrections de l'arborescence des pages et la fusion d'AcroForm ne sont que de petites retouches bornées sur un petit nombre d'objets. Le gros du travail consiste à réécrire des références à travers des milliers d'objets, et la manière naïve de le faire consiste à analyser chaque objet pour pouvoir repérer les références structurellement. L'approche de PDFlibPas MergeFileListFast adopte le point de vue inverse : les références sont aussi repérables dans les octets bruts, si vous faites attention aux contextes où une séquence chiffre-espace-chiffre-espace-R est pas une référence. Sautez l'analyse, décalez sur place et le coût par objet s'effondre à un simple balayage linéaire des octets que vous alliez de toute façon copier

Quand la réutilisation des octets source est prouvée sûre

La voie binaire n'est empruntée que lorsque les trois conditions sont vraies pour l'objet copié depuis un document suivant. Si l'une d'elles échoue, l'objet repasse par le parcours complet de décodage et de sérialisation de retour, donc la correction passe toujours avant la vitesse :

• Doc2.IsChangedObject(X) est False. Si le moteur de fusion a déjà modifié l'objet en mémoire (par exemple un objet de page dont /Parent a été redirigé), l'arbre en mémoire fait foi et les octets d'origine sont périmés. Seuls les objets intacts sont éligibles
• Les octets source ne contiennent aucun stream mot-clé. Le corps d'un objet flux est un binaire opaque encadré par stream/endstream, et un balayage naïf des références dans des données de flux compressées ou chiffrées pourrait très bien "trouver" et corrompre des motifs d'octets qui ressemblent à des références. Les objets flux conservent le chemin d'origine adapté aux flux
• Les octets source ne contiennent ni /StructTreeRootni /StructElem. Dans le profil rapide, l'arborescence structurelle des PDF balisés est supprimée plutôt que fusionnée, donc ces objets doivent passer par le chemin de décodage où le moteur peut les annuler volontairement

La décision se joue dans la boucle de copie objet par objet. Quand les trois vérifications passent, les octets de l'objet vont directement à ShiftIndRefsInSource puis à l'écrivain ; sinon les octets sont jetés et l'objet est reconstruit avec GetObject, décalé avec ShiftIndRef et sérialisé. La structure de cette branche vaut le détour, parce que l'ordre des vérifications est ce qui la garde sûre :

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;

Un ObjectData vide signale que la voie binaire a refusé l'objet. Ce seul sentinelle maintient les voies rapide et lente à distance raisonnable : un seul endroit décide, et un seul repli existe

L'automate de décalage des références et ses cas limites

La réécriture au niveau des octets des références indirectes est trompeusement facile à rater, parce que R et les suites de chiffres apparaissent partout dans un objet PDF dans des contextes qui ne sont pas des références. ShiftIndRefsInSource est un petit analyseur écrit à la main qui parcourt les octets une seule fois et ne réécrit un nombre que s'il est suivi, avec des blancs PDF entre les jetons, par un autre nombre puis par un R délimiteur. Les sorties de secours peu coûteuses viennent en premier : si le décalage vaut zéro ou si la source est vide, les octets sont renvoyés intacts sans même entrer dans l'analyseur

La correction de l'analyseur repose sur la reconnaissance des contextes où une séquence en forme de référence doit être laissée intacte. Ce sont les limites les plus faciles à manquer, et chacune est traitée explicitement :

• Chaînes littérales délimitées par ( et ) sont recopiées telles quelles, en suivant la profondeur d'imbrication et en respectant l'échappement par antislash afin qu'une parenthèse échappée ne fausse pas le décompte de profondeur. Une chaîne comme (see object 3 0 R for details) contient un motif de référence d'école qui n'est en réalité que du texte courant, et elle doit survivre octet pour octet
• Chaînes hexadécimales délimitées par < et > sont traversées sans interprétation. Les octets 52 à l'intérieur d'une chaîne hexadécimale sont le code ASCII de R, et un analyseur qui traiterait la charge utile hexadécimale comme du texte pourrait fabriquer une référence fantôme. La parenthèse ouvrante << d'un dictionnaire est détectée d'abord pour qu'un dictionnaire ne soit pas pris pour une chaîne hexadécimale
• Objets nommés commençant par / sont consommés en entier, du slash jusqu'à l'espace blanc ou au délimiteur suivant. Sans cela, un nom comme /R (une clé de ressource courante) pourrait être lu comme le R d'une référence
• Commentaires introduits par % vont jusqu'à la fin de la ligne et sont ignorés comme du texte opaque
• Le test nombre puis R est strict. Une référence n'est reconnue que comme N blanc G blanc R avec le R terminé par un blanc, un délimiteur ou la fin de l'entrée. Si le numéro de génération manque, ou si un R est suivi d'une lettre, les chiffres sont émis sans modification. C'est ce qui protège l'entier dans /Length 1234 et les quatre nombres d'un MediaBox d'être incrémentés silencieusement

Le cœur de ce test strict se lit presque exactement comme la phrase de spécification le décrit :

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;

Seul le numéro d'objet est réécrit ; le numéro de génération et l'espacement d'origine exact entre les jetons sont recopiés, de sorte que la sortie est identique octet pour octet à l'entrée, à l'exception du seul entier qui devait changer. Cette précision est tout l'enjeu : c'est elle qui rend la réutilisation des octets source équivalente à une sérialisation complète, et pas seulement presque équivalente. Le comportement est couvert par un ensemble ciblé de tests unitaires couvrant les références brutes, les références à l'intérieur de tableaux, les nombres qui ne sont pas des références, les chaînes littérales, les chaînes hexadécimales et les numéros de génération non nuls avec un décalage appliqué

Pourquoi les signets n'ont pas pu réutiliser AppendOutline

Fusionner les signets de plusieurs documents en un seul arbre de plan semble relever du AppendOutline helper, qui sait déjà greffer les signets de niveau supérieur d'un document sur ceux d'un autre. Ce n'est pas le bon outil ici, et la raison tient à un subtil décalage de couches. AppendOutline localise le dernier signet de premier niveau courant en parcourant les octets du fichier d'origine avec le lecteur. Mais la fusion rapide met ses modifications en tampon dans une zone de nouveaux objets via ChangeObject; le lecteur ne voit jamais ces modifications. Enchaînez trois documents ou plus et chaque ajout rattache à nouveau le dernier signet d'origine du premier document au document le plus récent, si bien que tous les signets des documents intermédiaires tombent hors de la chaîne ; seul le /Count cumul reste correct, ce qui rend le bogue facile à manquer jusqu'à ce que quelqu'un ouvre le panneau des signets

Le chemin rapide résout cela avec une injection en deux phases pilotée par les métadonnées, qui ne repasse jamais par le lecteur. Un premier passage sur toutes les entrées recueille, pour chaque document, l'objet racine du plan et les numéros de génération, les numéros du premier et du dernier signet de premier niveau, ainsi que le /Count. À partir de ce résumé, le code calcule les numéros globaux d'objet de chaque lien qu'il doit forger : le /Parent vers la racine partagée, le /Prev vers le dernier du document précédent, le /Next vers le premier du document suivant — en utilisant uniquement l'arithmétique des numéros d'objet. Il y a derrière cela une contrainte d'ordre d'écriture : les objets du premier document sont écrits avant même que le moindre document suivant ne soit ouvert, si bien que toutes les modifications du plan du premier document (racine /Count et /Last, et l'ancien dernier signet /Next) doivent pouvoir s'exprimer par une arithmétique qui n'a besoin d'aucun document ultérieur sous la main. Les modifications de chaque document suivant sont appliquées sur place après son ouverture mais avant son écriture, et passent donc par le même chemin de modification d'objet

Le principe d'alignement des décalages qui relie tout cela

Le décalage des références comme l'injection des signets dépendent d'un même invariant arithmétique, et c'est l'hypothèse la plus fragile de toute la conception. Une référence injectée dans un document suivant est écrite comme numéro global d'objet cible moins l'Offset de ce document, de sorte que lorsque l'objet est ensuite décalé de ShiftIndRef(Offset) la valeur tombe sur le numéro global voulu. Le premier document reçoit Offset = 0 et utilise directement les numéros globaux. Pour que cette soustraction soit correcte, la séquence de décalages en cours utilisée pendant l'injection doit correspondre à la séquence de décalages utilisée lorsque les objets sont finalement écrits

C'est le cas, à cause d'une propriété du fonctionnement des fusions de pages et de formulaires : AddPages, AddFields, et AddFieldFonts ne modifient que les objets existants du premier document — ils n'ajoutent jamais de nouveaux objets. Le nombre d'objets du premier document reste donc inchangé pendant l'étape de fusion des pages, et le décalage de chaque document suivant (la somme des nombres d'objets de tous les documents précédents) reste stable de l'injection jusqu'à l'écriture. Brisez cela — introduisez une étape qui crée un nouvel objet au milieu de la fusion — et chaque référence de page et de signet en aval serait décalée du nombre d'objets ajoutés. L'invariant est discret, mais il porte la charge

Trois points d'entrée pour un seul moteur

Le chemin rapide n'est pas une bifurcation du code de fusion. Dans le même travail, le moteur au niveau des octets a été factorisé en une seule routine interne, MergeFileListInternal(ListName, OutputFileName, PreserveStructTree, StrictMode), et les API publiques sont devenues de minces enveloppes qui choisissent deux indicateurs :

• MergeFileListFast appelle le moteur avec la préservation de l'arbre de structure désactivée, la voie la plus légère, qui supprime l'arbre PDF balisé afin que la route par octets s'applique au plus grand nombre d'objets
• MergeFileList l'appelle avec la préservation activée, de sorte que l'arbre de structure survit et que le résultat reste un PDF balisé exploitable. Ce chemin ordinaire hérite aussi de la fusion des signets et des formulaires multi-documents
• MergeFileListStrict active le mode strict : le premier passage sur les métadonnées s'arrête au premier fichier d'entrée qui ne signale pas une fusion propre, de sorte que seuls les documents collectés avant le mauvais fichier sont inclus, au lieu de sauter le mauvais fichier et de continuer

Le regroupement des chemins a aussi permis de reconstruire la fusion ordinaire à partir d'une O(N²) boucle paire par paire, fusionner les fichiers un et deux, fusionner ce résultat avec le trois, et ainsi de suite, en reparsant l'accumulateur croissant à chaque étape, en une seule passe linéaire qui ouvre chaque entrée une seule fois. Les deux points d'entrée historiques à deux fichiers et à deux flux, MergeFiles et MergeStreams, sont inchangés et restent disponibles pour les appelants qui veulent réellement une fusion paire par paire

Une précision honnête sur le comportement de l'arbre de structure, parce qu'il a piégé la suite de tests. Le "retrait" du chemin rapide n'est pas total : il supprime la référence du catalogue du premier document vers /StructTreeRoot, mais l'objet d'arbre de structure lui-même est quand même écrit en tant qu'orphelin. Les octets de la sortie rapide contiennent donc toujours la /StructTreeRoot chaîne, et vous ne pouvez pas distinguer la sortie rapide de la sortie ordinaire en cherchant cette chaîne. La vraie différence est de savoir si le catalogue atteint encore l'arbre de structure, ce qui détermine si le fichier reste un PDF balisé navigable

Quand choisir quel chemin

Le chemin par octets est une optimisation de débit pour assembler de nombreux documents lorsque vous n'avez pas besoin de conserver l'arbre de structure du PDF balisé, par exemple pour regrouper des rapports, produire des états ou faire des concaténations par lots. Mesurée sur des fusions répétées de jeux d'entrées de taille moyenne à grande, la réutilisation des octets a réduit d'environ quatre à treize pour cent le temps de mur, selon la composition des objets, sans nouveau échec sur les entrées petites ou mal formées, parce que tout objet que l'analyseur ne peut pas prouver sûr retombe sur l'analyse complète. Si vous avez besoin de l'arbre de structure intact pour l'accessibilité, utilisez le chemin de fusion ordinaire tagged-PDF de fusion, qui le préserve ; et si vous travaillez sur de très gros fichiers isolés plutôt que sur de nombreuses entrées, les techniques de copie binaire décrites dans l'article compagnon sur fusion et fractionnement de gros PDF avec accès direct au fichier appliquent à l'échelle du fichier la même philosophie, « copier les octets, éviter l'arborescence complète des objets »

Les routines de fusion et leurs variantes rapide et stricte font partie de la PDFlibPas Delphi PDF Library, dont la documentation contient la référence complète de l'API de liste de fichiers et des options de fusion décrites ici