Eigen JBIG2 Huffman-tabellen in een pure Pascal PDF-decoder

PDFlibPas versie 3.539.22 decodeert eigen JBIG2 Huffman-tabellen native: de pure Pascal-decoder in PDFlibJBIG2.pas parst het Tables-segment (type 53), kent canonieke prefixcodes toe in de volgorde van de tabelregels zoals ITU-T T.88 Annex B.3 vereist, verbruikt verwijzingen naar eigen tabellen in selectorvolgorde voor symbooldictionaries en tekstregio's, en begrenst elke read op de gedeclareerde segmentlengte in plaats van op welke bytes er toevallig volgen

Het bestand dat dit werk afdwong was oppervlakkig gezien niets bijzonders. Een gescand contract, JBIG2-gecomprimeerd met Huffman-symboolcodering in plaats van de veel gewonere arithmetische codering, en met een encoder die zijn eigen codetabellen meelevert in plaats van de standaardtabelen B.1 tot en met B.15. Twee onafhankelijke decoders waren het oneens over de refinement-pixels, en de PDFlibPas-decoder van dat moment produceerde tekst die door een shredder leek te zijn gehaald: glyphfragmenten een paar pixels verschoven, bij elk teken één kolom kwijt. Niets gooide een fout. Dat is de vorm van bug die jaren overleeft, want een decoder die een bestand weigert levert een supportticket op, terwijl een decoder die het net iets verkeerd rendert een klant oplevert die aanneemt dat de scan slecht was

Wat bevat een JBIG2 Tables-segment nu eigenlijk?

Een Tables-segment is een compacte beschrijving van één Huffman-tabel: één flags-byte, twee signed 32-bits grenzen, en dan een reeks (prefixlengte, bereiklengte)-paren die het interval tussen de grenzen opdelen, zoals vastgelegd in T.88 §7.4.13 en Annex B.2. Bit 0 van de flags-byte is HTOOB en zegt of de tabel een out-of-band-code heeft. Bits 1 tot en met 3 plus één geven HTPS, het aantal bits waarmee elke prefixlengte wordt geschreven; bits 4 tot en met 6 plus één geven HTRS, de breedte van elk bereiklengteveld. Bit 7 is gereserveerd, en PDFlibPas weigert het segment als die gezet is in plaats van te gokken wat een toekomstige revisie ermee bedoelde. Daarna volgen HTLOW en HTHIGH als signed 32-bits integers, en dat is de eerste plek waar een decoder de fout in kan gaan: ze als unsigned lezen laat een tabel waarvan de ondergrens negatief is — volstrekt normaal bij deltagecodeerde symboolbreedtes — lijken alsof hij bij vier miljard begint. Elk veld gaat door een lokale ReadField-helper die de aanvraag toetst tegen de bitpositie waar de segmentdata eindigt voordat hij de reader aanraakt, want een tabel die voorbij zijn segment leest zou de volgende segmentheader als prefixlengtes consumeren

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

De twee regels die na de lus worden toegevoegd zijn de escape-regels uit Annex B.2: de onderste bereiklengteregel begint bij HTLOW min één en telt naar beneden, de bovenste begint bij HTHIGH met een vaste bereiklengte van 32 bits, en de optionele OOB-regel heeft helemaal geen waarde. PDFlibPas markeert ze met de sentinel-bereiklengtes jbig2HuffmanLOW ($FFFFFFFD) en jbig2HuffmanOOB ($FFFFFFFE), dezelfde conventie die zijn vijftien ingebouwde standaardtabelen gebruiken, dus de decodeerlus maakt het niet uit of een tabel uit de specificatie of uit het bestand komt

Waarom moeten prefixcodes in de volgorde van de tabelregels worden toegekend?

Omdat de encoder de codes nooit wegschrijft. Een JBIG2 Tables-segment bevat alleen prefixlengtes, en beide kanten reconstrueren de werkelijke bitpatronen met de canonieke procedure uit Annex B.3: tel hoeveel regels elke lengte hebben, ken eerst de codes van lengte één toe, schuif dan naar links en ga door, en deel binnen één lengte de codes uit in de volgorde waarin de regels voorkomen. Elke afwijking van die volgorde levert stilzwijgend een andere tabel op. De decoder merkt het niet, want elk bitpatroon dat hij genereert is nog steeds een geldige prefixcode, alleen niet die de encoder gebruikte, en de output is een aannemelijk ogende bitmap die uit de verkeerde symbolen is samengesteld

