Reed-Solomon-fejl i fire Delphi 2D-stregkode-encodere

En Reed-Solomon-encoder der gemmer sit generatorpolynomium med konstantleddet først og derefter dividerer med førende led først, beregner slet ikke fejlkorrektion. HotPDF leverede præcis det i fire 2D-stregkode-encodere — QR, Data Matrix, PDF417 og Aztec — og hvert symbol de producerede, bar en checkblok som ingen standardkonform scanner kunne bruge

Det interessante er ikke regnefejlen. Det er spredningen. Én encoder blev skrevet først, dens divisionsløkke blev kopieret ind i de næste tre, og hvert nyt format arvede en fejl der aldrig var blevet valideret mod en eneste offentliggjort testvektor. Symboler blev stadig renderet, finder-mønstre sad det rigtige sted, størrelserne var korrekte. Kun de bytes der lader en 2D-stregkode overleve en smudsplet, var skrald

Ét omvendt polynomium, kopieret ind i fire encodere

Roden er et mismatch i lageringsrækkefølgen inde i den syntetiske divisionsløkke. Alle fire HotPDF-encodere bygger generatorpolynomiet med koefficienter fra lav til høj, så Gen[0] holder konstantleddet og Gen[High(Gen)] holder den moniske førende koefficient. Divisionsløkken indekserede Gen[J] fremad mens den gik gennem beskeden, hvilket aritmetisk er det samme som at dividere med det omvendte polynomium. Der var en anden konsekvens der skjulte den første: fordi den førende koefficient aldrig landede på position I, blev Work[I] aldrig nulstillet, så divisionen reelt aldrig reducerede noget. Løkken terminatede stadig og fyldte stadig halen med et array af præcis den rigtige længde

// THPDFQRCode.ComputeEC i HPDFQRCode.pas
Gen := GeneratorPoly(ECCount);            // Gen[0] er konstantleddet
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)] er det førende 1-tal der nulstiller Work[I]; at gå Gen
  // fremad dividerer i stedet med det omvendte polynomium
  for J := 0 to High(Gen) do
    Work[I + J] := Work[I + J] xor GFMul(Gen[High(Gen) - J], Factor);
end;

Rettelsen er det ene index-udtryk Gen[High(Gen) - J]. Bagefter reproducerer THPDFQRCode.ComputeEC det gennemregnede eksempel i ISO/IEC 18004 §7.5: version 1-M byte-mode-blokken 32 91 11 120 209 114 220 77 67 64 236 17 236 17 236 17 giver de ti checkord 196 35 39 119 235 215 231 226 93 23. Det er én assertion, og den ville være fejlet på dag ét

Hvorfor mistede Aztec-symbolet også sin payload?

Aztec bar en tungere version af samme fejl, fordi TAztecGF.Encode dividerer in place. Routinen modtager Words der holder beskeden efterfulgt af nulstillede checkord-slots, og kalderen emitter det hele array ind i symbolet. Polynomiedivision ødelægger dividenden mens den reducerer den, så da løkken blev rettet til faktisk at reducere, blev besked-ordene overskrevet undervejs. Både payload og mode message kom korrupte ud — en fejl den ødelagte version ved et tilfælde havde undgået ved aldrig at reducere noget

// TAztecGF.Encode i 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;
// Divisionen nulstiller besked-området, men kalderen emitter hele
// arrayet ind i symbolet, så data-ordene skal hentes tilbage
for I := 0 to DataCount - 1 do
  Words[I] := Message[I];

Aztec bruger to forskellige felter, og regression-fixturen øver begge. I GF(64), feltet for et seks-bit-symbol bygget over det primitive polynomium $43, giver ordene 12 45 3 med fem checkord 41 32 26 33 23 mens de tre førende forbliver urørte. I GF(16), feltet for mode message med det primitive polynomium $13, giver ordene 5 9 resultatet 11 15 6 8. Begge kører gennem HPDFAztecTestEncode-hooken mod ISO/IEC 24778

Hvorfor kræver Data Matrix to rettelser i stedet for én?

THPDFDataMatrix.ComputeEC stablede en anden, uafhængig fejl oven på den fælles: den byggede generatorpolynomiet med rødder startende ved α^0, mens ISO/IEC 16022 bilag E foreskriver rødder fra α^1. At rette kun divisionsindexet giver checkordene 146 107 90 179 128 for standardeksemplet, som ser lige så plausible ud som de korrekte og stadig er ulæselige. Begge fejl skulle væk før tallene stemte

// THPDFDataMatrix.ComputeEC i HPDFDataMatrix.pas
Gen[0] := 1;
for I := 0 to ECCount - 1 do
begin
  // DMExp[I + 1]: rødderne løber alpha^1..alpha^ECCount, ikke fra 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;

Referencen er lille nok til at stå i en kommentar. Strengen '123456' koder til ASCII-codeordene 142 164 186, et 10x10-symbol bærer fem checkord, og den korrekte blok er 114 25 5 88 102. HPDFDataMatrixTestComputeEC eksponerer klassefunktionen bag {$IFDEF HPDF_TESTING}-porten, så fixturen asserter de fem værdier uden at instantiere en encoder eller rendere en side. Galois-feltet selv, bygget af InitDMTables over det primitive polynomium $12D ind i DMExp- og DMLog-tabellerne, var korrekt hele tiden — hvilket er præcis hvorfor fejlen gemte sig så godt

