Hitro združevanje PDF v Delphi

Zlepljanje PDF-jev zveni, kot da bi moralo biti poceni. Vsebina strani je že postavljena, pisave so že vdelane, slike so že stisnjene. Načeloma je združevanje samo knjigovodstvo: preštevilčiti objekte, da se številčni prostori dveh datotek ne zaletijo, sešiti drevesa strani skupaj, popraviti tabelo medsklicev in zapisati. V praksi pa večina kode za merge to poceni naravo zavrže. Za vsak objekt v vsaki vhodni datoteki izvede popolno razčlenitev v tokenizirano drevo objektov, spremeni nekaj posrednih sklicev, nato pa drevo znova serializira v bajte. Razčlenitev in ponovna serializacija sta dragi polovici, pri veliki večini objektov pa proizvedeta zaporedje bajtov, skoraj enako tistemu, ki je šlo noter

PDFlibPas je izvorni motor PDF v Object Pascal za Delphi in C++Builder, njegova hitra pot za merge pa obstaja zato, da ta krog preskoči povsod, kjer je to dokazljivo varno. Ideja je ozka, vendar se izplača čez cele nabore dokumentov: za nespremenjen objekt brez toka vzemite izvorne bajte dobesedno in naredite samo en prepis posrednih sklicev na ravni bajtov, pri čemer vsako N G R spremenite v (N+Offset) G R. Brez tokenizerja, brez drevesa objektov, brez serializerja. Ta članek razloži, kje je ta bližnjica zakonita, stroj stanj parserja, ki prepis na ravni bajtov opravi brez kvarjenja česarkoli, zakaj je združevanje zaznamkov potrebovalo povsem drugačen mehanizem in kako je bila hkrati navadna pot za merge predelana iz kvadratne v linearno

Zakaj je preštevilčenje objektov pravi strošek združevanja

Vsak PDF nosi svoj lasten prostor številčenja objektov. Datoteka A ima objekt 1, objekt 2 in tako naprej; datoteka B ima svoj objekt 1, objekt 2 in tako naprej. Objektov iz B ne morete nespremenjenih spustiti v datoteko A, ker bi se številke zaletele in bi se vsak posredni sklic znotraj B zdaj razrešil v napačen objekt. Popravek je odmik: če se A konča pri številu objektov Offset, potem objekt N iz B v izhodu postane objekt N+Offset, vsak sklic N G R, ki se pojavi kjerkoli znotraj objektov B, pa mora biti zamaknjen na (N+Offset) G R, da se ujema

Ta zamik je celotno pomensko delo združevanja telesa. Popravki drevesa strani in združitev AcroForm so majhni, omejeni popravki na peščici objektov. Masovno delo je prepisovanje sklicev čez tisoče objektov, naiven način pa je, da vsak objekt razčlenite, da lahko sklice najdete strukturno. MergeFileListFast pri PDFlibPas zavzame nasprotno stališče: sklice je mogoče najti tudi v surovih bajtih, če ste previdni pri kontekstih, v katerih zaporedje številka-presledek-številka-presledek-R ni sklic. Preskočite razčlenitev, premaknite na mestu, strošek na objekt pa se sesede na en sam linearni pregled bajtov, ki bi jih tako ali tako kopirali

Kdaj je ponovna uporaba izvornih bajtov dokazljivo varna

Pot na ravni bajtov se uporabi samo takrat, ko za objekt, kopiran iz naslednjega dokumenta, hkrati veljajo vsi trije pogoji. Če kateri koli pade, se objekt vrne na celotno pot decode-and-reserialize, zato pravilnost vedno premaga hitrost:

