Nopea PDF-yhdistäminen Delphissä: bittitason viitevaihto

PDF-tiedostojen yhdistämisen luulisi olevan edullista. Sivun sisältö on jo valmiiksi aseteltu, fontit on upotettu ja kuvat on pakattu. Periaatteessa yhdistäminen on pelkkää kirjanpitoa: numeroidaan objektit uudelleen, jotta kahden tiedoston numerointiavaruudet eivät enää törmää, liitetään sivupuut yhteen, korjataan ristiviittaustaulukko (cross-reference table) ja kirjoitetaan. Käytännössä useimmat yhdistämiskoodit heittävät tämän edullisuuden hukkaan. Jokaiselle objektille jokaisessa syötetiedostossa suoritetaan täysi jäsennys tokenisoiduksi objektipuuksi, muokataan paria epäsuoraa viitettä ja sarjallistetaan puu takaisin tavuiksi. Jäsennys ja uudelleensarjallistus ovat prosessin kalleimmat osat, ja valtaosalle objekteista ne tuottavat tavujonon, joka on lähes identtinen alkuperäisen kanssa

PDFlibPas on alkuperäinen Object Pascal -pohjainen PDF-moottori Delphille ja C++Builderille, ja sen nopea yhdistämispolku on olemassa ohittamaan tämän edestakaisen kierroksen aina, kun se on todennettavasti turvallista. Idea on kapea-alainen, mutta se maksaa itsensä takaisin kokonaisissa dokumenttisarjoissa: muokkaamattomalle ei-virtaobjektille (non-stream object) otetaan alkuperäiset lähdetavut sellaisenaan ja tehdään yksi bittitason uudelleenkirjoitus niiden sisältämille epäsuorille viitteille, muuttaen jokaisen muodon N G R muotoon (N+Offset) G R. Ei tokenisoijaa, ei objektipuuta, ei sarjallistajaa. Tässä artikkelissa käydään läpi, missä tämä oikotie on laillinen, käsitellään bittitason uudelleenkirjoituksen tekevää jäsentimen tilakonetta, joka ei korruptoi mitään, miksi kirjanmerkkien yhdistäminen tarvitsi täysin erilaisen mekanismin ja miten tavallinen yhdistämispolku rakennettiin samalla uudelleen neliöllisestä (quadratic) lineaariseksi

Miksi objektien uudelleennumerointi on yhdistämisen todellinen hinta

Jokaisella PDF:llä on oma objektinumerointiavaruutensa. Tiedostossa A on objekti 1, objekti 2 ja niin edelleen; tiedostossa B on oma objekti 1, objekti 2 ja niin edelleen. Et voi pudottaa B:n objekteja sellaisenaan A:n tiedostoon, koska numerot törmäisivät ja jokainen epäsuora viite B:n sisällä viittaisi nyt väärään objektiin. Ratkaisu on siirtymä (offset): jos A päättyy objektimäärään Offset, niin B:n objektista N tulee tulosteessa objekti N+Offset, ja jokainen B:n objektien sisällä esiintyvä viite N G R on siirrettävä muotoon (N+Offset) G R

Tämä siirtymä on koko rungon yhdistämisen semanttinen tehtävä. Sivupuun korjaukset ja AcroForm-yhdistäminen ovat pieniä, rajattuja muokkauksia muutamaan objektiin. Suurin työ on viitteiden uudelleenkirjoittaminen tuhansissa objekteissa, ja naiivi tapa tehdä se on jäsentää jokainen objekti, jotta viitteet löytyvät rakenteellisesti. PDFlibPas:n MergeFileListFast ottaa vastakkaisen kannan: viitteet ovat löydettävissä myös raaoista tavuista, jos ollaan varovaisia niiden kontekstien kanssa, joissa numero-välilyönti-numero-välilyönti-R -sarja ei ole viite. Ohita jäsennys, tee siirto paikoillaan, ja objektikohtainen kustannus kutistuu yhdeksi lineaariseksi skannaukseksi tavuista, jotka olisit joka tapauksessa kopioinut

Milloin lähdetavujen uudelleenkäyttö on todennettavasti turvallista

Tavutason polku valitaan vain silloin, kun kaikki kolme ehtoa täyttyvät seuraavasta dokumentista kopioitavalle objektille. Minkä tahansa ehdon epäonnistuminen lähettää objektin takaisin täyden purku- ja uudelleensarjallistamisreitin kautta, joten oikeellisuus voittaa aina nopeuden:

