Décodeur JBIG2 Pascal : tables Huffman personnalisées

PDFlibPas version 3.539.22 décode nativement les tables Huffman personnalisées JBIG2 : le décodeur en Pascal pur de PDFlibJBIG2.pas analyse le segment Tables (type 53), attribue les codes préfixes canoniques dans l'ordre des lignes de table comme l'exige l'annexe B.3 de l'ITU-T T.88, consomme les références de tables personnalisées dans l'ordre des sélecteurs pour les dictionnaires de symboles et les régions de texte, et borne chaque lecture par la longueur de segment déclarée plutôt que par les octets qui se trouvent derrière

Le fichier qui a déclenché ce travail n'avait rien de remarquable en apparence. Un contrat scanné, compressé en JBIG2 avec un codage de symboles Huffman plutôt qu'avec le codage arithmétique bien plus courant, et dont l'encodeur livrait ses propres tables de codes au lieu des tables standard B.1 à B.15. Deux décodeurs indépendants n'étaient pas d'accord sur ses pixels de raffinement, et le décodeur PDFlibPas de l'époque produisait un texte qui semblait être passé au destructeur de documents : des fragments de glyphes décalés de quelques pixels, une colonne manquante dans chaque caractère. Rien ne levait d'erreur. C'est la forme de bug qui survit des années : un décodeur qui rejette un fichier génère un ticket de support, tandis qu'un décodeur qui le rend légèrement de travers laisse un client persuadé que le scan était mauvais

Que contient vraiment un segment Tables JBIG2 ?

Un segment Tables est la description compacte d'une table Huffman : un octet de drapeaux, deux bornes signées sur 32 bits, puis une suite de paires (longueur de préfixe, longueur de plage) qui partitionnent l'intervalle entre les bornes, selon la disposition de T.88 §7.4.13 et de l'annexe B.2. Le bit 0 de l'octet de drapeaux est HTOOB et indique si la table possède un code hors bande. Les bits 1 à 3 plus un donnent HTPS, le nombre de bits utilisés pour écrire chaque longueur de préfixe ; les bits 4 à 6 plus un donnent HTRS, la largeur de chaque champ de longueur de plage. Le bit 7 est réservé, et PDFlibPas refuse le segment s'il est positionné plutôt que de deviner ce qu'une révision future y mettrait. HTLOW et HTHIGH suivent en entiers signés sur 32 bits, ce qui est le premier endroit où un décodeur peut se tromper : les lire comme non signés fait qu'une table dont la borne basse est négative, ce qui est parfaitement normal pour des largeurs de symboles codées en delta, semble démarrer à quatre milliards. Chaque champ passe par un helper local ReadField qui vérifie la demande contre la position de bit où se terminent les données du segment avant de toucher au lecteur, parce qu'une table qui lirait au-delà de son segment consommerait l'en-tête du segment suivant comme des longueurs de préfixe

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

Les deux lignes ajoutées après la boucle sont les lignes d'échappement de l'annexe B.2 : la ligne de plage inférieure démarre à HTLOW moins un et compte vers le bas, la ligne de plage supérieure démarre à HTHIGH avec une plage fixe de 32 bits, et la ligne OOB facultative n'a aucune valeur du tout. PDFlibPas les marque avec les longueurs de plage sentinelles jbig2HuffmanLOW ($FFFFFFFD) et jbig2HuffmanOOB ($FFFFFFFE), la convention qu'utilisent aussi ses quinze tables standard intégrées, si bien que la boucle de décodage se moque qu'une table vienne de la spécification ou du fichier

Pourquoi les codes préfixes doivent-ils être attribués dans l'ordre des lignes de table ?

Parce que l'encodeur n'écrit jamais les codes. Un segment Tables JBIG2 ne transporte que des longueurs de préfixe, et les deux côtés reconstruisent les motifs de bits réels avec la procédure canonique de l'annexe B.3 : compter combien de lignes ont chaque longueur, attribuer d'abord les codes de longueur un, puis décaler vers la gauche et continuer, et à l'intérieur d'une même longueur distribuer les codes dans l'ordre d'apparition des lignes. Toute déviation par rapport à cet ordre produit silencieusement une autre table. Le décodeur ne le remarquera pas, car chaque motif de bits qu'il génère reste un code préfixe valide, simplement pas celui qu'a utilisé l'encodeur, et la sortie est une image bitmap plausible assemblée à partir des mauvais symboles

