گزینه های زیادی برای محاسبه مجموع کنترل CRC در اینترنت وجود دارد. اما دقیقاً چک چک چیست و چرا از این طریق محاسبه می شود؟ بگذارید بفهمیم
دستورالعمل ها
مرحله 1
اول ، بیایید کمی تئوری بگیریم. بنابراین دقیقاً CRC چیست؟ به طور خلاصه ، این یکی از انواع محاسبه جمع چک است. Checksum روشی برای بررسی یکپارچگی اطلاعات دریافتی در سمت گیرنده هنگام انتقال از طریق کانالهای ارتباطی است. به عنوان مثال ، یکی از ساده ترین بررسی ها استفاده از بیت برابری است. این زمانی است که تمام بیت های پیام ارسالی جمع می شوند و اگر حاصل جمع شدن زوج باشد ، 0 به فرد اضافه می شود ، اگر فرد باشد ، سپس 1. هنگام دریافت ، مجموع بیت های پیام نیز شمارش شده و با بیت برابری دریافت شده مقایسه می شوند. در صورت اختلاف ، خطاهایی هنگام انتقال رخ داده و اطلاعات ارسالی مخدوش شده است.
اما این روش برای تشخیص وجود خطاها بسیار غیر اطلاعاتی است و همیشه جواب نمی دهد ، زیرا اگر چندین بیت پیام تحریف شده باشد ، ممکن است برابری مبلغ تغییر نکند. بنابراین ، تعداد بیشتری چک "پیشرفته" از جمله CRC وجود دارد.
در واقع CRC یک جمع نیست بلکه نتیجه تقسیم مقدار معینی از اطلاعات (پیام اطلاعاتی) بر یک ثابت یا بهتر بگوییم ، باقی مانده تقسیم پیام بر روی یک ثابت است. با این حال ، CRC در طول تاریخ به عنوان "چک چک" نیز شناخته می شود. هر بیت از پیام به مقدار CRC کمک می کند. به این معنا که اگر حداقل یک بیت از پیام اصلی در حین انتقال تغییر کند ، جمع چک نیز تغییر می کند و به طور قابل توجهی. این یک امتیاز بزرگ برای چنین چک است ، زیرا به شما اجازه می دهد بدون ابهام تعیین کنید که آیا پیام اصلی هنگام انتقال تحریف شده است یا خیر.
گام 2
قبل از شروع محاسبه CRC ، کمی تئوری بیشتر لازم است.
پیام اصلی چیست باید روشن باشد. این یک توالی پیوسته از بیت های طول دلخواه است.
ثابت ای که باید پیام اصلی را تقسیم کنیم چیست؟ این عدد نیز به هر طولی است ، اما معمولاً از ضربات 1 بایت - 8 ، 16 و 32 بیت استفاده می شود. شمارش ساده تر است ، زیرا رایانه ها با بایت کار می کنند ، نه با بیت.
ثابت مقسوم علیه معمولاً به صورت چند جمله ای (چند جمله ای) مانند این نوشته می شود: x ^ 8 + x ^ 2 + x ^ 1 + x ^ 0. در اینجا ، درجه عدد "x" به معنای موقعیت یک بیت در عدد است که از صفر شروع می شود و مهمترین بیت درجه چند جمله ای را نشان می دهد و هنگام تفسیر عدد کنار گذاشته می شود. یعنی عدد نوشته شده قبلی چیزی بیش از (1) 00000111 به صورت باینری یا 7 به صورت اعشاری نیست. در پرانتز ، معنی قابل توجه ترین رقم عدد را نشان دادم.
مثالی دیگر: x ^ 16 + x ^ 15 + x ^ 2 + x ^ 0 = (1) 100000000000000101 = 0x8005 = 32773.
معمولاً از چند جمله ای استاندارد برای انواع مختلف CRC استفاده می شود.
مرحله 3
بنابراین چگونه می توان مجمع کنترل را محاسبه کرد؟ یک روش اساسی وجود دارد - تقسیم پیام به چند جمله ای "سر به سر" - و تغییرات آن به منظور کاهش تعداد محاسبات و بر این اساس ، تسریع در محاسبه CRC. ما به روش اساسی نگاه خواهیم کرد.
به طور کلی ، تقسیم عدد توسط یک چند جمله ای طبق الگوریتم زیر انجام می شود:
1) یک آرایه (ثبت) ایجاد می شود ، پر شده با صفر ، طول برابر با طول عرض چند جمله ای ؛
2) پیام اصلی با صفر در کمترین بیت ، در مقدار برابر با تعداد بیت های چند جمله ای ، تکمیل می شود.
3) یک بیت مهم پیام به کمترین بیت ثبت وارد می شود و یک بیت از مهمترین بیت رجیستر منتقل می شود.
4) اگر بیت توسعه یافته برابر با "1" باشد ، بیت ها معکوس می شوند (عملکرد XOR ، منحصر به فرد OR) در آن بیت های ثبتی که مطابق با چند جمله ای هستند
5) اگر هنوز بیت هایی در پیام وجود دارد ، به مرحله 3 بروید) ؛
6) هنگامی که تمام بیت های پیام وارد رجیستر می شوند و توسط این الگوریتم پردازش می شوند ، باقیمانده قسمت در رجیستر باقی می ماند که همان چک چک CRC است.
شکل تقسیم توالی بیت اصلی را بر روی عدد (1) 00000111 یا چند جمله ای x ^ 8 + x ^ 2 + x ^ 1 + x ^ 0 نشان می دهد.
مرحله 4
چند لمس اضافی باقی مانده است. همانطور که ممکن است متوجه شده باشید ، پیام را می توان با هر شماره تقسیم کرد. چگونه آن را انتخاب کنیم؟ تعدادی چند جمله ای استاندارد وجود دارد که برای محاسبه CRC استفاده می شود. به عنوان مثال ، برای CRC32 ممکن است 0x04C11DB7 و برای CRC16 ممکن است 0x8005 باشد.
علاوه بر این ، در ثبت نام در ابتدای محاسبه ، می توانید صفر ، بلکه تعداد دیگری بنویسید.
همچنین ، در حین محاسبات ، بلافاصله قبل از صدور چک نهایی CRC ، می توان آنها را با تعدادی دیگر تقسیم کرد.
و آخرین چیز بایت های پیام هنگام نوشتن در ثبت می توانند به عنوان مهمترین بیت "جلو" و بالعکس ، کمترین آنها قرار بگیرند.
مرحله 5
با توجه به همه موارد بالا ، بیایید یک تابع Basic. NET بنویسیم که با گرفتن تعدادی پارامتر که در بالا توضیح دادم و بازگرداندن مقدار CRC به عنوان یک عدد بدون علامت 32 بیتی ، جمع CRC را محاسبه می کند.
عملکرد به اشتراک گذاشته شده عمومی GetCrc (ByVal Bytes As Byte ()، ByVal poly As UInteger، Optional ByVal عرض As Integer = 32، Optional ByVal InitReg As UInteger = & HFFFFFFFFUI، ByVal اختیاری finalXor As UInteger = reverseCrc As Boolean = True) به عنوان UInteger
width widthInBytes As Integer = عرض / 8
'عرض پیام را با صفر اضافه کنید (محاسبه در بایت):
ReDim حفظ بایت (بایت. طول - 1 + عرضInBytes)
'ایجاد یک صف از پیام:
Dim msgFifo به عنوان صف جدید (از نوع Boolean) (بایت. تعداد * 8 - 1)
برای هر b به عنوان بایت در بایت
Dim ba as BitArray جدید ({b})
اگر reverseBytes سپس
برای i As Integer = 0 تا 7
msgFifo. Enqueue (ba (i))
بعد
دیگری
برای i As Integer = 7 تا 0 مرحله -1
msgFifo. Enqueue (ba (i))
بعد
اگر پایان دهید
بعد
از بیت های پر کننده اولیه ثبت یک صف ایجاد کنید:
کم کردن initBytes به عنوان بایت () = BitConverter. GetBytes (initReg)
کم کردن initBytes به عنوان IEnumerable (از بایت) = (از b به عنوان بایت در initBytes Take widthInBytes). معکوس
dim initFifo as New Queue (Of Boolean) (عرض - 1)
برای هر b به عنوان بایت در initBytesReversed
Dim ba as BitArray جدید ({b})
اگر نه reverseBytes سپس
برای i As Integer = 0 تا 7
initFifo. Enqueue (ba (i))
بعد
دیگری
برای i As Integer = 7 تا 0 مرحله -1
initFifo. Enqueue (ba (i))
بعد
اگر پایان دهید
بعد
'Shift و XOR:
ثبت نام کم به عنوان UInteger = 0 'ثبت کننده عرض بیت را با صفر پر کنید.
Do while msgFifo. Count> 0 را انجام دهید
Dim poppedBit As Integer = CInt (ثبت نام >> (عرض - 1)) و 1 "قبل از ثبت شیفت تعریف کنید.
Dim shiftedBit As Byte = Convert. ToByte (msgFifo. Dequeue)
اگر initFifo. Count> 0 سپس
Dim b As Byte = Convert. ToByte (initFifo. Dequeue)
shiftedBit = shiftedBit Xor b
اگر پایان دهید
ثبت نام = ثبت نام << 1
ثبت نام = ثبت نام یا جابجایی بیت
اگر poppedBit = 1 سپس
ثبت نام = ثبت نام Xor poly
اگر پایان دهید
حلقه
'تبدیل نهایی:
Dim crc As UInteger = Register 'ثبت کننده شامل بقیه قسمت == چک چک است.
اگر reverseCrc سپس
crc = انعکاس (CRC ، عرض)
اگر پایان دهید
CRC = CRC Xor نهایی Xor
crc = crc و (و HFFFFFFFFUI >> (32 - عرض)) "بیت های کم اهمیت را می پوشانند.
بازگشت CRC
عملکرد پایان
