Vlastné Huffmanove tabuľky JBIG2 v čistom Pascal dekodéri

PDFlibPas vo verzii 3.539.22 dekóduje vlastné Huffmanove tabuľky JBIG2 natívne: čistý Pascal dekodér v PDFlibJBIG2.pas parsuje segment Tables (typ 53), priraďuje kanonické prefixové kódy v poradí riadkov tabuľky, ako to vyžaduje ITU-T T.88 Annex B.3, konzumuje referencie na vlastné tabuľky v poradí selektorov pre symbol dictionaries aj text regions a ohraničuje každé čítanie deklarovanou dĺžkou segmentu, nie tým, aké bajty náhodou nasledujú

Súbor, ktorý túto prácu vynútil, bol na pohľad nenápadný. Naskenovaná zmluva, komprimovaná cez JBIG2 s Huffmanovým kódovaním symbolov namiesto oveľa bežnejšieho aritmetického kódovania, a encoder si k tomu posielal vlastné kódové tabuľky namiesto štandardných tabuliek B.1 až B.15. Dva nezávislé dekodéry sa nezhodli na refinement pixeloch a vtedajší dekodér PDFlibPas produkoval text, ktorý vyzeral, akoby prešiel skartovačkou: fragmenty glyfov posunuté o pár pixelov, v každom znaku chýbal jeden stĺpec. Nič nevyhodilo chybu. Presne tak vyzerá chyba, ktorá prežije roky, pretože dekodér, čo súbor odmietne, skončí ako support ticket, kým dekodér, ktorý ho vykreslí mierne zle, vyrobí zákazníka, ktorý si myslí, že zlý bol sken

Čo vlastne obsahuje segment Tables v JBIG2?

Segment Tables je kompaktný opis jednej Huffmanovej tabuľky: jeden flags bajt, dve znamienkové 32-bitové hranice a potom séria dvojíc (prefix length, range length), ktoré rozdelia interval medzi hranicami, presne ako to opisuje T.88 §7.4.13 a Annex B.2. Bit 0 flags bajtu je HTOOB a hovorí, či tabuľka má out-of-band kód. Bity 1 až 3 plus jedna dávajú HTPS, teda počet bitov, ktorými sa zapisuje každá prefix length; bity 4 až 6 plus jedna dávajú HTRS, šírku poľa range length. Bit 7 je rezervovaný a PDFlibPas segment odmietne, ak je nastavený, namiesto toho, aby hádal, čo tým nejaká budúca revízia myslela. Nasledujú HTLOW a HTHIGH ako znamienkové 32-bitové celé čísla, a práve tu sa dekodér môže po prvý raz pomýliť: ak ich číta ako neznamienkové, tabuľka s negatívnou dolnou hranicou, čo je pri delta-kódovaných šírkach symbolov úplne bežné, vyzerá, akoby začínala na štyroch miliardách. Každé pole ide cez lokálny helper ReadField, ktorý pred dotykom na čítačku overí požiadavku proti bitovej pozícii, kde končia dáta segmentu, pretože tabuľka, ktorá by čítala za svoj segment, by ako prefix lengths konzumovala hlavičku nasledujúceho segmentu

// 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));      // znamienkový HTLOW
HighValue  := Integer(ReadField(32));      // znamienkový 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 riadky pripojené za slučkou sú escape riadky z Annex B.2: dolný range riadok začína na HTLOW mínus jedna a počíta smerom nadol, horný range riadok začína na HTHIGH s pevným 32-bitovým rozsahom a voliteľný OOB riadok nemá hodnotu žiadnu. PDFlibPas ich označuje sentinelovými range lengths jbig2HuffmanLOW ($FFFFFFFD) a jbig2HuffmanOOB ($FFFFFFFE), teda tou istou konvenciou, akú používa jeho pätnásť vstavaných štandardných tabuliek, takže dekódovacej slučke je jedno, či tabuľka prišla zo špecifikácie alebo zo súboru

Prečo sa prefixové kódy musia priraďovať v poradí riadkov tabuľky?

