Lưới halftone JBIG2 trong PDFlibPas: HSKIP và offset âm

PDFlibPas đã sửa hai lỗi độc lập trong decoder halftone region JBIG2 thuần Pascal của mình: ở v3.539.37, mask skip HSKIP được đánh chỉ số dạng HSKIP[ng, mg] đúng như ITU-T T.88 §6.6.5.1 định nghĩa, và ở v3.539.38, những lưới chạm tới tọa độ âm — qua HGX hay HGY âm hoặc qua xoay — được đặt vị trí bằng phép dịch floor đúng nghĩa. Trước các bản phát hành ấy, các halftone region bị ảnh hưởng ra rác hoặc lệch chỗ, không một lỗi nào được nêu. Cả hai bug đều nấp sau dữ liệu thử tình cờ đối xứng hay không âm, và bug thứ hai dính tới một tính chất của Delphi và Free Pascal cắn sâu ngoài xa JBIG2: shr trên số nguyên có dấu là dịch logic, không phải phép >> số học mà chuẩn ngầm định

Halftone region là loại region JBIG2 hiếm gặp nhất, nên một decoder có thể xử lý hàng nghìn tài liệu scan trước khi gặp một tấm ảnh in lưới được mã hóa dưới dạng này. Khi gặp thật, cảnh thất bại rất khó chịu: tệp parse được, độ dài các segment cộng lại khớp, trang đúng kích thước, mà region thì là rác

Một halftone region JBIG2 thực chất giải mã cái gì?

Một halftone region JBIG2 là một lưới các bitmap nhỏ chọn từ một pattern dictionary, và công việc thật của decoder là tính chỉ số cho từng ô lưới cùng vị trí pixel nơi ô đó đáp xuống. Pattern dictionary giữ HNUMPATS pattern cỡ HPW × HPH pixel. Segment halftone region khi đó mô tả một lưới HGW cột nhân HGH hàng và một ảnh xám cùng cỡ, mã hóa thành các bitplane mã Gray. Mỗi bitplane được giải mã bằng thủ tục generic region trên một bitmap HGW × HGH, plane có trọng số cao nhất trước, và các plane cùng nhau cho từng ô chỉ số pattern của nó

Việc đặt ô dùng số học fixed-point với phần lẻ 8 bit. Gốc lưới HGX, HGY là một cặp giá trị 32-bit, còn vector lưới HRX, HRY mô tả bước nhảy giữa các ô kề nhau, cho phép lưới bị xoay. Với hàng lưới mg và cột lưới ng, T.88 §6.6.5 tính vị trí pixel như sau:

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

Mask skip đi vào qua flag HENABLESKIP tùy chọn. Khi flag được đặt, §6.6.5.1 dựng một bitmap HSKIP cỡ HGW × HGH và đặt HSKIP[ng, mg] bằng 1 cho mọi ô có pattern nằm hoàn toàn ngoài region: x + HPW <= 0, x >= HBW, y + HPH <= 0 hoặc y >= HBH. Các bitplane xám khi đó được giải mã với mask ấy làm bitmap skip của generic region, nên decoder số học chẳng đọc cũng chẳng cập nhật context cho ô bị skip. Decoder và encoder phải khớp nhau từng bit của HSKIP, nếu không hai bộ mã hóa số học lệch nhịp

Vì sao mask HSKIP bị chuyển vị chỉ làm hỏng lưới không vuông?

Mask skip bị ghi với tọa độ đảo cho nhau, và chỉ một lưới không vuông mới làm lộ nó, vì lưới vuông giữ mọi tọa độ đảo vẫn nằm trong mask. PDFlibPas lưu bitmap với accessor pixel dạng (column, row), còn code dựng mask lại truyền (mg, ng), hàng trước. Decoder bitplane xám đọc mask đúng theo (ng, mg). Vòng lặp đặt pattern đọc lại theo thứ tự đảo của thằng dựng, nên hai bên khớp nhau, và một lượt review riêng phần logic đặt pattern sẽ cho qua. Một cái bẫy đặt tên khiến chuyện còn tệ hơn: trong vòng lặp đặt pattern, biến tên col lại chạy theo hàng lưới còn Row chạy theo cột lưới