Doc2.IsChangedObject(X) je False. Če je motor za merge objekt v pomnilniku že spremenil (na primer objekt strani, katerega /Parent je bil preusmerjen), je drevo v pomnilniku vir resnice, izvorni bajti pa so zastareli. Ustrezajo samo nedotaknjeni objekti
Izvorni bajti ne vsebujejo ključne besede stream. Telo pretočnega objekta je neprozoren binarni blok, uokvirjen z stream/endstream, naiven pregled sklicev po stisnjenih ali šifriranih podatkih toka pa bi z veseljem "našel" in pokvaril vzorce bajtov, ki so videti kot sklici. Pretočni objekti ostanejo na prvotni poti, ki razume tokove
Izvorni bajti ne vsebujejo niti /StructTreeRoot niti /StructElem. V hitrem profilu se drevo strukture označenega PDF odvrže namesto združi, zato morajo ti objekti skozi pot dekodiranja, kjer jih motor lahko namerno izniči

Odločitev živi v zanki kopiranja po objektih. Ko vsi trije pregledi uspejo, gredo bajti objekta neposredno v ShiftIndRefsInSource in nato zapisovalniku; sicer se bajti zavržejo in objekt se znova zgradi z GetObject, zamakne z ShiftIndRef in serializira. Strukturo te veje je vredno videti, ker prav vrstni red preverjanj ohranja varnost:

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;

Prazen ObjectData je signal, da je pot na ravni bajtov ta objekt zavrnila. Ta en sam signal ohranja hitro in počasno pot skupaj: natanko eno mesto odloča in natanko eno mesto vrača nazaj

Stroj stanj za premikanje sklicev in njegovi robni primeri

Prepis posrednih sklicev na ravni bajtov je varljivo lahko narediti narobe, ker se R in nizi števk pojavljajo povsod po objektu PDF v kontekstih, ki niso sklici. ShiftIndRefsInSource je majhen ročno napisan pregledovalnik, ki bajte prehodi enkrat in številko prepiše samo takrat, ko ji po presledkih PDF med žetoni sledi druga številka in nato ločilo R. Poceni izhodi pridejo prvi: če je odmik nič ali je vir prazen, se bajti vrnejo nedotaknjeni, ne da bi sploh vstopili v pregledovalnik

Pravilnost pregledovalnika stoji na prepoznavanju kontekstov, v katerih mora zaporedje v obliki sklica ostati pri miru. To so meje, ki jih je najlažje zgrešiti, in vsaka je obravnavana izrecno:

Dobesedni nizi, razmejeni z ( in ), se kopirajo dobesedno, pri čemer se sledi globini gnezdenja in upošteva ubežno zaporedje z obratno poševnico, da ubežni oklepaj ne pokvari štetja globine. Niz, kot je (see object 3 0 R for details), vsebuje šolski vzorec sklica, ki je v resnici samo proza, in ta mora preživeti bajt za bajtom
Šestnajstiški nizi, razmejeni z < in >, se prepustijo brez interpretacije. Bajti 52 znotraj šestnajstiškega niza so koda ASCII za R, pregledovalnik, ki bi hex-vsebino obravnaval kot besedilo, pa bi lahko ustvaril fantomski sklic. Otvoritveni << slovarja se zazna najprej, da slovar ne bi bil zamenjan za šestnajstiški niz
Imenski objekti, ki se začnejo z /, se porabijo kot celota, od poševnice do naslednjega presledka ali ločila. Brez tega bi ime, kot je /R (pogost ključ vira), lahko prebrali kot R sklica
Komentarji, uvedeni z %, tečejo do konca vrstice in se preskočijo kot neprozorno besedilo
Preizkus številka-nato-R je strog. Sklic je prepoznan samo kot N presledek G presledek R z R, zaključenim s presledkom, ločilom ali koncem vhoda. Če številka generacije manjka ali R sledi črka, se števke izpišejo nespremenjene. To je tisto, kar ščiti celo število v /Length 1234 in štiri številke v MediaBox pred tihim povečanjem

Jedro tega strogega preizkusa se bere skoraj natanko tako, kot ga opisuje stavek iz specifikacije:

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;

