Быстрое слияние PDF в Delphi: сдвиг ссылок на уровне байтов

Конкатенация PDF звучит так, будто должна стоить дешево. Контент страниц уже разложен, шрифты уже встроены, изображения уже сжаты. В принципе merge - это просто бухгалтерия: перенумеровать объекты так, чтобы пространства нумерации двух файлов перестали сталкиваться, сшить деревья страниц, поправить cross-reference table и записать результат. На практике большинство merge-кода выбрасывает эту дешевизну в окно. Для каждого объекта каждого входного файла он делает полный parse в tokenized object tree, меняет пару косвенных ссылок, а затем сериализует дерево обратно в байты. Именно parse и reserialize являются дорогими половинами, и для подавляющего большинства объектов они производят последовательность байтов, почти идентичную входной

PDFlibPas - это нативный Object Pascal PDF engine для Delphi и C++Builder, и его fast merge path существует ровно для того, чтобы пропускать этот круг там, где это доказуемо безопасно. Идея узкая, но она окупается на целых наборах документов: для неизмененного non-stream object берутся исходные байты как есть и над ними выполняется один byte-level rewrite всех содержащихся в них косвенных ссылок, превращающий каждое N G R в (N+Offset) G R . Никакого tokenizer, никакого object tree, никакого serializer. Эта статья разбирает, где такой shortcut допустим, как именно parser state machine делает byte rewrite, не портя ничего вокруг, почему с bookmark понадобился вообще другой механизм и как одновременно обычный merge path был перестроен из квадратичного в линейный

Почему перенумерация объектов - это и есть реальная стоимость merge

Каждый PDF несет собственное пространство нумерации объектов. У файла A есть object 1, object 2 и так далее; у файла B есть свой object 1, object 2 и так далее. Нельзя просто вставить объекты B в файл A без изменений, потому что номера начнут конфликтовать, и каждая косвенная ссылка внутри B станет указывать не туда. Исправление - это offset: если A заканчивается на числе объектов Offset , то object N файла B становится object N+Offset в output, а каждая ссылка N G R , встречающаяся где угодно внутри объектов B, должна быть смещена в (N+Offset) G R , чтобы указывать на тот же семантический target

Именно этот сдвиг и есть вся семантическая работа merge для body. Поправка page tree и merge AcroForm - это маленькие, ограниченные правки на горстке объектов. Основная работа заключается в переписывании ссылок по тысячам объектов, и наивный путь делает для этого полный parse каждого объекта, чтобы находить ссылки структурно. MergeFileListFast у PDFlibPas смотрит на задачу наоборот: ссылки можно находить и в сырых байтах, если аккуратно различать контексты, в которых последовательность digit-space-digit-space-R не является ссылкой. Если пропустить parse, сместить их на месте и идти дальше, стоимость на объект схлопывается до одного линейного прохода по байтам, которые вы и так собирались копировать

Когда повторное использование исходных байтов доказуемо безопасно

Byte path включается только тогда, когда для копируемого объекта из следующего документа одновременно выполняются три условия. Если ломается хотя бы одно из них, объект немедленно отправляется по полному пути decode-and-reserialize, поэтому correctness здесь всегда выигрывает у speed:

Doc2.IsChangedObject(X) равно False. Если merge engine уже мутировал объект в памяти, например page object, у которого был перепривязан /Parent , то источником истины является уже in-memory tree, а исходные байты устарели. Для byte path годятся только действительно нетронутые объекты
Исходные байты не содержат ключевого слова stream . Тело stream object - это непрозрачный binary payload, ограниченный stream / endstream , и наивный scan ссылок по сжатым или зашифрованным stream data happily "найдет" и испортит байтовые последовательности, похожие на reference. Stream object остаются на исходном stream-aware path
Исходные байты не содержат ни /StructTreeRoot , ни /StructElem . В fast profile tagged-PDF structure tree отбрасывается, а не объединяется, поэтому такие объекты обязаны идти через decode path, где engine может занулить их намеренно

