Rychlé slučování PDF v Delphi: posun referencí na úrovni

Slučování PDF by mělo být levné. Obsah stránek je už vysázený, písma jsou už vložená, obrázky jsou už komprimované. V zásadě je sloučení jen účetnictví: přečíslovat objekty tak, aby se číselné prostory dvou souborů nesrážely, spojit stromy stránek, opravit xref tabulku a zapsat výsledek. V praxi většina kódu pro slučování tuhle levnost zahodí. U každého objektu v každém vstupním souboru provede plné parsování do tokenizovaného stromu objektů, upraví pár nepřímých referencí a pak strom znovu serializuje do bajtů. Parsování i znovuserializace jsou ty drahé poloviny a u drtivé většiny objektů vyprodukují téměř stejnou bajtovou sekvenci, jaká vstoupila dovnitř

PDFlibPas je nativní PDF engine v Object Pascalu pro Delphi a C++Builder a jeho rychlá větev pro slučování existuje proto, aby tento oběh přeskočila všude, kde je to prokazatelně bezpečné. Myšlenka je úzká, ale vyplácí se napříč celými sadami dokumentů: u nezměněného objektu bez streamu vezměte původní zdrojové bajty doslova a proveďte jediný přepis nepřímých referencí na úrovni bajtů, které obsahují, a změňte každý N G R na (N+Offset) G R. Žádný tokenizer, žádný strom objektů, žádný serializátor. Tento článek prochází tím, kde je tenhle trik povolený, parserovým stavovým automatem, který provádí přepis bajtů bez poškození čehokoli, proč slučování záložek potřebovalo úplně jiný mechanismus a jak byla současně přestavěna běžná větev slučování z kvadratické na lineární

Proč je přečíslování objektů skutečným nákladem slučování

Každý PDF soubor nese vlastní prostor číslování objektů. Soubor A má objekt 1, objekt 2 a tak dále; soubor B má svůj vlastní objekt 1, objekt 2 a tak dále. Nemůžete vložit objekty B do souboru A beze změny, protože by se čísla srazila a každá nepřímá reference uvnitř B by se teď vyhodnocovala na špatný objekt. Řešením je offset: pokud A končí počtem objektů Offset, pak objekt B N se stane objektem N+Offset ve výstupu a každá reference N G R která se objeví kdekoli uvnitř objektů B, se musí posunout na (N+Offset) G R aby seděla

Ten posun je celý sémantický úkol při slučování těla dokumentu. Opravy stromu stránek a sloučení AcroForm jsou malé, omezené zásahy do hrstky objektů. Hlavní práce je přepisovat reference napříč tisíci objektů a naivní způsob je parsovat každý objekt, abyste reference našli strukturálně. Přístup PDFlibPasu MergeFileListFast jde opačnou cestou: reference lze najít i v surových bajtech, pokud si dáte pozor na kontexty, kde je sekvence číslice-mezera-číslice-mezera-R není referencí. Přeskočte parsování, posuňte na místě a náklady na jeden objekt se smrsknou na jediný lineární průchod bajtů, které byste stejně kopírovali

Kdy je opětovné použití zdrojových bajtů prokazatelně bezpečné

Bajtová cesta se použije jen tehdy, když u objektu kopírovaného z následujícího dokumentu platí všechny tři podmínky. Jakékoli selhání vrátí objekt na plnou cestu dekódování a znovuserializace, takže správnost vždy vítězí nad rychlostí:

Doc2.IsChangedObject(X) je False. Pokud už stroj pro slučování objekt v paměti změnil (například stránkový objekt, jehož /Parent byl přepojen, například), je strom v paměti zdrojem pravdy a původní bajty jsou zastaralé. V úvahu přicházejí jen nedotčené objekty
Zdrojové bajty neobsahují žádné stream klíčové slovo. Tělo streamového objektu je neprůhledný binární blok ohraničený stream/endstream, a naivní prohledávání komprimovaných nebo šifrovaných streamových dat by bez váhání nalezlo a poškodilo vzory bajtů, které vypadají jako reference. Streamové objekty zůstávají na původní cestě, která zohledňuje streamy
Zdrojové bajty neobsahují ani /StructTreeRoot ani /StructElem. V rychlém profilu se strom struktury tagged-PDF zahodí místo sloučení, takže tyto objekty musí projít dekódovací cestou, kde je engine může záměrně vynulovat

Rozhodnutí padá v kopírovací smyčce pro každý objekt. Když všechny tři kontroly projdou, bajty objektu jdou rovnou do ShiftIndRefsInSource a potom do zapisovače; jinak se bajty zahodí a objekt se znovu sestaví pomocí GetObject, posune pomocí ShiftIndRef, a serializuje. Struktura té větve stojí za to vidět, protože právě pořadí kontrol ji drží bezpečnou:

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ázdný ObjectData je signál, že bajtová větev objekt odmítla. Ten jediný sentinel drží rychlou a pomalou cestu od sebe: existuje přesně jedno místo, které rozhoduje, a přesně jedna záloha