Prepisana je samo številka objekta; številka generacije in natančni izvorni presledki med žetoni se kopirajo naprej, zato je izhod bajtno enak vhodu, razen enega samega celega števila, ki se je moralo spremeniti. Ta natančnost je celoten smisel - prav to naredi ponovno uporabo izvornih bajtov enakovredno popolni ponovni serializaciji, ne le približno podobno. Vedenje pokriva osredotočen nabor enotskih testov, ki preizkušajo gole sklice, sklice znotraj polj, številke, ki niso sklici, dobesedne nize, šestnajstiške nize in neničelne številke generacije z uporabljenim odmikom

Zakaj zaznamki niso mogli ponovno uporabiti AppendOutline

Združevanje zaznamkov več dokumentov v eno drevo orisa je videti kot naloga za obstoječi pomočnik AppendOutline, ki že zna vrhnje zaznamke enega dokumenta cepiti na drugega. Tukaj je to napačno orodje, razlog pa je subtilno neskladje plasti. AppendOutline poišče trenutni zadnji vrhnji zaznamek tako, da bralnik sprehodi po izvornih bajtih prvotne datoteke. Hitra združitev pa svoje spremembe zloži v medpomnilnik novih objektov prek ChangeObject; bralnik teh sprememb nikoli ne vidi. Povežite tri ali več dokumentov in vsak append preusmeri prvotni zadnji zaznamek prvega dokumenta na najnovejši dokument, zato zaznamki vseh vmesnih dokumentov padejo iz verige - pravilen ostane samo kumulativni /Count, zato je hrošča lahko spregledati, dokler nekdo ne odpre plošče zaznamkov

Hitra pot to reši z dvofaznim, z metapodatki vodenim vbrizgom, ki bralnika nikoli več ne prehodi. Prvi prehod čez vse vhode za vsak dokument zbere korenski objekt orisa in številke generacije, številki prvega in zadnjega vrhnjega zaznamka ter /Count korena. Iz tega povzetka koda izračuna globalne številke objektov vseh povezav, ki jih mora skovati - /Parent vsakega dokumenta na skupni koren, /Prev prvega zaznamka na zadnjega iz prejšnjega dokumenta, /Next zadnjega zaznamka na prvega iz naslednjega dokumenta - z uporabo čiste aritmetike številk objektov. V ozadju obstaja omejitev vrstnega reda zapisovanja: objekti prvega dokumenta se zapišejo, še preden se katerikoli naslednji dokument sploh odpre, zato morajo biti vsi popravki orisa prvega dokumenta (korenska /Count in /Last, ter /Next starega zadnjega zaznamka) izraženi kot aritmetika, ki ne potrebuje poznejšega dokumenta v roki. Popravki vsakega naslednjega dokumenta se uporabijo na mestu po njegovem odprtju, vendar pred zapisom, zato odpotujejo ven skozi isto pot spremenjenega objekta

Invarianta poravnave odmikov, ki vse poveže

Tako premik sklicev kot vbrizg zaznamkov sta odvisna od ene aritmetične invarianti in to je najbolj krhka predpostavka v celotni zasnovi. Sklic, vbrizgan v naslednji dokument, se zapiše kot ciljna globalna številka objekta minus Offset tega dokumenta, tako da ob poznejšem premiku z ShiftIndRef(Offset) vrednost pristane na predvideni globalni številki. Prvi dokument dobi Offset = 0 in neposredno uporablja globalne številke. Da je to odštevanje pravilno, se mora zaporedje tekočih odmikov, uporabljeno med vbrizgom, ujemati z zaporedjem odmikov, uporabljenim pri končnem zapisovanju objektov

To se zgodi zaradi lastnosti načina, kako delujeta združevanje strani in obrazcev: AddPages, AddFields in AddFieldFonts spreminjajo samo obstoječe objekte prvega dokumenta - nikoli ne dodajo novih. Zato število objektov prvega dokumenta ostane čez fazo združevanja strani nespremenjeno, odmik vsakega naslednjega dokumenta (vsota števil objektov vseh predhodnih dokumentov) pa ostane stabilen od vbrizga do zapisovanja. Prelomite to - uvedite stopnjo, ki sredi merge ustvari nov objekt - in vsi nadaljnji sklici strani in zaznamkov bi zgrešili za število dodanih objektov. Invarianta je tiha, vendar nosi breme

