PDF Page Order Bugs in HotPDF: Physical vs Logical Structure

Simptom se pojavio u uslužnom programu za kopiranje stranica izgrađenom na vrhu komponente HotPDF: traženje stranice 1 dokumenta od tri stranice dosljedno je proizvodilo stranicu 2. Provjera logike indeksiranja nije otkrila nikakve pogreške. Poziv je koristio logički indeks temeljen na 0, aritmetika je bila točna, a granični uvjeti u redu. Ipak, svaki put bi ispala pogrešna stranica.

Pogreška uopće nije bila u kodu za kopiranje. Bila je u načinu na koji je HotPDF gradio svoj unutarnji niz stranica prilikom učitavanja datoteke.

Dva redoslijeda, jedan izvor zabune

PDF datoteka je zbirka neizravnih objekata, od kojih je svaki identificiran brojem objekta. Fizička struktura datoteke ne nameće nikakvu obvezu da ti brojevi odražavaju redoslijed čitanja. Objekt 1 može sadržavati stranicu 2; objekt 20 može sadržavati stranicu 1. Ono što zapravo definira redoslijed čitanja jest stablo stranica: hijerarhija rječnika /Pages čija polja /Kids navode reference stranica u nizu u kojem bi ih preglednik trebao prikazati (ISO 32000-1 §7.7.3).

Dokument koji je izazvao pogrešku imao je ovu 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 slučajno navela objekt 1 i objekt 4 prije objekta 20 u toku bajtova. Svaki parser koji prolazi kroz neizravne objekte redoslijedom u datoteci i upisuje ih u PageArr kako pronalazi rječnike tipa stranice završio bi s objektom 1 na indeksu 0, objektom 4 na indeksu 1 i objektom 20 na indeksu 2. Logička stranica 1 nalazi se na PageArr[2]. Traženje indeksa stranice 0 stoga dohvaća logičku stranicu 2.

To je upravo ono što su činila oba interna puta parsiranja u HotPDF-u. Tradicionalni put, koji se koristi za datoteke PDF 1.3/1.4, i moderni put, koji se koristi za dokumente s tokovima objekata (PDF 1.5+), gradili su PageArr prolazeći kroz neizravne objekte u fizičkom redoslijedu datoteke umjesto da prate lanac /Kids.

Potvrda hipoteze

Prije bilo kakvog popravka, nesuglasje je trebalo dokazati, a ne samo pretpostaviti. Alat naredbenog retka qpdf to čini jednostavnim:

{ 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 provjera veličina datoteka potvrdili su mapiranje: ono što je proizveo PageArr[0] bio je sadržaj koji pripada logičkoj stranici 2, dok je PageArr[2] sadržavao logičku stranicu 1. Kružno pomicanje bilo je krunski dokaz. To je također objasnilo zašto se problem pojavio na više različitih izvornih dokumenata: svaki PDF u kojem su objekti stranica slučajno imali manje brojeve objekata od ranije logičke stranice izazvao bi ovaj problem.

Postoji jasan razlog zašto PDF-ovi završavaju u ovom stanju. Inkrementalna spremanja dodaju ažurirane objekte s novim brojevima objekata, ostavljajući stara mjesta u tablici unakrsnih referenci da ne pokazuju nigdje. Urednici koji dodaju naslovnu stranicu umeću je s visokim brojem objekta bez obzira na njezin položaj u polju Kids. Neki generatori jednostavno pišu stranice redoslijedom koji je prikladan za strujanje sadržaja, a ne logičkim slijedom stranica. PDF format od njih ne zahtijeva drugačije.

Popravak: pratite polje Kids

Ispravan pristup je izgradnja PageArr praćenjem lanca /Kids iz korijena kataloga, a ne skeniranjem neizravnih objekata. Nakon što oba puta parsiranja završe svoj početni prolaz, korak naknadne obrade rješava logički redoslijed:

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 kraj svakog puta parsiranja, nakon što su svi objekti katalogizirani, ali prije nego što se izvrši bilo koja operacija nad stranicom:

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

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

Korak preraspodjele je složenosti O(n * m), gdje je n broj Kids stavki, a m trenutna duljina PageArr-a, ali za bilo koji dokument s ravnim stablom stranica (svi listovi na dubini 1, što pokriva veliku većinu stvarnih PDF-ova), obje su vrijednosti iste i trošak je zanemariv. Duboko ugniježđena stabla stranica zahtijevaju rekurzivni prolaz umjesto ovdje prikazanog jednorazinskog pristupa; produkcijska implementacija rješava taj slučaj zasebno.

Korištenje CopyPageFromDocument nakon popravka

S uvedenim ReorderPageArrByPagesTree, logički indeksi stranica rade očekivano. Viša razina CopyPageFromDocument uzima logički indeks temeljen na 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;

CopyPageFromDocument interno ispituje redoslijed stabla stranica umjesto da se oslanja na sirovi indeks PageArr, pa se ponaša ispravno čak i kod dokumenata u kojima se fizički i logički redoslijed razlikuju. Za skupne operacije, InsertPagesFromDocument prihvaća polje logičkih indeksa i kopira ih u jednom prolazu.

Što nam ovo otkriva o parsiranju PDF-a

PDF specifikacija je eksplicitna: logički redoslijed stranica definiran je poljem /Kids stabla stranica, a ne brojevima objekata ili pomacima bajtova (ISO 32000-1 §7.7.3.2). Svaki parser koji koristi drugačiji redoslijed kao prečac dat će ispravne rezultate na većini dokumenata koje vidi, jer većina generatora piše stranice prirodnim redoslijedom i dodjeljuje sekvencijalne brojeve objekata. Pogreška ostaje skrivena sve dok netko ne učita PDF koji je inkrementalno uređivan, reorganiziran drugim alatom ili generiran softverom koji je odabrao drugačiji izgled.

Testiranje samo na vlastitim generiranim PDF-ovima potpuno propušta ovu klasu problema. Popravak regresije redoslijeda stranica stoga zahtijeva korpus dokumenata iz različitih izvora: inkrementalnih spremanja, skeniranih dokumenata s umetnutim naslovnim stranicama, PDF-ova proizvedenih alatima koji različito lineariziraju ili optimiziraju graf objekata. Dokument koji je izazvao izvornu pogrešku trebao bi trajno ostati u regresijskom paketu.

Stranica komponente HotPDF pokriva cijeli API za operacije nad stranicama, uključujući CopyPageFromDocument, InsertPagesFromDocument i MovePage.