Tabelas Huffman JBIG2: prefixos canónicos no Delphi

O PDFlibPas versão 3.539.22 descodifica tabelas Huffman personalizadas do JBIG2 de forma nativa: o descodificador em Pascal puro do PDFlibJBIG2.pas faz o parse do segmento Tables (tipo 53), atribui códigos de prefixo canónicos na ordem das linhas da tabela como o Anexo B.3 da ITU-T T.88 exige, consome referências a tabelas personalizadas na ordem dos selectores para symbol dictionaries e regions de texto, e limita cada leitura ao comprimento de segmento declarado em vez de aos bytes que por acaso se seguem

O ficheiro que obrigou a este trabalho não tinha nada de notável à superfície. Um contrato digitalizado, comprimido em JBIG2 com codificação Huffman de símbolos em vez da muito mais comum codificação aritmética, e com o encoder a enviar as suas próprias tabelas de códigos em vez das tabelas padrão B.1 a B.15. Dois descodificadores independentes discordavam nos píxeis de refinement, e o descodificador do PDFlibPas da altura produzia texto com o aspeto de ter passado por uma trituradora: fragmentos de glifos deslocados alguns píxeis, uma coluna de cada caractere em falta. Nada levantava erro. É esta a forma de bug que sobrevive anos, porque um descodificador que rejeita um ficheiro gera um pedido de suporte, enquanto um descodificador que o desenha ligeiramente mal arranja um cliente que assume que o digitalizado era mau

O que contém exatamente um segmento Tables do JBIG2?

Um segmento Tables é uma descrição compacta de uma tabela Huffman: um byte de flags, dois limites assinados de 32 bits, e depois uma série de pares (comprimento do prefixo, comprimento do intervalo) que particionam o intervalo entre os limites, tal como definido na T.88 §7.4.13 e no Anexo B.2. O bit 0 do byte de flags é HTOOB e diz se a tabela tem um código out-of-band. Os bits 1 a 3 mais um dão HTPS, o número de bits usados para escrever cada comprimento de prefixo; os bits 4 a 6 mais um dão HTRS, a largura de cada campo de comprimento de intervalo. O bit 7 é reservado, e o PDFlibPas recusa o segmento se estiver ligado, em vez de adivinhar o que uma revisão futura lhe quis dizer. HTLOW e HTHIGH vêm a seguir como inteiros assinados de 32 bits, e é aqui o primeiro sítio onde um descodificador pode errar: lê-los como não assinados faz uma tabela cujo limite inferior é negativo, perfeitamente normal em larguras de símbolos codificadas por delta, parecer começar em quatro mil milhões. Todos os campos passam por um helper local ReadField que verifica o pedido contra a posição de bit onde terminam os dados do segmento antes de tocar no leitor, porque uma tabela que lesse para lá do seu segmento estaria a consumir o cabeçalho do segmento seguinte como se fossem comprimentos de prefixo

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

As duas linhas acrescentadas depois do ciclo são as linhas de escape do Anexo B.2: a linha de intervalo inferior começa em HTLOW menos um e conta para baixo, a linha de intervalo superior começa em HTHIGH com um intervalo fixo de 32 bits, e a linha OOB opcional não tem valor nenhum. O PDFlibPas marca-as com os comprimentos de intervalo sentinela jbig2HuffmanLOW ($FFFFFFFD) e jbig2HuffmanOOB ($FFFFFFFE), a mesma convenção que as suas quinze tabelas padrão incorporadas usam, pelo que o ciclo de descodificação não quer saber se a tabela veio da especificação ou do ficheiro

Porque é que os códigos de prefixo têm de ser atribuídos pela ordem das linhas da tabela?

