Errores Reed-Solomon en cuatro codificadores 2D de Delphi

Un codificador Reed-Solomon que guarda primero el término constante de su polinomio generador y después divide primero por el término principal no está calculando corrección de errores en absoluto. HotPDF llevaba exactamente eso en cuatro codificadores de códigos 2D, QR, Data Matrix, PDF417 y Aztec, y cada símbolo que producían traía un bloque de comprobación que ningún lector compatible podía usar

Lo interesante no es el desliz aritmético, sino la propagación. Se escribió primero un codificador, su bucle de división se copió en los otros tres, y cada formato nuevo heredó un defecto que jamás se había validado contra un solo vector de prueba publicado. Los símbolos seguían renderizándose, los patrones de localización estaban en su lugar, los tamaños eran correctos. Solo los bytes que le permiten a un código 2D sobrevivir a una mancha eran basura

Un polinomio invertido, copiado en cuatro codificadores

La causa raíz es un desajuste en el orden de almacenamiento dentro del bucle de división sintética. Los cuatro codificadores de HotPDF construyen el polinomio generador con los coeficientes de menor a mayor, así que Gen[0] contiene el término constante y Gen[High(Gen)] el coeficiente principal mónico. El bucle de división recorría Gen[J] hacia adelante mientras avanzaba por el mensaje, lo que aritméticamente equivale a dividir por el polinomio invertido. Hubo una segunda consecuencia que ocultó a la primera: como el coeficiente principal nunca llegaba a la posición I, Work[I] nunca se limpiaba, así que la división en realidad nunca reducía nada. El bucle igual terminaba y llenaba la cola con un arreglo de exactamente el largo correcto

// THPDFQRCode.ComputeEC en HPDFQRCode.pas
Gen := GeneratorPoly(ECCount);            // Gen[0] es el término constante
SetLength(Work, Length(Data) + ECCount);
for I := 0 to High(Data) do
  Work[I] := Data[I];
for I := Length(Data) to High(Work) do
  Work[I] := 0;
for I := 0 to High(Data) do
begin
  Factor := Work[I];
  if Factor = 0 then
    Continue;
  // Gen[High(Gen)] es el 1 principal que limpia Work[I]; recorrer Gen
  // hacia adelante divide por el polinomio invertido
  for J := 0 to High(Gen) do
    Work[I + J] := Work[I + J] xor GFMul(Gen[High(Gen) - J], Factor);
end;

La corrección es la única expresión de índice Gen[High(Gen) - J]. Con ella, THPDFQRCode.ComputeEC reproduce el ejemplo resuelto de ISO/IEC 18004 §7.5: el bloque en modo byte 1-M 32 91 11 120 209 114 220 77 67 64 236 17 236 17 236 17 produce las diez palabras de comprobación 196 35 39 119 235 215 231 226 93 23. Es una sola aserción, y habría fallado el primer día

¿Por qué el símbolo Aztec también perdía su carga útil?

Aztec arrastraba una versión más pesada del mismo bug porque TAztecGF.Encode hace la división in-place. La rutina recibe Words con el mensaje seguido de los espacios de palabras de comprobación en cero, y quien la llama vuelca ese arreglo completo en el símbolo. La división polinómica destruye el dividendo mientras lo reduce, así que cuando el bucle se corrigió para que de verdad redujera, las palabras del mensaje se sobrescribieron en el camino. Tanto la carga útil como el mensaje de modo salieron corruptos, un fallo que la versión rota había evitado por accidente al no reducir nunca nada

// TAztecGF.Encode en HPDFAztec.pas
SetLength(Message, DataCount);
for I := 0 to DataCount - 1 do
  Message[I] := Words[I];
for I := 0 to DataCount - 1 do
begin
  Factor := Words[I];
  if Factor = 0 then
    Continue;
  for J := 0 to ECCount do
    Words[I + J] := Words[I + J] xor Multiply(Gen[ECCount - J], Factor);
