PDFlibPas JBIG2: HSKIP e offsets negativos de grid

O PDFlibPas consertou duas falhas independentes no decodificador nativo de halftone region JBIG2 dele: na v3.539.37 a skip mask do HSKIP é indexada como HSKIP[ng, mg], como a ITU-T T.88 §6.6.5.1 define, e na v3.539.38 grids que alcançam coordenadas negativas, por um HGX ou HGY negativo ou por rotação, são posicionadas com um floor shift de verdade. Antes dessas releases, regions de halftone afetadas saíam embaralhadas ou deslocadas, sem levantar erro nenhum. Os dois bugs se esconderam atrás de dados de teste que por acaso eram simétricos ou não negativos, e o segundo acende sobre uma propriedade de Delphi e Free Pascal que morde muito além do JBIG2: shr sobre um inteiro com sinal é um shift lógico, não o >> aritmético que o padrão assume

Halftone regions são o tipo de region JBIG2 menos comum, então um decodificador pode processar milhares de documentos escaneados antes de encontrar uma fotografia com retícula codificada como uma. Quando encontra, a falha é desagradável: o arquivo parseia, os comprimentos de segmento somam, a página tem o tamanho certo, e a region é lixo

O que uma halftone region JBIG2 realmente decodifica?

Uma halftone region JBIG2 é um grid de bitmaps pequenos escolhidos de um pattern dictionary, e o trabalho real do decodificador é computar um índice para cada célula do grid e a posição de pixel onde essa célula pousa. O pattern dictionary guarda HNUMPATS patterns de HPW × HPH pixels. O segmento de halftone region então descreve um grid de HGW colunas por HGH linhas e uma gray-scale image do mesmo tamanho, codificada como bitplanes Gray-coded. Cada bitplane é decodificado com o procedimento de generic region sobre um bitmap de HGW × HGH, o plano mais significativo primeiro, e os planos juntos dão a cada célula o pattern index dela

O posicionamento de células usa aritmética de ponto fixo com fração de 8 bits. A origem do grid HGX, HGY é um par de valores de 32 bits, e o grid vector HRX, HRY descreve o passo entre células vizinhas, o que permite um grid rotacionado. Para a linha de grid mg e a coluna de grid ng, a T.88 §6.6.5 computa a posição de pixel como:

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

A skip mask entra pela flag opcional HENABLESKIP. Quando a flag está setada, a §6.6.5.1 constrói um bitmap HGW × HGH chamado HSKIP e seta HSKIP[ng, mg] para 1 em toda célula cujo pattern fica inteiramente fora da region: x + HPW <= 0, x >= HBW, y + HPH <= 0 ou y >= HBH. Os bitplanes gray-scale são então decodificados com essa mask como skip bitmap do generic region, então o arithmetic decoder não lê nem atualiza contexto para uma célula pulada. Decodificador e encoder precisam concordar em todo bit do HSKIP, ou os dois arithmetic coders dessincronizam

Por que uma skip mask HSKIP transposta só quebrava grids não quadrados?

A skip mask era escrita com as coordenadas trocadas, e só um grid não quadrado a expunha, porque um grid quadrado mantém toda coordenada trocada dentro da mask. O PDFlibPas guarda bitmaps com um acessor de pixel (coluna, linha), e o código que construía a mask passava (mg, ng), linha primeiro. O decodificador de bitplanes gray-scale lê a mask corretamente como (ng, mg). O loop de posicionamento de patterns a lia de volta na ordem trocada do construtor, então os dois concordavam, e uma revisão só da lógica de posicionamento a aprovaria. Uma armadilha de nomes piorou isso: no loop de posicionamento a variável chamada col itera linhas de grid e Row itera colunas de grid

Tome o grid de 5 × 3 de patterns de 4 × 4 numa region de 16 × 8 que a v3.539.37 usa como caso de regressão. Com HRX = 1024 e HRY = 0, a coluna de grid 4 pousa em x = 16 e a linha de grid 2 em y = 8, ambas fora da region. A mask correta marca sete células: a coluna 4 inteira e a linha 2 inteira. As escritas trocadas tentavam setar pixels nos índices de linha 3 e 4 numa mask de só três linhas de altura, e o setter do bitmap silenciosamente ignorava essas escritas fora de faixa. O que sobrou foi a coluna 2, linhas 0 a 2. O decodificador portanto pulava duas células que o encoder tinha codificado, e decodificava seis células que o encoder tinha pulado

O arithmetic decoder não falha quando isso acontece. Ele decodifica pixels extras a partir de bits que pertencem a células posteriores, os contextos dele leem vizinhos errados, e todo pattern index depois do primeiro desencontro é ruído, e é por isso que o sintoma era uma region embaralhada em vez de algumas células fora do lugar. Num grid quadrado o mesmo bug costuma ser invisível: nenhuma coordenada trocada sai da mask, e quando as células fora da region são simétricas em torno da diagonal, um grid que transborda as bordas direita e inferior pelo mesmo número de células por exemplo, a mask transposta é bit a bit a correta. O HENABLESKIP também é opcional, precisa ser 0 quando a gray-scale image é MMR-coded, e raramente é setado por encoders, então o bug tinha muito poucos jeitos de aparecer. Desde a v3.539.37 o construtor escreve HSKIP[ng, mg] e o loop de posicionamento lê na mesma ordem