Porque o encoder nunca escreve os códigos. Um segmento Tables do JBIG2 transporta apenas comprimentos de prefixo, e ambos os lados reconstroem os padrões de bits reais com o procedimento canónico do Anexo B.3: contar quantas linhas têm cada comprimento, atribuir primeiro os códigos de comprimento um, depois deslocar à esquerda e continuar, e dentro de um mesmo comprimento distribuir os códigos pela ordem em que as linhas aparecem. Qualquer desvio a essa ordem produz silenciosamente uma tabela diferente. O descodificador não vai dar por isso, porque todos os padrões de bits que gera continuam a ser um código de prefixo válido, só não é o que o encoder usou, e a saída é um bitmap de aspeto plausível montado a partir dos símbolos errados

// 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            // estável: ordem original mantida
  if table[I].prefixLen > 0 then       // dentro de cada comprimento
  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;

O THuffmanDecoder.buildTable é uma ordenação por contagem em vez de uma ordenação por comparação por uma razão: uma passagem de contagem sobre Counts, Starts e Positions é estável por construção, pelo que as linhas com o mesmo comprimento de prefixo ficam no resultado pela ordem em que foram declaradas, que é precisamente a ordenação pela qual o Anexo B.3 atribui os códigos. As linhas com comprimento de prefixo zero são descartadas antes da atribuição dos códigos, porque o B.3 define-as como não usadas e não como códigos de um bit. Duas proteções estão no mesmo ciclo. A verificação de sobre-subscrição apanha uma tabela cujos comprimentos reclamam mais códigos do que um código de prefixo dessa profundidade pode conter, o que é a desigualdade de Kraft expressa como comparação de inteiros; sem ela, uma tabela hostil produz um código que corresponde a duas linhas e o descodificador escolhe a que varre primeiro. O teto de 32 bits existe porque prefix é um Cardinal e o matcher em decodeInt acumula bits num só. A T.88 permite prefixos mais longos no papel, o PDFlibPas recusa-os por nome, e nunca se viu um encoder real a emitir um. A aritmética dos valores precisa do mesmo cuidado que a aritmética dos códigos: THuffmanTable.val é um Int64, e a linha de intervalo inferior é descodificada como val - readBits(32), um offset não assinado de 32 bits subtraído a HTLOW menos um. Com intermediários Integer essa subtração dá a volta, e o valor que deu a volta é depois aceite como largura de símbolo. O caminho de 64 bits calcula o valor verdadeiro, verifica-o contra o intervalo assinado de 32 bits e levanta erro se não couber, o que transforma uma corrupção silenciosa numa recusa explícita

Porque é que as tabelas personalizadas nunca disparavam antes da 3.539.22?

Dois defeitos escondiam-se um ao outro. O primeiro era um bug de uma linha num setter: o TTextRegionHuffmanFlags.setFlags recebia o seu argumento com o mesmo nome do campo onde o guardava, pelo que Self.flagsAsInt := flagsAsInt atribuía o campo não inicializado a si próprio e todos os selectores voltavam a zero, o que mandava as regions de texto que pediam tabelas personalizadas pelas tabelas padrão F, H e K. O segundo defeito fazia com que corrigir apenas o primeiro ainda produzisse símbolos corrompidos. Quando um symbol dictionary de Huffman guarda os seus símbolos como um collective bitmap não comprimido, o último byte de cada linha é parcial, e o antigo ciclo de cópia tratava padding, que contém o número de bits válidos, como a posição do bit válido mais baixo; uma linha de 63 píxeis de largura copiava um bit do seu byte final em vez de sete. O ciclo corrigido corre for bitPointer := 7 downto ((8 - padding) and 7), e fixtures sintéticos com larguras de 7 e 9 bits fixam os dois lados da fronteira do byte. Com os selectores a ler corretamente, as tabelas são distribuídas pela ordem em que a especificação as lista, que a T.88 §7.4.3.1.2 fixa para as regions de texto como FS, DS, DT, RDW, RDH, RDX, RDY e RSIZE e a §7.4.2.1.1 fixa para os symbol dictionaries como DH, DW, BMSIZE e AGGINST. Cada selector de dois bits significa tabela padrão 0 ou 1, reservado para 2 nos campos que só têm duas tabelas padrão, e personalizada para 3, e cada seleção personalizada consome o próximo segmento Tables entre os segmentos referidos, na ordem de referência. O NextCustomHuffmanTable faz exatamente essa caminhada e levanta missing custom Huffman table reference quando uma region refere menos tabelas do que os seus selectores exigem. Há mais uma linha no mesmo conjunto de correções: um symbol dictionary de Huffman cujos símbolos de entrada e novos somam um calcula um comprimento de código de símbolo de zero a partir da fórmula log2, enquanto a variante Huffman do formato escreve cada ID de símbolo com pelo menos um bit, por isso if sdHuffman and (symbolCodeLength = 0) then symbolCodeLength := 1 em TSymbolDictionarySegment impede que o caminho de refinement e agregação leia zero bits por ID de símbolo

