Tabele Huffman personalizate în decodorul JBIG2 Pascal pur

PDFlibPas versiunea 3.539.22 decodează nativ tabelele Huffman personalizate JBIG2: decodorul în Pascal pur din PDFlibJBIG2.pas parsează segmentul Tables (tip 53), atribuie codurile prefix canonice în ordinea liniilor din tabel așa cum cere ITU-T T.88 Anexa B.3, consumă referințele la tabelele personalizate în ordinea selectoarelor pentru dicționarele de simboluri și regiunile de text, și mărginește fiecare citire după lungimea declarată a segmentului, nu după ce octeți se nimerește să urmeze

Fișierul care a forțat munca asta nu avea nimic ieșit din comun la suprafață. Un contract scanat, comprimat JBIG2 cu codare Huffman de simboluri în loc de codarea aritmetică mult mai răspândită, iar encoderul livra propriile tabele de coduri în locul tabelelor standard B.1 până la B.15. Doi decodorii independenți nu cădeau de acord asupra pixelilor de rafinare, iar decodorul PDFlibPas de atunci producea text care arăta ca trecut prin tocător: fragmente de glif deplasate cu câțiva pixeli, o coloană lipsă la fiecare caracter. Nimic nu ridica vreo eroare. Asta este forma de bug care supraviețuiește ani de zile, pentru că un decodor care respinge un fișier primește un tichet de suport, în timp ce un decodor care îl randează ușor greșit primește un client care presupune că scanarea a fost proastă

Ce conține de fapt un segment Tables JBIG2?

Un segment Tables este o descriere compactă a unui singur tabel Huffman: un octet de flag-uri, două limite cu semn pe 32 de biți, apoi o serie de perechi (lungime prefix, lungime interval) care partiționează intervalul dintre limite, așa cum e descris în T.88 §7.4.13 și Anexa B.2. Bitul 0 al octetului de flag-uri este HTOOB și spune dacă tabelul are un cod în afara benzii. Biții 1-3 plus unu dau HTPS, numărul de biți folosiți pentru a scrie fiecare lungime de prefix; biții 4-6 plus unu dau HTRS, lățimea fiecărui câmp de lungime de interval. Bitul 7 este rezervat, iar PDFlibPas respinge segmentul dacă este setat, în loc să ghicească ce a vrut să însemne într-o revizie viitoare. HTLOW și HTHIGH urmează ca întregi cu semn pe 32 de biți, și aici greșește un decodor prima dată: citite ca fără semn, fac un tabel a cărui limită inferioară este negativă, perfect normal pentru lățimi de simbol codate diferențial, să pară că începe la patru miliarde. Fiecare câmp trece printr-un helper local ReadField care verifică cererea față de poziția de bit unde se termină datele segmentului înainte de a atinge cititorul, pentru că un tabel care citește dincolo de segmentul său ar consuma header-ul segmentului următor drept lungimi de 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 cu semn
HighValue  := Integer(ReadField(32));      // HTHIGH cu semn
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);

Cele două linii adăugate după buclă sunt liniile de evadare din Anexa B.2: linia de interval inferioară începe la HTLOW minus unu și numără în jos, linia de interval superioară începe la HTHIGH cu un interval fix pe 32 de biți, iar linia OOB opțională nu are nicio valoare. PDFlibPas le marchează cu lungimile de interval santinelă jbig2HuffmanLOW ($FFFFFFFD) și jbig2HuffmanOOB ($FFFFFFFE), aceeași convenție pe care o folosesc cele cincisprezece tabele standard integrate, așa că buclei de decodare nu-i pasă dacă un tabel vine din specificație sau din fișier

De ce trebuie atribuite codurile prefix în ordinea liniilor din tabel?

Pentru că encoderul nu scrie niciodată codurile. Un segment Tables JBIG2 cară doar lungimi de prefix, iar ambele părți reconstruiesc tiparele de biți reale cu procedura canonică din Anexa B.3: numără câte linii au fiecare lungime, atribuie întâi codurile de lungime unu, apoi deplasează la stânga și continuă, iar în cadrul aceleiași lungimi distribuie codurile în ordinea în care apar liniile. Orice abatere de la ordinea aceea produce în tăcere un tabel diferit. Decodorul nu va observa, pentru că fiecare tipar de biți pe care îl generează este tot un cod prefix valid, doar că nu cel folosit de encoder, iar ieșirea este un bitmap plauzibil la vedere, asamblat din simbolurile greșite

