JBIG2-mukautetut Huffman-taulukot Pascal-PDF-dekooderissa

PDFlibPas versio 3.539.22 purkaa JBIG2:n mukautetut Huffman-taulukot natiivisti: PDFlibJBIG2.pas-tiedoston puhdas Pascal-dekooderi jäsentää Tables-segmentin (tyyppi 53), jakaa kanoniset etuliitekoodit taulukkorivien järjestyksessä siten kuin ITU-T T.88:n liite B.3 vaatii, kuluttaa mukautettujen taulukoiden viittaukset valitsimien järjestyksessä symbolisanakirjoille ja tekstialueille ja rajaa jokaisen luvun segmentin ilmoitettuun pituuteen sen sijaan, että luottaisi siihen mitä tavuja sattuu seuraamaan

Tämän työn laukaissut tiedosto oli pinnalta katsoen mitäänsanomaton. Skannattu sopimus, pakattu JBIG2:lla Huffman-symbolikoodauksella eikä paljon yleisemmällä aritmeettisella koodauksella, ja koodaaja toimitti mukanaan omat kooditaulukkonsa standarditaulukoiden B.1–B.15 sijaan. Kaksi riippumatonta dekooderia oli eri mieltä sen tarkennuspikseleistä, ja tuolloisen PDFlibPasin dekooderi tuotti tekstiä, joka näytti silppurista tulleelta: glyph-fragmentit muutaman pikselin verran siirtyneinä, jokaisesta merkistä yksi sarake puuttui. Mikään ei nostanut virhettä. Juuri tuon muotoiset viat selviävät vuosia, sillä tiedoston hylkäävä dekooderi saa aikaan tukipyynnön, kun taas hieman väärin renderöivä dekooderi saa asiakkaan, joka olettaa skannauksen olleen huono

Mitä JBIG2:n Tables-segmentti oikeastaan sisältää?

Tables-segmentti on yhden Huffman-taulukon tiivis kuvaus: yksi flags-tavu, kaksi etumerkillistä 32-bittistä rajaa ja sitten jono (etuliitteen pituus, alueen pituus) -pareja, jotka jakavat rajojen välisen välin osiin, siten kuin T.88 §7.4.13 ja liite B.2 määrittelevät. Flags-tavun bitti 0 on HTOOB ja kertoo, onko taulukossa kaistan ulkopuolinen koodi. Bitit 1–3 plus yksi antavat HTPS:n eli sen, kuinka monella bitillä kunkin etuliitteen pituus kirjoitetaan; bitit 4–6 plus yksi antavat HTRS:n eli kunkin alueen pituuskentän leveyden. Bitti 7 on varattu, ja PDFlibPas hylkää segmentin, jos se on asetettu, sen sijaan että arvailisi mitä jokin tuleva revisio sillä tarkoitti. Seuraavaksi tulevat HTLOW ja HTHIGH etumerkillisinä 32-bittisinä kokonaislukuina, ja tässä dekooderi voi mennä pieleen ensimmäisen kerran: niiden lukeminen etumerkittöminä saa taulukon, jonka alaraja on negatiivinen, mikä on täysin normaalia deltakoodatuille symbolileveyksille, näyttämään siltä että se alkaa neljästä miljardista. Jokainen kenttä kulkee paikallisen ReadField-apufunktion kautta, joka tarkistaa pyynnön sitä bittisijaintia vasten, johon segmentin data päättyy, ennen kuin koskee lukijaan, koska segmenttinsä yli lukeva taulukko söisi seuraavan segmentin otsikon etuliitteiden pituuksina

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

Luupin jälkeen lisätyt kaksi riviä ovat liitteen B.2 escape-rivit: alarajan rivi alkaa HTLOW miinus yhdestä ja laskee alaspäin, ylärajan rivi alkaa HTHIGH:sta kiinteällä 32-bittisellä alueella, eikä valinnaisella OOB-rivillä ole arvoa lainkaan. PDFlibPas merkitsee ne sentinel-alueen pituuksilla jbig2HuffmanLOW ($FFFFFFFD) ja jbig2HuffmanOOB ($FFFFFFFE), samalla käytännöllä jota sen viisitoista sisäänrakennettua standarditaulukkoa käyttävät, joten dekoodausluuppi ei välitä siitä, tuliko taulukko spesifikaatiosta vai tiedostosta

