JBIG2 pasirinktinės Huffman lentelės Pascal PDF dekoderiuje

PDFlibPas 3.539.22 versija dekoduoja JBIG2 pasirinktines Huffman lenteles pati: grynai Pascal dekoderis faile PDFlibJBIG2.pas analizuoja Tables segmentą (53 tipas), priskiria kanoninius prefiksų kodus lentelės eilučių tvarka, kaip reikalauja ITU-T T.88 B.3 priedas, vartoja pasirinktinių lentelių nuorodas selektorių eilės tvarka simbolių žodynams ir teksto sritims, ir kiekvieną skaitymą apriboja deklaruotu segmento ilgiu, o ne bet kokiais baitais, kurie atsitiktinai eina po jo

Failas, kuris privertė imtis šio darbo, iš išorės buvo visai neįspūdingas. Nuskenuota sutartis, suspausta JBIG2 su Huffman simbolių kodavimu, o ne su daug įprastesniu aritmetiniu kodavimu, ir enkoderis pateikė savo kodo lenteles vietoje standartinių B.1–B.15 lentelių. Du nepriklausomi dekoderiai nesutarė dėl jos refinement pikselių, o tuo metu esamas PDFlibPas dekoderis davė tekstą, kuris atrodė praėjęs per smulkintuvą: glifų fragmentai pasislinkę keliais pikseliais, kiekvienam simboliui trūksta po vieną stulpelį. Niekas nekėlė klaidos. Būtent tokios formos defektai ir išgyvena metus, nes dekoderis, atmetantis failą, sulaukia palaikymo bilieto, o dekoderis, atvaizduojantis jį šiek tiek neteisingai, sulaukia kliento, kuris mano, kad skenavimas buvo blogas

Ką iš tikrųjų talpina JBIG2 Tables segmentas?

Tables segmentas yra kompaktiškas vienos Huffman lentelės aprašas: vienas vėliavėlių baitas, dvi ženklinės 32 bitų ribos, o tada (prefiksų ilgio, ruožo ilgio) porų seka, padalijanti intervalą tarp tų ribų, kaip išdėstyta T.88 §7.4.13 ir B.2 priede. Vėliavėlių baito 0 bitas yra HTOOB ir nurodo, ar lentelė turi už juostos esantį kodą. Bitai nuo 1 iki 3 plius vienas duoda HTPS – bitų skaičių, kuriuo užrašomas kiekvienas prefikso ilgis; bitai nuo 4 iki 6 plius vienas duoda HTRS – kiekvieno ruožo ilgio lauko plotį. 7 bitas yra rezervuotas, ir PDFlibPas atmeta segmentą, jei jis nustatytas, o ne spėja, ką būsima redakcija turėjo omenyje. Po to eina HTLOW ir HTHIGH kaip ženkliniai 32 bitų sveikieji skaičiai, ir čia dekoderis gali suklysti pirmą kartą: skaitymas kaip beženklio paverčia lentelę, kurios apatinė riba yra neigiama – visiškai normalus dalykas delta koduotiems simbolių pločiams – į tokią, kuri atrodo prasidedanti nuo keturių milijardų. Kiekvienas laukas eina per vietinį ReadField pagalbininką, kuris prieš liesdamas skaitytuvą patikrina prašymą prieš bito poziciją, kur baigiasi segmento duomenys, nes lentelė, skaitanti už savo segmento, vartotų kito segmento antraštę kaip prefiksų ilgius

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

Dvi eilutės, pridedamos po kilpos, yra pabėgimo eilutės iš B.2 priedo: apatinio ruožo eilutė prasideda nuo HTLOW minus vienas ir skaičiuoja žemyn, viršutinio ruožo eilutė prasideda nuo HTHIGH su fiksuotu 32 bitų ruožu, o pasirenkama OOB eilutė neturi jokios reikšmės. PDFlibPas jas žymi žyminčiais ruožų ilgiais jbig2HuffmanLOW ($FFFFFFFD) ir jbig2HuffmanOOB ($FFFFFFFE) – ta pačia konvencija, kurią naudoja jos penkiolika įtaisytų standartinių lentelių – tad dekodavimo kilpai nerūpi, ar lentelė atėjo iš specifikacijos, ar iš failo

Kodėl prefiksų kodai turi būti priskiriami lentelės eilučių tvarka?

