Bộ giải mã PDFlibPas xử lý bảng Huffman tùy biến JBIG2

PDFlibPas phiên bản 3.539.22 giải mã bảng Huffman tùy biến của JBIG2 ngay trong mã nguồn: bộ giải mã thuần Pascal trong PDFlibJBIG2.pas phân tích segment Tables (type 53), gán prefix code chuẩn tắc theo đúng thứ tự dòng trong bảng như ITU-T T.88 Annex B.3 yêu cầu, tiêu thụ các tham chiếu bảng tùy biến theo thứ tự selector cho symbol dictionary và text region, và chặn mọi lần đọc bằng độ dài segment đã khai báo chứ không bằng đại khái số byte nằm ngay sau đó

Tệp buộc phải làm việc này ngoài mặt chẳng có gì đặc biệt. Một hợp đồng scan, nén JBIG2 bằng Huffman symbol coding chứ không phải arithmetic coding phổ biến hơn nhiều, và bộ mã hóa mang theo bảng mã riêng thay vì dùng các bảng chuẩn B.1 tới B.15. Hai bộ giải mã độc lập bất đồng về các pixel refinement của nó, còn bộ giải mã PDFlibPas thời điểm đó cho ra văn bản trông như bị xé vụn: các mảnh glyph lệch đi vài pixel, mỗi ký tự mất một cột. Không có gì báo lỗi. Đó chính là dạng bug sống sót hàng năm trời, vì bộ giải mã từ chối tệp thì nhận được ticket hỗ trợ, còn bộ giải mã hiển thị sai một chút thì nhận được một khách hàng tin rằng bản scan vốn đã xấu

Một segment Tables của JBIG2 thực chất chứa gì?

Một segment Tables là bản mô tả gọn của một bảng Huffman: một byte flags, hai cận 32 bit có dấu, rồi một dãy cặp (độ dài prefix, độ dài range) chia khoảng giữa hai cận đó, đúng theo bố cục ở T.88 §7.4.13 và Annex B.2. Bit 0 của byte flags là HTOOB, cho biết bảng có mã out-of-band hay không. Bit 1 tới 3 cộng một cho ra HTPS, số bit dùng để ghi mỗi độ dài prefix; bit 4 tới 6 cộng một cho ra HTRS, độ rộng của mỗi trường độ dài range. Bit 7 là bit dành riêng, và PDFlibPas từ chối segment nếu bit đó được bật thay vì đoán xem một bản sửa đổi tương lai muốn nói gì. Tiếp theo là HTLOW và HTHIGH dưới dạng số nguyên 32 bit có dấu, và đây là chỗ đầu tiên bộ giải mã có thể sai: đọc chúng như số không dấu sẽ biến một bảng có cận dưới âm — chuyện hoàn toàn bình thường với độ rộng symbol mã hóa delta — thành một bảng như thể bắt đầu từ bốn tỷ. Mọi trường đều đi qua helper ReadField cục bộ, hàm này đối chiếu yêu cầu với vị trí bit kết thúc dữ liệu segment trước khi chạm vào bộ đọc, vì một bảng đọc vượt quá segment của nó sẽ tiêu thụ luôn header của segment kế tiếp như thể đó là các độ dài prefix

// TCodeTableSegment.readSegment, PDFlibJBIG2.pas
EndBit := (Int64(decoder.reader.bytePointer) +
  segmentHeader.getSegmentDataLength) * 8;
Flags := ReadField(8);
if (Flags and $80) <> 0 then
  raise EJBIG2DecodeError.Create('reserved custom Huffman table flag');
PrefixBits := ((Flags shr 1) and 7) + 1;   // HTPS
RangeBits  := ((Flags shr 4) and 7) + 1;   // HTRS
LowValue   := Integer(ReadField(32));      // HTLOW có dấu
HighValue  := Integer(ReadField(32));      // HTHIGH có dấu
if LowValue >= HighValue then
  raise EJBIG2DecodeError.Create('invalid custom Huffman range bounds');
CurrentValue := LowValue;
while CurrentValue < HighValue do
begin
  PrefixLength := ReadField(PrefixBits);
  RangeLength  := ReadField(RangeBits);
  if RangeLength > 32 then
    raise EJBIG2DecodeError.Create('invalid custom Huffman range length');
  AddLine(CurrentValue, PrefixLength, RangeLength);
  Inc(CurrentValue, Int64(1) shl RangeLength);
