Bug Urutan Halaman PDF di HotPDF: Struktur Fisik vs Logis

Gejala muncul dalam utilitas penyalinan halaman yang dibangun di atas HotPDF Component: meminta halaman 1 dari dokumen tiga halaman secara konsisten menghasilkan halaman 2. Memeriksa logika pengindeksan tidak menemukan kesalahan apa pun. Panggilan menggunakan indeks logis berbasis 0, aritmatika sudah benar, kondisi batas sudah baik. Namun halaman yang salah selalu keluar

Bug tersebut sama sekali bukan di kode penyalinan. Bug tersebut ada di bagaimana HotPDF membangun array halaman internalnya saat memuat file

Dua pengurutan, satu sumber kebingungan

File PDF adalah kumpulan objek tidak langsung, masing-masing diidentifikasi oleh nomor objek. Struktur file tidak memaksakan kewajiban pada nomor-nomor tersebut untuk mencerminkan urutan membaca. Objek 1 dapat menyimpan halaman 2; objek 20 dapat menyimpan halaman 1. Yang sebenarnya mendefinisikan urutan membaca adalah pohon halaman: hirarki kamus /Pages yang array /Kids-nya mencantumkan referensi halaman dalam urutan yang harus ditampilkan viewer (ISO 32000-1 §7.7.3)

Dokumen yang memicu bug memiliki struktur pohon halaman ini:

{ 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

File tersebut secara kebetulan mencantumkan objek 1 dan objek 4 sebelum objek 20 dalam aliran byte. Parser mana pun yang mengulang melalui objek tidak langsung dalam urutan file dan memasukkannya ke dalam PageArr saat menemukan kamus bertipe halaman akan berakhir dengan objek 1 di indeks 0, objek 4 di indeks 1, dan objek 20 di indeks 2. Halaman logis 1 berada di PageArr[2]. Meminta indeks halaman 0 mengambil halaman logis 2

Itulah tepatnya yang dilakukan oleh kedua jalur parsing internal HotPDF. Jalur tradisional, digunakan untuk file PDF 1.3/1.4, dan jalur modern, digunakan untuk dokumen object-stream (PDF 1.5+), masing-masing membangun PageArr dengan berjalan melalui objek tidak langsung dalam urutan fisik file daripada mengikuti rantai /Kids

Mengkonfirmasi hipotesis

Sebelum menyentuh perbaikan apa pun, ketidakcocokan perlu dibuktikan bukan sekadar diasumsikan. Alat baris perintah qpdf membuatnya mudah:

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

Mengekstrak setiap halaman secara individual dan memeriksa ukuran file mengkonfirmasi pemetaannya: apa yang dihasilkan PageArr[0] adalah konten milik halaman logis 2, dan PageArr[2] menyimpan halaman logis 1. Pergeseran melingkar tersebut adalah bukti nyatanya. Ini juga menjelaskan mengapa masalah muncul di berbagai dokumen sumber yang berbeda: PDF mana pun di mana objek halaman memiliki nomor objek lebih rendah dari halaman logis sebelumnya akan memicunya

Ada alasan langsung mengapa PDF berakhir dalam kondisi ini. Penyimpanan inkremental menambahkan objek yang diperbarui dengan nomor objek baru, meninggalkan slot lama dalam tabel referensi silang yang tidak menunjuk ke mana pun. Editor yang menambahkan halaman sampul menyisipkannya dengan nomor objek tinggi terlepas dari posisinya dalam array Kids. Beberapa generator hanya menulis halaman dalam urutan yang nyaman untuk streaming konten daripada urutan halaman logis. Format PDF tidak mengharuskan mereka sebaliknya

Perbaikan: ikuti array Kids

Pendekatan yang benar adalah membangun PageArr dengan berjalan melalui rantai /Kids dari root catalog, bukan dengan memindai objek tidak langsung. Setelah kedua jalur parsing menyelesaikan jalan pertama mereka, langkah pasca-pemrosesan menyelesaikan urutan logis:

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;

Panggilannya ada di akhir setiap jalur parsing, setelah semua objek dikatalogkan tetapi sebelum operasi halaman apa pun dilayani:

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

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

Langkah pengurutan ulang adalah O(n * m) di mana n adalah jumlah Kids dan m adalah panjang PageArr saat ini, tetapi untuk dokumen mana pun dengan pohon halaman datar (semua daun pada kedalaman 1, yang mencakup sebagian besar PDF dunia nyata) keduanya bernilai sama dan biayanya dapat diabaikan. Pohon halaman yang bersarang dalam memerlukan jalan rekursif daripada pendekatan satu tingkat yang ditunjukkan di sini; implementasi produksi menangani kasus tersebut secara terpisah

Menggunakan CopyPageFromDocument setelah perbaikan

Dengan ReorderPageArrByPagesTree yang terpasang, indeks halaman logis bekerja seperti yang diharapkan. CopyPageFromDocument tingkat lebih tinggi mengambil indeks logis berbasis 0 dan menyalin halaman yang benar ke dalam dokumen tujuan:

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 secara internal mengkueri urutan pohon halaman daripada mengandalkan indeks PageArr mentah, sehingga berperilaku benar bahkan terhadap dokumen di mana urutan fisik dan logis berbeda. Untuk operasi batch, InsertPagesFromDocument menerima array indeks logis dan menyalinnya dalam satu kali jalan

Apa yang terungkap tentang parsing PDF

Spesifikasi PDF jelas: urutan halaman logis didefinisikan oleh array /Kids dari pohon halaman, bukan oleh nomor objek atau offset byte (ISO 32000-1 §7.7.3.2). Parser mana pun yang menggunakan pengurutan berbeda sebagai pintasan akan menghasilkan hasil yang benar pada sebagian besar dokumen yang dilihatnya, karena sebagian besar generator menulis halaman dalam urutan alami dan menetapkan nomor objek berurutan. Bug tersebut tersembunyi sampai seseorang memuat PDF yang diedit secara inkremental, diatur ulang oleh alat lain, atau dihasilkan oleh perangkat lunak yang memilih tata letak berbeda

Pengujian hanya terhadap PDF yang dihasilkan sendiri melewatkan kelas masalah ini sepenuhnya. Perbaikan untuk regresi pengurutan halaman oleh karena itu membutuhkan kumpulan dokumen dari berbagai sumber: penyimpanan inkremental, dokumen yang dipindai dengan halaman sampul yang disisipkan, PDF yang dihasilkan oleh alat yang meliniearisasi atau mengoptimalkan grafik objek secara berbeda. Dokumen yang memicu bug asli harus tetap ada dalam suite regresi secara permanen

Halaman HotPDF Component mencakup API lengkap untuk operasi halaman, termasuk CopyPageFromDocument, InsertPagesFromDocument, dan MovePage