JBIG2 custom Huffman-tabeller i en ren Pascal PDF-decoder

PDFlibPas version 3.539.22 dekoder JBIG2 custom Huffman-tabeller nativt: den rene Pascal-decoder i PDFlibJBIG2.pas parser Tables-segmentet (type 53), tildeler kanoniske prefix-koder i tabel-linje-rækkefølge, som ITU-T T.88 Annex B.3 kræver, indtager custom tabel-referencer i selector-rækkefølge til symbol dictionaries og text regions og afgrænser hver eneste read med den deklarerede segmentlængde i stedet for med de bytes, der tilfældigvis følger efter

Filen, der tvang dette arbejde frem, var umiddelbart uinteressant. En scannet kontrakt, JBIG2-komprimeret med Huffman symbol coding i stedet for den langt mere almindelige arithmetic coding, og med encoderen, der shippede sine egne kodetabeller i stedet for standardtabellerne B.1 til B.15. To uafhængige decodere var uenige om dens refinement-pixels, og datidens PDFlibPas-decoder producerede tekst, der så ud, som om den havde været gennem en makulator: glyph-fragmenter forskudt et par pixels, én kolonne af hvert tegn manglende. Intet rejste en fejl. Det er formen på den bug, der overlever i årevis, fordi en decoder, der afviser en fil, får en support-billet, mens en decoder, der renderer den lidt forkert, får en kunde, der går ud fra, at scannet bare var dårligt

Hvad indeholder et JBIG2 Tables-segment egentlig?

Et Tables-segment er en kompakt beskrivelse af én Huffman-tabel: én flags-byte, to signede 32-bit-grænser og derefter en række (prefix length, range length)-par, der partitionerer intervallet mellem grænserne, som det er lagt op i T.88 §7.4.13 og Annex B.2. Bit 0 i flags-byten er HTOOB og siger, om tabellen har en out-of-band-kode. Bit 1 til 3 plus én giver HTPS, antallet af bits, der bruges til at skrive hver prefix length; bit 4 til 6 plus én giver HTRS, bredden af hvert range length-felt. Bit 7 er reserveret, og PDFlibPas nægter segmentet, hvis den er sat, i stedet for at gætte, hvad en fremtidig revision mener med den. HTLOW og HTHIGH følger som signede 32-bit-heltal, og det er det første sted, en decoder kan tage fejl: Læses de som unsigned, ser en tabel, hvis nedre grænse er negativ — hvilket er helt normalt for delta-kodede symbolbredder — ud som om, den starter ved fire milliarder. Hvert felt går gennem en lokal ReadField-hjælper, der tjekker forespørgslen op imod den bitposition, hvor segmentdataene slutter, før den rører readeren, for en tabel, der læser forbi sit segment, ville indtage næste segment-header som prefix lengths

// 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 to linjer, der føjes til efter løkken, er escape-linjerne fra Annex B.2: den nedre range-linje starter ved HTLOW minus én og tæller nedad, den øvre range-linje starter ved HTHIGH med en fast 32-bit range, og den valgfrie OOB-linje har slet ingen værdi. PDFlibPas markerer dem med sentinel range lengths jbig2HuffmanLOW ($FFFFFFFD) og jbig2HuffmanOOB ($FFFFFFFE), samme konvention som dens femten indbyggede standardtabeller bruger, så dekodningsløkken er ligeglad med, om tabellen kom fra specifikationen eller fra filen

Hvorfor skal prefix-koder tildeles i tabel-linje-rækkefølge?

Fordi encoderen aldrig skriver koderne. Et JBIG2 Tables-segment bærer kun prefix lengths, og begge sider rekonstruerer de faktiske bitmønstre med den kanoniske procedure i Annex B.3: tæl, hvor mange linjer der har hver længde, tildel koder af længde én først, skift så venstre og fortsæt, og inden for én længde uddeles koderne i den rækkefølge, linjerne optræder. Enhver afvigelse fra den rækkefølge producerer i stilhed en anden tabel. Decoderen bemærker det ikke, for hvert bitmønster, den genererer, er stadig en gyldig prefix-kode, bare ikke den, encoderen brugte, og outputtet er en bitmap, der ligner noget plausibelt, sat sammen af de forkerte 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: oprindelig rækkefølge bevaret
  if table[I].prefixLen > 0 then       // inden for hver 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 er en counting sort snarere end en comparison sort af én grund: et tællegennemløb over Counts, Starts og Positions er stabilt af konstruktion, så linjer med samme prefix length lander i resultatet i den rækkefølge, de blev deklareret, hvilket præcis er den rækkefølge, Annex B.3 tildeler koder efter. Linjer med prefix length nul droppes før kode-tildelingen, for B.3 definerer dem som ubrugte snarere end som én-bit-koder. To værn sidder i samme løkke. Oversubscription-tjekket fanger en tabel, hvis længder påstår flere koder, end en prefix-kode af den dybde kan holde, hvilket er Kraft-uligheden udtrykt som en integer-sammenligning; uden den producerer en fjendtlig tabel en kode, der matcher to linjer, og decoderen vælger den, den tilfældigt skanner først. 32-bit-loftet findes, fordi prefix er en Cardinal, og matcheren i decodeInt akkumulerer bits i én. T.88 tillader længere prefixer på papiret, PDFlibPas afviser dem ved navn, og ingen reel encoder er set emitte én. Værdi-aritmetikken kræver den samme omhu som kode-aritmetikken: THuffmanTable.val er en Int64, og den nedre range-linje dekodes som val - readBits(32), en 32-bit unsigned offset trukket fra HTLOW minus én. Med Integer-mellemregn løber subtraktionen over, og den overløbne værdi bliver derefter accepteret som en symbolbredde. 64-bit-vejen beregner den sande værdi, tjekker den op mod det signede 32-bit-område og raise'r, hvis den ikke passer, hvilket forvandler en stille korruption til en eksplicit nægtelse