Miksi etuliitekoodit on jaettava taulukkorivien järjestyksessä?

Koska koodaaja ei koskaan kirjoita koodeja. JBIG2:n Tables-segmentti kuljettaa mukanaan vain etuliitteiden pituudet, ja molemmat osapuolet rakentavat varsinaiset bittikuviot liitteen B.3 kanonisella menettelyllä: lasketaan kuinka monella rivillä on kukin pituus, jaetaan ensin yhden pituiset koodit, siirretään sitten vasemmalle ja jatketaan, ja yhden pituuden sisällä koodit jaetaan siinä järjestyksessä kuin rivit esiintyvät. Mikä tahansa poikkeama tuosta järjestyksestä tuottaa hiljaa eri taulukon. Dekooderi ei huomaa sitä, koska jokainen sen tuottama bittikuvio on edelleen kelvollinen etuliitekoodi, vain ei se jota koodaaja käytti, ja tuloksena on uskottavan näköinen bittikartta, joka on koottu vääristä symboleista

// 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            // vakaa: alkuperäinen järjestys säilyy
  if table[I].prefixLen > 0 then       // kunkin etuliitteen pituuden sisällä
  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 on laskentalajittelu eikä vertailulajittelu yhdestä syystä: laskentakierros Counts-, Starts- ja Positions-taulukoiden yli on rakenteellisesti vakaa, joten samanpituiset rivit päätyvät tulokseen siinä järjestyksessä kuin ne ilmoitettiin, mikä on täsmälleen se järjestys, jolla liite B.3 jakaa koodit. Nollapituiset rivit pudotetaan pois ennen koodien jakoa, koska B.3 määrittelee ne käyttämättömiksi eikä yhden bitin koodeiksi. Samassa luupissa on kaksi vartijaa. Ylivaraustarkistus nappaa taulukon, jonka pituudet vaativat enemmän koodeja kuin tuon syvyinen etuliitekoodi voi sisältää, eli Kraftin epäyhtälön kokonaislukuvertailuna ilmaistuna; ilman sitä vihamielinen taulukko tuottaa koodin, joka täsmää kahteen riviin, ja dekooderi valitsee niistä sen, jonka se skannaa ensin. 32 bitin katto on olemassa siksi, että prefix on Cardinal ja decodeInt-funktion täsmäyttäjä kerää bitit yhteen sellaiseen. T.88 sallii paperilla pidemmät etuliitteet, PDFlibPas hylkää ne nimeltä mainiten, eikä yhdenkään oikean koodaajan ole nähty tuottavan sellaista. Arvoaritmetiikka vaatii samaa huolenpitoa kuin koodiaritmetiikka: THuffmanTable.val on Int64, ja alarajan rivin arvo puretaan muodossa val - readBits(32), jossa HTLOW miinus yhdestä vähennetään 32-bittinen etumerkitön siirtymä. Integer-välituloksilla tuo vähennyslasku kiertyy ympäri, ja kiertynyt arvo hyväksytään sitten symbolin leveydeksi. 64-bittinen polku laskee todellisen arvon, tarkistaa sen etumerkillistä 32 bitin aluetta vasten ja nostaa virheen, jos se ei mahdu, mikä muuttaa äänettömän turmeltuman selkeäksi hylkäykseksi

Miksi mukautetut taulukot eivät koskaan lauenneet ennen versiota 3.539.22?

