Tabele Huffman po meri v dekoderju JBIG2, pisanem v Pascalu

Različica PDFlibPas 3.539.22 dekodira tabele Huffman po meri JBIG2 izvorno: čisti pascalovski dekoder v PDFlibJBIG2.pas razčleni segment Tables (tip 53), dodeli kanonične predpone po vrstnem redu vrstic tabele, kot zahteva dodatek B standarda ITU-T T.88, porabi sklice na tabele po meri po vrstnem redu izbirnikov za slovarje simbolov in besedilna območja ter vsako branje omeji z deklarirano dolžino segmenta, ne s tem, kateri bajti slučajno sledijo

Datoteka, ki je sprožila to delo, na zunaj ni bila nič posebnega. Skenirana pogodba, stisnjena z JBIG2 s Huffmanovim kodiranjem simbolov namesto veliko pogostejšega aritmetičnega kodiranja, pri čemer je kodirnik dobavljal svoje kodne tabele namesto standardnih tabel B.1 do B.15. Dva neodvisna dekoderja se nista ujemala glede pik prefinjanja, takratni dekoder PDFlibPas pa je dajal besedilo, ki je bilo videti, kot da je šlo skozi uničevalnik dokumentov: drobci glifov, premaknjeni za nekaj pik, manjkajoč en stolpec vsakega znaka. Nič ni sprožilo napake. Prav takšna napaka preživi leta, saj dekoder, ki datoteko zavrne, dobi zahtevek za podporo, dekoder, ki jo upodobi nekoliko narobe, pa dobi stranko, ki sklepa, da je skeniranje slabo

Kaj pravzaprav vsebuje segment Tables v JBIG2?

Segment Tables je strnjen opis ene tabele Huffman: en bajt zastavic, dve predznačeni 32-bitni meji in nato niz parov (dolžina predpone, dolžina obsega), ki razdelijo interval med mejama, kot je določeno v T.88 §7.4.13 in dodatku B.2. Bit 0 bajta zastavic je HTOOB in pove, ali ima tabela kodo zunaj pasu. Biti od 1 do 3 plus ena dajo HTPS, število bitov za zapis vsake dolžine predpone; biti od 4 do 6 plus ena dajo HTRS, širino polja vsake dolžine obsega. Bit 7 je rezerviran in PDFlibPas segment zavrne, če je nastavljen, namesto da bi ugibal, kaj je s tem mislila prihodnja revizija. Sledita HTLOW in HTHIGH kot predznačeni 32-bitni celi števili, in prav tu se lahko dekoder prvič zmoti: če ju bere kot nepredznačeni, je videti, da se tabela, katere spodnja meja je negativna, kar je povsem običajno za delta kodirane širine simbolov, začne pri štirih milijardah. Vsako polje gre skozi lokalni pomožnik ReadField, ki zahtevo preveri proti bitnemu položaju, kjer se podatki segmenta končajo, še preden se dotakne bralnika, saj bi tabela, ki bere čez svoj segment, kot dolžine predpon požrla glavo naslednjega segmenta

// 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);

Vrstici, dodani za zanko, sta ubežni vrstici iz dodatka B.2: spodnja vrstica obsega se začne pri HTLOW minus ena in šteje navzdol, zgornja vrstica obsega se začne pri HTHIGH s fiksno 32-bitnim obsegom, neobvezna vrstica OOB pa nima nobene vrednosti. PDFlibPas ju označi s sentinelnima dolžinama obsega jbig2HuffmanLOW ($FFFFFFFD) in jbig2HuffmanOOB ($FFFFFFFE), po isti konvenciji, kot jo uporablja njenih petnajst vgrajenih standardnih tabel, zato zanke dekodiranja ne zanima, ali je tabela prišla iz specifikacije ali iz datoteke

Zakaj je treba kode predpon dodeliti po vrstnem redu vrstic tabele?

Ker kodirnik kod nikoli ne zapiše. Segment Tables v JBIG2 prinaša samo dolžine predpon, obe strani pa dejanske bitne vzorce rekonstruirata s kanoničnim postopkom iz dodatka B.3: preštej, koliko vrstic ima katero dolžino, najprej dodeli kode dolžine ena, nato zamakni v levo in nadaljuj, znotraj ene dolžine pa kode podeli v vrstnem redu, v katerem se vrstice pojavijo. Vsako odstopanje od tega vrstnega reda tiho ustvari drugačno tabelo. Dekoder tega ne opazi, ker je vsak bitni vzorec, ki ga ustvari, še vedno veljavna koda predpone, le tista, ki jo je uporabil kodirnik, ni, izhod pa je na videz verjetna bitna slika, sestavljena iz napačnih simbolov

