JBIG2 Custom Huffman Tables im Pure-Pascal-PDF-Decoder

PDFlibPas Version 3.539.22 dekodiert JBIG2-Custom-Huffman-Tables nativ: Der Pure-Pascal-Decoder in PDFlibJBIG2.pas parst das Tables-Segment (Typ 53), weist kanonische Prefix Codes in Table-Line-Reihenfolge zu, wie es ITU-T T.88 Annex B.3 verlangt, konsumiert Custom-Table-Referenzen in Selektor-Reihenfolge für Symbol Dictionaries und Text Regions und begrenzt jeden Read an der deklarierten Segmentlänge statt an den Bytes, die zufällig folgen

Die Datei, die diese Arbeit erzwungen hat, war an der Oberfläche unspektakulär. Ein gescannter Vertrag, JBIG2-komprimiert mit Huffman-Symbolkodierung statt der deutlich häufigeren arithmetischen Kodierung, und mit einem Encoder, der seine eigenen Code-Tables mitschickt statt der Standard-Tables B.1 bis B.15. Zwei unabhängige Decoder stritten über seine Refinement-Pixel, und der damalige PDFlibPas-Decoder produzierte Text, der aussah, als wäre er durch einen Aktenvernichter gegangen: Glyphenfragmente um einige Pixel verschoben, bei jedem Zeichen eine Spalte fehlend. Nichts hat einen Fehler geworfen. Das ist die Sorte Bug, die jahrelang überlebt, denn ein Decoder, der eine Datei ablehnt, bekommt ein Support-Ticket, während ein Decoder, der sie leicht falsch rendert, einen Kunden bekommt, der den Scan für schlecht hält

Was enthält ein JBIG2-Tables-Segment eigentlich?

Ein Tables-Segment ist eine kompakte Beschreibung einer Huffman-Tabelle: ein Flags-Byte, zwei vorzeichenbehaftete 32-Bit-Grenzen und dann eine Folge von Paaren aus Prefix-Länge und Range-Länge, die das Intervall zwischen den Grenzen partitioniert, ausgeführt in T.88 §7.4.13 und Annex B.2. Bit 0 des Flags-Bytes ist HTOOB und sagt, ob die Table einen Out-of-Band-Code hat. Bits 1 bis 3 plus eins ergeben HTPS, die Bitzahl zum Schreiben jeder Prefix-Länge; Bits 4 bis 6 plus eins ergeben HTRS, die Breite jedes Range-Length-Felds. Bit 7 ist reserviert, und PDFlibPas weist das Segment zurück, wenn es gesetzt ist, statt zu raten, was eine künftige Revision damit gemeint haben könnte. HTLOW und HTHIGH folgen als vorzeichenbehaftete 32-Bit-Integer, und das ist die erste Stelle, an der ein Decoder danebengehen kann: Liest man sie als vorzeichenlos, sieht eine Table mit negativer unterer Grenze – für delta-codierte Symbolbreiten völlig normal – aus, als begänne sie bei vier Milliarden. Jedes Feld läuft durch einen lokalen ReadField-Helfer, der die Anforderung gegen die Bitposition prüft, an der die Segmentdaten enden, bevor er den Reader anfasst, denn eine Table, die über ihr Segment hinausliest, würde den nächsten Segment-Header als Prefix-Längen konsumieren

// 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 mit Vorzeichen
HighValue  := Integer(ReadField(32));      // HTHIGH mit Vorzeichen
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);

Die beiden nach der Schleife angehängten Lines sind die Escape-Lines aus Annex B.2: Die untere Range-Line startet bei HTLOW minus eins und zählt abwärts, die obere Range-Line startet bei HTHIGH mit fester 32-Bit-Range, und die optionale OOB-Line hat überhaupt keinen Wert. PDFlibPas markiert sie mit den Sentinel-Range-Längen jbig2HuffmanLOW ($FFFFFFFD) und jbig2HuffmanOOB ($FFFFFFFE), derselben Konvention, die seine fünfzehn eingebauten Standard-Tables nutzen, sodass die Dekodierschleife nicht interessiert, ob eine Table aus der Spezifikation oder aus der Datei stammt

Warum müssen Prefix Codes in Table-Line-Reihenfolge zugewiesen werden?