Hvorfor kom custom-tabeller aldrig i spil før 3.539.22?

To defekter gemte sig for hinanden. Den første var en ét-linjers setter-bug: TTextRegionHuffmanFlags.setFlags modtog sit argument under samme navn som det felt, den gemte i, så Self.flagsAsInt := flagsAsInt tildelte det uinitialiserede felt til sig selv, og hver selector læste tilbage som nul, hvilket sendte text regions, der bad om custom-tabeller, gennem standardtabellerne F, H og K i stedet. Den anden defekt betød, at alene at fikse den første alligevel ville have produceret korrupte symboler. Når en Huffman symbol dictionary gemmer sine symboler som en uncompressed collective bitmap, er den sidste byte af hver række delvis, og den gamle kopieringsløkke behandlede padding, som holder antallet af gyldige bits, som positionen af den laveste gyldige bit; en række på 63 pixels kopierede én bit fra sin sidste byte i stedet for syv. Den korrigerede løkke kører for bitPointer := 7 downto ((8 - padding) and 7), og syntetiske fixtures ved 7-bit- og 9-bit-bredder låser begge sider af byte-grænsen fast. Med selectorerne læsende korrekt uddeles tabellerne i den rækkefølge, specifikationen lister dem, hvilket T.88 §7.4.3.1.2 fikserer for text regions som FS, DS, DT, RDW, RDH, RDX, RDY og RSIZE, og §7.4.2.1.1 fikserer for symbol dictionaries som DH, DW, BMSIZE og AGGINST. Hver to-bit-selector betyder standardtabel 0 eller 1, er reserveret ved 2 på felter med kun to standardtabeller, og custom ved 3, og ethvert custom-valg indtager det næste Tables-segment blandt de refererede segmenter i referral-rækkefølge. NextCustomHuffmanTable gør præcis den gennemløbning og raise'r missing custom Huffman table reference, når en region refererer til færre tabeller, end dens selectors forlanger. Én linje mere hører til samme fix: en Huffman symbol dictionary, hvis input og nye symboler lagt sammen bliver til én, beregner en symbol code length på nul ud fra log2-formlen, mens Huffman-varianten af formatet skriver hvert symbol ID med mindst én bit, så if sdHuffman and (symbolCodeLength = 0) then symbolCodeLength := 1 i TSymbolDictionarySegment forhindrer refinement- og aggregate-vejen i at læse nul bits pr. symbol ID

Hvad garanterer segmentgrænsen?

PDFlibPas behandler segmentdata-længden i hver header som en kontrakt, som begge retninger skal ære: et segment må ikke læse forbi sin deklarerede slutning, og det må ikke slutte for tidligt og efterlade næste header på en uforudsigelig offset. De regler, der faldt ud af den kontrakt, er hver for sig små. En data-længde med bit 31 sat er unknown-length-markøren fra T.88 §7.2.7, og handleSegmentDataLength mapper den til en negativ værdi, som readSegments afviser på stedet i stedet for at skanne frem efter en terminator. Hvert referred-to segmentnummer skal være mindre end det aktuelle segmentnummer og skal allerede eksistere, så en fremadrettet eller hængende reference fejler, før nogen region forsøger at resolve den. END_OF_PAGE og END_OF_FILE skal deklarere nul bytes data. Et Profiles-segment (type 52) bærer en 32-bit count efterfulgt af lige så mange 32-bit-id'er og slet ingen pixels, så det tjekkes som 4 plus 4 gange counten op mod den deklarerede længde, springes over og beholdes i segmentlisten kun for, at senere segmenter stadig kan referere til det ved nummer. En ukendt profil-identifikator er ikke en ukendt encoding, og at behandle den som én ville afvise filer, der dekoder fuldkommen fint

// 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');
// ... opret segment-objektet for denne type ...
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 efterlade EOFB ulæst
  reader.bitPointer := 7;
end;