Nes enkoderis niekada neužrašo pačių kodų. JBIG2 Tables segmentas neša tik prefiksų ilgius, ir abi pusės atkuria tikruosius bitų šablonus kanonine tvarka iš B.3 priedo: suskaičiuoja, kiek eilučių turi kiekvieną ilgį, pirmiausia priskiria vieno ilgio kodus, tada pastumia į kairę ir tęsia, o vieno ilgio ribose kodus išdalinėja tokia tvarka, kokia pasirodo eilutės. Bet koks nukrypimas nuo tos tvarkos tyliai duoda kitokią lentelę. Dekoderis to nepastebės, nes kiekvienas jo generuojamas bitų šablonas vis tiek yra galiojantis prefikso kodas – tik ne tas, kurį naudojo enkoderis – o išvestis yra patikimai atrodanti bitų mapa, surinkta iš neteisingų simbolių

// 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            // stabilus: pradinė tvarka išlaikoma
  if table[I].prefixLen > 0 then       // kiekvieno prefikso ilgio ribose
  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 yra skaičiavimo, o ne palyginimo rūšiavimas dėl vienos priežasties: skaičiavimo praėjimas per Counts, Starts ir Positions yra stabilus iš paties konstrukto, tad vienodo prefikso ilgio eilutės rezultate atsiduria tokia tvarka, kokia buvo deklaruotos, o būtent pagal tokią tvarką B.3 priedas ir priskiria kodus. Nulinio prefikso ilgio eilutės išmetamos dar prieš kodo priskyrimą, nes B.3 jas apibrėžia kaip nenaudojamas, o ne kaip vieno bito kodus. Toje pačioje kilpoje sėdi dvi sargybos. Perskirstymo patikrinimas pagauna lentelę, kurios ilgiai reikalauja daugiau kodų, nei tokio gylio prefikso kodas gali talpinti – tai Kraft nelygybė, išreikšta sveikųjų skaičių palyginimu; be jo priešiška lentelė sukuria kodą, kuris sutampa su dviem eilutėmis, ir dekoderis pasirenka tą, kurią perskaito pirmą. 32 bitų lubos egzistuoja todėl, kad prefix yra Cardinal, o decodeInt suderintuvas kaupia bitus į vieną. T.88 popieriuje leidžia ilgesnius prefiksus, PDFlibPas juos atmeta vardu, ir nė vienas tikras enkoderis nebuvo pastebėtas tokio išduodantis. Reikšmių aritmetikai reikia tokios pačios priežiūros kaip ir kodų aritmetikai: THuffmanTable.val yra Int64, o apatinio ruožo eilutė dekoduojama kaip val - readBits(32) – 32 bitų beženklis poslinkis, atimamas iš HTLOW minus vienas. Su Integer tarpiniais dydžiais ta atimtis apsiverčia, o apsivertusi reikšmė tada priimama kaip simbolio plotis. 64 bitų kelias apskaičiuoja tikrąją reikšmę, patikrina ją prieš ženklinį 32 bitų diapazoną ir kelia klaidą, jei ji netelpa – tai tylų sugadinimą paverčia aiškiu atmetimu

Kodėl pasirinktinės lentelės neveikė iki 3.539.22?

Du defektai slėpė vienas kitą. Pirmasis buvo vienos eilutės setterio klaida: TTextRegionHuffmanFlags.setFlags savo argumentą gaudavo tuo pačiu vardu kaip ir lauką, į kurį įrašydavo, tad Self.flagsAsInt := flagsAsInt priskirdavo neinicializuotą lauką pačiam sau, ir kiekvienas selektorius būdavo perskaitomas kaip nulis – tai teksto sritis, prašančias pasirinktinių lentelių, nukreipdavo per standartines F, H ir K lenteles. Antrasis defektas reiškė, kad vien pirmojo pataisymas vis tiek būtų davęs sugadintus simbolius. Kai Huffman simbolių žodynas savo simbolius laiko kaip nesuglaudintą kolektyvinę bitų mapą, paskutinis kiekvienos eilutės baitas yra dalinis, o sena kopijavimo kilpa padding, kuriame laikomas galiojančių bitų skaičius, traktavo kaip žemiausio galiojančio bito poziciją; 63 pikselių pločio eilutė nukopijuodavo vieną bitą iš paskutinio baito vietoje septynių. Pataisyta kilpa sukasi for bitPointer := 7 downto ((8 - padding) and 7), o sintetiniai 7 ir 9 bitų pločio testiniai duomenys prisega abi baito ribos puses. Selektoriams skaitant teisingai, lentelės išdalinamos tokia tvarka, kokia jas išvardija specifikacija, ir T.88 §7.4.3.1.2 ją fiksuoja teksto sritims kaip FS, DS, DT, RDW, RDH, RDX, RDY ir RSIZE, o §7.4.2.1.1 – simbolių žodynams kaip DH, DW, BMSIZE ir AGGINST. Kiekvienas dviejų bitų selektorius reiškia standartinę lentelę 0 arba 1, rezervuotas yra 2 laukuose, turinčiuose tik dvi standartines lenteles, o 3 reiškia pasirinktinę, ir kiekvienas pasirinktinės lentelės pasirinkimas vartoja kitą Tables segmentą tarp nurodytų segmentų nurodymo tvarka. NextCustomHuffmanTable atlieka būtent tokį ėjimą ir kelia missing custom Huffman table reference, kai sritis nurodo mažiau lentelių, nei reikalauja jos selektoriai. Dar viena eilutė priklauso tai pačiai pataisai: Huffman simbolių žodynas, kurio įvesties ir naujų simbolių suma lygi vienetui, pagal log2 formulę apskaičiuoja nulinį simbolio kodo ilgį, o Huffman formato variantas užrašo kiekvieną simbolio ID bent vienu bitu, tad if sdHuffman and (symbolCodeLength = 0) then symbolCodeLength := 1 TSymbolDictionarySegment viduje neleidžia refinement ir agregavimo keliui skaityti nulinių bitų vienam simbolio ID