// 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            // stabil: ordinea originală păstrată
  if table[I].prefixLen > 0 then       // în cadrul fiecărei lungimi de 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 este o sortare prin numărare, nu una prin comparație, dintr-un singur motiv: o trecere de numărare peste Counts, Starts și Positions este stabilă prin construcție, așa că liniile cu aceeași lungime de prefix ajung în rezultat în ordinea în care au fost declarate, care este exact ordinea după care atribuie Anexa B.3 codurile. Liniile cu lungime de prefix zero sunt eliminate înainte de atribuirea codurilor, pentru că B.3 le definește ca nefolosite, nu ca pe niște coduri de un bit. Două paze stau în aceeași buclă. Verificarea de suprapopulare prinde un tabel ale cărui lungimi pretind mai multe coduri decât poate ține un cod prefix de adâncimea aceea, adică inegalitatea Kraft exprimată ca o comparație de întregi; fără ea, un tabel ostil produce un cod care se potrivește cu două linii, iar decodorul o alege pe cea pe care o scanează prima. Plafonul de 32 de biți există pentru că prefix este un Cardinal, iar potrivitorul din decodeInt acumulează biți într-unul singur. T.88 permite pe hârtie prefixe mai lungi, PDFlibPas le respinge pe nume, iar un encoder real care să emită vreunul nu s-a văzut. Aritmetica valorilor are nevoie de aceeași grijă ca aritmetica codurilor: THuffmanTable.val este un Int64, iar linia de interval inferioară se decodează ca val - readBits(32), un offset fără semn pe 32 de biți scăzut din HTLOW minus unu. Cu intermediari Integer, scăderea aceea se învârte, iar valoarea învârtită este apoi acceptată drept lățime de simbol. Calea pe 64 de biți calculează valoarea adevărată, o verifică față de intervalul cu semn pe 32 de biți și ridică excepție dacă nu încape, ceea ce transformă o corupere tăcută într-un refuz explicit

De ce nu s-au activat niciodată tabelele personalizate înainte de 3.539.22?

Două defecte se ascundeau unul pe celălalt. Primul era un bug de setter de o linie: TTextRegionHuffmanFlags.setFlags își primea argumentul sub același nume ca câmpul în care îl scria, așa că Self.flagsAsInt := flagsAsInt atribuia câmpul neinițializat lui însuși și fiecare selector se citea înapoi ca zero, ceea ce trimitea regiunile de text care cereau tabele personalizate prin tabelele standard F, H și K. Al doilea defect însemna că repararea doar a primului ar fi produs tot simboluri corupte. Când un dicționar de simboluri Huffman își stochează simbolurile ca bitmap colectiv necomprimat, ultimul octet al fiecărui rând este parțial, iar bucla veche de copiere trata padding, care ține numărul de biți valizi, drept poziția celui mai de jos bit valid; un rând lat de 63 de pixeli copia un bit din octetul final în loc de șapte. Bucla corectată rulează for bitPointer := 7 downto ((8 - padding) and 7), iar fixture-urile sintetice la lățimi de 7 și 9 biți fixează ambele părți ale graniței de octet. Cu selectoarele citindu-se corect, tabelele se distribuie în ordinea în care le listează specificația, pe care T.88 §7.4.3.1.2 o fixează pentru regiunile de text ca FS, DS, DT, RDW, RDH, RDX, RDY și RSIZE, iar §7.4.2.1.1 pentru dicționarele de simboluri ca DH, DW, BMSIZE și AGGINST. Fiecare selector de doi biți înseamnă tabelul standard 0 sau 1, rezervat pentru 2 pe câmpurile cu doar două tabele standard, și personalizat pentru 3, iar fiecare selecție personalizată consumă următorul segment Tables dintre segmentele referite, în ordinea referirii. NextCustomHuffmanTable face exact parcurgerea aceea și ridică missing custom Huffman table reference când o regiune referă mai puține tabele decât cer selectoarele sale. Încă o linie ține de aceeași reparație: un dicționar de simboluri Huffman ale cărui simboluri de intrare și noi se adună la unu calculează o lungime de cod de simbol de zero din formula log2, în timp ce varianta Huffman a formatului scrie fiecare ID de simbol cu cel puțin un bit, așa că if sdHuffman and (symbolCodeLength = 0) then symbolCodeLength := 1 din TSymbolDictionarySegment oprește calea de rafinare și de agregare să citească zero biți pe ID de simbol

