Tabelle Huffman custom JBIG2 in un decoder PDF Pascal puro

PDFlibPas versione 3.539.22 decodifica nativamente le tabelle Huffman custom di JBIG2: il decoder interamente in Pascal dentro PDFlibJBIG2.pas analizza il segmento Tables (tipo 53), assegna i codici di prefisso canonici nell'ordine delle righe della tabella come richiede ITU-T T.88 Annex B.3, consuma i riferimenti alle tabelle custom nell'ordine dei selettori per symbol dictionary e text region, e limita ogni lettura alla lunghezza dichiarata del segmento invece che ai byte che capita di trovare dopo

Il file che ha reso necessario tutto questo, in superficie, non aveva niente di strano. Un contratto scansionato, compresso in JBIG2 con la codifica Huffman dei simboli invece che con l'arithmetic coding molto più comune, e con l'encoder che si portava le proprie tabelle di codici al posto delle tabelle standard da B.1 a B.15. Due decoder indipendenti non concordavano sui suoi pixel di refinement, e il decoder PDFlibPas di allora produceva testo che sembrava passato in un trituratore: frammenti di glifo spostati di qualche pixel, una colonna mancante in ogni carattere. Niente sollevava un errore. È la forma di bug che sopravvive per anni, perché un decoder che rifiuta un file ti procura un ticket di supporto, mentre uno che lo renderizza leggermente sbagliato ti procura un cliente convinto che la scansione fosse pessima

Cosa contiene davvero un segmento Tables JBIG2?

Un segmento Tables è la descrizione compatta di una tabella Huffman: un byte di flag, due limiti signed a 32 bit, e poi una serie di coppie (lunghezza del prefisso, lunghezza del range) che partizionano l'intervallo tra i due limiti, come disposto in T.88 §7.4.13 e Annex B.2. Il bit 0 del byte di flag è HTOOB e dice se la tabella ha un codice out-of-band. I bit da 1 a 3 più uno danno HTPS, il numero di bit usati per scrivere ogni lunghezza di prefisso; i bit da 4 a 6 più uno danno HTRS, la larghezza di ogni campo di lunghezza di range. Il bit 7 è riservato, e PDFlibPas rifiuta il segmento se è impostato invece di indovinare cosa intendesse una revisione futura. Seguono HTLOW e HTHIGH come interi signed a 32 bit, ed è il primo punto dove un decoder può sbagliare: leggerli come unsigned fa sembrare che una tabella il cui limite inferiore è negativo, cosa del tutto normale per le larghezze di simbolo codificate in delta, parta da quattro miliardi. Ogni campo passa per un helper locale ReadField che verifica la richiesta contro la posizione di bit in cui finiscono i dati del segmento prima di toccare il reader, perché una tabella che leggesse oltre il proprio segmento starebbe consumando l'header del segmento successivo come lunghezze di prefisso

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

Le due righe aggiunte dopo il ciclo sono le righe di escape dell'Annex B.2: la riga di range inferiore parte da HTLOW meno uno e conta verso il basso, la riga di range superiore parte da HTHIGH con un range fisso a 32 bit, e la riga OOB opzionale non ha valore. PDFlibPas le contrassegna con le lunghezze di range sentinella jbig2HuffmanLOW ($FFFFFFFD) e jbig2HuffmanOOB ($FFFFFFFE), la stessa convenzione usata dalle sue quindici tabelle standard integrate, così il ciclo di decodifica non deve sapere se una tabella arriva dalla specifica o dal file

Perché i codici di prefisso vanno assegnati nell'ordine delle righe della tabella?

Perché l'encoder i codici non li scrive mai. Un segmento Tables JBIG2 porta solo lunghezze di prefisso, ed entrambe le parti ricostruiscono i pattern di bit effettivi con la procedura canonica dell'Annex B.3: conta quante righe hanno ogni lunghezza, assegna prima i codici di lunghezza uno, poi scala a sinistra e continua, e dentro una stessa lunghezza distribuisci i codici nell'ordine in cui le righe compaiono. Qualsiasi deviazione da quell'ordine produce in silenzio una tabella diversa. Il decoder non se ne accorge, perché ogni pattern di bit che genera è comunque un codice di prefisso valido, solo non quello usato dall'encoder, e l'output è una bitmap dall'aspetto plausibile montata con i simboli sbagliati