Решение живет в per-object copy loop. Если все три условия проходят, байты объекта идут прямо в ShiftIndRefsInSource и затем в writer. Иначе байты отбрасываются, объект пересобирается через GetObject , смещается через ShiftIndRef и сериализуется. Структуру этой ветки стоит увидеть, потому что именно порядок проверок и делает ее безопасной:

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 отказался от объекта. Этот один sentinel не дает fast и slow route разъехаться: существует ровно одно место принятия решения и ровно один fallback

Машина состояний для сдвига ссылок и ее крайние случаи

Byte rewrite косвенных ссылок обманчиво легко сделать неправильно, потому что R и длинные серии цифр встречаются по всему PDF object в контекстах, которые ссылками не являются. ShiftIndRefsInSource - это небольшой hand-written scanner, который один раз проходит по байтам и переписывает число только тогда, когда за ним, с PDF whitespace между token, следует другое число, а затем delimiter R . Дешевые выходы стоят первыми: если offset равен нулю или source пуст, байты возвращаются без изменений, и scanner вообще не запускается

Корректность scanner держится на распознавании контекстов, где последовательность, похожая на reference, должна быть оставлена в покое. Именно эти границы легче всего пропустить, и каждая из них обрабатывается явно:

Literal string , ограниченные ( и ) , копируются как есть, с отслеживанием глубины вложенности и уважением к escape backslash, чтобы экранированная скобка не сбивала счетчик глубины. Строка вроде (see object 3 0 R for details) содержит textbook pattern ссылки, но на самом деле это просто проза, и она обязана пережить rewrite байт в байт
Hexadecimal string , ограниченные < и > , проходят без интерпретации. Байты 52 внутри hex string являются ASCII-кодом для R , и scanner, который трактовал бы hex payload как text, легко изготовил бы phantom reference. Открывающая << dictionary распознается раньше, чтобы dictionary не был ошибочно принят за hex string
Name object , начинающиеся с / , поглощаются целиком, от slash до следующего whitespace или delimiter. Иначе имя вроде /R , обычный resource key, могло бы быть прочитано как object number ссылки.R
Comment , вводимые через % , тянутся до конца строки и пропускаются как непрозрачный text
Тест "число затем R" сделан строгим. Reference распознается только как N whitespace G whitespace R c R , причем R обязано завершаться whitespace, delimiter либо концом input. Если generation number отсутствует или за /Length 1234 идет буква, цифры выдаются как есть. Именно это защищает integer внутри MediaBox и четыре числа в

от тихого инкремента

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 между token копируются как есть, поэтому output совпадает с input побайтно, за исключением одного integer, который действительно нужно было изменить. В этом вся цель - именно такая точность делает повторное использование исходных байтов эквивалентом полного reserialize, а не лишь чем-то "почти похожим". Поведение прикрыто узким набором unit test, которые прогоняют голые reference, reference внутри array, числа, не являющиеся reference, literal string, hex string и ненулевые generation number при приложенном offset

Почему bookmark не могли переиспользовать AppendOutlineAppendOutlineСлияние bookmark из нескольких документов в одно outline tree выглядит задачей для уже существующего helper AppendOutline , который и так умеет пришивать top-level bookmark одного документа к другому. Но здесь он оказывается неправильным инструментом, и причина в тонком несовпадении слоев. ChangeObject находит текущий последний top-level bookmark, обходя reader по исходным байтам файла. Но fast merge staging держит свои правки в new-objects buffer через /Count ; reader этих правок никогда не видит. Если вы сцепляете три документа и больше, каждое добавление перепривязывает исходный последний bookmark первого документа к самому новому документу, и все промежуточные bookmark выпадают из цепочки. Верным остается только суммарный

, а потому bug легко не заметить, пока кто-то не откроет панель bookmark./CountFast path решает задачу двухфазным, управляемым метаданными injection, которое никогда не делает повторный walk reader. Первый проход по всем input собирает для каждого документа номер и generation корня outline, номера first и last top-level bookmark и /Parent корня. По этому summary код вычисляет глобальные object number всех link, которые нужно собрать: top-level /Prev каждого документа к общему root, /Next первого bookmark к last предыдущего документа, /Count последнего bookmark к first следующего документа - и все это чистой арифметикой по номерам объектов. Здесь есть constraint порядка записи: объекты первого документа выводятся до того, как даже открыт любой следующий документ, поэтому все outline edit для первого документа, /Last и /Next корня и

