Rýchle zlučovanie PDF v Delphi

Zreťazenie PDF znie, akoby malo byť lacné. Obsah strán je už rozložený, fonty sú už vložené a obrázky sú už komprimované. V princípe je merge len účtovníctvo: prečíslovať objekty tak, aby si číslovacie priestory dvoch súborov neprekážali, zošiť page trees, opraviť cross-reference table a zapísať výsledok. V praxi však väčšina merge kódu túto lacnosť zahodí. Pre každý objekt v každom vstupnom súbore vykoná plný parse do tokenizovaného object tree, zmení pár indirect reference a potom strom znovu serializuje do bajtov. Parse aj reserialize sú drahé polovice práce a pre veľkú väčšinu objektov vytvoria sekvenciu bajtov takmer zhodnú s tým, čo vošlo dnu

PDFlibPas je natívny Object Pascal PDF engine pre Delphi a C++Builder a jeho rýchla merge cesta existuje presne preto, aby tento okruh preskočila všade tam, kde je to preukázateľne bezpečné. Myšlienka je úzka, ale vypláca sa naprieč celými sadami dokumentov: pri neupravenom non-stream objekte vezmite pôvodné zdrojové bajty doslova a urobte v nich jediný byte-level prepis indirect reference, ktorý z každého N G R urobí (N+Offset) G R. Žiadny tokenizer, žiadny object tree, žiadny serializer. Tento článok rozoberá, kde je takáto skratka legálna, aký parser state machine vykonáva prepísanie bajtov bez toho, aby čokoľvek poškodil, prečo merge bookmarkov potreboval úplne iný mechanizmus a ako sa pri tej istej práci prestaval aj obyčajný merge path z kvadratického na lineárny

Prečo je prečíslovanie objektov skutočnou cenou merge

Každé PDF nesie vlastný priestor číslovania objektov. Súbor A má objekt 1, objekt 2 a tak ďalej. Súbor B má svoje vlastné objekty 1, 2 a tak ďalej. Objekty B nemôžete vložiť do A bez zmeny, pretože čísla by kolidovali a každá indirect reference vo vnútri B by sa teraz vyriešila na nesprávny objekt. Oprava je offset: ak A končí počtom objektov Offset, potom objekt N zo súboru B sa vo výstupe stane objektom N+Offset a každá referencia N G R objavujúca sa kdekoľvek vo vnútri objektov B sa musí posunúť na (N+Offset) G R tak, aby sedela

Práve tento posun je celou sémantickou prácou pri merge tela dokumentu. Opravy page tree a merge AcroForm sú malé, ohraničené zásahy do hŕstky objektov. Objemy práce vznikajú pri prepise referencií cez tisíce objektov a naivný spôsob je každý objekt naparsovať, aby ste referencie našli štrukturálne. MergeFileListFast v PDFlibPas na to ide opačne: referencie sa dajú nájsť aj v raw bytes, ak ste opatrní v kontextoch, kde sekvencia digit-medzera-digit-medzera-R nie je referenciou. Preskočte parse, posuňte na mieste a cena za objekt sa zrúti na jediný lineárny scan bajtov, ktoré ste aj tak išli kopírovať

Keď je znovupoužitie zdrojových bajtov preukázateľne bezpečné

Byte path sa použije len vtedy, keď pre objekt kopírovaný z nasledujúceho dokumentu platia všetky tri podmienky. Ak zlyhá čo i len jedna z nich, objekt sa vráti na plnú decode-and-reserialize cestu, takže korektnosť vždy víťazí nad rýchlosťou:

Doc2.IsChangedObject(X) je False. Ak merge engine objekt v pamäti už zmenil, napríklad page object, ktorému sa prepísal /Parent, potom je zdrojom pravdy in-memory strom a pôvodné bajty sú zastarané. Nárok majú len nedotknuté objekty
Zdrojové bajty neobsahujú kľúčové slovo stream. Telo stream objektu je nepriehľadný binárny obsah orámovaný stream/endstream, a naivný scan referencií cez komprimované alebo šifrované stream dáta by ochotne "našiel" a poškodil vzory bajtov, ktoré len vyzerajú ako referencie. Stream objekty ostávajú na pôvodnej stream-aware ceste
Zdrojové bajty neobsahujú ani /StructTreeRoot ani /StructElem. V rýchlom profile sa tagged-PDF structure tree zahodí namiesto merge, takže tieto objekty musia prejsť decode path, kde ich engine vie úmyselne vynulovať

Rozhodnutie žije v per-object copy loop. Keď všetky tri kontroly prejdú, bajty objektu idú rovno do ShiftIndRefsInSource a potom do writeru. Inak sa bajty zahodia a objekt sa prestaví pomocou GetObject, posunie sa cez ShiftIndRef a serializuje. Tvar tohto vetvenia stojí za videnie, pretože poradie kontrol je presne to, čo ho drží bezpečným:

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;

Prázdne ObjectData je signál, že byte path objekt odmietla. Tento jediný sentinel drží rýchlu a pomalú cestu pohromade: existuje presne jedno miesto, ktoré rozhoduje, a presne jeden fallback

State machine pre posun referencií a jeho hraničné prípady

Byte-level prepis indirect reference je zradne ľahké pokaziť, pretože R aj sekvencie číslic sa v PDF objekte objavujú všade aj v kontextoch, ktoré referenciami nie sú. ShiftIndRefsInSource je malý ručne písaný scanner, ktorý prejde bajty raz a prepíše číslo len vtedy, keď po ňom s PDF whitespace medzi tokenmi nasleduje ďalšie číslo a potom delimiter R. Najlacnejšie ukončenia prichádzajú prvé: ak je offset nulový alebo je zdroj prázdny, bajty sa vrátia bez zmeny bez toho, aby sa scanner vôbec spúšťal

Korektnosť scannera stojí na rozpoznaní kontextov, v ktorých musí sekvenciu vyzerajúcu ako referencia nechať na pokoji. Toto sú hranice, ktoré sa najľahšie prehliadnu, a každá z nich sa rieši explicitne:

Literálové stringy ohraničené znakmi ( a ) sa kopírujú doslova, pričom sa sleduje hĺbka vnorenia a rešpektuje backslash escape, aby escapovaná zátvorka nerozbila počítanie hĺbky. Reťazec ako (see object 3 0 R for details) obsahuje učebnicový vzor referencie, ktorý je však v skutočnosti len prozaický text a musí prežiť bajt po bajte
Hexadecimálne stringy ohraničené znakmi < a > sa prepúšťajú bez interpretácie. Bajty 52 vo vnútri hex stringu sú ASCII kód pre R, a scanner, ktorý by hex payload považoval za text, by si mohol vyrobiť phantom reference. Otváracie << slovníka sa rozpoznáva skôr, aby sa dictionary nepomýlil s hex stringom
Name objekty začínajúce na / sa spotrebujú celé, od slashu po najbližší whitespace alebo delimiter. Bez toho by meno ako /R čo je bežný resource key, mohlo byť omylom prečítané ako R z referencie
Komentáre zavedené znakom % siahajú po koniec riadka a preskakujú sa ako nepriehľadný text
Test číslo-potom-R je prísny. Referencia sa rozpozná len ako N whitespace G whitespace R s tým, že R je ukončené whitespace, delimiterom alebo koncom vstupu. Ak generation number chýba alebo po R nasleduje písmeno, číslice sa vypíšu bez zmeny. Práve to chráni celé číslo v /Length 1234 a štyri čísla v MediaBox pred tichým inkrementovaním

Jadro tohto prísneho testu číta takmer presne to, čo opisuje samotná veta špecifikácie:

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;