Doc2.IsChangedObject(X) on False. Jos yhdistämismoottori muutti jo objektia muistissa (esimerkiksi sivukohdetta, jonka /Parent osoitettiin uudelleen), muistissa oleva puu on totuuden lähde ja alkuperäiset tavut ovat vanhentuneita. Vain muuttumattomat objektit kelpaavat
Lähdetavut eivät sisällä stream-avainsanaa. Virtaobjektin runko on läpinäkymätöntä binääritietoa, jota rajaavat avainsanat stream/endstream. Naiivi viiteskannaus pakatun tai salatun virtatiedon yli löytäisi ja korruptoisi helposti viitteiltä näyttäviä tavukuvioita. Virtaobjektit noudattavat alkuperäistä virta-tietoista polkua
Lähdetavut eivät sisällä avainsanaa /StructTreeRoot eivätkä /StructElem. Nopeassa profiilissa merkityn PDF:n (tagged PDF) rakenne-puu pudotetaan sen sijaan, että se yhdistettäisiin, joten näiden objektien on mentävä purkupolun kautta, jossa moottori voi nollata ne tarkoituksella

Päätös elää objektikohtaisessa kopiointisilmukassa. Kun kaikki kolme tarkistusta menevät läpi, objektin tavut menevät suoraan ShiftIndRefsInSource-aliohjelmalle ja sieltä kirjoittajalle; muussa tapauksessa tavut hylätään ja objekti rakennetaan uudelleen GetObject-metodilla, siirretään ShiftIndRef-metodilla ja sarjallistetaan. Tämän haaran rakenne on näkemisen arvoinen, koska tarkistusten järjestys pitää sen turvallisena:

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;

Tyhjä ObjectData on merkki siitä, että tavupolku hylkäsi objektin. Tämä yksittäinen vartija estää nopean ja hitaan reitin erkaantumisen: on tarkalleen yksi paikka, joka päättää, ja tarkalleen yksi varasuunnitelma

Viitteensiirron tilakone ja sen reunatapaukset

Epäsuorien viitteiden bittitason uudelleenkirjoitus on petollisen helppo tehdä väärin, koska R-merkki ja numerosarjat esiintyvät kaikkialla PDF-objektissa yhteyksissä, jotka eivät ole viitteitä. ShiftIndRefsInSource on pieni käsin kirjoitettu skanneri, joka käy tavut läpi kerran ja kirjoittaa numeron uudelleen vain, jos sitä seuraa (PDF-tyhjämerkillä erotettuna) toinen numero ja sitten R-erotin. Helpot poistumiset käsitellään ensin: jos siirtymä on nolla tai lähde on tyhjä, tavut palautetaan koskemattomina menemättä lainkaan skanneriin

Skannerin oikeellisuus perustuu sellaisten kontekstien tunnistamiseen, joissa viitteen muotoinen sarja on jätettävä rauhaan. Nämä rajat on helpointa unohtaa, ja jokainen niistä käsitellään erikseen:

Kirjaimelliset merkkijonot, joita rajaavat ( ja ), kopioidaan sellaisenaan, seuraten sisäkkäisyyden syvyyttä ja kunnioittaen kenoviivalla suojattuja merkkejä, jotta suojattu sulkumerkki ei sekoita syvyyslaskentaa. Merkkijono kuten (see object 3 0 R for details) sisältää tyypillisen viitekuvion, joka on todellisuudessa vain tekstiä, ja sen on säilyttävä tavu tavulta
Heksadesimaaliset merkkijonot, joita rajaavat < ja >, viedään läpi tulkitsematta. Heksatavut 52 vastaavat ASCII-merkkiä R, ja skanneri, joka käsittelisi heksadataa tekstinä, voisi luoda haamukoodeja. Sanakirjan avaava << tunnistetaan ensin, jotta sanakirjaa ei luulla heksamerkkijonoksi
Nimiobjektit, jotka alkavat merkillä /, kulutetaan kokonaan vinoviivasta seuraavaan tyhjämerkkiin tai erottimeen asti. Ilman tätä nimen /R (yleinen resurssiavain) kaltainen kohde voitaisiin tulkita viitteen R-merkiksi
Kommentit, jotka alkavat merkillä %, ulottuvat rivin loppuun ja ohitetaan läpinäkymättömänä tekstinä
Numero-sitten-R-testi on tiukka. Viite tunnistetaan vain muodossa N tyhjämerkki G tyhjämerkki R, jossa R päättyy tyhjämerkkiin, erottimeen tai syötteen loppuun. Jos sukupolven numero puuttuu tai R-merkkiä seuraa kirjain, numerot jätetään ennalleen. Tämä suojaa kokonaislukua avaimessa /Length 1234 ja MediaBox-osion neljää numeroa tulemasta virheellisesti korotetuiksi