end;
AddLine(LowValue - 1, ReadField(PrefixBits), jbig2HuffmanLOW);
AddLine(HighValue,   ReadField(PrefixBits), 32);
if (Flags and 1) <> 0 then
  AddLine(0, ReadField(PrefixBits), jbig2HuffmanOOB);

Hai dòng được thêm vào sau vòng lặp là các dòng escape từ Annex B.2: dòng range dưới bắt đầu từ HTLOW trừ một và đếm ngược xuống, dòng range trên bắt đầu từ HTHIGH với range cố định 32 bit, còn dòng OOB tùy chọn thì không mang giá trị nào cả. PDFlibPas đánh dấu chúng bằng các độ dài range sentinel jbig2HuffmanLOW ($FFFFFFFD) và jbig2HuffmanOOB ($FFFFFFFE), đúng quy ước mà mười lăm bảng chuẩn tích hợp của nó đang dùng, nên vòng lặp giải mã không cần biết bảng đến từ đặc tả hay từ chính tệp

Vì sao prefix code buộc phải được gán theo thứ tự dòng trong bảng?

Vì bộ mã hóa không bao giờ ghi ra các mã. Một segment Tables của JBIG2 chỉ mang độ dài prefix, và cả hai bên đều dựng lại mẫu bit thật bằng thủ tục chuẩn tắc trong Annex B.3: đếm xem mỗi độ dài có bao nhiêu dòng, cấp mã độ dài một trước, rồi dịch trái và đi tiếp, và trong cùng một độ dài thì phát mã theo thứ tự các dòng xuất hiện. Lệch khỏi thứ tự đó sẽ âm thầm tạo ra một bảng khác. Bộ giải mã sẽ không nhận ra, vì mọi mẫu bit nó sinh ra vẫn là prefix code hợp lệ, chỉ có điều không phải mẫu mà bộ mã hóa đã dùng, và đầu ra là một bitmap trông có vẻ hợp lý được ghép từ những symbol sai

// THuffmanDecoder.buildTable, PDFlibJBIG2.pas
FillChar(Counts, SizeOf(Counts), 0);
for I := 0 to length - 1 do
begin
  if table[I].prefixLen > 32 then
    raise EJBIG2DecodeError.Create(
      'Huffman prefixes longer than 32 bits are not supported');
  Inc(Counts[table[I].prefixLen]);
end;
Active := 0;
Code := 0;
for Bits := 1 to 32 do
begin
  Starts[Bits]    := Active;
  Positions[Bits] := Active;
  Inc(Active, Counts[Bits]);
  if Code + UInt64(Counts[Bits]) > (UInt64(1) shl Bits) then
    raise EJBIG2DecodeError.Create('oversubscribed Huffman prefix codes');
  Code := (Code + UInt64(Counts[Bits])) shl 1;
end;
SetLength(Result, Active + 1);
for I := 0 to length - 1 do            // ổn định: giữ nguyên thứ tự gốc
  if table[I].prefixLen > 0 then       // trong từng độ dài prefix
  begin
    Result[Positions[table[I].prefixLen]] := table[I];
    Inc(Positions[table[I].prefixLen]);
  end;
Code := 0;
for Bits := 1 to 32 do
begin
  for I := Starts[Bits] to Positions[Bits] - 1 do
  begin
    Result[I].prefix := Cardinal(Code);
    Inc(Code);
  end;
  Code := Code shl 1;
end;
Result[Active].rangeLen := jbig2HuffmanEOT;

THuffmanDecoder.buildTable là counting sort chứ không phải comparison sort vì một lý do: một lượt đếm trên Counts, Starts và Positions ổn định theo cấu trúc, nên các dòng có cùng độ dài prefix rơi vào kết quả theo đúng thứ tự chúng được khai báo, mà đó chính là thứ tự Annex B.3 dùng để cấp mã. Những dòng có độ dài prefix bằng không bị loại trước khi cấp mã, vì B.3 định nghĩa chúng là không dùng đến chứ không phải mã một bit. Hai chốt chặn nằm ngay trong cùng vòng lặp đó. Phép kiểm tra vượt sức chứa bắt những bảng mà các độ dài khai nhiều mã hơn mức một prefix code ở độ sâu đó có thể chứa, tức bất đẳng thức Kraft viết dưới dạng so sánh số nguyên; thiếu nó thì một bảng thù địch tạo ra mã khớp với hai dòng và bộ giải mã chọn dòng nào nó quét tới trước. Còn trần 32 bit tồn tại vì prefix là một Cardinal và bộ so khớp trong decodeInt dồn bit vào đúng một biến đó. T.88 trên giấy cho phép prefix dài hơn, PDFlibPas từ chối thẳng tên, và chưa từng thấy bộ mã hóa thực tế nào phát ra như vậy. Số học giá trị cũng cần được chăm như số học mã: THuffmanTable.val là một Int64, và dòng range dưới được giải mã thành val - readBits(32), tức một offset không dấu 32 bit bị trừ khỏi HTLOW trừ một. Với các giá trị trung gian kiểu Integer, phép trừ đó sẽ tràn vòng, và giá trị tràn vòng lại được chấp nhận như một độ rộng symbol. Đường 64 bit tính ra giá trị thật, đối chiếu với khoảng 32 bit có dấu, và raise nếu không vừa, biến một lỗi âm thầm thành một lời từ chối rõ ràng

