LlosLab Software Development BlogИнженерни бележки за разработчици на PDF, Delphi и софтуер за документи.

Техническа статия

Бързо PDF сливане в Delphi: byte-level ref shifting

Delphi PDF Library

Съединяването на PDF-и звучи така, сякаш трябва да е евтино. Page content-ът вече е подреден, font-овете вече са embedded, изображенията вече са compressed. По принцип merge-ът е просто bookkeeping: преномерирайте object-ите, така че numbering space-овете на двата файла да не се сблъскват, зашийте page tree-овете, оправете cross-reference table-а и запишете. На практика повечето merge code изхвърля тази евтиност. За всеки object във всеки input файл той пуска пълен parse в tokenized object tree, променя няколко indirect references и после сериализира tree-то обратно до bytes. Parse-ът и reserialize-ът са скъпите половини и за огромното мнозинство обекти произвеждат byte sequence, почти идентичен с този, който е влязъл

PDFlibPas е нативен Object Pascal PDF engine за Delphi и C++Builder и fast merge path-ът му съществува, за да прескочи този round trip, където е доказуемо безопасно. Идеята е тясна, но носи полза върху цели sets от документи: за немодифициран non-stream object вземете оригиналните source bytes дословно и направете еднократно byte-level rewrite на indirect references, които те съдържат, като превърнете всеки N G R в (N+Offset) G R. Няма tokenizer, няма object tree, няма serializer. Тази статия обхожда къде този shortcut е легален, parser state machine-ът, който прави byte rewrite-а без да повреди нещо, защо bookmark merging-ът се нуждаеше от съвсем друг механизъм и как обичайният merge path беше преработен от quadratic към linear в същото време

Защо object renumbering е истинската цена на merge-а

Всеки PDF носи собствено object numbering space. File A има object 1, object 2 и така нататък; file B има своите object 1, object 2 и така нататък. Не можете да пуснете B-овите objects в A-овия файл без промяна, защото numbers-ите ще се сблъскат и всяка indirect reference вътре в B ще започне да сочи към грешния object. Fix-ът е offset: ако A завършва с object count Offset, тогава B object N става object N+Offset в output-а и всяка reference N G R която се появява някъде вътре в B-овите objects, трябва да бъде изместена до (N+Offset) G R за да съвпадне

Това изместване е цялата семантична задача на body merge-а. Page tree fixup-ите и AcroForm merge-ът са малки, ограничени edits върху шепа objects. Основната работа е пренаписване на references през хиляди objects, а наивният начин да го направите е да parse-нете всеки object, за да намерите references structuralно. PDFlibPas's MergeFileListFast взема обратната позиция: references-ите могат да се намерят и в raw bytes, стига да внимавате за контекстите, в които digit-space-digit-space-R sequence е не reference. Прескочете parse-а, shift-нете in place и per-object cost-ът се свлича до един линеен scan на bytes, които така или иначе щяхте да копирате

Кога преизползването на source bytes е доказуемо безопасно

Byte path-ът се взема само когато за object-а, който се копира от следващ документ, са изпълнени три условия. Ако дори едно липсва, object-ът се връща през пълния decode-and-reserialize route, така че correctness винаги печели над speed:

  • Doc2.IsChangedObject(X) е False. Ако merge engine-ът вече е променил object-а в memory (page object, чийто /Parent е пренасочен, например), in-memory tree-то е source of truth и оригиналните bytes са stale. Само недокоснатите objects се квалифицират
  • Source bytes-овете не съдържат stream keyword. Body-то на stream object е opaque binary, обградено от stream/ endstream, а наивен reference scan върху compressed или encrypted stream data би „намирал“ и повреждал byte patterns, които приличат на references. Stream objects остават по оригиналния stream-aware path
  • Source bytes-овете не съдържат нито /StructTreeRoot, нито /StructElem. В fast profile-а tagged-PDF structure tree-то се dropped-ва, вместо да се merged-ва, така че тези objects трябва да минат през decode path-а, където engine-ът може нарочно да ги null-не

Решението живее в per-object copy loop-а. Когато и трите проверки минат, bytes-овете на object-а отиват направо към ShiftIndRefsInSource и после към writer-а; иначе bytes-овете се изхвърлят и object-ът се rebuild-ва с GetObject, shifted с ShiftIndRef и сериализиран. Структурата на този branch си струва да се види, защото редът на проверките е това, което го прави безопасен:

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;