// 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            // stabiel: oorspronkelijke volgorde blijft
  if table[I].prefixLen > 0 then       // binnen elke prefixlengte
  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 is een counting sort en geen comparison sort, om één reden: een telronde over Counts, Starts en Positions is stabiel per constructie, dus regels met dezelfde prefixlengte belanden in het resultaat in de volgorde waarin ze zijn gedeclareerd, en dat is precies de ordening waarmee Annex B.3 codes toekent. Regels met prefixlengte nul vallen af vóór de codetoekenning, omdat B.3 ze als ongebruikt definieert en niet als codes van één bit. In dezelfde lus zitten twee guards. De oversubscription-check vangt een tabel waarbij de lengtes meer codes opeisen dan een prefixcode van die diepte kan bevatten, de Kraft-ongelijkheid uitgedrukt als integervergelijking; zonder die check levert een vijandige tabel een code op die op twee regels past en pikt de decoder degene die hij het eerst scant. Het plafond van 32 bits bestaat omdat prefix een Cardinal is en de matcher in decodeInt bits in eentje ophoopt. T.88 staat op papier langere prefixes toe, PDFlibPas weigert ze bij naam, en er is nooit een echte encoder gezien die er een uitstuurt. De waarderekenkunde vraagt dezelfde zorg als de coderekenkunde: THuffmanTable.val is een Int64, en de onderste bereiklengteregel wordt gedecodeerd als val - readBits(32), een 32-bits unsigned offset die van HTLOW min één wordt afgetrokken. Met Integer-tussenwaarden wrapt die aftrekking, en de gewrapte waarde wordt vervolgens als symboolbreedte geaccepteerd. Het 64-bits pad berekent de echte waarde, toetst hem tegen het signed 32-bits bereik en gooit een fout als hij niet past, wat een stille corruptie in een expliciete weigering verandert

Waarom kwamen eigen tabellen vóór 3.539.22 nooit in actie?

Twee defecten verborgen elkaar. Het eerste was een setterbug van één regel: TTextRegionHuffmanFlags.setFlags kreeg zijn argument onder dezelfde naam als het veld waarin het opsloeg, dus Self.flagsAsInt := flagsAsInt wees het ongeïnitialiseerde veld aan zichzelf toe en elke selector las als nul terug, waardoor tekstregio's die om eigen tabellen vroegen via de standaardtabelen F, H en K werden bediend. Het tweede defect betekende dat alleen het eerste repareren nog steeds beschadigde symbolen had opgeleverd. Wanneer een Huffman-symbooldictionary zijn symbolen als ongecomprimeerde collective bitmap opslaat, is de laatste byte van elke rij gedeeltelijk gevuld, en de oude kopieerlus behandelde padding, dat het aantal geldige bits bevat, als de positie van het laagste geldige bit; een rij van 63 pixels breed kopieerde één bit uit zijn laatste byte in plaats van zeven. De gecorrigeerde lus loopt for bitPointer := 7 downto ((8 - padding) and 7), en synthetische fixtures op 7 en 9 bits breed leggen beide kanten van de bytegrens vast. Nu de selectors correct lezen, worden tabellen uitgedeeld in de volgorde waarin de specificatie ze noemt, wat T.88 §7.4.3.1.2 voor tekstregio's vastlegt als FS, DS, DT, RDW, RDH, RDX, RDY en RSIZE en §7.4.2.1.1 voor symbooldictionaries als DH, DW, BMSIZE en AGGINST. Elke selector van twee bits betekent standaardtabel 0 of 1, gereserveerd voor 2 op velden met slechts twee standaardtabelen, en eigen tabel voor 3, en elke keuze voor een eigen tabel verbruikt het volgende Tables-segment onder de gerefereerde segmenten in verwijzingsvolgorde. NextCustomHuffmanTable doet precies die wandeling en gooit missing custom Huffman table reference wanneer een regio naar minder tabellen verwijst dan zijn selectors vragen. Er hoort nog één regel bij dezelfde fix: een Huffman-symbooldictionary waarvan de input- en nieuwe symbolen samen één zijn berekent uit de log2-formule een symboolcodelengte van nul, terwijl de Huffman-variant van het formaat elke symbool-ID met minstens één bit schrijft, dus if sdHuffman and (symbolCodeLength = 0) then symbolCodeLength := 1 in TSymbolDictionarySegment houdt het refinement- en aggregatiepad ervan af om nul bits per symbool-ID te lezen