// 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: izvirni vrstni red
  if table[I].prefixLen > 0 then       // je ohranjen znotraj vsake dolžine
  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 štetje namesto primerjalnega urejanja iz enega razloga: prehod s štetjem po Counts, Starts in Positions je stabilen že po zasnovi, zato vrstice z enako dolžino predpone pristanejo v rezultatu v vrstnem redu, v katerem so bile deklarirane, in prav po tem vrstnem redu dodatek B.3 dodeljuje kode. Vrstice z dolžino predpone nič se izločijo pred dodelitvijo kod, ker jih B.3 definira kot neuporabljene in ne kot enobitne kode. V isti zanki sedita dve varovali. Preverjanje prekomerne dodelitve ujame tabelo, katere dolžine zahtevajo več kod, kot jih lahko sprejme koda predpone te globine, kar je Kraftova neenakost, izražena kot primerjava celih števil; brez njega sovražna tabela ustvari kodo, ki se ujema z dvema vrsticama, dekoder pa izbere tisto, ki jo prebere prvo. Zgornja meja 32 bitov obstaja zato, ker je prefix tipa Cardinal in matcher v decodeInt zbira bite v enega. T.88 na papirju dopušča daljše predpone, PDFlibPas jih zavrne po imenu, noben resnični kodirnik pa po vsem videnem take predpone ne oddaja. Aritmetika vrednosti potrebuje enako skrb kot aritmetika kod: THuffmanTable.val je Int64, spodnja vrstica obsega pa se dekodira kot val - readBits(32), 32-bitni nepredznačeni odmik, odštet od HTLOW minus ena. Z vmesnimi vrednostmi tipa Integer se to odštevanje ovije, ovita vrednost pa se nato sprejme kot širina simbola. 64-bitna pot izračuna pravo vrednost, jo preveri proti predznačenemu 32-bitnemu obsegu in sproži izjemo, če se ne ujame, kar tiho okvaro spremeni v izrecno zavrnitev

Zakaj tabele po meri pred različico 3.539.22 niso nikoli nastopile?

Dve napaki sta se skrivali ena za drugo. Prva je bila napaka v enovrstičnem setterju: TTextRegionHuffmanFlags.setFlags je svoj argument prejel pod istim imenom kot polje, v katerega ga je shranil, zato je Self.flagsAsInt := flagsAsInt dodelil neinicializirano polje samo sebi in vsak izbirnik se je bral nazaj kot nič, kar je besedilna območja, ki so zahtevala tabele po meri, speljalo skozi standardne tabele F, H in K. Druga napaka je pomenila, da bi popravek samo prve še vedno dajal okvarjene simbole. Ko slovar simbolov Huffman shrani svoje simbole kot nestisnjeno kolektivno bitno sliko, je zadnji bajt vsake vrstice delen, stara zanka za kopiranje pa je padding, ki vsebuje število veljavnih bitov, obravnavala kot položaj najnižjega veljavnega bita; vrstica, široka 63 pik, je iz zadnjega bajta prekopirala en bit namesto sedmih. Popravljena zanka teče for bitPointer := 7 downto ((8 - padding) and 7), sintetične fiksne datoteke s širinami 7 in 9 bitov pa pripnejo obe strani bajtne meje. Ko izbirniki berejo pravilno, se tabele podeljujejo v vrstnem redu, v katerem jih našteva specifikacija, kar T.88 §7.4.3.1.2 za besedilna območja določi kot FS, DS, DT, RDW, RDH, RDX, RDY in RSIZE, §7.4.2.1.1 pa za slovarje simbolov kot DH, DW, BMSIZE in AGGINST. Vsak dvobitni izbirnik pomeni standardno tabelo 0 ali 1, rezerviran za 2 na poljih z le dvema standardnima tabelama, po meri pa za 3, vsaka izbira po meri pa porabi naslednji segment Tables med navedenimi segmenti v vrstnem redu navedb. NextCustomHuffmanTable opravi natanko ta sprehod in sproži missing custom Huffman table reference, kadar območje navaja manj tabel, kot jih zahtevajo njegovi izbirniki. K istemu popravku spada še ena vrstica: slovar simbolov Huffman, pri katerem vhodni in novi simboli skupaj dajo ena, po formuli log2 izračuna dolžino kode simbola nič, huffmanova različica formata pa vsak ID simbola zapiše z vsaj enim bitom, zato if sdHuffman and (symbolCodeLength = 0) then symbolCodeLength := 1 v TSymbolDictionarySegment prepreči, da bi pot prefinjanja in agregacije brala nič bitov na ID simbola

