Combinare rapidă a PDF-urilor în Delphi: deplasarea referințelor la nivel de octet

Combinarea PDF-urilor ar trebui, în teorie, să fie ieftină. Conținutul paginilor este deja așezat, fonturile sunt deja încorporate, imaginile sunt deja comprimate. În principiu, o îmbinare este doar contabilitate: renumerotezi obiectele astfel încât spațiile de numerotare ale celor două fișiere să nu se mai suprapună, unești arborii de pagini, corectezi tabelul de cross-reference și scrii rezultatul. În practică, majoritatea codurilor de îmbinare aruncă la gunoi această simplitate. Pentru fiecare obiect din fiecare fișier de intrare, ele fac o analiză completă într-un arbore de obiecte tokenizat, modifică câteva referințe indirecte, apoi serializează arborele înapoi în octeți. Analiza și serializarea din nou sunt părțile costisitoare și, pentru marea majoritate a obiectelor, produc o secvență de octeți aproape identică cu cea de la intrare

PDFlibPas este un motor PDF nativ în Object Pascal pentru Delphi și C++Builder, iar traseul său rapid de îmbinare există ca să sară peste acest dus-întors ori de câte ori este demonstrabil sigur. Ideea este restrânsă, dar dă randament pe seturi întregi de documente: pentru un obiect nemodificat, care nu este de tip stream, ia octeții sursă originali exact așa cum sunt și face o singură rescriere la nivel de octet a referințelor indirecte pe care le conțin, transformând fiecare N G R în (N+Offset) G R. Fără tokenizer, fără arbore de obiecte, fără serializer. Acest articol trece prin cazurile în care această scurtătură este permisă, prin mașina de stări a parserului care face rescrierea la nivel de octet fără să corupă nimic, prin motivul pentru care îmbinarea semnelor de carte a avut nevoie de un mecanism complet diferit și prin felul în care traseul obișnuit de îmbinare a fost refăcut, în același timp, din quadratic în liniar

De ce renumerotarea obiectelor este costul real al unei îmbinări

Fiecare PDF își poartă propriul spațiu de numerotare a obiectelor. Fișierul A are obiectul 1, obiectul 2 și așa mai departe; fișierul B are propriul obiect 1, propriul obiect 2 și așa mai departe. Nu poți introduce obiectele din B în fișierul A fără modificări, pentru că numerele s-ar suprapune și fiecare referință indirectă din B ar ajunge acum să trimită la obiectul greșit. Soluția este un offset: dacă A se termină la numărul de obiecte Offset, atunci obiectul N din B devine obiectul N+Offset în rezultatul final, iar fiecare referință N G R care apare oriunde în obiectele lui B trebuie deplasată la (N+Offset) G R ca să se potrivească

Această deplasare este întreaga sarcină semantică a îmbinării corpului documentului. Corecțiile pentru arborele de pagini și îmbinarea AcroForm sunt modificări mici, delimitate, pe un număr redus de obiecte. Munca principală este rescrierea referințelor în mii de obiecte, iar modul naiv de a face asta este să parcurgi în analiză fiecare obiect ca să poți găsi structural referințele. Traseul MergeFileListFast al PDFlibPas privește în direcția opusă: referințele pot fi găsite și în octeții brute, dacă ești atent la contextul în care o secvență cifră-spațiu-cifră-spațiu-R este not o referință. Sare peste analiză, deplasează în loc și costul per obiect cade la o singură scanare liniară a octeților pe care oricum urma să îi copiezi

Când refolosirea octeților sursă este în mod demonstrabil sigură

Traseul pe octeți este folosit doar când toate cele trei condiții sunt îndeplinite pentru obiectul copiat dintr-un document următor. Dacă oricare dintre ele eșuează, obiectul revine pe traseul complet de decodare și reserializare, așa că exactitatea câștigă mereu în fața vitezei:

