Błędy kolejności stron PDF w HotPDF: Struktura fizyczna a logiczna

Objaw pojawił się w narzędziu do kopiowania stron zbudowanym na komponencie HotPDF Delphi Component: żądanie strony 1 z trzystronicowego dokumentu za każdym razem zwracało stronę 2. Sprawdzenie logiki indeksowania nie wykazało niczego złego. Wywołanie używało indeksu logicznego liczonego od zera, arytmetyka była poprawna, warunki brzegowe były w porządku. A mimo to za każdym razem wychodziła zła strona

Błąd wcale nie leżał w kodzie kopiującym. Leżał w sposobie, w jaki HotPDF budował swoją wewnętrzną tablicę stron podczas wczytywania pliku

Dwa porządki, jedno źródło nieporozumień

Plik PDF to zbiór obiektów pośrednich, z których każdy jest identyfikowany numerem obiektu. Struktura pliku nie nakłada na te numery żadnego obowiązku odzwierciedlania kolejności czytania. Obiekt 1 może zawierać stronę 2; obiekt 20 może zawierać stronę 1. Tym, co faktycznie definiuje kolejność czytania, jest drzewo stron: hierarchia słowników /Pages, których tablice /Kids wymieniają odwołania do stron w kolejności, w jakiej przeglądarka powinna je wyświetlać (ISO 32000-1 §7.7.3)

Dokument wywołujący błąd miał taką strukturę drzewa stron:

{ Korzeń drzewa Pages, obiekt 16 }
16 0 obj
<<
  /Type /Pages
  /Count 3
  /Kids [20 0 R   { strona logiczna 1 }
         1 0 R    { strona logiczna 2 }
         4 0 R]   { strona logiczna 3 }
>>
endobj

W tym pliku obiekt 1 i obiekt 4 znalazły się w strumieniu bajtów przed obiektem 20. Każdy parser, który przechodzi przez obiekty pośrednie w kolejności pliku i wpisuje je do PageArr w miarę napotykania słowników typu strona, skończy z obiektem 1 na indeksie 0, obiektem 4 na indeksie 1 i obiektem 20 na indeksie 2. Strona logiczna 1 siedzi wtedy pod PageArr[2]. Żądanie indeksu strony 0 pobiera zamiast niej stronę logiczną 2

Dokładnie to robiły obie wewnętrzne ścieżki parsowania w HotPDF. Ścieżka tradycyjna, używana dla plików PDF 1.3/1.4, i ścieżka nowoczesna, używana dla dokumentów ze strumieniami obiektów (PDF 1.5+), każda budowała PageArr, przechodząc przez obiekty pośrednie w fizycznej kolejności pliku, zamiast podążać za łańcuchem /Kids

Potwierdzenie hipotezy

Zanim dotknięto jakiejkolwiek poprawki, rozbieżność trzeba było udowodnić, a nie tylko założyć. Narzędzie wiersza poleceń qpdf ułatwia to zadanie:

{ powłoka }
qpdf --show-pages input.pdf
{ Wynik ujawnia kolejność Kids: 20 0 R, potem 1 0 R, potem 4 0 R }

qpdf --show-object="16 0 R" input.pdf
{ Pokazuje słownik Pages z /Kids w kolejności czytania }

Wyodrębnienie każdej strony osobno i sprawdzenie rozmiarów plików potwierdziło to mapowanie: to, co produkował PageArr[0], było treścią należącą do strony logicznej 2, a PageArr[2] trzymał stronę logiczną 1. To cykliczne przesunięcie było dymiącym pistoletem. To wyjaśniało również, dlaczego problem pojawiał się w wielu różnych dokumentach źródłowych: wywoływał go każdy plik PDF, w którym obiekty strony miały akurat niższe numery obiektów niż wcześniejsza strona logiczna

Istnieje prosty powód, dla którego pliki PDF trafiają w taki stan. Zapisy przyrostowe dopisują zaktualizowane obiekty z nowymi numerami obiektów, zostawiając stare miejsca w tabeli odwołań krzyżowych wskazujące donikąd. Edytory, które dodają stronę tytułową, wstawiają ją z wysokim numerem obiektu, niezależnie od jej pozycji w tablicy Kids. Niektóre generatory po prostu zapisują strony w kolejności wygodnej dla strumieniowania treści, a nie w logicznej sekwencji stron. Format PDF nie wymaga od nich niczego innego

Poprawka: podążanie za tablicą Kids

