Prilagođene JBIG2 Huffman tablice u Pascal dekoderu

PDFlibPas verzija 3.539.22 nativno dekodira prilagođene JBIG2 Huffman tablice: dekoder u čistom Pascalu u PDFlibJBIG2.pas parsira Tables segment (tip 53), dodjeljuje kanonske prefix kodove u redoslijedu redaka tablice kako zahtijeva ITU-T T.88 Annex B.3, troši reference na prilagođene tablice u redoslijedu selektora za rječnike simbola i tekstualne regije, i omeđuje svako čitanje deklariranom duljinom segmenta, a ne bajtovima koji se slučajno nađu iza

Datoteka koja je pokrenula ovaj posao naizgled nije bila ništa posebno. Skenirani ugovor, JBIG2-komprimiran s Huffman simbol codingom umjesto daleko češćeg aritmetičkog kodiranja, i s enkoderom koji šalje vlastite kodne tablice umjesto standardnih tablica B.1 do B.15. Dva neovisna 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 rezač papira: fragmenti glifova pomaknuti za nekoliko piksela, jedan stupac svakog znaka nedostaje. Ništa nije prijavilo grešku. To je oblik buga koji preživi godinama, jer dekoder koji odbije datoteku dobije support ticket, a dekoder koji je prikaže malo pogrešno dobije kupca koji zaključi da je skeniranje bilo loše

Što JBIG2 Tables segment zapravo sadrži?

Tables segment je sažeti opis jedne Huffman tablice: jedan flags bajt, dvije predznačene 32-bitne granice, a zatim niz parova (duljina prefiksa, duljina raspona) koji dijele interval između granica, kako je opisano u T.88 §7.4.13 i Annex B.2. Bit 0 flags bajta je HTOOB i kaže ima li tablica out-of-band kod. Bitovi 1 do 3 plus jedan daju HTPS, broj bitova kojima se zapisuje svaka duljina prefiksa; bitovi 4 do 6 plus jedan daju HTRS, širinu svakog polja duljine raspona. Bit 7 je rezerviran, i PDFlibPas odbija segment ako je postavljen, umjesto da nagađa što je buduća revizija njime mislila. HTLOW i HTHIGH slijede kao predznačeni 32-bitni cijeli brojevi, i to je prvo mjesto gdje dekoder može pogriješiti: čitanje bez predznaka čini da tablica čija je donja granica negativna, što je posve normalno za delta-kodirane širine simbola, izgleda kao da počinje na četiri milijarde. Svako polje prolazi kroz lokalni ReadField pomoćnik koji provjerava zahtjev prema bit poziciji na kojoj završavaju podaci segmenta prije nego dotakne čitač, jer tablica koja čita iza svog segmenta trošila bi zaglavlje sljedećeg segmenta kao duljine prefiksa

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

Dva retka dodana nakon petlje escape su reci iz Annex B.2: redak donjeg raspona počinje na HTLOW minus jedan i broji prema dolje, redak gornjeg raspona počinje na HTHIGH s fiksnim 32-bitnim rasponom, a opcionalni OOB redak nema nikakvu vrijednost. PDFlibPas ih označava sentinel duljinama raspona jbig2HuffmanLOW ($FFFFFFFD) i jbig2HuffmanOOB ($FFFFFFFE), istom konvencijom koju koristi njegovih petnaest ugrađenih standardnih tablica, pa petlju dekodiranja nije briga je li tablica došla iz specifikacije ili iz datoteke

Zašto se prefix kodovi moraju dodijeliti u redoslijedu redaka tablice?

