PDFlibPas JBIG2-Halftone-Raster: HSKIP und negative Offsets

PDFlibPas hat zwei unabhängige Defekte in seinem nativen JBIG2-Halftone-Region-Dekoder behoben: In v3.539.37 wird die HSKIP-Skip-Maske als HSKIP[ng, mg] indexiert, wie ITU-T T.88 §6.6.5.1 es definiert, und in v3.539.38 werden Raster, die zu negativen Koordinaten kommen — durch ein negatives HGX oder HGY oder durch Rotation — mit einem echten Floor-Shift platziert. Vor diesen Releases kamen betroffene Halftone-Regionen als Datenmüll oder verschoben heraus, ohne dass ein Fehler geworfen wurde. Beide Bugs versteckten sich hinter Testdaten, die zufällig symmetrisch oder nicht negativ waren, und der zweite dreht sich an einer Eigenschaft von Delphi und Free Pascal auf, die weit über JBIG2 hinaus zubeißt: shr auf einer vorzeichenbehafteten Ganzzahl ist ein logischer Shift, nicht der arithmetische >>, den der Standard annimmt

Halftone-Regionen sind der seltenste JBIG2-Regionstyp, ein Dekoder kann also Tausende gescannter Dokumente verarbeiten, bevor ihm eine als solche kodierte gerasterte Fotografie begegnet. Wenn es so weit ist, ist der Ausfall übel: Die Datei parst, die Segmentlängen addieren sich, die Seite hat die richtige Größe, und die Region ist Müll

Was dekodiert eine JBIG2-Halftone-Region eigentlich?

Eine JBIG2-Halftone-Region ist ein Raster kleiner Bitmaps aus einem Pattern-Dictionary, und die eigentliche Arbeit des Dekoders besteht darin, für jede Rasterzelle einen Index und die Pixelposition zu berechnen, an der diese Zelle landet. Das Pattern-Dictionary hält HNUMPATS Patterns von HPW × HPH Pixeln. Das Halftone-Region-Segment beschreibt dann ein Raster aus HGW Spalten mal HGH Zeilen und ein Graustufenbild derselben Größe, kodiert als Gray-kodierte Bitplanes. Jedes Bitplane wird mit der Generic-Region-Prozedur über eine HGW × HGH-Bitmap dekodiert, höchstwertige Plane zuerst, und die Planes zusammen geben jeder Zelle ihren Pattern-Index

Die Zellplatzierung nutzt Fixed-Point-Arithmetik mit 8-Bit-Bruchteil. Der Rasterursprung HGX, HGY ist ein Paar 32-Bit-Werte, und der Rastervektor HRX, HRY beschreibt den Schritt zwischen Nachbarzellen, was ein rotiertes Raster erlaubt. Für Rasterzeile mg und Rasterspalte ng berechnet T.88 §6.6.5 die Pixelposition als:

• x = (HGX + mg × HRY + ng × HRX) >> 8
• y = (HGY + mg × HRX − ng × HRY) >> 8

Die Skip-Maske kommt über das optionale HENABLESKIP-Flag ins Spiel. Ist das Flag gesetzt, baut §6.6.5.1 eine HGW × HGH-Bitmap HSKIP und setzt HSKIP[ng, mg] auf 1 für jede Zelle, deren Pattern vollständig außerhalb der Region liegt: x + HPW <= 0, x >= HBW, y + HPH <= 0 oder y >= HBH. Die Graustufen-Bitplanes werden dann mit dieser Maske als Skip-Bitmap der Generic-Region dekodiert, der arithmetische Dekoder liest also weder Kontext für eine übersprungene Zelle noch aktualisiert er ihn. Dekoder und Encoder müssen sich in jedem Bit von HSKIP einig sein, sonst geraten die beiden arithmetischen Coder aus dem Tritt

Warum brach eine transponierte HSKIP-Maske nur nicht-quadratische Raster?