Weil der Encoder die Codes nie schreibt. Ein JBIG2-Tables-Segment trägt nur Prefix-Längen, und beide Seiten rekonstruieren die tatsächlichen Bitmuster mit dem kanonischen Verfahren aus Annex B.3: Zählen, wie viele Lines jede Länge haben, zuerst Codes der Länge eins zuweisen, dann nach links schieben und weitermachen, und innerhalb einer Länge Codes in der Reihenfolge vergeben, in der die Lines erscheinen. Jede Abweichung von dieser Reihenfolge erzeugt stillschweigend eine andere Table. Der Decoder merkt es nicht, denn jedes Bitmuster, das er erzeugt, ist weiterhin ein gültiger Prefix Code, nur eben nicht der, den der Encoder benutzt hat, und die Ausgabe ist eine plausibel aussehende Bitmap, zusammengesetzt aus den falschen Symbolen

// 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: ursprüngliche Reihenfolge
  if table[I].prefixLen > 0 then       // innerhalb jeder Prefix-Länge
  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 ist aus einem Grund ein Counting Sort statt eines Comparison Sort: Ein Zähldurchlauf über Counts, Starts und Positions ist von der Konstruktion her stabil, also landen Lines gleicher Prefix-Länge in der Reihenfolge im Ergebnis, in der sie deklariert wurden – exakt die Ordnung, nach der Annex B.3 Codes vergibt. Lines mit Prefix-Länge null fallen vor der Code-Zuweisung heraus, denn B.3 definiert sie als ungenutzt, nicht als Ein-Bit-Codes. Zwei Guards sitzen in derselben Schleife. Die Oversubscription-Prüfung erwischt eine Table, deren Längen mehr Codes beanspruchen, als ein Prefix Code dieser Tiefe halten kann – die Kraft-Ungleichung als Integer-Vergleich ausgedrückt; ohne sie erzeugt eine feindliche Table einen Code, der auf zwei Lines passt, und der Decoder nimmt die, die er zuerst scannt. Die 32-Bit-Grenze existiert, weil prefix ein Cardinal ist und der Matcher in decodeInt Bits in genau einem akkumuliert. T.88 erlaubt längere Prefixes auf dem Papier, PDFlibPas lehnt sie beim Namen ab, und kein realer Encoder ist je dabei gesehen worden, einen zu emittieren. Die Wert-Arithmetik braucht dieselbe Sorgfalt wie die Code-Arithmetik: THuffmanTable.val ist ein Int64, und die untere Range-Line wird als val - readBits(32) dekodiert, ein 32-Bit-Offset ohne Vorzeichen, subtrahiert von HTLOW minus eins. Mit Integer-Zwischenwerten läuft diese Subtraktion über, und der überlaufene Wert wird dann als Symbolbreite akzeptiert. Der 64-Bit-Pfad berechnet den wahren Wert, prüft ihn gegen den vorzeichenbehafteten 32-Bit-Bereich und wirft, wenn er nicht hineinpasst – aus stiller Korruption wird eine explizite Zurückweisung

Warum sprangen Custom Tables vor 3.539.22 nie an?

Zwei Defekte versteckten sich gegenseitig. Der erste war ein Einzeiler-Setter-Bug: TTextRegionHuffmanFlags.setFlags bekam sein Argument unter demselben Namen wie das Feld, in das es gespeichert wird, also wies Self.flagsAsInt := flagsAsInt das uninitialisierte Feld sich selbst zu, jeder Selektor las null zurück, und Text Regions mit Custom-Table-Anforderung liefen stattdessen durch die Standard-Tables F, H und K. Der zweite Defekt bedeutete, dass das Beheben des ersten allein weiterhin korrupte Symbole produziert hätte. Legt ein Huffman-Symbol-Dictionary seine Symbole als unkomprimierte Collective Bitmap ab, ist das letzte Byte jeder Zeile teilweise gefüllt, und die alte Kopierschleife behandelte padding, das die Anzahl gültiger Bits hält, als Position des niederwertigsten gültigen Bits; eine 63 Pixel breite Zeile kopierte ein Bit aus ihrem letzten Byte statt sieben. Die korrigierte Schleife läuft for bitPointer := 7 downto ((8 - padding) and 7), und synthetische Fixtures mit 7-Bit- und 9-Bit-Breiten nageln beide Seiten der Byte-Grenze fest. Mit korrekt lesenden Selektoren werden die Tables in der Reihenfolge vergeben, in der die Spezifikation sie listet – T.88 §7.4.3.1.2 legt sie für Text Regions als FS, DS, DT, RDW, RDH, RDX, RDY und RSIZE fest, §7.4.2.1.1 für Symbol Dictionaries als DH, DW, BMSIZE und AGGINST. Jeder Zwei-Bit-Selektor bedeutet Standard-Table 0 oder 1, reserviert für 2 bei Feldern mit nur zwei Standard-Tables und Custom für 3, und jede Custom-Auswahl konsumiert das nächste Tables-Segment unter den referred-to Segments in Referral-Reihenfolge. NextCustomHuffmanTable macht genau diesen Gang und wirft missing custom Huffman table reference, wenn eine Region auf weniger Tables verweist, als ihre Selektoren verlangen. Eine weitere Zeile gehört zum selben Fix: Addieren sich Input- und neue Symbole eines Huffman-Symbol-Dictionary zu eins, rechnet die log2-Formel eine Symbol-Code-Länge von null aus, während die Huffman-Variante des Formats jede Symbol-ID mit mindestens einem Bit schreibt, also hält if sdHuffman and (symbolCodeLength = 0) then symbolCodeLength := 1 in TSymbolDictionarySegment den Refinement- und Aggregate-Pfad davon ab, null Bits pro Symbol-ID zu lesen

