Rask PDF-sammenslåing i Delphi med referanseforskyvning

Sammenslåing av PDF-er høres ut som noe som burde være billig. Sideinnholdet er allerede lagt ut, skrifttypene er allerede innebygd, og bildene er allerede komprimert. I prinsippet er en sammenslåing bare bokføring: nummerer objektene på nytt så to filers nummerrom slutter å kollidere, sy sammen sidetrærne, rett opp krysstabellen og skriv ut. I praksis kaster de fleste sammenslåingsrutiner bort denne billigheten. For hvert objekt i hver inndatafil kjører de en full parsing til et tokenisert objekttre, endrer et par indirekte referanser og serialiserer deretter treet tilbake til bytes. Parsing og serialisering er de dyre halvdelene, og for det store flertallet av objekter gir de en byte-sekvens som er nesten identisk med det som kom inn

PDFlibPas er en innfødt Object Pascal PDF-motor for Delphi og C++Builder, og det raske sammenslåingsløpet finnes for å hoppe over den runden der det beviselig er trygt. Ideen er smal, men den gir uttelling på tvers av hele dokumentsett: for et uendret objekt som ikke er en stream, ta de opprinnelige kildebytesene ordrett og gjør én bytebasert omskriving av de indirekte referansene de inneholder, slik at hver N G R blir til (N+Offset) G R. Ingen tokenizer, intet objekttre, ingen serialisator. Denne artikkelen går gjennom hvor snarveien er lovlig, tilstandsmaskinen som gjør byteomskrivingen uten å ødelegge noe, hvorfor bokmerkesammenslåing trengte en helt annen mekanisme, og hvordan den vanlige sammenslåingsveien ble bygget om fra kvadratisk til lineær samtidig

Hvorfor objektnummerering er den virkelige kostnaden ved en sammenslåing

Hver PDF har sitt eget objektnummerrom. Fil A har objekt 1, objekt 2 og så videre, mens fil B har sitt eget objekt 1, objekt 2 og så videre. Du kan ikke legge B-objektene inn i A-filen uendret, fordi tallene vil kollidere og hver indirekte referanse inne i B da vil peke til feil objekt. Løsningen er et offset: hvis A ender på objekttall Offset, blir B-objekt N til objekt N+Offset i utdata, og hver referanse N G R som dukker opp hvor som helst inne i B-objektene må forskyves til (N+Offset) G R for å stemme

Den forskyvningen er hele den semantiske jobben ved å slå sammen objektkroppen. Rettelser i sidetreet og sammenslåingen av AcroForm er små, avgrensede endringer på noen få objekter. Hovedarbeidet er å skrive om referanser på tvers av tusenvis av objekter, og den naive måten å gjøre det på er å parse hvert objekt så du kan finne referansene strukturelt. PDFlibPas sin MergeFileListFast gjør det motsatte: referansene kan også finnes i råbytesene, hvis du er nøye med kontekstene der en tall-mellomrom-tall-mellomrom-R-sekvens ikke er en referanse. Hopp over parsing, forskyv på stedet, og kostnaden per objekt krymper til én lineær skanning av bytes du uansett skulle kopiere

Når gjenbruk av kildebytes er trygt å gjøre

Bytebanen brukes bare når tre forhold alle er oppfylt for objektet som kopieres ut av et senere dokument. Hvis ett av dem feiler, sendes objektet tilbake til full decode- og serialiseringsvei, så korrekthet vinner alltid over fart:

Doc2.IsChangedObject(X) er False. Hvis sammenslåingsmotoren allerede har endret objektet i minnet, for eksempel et sideobjekt der /Parent er blitt pekt om, er det interne treet sannhetskilden og de opprinnelige bytesene er utdaterte. Bare urørte objekter kvalifiserer
Kildebytesene inneholder ikke nøkkelordet stream. Kroppen til et stream-objekt er opak binærdata innrammet av stream/endstream, og en naiv referanseskanning over komprimert eller kryptert stream-data ville gladelig "finne" og ødelegge byte-mønstre som ser ut som referanser. Stream-objekter beholder den opprinnelige stream-bevisste veien
Kildebytesene inneholder verken /StructTreeRoot eller /StructElem. I den raske profilen blir strukturtreet for tagget PDF droppet i stedet for slått sammen, så disse objektene må gjennom decode-veien der motoren kan nullstille dem bevisst

Beslutningen ligger i kopieringsløkken per objekt. Når alle tre sjekkene passerer, går objektets bytes rett til ShiftIndRefsInSource og deretter til skriveren, ellers kastes bytesene og objektet bygges opp på nytt med GetObject, forskyves med ShiftIndRef og serialiseres. Strukturen i den grenen er verdt å se, fordi rekkefølgen på sjekkene er det som holder den trygg

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;

Tom ObjectData er signalet om at bytebanen avviste objektet. Den ene markøren holder rask og langsom vei fra å drive fra hverandre: det finnes nøyaktig ett sted som bestemmer, og nøyaktig ett fallback-løp

