Vlastní Huffmanovy tabulky JBIG2 v Pascalovém dekodéru PDF

PDFlibPas ve verzi 3.539.22 dekóduje vlastní Huffmanovy tabulky JBIG2 nativně: čistě Pascalový dekodér v PDFlibJBIG2.pas parsuje segment Tables (typ 53), přiděluje kanonické prefixové kódy v pořadí řádků tabulky, jak vyžaduje příloha B.3 ITU-T T.88, konzumuje odkazy na vlastní tabulky v pořadí selectorů pro symbolové slovníky i textové regiony a každé čtení ohraničuje deklarovanou délkou segmentu, nikoli tím, jaké bajty náhodou následují

Soubor, který vynutil tuhle práci, byl na pohled nepozoruhodný. Naskenovaná smlouva, komprimovaná přes JBIG2 s Huffmanovým symbolovým kódováním místo daleko běžnějšího aritmetického kódování, a s tím, že si encoder posílá vlastní kódové tabulky místo standardních tabulek B.1 až B.15. Dva nezávislé dekodéry se neshodly na jeho refinement pixelech a tehdejší dekodér PDFlibPas produkoval text, který vypadal, jako prošel skartovačkou: fragmenty glyfů posunuté o pár pixelů, u každého znaku chyběl jeden sloupec. Nic nevyhodilo chybu. To je tvar chyby, která přežije roky, protože dekodér, který soubor odmítne, dostane support ticket, zatímco dekodér, který to vykreslí trochu špatně, dostane zákazníka, jenž předpokládá, že špatný byl sken

Co segment Tables v JBIG2 vlastně obsahuje?

Segment Tables je kompaktní popis jedné Huffmanovy tabulky: jeden byte příznaků, dvě znaménkové 32bitové meze a pak běh párů (délka prefixu, délka rozsahu), které rozdělí interval mezi mezemi, jak je rozepsáno v T.88 §7.4.13 a příloze B.2. Bit 0 bytu příznaků je HTOOB a říká, zda má tabulka out-of-band kód. Bity 1 až 3 plus jedna dávají HTPS, počet bitů na zápis každé délky prefixu; bity 4 až 6 plus jedna dávají HTRS, šířku každého pole délky rozsahu. Bit 7 je rezervovaný a PDFlibPas segment odmítne, když je nastavený, místo aby hádal, co jím autor budoucí revize myslel. HTLOW a HTHIGH následují jako znaménková 32bitová celá čísla a tohle je první místo, kde se dekodér může splést: čte-li je jako unsigned, tabulka se zápornou spodní mezí — pro delta-kódované šířky symbolů úplně normální — vypadá, jako by začínala na čtyři miliardy. Každé pole projde lokálním helperem ReadField, který před saháním na čtečku zkontroluje požadavek proti bitové pozici, kde data segmentu končí, protože tabulka, která čte za svým segmentem, by si jako délky prefixu svačila hlavičku dalšího 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));      // znaménkové HTLOW
HighValue  := Integer(ReadField(32));      // znaménkové 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);

Ty dva řádky přidané za smyčkou jsou únikové řádky z přílohy B.2: spodní řádek rozsahu začíná na HTLOW minus jedna a počítá dolů, horní řádek rozsahu začíná na HTHIGH s pevným 32bitovým rozsahem a volitelný řádek OOB nemá žádnou hodnotu. PDFlibPas je označuje sentinelovými délkami rozsahu jbig2HuffmanLOW ($FFFFFFFD) a jbig2HuffmanOOB ($FFFFFFFE), stejnou konvencí, jakou používá jeho patnáct vestavěných standardních tabulek, takže dekódovací smyčka neřeší, jestli tabulka přišla ze specifikace nebo ze souboru

Proč se prefixové kódy musí přidělovat v pořadí řádků tabulky?

