Υπάρχουν πολλές επιλογές για τον υπολογισμό του CRC checksum στο Διαδίκτυο. Αλλά τι ακριβώς είναι ένα άθροισμα ελέγχου και γιατί υπολογίζεται με αυτόν τον τρόπο; Ας το καταλάβουμε.
Οδηγίες
Βήμα 1
Κατ 'αρχάς, ας πάρουμε λίγη θεωρία. Λοιπόν, τι ακριβώς είναι το CRC; Εν ολίγοις, αυτή είναι μια από τις ποικιλίες του υπολογισμού αθροίσματος ελέγχου. Το Checksum είναι μια μέθοδος ελέγχου της ακεραιότητας των ληφθέντων πληροφοριών από την πλευρά του δέκτη κατά τη μετάδοση μέσω καναλιών επικοινωνίας. Για παράδειγμα, ένας από τους απλούστερους ελέγχους είναι να χρησιμοποιήσετε το bit ισοτιμίας. Αυτό συμβαίνει όταν όλα τα bit του μεταδιδόμενου μηνύματος συνοψίζονται και εάν το άθροισμα αποδειχθεί ομοιόμορφο, τότε το 0 προστίθεται στο τέλος του μηνύματος, εάν είναι περίεργο, τότε 1. Κατά τη λήψη, το άθροισμα Τα bit των μηνυμάτων υπολογίζονται και συγκρίνονται με το bit ισοτιμίας που λαμβάνεται. Εάν διαφέρουν, τότε προέκυψαν σφάλματα κατά τη μετάδοση και οι πληροφορίες που μεταδόθηκαν παραμορφώθηκαν.
Αλλά αυτή η μέθοδος ανίχνευσης της παρουσίας σφαλμάτων είναι πολύ μη ενημερωτική και δεν λειτουργεί πάντα, γιατί Εάν παραμορφωθούν πολλά bits του μηνύματος, η ισοτιμία του αθροίσματος ενδέχεται να μην αλλάξει. Επομένως, υπάρχουν πολλοί περισσότεροι "προηγμένοι" έλεγχοι, συμπεριλαμβανομένου του CRC.
Στην πραγματικότητα, το CRC δεν είναι ένα άθροισμα, αλλά το αποτέλεσμα της διαίρεσης ενός συγκεκριμένου όγκου πληροφοριών (μήνυμα πληροφοριών) με μια σταθερά, ή μάλλον, το υπόλοιπο της διαίρεσης ενός μηνύματος με μια σταθερά. Ωστόσο, το CRC αναφέρεται επίσης ιστορικά ως «άθροισμα ελέγχου». Κάθε bit του μηνύματος συμβάλλει στην τιμή CRC. Δηλαδή, εάν αλλάξει τουλάχιστον ένα κομμάτι του αρχικού μηνύματος κατά τη μετάδοση, το άθροισμα ελέγχου θα αλλάξει επίσης και σημαντικά. Αυτό είναι ένα μεγάλο πλεονέκτημα ενός τέτοιου ελέγχου, καθώς σας επιτρέπει να προσδιορίσετε αναμφίβολα εάν το αρχικό μήνυμα παραμορφώθηκε κατά τη μετάδοση ή όχι.
Βήμα 2
Πριν αρχίσουμε να υπολογίζουμε το CRC, χρειάζεται λίγο περισσότερη θεωρία.
Ποιο είναι το αρχικό μήνυμα πρέπει να είναι σαφές. Είναι μια συνεχόμενη ακολουθία bits αυθαίρετου μήκους.
Ποια είναι η σταθερά με την οποία πρέπει να διαιρέσουμε το αρχικό μήνυμα; Αυτός ο αριθμός έχει επίσης οποιοδήποτε μήκος, αλλά συνήθως χρησιμοποιούνται πολλαπλάσια του 1 byte - 8, 16 και 32 bit. Είναι πιο εύκολο να μετρήσετε, επειδή οι υπολογιστές λειτουργούν με byte, όχι με bit.
Η σταθερά διαιρέτη γράφεται συνήθως ως πολυώνυμο (πολυώνυμο) ως εξής: x ^ 8 + x ^ 2 + x ^ 1 + x ^ 0. Εδώ, ο βαθμός του αριθμού "x" σημαίνει τη θέση του one-bit στον αριθμό, ξεκινώντας από το μηδέν, και το πιο σημαντικό bit δείχνει τον βαθμό του πολυωνύμου και απορρίπτεται κατά την ερμηνεία του αριθμού. Δηλαδή, ο προηγουμένως γραμμένος αριθμός δεν είναι τίποτα περισσότερο από (1) 00000111 σε δυαδικό ή 7 σε δεκαδικό Στις παρενθέσεις, έδειξα το σιωπηρό σημαντικότερο ψηφίο του αριθμού.
Ακολουθεί ένα άλλο παράδειγμα: x ^ 16 + x ^ 15 + x ^ 2 + x ^ 0 = (1) 1000000000000101 = 0x8005 = 32773.
Συνήθως ορισμένα τυπικά πολυώνυμα χρησιμοποιούνται για διαφορετικούς τύπους CRC.
Βήμα 3
Λοιπόν, πώς υπολογίζετε το άθροισμα ελέγχου; Υπάρχει μια βασική μέθοδος - διαίρεση ενός μηνύματος σε ένα πολυώνυμο "head-on" - και οι τροποποιήσεις του προκειμένου να μειωθεί ο αριθμός των υπολογισμών και, κατά συνέπεια, να επιταχυνθεί ο υπολογισμός CRC. Θα εξετάσουμε τη βασική μέθοδο.
Γενικά, η διαίρεση ενός αριθμού από ένα πολυώνυμο πραγματοποιείται σύμφωνα με τον ακόλουθο αλγόριθμο:
1) δημιουργείται ένας πίνακας (register), γεμάτος με μηδενικά, ίσου μήκους με το μήκος του πολυωνυμικού πλάτους.
2) το αρχικό μήνυμα συμπληρώνεται με μηδενικά στα λιγότερο σημαντικά bit, σε ποσό ίσο με τον αριθμό των bit του πολυωνύμου.
3) ένα πιο σημαντικό κομμάτι του μηνύματος εισάγεται στο λιγότερο σημαντικό κομμάτι του μητρώου και ένα bit μετακινείται από το πιο σημαντικό κομμάτι του μητρώου.
4) εάν το εκτεταμένο bit είναι ίσο με "1", τότε τα bits είναι ανεστραμμένα (λειτουργία XOR, αποκλειστική OR) σε εκείνα τα bit καταχωρητή που αντιστοιχούν σε αυτά στο πολυώνυμο.
5) εάν υπάρχουν ακόμα bits στο μήνυμα, προχωρήστε στο βήμα 3).
6) όταν όλα τα bits του μηνύματος εισήχθησαν στον καταχωρητή και υποβλήθηκαν σε επεξεργασία με αυτόν τον αλγόριθμο, το υπόλοιπο της διαίρεσης παραμένει στο μητρώο, το οποίο είναι το CRC checksum.
Το σχήμα απεικονίζει τη διαίρεση της αρχικής ακολουθίας bit με τον αριθμό (1) 00000111, ή το πολυώνυμο x ^ 8 + x ^ 2 + x ^ 1 + x ^ 0.
Βήμα 4
Απομένουν μερικές επιπλέον πινελιές. Όπως ίσως έχετε παρατηρήσει, το μήνυμα μπορεί να διαιρεθεί με οποιονδήποτε αριθμό. Πώς να το επιλέξετε; Υπάρχουν ορισμένα τυπικά πολυώνυμα που χρησιμοποιούνται για τον υπολογισμό του CRC. Για παράδειγμα, για CRC32 μπορεί να είναι 0x04C11DB7, και για CRC16 μπορεί να είναι 0x8005.
Επιπλέον, στο μητρώο στην αρχή του υπολογισμού, μπορείτε να γράψετε όχι μηδενικά, αλλά κάποιον άλλο αριθμό.
Επίσης, κατά τη διάρκεια των υπολογισμών, αμέσως πριν από την έκδοση του τελικού άθροισμα ελέγχου CRC, μπορούν να διαιρεθούν με κάποιον άλλο αριθμό.
Και το τελευταίο πράγμα. Τα byte του μηνύματος κατά την εγγραφή στο μητρώο μπορούν να τοποθετηθούν ως το πιο σημαντικό bit "forward", και αντίστροφα, το λιγότερο σημαντικό.
Βήμα 5
Με βάση όλα τα παραπάνω, ας γράψουμε μια βασική συνάρτηση. NET που υπολογίζει το CRC checksum, λαμβάνοντας μια σειρά παραμέτρων που περιέγραψα παραπάνω και επιστρέφοντας την τιμή CRC ως 32-bit χωρίς υπογραφή αριθμό.
Δημόσια κοινόχρηστη λειτουργία GetCrc (ByVal bytes As Byte (), ByVal poly As UInteger, Προαιρετικό πλάτος ByVal As Integer = 32, Προαιρετικό ByVal initReg As UInteger = & HFFFFFFFFUI, Προαιρετικό ByVal finalXor As UInteger = & HFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF reverseCrc As Boolean = True) Ως UInteger
Dim widthInBytes As Integer = πλάτος / 8
Συμπληρώστε το πλάτος του μηνύματος με μηδενικά (υπολογισμός σε byte):
ReDim Preserve bytes (bytes. Μήκος - 1 + πλάτοςInBytes)
Δημιουργήστε μια ουρά λίγο από το μήνυμα:
Dim msgFifo As New Queue (Of Boolean) (bytes. Count * 8 - 1)
Για κάθε b ως Byte In byte
Dim ba As New BitArray ({b})
Αν αντιστραφεί, τότε
Για το i As Integer = 0 έως 7
msgFifo. Enqueue (ba (i))
Επόμενο
Αλλού
For i As Integer = 7 έως 0 Βήμα -1
msgFifo. Enqueue (ba (i))
Επόμενο
Τέλος εαν
Επόμενο
Δημιουργήστε μια ουρά από τα αρχικά bits πλήρωσης του μητρώου:
Dim initBytes As Byte () = BitConverter. GetBytes (initReg)
Dim initBytesReversed As IEnumerable (Of Byte) = (From b As Byte In initBytes Λήψη widthInBytes). Αντίστροφη
Dim initFifo As New Queue (Of Boolean) (πλάτος - 1)
Για κάθε b ως By By InitBytesReversed
Dim ba As New BitArray ({b})
Αν όχι αντίστροφα Bytes τότε
Για το i As Integer = 0 έως 7
initFifo. Enqueue (βα (i))
Επόμενο
Αλλού
Για i As Integer = 7 έως 0 Βήμα -1
initFifo. Enqueue (βα (i))
Επόμενο
Τέλος εαν
Επόμενο
Shift και XOR:
Dim register As UInteger = 0 'συμπληρώστε τον καταχωρητή πλάτους-bit με μηδενικά.
Do While msgFifo. Count> 0
Dim poppedBit As Integer = CInt (register >> (width - 1)) Και 1 'καθορισμός πριν από το shift register.
Dim shiftBit As Byte = Μετατροπή. ToByte (msgFifo. Dequeue)
Εάν initFifo. Count> 0 τότε
Dim b As Byte = Μετατροπή. ToByte (initFifo. Dequeue)
shiftBit = shiftBit Xor β
Τέλος εαν
register = εγγραφή << 1
register = register ή shiftBit
Εάν poppedBit = 1 Τότε
register = εγγραφή Xor poly
Τέλος εαν
Βρόχος
«Τελικές μετατροπές:
Dim crc As UInteger = register 'Το μητρώο περιέχει το υπόλοιπο της διαίρεσης == checksum.
Εάν αντίστροφαCrc τότε
crc = αντανακλά (crc, πλάτος)
Τέλος εαν
crc = crc Xor finalXor
crc = crc Και (& HFFFFFFFFUI >> (32 - πλάτος)) 'κρύβουμε τα λιγότερο σημαντικά bit.
Επιστροφή crc
Λειτουργία τερματισμού