Pretože encoder tie kódy nikdy nezapíše. Segment Tables v JBIG2 nesie len prefix lengths a obe strany rekonštruujú konkrétne bitové vzory kanonickým postupom z Annex B.3: spočítajte, koľko riadkov má ktorú dĺžku, najprv priraďte kódy dĺžky jedna, potom posúvajte doľava a pokračujte, a v rámci jednej dĺžky rozdávajte kódy v poradí, v akom riadky prichádzajú. Akákoľvek odchýlka od toho poradia potichu vyrobí inú tabuľku. Dekodér si to nevšimne, pretože každý bitový vzor, ktorý vygeneruje, je stále platný prefixový kód, len nie ten, ktorý použil encoder, a na výstupe je vierohodne vyzerajúca bitmapa poskladaná z nesprávnych symbolov

// 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            // stabilné: pôvodné poradie zachované
  if table[I].prefixLen > 0 then       // v rámci každej prefix length
  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, nie porovnávací sort, a to z jedného dôvodu: counting prechod cez Counts, Starts a Positions je stabilný už zo svojej podstaty, takže riadky s rovnakou prefix length pristanú vo výsledku v poradí, v akom boli deklarované, a práve podľa toho poradia Annex B.3 priraďuje kódy. Riadky s nulovou prefix length sa pred priradením kódov zahodia, pretože B.3 ich definuje ako nepoužité, nie ako jednobitové kódy. V tej istej slučke sedia dve stráže. Kontrola oversubscription zachytí tabuľku, ktorej dĺžky si nárokujú viac kódov, než sa do prefixového kódu tej hĺbky zmestí, čo je Kraftova nerovnosť vyjadrená ako porovnanie celých čísel; bez nej nepriateľská tabuľka vyrobí kód, ktorý sedí na dva riadky, a dekodér si vyberie ten, na ktorý narazí skôr. Strop 32 bitov existuje preto, že prefix je Cardinal a matcher v decodeInt akumuluje bity do jedného. T.88 na papieri dovoľuje dlhšie prefixy, PDFlibPas ich odmieta menovite a žiadny reálny encoder sa s takým nevidel. Aritmetika hodnôt si vyžaduje rovnakú starostlivosť ako aritmetika kódov: THuffmanTable.val je Int64 a dolný range riadok sa dekóduje ako val - readBits(32), teda 32-bitový neznamienkový offset odčítaný od HTLOW mínus jedna. S medzivýsledkami typu Integer sa to odčítanie pretočí a pretočená hodnota sa potom prijme ako šírka symbolu. 64-bitová cesta spočíta skutočnú hodnotu, overí ju proti znamienkovému 32-bitovému rozsahu a ak sa nezmestí, vyhodí výnimku, čím sa tichá korupcia mení na explicitné odmietnutie

Prečo vlastné tabuľky pred 3.539.22 nikdy nezabrali?

Dva defekty sa navzájom skrývali. Prvý bola chyba v jednoriadkovom setteri: TTextRegionHuffmanFlags.setFlags dostal svoj argument pod tým istým menom, aké malo pole, do ktorého ho ukladal, takže Self.flagsAsInt := flagsAsInt priradilo neinicializované pole samo sebe a každý selektor sa čítal ako nula, čo posielalo text regions žiadajúce vlastné tabuľky cez štandardné tabuľky F, H a K. Druhý defekt znamenal, že samotná oprava prvého by stále produkovala skorumpované symboly. Keď Huffman symbol dictionary ukladá svoje symboly ako nekomprimovanú collective bitmap, posledný bajt každého riadku je čiastočný a stará kopírovacia slučka brala padding, v ktorom je počet platných bitov, ako pozíciu najnižšieho platného bitu; riadok široký 63 pixelov tak skopíroval z posledného bajtu jeden bit namiesto siedmich. Opravená slučka beží for bitPointer := 7 downto ((8 - padding) and 7) a syntetické fixture so šírkou 7 a 9 bitov pripínajú obe strany bajtovej hranice. Keď selektory čítajú správne, tabuľky sa rozdávajú v poradí, v akom ich vypisuje špecifikácia, čo T.88 §7.4.3.1.2 fixuje pre text regions ako FS, DS, DT, RDW, RDH, RDX, RDY a RSIZE a §7.4.2.1.1 fixuje pre symbol dictionaries ako DH, DW, BMSIZE a AGGINST. Každý dvojbitový selektor znamená štandardnú tabuľku 0 alebo 1, hodnota 2 je rezervovaná pre polia, ktoré majú len dve štandardné tabuľky, a hodnota 3 znamená vlastnú, pričom každý výber vlastnej tabuľky skonzumuje ďalší segment Tables spomedzi referencovaných segmentov v poradí referencií. NextCustomHuffmanTable robí presne ten prechod a vyhodí missing custom Huffman table reference, keď oblasť odkazuje na menej tabuliek, než koľko si jej selektory vyžadujú. Do tej istej opravy patrí ešte jeden riadok: Huffman symbol dictionary, ktorému vstupné a nové symboly dajú spolu jednu, spočíta z log2 vzorca dĺžku kódu symbolu nula, kým Huffmanova varianta formátu zapisuje každé symbol ID aspoň jedným bitom, takže if sdHuffman and (symbolCodeLength = 0) then symbolCodeLength := 1 v TSymbolDictionarySegment drží refinement aj aggregate cestu od toho, aby čítali nula bitov na symbol ID

