Snabb PDF-sammanslagning i Delphi: bytevis referensskift

Att sammanfoga PDF-filer låter som att det borde vara billigt. Sidinnehållet är redan satt, typsnitten är redan inbäddade, bilderna är redan komprimerade. I princip är en sammanslagning bara bokföring: numrera om objekten så att två filers numreringsrymder slutar krocka, sy ihop sidträden, rätta till korsreferenstabellen och skriv ut. I praktiken kastar det mesta sammanslagningskoden bort den billigheten. För varje objekt i varje indatafil gör den en fullständig parsning till ett tokeniserat objekträd, muterar ett par indirekta referenser och serialiserar sedan trädet tillbaka till bytes. Parsningen och reserialiseringen är de dyra halvorna, och för den stora majoriteten av objekten ger de en bytesekvens som nästan är identisk med det som gick in

PDFlibPas är en inbyggd Object Pascal-PDF-motor för Delphi och C++Builder, och dess snabba sammanslagningsväg finns för att hoppa över det varvet där det bevisligen är säkert. Idén är smal men ger utdelning över hela dokumentuppsättningar: för ett oförändrat icke-strömobjekt, ta de ursprungliga källbytesen ordagrant och gör en enda bytevis omskrivning av de indirekta referenserna de innehåller, så att varje N G R blir (N+Offset) G R. Ingen tokenizer, inget objekträd, ingen serializer. Den här artikeln går igenom var den genvägen är tillåten, den parserns tillståndsmaskin som gör byteomskrivningen utan att korrumpera något, varför bokmärkessammanslagning behövde en helt annan mekanism, och hur den ordinarie sammanslagningsvägen byggdes om från kvadratisk till linjär samtidigt

Varför omnumrering av objekt är den verkliga kostnaden vid en sammanslagning

Varje PDF har sitt eget objektnumreringsutrymme. Fil A har objekt 1, objekt 2 och så vidare; fil B har sitt eget objekt 1, objekt 2 och så vidare. Du kan inte lägga in B:s objekt i A:s fil oförändrade, eftersom numren skulle krocka och varje indirekt referens inne i B då skulle peka på fel objekt. Lösningen är en förskjutning: om A slutar vid objektnummer Offset, så blir B:s objekt N till objekt N+Offset i utdata, och varje referens N G R som förekommer någonstans inne i B:s objekt måste förskjutas till (N+Offset) G R för att stämma

Det där skiftet är hela den semantiska uppgiften i att slå ihop kroppen. Sidträdsfixarna och AcroForm-sammanslagningen är små, avgränsade redigeringar på några få objekt. Huvudarbetet är att skriva om referenser över tusentals objekt, och det naiva sättet att göra det på är att parsa varje objekt så att du kan hitta referenserna strukturellt. PDFlibPas MergeFileListFast tar motsatt syn: referenserna går också att hitta i de råa bytesen, om du är noga med de sammanhang där en digit-space-digit-space-R-sekvens är inte en referens. Hoppa över parsningen, förskjut på plats, och kostnaden per objekt krymper till en enda linjär genomsökning av bytes du ändå skulle kopiera

När det är bevisligen säkert att återanvända källbytes

Bytevägen används bara när tre villkor alla håller för objektet som kopieras ut ur ett senare dokument. Om något av dem faller bort skickas objektet tillbaka genom den fullständiga avkodnings- och reserialiseringsvägen, så korrektheten vinner alltid över hastigheten:

Doc2.IsChangedObject(X) är False. Om sammanslagningsmotorn redan har muterat objektet i minnet (ett sidobjekt vars /Parent pekades om, till exempel), är trädet i minnet sanningskällan och de ursprungliga bytesen är föråldrade. Endast orörda objekt kvalificerar
Källbytesen innehåller inget stream nyckelord. Kroppen i ett strömobjekt är ogenomskinlig binär data inramad av stream/endstream, och en naiv referensskanning över komprimerade eller krypterade strömdata skulle gärna "hitta" och korrumpera byteformer som ser ut som referenser. Strömobjekt håller sig till den ursprungliga strömmedvetna vägen
Källbytesen innehåller varken /StructTreeRoot eller /StructElem. I den snabba profilen släpps det taggade PDF-strukturträdet i stället för att slås ihop, så de objekten måste gå genom avkodningsvägen där motorn kan nulla ut dem medvetet

Beslutet ligger i den objektvisa kopieringsslingan. När alla tre kontrollerna går igenom, går objektets bytes direkt till ShiftIndRefsInSource och sedan till skrivaren; annars kastas bytesen och objektet byggs om med GetObject, förskjuts med ShiftIndRef och serialiseras. Det är värt att se strukturen i den grenen, eftersom ordningen på kontrollerna är det som gör den säker:

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;

