JBIG2 egyedi Huffman-táblák natív Pascal PDF-dekóderben

A PDFlibPas 3.539.22-es verziója natívan dekódolja a JBIG2 egyedi Huffman-táblákat: a PDFlibJBIG2.pas tiszta Pascal dekódere feldolgozza a Tables szegmenst (53-as típus), kanonikus prefixkódokat oszt ki táblasorrendben, ahogy az ITU-T T.88 B.3 melléklete megköveteli, a szelektorok sorrendjében fogyasztja az egyedi táblahivatkozásokat a szimbólumszótárakhoz és a szövegrégiókhoz, és minden olvasást a deklarált szegmenshosszhoz köt, nem pedig ahhoz, hogy épp milyen bájtok következnek utána

Az a fájl, ami ezt a munkát kikényszerítette, a felszínen semmi különöset nem mutatott. Egy beszkennelt szerződés, JBIG2-vel tömörítve, Huffman szimbólumkódolással a sokkal gyakoribb aritmetikai kódolás helyett, és a kódoló a saját kódtábláit szállította a B.1–B.15 szabványos táblák helyett. Két független dekóder nem értett egyet a finomítási pixelein, a korabeli PDFlibPas dekóder pedig olyan szöveget adott ki, mintha átment volna egy iratmegsemmisítőn: néhány pixellel eltolt glif-töredékek, és minden karakterből hiányzott egy oszlop. Semmi nem jelzett hibát. Ez az a fajta hiba, ami évekig túlél, mert a fájlt visszautasító dekóder support-ticketet kap, az viszont, amelyik kicsit rosszul rendereli, olyan ügyfelet, aki azt hiszi, rossz volt a szkennelés

Mit tartalmaz valójában egy JBIG2 Tables szegmens?

Egy Tables szegmens egy Huffman-tábla tömör leírása: egy flags bájt, két előjeles 32 bites korlát, majd (prefixhossz, tartományhossz) párok sora, amelyek felosztják a korlátok közötti intervallumot, a T.88 §7.4.13 és a B.2 melléklet szerinti elrendezésben. A flags bájt 0. bitje a HTOOB, ami megmondja, hogy a táblának van-e sávon kívüli kódja. Az 1–3. bit plusz egy adja a HTPS-t, azaz a prefixhosszak leírásához használt bitek számát; a 4–6. bit plusz egy adja a HTRS-t, a tartományhossz-mezők szélességét. A 7. bit fenntartott, és a PDFlibPas visszautasítja a szegmenst, ha be van állítva, ahelyett hogy találgatná, mit értett rajta egy jövőbeli revízió. Ezután HTLOW és HTHIGH következik előjeles 32 bites egészként, és itt tud először elromolni a dekóder: ha előjel nélküliként olvasod őket, egy olyan tábla, aminek az alsó korlátja negatív — ami teljesen normális a delta-kódolt szimbólumszélességeknél —, úgy néz ki, mintha négymilliárdnál kezdődne. Minden mező egy lokális ReadField helperen megy át, ami az olvasó megérintése előtt ellenőrzi a kérést a szegmensadat végét jelző bitpozíció ellen, mert egy tábla, ami a saját szegmensén túl olvasna, a következő szegmens fejlécét fogyasztaná prefixhosszként

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

A ciklus után hozzáfűzött két sor a B.2 melléklet escape-sorai: az alsó tartománysor a HTLOW mínusz egytől indul és lefelé számol, a felső tartománysor a HTHIGH-tól indul fix 32 bites tartománnyal, az opcionális OOB sor pedig egyáltalán nem hordoz értéket. A PDFlibPas a jbig2HuffmanLOW ($FFFFFFFD) és a jbig2HuffmanOOB ($FFFFFFFE) sentinel tartományhosszakkal jelöli őket, ugyanazzal a konvencióval, amit a tizenöt beépített szabványos táblája használ, így a dekódoló ciklus nem törődik azzal, hogy a tábla a specifikációból vagy a fájlból jött-e

Miért kell a prefixkódokat táblasorrendben kiosztani?

Mert a kódokat soha nem a kódoló írja le. Egy JBIG2 Tables szegmens csak prefixhosszakat hordoz, a tényleges bitmintázatot mindkét oldal a B.3 melléklet kanonikus eljárásával állítja vissza: megszámolja, hány sor tartozik az egyes hosszakhoz, először az egybites kódokat osztja ki, majd balra tol és folytat, egy hosszon belül pedig a sorok megjelenési sorrendjében adja ki a kódokat. Ettől a sorrendtől bármilyen eltérés csendben egy másik táblát állít elő. A dekóder nem fogja észrevenni, mert minden bitmintázat, amit generál, továbbra is érvényes prefixkód — csak épp nem az, amit a kódoló használt —, a kimenet pedig egy hihetően kinéző bitmap, rossz szimbólumokból összerakva