Vì sao bảng tùy biến chưa từng kích hoạt trước 3.539.22?

Hai khiếm khuyết che nhau. Cái thứ nhất là bug setter một dòng: TTextRegionHuffmanFlags.setFlags nhận tham số trùng tên với chính trường mà nó ghi vào, nên Self.flagsAsInt := flagsAsInt gán trường chưa khởi tạo cho chính nó và mọi selector đọc về đều bằng không, khiến các text region xin bảng tùy biến lại đi qua bảng chuẩn F, H và K. Khiếm khuyết thứ hai có nghĩa là chỉ sửa cái đầu thì vẫn cho ra symbol hỏng. Khi một symbol dictionary kiểu Huffman lưu các symbol dưới dạng collective bitmap không nén, byte cuối của mỗi dòng là byte dở dang, và vòng lặp copy cũ coi padding — thứ giữ số bit hợp lệ — là vị trí của bit hợp lệ thấp nhất; một dòng rộng 63 pixel vì thế copy đúng một bit từ byte cuối thay vì bảy bit. Vòng lặp đã sửa chạy for bitPointer := 7 downto ((8 - padding) and 7), và các fixture tổng hợp ở độ rộng 7 bit lẫn 9 bit chốt cả hai phía của ranh giới byte. Khi các selector đọc đúng, bảng được phát theo đúng thứ tự đặc tả liệt kê: T.88 §7.4.3.1.2 cố định cho text region là FS, DS, DT, RDW, RDH, RDX, RDY và RSIZE, còn §7.4.2.1.1 cố định cho symbol dictionary là DH, DW, BMSIZE và AGGINST. Mỗi selector hai bit mang nghĩa bảng chuẩn 0 hoặc 1, giá trị 2 là dành riêng trên những trường chỉ có hai bảng chuẩn, và giá trị 3 là bảng tùy biến, và mỗi lần chọn tùy biến sẽ tiêu thụ segment Tables kế tiếp trong số các segment được tham chiếu theo đúng thứ tự tham chiếu. NextCustomHuffmanTable làm chính xác phép duyệt đó và raise missing custom Huffman table reference khi một region tham chiếu ít bảng hơn số mà các selector của nó đòi. Còn một dòng nữa thuộc cùng bản sửa: một symbol dictionary kiểu Huffman mà input và new symbol cộng lại bằng một sẽ tính ra độ dài mã symbol bằng không từ công thức log2, trong khi biến thể Huffman của định dạng ghi mọi symbol ID bằng ít nhất một bit, nên if sdHuffman and (symbolCodeLength = 0) then symbolCodeLength := 1 trong TSymbolDictionarySegment giữ cho đường refinement và aggregate không đọc không bit cho mỗi symbol ID

Ranh giới segment bảo đảm điều gì?

PDFlibPas coi độ dài dữ liệu segment trong mọi header là một khế ước mà cả hai chiều đều phải tôn trọng: segment không được đọc vượt quá điểm kết thúc đã khai báo, và cũng không được kết thúc sớm rồi để header kế tiếp ở một offset không đoán trước. Những quy tắc rút ra từ khế ước đó đều nhỏ. Một độ dài dữ liệu có bit 31 bật là dấu unknown-length của T.88 §7.2.7, và handleSegmentDataLength ánh xạ nó thành giá trị âm mà readSegments từ chối thẳng thay vì quét tới tìm dấu kết thúc. Mọi số segment được tham chiếu đều phải nhỏ hơn số segment hiện tại và phải đã tồn tại, nên một tham chiếu tới phía trước hay tham chiếu treo sẽ hỏng trước khi bất kỳ region nào thử phân giải nó. END_OF_PAGE và END_OF_FILE phải khai báo không byte dữ liệu. Một segment Profiles (type 52) mang một bộ đếm 32 bit theo sau là bấy nhiêu định danh 32 bit và không có pixel nào, nên nó được kiểm tra bằng 4 cộng 4 nhân bộ đếm so với độ dài đã khai, bị bỏ qua, và chỉ được giữ trong danh sách segment để các segment sau vẫn tham chiếu được nó theo số. Một định danh profile lạ không phải một kiểu mã hóa lạ, và coi nó là như vậy sẽ từ chối những tệp giải mã hoàn toàn tốt

