บั๊กการเรียงหน้า PDF ใน HotPDF: โครงสร้างทางกายภาพและเชิงตรรกะ

อาการนี้พบในยูทิลิตีคัดลอกหน้าที่สร้างขึ้นบน HotPDF Component เมื่อเรียกขอหน้า 1 ของเอกสารที่มี 3 หน้ากลับได้หน้า 2 ออกมาเสมอ การตรวจสอบตรรกะการทำอินเด็กซ์ไม่พบความผิดปกติใดๆ การเรียกใช้งานใช้อินเด็กซ์เชิงตรรกะที่เริ่มต้นด้วย 0 การคำนวณคณิตศาสตร์ถูกต้อง และเงื่อนไขขอบเขตก็ทำงานได้ดี แต่ก็ยังได้หน้าที่ผิดออกมาทุกครั้ง

บั๊กไม่ได้อยู่ในโค้ดคัดลอกเลย แต่อยู่ที่วิธีที่ HotPDF สร้างอาร์เรย์หน้าภายในขณะโหลดไฟล์

สองการจัดเรียง หนึ่งสาเหตุของความสับสน

ไฟล์ PDF คือชุดของออบเจ็กต์ทางอ้อม ซึ่งแต่ละตัวระบุด้วยหมายเลขออบเจ็กต์ โครงสร้างไฟล์ไม่ได้บังคับให้หมายเลขเหล่านี้สอดคล้องกับลำดับการอ่าน ออบเจ็กต์ 1 อาจเก็บหน้า 2 ส่วนออบเจ็กต์ 20 อาจเก็บหน้า 1 สิ่งที่กำหนดลำดับการอ่านจริงๆ คือโครงสร้างต้นไม้หน้าเว็บ ซึ่งเป็นลำดับชั้นของดิกชันนารี /Pages ที่อาร์เรย์ /Kids จะระบุการอ้างอิงหน้าในลำดับที่โปรแกรมดูควรแสดงผล (ISO 32000-1 §7.7.3)

เอกสารที่ทำให้เกิดบั๊กมีโครงสร้างต้นไม้หน้าเว็บดังนี้:

{ 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

ไฟล์นี้บังเอิญแสดงออบเจ็กต์ 1 และออบเจ็กต์ 4 ก่อนออบเจ็กต์ 20 ในสตรีมไบต์ พาร์สเซอร์ใดก็ตามที่วนลูปออบเจ็กต์ทางอ้อมตามลำดับไฟล์และบันทึกลงใน PageArr เมื่อพบดิกชันนารีประเภทหน้า จะลงเอยด้วยออบเจ็กต์ 1 ที่อินเด็กซ์ 0 ออบเจ็กต์ 4 ที่อินเด็กซ์ 1 และออบเจ็กต์ 20 ที่อินเด็กซ์ 2 หน้าเชิงตรรกะ 1 จะอยู่ที่ PageArr[2] การขอหน้าอินเด็กซ์ 0 จึงไปดึงหน้าเชิงตรรกะ 2 มาแทน

นั่นคือสิ่งที่เส้นทางการพาร์สภายในของ HotPDF ทั้งสองแบบกำลังทำอยู่ เส้นทางดั้งเดิมซึ่งใช้สำหรับไฟล์ PDF 1.3/1.4 และเส้นทางสมัยใหม่ที่ใช้สำหรับเอกสารสตรีมออบเจ็กต์ (PDF 1.5+) ต่างสร้าง PageArr โดยการเดินตามออบเจ็กต์ทางอ้อมในลำดับไฟล์ทางกายภาพแทนที่จะตามสายเชื่อม /Kids

ยืนยันสมมติฐาน

ก่อนที่จะแก้ไขใดๆ ต้องพิสูจน์ความไม่สอดคล้องกันนี้แทนที่จะทึกทักเอาเอง เครื่องมือบรรทัดคำสั่ง qpdf ทำให้เรื่องนี้ตรงไปตรงมา:

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

การดึงแต่ละหน้าออกมาทีละหน้าและตรวจสอบขนาดไฟล์ช่วยยืนยันการแมป: สิ่งที่ PageArr[0] สร้างขึ้นคือเนื้อหาที่เป็นของหน้าเชิงตรรกะ 2 และ PageArr[2] เก็บหน้าเชิงตรรกะ 1 การเลื่อนแบบวงกลมนี้เป็นหลักฐานชิ้นสำคัญ นอกจากนี้ยังอธิบายได้ว่าทำไมปัญหาจึงปรากฏในเอกสารต้นทางที่แตกต่างกันหลายฉบับ: PDF ใดๆ ที่ออบเจ็กต์หน้าบังเอิญมีหมายเลขออบเจ็กต์ต่ำกว่าหน้าเชิงตรรกะก่อนหน้าก็จะทำให้เกิดบั๊กนี้

มีเหตุผลตรงไปตรงมาที่ทำให้ PDF อยู่ในสถานะนี้ การบันทึกแบบเพิ่มทีละส่วนจะต่อท้ายออบเจ็กต์ที่อัปเดตด้วยหมายเลขออบเจ็กต์ใหม่ ปล่อยให้ช่องเดิมในตารางการอ้างอิงข้ามชี้ไปที่ความว่างเปล่า โปรแกรมแก้ไขที่เพิ่มหน้าปกจะแทรกด้วยหมายเลขออบเจ็กต์สูงเสมอไม่ว่าจะอยู่ที่ตำแหน่งใดในอาร์เรย์ Kids เครื่องสร้างบางตัวเพียงแค่เขียนหน้าในลำดับที่สะดวกต่อการสตรีมเนื้อหามากกว่าลำดับหน้าเชิงตรรกะ รูปแบบ PDF ไม่ได้บังคับให้ต้องทำเป็นอย่างอื่น

การแก้ไข: ตามอาร์เรย์ Kids

แนวทางที่ถูกต้องคือการสร้าง PageArr โดยเดินตามสายเชื่อม /Kids จากแคตตาล็อกราก ไม่ใช่สแกนออบเจ็กต์ทางอ้อม หลังจากทั้งสองเส้นทางการพาร์สผ่านรอบแรกเสร็จสิ้น ขั้นตอนหลังการประมวลผลจะจัดเรียงลำดับเชิงตรรกะใหม่:

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;

การเรียกใช้งานนี้จะอยู่ที่ท้ายของแต่ละเส้นทางการพาร์ส หลังจากจัดหมวดหมู่ออบเจ็กต์ทั้งหมดแล้วแต่ก่อนที่การทำงานของหน้าใดๆ จะถูกเรียกใช้:

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

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

ขั้นตอนการเรียงลำดับใหม่นี้ทำงานแบบ O(n * m) โดยที่ n คือจำนวน Kids และ m คือความยาว PageArr ปัจจุบัน แต่สำหรับเอกสารใดๆ ที่มีโครงสร้างต้นไม้หน้าเว็บแบบแบน (ใบทั้งหมดอยู่ที่ความลึก 1 ซึ่งครอบคลุม PDF ในโลกแห่งความเป็นจริงส่วนใหญ่) ทั้งสองค่านี้จะมีค่าเท่ากันและค่าใช้จ่ายในการประมวลผลก็น้อยมาก โครงสร้างต้นไม้หน้าเว็บที่ซ้อนกันลึกๆ จะต้องใช้การเดินซ้ำ (recursive) แทนที่จะเป็นวิธีระดับเดียวแบบที่แสดงไว้ที่นี่ การนำไปใช้งานจริงจะจัดการกรณีนั้นแยกต่างหาก

การใช้ CopyPageFromDocument หลังการแก้ไข

เมื่อมี ReorderPageArrByPagesTree อินเด็กซ์หน้าเชิงตรรกะก็จะทำงานตามที่คาดไว้ ฟังก์ชันระดับสูงกว่า CopyPageFromDocument จะรับอินเด็กซ์เชิงตรรกะที่เริ่มต้นด้วย 0 และคัดลอกหน้าที่ถูกต้องไปยังเอกสารปลายทาง:

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 จะคิวรีลำดับของโครงสร้างต้นไม้หน้าเว็บภายในแทนที่จะพึ่งพาอินเด็กซ์ PageArr ดิบ ดังนั้นมันจึงทำงานได้ถูกต้องแม้กับเอกสารที่ลำดับทางกายภาพและเชิงตรรกะไม่ตรงกัน สำหรับการดำเนินการแบบกลุ่ม InsertPagesFromDocument จะรับอาร์เรย์ของอินเด็กซ์เชิงตรรกะและคัดลอกในรวดเดียว

สิ่งที่เผยให้เห็นเกี่ยวกับการพาร์ส PDF

ข้อกำหนดของ PDF นั้นชัดเจน: ลำดับหน้าเชิงตรรกะถูกกำหนดโดยอาร์เรย์ /Kids ของโครงสร้างต้นไม้หน้าเว็บ ไม่ใช่โดยหมายเลขออบเจ็กต์หรือออฟเซ็ตไบต์ (ISO 32000-1 §7.7.3.2) พาร์สเซอร์ใดก็ตามที่ใช้การจัดเรียงอื่นเป็นทางลัดจะสร้างผลลัพธ์ที่ถูกต้องกับเอกสารส่วนใหญ่ที่พบ เพราะเครื่องสร้างส่วนใหญ่จะเขียนหน้าตามลำดับธรรมชาติและกำหนดหมายเลขออบเจ็กต์ตามลำดับ บั๊กจะซ่อนอยู่จนกว่าจะมีคนโหลด PDF ที่ถูกแก้ไขทีละส่วน ถูกจัดระเบียบใหม่โดยเครื่องมืออื่น หรือสร้างโดยซอฟต์แวร์ที่เลือกเลย์เอาต์ที่แตกต่างออกไป

การทดสอบเฉพาะกับ PDF ที่สร้างขึ้นเองจะมองข้ามปัญหานี้ไปโดยสิ้นเชิง ดังนั้นการแก้ไขปัญหาระบบจัดเรียงหน้าจึงต้องการคลังเอกสารจากหลากหลายแหล่ง: การบันทึกแบบเพิ่มทีละส่วน เอกสารที่สแกนพร้อมแทรกหน้าปก PDF ที่ผลิตโดยเครื่องมือที่สร้างเชิงเส้น (linearize) หรือเพิ่มประสิทธิภาพกราฟออบเจ็กต์ที่ต่างออกไป เอกสารที่ทำให้เกิดบั๊กดั้งเดิมควรอยู่ในชุดทดสอบการถดถอยอย่างถาวร

หน้า HotPDF Component ครอบคลุม API ทั้งหมดสำหรับการดำเนินการเกี่ยวกับหน้า รวมถึง CopyPageFromDocument, InsertPagesFromDocument และ MovePage