أخطاء Reed-Solomon في أربعة مشفّرات باركود لـ Delphi

مشفّر Reed-Solomon يخزّن الحد الثابت لمتعددة الحدود المولّدة أولاً ثم يقسم بدءاً من الحد الرائد، لا يحسب تصحيح الأخطاء إطلاقاً. وهذا بالضبط ما خرج به HotPDF في أربعة مشفّرات باركود ثنائية الأبعاد: QR وData Matrix وPDF417 وAztec، وكل رمز أنتجوه حمل كتلة تحقق لا يستطيع أي ماسح ضوئي مطابق للمواصفة استخدامها

الجزء المثير للاهتمام ليس الزلّة الحسابية، بل انتشارها. كُتب مشفّر واحد أولاً، ثم نُسخت حلقة القسمة منه إلى المشفّرات الثلاثة التالية، وورث كل صيغة جديدة عيباً لم يُتحقق منه مقابل متجه اختبار منشور واحد. الرموز كانت تُرسم، ونمط التحديد يجلس في مكانه الصحيح، والأبعاد صحيحة. الوحيد الذي كان هراءً هو البايتات التي تسمح للباركود ثنائي الأبعاد بالنجاة من التلطيخ

متعددة حدود معكوسة واحدة، نُسخت إلى أربعة مشفّرات

السبب الجذري هو عدم تطابق ترتيب التخزين داخل حلقة القسمة التركيبية. كل مشفّرات HotPDF الأربعة تبني متعددة الحدود المولّدة بمعاملات من الأقل إلى الأعلى، لذا يحمل Gen[0] الحد الثابت ويحمل Gen[High(Gen)] المعامل الرائد الأحادي. حلقة القسمة كانت تفهرس Gen[J] إلى الأمام أثناء السير في الرسالة، وهو مطابق حسابياً للقسمة على متعددة الحدود المعكوسة. وكانت هناك نتيجة ثانية أخفت الأولى: لأن المعامل الرائد لم يصل قط إلى الموضع I، لم يُمسح Work[I] أبداً، فلم تكن القسمة في الواقع تختزل شيئاً. ومع ذلك كانت الحلقة تنتهي، وتملأ الذيل بمصفوفة بالطول الصحيح تماماً

// THPDFQRCode.ComputeEC في HPDFQRCode.pas
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)] هو المعامل القائد 1 الذي يمسح Work[I]؛ والمرور عبر 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 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 يقسم في المكان نفسه. الروتين يستقبل Words التي تحمل الرسالة متبوعة بخانات كلمات تحقق مصفّرة، والمستدعي يبث المصفوفة كاملة إلى الرمز. قسمة متعددات الحدود تدمر المقسوم وهي تختزله، لذا ما إن أُصلحت الحلقة لتبدأ الاختزال الفعلي حتى استُبدلت كلمات الرسالة في الطريق. خرجت الحمولة ورسالة الوضع معاً تالفتين، وهو فشل كانت النسخة المعطوبة تتجنبه صدفة لأنها لم تكن تختزل شيئاً

// TAztecGF.Encode في 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;
// القسمة تمسح منطقة الرسالة، لكن المُستدعي يُخرج المصفوفة
// كاملة إلى الرمز، لذا يجب أن تعود كلمات البيانات
for I := 0 to DataCount - 1 do
  Words[I] := Message[I];

يستخدم Aztec حقلين مختلفين، واختبار الانحدار يمرّن الاثنين معاً. في GF(64)، حقل رمز ستة بتات المبني من متعددة الحدود الأولية $43، الكلمات 12 45 3 مع خمس كلمات تحقق تعطي 41 32 26 33 23 بينما تبقى الكلمات الثلاث الأولى كما هي. وفي GF(16)، حقل رسالة الوضع مع متعددة الحدود الأولية $13، الكلمات 5 9 تعطي 11 15 6 8. كلاهما يمر عبر خطاف HPDFAztecTestEncode مقابل ISO/IEC 24778

