حشو بايتات علوية متسق

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

حشو البايتات هو عملية تحويل سلسلة من بايتات البيانات التي قد تحتوي على قيم "غير مسموح بها" أو "محجوزة" (مثل فاصل الحزم) إلى سلسلة أطول لا تحتوي على أي من هذه القيم. يُشار عادةً إلى الطول الإضافي للسلسلة المُحوّلة باسم "عبء الخوارزمية ". يُعد تأطير HDLC مثالًا معروفًا، ويُستخدم بشكل خاص في بروتوكول PPP (انظر RFC 1662 § 4.2 ). على الرغم من أن عبء تأطير HDLC أقل من 1% في المتوسط ، إلا أنه يُعاني من عبء كبير جدًا في أسوأ الحالات يصل إلى 100%؛ فبالنسبة للمدخلات التي تتكون بالكامل من بايتات تتطلب تهريبًا، سيؤدي حشو بايتات HDLC إلى مضاعفة حجم المدخلات.

من ناحية أخرى، يحدّ خوارزمية COBS بشكل دقيق من الحمل الزائد في أسوأ الحالات. تتطلب COBS حدًا أدنى من الحمل الزائد يبلغ بايتًا واحدًا، وحدًا أقصى يبلغ ⌈ n /254 ⌉ بايتًا لعدد n من بايتات البيانات (بايت واحد من كل 254 بايتًا، مُقرّبًا لأعلى). ونتيجةً لذلك، يُمكن التنبؤ بدقة عالية بزمن إرسال تسلسل البايتات المُشفّر، مما يجعل COBS مفيدةً للتطبيقات الآنية التي قد يُشكّل فيها التذبذب مشكلة. تتميز الخوارزمية بانخفاض تكلفتها الحسابية، وبالإضافة إلى حملها الزائد المرغوب في أسوأ الحالات، فإن متوسط ​​حملها الزائد منخفض أيضًا مقارنةً بخوارزميات التأطير غير المبهمة الأخرى مثل HDLC. ^{[ 1 ] [ 2 ]} مع ذلك، تتطلب COBS ما يصل إلى 254 بايتًا من التوقع المسبق . قبل إرسال البايت الأول، تحتاج إلى معرفة موضع أول بايت صفري (إن وُجد) في الـ 254 بايتًا التالية.

اقترح مشروع إنترنت صدر عام 1999 توحيد معيار COBS كبديل لتأطير HDLC في PPP ، وذلك بسبب التكلفة الإضافية السيئة المذكورة أعلاه لتأطير HDLC. ^{[ 3 ]}

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

يحوّل نظام COBS أي سلسلة بايتات في النطاق [0,255] إلى بايتات في النطاق [1,255]. بعد حذف جميع البايتات الصفرية من البيانات، يمكن استخدام بايت صفري لتمييز نهاية البيانات المُحوّلة بشكلٍ لا لبس فيه. يتم ذلك بإضافة بايت صفري إلى البيانات المُحوّلة، مُشكّلاً بذلك حزمة بيانات مُشفّرة بنظام COBS (الحمولة ) لتمييز نهاية الحزمة بشكلٍ لا لبس فيه.

(يمكن حجز أي قيمة بايت أخرى كفاصل للحزمة، ولكن استخدام الصفر يبسط الوصف.)

هناك طريقتان متكافئتان لوصف عملية ترميز COBS:

وصف الكتلة المُسبقة

لترميز بعض البايتات، أضف أولاً بايتًا صفريًا، ثم قسّمها إلى مجموعات من 254 بايتًا غير صفري، أو من 0 إلى 253 بايتًا غير صفري متبوعًا ببايت صفري. وبسبب البايت الصفري المضاف، فإن هذا ممكن دائمًا.

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

كاستثناء خاص، إذا انتهت حزمة البيانات بمجموعة من 254 بايت غير صفرية، فلا داعي لإضافة البايت الصفري الأخير. وهذا يوفر بايتًا واحدًا في بعض الحالات.

وصف القائمة المرتبطة

أولًا، أضف بايتًا صفريًا في بداية الحزمة، وبعد كل سلسلة من 254 بايتًا غير صفري. من الواضح أن هذا التشفير قابل للعكس. ليس من الضروري إضافة بايت صفري في نهاية الحزمة إذا انتهت بالضبط بـ 254 بايتًا غير صفري.

ثانيًا، استبدل كل بايت صفري بإزاحة البايت الصفري التالي، أو نهاية الحزمة. وبسبب الأصفار الإضافية المضافة في الخطوة الأولى، يُضمن ألا تتجاوز كل إزاحة 255.

توضح هذه الأمثلة كيفية ترميز تسلسلات البيانات المختلفة باستخدام خوارزمية COBS. في هذه الأمثلة، تُعبّر جميع البايتات عن قيم سداسية عشرية ، وتُعرض البيانات المُرمّزة بتنسيق نصي لتوضيح خصائصها المختلفة.

