LZW EarlyChange en Delphi: el encoder lleva la delantera

El diccionario de un encoder LZW siempre va una entrada por delante del decoder que leerá su salida, así que los dos lados no pueden compartir un único umbral de ancho de código. PDFlibPas les da a TPLLZWEncoder y TPDFLZWDecompressor umbrales separados derivados del mismo flag EarlyChange, y esa ventaja de una entrada es toda la razón de que el flag exista

Casi toda implementación LZW hecha a mano falla en el mismo lugar. Escribes el decoder primero, porque es lo que necesitas para abrir archivos. Funciona. Después escribes el encoder, reflejando la lógica del decoder línea por línea porque LZW es simétrico, corres un test de round-trip y pasa. Lo publicas. Seis meses después un cliente abre tu salida en un visor que no es el tuyo y es basura desde algún punto del medio del stream en adelante. El espejo era el bug: las dos mitades de LZW no son simétricas, y pretender que lo son produce streams que solo tu propio código puede leer

¿Por qué el encoder necesita un umbral distinto al del decoder?

Porque el encoder aprende cada entrada del diccionario un paso antes de lo que puede el decoder. Eso no es una decisión de diseño en PDFlibPas; es inherente a cómo funciona LZW, y toda implementación correcta tiene que compensarlo en algún lugar. Recorre el loop y verás de dónde viene la ventaja. El encoder acumula una coincidencia, descubre que el siguiente byte la rompe, emite el código de la coincidencia e inmediatamente agrega coincidencia-más-byte a su diccionario. El decoder recibe ese mismo código y lo expande, pero todavía no puede agregar la entrada correspondiente, porque la entrada nueva necesita el primer byte de la siguiente string, que llega recién con el código siguiente. Así que en cualquier instante mientras fluyen los códigos, la tabla del encoder tiene una entrada más que la del decoder. Si ambos lados ensanchan el código de 9 a 10 bits cuando su propio FNextCode llega al mismo número, se ensanchan con un código de diferencia y el bit reader del otro extremo se desincroniza para siempre. En TPDFLZWDecompressor.ResetDictionary el umbral del decoder se calcula una vez y se guarda en FChangeCode:

// TPDFLZWDecompressor.ResetDictionary: el lado del decoder del umbral
FCodeSize := FInitialCodeSize;                 // 9 para LZWDecode de PDF
FBitMask  := (Cardinal(1) shl FCodeSize) - 1;  // 511
if FEarlyChange then
  FChangeCode := FBitMask                      // ensancha cuando FNextCode llega a 511
else
  FChangeCode := FBitMask + 1;                 // ensancha cuando FNextCode llega a 512
FClearCode := 1 shl (FCodeSize - 1);           // 256
FEOICode   := FClearCode + 1;                  // 257
FNextCode  := FClearCode + 2;                  // 258

El loop de decodificación ensancha justo después de agregar una entrada, probando (FNextCode = FChangeCode) and (FCodeSize < 12) y recalculando tanto FBitMask como FChangeCode para el ancho nuevo. Nueve bits disparan en 511 o 512, diez bits en 1023 o 1024, once bits en 2047 o 2048, y doce bits es el techo donde el diccionario tiene que purgarse con un ClearCode en lugar de crecer. El encoder no puede reutilizar ninguno de esos números. Su GrowCodeSize suma uno para compensar la ventaja, así que con EarlyChange activado ensancha en 512 mientras el decoder ensancha en 511:

procedure GrowCodeSize(FinalDataCode: Boolean);
var
  ChangeCode: Cardinal;
begin
  if FCodeSize >= 12 then
    Exit;
  if FEarlyChange then
    ChangeCode := Cardinal(1) shl FCodeSize          // 512 mientras esté en 9 bits
  else
    ChangeCode := (Cardinal(1) shl FCodeSize) + 1;   // 513 mientras esté en 9 bits
  // El decoder agrega su última entrada pendiente antes de leer EOI.
  if FinalDataCode then
    Dec(ChangeCode);
  if FNextCode = ChangeCode then
    Inc(FCodeSize);
  end;

El último data code es donde ambos lados por fin se encuentran

