LlosLab Software Development BlogPDF, Delphi 및 문서 소프트웨어 개발자를 위한 엔지니어링 노트.

기술 문서

Delphi 2D 바코드 인코더 네 개의 Reed-Solomon 버그

HotPDF Delphi Component

생성 다항식을 상수항부터 저장하고 최고차항부터 나누는 Reed-Solomon 인코더는 애초에 오류 정정을 계산하고 있는 것이 아닙니다. HotPDF는 정확히 그렇게 만든 코드를 2D 바코드 인코더 네 개, QR, Data Matrix, PDF417, Aztec에서 출하했고, 그들이 만든 모든 심볼에는 어떤 규격 준수 스캐너도 쓸 수 없는 체크 블록이 실려 있었습니다

흥미로운 부분은 산술 실수 자체가 아닙니다. 전파입니다. 인코더 하나가 먼저 작성되었고, 그 나눗셈 루프가 나머지 셋에 복사되었으며, 각각의 새 형식은 공개된 테스트 벡터 하나로도 검증된 적 없는 결함을 물려받았습니다. 심볼은 여전히 렌더링되었고, 파인더 패턴은 제자리에 있었으며, 크기도 정확했습니다. 2D 바코드가 얼룩에서 살아남게 해주는 바이트만이 쓰레기였습니다

뒤집힌 다항식 하나, 인코더 네 개에 복사되다

근본 원인은 synthetic division 루프 안의 저장 순서 불일치입니다. HotPDF 인코더 네 개 모두 생성 다항식을 계수 낮은 것부터 높은 순으로 만듭니다. 그래서 Gen[0]은 상수항을, Gen[High(Gen)]은 monic 최고차 계수를 담습니다. 나눗셈 루프는 메시지를 훑는 동안 Gen[J]를 앞으로 인덱싱했는데, 이는 뒤집힌 다항식으로 나누는 것과 산술적으로 동일합니다. 첫 번째를 숨긴 두 번째 결과도 있었습니다. 최고차 계수가 I 위치에 닿지 않아 Work[I]가 절대 지워지지 않았고, 그래서 나눗셈은 실제로 아무것도 환원하지 못했습니다. 그래도 루프는 종료되었고 정확히 올바른 길이의 배열로 꼬리를 채웠습니다

HotPDF 바코드 인코더 네 개의 Reed-Solomon 생성 다항식 결함 다이어그램: 계수가 낮은 것부터 높은 순으로 저장되고 monic 최고차항이 마지막이며, 나눗셈 루프가 앞으로 인덱싱해 뒤집힌 다항식으로 나눠 Work가 지워지지 않았고, 수정된 Gen 인덱스가 ISO 18004 체크 워드를 재현합니다
루프는 여전히 종료되었고 꼬리도 여전히 올바른 길이였습니다. 그래서 심볼은 렌더링되는데 모든 체크 바이트는 쓸 수 없는 쓰레기로 남았습니다
// HPDFQRCode.pas의 THPDFQRCode.ComputeEC
Gen := GeneratorPoly(ECCount);            // Gen[0]은 상수항
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)]은 Work[I]를 지우는 최고차 1이며, Gen을 앞으로
  // 훑으면 뒤집힌 다항식으로 나누는 셈입니다
  for J := 0 to High(Gen) do
    Work[I + J] := Work[I + J] xor GFMul(Gen[High(Gen) - J], Factor);
end;

수정은 인덱스 식 하나, Gen[High(Gen) - J]입니다. 그 뒤로 THPDFQRCode.ComputeEC는 ISO/IEC 18004 §7.5의 작업 예제를 재현합니다. version 1-M byte-mode 블록 32 91 11 120 209 114 220 77 67 64 236 17 236 17 236 17은 체크 워드 196 35 39 119 235 215 231 226 93 23을 산출합니다. 그것이 단언 하나이며, 첫날부터 실패했을 것입니다

Aztec 심볼은 왜 페이로드까지 잃었을까요?

Aztec은 TAztecGF.Encode가 제자리에서 나누기 때문에 같은 버그의 더 무거운 버전을 지녔습니다. 루틴은 메시지 뒤에 0으로 채운 체크 워드 슬롯이 이어진 Words를 받고, 호출자는 그 배열 전체를 심볼로 내보냅니다. 다항식 나눗셈은 환원하며 피제수를 파괴하므로, 루프가 실제로 환원하도록 고쳐지자 메시지 워드는 도중에 덮어써졌습니다. 페이로드와 모드 메시지가 둘 다 손상되어 나왔는데, 고장난 버전은 아무것도 환원하지 않음으로써 그 실패를 우연히 피하고 있었습니다

