Egna Huffman-tabeller för JBIG2 i ren Pascal-PDF-avkodare

PDFlibPas version 3.539.22 avkodar JBIG2-anpassade Huffman-tabeller nativt: den rena Pascal-avkodaren i PDFlibJBIG2.pas tolkar Tables-segmentet (typ 53), tilldelar kanoniska prefixkoder i tabellradsordning enligt ITU-T T.88 Annex B.3, konsumerar referenser till anpassade tabeller i selectorordning för symbolordböcker och textregioner, och begränsar varje läsning till den deklarerade segmentlängden i stället för till vilka byte som råkar följa efter

Filen som tvingade fram det här arbetet var oansenlig till det yttre. Ett skannat kontrakt, JBIG2-komprimerat med Huffman-symbolkodning i stället för den mycket vanligare aritmetiska kodningen, och med en encoder som skickade med sina egna kodtabeller i stället för standardtabellerna B.1 till B.15. Två oberoende avkodare var oense om dess refinement-pixlar, och tidens PDFlibPas-avkodare producerade text som såg ut att ha gått genom en strimlare: glyffragment förskjutna några pixlar, en kolumn av varje tecken borta. Ingenting kastade något fel. Det är formen på buggar som överlever i åratal, för en avkodare som avvisar en fil får ett supportärende, medan en avkodare som renderar den lite fel får en kund som antar att skanningen var dålig

Vad innehåller ett JBIG2 Tables-segment egentligen?

Ett Tables-segment är en kompakt beskrivning av en Huffman-tabell: en flags-byte, två teckenförsedda 32-bitars gränser, och sedan en följd av (prefixlängd, räckviddslängd)-par som delar in intervallet mellan gränserna, enligt T.88 §7.4.13 och Annex B.2. Bit 0 i flags-byten är HTOOB och säger om tabellen har en out-of-band-kod. Bitarna 1 till 3 plus ett ger HTPS, antalet bitar som används för att skriva varje prefixlängd; bitarna 4 till 6 plus ett ger HTRS, bredden på varje fält för räckviddslängd. Bit 7 är reserverad, och PDFlibPas avvisar segmentet om den är satt i stället för att gissa vad en framtida revision menade med den. HTLOW och HTHIGH följer som teckenförsedda 32-bitars heltal, vilket är den första platsen en avkodare kan gå fel: att läsa dem som unsigned får en tabell vars nedre gräns är negativ, vilket är helt normalt för deltakodade symbolbredder, att se ut som om den börjar på fyra miljarder. Varje fält går genom en lokal ReadField-hjälpare som kontrollerar begäran mot den bitposition där segmentdatan slutar innan den rör läsaren, eftersom en tabell som läser förbi sitt segment skulle konsumera nästa segmentheader som prefixlängder

// 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));      // teckenförsedd HTLOW
HighValue  := Integer(ReadField(32));      // teckenförsedd 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 två raderna som läggs till efter loopen är escape-raderna från Annex B.2: den nedre räckviddsraden börjar på HTLOW minus ett och räknar nedåt, den övre räckviddsraden börjar på HTHIGH med en fast 32-bitars räckvidd, och den valfria OOB-raden har inget värde alls. PDFlibPas markerar dem med sentinel-räckviddslängderna jbig2HuffmanLOW ($FFFFFFFD) och jbig2HuffmanOOB ($FFFFFFFE), samma konvention som dess femton inbyggda standardtabeller använder, så avkodningsloopen bryr sig inte om en tabell kom från specifikationen eller från filen

Varför måste prefixkoder tilldelas i tabellradsordning?

Därför att encodern aldrig skriver själva koderna. Ett JBIG2 Tables-segment bär bara prefixlängder, och båda sidor rekonstruerar de faktiska bitmönstren med den kanoniska proceduren i Annex B.3: räkna hur många rader som har varje längd, tilldela koder av längd ett först, skifta sedan vänster och fortsätt, och dela inom en längd ut koder i den ordning raderna förekommer. Varje avvikelse från den ordningen producerar tyst en annan tabell. Avkodaren märker det inte, eftersom varje bitmönster den genererar fortfarande är en giltig prefixkod, bara inte den encodern använde, och utdatan är en rimligt utseende bitmap ihopsatt av fel symboler