El final del stream es el único lugar donde el encoder tiene que dejar de liderar y pensar como el decoder, que es para lo que sirve el parámetro FinalDataCode de GrowCodeSize. Emite el código EOI con el ancho equivocado y todo lo anterior sigue siendo perfectamente válido, así que el defecto se esconde detrás de miles de bytes correctos. La secuencia va así. El encoder emite su último data code y, a diferencia de toda iteración anterior, no agrega nada a su diccionario después, porque no queda ningún byte siguiente con el que extender la coincidencia. El decoder hace lo contrario: recibe ese código final y solo ahora puede completar la entrada que venía reteniendo desde el código anterior. En el último paso el decoder alcanza al encoder, la ventaja colapsa a cero, y el ancho que usará para leer EOI lo decide una entrada que el encoder nunca creó. Dec(ChangeCode) es el encoder fingiendo, por exactamente una llamada, que es el decoder:

// TPLLZWEncoder.Compress, la cola del stream
EmitCode(CurCode);      // último data code, al ancho que sea el actual
GrowCodeSize(True);     // puede ensanchar usando el umbral decrementado
EmitCode(FEOICode);     // EOI al ancho que el decoder realmente va a leer
FlushBits;
FlushOutput;

La ventana en la que esto importa es angosta, que es lo que lo hace peligroso. Solo muerde cuando los datos se terminan justo dentro de una entrada de diccionario de un límite de ancho, así que un corpus de cien archivos de prueba puede pasarlo por alto del todo mientras un archivo de un cliente lo golpea siempre. Los casos de borde en Compress hay que llevarlos a propósito: fabrica inputs cuyo diccionario aterrice en 510, 511 y 512 entradas, y luego lee el ancho de bits del EOI emitido directamente del stream en lugar de inferirlo de una decodificación exitosa

¿Por qué un round-trip que pasa puede seguir ocultando un stream roto?

Porque dos implementaciones que cometen el mismo error se ponen de acuerdo entre ellas. Si tu encoder y tu decoder ensanchan ambos un código demasiado temprano, o ambos un código demasiado tarde, se quedan en lockstep, el round trip reproduce el input byte por byte y la suite queda verde mientras el stream que produjiste es ilegible para cualquier otra cosa. Esa es la lección más valiosa de todo este asunto: para LZW, la autoconsistencia no vale nada como evidencia. Así que el round-trip con uno mismo no puede ser el test principal, y PDFlibPas valida el camino LZW de otras tres formas. Streams de código armados a mano con el patrón de bits esperado escrito a mano, para que la aserción sea sobre los bytes y no sobre el resultado de decodificarlos. Interoperabilidad bidireccional contra implementaciones independientes, donde streams que produjo este encoder se decodifican en otro lado y streams producidos en otro lado los decodifica TPDFLZWDecompressor. Y decodificación diferencial, leyendo los mismos bytes dos veces con EarlyChange activado en ambos sentidos, para que un stream que decodifica limpio bajo la configuración equivocada te diga que los límites de ancho nunca se ejercieron:

Dec := TPDFLZWDecompressor.Create;
try
  Dec.EarlyChange := True;
  A := Dec.Decompress(Stream);
finally
  Dec.Free;
end;
Dec := TPDFLZWDecompressor.Create;
try
  Dec.EarlyChange := False;   // a propósito la regla equivocada para PDF
  B := Dec.Decompress(Stream);
finally
  Dec.Free;
end;
// A debe coincidir con la fuente; B NO debe coincidir. Si B también coincide,
// el input era demasiado corto para cruzar un límite de ancho de código.

Los inputs externos son lo que de verdad da esa cobertura. El material de test actual cruza anchos de 9, 10, 11 y 12 bits y fuerza 34 resets de diccionario en un solo stream, que es la única forma realista de probar que el camino ClearCode en el techo de 4095 funciona. Si tus fixtures nunca pasan de unos kilobytes, nada de ese código se ejecutó jamás. Y cuando un fix cambia lo que produce tu encoder, trata la salida vieja como rota en lugar de como una baseline de compatibilidad que valga la pena preservar; un stream que mezcla anchos de código de forma incorrecta no es un formato legacy, es un bug que por casualidad se escribió en disco