// 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            // stable : ordre d'origine conservé
  if table[I].prefixLen > 0 then       // à l'intérieur de chaque longueur
  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 est un tri par comptage plutôt qu'un tri par comparaison pour une raison : une passe de comptage sur Counts, Starts et Positions est stable par construction, donc les lignes de même longueur de préfixe arrivent dans le résultat dans l'ordre où elles ont été déclarées, ce qui est exactement l'ordre selon lequel l'annexe B.3 attribue les codes. Les lignes de longueur de préfixe nulle sont écartées avant l'attribution des codes, parce que B.3 les définit comme inutilisées plutôt que comme des codes d'un bit. Deux gardes occupent la même boucle. Le contrôle de sursouscription attrape une table dont les longueurs réclament plus de codes qu'un code préfixe de cette profondeur ne peut en contenir, ce qui est l'inégalité de Kraft exprimée en comparaison d'entiers ; sans lui, une table hostile produit un code qui correspond à deux lignes et le décodeur prend celle qu'il rencontre en premier. Le plafond de 32 bits existe parce que prefix est un Cardinal et que le matcher de decodeInt accumule les bits dans un seul. T.88 autorise des préfixes plus longs sur le papier, PDFlibPas les refuse nommément, et aucun encodeur réel n'en a été vu émettre. L'arithmétique des valeurs demande le même soin que celle des codes : THuffmanTable.val est un Int64, et la ligne de plage inférieure est décodée comme val - readBits(32), un décalage non signé de 32 bits retranché à HTLOW moins un. Avec des intermédiaires Integer, cette soustraction déborde, et la valeur résultante est ensuite acceptée comme largeur de symbole. Le chemin 64 bits calcule la vraie valeur, la compare à la plage signée de 32 bits et lève une erreur si elle ne rentre pas, ce qui transforme une corruption silencieuse en refus explicite

Pourquoi les tables personnalisées ne se déclenchaient-elles jamais avant la 3.539.22 ?

Deux défauts se cachaient l'un l'autre. Le premier était un bug de setter d'une ligne : TTextRegionHuffmanFlags.setFlags recevait son argument sous le même nom que le champ dans lequel il le stockait, donc Self.flagsAsInt := flagsAsInt affectait le champ non initialisé à lui-même et chaque sélecteur se relisait à zéro, ce qui envoyait les régions de texte demandant des tables personnalisées vers les tables standard F, H et K. Le second défaut faisait que corriger le premier seul aurait quand même produit des symboles corrompus. Quand un dictionnaire de symboles Huffman stocke ses symboles sous forme de bitmap collective non compressée, le dernier octet de chaque ligne est partiel, et l'ancienne boucle de copie traitait padding, qui contient le nombre de bits valides, comme la position du bit valide le plus bas ; une ligne large de 63 pixels copiait un bit de son dernier octet au lieu de sept. La boucle corrigée fait for bitPointer := 7 downto ((8 - padding) and 7), et des fixtures synthétiques en largeurs 7 et 9 bits verrouillent les deux côtés de la frontière d'octet. Les sélecteurs lisant correctement, les tables sont distribuées dans l'ordre où la spécification les énumère, que T.88 §7.4.3.1.2 fixe pour les régions de texte à FS, DS, DT, RDW, RDH, RDX, RDY et RSIZE et que §7.4.2.1.1 fixe pour les dictionnaires de symboles à DH, DW, BMSIZE et AGGINST. Chaque sélecteur de deux bits signifie table standard 0 ou 1, réservé pour 2 sur les champs qui n'ont que deux tables standard, et personnalisée pour 3, et chaque sélection personnalisée consomme le segment Tables suivant parmi les segments référencés, dans l'ordre de référence. NextCustomHuffmanTable fait exactement ce parcours et lève missing custom Huffman table reference quand une région référence moins de tables que ses sélecteurs n'en demandent. Une ligne de plus appartient au même correctif : un dictionnaire de symboles Huffman dont l'entrée et les nouveaux symboles totalisent un calcule une longueur de code de symbole nulle avec la formule log2, alors que la variante Huffman du format écrit chaque identifiant de symbole sur au moins un bit, donc if sdHuffman and (symbolCodeLength = 0) then symbolCodeLength := 1 dans TSymbolDictionarySegment empêche le chemin de raffinement et d'agrégation de lire zéro bit par identifiant de symbole