Poprawnym podejściem jest budowanie PageArr przez przejście łańcucha /Kids od korzenia katalogu, a nie przez skanowanie obiektów pośrednich. Po zakończeniu wstępnego przebiegu przez obie ścieżki parsowania krok post-processingu rozwiązuje kolejność logiczną:

procedure THotPDF.ReorderPageArrByPagesTree;
var
  PagesObj  : THPDFDictionaryObject;
  KidsArray : THPDFArrayObject;
  NewPageArr: array of THPDFDictArrItem;
  I, J, PageIndex, KidsIndex: Integer;
  RefObj    : THPDFLink;
  PageObjNum: Integer;
  Found     : Boolean;
begin
  { Odnajdź korzeniowy słownik /Pages poprzez 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;
    { Węzły Kids niebędące stronami (pośrednie węzły /Pages) nie dają dopasowania; pomijamy je }
  end;

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

Wywołanie trafia na koniec każdej ścieżki parsowania, po skatalogowaniu wszystkich obiektów, ale przed obsłużeniem jakiejkolwiek operacji na stronach:

{ Ścieżka tradycyjna }
ListExtDictionary(THPDFDictionaryObject(IndirectObjects.Items[I]), FPageslink);
ReorderPageArrByPagesTree;
Break;

{ Ścieżka nowoczesna (strumienie obiektów) }
if TryParseModernPDF then
begin
  Result := ModernPageCount;
  ReorderPageArrByPagesTree;
  Exit;
end;

Krok reorganizacji ma złożoność O(n * m), gdzie n to liczba elementów Kids, a m to bieżąca długość PageArr, ale dla każdego dokumentu z płaskim drzewem stron (wszystkie liście na głębokości 1, co obejmuje zdecydowaną większość rzeczywistych plików PDF) obie wartości są sobie równe, a koszt jest pomijalny. Głęboko zagnieżdżone drzewa stron wymagają rekurencyjnego przejścia zamiast podejścia jednopoziomowego pokazanego tutaj; produkcyjna implementacja obsługuje ten przypadek osobno

Używanie CopyPageFromDocument po poprawce

Gdy ReorderPageArrByPagesTree jest już na miejscu, logiczne indeksy stron działają zgodnie z oczekiwaniami. Wyższego poziomu CopyPageFromDocument przyjmuje indeks logiczny liczony od zera i kopiuje właściwą stronę do dokumentu docelowego:

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

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

    { Kopiuje logiczną stronę 0 (pierwsza strona widziana przez użytkownika) }
    Dest.CopyPageFromDocument(Source, 0, 0);

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

CopyPageFromDocument wewnętrznie odpytuje kolejność drzewa stron zamiast polegać na surowym indeksie PageArr, więc zachowuje się poprawnie nawet wobec dokumentów, w których kolejność fizyczna i logiczna się rozjeżdżają. Do operacji wsadowych InsertPagesFromDocument przyjmuje tablicę indeksów logicznych i kopiuje je w jednym przebiegu

Co to mówi o parsowaniu PDF

Specyfikacja PDF jest jednoznaczna: logiczna kolejność stron jest definiowana przez tablicę /Kids drzewa stron, a nie przez numery obiektów czy przesunięcia bajtowe (ISO 32000-1 §7.7.3.2). Każdy parser, który jako skrót używa innego porządkowania, da poprawne wyniki dla większości napotkanych dokumentów, ponieważ większość generatorów zapisuje strony w naturalnej kolejności i przypisuje sekwencyjne numery obiektów. Błąd ukrywa się, dopóki ktoś nie wczyta pliku PDF, który był edytowany przyrostowo, przeorganizowany przez inne narzędzie, albo wygenerowany przez oprogramowanie, które wybrało inny układ

Testowanie wyłącznie na plikach PDF wygenerowanych we własnym zakresie całkowicie pomija tę klasę problemów. Poprawka regresji kolejności stron potrzebuje więc korpusu dokumentów z różnorodnych źródeł: zapisów przyrostowych, zeskanowanych dokumentów ze wstawionymi stronami tytułowymi, plików PDF wyprodukowanych przez narzędzia, które linearyzują lub optymalizują graf obiektów w inny sposób. Dokument, który wywołał pierwotny błąd, powinien pozostać w zestawie testów regresyjnych na stałe

Strona HotPDF Delphi Component obejmuje pełne API dla operacji na stronach, w tym CopyPageFromDocument, InsertPagesFromDocument i MovePage