การ Decode Predictor และ LZWDecode ของ PDF ใน Delphi ด้วย HotPDF

Stream ที่ทำเครื่องหมาย /Predictor 12 ไว้ไม่ได้หมายความว่าทุกแถวใช้ PNG filter 2 HotPDF ซึ่งเป็น native VCL PDF component สำหรับ Delphi และ C++Builder ปฏิบัติต่อค่า predictor 10 ถึง 15 เป็นตระกูลเดียวกัน คือ filter tag ที่แท้จริง ตั้งแต่ 0 ถึง 4 เป็น byte แรกของแต่ละแถวที่เข้ารหัสไว้ และ HPDFDecodePredictor อ่านและตรวจสอบ tag นั้นทีละแถว ความแตกต่างนี้คือรูปแบบของบั๊กเกือบทุกตัวในมุมนี้ของ PDF เพราะไม่มีอะไร raise ขึ้นเมื่อคุณทำผิด filter chain ทำงานไปเรื่อย ๆ raster มีขนาดตามที่คุณคาดไว้ และภาพก็ออกมาเป็น static แนวทแยงหรือ gradient ที่เพี้ยนมากขึ้นทุก scanline ตัวเลขห้าตัวใน /DecodeParms (ISO 32000-1 §7.4.4) ส่วนใหญ่เปลี่ยนความหมายของ byte มากกว่าความยาวของมัน ดังนั้นค่าที่ผิดจึงสร้างขยะที่ดูสมเหตุสมผลแทนที่จะสร้าง error

ทำไม /Predictor 12 ไม่ได้หมายถึง PNG filter 2 บนทุกแถว

เพราะหมายเลข predictor บอกแค่ว่า "กำลังใช้ PNG prediction อยู่" ไม่ได้บอกว่าเป็น filter ตัวไหน ตัวเข้ารหัส PNG เลือก filter ต่อ scanline หนึ่งเส้น และ filter ของ PDF ก็รับสืบทอดมาแบบนั้น ดังนั้นค่า predictor 10 (None), 11 (Sub), 12 (Up), 13 (Average), 14 (Paeth) และ 15 (Optimum) ทั้งหมด decode เหมือนกัน คือ tag byte ที่นำหน้าของแต่ละแถวคือสิ่งที่ตัว decode ต้องเชื่อฟัง ผลที่ตามมาด้าน layout สำคัญพอ ๆ กับความหมาย แต่ละแถวที่เข้ารหัสไว้มีความยาว 1 + RowBytes byte ดังนั้น input จึงมากกว่า output พอดีเท่ากับจำนวนแถว และ stream ที่ความยาวไม่ใช่จำนวนเต็มของ RowBytes + 1 จึงถูกตัดทอนตามนิยาม HotPDF ตรวจสอบขอบเขตนั้นก่อนแตะ byte ใด ๆ ปฏิเสธ tag ใดที่มากกว่า 4 ด้วยข้อความ Invalid PNG predictor row tag และอ่านแถวก่อนหน้าออกมาจาก output buffer ตัวเดียวโดยตรง แทนที่จะสร้าง row array แบบสองมิติขึ้นมา filter 1 และ 3 ย้อนกลับไป BytesPerPixel ภายในแถวปัจจุบัน filter 2 อ่านตรงขึ้นไปด้านบน filter 4 รัน Paeth choice บนซ้าย บน และบนซ้าย และทั้งสี่ทำงานบน output ที่ถูกสร้างขึ้นใหม่แล้วเท่านั้น นี่คือเหตุผลที่แถวด้านบนต้องเป็นแถวที่ decode แล้ว ไม่ใช่ input ที่ยังผ่าน filter อยู่

uses
  HPDFPredictor;

var
  Filtered, Raster: AnsiString;
  ErrorText: string;
begin
  // /DecodeParms << /Predictor 12 /Colors 3 /BitsPerComponent 8 /Columns 1024 >>
  if HPDFTryDecodePredictor(Filtered, 12, 3, 8, 1024,
       Int64(1024) * 3 * 8192, Raster, ErrorText) then
    ConsumeRaster(Raster)
  else
    LogStreamDefect('predictor', ErrorText);   // no exception, no partial raster