Wat garandeert de segmentgrens?

PDFlibPas behandelt de segmentdatalengte in elke header als een contract dat beide richtingen moeten nakomen: een segment mag niet voorbij zijn gedeclareerde einde lezen, en het mag niet te vroeg eindigen en de volgende header op een onvoorspelbare offset achterlaten. De regels die uit dat contract volgen zijn stuk voor stuk klein. Een datalengte met bit 31 gezet is de marker voor onbekende lengte uit T.88 §7.2.7, en handleSegmentDataLength zet hem om in een negatieve waarde die readSegments botweg weigert in plaats van vooruit te scannen naar een terminator. Elk gerefereerd segmentnummer moet kleiner zijn dan het huidige segmentnummer en al bestaan, dus een vooruitwijzende of losse verwijzing faalt voordat een regio hem probeert op te lossen. END_OF_PAGE en END_OF_FILE moeten nul bytes data declareren. Een Profiles-segment (type 52) draagt een 32-bits count gevolgd door evenveel 32-bits identifiers en helemaal geen pixels, dus het wordt gecontroleerd als 4 plus 4 keer de count tegen de gedeclareerde lengte, overgeslagen, en alleen in de segmentlijst gehouden zodat latere segmenten er nog naar kunnen verwijzen op nummer. Een onbekende profielidentifier is geen onbekende codering, en hem daarvoor aanzien zou bestanden weigeren die prima decoderen

// 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');
// ... maak het segmentobject voor dit type aan ...
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 laat EOFB mogelijk ongelezen
  reader.bitPointer := 7;
end;

Het staartje van die lus is waar een eerdere versie van de decoder misging bij MMR-gecodeerde regio's. Een MMR-decoder weet dat hij klaar is wanneer de laatste pixel van de laatste rij is geproduceerd, en dat kan gebeuren voordat hij de EOFB-terminator heeft verbruikt die T.88 §6.2.5.7 aan het einde van de data plaatst. De oude code nam aan dat de reader bij de volgende header stond, dus de achtergebleven terminatorbytes werden als segmentnummer geparst en de stream faalde een paar bytes later met een misleidende fout. Nu wint het gedeclareerde einde: voorbij dat einde lezen is een fout, te vroeg stoppen is normaal, en de reader wordt naar DataEnd verplaatst met de bitpointer gereset zodat de volgende header wordt gelezen waar het bestand zei dat hij zou staan. Dezelfde discipline duikt overal op waar PDFlibPas niet-vertrouwde PDF-structuren parst: de gedeclareerde lengte is de grens, en de decoder gaat niet op zoek naar een vriendelijkere

Waar leest Huffman-refinement zijn bitmapgrootte?