Ką garantuoja segmento riba?

PDFlibPas kiekvienoje antraštėje esantį segmento duomenų ilgį traktuoja kaip kontraktą, kurį abi pusės turi gerbti: segmentas negali skaityti už deklaruotos pabaigos ir negali baigtis per anksti, palikdamas kitą antraštę nenuspėjamame poslinkyje. Taisyklės, kylančios iš to kontrakto, atskirai paėmus nedidelės. Duomenų ilgis su nustatytu 31 bitu yra nežinomo ilgio žymuo iš T.88 §7.2.7, ir handleSegmentDataLength paverčia jį neigiama reikšme, kurią readSegments atmeta iš karto, o ne skenuoja į priekį ieškodamas terminatoriaus. Kiekvienas nurodyto segmento numeris turi būti mažesnis už dabartinio segmento numerį ir jau turi egzistuoti, tad nuoroda į priekį arba kabanti nuoroda krinta dar prieš bet kuriai sričiai bandant ją išspręsti. END_OF_PAGE ir END_OF_FILE turi deklaruoti nulį duomenų baitų. Profiles segmentas (52 tipas) neša 32 bitų skaičių, po kurio eina tiek pat 32 bitų identifikatorių ir visai jokių pikselių, tad jis tikrinamas kaip 4 plius 4 kartus skaičius prieš deklaruotą ilgį, praleidžiamas ir laikomas segmentų sąraše tik tam, kad vėlesni segmentai vis tiek galėtų į jį nurodyti numeriu. Nežinomas profilio identifikatorius nėra nežinomas kodavimas, ir traktavimas kaip tokio atmestų failus, kurie dekoduojasi visiškai gerai

// 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');
// ... čia sukuriamas šio tipo segmento objektas ...
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 gali palikti EOFB nenuskaitytą
  reader.bitPointer := 7;
end;

Būtent tos kilpos pabaigoje ankstesnė dekoderio versija ir suklysdavo ties MMR koduotomis sritimis. MMR dekoderis žino, kad baigė, kai pagaminamas paskutinis paskutinės eilutės pikselis, o tai gali įvykti dar nesuvartojus EOFB terminatoriaus, kurį T.88 §6.2.5.7 stato duomenų gale. Senas kodas manė, kad skaitytuvas jau stovi prie kitos antraštės, tad likę terminatoriaus baitai būdavo perskaitomi kaip segmento numeris ir srautas krisdavo keliais baitais vėliau su klaidinančia klaida. Dabar laimi deklaruota pabaiga: skaitymas už jos yra klaida, sustojimas anksčiau yra norma, o skaitytuvas perkeliamas į DataEnd su atstatytu bito žymekliu, kad kita antraštė būtų skaitoma iš ten, kur failas sakė esant. Ta pati disciplina matosi visur, kur PDFlibPas analizuoja nepatikimas PDF struktūras: deklaruotas ilgis yra riba, ir dekoderis neieško draugiškesnės

Iš kur Huffman refinement paima savo bitų mapos dydį?

