JBIG2 halftone ใน PDFlibPas: HSKIP สลับตำแหน่งกับ grid ติดลบ

PDFlibPas แก้ความผิดพลาดอิสระกันสองจุดใน JBIG2 halftone region decoder native ของตัวเอง: ใน v3.539.37 skip mask ของ HSKIP ถูก index เป็น HSKIP[ng, mg] ตามที่ ITU-T T.88 §6.6.5.1 นิยามไว้ และใน v3.539.38 grid ที่ไปถึงพิกัดติดลบ ไม่ว่าจะผ่าน HGX หรือ HGY ติดลบ หรือผ่านการหมุน grid ถูกวางด้วยการเลื่อนบิตแบบ floor จริง ๆ ก่อน release ทั้งสอง halftone region ที่เป็นพื้นที่เสี่ยงออกมาเละหรือเหลื่อมตำแหน่ง โดยไม่ยก error ขึ้นมาเลย บั๊กทั้งคู่ซุ่มอยู่หลังข้อมูลทดสอบที่บังเอิญสมมาตรหรือไม่ติดลบ และตัวที่สองเปิดเผยสมบัติของ Delphi กับ Free Pascal ที่กัดคนไกลกว่า JBIG2 มาก: shr บนจำนวนเต็มมีเครื่องหมายเป็น logical shift ไม่ใช่ >> แบบ arithmetic ที่มาตรฐานสมมติไว้

halftone region เป็นชนิด region ของ JBIG2 ที่พบน้อยที่สุด decoder เลยไล่งานเอกสารสแกนไปได้เป็นพันฉบับกว่าจะเจอภาพถ่ายแบบ screened ที่ encode เป็นชนิดนี้ พอเจอเข้าอาการก็แสบ: ไฟล์ parse ผ่าน ความยาว segment รวมกันลงตัว หน้ากระดาษขนาดถูก แล้ว region ก็เป็นขยะ

JBIG2 halftone region ถอดรหัสอะไรกันแน่

JBIG2 halftone region คือ grid ของ bitmap เล็ก ๆ ที่หยิบมาจาก pattern dictionary และงานจริงของ decoder คือคำนวณ index ให้ทุกช่องของ grid กับตำแหน่ง pixel ที่ช่องนั้นตกลงไป pattern dictionary ถือ pattern จำนวน HNUMPATS ตัวขนาด HPW คูณ HPH pixel ส่วน segment ของ halftone region อธิบาย grid จำนวน HGW column คูณ HGH row กับภาพ gray-scale ขนาดเท่ากัน ที่ encode เป็น bitplane แบบ Gray-coded แต่ละ bitplane ถูกถอดด้วย generic region procedure บน bitmap HGW คูณ HGH เริ่มจาก plane บนสุดก่อน และ plane ทั้งชุดให้ index ของ pattern แก่ทุกช่อง

การวางช่องใช้ fixed-point arithmetic ที่มีเศษ 8 บิต จุด origin ของ grid คือคู่ HGX, HGY เป็นค่า 32 บิตสองตัว และเวกเตอร์ grid HRX, HRY บรรยายระยะก้าวระหว่างช่องติดกัน ซึ่งเปิดทางให้ grid หมุนได้ สำหรับ row mg กับ column ng ของ grid T.88 §6.6.5 คำนวณตำแหน่ง pixel เป็น:

• x = (HGX + mg × HRY + ng × HRX) >> 8
• y = (HGY + mg × HRX − ng × HRY) >> 8

skip mask เข้ามาผ่าน flag HENABLESKIP ที่เป็น optional เมื่อ flag ถูกเซ็ต §6.6.5.1 สร้าง bitmap HGW คูณ HGH ชื่อ HSKIP แล้วเซ็ต HSKIP[ng, mg] เป็น 1 ให้ทุกช่องที่ pattern ของมันอยู่นอก region ทั้งก้อน: x + HPW <= 0, x >= HBW, y + HPH <= 0 หรือ y >= HBH จากนั้น bitplane gray-scale ถูกถอดโดยใช้ mask นั้นเป็น skip bitmap ของ generic region arithmetic decoder จึงไม่อ่านและไม่อัปเดต context ของช่องที่ถูก skip decoder กับ encoder ต้องเห็นตรงกันทุกบิตของ HSKIP ไม่งั้น arithmetic coder สองฝั่งก็เดินหลุดจังหวะกัน