Halen af den løkke er der, hvor en tidligere version af decoderen tog fejl på MMR-kodede regioner. En MMR-decoder ved, at den er færdig, når den sidste pixel af den sidste række er produceret, hvilket kan ske, før den har indtaget EOFB-terminatoren, som T.88 §6.2.5.7 placerer i slutningen af dataene. Den gamle kode gik ud fra, at readeren stod ved næste header, så de tilbageværende terminator-bytes blev parset som et segmentnummer, og streamen fejlede et par bytes senere med en vildledende fejl. Nu vinder den deklarerede slutning: at læse forbi den er en fejl, at stoppe for tidligt er normalt, og readeren flyttes til DataEnd med bit-pointeren nulstillet, så næste header læses dér, hvor filen sagde, den ville være. Den samme disciplin viser sig, hvor end PDFlibPas parser utroværdige PDF-strukturer: den deklarerede længde er grænsen, og decoderen leder ikke efter en venligere en

Hvor læser Huffman refinement sin bitmap-størrelse?

Før arithmetic decoderen starter, og fra et felt, som kun findes i Huffman-tilstand. Når en text region-instans bærer refinement (RI er forskellig fra nul) og SBHUFF er sat, får T.88 §6.4.11 decoderen til at læse RDW, RDH, RDX og RDY med deres valgte tabeller, derefter BMSIZE med RSIZE-tabellen, derefter aligne til en byte-grænse, og først derefter køre den generiske refinement-dekodning over præcis BMSIZE bytes. Text regions i arithmetic-tilstand har intet sådant felt, og en decoder, der deler én kodevej mellem begge tilstande, vil springe det over, starte arithmetic decoderen to eller flere bytes for tidligt og refinere hvert symbol op imod skrald. Symbol dictionary-vejen med REFAGG og en enkelt refinement-instans, beskrevet i §6.5.8.2.2, har samme BMSIZE-felt med de samme konsekvenser. I PDFlibPas er den øvre grænse for den størrelse TStreamReader.SegmentEnd, slutningen af det aktuelle segment som sat af readSegments, ikke slutningen af hele streamen, for en BMSIZE, som kun kan tilfredsstilles ved at låne bytes fra det følgende segment, er misdannet, og at validere den op mod stream-længden ville lade arithmetic decoderen læse ud i næste header. Den nedre grænse på to bytes afspejler det indledende byte-par, som arithmetic decoderen altid indtager, og efter refinement hopper readeren til RefinementEnd uanset hvor langt arithmetic decoderen læste forud, for dens endelige position er ikke positionen af det næste Huffman-kodede felt

// TJBIG2Bitmap text region-dekodning, Huffman refinement-vejen
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;

Hvad blev verificeret, og hvad nægtes fortsat?

Prøven, der startede det hele, et JBIG2-billede på 500 x 473 pixels med custom-tabeller og Huffman refinement, dekoder nu til en bitmap med nul afvigende pixels op mod en uafhængig decoder, og de syntetiske 7-bit- og 9-bit collective bitmap-fixtures producerer de forventede rækker på begge. De to uafhængige decodere, der var uenige om den oprindelige prøve, er stadig uenige med hinanden; PDFlibPas matcher én af dem, og den ærlige udtalelse er, at det native output er i overensstemmelse med én uafhængig implementation og med specifikationen som læst, ikke at alle verdens decodere er enige. Den misdannede side af suiten dækker:

• en reserveret flagbit eller en reserveret selectorværdi
• en tabel, der er trunkeret midt i en linje
• oversubscribede prefix lengths og prefixer længere end 32 bits
• en region, hvis selectors beder om flere custom-tabeller, end den refererer til
• bekræftelse på, at forældet output ryddes efter en fejlet dekodning i stedet for at blive efterladt, så calleren kan tage det for et resultat

Tre grænser er fortsat bevidste. Random-access stream-organisation, hvor alle segment-headers går forud for alle segmentdata, raise'r JBIG2 random-access organisation is not supported, så snart fil-headerens flags er læst, for der findes ingen repræsentativ prøve at validere den op imod, og en halvfærdig implementeret vej er værre end en navngiven nægtelse. Custom-tabeller er loftet til 65.536 linjer og 32-bit-prefixer. Og det offentlige dekodningsindgangspunkt, TPLJBIG2Decoder.LoadFromByteArray, returnerer den første side-bitmap i stream-rækkefølge gennem getPageAsJBIG2Bitmap(0), det første page-information-segment, der mødes, snarere end at slå page association nul op; indlejrede PDF-streams nummererer rutinemæssigt deres eneste side som 1, og at bede om side 0 via association ville finde ingenting. Fejlteksten lander i TPLJBIG2Decoder.LastError, decoderens interne diagnostik, der bærer segmentnummer, type og byte-offset for fejlen, og er ikke det samme som det biblioteksniveau TPDFlib.LastErrorCode. Intet af dette rører encodingsiden, som er dækket i noterne om JBIG2 encoder-backends og hvordan de linkes; read-vejen skal acceptere, hvad en andens encoder har besluttet at emitte, og den deler sine regler med resten af image-stakken, inklusive den indbyggede TIFF-decoder og dens BigTIFF- og tiled-layout-nægtelser: nægt ved navn, lån aldrig bytes hen over en deklareret grænse, og hold aritmetikken bred nok til, at en overløben mellemværdi ikke kan give sig ud for et gyldigt svar. Hvis du evaluerer en native JBIG2 read-vej til Delphi eller C++Builder, er decoderen og resten af image-håndteringen dokumenteret på PDF Library for Delphi-siden