O que garante a fronteira do segmento?

O PDFlibPas trata o comprimento de dados de cada cabeçalho de segmento como um contrato que as duas direções têm de cumprir: um segmento não pode ler para lá do fim declarado, e não pode terminar antes e deixar o cabeçalho seguinte numa posição imprevisível. As regras que saem desse contrato são individualmente pequenas. Um comprimento de dados com o bit 31 ligado é o marcador de comprimento desconhecido da T.88 §7.2.7, e o handleSegmentDataLength mapeia-o para um valor negativo que o readSegments rejeita de imediato em vez de procurar à frente um terminador. Cada número de segmento referido tem de ser menor que o número do segmento atual e já tem de existir, pelo que uma referência para a frente ou pendente falha antes de qualquer region tentar resolvê-la. END_OF_PAGE e END_OF_FILE têm de declarar zero bytes de dados. Um segmento Profiles (tipo 52) transporta uma contagem de 32 bits seguida de tantos identificadores de 32 bits e nenhum píxel, por isso é verificado como 4 mais 4 vezes a contagem contra o comprimento declarado, é ignorado e fica na lista de segmentos só para que os segmentos posteriores o possam continuar a referir por número. Um identificador de perfil desconhecido não é uma codificação desconhecida, e tratá-lo como tal rejeitaria ficheiros que descodificam perfeitamente bem

// 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');
// ... criar o objeto de segmento para este 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;   // o MMR pode deixar o EOFB por ler
  reader.bitPointer := 7;
end;

A cauda desse ciclo é onde uma versão anterior do descodificador errava em regions codificadas em MMR. Um descodificador MMR sabe que terminou quando o último píxel da última linha é produzido, o que pode acontecer antes de ter consumido o terminador EOFB que a T.88 §6.2.5.7 coloca no fim dos dados. O código antigo assumia que o leitor estava posicionado no cabeçalho seguinte, pelo que os bytes do terminador sobrantes eram interpretados como um número de segmento e o stream falhava uns bytes depois com um erro enganador. Agora o fim declarado ganha: ler para lá dele é um erro, terminar antes é normal, e o leitor é movido para DataEnd com o ponteiro de bits reiniciado, para que o cabeçalho seguinte seja lido de onde o ficheiro disse que estaria. A mesma disciplina aparece em todo o sítio onde o PDFlibPas faz o parse de estruturas PDF não fidedignas: o comprimento declarado é a fronteira, e o descodificador não vai à procura de uma mais amigável

Onde é que o refinement de Huffman lê o tamanho do bitmap?

