JBIG2 custom Huffman tabele u čistom Pascal PDF dekoderu

PDFlibPas verzija 3.539.22 dekodira JBIG2 custom Huffman tabele nativno: čist Pascal dekoder u PDFlibJBIG2.pas parsira Tables segment (tip 53), dodeljuje kanonske prefix kodove u redosledu linija tabele kako zahteva ITU-T T.88 Aneks B.3, troši reference na custom tabele u redosledu selektora za symbol dictionary-je i text region-e, i ograničava svako čitanje deklarisanom dužinom segmenta, a ne bajtovima koji se slučajno nađu posle

Fajl koji je pokrenuo ovaj rad na površini nije bio ništa posebno. Skenerom snimljen ugovor, JBIG2-komprimovan sa Huffman kodiranjem simbola umesto mnogo češćeg aritmetičkog kodiranja, i sa enkoderom koji šalje sopstvene kodne tabele umesto standardnih tabela B.1 do B.15. Dva nezavisna dekodera nisu se slagala oko njegovih refinement piksela, a tadašnji PDFlibPas dekoder davao je tekst koji je izgledao kao da je prošao kroz rešeto: fragmenti glifova pomereni za po nekoliko piksela, po jedna kolona nedostaje u svakom znaku. Ništa nije prijavilo grešku. To je oblik bug-a koji preživi godinama, jer dekoder koji odbije fajl dobije support tiket, a dekoder koji ga iscrta malo pogrešno dobije korisnika koji pomisli da je skeniranje bilo loše

Šta zapravo sadrži JBIG2 Tables segment?

Tables segment je kompaktan opis jedne Huffman tabele: jedan bajt flag-ova, dve označene 32-bitne granice, i zatim niz parova (dužina prefix-a, dužina opsega) koji dele interval između granica, kako je izloženo u T.88 §7.4.13 i Aneksu B.2. Bit 0 bajta flag-ova je HTOOB i kaže da li tabela ima out-of-band kod. Bitovi 1 do 3 plus jedan daju HTPS, broj bitova kojima se piše svaka dužina prefix-a; bitovi 4 do 6 plus jedan daju HTRS, širinu polja svake dužine opsega. Bit 7 je rezervisan, i PDFlibPas odbija segment ako je postavljen, umesto da pogađa šta je neka buduća revizija njime mislila. HTLOW i HTHIGH slede kao označeni 32-bitni celi brojevi, i tu dekoder prvi put može da pogreši: ako ih čita kao neoznačene, tabela čija je donja granica negativna, što je sasvim normalno za delta-kodirane širine simbola, izgleda kao da počinje od četiri milijarde. Svako polje prolazi kroz lokalni ReadField pomoćnik koji proverava zahtev prema bit poziciji na kojoj se podaci segmenta završavaju pre nego što dodirne čitač, jer bi tabela koja čita iza svog segmenta trošila header sledećeg segmenta kao dužine prefix-a

// 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));      // označeni HTLOW
HighValue  := Integer(ReadField(32));      // označeni HTHIGH
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);

Dve linije dodate posle petlje su escape linije iz Aneksa B.2: linija donjeg opsega počinje od HTLOW minus jedan i broji naniže, linija gornjeg opsega počinje od HTHIGH sa fiksiranim 32-bitnim opsegom, a opciona OOB linija nema vrednost uopšte. PDFlibPas ih obeležava sentinel dužinama opsega jbig2HuffmanLOW ($FFFFFFFD) i jbig2HuffmanOOB ($FFFFFFFE), istom konvencijom koju koristi njenih petnaest ugrađenih standardnih tabela, pa petlji dekodiranja nije važno da li tabela dolazi iz specifikacije ili iz fajla

Zašto se prefix kodovi moraju dodeljivati u redosledu linija tabele?