Tilstandsmaskinen for referanseforskyvning og kanttilfellene

Byteomskriving av indirekte referanser er forrædersk lett å gjøre feil, fordi R og tallrekker dukker opp overalt i et PDF-objekt i kontekster som ikke er referanser. ShiftIndRefsInSource er en liten håndskrevet skanner som går gjennom bytesene én gang og bare skriver om et tall når det følges, med PDF-hvitt mellom tokenene, av et nytt tall og deretter en R-avgrenser. De billige utgangene kommer først: hvis offseten er null eller kilden er tom, returneres bytesene urørt uten at skanneren i det hele tatt aktiveres

Skannerens korrekthet hviler på å kjenne igjen kontekstene der en referanseformet sekvens må få være i fred. Dette er grensene som er lettest å overse, og hver av dem håndteres eksplisitt:

Literalstrenger avgrenset av ( og ) kopieres ordrett, med sporing av nestingsdybde og hensyn til omvendt skråstrek-escape, slik at en parentes som er escapet ikke forstyrrer dybdetellingen. En streng som (see object 3 0 R for details) inneholder et skolebokeksempel på et referansemønster som egentlig bare er prosa, og den må overleve byte for byte
Heksadesimale strenger avgrenset av < og > sendes videre uten tolkning. Byteverdien 52 inne i en hex-streng er ASCII-koden for R, og en skanner som behandlet hex-lasten som tekst kunne fabrikkere en spøkelsesreferanse. Åpningssekvensen << for en ordbok oppdages først, slik at en ordbok ikke forveksles med en heksadesimal streng
Navneobjekter som starter med / leses helt ut, fra skråstreken til neste mellomrom eller skilletegn. Uten dette kunne et navn som /R, en vanlig ressursnøkkel, bli lest som R i en referanse
Kommentarer som introduseres med % løper til linjeslutt og hoppes over som opak tekst
Tall-etter-R-testen er streng. En referanse gjenkjennes bare som N mellomrom G mellomrom R, der R er avsluttet av mellomrom, et skilletegn eller slutten av input. Hvis generasjonsnummeret mangler, eller en R følges av en bokstav, blir tallene sendt ut uendret. Dette er det som beskytter heltallet i /Length 1234 og de fire tallene i en MediaBox mot å bli stille inkrementert

Kjernen i den strenge testen leser nesten nøyaktig slik spesifikasjonssatsen beskriver den:

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;

Bare objektnummeret skrives om; generasjonsnummeret og det eksakte opprinnelige mellomrommet mellom tokenene kopieres videre, så utdataene er byte-identiske med inndataene bortsett fra det ene tallet som måtte endres. Den presisjonen er hele poenget, det er det som gjør gjenbruk av kildebytes ekvivalent med en full serialisering, ikke bare nesten. Atferden er dekket av et fokusert sett enhetstester som øver på bare referanser, referanser inne i arrays, tall som ikke er referanser, literalstrenger, heksadesimale strenger og ikke-null generasjonsnummer med offset brukt

Hvorfor bokmerker ikke kunne gjenbruke AppendOutline

Å slå sammen bokmerker fra flere dokumenter til ett outline-tre ser ut som en jobb for den eksisterende AppendOutline-hjelperen, som allerede vet hvordan man fester toppnivåbokmerker fra ett dokument til et annet. Det er feil verktøy her, og grunnen er en subtil lagdelingsmismatch. AppendOutline finner det nåværende siste toppnivåbokmerket ved å gå gjennom leseren over de opprinnelige filbytesene. Men det raske sammenslåingsløpet legger endringene sine i en buffer for nye objekter via ChangeObject, og leseren ser aldri disse endringene. Kjedes du tre eller flere dokumenter, vil hver append peke det første dokumentets opprinnelige siste bokmerke mot det nyeste dokumentet, så alle bokmerkene i mellomdokumentene faller ut av kjeden, og bare den kumulative /Count blir riktig, noe som gjør feilen lett å overse til noen åpner bokmerkeruten

Bytebanen løser dette med en todelt, metadatadrevet injeksjon som aldri går tilbake og leser gjennom leseren. En første gjennomgang over alle input samler per dokument outline-roten og generasjonsnumrene, første og siste toppnivåbokmerke og rotens /Count. Fra det sammendraget regner koden ut de globale objektnumrene for hver lenke den må smi, hvert dokuments toppnivå /Parent til den delte roten, første bokmerkes /Prev til forrige dokuments siste, siste bokmerkes /Next til neste dokuments første, ved ren objektnummeraritmetikk. Bak dette ligger en skriveordensbegrensning: det første dokumentets objekter skrives ut før noe etterfølgende dokument i det hele tatt åpnes, så alle endringene i det første dokumentets outline, rotens /Count og /Last, og den gamle siste bokmerkets /Next, må kunne uttrykkes som aritmetikk som ikke trenger noe senere dokument i hånden. Endringene for hvert etterfølgende dokument brukes på plass etter at dokumentet er åpnet, men før det skrives, så de følger med ut gjennom den samme change-object-veien