Antes de o descodificador aritmético arrancar, e a partir de um campo que só existe no modo Huffman. Quando uma instância de region de texto transporta refinement (RI diferente de zero) e SBHUFF está ligado, a T.88 §6.4.11 faz o descodificador ler RDW, RDH, RDX e RDY com as tabelas selecionadas, depois BMSIZE com a tabela RSIZE, depois alinhar a uma fronteira de byte, e só então correr a descodificação genérica de refinement sobre exatamente BMSIZE bytes. As regions de texto em modo aritmético não têm esse campo, e um descodificador que partilha um único caminho de código para os dois modos vai saltá-lo, arrancar o descodificador aritmético dois ou mais bytes mais cedo, e refinar cada símbolo contra lixo. O caminho do symbol dictionary com REFAGG e uma única instância de refinement, descrito em §6.5.8.2.2, tem o mesmo campo BMSIZE com as mesmas consequências. No PDFlibPas o limite superior desse tamanho é o TStreamReader.SegmentEnd, o fim do segmento atual tal como foi definido pelo readSegments, e não o fim do stream inteiro, porque um BMSIZE que só se satisfaça pedindo bytes emprestados ao segmento seguinte está malformado e validá-lo contra o comprimento do stream deixaria o descodificador aritmético ler para dentro do cabeçalho seguinte. O limite inferior de dois bytes reflete o par de bytes inicial que o descodificador aritmético consome sempre, e depois do refinement o leitor salta para RefinementEnd independentemente do quanto o descodificador aritmético leu à frente, já que a sua posição final não é a posição do próximo campo codificado em Huffman

// Descodificação de region de texto em TJBIG2Bitmap, caminho de 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;

O que foi verificado, e o que continua a ser recusado

A amostra que deu origem a isto, uma imagem JBIG2 de 500 por 473 píxeis com tabelas personalizadas e refinement de Huffman, descodifica agora para um bitmap com zero píxeis diferentes em relação a um descodificador independente, e os fixtures sintéticos de collective bitmap de 7 e 9 bits produzem as linhas esperadas em ambos. Os dois descodificadores independentes que discordavam na amostra original continuam a discordar um do outro; o PDFlibPas coincide com um deles, e a afirmação honesta é que a saída nativa coincide com uma implementação independente e com a especificação tal como lida, não que todos os descodificadores do mundo coincidam. O lado malformado da suite cobre:

• um bit de flag reservado ou um valor de selector reservado
• uma tabela truncada a meio de uma linha
• comprimentos de prefixo sobre-subscritos e prefixos com mais de 32 bits
• uma region cujos selectores pedem mais tabelas personalizadas do que aquelas que refere
• confirmação de que a saída obsoleta é limpa depois de uma descodificação falhada, em vez de ficar lá para o chamador a tomar por um resultado

Três limites continuam a ser deliberados. A organização de stream de acesso aleatório, em que todos os cabeçalhos de segmento precedem todos os dados de segmento, levanta JBIG2 random-access organisation is not supported assim que as flags do cabeçalho do ficheiro são lidas, porque não existe nenhuma amostra representativa para validá-la e um caminho meio implementado é pior do que uma recusa com nome. As tabelas personalizadas estão limitadas a 65.536 linhas e a prefixos de 32 bits. E a entrada pública de descodificação, TPLJBIG2Decoder.LoadFromByteArray, devolve o primeiro bitmap de página na ordem do stream através de getPageAsJBIG2Bitmap(0), o primeiro segmento page-information encontrado, em vez de procurar pela associação de página zero; os streams PDF incorporados numeram habitualmente a sua única página como 1, e pedir a página 0 por associação não encontraria nada. O texto de falha fica em TPLJBIG2Decoder.LastError, o diagnóstico interno do descodificador que transporta o número de segmento, o tipo e o offset de bytes da falha, e não é a mesma coisa que o TPDFlib.LastErrorCode ao nível da biblioteca. Nada disto toca no lado da codificação, que é abordado nas notas sobre backends de encoder JBIG2 e a forma como são ligados; o caminho de leitura tem de aceitar o que quer que o encoder de outra pessoa decidiu emitir, e partilha as suas regras com o resto da pilha de imagens, incluindo o descodificador TIFF incorporado e as suas recusas de BigTIFF e de layout em mosaico: recusar por nome, nunca pedir bytes emprestados através de uma fronteira declarada, e manter a aritmética suficientemente larga para que um intermediário que deu a volta não passe por resposta válida. Se está a avaliar um caminho de leitura JBIG2 nativo para Delphi ou C++Builder, o descodificador e o resto do tratamento de imagens estão documentados na página da PDF Library for Delphi