Greitas PDF sujungimas Delphi aplinkoje: baitų lygmens nuorodų poslinkis

PDF sujungimas skamba taip, tarsi turėtų būti pigus. Puslapio turinys jau išdėliotas, šriftai jau įterpti, vaizdai jau suspausti. Iš principo sujungimas tėra apskaita: pernumeruoti objektus taip, kad dviejų failų numeracijos erdvės nebesikirstų, susiūti puslapių medžius, pataisyti kryžminių nuorodų lentelę ir įrašyti. Praktikoje dauguma sujungimo realizacijų tą pigumą išmeta lauk. Kiekvienam kiekvieno įvesties failo objektui jos atlieka pilną parse į tokenizuotą objektų medį, pakeičia kelias netiesiogines nuorodas, tada visą medį vėl serializuoja į baitus. Būtent parse ir pakartotinis serializavimas yra brangiosios pusės, o didžiajai daugumai objektų jos duoda baitų seką, beveik nesiskiriančią nuo pradinės

PDFlibPas yra gimtasis Object Pascal PDF variklis, skirtas Delphi ir C++Builder, o jo greitasis sujungimo kelias egzistuoja tam, kad šį ratą praleistų visur, kur tai įmanoma įrodyti saugiai. Idėja siaura, bet ji atsiperka per ištisus dokumentų rinkinius: jei nestreaminis objektas nebuvo keistas, paimkite originalius šaltinio baitus pažodžiui ir atlikite vieną baitų lygmens visų juose esančių netiesioginių nuorodų perrašymą, paversdami kiekvieną N G R į (N+Offset) G R. Jokio tokenizatoriaus, jokio objektų medžio, jokio serializatoriaus. Šiame straipsnyje aptariama, kur toks trumpasis kelias leidžiamas, kokia parserio būsenų mašina atlieka baitų perrašymą nieko nesugadindama, kodėl žymių sujungimui prireikė visai kito mechanizmo ir kaip tuo pat metu įprastas sujungimo kelias buvo perstatytas iš kvadratinio į linijinį

Kodėl objektų pernumeravimas yra tikroji sujungimo kaina

Kiekvienas PDF turi savo objektų numeracijos erdvę. Failas A turi 1 objektą, 2 objektą ir taip toliau; failas B turi savąjį 1 objektą, 2 objektą ir taip toliau. Jūs negalite B objektų tiesiog nepakeitę įdėti į A failą, nes numeriai susidurtų ir kiekviena B viduje esanti netiesioginė nuoroda dabar rodytų į neteisingą objektą. Taisymas yra poslinkis: jei A baigiasi ties objektų skaičiumi Offset, tuomet B objektas N išvestyje tampa objektu N+Offset, o kiekviena nuoroda N G R, esanti bet kur B objektų viduje, turi būti perkelta į (N+Offset) G R, kad atitiktų naują padėtį

Tas poslinkis ir yra visa sujungimo semantinė užduotis korpuso lygyje. Puslapių medžio pataisos ir AcroForm sujungimas yra maži, apriboti kelių objektų pakeitimai. Didžioji darbo dalis yra nuorodų perrašymas per tūkstančius objektų, o naivus būdas tam yra išparsinti kiekvieną objektą, kad nuorodas rastumėte struktūriškai. PDFlibPas MergeFileListFast remiasi priešingu požiūriu: nuorodas galima rasti ir žaliuose baituose, jei atsargiai atskiriate kontekstus, kuriuose skaitmuo-tarpas-skaitmuo-tarpas-R seka yra ne nuoroda. Praleiskite parse, atlikite poslinkį vietoje, ir vieno objekto kaina susmunka iki vieno linijinio praėjimo per baitus, kuriuos vis tiek būtumėte kopijavę

Kada šaltinio baitus galima saugiai naudoti pakartotinai

Baitų kelias pasirenkamas tik tada, kai objektui, kopijuojamam iš vėlesnio dokumento, tenkinamos visos trys sąlygos. Jei bent viena iš jų netinka, objektas grąžinamas į pilną decode-and-reserialize maršrutą, todėl teisingumas visada laimi prieš greitį:

• Doc2.IsChangedObject(X) yra False. Jei sujungimo variklis jau pakeitė objektą atmintyje, pavyzdžiui, puslapio objektą, kuriam buvo peradresuotas /Parent, tiesos šaltinis yra atmintyje esantis medis, o originalūs baitai jau pasenę. Tinka tik nepaliesti objektai
• Šaltinio baituose nėra raktinio žodžio stream. Stream objekto korpusas yra nepermatomas dvejetainis turinys, aprėmintas stream/endstream, o naivi nuorodų paieška per suspaustus ar užšifruotus stream duomenis mielai „rastų“ ir sugadintų baitų sekas, panašias į nuorodas. Stream objektai lieka originaliame, stream išmanančiame kelyje
• Šaltinio baituose nėra nei /StructTreeRoot, nei /StructElem. Greitajame profilyje pažymėto PDF struktūros medis atmetamas, o ne sujungiamas, todėl šie objektai turi pereiti decode keliu, kur variklis gali juos sąmoningai nunulinti

Sprendimas gyvena vieno objekto kopijavimo cikle. Kai visi trys patikrinimai praeina, objekto baitai keliauja tiesiai į ShiftIndRefsInSource, o iš ten į rašytoją; kitu atveju baitai atmetami, o objektas atstatomas per GetObject, perstumiamas su ShiftIndRef ir serializuojamas. Verta pamatyti šios šakos struktūrą, nes patikrinimų seka ir yra tai, kas išlaiko visą kelią saugų:

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;

Tuščias ObjectData yra signalas, kad baitų kelias šio objekto atsisakė. Šis vienas sargybinis neleidžia greitajam ir lėtajam maršrutams išsiskirti: yra tik viena vieta, kuri apsisprendžia, ir tik viena atsitraukimo kryptis

Nuorodų poslinkio būsenų mašina ir jos kraštiniai atvejai

Baitų lygmens netiesioginių nuorodų perrašymą stebėtinai lengva sugadinti, nes R ir skaitmenų sekos PDF objekte pasirodo daugybėje kontekstų, kurie visai nėra nuorodos. ShiftIndRefsInSource yra nedidelis ranka rašytas skeneris, vieną kartą pereinantis per baitus ir perrašantis skaičių tik tada, kai po jo, PDF tarpais atskirtas, eina kitas skaičius ir tada ribotuvu užbaigtas R. Pirmiausia ateina pigūs ankstyvi išėjimai: jei poslinkis lygus nuliui arba šaltinis tuščias, baitai grąžinami nepakeisti net nepradėjus skenerio

Skenerio teisingumas remiasi tuo, kad jis atpažįsta kontekstus, kuriuose į nuorodą panaši seka turi būti palikta ramybėje. Šias ribas lengviausia praleisti, todėl kiekviena iš jų apdorojama aiškiai:

• Tiesioginės eilutės, apribotos ( ir ), kopijuojamos pažodžiui, sekant lizdų gylį ir gerbiant pasvirąjį brūkšnį kaip escape ženklą, kad escapintas skliaustas nesugriautų gylio skaičiavimo. Eilutė, tokia kaip (see object 3 0 R for details), turi vadovėlinį nuorodos šabloną, kuris iš tikrųjų yra tik proza, ir ji turi išlikti baitas į baitą
• Šešioliktainės eilutės, apribotos < ir >, praleidžiamos jų neinterpretuojant. Baitai 52 šešioliktainėje eilutėje yra ASCII kodas simboliui R, o skeneris, kuris šešioliktainį turinį laikytų tekstu, galėtų sukurti vaiduoklinę nuorodą. Žodyno pradžia << aptinkama pirmiau, kad žodynas nebūtų supainiotas su šešioliktainiu tekstu
• Pavadinimo objektai, prasidedantys /, suvartojami visi, nuo pasvirojo brūkšnio iki kito tarpo arba ribotuvo. Be to toks vardas kaip /R, įprastas resurso raktas, galėtų būti perskaitytas kaip nuorodos R
• Komentarai, prasidedantys %, tęsiasi iki eilutės pabaigos ir praleidžiami kaip nepermatomas tekstas
• Tikrinimas „skaičius, tada R“ yra griežtas. Nuoroda atpažįstama tik tada, kai forma yra N whitespace G whitespace R, o po R eina tarpas, ribotuvas arba įvesties pabaiga. Jei generacijos numerio nėra, arba po R eina raidė, skaitmenys išrašomi nepakeisti. Būtent tai apsaugo sveikąjį skaičių /Length 1234 ir keturis MediaBox skaičius nuo tylaus padidinimo

Šio griežto tikrinimo šerdis skaitosi beveik lygiai taip, kaip ją aprašo specifikacijos sakinys:

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;