// 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: ursprunglig ordning behålls
  if table[I].prefixLen > 0 then       // inom varje prefixlängd
  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 är en räknesortering i stället för en jämförelsesortering av ett skäl: en räkningenomgång över Counts, Starts och Positions är stabil till sin konstruktion, så rader med samma prefixlängd hamnar i resultatet i den ordning de deklarerades, vilket är precis den ordning Annex B.3 tilldelar koder efter. Rader med prefixlängd noll tas bort före kodtilldelningen, eftersom B.3 definierar dem som oanvända och inte som enbitskoder. Två vakter sitter i samma loop. Överskridandekontrollen fångar en tabell vars längder gör anspråk på fler koder än en prefixkod på det djupet kan rymma, vilket är Kraft-olikheten uttryckt som en heltalsjämförelse; utan den producerar en fientlig tabell en kod som matchar två rader och avkodaren väljer den den skannar först. Taket på 32 bitar finns för att prefix är en Cardinal och matcharen i decodeInt ackumulerar bitar i en sådan. T.88 tillåter längre prefix på papperet, PDFlibPas avvisar dem vid namn, och ingen verklig encoder har setts skicka ut ett. Värdearitmetiken behöver samma omsorg som kodaritmetiken: THuffmanTable.val är en Int64, och den nedre räckviddsraden avkodas som val - readBits(32), en 32-bitars unsigned offset subtraherad från HTLOW minus ett. Med Integer som mellanresultat slår subtraktionen runt, och det rundade värdet accepteras sedan som en symbolbredd. 64-bitarsvägen räknar fram det sanna värdet, kontrollerar det mot det teckenförsedda 32-bitarsintervallet och kastar om det inte passar, vilket förvandlar en tyst korruption till ett uttalat avvisande

Varför utlöstes aldrig anpassade tabeller före 3.539.22?

Två defekter gömde varandra. Den första var en setter-bugg på en rad: TTextRegionHuffmanFlags.setFlags tog emot sitt argument under samma namn som fältet det lagrade i, så Self.flagsAsInt := flagsAsInt tilldelade det oinitierade fältet till sig självt och varje selector lästes tillbaka som noll, vilket skickade textregioner som bad om anpassade tabeller genom standardtabellerna F, H och K i stället. Den andra defekten innebar att en fix av den första ändå skulle ha producerat korrupta symboler. När en Huffman-symbolordbok lagrar sina symboler som en okomprimerad kollektiv bitmap är sista byten i varje rad partiell, och den gamla kopieringsloopen behandlade padding, som håller antalet giltiga bitar, som positionen för den lägsta giltiga biten; en rad på 63 pixlar kopierade en bit från sin sista byte i stället för sju. Den rättade loopen kör for bitPointer := 7 downto ((8 - padding) and 7), och syntetiska fixture i bredderna 7 och 9 bitar fäster båda sidor av bytegränsen. Med selectorerna lästa korrekt delas tabeller ut i den ordning specifikationen listar dem, vilket T.88 §7.4.3.1.2 fastställer för textregioner som FS, DS, DT, RDW, RDH, RDX, RDY och RSIZE och §7.4.2.1.1 fastställer för symbolordböcker som DH, DW, BMSIZE och AGGINST. Varje tvåbitarsselector betyder standardtabell 0 eller 1, reserverat för 2 på fält med bara två standardtabeller, och anpassad för 3, och varje anpassat val konsumerar nästa Tables-segment bland de refererade segmenten i referensordning. NextCustomHuffmanTable gör exakt den genomgången och kastar missing custom Huffman table reference när en region refererar till färre tabeller än dess selectorer kräver. En rad till hör till samma fix: en Huffman-symbolordbok vars indata och nya symboler summerar till ett räknar fram en symbolkodlängd på noll från log2-formeln, medan formatets Huffman-variant skriver varje symbol-ID med minst en bit, så if sdHuffman and (symbolCodeLength = 0) then symbolCodeLength := 1 i TSymbolDictionarySegment hindrar refinement- och aggregatvägen från att läsa noll bitar per symbol-ID

Vad garanterar segmentgränsen?

PDFlibPas behandlar segmentdatalängden i varje header som ett kontrakt som båda riktningarna måste hålla: ett segment får inte läsa förbi sitt deklarerade slut, och det får inte sluta för tidigt och lämna nästa header på en oförutsägbar offset. Reglerna som följer av det kontraktet är var för sig små. En datalängd med bit 31 satt är markören för okänd längd i T.88 §7.2.7, och handleSegmentDataLength mappar den till ett negativt värde som readSegments avvisar direkt i stället för att skanna framåt efter en terminator. Varje refererat segmentnummer måste vara mindre än det aktuella segmentnumret och måste redan finnas, så en framåtriktad eller dinglande referens faller innan någon region försöker lösa upp den. END_OF_PAGE och END_OF_FILE måste deklarera noll byte data. Ett Profiles-segment (typ 52) bär ett 32-bitars antal följt av så många 32-bitars identifierare och inga pixlar alls, så det kontrolleras som 4 plus 4 gånger antalet mot den deklarerade längden, hoppas över, och behålls i segmentlistan bara för att senare segment fortfarande ska kunna referera till det via nummer. En okänd profilidentifierare är inte en okänd kodning, och att behandla den som en skulle avvisa filer som avkodas alldeles utmärkt

// 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');
// ... skapa segmentobjektet för den här typen ...
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 kan lämna EOFB oläst
  reader.bitPointer := 7;
end;