Protože encoder kódy nikdy nezapisuje. Segment Tables v JBIG2 nese jen délky prefixů a obě strany rekonstruují skutečné bitové vzory kanonickým postupem z přílohy B.3: spočítejte, kolik řádků má každou délku, přidělte nejdřív kódy délky jedna, pak posuňte doleva a pokračujte a v rámci jedné délky rozdávejte kódy v pořadí, v jakém řádky vystupují. Jakákoli odchylka od toho pořadí tiše vytvoří jinou tabulku. Dekodér si toho nevšimne, protože každý bitový vzor, který vygeneruje, je stále platný prefixový kód, jen ne ten, který použil encoder, a výstupem je věrohodně vypadající bitmapa složená ze špatných symbolů

// 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í pořadí zůstává
  if table[I].prefixLen > 0 then       // v rámci každé délky prefixu
  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, ne srovnávací sort, a to z jednoho důvodu: počítací průchod přes Counts, Starts a Positions je stabilní konstrukcí, takže řádky se stejnou délkou prefixu dopadnou do výsledku v pořadí deklarace — přesně podle toho pořadí přiděluje kódy příloha B.3. Řádky s nulovou délkou prefixu se zahodí před přidělováním kódů, protože B.3 je definuje jako nepoužité, ne jako jednobitové kódy. Ve stejné smyčce sedí dvě hlídky. Kontrola přeplnění chytí tabulku, jejíž délky si nárokují víc kódů, než dokáže pojmout prefixový kód té hloubky — Kraftova nerovnost vyjádřená jako porovnání celých čísel; bez ní nepřátelská tabulka vytvoří kód, který sedí na dva řádky, a dekodér vybere to, na co narazí první. Strop 32 bitů existuje proto, že prefix je Cardinal a matcher ve decodeInt do něj bity akumuluje. T.88 povoluje delší prefixy na papíře, PDFlibPas je odmítá jmenovitě a žádný reálný encoder nebyl viděn, že by nějaký vysílal. Aritmetika hodnot si žádá stejnou péči jako aritmetika kódů: THuffmanTable.val je Int64 a spodní řádek rozsahu se dekóduje jako val - readBits(32), tedy 32bitový unsigned offset odečtený od HTLOW minus jedna. S Integer mezivýsledky se ten odečet přeteče a přetečená hodnota pak projde jako šířka symbolu. 64bitová cesta spočítá skutečnou hodnotu, zkontroluje ji proti znaménkovému 32bitovému rozsahu a vyhodí výjimku, pokud se nevejde, čímž z tichého poškození udělá výslovné odmítnutí

Proč se vlastní tabulky před 3.539.22 nikdy neaktivovaly?

Dvě vady se navzájem kryly. První byla jednořádková chyba setteru: TTextRegionHuffmanFlags.setFlags přijímal argument pod stejným jménem, jaké má pole, do kterého ho ukládal, takže Self.flagsAsInt := flagsAsInt přiřadilo neinicializované pole samo sobě a každý selector se četl jako nula, což poslalo textové regiony žadonící o vlastní tabulky do standardních tabulek F, H a K. Druhá vada znamenala, že samotná oprava té první by stejně produkovala poškozené symboly. Když Huffmanův symbolový slovník ukládá své symboly jako nekomprimovanou kolektivní bitmapu, poslední byte každého řádku je částečný a stará kopírovací smyčka brala padding, který drží počet platných bitů, jako pozici nejnižšího platného bitu; řádek široký 63 pixelů zkopíroval ze svého posledního bytu jeden bit místo sedmi. Opravená smyčka běží for bitPointer := 7 downto ((8 - padding) and 7) a syntetické fixture široké 7 a 9 bitů přibíjí obě strany bajtové hranice. Se správně čtenými selectory se tabulky rozdávají v pořadí, v jakém je specifikace vyjmenovává — T.88 §7.4.3.1.2 pro textové regiony fixuje FS, DS, DT, RDW, RDH, RDX, RDY a RSIZE a §7.4.2.1.1 pro symbolové slovníky DH, DW, BMSIZE a AGGINST. Každý dvoubitový selector znamená standardní tabulku 0 nebo 1, pro 2 rezervu u polí se pouze dvěma standardními tabulkami a pro 3 vlastní, a každý vlastní výběr spotřebuje další segment Tables mezi odkazovanými segmenty v pořadí odkazů. NextCustomHuffmanTable dělá přesně tenhle průchod a vyhodí missing custom Huffman table reference, když region odkazuje na méně tabulek, než kolik vyžadují jeho selectory. Jedna další řádka patří ke stejné opravě: Huffmanův symbolový slovník, u kterého se vstupní a nové symboly sečtou na jednu, spočítá z log2 vzorce délku symbolového kódu nula, zatímco Huffmanova varianta formátu zapisuje každé symbolové ID aspoň jedním bitem, takže if sdHuffman and (symbolCodeLength = 0) then symbolCodeLength := 1 v TSymbolDictionarySegment brání cestě refinementu a agregace číst nula bitů na symbolové ID

