A Reed-Solomon encoder that stores its generator polynomial constant term first and then divides leading term first is not computing error correction at all. HotPDF shipped exactly that in four 2D barcode encoders, QR, Data Matrix, PDF417 and Aztec, and every symbol they produced carried a check block that no conforming scanner could use
The interesting part is not the arithmetic slip. It is the propagation. One encoder was written first, its division loop was copied into the next three, and each new format inherited a defect that had never been validated against a single published test vector. Symbols still rendered, finder patterns sat in the right place, sizes were correct. Only the bytes that let a 2D barcode survive a smudge were garbage
One reversed polynomial, copied into four encoders
The root cause is a storage-order mismatch inside the synthetic division loop. All four HotPDF encoders build the generator polynomial with coefficients low to high, so Gen[0] holds the constant term and Gen[High(Gen)] holds the monic leading coefficient. The division loop indexed Gen[J] forwards while walking the message, which is arithmetically identical to dividing by the reversed polynomial. There was a second consequence that hid the first: because the leading coefficient never landed at position I, Work[I] was never cleared, so the division never actually reduced anything. The loop still terminated and still filled the tail with an array of exactly the right length
// THPDFQRCode.ComputeEC in HPDFQRCode.pas
Gen := GeneratorPoly(ECCount); // Gen[0] is the constant term
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)] is the leading 1 that clears Work[I]; walking Gen
// forwards divides by the reversed polynomial instead
for J := 0 to High(Gen) do
Work[I + J] := Work[I + J] xor GFMul(Gen[High(Gen) - J], Factor);
end;The fix is the single index expression Gen[High(Gen) - J]. After it, THPDFQRCode.ComputeEC reproduces the ISO/IEC 18004 §7.5 worked example: the version 1-M byte-mode block 32 91 11 120 209 114 220 77 67 64 236 17 236 17 236 17 yields the ten check words 196 35 39 119 235 215 231 226 93 23. That is one assertion, and it would have failed on day one
Why did the Aztec symbol lose its payload as well?
Aztec carried a heavier version of the same bug because TAztecGF.Encode divides in place. The routine receives Words holding the message followed by zeroed check-word slots, and the caller emits that entire array into the symbol. Polynomial division destroys the dividend as it reduces it, so once the loop was fixed to actually reduce, the message words were overwritten along the way. Payload and mode message both came out corrupted, a failure the broken version had accidentally avoided by never reducing anything
// TAztecGF.Encode in 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;
// The division clears the message region, but the caller emits the whole
// array into the symbol, so the data words have to come back
for I := 0 to DataCount - 1 do
Words[I] := Message[I];Aztec uses two different fields, and the regression fixture exercises both. In GF(64), the field of a six-bit symbol built from primitive polynomial $43, the words 12 45 3 with five check words produce 41 32 26 33 23 while the leading three stay untouched. In GF(16), the field of the mode message with primitive polynomial $13, the words 5 9 produce 11 15 6 8. Both run through the HPDFAztecTestEncode hook against ISO/IEC 24778
What makes Data Matrix need two fixes instead of one?
THPDFDataMatrix.ComputeEC stacked a second, independent error on top of the shared one: it built the generator polynomial with roots starting at α^0, while ISO/IEC 16022 Annex E specifies roots from α^1. Fixing only the division index gives the check words 146 107 90 179 128 for the standard example, which look every bit as plausible as the correct ones and are still unreadable. Both defects had to go before the numbers matched
// THPDFDataMatrix.ComputeEC in HPDFDataMatrix.pas
Gen[0] := 1;
for I := 0 to ECCount - 1 do
begin
// DMExp[I + 1]: the roots run alpha^1..alpha^ECCount, not from 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;The reference point is small enough to keep in a comment. The string '123456' encodes to the ASCII code words 142 164 186, a 10x10 symbol carries five check words, and the correct block is 114 25 5 88 102. HPDFDataMatrixTestComputeEC exposes the class function behind the {$IFDEF HPDF_TESTING} gate, so the fixture asserts those five values without instantiating an encoder or rendering a page. The Galois field itself, built by InitDMTables over primitive polynomial $12D into the DMExp and DMLog tables, was correct the whole time, which is exactly why the bug hid so well
PDF417 divides over a prime field, where signs matter
PDF417 needed four changes rather than one, because GF(929) is a prime field and not a binary extension field: addition is not xor, subtraction is not addition, and the sign of each generator factor is real arithmetic rather than notation. Each factor must be (x - 3^i), which in code means multiplying by 929 - GF929Pow(3, I); the reduction step must subtract; the roots run from 3^1 per ISO/IEC 15438 §5.5; and Factor must be latched into a local before the inner loop runs, because the J = 0 pass writes Work[I] and would otherwise change the multiplier underneath itself. HPDFPDF417TestComputeEC pins the corrected result: the code words 5 453 178 121 239 with four error correction words give 452 327 657 619
// THPDFPDF417.ComputeEC in HPDFPDF417.pas
for I := 1 to ECCount do
begin
Root := (929 - GF929Pow(3, I)) mod 929; // the factor is (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 rewrites 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;The Data Matrix finder was installed inside out
Correct check words do not save a symbol whose finder pattern is mirrored, and the same release had to fix that too. The placement code drew a solid left column, a solid right column, and alternating modules along the top and bottom rows, while ISO/IEC 16022 §5.2 asks for a solid left column plus a solid bottom row, the L-shaped finder, with the alternating clock track running along the top row and the right column. What makes this easy to get backwards is the coordinate convention: HotPDF renders module rows at Y + I * ModuleSize, which is top-left origin semantics, so Modules[Size - 1, *] is the bottom row of the printed symbol. Anyone reasoning in PDF user space, where Y grows upward, puts the solid leg on the wrong side and sees nothing suspicious on screen
Why did four broken encoders pass the tests for years?
Because the tests asserted structure and the defects were in arithmetic. The existing QR, Data Matrix and Aztec cases checked finder modules, timing patterns and symbol dimensions, all of which were genuinely correct; no test had ever compared a check word against a published vector. The second reason generalizes further. HotPDF ships a built-in QR decoder, and using it to validate the encoder feels like an obvious round trip, except that this decoder reads data code words and performs no Reed-Solomon correction, so it read back exactly what the encoder wrote and reported success. When an encoder and a decoder share an assumption, a round-trip test proves that they agree, not that either is right. An error correcting code has to be validated against vectors printed in the standard, never against your own decoder. The fixture THPDFBarcodeECCTests now holds one test per format, each named for what it pins down, and each reaching the arithmetic through a hook compiled only under {$IFDEF HPDF_TESTING}:
QRCheckWordsMatchISO18004Exampleasserts the ten check words of the version 1-M byte-mode exampleDataMatrixCheckWordsMatchISO16022Exampleasserts 114 25 5 88 102 for the code words 142 164 186PDF417CheckWordsMatchGF929Referenceasserts 452 327 657 619 over GF(929) with roots 3^1 to 3^4AztecCheckWordsKeepMessageAndMatchReferenceasserts the check words and that the message words survive the in-place division
Four questions catch most of this family in any encoder you maintain. Does your generator storage order match your division index order, and can you point at the line that proves it? Do the roots start where the standard says, α^1 for Data Matrix and 3^1 for PDF417? Does an in-place division restore the message region afterward? Does at least one test compare check words, rather than module counts, against a number printed in a specification? Scope matters too when you decide what to do about existing artifacts. Symbols generated before v2.748.0 render and often scan under ideal conditions, because a clean image needs no correction to be read; what they lost is the damage tolerance that is the whole reason to choose these formats. Long-lived labels and archived documents carrying affected symbols are worth regenerating rather than spot-checking with a phone camera. The encoders live in the barcode support in HotPDF, alongside the QR decoding path and its orientation handling and the report output layer that places symbols on a page; the full barcode API reference ships with the HotPDF Delphi Component for Delphi and C++Builder