end;

อาร์กิวเมนต์ MaxOutputBytes ไม่ใช่ของตกแต่ง ขั้นตอน predictor คือขั้นตอนคลายการบีบอัดที่แฝงตัวมา และค่า /Columns ที่ประสงค์ร้ายหรือแค่พังก็สามารถเปลี่ยน input ไม่กี่กิโลไบต์ให้กลายเป็นคำขอจัดสรรหน่วยความจำหลายกิกะไบต์ได้ HotPDF คำนวณบิตต่อแถว byte ต่อแถว และขนาด raster รวมเป็น Int64 ก่อน ปฏิเสธเรขาคณิตที่ overflow และเคารพเพดานที่ผู้เรียกกำหนดมาให้ ส่งขอบเขตจริงที่ได้มาจาก image dictionary เข้าไป แล้วโหมดความล้มเหลวก็จะกลายเป็นข้อความ log แทนที่จะเป็นไดอะล็อก out-of-memory บนเครื่องของลูกค้า

ทำไม TIFF Predictor 2 ถึงทำให้ภาพ 4 บิตเสียหาย

เพราะ Predictor 2 คือการหาผลต่างแนวนอนต่อตัวอย่าง ไม่ใช่ต่อ byte และที่ 1, 2 หรือ 4 บิตต่อคอมโพเนนต์ ตัวอย่างหลายตัวใช้ byte ร่วมกัน implementation ทั่วไปบวก byte N-Colors เข้ากับ byte N ซึ่งบังเอิญถูกต้องที่ 8 บิตต่อคอมโพเนนต์ แต่ผิดอย่างเงียบ ๆ ในทุกที่อื่น การสแกน RGB 8 บิต decode ได้สมบูรณ์แบบ แล้วโค้ดเดียวกันนั้นก็ทำลายภาพแบบ indexed 4 บิตทันทีที่มันปรากฏขึ้นในการใช้งานจริงเป็นครั้งแรก

เลขคณิตที่ถูกต้องทำงานภายในฟิลด์บิต HotPDF ไล่ตัวอย่างจาก index Colors ถึง Colors * Columns - 1 ดึงตัวอย่างและตัวข้างเคียงซ้ายที่เป็นคอมโพเนนต์เดียวกันออกมาด้วย mask ของ (1 shl BitsPerComponent) - 1 ที่ shift ที่เหมาะสม บวกกัน modulo mask นั้น แล้วเขียนผลลัพธ์กลับโดยไม่รบกวนตัวอย่างอื่นที่บรรจุอยู่ใน byte เดียวกัน ส่วนหางก็สำคัญเช่นกัน แถวหนึ่งถูกเติมให้พอดีขอบเขต byte ดังนั้นบิต padding หลังตัวอย่างสุดท้ายต้องรอดโดยไม่ถูกแตะต้อง แทนที่จะถูกพับเข้าไปในการคำนวณ ที่ 16 บิตต่อคอมโพเนนต์ แต่ละตัวอย่างเป็นคู่ byte แบบ big-endian และการบวกจะวนที่ $FFFF ข้ามทั้งคู่ แทนที่จะทดเลขระหว่าง byte แยกกัน ที่ 8 บิต การวนซ้ำแบบ byte ธรรมดาถูกต้องอยู่แล้ว โดยก้าวทีละ Colors เพื่อให้สีแดงสะสมกับสีแดง และ alpha กับ alpha ในทุกรูปแบบ พิกเซลแรกของแถวเป็นค่าตามตัวอักษรเสมอ ไม่ใช่ผลต่าง และการวนซ้ำเริ่มใหม่ทุกขอบเขตแถว การทำนายแบบ TIFF ไม่เคยอ่านแถวด้านบนเลย นี่คือความแตกต่างทั้งหมดระหว่างมันกับตระกูล PNG