En tom ObjectData är signalen att bytevägen avvisade objektet. Den där enda sentineln håller snabb och långsam väg från att driva isär: det finns exakt en plats som avgör och exakt ett återfall

Referensskiftets tillståndsmaskin och dess kantfall

Att skriva om indirekta referenser på bytesnivå är bedrägligt lätt att göra fel, eftersom R och sifferföljder finns överallt i ett PDF-objekt i sammanhang som inte är referenser. ShiftIndRefsInSource är en liten handskriven scanner som går igenom bytesen en gång och bara skriver om ett tal när det följs, med PDF-vitt mellan tokenen, av ett annat tal och sedan en R avgränsare. De billiga utgångarna kommer först: om förskjutningen är noll eller källan är tom återlämnas bytesen orörda utan att scannern ens startar

Scannerns korrekthet bygger på att känna igen de sammanhang där en referensformad sekvens måste lämnas i fred. Det här är gränserna som är lättast att missa, och var och en hanteras uttryckligen:

Litterala strängar avgränsade av ( och ) kopieras ordagrant, med spårning av nästlingsdjup och respekt för backslash-escape så att en undangömd parentes inte sabbar djupräkningen. En sträng som (see object 3 0 R for details) innehåller ett skolboksexempel på ett referensmönster som egentligen bara är prosa, och den måste överleva byte för byte
Hexadecimala strängar avgränsade av < och > passerar igenom utan tolkning. Bytesen 52 inuti en hex-sträng är ASCII-koden för R, och en scanner som behandlade hex-innehåll som text kunde skapa en spökreferens. Den inledande << i en ordbok upptäcks först så att en ordbok inte misstas för en hex-sträng
Namnobjekt som börjar med / tas som helhet, från snedstrecket till nästa blanksteg eller avgränsare. Utan detta kunde ett namn som /R (en vanlig resursnyckel) läsas som R på en referens
Kommentarer inledda med % löper till radslut och hoppas över som ogenomskinlig text
Testet mellan tal och R är strikt. En referens känns bara igen som N blanksteg G blanksteg R med R avslutat av blanksteg, en avgränsare eller indata-slut. Om generationsnumret saknas, eller ett R följs av en bokstav, skrivs siffrorna ut oförändrade. Det är det som skyddar heltalet i /Length 1234 och de fyra talen i en MediaBox från att tyst ökas

Kärnan i det strikta testet ser nästan exakt ut som specifikationsmeningen beskriver det:

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;

Endast objektnumret skrivs om; generationsnumret och det exakta ursprungliga blanksteget mellan tokenen kopieras igenom, så utdata blir byte-identisk med indata förutom det enda heltal som behövde ändras. Den precisionen är hela poängen - det är det som gör återanvändning av källbytes likvärdig med en full reserialisering, inte bara nästan likvärdig. Beteendet täcks av en fokuserad uppsättning enhetstester som övar på fristående referenser, referenser inuti arrayer, tal som inte är referenser, litterala strängar, hex-strängar och icke-noll generationsnummer med en förskjutning tillämpad

Varför bokmärken inte kunde återanvända AppendOutline

Att slå ihop flera dokumentbokmärken till ett enda dispositionsträd ser ut som ett jobb för den befintliga AppendOutline hjälpfunktionen, som redan vet hur man graftar ett dokuments toppnivåbokmärken på ett annat. Det är fel verktyg här, och orsaken är en subtil lagerkrock. AppendOutline hittar det nuvarande sista bokmärket på toppnivå genom att låta läsaren gå igenom de ursprungliga filbytesen. Men den snabba sammanslagningen lägger sina ändringar i en buffert för nya objekt via ChangeObject; läsaren ser aldrig de ändringarna. Kedjar du tre eller fler dokument och varje tillägg pekar om det första dokumentets ursprungliga sista bokmärke till det nyaste dokumentet, faller alla de mellanliggande dokumentens bokmärken ur kedjan - bara den kumulativa /Count stannar rätt, vilket gör buggen lätt att missa tills någon öppnar bokmärkespanelen

Den snabba vägen löser det med en tvåfasig, metadata-driven injektion som aldrig går om läsaren. En första genomgång av alla indata samlar, per dokument, dispositionens rotobjekt och generationsnummer, de första och sista bokmärkesnumren på toppnivå, och rotens /Count. Från den sammanfattningen räknar koden ut de globala objektnumren för varje länk den behöver smida - varje dokuments toppnivå /Parent till den delade roten, det första bokmärkets /Prev till det föregående dokumentets sista, det sista bokmärkets /Next till det nästa dokumentets första - med ren objektnummersaritmetik. Bakom detta finns en skrivordningsbegränsning: det första dokumentets objekt skrivs ut innan något följande dokument ens öppnas, så alla det första dokumentets dispositionredigeringar (rot /Count och /Last, och det gamla sista bokmärkets /Next) måste kunna uttryckas som aritmetik som inte behöver något senare dokument i handen. Varje följande dokuments redigeringar tillämpas på plats efter att det har öppnats men innan det skrivs, så de följer med ut genom samma ändringsobjektsväg