PDF417 dividerer over et primtalsfelt, hvor fortegn betyder noget

PDF417 krævede fire ændringer frem for én, for GF(929) er et primtalsfelt og ikke et binært udvidelsesfelt: addition er ikke xor, subtraktion er ikke addition, og tegnet på hver generatorfaktor er ægte aritmetik frem for notation. Hver faktor skal være (x - 3^i), hvilket i kode betyder at gange med 929 - GF929Pow(3, I); reduktionstrinnet skal subtrahere; rødderne løber fra 3^1 per ISO/IEC 15438 §5.5; og Factor skal låses fast i en lokal før den indre løkke kører, for J = 0-passet skriver til Work[I] og ville ellers ændre multiplikatoren under sig selv. HPDFPDF417TestComputeEC fastlåser det korrigerede resultat: codeordene 5 453 178 121 239 med fire fejlkorrektionsord giver 452 327 657 619

// THPDFPDF417.ComputeEC i HPDFPDF417.pas
for I := 1 to ECCount do
begin
  Root := (929 - GF929Pow(3, I)) mod 929;   // faktoren er (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 skriver Work[I] om
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;

Data Matrix-finderen blev installeret på vrangen

Korrekte checkord redder ikke et symbol hvis finder-mønster er spejlvendt, og samme release skulle også rette det. Placeringskoden tegnede en solid venstre kolonne, en solid højre kolonne og alternerende moduler langs top- og bund-rækkerne, mens ISO/IEC 16022 §5.2 kræver en solid venstre kolonne plus en solid bund-række — den L-formede finder — med det alternerende clock-spor langs top-rækken og højre kolonne. Det der gør det let at få bagvendt, er koordinatkonventionen: HotPDF renderer modul-rækker ved Y + I * ModuleSize, hvilket er top-left-ursprung-semantik, så Modules[Size - 1, *] er bund-rækken i det trykte symbol. Enhver der ræsonnerer i PDF-user space, hvor Y vokser opad, sætter det solide ben på den forkerte side og ser intet mistænkeligt på skærmen

Hvorfor bestod fire ødelagte encodere testene i årevis?

Fordi testene asserterede struktur, og fejlene lå i aritmetikken. De eksisterende QR-, Data Matrix- og Aztec-cases tjekkede finder-moduler, timing-mønstre og symbol-dimensioner, alt sammen ægte korrekt; ingen test havde nogensinde sammenlignet et checkord med en offentliggjort vektor. Den anden grund generaliserer videre. HotPDF leverer en indbygget QR-dekoder, og at bruge den til at validere encoderen føles som en oplagt round trip — bortset fra at denne dekoder læser data-codeord og ikke udfører nogen Reed-Solomon-korrektion, så den læste præcis det encoderen skrev tilbage og rapporterede succes. Når en encoder og en dekoder deler en antagelse, beviser en round-trip-test at de er enige — ikke at nogen af dem har ret. En fejlkorrigerende kode skal valideres mod vektorer trykt i standarden, aldrig mod din egen dekoder. Fixturen THPDFBarcodeECCTests har nu én test per format, hver opkaldt efter hvad den fastlåser, og hver når aritmetikken gennem en hook der kun kompileres under {$IFDEF HPDF_TESTING}:

• QRCheckWordsMatchISO18004Example asserter de ti checkord fra version 1-M byte-mode-eksemplet
• DataMatrixCheckWordsMatchISO16022Example asserter 114 25 5 88 102 for codeordene 142 164 186
• PDF417CheckWordsMatchGF929Reference asserter 452 327 657 619 over GF(929) med rødder 3^1 til 3^4
• AztecCheckWordsKeepMessageAndMatchReference asserter checkordene og at besked-ordene overlever in-place-divisionen

Fire spørgsmål fanger det meste af denne familie i enhver encoder du vedligeholder. Stemmer din generator-lagringsrækkefølge overens med din divisionsindex-rækkefølge, og kan du pege på linjen der beviser det? Starter rødderne der standarden siger, α^1 for Data Matrix og 3^1 for PDF417? Gendanner en in-place-division besked-området bagefter? Sammenligner mindst én test checkord — frem for modul-antal — med et tal trykt i en specifikation? Omfang betyder også noget når du beslutter hvad du skal gøre ved eksisterende artefakter. Symboler genereret før v2.748.0 renderes og scannes ofte fint under ideelle forhold, for et rent billede behøver ingen korrektion for at kunne læses; hvad de mistede, er skadestolerancen der er hele grunden til at vælge disse formater. Langlivede labels og arkiverede dokumenter med berørte symboler er værd at regenerere frem for at stikprøve med et telefonkamera. Encoderne bor i barcode-supporten i HotPDF, ved siden af QR-dekodningsstien og dens orientationshåndtering og report output-laget der placerer symboler på en side; den fulde barcode-API-reference leveres med HotPDF Delphi Component til Delphi og C++Builder