Grilles JBIG2 PDFlibPas : HSKIP et offsets négatifs

PDFlibPas a corrigé deux défauts indépendants de son décodeur natif de régions halftone JBIG2 : en v3.539.37, le masque de saut HSKIP est indexé en HSKIP[ng, mg] comme le définit ITU-T T.88 §6.6.5.1, et en v3.539.38, les grilles qui atteignent des coordonnées négatives, via un HGX ou HGY négatif ou via une rotation, sont placées avec un vrai décalage floor. Avant ces versions, les régions halftone touchées sortaient brouillées ou déplacées, sans qu’aucune erreur ne soit levée. Les deux bugs se cachaient derrière des données de test par chance symétriques ou non négatives, et le second tient à une propriété de Delphi et Free Pascal qui mord bien au-delà de JBIG2 : shr sur un entier signé est un décalage logique, pas le >> arithmétique que la norme suppose

Les régions halftone sont le type de région JBIG2 le moins courant, si bien qu’un décodeur peut traiter des milliers de documents scannés avant de rencontrer une photographie tramée encodée ainsi. Quand ça arrive, l’échec est peu aimable : le fichier se parse, les longueurs de segments s’additionnent, la page a la bonne taille, et la région est de la bouillie

Que décode réellement une région halftone JBIG2 ?

Une région halftone JBIG2 est une grille de petits bitmaps tirés d’un dictionnaire de motifs, et le vrai travail du décodeur est de calculer un index pour chaque cellule de la grille et la position en pixels où cette cellule atterrit. Le dictionnaire de motifs contient HNUMPATS motifs de HPW × HPH pixels. Le segment de région halftone décrit ensuite une grille de HGW colonnes par HGH lignes et une image en niveaux de gris de même taille, codée en bitplans à codage Gray. Chaque bitplan est décodé avec la procédure de région générique sur un bitmap HGW × HGH, plan de poids fort en premier, et les plans ensemble donnent à chaque cellule son index de motif

Le placement des cellules utilise une arithmétique en virgule fixe avec une fraction de 8 bits. L’origine de grille HGX, HGY est une paire de valeurs 32 bits, et le vecteur de grille HRX, HRY décrit le pas entre cellules voisines, ce qui autorise une grille tournée. Pour la ligne de grille mg et la colonne de grille ng, T.88 §6.6.5 calcule la position en pixels ainsi :

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

Le masque de saut entre par le drapeau optionnel HENABLESKIP. Quand le drapeau est posé, §6.6.5.1 construit un bitmap HGW × HGH nommé HSKIP et met HSKIP[ng, mg] à 1 pour chaque cellule dont le motif se trouve entièrement hors de la région : x + HPW <= 0, x >= HBW, y + HPH <= 0 ou y >= HBH. Les bitplans de niveaux de gris sont ensuite décodés avec ce masque comme bitmap de saut de région générique, si bien que le décodeur arithmétique ne lit ni ne met à jour de contexte pour une cellule sautée. Décodeur et encodeur doivent tomber d’accord sur chaque bit de HSKIP, sinon les deux codeurs arithmétiques se désynchronisent

Pourquoi un masque HSKIP transposé ne cassait-il que les grilles non carrées ?

Le masque de saut était écrit avec ses coordonnées inversées, et seule une grille non carrée le révélait, parce qu’une grille carrée garde toute coordonnée inversée dans le masque. PDFlibPas stocke les bitmaps avec un accesseur de pixels (column, row), et le code qui construisait le masque passait (mg, ng), ligne d’abord. Le décodeur de bitplans de niveaux de gris lit le masque correctement en (ng, mg). La boucle de placement des motifs le relisait dans l’ordre inversé du constructeur, donc les deux s’accordaient, et une revue de la seule logique de placement l’aurait laissée passer. Un piège de nommage aggravait la chose : dans la boucle de placement, la variable appelée col itère les lignes de grille et Row itère les colonnes