• Doc2.IsChangedObject(X) este False. Dacă motorul de îmbinare a modificat deja obiectul în memorie, de exemplu un obiect de pagină al cărui /Parent a fost realiniat, arborele din memorie este sursa de adevăr, iar octeții originali sunt depășiți. Numai obiectele nemodificate se califică
• Octeții sursă nu conțin niciun stream cuvânt-cheie. Corpul unui obiect de tip stream este binar opac, încadrat de stream/endstream, iar o scanare naivă a referințelor peste datele comprimate sau criptate ar "găsi" și ar corupe cu plăcere tipare de octeți care seamănă cu referințe. Obiectele de tip stream păstrează traseul original, conștient de stream
• Octeții sursă nu conțin nici /StructTreeRoot nici /StructElem. În profilul rapid, arborele structurii PDF etichetat este eliminat, nu îmbinat, așa că acele obiecte trebuie să treacă prin traseul de decodare, unde motorul le poate goli în mod deliberat

Decizia se ia în bucla de copiere per obiect. Când toate cele trei verificări trec, octeții obiectului merg direct la ShiftIndRefsInSource și apoi la writer; altfel, octeții sunt aruncați și obiectul este reconstruit cu GetObject, deplasat cu ShiftIndRef, și serializat. Structura acestei ramuri merită văzută, pentru că ordinea verificărilor este ceea ce o păstrează sigură:

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 gol este semnalul că traseul pe octeți a refuzat obiectul. Acest singur sentinel păstrează traseele rapid și lent în pas: există exact un loc care decide și exact o singură revenire

Mașina de stare pentru mutarea referințelor și cazurile ei limită

Rescrierea la nivel de octet a referințelor indirecte este înșelător de ușor de greșit, deoarece R și șirurile de cifre apar peste tot într-un obiect PDF, în contexte care nu sunt referințe. ShiftIndRefsInSource este un mic scanner scris manual care parcurge octeții o singură dată și rescrie un număr doar atunci când este urmat, cu spațiu alb PDF între tokenuri, de un alt număr și apoi de un R delimitator. Ieșirile rapide vin primele: dacă deplasarea este zero sau sursa este goală, octeții sunt returnați nemodificați, fără a intra deloc în scanner

Corectitudinea scannerului se bazează pe recunoașterea contextelor în care o secvență cu aspect de referință trebuie lăsată în pace. Acestea sunt granițele cele mai ușor de ratat, iar fiecare este tratată explicit:

• Șiruri literale delimitate de ( și ) sunt copiate verbatim, urmărind adâncimea de imbricare și respectând escape-ul cu backslash, astfel încât o paranteză escapată să nu deregleze numărătoarea adâncimii. Un șir precum (see object 3 0 R for details) conține un model clasic de referință care este, de fapt, doar text și trebuie să supraviețuiască byte cu byte
• Șiruri hexazecimale delimitate de < și > sunt transmise mai departe fără interpretare. Octeții 52 dintr-un șir hexazecimal reprezintă codul ASCII pentru R, iar un scanner care ar trata conținutul hexazecimal ca text ar putea fabrica o referință fantomă. Deschiderea << a unui dicționar este detectată prima, astfel încât un dicționar să nu fie confundat cu un șir hexazecimal
• Obiecte de tip nume care încep cu / sunt consumate integral, de la slash până la următorul spațiu alb sau delimitator. Fără asta, un nume precum /R (o cheie de resursă comună) ar putea fi citit ca R începutul unei referințe
• Comentarii introduse de % se întind până la sfârșitul liniei și sunt omise ca text opac
• Testul număr-urmat-de-R este strict. O referință este recunoscută doar ca N spațiu alb G spațiu alb R cu R încheiată de spațiu alb, un delimitator sau sfârșitul intrării. Dacă numărul de generație lipsește sau un R este urmat de o literă, cifrele sunt emise nemodificate. Acesta este lucrul care protejează întregul din /Length 1234 și cele patru numere ale unui MediaBox de a fi incrementate în tăcere

Nucleul acestui test strict se citește aproape exact așa cum îl descrie propoziția din specificație:

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;

