Có nhiều tùy chọn để tính toán tổng kiểm tra CRC trên Internet. Nhưng chính xác thì tổng kiểm tra là gì và tại sao nó lại được tính theo cách này? Hãy tìm ra nó.
Hướng dẫn
Bước 1
Đầu tiên, chúng ta hãy tìm hiểu một chút về lý thuyết. Vậy CRC chính xác là gì? Tóm lại, đây là một trong những kiểu tính toán tổng kiểm tra. Checksum là một phương pháp kiểm tra tính toàn vẹn của thông tin nhận được từ phía người nhận khi truyền qua các kênh truyền thông. Ví dụ, một trong những cách kiểm tra đơn giản nhất là sử dụng bit chẵn lẻ. Đây là khi tất cả các bit của thông điệp đã truyền được cộng lại, và nếu tổng là chẵn, thì 0 được thêm vào cuối thông báo, nếu là lẻ thì 1. Khi nhận, tổng của các bit thông báo cũng được đếm và so sánh với bit chẵn lẻ nhận được. Nếu chúng khác nhau, thì lỗi xảy ra trong quá trình truyền và thông tin được truyền bị bóp méo.
Nhưng phương pháp phát hiện sự hiện diện của lỗi này rất khó hiểu và không phải lúc nào cũng hoạt động, bởi vì nếu một số bit của thông báo bị bóp méo, tính chẵn lẻ của tổng có thể không thay đổi. Do đó, có nhiều cách kiểm tra "cao cấp" hơn, bao gồm cả CRC.
Trên thực tế, CRC không phải là một tổng, mà là kết quả của việc chia một lượng thông tin nhất định (thông điệp thông tin) cho một hằng số, hay nói đúng hơn là phần còn lại của việc chia một thông điệp cho một hằng số. Tuy nhiên, CRC trong lịch sử cũng được gọi là "tổng kiểm tra". Mỗi bit của thông báo đóng góp vào giá trị CRC. Nghĩa là, nếu ít nhất một bit của thông điệp gốc thay đổi trong quá trình truyền, tổng kiểm tra cũng sẽ thay đổi, và đáng kể. Đây là một điểm cộng lớn của việc kiểm tra như vậy, vì nó cho phép bạn xác định rõ ràng liệu tin nhắn gốc có bị bóp méo trong quá trình truyền hay không.
Bước 2
Trước khi chúng tôi bắt đầu tính toán CRC, cần thêm một chút lý thuyết.
Thông điệp gốc là gì cần phải rõ ràng. Nó là một chuỗi các bit liền nhau có độ dài tùy ý.
Hằng số mà chúng ta nên chia thông điệp ban đầu là gì? Con số này cũng có độ dài bất kỳ, nhưng thường sử dụng bội số của 1 byte - 8, 16 và 32 bit. Nó chỉ dễ dàng hơn để đếm, bởi vì máy tính hoạt động với byte, không phải với bit.
Hằng số chia thường được viết dưới dạng đa thức (polynomial) như sau: x ^ 8 + x ^ 2 + x ^ 1 + x ^ 0. Ở đây, bậc của số "x" có nghĩa là vị trí của một bit trong số, bắt đầu từ số 0 và bit quan trọng nhất cho biết bậc của đa thức và bị loại bỏ khi diễn giải số. Có nghĩa là, số được viết trước đó không hơn gì (1) 00000111 ở dạng nhị phân hoặc 7 ở dạng thập phân. Trong ngoặc đơn, tôi đã chỉ ra chữ số có ý nghĩa nhất của con số.
Đây là một ví dụ khác: x ^ 16 + x ^ 15 + x ^ 2 + x ^ 0 = (1) 1000000000000101 = 0x8005 = 32773.
Thông thường một số đa thức chuẩn được sử dụng cho các loại CRC khác nhau.
Bước 3
Vì vậy, làm thế nào để bạn tính toán tổng kiểm tra? Có một phương pháp cơ bản - chia một thông báo thành một "đầu" đa thức - và các sửa đổi của nó để giảm số lượng phép tính và theo đó, tăng tốc độ tính toán CRC. Chúng ta sẽ xem xét phương pháp cơ bản.
Nói chung, phép chia một số cho một đa thức được thực hiện theo thuật toán sau:
1) một mảng (thanh ghi) được tạo ra, chứa đầy các số không, có chiều dài bằng chiều dài của chiều rộng đa thức;
2) thông điệp ban đầu được bổ sung các số không trong các bit ít quan trọng nhất, với số lượng bằng số bit của đa thức;
3) một bit quan trọng nhất của thông báo được nhập vào bit quan trọng nhất của thanh ghi, và một bit được chuyển từ bit quan trọng nhất của thanh ghi;
4) nếu bit mở rộng bằng "1", thì các bit được đảo ngược (phép toán XOR, OR loại trừ) trong các bit đăng ký đó tương ứng với các bit trong đa thức;
5) nếu vẫn còn bit trong tin nhắn, hãy chuyển sang bước 3);
6) khi tất cả các bit của thông báo vào thanh ghi và được xử lý bởi thuật toán này, phần còn lại của phép chia vẫn còn trong thanh ghi, đó là tổng kiểm tra CRC.
Hình minh họa phép chia chuỗi bit ban đầu cho số (1) 00000111, hoặc đa thức x ^ 8 + x ^ 2 + x ^ 1 + x ^ 0.
Bước 4
Còn lại một vài thao tác bổ sung. Như bạn có thể nhận thấy, tin nhắn có thể được chia cho bất kỳ số nào. Làm thế nào để chọn nó? Có một số đa thức tiêu chuẩn được sử dụng để tính CRC. Ví dụ: đối với CRC32, nó có thể là 0x04C11DB7 và đối với CRC16, nó có thể là 0x8005.
Ngoài ra, trong thanh ghi ở đầu phép tính, bạn có thể viết không phải số 0 mà là một số khác.
Ngoài ra, trong quá trình tính toán, ngay trước khi phát hành tổng kiểm tra CRC cuối cùng, chúng có thể được chia cho một số khác.
Và điều cuối cùng. Các byte của thông báo khi ghi vào thanh ghi có thể được đặt là bit quan trọng nhất "chuyển tiếp" và ngược lại, bit ít quan trọng nhất.
Bước 5
Dựa trên tất cả những điều trên, hãy viết một hàm Cơ bản. NET để tính toán tổng kiểm tra CRC bằng cách lấy một số tham số mà tôi đã mô tả ở trên và trả về giá trị CRC dưới dạng số không dấu 32 bit.
Hàm chia sẻ công khai GetCrc (ByVal byte As Byte (), ByVal poly As UInteger, ByVal width As Integer = 32, ByVal tùy chọn initReg As UInteger = & HFFFFFFFFUI, ByVal finalXor As UInteger tùy chọn = & HFFFFFFFFUI, Tùy chọn ByVal đảo ngượcBytes reverseCrc As Boolean = True) Là UInteger
Dim widthInBytes As Integer = width / 8
'Bổ sung chiều rộng thông báo bằng các số không (tính bằng byte):
ReDim Bảo tồn byte (byte. Length - 1 + widthInBytes)
'Tạo một hàng đợi bit từ tin nhắn:
Dim msgFifo làm hàng đợi mới (Của Boolean) (byte. Count * 8 - 1)
Đối với mỗi b As Byte Trong byte
Dim ba As New BitArray ({b})
If reverseBytes Then
Đối với tôi là số nguyên = 0 đến 7
msgFifo. Enqueue (ba (i))
Kế tiếp
Khác
Đối với tôi là số nguyên = 7 đến 0 Bước -1
msgFifo. Enqueue (ba (i))
Kế tiếp
Kết thúc nếu
Kế tiếp
'Tạo một hàng đợi từ các bit điền ban đầu của thanh ghi:
Dim initBytes As Byte () = BitConverter. GetBytes (initReg)
Dim initBytesReversed As IEnumerable (Of Byte) = (Từ b As Byte Trong initBytes Lấy widthInBytes).
Dim initFifo làm hàng đợi mới (Của Boolean) (chiều rộng - 1)
Đối với mỗi b As Byte Trong initBytesReversed
Dim ba As New BitArray ({b})
Nếu không đảo ngược thì
Đối với tôi là số nguyên = 0 đến 7
initFifo. Enqueue (ba (i))
Kế tiếp
Khác
Đối với tôi là số nguyên = 7 đến 0 Bước -1
initFifo. Enqueue (ba (i))
Kế tiếp
Kết thúc nếu
Kế tiếp
'Shift và XOR:
Dim register As UInteger = 0 'điền vào thanh ghi width-bit bằng các số không.
Do trong khi msgFifo. Count> 0
Dim poppedBit As Integer = CInt (register >> (width - 1)) Và 1 'xác định trước thanh ghi shift.
Dim shiftBit As Byte = Convert. ToByte (msgFifo. Dequeue)
Nếu initFifo. Count> 0 Thì
Dim b As Byte = Convert. ToByte (initFifo. Dequeue)
shiftBit = shiftBit Xor b
Kết thúc nếu
register = đăng ký << 1
register = đăng ký Hoặc shiftBit
Nếu poppedBit = 1 Thì
register = đăng ký Xor poly
Kết thúc nếu
Vòng
'Chuyển đổi cuối cùng:
Dim crc As UInteger = register 'Thanh ghi chứa phần còn lại của phép chia == checksum.
Nếu đảo ngượcCrc Sau đó
crc = phản xạ (crc, chiều rộng)
Kết thúc nếu
crc = crc Xor finalXor
crc = crc Và (& HFFFFFFFFUI >> (32 - width)) 'che đi các bit ít quan trọng nhất.
Trả lại crc
Chức năng kết thúc