Kaksi vikaa piilotti toisensa. Ensimmäinen oli yhden rivin setteribugi: TTextRegionHuffmanFlags.setFlags sai argumenttinsa samalla nimellä kuin kenttä, johon se tallensi, joten Self.flagsAsInt := flagsAsInt sijoitti alustamattoman kentän itseensä ja jokainen valitsin luettiin takaisin nollana, mikä ohjasi mukautettuja taulukoita pyytävät tekstialueet standarditaulukoiden F, H ja K kautta. Toinen vika tarkoitti, että pelkän ensimmäisen korjaaminen olisi silti tuottanut turmeltuneita symboleja. Kun Huffman-symbolisanakirja tallentaa symbolinsa pakkaamattomana kollektiivisena bittikarttana, kunkin rivin viimeinen tavu on osittainen, ja vanha kopiointiluuppi käsitteli padding-arvoa, joka kertoo kelvollisten bittien määrän, alimman kelvollisen bitin sijaintina; 63 pikselin levyinen rivi kopioi viimeisestä tavustaan yhden bitin seitsemän sijaan. Korjattu luuppi pyörii muodossa for bitPointer := 7 downto ((8 - padding) and 7), ja synteettiset 7- ja 9-bittiset fixturet kiinnittävät tavurajan molemmat puolet. Kun valitsimet luetaan oikein, taulukot jaetaan siinä järjestyksessä kuin spesifikaatio ne luettelee, minkä T.88 §7.4.3.1.2 kiinnittää tekstialueille muotoon FS, DS, DT, RDW, RDH, RDX, RDY ja RSIZE ja §7.4.2.1.1 symbolisanakirjoille muotoon DH, DW, BMSIZE ja AGGINST. Kukin kahden bitin valitsin tarkoittaa standarditaulukkoa 0 tai 1, arvoa 2 varattuna kentille joilla on vain kaksi standarditaulukkoa, ja arvoa 3 mukautettua taulukkoa, ja jokainen mukautettu valinta kuluttaa seuraavan Tables-segmentin viitattujen segmenttien joukosta viittausjärjestyksessä. NextCustomHuffmanTable tekee täsmälleen tuon kierroksen ja nostaa virheen missing custom Huffman table reference, kun alue viittaa harvempiin taulukoihin kuin sen valitsimet vaativat. Samaan korjaukseen kuuluu vielä yksi rivi: Huffman-symbolisanakirja, jonka syöte- ja uudet symbolit lasketaan yhteen yhdeksi, laskee log2-kaavasta symbolikoodin pituudeksi nollan, kun taas formaatin Huffman-muunnos kirjoittaa jokaisen symbolitunnisteen vähintään yhdellä bitillä, joten if sdHuffman and (symbolCodeLength = 0) then symbolCodeLength := 1 TSymbolDictionarySegment-luokassa estää tarkennus- ja aggregaattipolkua lukemasta nollaa bittiä symbolitunnistetta kohti

Mitä segmentin raja takaa?

PDFlibPas pitää jokaisen otsikon segmentin datan pituutta sopimuksena, jota molempien suuntien on noudatettava: segmentti ei saa lukea ilmoitetun loppunsa yli eikä päättyä liian aikaisin ja jättää seuraavaa otsikkoa arvaamattomaan siirtymään. Tuosta sopimuksesta seuraavat säännöt ovat yksitellen pieniä. Datan pituus, jonka bitti 31 on asetettu, on T.88 §7.2.7:n tuntemattoman pituuden merkki, ja handleSegmentDataLength kuvaa sen negatiiviseksi arvoksi, jonka readSegments hylkää suoraan sen sijaan että skannaisi eteenpäin etsien terminaattoria. Jokaisen viitatun segmentin numeron on oltava pienempi kuin nykyisen segmentin numero ja sen on jo oltava olemassa, joten eteenpäin osoittava tai riippuva viittaus epäonnistuu ennen kuin yksikään alue yrittää ratkaista sitä. END_OF_PAGE- ja END_OF_FILE-segmenttien on ilmoitettava nollaa tavua dataa. Profiles-segmentti (tyyppi 52) kuljettaa 32-bittistä lukumäärää, jota seuraa sen verran 32-bittisiä tunnisteita eikä yhtään pikseliä, joten se tarkistetaan muodossa 4 plus 4 kertaa lukumäärä ilmoitettua pituutta vasten, ohitetaan ja pidetään segmenttilistassa vain siksi, että myöhemmät segmentit voivat edelleen viitata siihen numerolla. Tuntematon profiilitunniste ei ole tuntematon koodaus, ja sen käsitteleminen sellaisena hylkäisi tiedostoja, jotka purkautuvat täysin virheettä