Ce garantează granița de segment?

PDFlibPas tratează lungimea datelor de segment din fiecare header ca pe un contract pe care ambele direcții trebuie să îl respecte: un segment nu poate citi dincolo de sfârșitul declarat și nu se poate termina mai devreme, lăsând header-ul următor la un offset imprevizibil. Regulile care ies din contractul acela sunt fiecare mici. O lungime de date cu bitul 31 setat este marcajul de lungime necunoscută din T.88 §7.2.7, iar handleSegmentDataLength îl mapează la o valoare negativă pe care readSegments o respinge direct, în loc să scaneze înainte după un terminator. Fiecare număr de segment referit trebuie să fie mai mic decât numărul segmentului curent și trebuie să existe deja, așa că o referință înainte sau căzută în gol eșuează înainte ca vreo regiune să încerce să o rezolve. END_OF_PAGE și END_OF_FILE trebuie să declare zero octeți de date. Un segment Profiles (tip 52) cară un contor pe 32 de biți urmat de atâtea identificatoare pe 32 de biți și de niciun pixel, așa că este verificat ca 4 plus 4 ori contorul față de lungimea declarată, sărit, și ținut în lista de segmente doar ca segmentele ulterioare să poată referi la el după număr. Un identificator de profil necunoscut nu este o codare necunoscută, iar tratarea lui ca atare ar respinge fișiere care se decodează perfect bine

// 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');
// ... creează obiectul de segment pentru tipul acesta ...
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 poate lăsa EOFB necitit
  reader.bitPointer := 7;
end;

Coada buclei aceleia este locul unde o versiune anterioară a decodorului greșea pe regiunile codate MMR. Un decodor MMR știe că a terminat când ultimul pixel din ultimul rând este produs, ceea ce se poate întâmpla înainte să fi consumat terminatorul EOFB pe care T.88 §6.2.5.7 îl pune la sfârșitul datelor. Codul vechi presupunea că cititorul era poziționat la header-ul următor, așa că octeții de terminator rămași erau parsați drept număr de segment și stream-ul eșua câțiva octeți mai încolo, cu o eroare înșelătoare. Acum câștigă sfârșitul declarat: citirea dincolo de el este o eroare, oprirea mai devreme este normală, iar cititorul este mutat la DataEnd cu pointerul de bit resetat, ca header-ul următor să fie citit de acolo de unde fișierul a spus că va fi. Aceeași disciplină apare oriunde PDFlibPas parsează structuri PDF nedemne de încredere: lungimea declarată este granița, iar decodorul nu pleacă să caute una mai prietenoasă

De unde citește rafinarea Huffman dimensiunea bitmap-ului?