Die Skip-Maske wurde mit vertauschten Koordinaten geschrieben, und nur ein nicht-quadratisches Raster legte das offen, denn ein quadratisches Raster hält jede vertauschte Koordinate innerhalb der Maske. PDFlibPas speichert Bitmaps mit einem (column, row)-Pixel-Accessor, und der Code, der die Maske baute, übergab (mg, ng), Zeile zuerst. Der Graustufen-Bitplane-Dekoder liest die Maske korrekt als (ng, mg). Die Pattern-Platzierungsschleife las sie in der vertauschten Reihenfolge des Builders zurück, die beiden waren sich also einig, und eine Überprüfung allein der Platzierungslogik hätte sie durchgehen lassen. Eine Namensfalle verschärfte das: In der Platzierungsschleife iteriert die Variable namens col über Rasterzeilen und Row über Rasterspalten

Nehmen Sie das 5 × 3-Raster aus 4 × 4-Patterns auf einer 16 × 8-Region, das v3.539.37 als Regressionfall nutzt. Mit HRX = 1024 und HRY = 0 landet Rasterspalte 4 bei x = 16 und Rasterzeile 2 bei y = 8, beide außerhalb der Region. Die korrekte Maske markiert sieben Zellen: die ganze Spalte 4 und die ganze Zeile 2. Die vertauschten Schreibvorgänge versuchten, Pixel in den Zeilenindizes 3 und 4 einer nur drei Zeilen hohen Maske zu setzen, und der Bitmap-Setter ignorierte diese außerhalb des Bereichs liegenden Schreibvorgänge stillschweigend. Übrig blieb Spalte 2, Zeilen 0 bis 2. Der Dekoder übersprang also zwei Zellen, die der Encoder kodiert hatte, und dekodierte sechs Zellen, die der Encoder übersprungen hatte

Der arithmetische Dekoder scheitert nicht, wenn das passiert. Er dekodiert zusätzliche Pixel aus Bits, die späteren Zellen gehören, seine Kontexte lesen falsche Nachbarn, und jeder Pattern-Index nach der ersten Diskrepanz ist Rauschen — deshalb war das Symptom eine vermüllte Region statt ein paar verrutschter Zellen. Auf einem quadratischen Raster ist derselbe Bug oft unsichtbar: Keine vertauschte Koordinate verlässt die Maske, und wenn die Zellen außerhalb der Region symmetrisch zur Diagonale liegen — ein Raster, das rechte und untere Kante um dieselbe Zellenzahl überragt, zum Beispiel —, ist die transponierte Maske bit für bit die korrekte. HENABLESKIP ist zudem optional, muss 0 sein, wenn das Graustufenbild MMR-kodiert ist, und wird von Encodern selten gesetzt, der Bug hatte also sehr wenige Möglichkeiten aufzutauchen. Seit v3.539.37 schreibt der Builder HSKIP[ng, mg], und die Platzierungsschleife liest dieselbe Reihenfolge

Warum scheitern negative Halftone-Grid-Offsets in drei Schichten?

Ein Halftone-Raster, das links von oder über seiner Region beginnt, brachte PDFlibPas an drei getrennten Stellen zu Fall, und jeder Defekt versteckte den nächsten. T.88 erlaubt diese Geometrie mit Absicht. Ein Encoder, der sein Raster an der Seite statt an der Region ausrichtet oder ein rotiertes Raster nutzt, produziert natürlich negative Zellecken, die die Region beschneidet. v3.539.38 fixte alle drei Schichten zusammen, denn jeder einzeln gefixte hätte nur das Symptom verändert

Schicht 1: ein Vorzeichenfeld als vorzeichenlos gelesen

T.88 §7.4.5.1.2 definiert HGX und HGY als vorzeichenbehaftete 32-Bit-Werte, aber der Dekoder las sie mit demselben 32-Bit-Helfer, den er für vorzeichenlose Felder benutzte, und dieser Helfer klemmte jedes negative Ergebnis auf 0. Ein Raster, das bei HGX = -900 beginnen sollte, wurde stillschweigend auf den Regionsursprung geschoben. Im Regressionfall von v3.539.38 kam das ganze Bild zwei Zeilen zu tief heraus. Die Klemme erklärt auch, warum die anderen beiden Defekte so lange überlebten: Bei einem erzwungen nicht-negativen Ursprung konnte eine negative Koordinate nur über ein rotiertes Raster mit HRY > 0 erscheinen, wo y = HGY + mg × HRX − ng × HRY für spätere Rasterspalten unter null fällt