HotPDF의 Aztec 제자리 나눗셈 버그 다이어그램: Words가 메시지 뒤에 0으로 채운 체크 슬롯을 담고, 다항식 나눗셈이 올바른 체크 바이트를 만들며 메시지 워드를 덮어쓰고, 호출자가 배열 전체를 내보내 페이로드가 사라지며, 수정된 TAztecGF.Encode가 환원 후 스냅샷을 복원합니다
환원 수정이 두 번째 결함을 드러냈습니다. 피제수를 파괴하는 나눗셈은 심볼 내보내기와 배열을 공유할 수 없기 때문입니다
// HPDFAztec.pas의 TAztecGF.Encode
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;
// 나눗셈이 메시지 영역을 지우지만 호출자는 배열 전체를
// 심볼로 내보내므로 데이터 워드를 되살려야 합니다
for I := 0 to DataCount - 1 do
  Words[I] := Message[I];

Aztec은 서로 다른 두 필드를 쓰며, 회귀 픽스처는 둘 모두를 시험합니다. GF(64), 즉 원시 다항식 $43으로 만든 6비트 심볼의 필드에서 워드 12 45 3은 체크 워드 다섯 개와 함께 41 32 26 33 23을 만들어내고 앞의 셋은 그대로 남습니다. GF(16), 즉 원시 다항식 $13으로 만든 모드 메시지 필드에서 워드 5 9는 11 15 6 8을 만들어냅니다. 둘 모두 ISO/IEC 24778을 상대로 HPDFAztecTestEncode 훅을 통해 실행됩니다

Data Matrix는 왜 수정이 두 개 필요할까요?

THPDFDataMatrix.ComputeEC는 공유된 그 오류 위에 두 번째 독립 오류를 얹었습니다. 생성 다항식을 α^0부터 시작하는 근으로 만든 것인데, ISO/IEC 16022 Annex E는 α^1부터의 근을 명시합니다. 나눗셈 인덱스만 고치면 표준 예제에서 체크 워드 146 107 90 179 128이 나오는데, 이는 올바른 것 못지않게 그럴듯해 보이면서도 여전히 읽을 수 없습니다. 숫자가 맞기 전에 두 결함 모두 사라져야 했습니다

// HPDFDataMatrix.pas의 THPDFDataMatrix.ComputeEC
Gen[0] := 1;
for I := 0 to ECCount - 1 do
begin
  // DMExp[I + 1]: 근은 alpha^0이 아니라 alpha^1..alpha^ECCount로 흐릅니다
  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;

기준점은 주석에 담을 만큼 작습니다. 문자열 '123456'은 ASCII 코드 워드 142 164 186으로 인코딩되고, 10x10 심볼은 체크 워드 다섯 개를 실으며, 올바른 블록은 114 25 5 88 102입니다. HPDFDataMatrixTestComputeEC는 {$IFDEF HPDF_TESTING} 게이트 뒤의 클래스 함수를 노출하므로, 픽스처는 인코더를 인스턴스화하거나 페이지를 렌더링하지 않고 그 다섯 값을 단언합니다. 원시 다항식 $12D 위에서 InitDMTables가 DMExp와 DMLog 테이블로 만든 갈루아 필드 자체는 내내 올바랐습니다. 그것이 정확히 이 버그가 그렇게 잘 숨은 이유입니다

PDF417은 부호가 중요한 소수 필드 위에서 나눕니다

PDF417은 하나가 아니라 네 가지 변경이 필요했습니다. GF(929)는 소수 필드이지 이진 확장 필드가 아니기 때문입니다. 덧셈은 xor가 아니고, 뺄셈은 덧셈이 아니며, 각 생성 인자의 부호는 표기 문제가 아니라 실제 산술입니다. 각 인자는 (x - 3^i)여야 하며, 코드로는 929 - GF929Pow(3, I)를 곱한다는 뜻입니다. 환원 단계는 빼야 하고, 근은 ISO/IEC 15438 §5.5에 따라 3^1부터 흐르며, Factor는 내부 루프가 돌기 전에 로컬에 래치되어야 합니다. J = 0 패스가 Work[I]를 쓰므로, 그러지 않으면 자기 아래의 승수를 바꿔버리기 때문입니다. HPDFPDF417TestComputeEC가 수정된 결과를 고정합니다. 코드 워드 5 453 178 121 239에 오류 정정 워드 네 개를 더하면 452 327 657 619가 나옵니다

// HPDFPDF417.pas의 THPDFPDF417.ComputeEC
for I := 1 to ECCount do
begin
  Root := (929 - GF929Pow(3, I)) mod 929;   // 인자는 (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];                          // 래치: J = 0이 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;

Data Matrix 파인더는 뒤집혀 설치되었습니다