Vain objektin numero kirjoitetaan uudelleen; sukupolvinumero ja tokenien välinen alkuperäinen tyhjä tila kopioidat sellaisenaan, joten tuloste on tavuittain identtinen syötteen kanssa lukuun ottamatta sitä yhtä kokonaislukua, jonka piti muuttua. Tämä tarkkuus on koko asian ydin – se tekee lähdetavujen uudelleenkäytöstä täysin vastaavan kuin täysi uudelleensarjallistus, eikä vain lähellä sitä. Toiminta on katettu kohdistetuilla yksikkötesteillä, jotka testaavat paljaita viitteitä, viitteitä taulukoiden sisällä, muita kuin viitenumeroita, kirjaimellisia merkkijonoja, heksamerkkijonoja ja nollasta poikkeavia sukupolvinumeroita siirtymää sovellettaessa

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;

Miksi kirjanmerkit eivät voineet käyttää AppendOutlinea uudelleen

Useiden dokumenttien kirjanmerkkien yhdistäminen yhdeksi jäsennyspuuksi näyttää sopivalta tehtävältä olemassa olevalle AppendOutline-apuohjelmalle, joka osaa jo liittää yhden dokumentin ylätason kirjanmerkit toiseen. Se on kuitenkin väärä työkalu tähän tehtävään, ja syynä on hienovirheinen tasojen yhteensopimattomuus. AppendOutline etsii nykyisen viimeisen ylätason kirjanmerkin lukemalla lukijalla alkuperäisiä tiedostotavuja. Nopea yhdistäminen kuitenkin vaiheistaa muokkauksensa uusien objektien puskuriin ChangeObject-metodin kautta; lukija ei koskaan näe näitä muokkauksia. Ketjuta kolme tai useampia dokumentteja, ja jokainen lisäys osoittaa ensimmäisen dokumentin alkuperäisen viimeisen kirjanmerkin uusimpaan dokumenttiin, jolloin kaikkien väliin jäävien dokumenttien kirjanmerkit putoavat ketjusta – vain kumulatiivinen /Count pysyy oikeana, mikä tekee virheestä helpon unohtaa, kunnes joku avaa kirjanmerkkipaneelin

Nopea polku ratkaisee sen kaksivaiheisella, metatietoihin perustuvalla injektiolla, joka ei koskaan käy lukijaa uudelleen läpi. Ensimmäinen vaihe kaikkien syötteiden yli kerää dokumenttikohtaisesti jäsennyspuun juuriobjektin ja sukupolvinumerot, ensimmäisen ja viimeisen ylätason kirjanmerkin numerot sekä juuren /Count-arvon. Tästä tiivistelmästä koodi laskee jokaisen tarvitsemansa linkin globaalit objektinumerot – kunkin dokumentin ylätason /Parent-viitteen jaettuun juureen, ensimmäisen kirjanmerkin /Prev-viitteen edellisen dokumentin viimeiseen, ja viimeisen kirjanmerkin /Next-viitteen seuraavan dokumentin ensimmäiseen – käyttäen puhdasta objektinumeromatematiikkaa. Tässä on taustalla kirjoitusjärjestyksen rajoitus: ensimmäisen dokumentin objektit kirjoitetaan ulos ennen kuin mitään seuraavista dokumenteista edes avataan, joten kaikki ensimmäisen dokumentin jäsennyspuun muokkaukset (juuren /Count ja /Last sekä vanhan viimeisen kirjanmerkin /Next) on voitava ilmaista matematiikalla, joka ei tarvitse myöhempiä dokumentteja käsiinsä. Jokaisen seuraavan dokumentin muokkaukset sovelletaan paikoilleen sen avaamisen jälkeen, mutta ennen kirjoittamista, joten ne kulkevat saman ChangeObject-polun kautta

Siirron ja kohdistuksen invariantti, joka sitoo kaiken yhteen

Sekä nopea yhdistäminen että kirjanmerkkien injektointi riippuvat yhdestä aritmeettisesta invariantista, ja se on koko suunnittelun haurain oletus. Seuraavaan dokumenttiin injektoitu viite kirjoitetaan muodossa kohteen globaali objektinumero miinus kyseisen dokumentin siirtymä (Offset), jotta kun objektia myöhemmin siirretään ShiftIndRef(Offset)-kutsulla, arvo osuu haluttuun globaaliin numeroon. Ensimmäinen dokumentti saa arvon Offset = 0 ja käyttää globaaleja numeroita suoraan. Jotta tämä vähennyslasku olisi oikein, injektion aikana käytetyn juoksevan siirtymäsekvenssin on vastattava sitä siirtymäsekvenssiä, jota käytetään objektien lopullisessa kirjoitusvaiheessa