Prenons la grille 5 × 3 de motifs 4 × 4 sur une région 16 × 8 que v3.539.37 utilise comme cas de régression. Avec HRX = 1024 et HRY = 0, la colonne de grille 4 atterrit à x = 16 et la ligne de grille 2 à y = 8, toutes deux hors région. Le masque correct marque sept cellules : toute la colonne 4 et toute la ligne 2. Les écritures inversées tentaient de poser des pixels aux index de lignes 3 et 4 dans un masque haut de trois lignes seulement, et le setter de bitmap ignorait en silence ces écritures hors bornes. Ce qui survivait, c’était la colonne 2, lignes 0 à 2. Le décodeur sautait donc deux cellules que l’encodeur avait codées, et décodait six cellules que l’encodeur avait sautées

Le décodeur arithmétique ne plante pas quand ça arrive. Il décode des pixels en trop à partir de bits qui appartiennent à des cellules suivantes, ses contextes lisent de mauvais voisins, et tout index de motif après le premier désaccord est du bruit, voilà pourquoi le symptôme était une région brouillée plutôt que quelques cellules mal placées. Sur une grille carrée, le même bug est souvent invisible : aucune coordonnée inversée ne sort du masque, et quand les cellules hors région sont symétriques par rapport à la diagonale, une grille qui déborde des bords droit et bas du même nombre de cellules par exemple, le masque transposé est bit pour bit le masque correct. HENABLESKIP est en plus optionnel, doit valoir 0 quand l’image en niveaux de gris est codée MMR, et est rarement posé par les encodeurs, si bien que le bug avait très peu de façons de se manifester. Depuis v3.539.37, le constructeur écrit HSKIP[ng, mg] et la boucle de placement lit le même ordre

Pourquoi les offsets de grille halftone négatifs échouent-ils en trois couches ?

Une grille halftone qui démarre à gauche ou au-dessus de sa région cassait PDFlibPas à trois endroits distincts, et chaque défaut cachait le suivant. T.88 autorise cette géométrie délibérément. Un encodeur qui aligne sa trame sur la page plutôt que sur la région, ou qui utilise une grille tournée, produit naturellement des coins de cellules négatifs que la région rogne. v3.539.38 a corrigé les trois couches ensemble, parce que n’en corriger qu’une ne changeait que le symptôme

Couche 1 : un champ signé lu comme non signé

T.88 §7.4.5.1.2 définit HGX et HGY comme des valeurs 32 bits signées, mais le décodeur les lisait avec le même helper 32 bits que pour les champs non signés, et ce helper écrêtait tout résultat négatif à 0. Une grille censée démarrer à HGX = -900 était tranquillement ramenée sur l’origine de la région. Dans le cas de régression de v3.539.38, toute l’image sortait deux lignes trop bas. L’écrêtage explique aussi pourquoi les deux autres défauts ont survécu si longtemps : l’origine étant forcée non négative, une coordonnée négative ne pouvait apparaître que par une grille tournée avec HRY > 0, où y = HGY + mg × HRX − ng × HRY passe sous zéro pour les colonnes de grille suivantes

Couche 2 : shr n’est pas >> 8

T.88 écrit >> 8 et entend un décalage arithmétique, qui arrondit vers moins l’infini. Le décodeur le traduisait en shr 8. En Delphi et Free Pascal, shr sur un entier signé est un décalage logique : le bit de signe est décalé comme un zéro. Pour un Integer tenant -512, shr 8 donne 16777214 au lieu de -2. Un motif qui aurait dû être dessiné à y = -2 et rogné à sa moitié basse partait 16 millions de lignes plus bas et était abandonné comme hors région. Rien ne plantait ; la ligne du haut du halftone disparaissait simplement

Couche 3 : comparer de la virgule fixe au lieu de pixels

Le test de saut comparait des valeurs en virgule fixe, pas des positions en pixels, et les deux ne sont pas équivalents dès que la fraction est non nulle. Le code d’origine esquivait le décalage logique en testant xx + HPW × 256 <= 0 sur la valeur non décalée, un prétendu équivalent du test T.88. Avec HGX = -900 et un motif de 4 pixels, ça donne -900 + 1024 = 124, donc positif, et la cellule n’est pas sautée. La norme décale d’abord : floor(-900 / 256) = -4, et -4 + 4 = 0 satisfait x + HPW <= 0, donc la cellule est entièrement dehors et doit être sautée. L’encodeur la sautait, le décodeur la décodait, et l’image en niveaux de gris dérivait exactement comme dans le cas du masque transposé

