Интернетте CRC бақылау сомасын есептеудің көптеген нұсқалары бар. Бірақ бақылау сомасы дегеніміз не және ол неге осылай есептеледі? Осыны анықтайық.
Нұсқаулық
1-қадам
Алдымен кішкене теория алайық. Сонымен, CRC дегеніміз не? Қысқаша айтқанда, бұл бақылау сомасын есептеудің бір түрі. Бақылау сомасы - бұл байланыс арналары арқылы беру кезінде қабылданған ақпараттың қабылдағыш жағынан тұтастығын тексеру әдісі. Мысалы, қарапайым чектердің бірі - паритеттік битті қолдану. Бұл кезде жіберілген хабарламаның барлық биттері қорытындыланады, ал егер қосынды жұп болып шықса, онда хабарламаның соңына 0 қосылады, егер тақ болса, онда 1. Қабылдау кезінде, қосындының қосындысы хабарлама биттері де есептеледі және алынған париттік битпен салыстырылады. Егер олар бір-бірінен ерекшеленетін болса, онда жіберу кезінде қателер орын алып, берілген ақпарат бұрмаланған.
Бірақ қателердің болуын анықтаудың бұл әдісі өте ақпаратсыз және әрдайым жұмыс істей бермейді, өйткені егер хабарламаның бірнеше биті бұрмаланса, қосынды паритеті өзгермеуі мүмкін. Сондықтан, көптеген «жетілдірілген» тексерулер бар, оның ішінде CRC.
Іс жүзінде, CRC - бұл қосынды емес, белгілі бір көлемдегі ақпаратты (ақпараттық хабарламаны) тұрақтыға бөлудің нәтижесі, дәлірек айтқанда, хабарламаны тұрақтыға бөлудің қалдығы. Алайда, CRC тарихи тұрғыдан «бақылау сомасы» деп те аталады. Хабарламаның әрбір бөлігі CRC мәніне ықпал етеді. Яғни, егер жіберу кезінде бастапқы хабарламаның кем дегенде бір биті өзгерсе, бақылау сомасы да өзгереді және айтарлықтай болады. Бұл мұндай чектің үлкен плюсы, өйткені ол хабардың түпнұсқасын жіберу кезінде бұрмаланған-бұрмаланбағанын анық анықтауға мүмкіндік береді.
2-қадам
CRC есептеуді бастамас бұрын, тағы біраз теория қажет.
Түпнұсқа хабарлама неде айқын болуы керек. Бұл ерікті ұзындықтағы биттердің сабақтас тізбегі.
Бастапқы хабарламаны қандай тұрақты арқылы бөлу керек? Бұл сан кез-келген ұзындықта болады, бірақ әдетте 1 байт еселігі қолданылады - 8, 16 және 32 бит. Тек санау оңайырақ, өйткені компьютер биттермен емес, байттармен жұмыс істейді.
Бөлгіштің константасы әдетте көпмүшелік (көпмүшелік) түрінде былай жазылады: x ^ 8 + x ^ 2 + x ^ 1 + x ^ 0. Мұндағы «х» санының дәрежесі нөлдегі басталатын сандағы бір разрядтың орнын білдіреді, ал ең маңызды бит көпмүшенің дәрежесін көрсетеді және санды түсіндіру кезінде жойылады. Яғни, бұрын жазылған сан екіліктегі (1) 00000111-ден, ондықтан оннан басқа ештеңе емес. Жақша ішінде мен санның ең маңызды цифрларын көрсеттім.
Міне тағы бір мысал: x ^ 16 + x ^ 15 + x ^ 2 + x ^ 0 = (1) 1000000000000101 «= 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 болуы мүмкін.
Сонымен қатар, есептеудің басындағы тізілімде нөлдерді емес, басқа нөмірлерді жазуға болады.
Сондай-ақ, есептеулер кезінде, соңғы CRC бақылау сомасын шығарар алдында, оларды басқа санға бөлуге болады.
Және соңғы нәрсе. Хабарлама тізіліміне жазған кезде оны «алға», ал керісінше, ең маңызды бит ретінде орналастыруға болады.
5-қадам
Жоғарыда айтылғандардың негізінде, мен жоғарыда сипатталған бірнеше параметрлерді алып, CRC мәнін 32-биттік белгісіз сан ретінде қайтару арқылы CRC бақылау сомасын есептейтін Basic. NET функциясын жазайық.
Жалпы пайдаланылатын функция GetCrc (ByVal байт ретінде байт (), ByVal поли As UInteger, қалау бойынша ByVal ені Integer ретінде = 32, қосымша ByVal initReg As UInteger = & HFFFFFFFFUI, қосымша ByVal finalXor ретінде UInteger OptyFFF, және & HFFFF, reverseCrc As Boolean = True) UInteger ретінде
Dim widthInBytes As Integer = width / 8
'Хабардың енін нөлдермен толықтыр (байтпен есептеу):
ReDim сақтау байттары (байт. Ұзындығы - 1 + еніInBytes)
'Хабарламадан біраз кезек жасаңыз:
Dim msgFifo Жаңа кезек ретінде (логикалық) (байт. Санау * 8 - 1)
Әр b үшін байт байт үшін
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 As Byte () = BitConverter. GetBytes (initReg)
Dim initBytesReversed IEnumerable (Of Byte) = (b As Byte InitBytes еніInBytes алады). Reverse
Dim initFifo жаңа кезек ретінде (бульдік) (ені - 1)
Әр b үшін байт InitBytesReversed
Dim Ba ретінде жаңа BitArray ({b})
Егер кері емес болса
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 'ауысым регистрінің алдында анықтайды.
Күңгірт жылжытылғанБит ретінде байт = Түрлендіру. ТоБайт (msgFifo. Dequeue)
Егер initFifo. Count> 0 Сонда
Dim b As Byte = Convert. ToByte (initFifo. Dequeue)
shifttedBit = shifttedBit Xor b
Аяқтау Егер
регистр = регистр << 1
регистр = тіркеу Немесе shifttedBit
Егер poppedBit = 1 Сонда
регистр = тіркеу Xor poly
Аяқтау Егер
Ілмек
'Соңғы конверсиялар:
Dim crc As UInteger = регистр 'Реестрде бөлінудің қалған бөлігі бар == бақылау сомасы.
Егер reverseCrc Содан кейін
crc = шағылыстыру (crc, ені)
Аяқтау Егер
crc = crc Xor finalXor
crc = crc Және (& HFFFFFFFFFUI >> (ені 32)) 'ең аз биттерді бүркемелейді.
Оралу CRC
Аяқтау функциясы