لماذا احتاج Data Matrix إصلاحين بدلاً من واحد؟

رصّ THPDFDataMatrix.ComputeEC خطأً ثانياً مستقلاً فوق الخطأ المشترك: بنى متعددة الحدود المولّدة بجذور تبدأ من α^0، بينما تنص ISO/IEC 16022 الملحق E على جذور من α^1. إصلاح فهرس القسمة وحده يعطي كلمات التحقق 146 107 90 179 128 للمثال القياسي، وهي تبدو مقنعة تماماً مثل الصحيحة وما زالت غير قابلة للقراءة. كان على العيبين معاً أن يختفيا قبل أن تتطابق الأرقام

// THPDFDataMatrix.ComputeEC في HPDFDataMatrix.pas
Gen[0] := 1;
for I := 0 to ECCount - 1 do
begin
  // DMExp[I + 1]: الجذور تمتد عبر alpha^1..alpha^ECCount، وليس من 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;

نقطة المرجع صغيرة بما يكفي لتوضع في تعليق. السلسلة '123456' تُرمَّز إلى كلمات ASCII 142 164 186، ورمز 10x10 يحمل خمس كلمات تحقق، والكتلة الصحيحة هي 114 25 5 88 102. يكشف HPDFDataMatrixTestComputeEC دالة الصنف خلف بوابة {$IFDEF HPDF_TESTING}، لذا يؤكد الاختبار تلك القيم الخمس دون إنشاء مشفّر أو رسم صفحة. حقل Galois نفسه، المبني بواسطة InitDMTables فوق متعددة الحدود الأولية $12D داخل جدولي DMExp وDMLog، كان صحيحاً طوال الوقت، وهذا بالضبط سبب نجاح العيب في الاختباء بهذا الشكل

PDF417 يقسم في حقل أولي حيث للإشارات معنى

احتاج PDF417 أربعة تغييرات بدلاً من واحد، لأن GF(929) حقل أولي وليس حقل امتداد ثنائياً: الجمع ليس xor، والطرح ليس جمعاً، وإشارة كل عامل من عوامل المولّدة حساب حقيقي لا مجرد اصطلاح. كل عامل يجب أن يكون (x - 3^i)، وهو ما يعني في الكود الضرب في 929 - GF929Pow(3, I)؛ وخطوة الاختزال يجب أن تطرح؛ والجذور تمتد من 3^1 وفق ISO/IEC 15438 §5.5؛ ويجب تثبيت Factor في متغير محلي قبل تشغيل الحلقة الداخلية، لأن تمريرة J = 0 تكتب Work[I] وإلا لتغيّر المضروب تحته. يثبّت HPDFPDF417TestComputeEC النتيجة المصححة: كلمات البيانات 5 453 178 121 239 مع أربع كلمات تصحيح خطأ تعطي 452 327 657 619

// THPDFPDF417.ComputeEC في HPDFPDF417.pas
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];                          // 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;

نُصّب نمط التحديد في Data Matrix معكوساً من الداخل

كلمات التحقق الصحيحة لا تنقذ رمزاً انعكس نمط التحديد فيه، وكان على الإصدار نفسه إصلاح هذا أيضاً. كود التموضع كان يرسم عموداً أيسر مصمتاً وعموداً أيمن مصمتاً وخانات متناوبة على طول الصفين العلوي والسفلي، بينما تطلب ISO/IEC 16022 §5.2 عموداً أيسر مصمتاً مع صف سفلي مصمت، أي نمط التحديد على شكل L، مع نمط التوقيت المتناوب على طول الصف العلوي والعمود الأيمن. ما يجعل انعكاس هذا سهلاً هو اصطلاح الإحداثيات: HotPDF يرسم صفوف الخانات عند Y + I * ModuleSize، وهي دلالات أصل أعلى-يسار، لذا فإن Modules[Size - 1, *] هو الصف السفلي للرمز المطبوع. أي شخص يفكر في فضاء مستخدم PDF، حيث تكبر Y نحو الأعلى، سيضع الضلع المصمت في الجانب الخطأ ولن يرى شيئاً مريباً على الشاشة