// 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');
// ... luodaan tämän tyypin segmenttiobjekti ...
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 voi jättää EOFB:n lukematta
  reader.bitPointer := 7;
end;

Tuon luupin häntä on se kohta, jossa dekooderin aiempi versio meni pieleen MMR-koodatuilla alueilla. MMR-dekooderi tietää olevansa valmis, kun viimeisen rivin viimeinen pikseli on tuotettu, mikä voi tapahtua ennen kuin se on kuluttanut EOFB-terminaattorin, jonka T.88 §6.2.5.7 sijoittaa datan loppuun. Vanha koodi oletti lukijan olevan seuraavan otsikon kohdalla, joten jäljelle jääneet terminaattoritavut jäsennettiin segmentin numeroksi ja stream kaatui muutamaa tavua myöhemmin harhaanjohtavaan virheeseen. Nyt ilmoitettu loppu voittaa: sen yli lukeminen on virhe, liian aikaisin pysähtyminen on normaalia, ja lukija siirretään DataEnd-kohtaan bittiosoitin nollattuna, jotta seuraava otsikko luetaan sieltä, missä tiedosto sanoi sen olevan. Sama kurinalaisuus näkyy kaikkialla siellä, missä PDFlibPas jäsentää epäluotettuja PDF-rakenteita: ilmoitettu pituus on raja, eikä dekooderi lähde etsimään ystävällisempää

Mistä Huffman-tarkennus lukee bittikarttansa koon?

Ennen kuin aritmeettinen dekooderi käynnistyy, ja kentästä, jota on olemassa vain Huffman-tilassa. Kun tekstialueen instanssi sisältää tarkennuksen (RI on nollasta poikkeava) ja SBHUFF on asetettu, T.88 §6.4.11 antaa dekooderin lukea RDW-, RDH-, RDX- ja RDY-arvot valitsemillaan taulukoilla, sitten BMSIZE-arvon RSIZE-taulukolla, kohdistaa sen sen jälkeen tavurajaan ja vasta sitten ajaa yleisen tarkennusdekoodauksen täsmälleen BMSIZE tavun yli. Aritmeettisen tilan tekstialueilla ei ole tällaista kenttää, ja dekooderi, joka jakaa yhden koodipolun molemmille tiloille, ohittaa sen, käynnistää aritmeettisen dekooderin kaksi tai useampia tavuja liian aikaisin ja tarkentaa jokaisen symbolin roskan päälle. Symbolisanakirjan polulla REFAGG-arvolla ja yhdellä tarkennusinstanssilla, jotka on kuvattu kohdassa §6.5.8.2.2, on sama BMSIZE-kenttä ja samat seuraukset. PDFlibPasissa tuon koon yläraja on TStreamReader.SegmentEnd eli readSegments-kutsun asettama nykyisen segmentin loppu eikä koko streamin loppu, koska BMSIZE, joka voidaan tyydyttää vain lainaamalla tavuja seuraavasta segmentistä, on epämuodostunut, ja sen validoiminen streamin pituutta vasten päästäisi aritmeettisen dekooderin lukemaan seuraavaan otsikkoon. Kahden tavun alaraja heijastaa alkuperäistä tavuparia, jonka aritmeettinen dekooderi aina kuluttaa, ja tarkennuksen jälkeen lukija hyppää RefinementEnd-kohtaan riippumatta siitä, kuinka pitkälle aritmeettinen dekooderi luki eteenpäin, koska sen lopullinen sijainti ei ole seuraavan Huffman-koodatun kentän sijainti