ทำไม HSKIP ที่สลับตำแหน่งพังแค่ grid ไม่จัตุรัส

skip mask ถูกเขียนด้วยพิกัดสลับที่กัน และมีแต่ grid ที่ไม่ใช่จัตุรัสเท่านั้นที่เปิดโปง เพราะ grid จัตุรัสทำให้พิกัดที่สลับแล้วทุกตัวยังอยู่ใน mask PDFlibPas เก็บ bitmap ด้วย accessor รูป (column, row) แต่โค้ดที่สร้าง mask ส่ง (mg, ng) ไปให้ โดยมา row ก่อน decoder ของ bitplane gray-scale อ่าน mask ถูกต้องเป็น (ng, mg) ส่วน loop วาง pattern อ่านกลับมาในลำดับที่ถูกสลับของตัวสร้าง สองฝั่งจึงเห็นตรงกัน และการรีวิวแค่ logic การวางก็ผ่านไปได้ กับดักการตั้งชื่อยิ่งทำให้เลวลง ใน loop วาง pattern ตัวแปรที่ชื่อ col ไล่ row ของ grid ส่วน Row ไล่ column ของ grid

ยก grid 5 คูณ 3 ของ pattern 4 คูณ 4 บน region 16 คูณ 8 ที่ v3.539.37 ใช้เป็นเคส regression ด้วย HRX = 1024 กับ HRY = 0 column ที่ 4 ของ grid ตกที่ x = 16 และ row ที่ 2 ตกที่ y = 8 อยู่นอก region ทั้งคู่ mask ที่ถูกต้อง mark 7 ช่อง: column 4 ทั้งเส้นและ row 2 ทั้งแถว การเขียนแบบสลับพยายามเซ็ต pixel ที่ row index 3 กับ 4 ใน mask ที่สูงแค่สามแถว และตัวเซ็ต bitmap เงียบ ๆ ข้ามการเขียนล้ำเขตพวกนั้นทิ้ง สิ่งที่รอดคือ column 2 rows 0 ถึง 2 decoder เลย skip สองช่องที่ encoder เขียนโค้ดไว้ และถอดหกช่องที่ encoder skip ไป

arithmetic decoder ไม่ล้มเมื่อเรื่องแบบนี้เกิดขึ้น มันถอด pixel เกินออกจากบิตที่เป็นของช่องถัดไป context ของมันอ่านเพื่อนบ้านผิดตัว และ pattern index ทุกตัวหลังความเห็นต่างจุดแรกกลายเป็น noise อาการจึงเป็น region เละทั้งก้อน ไม่ใช่ช่องเหลื่อมสักสองสามช่อง บน grid จัตุรัสบั๊กเดียวกันมักมองไม่เห็น ไม่มีพิกัดที่สลับแล้วหลุดออกนอก mask และเมื่อช่องนอก region สมมาตรกันเทียบเส้นทแยง เช่น grid ที่ยื่นเกินขอบขวากับล่างด้วยจำนวนช่องเท่ากัน mask ที่สลับแล้วก็คือ mask ที่ถูกต้องไบต์ต่อไบต์ HENABLESKIP ยังเป็น optional ต้องเป็น 0 เมื่อภาพ gray-scale encode แบบ MMR และ encoder แทบไม่เซ็ตมัน บั๊กจึงมีช่องให้ปรากฏตัวน้อยมาก ตั้งแต่ v3.539.37 ตัวสร้าง mask เขียน HSKIP[ng, mg] และ loop วาง pattern อ่านลำดับเดียวกัน

ทำไม offset ของ halftone grid ที่ติดลบถึงพังสามชั้น