Se vastaa, koska sivujen ja lomakkeiden yhdistäminen toimii tietyllä tavalla: AddPages, AddFields ja AddFieldFonts muokkaavat vain ensimmäisen dokumentin olemassa olevia objekteja – ne eivät koskaan lisää uusia. Joten ensimmäisen dokumentin objektimäärä pysyy muuttumattomana sivujen yhdistämisvaiheessa, ja jokaisen seuraavan dokumentin siirtymä (kaikkien edellisten dokumenttien objektimäärien summa) pysyy vakaana injektiosta kirjoittamiseen asti. Jos rikot tämän – esimerkiksi tuomalla vaiheen, joka luo uuden objektin kesken yhdistämisen – jokainen sivun ja kirjanmerkin viite jälkipäässä heittäisi lisäämiesi objektien määrällä. Invariantti on hiljainen, mutta se kantaa kuorman

Kolme sisääntulopistettä yhden moottorin päällä

Nopea polku ei ole haarautuma yhdistämiskoodista. Samassa yhteydessä tavutason moottori refaktoroitiin yhdeksi sisäiseksi rutiiniksi MergeFileListInternal(ListName, OutputFileName, PreserveStructTree, StrictMode), ja julkisista API:ista tuli ohuita kääreitä, jotka valitsevat kaksi lippua:

MergeFileListFast kutsuu moottoria rakenne-puun säilytys pois päältä – tämä on kevein polku, joka pudottaa merkityn PDF-puun, jotta tavutason reitti soveltuu mahdollisimman moneen objektiin
MergeFileList kutsuu sitä säilytys päällä, joten rakenne-puu säilyy ja lopputulos pysyy käyttökelpoisena merkittynä PDF-tiedostona. Tämä tavallinen polku perii myös useamman dokumentin kirjanmerkkien ja lomakkeiden yhdistämisen
MergeFileListStrict ottaa käyttöön tiukan tilan: ensimmäinen metatietojen läpikäynti pysähtyy ensimmäiseen syötteeseen, joka ei raportoi siistiä yhdistämistä, joten vain ennen viallista tiedostoa kerätyt dokumentit sisällytetään, sen sijaan että viallinen tiedosto ohitettaisiin ja jatkettaisiin

Polkujen yhdistäminen antoi myös mahdollisuuden rakentaa tavallinen yhdistäminen uudelleen neliöllisestä lineaariseksi, joka avaa jokaisen syötteen vain kerran. Kaksi pitkäaikaista sisääntulopistettä, MergeFiles ja MergeStreams, säilyivät koskemattomina ja ovat edelleen käytettävissä kutsujille, jotka todella haluavat parittaisen yhdistämisen. Yksi rehellinen huomautus rakenne-puun käyttäytymisestä, koska se aiheutti päänvaivaa testiryhmälle: nopean polun pudotus (drop) ei ole täydellinen. Se poistaa ensimmäisen dokumentin luetteloviitteen (catalog reference) kohteeseen /StructTreeRoot, mutta itse rakenne-puuobjekti kirjoitetaan silti ulos orpona. Joten nopean polun tulosteen tavut sisältävät edelleen /StructTreeRoot-merkkijonon, eikä nopeaa ja tavallista tulostetta voi erottaa etsimällä kyseistä merkkijonoa – todellinen ero on siinä, viittaako luettelo (catalog) edelleen rakenne-puuhun, mikä määrittää, onko tiedosto edelleen navigoitava merkitty PDF-tiedosto

Milloin valita mikäkin polku

Tavutason polku on suorituskykyoptimointi monien sellaisten dokumenttien yhdistämiseen, joissa et tarvitse merkityn PDF:n rakenne-puun säilyttämistä – esimerkiksi raporttien niputtamiseen, tiliotteiden ajoihin tai eräyhdistämiseen. Mitattuna toistuvilla keskikokoisten ja suurten syötejoukkojen yhdistämisillä, tavujen uudelleenkäyttö lyhensi suoritusaikaa noin 4–13 prosenttia objektien sekoituksesta riippuen. Se ei tuonut uusia virheitä pienillä tai virheellisillä syötteillä, koska kaikki kohteet, joita skanneri ei voi todistaa turvallisiksi, putoavat täyden jäsennyksen polulle. Jos tarvitset rakenne-puun säilyttämistä esteettömyyden vuoksi, käytä tavallista merkityn PDF:n yhdistämispolkua, joka säilyttää sen. Jos työskentelet erittäin suurten yksittäisten tiedostojen parissa useiden syötteiden sijaan, rinnakkaisartikkelissa suurten PDF-tiedostojen yhdistämisestä ja jakamisesta suoralla tiedosto-oikeudella kuvatut tavukopiointitekniikat soveltavat samaa 'kopioi tavut, vältä koko objektipuuta' -filosofiaa tiedostotasolla

Yhdistämisrutiinit ja niiden nopeat sekä tiukat variantit ovat osa PDFlibPas Delphi PDF -kirjastoa, jonka dokumentaatio sisältää täydellisen viitteen tiedostolista-API:lle ja tässä kuvatuille yhdistämisvaihtoehdoille