Co garantuje hranice segmentu?

PDFlibPas bere délku dat segmentu v každé hlavičce jako kontrakt, který musí obě strany dodržet: segment nesmí číst za svým deklarovaným koncem a nesmí skončit dřív a nechat další hlavičku na nepředvídatelném offsetu. Pravidla, která z toho kontraktu vypadla, jsou jednotlivě malá. Délka dat s nastaveným bitem 31 je marker neznámé délky z T.88 §7.2.7 a handleSegmentDataLength ho mapuje na zápornou hodnotu, kterou readSegments rovnou odmítne, místo aby skenovala dopředu za terminátorem. Každé odkazované číslo segmentu musí být menší než číslo aktuálního segmentu a už musí existovat, takže dopředný nebo visící odkaz selže, než se ho kterýkoli region pokusí vyřešit. END_OF_PAGE a END_OF_FILE musí deklarovat nula bajtů dat. Segment Profiles (typ 52) nese 32bitový počet a za ním tolik 32bitových identifikátorů a žádné pixely, takže se kontroluje jako 4 plus 4 krát počet proti deklarované délce, přeskočí a v seznamu segmentů se drží jen proto, aby se na něj pozdější segmenty mohly stále odkazovat číslem. Neznámý profilový identifikátor není neznámé kódování a brát ho tak by odmítlo soubory, které se dekódují úplně v pořádku

// 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');
// ... vytvoř objekt segmentu pro 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 nechat EOFB nepřečtený
  reader.bitPointer := 7;
end;

Na ocase té smyčky se dřívější verze dekodéru spletla u regionů kódovaných MMR. MMR dekodér ví, že skončil, když se vytvoří poslední pixel posledního řádku, což může nastat dřív, než stihne skonzumovat terminátor EOFB, který T.88 §6.2.5.7 klade na konec dat. Starý kód předpokládal, že čtečka stojí na další hlavičce, takže zbylé bajty terminátoru se parsovaly jako číslo segmentu a stream o pár bajtů později spadl s zavádějící chybou. Teď vyhrává deklarovaný konec: čtení za ním je chyba, zastavit se dřív je normální a čtečka se přesune na DataEnd s resetovaným bitovým ukazatelem, takže další hlavička se čte odtud, kde ji soubor slíbil. Stejná disciplína se ukazuje všude tam, kde PDFlibPas parsuje nedůvěryhodné PDF struktury: deklarovaná délka je hranice a dekodér si nechodí hledat žádnou pohodlnější

Odkud čte Huffman refinement velikost své bitmapy?