// TJBIG2Bitmap-tekstialueen dekoodaus, Huffman-tarkennuspolku
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;

Mitä varmennettiin ja mikä hylätään edelleen

Tämän työn aloittanut näyte, 500 × 473 pikselin JBIG2-kuva, jossa on mukautetut taulukot ja Huffman-tarkennus, purkautuu nyt bittikartaksi, jossa on nolla eroavaa pikseliä riippumatonta dekooderia vasten, ja synteettiset 7- ja 9-bittiset kollektiivisen bittikartan fixturet tuottavat odotetut rivit kummallakin. Ne kaksi riippumatonta dekooderia, jotka olivat eri mieltä alkuperäisestä näytteestä, ovat edelleen eri mieltä keskenään; PDFlibPas täsmää toisen kanssa, ja rehellinen muotoilu on, että natiivi tulos on yhtä mieltä yhden riippumattoman toteutuksen kanssa ja luetun spesifikaation kanssa, ei että jokainen dekooderi maailmassa olisi samaa mieltä. Vikatapausten kirjasto kattaa:

• varattu flags-bitti tai varattu valitsimen arvo
• taulukko, joka on katkaistu rivin keskeltä
• ylivaratut etuliitteiden pituudet ja yli 32 bitin etuliitteet
• alue, jonka valitsimet pyytävät useampia mukautettuja taulukoita kuin mihin se viittaa
• varmistus siitä, että vanhentunut tulos nollataan epäonnistuneen purkamisen jälkeen sen sijaan että se jäisi paikalleen kutsujan luultavaksi tulokseksi

Kolme rajaa on edelleen tarkoituksellisia. Satunnaispääsystreamin järjestely, jossa kaikki segmenttien otsikot edeltävät kaikkea segmenttien dataa, nostaa virheen JBIG2 random-access organisation is not supported heti kun tiedoston otsikon flagbitit on luettu, koska yhtään edustavaa näytettä ei ole sen validoimiseksi ja puoliksi toteutettu polku on huonompi kuin nimetty hylkäys. Mukautetut taulukot on rajattu 65 536 riviin ja 32 bitin etuliitteisiin. Ja julkinen purkupiste TPLJBIG2Decoder.LoadFromByteArray palauttaa ensimmäisen sivun bittikartan stream-järjestyksessä getPageAsJBIG2Bitmap(0)-kutsulla, ensimmäisen vastaan tulevan sivutietosegmentin, sen sijaan että etsisi sivukytkentää nolla; upotetut PDF-streamit numeroivat ainoan sivunsa rutiininomaisesti sivuksi 1, ja sivun 0 kysyminen kytkennän perusteella ei löytäisi mitään. Virheteksti päätyy TPLJBIG2Decoder.LastError-kenttään, joka on dekooderin sisäinen diagnostiikka ja kuljettaa vian segmentin numeron, tyypin ja tavusiirtymän, eikä se ole sama asia kuin kirjastotason TPDFlib.LastErrorCode. Mikään tästä ei kosketa koodauspuolta, jota on käsitelty muistiinpanoissa JBIG2-koodaajataustoista ja niiden linkityksestä; lukupolun on hyväksyttävä se, mitä jonkun toisen koodaaja päättää tuottaa, ja se jakaa sääntönsä muun kuvapinon kanssa, mukaan lukien sisäänrakennettu TIFF-dekooderi ja sen BigTIFF- ja laattajärjestelyjen hylkäykset: hylkää nimeltä mainiten, älä koskaan lainaa tavuja ilmoitetun rajan yli ja pidä aritmetiikka riittävän leveänä, ettei kiertynyt välitulos voi mennä kelvollisesta vastauksesta. Jos arvioit natiivia JBIG2-lukupolkua Delphiä tai C++Builderia varten, dekooderi ja muu kuvankäsittely on dokumentoitu PDF Library for Delphi -sivulla