Stavový automat pro posun referencí a jeho hraniční případy

Přepis bajtů nepřímých referencí se snadno pokazí, protože R a posloupnosti číslic se v objektu PDF objevují všude i v kontextech, které nejsou reference. ShiftIndRefsInSource je malý ručně psaný scanner, který projde bajty jen jednou a číslo přepíše pouze tehdy, když po něm, s mezerami PDF mezi tokeny, následuje další číslo a pak R oddělovač. Levné úniky jsou na prvním místě: když je offset nula nebo je zdroj prázdný, bajty se vrátí beze změny a scanner se vůbec nespustí

Správnost scanneru stojí na rozpoznání kontextů, ve kterých je třeba sekvenci vypadající jako reference nechat být. Jde o hranice, které se nejlépe přehlížejí, a každá z nich je řešena výslovně:

Literální řetězce vymezené pomocí ( a ) jsou kopírovány doslova, přičemž se sleduje hloubka vnoření a respektuje se backslash escape, aby escapovaná závorka nerozhodila počítání hloubky. Řetězec jako (see object 3 0 R for details) obsahuje učebnicový vzor reference, který je ve skutečnosti jen próza, a musí projít bajt po bajtu
Hexadecimální řetězce vymezené pomocí < a > jsou předávány dál bez interpretace. Bajty 52 uvnitř hex řetězce jsou ASCII kód pro R, a scanner, který by hex payload bral jako text, by mohl vyrobit fantomovou referenci. Otevírací << slovníku se rozpozná jako první, aby si slovník nebyl spleten s hex řetězcem
Názvové objekty začínající na / se spotřebují celé, od lomítka až po další bílý znak nebo oddělovač. Bez toho by název jako /R (běžný klíč prostředku) mohl být přečten jako R reference
Komentáře uvedené pomocí % sahají až na konec řádku a jsou přeskočeny jako neprůhledný text
Test číslo-pak-R je přísný. Reference je rozpoznána pouze jako Nmezera Gmezera R s R ukončeným mezerou, oddělovačem nebo koncem vstupu. Chybí-li generace, nebo je R následováno písmenem, číslice se vypíší beze změny. To chrání celé číslo v /Length 1234 a čtyři čísla v MediaBox před tichým navýšením

Jádro tohoto přísného testu je téměř přesně to, jak to popisuje věta ve specifikaci:

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;

Přepisuje se pouze číslo objektu; číslo generace i přesné původní mezery mezi tokeny se kopírují dál, takže výstup je byteově totožný se vstupem s výjimkou jediného čísla, které se muselo změnit. Tahle přesnost je celý smysl, protože díky ní je znovupoužití zdrojových bajtů ekvivalentní úplnému novému serializování, ne jenom něčemu skoro podobnému. Chování pokrývá cílená sada unit testů, které ověřují holé reference, reference uvnitř polí, čísla, která reference nejsou, literální řetězce, hex řetězce a nenulová čísla generace s uplatněným offsetem

Proč záložky nemohly znovu použít AppendOutline

Sloučení záložek z více dokumentů do jednoho stromu osnovy vypadá jako úkol pro stávající pomocnou funkci AppendOutline která už umí připojit horní záložky jednoho dokumentu k jinému. Tady je to ale špatný nástroj, a důvodem je jemný nesoulad vrstev.AppendOutline vyhledá aktuální poslední záložku na nejvyšší úrovni tak, že prochází čtečku přes původní bajty souboru. Fast merge ale ukládá své úpravy do bufferu nových objektů přes ChangeObject; čtečka tyto úpravy nikdy neuvidí. Když spojíte tři nebo více dokumentů, každé připojení znovu nasměruje původní poslední záložku prvního dokumentu na nejnovější dokument, takže všechny mezilehlé dokumenty z řetězu vypadnou - zůstane správně jen kumulativní /Count a to dělá chybu snadno přehlédnutelnou, dokud někdo neotevře panel záložek

Rychlá cesta to řeší dvoufázovým vkládáním řízeným metadaty, které už nikdy znovu neprochází čtečku. První průchod přes všechny vstupy shromáždí pro každý dokument kořenový objekt obrysů a čísla generací, čísla první a poslední záložky na nejvyšší úrovni a /Count. Z tohoto souhrnu kód spočítá globální čísla objektů všech vazeb, které potřebuje vytvořit - top-level /Parent na sdílený root, /Prev první záložky na poslední záložku předchozího dokumentu, /Next poslední záložky na první záložku dalšího dokumentu - čistě pomocí aritmetiky čísel objektů. Za tím stojí omezení pořadí zápisu: objekty prvního dokumentu se zapisují dřív, než se vůbec otevře jakýkoli další dokument, takže všechny úpravy obrysů prvního dokumentu (odkaz rootu a /Count, a /Last, a odkaz staré poslední záložky /Next) musí být vyjádřitelné aritmetikou, která nepotřebuje žádný pozdější dokument po ruce. Úpravy každého následujícího dokumentu se provedou přímo po jeho otevření, ale před zápisem, takže procházejí stejnou cestou change-object