Vóór de arithmetische decoder start, en uit een veld dat alleen in Huffman-modus bestaat. Wanneer een tekstregio-instantie refinement draagt (RI is niet nul) en SBHUFF gezet is, laat T.88 §6.4.11 de decoder RDW, RDH, RDX en RDY lezen met hun gekozen tabellen, dan BMSIZE met de RSIZE-tabel, dan uitlijnen op een bytegrens, en pas daarna de generieke refinementdecodering over precies BMSIZE bytes lopen. Tekstregio's in arithmetische modus hebben dat veld niet, en een decoder die één codepad voor beide modi deelt slaat het over, start de arithmetische decoder twee of meer bytes te vroeg, en verfijnt elk symbool tegen garbage. Het symbooldictionarypad met REFAGG en één refinement-instantie, beschreven in §6.5.8.2.2, heeft hetzelfde BMSIZE-veld met dezelfde gevolgen. In PDFlibPas is de bovengrens voor die grootte TStreamReader.SegmentEnd, het einde van het huidige segment zoals gezet door readSegments, niet het einde van de hele stream, want een BMSIZE die alleen kan kloppen door bytes van het volgende segment te lenen is misvormd, en hem tegen de streamlengte valideren zou de arithmetische decoder tot in de volgende header laten lezen. De ondergrens van twee bytes weerspiegelt het eerste bytepaar dat de arithmetische decoder altijd verbruikt, en na de refinement springt de reader naar RefinementEnd, ongeacht hoeveel de arithmetische decoder vooruit heeft gelezen, want zijn eindpositie is niet de positie van het volgende Huffman-gecodeerde veld

// TJBIG2Bitmap tekstregio-decodering, Huffman-refinementpad
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;

Wat is er geverifieerd, en wat wordt nog steeds geweigerd

Het sample dat dit alles op gang bracht, een JBIG2-afbeelding van 500 bij 473 pixels met eigen tabellen en Huffman-refinement, decodeert nu naar een bitmap met nul verschillende pixels tegen een onafhankelijke decoder, en de synthetische fixtures van 7 en 9 bits breed leveren bij beide de verwachte rijen op. De twee onafhankelijke decoders die het over het oorspronkelijke sample oneens waren, zijn het nog steeds met elkaar oneens; PDFlibPas komt overeen met één van hen, en de eerlijke formulering is dat de native output overeenkomt met één onafhankelijke implementatie en met de specificatie zoals gelezen, niet dat elke decoder ter wereld het eens is. De misvormde kant van de suite dekt:

• een gereserveerd flagbit of een gereserveerde selectorwaarde
• een tabel die midden in een regel is afgekapt
• oversubscribed prefixlengtes en prefixes langer dan 32 bits
• een regio waarvan de selectors om meer eigen tabellen vragen dan waar hij naar verwijst
• bevestiging dat verouderde output na een mislukte decode wordt gewist in plaats van te blijven staan zodat de aanroeper hem voor een resultaat aanziet

Drie limieten blijven bewust staan. Random-access-streamorganisatie, waarbij alle segmentheaders vóór alle segmentdata staan, gooit JBIG2 random-access organisation is not supported zodra de flags van de bestandsheader worden gelezen, omdat er geen representatief sample bestaat om het tegen te valideren en een half geïmplementeerd pad erger is dan een weigering met naam. Eigen tabellen zijn begrensd op 65.536 regels en prefixes van 32 bits. En het publieke decodeer-entrypoint TPLJBIG2Decoder.LoadFromByteArray geeft de eerste paginabitmap in streamvolgorde terug via getPageAsJBIG2Bitmap(0), het eerste page-information-segment dat hij tegenkomt, in plaats van page association nul op te zoeken; embedded PDF-streams nummeren hun enige pagina routineus als 1, en om pagina 0 vragen op associatie zou niets vinden. De fouttekst belandt in TPLJBIG2Decoder.LastError, de interne decoderdiagnostiek die het segmentnummer, type en byteoffset van de fout bevat, en dat is niet hetzelfde als het library-brede TPDFlib.LastErrorCode. Niets hiervan raakt de encodeerkant, die aan bod komt in de notities over JBIG2-encoderbackends en hoe ze gelinkt worden; het leespad moet accepteren wat andermans encoder besloten heeft uit te sturen, en het deelt zijn regels met de rest van de imagestack, inclusief de ingebouwde TIFF-decoder en zijn weigeringen voor BigTIFF en getegelde layout: weiger bij naam, leen nooit bytes over een gedeclareerde grens, en houd de rekenkunde breed genoeg dat een gewrapte tussenwaarde niet voor een geldig antwoord kan doorgaan. Als u een native JBIG2-leespad voor Delphi of C++Builder aan het beoordelen bent, staan de decoder en de rest van de imagebehandeling gedocumenteerd op de PDF Library for Delphi-pagina