halftone grid ที่เริ่มซ้ายกว่าหรือสูงกว่า region ของมันทำ PDFlibPas พังสามจุดแยกกัน และแต่ละจุดซ่อนจุดถัดไปไว้ T.88 ยอมรับ geometry แบบนี้ตั้งใจ encoder ที่จัดแนว screen ของมันกับหน้ากระดาษแทนที่จะจัดกับ region หรือใช้ grid ที่หมุน ย่อมผลิตมุมช่องติดลบที่ region ตัดทิ้งตามธรรมชาติ v3.539.38 แก้ทั้งสามชั้นพร้อมกัน เพราะแก้ทีละอันก็แค่เปลี่ยนอาการ

ชั้นที่ 1: field มีเครื่องหมายถูกอ่านเป็น unsigned

T.88 §7.4.5.1.2 นิยาม HGX กับ HGY เป็นค่า 32 บิตมีเครื่องหมาย แต่ decoder อ่านด้วย helper 32 บิตตัวเดียวกับที่ใช้กับ field แบบ unsigned และ helper ตัวนั้นหนีบทุกผลลัพธ์ติดลบเป็น 0 grid ที่ตั้งใจเริ่มที่ HGX = -900 ถูกย้ายเงียบ ๆ ไปกอด origin ของ region ในเคส regression ของ v3.539.38 ภาพทั้งภาพออกมาต่ำกว่าจริงสองแถว การหนีบยังอธิบายได้ด้วยว่าทำไมอีกสองความผิดพลาดรอดมาได้นาน พอ origin ถูกบังคับไม่ให้ติดลบ พิกัดติดลบจะโผล่ได้ทางเดียวคือผ่าน grid ที่หมุนโดย HRY > 0 ซึ่ง y = HGY + mg × HRX − ng × HRY จะจมต่ำกว่าศูนย์เมื่อ column ของ grid ลึกขึ้น

ชั้นที่ 2: shr ไม่ใช่การเลื่อนขวา 8 บิตแบบที่คิด

T.88 เขียน >> 8 และหมายถึง arithmetic shift ที่ปัดเข้าหาลบอนันต์ decoder แปลมันเป็น shr 8 ใน Delphi กับ Free Pascal shr บนจำนวนเต็มมีเครื่องหมายเป็น logical shift: บิตเครื่องหมายถูกดันเข้ามาเป็นศูนย์ สำหรับ Integer ที่ถือ -512 shr 8 ให้ 16777214 แทนที่จะเป็น -2 pattern ที่ควรถูกวาดที่ y = -2 แล้วถูก crop เหลือครึ่งล่าง ถูกส่งไปไกล 16 ล้านแถวแล้วทิ้งในฐานะ off-region ไม่มีอะไร crash แถวบนสุดของ halftone หายไปเฉย ๆ

ชั้นที่ 3: เทียบค่า fixed-point แทนที่จะเทียบ pixel

เช็ค skip เทียบค่า fixed-point กัน ไม่ใช่ตำแหน่ง pixel และสองอย่างนี้ไม่เท่ากันเมื่อเศษไม่เป็นศูนย์ โค้ดเดิมหลบ logical shift ด้วยการทดสอบ xx + HPW × 256 <= 0 บนค่าที่ยังไม่ได้เลื่อน ซึ่งคิดกันว่าเทียบเท่ากับ test ของ T.88 ด้วย HGX = -900 กับ pattern 4 pixel ได้ -900 + 1024 = 124 เป็นบวก ช่องจึงไม่ถูก skip มาตรฐานเลื่อนบิตก่อน: floor(-900 / 256) = -4 และ -4 + 4 = 0 เข้าเงื่อนไข x + HPW <= 0 ช่องจึงอยู่นอก region ทั้งก้อนและต้องถูก skip encoder skip มัน decoder ถอดมัน ภาพ gray-scale จึงค่อย ๆ เหลื่อมไปแบบเดียวกับเคส mask สลับแกน