Празен ObjectData е сигналът, че byte path-ът е отказал object-а. Този единствен sentinel държи fast и slow маршрутите отдалечени един от друг: има точно едно място, което решава, и точно един fallback

Reference-shifting state machine-ът и неговите edge cases

Byte rewrite на indirect references е измамно лесен за объркване, защото R и runs от цифри се появяват навсякъде в PDF object в контексти, които не са references. ShiftIndRefsInSource е малък ръчен scanner, който обхожда байтовете веднъж и пренаписва число само когато след него, с PDF whitespace между tokens-ите, идва още едно число и после R delimiter. Евтините exits идват първо: ако offset-ът е нула или source-ът е празен, байтовете се връщат непокътнати, без изобщо да се влиза в scanner-а

Коректността на scanner-а зависи от това да разпознава контекстите, в които sequence, приличаща на reference, трябва да остане на мира. Това са boundary-ите, които се пропускат най-лесно, и всеки от тях е обработен изрично:

  • Literal strings delimited by ( и ) се копират дословно, като се следи nesting depth и backslash escape-ът, така че escaped parenthesis да не обърка depth count-а. Низ като (see object 3 0 R for details) съдържа textbook reference pattern, който всъщност е просто prose, и трябва да оцелее byte-for-byte
  • Hexadecimal strings delimited by < и > се пропускат без интерпретация. Байтовете 52 вътре в hex string са ASCII кодът за R, и scanner, който третира hex payload-а като text, би могъл да създаде phantom reference. Отварящото << на dictionary се открива първо, така че dictionary да не бъде сбъркан за hex string
  • Name objects започващи с / се консумират цели, от slash-а до следващото whitespace или delimiter. Без това name като /R (често срещан resource key) може да бъде прочетено като R на reference
  • Comments въведени от % стигат до края на реда и се пропускат като opaque text
  • Числото-плюс-R test-ът е строг. Reference се разпознава само като N whitespace G whitespace R с R завършено от whitespace, delimiter или края на input-а. Ако generation number липсва, или R е последвано от буква, digits-ите се изписват без промяна. Това е, което пази integer-а в /Length 1234 и четирите numbers на MediaBox от това да бъдат тихо увеличени

Сърцевината на този строг test почти точно следва изречението от specification-а:

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;

Само object number-ът се пренаписва; generation number-ът и точното оригинално whitespace между tokens-ите се копират нататък, така че output-ът да е byte-identical на input-а, освен за едното integer, което е трябвало да се промени. Тази точност е целият смисъл - тя прави преизползването на source bytes еквивалентно на full reserialize, а не просто близко до него. Поведението е покрито от фокусиран набор от unit tests, които упражняват bare references, references вътре в arrays, non-reference numbers, literal strings, hex strings и non-zero generation numbers с приложен offset

Защо bookmarks не можеха да преизползват AppendOutline

Сливането на bookmarks на няколко documents в едно outline tree изглежда като работа за съществуващия AppendOutline helper, който вече знае как да graft-не top-level bookmarks на един document върху друг. Той е грешният инструмент тук и причината е фин mismatch в layering-а.AppendOutlineAppendOutlineChangeObject намира текущия последен top-level bookmark, като обхожда reader-а през оригиналните file bytes. Но fast merge-ът подрежда edit-ите си в new-objects buffer през /Count; reader-ът никога не вижда тези edits. Подредете три или повече documents и всяко append пренасочва първия document original last bookmark към най-новия document, така че всички intermediate documents bookmarks изпадат от chain-а - само cumulative

остава правилно, което прави bug-а лесен за изпускане, докато някой не отвори bookmark panel-а./CountFast path-ът го решава с two-phase, metadata-driven injection, която никога не преглежда reader-а повторно. Първи pass през всички inputs събира, за всеки document, outline root object-а и generation numbers, първия и последния top-level bookmark numbers и root-/Parent to the shared root, first bookmark-ът /Prev до предходния document последен, last bookmark-ът /Next към следващия document първи - чрез pure object-number arithmetic. Зад това има write-ordering constraint: първият document objects се записват преди който и да е следващ document да бъде дори отворен, така че всички outline edits на първия document (root /Count и /Last, и стария last bookmark /Next) трябва да могат да се изразят като arithmetic, която не изисква по-късен document на ръка. Всеки следващ document edits се прилагат in place, след като бъде отворен, но преди да бъде записан, така че те минават през същия change-object path