// 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            // stabile: l'ordine originale è conservato
  if table[I].prefixLen > 0 then       // dentro ogni lunghezza di prefisso
  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 è un counting sort invece di un comparison sort per una ragione sola: un passaggio di conteggio su Counts, Starts e Positions è stabile per costruzione, quindi le righe con la stessa lunghezza di prefisso finiscono nel risultato nell'ordine in cui sono state dichiarate, che è esattamente l'ordine con cui l'Annex B.3 assegna i codici. Le righe con lunghezza di prefisso zero vengono scartate prima dell'assegnazione dei codici, perché B.3 le definisce come non usate e non come codici di un bit. Nello stesso ciclo ci sono due guardie. Il controllo di oversubscription intercetta una tabella le cui lunghezze rivendicano più codici di quanti un codice di prefisso di quella profondità ne possa contenere, che è la disuguaglianza di Kraft espressa come confronto tra interi; senza di esso, una tabella ostile produce un codice che corrisponde a due righe e il decoder sceglie quella che scansiona per prima. Il tetto dei 32 bit esiste perché prefix è un Cardinal e il matcher in decodeInt accumula i bit in uno solo. T.88 sulla carta ammette prefissi più lunghi, PDFlibPas li rifiuta per nome, e nessun encoder reale è stato visto emetterne uno. L'aritmetica dei valori richiede la stessa attenzione di quella dei codici: THuffmanTable.val è un Int64, e la riga di range inferiore viene decodificata come val - readBits(32), un offset unsigned a 32 bit sottratto da HTLOW meno uno. Con intermedi Integer quella sottrazione va in wrap, e il valore wrappato viene poi accettato come larghezza di simbolo. Il percorso a 64 bit calcola il valore vero, lo verifica contro l'intervallo signed a 32 bit e solleva un'eccezione se non ci sta, il che trasforma una corruzione silenziosa in un rifiuto esplicito

Perché le tabelle custom non scattavano mai prima della 3.539.22?

Due difetti si nascondevano a vicenda. Il primo era un bug di una riga in un setter: TTextRegionHuffmanFlags.setFlags riceveva il proprio argomento con lo stesso nome del campo in cui lo memorizzava, quindi Self.flagsAsInt := flagsAsInt assegnava il campo non inizializzato a se stesso e ogni selettore si rileggeva come zero, il che mandava le text region che chiedevano tabelle custom attraverso le tabelle standard F, H e K. Il secondo difetto faceva sì che correggere solo il primo avrebbe comunque prodotto simboli corrotti. Quando un symbol dictionary Huffman memorizza i propri simboli come collective bitmap non compressa, l'ultimo byte di ogni riga è parziale, e il vecchio ciclo di copia trattava padding, che contiene il numero di bit validi, come la posizione del bit valido più basso; una riga larga 63 pixel copiava un bit dal suo byte finale invece di sette. Il ciclo corretto esegue for bitPointer := 7 downto ((8 - padding) and 7), e fixture sintetiche a larghezza 7 e 9 bit fissano entrambi i lati del confine del byte. Con i selettori che si leggono correttamente, le tabelle vengono distribuite nell'ordine in cui la specifica le elenca, che T.88 §7.4.3.1.2 fissa per le text region come FS, DS, DT, RDW, RDH, RDX, RDY e RSIZE e il §7.4.2.1.1 fissa per i symbol dictionary come DH, DW, BMSIZE e AGGINST. Ogni selettore da due bit significa tabella standard 0 o 1, riservato per 2 sui campi che hanno solo due tabelle standard, e custom per 3, e ogni selezione custom consuma il successivo segmento Tables tra i segmenti referenziati, in ordine di referenza. NextCustomHuffmanTable fa esattamente quel percorso e solleva missing custom Huffman table reference quando una region fa riferimento a meno tabelle di quante ne richiedano i suoi selettori. Alla stessa correzione appartiene un'altra riga: un symbol dictionary Huffman i cui simboli di input e nuovi sommano a uno calcola una lunghezza del codice di simbolo pari a zero dalla formula log2, mentre la variante Huffman del formato scrive ogni symbol ID con almeno un bit, quindi if sdHuffman and (symbolCodeLength = 0) then symbolCodeLength := 1 in TSymbolDictionarySegment impedisce al percorso di refinement e aggregate di leggere zero bit per symbol ID