เคส regression ของ v3.539.38 ใช้ grid 4 คูณ 3 ของ pattern 4 คูณ 4 ที่ HGX = -900, HGY = -512, HRX = 1024 บน region 12 คูณ 10 column ของ grid ตกที่ x = -4, 0, 4 และ 8 column 0 จึงอยู่นอกทั้งก้อนและควรอยู่ใน HSKIP ส่วน row ตกที่ y = -2, 2 และ 6 row 0 ต้องถูก crop เหลือสองแถว pixel ล่าง ไม่ใช่ทิ้งทั้งแถว แก้ทีละชั้นจะได้กองอาการแบบนี้:

ความผิดพลาดที่แก้แล้ว	region ที่ถอดได้
ไม่แก้เลย (ก่อน v3.539.38)	grid ถูกดึงไปกอด origin ภาพทั้งภาพต่ำกว่าจริงสองแถว
แก้การอ่าน HGX / HGY แบบมีเครื่องหมายอย่างเดียว	row แรกของ grid หาย ที่เหลือเละเพราะการเหลื่อมของเช็ค skip
อ่านแบบมีเครื่องหมาย เลื่อนบิตแบบ floor และเช็ค skip ในพื้นที่ pixel	เหมือนกันเป๊ะทีละ pixel กับหน้าที่คำนวณจาก T.88 §6.6.5 และกับ reference decoder อิสระสองตัว

การแก้คือ helper ตัวเดียว HalftoneGridPixel ที่ตัวสร้าง skip mask กับ loop วาง pattern ใช้ร่วมกัน มันสะสมพิกัดใน Int64 ผลคูณ mg × HRX ที่ใหญ่จึงวนกลับไม่ได้ หารด้วย 256 โดยปัดเข้าหาลบอนันต์ แล้วหนีบไว้ที่ ±MaxInt div 2 grid ที่พังจึงไม่มีทางทำ bitmap arithmetic ล้นในภายหลัง เช็ค skip ตอนนี้เทียบค่า pixel พวกนี้กับ HPW, HPH, HBW กับ HBH ตรงตามที่ §6.6.5.1 พูดไว้

เขียน arithmetic right shift ใน Delphi อย่างไร

Delphi ไม่มี operator เลื่อนขวาแบบ arithmetic การเลื่อนขวาค่ามีเครื่องหมายที่ถูกต้องจึงต้องเขียนเป็นการหารแบบ floor และ div ธรรมดาไม่ใช่การหารแบบนั้น div ตัดทอนเข้าหาศูนย์ สำหรับค่าไม่ติดลบการตัดทอนกับ floor เห็นตรงกัน และก็เห็นตรงกันด้วยกับค่าติดลบที่เป็นผลคูณเต็มของตัวหาร นั่นเหตุผลที่ -512 div 256 = -2 ดูโอเคใน test ด่วน ๆ แต่ที่อื่นทั้งหมดพวกมันคลาดกัน: -900 div 256 เป็น -3 ขณะที่ floor คือ -4 และ -1 div 256 เป็น 0 ขณะที่ floor คือ -1 พิกัด JBIG2 ที่มีเศษไม่เป็นศูนย์เป๊ะ ๆ คือเคสที่ div ให้ pixel ผิดตัว

บน compiler Delphi Win32 กับ Win64 ตัวแปร Integer ที่ถือ -512 เลื่อนขวา 8 ได้ 16777214 และ Int64 ที่ถือ -512 ได้ 72057594037927934 Free Pascal นิยาม shr เป็น logical shift เหมือนกัน และแถม SarLongint กับ SarInt64 มาในยูนิต System สำหรับเวอร์ชัน arithmetic แต่สองฟังก์ชันนี้ไม่มีใน Delphi โค้ดที่ใช้ร่วมสอง compiler จึงต้องมี helper ของตัวเอง:

// หารแบบ floor: ปัดเข้าหาลบอนันต์ไม่ว่า A กับ B จะติดลบหรือไม่
// B ห้ามเป็น 0 และ FloorDiv(Low(Integer), -1) ล้นแบบเดียวกับ div
function FloorDiv(A, B: Integer): Integer;
begin
  Result := A div B;
  if (A mod B <> 0) and ((A < 0) <> (B < 0)) then
    Dec(Result);