старого последнего bookmark, должны выражаться арифметикой, не требующей наличия следующего документа под рукой. Правки следующих документов применяются на месте после открытия, но до записи, и уходят наружу через тот же path change-object

Инвариант выравнивания offset, который связывает все вместеИ reference shift, и bookmark injection зависят от одного арифметического инварианта, и это самое хрупкое предположение во всем дизайне. Reference, внедренная в следующий документ, записывается как целевой глобальный номер объекта минус Offset этого документаShiftIndRef(Offset) , чтобы при последующем сдвиге объекта на Offset = 0 значение попало точно в intended global number. Первый документ получает

и использует глобальные номера напрямую. Для корректности этого вычитания последовательность running offset, использованная при injection, должна совпадать с последовательностью offset, используемой при окончательной записи объектов.AddPagesОна совпадает благодаря свойству того, как устроены merge страниц и forms: AddFields , AddFieldFonts и

модифицируют только уже существующие объекты первого документа и никогда не добавляют новые. Поэтому object count первого документа не меняется на стадии page-merge, а offset каждого следующего документа, сумма object count всех предыдущих документов, остается стабильным от injection до write-out. Нарушьте это, добавьте стадию, создающую новый объект посреди merge, и каждая page и bookmark reference дальше по цепочке съедет на число добавленных объектов. Инвариант тихий, но несущий

Три entry point поверх одного engineMergeFileListInternal(ListName, OutputFileName, PreserveStructTree, StrictMode)Fast path - это не отдельная fork merge-кода. В этой же линии работ byte-level engine был вынесен в единый internal routine

MergeFileListFast , а публичные API стали тонкими wrapper, выбирающими два флага:
MergeFileList вызывает engine с выключенным сохранением structure tree - это самый легкий путь, сбрасывающий tagged-PDF tree, чтобы byte route применялся к максимально возможному числу объектов
MergeFileListStrict вызывает его с сохранением structure tree, поэтому tree выживает, а результат остается пригодным tagged PDF. Этот обычный путь также наследует merge bookmark и form для нескольких документов

включает strict mode: первый metadata pass останавливается на первом input, который не отчитывается о clean merge, поэтому в результат попадают только документы, собранные до плохого файла, вместо того чтобы тихо пропустить плохой и идти дальше.Сведение путей вместе позволило также перестроить ordinary merge из pairwise цикла O(N²)MergeFiles - merge file one and two, merge that result with three и так далее, каждый раз заново парся растущий accumulator - в единый линейный проход, открывающий каждый input ровно один раз. Два старых двухфайловых и двухпоточных entry point, MergeStreams и

, не тронуты и по-прежнему доступны для тех вызывающих сторон, которым действительно нужен pairwise merge./StructTreeRootИ еще одно честное замечание о поведении structure tree, потому что именно на нем споткнулся test suite. "Drop" у fast path не является полным: он убирает ссылку catalog первого документа на /StructTreeRoot , но сам object structure tree все равно записывается как orphan. Поэтому в байтах fast output строка

все еще присутствует, и отличить fast от ordinary output простым поиском этой строки нельзя. Реальная разница в том, достигает ли catalog structure tree, потому что именно это определяет, остается ли файл navigable tagged PDF

Когда выбирать какой путьByte path - это optimization по throughput для сборки множества документов там, где вам не нужно сохранять structure tree tagged PDF, например в пакетной bundling отчетов, statement run и batch concatenation. В измерениях на повторяющихся merge средних и крупных наборов input повторное использование байтов снимало примерно от четырех до тринадцати процентов wall-clock time в зависимости от смеси объектов, без новых отказов на маленьких или malformed input, потому что любой объект, который scanner не может доказать безопасным, автоматически откатывается к полному parse. Если же вам нужно сохранить structure tree intact ради accessibility, используйте обычный путь merge tagged-PDF , который ее сохраняет. А если вы работаете не со множеством input, а с очень большими одиночными файлами, то byte-copy techniques из сопутствующего материала о large PDF merge and split with direct file access

применяют ту же философию "копировать байты и избегать полного object tree" уже в масштабе файла.Merge routine и их fast и strict варианты входят в PDFlibPas Delphi PDF Library