Schicht 2: shr ist nicht >> 8

T.88 schreibt >> 8 und meint einen arithmetischen Shift, der gegen minus unendlich rundet. Der Dekoder übersetzte es als shr 8. In Delphi und Free Pascal ist shr auf einer vorzeichenbehafteten Ganzzahl ein logischer Shift: Als Vorzeichenbit wird eine Null hereingeschoben. Für einen Integer mit -512 liefert shr 8 16777214 statt -2. Ein Pattern, das bei y = -2 gezeichnet und auf seine untere Hälfte beschnitten werden sollte, wurde 16 Millionen Zeilen nach unten geschickt und als außerhalb der Region liegend verworfen. Nichts stürzte ab; die oberste Zeile des Halftone verschwand einfach

Schicht 3: Fixed Point statt Pixel verglichen

Der Skip-Test verglich Fixed-Point-Werte, keine Pixelpositionen, und die beiden sind nicht äquivalent, sobald der Bruchteil ungleich null ist. Der Originalcode umging den logischen Shift, indem er xx + HPW × 256 <= 0 auf dem unverschobenen Wert testete, ein vermeintliches Äquivalent des T.88-Tests. Mit HGX = -900 und einem 4-Pixel-Pattern ergibt das -900 + 1024 = 124, was positiv ist, die Zelle wird also nicht übersprungen. Der Standard shiftet zuerst: floor(-900 / 256) = -4, und -4 + 4 = 0 erfüllt x + HPW <= 0, die Zelle liegt also vollständig außerhalb und muss übersprungen werden. Der Encoder übersprang sie, der Dekoder dekodierte sie, und das Graustufenbild driftete exakt wie im Fall der transponierten Maske

Der Regressionfall aus v3.539.38 nutzt ein 4 × 3-Raster aus 4 × 4-Patterns bei HGX = -900, HGY = -512, HRX = 1024 auf einer 12 × 10-Region. Rasterspalten landen bei x = -4, 0, 4 und 8, Spalte 0 liegt also vollständig außerhalb und gehört in HSKIP; Rasterzeilen landen bei y = -2, 2 und 6, Zeile 0 muss also auf ihre unteren zwei Pixelzeilen beschnitten statt verworfen werden. Die Schichten einzeln zu fixen reproduziert den Stapel:

Gefixte Defekte	Dekodierte Region
Keine (vor v3.539.38)	Raster zum Ursprung gezogen, das ganze Bild zwei Zeilen zu tief
Nur Lesen von HGX / HGY mit Vorzeichen	Erste Rasterzeile fehlt, der Rest durch die Skip-Test-Drift vermüllt
Vorzeichenbehaftetes Lesen, Floor-Shift und Skip-Test im Pixelraum	Identisch, Pixel für Pixel, mit der aus T.88 §6.6.5 berechneten Seite und mit zwei unabhängigen Referenzdekodern

Der Fix ist ein einziger Helfer, HalftoneGridPixel, geteilt zwischen Skip-Masken-Builder und Platzierungsschleife. Er akkumuliert die Koordinate in Int64, sodass ein großes mg × HRX-Produkt nicht überlaufen kann, dividiert durch 256 mit Rundung gegen minus unendlich und klemmt auf ±MaxInt div 2, damit ein korruptes Raster keine spätere Bitmap-Arithmetik überlaufen kann. Der Skip-Test vergleicht jetzt diese Pixelwerte gegen HPW, HPH, HBW und HBH, exakt wie §6.6.5.1 es formuliert

Wie schreibt man einen arithmetischen Right Shift in Delphi?