end;
// La división limpia la región del mensaje, pero quien la llama vuelca el
// arreglo completo en el símbolo, así que las palabras de datos deben volver
for I := 0 to DataCount - 1 do
  Words[I] := Message[I];

Aztec usa dos campos distintos, y el fixture de regresión ejercita ambos. En GF(64), el campo de un símbolo de seis bits construido con el polinomio primitivo $43, las palabras 12 45 3 con cinco palabras de comprobación producen 41 32 26 33 23 mientras las tres primeras quedan intactas. En GF(16), el campo del mensaje de modo con el polinomio primitivo $13, las palabras 5 9 producen 11 15 6 8. Ambos pasan por el hook HPDFAztecTestEncode contra ISO/IEC 24778

¿Por qué Data Matrix necesitó dos correcciones en lugar de una?

THPDFDataMatrix.ComputeEC apiló un segundo error independiente encima del compartido: construía el polinomio generador con raíces que arrancan en α^0, mientras que el anexo E de ISO/IEC 16022 especifica raíces desde α^1. Corregir solo el índice de división da las palabras de comprobación 146 107 90 179 128 para el ejemplo estándar, que se ven tan plausibles como las correctas y siguen siendo ilegibles. Tuvieron que salir los dos defectos antes de que los números cuadraran

// THPDFDataMatrix.ComputeEC en HPDFDataMatrix.pas
Gen[0] := 1;
for I := 0 to ECCount - 1 do
begin
  // DMExp[I + 1]: las raíces van de alpha^1 a alpha^ECCount, no desde alpha^0
  for J := ECCount downto 1 do
    Gen[J] := GFMul(Gen[J], DMExp[I + 1]) xor Gen[J - 1];
  Gen[0] := GFMul(Gen[0], DMExp[I + 1]);
end;

El punto de referencia es lo bastante pequeño para vivir en un comentario. La cadena '123456' se codifica en las palabras de código ASCII 142 164 186, un símbolo de 10x10 lleva cinco palabras de comprobación, y el bloque correcto es 114 25 5 88 102. HPDFDataMatrixTestComputeEC expone la función de clase detrás de la compuerta {$IFDEF HPDF_TESTING}, así que el fixture valida esos cinco valores sin instanciar un codificador ni renderizar una página. El campo de Galois en sí, construido por InitDMTables sobre el polinomio primitivo $12D en las tablas DMExp y DMLog, fue correcto todo el tiempo, que es exactamente por qué el bug se ocultó tan bien

PDF417 divide sobre un campo primo, donde los signos importan

PDF417 necesitó cuatro cambios en lugar de uno, porque GF(929) es un campo primo y no un campo de extensión binario: la suma no es xor, la resta no es la suma, y el signo de cada factor del generador es aritmética real y no notación. Cada factor debe ser (x - 3^i), que en código significa multiplicar por 929 - GF929Pow(3, I); el paso de reducción debe restar; las raíces van desde 3^1 según ISO/IEC 15438 §5.5; y Factor debe capturarse en una variable local antes de que corra el bucle interno, porque la pasada J = 0 escribe Work[I] y, de otro modo, el multiplicador cambiaría a mitad de camino. HPDFPDF417TestComputeEC fija el resultado corregido: las palabras de código 5 453 178 121 239 con cuatro palabras de corrección de errores dan 452 327 657 619

// THPDFPDF417.ComputeEC en HPDFPDF417.pas
for I := 1 to ECCount do
begin
  Root := (929 - GF929Pow(3, I)) mod 929;   // el factor es (x - 3^i)
  for J := ECCount downto 1 do
    Gen[J] := (GF929Mul(Gen[J], Root) + Gen[J - 1]) mod 929;
  Gen[0] := GF929Mul(Gen[0], Root);
end;
// ...
Factor := Work[I];                          // latch: J = 0 reescribe Work[I]
if Factor = 0 then
  Continue;
for J := 0 to ECCount do
  Work[I + J] := (Work[I + J] + 929 - GF929Mul(Gen[ECCount - J], Factor)) mod 929;