Zato što enkoder nikada ne piše kodove. JBIG2 Tables segment nosi samo dužine prefix-a, a obe strane rekonstruišu stvarne bit šablone kanonskim postupkom iz Aneksa B.3: prebroj koliko linija ima svaku dužinu, dodeli prvo kodove dužine jedan, pa pomeraj ulevo i nastavi, i unutar jedne dužine deli kodove redosledom kojim se linije pojavljuju. Svako odstupanje od tog redosleda tiho proizvodi drugu tabelu. Dekoder to neće primetiti, jer je svaki bit šablon koji generiše i dalje validan prefix kod, samo ne onaj koji je enkoder koristio, a izlaz je bitmap koji izgleda uverljivo a sastavljen je od pogrešnih simbola

// 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            // stabilno: zadržan originalni redosled
  if table[I].prefixLen > 0 then       // unutar svake dužine prefix-a
  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 je counting sort, a ne comparison sort, iz jednog razloga: prolaz brojanja kroz Counts, Starts i Positions je stabilan po konstrukciji, pa linije jednake dužine prefix-a sležu u rezultat redosledom kojim su deklarisane, što je upravo redosled po kojem Aneks B.3 dodeljuje kodove. Linije sa nultom dužinom prefix-a ispadaju pre dodele kodova, jer ih B.3 definiše kao neiskorišćene, a ne kao jednobitne kodove. Dva čuvara sede u istoj petlji. Provera prekoračenja hvata tabelu čije dužine traže više kodova nego što prefix kod te dubine može da primi, što je Kraft nejednakost izražena kao poređenje celih brojeva; bez nje zlonamerna tabela proizvodi kod koji odgovara dvema linijama i dekoder bira onu koju prvu pregleda. Granica od 32 bita postoji jer je prefix tipa Cardinal a matcher u decodeInt akumulira bitove u jedan. T.88 na papiru dopušta duže prefix-e, PDFlibPas ih odbija po imenu, i nije viđen nijedan pravi enkoder koji bi takav emitovao. Aritmetika vrednosti zahteva istu pažnju kao aritmetika kodova: THuffmanTable.val je Int64, a linija donjeg opsega dekodira se kao val - readBits(32), 32-bitni neoznačeni offset oduzet od HTLOW minus jedan. Sa Integer međurezultatima to oduzimanje se obavija, a obavijena vrednost se zatim prihvata kao širina simbola. Putanja od 64 bita izračuna pravu vrednost, proveri je prema označenom 32-bitnom opsegu i podigne grešku ako se ne uklapa, što tiho kvarenje pretvara u eksplicitno odbijanje

Zašto se custom tabele nisu aktivirale pre 3.539.22?

Dva defekta su krila jedan drugi. Prvi je bio bug u setter-u od jednog reda: TTextRegionHuffmanFlags.setFlags primao je svoj argument pod istim imenom kao polje u koje ga je smeštao, pa je Self.flagsAsInt := flagsAsInt dodeljivao neinicijalizovano polje samom sebi i svaki selektor se čitao kao nula, što je text region-e koji traže custom tabele slalo kroz standardne tabele F, H i K. Drugi defekt značio je da bi popravka samo prvog i dalje davala pokvarene simbole. Kada Huffman symbol dictionary čuva svoje simbole kao nekomprimovani collective bitmap, poslednji bajt svakog reda je delimičan, a stara petlja kopiranja tretirala je padding, koji drži broj validnih bitova, kao poziciju najnižeg validnog bita; red širine 63 piksela kopirao je jedan bit iz svog poslednjeg bajta umesto sedam. Ispravljena petlja radi for bitPointer := 7 downto ((8 - padding) and 7), a sintetički fiksturi širine 7 i 9 bitova prikivaju obe strane bajt granice. Sa selektorima koji se čitaju ispravno, tabele se dele redosledom kojim ih specifikacija navodi, što T.88 §7.4.3.1.2 za text region-e fiksira kao FS, DS, DT, RDW, RDH, RDX, RDY i RSIZE, a §7.4.2.1.1 za symbol dictionary-je kao DH, DW, BMSIZE i AGGINST. Svaki dvobitni selektor znači standardna tabela 0 ili 1, rezervisano za 2 na poljima sa samo dve standardne tabele, i custom za 3, a svaki custom izbor troši sledeći Tables segment među referenciranim segmentima u redosledu referenciranja. NextCustomHuffmanTable radi upravo taj hod i podiže missing custom Huffman table reference kada region referencira manje tabela nego što njegovi selektori zahtevaju. Još jedan red pripada istoj popravci: Huffman symbol dictionary čiji ulazni i novi simboli zajedno daju jedan izračuna dužinu koda simbola nula po log2 formuli, dok Huffman varijanta formata piše svaki ID simbola sa najmanje jednim bitom, pa if sdHuffman and (symbolCodeLength = 0) then symbolCodeLength := 1 u TSymbolDictionarySegment čuva refinement i aggregate putanju od čitanja nula bitova po ID-u simbola