Prepisuje sa len object number. Generation number aj presný pôvodný whitespace medzi tokenmi sa kopírujú ďalej, takže výstup je bajtovo zhodný so vstupom okrem jediného integeru, ktorý sa musel zmeniť. Táto presnosť je celým pointom. Práve vďaka nej je znovupoužitie source bytes ekvivalentom plného reserialize, nie iba niečím, čo je tomu podobné. Správanie pokrýva cielená sada unit testov pre holé referencie, referencie vo vnútri polí, čísla ktoré referenciami nie sú, literal strings, hex strings a nenulové generation number s aplikovaným offsetom

Prečo bookmarky nemohli znovu použiť AppendOutline

Merge bookmarkov z viacerých dokumentov do jedného outline tree vyzerá ako práca pre existujúci helper AppendOutline, ktorý už vie naštepiť top-level bookmarky jedného dokumentu na druhý. Tu je to však nesprávny nástroj a dôvodom je jemný nesúlad vrstiev. AppendOutline nájde aktuálny posledný top-level bookmark tak, že readerom prejde pôvodné bajty súboru. Rýchly merge však svoje úpravy pripravuje v new-objects bufferi cez ChangeObject; reader tieto úpravy nikdy nevidí. Pri zreťazení troch a viac dokumentov preto každé append prepichne pôvodný posledný bookmark prvého dokumentu na najnovší dokument, takže bookmarky všetkých medzidokumentov vypadnú z reťazca. Správne zostáva len kumulatívne /Count, a preto sa bug ľahko prehliadne, kým niekto neotvorí panel bookmarkov

Rýchla cesta to rieši dvojfázovou injekciou riadenou metadátami, ktorá reader znovu neprechádza. Prvý prechod cez všetky vstupy pozbiera pre každý dokument číslo objektu outline rootu a generation number, čísla prvého a posledného top-level bookmarku a hodnotu /Count rootu. Z tohto súhrnu vie kód vypočítať globálne object number všetkých liniek, ktoré treba vykovať: top-level /Parent každého dokumentu smerom na shared root, /Prev prvého bookmarku smerom na posledný bookmark predchádzajúceho dokumentu a /Next posledného bookmarku smerom na prvý bookmark nasledujúceho dokumentu, čisto pomocou aritmetiky object number. V pozadí je aj obmedzenie poradia zápisu: objekty prvého dokumentu sa zapisujú skôr, než sa vôbec otvorí ktorýkoľvek nasledujúci dokument, takže všetky outline úpravy prvého dokumentu, teda root /Count a /Last, plus /Next starého posledného bookmarku, musia byť vyjadriteľné len aritmetikou bez potreby mať neskorší dokument v ruke. Úpravy každého ďalšieho dokumentu sa aplikujú na mieste po jeho otvorení, ale ešte pred zápisom, takže odvezú sa von rovnakou change-object cestou

Invarianta zarovnania offsetu, ktorá to celé drží pokope

Posun referencií aj injekcia bookmarkov závisia od jednej aritmetickej invarianty a je to najkrehkejší predpoklad celého návrhu. Referencia vstrekovaná do nasledujúceho dokumentu sa zapisuje ako cieľové globálne číslo objektu mínus Offset daného dokumentu, aby sa po neskoršom posune o ShiftIndRef(Offset) hodnota trafila do zamýšľaného globálneho čísla. Prvý dokument má Offset = 0 a používa globálne čísla priamo. Aby toto odčítanie fungovalo, bežiaca sekvencia offsetov použitá počas injekcie sa musí zhodovať so sekvenciou offsetov použitou pri finálnom výstupe objektov

Zhoduje sa, a to vďaka vlastnosti page a form merge operácií: AddPages, AddFields, a AddFieldFonts modifikujú len existujúce objekty prvého dokumentu. Nikdy nepridávajú nové. Počet objektov prvého dokumentu sa teda počas page-merge fázy nemení a offset každého nasledujúceho dokumentu, teda súčet počtov objektov všetkých predchádzajúcich dokumentov, ostáva stabilný od injekcie až po write-out. Keby sa to porušilo, teda keby niektorá fáza uprostred merge vytvorila nový objekt, každá page a bookmark referencia ďalej po prúde by bola mimo o počet novo pridaných objektov. Táto invarianta je tichá, ale nesie celú stavbu

