LZW EarlyChange no Delphi: o encoder lidera o decoder

Um dicionário de encoder LZW está sempre uma entrada à frente do decoder que vai ler sua saída, então os dois lados não podem compartilhar um único limiar de largura de código. A PDFlibPas dá a TPLLZWEncoder e TPDFLZWDecompressor limiares separados derivados da mesma flag EarlyChange, e essa liderança de uma entrada é exatamente o motivo de a flag existir

Quase toda implementação LZW feita na mão erra isso no mesmo lugar. Você escreve o decoder primeiro, porque é o que precisa para abrir arquivos. Funciona. Então escreve o encoder, espelhando a lógica do decoder linha por linha porque LZW é simétrico, roda um teste de round-trip, e passa. Você publica. Seis meses depois um cliente abre sua saída em um viewer que não é o seu, e é lixo de algum ponto no meio do stream em diante. O espelho era o bug: as duas metades do LZW não são simétricas, e fingir que são produz streams que só seu próprio código consegue ler

Por que o encoder precisa de um limiar diferente do decoder?

Porque o encoder aprende cada entrada do dicionário um passo antes do decoder. Isso não é uma escolha de design da PDFlibPas; é inerente a como o LZW funciona, e toda implementação correta tem que compensar isso em algum lugar. Percorra o loop e você vê de onde vem a liderança. O encoder acumula uma correspondência, descobre que o próximo byte a quebra, emite o código da correspondência e adiciona imediatamente correspondência-mais-byte ao seu dicionário. O decoder recebe esse mesmo código e o expande, mas não consegue adicionar a entrada correspondente ainda, porque a nova entrada precisa do primeiro byte da próxima string, que chega apenas com o próximo código. Então a qualquer instante enquanto códigos estão fluindo, a tabela do encoder guarda uma entrada a mais que a do decoder. Se ambos os lados alargam o código de 9 para 10 bits quando seu próprio FNextCode atinge o mesmo número, eles alargam um código de distância e o bit reader do outro lado se dessincroniza permanentemente. Em TPDFLZWDecompressor.ResetDictionary o limiar do decoder é calculado uma vez e armazenado em FChangeCode:

// TPDFLZWDecompressor.ResetDictionary: o lado do decodificador do limiar
FCodeSize := FInitialCodeSize;                 // 9 para PDF LZWDecode
FBitMask  := (Cardinal(1) shl FCodeSize) - 1;  // 511
if FEarlyChange then
  FChangeCode := FBitMask                      // aumenta quando FNextCode atinge 511
else
  FChangeCode := FBitMask + 1;                 // aumenta quando FNextCode atinge 512
FClearCode := 1 shl (FCodeSize - 1);           // 256
FEOICode   := FClearCode + 1;                  // 257
FNextCode  := FClearCode + 2;                  // 258

O loop de decodificação alarga logo depois de anexar uma entrada, testando (FNextCode = FChangeCode) and (FCodeSize < 12) e recalculando tanto FBitMask quanto FChangeCode para a nova largura. Nove bits disparam em 511 ou 512, dez bits em 1023 ou 1024, onze bits em 2047 ou 2048, e doze bits é o teto onde o dicionário precisa ser flushed com um ClearCode em vez de crescer. O encoder não pode reutilizar nenhum desses números. Seu GrowCodeSize adiciona um para compensar a liderança, então com EarlyChange definido ele alarga em 512 enquanto o decoder alarga em 511:

procedure GrowCodeSize(FinalDataCode: Boolean);
var
  ChangeCode: Cardinal;
begin
  if FCodeSize >= 12 then
    Exit;
  if FEarlyChange then
    ChangeCode := Cardinal(1) shl FCodeSize          // 512 while at 9 bits
  else
    ChangeCode := (Cardinal(1) shl FCodeSize) + 1;   // 513 while at 9 bits
  // O decodificador adiciona sua última entrada pendente antes de ler EOI.
  if FinalDataCode then
    Dec(ChangeCode);
  if FNextCode = ChangeCode then
    Inc(FCodeSize);
  end;

O último data code é onde os dois lados finalmente se encontram

