PDF puslapių sekos klaidos HotPDF: fizinė prieš loginę struktūrą

Simptomas pasireiškė puslapių kopijavimo programoje, sukurtoje naudojant HotPDF Component komponentą: prašant pirmojo puslapio (indeksas 1) trijų puslapių dokumente, programa nuolat pateikdavo antrąjį puslapį. Indeksavimo logikos patikrinimas nerodė jokių klaidų. Iškvietimas naudojo loginį indeksą nuo 0, aritmetika buvo teisinga, o ribinės sąlygos – tvarkingos. Nepaisant to, kiekvieną kartą buvo atvaizduojamas neteisingas puslapis.

Klaida buvo visiškai ne kopijavimo kode. Ji slypėjo tame, kaip HotPDF kūrė savo vidinį puslapių masyvą failo įkėlimo metu.

Dvi sekos, vienas painiavos šaltinis

PDF failas yra netiesioginių objektų rinkinys, kur kiekvienas objektas identifikuojamas objekto numeriu. Failo struktūra neįpareigoja šių numerių atspindėti skaitymo sekos. 1 objektas gali saugoti 2 puslapį, o 20 objektas – 1 puslapį. Tai, kas iš tikrųjų apibrėžia skaitymo seką, yra puslapių medis – /Pages žodynų hierarchija, kurios /Kids masyvuose pateikiamos nuorodos į puslapius ta seka, kuria skaitytuvas turėtų juos rodyti (ISO 32000-1 §7.7.3).

Dokumentas, sukėlęs klaidą, turėjo tokią puslapių medžio struktūrą:

{ 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

Faile 1 objektas ir 4 objektas sraute buvo išvardyti prieš 20 objektą. Bet koks analizatorius, kuris eitų per netiesioginius objektus failo tvarka ir registruotų juos PageArr masyve, kai tik ras puslapio tipo žodyną, gautų 1 objektą indekse 0, 4 objektą indekse 1 ir 20 objektą indekse 2. Taigi, 1 loginis puslapis atsidurtų ties PageArr[2]. Prašant puslapio su indeksu 0, būtų grąžinamas 2 loginis puslapis.

Būtent tai darė abu HotPDF vidiniai analizavimo keliai. Tradicinis kelias, naudojamas PDF 1.3/1.4 failams, ir modernus kelias, naudojamas objektų srauto dokumentams (PDF 1.5+), abu kūrė PageArr masyvą eidami per netiesioginius objektus fizine failo tvarka, o ne sekdami /Kids grandine.

Hipotezės patvirtinimas

Prieš imantis bet kokių taisymų, šį neatitikimą reikėjo įrodyti, o ne daryti prielaidą. Programos „qpdf“ komandinės eilutės įrankis leidžia tai padaryti labai paprastai:

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

Ištraukus kiekvieną puslapį atskirai ir patikrinus failų dydžius, šis susiejimas pasitvirtino: tai, ką sugeneravo PageArr[0], buvo turinys, priklausantis 2 loginiam puslapiui, o PageArr[2] turėjo 1 loginį puslapį. Šis pasislinkimas ratu buvo tiesioginis įrodymas. Tai taip pat paaiškino, kodėl problema pasireiškė keliuose skirtinguose šaltinio dokumentuose: bet kuris PDF failas, kuriame puslapio objektai atsitiktinai turėjo mažesnius objektų numerius nei ankstesnis loginis puslapis, sukeldavo šį sutrikimą.

Yra paprasta priežastis, kodėl PDF failai atsiduria tokioje būsenoje. Priaugamieji išsaugojimai (angl. incremental saves) prideda atnaujintus objektus su naujais numeriais, palikdami senas vietas kryžminių nuorodų lentelėje nurodančias į niekur. Redaktoriai, kurie prideda titulinį puslapį, įterpia jį su dideliu objekto numeriu, nepriklausomai nuo jo pozicijos Kids masyve. Kai kurie generatoriai tiesiog įrašo puslapius tokia tvarka, kuri yra patogi turinio srautui, o ne pagal loginę puslapių seką. PDF formatas nereikalauja iš jų elgtis kitaip.

Pataisymas: sekimas Kids masyvu

Teisingas būdas yra kurti PageArr masyvą einant per /Kids grandinę nuo katalogo šaknies, o ne skenuojant netiesioginius objektus. Kai abu analizavimo keliai baigia savo pradinį etapą, papildomas apdorojimo žingsnis išsprendžia loginę tvarką:

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;

Iškvietimas įterpiamas kiekvieno analizavimo kelio pabaigoje, kai visi objektai yra suregistruoti, bet prieš pradedant bet kokią puslapio operaciją:

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

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

Perrikiavimo žingsnis yra O(n * m) sudėtingumo, kur n yra Kids sąrašo elementų skaičius, o m – dabartinis PageArr ilgis. Bet kuriam dokumentui su plokščiu puslapių medžiu (visi lapai yra 1 lygio gylyje, o tai apima didžiąją dalį realių PDF failų) abu šie dydžiai yra vienodi, tad laiko sąnaudos yra nereikšmingos. Giliai lizdiniams puslapių medžiams reikalingas rekursinis perėjimas, o ne čia parodytas vieno lygio metodas; gamybinė realizacija šį atvejį apdoroja atskirai.

CopyPageFromDocument naudojimas po pataisymo

Įdiegus ReorderPageArrByPagesTree, loginiai puslapių indeksai veikia taip, kaip tikimasi. Aukštesnio lygio metodas CopyPageFromDocument priima loginį indeksą nuo 0 ir nukopijuoja teisingą puslapį į tikslinį 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;

Metodas CopyPageFromDocument viduje užklausia puslapių medžio seką, o ne pasikliauja tiesioginiu PageArr indeksu, todėl jis veikia teisingai netgi su tais dokumentais, kuriuose fizinė ir loginė seka skiriasi. Paketiniams veiksmams InsertPagesFromDocument priima loginių indeksų masyvą ir nukopijuoja juos vienu žingsniu.

Ką tai atskleidžia apie PDF analizavimą

PDF specifikacija yra aiški: loginę puslapio seką apibrėžia puslapių medžio /Kids masyvas, o ne objektų numeriai ar baitų poslinkiai (ISO 32000-1 §7.7.3.2). Bet koks analizatorius, kuris naudoja kitokią seką kaip trumpesnį kelią, duos teisingus rezultatus daugumoje dokumentų, nes dauguma generatorių įrašo puslapius natūralia tvarka ir priskiria nuoseklius objektų numerius. Ši klaida lieka nepastebėta tol, kol kas nors neįkelia PDF failo, kuris buvo redaguotas priaugamuoju būdu, pertvarkytas kito įrankio arba sugeneruotas programinės įrangos, parinkusios kitokį išdėstymą.

Testavimas tik su pačių sugeneruotais PDF failais visiškai praleidžia šios klasės problemą. Puslapių sekos regresijos pataisymui reikalingas dokumentų rinkinys iš įvairių šaltinių: priaugamųjų išsaugojimų, nuskenuotų dokumentų su įterptais tituliniais puslapiais, PDF failų, sukurtų įrankiais, kurie kitaip atlieka tiesinimą (angl. linearization) ar optimizuoja objektų grafiką. Dokumentas, kuris sukėlė šią klaidą, turėtų visam laikui likti regresinio testavimo rinkinyje.

Komponento HotPDF Component puslapis apima pilną puslapių operacijų API, įskaitant CopyPageFromDocument, InsertPagesFromDocument ir MovePage.