Was garantiert die Segmentgrenze?

PDFlibPas behandelt die Segmentdatenlänge in jedem Header als Kontrakt, den beide Richtungen einhalten müssen: Ein Segment darf nicht über sein deklariertes Ende hinauslesen, und es darf nicht vorzeitig aufhören und den nächsten Header an einem unvorhersehbaren Offset zurücklassen. Die Regeln, die aus diesem Kontrakt fallen, sind einzeln klein. Eine Datenlänge mit gesetztem Bit 31 ist der Unknown-Length-Marker aus T.88 §7.2.7, und handleSegmentDataLength mappt ihn auf einen negativen Wert, den readSegments rundweg ablehnt, statt vorwärts nach einem Terminator zu scannen. Jede referred-to Segmentnummer muss kleiner als die aktuelle Segmentnummer sein und bereits existieren, sodass eine Vorwärts- oder lose Referenz scheitert, bevor irgendeine Region sie auflösen will. END_OF_PAGE und END_OF_FILE müssen null Bytes Daten deklarieren. Ein Profiles-Segment (Typ 52) trägt einen 32-Bit-Zähler, gefolgt von so vielen 32-Bit-Identifikatoren, und überhaupt keine Pixel, also wird es als 4 plus 4 mal der Zähler gegen die deklarierte Länge geprüft, übersprungen und nur in der Segmentliste gehalten, damit spätere Segmente weiterhin per Nummer auf es verweisen können. Ein unbekannter Profil-Identifikator ist keine unbekannte Kodierung, und ihn als solche zu behandeln würde Dateien zurückweisen, die tadellos dekodieren

// 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');
// ... hier das Segment-Objekt für diesen Typ anlegen ...
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 kann EOFB ungelesen lassen
  reader.bitPointer := 7;
end;

Am Ende dieser Schleife ist die Stelle, an der eine frühere Decoder-Version bei MMR-codierten Regionen danebenging. Ein MMR-Decoder weiß, dass er fertig ist, wenn das letzte Pixel der letzten Zeile produziert ist – was passieren kann, bevor er den EOFB-Terminator konsumiert hat, den T.88 §6.2.5.7 ans Datenende setzt. Der alte Code nahm an, der Reader stünde am nächsten Header, also wurden die übrig gebliebenen Terminator-Bytes als Segmentnummer geparst, und der Stream scheiterte ein paar Bytes später mit einer irreführenden Meldung. Jetzt gewinnt das deklarierte Ende: Darüber hinaus zu lesen ist ein Fehler, früher aufzuhören ist normal, und der Reader wird auf DataEnd gesetzt, mit zurückgesetztem Bit-Pointer, damit der nächste Header dort gelesen wird, wo die Datei ihn versprochen hat. Dieselbe Disziplin zeigt sich überall dort, wo PDFlibPas nicht vertrauenswürdige PDF-Strukturen parst: Die deklarierte Länge ist die Grenze, und der Decoder sucht nicht nach einer freundlicheren

Wo liest das Huffman-Refinement seine Bitmap-Größe?