Delphi hat keinen arithmetischen Shift-Operator, ein korrekter vorzeichenbehafteter Right Shift muss also als Floor-Division geschrieben werden, und das schlichte div ist nicht diese Division. div schneidet gegen null ab. Für nicht-negative Werte stimmen Abschneiden und Floor überein, und sie stimmen auch für negative Werte überein, die exakte Vielfache des Divisors sind — deshalb sieht -512 div 256 = -2 in einem Schnelltest fein aus. Überall sonst sind sie sich uneinig: -900 div 256 ist -3, der Floor ist -4, und -1 div 256 ist 0, der Floor ist -1. Eine JBIG2-Koordinate mit von null verschiedenem Bruchteil ist exakt der Fall, in dem div das falsche Pixel liefert

Auf den Delphi-Compilern Win32 und Win64 liefert eine Integer-Variable mit -512, um 8 nach rechts geschoben, 16777214, und ein Int64 mit -512 liefert 72057594037927934. Free Pascal definiert shr ebenfalls als logischen Shift und liefert SarLongint und SarInt64 in seiner System-Unit für die arithmetische Variante, aber diese Funktionen existieren in Delphi nicht, also braucht zwischen beiden Compilern geteilter Code einen eigenen Helfer:

// Floor-Division: rundet gegen minus unendlich für jedes Vorzeichen von A und B.
// B darf nicht 0 sein, und FloorDiv(Low(Integer), -1) überläuft genau wie div
function FloorDiv(A, B: Integer): Integer;
begin
  Result := A div B;
  if (A mod B <> 0) and ((A < 0) <> (B < 0)) then
    Dec(Result);
end;

// Arithmetischer Right Shift (das ">>" von C und T.88 auf Werten mit Vorzeichen).
// Bei negativem Value ist not Value = -Value - 1 nicht negativ, der logische
// shr ist dort sicher, und das äußere not bildet das Ergebnis zurück
function SarInt32(Value: Integer; Shift: Integer): Integer;  // Shift 0..31
begin
  if Value >= 0 then
    Result := Value shr Shift
  else
    Result := not ((not Value) shr Shift);
end;

function SarInt64(Value: Int64; Shift: Integer): Int64;      // Shift 0..63
begin
  if Value >= 0 then
    Result := Value shr Shift
  else
    Result := not ((not Value) shr Shift);
end;

Der not-Trick shiftet nie eine negative Zahl, hängt also nicht davon ab, wie ein Compiler das Vorzeichenbit behandelt, und er läuft nie über, auch nicht für Low(Integer). Beide Helfer wurden gegen eine Int64-Floor-Referenz über mehrere Millionen Werte geprüft, jeder Shift von 0 bis 31 und die Ränder Low(Integer) und High(Integer) auf Delphi Win32, Delphi Win64 und Free Pascal x86_64. Ein Sanity-Check, den jeder Unit-Test verdient, der Koordinaten anfasst:

var
  V: Integer;
begin
  V := -900;
  Writeln(V shr 8);           // 16777212  logischer Shift, der alte Bug
  Writeln(V div 256);         // -3        Abschneiden gegen null
  Writeln(FloorDiv(V, 256));  // -4        was T.88 mit >> 8 meint
  Writeln(SarInt32(V, 8));    // -4
end;

Math.Floor(V / 256) liefert ebenfalls -4, aber sein Umweg über Double verliert Präzision für Int64-Werte über 2⁵³, Ganzzahl-Geometrie sollte also in Ganzzahlen bleiben

Welche PDFlibPas-Aufrufe fahren den Halftone-Dekoder?

Der JBIG2-Halftone-Dekoder läuft, wenn PDFlibPas eine Seite mit dem eingebauten Renderer rendert, denn Rendern braucht Pixel. RenderPageToFile und RenderPageToStream erreichen ihn beide über die JBIG2Decode-Bildstreams der Seite, ein Halftone-Blatt also erneut zu rendern ist der direkte Weg zu bestätigen, dass v3.539.38 Ihre Ausgabe verändert. Derselbe Dekoder behandelt die anderen JBIG2-Regionstypen, behandelt in JBIG2 Custom Huffman Tables im Pure-Pascal-Dekoder und Random-Access-JBIG2-Dateien in Delphi dekodieren, und die gerenderte Bitmap füttert Konversionen wie PDF-Seiten nach 1-Bit-Monochrome rendern

uses
  SysUtils, PDFlibrary;

var
  Lib: TPDFlib;
  Page: Integer;