Înainte să pornească decodorul aritmetic, și dintr-un câmp care există doar în modul Huffman. Când o instanță de regiune de text cară rafinare (RI diferit de zero) și SBHUFF este setat, T.88 §6.4.11 îi cere decodorului să citească RDW, RDH, RDX și RDY cu tabelele lor selectate, apoi BMSIZE cu tabelul RSIZE, apoi să alinieze la o graniță de octet și abia apoi să ruleze decodarea generică de rafinare peste exact BMSIZE octeți. Regiunile de text în mod aritmetic nu au un astfel de câmp, iar un decodor care împarte o singură cale de cod pentru ambele moduri îl sare, pornește decodorul aritmetic cu doi sau mai mulți octeți prea devreme și rafinează fiecare simbol pe gunoi. Calea de dicționar de simboluri cu REFAGG și o singură instanță de rafinare, descrisă în §6.5.8.2.2, are același câmp BMSIZE cu aceleași consecințe. În PDFlibPas, limita superioară pentru dimensiunea aceea este TStreamReader.SegmentEnd, sfârșitul segmentului curent așa cum a fost stabilit de readSegments, nu sfârșitul întregului stream, pentru că un BMSIZE care poate fi satisfăcut doar împrumutând octeți din segmentul următor este malformat, iar validarea lui față de lungimea stream-ului ar lăsa decodorul aritmetic să citească în header-ul următor. Limita inferioară de doi octeți reflectă perechea inițială de octeți pe care decodorul aritmetic o consumă mereu, iar după rafinare cititorul sare la RefinementEnd indiferent cât de departe a citit înainte decodorul aritmetic, pentru că poziția lui finală nu este poziția următorului câmp codat Huffman

// Decodarea regiunii de text TJBIG2Bitmap, calea de rafinare 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;

Ce s-a verificat și ce se mai refuză

Eșantionul care a pornit toată treaba, o imagine JBIG2 de 500 pe 473 de pixeli cu tabele personalizate și rafinare Huffman, se decodează acum într-un bitmap cu zero pixeli diferiți față de un decodor independent, iar fixture-urile sintetice de bitmap colectiv la 7 și 9 biți produc rândurile așteptate pe amândouă. Cei doi decodorii independenți care nu cădeau de acord pe eșantionul original încă nu cad de acord între ei; PDFlibPas se potrivește cu unul dintre ei, iar afirmația onestă este că ieșirea nativă este de acord cu o implementare independentă și cu specificația citită, nu că toți decodorii din lume sunt de acord. Partea de fișiere malformate din suită acoperă:

• un bit de flag rezervat sau o valoare rezervată de selector
• un tabel trunchiat la mijlocul unei linii
• lungimi de prefix suprapopulate și prefixe mai lungi de 32 de biți
• o regiune ale cărei selectoare cer mai multe tabele personalizate decât referă
• confirmarea că ieșirea veche este curățată după o decodare eșuată, în loc să rămână pe loc ca apelantul să o confunde cu un rezultat

Trei limite rămân deliberate. Organizarea de stream cu acces aleator, unde toate header-ele de segment preced toate datele de segment, ridică JBIG2 random-access organisation is not supported imediat ce flag-urile de header de fișier sunt citite, pentru că nu există niciun eșantion reprezentativ față de care să o validezi, iar o cale pe jumătate implementată este mai rea decât un refuz pe nume. Tabelele personalizate sunt plafonate la 65.536 de linii și prefixe pe 32 de biți. Iar intrarea publică de decodare, TPLJBIG2Decoder.LoadFromByteArray, întoarce primul bitmap de pagină în ordinea stream-ului prin getPageAsJBIG2Bitmap(0), primul segment de informații de pagină întâlnit, în loc să caute asocierea de pagină zero; stream-urile PDF încorporate își numerotează de regulă pagina unică cu 1, iar cererea paginii 0 după asociere nu ar găsi nimic. Textul de eroare ajunge în TPLJBIG2Decoder.LastError, diagnosticul intern al decodorului care cară numărul segmentului, tipul și offsetul de octet al defectului, și nu este același lucru cu TPDFlib.LastErrorCode de la nivel de librărie. Nimic din toate astea nu atinge partea de codare, acoperită în notele despre backend-urile de encoder JBIG2 și felul în care sunt linkate; calea de citire trebuie să accepte orice a decis encoderul altcuiva să emită, și își împarte regulile cu restul stivei de imagini, inclusiv decodorul TIFF integrat și refuzurile sale pentru BigTIFF și aspectul cu plăci: refuză pe nume, nu împrumuta niciodată octeți peste o graniță declarată și ține aritmetica destul de lată încât un intermediar învârtit să nu poată trece drept răspuns valid. Dacă evaluați o cale nativă de citire JBIG2 pentru Delphi sau C++Builder, decodorul și restul manipulării imaginilor sunt documentate pe pagina PDF Library for Delphi