JBIG2 egendefinerte Huffman-tabeller i ren Pascal

PDFlibPas versjon 3.539.22 dekoder JBIG2-tabeller med egendefinert Huffman nativt: den rene Pascal-dekoderen i PDFlibJBIG2.pas parser Tables-segmentet (type 53), tildeler kanoniske prefikskoder i tabellinje-rekkefølge slik ITU-T T.88 vedlegg B.3 krever, konsumerer referanser til egendefinerte tabeller i selektor-rekkefølge for symbolordbøker og tekstregioner, og avgrenser hver lesing mot den deklarerte segmentlengden i stedet for mot hvilke byte som nå enn følger etter

Filen som utløste dette arbeidet, var tilsynelatende intetsigende. En skannet kontrakt, JBIG2-komprimert med Huffman-symbolkoding i stedet for den langt vanligere aritmetiske kodingen, og med koderen som sendte sine egne kodetabeller i stedet for standardtabellene B.1 til B.15. To uavhengige dekodere var uenige om forbedringspikslene i den, og PDFlibPas-dekoderen på det tidspunktet produserte tekst som så ut som den hadde vært gjennom en makulator: glyffragmenter forskjøvet noen piksler, én kolonne av hvert tegn borte. Ingenting kastet en feil. Det er formen på feil som overlever i årevis, for en dekoder som avviser en fil, får en support-sak, mens en dekoder som gjengir den litt feil, får en kunde som antar at skanningen var dårlig

Hva inneholder egentlig et JBIG2 Tables-segment?

Et Tables-segment er en kompakt beskrivelse av én Huffman-tabell: én flaggbyte, to fortegnede 32-bits grenser, og deretter en serie på (prefikslengde, områdelengde)-par som partisjonerer intervallet mellom grensene, slik det er lagt ut i T.88 §7.4.13 og vedlegg B.2. Bit 0 i flaggbyten er HTOOB og sier om tabellen har en out-of-band-kode. Bit 1 til 3 pluss én gir HTPS, antall biter som brukes til å skrive hver prefikslengde; bit 4 til 6 pluss én gir HTRS, bredden på hvert områdelengde-felt. Bit 7 er reservert, og PDFlibPas avviser segmentet hvis det er satt, i stedet for å gjette hva en fremtidig revisjon mente med det. HTLOW og HTHIGH følger som fortegnede 32-bits heltall, som er det første stedet en dekoder kan gå galt: å lese dem som usignerte gjør en tabell hvis nedre grense er negativ, noe som er helt normalt for deltakodede symbolbredder, til å se ut som den starter på fire milliarder. Hvert felt går gjennom en lokal ReadField-hjelper som sjekker forespørselen mot bitposisjonen der segmentdataene slutter, før den rører leseren, fordi en tabell som leser forbi segmentet sitt, ville konsumere neste segmentheader som prefikslengder

// 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));      // signert HTLOW
HighValue  := Integer(ReadField(32));      // signert 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 linjene som legges til etter løkken, er escape-linjene fra vedlegg B.2: den nedre områdelinjen starter på HTLOW minus én og teller nedover, den øvre områdelinjen starter på HTHIGH med et fast 32-bits område, og den valgfrie OOB-linjen har ingen verdi i det hele tatt. PDFlibPas markerer dem med sentinel-områdelengdene jbig2HuffmanLOW ($FFFFFFFD) og jbig2HuffmanOOB ($FFFFFFFE), samme konvensjon som de femten innebygde standardtabellene bruker, så dekodeløkken bryr seg ikke om en tabell kom fra spesifikasjonen eller fra filen

Hvorfor må prefikskoder tildeles i tabellinje-rekkefølge?