// 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            // stabil: az eredeti sorrend megmarad
  if table[I].prefixLen > 0 then       // minden prefixhosszon belül
  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;

A THuffmanDecoder.buildTable egyetlen okból számláló rendezés összehasonlító rendezés helyett: a Counts, Starts és Positions feletti számláló menet konstrukció szerint stabil, így az azonos prefixhosszúságú sorok a deklaráció sorrendjében kerülnek az eredménybe, ami pontosan az a sorrend, ami szerint a B.3 melléklet a kódokat kiosztja. A nulla prefixhosszúságú sorok még a kódkiosztás előtt kiesnek, mert a B.3 használatlanként definiálja őket, nem egybites kódként. Két őr ül ugyanabban a ciklusban. A túljelentkezés-ellenőrzés azokat a táblákat kapja el, amelyeknek a hosszai több kódot követelnek, mint amennyit egy ilyen mélységű prefixkód el tud tartani, ami a Kraft-egyenlőtlenség egész összehasonlítás formájában; nélküle egy ellenséges tábla olyan kódot állít elő, ami két sorra is illeszkedik, és a dekóder azt választja, amelyiket előbb beolvassa. A 32 bites plafon azért van, mert a prefix egy Cardinal, a decodeInt-ben lévő matcher pedig egyetlen változóba gyűjti a biteket. A T.88 papíron hosszabb prefixeket is enged, a PDFlibPas név szerint visszautasítja őket, és valódi kódolót még senki nem látott ilyet kibocsátani. Az értékaritmetika ugyanolyan gondosságot kíván, mint a kódaritmetika: a THuffmanTable.val egy Int64, az alsó tartománysor pedig val - readBits(32)-ként dekódolódik, azaz egy 32 bites előjel nélküli eltolást vonunk ki a HTLOW mínusz egyből. Integer köztes értékekkel ez a kivonás átfordul, az átfordult értéket pedig elfogadja szimbólumszélességként. A 64 bites út kiszámítja a valódi értéket, ellenőrzi az előjeles 32 bites tartomány ellen, és kivételt dob, ha nem fér bele, ami a csendes sérülést explicit visszautasítássá fordítja

Miért nem sültek el soha az egyedi táblák a 3.539.22 előtt?

Két hiba rejtette el egymást. Az első egy egysoros setter-bug volt: a TTextRegionHuffmanFlags.setFlags ugyanazon a néven kapta az argumentumát, mint a mező, ahova tárolt, így a Self.flagsAsInt := flagsAsInt az inicializálatlan mezőt önmagába írta, és minden szelektor nullaként olvasódott vissza, ami a szövegrégiókat az egyedi táblák helyett a szabványos F, H és K táblákon keresztül küldte. A második hiba miatt az első önmagában való javítása is korrupt szimbólumokat eredményezett volna. Amikor egy Huffman szimbólumszótár tömörítetlen kollektív bitmapekként tárolja a szimbólumait, minden sor utolsó bájtja részleges, a régi másoló ciklus pedig a padding-et — ami az érvényes bitek számát tartja — a legalsó érvényes bit pozíciójaként kezelte; egy 63 pixel széles sor egy bitet másolt az utolsó bájtjából hét helyett. A javított ciklus így fut: for bitPointer := 7 downto ((8 - padding) and 7), és a 7 bites és 9 bites szélességű szintetikus fixture-ök a bájt-határ mindkét oldalát rögzítik. A szelektorok helyes olvasásával a táblák abban a sorrendben osztódnak ki, ahogy a specifikáció felsorolja őket, amit a T.88 §7.4.3.1.2 a szövegrégiókra FS, DS, DT, RDW, RDH, RDX, RDY és RSIZE sorrendben rögzít, a §7.4.2.1.1 pedig a szimbólumszótárakra DH, DW, BMSIZE és AGGINST sorrendben. Minden kétbites szelektor 0 vagy 1 esetén a szabványos táblát jelenti, 2 fenntartott azokon a mezőkön, ahol csak két szabványos tábla van, 3 pedig az egyedit, és minden egyedi választás a hivatkozott szegmensek közül a következő Tables szegmenst fogyasztja, hivatkozási sorrendben. A NextCustomHuffmanTable pontosan ezt a bejárást csinálja, és missing custom Huffman table reference hibát dob, amikor egy régió kevesebb táblára hivatkozik, mint amennyit a szelektorai megkövetelnek. Még egy sor tartozik ugyanehhez a javításhoz: egy Huffman szimbólumszótár, aminek a bemeneti és új szimbólumai együtt egyet adnak ki, a log2 képletből nulla szimbólumkód-hosszt számol, míg a formátum Huffman-változata minden szimbólumazonosítót legalább egy bittel ír le, ezért a if sdHuffman and (symbolCodeLength = 0) then symbolCodeLength := 1 a TSymbolDictionarySegment-ben megakadályozza, hogy a finomítási és aggregált útvonal nulla bitet olvasson szimbólumazonosítónként