end;

// arithmetic right shift (">>" ของภาษา C และ T.88 บนค่ามีเครื่องหมาย)
// สำหรับ Value ติดลบ not Value = -Value - 1 จะไม่ติดลบ shr แบบ logical
// จึงปลอดภัยตรงนั้น แล้ว not ชั้นนอก map ผลลัพธ์กลับมา
function SarInt32(Value: Integer; Shift: Integer): Integer;  // Shift 0..31
begin
  if Value >= 0 then
    Result := Value shr Shift
  else
    Result := not ((not Value) shr Shift);
end;

function SarInt64(Value: Int64; Shift: Integer): Int64;      // Shift 0..63
begin
  if Value >= 0 then
    Result := Value shr Shift
  else
    Result := not ((not Value) shr Shift);
end;

ลูกเล่น not นี้ไม่เคยเลื่อนจำนวนติดลบเลย มันจึงไม่พึ่งพาว่า compiler จะปฏิบัติกับบิตเครื่องหมายอย่างไร และไม่เคยล้น รวมถึงกรณี Low(Integer) helper ทั้งคู่เทียบกับ floor reference แบบ Int64 ครบหลายล้านค่า ทุกการเลื่อนจาก 0 ถึง 31 และขอบ Low(Integer) กับ High(Integer) บน Delphi Win32, Delphi Win64 และ Free Pascal x86_64 เช็คสุขภาพจิตที่ควรเก็บไว้ใน unit test ไหนที่แตะพิกัด:

var
  V: Integer;
begin
  V := -900;
  Writeln(V shr 8);           // 16777212  logical shift บั๊กรุ่นเก่า
  Writeln(V div 256);         // -3        ตัดทอนเข้าหาศูนย์
  Writeln(FloorDiv(V, 256));  // -4        สิ่งที่ T.88 หมายถึงด้วย >> 8
  Writeln(SarInt32(V, 8));    // -4
end;

Math.Floor(V / 256) ก็คืน -4 เหมือนกัน แต่วงเวียนผ่าน Double เสียความแม่นยำกับค่า Int64 ที่เกิน 2⁵³ geometry แบบจำนวนเต็มจึงควรอยู่ในจำนวนเต็ม

call ไหนของ PDFlibPas ที่รัน decoder ของ halftone

JBIG2 halftone decoder รันเมื่อ PDFlibPas render หน้าด้วย built-in renderer เพราะการ render ต้องมี pixel RenderPageToFile กับ RenderPageToStream ต่างไปถึงมันผ่าน image stream แบบ JBIG2Decode ของหน้า การ render หน้า halftone ซ้ำจึงเป็นทางตรงที่สุดในการยืนยันว่า v3.539.38 เปลี่ยน output ของคุณ decoder ตัวเดียวกันดูแล region ชนิดอื่นของ JBIG2 ด้วย ซึ่งเล่าไว้ในตาราง Huffman แบบกำหนดเองของ JBIG2 ใน decoder Pascal ล้วน และการถอดไฟล์ JBIG2 แบบ random-access ใน Delphi ส่วน bitmap ที่ render ออกมาหล่อเข้างานแปลงไฟล์อย่างการ render หน้า PDF เป็นภาพขาวดำ 1 บิต

uses
  SysUtils, PDFlibrary;

var
  Lib: TPDFlib;
  Page: Integer;
begin
  Lib := TPDFlib.Create;
  try
    if Lib.LoadFromFile('scanned-halftone.pdf', '') <> 1 then
      raise Exception.CreateFmt('Load failed, error %d', [Lib.LastErrorCode]);
    for Page := 1 to Lib.PageCount do
      // การ render decode JBIG2 region ทุกชนิด รวมถึง halftone ด้วย
      if Lib.RenderPageToFile(150, Page, PDF_RENDER_PNG,
        Format('page-%.3d.png', [Page])) <> 1 then
        Writeln('Page ', Page, ' was not rendered');
  finally
    Lib.Free;
  end;
