Greške u redosledu PDF stranica u HotPDF-u: Fizička naspram logičke strukture

Simptom se pojavio u programu za kopiranje stranica napravljenom pomoću komponente HotPDF Component: traženje prve stranice (indeks 0) dokumenta od tri stranice dosledno je davalo drugu stranicu. Provera logike indeksiranja nije otkrila nikakvu grešku. Poziv je koristio logički indeks sa početnom vrednošću 0, aritmetika je bila ispravna, granični uslovi su bili u redu. Pa ispit, svaki put bi se dobila pogrešna stranica

Greška uopšte nije bila u kodu za kopiranje. Nalazila se u načinu na koji je HotPDF gradio svoj interni niz stranica prilikom učitavanja datoteke

Dva redosleda, jedan izvor zabune

PDF datoteka je kolekcija indirektnih objekata, od kojih je svaki identifikovan brojem objekta. Struktura datoteke ne nameće obavezu da ti brojevi odražavaju redosled čitanja. Objekat 1 može da sadrži drugu stranicu, a objekat 20 prvu stranicu. Ono što zapravo definiše redosled čitanja jeste stablo stranica (page tree): hijerarhija rečnika /Pages čiji nizovi /Kids navode reference stranica u redosledu u kojem bi pregledač trebalo da ih prikaže (standard ISO 32000-1 §7.7.3)

Dokument koji je izazvao grešku imao je sledeću strukturu stabla stranica:

{ 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

Datoteka je u toku bajtova slučajno navodila objekat 1 i objekat 4 pre objekta 20. Svaki parser koji prolazi kroz indirektne objekte redosledom u datoteci i smešta ih u niz PageArr čim pronađe rečnike sa tipom stranice, završio bi sa objektom 1 na indeksu 0, objektom 4 na indeksu 1 i objektom 20 na indeksu 2. Logička stranica 1 se nalazi na PageArr[2]. Traženje indeksa stranice 0 stoga vraća logičku stranicu 2

To je upravo ono što su radile obe interne putanje analiziranja u HotPDF-u. Tradicionalna putanja, koja se koristi za datoteke PDF 1.3/1.4, i moderna putanja, koja se koristi za dokumente sa tokovima objekata (PDF 1.5+), gradile su niz PageArr prolazeći kroz indirektne objekte fizičkim redosledom u datoteci, umesto da prate lanac /Kids

Potvrda hipoteze

Pre bilo kakve izmene koda, neslaganje je moralo biti dokazano a ne samo pretpostavljeno. Alat qpdf u komandnoj liniji olakšava ovaj postupak:

{ 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 }

Izdvajanje svake stranice pojedinačno i provera veličina datoteka potvrdili su ovo mapiranje: ono što je generisao PageArr[0] bio je sadržaj koji pripada logičkoj stranici 2, a PageArr[2] je sadržao logičku stranicu 1. Kružni pomak je bio jasan dokaz. Ovo je takođe objasnilo zašto se problem javljao na više različitih izvornih dokumenata: svaki PDF u kojem su objekti stranica slučajno imali manje brojeve objekata od prethodnih logičkih stranica bi ga aktivirao

Postoji jasan razlog zašto PDF datoteke završavaju u ovom stanju. Inkrementalna čuvanja (incremental saves) dodaju ažurirane objekte sa novim brojevima objekata, ostavljajući stare slotove u tabeli unakrsnih referenci da ukazuju na ništa. Uređivači koji dodaju naslovnu stranicu umeću je sa visokim brojem objekta bez obzira na njenu poziciju u Kids nizu. Neki generatori jednostavno pišu stranice redosledom koji je pogodan za strimovanje sadržaja, a ne logičkim redosledom stranica. PDF format od njih i ne zahteva drugačije

Rešenje: pratite Kids niz

Ispravan pristup je da se PageArr izgradi prolaskom kroz lanac /Kids počevši od korena kataloga, a ne skeniranjem indirektnih objekata. Nakon što obe putanje analiziranja završe svoj početni prolaz, korak naknadne obrade rešava logički redosled:

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;

Poziv se umeće na kraju svake putanje analiziranja, nakon što su svi objekti popisani, ali pre nego što se izvrši bilo koja operacija nad stranicama:

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

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

Korak promene redosleda je složenosti O(n * m) gde je n broj Kids elemenata, a m je trenutna dužina niza PageArr, ali za svaki dokument sa ravnim stablom stranica (svi listovi na dubini 1, što pokriva veliku većinu stvarnih PDF-ova) obe vrednosti su iste i trošak je zanemarljiv. Duboko ugnježdena stabla stranica zahtevaju rekurzivni prolaz umesto jednoslojnog pristupa koji je ovde prikazan; produkciona implementacija taj slučaj rešava odvojeno

Korišćenje metode CopyPageFromDocument nakon popravke

Sa aktivnom procedurom ReorderPageArrByPagesTree, logički indeksi stranica rade kako se očekuje. Metoda višeg nivoa CopyPageFromDocument prima logički indeks sa početnom vrednošću 0 i kopira ispravnu stranicu u odredišni dokument:

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;

Metoda CopyPageFromDocument interno ispituje redosled stabla stranica umesto da se oslanja na sirovi indeks niza PageArr, tako da se ponaša ispravno čak i kod dokumenata kod kojih se fizički i logički redosled razlikuju. Za grupne operacije, InsertPagesFromDocument prihvata niz logičkih indeksa i kopira ih u jednom prolazu

Šta ovo otkriva o analiziranju PDF-a

Specifikacija PDF-a je izričita: logički redosled stranica je definisan nizom /Kids u stablu stranica, a ne brojevima objekata ili bajt-ofsetima (standard ISO 32000-1 §7.7.3.2). Svaki parser koji koristi drugačiji redosled kao prečicu davaće tačne rezultate na većini dokumenata na koje naiđe, jer većina generatora piše stranice prirodnim redosledom i dodeljuje uzastopne brojeve objekata. Greška ostaje skrivena sve dok neko ne učita PDF koji je inkrementalno uređivan, reorganizovan drugim alatom ili generisan softverom koji je izabrao drugačiji raspored

Testiranje samo na sopstvenim generisanim PDF datotekama potpuno propušta ovu klasu problema. Rešenje za regresiju redosleda stranica stoga zahteva korpus dokumenata iz različitih izvora: inkrementalna čuvanja, skenirane dokumente sa umetnutim naslovnim stranicama, PDF-ove koje su generisali alati koji drugačije linearizuju ili optimizuju graf objekata. Dokument koji je izazvao prvobitnu grešku trebalo bi trajno da ostane u regresionom test-skupu

Stranica HotPDF Component pokriva kompletan API za operacije nad stranicama, uključujući CopyPageFromDocument, InsertPagesFromDocument i MovePage