Fordi koderen aldri skriver kodene. Et JBIG2 Tables-segment bærer bare prefikslengder, og begge sider rekonstruerer de faktiske bitmønstrene med den kanoniske prosedyren i vedlegg B.3: tell hvor mange linjer som har hver lengde, tildel koder av lengde én først, skift deretter venstre og fortsett, og del ut koder innenfor én lengde i den rekkefølgen linjene forekommer. Enhver avvikelse fra den rekkefølgen produserer stille en annen tabell. Dekoderen vil ikke legge merke til det, for hvert bitmønster den genererer, er fortsatt en gyldig prefikskode, bare ikke den koderen brukte, og resultatet er et tilsynelatende rimelig bitmap satt sammen av feil 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: opprinnelig rekkefølge beholdt
  if table[I].prefixLen > 0 then       // innenfor hver prefikslengde
  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 tellesortering snarere enn en sammenligningssortering av én grunn: en tellepass over Counts, Starts og Positions er stabil av seg selv, så linjer med lik prefikslengde havner i resultatet i den rekkefølgen de ble deklarert, som er nøyaktig den rekkefølgen vedlegg B.3 tildeler koder etter. Linjer med prefikslengde null droppes før kodetildelingen, fordi B.3 definerer dem som ubrukte snarere enn som én-bits koder. To vakter sitter i samme løkke. Oversubskripsjons-sjekken fanger en tabell der lengdene hevder flere koder enn en prefikskode på den dybden kan romme, som er Kraft-ulikheten uttrykt som en heltallssammenligning; uten den produserer en ondsinnet tabell en kode som matcher to linjer, og dekoderen velger den den skanner først. Taket på 32 biter finnes fordi prefix er en Cardinal og matcheren i decodeInt akkumulerer biter i én. T.88 tillater lengre prefikser på papiret, PDFlibPas avviser dem ved navn, og ingen reell koder har blitt sett sende ut en. Verdiaritmetikken trenger samme omhu som kodearitmetikken: THuffmanTable.val er en Int64, og den nedre områdelinjen dekodes som val - readBits(32), en 32-bits usignert offset trukket fra HTLOW minus én. Med Integer-mellomverdier går den subtraksjonen rundt, og den omslåtte verdien godtas så som en symbolbredde. 64-bits-veien regner ut den sanne verdien, sjekker den mot det fortegnede 32-bits området og kaster hvis den ikke passer, som gjør en stille korrupsjon om til en eksplisitt avvisning

Hvorfor utløste egendefinerte tabeller aldri før 3.539.22?

To defekter skjulte hverandre. Den første var en én-linjers setter-feil: TTextRegionHuffmanFlags.setFlags mottok argumentet sitt under samme navn som feltet det lagret til, så Self.flagsAsInt := flagsAsInt tilordnet det uinitialiserte feltet til seg selv og hver selektor leste tilbake som null, som sendte tekstregioner som ba om egendefinerte tabeller, gjennom standardtabellene F, H og K i stedet. Den andre defekten gjorde at det å fikse bare den første fortsatt ville ha produsert korrumperte symboler. Når en Huffman-symbolordbok lagrer symbolene sine som et ukomprimert kollektivt bitmap, er den siste byten i hver rad partiell, og den gamle kopiløkken behandlet padding, som holder antall gyldige biter, som posisjonen til den laveste gyldige biten; en 63 piksel bred rad kopierte én bit fra sin siste byte i stedet for sju. Den korrigerte løkken kjører for bitPointer := 7 downto ((8 - padding) and 7), og syntetiske fixturer ved 7-bits og 9-bits bredde fester begge sider av bytegrensen. Med selektorene som leser korrekt, deles tabeller ut i den rekkefølgen spesifikasjonen lister dem, som T.88 §7.4.3.1.2 fastsetter for tekstregioner som FS, DS, DT, RDW, RDH, RDX, RDY og RSIZE og §7.4.2.1.1 fastsetter for symbolordbøker som DH, DW, BMSIZE og AGGINST. Hver to-bits selektor betyr standardtabell 0 eller 1, reservert for 2 på felt med bare to standardtabeller, og egendefinert for 3, og hvert egendefinert valg konsumerer neste Tables-segment blant de refererte segmentene i referanserekkefølge. NextCustomHuffmanTable gjør akkurat den gjennomgangen og kaster missing custom Huffman table reference når en region refererer til færre tabeller enn selektorene krever. Én linje til hører til samme fiks: en Huffman-symbolordbok der inndata- og nye symboler summerer til én, regner ut en symbolkodelengde på null fra log2-formelen, mens Huffman-varianten av formatet skriver hver symbol-ID med minst én bit, så if sdHuffman and (symbolCodeLength = 0) then symbolCodeLength := 1 i TSymbolDictionarySegment hindrer forbedrings- og aggregatveien i å lese null biter per symbol-ID

