สร้างตาราง Xref ของ PDF ที่เสียหายขึ้นใหม่ใน Delphi

เมื่อ cross-reference table ของ PDF ใช้งานไม่ได้แล้ว วิธีแก้คือเพิกเฉยต่อมันไปเลยแล้วสร้างขึ้นใหม่จากเนื้อหาไฟล์ PDFlibPas Delphi PDF Library ทำแบบนี้ด้วยการสแกน token รอบเดียวที่บันทึก indirect object header ที่แท้จริงทุกตัวที่พบ จากนั้นกู้คืน trailer dictionary แล้วส่งตารางที่สร้างขึ้นใหม่ให้ loader ปกติทำงานต่อ

อะไรพังก่อนเมื่อ PDF เสียหาย

Cross-reference table เป็นส่วนที่เปราะบางที่สุดของ PDF เพราะเป็นส่วนเดียวที่เก็บ byte offset แบบสัมบูรณ์ ISO 32000-1 §7.5.4 กำหนดให้ entry เหล่านั้นเป็น offset สิบหลักนับจากจุดเริ่มต้นของไฟล์ และ §7.5.5 วางคีย์เวิร์ด startxref ไว้ใกล้ท้ายไฟล์ชี้กลับไปที่ตัวตารางเอง ตัวเลขทุกตัวนั้นจะเป็นโมฆะทันทีที่มีการแก้ไขใดที่ทำให้ byte เลื่อนตำแหน่ง เซสชัน FTP ที่รันในโหมดข้อความแล้วแปลง CRLF การดาวน์โหลดที่ขาดหาย เซกเตอร์ที่เสียบน shared drive เครื่องมือ batch ที่ต่อท้ายไฟล์โดยไม่เขียน incremental update ให้ถูกต้อง ทั้งหมดนี้ทิ้งข้อมูลอ็อบเจกต์ไว้ให้อ่านได้อย่างสมบูรณ์ แต่ทำให้ index ชี้ไปยังขยะ

นี่คือเหตุผลที่ไดอะล็อก "the file is damaged and is being repaired" พบเห็นได้บ่อยขนาดนี้ ตัว byte เกือบทุกครั้งยังคงอยู่ครบ สิ่งที่หายไปคือแผนที่ต่างหาก การสร้างใหม่จึงไม่ใช่การกู้คืนข้อมูลที่สูญหายทางนิติวิทยาศาสตร์ แต่เป็นการสร้าง index ขึ้นใหม่ซึ่งสามารถอนุมานได้จากเนื้อหาไฟล์ และมันสำเร็จบ่อยกว่าที่ผู้ใช้คาดคิดมาก เพราะเนื้อหาที่มีต้นทุนสูงอย่าง page tree ฟอนต์ และภาพ ไม่ถูกแตะต้องเลย

ทำไมการสแกนหา N 0 obj ถึงพบผลลัพธ์ปลอม

การสร้างใหม่แบบไร้เดียงสาจะค้นหา byte ดิบเพื่อหารูปแบบ "จำนวนเต็ม, จำนวนเต็ม, obj" แล้วบันทึกทุกครั้งที่เจอ มันเจอมากเกินไป PDF เป็นรูปแบบ container และมีสามส่วนของไฟล์ที่ไวยากรณ์อ็อบเจกต์มองไม่เห็นทะลุเข้าไปได้ คือ comment (§7.2), string (§7.3.4) และ stream data (§7.3.8) ส่วนไหนก็ตามอาจมี byte ที่อ่านออกมาเหมือน object header เป๊ะ ๆ ทั้งที่ไม่ใช่ object header เลย caption ใน literal string ที่หลงเหลืออยู่ comment สำหรับ debug ที่ค้างไว้ หรือข้อมูล Flate หรือ DCT สองเมกะไบต์ ล้วนสามารถสร้างสิ่งที่หน้าตาเหมือน 99 0 obj ได้อย่างง่ายดาย

const
  Trap: AnsiString =
    '4 0 obj'#10 +
    '(a caption that mentions 88 0 obj)'#10 +   // literal string, not an object
    'endobj'#10 +
    '% 77 0 obj left over from a debug dump'#10 +  // comment, not an object
    '5 0 obj'#10 +
    '<< /Length 2097152 >>'#10 +
    'stream'#10 +
    { two MiB of compressed bytes that contain the byte sequence
      99 0 obj and, further along, a complete endstream }
    'endstream'#10 +
    'endobj'#10;

