Hrošči z vrstnim redom strani PDF v HotPDF: fizična proti logični strukturi

Simptom se je pojavil v pripomočku za kopiranje strani, zgrajenem na osnovi knjižnice HotPDF Component: zahteva za prvo stran dokumenta s tremi stranmi je dosledno vrnila drugo stran. Pregled logike indeksiranja ni pokazal nobenih napak. Klic je uporabljal logični indeks s štartno vrednostjo 0, aritmetika je bila pravilna, mejni pogoji so bili v redu. Kljub temu je bila vsakič izpisana napačna stran.

Hrošč sploh ni bil v kodi za kopiranje. Težava je bila v tem, kako je HotPDF ob nalaganju datoteke gradil svoje notranje polje strani.

Dva vrstna reda, en vir zmede

Datoteka PDF je zbirka posrednih objektov, od katerih je vsak označen s svojo številko. Struktura datoteke ne zahteva, da te številke odražajo vrstni red branja. Objekt 1 lahko vsebuje drugo stran, medtem ko objekt 20 vsebuje prvo stran. Tisto, kar dejansko določa vrstni red branja, je drevo strani: hierarhija slovarjev /Pages, katerih polja /Kids navajajo sklice na strani v zaporedju, v kakršnem jih mora pregledovalnik prikazati (ISO 32000-1 §7.7.3).

Dokument, ki je sprožil hrošča, je imel naslednjo strukturo drevesa strani:

{ 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 v bajtnem toku naključno navedla objekt 1 in objekt 4 pred objektom 20. Kateri koli parser, ki je pregledoval posredne objekte po vrstnem redu v datoteki in jih zapisoval v polje PageArr, ko je naletel na slovarje tipa page, bi končal z objektom 1 na indeksu 0, objektom 4 na indeksu 1 in objektom 20 na indeksu 2. Logična prva stran se tako nahaja na PageArr[2]. Zahteva za stran z indeksom 0 je zato vrnila logično drugo stran.

Točno to sta počeli obe notranji poti za razčlenjevanje v knjižnici HotXLS. Tradicionalna pot, uporabljena za datoteke PDF 1.3/1.4, in sodobna pot, uporabljena za dokumente s tokovi objektov (PDF 1.5+), sta obe gradili polje PageArr s prehajanjem posrednih objektov v fizičnem vrstnem redu datoteke, namesto da bi sledili verigi /Kids.

Potrditev hipoteze

Pred začetkom odpravljanja napake je bilo treba to neskladje dokazati in ne le predvidevati. Orodje qpdf v ukazni vrstici to opravi zelo enostavno:

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

Posamičen izvoz vsake strani in preverjanje velikosti datotek sta potrdila to preslikavo: PageArr[0] je ustvaril vsebino, ki pripada logični drugi strani, medtem ko je PageArr[2] vseboval logično prvo stran. Ta zamik je bil jasen dokaz. To je pojasnilo tudi, zakaj se je težava pojavila pri več različnih izvornih dokumentih: sprožil jo je vsak PDF, kjer so imeli objekti strani slučajno nižje številke objektov kot predhodna logična stran.

Obstaja preprost razlog, zakaj datoteke PDF končajo v takem stanju. Postopno shranjevanje (incremental saving) doda posodobljene objekte z novimi številkami objektov, pri čemer stari vnosi v tabeli navzkrižnih sklicev ne kažejo nikamor. Urejevalniki, ki dodajo naslovnico, jo vstavijo z visoko številko objekta, ne glede na njen položaj v polju Kids. Nekateri generatorji preprosto zapisujejo strani v vrstnem redu, ki je priročen za pretok vsebine, namesto v logičnem zaporedju strani. Format PDF od njih ne zahteva drugače.

Rešitev: sledenje polju Kids

Pravilen pristop je gradnja polja PageArr s prehodom verige /Kids iz korena kataloga in ne s pregledovanjem posrednih objektov. Ko obe poti zaključita svoj začetni prehod, korak po-procesiranja razreši logični vrstni red:

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;

Klic se izvede na koncu vsake poti razčlenjevanja, ko so vsi objekti katalogizirani, vendar pred izvedbo katere koli operacije na straneh:

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

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

Korak prerazporeditve ima časovno zahtevnost O(n * m), kjer je n število elementov Kids in m trenutna dolžina PageArr. Za kateri koli dokument z ravnim drevesom strani (vsi listi na globini 1, kar pokriva velika večina dejanskih PDF-jev) sta obe vrednosti enaki in strošek je zanemarljiv. Globoko ugniezdena drevesa strani zahtevajo rekurziven prehod namesto enonivojskega pristopa, ki je prikazan tukaj; produkcijska različica ta primer obravnava ločeno.

Uporaba funkcije CopyPageFromDocument po odpravi napake

Z uvedbo postopka ReorderPageArrByPagesTree logični indeksi strani delujejo po pričakovanjih. Višjenivojska funkcija CopyPageFromDocument sprejme logični indeks s štartno vrednostjo 0 in prekopira pravilno stran v ciljni 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;

Funkcija CopyPageFromDocument interno poizveduje po vrstnem redu drevesa strani, namesto da bi se zanašala na surovi indeks PageArr, zato deluje pravilno tudi pri dokumentih, kjer se fizični in logični vrstni red razlikujeta. Za paketne operacije funkcija InsertPagesFromDocument sprejme polje logičnih indeksov in jih prekopira v enem prehodu.

Kaj to razkriva o razčlenjevanju PDF

Specifikacija PDF je jasna: logični vrstni red strani določa polje /Kids v drevesu strani in ne številke objektov ali bajtni odmiki (ISO 32000-1 §7.7.3.2). Vsak parser, ki kot bližnjico uporablja drugačen vrstni red, bo vrnil pravilne rezultate pri večini dokumentov, saj večina generatorjev piše strani v naravnem vrstnem redu in dodeljuje zaporedne številke objektov. Hrošč ostane skrit, dokler nekdo ne naloži PDF-ja, ki je bil postopno urejan, reorganiziran z drugim orodjem ali pa ga je ustvaril program, ki je izbral drugačno postavitev.

Testiranje le na lastno ustvarjenih PDF-jih tovrstno težavo popolnoma spregleda. Popravek za napako pri vrstnem redu strani zato potrebuje zbirko dokumentov iz različnih virov: postopno shranjene datoteke, skenirane dokumente z vstavljenimi naslovnicami in PDF-je, ki so jih ustvarila orodja, ki drugače linearizirajo ali optimizirajo graf objektov. Dokument, ki je sprožil prvotnega hrošča, bi moral ostati del testne zbirke za preprečevanje ponovitve napak (regression suite).

Stran knjižnice HotPDF Component pokriva celoten vmesnik API za operacije s stranmi, vključno s CopyPageFromDocument, InsertPagesFromDocument in MovePage.