Invarianta zarovnání offsetů, která to drží pohromadě

Jak posun referencí, tak vkládání záložek závisí na jediné aritmetické invariantě, a ta je v celém návrhu nejkřehčím předpokladem. Reference vložená do následujícího dokumentu se zapíše jako cílové globální číslo objektu minus offset daného dokumentu, takže když se objekt později posune o ShiftIndRef(Offset) výsledná hodnota dopadne na zamýšlené globální číslo. První dokument dostane Offset = 0 a používá přímo globální čísla. Aby bylo toto odčítání správné, musí se posloupnost offsetů používaná během vkládání shodovat s posloupností offsetů použitou při finálním zápisu objektů

Funguje to díky vlastnosti toho, jak funguje sloučení stránek a formulářů: AddPages, AddFields, a AddFieldFonts upravují jen existující objekty prvního dokumentu - nikdy nepřidávají nové. Počet objektů prvního dokumentu se tedy během fáze sloučení stránek nemění a offset každého následujícího dokumentu (součet všech předchozích počtů objektů) zůstává od vkládání až po zápis stabilní. Porušte to - zaveďte fázi, která uprostřed merge vytvoří nový objekt - a každá reference ke stránkám a záložkám dál po proudu bude o počet přidaných objektů mimo. Ta invarianta je tichá, ale nese celé řešení

Tři vstupní body nad jedním jádrem

Rychlá cesta není větev kódu pro merge. Ve stejné práci bylo bajtové jádro rozděleno do jedné interní rutiny, MergeFileListInternal(ListName, OutputFileName, PreserveStructTree, StrictMode), a veřejná API se stala tenkými obálkami, které volí dva příznaky:

MergeFileListFast používá jádro s vypnutým zachováním stromu struktury - nejlehčí cesta, která zahodí tagged-PDF strom, aby bajtová trasa mohla platit pro co nejvíc objektů
MergeFileList volá jádro se zapnutým zachováním, takže strom struktury přežije a výsledek zůstane použitelný tagged PDF. Tato běžná cesta navíc dědí vícedokumentové slučování záložek a formulářů
MergeFileListStrict zapíná strict mode: první průchod metadaty se zastaví na prvním vstupu, který nehlásí čisté sloučení, takže se zahrnou jen dokumenty sesbírané před vadným souborem, místo aby se vadný soubor přeskočil a pokračovalo se dál

Sjednocení cest také umožnilo přestavět běžné sloučení z dvojice O(N²) smyčky - sloučit soubor jedna a dva, výsledek se třemi a tak dál, přičemž se rostoucí akumulátor při každém kroku znovu parsuje - na jediný lineární průchod, který každý vstup otevře jen jednou. Dlouhodobé dvousouborové a dvoustreamové vstupní body, MergeFiles a MergeStreams, zůstávají nedotčené a jsou dál k dispozici pro volající, kteří opravdu chtějí párové sloučení

Jeden upřímný poznatek k chování stromu struktury, protože narazilo na testovací sadu. Odstranění na rychlé cestě není úplné: odstraní odkaz katalogu prvního dokumentu na /StructTreeRoot, ale samotný objekt stromu struktury se stejně zapíše jako sirotek. Výstup v bajtech tedy pořád obsahuje řetězec /StructTreeRoot a nelze rychlý a běžný výstup rozlišit prostým hledáním tohoto řetězce - skutečný rozdíl je v tom, zda katalog stále dosáhne na strom struktury, což rozhoduje o tom, jestli je soubor pořád navigovatelný tagged PDF

Kdy sáhnout po které cestě

Bajtová cesta je optimalizace propustnosti pro skládání mnoha dokumentů, když nepotřebujete zachovat strom struktury tagged-PDF - spojování reportů, dávky výpisů, hromadné spojování. Při opakovaných merge středních až větších sad vstupů ušetřilo opětovné použití bajtů zhruba čtyři až třináct procent času běhu podle mixu objektů, bez nových selhání na malých nebo poškozených vstupech, protože jakýkoli objekt, který skener nedokáže bezpečně prokázat, padá zpět na plný parse. Pokud strom struktury potřebujete zachovat kvůli přístupnosti, použijte běžnou tagged-PDF merge cestu, která ho zachová; a pokud pracujete s velmi velkými jednotlivými soubory místo mnoha vstupů, techniky kopírování bajtů popsané v doprovodném článku o velkém PDF sloučení a rozdělení s přímým přístupem k souboru použít stejnou filozofii „kopírovat bajty, vyhnout se celému stromu objektů“ i na úrovni souborů

Funkce pro slučování a jejich rychlé i přísné varianty jsou součástí PDFlibPas Delphi PDF Library, jehož dokumentace obsahuje úplný odkaz na API pro seznam souborů a na možnosti slučování popsané zde

Rychlé slučování PDF v Delphi: posun referencí na úrovni bajtů