Chyby v pořadí stránek PDF v HotPDF: Fyzická vs. logická struktura

Příznak se projevil v nástroji pro kopírování stránek postaveném na komponentě HotPDF Component: dotaz na stránku 1 ze třístránkového dokumentu trvale vyprodukoval stránku 2. Kontrola indexovací logiky nenašla nic špatného. Volání používalo logický index založený na 0, aritmetika byla správná, okrajové podmínky byly v pořádku. Přesto se pokaždé objevila nesprávná stránka

Chyba vůbec nebyla v kopírovacím kódu. Byla ve způsobu, jakým HotPDF sestavoval své vnitřní pole stránek při načítání souboru

Dvě uspořádání, jeden zdroj zmatku

Soubor PDF je sbírka nepřímých objektů, z nichž každý je identifikován číslem objektu. Struktura souboru neukládá těmto číslům žádnou povinnost odrážet pořadí čtení. Objekt 1 může obsahovat stránku 2; objekt 20 může obsahovat stránku 1. To, co skutečně definuje pořadí čtení, je strom stránek: hierarchie slovníků /Pages, jejichž pole /Kids obsahují seznam odkazů na stránky v sekvenci, ve které by je měl prohlížeč zobrazovat (ISO 32000-1 §7.7.3)

Dokument, který spouštěl chybu, měl tuto strukturu stromu stránek:

{ Kořen stromu Pages, objekt 16 }
16 0 obj
<<
  /Type /Pages
  /Count 3
  /Kids [20 0 R   { logická stránka 1 }
         1 0 R    { logická stránka 2 }
         4 0 R]   { logická stránka 3 }
>>
endobj

Soubor náhodou uváděl objekt 1 a objekt 4 před objektem 20 v bytovém proudu. Jakýkoli parser, který iteroval přes nepřímé objekty v pořadí souboru a vkládal je do PageArr, jak nacházel slovníky typu stránka, by skončil s objektem 1 na indexu 0, objektem 4 na indexu 1 a objektem 20 na indexu 2. Logická stránka 1 leží na PageArr[2]. Dotaz na index stránky 0 načte místo toho logickou stránku 2

To je přesně to, co dělaly obě vnitřní cesty parsování v HotPDF. Tradiční cesta, používaná pro soubory PDF 1.3/1.4, a moderní cesta, používaná pro dokumenty s toky objektů (PDF 1.5+), obě sestavovaly PageArr procházením nepřímých objektů ve fyzickém pořadí souboru, spíše než sledováním řetězce /Kids

Potvrzení hypotézy

Před uplatněním jakékoli opravy bylo nutné neshodu spíše prokázat než předpokládat. Nástroj příkazové řádky qpdf to činí přímočarým:

{ shell }
qpdf --show-pages input.pdf
{ Výstup odhaluje pořadí Kids: 20 0 R, poté 1 0 R, poté 4 0 R }

qpdf --show-object="16 0 R" input.pdf
{ Zobrazuje slovník Pages s /Kids v pořadí pro čtení }

Extrahování každé stránky jednotlivě a kontrola velikostí souborů potvrdily mapování: to, co PageArr[0] vyprodukovalo, byl obsah patřící logické stránce 2, a PageArr[2] obsahovalo logickou stránku 1. Cyklický posun byl jasným důkazem. To také vysvětlovalo, proč se problém objevoval napříč několika různými zdrojovými dokumenty: jakékoli PDF, kde objekty stránek náhodou měly nižší čísla objektů než dřívější logická stránka, to spustilo

Existuje přímočarý důvod, proč PDF končí v tomto stavu. Inkrementální ukládání připojuje aktualizované objekty s novými čísly objektů, čímž ponechává staré sloty v tabulce křížových odkazů směřující nikam. Editory, které přidávají titulní stránku, ji vloží s vysokým číslem objektu bez ohledu na její pozici v poli Kids. Některé generátory jednoduše zapisují stránky v pořadí výhodném pro streamování obsahu spíše než v logickém sledu stránek. Formát PDF od nich nevyžaduje, aby to dělaly jinak