Perrašomas tik objekto numeris; generacijos numeris ir tikslūs originalūs tarpai tarp tokenų nukopijuojami kaip buvo, todėl išvestis yra baitas į baitą identiška įvesčiai, išskyrus tą vieną sveikąjį skaičių, kurį reikėjo pakeisti. Būtent tame ir esmė - tik toks tikslumas leidžia šaltinio baitų pakartotinį panaudojimą laikyti ekvivalenčiu pilnam perserializavimui, o ne tik maždaug artimu. Elgsena padengta kryptingu vienetinių testų rinkiniu, kuris tikrina plikas nuorodas, nuorodas masyvų viduje, ne nuorodų skaičius, tiesiogines eilutes, šešioliktaines eilutes ir nenulinės generacijos numerius, kai taikomas poslinkis

Kodėl žymėms netiko pakartotinai naudoti AppendOutline

Kelių dokumentų žymių sujungimas į vieną kontūrų medį atrodo kaip darbas esamam pagalbininkui AppendOutline, kuris jau moka vieno dokumento aukščiausio lygio žymes įskiepyti į kitą. Čia tai netinkamas įrankis, o priežastis yra subtilus sluoksniavimo neatitikimas. AppendOutline dabartinę paskutinę aukščiausio lygio žymę randa vaikščiodamas skaitytuvu per originalaus failo baitus. Tačiau greitasis sujungimas savo pakeitimus etapais kaupia naujų objektų buferyje per ChangeObject; skaitytuvas šių pakeitimų niekada nemato. Suverkite tris ar daugiau dokumentų, ir kiekvienas pridėjimas pirmojo dokumento originalią paskutinę žymę peradresuoja į naujausią dokumentą, todėl visų tarpinių dokumentų žymės iškrenta iš grandinės - teisingas lieka tik bendras /Count, ir dėl to klaidą lengva pražiūrėti, kol kas nors neatidaro žymių skydelio

Greitasis kelias tai išsprendžia dviejų fazių, metaduomenimis varomu įterpimu, kuris daugiau niekada nebevaikšto per skaitytuvą. Pirmasis praėjimas per visas įvestis surenka kiekvienam dokumentui kontūrų šaknies objekto ir generacijos numerius, pirmosios ir paskutinės aukščiausio lygio žymės numerius bei šaknies /Count. Iš šios santraukos kodas apskaičiuoja visų nuorodų, kurias reikia nukalti, globalius objektų numerius: kiekvieno dokumento aukščiausio lygio /Parent į bendrą šaknį, pirmos žymės /Prev į ankstesnio dokumento paskutinę, paskutinės žymės /Next į kito dokumento pirmąją, ir visa tai gryna objektų numerių aritmetika. Už to slypi ir įrašymo eiliškumo apribojimas: pirmojo dokumento objektai išrašomi dar iki to momento, kai apskritai atidaromas bet kuris vėlesnis dokumentas, todėl visos pirmojo dokumento kontūrų pataisos, šaknies /Count ir /Last bei senos paskutinės žymės /Next, turi būti išreiškiamos aritmetika, kuriai nereikia jokio vėlesnio dokumento rankoje. Kiekvieno vėlesnio dokumento pataisos pritaikomos vietoje po atidarymo, bet prieš išrašymą, todėl jos iškeliauja tuo pačiu change-object keliu

Poslinkių sulygiavimo invariantas, kuris viską suriša

Ir nuorodų poslinkis, ir žymių įterpimas remiasi vienu aritmetiniu invariantu, ir tai trapiausia prielaida visame sprendime. Į vėlesnį dokumentą įterpiama nuoroda užrašoma kaip tikslinis globalus objekto numeris minus to dokumento Offset, kad vėliau, kai objektas bus perstumtas per ShiftIndRef(Offset), reikšmė nusileistų tiksliai ant numatyto globalaus numerio. Pirmasis dokumentas gauna Offset = 0 ir naudoja globalius numerius tiesiogiai. Kad ši atimtis būtų teisinga, vykstantis poslinkių sekos skaičiavimas įterpimo metu turi sutapti su poslinkių seka, kuri naudojama galutiniam objektų išrašymui

Taip ir yra dėl vienos puslapių ir formų sujungimo savybės: AddPages, AddFields ir AddFieldFonts keičia tik jau egzistuojančius pirmojo dokumento objektus - jie niekada neprideda naujų. Todėl pirmojo dokumento objektų skaičius per puslapių sujungimo etapą nepasikeičia, o kiekvieno vėlesnio dokumento poslinkis, visų ankstesnių dokumentų objektų skaičių suma, išlieka stabilus nuo įterpimo iki išrašymo. Sulaužykite tai, pavyzdžiui, įveskite etapą, kuris sujungimo viduryje sukuria naują objektą, ir kiekviena vėlesnė puslapio bei žymės nuoroda bus pastumta per tiek objektų, kiek pridėjote. Invariantas tylus, bet laiko visą svorį