Bevor der arithmetische Decoder startet – und aus einem Feld, das es nur im Huffman-Modus gibt. Trägt eine Text-Region-Instanz Refinement (RI ungleich null) und SBHUFF ist gesetzt, lässt T.88 §6.4.11 den Decoder RDW, RDH, RDX und RDY mit ihren gewählten Tables lesen, dann BMSIZE mit der RSIZE-Table, dann auf eine Byte-Grenze ausrichten, und erst danach die generische Refinement-Dekodierung über exakt BMSIZE Bytes laufen. Text Regions im Arithmetik-Modus haben kein solches Feld, und ein Decoder, der einen Codepfad für beide Modi teilt, überspringt es, startet den arithmetischen Decoder zwei oder mehr Bytes zu früh und verfeinert jedes Symbol gegen Datenmüll. Der Symbol-Dictionary-Pfad mit REFAGG und einer einzelnen Refinement-Instanz, beschrieben in §6.5.8.2.2, hat dasselbe BMSIZE-Feld mit denselben Konsequenzen. In PDFlibPas ist die Obergrenze dieser Größe TStreamReader.SegmentEnd, das Ende des aktuellen Segments, wie readSegments es setzt, nicht das Ende des ganzen Streams, denn ein BMSIZE, das sich nur erfüllen lässt, indem man Bytes aus dem folgenden Segment borgt, ist malformed, und es gegen die Streamlänge zu validieren ließe den arithmetischen Decoder in den nächsten Header hineinlesen. Die Untergrenze von zwei Bytes spiegelt das initiale Bytepaar wider, das der arithmetische Decoder immer konsumiert, und nach dem Refinement springt der Reader auf RefinementEnd, egal wie weit der arithmetische Decoder vorausgelesen hat, denn seine Endposition ist nicht die Position des nächsten Huffman-codierten Felds

// TJBIG2Bitmap Text-Region-Dekodierung, Huffman-Refinement-Pfad
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;

Was verifiziert wurde und was weiterhin zurückgewiesen wird

Das Sample, das all das angestoßen hat – ein 500 mal 473 Pixel großes JBIG2-Bild mit Custom Tables und Huffman-Refinement –, dekodiert jetzt zu einer Bitmap mit null abweichenden Pixeln gegen einen unabhängigen Decoder, und die synthetischen 7-Bit- und 9-Bit-Collective-Bitmap-Fixtures produzieren auf beiden die erwarteten Zeilen. Die beiden unabhängigen Decoder, die sich beim Original-Sample stritten, streiten immer noch miteinander; PDFlibPas passt zu einem von ihnen, und die ehrliche Aussage ist, dass die native Ausgabe mit einer unabhängigen Implementierung und mit der Spezifikation, wie wir sie lesen, übereinstimmt – nicht, dass jeder Decoder der Welt übereinstimmt. Die Malformed-Seite der Suite deckt ab:

• ein reserviertes Flag-Bit oder ein reservierter Selektorwert
• eine Table, mitten in einer Line abgeschnitten
• übersubskribierte Prefix-Längen und Prefixes länger als 32 Bits
• eine Region, deren Selektoren mehr Custom Tables verlangen, als sie referenziert
• die Bestätigung, dass veraltete Ausgabe nach einer fehlgeschlagenen Dekodierung gelöscht wird, statt für den Aufrufer liegen zu bleiben, der sie für ein Ergebnis halten könnte

Drei Grenzen bleiben bewusst. Die Random-Access-Stream-Organisation, bei der alle Segment-Header allen Segmentdaten vorangehen, wirft JBIG2 random-access organisation is not supported, sobald die Datei-Header-Flags gelesen sind, denn es existiert kein repräsentatives Sample zum Validieren, und ein halb implementierter Pfad ist schlimmer als eine namentliche Zurückweisung. Custom Tables sind bei 65.536 Lines und 32-Bit-Prefixes gedeckelt. Und der öffentliche Dekodierungseinstieg TPLJBIG2Decoder.LoadFromByteArray liefert über getPageAsJBIG2Bitmap(0) die erste Seiten-Bitmap in Stream-Reihenfolge – das erste angetroffene Page-Information-Segment –, statt nach Seiten-Assoziation null zu suchen; eingebettete PDF-Streams nummerieren ihre einzelne Seite routinehaft 1, und eine Anfrage nach Seite 0 per Assoziation fände nichts. Der Fehlertext landet in TPLJBIG2Decoder.LastError, der internen Decoder-Diagnostik, die Segmentnummer, Typ und Byte-Offset des Fehlers trägt, und ist nicht dasselbe wie das Bibliotheks-Level-TPDFlib.LastErrorCode. Keines davon berührt die Encoding-Seite, die in den Notizen zu JBIG2-Encoder-Backends und wie sie gelinkt werden abgehandelt ist; der Lesepfad muss akzeptieren, was der Encoder eines anderen zu emittieren beschlossen hat, und er teilt seine Regeln mit dem Rest des Image-Stacks, inklusive des eingebauten TIFF-Decoders mit seinen BigTIFF- und Tiled-Layout-Zurückweisungen: Namentlich ablehnen, nie Bytes über eine deklarierte Grenze hinweg borgen und die Arithmetik breit genug halten, dass ein überlaufener Zwischenwert nicht als gültige Antwort durchgehen kann. Wer einen nativen JBIG2-Lesepfad für Delphi oder C++Builder evaluiert, findet Decoder und restliche Bildverarbeitung auf der Seite der PDF Library for Delphi dokumentiert