올바른 체크 워드도 파인더 패턴이 거울상인 심볼을 구하지 못하며, 같은 릴리스에서 그쪽도 고쳐야 했습니다. 배치 코드는 왼쪽 열 전체와 오른쪽 열 전체를 채우고 위아래 행을 따라 모듈을 번갈아 그렸는데, ISO/IEC 16022 §5.2는 왼쪽 열 전체에 아래 행 전체를 더한 L자형 파인더와, 위쪽 행과 오른쪽 열을 따라 흐르는 교대 클록 트랙을 요구합니다. 이것이 뒤집기 쉬운 이유는 좌표 관례입니다. HotPDF는 모듈 행을 Y + I * ModuleSize로 렌더링하는데, 이는 왼쪽 위 원점 의미론이라 Modules[Size - 1, *]이 인쇄된 심볼의 아래 행입니다. PDF 사용자 공간에서 Y가 위로 자란다고 생각하는 사람은 채움 다리를 틀린 쪽에 두고도 화면에서 아무것도 수상해 보이지 않습니다

HotPDF의 Data Matrix 파인더 패턴과 거울상 버전을 비교하는 다이어그램: 올바른 심볼은 왼쪽 열 전체와 아래 행 전체를 지니고 위와 오른쪽을 따라 교대 클록 트랙이 흐르지만, 왼쪽 위 원점에서 Y + I 곱하기 ModuleSize로 행을 렌더링하면 어떤 스캐너도 받아들이지 않는 위쪽 채움 다리를 유혹합니다
모듈 행은 왼쪽 위 모서리에서 아래로 그려지므로 배열의 마지막 행이 인쇄된 아래 행이며, L자형 파인더는 PDF 사용자 공간의 직관과 반대로 종이에 닿습니다

고장난 인코더 네 개가 수년간 테스트를 통과한 이유

테스트가 구조를 단언했고 결함이 산술에 있었기 때문입니다. 기존의 QR, Data Matrix, Aztec 케이스는 파인더 모듈, 타이밍 패턴, 심볼 크기를 확인했는데, 그 모두는 진짜로 올바른 것이었습니다. 어떤 테스트도 체크 워드를 공개 벡터와 비교한 적이 없었습니다. 두 번째 이유는 더 일반화됩니다. HotPDF는 내장 QR 디코더를 출하하며, 그걸로 인코더를 검증하는 것은 뻔한 왕복처럼 느껴집니다. 그런데 이 디코더는 데이터 코드 워드를 읽을 뿐 Reed-Solomon 정정을 수행하지 않아서, 인코더가 쓴 것을 그대로 읽고 성공을 보고했습니다. 인코더와 디코더가 가정을 공유하면, 왕복 테스트는 둘이 일치한다는 것을 증명할 뿐 어느 쪽이 옳다는 것은 증명하지 못합니다. 오류 정정 코드는 표준에 인쇄된 벡터로 검증되어야 하며, 절대 여러분의 디코더로 검증해서는 안 됩니다. 픽스처 THPDFBarcodeECCTests는 이제 형식마다 테스트 하나를 담는데, 각각이 고정하는 것을 이름으로 삼으며, {$IFDEF HPDF_TESTING} 아래에서만 컴파일되는 훅을 통해 산술에 닿습니다:

  • QRCheckWordsMatchISO18004Example은 version 1-M byte-mode 예제의 체크 워드 열 개를 단언합니다
  • DataMatrixCheckWordsMatchISO16022Example은 코드 워드 142 164 186에 대해 114 25 5 88 102를 단언합니다
  • PDF417CheckWordsMatchGF929Reference은 근 3^1부터 3^4까지의 GF(929) 위에서 452 327 657 619를 단언합니다
  • AztecCheckWordsKeepMessageAndMatchReference은 체크 워드와, 메시지 워드가 제자리 나눗셈을 살아남는 것을 단언합니다

여러분이 유지하는 어떤 인코더든 다음 네 질문이 이 부류의 대부분을 잡아냅니다. 생성 다항식의 저장 순서가 나눗셈 인덱스 순서와 일치하며, 그걸 증명하는 줄을 짚을 수 있나요? 근이 표준이 말하는 곳에서 시작하나요, Data Matrix는 α^1, PDF417은 3^1? 제자리 나눗셈이 나중에 메시지 영역을 복원하나요? 모듈 개수가 아니라 체크 워드를 명세에 인쇄된 숫자와 비교하는 테스트가 최소한 하나 있나요? 기존 산출물을 어떻게 처리할지 정할 때 범위도 중요합니다. v2.748.0 이전에 생성된 심볼은 렌더링되고 이상적인 조건에서는 자주 스캔됩니다. 깨끗한 이미지는 읽히는 데 정정이 필요 없기 때문입니다. 그들이 잃은 것은 이 형식들을 선택하는 이유 그 자체인 손상 허용치입니다. 영향받은 심볼을 지닌 장수 라벨과 보관 문서는 폰 카메라로 무작위 확인하는 것보다 재생성이 더 맞습니다. 인코더들은 HotPDF의 바코드 지원 안에서, QR 디코딩 경로와 그 방향 처리 및 심볼을 페이지에 배치하는 리포트 출력 계층과 함께 살며, 전체 바코드 API 레퍼런스는 Delphi와 C++Builder용 HotPDF Delphi Component와 함께 출하됩니다