O fim do stream é o único lugar onde o encoder precisa parar de liderar e pensar como o decoder, que é para isso que serve o parâmetro FinalDataCode em GrowCodeSize. Emita o código EOI na largura errada e tudo antes dele continua perfeitamente válido, então o defeito se esconde atrás de milhares de bytes corretos. A sequência é assim. O encoder emite seu último data code e, ao contrário de toda iteração anterior, não adiciona nada ao seu próprio dicionário em seguida, porque não sobrou nenhum byte seguinte para estender a correspondência. O decoder faz o oposto: recebe esse código final, e só agora consegue completar a entrada que vinha segurando desde a anterior. No último passo o decoder alcança, a liderança colapsa para zero, e a largura que ele vai usar para ler o EOI é decidida por uma entrada que o encoder nunca fez. Dec(ChangeCode) é o encoder fingindo, por exatamente uma chamada, que é o decoder:

// TPLLZWEncoder.Compress, a cauda do stream
EmitCode(CurCode);      // código de dados final, na largura atual
GrowCodeSize(True);     // pode aumentar a largura usando o limiar decrementado
EmitCode(FEOICode);     // EOI na largura que o decodificador realmente lerá
FlushBits;
FlushOutput;

A janela em que isso importa é estreita, e é isso que a torna perigosa. Ela morde apenas quando os dados acabam a uma entrada de dicionário de uma fronteira de largura, então um corpus de cem arquivos de teste pode perder isso por completo enquanto um único arquivo de cliente acerta toda vez. Casos de fronteira em Compress precisam ser conduzidos deliberadamente: crie entradas cujo dicionário pousa em 510, 511 e 512 entradas, e então leia a largura de bits do EOI emitido direto do stream, em vez de inferi-la de uma decodificação bem-sucedida

Por que um teste de round-trip que passa ainda consegue esconder um stream quebrado?

Porque duas implementações que cometem o mesmo erro concordam entre si. Se seu encoder e seu decoder ambos alargam um código cedo demais, ou ambos um código tarde demais, eles permanecem em lockstep, o round trip reproduz a entrada byte por byte, e a suíte fica verde enquanto o stream que você produziu é ilegível por qualquer outra coisa. Essa é a coisa mais valiosa para tirar do exercício inteiro: para LZW, autoconsistência não vale nada como evidência. Então o auto round-trip não pode ser o teste primário, e a PDFlibPas valida o caminho LZW de outras três maneiras. Streams de código montados à mão com o padrão de bits esperado escrito manualmente, de modo que a asserção seja sobre os bytes e não sobre o resultado de decodificá-los. Interoperabilidade bidirecional contra implementações independentes, onde streams produzidos por esse encoder são decodificados em outro lugar e streams produzidos em outro lugar são decodificados por TPDFLZWDecompressor. E decodificação diferencial, lendo os mesmos bytes duas vezes com EarlyChange definido para os dois lados, de modo que um stream que decodifica limpo sob a configuração errada te diz que as fronteiras de largura nunca foram exercitadas:

Dec := TPDFLZWDecompressor.Create;
try
  Dec.EarlyChange := True;
  A := Dec.Decompress(Stream);
finally
  Dec.Free;
end;
Dec := TPDFLZWDecompressor.Create;
try
  Dec.EarlyChange := False;   // deliberadamente a regra errada para PDF
  B := Dec.Decompress(Stream);
finally
  Dec.Free;
end;
// A deve corresponder à origem; B NÃO deve corresponder. Se B também corresponder,
// a entrada era curta demais para cruzar uma fronteira de largura de código.

Entradas externas são o que de fato dá essa cobertura. O material de teste atual cruza larguras de 9, 10, 11 e 12 bits e força 34 resets de dicionário em um único stream, que é a única maneira realista de provar que o caminho ClearCode no teto 4095 funciona. Se seus fixtures nunca passam de alguns kilobytes, nenhum desse código jamais rodou. E quando um fix muda o que seu encoder produz, trate a saída antiga como quebrada em vez de uma baseline de compatibilidade que vale preservar; um stream que mistura larguras de código incorretamente não é um formato legado, é um bug que por acaso foi gravado em disco