ผลลัพธ์ปลอมทุกรายการมีต้นทุนสองต่อ มันปนเปื้อนตารางที่สร้างขึ้นใหม่ด้วยหมายเลขอ็อบเจกต์ที่ไม่มีอยู่จริง และมันสามารถบดบังอ็อบเจกต์จริงที่มีหมายเลขเดียวกันซึ่งปรากฏทีหลังในไฟล์ได้ด้วย PDFlibPas จึงไม่ทำ pattern-match เลยแม้แต่น้อย มันทำการ tokenise ซึ่งหมายความว่ามันรู้เสมอว่า byte ใต้ cursor เป็นโค้ดหรือ payload และ payload จะถูกข้ามไปโดยไม่ถูกตีความเลย

State machine รอบเดียวบนบล็อกขนาด 64 KiB

PDFlibPas สแกนทั้งไฟล์เพียงครั้งเดียว เป็นบล็อกขนาด 64 KiB โดยใช้ state machine ที่สร้างจากกฎ token ของ ISO 32000-1 §7.2 และไวยากรณ์ indirect object ของ §7.3.10 token หนึ่งจะจบลงที่ white space หรือที่ตัวอักษร delimiter ตัวใดตัวหนึ่ง และ object header จะถูกบันทึกก็ต่อเมื่อพบลำดับที่สมบูรณ์ของหมายเลขอ็อบเจกต์ที่เป็นบวก หมายเลข generation ที่ไม่เป็นลบ และคีย์เวิร์ด obj เปล่า ๆ ครบทั้งหมดแล้วเท่านั้น offset ที่บันทึกไว้คือจุดเริ่มต้นของ token หมายเลขอ็อบเจกต์ ซึ่งเป็นสิ่งที่ cross-reference entry ต้องชี้ไปหา ไม่ใช่ตำแหน่งของคีย์เวิร์ด obj

function RebuildIsWhiteSpace(Value: Byte): Boolean;
begin
  Result := (Value = 0) or (Value = 9) or (Value = 10) or
            (Value = 12) or (Value = 13) or (Value = 32);
end;

function RebuildIsDelimiter(Value: Byte): Boolean;
begin
  Result := (Value = Ord('(')) or (Value = Ord(')')) or
            (Value = Ord('<')) or (Value = Ord('>')) or
            (Value = Ord('[')) or (Value = Ord(']')) or
            (Value = Ord('{')) or (Value = Ord('}')) or
            (Value = Ord('/')) or (Value = Ord('%'));
end;

รายละเอียดสำคัญคือ token state และ string state จะอยู่รอดข้ามขอบเขตบล็อกได้ header ที่คาบเกี่ยวเส้นแบ่ง 65536 byte ก็ยังถูกจดจำได้ เพราะ token ที่ยังไม่สมบูรณ์ คู่จำนวนเต็มที่ค้างอยู่ และ flag การอยู่ใน string ทั้งหมดจะถูกส่งต่อไปยังบล็อกถัดไป buffer มีขนาดตายตัว คือ 64 KiB สำหรับการสแกน และ 32 byte สำหรับ token ที่ยาวที่สุดที่เป็นไปได้ อาร์เรย์เดียวที่โตขึ้นตามขนาดไฟล์คือรายการหมายเลขอ็อบเจกต์ หมายเลข generation และ offset แบบ 64 บิต ซึ่งเป็นสัดส่วนกับจำนวนอ็อบเจกต์จริงมากกว่าขนาดไฟล์ ในทางปฏิบัติ การสแกนนี้ทำ sequential read และ seek ชัดเจนอย่างมากสองครั้งตลอดทั้งเอกสาร ซึ่งเป็นสิ่งที่ทำให้มันใช้งานได้จริงกับไฟล์ขนาดหลายร้อยเมกะไบต์ที่กล่าวถึงใน บทความเรื่อง direct access merge และ split

ทำไมจึงไว้ใจไม่ได้ว่า stream จะจบที่ endstream