Que garantit la frontière de segment ?

PDFlibPas traite la longueur des données de segment de chaque en-tête comme un contrat que les deux directions doivent honorer : un segment ne peut pas lire au-delà de sa fin déclarée, et il ne peut pas s'arrêter court en laissant l'en-tête suivant à un décalage imprévisible. Les règles qui découlent de ce contrat sont individuellement petites. Une longueur de données avec le bit 31 positionné est le marqueur de longueur inconnue de T.88 §7.2.7, et handleSegmentDataLength la ramène à une valeur négative que readSegments rejette d'emblée plutôt que de balayer en avant à la recherche d'un terminateur. Chaque numéro de segment référencé doit être inférieur au numéro du segment courant et doit déjà exister, donc une référence en avant ou pendante échoue avant qu'aucune région ne tente de la résoudre. END_OF_PAGE et END_OF_FILE doivent déclarer zéro octet de données. Un segment Profiles (type 52) porte un compteur 32 bits suivi d'autant d'identifiants de 32 bits et aucun pixel, il est donc contrôlé comme 4 plus 4 fois le compteur face à la longueur déclarée, sauté, et conservé dans la liste des segments uniquement pour que les segments suivants puissent encore le citer par numéro. Un identifiant de profil inconnu n'est pas un encodage inconnu, et le traiter comme tel rejetterait des fichiers qui se décodent parfaitement

// 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');
// ... créer l'objet de segment pour ce type ...
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 peut laisser l'EOFB non lu
  reader.bitPointer := 7;
end;

La queue de cette boucle est l'endroit où une version antérieure du décodeur se trompait sur les régions codées en MMR. Un décodeur MMR sait qu'il a fini quand le dernier pixel de la dernière ligne est produit, ce qui peut arriver avant qu'il ait consommé le terminateur EOFB que T.88 §6.2.5.7 place à la fin des données. L'ancien code supposait le lecteur positionné sur l'en-tête suivant, donc les octets de terminateur restants étaient analysés comme un numéro de segment et le flux échouait quelques octets plus loin avec une erreur trompeuse. Désormais la fin déclarée gagne : lire au-delà est une erreur, s'arrêter court est normal, et le lecteur est déplacé sur DataEnd avec le pointeur de bits remis à zéro pour que l'en-tête suivant soit lu là où le fichier avait annoncé qu'il se trouverait. La même discipline revient partout où PDFlibPas analyse des structures PDF non fiables : la longueur déclarée est la frontière, et le décodeur ne part pas chercher une frontière plus arrangeante

Où le raffinement Huffman lit-il sa taille de bitmap ?

Avant que le décodeur arithmétique démarre, et dans un champ qui n'existe qu'en mode Huffman. Quand une instance de région de texte porte un raffinement (RI non nul) et que SBHUFF est positionné, T.88 §6.4.11 fait lire au décodeur RDW, RDH, RDX et RDY avec leurs tables sélectionnées, puis BMSIZE avec la table RSIZE, puis l'aligne sur une frontière d'octet, et seulement ensuite exécute le décodage de raffinement générique sur exactement BMSIZE octets. Les régions de texte en mode arithmétique n'ont pas ce champ, et un décodeur qui partage un seul chemin de code pour les deux modes va le sauter, démarrer le décodeur arithmétique deux octets trop tôt et raffiner chaque symbole contre du bruit. Le chemin des dictionnaires de symboles avec REFAGG et une seule instance de raffinement, décrit en §6.5.8.2.2, a le même champ BMSIZE avec les mêmes conséquences. Dans PDFlibPas, la borne supérieure de cette taille est TStreamReader.SegmentEnd, la fin du segment courant telle que fixée par readSegments, et non la fin du flux entier, parce qu'un BMSIZE qui ne peut être satisfait qu'en empruntant des octets au segment suivant est malformé et que le valider contre la longueur du flux laisserait le décodeur arithmétique lire dans l'en-tête suivant. La borne inférieure de deux octets reflète la paire d'octets initiale que le décodeur arithmétique consomme toujours, et après le raffinement le lecteur saute à RefinementEnd quelle que soit la distance lue en avance par le décodeur arithmétique, puisque sa position finale n'est pas la position du prochain champ codé en Huffman