Zato što enkoder nikad ne zapisuje kodove. JBIG2 Tables segment nosi samo duljine prefiksa, a obje strane rekonstruiraju stvarne bitne uzorke kanonskim postupkom iz Annex B.3: prebroje koliko redaka ima koju duljinu, prvo dodijele kodove duljine jedan, zatim pomaknu ulijevo i nastave, a unutar jedne duljine dijele kodove redoslijedom kojim se reci pojavljuju. Svako odstupanje od tog redoslijeda tiho proizvodi drugu tablicu. Dekoder to neće primijetiti, jer je svaki bitni uzorak koji generira i dalje valjani prefix kod, samo ne onaj koji je enkoder koristio, a izlaz je uvjerljivo izgledajuća bitmapa sastavljena 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: izvorni redoslijed sačuvan
  if table[I].prefixLen > 0 then       // unutar svake duljine prefiksa
  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 sortiranje usporedbom, iz jednog razloga: prolaz brojanja po Counts, Starts i Positions stabilan je po konstrukciji, pa reci jednake duljine prefiksa dospijevaju u rezultat onim redoslijedom kojim su deklarirani, a upravo po tom redoslijedu Annex B.3 dodjeljuje kodove. Reci s nultom duljinom prefiksa ispadaju prije dodjele kodova, jer ih B.3 definira kao neiskorištene, a ne kao jednobitne kodove. U istoj petlji sjede dvije zaštite. Provjera prekoračenja hvata tablicu čije duljine traže više kodova nego što ih prefix kod te dubine može držati, što je Kraftova nejednakost izražena kao usporedba cijelih brojeva; bez nje zlonamjerna tablica proizvodi kod koji odgovara dvama recima i dekoder odabire onaj na koji prvi naiđe. Granica od 32 bita postoji jer je prefix tipa Cardinal, a matcher u decodeInt akumulira bitove u jedan. T.88 na papiru dopušta dulje prefikse, PDFlibPas ih odbija po imenu, a nijedan pravi enkoder dosad nije viđen da ih emitira. Aritmetika vrijednosti zahtijeva istu pažnju kao aritmetika kodova: THuffmanTable.val je Int64, a redak donjeg raspona dekodira se kao val - readBits(32), 32-bitni neoznačeni offset oduzet od HTLOW minus jedan. S Integer posrednicima to oduzimanje se prelijeva, a prelivena vrijednost zatim se prihvaća kao širina simbola. Put od 64 bita računa pravu vrijednost, provjerava je prema predznačenom 32-bitnom rasponu i podiže iznimku ako se ne uklapa, što tiho oštećenje pretvara u izričito odbijanje

Zašto se prilagođene tablice nikad nisu aktivirale prije 3.539.22?

Dvije greške skrivale su jedna drugu. Prva je bio bug u setteru od jednog retka: TTextRegionHuffmanFlags.setFlags primao je svoj argument pod istim imenom kao polje u koje je spremao, pa je Self.flagsAsInt := flagsAsInt dodjeljivao neinicijalizirano polje samome sebi i svaki selektor čitao se kao nula, što je tekstualne regije koje traže prilagođene tablice slalo kroz standardne tablice F, H i K. Druga greška značila je da bi popravak samo prve i dalje proizveo oštećene simbole. Kad Huffman rječnik simbola sprema svoje simbole kao nekomprimiranu kolektivnu bitmapu, posljednji bajt svakog retka je djelomičan, a stara petlja kopiranja tretirala je padding, koji drži broj valjanih bitova, kao poziciju najnižeg valjanog bita; redak širok 63 piksela kopirao je jedan bit iz svog završnog bajta umjesto sedam. Ispravljena petlja vrti for bitPointer := 7 downto ((8 - padding) and 7), a sintetički uzorci širine 7 i 9 bitova prikivaju obje strane bajtne granice. Kad selektori čitaju ispravno, tablice se dijele onim redoslijedom kojim ih specifikacija navodi, što T.88 §7.4.3.1.2 fiksira za tekstualne regije kao FS, DS, DT, RDW, RDH, RDX, RDY i RSIZE, a §7.4.2.1.1 za rječnike simbola kao DH, DW, BMSIZE i AGGINST. Svaki dvobitni selektor znači standardna tablica 0 ili 1, rezervirano za 2 na poljima sa samo dvije standardne tablice, i prilagođena za 3, a svaki prilagođeni odabir troši sljedeći Tables segment među referenciranim segmentima u redoslijedu referenciranja. NextCustomHuffmanTable radi točno taj hod i podiže missing custom Huffman table reference kad regija referencira manje tablica nego što njezini selektori zahtijevaju. Još jedan redak pripada istom popravku: Huffman rječnik simbola čiji ulazni i novi simboli zajedno daju jedan izračunava duljinu koda simbola nula iz log2 formule, dok Huffman varijanta formata zapisuje svaki ID simbola s barem jednim bitom, pa if sdHuffman and (symbolCodeLength = 0) then symbolCodeLength := 1 u TSymbolDictionarySegment čuva put refinementa i agregacije od čitanja nula bitova po ID-u simbola