end.

การ extract ภาพปกติเดินคนละเส้นทาง GetPageImageList คืนภาพ JBIG2 ในรูปแบบดั้งเดิม และ SaveImageListItemDataToFile หรือ GetImageListItemDataToString ส่งมอบไฟล์ JBIG2 แบบตั้งยืนที่ประกอบจากไบต์ของ stream: header ของไฟล์, ข้อมูล JBIG2Globals และ segment end-of-file ครอบข้อมูลหน้า property 400 ของ GetImageListItemIntProperty รายงานเป็น 6 สำหรับ item แบบนี้ เส้นทางนี้ไม่ decode อะไรเลย ไฟล์ .jb2 ที่ extract ออกมาดูถูกต้องใน viewer อื่นขณะที่หน้าที่ render โชว์ noise จึงเป็นสัญญาณคลาสสิกของบั๊ก halftone ทั้งสองตัว:

var
  ListID, I: Integer;
begin
  Lib.SelectPage(1);
  ListID := Lib.GetPageImageList(0);
  if ListID = 0 then
    Exit;
  try
    for I := 1 to Lib.GetImageListCount(ListID) do
      if Lib.GetImageListItemIntProperty(ListID, I, 400) = 6 then  // standalone JBIG2
        Lib.SaveImageListItemDataToFile(ListID, I, 0,
          Format('page1-image%d.jb2', [I]));
  finally
    Lib.ReleaseImageList(ListID);
  end;
end;

เมื่อ mask หรือการแปลงสีบังคับให้ต้อง render แทน item จะกลับมาเป็น bitmap ที่ถอดรหัสแล้ว และ decoder ของ halftone ก็รันจริง เรื่อง image list ละเอียดเพิ่มอยู่ในการ extract text, image และ font จาก PDF ใน Delphi

สรุปด่วน: กฎ grid ของ JBIG2 halftone

• index skip mask เป็น HSKIP[ng, mg] โดย column ของ grid มาก่อน และอ่านกลับด้วยลำดับเดียวกันทุกจุดที่วางช่อง (T.88 §6.6.5.1, แก้ใน PDFlibPas v3.539.37)
• ทดสอบโค้ด halftone หรือ grid ใด ๆ ด้วย grid ที่ไม่จัตุรัสและชุดช่องนอก region ที่ไม่สมมาตร เพราะ grid จัตุรัสซ่อน index ที่สลับแกนได้หมดจด
• อ่าน HGX กับ HGY เป็นค่า 32 บิตมีเครื่องหมาย (T.88 §7.4.5.1.2) อย่าผ่าน helper แบบ unsigned ที่หนีบค่าติดลบเด็ดขาด
• แปล >> 8 ในมาตรฐานเป็นการหารแบบ floor ด้วย 256 ไม่ใช่ shr 8 และไม่ใช่ div 256
• รันเช็ค skip บนตำแหน่ง pixel ที่เลื่อนบิตแล้ว รูป fixed-point ต่างกันทุกครั้งที่เศษไม่เป็นศูนย์ อย่างที่ HGX = -900 กับ pattern 4 pixel โชว์ให้เห็น
• สะสมพิกัด grid ใน Int64 แล้วหนีบก่อนส่งเข้าโค้ด bitmap grid ที่พังจึงทำให้ล้นไม่ได้
• อัปเกรดเป็น v3.539.38 ขึ้นไปถ้าเอกสารของคุณมี halftone region ที่ใช้ HENABLESKIP, origin ของ grid ติดลบ หรือ grid ที่หมุน

PDFlibPas render, extract และแก้ไขเอกสาร PDF จาก Delphi กับ C++Builder ด้วย JBIG2 decoder Pascal native ที่ตอนนี้จัดการ skip mask, origin ติดลบและ grid ที่หมุนของ halftone ตามที่ T.88 กำหนด ดูPDFlibPas Delphi PDF library สำหรับฟีเจอร์ edition และดาวน์โหลดเวอร์ชันทดลอง