Offset-alignment invariant-ът, който ги свързва

И reference shift-ът, и bookmark injection-ът зависят от един arithmetic invariant и той е най-крехкото предположение в целия дизайн. Reference, инжектиран в следващ document, се записва като target global object number минус този document Offset, така че когато object-ът по-късно бъде shift-нат с ShiftIndRef(Offset) стойността да попадне върху целевия global number. Първият document получава Offset = 0 и използва global numbers директно. За да е тази извадка правилна, running offset sequence-ът, използван по време на injection, трябва да съвпада с offset sequence-а, използван когато objects-ите накрая се записват

Съответства, заради property на това как page и form merges работят: AddPages, AddFields и AddFieldFonts модифицират само съществуващите objects на първия document - те никога не добавят нови. Така object count-ът на първия document остава непроменен през page-merge stage-а и offset-ът на всеки следващ document (сумата от всички предходни document object counts) остава стабилен от injection до write-out. Счупете това - въведете stage, който създава нов object по средата на merge-а - и всяка page и bookmark reference надолу по веригата ще се разсрещне с броя objects, който сте добавили. Invariant-ът е тих, но носи товара

Три входни точки върху един engine

Fast path-ът не е fork на merge code-а. В същата линия на работа byte-level engine-ът беше изваден в една вътрешна routine, MergeFileListInternal(ListName, OutputFileName, PreserveStructTree, StrictMode), а public API-тата станаха тънки wrappers, които избират два flag-а:

  • MergeFileListFast вика engine-а със structure-tree preservation изключено - най-леката пътека, която dropping-ва tagged-PDF tree-то, така че byte route-ът да се приложи към възможно най-много objects
  • MergeFileList го вика с preservation включено, така че structure tree-то да оцелее и резултатът да остане използваем tagged PDF. Този обикновен path също наследява multi-document bookmark и form merging
  • MergeFileListStrict включва strict mode: първият metadata pass спира при първия input, който не отчита clean merge, така че се включват само documents-ите, събрани преди лошия файл, вместо лошият файл просто да бъде прескочен и работата да продължи

Сливането на path-овете също позволи обикновеният merge да бъде преработен от pairwise O(N²) loop - merge file едно и две, merge-нете резултата с три и така нататък, като reparsing-вате растящия accumulator на всяка стъпка - в един линеен pass, който отваря всеки input веднъж. Двете дългогодишни two-file и two-stream entry points, MergeFiles и MergeStreams, са недокоснати и остават налични за callers, които наистина искат pairwise merge

Една честна бележка за behavior-а на structure tree-то, защото той удари test suite-а. Fast path „drop“-ът не е пълен: той премахва catalog reference-а на първия document към /StructTreeRoot, но самият structure-tree object пак се записва като orphan. Така bytes-овете на fast output-а все още съдържат /StructTreeRoot string-а и не можете да различите fast от ordinary output, като търсите този string - истинската разлика е дали catalog-ът още стига до structure tree-то, което определя дали file-ът все още е navigable tagged PDF

Кога да посегнете към кой path

Byte path-ът е throughput optimization за сглобяване на много documents, когато не ви трябва tagged-PDF structure tree-то да бъде preserved - report bundling, statement runs, batch concatenation. Измерено върху повторни merge-ове на medium-to-large input sets, byte reuse-а свали около четири до тринадесет процента от wall-clock time, в зависимост от object mix-а, без нови failures на малки или malformed inputs, защото всеки object, който scanner-ът не може да докаже като safe, пада обратно към пълния parse. Ако ви трябва structure tree-то непокътнато за accessibility, използвайте обичайния tagged-PDF merge path, който го preserve-ва; а ако работите с много големи single files, а не с много inputs, byte-copy техниките, описани в companion piece-а за large PDF merge and split with direct file access прилагат същата философия „копирай bytes, избягвай пълното object tree“ на файлова скала

Merge routine-ите и техните fast и strict variants са част от PDFlibPas Delphi PDF Library, чиято документация носи пълната reference за file-list API и merge options-ите, описани тук