Mit garantál a szegmenshatár?

A PDFlibPas minden fejlécben a szegmensadat hosszát olyan szerződésként kezeli, amit mindkét irányban be kell tartani: egy szegmens nem olvashat a deklarált vége után, és nem fejeződhet be rövidebben úgy, hogy a következő fejlécet kiszámíthatatlan eltoláson hagyja maga mögött. Az ebből a szerződésből következő szabályok egyenként aprók. A 31. bitet beállító adathossz a T.88 §7.2.7 ismeretlen hosszúságú jelölője, a handleSegmentDataLength pedig negatív értékre képezi le, amit a readSegments egyenesen visszautasít, ahelyett hogy előre pásztázna egy terminátort. Minden hivatkozott szegmensszámnak kisebbnek kell lennie az aktuális szegmensszámnál, és már léteznie kell, így egy előre- vagy lógó hivatkozás még az előtt elbukik, hogy bármelyik régió feloldaná. Az END_OF_PAGE és az END_OF_FILE nulla bájt adatot kell hogy deklaráljon. Egy Profiles szegmens (52-es típus) egy 32 bites darabszámot, majd annyi 32 bites azonosítót hordoz, és egyáltalán nem tartalmaz pixelt, ezért a rendszer 4 plusz 4-szer a darabszám alakban ellenőrzi a deklarált hossz ellen, átugorja, és csak azért tartja meg a szegmenslistában, hogy a későbbi szegmensek még hivatkozhassanak rá szám szerint. Egy ismeretlen profilazonosító nem ismeretlen kódolás, és annak kezelni azt jelentené, hogy olyan fájlokat utasítunk vissza, amik tökéletesen dekódolhatók

// 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');
// ... hozd létre a szegmensobjektumot ehhez a típushoz ...
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;   // az MMR olvasatlanul hagyhatja az EOFB-t
  reader.bitPointer := 7;
end;

Annak a ciklusnak a vége az, ahol a dekóder egy korábbi verziója elrontotta az MMR-kódolt régiókat. Az MMR dekóder akkor tudja, hogy végzett, amikor az utolsó sor utolsó pixelét előállította, ami megtörténhet azelőtt, hogy elfogyasztotta volna az EOFB terminátort, amit a T.88 §6.2.5.7 helyez az adat végére. A régi kód azt feltételezte, hogy az olvasó a következő fejlécen áll, így a megmaradt terminátorbájtok szegmensszámként parse-olódtak, és a stream néhány bájttal később egy félrevezető hibával bukott el. Most a deklarált vég győz: azon túl olvasni hiba, rövidebben megállni normális, és az olvasó a DataEnd-re kerül visszaállított bitpointerrel, hogy a következő fejléc onnan olvasódjon, ahol a fájl mondta. Ugyanez a fegyelem jelenik meg mindenhol, ahol a PDFlibPas nem megbízható PDF-struktúrákat parse-ol: a deklarált hossz a határ, és a dekóder nem indul el egy barátságosabbat keresni

Honnan olvassa a Huffman-finomítás a bitmap méretét?