Lấy lưới 5 × 3 gồm các pattern 4 × 4 trên một region 16 × 8 mà v3.539.37 dùng làm ca hồi quy. Với HRX = 1024 và HRY = 0, cột lưới 4 đáp tại x = 16 và hàng lưới 2 tại y = 8, đều ngoài region. Mask đúng đánh dấu bảy ô: trọn cột 4 và trọn hàng 2. Các lệnh ghi bị đảo cố đặt pixel tại chỉ số hàng 3 và 4 trong một mask chỉ cao ba hàng, và setter bitmap lặng lẽ bỏ qua những lệnh ghi ngoài vùng ấy. Sót lại là cột 2, hàng 0 tới 2. Decoder vì thế skip hai ô mà encoder đã mã hóa, và giải mã sáu ô mà encoder đã skip

Decoder số học không thất bại khi chuyện đó xảy ra. Nó giải mã thừa pixel từ những bit vốn thuộc về các ô phía sau, context của nó đọc nhầm hàng xóm, và mọi chỉ số pattern sau lần bất đồng đầu tiên đều là nhiễu — vì thế triệu chứng là một region thành rác chứ không phải vài ô lệch chỗ. Trên lưới vuông, cùng bug đó thường vô hình: không tọa độ đảo nào lọt ra ngoài mask, và khi các ô ngoài region đối xứng qua đường chéo — chẳng hạn một lưới tràn ra cạnh phải và cạnh dưới cùng số ô — thì mask bị chuyển vị lại giống bit-for-bit cái đúng. HENABLESKIP còn là flag tùy chọn, phải bằng 0 khi ảnh xám mã hóa MMR, và hiếm encoder nào đặt, nên bug gần như không có đường ló mặt. Kể từ v3.539.37, thằng dựng ghi HSKIP[ng, mg] và vòng lặp đặt pattern đọc cùng thứ tự ấy

Vì sao offset lưới halftone âm hỏng tới ba tầng?

Một lưới halftone bắt đầu bên trái hay bên trên region của nó làm sập PDFlibPas ở ba chỗ riêng biệt, và mỗi lỗi lại che lỗi kế tiếp. T.88 cho phép kiểu hình học này một cách có chủ đích. Một encoder canh screen theo trang thay vì theo region, hay dùng lưới xoay, tự nhiên sinh ra các góc ô âm mà region sẽ cắt bỏ. v3.539.38 sửa cả ba tầng cùng lúc, vì sửa riêng lẻ từng tầng chỉ đổi triệu chứng

Tầng 1: một trường có dấu bị đọc như không dấu

T.88 §7.4.5.1.2 định nghĩa HGX và HGY là các giá trị 32-bit có dấu, nhưng decoder đọc chúng bằng cùng helper 32-bit nó dùng cho các trường không dấu, và helper ấy kẹp mọi kết quả âm về 0. Một lưới lẽ ra bắt đầu tại HGX = -900 bị lặng lẽ kéo về gốc của region. Trong ca hồi quy của v3.539.38, cả bức tranh ra thấp hơn hai hàng. Cái kẹp còn giải thích vì sao hai lỗi kia sống dai thế: với gốc bị ép không âm, một tọa độ âm chỉ có thể xuất hiện qua lưới xoay với HRY > 0, nơi y = HGY + mg × HRX − ng × HRY rơi xuống dưới 0 ở các cột lưới về sau

Tầng 2: shr không phải >> 8

T.88 viết >> 8 và muốn nói một phép dịch số học, làm tròn về minus infinity. Decoder dịch nó thành shr 8. Trong Delphi và Free Pascal, shr trên số nguyên có dấu là dịch logic: bit dấu được dịch vào với giá trị 0. Với một Integer giữ -512, shr 8 cho 16777214 thay vì -2. Một pattern lẽ ra được vẽ tại y = -2 rồi cắt còn nửa dưới bị đẩy xuống mười sáu triệu hàng và vứt bỏ như ngoài region. Chẳng gì sập; hàng trên cùng của halftone chỉ đơn giản biến mất

Tầng 3: so sánh fixed-point thay vì pixel