Čo garantuje hranica segmentu?

PDFlibPas berie dĺžku dát segmentu v každej hlavičke ako kontrakt, ktorý musia dodržať obe strany: segment nesmie čítať za svoj deklarovaný koniec a nesmie skončiť skôr a nechať nasledujúcu hlavičku na nepredvídateľnom offsete. Pravidlá, ktoré z toho kontraktu vyplývajú, sú jednotlivo drobné. Dĺžka dát s nastaveným bitom 31 je marker neznámej dĺžky z T.88 §7.2.7 a handleSegmentDataLength ho mapuje na zápornú hodnotu, ktorú readSegments rovno odmietne, namiesto toho, aby dopredu skenoval terminátor. Každé referencované číslo segmentu musí byť menšie než číslo aktuálneho segmentu a musí už existovať, takže dopredná alebo visiaca referencia zlyhá skôr, než sa ju pokúsi vyriešiť akákoľvek oblasť. END_OF_PAGE a END_OF_FILE musia deklarovať nula bajtov dát. Segment Profiles (typ 52) nesie 32-bitový počet a za ním toľko 32-bitových identifikátorov a žiadne pixely, takže sa kontroluje ako 4 plus 4 krát počet proti deklarovanej dĺžke, preskočí sa a v zozname segmentov zostane len preto, aby naň neskoršie segmenty mohli stále odkazovať číslom. Neznámy identifikátor profilu nie je neznáme kódovanie a brať ho ako neznáme by odmietlo súbory, ktoré sa dekódujú úplne v poriadku

// 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');
// ... vytvor objekt segmentu pre tento typ ...
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 môže nechať EOFB neprečítaný
  reader.bitPointer := 7;
end;

Chvost tej slučky je miesto, kde sa staršia verzia dekodéra pomýlila pri MMR-kódovaných oblastiach. MMR dekodér vie, že skončil, keď vyprodukuje posledný pixel posledného riadku, a to sa môže stať skôr, než skonzumuje terminátor EOFB, ktorý T.88 §6.2.5.7 umiestňuje na koniec dát. Starý kód predpokladal, že čítačka stojí na nasledujúcej hlavičke, takže zvyšné bajty terminátora sa naparsovali ako číslo segmentu a stream zlyhal o pár bajtov neskôr s mätúcou chybou. Teraz vyhráva deklarovaný koniec: čítanie za ním je chyba, zastavenie pred ním je normálne a čítačka sa posunie na DataEnd s vynulovaným bit pointerom, aby sa nasledujúca hlavička čítala odtiaľ, kde súbor tvrdil, že bude. Tá istá disciplína sa objavuje všade, kde PDFlibPas parsuje nedôveryhodné PDF štruktúry: deklarovaná dĺžka je hranica a dekodér si nechodí hľadať priateľskejšiu

Odkiaľ si Huffman refinement číta veľkosť bitmapy?