Tri entry pointy nad jedným enginom

Rýchla cesta nie je fork merge kódu. V tej istej práci sa byte-level engine vyfaktoroval do jedinej internej rutiny MergeFileListInternal(ListName, OutputFileName, PreserveStructTree, StrictMode), a public API sa zmenili na tenké wrapre, ktoré volia dve flags:

MergeFileListFast volá engine s vypnutým zachovaním structure tree, teda najľahšiu cestu, ktorá tagged-PDF strom zahodí, aby sa byte route mohla uplatniť na čo najväčší počet objektov
MergeFileList volá engine so zapnutým zachovaním, takže structure tree prežije a výsledok ostane použiteľným tagged PDF. Táto obyčajná cesta zároveň dedia aj multi-document merge bookmarkov a formulárov
MergeFileListStrict zapína strict mode: prvý metadata pass sa zastaví pri prvom vstupe, ktorý nenahlási clean merge, takže sa zahrnú len dokumenty nazbierané pred chybným súborom, namiesto toho, aby sa chybný súbor preskočil a pokračovalo sa ďalej

Spojenie ciest zároveň umožnilo prestavať obyčajný merge z dvojicového O(N²) cyklu, teda merge súboru jedna a dva, potom výsledku s tromi a tak ďalej s opakovaným parse rastúceho akumulátora, na jediný lineárny prechod, ktorý každý vstup otvorí len raz. Dve staré dvoj-súborové a dvoj-stream entry pointy, MergeFiles a MergeStreams, zostali nedotknuté a sú stále k dispozícii volajúcim, ktorí skutočne chcú pairwise merge

Jedna poctivá poznámka k správaniu structure tree, pretože testy na tom padali. Rýchla cesta jeho "zahodenie" neurobí úplne: odstráni katalógovú referenciu prvého dokumentu na /StructTreeRoot, ale samotný objekt structure tree sa stále zapíše ako orphan. Bajty rýchleho výstupu teda stále obsahujú reťazec /StructTreeRoot, a rýchly a obyčajný výstup sa nedajú rozlíšiť len hľadaním tohto reťazca. Skutočný rozdiel je v tom, či katalóg na structure tree ešte dosiahne, a to je to, čo určuje, či je súbor ešte stále navigovateľným tagged PDF

Kedy siahnuť po ktorej ceste

Byte path je optimalizácia priepustnosti na skladanie mnohých dokumentov, keď nepotrebujete zachovať tagged-PDF structure tree: balenie reportov, dávky výpisov, batch concatenation. Pri meraniach na opakovaných merge stredne veľkých až veľkých vstupných sád znížilo znovupoužitie bajtov wall-clock čas približne o štyri až trinásť percent podľa zmesi objektov, bez nových zlyhaní na malých alebo poškodených vstupoch, pretože každý objekt, ktorého bezpečnosť scanner nevie dokázať, padá späť na plný parse. Ak structure tree pre prístupnosť potrebujete zachovať, použite obyčajnú merge cestu tagged-PDF, ktorá ju uchová. A ak pracujete s veľmi veľkými jednotlivými súbormi namiesto mnohých vstupov, byte-copy techniky opísané v sprievodnom článku o large PDF merge and split with direct file access používajú tú istú filozofiu typu "kopíruj bajty, vyhni sa plnému object tree" na úrovni celého súboru

Merge rutiny a ich rýchle aj strict varianty sú súčasťou PDFlibPas Delphi PDF Library, ktorej dokumentácia nesie plnú referenciu pre file-list API a merge options opísané v tomto článku

Rýchle zlučovanie PDF v Delphi: posun referencií na úrovni bajtov