เพราะข้อมูล stream คือ byte ใด ๆ ก็ได้ และ byte ใด ๆ ก็สามารถสะกดคำว่า endstream ขึ้นมาโดยบังเอิญได้ stream ที่เริ่มหลังคีย์เวิร์ด stream ต้องถูกข้ามไปเป็นข้อมูลทึบแสงจนกว่าจะจบลงจริง ๆ แต่การพบคีย์เวิร์ดปิดครั้งแรกเป็นเพียงตัวเลือกที่เป็นไปได้เท่านั้น PDFlibPas แก้ปัญหานี้ด้วยการเรียกร้องหลักฐานยืนยัน token endstream จะถูกยอมรับว่าเป็นจุดจบจริงของ stream ก็ต่อเมื่อ token ถัดไปที่ไม่ใช่ white space เป็น endobj เดี่ยว ๆ ซึ่งเป็นลำดับที่ §7.3.8 กำหนดไว้รอบ stream object การพบโดยบังเอิญภายในข้อมูลที่บีบอัดแทบจะไม่มีการตามมาแบบนั้นเลย ดังนั้น scanner จึงยังคงอยู่ภายใน stream ต่อไป ยังมีกฎเล็ก ๆ อีกสองข้อที่สำคัญไม่แพ้กัน คีย์เวิร์ด stream จะเข้าสู่ stream state ก็ต่อเมื่อมันเป็นคีย์เวิร์ดเปล่า ๆ เท่านั้น ดังนั้น name object อย่าง /stream ใน dictionary จึงไม่มีวันกระตุ้นมัน และ token obj หรือ trailer จะถูกยอมรับก็ต่อเมื่อ token นั้นไม่ล้นเกิน 32 byte และไม่ได้ขึ้นต้นด้วยเครื่องหมาย solidus หากไม่มีสองด่านนี้ resource dictionary ที่มีชื่อคีย์ผิดพลาดก็เพียงพอที่จะทำให้การสแกนหลุดราง ซึ่งเป็นประเภทของ input ที่ประสงค์ร้ายเดียวกับที่กล่าวถึงในบันทึกเรื่อง การ parse PDF ที่ไม่น่าเชื่อถือให้ปลอดภัย

การหาจุดจบที่แท้จริงของ trailer dictionary

การกู้คืนอ็อบเจกต์เป็นแค่ครึ่งหนึ่งของงาน เพราะ loader ยังต้องการ trailer เพื่อหา /Root PDFlibPas จดจำตำแหน่งคีย์เวิร์ด trailer 64 ตำแหน่งล่าสุดที่พบระหว่างการสแกน แล้ววนตรวจสอบย้อนหลัง เริ่มจากล่าสุดก่อน เพื่อให้ trailer ที่ใช้งานได้ล่าสุดชนะ และคีย์เวิร์ดหลงทางที่ไม่มี dictionary ตามมาก็จะล้มเหลวในการตรวจสอบและตกไปให้ตัวเลือกก่อนหน้าแทน แต่ละตัวเลือกจะถูกอ่านด้วยเพดาน 1 MiB และจุดจบของ dictionary หาได้ด้วยการติดตามความลึกของ << และ >> ที่ซ้อนกัน พร้อมกับ escape ของ literal string, hexadecimal string และ comment

// A naive reader that stops at the first '>>' truncates this trailer,
// and a fixed 2048-byte window can cut it in half on a large one
'trailer'#10 +
'<< /Size 5 /Root 1 0 R' +
'   /Custom << /Text (value >> preserved) >> >>'#10

การติดตามความลึกไม่ใช่เรื่องวิชาการเฉย ๆ trailer ที่ถูกตัดทอนจนสูญเสีย /Encrypt จะเปลี่ยนเอกสารเข้ารหัสที่กู้คืนได้ให้กลายเป็นเปิดไม่ได้เลย และการสูญเสีย /Info หรือ sub-dictionary ที่กำหนดเองจะทิ้ง metadata ที่ระบบปลายทางอาจต้องพึ่งพาอย่างเงียบ ๆ ถ้าไฟล์ถูกเข้ารหัส trailer ที่กู้คืนมาคือสิ่งที่ทำให้ credential path ปกติทำงานได้ และ retry semantics ก็เป็นชุดเดียวกับที่อธิบายไว้ใน บทความเรื่องการโหลดเอกสารที่เข้ารหัส

อะไรบ้างที่การสร้างใหม่คืนให้คุณไม่ได้