// TJBIG2StreamDecoder.readSegments, PDFlibJBIG2.pas
DataLength := segmentHeader.getSegmentDataLength;
if DataLength < 0 then
  raise EJBIG2DecodeError.Create(Context +
    'unknown or oversized segment length is not supported');
if DataLength > Length(reader.Data) - reader.bytePointer then
  raise EJBIG2DecodeError.Create(Context + 'truncated segment data');
DataEnd := reader.bytePointer + DataLength;
for I := 0 to noOfReferredToSegments - 1 do
  if (referredToSegments[I] >= segmentHeader.getSegmentNumber) or
     (findSegment(referredToSegments[I]) = nil) then
    raise EJBIG2DecodeError.Create(Context + 'invalid segment reference');
// ... tạo đối tượng segment cho type này ...
reader.SegmentEnd := DataEnd;
segment.readSegment;
if reader.bytePointer > DataEnd then
  raise EJBIG2DecodeError.Create(Context +
    'decoded data exceeds declared segment length');
if reader.bytePointer < DataEnd then
begin
  reader.bytePointer := DataEnd;   // MMR có thể để EOFB chưa đọc
  reader.bitPointer := 7;
end;

Đoạn cuối của vòng lặp đó là chỗ một phiên bản trước của bộ giải mã xử lý sai các region mã hóa MMR. Bộ giải mã MMR biết mình xong khi pixel cuối cùng của dòng cuối cùng được tạo ra, và điều đó có thể xảy ra trước khi nó tiêu thụ dấu kết thúc EOFB mà T.88 §6.2.5.7 đặt ở cuối dữ liệu. Đoạn mã cũ giả định bộ đọc đang nằm ngay tại header kế tiếp, nên các byte kết thúc còn sót bị phân tích như một số segment và stream hỏng thêm vài byte sau đó với một thông báo lỗi đánh lạc hướng. Giờ thì điểm kết thúc đã khai thắng: đọc vượt qua nó là lỗi, dừng sớm là bình thường, và bộ đọc được đưa tới DataEnd cùng bit pointer được đặt lại để header kế tiếp được đọc từ đúng chỗ mà tệp nói nó nằm. Kỷ luật này xuất hiện ở mọi nơi PDFlibPas phân tích các cấu trúc PDF không đáng tin: độ dài đã khai là ranh giới, và bộ giải mã không đi tìm một ranh giới dễ chịu hơn

Đường refinement kiểu Huffman đọc kích thước bitmap ở đâu?

Trước khi bộ giải mã số học khởi động, và từ một trường chỉ tồn tại ở chế độ Huffman. Khi một instance text region mang refinement (RI khác không) và SBHUFF được bật, T.88 §6.4.11 buộc bộ giải mã đọc RDW, RDH, RDX và RDY bằng các bảng đã chọn, rồi đọc BMSIZE bằng bảng RSIZE, rồi căn về ranh giới byte, và chỉ sau đó mới chạy phép giải mã refinement tổng quát trên đúng BMSIZE byte. Text region ở chế độ số học không có trường đó, và một bộ giải mã dùng chung một đường mã cho cả hai chế độ sẽ bỏ qua nó, khởi động bộ giải mã số học sớm hai byte hoặc hơn, và refine mọi symbol dựa trên rác. Đường symbol dictionary với REFAGG và một refinement instance duy nhất, được mô tả ở §6.5.8.2.2, cũng có đúng trường BMSIZE đó với hậu quả y hệt. Trong PDFlibPas, cận trên của kích thước đó là TStreamReader.SegmentEnd, tức điểm kết thúc segment hiện tại do readSegments đặt, chứ không phải điểm kết thúc của cả stream, vì một BMSIZE chỉ có thể thỏa mãn bằng cách vay byte từ segment sau là dữ liệu hỏng, và đối chiếu nó với độ dài stream sẽ cho phép bộ giải mã số học đọc lấn vào header kế tiếp. Cận dưới hai byte phản ánh cặp byte khởi đầu mà bộ giải mã số học luôn tiêu thụ, và sau khi refine, bộ đọc nhảy thẳng tới RefinementEnd bất kể bộ giải mã số học đã đọc trước bao xa, vì vị trí cuối của nó không phải vị trí của trường mã hóa Huffman kế tiếp