begin
  Lib := TPDFlib.Create;
  try
    if Lib.LoadFromFile('scanned-halftone.pdf', '') <> 1 then
      raise Exception.CreateFmt('Load failed, error %d', [Lib.LastErrorCode]);
    for Page := 1 to Lib.PageCount do
      // Rendering dekodiert jede JBIG2-Region, Halftones eingeschlossen
      if Lib.RenderPageToFile(150, Page, PDF_RENDER_PNG,
        Format('page-%.3d.png', [Page])) <> 1 then
        Writeln('Page ', Page, ' was not rendered');
  finally
    Lib.Free;
  end;
end.

Die Bildextraktion nimmt normalerweise einen anderen Pfad. GetPageImageList liefert JBIG2-Bilder in Native-Form, und SaveImageListItemDataToFile oder GetImageListItemDataToString gibt Ihnen eine eigenständige JBIG2-Datei aus den Stream-Bytes: der Dateiheader, die JBIG2Globals-Daten und ein End-of-File-Segment um die Seitendaten. Property 400 von GetImageListItemIntProperty meldet 6 für so ein Item. Auf diesem Pfad wird nichts dekodiert, eine extrahierte .jb2, die in einem anderen Viewer korrekt aussieht, während die gerenderte Seite Rauschen zeigt, war also ein typisches Zeichen dieser beiden Halftone-Bugs:

var
  ListID, I: Integer;
begin
  Lib.SelectPage(1);
  ListID := Lib.GetPageImageList(0);
  if ListID = 0 then
    Exit;
  try
    for I := 1 to Lib.GetImageListCount(ListID) do
      if Lib.GetImageListItemIntProperty(ListID, I, 400) = 6 then  // standalone JBIG2
        Lib.SaveImageListItemDataToFile(ListID, I, 0,
          Format('page1-image%d.jb2', [I]));
  finally
    Lib.ReleaseImageList(ListID);
  end;
end;

Wenn Masken oder Farbumwandlung einen gerenderten Fallback erzwingen, kommt das Item als dekodierte Bitmap zurück, und der Halftone-Dekoder fährt dann doch. Mehr zu Bildlisten in Delphi PDF Text-, Bild- und Font-Extraktion

Kurzreferenz: Regeln für JBIG2-Halftone-Raster

• Die Skip-Maske als HSKIP[ng, mg] indexieren, Rasterspalte zuerst, und sie überall dort in derselben Reihenfolge zurücklesen, wo Zellen platziert werden (T.88 §6.6.5.1, gefixt in PDFlibPas v3.539.37)
• Jeden Halftone- oder Raster-Code mit einem nicht-quadratischen Raster und einer asymmetrischen Menge von Zellen außerhalb der Region testen, denn ein quadratisches Raster kann einen transponierten Index komplett verstecken
• HGX und HGY als vorzeichenbehaftete 32-Bit-Werte lesen (T.88 §7.4.5.1.2), nie über einen vorzeichenlosen Helfer, der Negative klemmt
• Das >> 8 des Standards als Floor-Division durch 256 übersetzen, weder als shr 8 noch als div 256
• Den Skip-Test auf verschobenen Pixelpositionen fahren; die Fixed-Point-Form weicht immer dann ab, wenn der Bruchteil ungleich null ist, wie HGX = -900 mit einem 4-Pixel-Pattern zeigt
• Rasterkoordinaten in Int64 akkumulieren und klemmen, bevor sie in Bitmap-Code wandern, damit ein korruptes Raster nicht überlaufen kann
• Auf v3.539.38 oder später aktualisieren, wenn Ihre Dokumente Halftone-Regionen mit HENABLESKIP, negativen Rasterursprüngen oder rotierten Rastern enthalten

PDFlibPas rendert, extrahiert und editiert PDF-Dokumente aus Delphi und C++Builder mit einem nativen Pascal-JBIG2-Dekoder, der jetzt Halftone-Skip-Masken, negative Rasterursprünge und rotierte Raster so behandelt, wie T.88 es spezifiziert. Features, Editionen und einen Testdownload finden Sie auf der PDFlibPas Delphi PDF library