Cosa garantisce il confine del segmento?

PDFlibPas tratta la lunghezza dei dati di segmento in ogni header come un contratto che entrambe le direzioni devono rispettare: un segmento non può leggere oltre la propria fine dichiarata, e non può finire in anticipo lasciando l'header successivo a un offset imprevedibile. Le regole che discendono da quel contratto sono singolarmente piccole. Una lunghezza dati con il bit 31 impostato è il marcatore di lunghezza sconosciuta di T.88 §7.2.7, e handleSegmentDataLength lo mappa su un valore negativo che readSegments rifiuta senza mezzi termini invece di scansionare avanti alla ricerca di un terminatore. Ogni numero di segmento referenziato deve essere minore del numero di segmento corrente e deve già esistere, così un riferimento in avanti o pendente fallisce prima che qualche region provi a risolverlo. END_OF_PAGE e END_OF_FILE devono dichiarare zero byte di dati. Un segmento Profiles (tipo 52) porta un count a 32 bit seguito da altrettanti identificatori a 32 bit e nessun pixel, quindi viene verificato come 4 più 4 volte il count contro la lunghezza dichiarata, saltato, e tenuto nella lista dei segmenti solo perché i segmenti successivi possano ancora riferirsi a esso per numero. Un identificatore di profilo sconosciuto non è una codifica sconosciuta, e trattarlo come tale rifiuterebbe file che si decodificano benissimo

// 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');
// ... crea l'oggetto segmento per questo tipo ...
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 può lasciare EOFB non letto
  reader.bitPointer := 7;
end;

La coda di quel ciclo è il punto in cui una versione precedente del decoder sbagliava sulle region codificate MMR. Un decoder MMR sa di aver finito quando l'ultimo pixel dell'ultima riga è stato prodotto, cosa che può capitare prima di aver consumato il terminatore EOFB che T.88 §6.2.5.7 colloca alla fine dei dati. Il vecchio codice dava per scontato che il reader fosse posizionato sull'header successivo, quindi i byte del terminatore rimasti venivano analizzati come numero di segmento e lo stream falliva qualche byte più avanti con un errore fuorviante. Ora vince la fine dichiarata: leggere oltre è un errore, fermarsi prima è normale, e il reader viene portato a DataEnd con il bit pointer azzerato, così l'header successivo si legge da dove il file diceva che sarebbe stato. La stessa disciplina compare ovunque PDFlibPas analizza strutture PDF non fidate: la lunghezza dichiarata è il confine, e il decoder non va a cercarne uno più comodo

Dove legge la propria dimensione di bitmap il refinement Huffman?