Oprava: sledování pole Kids

Správným přístupem je sestavit PageArr procházením řetězce /Kids z kořene katalogu, nikoliv skenováním nepřímých objektů. Poté, co obě cesty parsování dokončí svůj počáteční průchod, krok následného zpracování vyřeší logické pořadí:

procedure THotPDF.ReorderPageArrByPagesTree;
var
  PagesObj  : THPDFDictionaryObject;
  KidsArray : THPDFArrayObject;
  NewPageArr: array of THPDFDictArrItem;
  I, J, PageIndex, KidsIndex: Integer;
  RefObj    : THPDFLink;
  PageObjNum: Integer;
  Found     : Boolean;
begin
  { Vyhledat kořenový slovník /Pages pomocí 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;
    { Kids, které nejsou stránkou (mezilehlé uzly /Pages), nevyvolají shodu; přeskočit }
  end;

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

Volání se umístí na konec každé cesty parsování, poté, co byly katalogizovány všechny objekty, ale předtím, než je obsloužena jakákoli operace se stránkou:

{ Tradiční cesta }
ListExtDictionary(THPDFDictionaryObject(IndirectObjects.Items[I]), FPageslink);
ReorderPageArrByPagesTree;
Break;

{ Moderní cesta (toky objektů) }
if TryParseModernPDF then
begin
  Result := ModernPageCount;
  ReorderPageArrByPagesTree;
  Exit;
end;

Krok přeřazení je O(n * m), kde n je počet Kids a m je aktuální délka PageArr, ale u jakéhokoli dokumentu s plochým stromem stránek (všechny listy v hloubce 1, což pokrývá drtivou většinu reálných PDF) jsou obě hodnoty stejné a náklady jsou zanedbatelné. Hluboce vnořené stromy stránek vyžadují rekurzivní průchod spíše než jednoúrovňový přístup, který je zde uveden; produkční implementace se tímto případem zabývá odděleně

Použití CopyPageFromDocument po opravě

S nasazeným ReorderPageArrByPagesTree fungují logické indexy stránek podle očekávání. Volání CopyPageFromDocument na vyšší úrovni převezme logický index založený na 0 a zkopíruje správnou stránku do cílového dokumentu:

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

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

    { Zkopírovat logickou stránku 0 (první stránka, kterou uživatel vidí) }
    Dest.CopyPageFromDocument(Source, 0, 0);

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

CopyPageFromDocument se interně dotazuje na pořadí stromu stránek spíše než aby se spoléhal na hrubý index PageArr, takže se chová správně i vůči dokumentům, kde se fyzické a logické pořadí liší. U dávkových operací přijímá InsertPagesFromDocument pole logických indexů a kopíruje je v jednom průchodu

Co to odhaluje o parsování PDF

Specifikace PDF je explicitní: logické pořadí stránek je definováno polem /Kids ve stromu stránek, nikoliv čísly objektů nebo bytovými offsety (ISO 32000-1 §7.7.3.2). Jakýkoli parser, který používá jiné uspořádání jako zkratku, přinese správné výsledky u většiny dokumentů, se kterými se setká, protože většina generátorů zapisuje stránky v přirozeném pořadí a přiřazuje sekvenční čísla objektů. Chyba se skrývá, dokud někdo nenačte PDF, které bylo inkrementálně upraveno, reorganizováno jiným nástrojem nebo vygenerováno softwarem, který zvolil jiné rozvržení

Testování pouze proti samostatně generovaným PDF tento druh problému zcela opomíjí. Oprava regrese pořadí stránek proto potřebuje korpus dokumentů z různých zdrojů: inkrementální ukládání, naskenované dokumenty s vloženými titulními stránkami, PDF vytvářená nástroji, které jinak linearizují nebo optimalizují graf objektů. Dokument, který spustil původní chybu, by měl zůstat v regresní sadě trvale

Stránka HotPDF Component pokrývá celé API pro operace se stránkami, včetně CopyPageFromDocument, InsertPagesFromDocument a MovePage