Što jamči granica segmenta?

PDFlibPas tretira duljinu podataka segmenta u svakom zaglavlju kao ugovor koji obje strane moraju poštovati: segment ne smije čitati iza svog deklariranog kraja i ne smije završiti prerano i ostaviti sljedeće zaglavlje na nepredvidivom offsetu. Pravila koja iz tog ugovora proizlaze pojedinačno su mala. Duljina podataka s postavljenim bitom 31 marker je nepoznate duljine iz T.88 §7.2.7, a handleSegmentDataLength preslikava je u negativnu vrijednost koju readSegments odmah odbija, umjesto da traži terminator unaprijed. Svaki broj referenciranog segmenta mora biti manji od broja trenutačnog segmenta i mora već postojati, pa forward ili dangling referenca pada prije nego je ijedna regija pokuša razriješiti. END_OF_PAGE i END_OF_FILE moraju deklarirati nula bajtova podataka. Profiles segment (tip 52) nosi 32-bitni brojač nakon kojeg slijedi toliko 32-bitnih identifikatora i nikakvih piksela, pa se provjerava kao 4 plus 4 puta brojač prema deklariranoj duljini, preskače se i ostaje na popisu segmenata samo zato da ga kasniji segmenti i dalje mogu referencirati po broju. Nepoznat identifikator profila nije nepoznato kodiranje, a tretiranje kao da jest odbilo bi datoteke koje se sasvim dobro dekodiraju

// 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');
// ... stvori objekt 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 ostaviti EOFB nepročitan
  reader.bitPointer := 7;
end;

Rep te petlje mjesto je na kojem je ranija verzija dekodera griješila na MMR-kodiranim regijama. MMR dekoder zna da je gotov kad je proizveden posljednji piksel posljednjeg retka, što se može dogoditi prije nego što je potrošio EOFB terminator koji T.88 §6.2.5.7 stavlja na kraj podataka. Stari kod pretpostavljao je da je čitač pozicioniran na sljedećem zaglavlju, pa su zaostali bajtovi terminatora parsirani kao broj segmenta i stream je pao nekoliko bajtova kasnije s obmanjujućom greškom. Sada deklarirani kraj pobjeđuje: čitanje iza njega je greška, prerano zaustavljanje je normalno, a čitač se pomiče na DataEnd uz resetiran bit pointer, pa se sljedeće zaglavlje čita odakle je datoteka rekla da će biti. Ista disciplina pojavljuje se svugdje gdje PDFlibPas parsira nepouzdane PDF strukture: deklarirana duljina je granica, i dekoder ne ide tražiti prijateljskiju

Gdje Huffman refinement čita veličinu svoje bitmape?

Prije nego što aritmetički dekoder krene, i to iz polja koje postoji samo u Huffman modu. Kad instanca tekstualne regije nosi refinement (RI nije nula) i SBHUFF je postavljen, T.88 §6.4.11 nalaže dekoderu da pročita RDW, RDH, RDX i RDY s njihovim odabranim tablicama, zatim BMSIZE s RSIZE tablicom, pa se poravna na bajtnu granicu, i tek onda pokrene generičko refinement dekodiranje nad točno BMSIZE bajtova. Tekstualne regije u aritmetičkom modu nemaju takvo polje, a dekoder koji dijeli jedan put koda za oba moda preskočit će ga, pokrenuti aritmetički dekoder dva ili više bajtova prerano i rafinirati svaki simbol prema smeću. Put rječnika simbola s REFAGG i jednom instancom refinementa, opisan u §6.5.8.2.2, ima isto BMSIZE polje s istim posljedicama. U PDFlibPas gornja granica te veličine je TStreamReader.SegmentEnd, kraj trenutačnog segmenta kako ga postavlja readSegments, a ne kraj cijelog streama, jer je BMSIZE koji se može zadovoljiti samo posuđivanjem bajtova iz sljedećeg segmenta neispravan, a provjera prema duljini streama pustila bi aritmetički dekoder da čita u sljedeće zaglavlje. Donja granica od dva bajta odražava početni par bajtova koji aritmetički dekoder uvijek troši, a nakon refinementa čitač skače na RefinementEnd bez obzira na to koliko je aritmetički dekoder čitao unaprijed, jer njegova završna pozicija nije pozicija sljedećeg Huffman-kodiranog polja