Prieš paleidžiant aritmetinį dekoderį ir iš lauko, kuris egzistuoja tik Huffman režime. Kai teksto srities egzempliorius turi refinement (RI nelygus nuliui) ir SBHUFF yra nustatytas, T.88 §6.4.11 liepia dekoderiui perskaityti RDW, RDH, RDX ir RDY su jų pasirinktomis lentelėmis, tada BMSIZE su RSIZE lentele, tada sulygiuoti prie baito ribos ir tik tada paleisti bendrą refinement dekodavimą lygiai per BMSIZE baitų. Aritmetinio režimo teksto sritys tokio lauko neturi, ir dekoderis, kuris abiem režimams turi vieną kodo kelią, jį praleis, paleis aritmetinį dekoderį dviem ar daugiau baitų per anksti ir atliks refinement kiekvienam simboliui prieš šiukšles. Simbolių žodyno kelias su REFAGG ir vienu refinement egzemplioriumi, aprašytas §6.5.8.2.2, turi tą patį BMSIZE lauką su tomis pačiomis pasekmėmis. PDFlibPas to dydžio viršutinė riba yra TStreamReader.SegmentEnd – dabartinio segmento pabaiga, nustatyta readSegments, o ne viso srauto pabaiga, nes BMSIZE, kurį galima patenkinti tik pasiskolinus baitų iš sekančio segmento, yra sugadintas, o tikrinimas prieš srauto ilgį leistų aritmetiniam dekoderiui skaityti į kitą antraštę. Dviejų baitų apatinė riba atspindi pradinę baitų porą, kurią aritmetinis dekoderis suvartoja visada, o po refinement skaitytuvas peršoka į RefinementEnd nepriklausomai nuo to, kiek į priekį buvo nuskaityta, nes jo galutinė pozicija nėra sekančio Huffman koduoto lauko pozicija

// TJBIG2Bitmap teksto srities dekodavimas, Huffman refinement kelias
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;

Kas buvo patikrinta ir kas vis dar atmetama

Pavyzdys, nuo kurio viskas prasidėjo – 500 x 473 pikselių JBIG2 paveikslėlis su pasirinktinėmis lentelėmis ir Huffman refinement – dabar dekoduojasi į bitų mapą su nuliu besiskiriančių pikselių, palyginus su nepriklausomu dekoderiu, o sintetiniai 7 ir 9 bitų kolektyvinės bitų mapos testiniai duomenys duoda laukiamas eilutes abiem atvejais. Du nepriklausomi dekoderiai, kurie nesutarė dėl pradinio pavyzdžio, vis dar nesutaria vienas su kitu; PDFlibPas sutampa su vienu iš jų, ir sąžiningas teiginys yra toks, kad savoji išvestis sutampa su viena nepriklausoma implementacija ir su perskaityta specifikacija, o ne kad sutaria kiekvienas pasaulio dekoderis. Sugadintų failų pusė rinkinyje apima:

• rezervuotą vėliavėlių bitą arba rezervuotą selektoriaus reikšmę
• lentelę, nukirptą eilutės viduryje
• perskirstytus prefiksų ilgius ir ilgesnius nei 32 bitų prefiksus
• sritį, kurios selektoriai prašo daugiau pasirinktinių lentelių, nei ji nurodo
• patvirtinimą, kad po nepavykusio dekodavimo pasenusi išvestis išvaloma, o ne paliekama kviečiančiajam supainioti su rezultatu

Trys ribos lieka sąmoningos. Savavališkos prieigos srauto organizavimas, kai visos segmentų antraštės eina prieš visus segmentų duomenis, kelia JBIG2 random-access organisation is not supported vos perskaičius failo antraštės vėliavėles, nes nėra reprezentatyvaus pavyzdžio jai patikrinti, o pusiau įgyvendintas kelias yra blogiau už įvardytą atmetimą. Pasirinktinės lentelės apribotos 65 536 eilučių ir 32 bitų prefiksais. O viešas dekodavimo įėjimas TPLJBIG2Decoder.LoadFromByteArray grąžina pirmą puslapio bitų mapą srauto tvarka per getPageAsJBIG2Bitmap(0) – pirmą sutiktą puslapio informacijos segmentą – o ne ieško puslapio asociacijos nulio; įterpti PDF srautai savo vienintelį puslapį paprastai numeruoja 1, ir prašymas puslapio 0 pagal asociaciją nieko nerasytų. Klaidos tekstas patenka į TPLJBIG2Decoder.LastError – vidinę dekoderio diagnostiką, kuri neša segmento numerį, tipą ir klaidos baito poslinkį, ir nėra tas pats, kas bibliotekos lygio TPDFlib.LastErrorCode. Niekas iš to neliečia kodavimo pusės, kuri aprašyta pastabose apie JBIG2 enkoderio backendus ir jų susiejimą; skaitymo kelias turi priimti tai, ką nusprendė išduoti svetimas enkoderis, ir dalijasi savo taisyklėmis su likusiu paveikslėlių steku, įskaitant įtaisytą TIFF dekoderį bei jo BigTIFF ir tiled išdėstymo atmetimus: atmesti vardu, niekada neskolintis baitų per deklaruotą ribą ir išlaikyti aritmetiką pakankamai plačią, kad apsivertęs tarpinis dydis nepraeitų kaip galiojantis atsakymas. Jei vertinate savąjį JBIG2 skaitymo kelią Delphi ar C++Builder, dekoderis ir likęs paveikslėlių apdorojimas aprašyti PDF Library for Delphi puslapyje