Hva garanterer segmentgrensen?

PDFlibPas behandler segmentdatalengden i hver header som en kontrakt begge retninger må respektere: et segment kan ikke lese forbi sin deklarerte slutt, og det kan ikke avslutte for tidlig og etterlate neste header på en uforutsigbar offset. Reglene som følger av den kontrakten, er hver for seg små. En datalengde med bit 31 satt er markøren for ukjent lengde i T.88 §7.2.7, og handleSegmentDataLength mapper den til en negativ verdi som readSegments avviser blankt i stedet for å skanne videre etter en terminator. Hvert referert segmentnummer må være mindre enn gjeldende segmentnummer og må allerede finnes, så en fremover- eller dinglende referanse feiler før noen region prøver å løse den opp. END_OF_PAGE og END_OF_FILE må deklarere null byte med data. Et Profiles-segment (type 52) bærer en 32-bits teller etterfulgt av så mange 32-bits identifikatorer og ingen piksler i det hele tatt, så det sjekkes som 4 pluss 4 ganger telleren mot den deklarerte lengden, hoppes over, og beholdes i segmentlisten bare for at senere segmenter fortsatt skal kunne referere til det ved nummer. En ukjent profilidentifikator er ikke en ukjent koding, og å behandle den som én ville avvise filer som dekoder helt 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');
// ... opprett segmentobjektet for denne 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 etterlate EOFB ules
  reader.bitPointer := 7;
end;

Halen av den løkken er der en tidligere versjon av dekoderen gikk galt på MMR-kodede regioner. En MMR-dekoder vet den er ferdig når den siste pikselen i den siste raden er produsert, noe som kan skje før den har konsumert EOFB-terminatoren som T.88 §6.2.5.7 plasserer på slutten av dataene. Den gamle koden antok at leseren sto ved neste header, så de gjenlevende terminatorbytene ble parset som et segmentnummer, og strømmen feilet noen byte senere med en misvisende feil. Nå vinner den deklarerte slutten: å lese forbi den er en feil, å stoppe for tidlig er normalt, og leseren flyttes til DataEnd med bitpekeren nullstilt, slik at neste header leses fra der filen sa den skulle være. Den samme disiplinen dukker opp overalt der PDFlibPas parser ubetrodde PDF-strukturer: den deklarerte lengden er grensen, og dekoderen går ikke på leting etter en vennligere en

Hvor leser Huffman-forbedring sin bitmapstørrelse?

Før den aritmetiske dekoderen starter, og fra et felt som bare finnes i Huffman-modus. Når en tekstregioninstans bærer forbedring (RI er ulik null) og SBHUFF er satt, lar T.88 §6.4.11 dekoderen lese RDW, RDH, RDX og RDY med sine valgte tabeller, deretter BMSIZE med RSIZE-tabellen, så justere til en bytegrense, og først da kjøre den generiske forbedringsdekodingen over nøyaktig BMSIZE byte. Tekstregioner i aritmetisk modus har ikke noe slikt felt, og en dekoder som deler én kodevei for begge moduser, vil hoppe over det, starte den aritmetiske dekoderen to eller flere byte for tidlig, og forbedre hvert symbol mot søppel. Symbolordbokveien med REFAGG og én enkelt forbedringsinstans, beskrevet i §6.5.8.2.2, har det samme BMSIZE-feltet med de samme konsekvensene. I PDFlibPas er øvre grense for den størrelsen TStreamReader.SegmentEnd, slutten på gjeldende segment slik readSegments satte den, ikke slutten på hele strømmen, fordi en BMSIZE som bare kan tilfredsstilles ved å låne byte fra det følgende segmentet, er misdannet, og å validere den mot strømlengden ville la den aritmetiske dekoderen lese inn i neste header. Nedre grense på to byte gjenspeiler det innledende byteparet den aritmetiske dekoderen alltid konsumerer, og etter forbedringen hopper leseren til RefinementEnd uansett hvor langt foran den aritmetiske dekoderen leste, siden dens endelige posisjon ikke er posisjonen til det neste Huffman-kodede feltet

