Швидке злиття PDF у Delphi: зсування посилань на рівні байтів

Об'єднання PDF звучить так, ніби це має бути дешево. Вміст сторінок уже розкладений, шрифти вже вбудовані, зображення вже стиснені. У принципі злиття - це лише облік: перенумерувати об'єкти так, щоб простори нумерації двох файлів не перетиналися, зшити дерева сторінок, виправити таблицю перехресних посилань і записати результат. На практиці більшість коду злиття вбиває цю дешевизну. Для кожного об'єкта в кожному вхідному файлі він виконує повний розбір у токенізоване дерево об'єктів, змінює кілька непрямих посилань, а потім серіалізує дерево назад у байти. Розбір і повторна серіалізація - це найдорожчі половини, і для переважної більшості об'єктів вони дають байтову послідовність, майже ідентичну тій, що була на вході

PDFlibPas - нативний рушій PDF на Object Pascal для Delphi та C++Builder, а його швидкий шлях злиття існує, щоб пропускати цей цикл усюди, де це можна безпечно довести. Ідея вузька, але вона окупається на цілих наборах документів: для незміненого не потокового об'єкта беріть вихідні байти дослівно і виконуйте одне переписування непрямих посилань на рівні байтів, які вони містять, перетворюючи кожне N G R на (N+Offset) G R. Без токенізатора, без дерева об'єктів, без серіалізатора. У статті розглядається, де цей обхідний шлях дозволений, який скінченний автомат парсера виконує переписування байтів, не пошкоджуючи нічого, чому злиття закладок потребувало зовсім іншого механізму, і як звичайний шлях злиття водночас перебудували з квадратичного на лінійний

Чому перенумерація об'єктів і є справжньою ціною злиття

Кожен PDF має власний простір нумерації об'єктів. У файлі A є об'єкт 1, об'єкт 2 і так далі; у файлі B є власні об'єкт 1, об'єкт 2 і так далі. Ви не можете просто перенести об'єкти B у файл A без змін, бо номери зіткнуться і кожне непряме посилання всередині B тепер вказуватиме не на той об'єкт. Рішенням є зсув: якщо A закінчується на лічильнику об'єктів Offset, то об'єкт B N стає об'єктом N+Offset у вихідному файлі, і кожне посилання N G R що трапляється будь-де всередині об'єктів B, треба зсунути до (N+Offset) G R щоб усе збіглося

Це зсування і є всією семантичною роботою злиття тіла документа. Виправлення дерева сторінок і злиття AcroForm - це невеликі, обмежені правки кількох об'єктів. Основна робота полягає в переписуванні посилань у тисячах об'єктів, а наївний спосіб зробити це - розібрати кожен об'єкт, щоб можна було структурно знайти посилання. Підхід PDFlibPas до цього MergeFileListFast дивиться з протилежного боку: посилання теж можна знайти в сирих байтах, якщо обережно ставитися до контекстів, у яких послідовність цифра-пробіл-цифра-пробіл-R не є посиланням. Пропустіть розбір, зсувайте на місці, і вартість на один об'єкт зводиться до одного лінійного проходу по байтах, які ви все одно збиралися копіювати

Коли повторне використання вихідних байтів є безпечно доведеним

Байтовий шлях застосовується лише тоді, коли для об'єкта, який копіюють із наступного документа, виконуються всі три умови. Якщо хоч одна з них не виконується, об'єкт повертається на повний шлях декодування та повторної серіалізації, тож коректність завжди важливіша за швидкість:

• Doc2.IsChangedObject(X) дорівнює False. Якщо рушій злиття вже змінив об'єкт у пам'яті (наприклад, об'єкт сторінки, чий /Parent був перенаправлений, наприклад), дерево в пам'яті є джерелом істини, а початкові байти вже застаріли. Підходять лише недоторкані об'єкти
• Вихідні байти не містять ключового слова stream keyword. Тіло об'єкта-потоку є непрозорими двійковими даними, обмеженими stream/endstream, і наївний пошук посилань у стиснених або зашифрованих даних потоку радо "знайшов би" та пошкодив би байтові шаблони, схожі на посилання. Об'єкти-потоки залишаються на початковому шляху з урахуванням потоку
• Вихідні байти не містять ані /StructTreeRoot ані /StructElem. У швидкому профілі дерево структури тегованого PDF не зливається, а відкидається, тож ці об'єкти мають пройти шлях декодування, де рушій може навмисно занулити їх

Рішення приймається в циклі копіювання для кожного об'єкта. Коли всі три перевірки проходять, байти об'єкта йдуть прямо до ShiftIndRefsInSource а потім до записувача; інакше байти відкидаються, а об'єкт перебудовується з 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 є сигналом, що байтовий шлях відхилив об'єкт. Цей єдиний маркер не дає швидкому й повільному шляхам розійтися: є рівно одне місце, де приймається рішення, і рівно один запасний варіант

Станова машина для зсуву посилань і її крайові випадки

Побайтне переписування непрямих посилань легко зробити неправильно, бо R і послідовності цифр трапляються всюди в об'єкті PDF у контекстах, які не є посиланнями. ShiftIndRefsInSource — це невеликий ручний сканер, який проходить байти один раз і переписує число лише тоді, коли за ним, з PDF-пробілами між токенами, іде інше число, а потім ще й Rроздільник. Дешеві виходи йдуть першими: якщо зсув нульовий або джерело порожнє, байти повертаються без змін, і сканер навіть не запускається

Правильність сканера тримається на розпізнаванні контекстів, де послідовність, схожа на посилання, має залишитися недоторканою. Це межі, які найпростіше пропустити, і кожну з них оброблено явно:

• Літеральні рядкиобмежені ( та ) копіюються дослівно, з відстеженням глибини вкладення і з урахуванням екранування зворотною скісною рискою, щоб екранована дужка не збивала підрахунок глибини. Рядок на кшталт (see object 3 0 R for details) містить зразковий шаблон посилання, хоча насправді це просто текст, і він має зберегтися байт у байт
• Шістнадцяткові рядкиобмежені < та > проходять без інтерпретації. Байти 52 у шістнадцятковому рядку є ASCII-кодом для R, а сканер, який сприйняв би шістнадцяткове корисне навантаження як текст, міг би згенерувати фантомне посилання. Відкривну << словника визначають першою, щоб словник не сплутати з шістнадцятковим рядком
• Об'єкти іменіщо починаються з / захоплюються цілком, від скісної риски до найближчого пробілу чи роздільника. Без цього ім'я на кшталт /R (поширений ключ ресурсу) можна було б прочитати як R посилання
• Коментаріпочинаються з % і тривають до кінця рядка, після чого ігноруються як непрозорий текст
• Перевірка «число, а потім R» є суворою.Посилання розпізнається лише як Nпробіл Gпробіл Rз Rпісля якого йде пробіл, роздільник або кінець вхідних даних. Якщо номер покоління відсутній або R за яким іде літера, цифри виводяться без змін. Це й захищає ціле число в /Length 1234 та чотири числа 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;

Змінюється лише номер об'єкта; номер покоління і точний початковий пробіл між токенами копіюються далі, тож вихід байт-у-байт збігається з вхідними даними, окрім одного цілого числа, яке потрібно було змінити. У цьому й полягає вся суть - так повторне використання вихідних байтів стає еквівалентом повного повторного серіалізування, а не просто близьким до нього. Поведінку покриває набір цільових модульних тестів, що перевіряють прості посилання, посилання в масивах, числа, які не є посиланнями, літеральні рядки, шістнадцяткові рядки та ненульові номери покоління зі зсувом, застосованим до них

Чому закладки не могли повторно використати AppendOutline

Злиття закладок кількох документів в одне дерево структури схоже на задачу для вже наявного AppendOutline допоміжного засобу, який уже вміє приєднувати верхньорівневі закладки одного документа до іншого. Але тут це не той інструмент, і причина в тонкій невідповідності рівнів абстракції. AppendOutline визначає поточну останню закладку верхнього рівня, проходячи читачем по байтах оригінального файлу. Але швидке злиття накопичує свої зміни в буфері нових об'єктів через ChangeObject; читач ніколи не бачить цих змін. З'єднайте три або більше документів, і кожне додавання перенаправляє оригінальну останню закладку першого документа на найновіший документ, тож закладки всіх проміжних документів випадають з ланцюга, правильним лишається лише сукупний /Count лишається правильним, тож помилку легко не помітити, доки хтось не відкриє панель закладок

Швидкий шлях розв'язує це за допомогою двофазного, керованого метаданими впровадження, яке ніколи не проганяє читач ще раз. Перший прохід по всіх вхідних даних збирає для кожного документа кореневий об'єкт структури та номери генерацій, номери першої й останньої закладки верхнього рівня та /Count. На основі цього зведення код обчислює глобальні номери об'єктів для кожного зв'язку, який треба зібрати: для закладки верхнього рівня кожного документа /Parent до спільного кореня, першої закладки - /Prev до останньої закладки попереднього документа, останньої закладки - /Next до першої закладки наступного документа, використовуючи чисту арифметику номерів об'єктів. За цим стоїть обмеження порядку запису: об'єкти першого документа записуються ще до того, як відкривається будь-який наступний документ, тож усі зміни структури першого документа (корінь /Count і /Last, а також старої останньої закладки - /Next) мають виражатися арифметикою, якій не потрібен жоден наступний документ під рукою. Зміни кожного наступного документа застосовуються на місці після відкриття, але до запису, тож вони проходять тим самим шляхом зміни об'єктів

Інваріант вирівнювання offset, який усе це з'єднує

І зсув посилання, і впровадження закладок залежать від одного арифметичного інваріанта, і це найкрихкіше припущення в усьому проєкті. Посилання, впроваджене в наступний документ, записується як цільовий глобальний номер об'єкта мінус Offset цього документа, щоб коли об'єкт пізніше буде зсунуто на ShiftIndRef(Offset) значення потрапило в потрібний глобальний номер. Перший документ отримує Offset = 0 і використовує глобальні номери напряму. Щоб це віднімання було правильним, поточна послідовність offset, що використовується під час впровадження, має збігатися з послідовністю offset, яка використовується під час фінального запису об'єктів

Так і є, завдяки особливості того, як працює злиття сторінок і форм: AddPages, AddFields, і AddFieldFonts змінюють лише наявні об'єкти першого документа - вони ніколи не додають нових. Отже, кількість об'єктів першого документа не змінюється на етапі злиття сторінок, а offset кожного наступного документа, тобто сума кількості об'єктів усіх попередніх документів, лишається сталою від впровадження до запису. Поруште це, додайте етап, який створює новий об'єкт посеред злиття, і кожне посилання на сторінку та закладку нижче по ланцюгу зміститься на кількість доданих об'єктів. Інваріант тихий, але він є несучим

Три точки входу над одним рушієм

Швидкий шлях не є відгалуженням коду злиття. У межах цієї ж роботи байтовий рушій було виділено в одну внутрішню процедуру, MergeFileListInternal(ListName, OutputFileName, PreserveStructTree, StrictMode), а публічні API стали тонкими обгортками, що вибирають два прапорці:

• MergeFileListFast викликає рушій із вимкненим збереженням дерева структури - це найлегший шлях, який прибирає дерево tagged-PDF, тож байтовий маршрут застосовується до найбільшої кількості об'єктів
• MergeFileList викликає його із увімкненим збереженням, тож дерево структури зберігається, а результат лишається придатним tagged PDF. Цей звичайний шлях також успадковує багатодокументне злиття закладок і форм
• MergeFileListStrict вмикає суворий режим: перший прохід метаданими зупиняється на першому вхідному файлі, який не повідомляє про чисте злиття, тож включаються лише документи, зібрані до проблемного файла, а не пропускається проблемний файл із подальшим продовженням

Об'єднання цих шляхів також дало змогу перебудувати звичайне злиття з попарного O(N²) циклу - зливати перший і другий файл, потім зливати результат із третім і так далі, щоразу повторно розбираючи зростаючий акумулятор - в один лінійний прохід, який відкриває кожен вхідний файл лише раз. Два давно наявні точки входу для двох файлів і двох потоків, MergeFiles і MergeStreams, не зачеплені й залишаються доступними для викликів, яким справді потрібне попарне злиття

Одна чесна примітка щодо поведінки дерева структури, бо це вдарило по тестовому набору. «Drop» у швидкому шляху не є повним: він прибирає посилання каталогу першого документа на /StructTreeRoot, але сам об'єкт дерева структури все одно записується як сирота. Тож байти швидкого виходу все ще містять рядок /StructTreeRoot string, і ви не можете відрізнити швидкий вихід від звичайного, шукаючи цей рядок, - реальна різниця в тому, чи каталог і далі веде до дерева структури, а саме це й визначає, чи файл лишається придатним до навігації tagged PDF

Коли який шлях обирати

Байтовий шлях - це оптимізація пропускної здатності для складання багатьох документів, коли вам не потрібно зберігати дерево структури tagged-PDF, наприклад для пакування звітів, пакетів виписок або масового об'єднання. На повторних злиттях наборів середнього й великого розміру повторне використання байтів скоротило час за годинником приблизно на чотири-тринадцять відсотків залежно від набору об'єктів, без нових збоїв на малих або пошкоджених вхідних даних, бо будь-який об'єкт, безпечність якого сканер не може довести, переходить на повний розбір. Якщо вам потрібне цілісне дерево структури для доступності, використовуйте звичайний tagged-PDF шлях злиття, який його зберігає; а якщо ви працюєте з дуже великими окремими файлами, а не з багатьма вхідними даними, техніки копіювання байтів, описані в супровідній статті про large PDF merge and split with direct file access застосовуйте ту саму філософію «копіювати байти, уникати повного дерева об'єктів» на рівні файла

Режими злиття та їхні швидкий і суворий варіанти є частиною PDFlibPas Delphi PDF Library, документація якої містить повний довідник для API списку файлів і параметрів злиття, описаних тут