Помилки порядку сторінок PDF у HotPDF: фізична та логічна структура

Симптом проявився в утиліті копіювання сторінок, побудованій на базі HotPDF Component: запит на сторінку 1 з тристорінкового документа постійно видавав сторінку 2. Перевірка логіки індексації не виявила нічого підозрілого. Виклик використовував логічний індекс від нуля, арифметика була правильною, граничні умови в нормі. Проте щоразу видавалася не та сторінка

Помилка була зовсім не в коді копіювання. Вона ховалася в тому, як HotPDF формував свій внутрішній масив сторінок під час завантаження файлу

Два порядки, одне джерело плутанини

PDF файл є набором непрямих об'єктів, кожен з яких ідентифікується номером об'єкта. Структура файлу не зобов'язує ці номери відображати порядок читання. Об'єкт 1 може містити сторінку 2, об'єкт 20 може містити сторінку 1. Те, що насправді визначає порядок читання, є деревом сторінок: ієрархія словників /Pages, чиї масиви /Kids перелічують посилання на сторінки у тій послідовності, в якій програма перегляду повинна їх відображати (ISO 32000-1 §7.7.3)

Документ, що викликав помилку, мав таку структуру дерева сторінок:

{ Pages tree root, object 16 }
16 0 obj
<<
  /Type /Pages
  /Count 3
  /Kids [20 0 R   { logical page 1 }
         1 0 R    { logical page 2 }
         4 0 R]   { logical page 3 }
>>
endobj

Файл випадковим чином розташував об'єкт 1 та об'єкт 4 перед об'єктом 20 у потоці байтів. Будь-який парсер, який би перебирав непрямі об'єкти у порядку файлу та заносив їх до PageArr під час знаходження словників типу сторінки, отримав би об'єкт 1 на індексі 0, об'єкт 4 на індексі 1 та об'єкт 20 на індексі 2. Логічна сторінка 1 знаходиться в PageArr[2]. Запит індексу сторінки 0 натомість витягує логічну сторінку 2

Це саме те, що робили обидва внутрішні шляхи парсингу HotPDF. Традиційний шлях, що використовується для файлів PDF 1.3/1.4, та сучасний шлях, що використовується для документів з потоками об'єктів (PDF 1.5+), кожен будував PageArr обходячи непрямі об'єкти у фізичному порядку файлу, а не слідуючи ланцюжку /Kids

Підтвердження гіпотези

Перш ніж братися за виправлення, невідповідність потрібно було довести, а не просто припустити. Утиліта командного рядка qpdf робить це дуже просто:

{ shell }
qpdf --show-pages input.pdf
{ Output reveals Kids order: 20 0 R, then 1 0 R, then 4 0 R }

qpdf --show-object="16 0 R" input.pdf
{ Shows the Pages dictionary with /Kids in reading order }

Витягнення кожної сторінки окремо та перевірка розмірів файлів підтвердили відображення: те, що видавало PageArr[0], було вмістом, що належав логічній сторінці 2, а PageArr[2] містив логічну сторінку 1. Круговий зсув був беззаперечним доказом. Це також пояснило, чому проблема виникала в багатьох різних вихідних документах: будь-який PDF, де об'єкти сторінок випадково мали менші номери об'єктів, ніж попередня логічна сторінка, спричиняв би її

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

Виправлення: слідування за масивом Kids

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

procedure THotPDF.ReorderPageArrByPagesTree;
var
  PagesObj  : THPDFDictionaryObject;
  KidsArray : THPDFArrayObject;
  NewPageArr: array of THPDFDictArrItem;
  I, J, PageIndex, KidsIndex: Integer;
  RefObj    : THPDFLink;
  PageObjNum: Integer;
  Found     : Boolean;
begin
  { Locate root /Pages dictionary via FRootIndex }
  PagesObj := FindPagesRootFromCatalog;
  if PagesObj = nil then Exit;

  KidsIndex := PagesObj.FindValue('Kids');
  if KidsIndex < 0 then Exit;
  KidsArray := THPDFArrayObject(PagesObj.GetIndexedItem(KidsIndex));

  SetLength(NewPageArr, KidsArray.Items.Count);
  PageIndex := 0;

  for I := 0 to KidsArray.Items.Count - 1 do
  begin
    RefObj     := THPDFLink(KidsArray.GetIndexedItem(I));
    PageObjNum := RefObj.Value.ObjectNumber;

    Found := False;
    for J := 0 to Length(PageArr) - 1 do
    begin
      if PageArr[J].PageLink.ObjectNumber = PageObjNum then
      begin
        NewPageArr[PageIndex] := PageArr[J];
        Inc(PageIndex);
        Found := True;
        Break;
      end;
    end;
    { Non-page Kids (intermediate /Pages nodes) produce no match; skip }
  end;

  if PageIndex > 0 then
  begin
    SetLength(PageArr, PageIndex);
    for I := 0 to PageIndex - 1 do
      PageArr[I] := NewPageArr[I];
  end;
end;

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

{ Traditional path }
ListExtDictionary(THPDFDictionaryObject(IndirectObjects.Items[I]), FPageslink);
ReorderPageArrByPagesTree;
Break;

{ Modern path (object streams) }
if TryParseModernPDF then
begin
  Result := ModernPageCount;
  ReorderPageArrByPagesTree;
  Exit;
end;

Етап перевпорядкування має складність O(n * m), де n це кількість Kids, а m поточна довжина PageArr, але для будь-якого документа з плоским деревом сторінок (всі листки на глибині 1, що охоплює переважну більшість реальних PDF-файлів) обидва значення однакові і витрати є незначними. Глибоко вкладені дерева сторінок вимагають рекурсивного обходу, а не однорівневого підходу, показаного тут; виробнича реалізація обробляє цей випадок окремо

Використання CopyPageFromDocument після виправлення

З реалізованим ReorderPageArrByPagesTree логічні індекси сторінок працюють як очікується. Високорівнева функція CopyPageFromDocument приймає логічний індекс від нуля та копіює правильну сторінку до цільового документа:

var
  Source, Dest: THotPDF;
begin
  Source := THotPDF.Create(nil);
  Dest   := THotPDF.Create(nil);
  try
    Source.LoadFromFile('source.pdf');

    Dest.FileName := 'extracted.pdf';
    Dest.BeginDoc;

    { Copy logical page 0 (first page the user sees) }
    Dest.CopyPageFromDocument(Source, 0, 0);

    Dest.EndDoc;
  finally
    Source.Free;
    Dest.Free;
  end;
end;

CopyPageFromDocument внутрішньо запитує порядок дерева сторінок замість того, щоб покладатися на необроблений індекс PageArr, тому вона поводиться правильно навіть з документами, де фізичний та логічний порядок розходяться. Для пакетних операцій InsertPagesFromDocument приймає масив логічних індексів і копіює їх за один прохід

Що це показує про парсинг PDF

Специфікація PDF є чіткою: логічний порядок сторінок визначається масивом /Kids дерева сторінок, а не номерами об'єктів чи зміщенням байтів (ISO 32000-1 §7.7.3.2). Будь-який парсер, який використовує інше впорядкування як швидкий шлях, даватиме правильні результати на більшості документів, з якими він стикається, оскільки більшість генераторів записують сторінки у природному порядку та призначають послідовні номери об'єктів. Помилка ховається доти, доки хтось не завантажить PDF, який був інкрементально відредагований, реорганізований іншим інструментом або згенерований програмним забезпеченням, що обрало інше компонування

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

Сторінка HotPDF Component охоплює повний API для операцій зі сторінками, включаючи CopyPageFromDocument, InsertPagesFromDocument та MovePage