EarlyChange ควบคุมอะไรจริง ๆ ใน LZWDecode

มันควบคุมว่าตัวอ่านจะขยาย code size ขึ้นทีละหนึ่งบิตเมื่อไร และการเหลื่อม code ไปหนึ่งตัวก็ทำให้ทุกอย่างที่ตามมาเสียหาย HotPDF แสดงกฎนี้เป็น invariant ตัวเดียว: หลังจากเพิ่ม entry เข้า dictionary แล้ว การอ่านครั้งถัดไปจะขยายเมื่อ NextCode ถึง (1 shl CodeSize) - Ord(EarlyChange) ด้วย /EarlyChange 1 ซึ่งเป็นค่าเริ่มต้นตาม ISO 32000-1 §7.4.4 การสลับจะเกิดขึ้นก่อนหนึ่ง code ด้วย /EarlyChange 0 มันจะเกิดขึ้นพอดีที่ขอบเขต ทั้งสองแบบปรากฏในไฟล์จริง และไม่มีอะไรใน bitstream บอกคุณได้ว่าตัวเข้ารหัสใช้แบบไหน ส่วนที่เหลือของ state machine ต้องเคลื่อนไปพร้อมกันแบบล็อกสเต็ป: clear code รีเซ็ต code size, bit mask, next free code และที่เก็บวลีพร้อมกันทั้งหมด และ end-of-information code จะถูกอ่านที่ความกว้างใดก็ตามที่เป็นปัจจุบัน ณ ขณะนั้น ไม่ใช่ที่ 9 บิตเริ่มต้น HotPDF เริ่มที่ InitialCodeSize 9 กำหนดเพดาน code size ที่ 12 และ dictionary ที่ 4096 entry และตั้งค่าเริ่มต้น FillOrder เป็น foTop เพราะ PDF บรรจุ code โดยเรียง bit ลำดับสูงก่อนเสมอ ส่วน foBottom มีไว้สำหรับ stream สไตล์ TIFF ที่ไม่ทำแบบนั้น

uses
  HPDFLZW;

var
  Decoder: TPDFLZWDecompressor;
  Parms: TPDFLZWParms;
  Plain: AnsiString;
begin
  Decoder := TPDFLZWDecompressor.Create;
  try
    Decoder.EarlyChange := True;      // /EarlyChange 1 is the PDF default
    Decoder.FillOrder := foTop;       // high-order bit first
    Decoder.MaxOutputBytes := 256 * 1024 * 1024;
    Decoder.RequireInitialClear := False;
    Decoder.RequireEndOfInformation := False;

    Parms.Predictor := 12;
    Parms.Colors := 3;
    Parms.BitsPerComponent := 8;
    Parms.Columns := 1024;
    Parms.ExpandedTo8Bit := False;
    Parms.ColorSpace := 'DeviceRGB';

    if Decoder.TryDecompress(RawStreamBytes, Parms, Plain) then
      LogDecodeStats(Decoder.PeakCodeSize, Decoder.DictionaryAdds,
        Decoder.KwKwKExpansions, Decoder.OutputBytes)
    else
      LogStreamDefect('lzw', Decoder.LastError);
  finally
    Decoder.Free;
  end;
end;

สถิติเหล่านี้มีไว้เพื่อคัดแยกปัญหา ไม่ใช่เพื่อความสวยงาม เมื่อไฟล์หนึ่ง decode ออกมาได้ความยาวถูกต้องแต่พิกเซลผิด PeakCodeSize กับ DictionaryAdds จะบอกคุณได้ทันทีว่าตัวอ่านเคยขยายตรงจุดที่ตัวเขียนขยายหรือไม่ สลับ EarlyChange แล้ว decode ใหม่ เปรียบเทียบทั้งสอง ถ้าตัวเลขขยับ คุณก็ได้คำตอบในการรันเดียวแทนที่จะต้อง step ผ่าน bit reader ทีละขั้น

สาขา KwKwK และเมื่อไรที่ stream ควรล้มเหลวไปเลยตรง ๆ