Predtým, než sa rozbehne aritmetický dekodér, a z poľa, ktoré existuje len v Huffman režime. Keď inštancia text region nesie refinement (RI je nenulové) a je nastavený SBHUFF, T.88 §6.4.11 núti dekodér prečítať RDW, RDH, RDX a RDY s ich vybranými tabuľkami, potom BMSIZE s tabuľkou RSIZE, potom sa zarovnať na bajtovú hranicu a až potom spustiť generické refinement dekódovanie presne cez BMSIZE bajtov. Text regions v aritmetickom režime také pole nemajú a dekodér, ktorý zdieľa jednu cestu kódu pre oba režimy, ho preskočí, naštartuje aritmetický dekodér o dva a viac bajtov skôr a každý symbol vyrefinuje proti odpadu. Cesta symbol dictionary s REFAGG a jedinou refinement inštanciou, opísaná v §6.5.8.2.2, má to isté pole BMSIZE s tými istými následkami. V PDFlibPas je hornou hranicou tej veľkosti TStreamReader.SegmentEnd, teda koniec aktuálneho segmentu tak, ako ho nastavil readSegments, nie koniec celého streamu, pretože BMSIZE, ktorý sa dá naplniť len požičaním bajtov z nasledujúceho segmentu, je malformovaný, a validovať ho proti dĺžke streamu by dovolilo aritmetickému dekodéru čítať do nasledujúcej hlavičky. Dolná hranica dvoch bajtov odzrkadľuje počiatočnú dvojicu bajtov, ktorú aritmetický dekodér vždy skonzumuje, a po refinemente čítačka skočí na RefinementEnd bez ohľadu na to, ako ďaleko dopredu aritmetický dekodér čítal, keďže jeho konečná pozícia nie je pozícia nasledujúceho Huffman-kódovaného poľa

// Dekódovanie text region v TJBIG2Bitmap, vetva Huffman refinement
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;

Čo bolo overené a čo sa stále odmieta

Vzorka, ktorá to celé spustila, 500 na 473 pixelov veľký obrázok JBIG2 s vlastnými tabuľkami a Huffman refinementom, sa teraz dekóduje na bitmapu s nulovým počtom odlišných pixelov proti nezávislému dekodéru a syntetické fixture s 7-bitovou a 9-bitovou collective bitmap dávajú očakávané riadky na oboch. Dva nezávislé dekodéry, ktoré sa nezhodli na pôvodnej vzorke, sa nezhodujú ani navzájom; PDFlibPas sa zhoduje s jedným z nich a poctivá formulácia je, že natívny výstup súhlasí s jednou nezávislou implementáciou a s takto prečítanou špecifikáciou, nie že súhlasia všetky dekodéry sveta. Malformovaná strana sady pokrýva:

• rezervovaný flag bit alebo rezervovanú hodnotu selektora
• tabuľku skrátenú v strede riadku
• oversubscribed prefix lengths a prefixy dlhšie než 32 bitov
• oblasť, ktorej selektory žiadajú viac vlastných tabuliek, než na koľko odkazuje
• potvrdenie, že po neúspešnom dekódovaní sa starý výstup vyčistí a nezostane na mieste, aby si ho volajúci pomýlil s výsledkom

Tri limity zostávajú zámerné. Random-access organizácia streamu, kde všetky hlavičky segmentov predchádzajú všetkým dátam segmentov, vyhodí JBIG2 random-access organisation is not supported hneď po prečítaní flagov hlavičky súboru, pretože neexistuje reprezentatívna vzorka, proti ktorej by sa dala validovať, a napoly implementovaná cesta je horšia než pomenované odmietnutie. Vlastné tabuľky sú ohraničené na 65 536 riadkov a 32-bitové prefixy. A verejný vstupný bod dekódovania TPLJBIG2Decoder.LoadFromByteArray vracia prvú bitmapu stránky v poradí streamu cez getPageAsJBIG2Bitmap(0), teda prvý nájdený segment s informáciami o stránke, namiesto vyhľadania asociácie stránky nula; vložené PDF streamy svoju jedinú stránku bežne číslujú ako 1 a pýtať sa na stránku 0 podľa asociácie by nenašlo nič. Text zlyhania pristane v TPLJBIG2Decoder.LastError, v internom diagnostickom poli dekodéra, ktoré nesie číslo segmentu, typ a bajtový offset poruchy, a nie je tou istou vecou ako TPDFlib.LastErrorCode na úrovni knižnice. Nič z toho sa nedotýka kódovacej strany, ktorú pokrývajú poznámky o backendoch JBIG2 encodera a ich linkovaní; čítacia cesta musí prijať, čo sa rozhodol vyprodukovať encoder niekoho iného, a zdieľa svoje pravidlá so zvyškom obrázkovej vetvy vrátane vstavaného TIFF dekodéru a jeho odmietnutí BigTIFF a tiled rozložení: odmietni menovite, nikdy si nepožičiavaj bajty cez deklarovanú hranicu a drž aritmetiku dosť širokú na to, aby pretočený medzivýsledok nemohol prejsť ako platná odpoveď. Ak zvažujete natívnu JBIG2 čítaciu cestu pre Delphi alebo C++Builder, dekodér a zvyšok spracovania obrázkov sú zdokumentované na stránke PDF Library for Delphi