El patrón de localización de Data Matrix se instaló al revés

Las palabras de comprobación correctas no salvan un símbolo cuyo patrón de localización está espejado, y esa misma versión tuvo que corregir también eso. El código de colocación dibujaba una columna izquierda sólida, una columna derecha sólida y módulos alternados a lo largo de las filas superior e inferior, mientras que ISO/IEC 16022 §5.2 pide una columna izquierda sólida más una fila inferior sólida, el patrón de localización en forma de L, con la pista de reloj alternada corriendo por la fila superior y la columna derecha. Lo que hace fácil invertirlo es la convención de coordenadas: HotPDF renderiza las filas de módulos en Y + I * ModuleSize, que es semántica de origen arriba a la izquierda, así que Modules[Size - 1, *] es la fila inferior del símbolo impreso. Cualquiera que razone en el espacio de usuario de PDF, donde Y crece hacia arriba, pone la pierna sólida en el lado equivocado y no ve nada sospechoso en pantalla

¿Por qué cuatro codificadores rotos pasaron las pruebas durante años?

Porque las pruebas afirmaban estructura y los defectos estaban en la aritmética. Los casos existentes de QR, Data Matrix y Aztec verificaban los módulos del patrón de localización, los patrones de sincronización y las dimensiones del símbolo, todo lo cual era genuinamente correcto; ninguna prueba había comparado jamás una palabra de comprobación contra un vector publicado. La segunda razón generaliza más lejos. HotPDF trae un decodificador QR integrado, y usarlo para validar el codificador parece un round trip obvio, salvo que ese decodificador lee las palabras de código de datos y no hace ninguna corrección Reed-Solomon, así que leía exactamente lo que el codificador escribía e informaba éxito. Cuando un codificador y un decodificador comparten un supuesto, una prueba de round trip demuestra que coinciden, no que alguno tenga razón. Un código de corrección de errores tiene que validarse contra vectores impresos en la norma, nunca contra tu propio decodificador. El fixture THPDFBarcodeECCTests ahora tiene una prueba por formato, cada una nombrada por lo que fija, y cada una llega a la aritmética a través de un hook compilado solo bajo {$IFDEF HPDF_TESTING}:

• QRCheckWordsMatchISO18004Example afirma las diez palabras de comprobación del ejemplo en modo byte 1-M
• DataMatrixCheckWordsMatchISO16022Example afirma 114 25 5 88 102 para las palabras de código 142 164 186
• PDF417CheckWordsMatchGF929Reference afirma 452 327 657 619 sobre GF(929) con raíces de 3^1 a 3^4
• AztecCheckWordsKeepMessageAndMatchReference afirma las palabras de comprobación y que las palabras del mensaje sobreviven a la división in-place

Cuatro preguntas atrapan a la mayor parte de esta familia en cualquier codificador que mantengas. ¿Tu orden de almacenamiento del generador coincide con tu orden de índices de división, y puedes señalar la línea que lo demuestra? ¿Las raíces arrancan donde dice la norma, α^1 para Data Matrix y 3^1 para PDF417? ¿Una división in-place restaura la región del mensaje después? ¿Al menos una prueba compara palabras de comprobación, y no conteos de módulos, contra un número impreso en una especificación? El alcance también importa cuando decides qué hacer con los artefactos existentes. Los símbolos generados antes de v2.748.0 se renderizan y a menudo se escanean en condiciones ideales, porque una imagen limpia no necesita corrección para leerse; lo que perdieron es la tolerancia al daño que es toda la razón para elegir estos formatos. Las etiquetas de larga vida y los documentos archivados con símbolos afectados valen más regenerados que revisados a ojo con la cámara del teléfono. Los codificadores viven en el soporte de códigos de barras en HotPDF, junto al camino de decodificación QR y su manejo de orientación y la capa de salida de reportes que coloca los símbolos en una página; la referencia completa de la API de códigos de barras viene con el HotPDF Delphi Component para Delphi y C++Builder