มีตัวเลือกมากมายสำหรับการคำนวณเช็คซัม CRC บนอินเทอร์เน็ต แต่เช็คซัมคืออะไรและทำไมจึงคำนวณด้วยวิธีนี้? ลองคิดออก
คำแนะนำ
ขั้นตอนที่ 1
ก่อนอื่น มาทำความเข้าใจทฤษฎีกันสักหน่อย แล้ว CRC คืออะไรกันแน่? กล่าวโดยสรุป นี่เป็นหนึ่งในความหลากหลายของการคำนวณเช็คซัม Checksum เป็นวิธีตรวจสอบความสมบูรณ์ของข้อมูลที่ได้รับจากฝั่งผู้รับเมื่อส่งผ่านช่องทางการสื่อสาร ตัวอย่างเช่น การตรวจสอบที่ง่ายที่สุดวิธีหนึ่งคือการใช้พาริตีบิต นี่คือเมื่อบิตทั้งหมดของข้อความที่ส่งถูกสรุป และถ้าผลรวมกลายเป็นคู่ ดังนั้น 0 จะถูกเพิ่มที่ส่วนท้ายของข้อความ หากเป็นเลขคี่ ให้เท่ากับ 1 เมื่อได้รับ ผลรวมของ บิตข้อความยังถูกนับและเปรียบเทียบกับบิตพาริตีที่ได้รับ หากต่างกัน แสดงว่าเกิดข้อผิดพลาดระหว่างการส่งและข้อมูลที่ส่งผิดเพี้ยน
แต่วิธีการตรวจหาข้อผิดพลาดนี้ไม่มีข้อมูลและไม่ได้ผลเสมอไปเพราะ หากข้อความบางส่วนบิดเบี้ยว ความเท่าเทียมกันของผลรวมอาจไม่เปลี่ยนแปลง ดังนั้นจึงมีการตรวจสอบ "ขั้นสูง" อีกมากมาย รวมทั้ง CRC
อันที่จริง CRC ไม่ใช่ผลรวม แต่เป็นผลมาจากการหารข้อมูลจำนวนหนึ่ง (ข้อความข้อมูล) ด้วยค่าคงที่ หรือมากกว่านั้น ส่วนที่เหลือของการหารข้อความด้วยค่าคงที่ อย่างไรก็ตาม CRC ยังถูกเรียกว่า "checksum" ในอดีตอีกด้วย แต่ละบิตของข้อความมีส่วนสนับสนุนค่า CRC นั่นคือ ถ้าอย่างน้อยหนึ่งบิตของข้อความต้นฉบับเปลี่ยนแปลงในระหว่างการส่ง เช็คซัมก็จะเปลี่ยนไปเช่นกัน นี่เป็นข้อดีอย่างมากของการตรวจสอบ เนื่องจากช่วยให้คุณสามารถระบุได้อย่างชัดเจนว่าข้อความต้นฉบับถูกบิดเบือนในระหว่างการส่งหรือไม่
ขั้นตอนที่ 2
ก่อนที่เราจะเริ่มคำนวณ CRC จำเป็นต้องมีทฤษฎีเพิ่มเติมเล็กน้อย
ข้อความต้นฉบับคืออะไรควรมีความชัดเจน เป็นลำดับต่อเนื่องกันของบิตที่มีความยาวตามอำเภอใจ
อะไรคือค่าคงที่ที่เราควรแบ่งข้อความต้นฉบับ? ตัวเลขนี้มีความยาวเท่าใดก็ได้ แต่โดยปกติแล้วจะใช้ทวีคูณของ 1 ไบต์ - 8, 16 และ 32 บิต นับง่ายกว่าเพราะคอมพิวเตอร์ทำงานกับไบต์ไม่ใช่บิต
ค่าคงที่ตัวหารมักจะเขียนเป็นพหุนาม (พหุนาม) ดังนี้: x ^ 8 + x ^ 2 + x ^ 1 + x ^ 0 ในที่นี้ ระดับของตัวเลข "x" หมายถึงตำแหน่งของหนึ่งบิตในตัวเลข โดยเริ่มจากศูนย์ และบิตที่สำคัญที่สุดระบุระดับของพหุนามและจะถูกละทิ้งเมื่อตีความตัวเลข นั่นคือ จำนวนที่เขียนไว้ก่อนหน้านี้ไม่มีอะไรมากไปกว่า (1) 000000111 ในเลขฐานสองหรือ 7 ในหน่วยทศนิยม ในวงเล็บ ฉันระบุตัวเลขที่มีนัยสำคัญที่สุดโดยนัยของตัวเลข
นี่เป็นอีกตัวอย่างหนึ่ง: x ^ 16 + x ^ 15 + x ^ 2 + x ^ 0 = (1) 1000000000000101 = 0x8005 = 32773
โดยปกติพหุนามมาตรฐานบางตัวจะใช้สำหรับ CRC ประเภทต่างๆ
ขั้นตอนที่ 3
คุณจะคำนวณเช็คซัมอย่างไร? มีวิธีการพื้นฐาน - การแบ่งข้อความออกเป็นพหุนาม "แบบตรง" - และการปรับเปลี่ยนเพื่อลดจำนวนการคำนวณและด้วยเหตุนี้จึงทำให้การคำนวณ CRC เร็วขึ้น เราจะดูวิธีการพื้นฐาน
โดยทั่วไป การหารจำนวนด้วยพหุนามจะดำเนินการตามอัลกอริธึมต่อไปนี้:
1) สร้างอาร์เรย์ (รีจิสเตอร์) เติมด้วยศูนย์เท่ากับความยาวเท่ากับความกว้างของพหุนาม
2) ข้อความต้นฉบับถูกเสริมด้วยศูนย์ในบิตที่มีนัยสำคัญน้อยที่สุด ในจำนวนที่เท่ากับจำนวนบิตของพหุนาม
3) บิตที่สำคัญที่สุดของข้อความถูกป้อนลงในบิตที่มีความสำคัญน้อยที่สุดของรีจิสเตอร์และหนึ่งบิตจะถูกย้ายจากบิตที่สำคัญที่สุดของรีจิสเตอร์
4) ถ้าบิตขยายเท่ากับ "1" บิตจะกลับด้าน (การดำเนินการ XOR, OR แบบเอกสิทธิ์เฉพาะบุคคล) ในบิตรีจิสเตอร์ที่สอดคล้องกับบิตในพหุนาม
5) หากยังมีบิตอยู่ในข้อความ ให้ไปที่ขั้นตอนที่ 3);
6) เมื่อบิตของข้อความทั้งหมดเข้าสู่รีจิสเตอร์และประมวลผลโดยอัลกอริธึมนี้ ส่วนที่เหลือของการหารจะยังคงอยู่ในรีจิสเตอร์ ซึ่งก็คือการตรวจสอบ CRC
รูปแสดงการแบ่งลำดับบิตดั้งเดิมด้วยตัวเลข (1) 000000111 หรือพหุนาม x ^ 8 + x ^ 2 + x ^ 1 + x ^ 0
ขั้นตอนที่ 4
เหลืออีกสองสามสัมผัส ตามที่คุณอาจสังเกตเห็น ข้อความสามารถแบ่งได้ด้วยตัวเลขใดๆ วิธีการเลือกมัน? มีพหุนามมาตรฐานจำนวนหนึ่งที่ใช้คำนวณ CRC ตัวอย่างเช่น สำหรับ CRC32 อาจเป็น 0x04C11DB7 และสำหรับ CRC16 อาจเป็น 0x8005
นอกจากนี้ในการลงทะเบียนที่จุดเริ่มต้นของการคำนวณคุณสามารถเขียนได้ไม่ใช่ศูนย์ แต่เป็นตัวเลขอื่น
นอกจากนี้ ในระหว่างการคำนวณ ทันทีก่อนที่จะออกผลรวมการตรวจสอบ CRC สุดท้าย พวกเขาสามารถหารด้วยตัวเลขอื่นได้
และสิ่งสุดท้าย ไบต์ของข้อความเมื่อเขียนไปยังรีจิสเตอร์สามารถวางเป็นบิตที่สำคัญที่สุด "ส่งต่อ" และในทางกลับกัน บิตที่มีนัยสำคัญน้อยที่สุด
ขั้นตอนที่ 5
จากทั้งหมดข้างต้น เรามาเขียนฟังก์ชัน Basic. NET ที่คำนวณเช็คซัม CRC โดยใช้พารามิเตอร์จำนวนหนึ่งที่ฉันอธิบายไว้ข้างต้นและส่งคืนค่า CRC เป็นตัวเลขที่ไม่มีเครื่องหมาย 32 บิต
ฟังก์ชั่นที่ใช้ร่วมกันสาธารณะ GetCrc (ByVal ไบต์เป็นไบต์ (), ByVal poly As UInteger, ความกว้าง ByVal ที่เป็นตัวเลือก As Integer = 32, ByVal initReg ทางเลือก As UInteger = & HFFFFFFFFUI, ByVal ที่เป็นตัวเลือก FinalXor As UInteger = & HFFFFFFFFUI, ByVal ที่เป็นตัวเลือก Boo reverseBytes, ByVal ที่เป็นตัวเลือก reverseCrc As Boolean = True) เป็น UInteger
หรี่ widthInBytes As Integer = width / 8
'เสริมความกว้างของข้อความด้วยศูนย์ (การคำนวณเป็นไบต์):
ReDim Preserve ไบต์ (bytes. Length - 1 + widthInBytes)
'สร้างคิวบิตจากข้อความ:
Dim msgFifo เป็นคิวใหม่ (ของบูลีน) (bytes. Count * 8 - 1)
สำหรับแต่ละ b As Byte In bytes
Dim ba เป็น BitArray ใหม่ ({b})
ถ้า reverseBytes แล้ว
สำหรับ i As Integer = 0 ถึง 7
msgFifo. Enqueue (ba (i))
ถัดไป
อื่น
สำหรับ i As Integer = 7 ถึง 0 ขั้นตอน -1
msgFifo. Enqueue (ba (i))
ถัดไป
จบถ้า
ถัดไป
'สร้างคิวจากบิตเติมเริ่มต้นของการลงทะเบียน:
Dim initBytes เป็น Byte () = BitConverter. GetBytes (initReg)
Dim initBytesReversed As IEnumerable (ของ Byte) = (จาก b As Byte ใน initBytes ใช้ widthInBytes). Reverse
Dim initFifo เป็นคิวใหม่ (ของบูลีน) (ความกว้าง - 1)
สำหรับแต่ละ b เป็นไบต์ใน initBytesReversed
Dim ba เป็น BitArray ใหม่ ({b})
หากไม่ย้อนกลับ Bytes แล้ว
สำหรับ i As Integer = 0 ถึง 7
initFifo. Enqueue (ba (i))
ถัดไป
อื่น
สำหรับ i As Integer = 7 ถึง 0 ขั้นตอน -1
initFifo. Enqueue (ba (i))
ถัดไป
จบถ้า
ถัดไป
'Shift และ XOR:
Dim register As UInteger = 0 'เติม width-bit register ด้วยศูนย์
ทำในขณะที่ msgFifo. Count> 0
Dim poppedBit As Integer = CInt (register >> (width - 1)) และ 1 'define before shift register
Dim shiftedBit As Byte = Convert. ToByte (msgFifo. Dequeue)
ถ้า initFifo. Count> 0 แล้ว
Dim b As Byte = Convert. ToByte (initFifo. Dequeue)
shiftedBit = shiftedBit Xor b
จบถ้า
ลงทะเบียน = ลงทะเบียน << 1
register = register หรือ shiftedBit
ถ้า poppedBit = 1 แล้ว
register = register Xor poly
จบถ้า
ห่วง
'การแปลงครั้งสุดท้าย:
Dim crc As UInteger = register 'การลงทะเบียนมีส่วนที่เหลือของแผนก == checksum
ถ้า reverseCrc แล้ว
crc = สะท้อน (crc, ความกว้าง)
จบถ้า
crc = crc Xor สุดท้ายXor
crc = crc And (& HFFFFFFFFUI >> (32 - width)) 'ปิดบังบิตที่มีนัยสำคัญน้อยที่สุด
ส่งคืน crc
ฟังก์ชั่นสิ้นสุด