O PDF diz 1, o TIFF diz que depende

A PDFlibPas define EarlyChange como True por padrão em ambos TPLLZWEncoder e TPDFLZWDecompressor porque a Tabela 10 da ISO 32000-1 define EarlyChange como um parâmetro de decodificação LZWDecode com valor padrão 1, ou seja, o comprimento do código aumenta um código antes. Isso é especificado na seção 7.4.4.2 da ISO 32000-1 junto com os parâmetros de predictor, e um PDF que quer o outro comportamento precisa dizer /EarlyChange 0 explicitamente no seu dicionário /DecodeParms. O TIFF é o motivo de a flag ser uma propriedade em vez de uma constante: a seção 13 do TIFF 6.0 descreve a compressão LZW sem a mesma declaração inequívoca, e encoders do mundo real historicamente divergem nisso, o que muito provavelmente explica a spec do PDF sentir necessidade de nomear o parâmetro. Em um pipeline TIFF-para-PDF a configuração portanto não é algo que você pode hardcodar em nenhuma das pontas. O que o lado do TIFF precisar tem que ser carregado explicitamente para o /DecodeParms do PDF, ou você converte um arquivo que abria bem em um que não abre. O mesmo cuidado vale para FillOrder, onde foTop e foBottom selecionam de qual ponta do byte o bit reader preenche, e para o differencing horizontal do TIFF Predictor 2, que TPDFLZWParms carrega via Predictor, Colors, BitsPerComponent e Columns. Nossas notas sobre endurecendo o decoder TIFF embutido para BigTIFF e layouts tiled cobrem o resto desse caminho

Duas armadilhas menores que valem ser nomeadas

As duas são fáceis de ligar errado quando você tem os objetos do encoder e do decoder abertos lado a lado e assume que a simetria vale lá também:

• InitialCodeSize não significa a mesma coisa nas duas classes. TPLLZWEncoder.InitialCodeSize é a largura do símbolo raiz, validada de 2 a 8, com InitDictionary derivando FClearCode como 1 shl FInitialCodeSize e definindo FCodeSize como FInitialCodeSize + 1. TPDFLZWDecompressor.InitialCodeSize é a primeira largura de código, validada de 2 a 9, com ResetDictionary derivando FClearCode como 1 shl (FCodeSize - 1). Para dados de PDF comuns de 8 bits os padrões são 8 e 9 respectivamente e você nunca nota; defina os dois para o mesmo número à mão e você construiu um par incompatível
• Decodificar LZW não confiável é um problema de segurança de memória antes de ser um problema de correção, porque os índices do dicionário vêm direto do arquivo. TPDFLZWDecompressor rejeita qualquer código acima de 4095 ou em ou acima de FNextCode, recusa adicionar entradas além de 4095, checa a entrada restante em bits antes de cada GetNextCode, e expõe SawExplicitEOI para que quem chama consiga distinguir um stream terminado corretamente de um que apenas ficou sem bytes. Um stream truncado não é um sucesso parcial. O levantamento mais amplo em endurecendo um parser de PDF em Pascal contra arquivos maliciosos cobre a classe de defeito que essas proteções fecham

O que isso deixa para você

LZW parece simétrico e não é. O dicionário do encoder lidera por uma entrada pelo corpo do stream e a liderança some no código final, então uma implementação correta carrega dois limiares mais um caso especial, e a flag EarlyChange desloca os dois limiares juntos. Erre qualquer um deles por um único código e você produz saída que é válida até deixar de ser, sem erro e sem exceção em lugar nenhum, só um viewer em algum lugar renderizando ruído. A fronteira honesta é que nada disso é testável de dentro: nada na sua própria suíte consegue distinguir um stream correto de um consistentemente errado, então a checagem de interoperabilidade não é uma passada extra opcional, é a única evidência real que você vai ter. As duas classes vêm na PDF Library for Delphi, que também cuida do trabalho de estrutura ao redor descrito em nossas notas sobre object streams e cross-reference streams, para Delphi e C++Builder em todas as versões de compilador que a biblioteca suporta