// TJBIG2Bitmap dekodiranje tekstualne regije, put Huffman refinementa
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;

Što je provjereno, a što se i dalje odbija

Uzorak koji je sve pokrenuo, JBIG2 slika od 500 puta 473 piksela s prilagođenim tablicama i Huffman refinementom, sada se dekodira u bitmapu s nula različitih piksela u odnosu na neovisni dekoder, a sintetički uzorci kolektivne bitmape širine 7 i 9 bitova daju očekivane retke na obama. Dva neovisna dekodera koja se nisu slagala oko izvornog uzorka i dalje se ne slažu jedan s drugim; PDFlibPas odgovara jednom od njih, i iskrena tvrdnja je da se nativni izlaz slaže s jednom neovisnom implementacijom i sa specifikacijom kako je pročitana, a ne da se slaže svaki dekoder na svijetu. Neispravna strana suitea pokriva:

• rezervirani flag bit ili rezerviranu vrijednost selektora
• tablicu odsječenu u sredini retka
• prekoračene duljine prefiksa i prefikse dulje od 32 bita
• regiju čiji selektori traže više prilagođenih tablica nego što ih referencira
• potvrdu da se zastarjeli izlaz očisti nakon neuspjelog dekodiranja, a ne ostavi pozivatelju da ga zamijeni za rezultat

Tri ograničenja ostaju namjerna. Random-access organizacija streama, u kojoj sva zaglavlja segmenata prethode svim podacima segmenata, podiže JBIG2 random-access organisation is not supported čim se pročitaju zastavice zaglavlja datoteke, jer ne postoji reprezentativni uzorak prema kojem bi se to validiralo, a napola implementiran put gori je od imenovanog odbijanja. Prilagođene tablice ograničene su na 65.536 redaka i prefikse od 32 bita. A javni ulaz za dekodiranje, TPLJBIG2Decoder.LoadFromByteArray, vraća bitmapu prve stranice u redoslijedu streama kroz getPageAsJBIG2Bitmap(0), prvi pronađeni page-information segment, umjesto da traži page association nula; ugrađeni PDF streamovi rutinski numeriraju svoju jedinu stranicu kao 1, pa bi traženje stranice 0 po asocijaciji našlo ništa. Tekst greške završava u TPLJBIG2Decoder.LastError, internoj dijagnostici dekodera koja nosi broj segmenta, tip i bajtni offset kvara, i nije isto što i TPDFlib.LastErrorCode na razini biblioteke. Ništa od ovoga ne dira stranu kodiranja, koja je obrađena u bilješkama o JBIG2 encoder backendovima i načinu na koji se linkaju; put čitanja mora prihvatiti što god je tuđi enkoder odlučio emitirati, a svoja pravila dijeli s ostatkom image stacka, uključujući ugrađeni TIFF dekoder i njegova odbijanja BigTIFF-a i tiled rasporeda: odbij po imenu, nikad ne posuđuj bajtove preko deklarirane granice i drži aritmetiku dovoljno širokom da preliveni posredni rezultat ne može proći kao valjan odgovor. Ako procjenjujete nativni JBIG2 put čitanja za Delphi ili C++Builder, dekoder i ostatak rukovanja slikama dokumentirani su na stranici PDF Library for Delphi