Svansen av den loopen är där en tidigare version av avkodaren gick fel på MMR-kodade regioner. En MMR-avkodare vet att den är klar när den sista pixeln på sista raden är producerad, vilket kan inträffa innan den har konsumerat EOFB-terminatorn som T.88 §6.2.5.7 placerar i slutet av datan. Den gamla koden antog att läsaren stod vid nästa header, så de överblivna terminatorbyten tolkades som ett segmentnummer och strömmen föll några byte senare med ett missvisande fel. Nu vinner det deklarerade slutet: att läsa förbi det är ett fel, att stanna kort är normalt, och läsaren flyttas till DataEnd med bitpekaren återställd så att nästa header läses där filen sade att den skulle ligga. Samma disciplin syns överallt där PDFlibPas tolkar opålitliga PDF-strukturer: den deklarerade längden är gränsen, och avkodaren ger sig inte ut för att leta efter en vänligare

Var läser Huffman-refinement sin bitmapstorlek?

Innan den aritmetiska avkodaren startar, och från ett fält som bara finns i Huffman-läge. När en textregionsinstans bär refinement (RI är icke-noll) och SBHUFF är satt, låter T.88 §6.4.11 avkodaren läsa RDW, RDH, RDX och RDY med sina valda tabeller, sedan BMSIZE med RSIZE-tabellen, sedan justera till en bytegräns, och först därefter köra den generiska refinement-avkodningen över exakt BMSIZE byte. Textregioner i aritmetiskt läge har inget sådant fält, och en avkodare som delar en kodväg för båda lägena hoppar över det, startar den aritmetiska avkodaren två eller fler byte för tidigt och refinerar varje symbol mot skräp. Symbolordboksvägen med REFAGG och en enda refinement-instans, beskriven i §6.5.8.2.2, har samma BMSIZE-fält med samma konsekvenser. I PDFlibPas är den övre gränsen för den storleken TStreamReader.SegmentEnd, slutet av det aktuella segmentet satt av readSegments, inte slutet av hela strömmen, eftersom en BMSIZE som bara kan uppfyllas genom att låna byte från nästa segment är felformad och en validering mot strömlängden skulle låta den aritmetiska avkodaren läsa in i nästa header. Den nedre gränsen på två byte speglar det inledande byteparet som den aritmetiska avkodaren alltid konsumerar, och efter refinement hoppar läsaren till RefinementEnd oavsett hur långt den aritmetiska avkodaren läste i förväg, eftersom dess slutposition inte är positionen för nästa Huffman-kodade fält

// TJBIG2Bitmap-avkodning av textregion, Huffman-refinement-vägen
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;

Vad som verifierades, och vad som fortfarande avvisas

Provet som startade det här, en JBIG2-bild på 500 gånger 473 pixlar med anpassade tabeller och Huffman-refinement, avkodas nu till en bitmap med noll avvikande pixlar mot en oberoende avkodare, och de syntetiska fixturena för kollektiva bitmaps i 7 och 9 bitars bredd ger förväntade rader på båda. De två oberoende avkodarna som var oense om originalprovet är fortfarande oense med varandra; PDFlibPas matchar en av dem, och det ärliga påståendet är att den nativa utdatan stämmer med en oberoende implementation och med specifikationen så som den är läst, inte att varje avkodare i världen håller med. Den felformade sidan av sviten täcker:

• en reserverad flaggbit eller ett reserverat selectorvärde
• en tabell trunkerad mitt i en rad
• överskridna prefixlängder och prefix längre än 32 bitar
• en region vars selectorer begär fler anpassade tabeller än den refererar till
• bekräftelse på att inaktuell utdata rensas efter en misslyckad avkodning i stället för att lämnas kvar så att anroparen tar den för ett resultat

Tre gränser är avsiktliga. Organisering för direktåtkomst, där alla segmentheadrar föregår all segmentdata, kastar JBIG2 random-access organisation is not supported så snart filhuvudets flaggor läses, eftersom inget representativt prov finns att validera mot och en halvfärdig väg är sämre än ett namngivet avvisande. Anpassade tabeller är begränsade till 65 536 rader och 32-bitars prefix. Och den publika avkodningsingången, TPLJBIG2Decoder.LoadFromByteArray, returnerar den första sidbitmappen i strömordning genom getPageAsJBIG2Bitmap(0), det första sidinformationssegmentet som påträffas, i stället för att slå upp sidassociation noll; inbäddade PDF-strömmar numrerar rutinmässigt sin enda sida som 1, och att fråga efter sida 0 via association skulle inte hitta något. Feltexten landar i TPLJBIG2Decoder.LastError, den interna avkodardiagnostiken som bär segmentnummer, typ och byteoffset för felet, och är inte samma sak som biblioteksnivåns TPDFlib.LastErrorCode. Inget av detta rör kodningssidan, som täcks i anteckningarna om JBIG2-encoderns backends och hur de länkas; läsvägen måste acceptera vad någon annans encoder än beslutar sig för att skicka ut, och den delar sina regler med resten av bildstacken, inklusive den inbyggda TIFF-avkodaren och dess avvisanden av BigTIFF och tiled-layouter: avvisa vid namn, låna aldrig byte över en deklarerad gräns, och håll aritmetiken så bred att ett runt mellanresultat inte kan passera som ett giltigt svar. Om du utvärderar en nativ JBIG2-läsväg för Delphi eller C++Builder finns avkodaren och resten av bildhanteringen dokumenterade på sidan för PDF Library for Delphi