Phép thử skip so sánh giá trị fixed-point chứ không phải vị trí pixel, và hai thứ không tương đương một khi phần lẻ khác 0. Code gốc né phép dịch logic bằng cách thử xx + HPW × 256 <= 0 trên giá trị chưa dịch, tưởng là tương đương với phép thử của T.88. Với HGX = -900 và pattern 4 pixel, kết quả là -900 + 1024 = 124, một số dương, nên ô không bị skip. Chuẩn dịch trước đã: floor(-900 / 256) = -4, và -4 + 4 = 0 thỏa x + HPW <= 0, nên ô nằm hoàn toàn ngoài và phải bị skip. Encoder skip nó, decoder giải mã nó, và ảnh xám trôi chính xác như trong ca mask bị chuyển vị

Ca hồi quy của v3.539.38 dùng một lưới 4 × 3 gồm các pattern 4 × 4 tại HGX = -900, HGY = -512, HRX = 1024 trên một region 12 × 10. Các cột lưới đáp tại x = -4, 0, 4 và 8, nên cột 0 nằm hoàn toàn ngoài và phải vào HSKIP; các hàng lưới đáp tại y = -2, 2 và 6, nên hàng 0 phải bị cắt còn hai hàng pixel dưới thay vì bị vứt. Sửa từng tầng một sẽ tái hiện lại chồng lỗi:

Lỗi đã sửa	Region sau giải mã
Không có (trước v3.539.38)	Lưới bị kéo về gốc, cả bức tranh thấp hơn hai hàng
Chỉ sửa phần đọc HGX / HGY có dấu	Hàng lưới đầu biến mất, phần còn lại thành rác vì trôi của phép thử skip
Đọc có dấu, dịch floor và phép thử skip trong không gian pixel	Giống hệt từng pixel với trang tính từ T.88 §6.6.5 và với hai decoder tham chiếu độc lập

Bản sửa là một helper duy nhất, HalftoneGridPixel, dùng chung cho thằng dựng mask skip và vòng lặp đặt pattern. Nó cộng dồn tọa độ trong Int64 để một tích mg × HRX lớn không thể tràn số, chia cho 256 làm tròn về minus infinity, và kẹp trong ±MaxInt div 2 để một lưới hỏng không thể làm tràn số học bitmap về sau. Phép thử skip giờ so các giá trị pixel ấy với HPW, HPH, HBW và HBH, đúng như §6.6.5.1 phát biểu

Viết phép dịch phải số học trong Delphi thế nào?

Delphi không có toán tử dịch số học, nên một phép dịch phải có dấu đúng phải viết thành một phép chia floor, mà div thường thì không phải phép chia ấy. div cắt về 0. Với giá trị không âm, cắt và floor cho cùng kết quả, và chúng cũng khớp với giá trị âm là bội đúng của số chia, đó là lý do -512 div 256 = -2 trông ổn trong một phép thử nhanh. Chúng lệch nhau ở mọi chỗ khác: -900 div 256 ra -3, trong khi floor là -4, còn -1 div 256 ra 0, trong khi floor là -1. Một tọa độ JBIG2 với phần lẻ khác 0 chính là trường hợp div đưa ra pixel sai

Trên các compiler Delphi Win32 và Win64, một biến Integer giữ -512 dịch phải 8 bit cho 16777214, còn một Int64 giữ -512 cho 72057594037927934. Free Pascal cũng định nghĩa shr là dịch logic và kèm sẵn SarLongint cùng SarInt64 trong unit System cho phiên bản số học, nhưng những hàm đó không tồn tại trong Delphi, nên code dùng chung cho hai compiler cần helper riêng:

// Chia lấy sàn: làm tròn về âm vô cực với mọi dấu của A và B.
// B phải khác 0, và FloorDiv(Low(Integer), -1) tràn số đúng như 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;

// Dịch phải số học (kiểu ">>" của C và T.88 trên giá trị có dấu).
// Với Value âm thì not Value = -Value - 1 không âm, nên
// logical shr ở đó là an toàn, và not bên ngoài đưa kết quả về lại
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;

Mẹo not không bao giờ dịch một số âm, nên nó không phụ thuộc cách compiler xử lý bit dấu, và không bao giờ tràn số, kể cả với Low(Integer). Cả hai helper khớp với một tham chiếu floor trên Int64 qua hàng triệu giá trị, mọi phép dịch từ 0 tới 31 cùng các biên Low(Integer) và High(Integer) trên Delphi Win32, Delphi Win64 và Free Pascal x86_64. Một phép thử hợp lý đáng giữ lại trong mọi unit test chạm tới tọa độ:

var
  V: Integer;
begin
  V := -900;
  Writeln(V shr 8);           // 16777212  dịch logic, bug cũ
  Writeln(V div 256);         // -3        cắt về 0
  Writeln(FloorDiv(V, 256));  // -4        điều T.88 muốn nói bằng >> 8
  Writeln(SarInt32(V, 8));    // -4
end;

Math.Floor(V / 256) cũng trả về -4, nhưng đường vòng qua Double của nó mất chính xác với các giá trị Int64 trên 2⁵³, nên hình học số nguyên nên ở lại với số nguyên

Những lời gọi PDFlibPas nào chạy decoder halftone?

Decoder halftone JBIG2 chạy khi PDFlibPas render một trang bằng renderer dựng sẵn, vì render thì cần pixel. RenderPageToFile và RenderPageToStream đều chạm tới nó qua các image stream JBIG2Decode của trang, nên render lại một trang halftone là cách trực tiếp nhất để xác nhận v3.539.38 đổi đầu ra của bạn. Cùng decoder đó xử lý các loại region JBIG2 khác, đã trình bày trong bảng Huffman tùy chỉnh JBIG2 trong decoder thuần Pascal và giải mã tệp JBIG2 truy cập ngẫu nhiên trong Delphi, còn bitmap đã render nuôi các phép chuyển đổi như render trang PDF ra đơn sắc 1-bit

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
      // Rendering giải mã mọi region JBIG2, gồm cả 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.

Trích ảnh thường đi một đường khác. GetPageImageList trả về ảnh JBIG2 ở dạng gốc, còn SaveImageListItemDataToFile hay GetImageListItemDataToString đưa cho bạn một tệp JBIG2 độc lập dựng từ các byte stream: header tệp, dữ liệu JBIG2Globals và một segment end-of-file bao quanh dữ liệu trang. Thuộc tính 400 của GetImageListItemIntProperty báo 6 cho một item như vậy. Không gì được giải mã trên đường này, nên một .jb2 trích ra trông đúng trong viewer khác trong khi trang render lại ra nhiễu là dấu hiệu điển hình của hai bug halftone này:

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;

Khi mask hay chuyển đổi màu ép buộc fallback qua render, item quay về dạng bitmap đã giải mã và decoder halftone có chạy thật. Thêm về image list nằm trong trích văn bản, ảnh và font PDF trong Delphi

Tra nhanh: quy tắc lưới halftone JBIG2

• Đánh chỉ số mask skip dạng HSKIP[ng, mg], cột lưới trước, và đọc lại cùng thứ tự ở mọi nơi đặt ô (T.88 §6.6.5.1, đã sửa trong PDFlibPas v3.539.37)
• Thử mọi code halftone hay lưới với một lưới không vuông và một tập ô ngoài region không đối xứng, vì lưới vuông có thể che hoàn toàn một chỉ số bị chuyển vị
• Đọc HGX và HGY như các giá trị 32-bit có dấu (T.88 §7.4.5.1.2), đừng bao giờ qua một helper không dấu kẹp giá trị âm
• Dịch >> 8 của chuẩn thành một phép chia floor cho 256, không phải shr 8 cũng không phải div 256
• Chạy phép thử skip trên vị trí pixel đã dịch; dạng fixed-point khác đi mỗi khi phần lẻ khác 0, như HGX = -900 với pattern 4 pixel cho thấy
• Cộng dồn tọa độ lưới trong Int64 và kẹp lại trước khi đưa cho code bitmap, để một lưới hỏng không thể gây tràn số
• Nâng lên v3.539.38 trở lên nếu tài liệu của bạn có halftone region với HENABLESKIP, gốc lưới âm hay lưới xoay

PDFlibPas render, trích xuất và chỉnh sửa tài liệu PDF từ Delphi và C++Builder với một decoder JBIG2 thuần Pascal nay xử lý mask skip halftone, gốc lưới âm và lưới xoay đúng như T.88 chỉ định. Xem PDFlibPas Delphi PDF library để biết tính năng, phiên bản và bản dùng thử