Por que offsets negativos de halftone grid falham em três camadas?

Um halftone grid que começa à esquerda de ou acima da region dele quebrava o PDFlibPas em três lugares separados, e cada falha escondia a seguinte. A T.88 permite essa geometria de propósito. Um encoder que alinha a retícula dele com a página em vez de com a region, ou usa um grid rotacionado, naturalmente produz cantos de célula negativos que a region recorta. A v3.539.38 consertou as três camadas juntas, porque consertar qualquer uma sozinha só mudava o sintoma

Camada 1: um campo com sinal lido como unsigned

A T.88 §7.4.5.1.2 define HGX e HGY como valores de 32 bits com sinal, mas o decodificador os lia com o mesmo helper de 32 bits que usava para campos unsigned, e esse helper clampeava todo resultado negativo para 0. Um grid que devia começar em HGX = -900 era silenciosamente movido para a origem da region. No caso de regressão da v3.539.38 a figura inteira saía duas linhas abaixo do certo. O clamp também explica por que as outras duas falhas sobreviveram tanto tempo: com a origem forçada a ser não negativa, uma coordenada negativa só podia aparecer através de um grid rotacionado com HRY > 0, em que y = HGY + mg × HRX − ng × HRY fica abaixo de zero para colunas de grid posteriores

Camada 2: shr não é >> 8

A T.88 escreve >> 8 e quer dizer um shift aritmético, que arredonda para menos infinito. O decodificador traduzia como shr 8. Em Delphi e Free Pascal, shr sobre um inteiro com sinal é um shift lógico: o bit de sinal entra como zero. Para um Integer segurando -512, shr 8 dá 16777214 em vez de -2. Um pattern que devia ser desenhado em y = -2 e recortado à metade inferior dele foi enviado 16 milhões de linhas para baixo e descartado como fora da region. Nada travou; a linha de cima do halftone simplesmente sumiu

Camada 3: comparar ponto fixo em vez de pixels

O teste de skip comparava valores de ponto fixo, não posições de pixel, e os dois não são equivalentes quando a fração é não zero. O código original driblava o shift lógico testando xx + HPW × 256 <= 0 sobre o valor sem shift, um suposto equivalente do teste da T.88. Com HGX = -900 e um pattern de 4 pixels, isso dá -900 + 1024 = 124, que é positivo, então a célula não é pulada. O padrão faz o shift primeiro: floor(-900 / 256) = -4, e -4 + 4 = 0 satisfaz x + HPW <= 0, então a célula está inteiramente fora e precisa ser pulada. O encoder pulava, o decodificador decodificava, e a gray-scale image derivava exatamente como no caso da mask transposta

O caso de regressão da v3.539.38 usa um grid de 4 × 3 de patterns de 4 × 4 em HGX = -900, HGY = -512, HRX = 1024 numa region de 12 × 10. As colunas de grid pousam em x = -4, 0, 4 e 8, então a coluna 0 está inteiramente fora e pertence ao HSKIP; as linhas de grid pousam em y = -2, 2 e 6, então a linha 0 precisa ser recortada às duas linhas de pixel inferiores dela em vez de descartada. Consertar as camadas uma a uma reproduz a pilha:

Falhas consertadas	Region decodificada
Nenhuma (antes da v3.539.38)	Grid puxado para a origem, figura inteira duas linhas abaixo
Leitura com sinal de HGX / HGY apenas	Primeira linha do grid faltando, o resto embaralhado pela deriva do teste de skip
Leitura com sinal, floor shift e teste de skip em espaço de pixels	Idêntica, pixel por pixel, à página computada da T.88 §6.6.5 e a dois decodificadores de referência independentes

A correção é um helper, HalftoneGridPixel, compartilhado pelo construtor da skip mask e pelo loop de posicionamento. Ele acumula a coordenada em Int64 para que um produto grande mg × HRX não dê wrap, divide por 256 arredondando para menos infinito, e clampa para ±MaxInt div 2 para que um grid corrompido não estoure a aritmética de bitmap mais tarde. O teste de skip agora compara esses valores de pixel contra HPW, HPH, HBW e HBH, exatamente como a §6.6.5.1 afirma

Como se escreve um shift aritmético à direita em Delphi?

Delphi não tem operador de shift aritmético, então um shift right correto com sinal precisa ser escrito como uma divisão floor, e o div comum não é essa divisão. O div trunca para zero. Para valores não negativos truncamento e floor concordam, e também concordam para valores negativos que são múltiplos exatos do divisor, e é por isso que -512 div 256 = -2 parece certo num teste rápido. Eles discordam em todo o resto: -900 div 256 é -3, enquanto o floor é -4, e -1 div 256 é 0, enquanto o floor é -1. Uma coordenada JBIG2 com fração não zero é exatamente o caso em que o div dá o pixel errado