لماذا اجتازت أربعة مشفّرات معطوبة الاختبارات لسنوات؟

لأن الاختبارات كانت تؤكد البنية بينما كانت العيوب في الحساب. حالات QR وData Matrix وAztec الموجودة كانت تفحص خانات نمط التحديد وأنماط التوقيت وأبعاد الرمز، وكل ذلك كان صحيحاً فعلاً؛ لا اختبار واحد قارن كلمة تحقق بمتجه منشور. والسبب الثاني أعمق. يشحن HotPDF فك ترميز QR مدمجاً، واستخدامه للتحقق من المشفّر يبدو رحلة ذهاب وإياب بديهية، إلا أن هذا المفكك يقرأ كلمات البيانات ولا ينفذ أي تصحيح Reed-Solomon، فكان يقرأ حرفياً ما كتبه المشفّر ويعلن النجاح. حين يتشارك مشفّر ومفكك افتراضاً واحداً، فإن اختبار الذهاب والإياب يثبت أنهما متفقان، لا أن أياً منهما على صواب. رمز تصحيح الأخطاء يجب أن يُتحقق منه مقابل المتجهات المطبوعة في المواصفة، أبداً مقابل المفكك الخاص بك. يحمل الاختبار THPDFBarcodeECCTests الآن اختباراً واحداً لكل صيغة، كلٌّ باسم يدل على ما يثبته، وكلٌّ يصل إلى الحساب عبر خطاف يُترجم فقط تحت {$IFDEF HPDF_TESTING}:

• QRCheckWordsMatchISO18004Example يؤكد كلمات التحقق العشر لمثال وضع البايت version 1-M
• DataMatrixCheckWordsMatchISO16022Example يؤكد القيم 114 25 5 88 102 لكلمات البيانات 142 164 186
• PDF417CheckWordsMatchGF929Reference يؤكد القيم 452 327 657 619 فوق GF(929) بجذور من 3^1 إلى 3^4
• AztecCheckWordsKeepMessageAndMatchReference يؤكد كلمات التحقق وأن كلمات الرسالة تنجو من القسمة في المكان نفسه

أربعة أسئلة تكشف معظم هذه العائلة في أي مشفّر تصونه. هل يتطابق ترتيب تخزين المولّدة مع ترتيب فهرس القسمة، وهل تستطيع الإشارة إلى السطر الذي يثبت ذلك؟ هل تبدأ الجذور حيث تنص المواصفة، α^1 في Data Matrix و3^1 في PDF417؟ هل تعيد القسمة في المكان نفسه منطقة الرسالة بعدها؟ هل يوجد اختبار واحد على الأقل يقارن كلمات التحقق، لا عدد الخانات، برقم مطبوع في مواصفة؟ والنطاق مهم أيضاً حين تقرر ماذا تفعل بالمخرجات الموجودة. الرموز المولدة قبل v2.748.0 تُرسم وغالباً تُمسح في الظروف المثالية، لأن الصورة النظيفة لا تحتاج تصحيحاً لتُقرأ؛ وما خسرته هو تحمل الأضرار الذي هو السبب الوحيد لاختيار هذه الصيغ. الملصقات طويلة العمر والمستندات المؤرشفة التي تحمل رموزاً متأثرة تستحق إعادة توليد بدلاً من فحصها على عجل بكاميرا الهاتف. تعيش المشفّرات في دعم الباركود في HotPDF، بجانب مسار فك ترميز QR ومعالجة اتجاهاته وطبقة مخرجات التقارير التي تضع الرموز على الصفحة؛ ومرجع API الكامل للباركود يأتي مع HotPDF Delphi Component لـ Delphi وC++Builder