กรณีที่ถูกกฎหมายกรณีเดียวที่ดูเหมือนผิดกฎหมายคือ Code = NextCode และ HotPDF จัดการมันด้วยการสร้าง entry ก่อนที่จะปล่อยมันออกมา ตัวเข้ารหัสอาจปล่อย code สำหรับวลีที่มันกำลังนิยามอยู่ในขั้นตอนเดียวกัน ซึ่งเกิดขึ้นเมื่อ input มีรูปแบบ K w K w K ตัวถอดรหัสค้นหา code นั้นไม่ได้เพราะมันยังไม่มีอยู่ ดังนั้นจึงต้องสร้าง Previous + First(Previous) เพิ่มมันเป็น entry ใหม่ แล้วปล่อย entry ที่เพิ่งสร้างนั้นออกมา HotPDF นับกรณีเหล่านี้ไว้ใน KwKwKExpansions และตรวจสอบไขว้ว่า code ที่มันเพิ่มคือ code ที่มันถูกร้องขอ ทุกอย่างที่มากกว่า NextCode คือความเสียหาย และตรงนั้นตัวถอดรหัสควรหยุดแทนที่จะด้นสด HotPDF จะ raise เมื่อพบ code ในอนาคต เมื่อ dictionary prefix ชี้ออกนอก phrase arena เมื่อ dictionary เต็ม และเมื่อ code แรกไม่ใช่ literal สวิตช์ความเข้มงวดสองตัวถูกปิดโดยตั้งใจตามค่าเริ่มต้น คือ RequireInitialClear และ RequireEndOfInformation เพราะไฟล์ PDF ที่ใช้งานจริงจำนวนมากละเว้น clear code ที่นำหน้า หรือหมดข้อมูลโดยไม่มีตัวจบ เปิดมันเมื่อตรวจสอบ output ของคุณเอง ปล่อยให้ปิดไว้เมื่ออ่านไฟล์จากภายนอก

ตำแหน่งที่ /DecodeParms ถูกอ่านจริง ๆ ในฝั่งเอกสารที่โหลดแล้ว

HotPDF resolve /DecodeParms หรือคำย่อ /DP บน image stream dictionary ยอมรับได้ทั้ง dictionary หรือ array และเมื่อเป็น array จะเอาสมาชิกสุดท้าย จากนั้นนำ Predictor, Colors, BitsPerComponent, Columns และ EarlyChange เข้าสู่ path raster กรณี array คือสิ่งที่คนมักลืม stream ที่ผ่าน filter ด้วย [/ASCII85Decode /FlateDecode] บรรจุ parameter array คู่ขนานไว้ และค่า predictor เป็นของ filter ตัวสุดท้าย ไม่ใช่ตัวแรก

var
  Pdf: THotPDF;
  Info: THPDFLoadedImageInfo;
  Bmp: TBitmap;
  I: Integer;
begin
  Pdf := THotPDF.Create(nil);
  try
    if Pdf.LoadFromFile('scanned.pdf', '') > 0 then
      for I := 0 to Pdf.GetLoadedImageCount - 1 do
        if Pdf.GetLoadedImageInfo(I, Info) then
        begin
          Bmp := Pdf.ExtractLoadedImage(I);   // nil when the raster is unusable
          if Bmp <> nil then
          try
            Bmp.SaveToFile(Format('image-%d.bmp', [I]));
          finally
            Bmp.Free;
          end;
        end;
  finally
    Pdf.Free;
  end;
end;