// Giải mã text region của TJBIG2Bitmap, đường refinement kiểu Huffman
RefinementSize := huffmanDecoder.decodeInt(huffmanRSizeTable).intResult;
huffmanDecoder.consumeRemainingBits;
if (RefinementSize < 2) or
   (RefinementSize > huffmanDecoder.reader.SegmentEnd -
                     huffmanDecoder.reader.bytePointer) then
  raise EJBIG2DecodeError.Create('invalid refinement bitmap size');
RefinementEnd := huffmanDecoder.reader.bytePointer + RefinementSize;
arithmeticDecoder.start;
// ... readGenericRefinementRegion ...
if huffmanDecoder.reader.bytePointer > RefinementEnd then
  raise EJBIG2DecodeError.Create('refinement data exceeds declared size');
huffmanDecoder.reader.bytePointer := RefinementEnd;
huffmanDecoder.reader.bitPointer := 7;

Đã kiểm chứng những gì, và những gì vẫn bị từ chối

Mẫu khởi nguồn cho tất cả chuyện này, một ảnh JBIG2 500 x 473 pixel với bảng tùy biến và refinement kiểu Huffman, giờ giải mã ra bitmap không lệch một pixel nào so với một bộ giải mã độc lập, còn các fixture collective bitmap tổng hợp ở 7 bit và 9 bit đều cho ra đúng các dòng mong đợi trên cả hai. Hai bộ giải mã độc lập từng bất đồng về mẫu gốc giờ vẫn bất đồng với nhau; PDFlibPas khớp với một trong hai, và phát biểu trung thực là đầu ra native khớp với một bản cài đặt độc lập và khớp với đặc tả như đã đọc, chứ không phải mọi bộ giải mã trên đời đều đồng ý. Phần dữ liệu hỏng của bộ kiểm thử bao gồm:

• một bit flags dành riêng hoặc một giá trị selector dành riêng
• một bảng bị cắt cụt ngay giữa một dòng
• các độ dài prefix vượt sức chứa và các prefix dài hơn 32 bit
• một region có các selector đòi nhiều bảng tùy biến hơn số nó tham chiếu
• xác nhận rằng đầu ra cũ bị xóa sau một lần giải mã thất bại thay vì để nguyên cho bên gọi nhầm thành kết quả

Ba giới hạn vẫn được giữ có chủ đích. Tổ chức stream theo kiểu random-access, nơi mọi header segment đứng trước toàn bộ dữ liệu segment, sẽ raise JBIG2 random-access organisation is not supported ngay khi các flag ở file header được đọc, vì không có mẫu tiêu biểu nào để đối chiếu và một đường cài đặt nửa vời còn tệ hơn một lời từ chối có tên. Bảng tùy biến bị giới hạn ở 65.536 dòng và prefix 32 bit. Còn điểm vào giải mã công khai, TPLJBIG2Decoder.LoadFromByteArray, trả về bitmap của trang đầu theo thứ tự trong stream qua getPageAsJBIG2Bitmap(0), tức segment page-information đầu tiên gặp được, chứ không tra theo page association bằng không; các stream PDF nhúng thường đánh số trang duy nhất của chúng là 1, và hỏi trang 0 theo association sẽ chẳng tìm thấy gì. Văn bản lỗi nằm trong TPLJBIG2Decoder.LastError, chẩn đoán nội bộ của bộ giải mã mang số segment, type và byte offset của chỗ hỏng, và không phải cùng thứ với TPDFlib.LastErrorCode ở tầng thư viện. Không phần nào ở đây đụng tới phía mã hóa, vốn được bàn trong ghi chú về các backend encoder JBIG2 và cách chúng được liên kết; đường đọc phải chấp nhận bất cứ thứ gì bộ mã hóa của người khác quyết định phát ra, và nó chia sẻ quy tắc với phần còn lại của hệ thống xử lý ảnh, kể cả bộ giải mã TIFF tích hợp cùng các lời từ chối với BigTIFF và bố cục tiled: từ chối có tên, không bao giờ vay byte qua một ranh giới đã khai, và giữ phép tính đủ rộng để một giá trị trung gian tràn vòng không thể lọt qua như một đáp án hợp lệ. Nếu bạn đang cân nhắc một đường đọc JBIG2 native cho Delphi hay C++Builder, bộ giải mã cùng phần còn lại của khâu xử lý ảnh được ghi lại trên trang PDF Library for Delphi