Se rescrie doar numărul obiectului; numărul de generație și spațiul alb original exact dintre tokenuri sunt copiate mai departe, astfel încât ieșirea este identică la nivel de octet cu intrarea, cu excepția singurului întreg care trebuia schimbat. Această precizie este tocmai esența, pentru că face refolosirea octeților sursă echivalentă cu o reserializare completă, nu doar apropiată de ea. Comportamentul este acoperit de un set focalizat de teste unitare care exercită referințe simple, referințe în interiorul array-urilor, numere care nu sunt referințe, șiruri literale, șiruri hexazecimale și numere de generație nenule cu un offset aplicat

De ce bookmark-urile nu puteau reutiliza AppendOutline

Combinarea bookmark-urilor din mai multe documente într-un singur arbore de contur pare o treabă pentru AppendOutline utilitarul existent, care deja știe cum să atașeze bookmark-urile de nivel superior ale unui document la altul. Este instrumentul greșit aici, iar motivul este o nepotrivire subtilă de stratificare. AppendOutline localizează ultimul marcaj de nivel superior curent parcurgând cititorul peste biții originali ai fișierului. Dar îmbinarea rapidă își pregătește modificările într-un buffer de obiecte noi prin ChangeObject; cititorul nu vede niciodată aceste modificări. Leagă trei sau mai multe documente și fiecare adăugare redirecționează ultimul marcaj original al primului document către documentul cel mai nou, astfel încât toate marcajele documentelor intermediare ies din lanț - doar /Count rămâne corect, ceea ce face ca eroarea să fie ușor de ratat până când cineva deschide panoul de marcaje

Fluxul rapid o rezolvă cu o injecție în doi pași, bazată pe metadate, care nu mai reia parcurgerea cititorului. O primă trecere peste toate intrările colectează, pentru fiecare document, obiectul rădăcină al schemei și numerele de generație, primele și ultimele numere de marcaj de nivel superior și /Count. Din acel rezumat, codul calculează numerele globale de obiect pentru fiecare legătură pe care trebuie să o construiască - fiecare document, marcajul său de nivel superior /Parent către rădăcina partajată, marcajul de început al primului /Prev către ultimul marcaj al documentului anterior, marcajul de sfârșit al ultimului /Next către primul marcaj al documentului următor - folosind aritmetică pură a numerelor de obiect. În spatele acestui lucru stă o constrângere de ordine a scrierii: obiectele primului document sunt scrise înainte ca vreun document următor să fie măcar deschis, așa că toate ajustările schemei primului document (rădăcină /Count și /Last, iar al vechiului ultim marcaj de carte /Next) trebuie să poată fi exprimate ca aritmetică ce nu are nevoie de niciun document ulterior la îndemână. Ajustările fiecărui document următor sunt aplicate la loc după deschidere, dar înainte de scriere, astfel încât trec prin aceeași cale de change-object

Invarianta de aliniere a offsetului care le leagă

Atât deplasarea referinței, cât și injecția marcajelor depind de o singură invariantă aritmetică, iar aceasta este cea mai fragilă presupunere din întreaga proiectare. O referință injectată într-un document următor este scrisă ca numărul global al obiectului țintă minus Offset-ul acelui document, astfel încât atunci când obiectul este deplasat ulterior cu ShiftIndRef(Offset) valoarea să ajungă pe numărul global dorit. Primul document primește Offset = 0 și folosește direct numerele globale. Pentru ca acea scădere să fie corectă, secvența de offseturi folosită în timpul injecției trebuie să se potrivească cu secvența de offseturi folosită atunci când obiectele sunt scrise în final

Așa se întâmplă, din cauza unei proprietăți a modului în care funcționează îmbinările de pagini și formulare: AddPages, AddFields, și AddFieldFonts modifică doar obiectele existente ale primului document - nu adaugă niciodată altele noi. Așadar, numărul de obiecte al primului document rămâne neschimbat în etapa de îmbinare a paginilor, iar offsetul fiecărui document următor, adică suma tuturor numerelor de obiecte ale documentelor precedente, rămâne stabil de la injecție până la scrierea finală. Rupe asta - introduce o etapă care creează un obiect nou în mijlocul îmbinării - și fiecare referință de pagină și de marcaj de carte din aval ar fi deplasată cu numărul de obiecte pe care le-ai adăugat. Invarianta este tăcută, dar poartă greutatea întregului sistem