ข้อบกพร่องทางประวัติศาสตร์อันหนึ่งใน path นั้นควรค่าแก่การเอ่ยถึง เพราะบั๊กประเภทนี้เกิดซ้ำได้เสมอ routine Flate-with-parameters แบบเก่าสร้าง decompression stream แล้วคัดลอกจาก input ที่บีบอัดไว้ต้นฉบับ ทำให้ขั้นตอน predictor ได้รับ byte ที่ยังบีบอัดอยู่ แล้วก็ทำการ un-predict มันไปอย่างขยันขันแข็ง ผิดเสมอ ไม่เคย raise เลย โค้ดปัจจุบันอ่านจาก decoder เพียงอย่างเดียวก่อนส่งผลลัพธ์ให้ predictor ที่ใช้ร่วมกัน และปฏิเสธ raster ที่สั้นกว่าขนาดที่คำนวณไว้ แทนที่จะถอยกลับไปใช้ byte ที่ยังบีบอัดอยู่ ซึ่ง fallback แบบนั้นเคยเปลี่ยนความล้มเหลวในการ decode ให้กลายเป็น bitmap ที่เสียหาย implementation ของ predictor ตัวเดียวกันนี้ตอนนี้ให้บริการกับ cross-reference stream ด้วย ซึ่งเป็นความสอดคล้องที่มีประโยชน์ถ้าคุณทำงานกับ object stream และ incremental update ด้วย และกลไกการแตกไฟล์โดยรอบครอบคลุมไว้ในบทความคู่กันเรื่อง การแตกภาพที่โหลดแล้วและ decode filter ของมัน ภาพที่มาในรูป DCTDecode หรือ JPXDecode ไม่มีวันไปถึง predictor เลย พวกมันบรรทุกโมเดลพิกเซลที่บีบอัดของตัวเองมา

ปริมาณงาน: phrase arena ต่อเนื่องเทียบกับ string แยก entry

การแทนที่ string dictionary แบบแยก entry ด้วย phrase arena ต่อเนื่อง วัดได้เร็วขึ้นประมาณ 1.61 เท่าบน input ที่โหดร้าย คือ 1558 MiB/s เทียบกับ 969 MiB/s บน benchmark ที่วลีเดียวที่ยาวที่สุดมีขนาดถึง 7,370,880 byte รูปร่างของ input นั้นอธิบายช่องว่างนี้ได้ เพราะ implementation แบบคลาสสิกเลือกหนึ่งในสองการแลกที่แย่ dictionary ของค่า AnsiString จัดสรรและคัดลอก string ใหม่ทั้งหมดสำหรับทุก entry จากที่มีได้ถึง 4096 entry แต่ละ entry ใหม่คัดลอก parent ของมันทั้งก้อน ส่วน prefix/suffix stack หลีกเลี่ยงหน่วยความจำนั้นได้ทั้งหมดแต่สร้างแต่ละวลีขึ้นใหม่ด้วยการไล่ chain ย้อนกลับทีละ byte แล้วกลับด้าน ซึ่งใช้ได้ดีกับข้อความทั่วไปแต่ทรมานเมื่อวลีหนึ่งยาวถึงหลายเมกะไบต์ HotPDF ต่อแต่ละวลีเข้าไปใน arena ที่โตขึ้นแบบเรขาคณิตต่อเนื่อง สร้าง index entry ด้วย offset กับความยาว และปล่อยวลีออกมาด้วย Move ครั้งเดียวเข้า output buffer ต้นทุนที่ซื่อตรงคือหน่วยความจำ arena ที่เก็บทุกวลีไว้ครบถ้วนถูกจำกัดด้วยผลรวมของความยาววลีทั้งหมด ไม่ใช่ด้วยจำนวน entry ซึ่งนี่คือเหตุผลที่ MaxOutputBytes มีอยู่ทั้งบน decompressor และ predictor นำขีดจำกัดนั้นมาจากสิ่งที่ image dictionary อ้างว่า raster ควรจะเป็น แล้ว stream ที่โกหกจะล้มเหลวเร็ว

ตัวถอดรหัส LZW, predictor ที่ใช้ร่วมกัน และ path การแตกภาพที่โหลดแล้วที่แสดงไว้ที่นี่มาพร้อมกับ HotPDF Component มาตรฐานสำหรับ Delphi และ C++Builder พร้อมเอกสารอ้างอิง filter และ DecodeParms แบบเต็มบนหน้าผลิตภัณฑ์