Tri vstopne točke nad enim motorjem

Hitra pot ni veja kode za merge. V isti liniji dela je bil motor na ravni bajtov izločen v eno samo interno rutino MergeFileListInternal(ListName, OutputFileName, PreserveStructTree, StrictMode), javni API-ji pa so postali tanke ovojnice, ki izbereta dve zastavici:

MergeFileListFast pokliče motor z izključenim ohranjanjem strukturnega drevesa - najvitkejša pot, ki drevo označenega PDF odvrže, da se pot na ravni bajtov lahko uporabi za največ objektov
MergeFileList ga pokliče z vključenim ohranjanjem, tako da strukturno drevo preživi in rezultat ostane uporaben označen PDF. Ta navadna pot podeduje tudi združevanje zaznamkov in obrazcev prek več dokumentov
MergeFileListStrict vklopi strogi način: prvi prehod po metapodatkih se ustavi pri prvem vhodu, ki ne poroča o čistem merge, tako da so vključeni samo dokumenti, zbrani pred slabo datoteko, namesto da bi slabo datoteko preskočil in nadaljeval

Zlaganje poti skupaj je omogočilo tudi, da je bila navadna združitev obnovljena iz parne zanke O(N²) - združi datoteko ena in dve, ta rezultat združi s tretjo in tako naprej ter pri vsakem koraku znova razčleni rastoči akumulator - v en sam linearen prehod, ki vsak vhod odpre enkrat. Dve dolgoletni vstopni točki za dve datoteki oziroma dva toka, MergeFiles in MergeStreams, ostaneta nedotaknjeni in na voljo klicateljem, ki si res želijo združevanje po parih

Ena poštena opomba o vedenju strukturnega drevesa, ker je ugriznila testno zbirko. Hitra pot ga ne "odvrže" povsem: odstrani sklic kataloga prvega dokumenta na /StructTreeRoot, sam objekt strukturnega drevesa pa se vseeno zapiše ven kot sirota. Zato bajti hitrega izhoda še vedno vsebujejo niz /StructTreeRoot in hitrega izhoda od navadnega ne morete ločiti z iskanjem po tem nizu - prava razlika je v tem, ali katalog še vedno doseže strukturno drevo, kar določa, ali je datoteka še vedno navigabilen označen PDF

Kdaj poseči po kateri poti

Pot na ravni bajtov je optimizacija prepustnosti za sestavljanje mnogih dokumentov, kjer vam ni treba ohraniti drevesa strukture označenega PDF - združevanje poročil, teki izpiskov, paketno lepljenje. Pri ponavljajočih se meritvah nad srednje velikimi do velikimi nabori vhodov je ponovno uporabljanje bajtov odrezalo približno štiri do trinajst odstotkov stenskega časa, odvisno od mešanice objektov, brez novih napak na majhnih ali napačno oblikovanih vhodih, ker vsak objekt, ki ga pregledovalnik ne more dokazati kot varnega, pade nazaj na popolno razčlenitev. Če drevo strukture za dostopnost potrebujete nedotaknjeno, uporabite navadno pot za merge tagged-PDF, ki ga ohrani; in če delate z zelo velikimi posameznimi datotekami namesto z mnogimi vhodi, tehnike kopiranja bajtov, opisane v spremljevalnem članku o združevanju in deljenju velikih PDF z neposrednim dostopom do datoteke na ravni datoteke uveljavijo isto filozofijo "kopiraj bajte, izogni se polnemu drevesu objektov"

Rutine za merge ter njihove hitre in stroge različice so del PDFlibPas Delphi PDF Library, katere dokumentacija vsebuje celoten reference za API seznama datotek in tukaj opisane možnosti združevanja

Hitro združevanje PDF v Delphi: premikanje sklicev na ravni bajtov