Šta garantuje granica segmenta?

PDFlibPas tretira dužinu podataka segmenta u svakom header-u kao ugovor koji obe strane moraju da poštuju: segment ne sme da čita iza svog deklarisanog kraja, i ne sme da završi prerano i ostavi sledeći header na nepredvidivom offsetu. Pravila koja ispadaju iz tog ugovora su pojedinačno mala. Dužina podataka sa postavljenim bitom 31 je marker nepoznate dužine iz T.88 §7.2.7, i handleSegmentDataLength je mapira u negativnu vrednost koju readSegments odbija odmah, umesto da skenira napred tražeći terminator. Svaki broj referenciranog segmenta mora biti manji od broja tekućeg segmenta i mora već postojati, pa forward ili dangling referenca pada pre nego što bilo koji region pokuša da je razreši. END_OF_PAGE i END_OF_FILE moraju da deklarišu nula bajtova podataka. Profiles segment (tip 52) nosi 32-bitni brojač praćen tolikim brojem 32-bitnih identifikatora i nimalo piksela, pa se proverava kao 4 plus 4 puta brojač prema deklarisanoj dužini, preskače, i ostaje u listi segmenata samo da bi kasniji segmenti i dalje mogli da ga referenciraju po broju. Nepoznat identifikator profila nije nepoznato kodiranje, i tretiranje kao da jeste odbilo bi fajlove koji se dekodiraju sasvim dobro

// 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');
// ... kreiraj objekat segmenta za ovaj tip ...
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 može da ostavi EOFB nepročitan
  reader.bitPointer := 7;
end;

Rep tog ciklusa je mesto gde je ranija verzija dekodera pogrešila na MMR-kodiranim regionima. MMR dekoder zna da je završio kada je proizveden poslednji piksel poslednjeg reda, što se može desiti pre nego što je potrošio EOFB terminator koji T.88 §6.2.5.7 postavlja na kraj podataka. Stari kod je pretpostavljao da je čitač pozicioniran na sledeći header, pa su preostali bajtovi terminatora parsirani kao broj segmenta i stream je pao nekoliko bajtova kasnije uz zavaravajuću grešku. Sada pobeđuje deklarisani kraj: čitanje iza njega je greška, zaustavljanje pre njega je normalno, a čitač se pomera na DataEnd uz resetovan bit pointer da bi se sledeći header čitao odatle gde je fajl rekao da će biti. Ista disciplina se pojavljuje svuda gde PDFlibPas parsira nepoverljive PDF strukture: deklarisana dužina je granica, i dekoder ne ide u potragu za ljubaznijom

Gde Huffman refinement čita veličinu svog bitmap-a?