Le cas de régression de v3.539.38 utilise une grille 4 × 3 de motifs 4 × 4 à HGX = -900, HGY = -512, HRX = 1024 sur une région 12 × 10. Les colonnes de grille atterrissent à x = -4, 0, 4 et 8, donc la colonne 0 est entièrement dehors et sa place est dans HSKIP ; les lignes de grille atterrissent à y = -2, 2 et 6, donc la ligne 0 doit être rognée à ses deux rangées de pixels basses plutôt qu’abandonnée. Corriger les couches une à une reproduit la pile :

Défauts corrigés	Région décodée
Aucun (avant v3.539.38)	Grille tirée vers l’origine, toute l’image deux lignes trop bas
Lecture signée de HGX / HGY seule	Première ligne de grille manquante, le reste brouillé par la dérive du test de saut
Lecture signée, décalage floor et test de saut en espace pixels	Identique, pixel pour pixel, à la page calculée depuis T.88 §6.6.5 et à deux décodeurs de référence indépendants

La correction tient en un helper, HalftoneGridPixel, partagé par le constructeur du masque de saut et la boucle de placement. Il accumule la coordonnée en Int64 pour qu’un gros produit mg × HRX ne puisse pas boucler, divise par 256 en arrondissant vers moins l’infini, et écrête à ±MaxInt div 2 pour qu’une grille corrompue ne puisse pas faire déborder l’arithmétique de bitmaps ensuite. Le test de saut compare désormais ces valeurs en pixels à HPW, HPH, HBW et HBH, exactement comme le stipule §6.6.5.1

Comment écrire un décalage à droite arithmétique en Delphi ?

Delphi n’a pas d’opérateur de décalage arithmétique, donc un décalage à droite signé correct doit s’écrire comme une division floor, et le div banal n’est pas cette division. div tronque vers zéro. Pour les valeurs non négatives, troncature et floor tombent d’accord, et ils s’accordent aussi pour les valeurs négatives qui sont des multiples exacts du diviseur, voilà pourquoi -512 div 256 = -2 a l’air bon dans un test rapide. Ils divergent partout ailleurs : -900 div 256 vaut -3 alors que le floor vaut -4, et -1 div 256 vaut 0 alors que le floor vaut -1. Une coordonnée JBIG2 à fraction non nulle est exactement le cas où div donne le mauvais pixel

Sur les compilateurs Delphi Win32 et Win64, une variable Integer tenant -512 décalée à droite de 8 donne 16777214, et un Int64 tenant -512 donne 72057594037927934. Free Pascal définit aussi shr comme un décalage logique et livre SarLongint et SarInt64 dans son unité System pour la version arithmétique, mais ces fonctions n’existent pas en Delphi, donc le code partagé entre les deux compilateurs a besoin de son propre helper :

// Division floor : arrondit vers moins l’infini quel que soit le signe de A et B.
// B ne doit pas valoir 0, et FloorDiv(Low(Integer), -1) déborde comme 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;

// Décalage à droite arithmétique (le ">>" du C et de T.88 sur valeurs signées).
// Pour Value négatif, not Value = -Value - 1 est non négatif, donc le
// shr logique y est sûr, et le not externe remet le résultat en place
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;

L’astuce not ne décale jamais un nombre négatif, donc elle ne dépend pas de la façon dont un compilateur traite le bit de signe, et elle ne déborde jamais, y compris pour Low(Integer). Les deux helpers ont égalé une référence floor en Int64 sur plusieurs millions de valeurs, chaque décalage de 0 à 31 et les bords Low(Integer) et High(Integer) sur Delphi Win32, Delphi Win64 et Free Pascal x86_64. Un contrôle de bon sens à garder dans tout test unitaire qui touche des coordonnées :