// Décodage des régions de texte TJBIG2Bitmap, chemin de raffinement 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;

Ce qui a été vérifié, et ce qui reste refusé

L'échantillon qui est à l'origine de tout ceci, une image JBIG2 de 500 par 473 pixels avec tables personnalisées et raffinement Huffman, se décode désormais en un bitmap sans aucun pixel divergent face à un décodeur indépendant, et les fixtures synthétiques de bitmap collective en 7 et 9 bits produisent les lignes attendues sur les deux. Les deux décodeurs indépendants qui n'étaient pas d'accord sur l'échantillon d'origine ne sont toujours pas d'accord entre eux ; PDFlibPas correspond à l'un des deux, et l'énoncé honnête est que la sortie native concorde avec une implémentation indépendante et avec la spécification telle qu'elle se lit, pas que tous les décodeurs du monde sont d'accord. Le volet malformé de la suite couvre :

• un bit de drapeau réservé ou une valeur de sélecteur réservée
• une table tronquée au milieu d'une ligne
• des longueurs de préfixe en sursouscription et des préfixes de plus de 32 bits
• une région dont les sélecteurs demandent plus de tables personnalisées qu'elle n'en référence
• la confirmation qu'une sortie périmée est effacée après un décodage raté plutôt que laissée en place pour que l'appelant la prenne pour un résultat

Trois limites restent délibérées. L'organisation de flux à accès aléatoire, où tous les en-têtes de segment précèdent toutes les données de segment, lève JBIG2 random-access organisation is not supported dès la lecture des drapeaux d'en-tête de fichier, parce qu'aucun échantillon représentatif n'existe pour la valider et qu'un chemin à moitié implémenté est pire qu'un refus nommé. Les tables personnalisées sont plafonnées à 65 536 lignes et à des préfixes de 32 bits. Et l'entrée publique de décodage, TPLJBIG2Decoder.LoadFromByteArray, renvoie le bitmap de la première page dans l'ordre du flux via getPageAsJBIG2Bitmap(0), le premier segment d'informations de page rencontré, plutôt que de chercher l'association de page zéro ; les flux PDF embarqués numérotent couramment leur page unique 1, et demander la page 0 par association ne trouverait rien. Le texte d'échec atterrit dans TPLJBIG2Decoder.LastError, le diagnostic interne du décodeur qui porte le numéro de segment, le type et le décalage d'octet du défaut, et ce n'est pas la même chose que TPDFlib.LastErrorCode au niveau de la bibliothèque. Rien de tout cela ne touche le côté encodage, qui est traité dans les notes sur les backends d'encodeur JBIG2 et leur édition de liens ; le chemin de lecture doit accepter ce que l'encodeur de quelqu'un d'autre a décidé d'émettre, et il partage ses règles avec le reste de la pile d'images, y compris le décodeur TIFF intégré et ses refus du BigTIFF et des dispositions tuilées : refuser en le nommant, ne jamais emprunter d'octets au-delà d'une frontière déclarée, et garder l'arithmétique assez large pour qu'un intermédiaire qui déborde ne puisse pas passer pour une réponse valide. Si vous évaluez un chemin de lecture JBIG2 natif pour Delphi ou C++Builder, le décodeur et le reste du traitement d'images sont documentés sur la page PDF Library for Delphi