Kaj zagotavlja meja segmenta?

PDFlibPas dolžino podatkov segmenta v vsaki glavi obravnava kot pogodbo, ki jo morata spoštovati obe smeri: segment ne sme brati čez svoj deklarirani konec in ne sme se končati prej ter pustiti naslednje glave na nepredvidljivem odmiku. Pravila, ki izhajajo iz te pogodbe, so vsako zase majhno. Dolžina podatkov z nastavljenim bitom 31 je oznaka neznane dolžine iz T.88 §7.2.7 in handleSegmentDataLength jo preslika v negativno vrednost, ki jo readSegments takoj zavrne, namesto da bi iskal zaključitelj naprej. Vsaka številka navedenega segmenta mora biti manjša od številke trenutnega segmenta in mora že obstajati, zato navedba naprej ali viseča navedba pade, preden jo poskusi razrešiti katero koli območje. END_OF_PAGE in END_OF_FILE morata deklarirati nič bajtov podatkov. Segment Profiles (tip 52) prinaša 32-bitni števec, ki mu sledi toliko 32-bitnih identifikatorjev in nič pik, zato se preveri kot 4 plus 4 krat števec proti deklarirani dolžini, preskoči in obdrži na seznamu segmentov le zato, da se lahko poznejši segmenti nanj še sklicujejo po številki. Neznan identifikator profila ni neznano kodiranje in če bi ga obravnavali kot tako, bi zavrnili datoteke, ki se dekodirajo povsem 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');
// ... ustvari objekt segmenta za ta 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 lahko pusti EOFB neprebran
  reader.bitPointer := 7;
end;

Prav na koncu te zanke se je starejša različica dekoderja zmotila pri območjih, kodiranih z MMR. Dekoder MMR ve, da je končal, ko je izdelana zadnja pika zadnje vrstice, kar se lahko zgodi, preden je požrl zaključitelj EOFB, ki ga T.88 §6.2.5.7 postavlja na konec podatkov. Stara koda je predpostavljala, da je bralnik postavljen na naslednjo glavo, zato so se preostali bajti zaključitelja razčlenili kot številka segmenta in tok je nekaj bajtov pozneje odpovedal z zavajajočo napako. Zdaj zmaga deklarirani konec: branje čezenj je napaka, ustavitev prej je običajna, bralnik pa se premakne na DataEnd s ponastavljenim bitnim kazalcem, tako da se naslednja glava bere od tam, kjer je datoteka rekla, da bo. Ista disciplina se pokaže povsod, kjer PDFlibPas razčlenjuje nezaupanja vredne strukture PDF: deklarirana dolžina je meja in dekoder ne gre iskat prijaznejše

Kje prefinjanje Huffman prebere velikost svoje bitne slike?