Offset-justeringsinvarianten som binder alt sammen

Både referanseforskyvningen og bokmerkeinjeksjonen er avhengige av én aritmetisk invariant, og det er den skjøreste antakelsen i hele designet. En referanse som settes inn i et senere dokument, skrives som målglobalt objektnummer minus det dokumentets Offset, slik at når objektet senere forskyves av ShiftIndRef(Offset), lander verdien på det tiltenkte globale nummeret. Det første dokumentet får Offset = 0 og bruker globale nummer direkte. For at den subtraksjonen skal være riktig, må den løpende offset-sekvensen som brukes under injeksjonen matche offset-sekvensen som brukes når objektene til slutt skrives ut

Det gjør den, fordi side- og form-sammenslåingen har en egenskap: AddPages, AddFields og AddFieldFonts modifiserer bare det første dokumentets eksisterende objekter, de legger aldri til nye. Dermed er det første dokumentets objekttall uendret gjennom side-sammenslåingsfasen, og offseten til hvert senere dokument, summen av alle foregående dokumenters objekttall, forblir stabil fra injeksjon til utskriving. Bryter du det, og introduserer du en fase som lager et nytt objekt midt i sammenslåingen, vil hver side- og bokmerkereferanse nedstrøms være forskjøvet med antallet objekter du la til. Invarianten er stille, men den bærer lasten

Tre innganger over én motor

Det raske løpet er ikke en forgrening av sammenslåingskoden. I samme arbeid ble byte-motoren delt ut i én intern rutine, MergeFileListInternal(ListName, OutputFileName, PreserveStructTree, StrictMode), og de offentlige API-ene ble tynne omslag som velger to flagg:

MergeFileListFast kaller motoren med bevaring av strukturtre av, den slankeste veien, der den taggede PDF-strukturen droppes så byteveien kan brukes på flest mulig objekter
MergeFileList kaller den med bevaring på, slik at strukturtreet overlever og resultatet forblir en brukbar tagget PDF. Denne vanlige veien arver også sammenslåingen av bokmerker og skjemaer på tvers av dokumenter
MergeFileListStrict slår på strict mode: den første metadata-gjennomgangen stopper ved den første inputen som ikke rapporterer en ren sammenslåing, så bare dokumentene som ble samlet før den dårlige filen blir tatt med, i stedet for å hoppe over den dårlige filen og fortsette

Å folde veiene sammen gjorde det også mulig å bygge om den vanlige sammenslåingen fra en parvis O(N²)-løkke, slå sammen fil én og to, slå sammen resultatet med tre og så videre, med reparsing av den voksende akkumulatoren for hvert steg, til én lineær gjennomgang som åpner hver input bare én gang. De to gamle to-fil- og to-strøm-inngangene, MergeFiles og MergeStreams, er urørt og forblir tilgjengelige for kallere som virkelig vil ha en parvis sammenslåing

En ærlig merknad om strukturtre-atferden, fordi den bet testsettet. Den raske veiens "drop" er ikke total: den fjerner det første dokumentets katalogreferanse til /StructTreeRoot, men selve strukturtreobjektet blir likevel skrevet ut som et foreldreløst objekt. Så byteutdataene fra den raske veien inneholder fortsatt strengen /StructTreeRoot, og du kan ikke skille rask og vanlig utdata ved å søke etter den strengen, den virkelige forskjellen er om katalogen fortsatt når strukturtreet, som er det som avgjør om filen fortsatt er en navigerbar tagget PDF

Når du skal velge hvilken vei

Bytebanen er en gjennomstrømningsoptimalisering for å sette sammen mange dokumenter der du ikke trenger at strukturtreet for tagget PDF bevares, for eksempel rapportbunting, kontoutskrifter og massekonkatenering. Målt over gjentatte sammenslåinger av mellomstore til store inputsett trimmet bytegjenbruken omtrent fire til tretten prosent av veggklokketiden, avhengig av objektsammensetning, uten nye feil på små eller feilformede input, fordi hvert objekt som skanneren ikke kan bevise at er trygt, faller tilbake til full parsing. Hvis du trenger strukturtreet intakt for tilgjengelighet, bruk den vanlige taggede PDF-sammenslåingen, som bevarer det, og hvis du jobber med svært store enkeltfiler snarere enn mange input, gjelder bytekopiteknikkene som er beskrevet i den tilhørende artikkelen om sammenslåing og splitting av store PDF-er med direkte filtilgang den samme filosofien med "kopier bytes, unngå hele objekttreet" på filnivå

Sammenslåingsrutinene og deres raske og strenge varianter er en del av PDFlibPas Delphi PDF Library, hvis dokumentasjon har hele referansen for fil-liste-API-et og sammenslåingsvalgene som er beskrevet her