Trys įėjimo taškai virš vieno variklio

Greitasis kelias nėra atskira sujungimo kodo šaka. Toje pačioje darbo linijoje baitų lygmens variklis buvo išskirtas į vieną vidinę rutiną MergeFileListInternal(ListName, OutputFileName, PreserveStructTree, StrictMode), o viešieji API tapo plonais apvalkalais, kurie parenka dvi vėliavas:

• MergeFileListFast kviečia variklį su išjungtu struktūros medžio išsaugojimu - tai liesiausias kelias, atmetantis pažymėto PDF medį, kad baitų maršrutas galiotų kuo daugiau objektų
• MergeFileList jį kviečia su išsaugojimu įjungtu, todėl struktūros medis išlieka, o rezultatas lieka naudojamas pažymėtas PDF. Šis įprastas kelias taip pat paveldi kelių dokumentų žymių ir formų sujungimą
• MergeFileListStrict įjungia griežtą režimą: pirmasis metaduomenų praėjimas sustoja ties pirmuoju įvesties failu, kuris nepraneša apie švarų sujungimą, todėl į rezultatą įtraukiami tik tie dokumentai, kurie buvo surinkti iki blogo failo, užuot praleidus blogą failą ir tęsus toliau

Sujungus kelius į vieną taip pat pavyko perstatyti įprastą sujungimą iš porinio O(N²) ciklo, „sujunk pirmą ir antrą failą, tada tą rezultatą su trečiu ir taip toliau“, kai augantis akumuliatorius kiekviename žingsnyje vėl perparsindavo pats save, į vieną linijinį praėjimą, kuris kiekvieną įvestį atidaro tik vieną kartą. Du seniai egzistavę dviejų failų ir dviejų srautų įėjimo taškai, MergeFiles ir MergeStreams, liko nepaliesti ir tebėra prieinami kviesiantiesiems, kuriems tikrai reikia porinio sujungimo

Viena sąžininga pastaba apie struktūros medžio elgseną, nes ji įkando testų rinkiniui. Greitojo kelio „atmesti“ nėra visiška: jis pašalina pirmojo dokumento katalogo nuorodą į /StructTreeRoot, bet pats struktūros medžio objektas vis tiek išrašomas kaip našlaitis. Todėl greitosios išvesties baituose vis dar yra eilutė /StructTreeRoot, ir negalite atskirti greitosios išvesties nuo įprastos tiesiog ieškodami šios eilutės - tikrasis skirtumas yra tai, ar katalogas dar pasiekia struktūros medį, nes būtent tai nulemia, ar failas vis dar yra naviguojamas pažymėtas PDF

Kada rinktis kurį kelią

Baitų kelias yra pralaidumo optimizacija atvejams, kai jungiate daug dokumentų ir jums nereikia išsaugoti pažymėto PDF struktūros medžio - ataskaitų paketams, išrašų serijoms, paketiniam sujungimui. Matuojant pakartotinius vidutinio ir didelio dydžio įvesčių rinkinių sujungimus, baitų pakartotinis naudojimas nuo bendro vykdymo laiko nukirpo maždaug keturis iki trylikos procentų, priklausomai nuo objektų mišinio, ir nesukėlė naujų klaidų mažose ar netvarkingose įvestyse, nes kiekvienas objektas, kurio skeneris negali įrodyti saugiu, grįžta į pilną parse kelią. Jei jums reikia nepažeisto struktūros medžio dėl prieinamumo, naudokite įprastą pažymėto PDF sujungimo kelią, kuris jį išsaugo; o jei dirbate ne su daugybe įvesčių, o su labai dideliais pavieniais failais, tame pačiame filosofiniame registre veikia ir palydimajame straipsnyje apie didelių PDF sujungimą bei skaidymą tiesiogine failų prieiga aprašytos baitų kopijavimo technikos

Sujungimo rutinų šeima ir jos greitieji bei griežtieji variantai yra PDFlibPas Delphi PDF Library dalis, o jos dokumentacijoje pateikiama visa failų sąrašo API ir čia aptartų sujungimo parinkčių nuoroda