การสร้างใหม่คือความพยายามที่ดีที่สุดเท่าที่ทำได้ และการซื่อสัตย์เกี่ยวกับขีดจำกัดของมันก็เป็นส่วนหนึ่งของการนำไปใช้งานจริง มีสามกรณีที่ล้มเหลวโดยสิ้นเชิง อ็อบเจกต์ที่บรรจุอยู่ภายใน object stream (§7.5.7) จะมองไม่เห็นทีละตัวจากการสแกน byte ดังนั้นถ้า container รอดแต่ cross-reference stream ของมัน (§7.5.8) ไม่รอด อ็อบเจกต์ที่มันเก็บไว้ก็จะไม่ถูกจัดทำ index โดยการสร้างใหม่ ไฟล์ที่เนื้อหาถูกทำลายจริง ๆ ไม่ใช่แค่ทำ index ผิด จะสร้าง header ที่เนื้อหาข้างในไม่สามารถ parse ได้อีกต่อไป และไฟล์ที่ไม่มีคีย์เวิร์ด trailer ที่กู้คืนได้เลยและไม่มี catalog ที่อ่านได้ ก็ไม่มีอะไรให้ยึดโยง document tree ไว้เลย ไม่ว่าจะพบ object header กี่ตัวก็ตาม

หมายเลขอ็อบเจกต์ซ้ำเป็นกรณีกลาง ๆ ที่น่าสนใจ ไฟล์ที่ถูก update แบบ incremental มี generation ของหมายเลขอ็อบเจกต์เดียวกันหลายชุดอย่างถูกต้องตามกฎ และ cross-reference chain ที่รอดอยู่คือบันทึกเดียวว่าตัวไหนคือตัวปัจจุบัน การสร้างใหม่ไม่มี chain นั้น จึงบันทึก header ทุกตัวที่พบตามลำดับในไฟล์แล้วค่อยแก้ปัญหาด้วยหมายเลขอ็อบเจกต์ทีหลัง โดยปกติ revision หลังสุดจะชนะ ซึ่งมักจะถูกต้อง แต่เอกสารที่ถูก update แล้วถูกย้อนกลับบางส่วนอาจกลับมาแตกต่างเล็กน้อยจากสิ่งที่ xref ดั้งเดิมอธิบายไว้ ไฟล์แบบ linearised ก็มีข้อควรระวังแบบเดียวกันจากอีกด้านหนึ่ง เพราะ layout หน้าแรกและ hint table จะไม่มีความหมายอีกต่อไปเมื่อ index ถูกสร้างใหม่ ดังนั้นไฟล์ที่ถูกซ่อมแล้วควรถูกปฏิบัติเหมือนเป็นเอกสารธรรมดาที่ไม่ linearised

var
  Pdf: TPDFlib;
begin
  Pdf := TPDFlib.Create;
  try
    if Pdf.LoadFromFile('truncated-invoice.pdf', '') = 1 then
    begin
      if Pdf.GetDocumentRepaired = 1 then
        LogWarning('xref was unusable; the table was reconstructed');
      if Pdf.PageCount > 0 then
        Pdf.SaveToFile('recovered-invoice.pdf');   // writes a clean xref
    end;
  finally
    Pdf.Free;
  end;
end;

Fallback นี้เป็นแบบอัตโนมัติ PDFlibPas จะรันการสแกนแบบ raw ทุกครั้งที่ cross-reference chain อ่านไม่ได้ และรันด้วยเมื่อ entry ที่ใช้งานอยู่ทุกตัวอ้างว่า offset เป็นศูนย์ ซึ่งเป็นลายเซ็นของตารางที่ถูกเขียนไว้แต่ไม่เคยถูกเติมข้อมูลจริง GetDocumentRepaired คืนค่า 1 เมื่อ path นั้นทำงาน และควร log ไว้แทนที่จะเพิกเฉย เพราะเอกสารที่โหลดผ่านการสร้างใหม่ควรถูกเซฟใหม่เป็นไฟล์สะอาดแทนที่จะปล่อยไว้ใน pipeline เหมือนไม่มีอะไรเกิดขึ้น การเซฟมันจะเขียน cross-reference table ใหม่ที่สดและสอดคล้องกัน ซึ่งเป็นวิธีแก้ปัญหาที่ถูกที่สุดสำหรับผู้บริโภคปลายทางทุกราย

Path การสร้างใหม่ flag GetDocumentRepaired และ streaming loader ที่แสดงไว้ที่นี่เป็นส่วนหนึ่งของ PDFlibPas Delphi PDF Library ควบคู่ไปกับ API สำหรับ parsing, rendering และ signing ที่กล่าวถึงในที่อื่นของบล็อกนี้