Nos compiladores Delphi Win32 e Win64, uma variável Integer segurando -512 deslocada à direita por 8 dá 16777214, e um Int64 segurando -512 dá 72057594037927934. O Free Pascal também define shr como shift lógico e entrega SarLongint e SarInt64 na unit System dele para a versão aritmética, mas essas funções não existem em Delphi, então código compartilhado entre os dois compiladores precisa do próprio helper:

// Divisão floor: arredonda para menos infinito para qualquer sinal de A e B.
// B não pode ser 0, e FloorDiv(Low(Integer), -1) estoura exatamente como 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;

// Shift aritmético à direita (o ">>" de C e da T.88 sobre valores com sinal).
// Para Value negativo, not Value = -Value - 1 é não negativo, então o
// shr lógico é seguro ali, e o not externo mapeia o resultado de volta
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;

O truque do not nunca desloca um número negativo, então não depende de como o compilador trata o bit de sinal, e nunca estoura, inclusive para Low(Integer). Ambos os helpers bateram com uma referência de floor em Int64 sobre vários milhões de valores, todo shift de 0 a 31 e as bordas Low(Integer) e High(Integer) no Delphi Win32, Delphi Win64 e Free Pascal x86_64. Um sanity check que vale manter em qualquer teste de unit que toque coordenadas:

var
  V: Integer;
begin
  V := -900;
  Writeln(V shr 8);           // 16777212  shift lógico, o bug antigo
  Writeln(V div 256);         // -3        truncamento para zero
  Writeln(FloorDiv(V, 256));  // -4        o que a T.88 quer dizer com >> 8
  Writeln(SarInt32(V, 8));    // -4
end;

O Math.Floor(V / 256) também retorna -4, mas o desvio dele por Double perde precisão para valores Int64 acima de 2⁵³, então geometria inteira deve ficar em inteiros

Quais chamadas do PDFlibPas rodam o decodificador de halftone?

O decodificador de halftone JBIG2 roda quando o PDFlibPas renderiza uma página com o renderer embutido, porque renderizar precisa de pixels. O RenderPageToFile e o RenderPageToStream ambos chegam até ele através dos image streams JBIG2Decode da página, então re-renderizar uma página de halftone é o caminho direto para confirmar que a v3.539.38 muda o seu output. O mesmo decodificador cuida dos outros tipos de region JBIG2, cobertos em tabelas de Huffman customizadas JBIG2 no decodificador Pascal puro e decodificar arquivos JBIG2 random-access em Delphi, e o bitmap renderizado alimenta conversões como renderizar páginas de PDF para 1-bit monochrome

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
      // Renderizar decodifica toda region JBIG2, halftones incluídos
      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.

A extração de imagens normalmente toma um caminho diferente. O GetPageImageList retorna imagens JBIG2 na forma nativa, e o SaveImageListItemDataToFile ou o GetImageListItemDataToString te entrega um arquivo JBIG2 standalone construído dos bytes do stream: o file header, os dados de JBIG2Globals e um segmento end-of-file em torno dos dados da página. A propriedade 400 do GetImageListItemIntProperty reporta 6 para tal item. Nada é decodificado nesse caminho, então um .jb2 extraído que parece correto em outro viewer enquanto a página renderizada mostra ruído era um sinal típico desses dois bugs de 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 standalone
        Lib.SaveImageListItemDataToFile(ListID, I, 0,
          Format('page1-image%d.jb2', [I]));
  finally
    Lib.ReleaseImageList(ListID);
  end;
end;

Quando masks ou conversão de cor forçam um fallback renderizado, o item volta como bitmap decodificado e o decodificador de halftone roda mesmo. Mais sobre image lists está em extração de texto, imagem e fonte de PDF em Delphi

Referência rápida: regras de halftone grid JBIG2

• Indexe a skip mask como HSKIP[ng, mg], coluna de grid primeiro, e leia de volta na mesma ordem onde quer que células sejam posicionadas (T.88 §6.6.5.1, corrigido no PDFlibPas v3.539.37)
• Teste qualquer código de halftone ou de grid com um grid não quadrado e um conjunto assimétrico de células fora da region, porque um grid quadrado pode esconder completamente um índice transposto
• Leia HGX e HGY como valores de 32 bits com sinal (T.88 §7.4.5.1.2), nunca através de um helper unsigned que clampe negativos
• Traduza o >> 8 do padrão como uma divisão floor por 256, não como shr 8 e não como div 256
• Rode o teste de skip sobre posições de pixel deslocadas; a forma de ponto fixo difere sempre que a fração é não zero, como HGX = -900 com um pattern de 4 pixels mostra
• Acumule coordenadas de grid em Int64 e clampe antes de entregá-las a código de bitmap, para que um grid corrompido não estoure
• Faça upgrade para a v3.539.38 ou posterior se os seus documentos contêm halftone regions com HENABLESKIP, origens de grid negativas ou grids rotacionados

O PDFlibPas renderiza, extrai e edita documentos PDF a partir de Delphi e C++Builder com um decodificador JBIG2 Pascal nativo que agora cuida de skip masks de halftone, origens de grid negativas e grids rotacionados como a T.88 especifica. Veja a biblioteca de PDF PDFlibPas para Delphi para recursos, edições e download de teste