var
  V: Integer;
begin
  V := -900;
  Writeln(V shr 8);           // 16777212  décalage logique, l’ancien bug
  Writeln(V div 256);         // -3        troncature vers zéro
  Writeln(FloorDiv(V, 256));  // -4        ce que T.88 entend par >> 8
  Writeln(SarInt32(V, 8));    // -4
end;

Math.Floor(V / 256) renvoie aussi -4, mais son détour par Double perd en précision pour des valeurs Int64 au-delà de 2⁵³, donc la géométrie entière doit rester dans les entiers

Quels appels PDFlibPas font tourner le décodeur halftone ?

Le décodeur halftone JBIG2 tourne quand PDFlibPas rend une page avec le moteur de rendu intégré, parce que le rendu a besoin de pixels. RenderPageToFile et RenderPageToStream l’atteignent tous deux par les flux d’images JBIG2Decode de la page, donc re-rendre une page halftone est la façon directe de confirmer que v3.539.38 change votre sortie. Le même décodeur gère les autres types de régions JBIG2, traités dans les tables Huffman personnalisées JBIG2 du décodeur Pascal pur et le décodage de fichiers JBIG2 à accès aléatoire en Delphi, et le bitmap rendu alimente des conversions comme le rendu de pages PDF en monochrome 1 bit

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
      // Le rendu décode chaque région JBIG2, halftones compris
      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.

L’extraction d’images prend normalement un autre chemin. GetPageImageList renvoie les images JBIG2 sous forme native, et SaveImageListItemDataToFile ou GetImageListItemDataToString vous remet un fichier JBIG2 autonome construit à partir des octets du flux : l’en-tête de fichier, les données JBIG2Globals et un segment de fin de fichier autour des données de page. La propriété 400 de GetImageListItemIntProperty rapporte 6 pour un tel élément. Rien n’est décodé sur ce chemin, si bien qu’un .jb2 extrait correct dans un autre visualiseur pendant que la page rendue montre du bruit était un signe typique de ces deux bugs halftone :

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  // JBIG2 autonome
        Lib.SaveImageListItemDataToFile(ListID, I, 0,
          Format('page1-image%d.jb2', [I]));
  finally
    Lib.ReleaseImageList(ListID);
  end;
end;

Quand des masques ou une conversion de couleurs forcent un passage par le rendu, l’élément revient en bitmap décodé et le décodeur halftone tourne alors. Plus sur les listes d’images dans l’extraction de texte, d’images et de polices PDF en Delphi

Aide-mémoire : règles de grille halftone JBIG2

• Indexez le masque de saut en HSKIP[ng, mg], colonne de grille d’abord, et relisez-le dans le même ordre partout où des cellules sont placées (T.88 §6.6.5.1, corrigé en PDFlibPas v3.539.37)
• Testez tout code halftone ou de grille avec une grille non carrée et un jeu asymétrique de cellules hors région, parce qu’une grille carrée peut masquer complètement un index transposé
• Lisez HGX et HGY comme des valeurs 32 bits signées (T.88 §7.4.5.1.2), jamais via un helper non signé qui écrête les négatifs
• Traduisez le >> 8 de la norme en une division floor par 256, ni en shr 8 ni en div 256
• Passez le test de saut sur des positions en pixels décalées ; la forme en virgule fixe diffère dès que la fraction est non nulle, comme le montre HGX = -900 avec un motif de 4 pixels
• Accumulez les coordonnées de grille en Int64 et écrêtez avant de les remettre au code de bitmap, pour qu’une grille corrompue ne puisse pas déborder
• Passez à v3.539.38 ou ultérieure si vos documents contiennent des régions halftone avec HENABLESKIP, des origines de grille négatives ou des grilles tournées

PDFlibPas rend, extrait et édite des documents PDF depuis Delphi et C++Builder avec un décodeur JBIG2 Pascal natif qui gère désormais masques de saut halftone, origines de grille négatives et grilles tournées comme le spécifie T.88. Voyez PDFlibPas Delphi PDF library pour les fonctionnalités, les éditions et un téléchargement d’essai