• يشير الخط الغامق إلى بايت بيانات لم يتم تغييره أثناء عملية التشفير. جميع بايتات البيانات غير الصفرية تبقى دون تغيير.
• يشير اللون الأخضر إلى بايت بيانات صفري تم تعديله أثناء عملية التشفير. تُستبدل جميع بايتات البيانات الصفرية أثناء التشفير بإزاحة إلى بايت الصفر التالي (أي واحد زائد عدد البايتات غير الصفرية التي تليه). وهو في الواقع مؤشر إلى بايت الحزمة التالي الذي يتطلب تفسيرًا: إذا كان البايت المُشار إليه غير صفري، فهو بايت رأس المجموعة التالي، وهو بايت البيانات الصفرية الذي يشير إلى البايت التالي الذي يتطلب تفسيرًا؛ أما إذا كان البايت المُشار إليه صفريًا، فهو نهاية الحزمة .
• يمثل البايت الأحمر بايتًا إضافيًا، وهو أيضًا بايت رأس المجموعة الذي يحتوي على إزاحة إلى المجموعة التالية، ولكنه لا يتطابق مع بايت البيانات. يظهر هذا البايت في موضعين: في بداية كل حزمة مشفرة، وبعد كل مجموعة من 254 بايتًا غير صفرية.
• يظهر بايت أزرق صفري في نهاية كل حزمة بيانات للإشارة إلى نهاية الحزمة لجهاز استقبال البيانات. هذا البايت الفاصل للحزمة ليس جزءًا من بروتوكول COBS نفسه؛ بل هو بايت تأطير إضافي يُضاف إلى المخرجات المشفرة.

فيما يلي رسم تخطيطي باستخدام المثال 4 من الجدول أعلاه، لتوضيح كيفية تحديد موقع كل بايت بيانات معدل، وكيفية التعرف عليه كبايت بيانات أو بايت نهاية الإطار.

 [OHB] : بايت علوي (بداية الإطار) 3+ -------------->| : يشير إلى الموقع النسبي لأول رمز صفر 2+-------->| : بايت بيانات صفري، يشير إلى رمز الصفر التالي [EOP]: موقع رمز الصفر في نهاية الحزمة. 0 1 2 3 4 5 : موضع البايت 03 11 22 02 33 00 : إطار بيانات COBS 11 22 00 33: البيانات المستخرجة OHB = بايت علوي (يشير إلى رمز الصفر التالي) EOP = نهاية الحزمة 

توضح الأمثلة من 7 إلى 10 كيف يختلف الحمل الزائد اعتمادًا على البيانات التي يتم ترميزها لأطوال الحزم التي تبلغ 255 أو أكثر.

يقوم الكود التالي بتنفيذ مشفر ومفكك COBS بلغة البرمجة C ، حيث يقوم بمعالجة البيانات بايتًا بايتًا.

#include <stddef.h> #include <stdint.h> #include <assert.h>/** ترميز البيانات باستخدام COBS إلى المخزن المؤقت  @param data مؤشر إلى بيانات الإدخال المراد ترميزها  @param length عدد البايتات المراد ترميزها  @param buffer مؤشر إلى مخزن الإخراج المرمز  @return طول المخزن المؤقت المرمز بالبايتات  @note لا يتم إخراج بايت الفاصل */ size_t cobsEncode ( const void * data , size_t length , uint8_t * buffer ) { assert ( data && buffer );uint8_t * encode = buffer ; // مؤشر البايت المُشفّر uint8_t * codep = encode ++ ; // مؤشر رمز الإخراج uint8_t code = 1 ; // قيمة الرمزfor ( const uint8_t * byte = ( const uint8_t * ) data ; length -- ; ++ byte ) { if ( * byte ) // البايت ليس صفرًا، اكتبه * encode ++ = * byte , ++ code ;إذا لم يكن * بايت أو كان الرمز يساوي 0xff ، فهذا يعني أن الإدخال صفر أو أن الكتلة قد اكتملت، لذا أعد التشغيل. { * codep = code , code = 1 , codep = encode ; إذا لم يكن * بايت أو كان الطول يساوي 0xff، فقم بزيادة قيمة encode بمقدار 1. } * codep = code ; // اكتب قيمة الرمز النهائيةreturn ( size_t )( encode - buffer ); }/** COBS فك تشفير البيانات من المخزن المؤقت  @param buffer مؤشر إلى بايتات الإدخال المشفرة  @param length عدد البايتات المراد فك تشفيرها  @param data مؤشر إلى بيانات الإخراج التي تم فك تشفيرها  @return عدد البايتات التي تم فك تشفيرها بنجاح  @note توقف فك التشفير إذا تم العثور على بايت فاصل */ size_t cobsDecode ( const uint8_t * buffer , size_t length , void * data ) { assert ( buffer && data );const uint8_t * byte = buffer ; // مؤشر بايت الإدخال المشفر uint8_t * decode = ( uint8_t * ) data ; // مؤشر بايت الإخراج غير المشفرfor ( uint8_t code = 0xff , block = 0 ; byte < buffer + length ; --block ) { if ( block ) // فك تشفير الكتلة byte * decode ++ = * byte ++ ; else { block = * byte ++ ; // جلب طول الكتلة التالية if ( block && ( code != 0xff )) // تم ترميز الصفر، اكتبه ما لم يكن فاصلًا. * decode ++ = 0 ; code = block ; if ( ! code ) // تم العثور على رمز الفاصل break ; } }return ( size_t )( decode - ( uint8_t * ) data ); }

• حشوة صغيرة
• بروتوكول الإنترنت عبر الخط التسلسلي

• تطبيق بايثون
• تنفيذ بديل بلغة C
• تطبيق آخر بلغة C
• حشو البايتات العلوي المتسق - مُخفَّض (COBS/R)
• براءة اختراع تصف مخططًا يحقق نتيجة مماثلة ولكن باستخدام طريقة مختلفة