Trei puncte de intrare peste un singur motor

Calea rapidă nu este o ramură a codului de îmbinare. În aceeași linie de lucru, motorul la nivel de biți a fost factorizat într-o singură rutină internă, MergeFileListInternal(ListName, OutputFileName, PreserveStructTree, StrictMode), iar API-urile publice au devenit învelișuri subțiri care aleg două flaguri:

• MergeFileListFast apelează motorul cu păstrarea arborelui de structură dezactivată - cea mai suplă cale, care elimină arborele PDF-etichetat astfel încât ruta pe biți să se aplice celui mai mare număr de obiecte
• MergeFileList îl apelează cu păstrarea activată, astfel încât arborele de structură supraviețuiește și rezultatul rămâne un PDF etichetat utilizabil. Această cale obișnuită moștenește și îmbinarea marcajelor de carte și a formularelor pentru mai multe documente
• MergeFileListStrict activează modul strict: prima trecere peste metadate se oprește la prima intrare care nu raportează o îmbinare curată, astfel încât sunt incluse doar documentele colectate înainte de fișierul defect, în loc să se sară peste fișierul defect și să se continue

Unificarea acestor căi a permis și reconstruirea îmbinării obișnuite dintr-o buclă pereche O(N²) - îmbină fișierul unu cu doi, îmbină rezultatul cu trei și așa mai departe, reanalizând la fiecare pas acumulatorul în creștere - într-o singură trecere liniară care deschide fiecare intrare o singură dată. Cele două puncte de intrare vechi pentru două fișiere și două fluxuri, MergeFiles și MergeStreams, rămân intacte și disponibile pentru apelanții care chiar își doresc o îmbinare pereche

O observație onestă despre comportamentul arborelui de structură, pentru că a mușcat suita de teste. „Drop”-ul din calea rapidă nu este total: elimină referința din catalogul primului document către /StructTreeRoot, dar obiectul arborelui de structură este totuși scris mai departe ca orfan. Așa că biții de ieșire ai căii rapide încă includ șirul /StructTreeRoot, iar tu nu poți distinge ieșirea rapidă de cea obișnuită căutând acel șir - diferența reală este dacă catalogul mai ajunge la arborele de structură, lucru care determină dacă fișierul este în continuare un PDF etichetat navigabil

Când să alegi fiecare cale

Calea pe biți este o optimizare de debit pentru asamblarea multor documente atunci când nu ai nevoie ca arborele de structură PDF-etichetat să fie păstrat - pachete de rapoarte, serii de extrase, concatenare în loturi. Măsurat pe îmbinări repetate ale unor seturi de intrare medii spre mari, reutilizarea biților a redus timpul de perete cu aproximativ patru până la treisprezece la sută, în funcție de amestecul de obiecte, fără erori noi pe intrări mici sau defecte, deoarece orice obiect pe care scannerul nu poate demonstra că este sigur revine la parsarea completă. Dacă ai nevoie ca arborele de structură să rămână intact pentru accesibilitate, folosește calea obișnuită de îmbinare PDF-etichetat, care îl păstrează; iar dacă lucrezi cu fișiere individuale foarte mari, nu cu multe intrări, tehnicile de copiere a biților descrise în articolul însoțitor despre îmbinare și împărțire PDF de mari dimensiuni cu acces direct la fișier aplicați aceeași filosofie „copiați biții, evitați arborele complet de obiecte” la nivel de fișier

Rutinele de îmbinare și variantele lor rapide și stricte fac parte din PDFlibPas Delphi PDF Library, a cărei documentație include referința completă pentru API-ul file-list și opțiunile de îmbinare descrise aici