Offset-justeringsinvarianten som håller ihop allt

Både referensskiftet och bokmärkesinjektionen är beroende av en aritmetisk invariant, och det är hela konstruktionens sköraste antagande. En referens som injiceras i ett följande dokument skrivs som målets globala objektnummer minus det dokumentets Offset, så att när objektet senare förskjuts med ShiftIndRef(Offset) landar värdet på det avsedda globala numret. Det första dokumentet får Offset = 0 och använder globala nummer direkt. För att den subtraktionen ska vara korrekt måste den löpande offset-sekvens som används under injektionen matcha offset-sekvensen som används när objekten till slut skrivs ut

Det gör den, tack vare en egenskap i hur sid- och formulärsammanfogningarna fungerar: AddPages, AddFields, och AddFieldFonts ändrar bara det första dokumentets befintliga objekt - de lägger aldrig till några nya. Så det första dokumentets objektantal är oförändrat genom sid-sammanfogningssteget, och varje följande dokuments offset (summan av alla föregående dokumentens objektantal) förblir stabil från injektion till utskrift. Bryt det - inför ett steg som skapar ett nytt objekt mitt i en sammanslagning - och varje sid- och bokmärkesreferens nedströms skulle hamna fel med det antal objekt du lade till. Invarianten är tyst, men den bär lasten

Tre ingångspunkter över en motor

Den snabba vägen är inte en gaffel av sammanslagningskoden. I samma arbete styckades den bytevisa motorn ut till en enda intern rutin, MergeFileListInternal(ListName, OutputFileName, PreserveStructTree, StrictMode), och de publika API:erna blev tunna omslag som väljer två flaggor:

MergeFileListFast anropar motorn med strukturträdsbevarande av - den magraste vägen, som släpper den taggade PDF-trädet så att bytevägen gäller för flest objekt
MergeFileList anropar den med bevarande på, så att strukturträdet överlever och resultatet förblir en användbar taggad PDF. Den vanliga vägen ärver också sammanslagningen av bokmärken och formulär över flera dokument
MergeFileListStrict sätter på strikt läge: den första metadataomgången stoppar vid det första indata som inte rapporterar en ren sammanslagning, så bara dokumenten som samlats före den dåliga filen ingår, i stället för att hoppa över den dåliga filen och fortsätta

Att slå ihop vägarna gjorde också att den ordinarie sammanslagningen kunde byggas om från en parvis O(N²) loop - slå ihop fil ett och två, slå ihop resultatet med tre, och så vidare, och parsa om den växande ackumulatorn varje steg - till en enda linjär genomgång som öppnar varje indata en gång. De två sedan länge etablerade tvåfil- och tvåströmspunkterna, MergeFiles och MergeStreams, är orörda och finns kvar för anropare som verkligen vill ha en parvis sammanslagning

En ärlig not om strukturträd-beteendet, eftersom det bet testsviten. Den snabba vägens "släpp" är inte totalt: det tar bort det första dokumentets katalogreferens till /StructTreeRoot, men själva strukturträd-objektet skrivs fortfarande ut som ett föräldralöst objekt. Så den snabba utdataens bytes innehåller fortfarande /StructTreeRoot strängen, och du kan inte skilja snabb och vanlig utdata åt genom att söka efter den strängen - den verkliga skillnaden är om katalogen fortfarande når strukturträdet, vilket avgör om filen fortfarande är en navigerbar taggad PDF

När man ska välja vilken väg

Bytevägen är en genomströmningsoptimering för att sätta ihop många dokument där du inte behöver att det taggade PDF-strukturträdet bevaras - rapportpaketering, utdragskörningar, batchsammanfogning. Mätt över upprepade sammanslagningar av medelstora till stora indatauppsättningar skar byteåteranvändningen bort ungefär fyra till tretton procent av väggklocktiden beroende på objektblandning, utan nya fel på små eller felaktiga indata, eftersom varje objekt som scannern inte kan bevisa säkert faller tillbaka till full parsning. Om du behöver strukturträdet intakt för tillgänglighet, använd den vanliga taggade PDF sammanslagningsvägen, som bevarar det; och om du arbetar med mycket stora enskilda filer snarare än många indata, gäller bytekopieringsteknikerna som beskrivs i följeskrivelsen om stor PDF-sammanslagning och delning med direkt filåtkomst tillämpar samma filosofi om att "kopiera bytes, undvika hela objekträdet" i filskala

Sammanslagningsrutinerna och deras snabba och strikta varianter är en del av PDFlibPas Delphi PDF Library, vars dokumentation innehåller hela referensen för fil-list-API:et och sammanslagningsalternativen som beskrivs här