Prima che parta l'arithmetic decoder, e da un campo che esiste solo in modalità Huffman. Quando un'istanza di text region porta un refinement (RI diverso da zero) e SBHUFF è impostato, T.88 §6.4.11 fa leggere al decoder RDW, RDH, RDX e RDY con le loro tabelle selezionate, poi BMSIZE con la tabella RSIZE, poi l'allineamento al confine di byte, e solo allora esegue la decodifica di refinement generica su esattamente BMSIZE byte. Le text region in modalità aritmetica un campo così non ce l'hanno, e un decoder che condivide un solo percorso per entrambe le modalità lo salta, fa partire l'arithmetic decoder due o più byte prima e raffina ogni simbolo contro spazzatura. Il percorso symbol dictionary con REFAGG e una singola istanza di refinement, descritto in §6.5.8.2.2, ha lo stesso campo BMSIZE con le stesse conseguenze. In PDFlibPas il limite superiore di quella dimensione è TStreamReader.SegmentEnd, la fine del segmento corrente come impostata da readSegments, non la fine dell'intero stream, perché un BMSIZE che può essere soddisfatto solo prendendo in prestito byte dal segmento seguente è malformato e verificarlo contro la lunghezza dello stream lascerebbe l'arithmetic decoder leggere dentro l'header successivo. Il limite inferiore di due byte riflette la coppia iniziale di byte che l'arithmetic decoder consuma sempre, e dopo il refinement il reader salta a RefinementEnd indipendentemente da quanto avanti abbia letto l'arithmetic decoder, dato che la sua posizione finale non è la posizione del campo Huffman successivo

// decodifica di una text region TJBIG2Bitmap, percorso di refinement Huffman
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;

Cosa è stato verificato e cosa continua a essere rifiutato

Il campione da cui è partito tutto, un'immagine JBIG2 da 500 per 473 pixel con tabelle custom e refinement Huffman, ora si decodifica in una bitmap con zero pixel differenti rispetto a un decoder indipendente, e le fixture sintetiche di collective bitmap a 7 e 9 bit producono su entrambe le righe attese. I due decoder indipendenti che non concordavano sul campione originale continuano a non concordare tra loro; PDFlibPas corrisponde a uno dei due, e l'affermazione onesta è che l'output nativo concorda con un'implementazione indipendente e con la specifica come l'abbiamo letta, non che ogni decoder del mondo concordi. Il lato malformato della suite copre:

• un bit di flag riservato o un valore di selettore riservato
• una tabella troncata a metà di una riga
• lunghezze di prefisso in oversubscription e prefissi più lunghi di 32 bit
• una region i cui selettori chiedono più tabelle custom di quante ne referenzia
• la conferma che l'output obsoleto viene azzerato dopo una decodifica fallita invece di restare lì per essere scambiato dal chiamante per un risultato

Restano tre limiti voluti. L'organizzazione di stream ad accesso casuale, dove tutti gli header di segmento precedono tutti i dati di segmento, solleva JBIG2 random-access organisation is not supported non appena si leggono i flag dell'header del file, perché non esiste un campione rappresentativo con cui validarla e un percorso implementato a metà è peggio di un rifiuto con un nome. Le tabelle custom sono limitate a 65.536 righe e a prefissi da 32 bit. E l'entry point pubblico di decodifica, TPLJBIG2Decoder.LoadFromByteArray, restituisce la prima bitmap di pagina in ordine di stream tramite getPageAsJBIG2Bitmap(0), cioè il primo segmento page-information incontrato, invece di cercare la page association zero; gli stream PDF incorporati numerano abitualmente la loro unica pagina come 1, e chiedere la pagina 0 per associazione non troverebbe nulla. Il testo dell'errore finisce in TPLJBIG2Decoder.LastError, la diagnostica interna del decoder che porta numero di segmento, tipo e offset di byte del guasto, e non è la stessa cosa di TPDFlib.LastErrorCode a livello di libreria. Niente di tutto questo tocca il lato encoding, che è coperto nelle note su i backend dell'encoder JBIG2 e come vengono linkati; il percorso di lettura deve accettare quello che l'encoder di qualcun altro ha deciso di emettere, e condivide le sue regole con il resto dello stack immagini, incluso il decoder TIFF integrato e i suoi rifiuti su BigTIFF e layout tiled: rifiuta per nome, non prendere mai byte in prestito oltre un confine dichiarato, e tieni l'aritmetica abbastanza larga che un intermedio wrappato non possa passare per una risposta valida. Se stai valutando un percorso di lettura JBIG2 nativo per Delphi o C++Builder, il decoder e il resto della gestione immagini sono documentati nella pagina di PDF Library for Delphi