ინტერნეტში 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) 10000000000001010 = 0x8005 = 32773.
ჩვეულებრივ, რამდენიმე სტანდარტული მრავალწევრი გამოიყენება სხვადასხვა ტიპის CRC- ებისთვის.
ნაბიჯი 3
ასე როგორ გამოითვალეთ საკონტროლო ჯამი? არსებობს ძირითადი მეთოდი - წერილის დაყოფა მრავალწევრად "თავდაპირველად" - და მისი მოდიფიკაციები, რომ შემცირდეს გამოთვლების რაოდენობა და, შესაბამისად, დააჩქაროს CRC გაანგარიშება. ჩვენ გადავხედავთ ძირითად მეთოდს.
ზოგადად, მრავალწევრის მიხედვით რიცხვის დაყოფა ხორციელდება შემდეგი ალგორითმის მიხედვით:
1) იქმნება მასივი (რეგისტრი), რომელიც ივსება ნულებით, სიგრძით ტოლია მრავალწევრის სიგანის სიგრძე;
2) ორიგინალ შეტყობინებას ემატება ნულები ყველაზე ნაკლებად მნიშვნელოვანი ბიტით, პოლინომის ბიტების რაოდენობის ტოლი თანხით;
3) შეტყობინების ერთი ყველაზე მნიშვნელოვანი ბიტი შედის რეესტრის ყველაზე ნაკლებად მნიშვნელოვან ბიტზე და ერთი ბიტი გადადის რეესტრის ყველაზე მნიშვნელოვანი ბიტიდან;
4) თუ გაფართოებული ბიტი უდრის "1" -ს, მაშინ ბიტი ინვერსიულია (XOR ოპერაცია, ექსკლუზიური ან) იმ რეესტრის ბიტებში, რომლებიც შეესაბამება პოლინომში არსებულ ბიტებს;
5) თუ შეტყობინებაში ჯერ კიდევ არის ბიტი, გადადით ნაბიჯ 3);
6) როდესაც წერილის ყველა ბიტი შემოვიდა რეესტრში და დამუშავდა ამ ალგორითმით, განყოფილების დარჩენილი ნაწილი რჩება რეგისტრში, რომელიც არის CRC საკონტროლო ჯამი.
ნახაზი ასახავს ორიგინალის ბიტის მიმდევრობის დაყოფას რიცხვის (1) 00000111 ან მრავალწევრის x ^ 8 + x ^ 2 + x ^ 1 + x ^ 0 მიხედვით.
ნაბიჯი 4
დარჩა ორიოდე დამატებითი შეხება. როგორც ალბათ შენიშნეთ, შეტყობინების დაყოფა შესაძლებელია ნებისმიერი რიცხვით. როგორ ავირჩიოთ იგი? არსებობს მთელი რიგი სტანდარტული მრავალწევრები, რომლებიც გამოიყენება CRC- ს გამოსათვლელად. მაგალითად, CRC32- სთვის ეს შეიძლება იყოს 0x04C11DB7 და CRC16- ისთვის შეიძლება იყოს 0x8005.
გარდა ამისა, გაანგარიშების დასაწყისში რეგისტრში შეგიძლიათ დაწეროთ არა 0 ნული, არამედ სხვა ნომერი.
ასევე, გამოთვლების დროს, CRC საბოლოო შემოწმების გაცემისთანავე, მათი დაყოფა შესაძლებელია სხვა რიცხვზე.
და ბოლო რამ. წერილის ბიტი რეესტრში ჩაწერისას შეიძლება განთავსდეს როგორც ყველაზე მნიშვნელოვანი ბიტი "წინ" და პირიქით, ყველაზე ნაკლებად მნიშვნელოვანი.
ნაბიჯი 5
ყოველივე ზემოთქმულიდან გამომდინარე, მოდით დავწეროთ ძირითადი. NET ფუნქცია, რომელიც გამოთვლის CRC საკონტროლო ჯამს, აღვწერე მთელი რიგი პარამეტრების, რომლებიც ზემოთ აღვწერე და CRC მნიშვნელობის დაბრუნებით, როგორც 32 ბიტიანი ხელმოუწერელი რიცხვი.
საზოგადოებრივი გაზიარებული ფუნქცია GetCrc (ByVal bytes as Byte (), ByVal poly As UInteger, Optional ByVal width As Integer = 32, Optional ByVal initReg As UInteger = & HFFFFFFFFUI, Optional ByVal finalXor As UInteger = & HFFFFFFFFUal Ontalial Byal) reverseCrc როგორც ლოგიკური = True) როგორც UInteger
Dim widthInBytes როგორც Integer = სიგანე / 8
წერილის სიგანე დაამატეთ ნულებით (გაანგარიშება ბაიტებში):
ReDim შეინარჩუნეთ ბაიტი (ბაიტი. სიგრძე - 1 + სიგანეInBytes)
'შექმენით ცოტა რიგი შეტყობინებიდან:
Dim msgFifo როგორც ახალი რიგი (ლოგიკური) (ბაიტი. დათვლა * 8 - 1)
თითოეული b როგორც ბაიტი ბაიტებში
Dim ba როგორც ახალი BitArray ({b})
თუ reverseBytes შემდეგ
For i As Integer = 0-დან 7-მდე
msgFifo. Enqueue (ba (i))
შემდეგი
სხვა
For i As Integer = 7-დან 0 ნაბიჯი -1
msgFifo. Enqueue (ba (i))
შემდეგი
Დაასრულე თუ
შემდეგი
შექმენით რიგი რეგისტრის საწყისი შევსების ბიტიდან:
Dim initBytes როგორც ბაიტი () = BitConverter. GetBytes (initReg)
Dim initBytes შეცვლილია როგორც IEnumerable (ბაიტი) = (b- დან By byte In initBytes მიიღეთ widthInBytes). შეცვლა
Dim initFifo როგორც ახალი რიგი (ლოგიკური) (სიგანე - 1)
თითოეული b, როგორც ბაიტი In initBytesReversed
Dim ba როგორც ახალი BitArray ({b})
თუ არა reverseBytes მაშინ
For i As Integer = 0-დან 7-მდე
initFifo. Enqueue (ba (i))
შემდეგი
სხვა
For i As Integer = 7 – დან 0 – მდე ნაბიჯი -1
initFifo. Enqueue (ba (i))
შემდეგი
Დაასრულე თუ
შემდეგი
'Shift და XOR:
Dim regjist as UInteger = 0 'შეავსეთ სიგანე-ბიტიანი რეგისტრი ნულებით.
Do while msgFifo. Count> 0
Dim poppedBit როგორც Integer = CInt (რეგისტრაცია >> (სიგანე - 1)) და 1 'განსაზღვრავს ცვლის რეგისტრატორამდე.
Dim shiftedBit As Byte = Convert. ToByte (msgFifo. Dequeue)
თუ initFifo. დათვლა> 0 შემდეგ
Dim b As Byte = Convert. ToByte (initFifo. Dequeue)
shiftedBit = გადატანილი Bit Xor ბ
Დაასრულე თუ
რეგისტრაცია = დარეგისტრირება << 1
რეგისტრაცია = რეგისტრაცია ან გადატანილი Bit
თუ poppedBit = 1 მაშინ
რეგისტრაცია = რეგისტრაცია Xor poly
Დაასრულე თუ
მარყუჟი
'საბოლოო გადაკეთებები:
Dim crc As UInteger = register 'რეგისტრი შეიცავს დანაყოფის == შემოწმების ჯამს.
თუ reverseCrc შემდეგ
crc = ასახვა (crc, სიგანე)
Დაასრულე თუ
crc = crc Xor საბოლოო Xor
crc = crc და (& HFFFFFFFFUI >> (32 - სიგანე)) 'ნიღბავს ყველაზე ნაკლებად მნიშვნელოვან ბიტებს.
დააბრუნე CRC
დასრულების ფუნქცია