PDF dice 1, TIFF depende

PDFlibPas define EarlyChange como True tanto en TPLLZWEncoder como en TPDFLZWDecompressor porque la Tabla 10 de ISO 32000-1 define EarlyChange como un parámetro de decodificación de LZWDecode con valor predeterminado 1, lo que significa que la longitud del código crece un código antes. Eso se especifica en la sección 7.4.4.2 de ISO 32000-1 junto con los parámetros de predictor, y un PDF que quiera el otro comportamiento tiene que decir /EarlyChange 0 explícitamente en su diccionario /DecodeParms. TIFF es la razón de que el flag sea una propiedad y no una constante: la sección 13 de TIFF 6.0 describe la compresión LZW sin la misma afirmación inequívoca, y los encoders del mundo real se han dividido históricamente al respecto, que es muy probablemente la razón por la que la spec de PDF sintió la necesidad de nombrar el parámetro. En un pipeline de TIFF a PDF, por tanto, la configuración no es algo que puedas hardcodear en ninguno de los dos extremos. Lo que haya resultado necesario del lado TIFF tiene que llevarse explícito al /DecodeParms del PDF, o conviertes un archivo que abría bien en uno que no abre. El mismo cuidado aplica a FillOrder, donde foTop y foBottom eligen de qué extremo del byte llena el bit reader, y al Predictor 2 de TIFF con diferencia horizontal, que TPDFLZWParms lleva a través de Predictor, Colors, BitsPerComponent y Columns. Nuestras notas sobre endurecer el decoder TIFF integrado para BigTIFF y layouts con tiles cubren el resto de ese camino

Dos trampas más chicas que vale la pena nombrar

Las dos son fáciles de conectar mal cuando tienes los objetos del encoder y del decoder abiertos lado a lado y asumes que la simetría se mantiene también ahí:

• InitialCodeSize no significa lo mismo en ambas clases. TPLLZWEncoder.InitialCodeSize es el ancho de símbolo raíz, validado de 2 a 8, con InitDictionary derivando FClearCode como 1 shl FInitialCodeSize y poniendo FCodeSize en FInitialCodeSize + 1. TPDFLZWDecompressor.InitialCodeSize es el primer ancho de código, validado de 2 a 9, con ResetDictionary derivando FClearCode como 1 shl (FCodeSize - 1). Para datos PDF ordinarios de 8 bits los predeterminados son 8 y 9 respectivamente y nunca lo notas; ponles a los dos el mismo número a mano y has construido un par desalineado
• Decodificar LZW de fuentes no confiables es un problema de seguridad de memoria antes que de corrección, porque los índices del diccionario vienen directo del archivo. TPDFLZWDecompressor rechaza cualquier código por encima de 4095 o igual o por encima de FNextCode, se niega a agregar entradas pasadas 4095, revisa el input restante en bits antes de cada GetNextCode y expone SawExplicitEOI para que un caller pueda distinguir un stream terminado como corresponde de uno que simplemente se quedó sin bytes. Un stream truncado no es un éxito parcial. El recorrido más amplio en endurecer un parser PDF en Pascal contra archivos maliciosos cubre la clase de defectos que cierran estas guardas

Con qué te quedas de todo esto

LZW parece simétrico y no lo es. El diccionario del encoder va una entrada por delante durante todo el cuerpo del stream y la ventaja desaparece en el código final, así que una implementación correcta lleva dos umbrales más un caso especial, y el flag EarlyChange desplaza ambos umbrales juntos. Desfasa cualquiera de los dos por un solo código y produces salida que es válida justo hasta que deja de serlo, sin error y sin excepción en ningún lado, solo un visor en algún lugar renderizando ruido. El límite honesto es que nada de esto es testeable desde adentro: nada en tu propia suite puede distinguir un stream correcto de uno consistentemente equivocado, así que el chequeo de interoperabilidad no es una pasada extra opcional, es la única evidencia real que vas a tener jamás. Ambas clases viajan en PDF Library for Delphi, que además se encarga del trabajo estructural circundante que describen nuestras notas sobre object streams y cross-reference streams, para Delphi y C++Builder en las versiones de compilador que soporta la librería