Pre nego što aritmetički dekoder počne, i to iz polja koje postoji samo u Huffman režimu. Kada instanca text region-a nosi refinement (RI nije nula) i SBHUFF je postavljen, T.88 §6.4.11 nalaže da dekoder pročita RDW, RDH, RDX i RDY svojim izabranim tabelama, zatim BMSIZE pomoću RSIZE tabele, pa da se poravna na bajt granicu, i tek onda pokrene generičko refinement dekodiranje nad tačno BMSIZE bajtova. Aritmetički text region-i nemaju takvo polje, i dekoder koji deli jednu putanju koda za oba režima preskočiće ga, pokrenuti aritmetički dekoder dva ili više bajtova prerano, i rafinirati svaki simbol prema smeću. Putanja symbol dictionary-ja sa REFAGG i jednom refinement instancom, opisana u §6.5.8.2.2, ima isto BMSIZE polje sa istim posledicama. U PDFlibPas-u je gornja granica te veličine TStreamReader.SegmentEnd, kraj tekućeg segmenta kako ga postavlja readSegments, a ne kraj celog stream-a, jer je BMSIZE koji se može zadovoljiti samo pozajmljivanjem bajtova iz sledećeg segmenta malformiran i validacija prema dužini stream-a pustila bi aritmetički dekoder da čita u sledeći header. Donja granica od dva bajta odražava početni par bajtova koji aritmetički dekoder uvek potroši, a posle refinement-a čitač skače na RefinementEnd bez obzira na to koliko je aritmetički dekoder čitao unapred, jer njegova finalna pozicija nije pozicija sledećeg Huffman-kodiranog polja

// TJBIG2Bitmap dekodiranje text region-a, Huffman refinement putanja
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;

Šta je verifikovano, a šta se i dalje odbija

Uzorak koji je sve ovo pokrenuo, JBIG2 slika od 500 puta 473 piksela sa custom tabelama i Huffman refinement-om, sada se dekodira u bitmap sa nula različitih piksela prema nezavisnom dekoderu, a sintetički fiksturi collective bitmap-a širine 7 i 9 bitova daju očekivane redove na oba. Dva nezavisna dekodera koja se nisu slagala oko originalnog uzorka i dalje se ne slažu jedan s drugim; PDFlibPas se poklapa sa jednim od njih, i iskrena tvrdnja je da se nativni izlaz poklapa sa jednom nezavisnom implementacijom i sa specifikacijom kako je pročitana, a ne da se svi dekoderi na svetu slažu. Malformirana strana suite-a pokriva:

• rezervisan bit flag-a ili rezervisana vrednost selektora
• tabelu skraćenu u sredini linije
• prekoračene dužine prefix-a i prefix-e duže od 32 bita
• region čiji selektori traže više custom tabela nego što ih referencira
• potvrdu da se zastareo izlaz briše posle neuspelog dekodiranja, a ne ostavlja pozivaocu da ga pomeša sa rezultatom

Tri ograničenja ostaju namerna. Organizacija stream-a sa slučajnim pristupom, gde svi header-i segmenata prethode svim podacima segmenata, podiže JBIG2 random-access organisation is not supported čim se pročitaju flag-ovi header-a fajla, jer ne postoji reprezentativan uzorak za validaciju a poluimplementirana putanja je gora od odbijanja po imenu. Custom tabele su ograničene na 65.536 linija i prefix-e od 32 bita. A javni ulaz za dekodiranje, TPLJBIG2Decoder.LoadFromByteArray, vraća bitmap prve stranice u redosledu stream-a kroz getPageAsJBIG2Bitmap(0), prvi page-information segment na koji naiđe, umesto da traži page association nula; ugrađeni PDF stream-ovi rutinski numerišu svoju jednu stranicu kao 1, i traženje stranice 0 po asocijaciji ne bi našlo ništa. Tekst greške sleće u TPLJBIG2Decoder.LastError, internu dijagnostiku dekodera koja nosi broj segmenta, tip i bajt offset kvara, i nije isto što i TPDFlib.LastErrorCode na nivou biblioteke. Ništa od ovoga ne dira stranu kodiranja, koja je obrađena u beleškama o JBIG2 encoder backend-ima i načinu na koji se linkuju; putanja čitanja mora da prihvati šta god je tuđi enkoder odlučio da emituje, i deli svoja pravila sa ostatkom image stack-a, uključujući ugrađeni TIFF dekoder i njegova odbijanja BigTIFF i tiled rasporeda: odbij po imenu, nikada ne pozajmljuj bajtove preko deklarisane granice, i drži aritmetiku dovoljno širokom da obavijeni međurezultat ne može da prođe kao validan odgovor. Ako procenjujete nativnu JBIG2 putanju čitanja za Delphi ili C++Builder, dekoder i ostatak rukovanja slikama dokumentovani su na stranici PDF Library for Delphi