// TJBIG2Bitmap tekstregiondekoding, Huffman-forbedringsveien
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;

Hva ble verifisert, og hva avvises fortsatt

Utvalget som startet dette, et JBIG2-bilde på 500 x 473 piksler med egendefinerte tabeller og Huffman-forbedring, dekoder nå til et bitmap med null avvikende piksler mot en uavhengig dekoder, og de syntetiske 7-bits og 9-bits kollektiv-bitmap-fixturene produserer de forventede radene på begge. De to uavhengige dekoderne som var uenige om det opprinnelige utvalget, er fortsatt uenige med hverandre; PDFlibPas matcher én av dem, og den ærlige formuleringen er at den native utdataen stemmer med én uavhengig implementasjon og med spesifikasjonen slik den er lest, ikke at hver dekoder i verden er enig. Den misdannede siden av pakken dekker:

• en reservert flaggbit eller en reservert selektorverdi
• en tabell som er avkuttet midt i en linje
• oversubskriberte prefikslengder og prefikser lengre enn 32 biter
• en region hvis selektorer ber om flere egendefinerte tabeller enn den refererer til
• bekreftelse på at utdatert utdata tømmes etter en mislykket dekoding i stedet for å bli stående slik at kalleren kan ta den for et resultat

Tre grenser står fortsatt bevisst. Tilfeldig tilgang-organisering av strømmen, der alle segmentheadere kommer før alle segmentdata, kaster JBIG2 random-access organisation is not supported så snart filheader-flaggenes leses, fordi det ikke finnes noe representativt utvalg å validere den mot, og en halvveis implementert vei er verre enn en navngitt avvisning. Egendefinerte tabeller er begrenset til 65 536 linjer og 32-bits prefikser. Og det offentlige dekodeinngangspunktet, TPLJBIG2Decoder.LoadFromByteArray, returnerer det første sidebitmapet i strømrekkefølge gjennom getPageAsJBIG2Bitmap(0), det første page-information-segmentet som påtreffes, i stedet for å slå opp sidetilknytning null; innebygde PDF-strømmer nummererer rutinemessig sin enkelte side som 1, og å be om side 0 etter tilknytning ville ikke finne noe. Feilteksten lander i TPLJBIG2Decoder.LastError, den interne dekoderdiagnostikken som bærer segmentnummer, type og byteoffset for feilen, og er ikke det samme som biblioteknivåets TPDFlib.LastErrorCode. Ingenting av dette berører kodingssiden, som er dekket i notatene om JBIG2-koderbackender og hvordan de lenkes; leseveien må godta hva enn noen andres koder bestemte seg for å sende ut, og den deler reglene sine med resten av bilde-stakken, inkludert den innebygde TIFF-dekoderen og dens avvisninger av BigTIFF og tiled-layout: avvis ved navn, lån aldri byte på tvers av en deklarert grense, og hold aritmetikken vid nok til at en omslått mellomverdi ikke kan passere som et gyldig svar. Hvis du vurderer en nativ JBIG2-lesevei for Delphi eller C++Builder, er dekoderen og resten av bildehåndteringen dokumentert på siden for PDF Library for Delphi