Než se spustí aritmetický dekodér, a z pole, které existuje jen v Huffmanovém režimu. Když instance textového regionu nese refinement (RI je nenulové) a SBHUFF je nastavený, nařizuje T.88 §6.4.11 dekodéru přečíst RDW, RDH, RDX a RDY svými vybranými tabulkami, pak BMSIZE tabulkou RSIZE, pak se vyrovnat na bajtovou hranici a teprve potom spustit generické dekódování refinementu přes přesně BMSIZE bajtů. Textové regiony v aritmetickém režimu takové pole nemají a dekodér, který sdílí jednu kódovou cestu pro oba režimy, ho přeskočí, spustí aritmetický dekodér o dva a víc bajtů dřív a refinuje každý symbol proti odpadu. Cesta symbolového slovníku s REFAGG a jedinou instancí refinementu, popsaná v §6.5.8.2.2, má také pole BMSIZE se stejnými důsledky. V PDFlibPas je horní mez té velikosti TStreamReader.SegmentEnd, konec aktuálního segmentu tak, jak ho nastavuje readSegments, ne konec celého streamu, protože BMSIZE, které se dá uspokojit jen vypůjčením bajtů z následujícího segmentu, je deformované a jeho ověřování proti délce streamu by aritmetickému dekodéru dovolilo číst až do další hlavičky. Spodní mez dvou bajtů odpovídá počátečnímu páru bajtů, který aritmetický dekodér konzumuje vždy, a po refinementu skočí čtečka na RefinementEnd bez ohledu na to, jak daleko aritmetický dekodér četl dopředu, protože jeho konečná pozice není pozicí dalšího Huffmanem kódovaného pole

// TJBIG2Bitmap dekódování textového regionu, cesta Huffman refinementu
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;

Co se ověřilo a co se pořád odmítá

Vzorek, který tohle všechno rozjíždíl — JBIG2 obrázek 500 na 473 pixelů s vlastními tabulkami a Huffman refinementem — se teď dekóduje do bitmapy s nulou rozdílných pixelů vůči nezávislému dekodéru a syntetické kolektivní bitmapy široké 7 a 9 bitů produkují očekávané řádky na obou. Ty dva nezávislé dekodéry, které se hádaly o původním vzorku, se přestále hádají i mezi sebou; PDFlibPas sedí na jednom z nich a poctivé tvrzení zní, že nativní výstup souhlasí s jednou nezávislou implementací a se specifikací, jak byla čtena — ne že se shoduje každý dekodér na světě. Deformovaná strana sady pokrývá:

• rezervovaný bit příznaků nebo rezervovanou hodnotu selectoru
• tabulku useknutou uprostřed řádku
• přeplněné délky prefixů a prefixy delší než 32 bitů
• region, jehož selectory žádají víc vlastních tabulek, než na kolik odkazuje
• potvrzení, že po neúspěšném dekódu se starý výstup vymaže, místo aby zůstal viset a volající si ho spletl s výsledkem

Tři limity zůstávají záměrné. Organizace streamu s náhodným přístupem, kde všechny hlavičky segmentů předcházejí všem datům segmentů, vyhodí JBIG2 random-access organisation is not supported hned, jakmile se přečtou příznaky hlavičky souboru, protože neexistuje žádný reprezentativní vzorek, proti kterému by se to dalo ověřit, a napůl implementovaná cesta je horší než jmenovité odmítnutí. Vlastní tabulky mají strop 65 536 řádků a 32bitových prefixů. A veřejný dekódovací vstup, TPLJBIG2Decoder.LoadFromByteArray, vrací bitmapu první stránky v pořadí streamu přes getPageAsJBIG2Bitmap(0), tedy první narazený segment page-information, místo aby hledal přiřazení stránky nula; vestavěné PDF streamy číslují svou jedinou stránku obvykle 1 a dotaz na stránku 0 podle přiřazení by nenašel nic. Text selhání dopadá do TPLJBIG2Decoder.LastError, interní diagnostiky dekodéru, která nese číslo segmentu, typ a bajtový offset vady, a není totéž co knihovní TPDFlib.LastErrorCode. Nic z toho se nedotýká stránky kódování, kterou pokrývají poznámky o backendech JBIG2 encoderu a jejich linkování; čtecí cesta musí přijmout, co se rozhodl vysílat encoder někoho jiného, a svá pravidla sdílí se zbytkem obrazového stacku, včetně vestavěného dekodéru TIFF a jeho odmítání BigTIFF a tiled rozvržení: odmítej jmenovitě, nikdy si nevypůjčuj bajty přes deklarovanou hranici a drž aritmetiku dost širokou, aby přetečený mezivýsledek neprošel za platnou odpověď. Když hodnotíte nativní JBIG2 čtecí cestu pro Delphi nebo C++Builder, dekodér i zbytek obrazové obsluhy jsou zdokumentované na stránce PDF Library for Delphi