Mielőtt az aritmetikai dekóder elindul, és egy olyan mezőből, ami csak Huffman módban létezik. Amikor egy szövegrégió-példány finomítást hordoz (RI nem nulla) és az SBHUFF be van állítva, a T.88 §6.4.11 szerint a dekóder előbb a kiválasztott tábláikkal olvassa az RDW, RDH, RDX és RDY mezőket, majd a BMSIZE-t az RSIZE táblával, aztán bájt-határra igazít, és csak ezután futtatja az általános finomítási dekódolást pontosan BMSIZE bájton. Az aritmetikai módú szövegrégióknak nincs ilyen mezőjük, és egy dekóder, ami egy kódútvonalat oszt meg a két mód között, át fogja ugrani, két vagy több bájttal korábban indítja az aritmetikai dekódert, és minden szimbólumot szemét ellenében finomít. A szimbólumszótár REFAGG-gal és egyetlen finomítási példánnyal járó útjának, amit a §6.5.8.2.2 ír le, ugyanaz a BMSIZE mezője és ugyanazok a következményei. A PDFlibPasban ennek a méretnek a felső korlátja a TStreamReader.SegmentEnd, az aktuális szegmens vége, ahogy a readSegments beállította, nem pedig a teljes stream vége, mert egy olyan BMSIZE, ami csak a következő szegmensből kölcsönzött bájtokkal teljesíthető, hibás, és a stream hosszához validálni azt jelentené, hogy az aritmetikai dekóder a következő fejlécbe olvas. A kétbájtos alsó korlát azt a kezdeti bájtpárt tükrözi, amit az aritmetikai dekóder mindig elfogyaszt, a finomítás után pedig az olvasó a RefinementEnd-re ugrik, függetlenül attól, milyen messzire olvasott előre az aritmetikai dekóder, mert a végpozíciója nem a következő Huffman-kódolt mező pozíciója

// TJBIG2Bitmap szövegrégió-dekódolás, Huffman-finomítási útvonal
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 ellenőriztünk, és mit utasítunk még mindig vissza

Az a minta, ami ezt elindította, egy 500 × 473 pixeles JBIG2 kép egyedi táblákkal és Huffman-finomítással, ma nulla eltérő pixellel dekódolódik egy független dekóderrel összevetve, a szintetikus 7 bites és 9 bites kollektív bitmap fixture-ök pedig mindkettőn a várt sorokat adják. A két független dekóder, ami az eredeti mintán nem értett egyet, még mindig nem ért egyet egymással; a PDFlibPas az egyikkel egyezik, és a becsületes megfogalmazás az, hogy a natív kimenet egy független implementációval és az olvasott specifikációval egyezik, nem az, hogy a világ minden dekódere egyetért. A hibás bemenetek oldalát a sorozat lefedi:

• fenntartott flag-bit vagy fenntartott szelektorérték
• egy tábla, ami egy sor közepén megszakad
• túljelentkezett prefixhosszak és 32 bitnél hosszabb prefixek
• egy régió, aminek a szelektorai több egyedi táblát kérnek, mint amennyire hivatkozik
• annak igazolása, hogy egy sikertelen dekódolás után az elavult kimenet törlődik, nem pedig ott marad, hogy a hívó eredménynek nézze

Három korlát szándékosan megmarad. A random-access stream-szervezés, ahol minden szegmensfejléc megelőzi az összes szegmensadatot, rögtön a fájlfejléc flagek beolvasásakor JBIG2 random-access organisation is not supported hibát dob, mert nincs reprezentatív minta, amin validálni lehetne, és egy félig implementált útvonal rosszabb egy névvel ellátott visszautasításnál. Az egyedi táblák 65 536 sorban és 32 bites prefixekben vannak maximálva. A nyilvános dekódolási belépési pont pedig, a TPLJBIG2Decoder.LoadFromByteArray, stream-sorrendben az első oldal bitmapjét adja vissza a getPageAsJBIG2Bitmap(0)-n keresztül, az elsőként előkerülő page-information szegmensét, ahelyett hogy a nulla oldalasszociációra keresne; a beágyazott PDF streamek rutinszerűen 1-nek számozzák az egyetlen oldalukat, és a nulla oldalt asszociáció szerint kérni nem találna semmit. A hibaüzenet a TPLJBIG2Decoder.LastError-be kerül, abba a belső dekóder-diagnosztikába, ami a hiba szegmensszámát, típusát és bájteltolását hordozza, és nem ugyanaz, mint a könyvtárszintű TPDFlib.LastErrorCode. Mindez nem érinti a kódolási oldalt, amit a JBIG2 kódoló back-endekről és linkelésükről szóló jegyzetek tárgyalnak; az olvasási útvonalnak el kell fogadnia, amit valaki más kódolója kibocsátani döntött, és a szabályait az image-stack többi részével osztja, beleértve a beépített TIFF-dekódert és annak BigTIFF- és csempézett elrendezés visszautasításait: utasíts vissza név szerint, soha ne kölcsönözz bájtokat egy deklarált határon át, és tartsd elég szélesen az aritmetikát, hogy egy átfordult köztes érték ne mehessen át érvényes válaszként. Ha natív JBIG2 olvasási útvonalat értékelsz Delphihez vagy C++Builderhez, a dekóder és az image-kezelés többi része a PDF Library for Delphi oldalán van dokumentálva