Preden se zažene aritmetični dekoder, in to s polja, ki obstaja le v načinu Huffman. Ko instanca besedilnega območja prinaša prefinjanje (RI ni nič) in je nastavljen SBHUFF, T.88 §6.4.11 naroči dekoderju, naj prebere RDW, RDH, RDX in RDY s svojimi izbranimi tabelami, nato BMSIZE s tabelo RSIZE, se nato poravna na bajtno mejo in šele potem požene splošno dekodiranje prefinjanja po natanko BMSIZE bajtih. Besedilna območja v aritmetičnem načinu takega polja nimajo in dekoder, ki si oba načina deli eno pot kode, ga bo preskočil, aritmetični dekoder zagnal dva ali več bajtov prezgodaj ter vsak simbol prefinil proti smeteh. Pot slovarja simbolov z REFAGG in eno samo instanco prefinjanja, opisana v §6.5.8.2.2, ima isto polje BMSIZE z istimi posledicami. V PDFlibPas je zgornja meja te velikosti TStreamReader.SegmentEnd, konec trenutnega segmenta, kot ga nastavi readSegments, ne konec celega toka, ker je BMSIZE, ki ga je mogoče zadovoljiti le z izposojo bajtov iz naslednjega segmenta, pokvarjen, preverjanje proti dolžini toka pa bi aritmetičnemu dekoderju dovolilo branje v naslednjo glavo. Spodnja meja dveh bajtov odraža začetni par bajtov, ki ga aritmetični dekoder vedno požre, po prefinjanju pa bralnik skoči na RefinementEnd ne glede na to, kako daleč naprej je bral aritmetični dekoder, saj njegov končni položaj ni položaj naslednjega s Huffmanom kodiranega polja

// TJBIG2Bitmap: dekodiranje besedilnega območja, pot prefinjanja 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;

Kaj je bilo preverjeno in kaj se še vedno zavrača

Vzorec, ki je vse skupaj sprožil, slika JBIG2 500 krat 473 pik s tabelami po meri in prefinjanjem Huffman, se zdaj dekodira v bitno sliko brez ene same različne pike proti neodvisnemu dekoderju, sintetični fiksni datoteki s 7-bitno in 9-bitno kolektivno bitno sliko pa na obeh dajeta pričakovane vrstice. Dva neodvisna dekoderja, ki se glede izvirnega vzorca nista ujemala, se še vedno ne ujemata drug z drugim; PDFlibPas se ujema z enim od njiju in poštena izjava je, da se izvorni izhod ujema z eno neodvisno implementacijo in s prebrano specifikacijo, ne pa da se ujemajo vsi dekoderji na svetu. Slaba stran niza pokriva:

• rezerviran bit zastavic ali rezervirano vrednost izbirnika
• tabelo, odrezano na sredi vrstice
• prekomerno dodeljene dolžine predpon in predpone, daljše od 32 bitov
• območje, katerega izbirniki zahtevajo več tabel po meri, kot jih navaja
• potrditev, da se zastarel izhod po spodletelem dekodiranju počisti in ne pusti na mestu, da bi ga klicatelj zamenjal za rezultat

Tri omejitve ostajajo namerne. Naključno dostopna organizacija toka, kjer vse glave segmentov stojijo pred vsemi podatki segmentov, sproži JBIG2 random-access organisation is not supported takoj, ko se preberejo zastavice glave datoteke, ker ni reprezentativnega vzorca, proti kateremu bi jo preverili, in napol izvedena pot je slabša od poimenovane zavrnitve. Tabele po meri so omejene na 65.536 vrstic in 32-bitne predpone. Javni vstop v dekodiranje, TPLJBIG2Decoder.LoadFromByteArray, pa vrne bitno sliko prve strani v vrstnem redu toka skozi getPageAsJBIG2Bitmap(0), prvi naleteli segment s podatki o strani, namesto da bi poiskal pridružitev strani nič; vdelani tokovi PDF svojo edino stran redno oštevilčijo z 1 in iskanje strani 0 po pridružitvi ne bi našlo ničesar. Besedilo napake pristane v TPLJBIG2Decoder.LastError, notranji diagnostiki dekoderja, ki prinaša številko segmenta, tip in bajtni odmik napake, in ni isto kot knjižnična TPDFlib.LastErrorCode. Nič od tega se ne dotakne kodirne strani, ki je opisana v zapiskih o zaledjih kodirnika JBIG2 in njihovem povezovanju; bralna pot mora sprejeti, kar koli se je odločil oddati tuj kodirnik, svoja pravila pa si deli z ostalim skladom za slike, vključno z vgrajenim dekoderjem TIFF in njegovimi zavrnitvami BigTIFF in razdeljenih postavitev: zavrni po imenu, nikoli si ne izposojaj bajtov čez deklarirano mejo in ohrani aritmetiko dovolj široko, da ovita vmesna vrednost ne more veljati za veljaven odgovor. Če ocenjujete izvorno bralno pot JBIG2 za Delphi ali C++Builder, sta dekoder in ostalo ravnanje s slikami dokumentirana na strani PDF Library for Delphi