Старший бит должен быть всегда 1, иначе при первой же операции получим 1 в остатке и никуда с места не сдвинемся. Исходная последовательность. 010100111010 Но поскольку она начинается с нуля, двигаем ее влево до первой единицы. Вычисление происходит так (на примере 4-битного): 10100111010 1001 ---- 001101 1001 0100 ---- 1001 1001 ---- 00001010 1001 ---- 0011 После каждого XOR остаток сдвигается влево на количество нулей (чтобы первой была 1) и такое же кол-во бит их потока запихивается в конец остатка. Но посмотрел алгоритм в Википедии: unsigned char Crc8(unsigned char *pcBlock, unsigned char len) { unsigned char crc = 0xFF; unsigned char i; while (len--) { crc ^= *pcBlock++; for (i = 0; i < 8; i++) crc = crc & 0x80 ? (crc << 1) ^ 0x31 : crc << 1; } return crc; } Подсчет crc ведется побайтово (crc ^= *pcBlock++), а не побитово и когда остаток сдвигается, в его конец ничего не пихается (crc << 1). Я понимаю что у ЭВМ нет таких операций как "первые N бит слова запихать в конец другого слова" и не может работать с битами в отдельности. Но этот алгоритм встречается везде, скорее всего - он правильный. Тогда я не понимаю - какая хитрость или извращение используется в этом алгоритме. Он другой, но он делает тоже самое. Кто-нибудь может мне объяснить? Советчики не копаться в алгоритме, если все и так работает, пусть читают другую тему.
Программный делает тоже самое, но с таблицей, обрабатывая сразу 8 бит, усек? А вот сама таблица считается побитово, во как.
На 99% он правильный. Но если взять код CRC16-CCITT И проверить прямой метод с побитовым делением и табличный то получаться расхождения. Правда табличный легко корректируется.
Pavia Это еще как??? Примеры в студию! А то это типа "как складывать парашют. издание второе, исправленное".
Наконец-то я смог зайти на сайт. Модем опять его не видит! Pavia Не факт, есть бестабличные алгоритмы. И для CRC32 и CRC64 таблица будет очень большая. Вообще-то CRC - это побитовый алгоритм и почему его используют в ЭВМ, мне непонятно. Алгоритм какой-то извращенный. Но вот скажите, почему делается вот так: Код (Text): crc ^= *pcBlock++; Вообщем как побитовый алгоритм заменяется побайтовым и при этом работает одинаково? Вот давно я написал тот же алгоритм CRC, но с Init=00h, он побитовый - создается слово, а биты задвигаются в старший байт из младшего, потом когда 8 бит будет задвинуто, в low пихается следующий байт (см. функцию myCrc8): http://exfile.ru/68332 Только вот я не проверил - выдает ли он тот же результат, что и алгоритм, приведенный выше (init разный).
AndreyMust19 А почитать? crc Смотрим вконце на ссылки. Например: "CRC, и как его восстановить" З.Ы Гугл не стоит игнорить.
AndreyMust19 В общем, брателло, развел ты здесь настояший детский сад с сопельками и памперсами. Но ничего, обижаться не стоит, тебе тут все объяснят. Для начала забудь про побитовое деление и попробуй отыскать остаток от деления обычных чисел, не используя само деление. Например, 12345432100 mod 13 = 1 Составь таблицу остатков, аналогичную той, что используется в CRC: Tab[0]=000 mod 13=00 Tab[1]=100 mod 13=09 Tab[2]=200 mod 13=05 Tab[3]=300 mod 13=01 Tab[4]=400 mod 13=10 Tab[5]=500 mod 13=06 Tab[6]=600 mod 13=02 Tab[7]=700 mod 13=11 Tab[8]=800 mod 13=07 Tab[9]=900 mod 13=03 А теперь откусываем слева первую цифру, находим соответствующей ей остаток из таблицы и прибавляем его с головы: 12345432100 3245432100 255432100 60432100 632100 34100 4200 300 01 Таким образом, остаток от деления, он же контрольная сумма, равен 1. Его мы нашли с помошью поциферной таблицы не прибегая к делению. CRC32 и CRC64 работают похожим образом. Таблицы там разумеется небольшие, на 256 входов, всего по числу вариантов значений одного байта (а у нас в примере было 10 входов, так как пример в десятичной системе) На практике к последовательности сначала добавляют FFFFFFFF…, чтобы контрольные суммы часто встречающихся последовательностей из нулей были разные. Саму контрольную сумму в конце гасят FFFFFFFF…, чтобы контрольная сумма пустой строки была равна нулю.
Совсем запутался... То что ты привел из Вики это побитовый алгоритм. Побайтовый вот: crc=(crc shr 8) xor Table[crc xor byte and 255] Для crc8 все вырождается в простую выборку из таблицы crc8=Table[crc8 xor byte] Такие командочки есть, можешь сдвигать длинные регистры и последовательности. Но с таблицей оно быстрее будет на порядок.
Ну да, алгоритм побитовый, но организован так, чтобы не двигать каждый раз всю последовательность, а двигать только байт. Настоящие же побайтовые а не эта демострашка дурацкая используют байтовую таблицу. Да в том, что аппаратно это происходит в специальном регистре с обратными связями такт за тактом, а не в простом регистре с кучей операций.
AndreyMust19 фу ты черт, я и сам запутался где побитовый а где побайтовый. То что ты привел, это действительно побайтовый алгоритм и все что я писал про табличный, к нему применимо. Просто код содержит тупую работу и дрючит каждый байт восемь раз вместо того чтобы затабличить один раз и потом вынимать. То есть твой код эквивалентен коду crc8=Table[crc8 XOR byte] только таблица каждый раз вычисляется налету, что не целесообразно
persicum В аппаратуре - побитовый, а в системе - программый. Реализации разные, а работать должны одинаково. Вот я и пытаюсь понять - как изменили побайтовый алгоритм, чтобы он работал также, как побитовый. Из всего сказанного (спасибо!) я думаю что Википедиа-алгоритм делает так: byte ^ 1001101 ^ 0011010 ^ 0110100 то есть ксорит байт, сдвигает остаток влево, опять ксорит полиномом и так далее 8 раз, то есть цикл "for-8" вычисляет остаток от деления 8-ми битов байта на полином. Как бы не по одному биту за раз, а по 8. Решил проверить оба алгоритма, должны выдать одинаковый результат, но не выдают: Начальные данные: init = 11111111 poly = 10110001 MyCrc8: Код (Text): 1101001000111000 xor | 11111111 | --------(180d) | 00101101 | 10110100 | 10110001 | -------- | 0000010111100|(188d) 10110001| --------\ 000011010 = 1Ah Crc8: Код (Text): 1101001000111000 xor 11111111 -------- 00101101 Первый байт: 00101101 <<2 (i = 6) 101101000 (180d) 10110001 -------- 110110010 (i = 4) 10110001 -------- 00000011 <<4 (i = 0) 00110000 (48d) Второй байт: 00111000 00101101 -------- 00001000 (8d) <<4 (i = 4) 100000000 10110001 (177d) -------- 101100010 10110001 -------- 110100110 10110001 -------- 00010111 (23d) <<1 (i = 0) 00101110 = 2Eh
AndreyMust19 пора бы научиться прогать на сях или на пасе... Привожу байтовый и битовый релиз crc8, на первый взгляд они ничем не отличаются, но между ними принципиальная разница, попробуй определить какая. Код (Text): {$APPTYPE CONSOLE} type TByte=array [1..MaxInt] of byte; PByte=^TByte; var Buff:PByte; BuffLen,i:Cardinal; crc8:byte; const Poly:byte=$31; //побайтовый алгоритм, xor Poly это сложение //границы между байтами не обрабатываются procedure crc8byte(var crc:byte;Buff:PByte;Len:Cardinal); var i,j:Cardinal; begin for i:=1 to Len do begin crc:=crc xor Buff[i]; for j:=1 to 8 do begin if (crc and $80)<>0 then crc:=(crc shl 1) xor Poly else crc:=(crc shl 1); end; end; end; //побитовый алгоритм, xor Poly это вычитание //границы между байтами обрабатываются, т.к. сдвигается тип word procedure crc8bit(var crc:byte;Buff:PByte;Len:Cardinal); var i,j:Cardinal; w,p:word; begin w:=crc shl 8; p:=Poly shl 8; for i:=1 to Len+1 do begin if i<=Len then w:=w or Buff[i]; for j:=1 to 8 do begin if (w and $8000)<>0 then w:=(w shl 1) xor p else w:=(w shl 1); end; end; crc:=w shr 8; end; BEGIN BuffLen:=2048; GetMem(Buff,BuffLen); Randomize; for i:=1 to BuffLen do Buff[i]:=Random(256); crc8:=0; crc8byte(crc8,Buff,BuffLen); writeln(crc8); crc8:=0; crc8bit(crc8,Buff,BuffLen); writeln(crc8); FreeMem(Buff); END.
так ты че, серьезно полагаешь что на компе нельзя организовать побитовое деление длинного полинома? Посмотри функцию crc8bit и можешь смело встречать девятнадцатилетие.
Код (Text): procedure crc8bit(var crc:byte;Buff:PByte;Len:Cardinal); var i,j:Cardinal; w,p:word; begin w:=crc shl 8; p:=Poly shl 8; for i:=1 to Len+1 do begin if i<=Len then w:=w or Buff[i]; for j:=1 to 8 do begin if (w and $8000)<>0 then w:=(w shl 1) xor p else w:=(w shl 1); end; end; crc:=w shr 8; end; А разве я выше не тот же алгоритм побитового CRC привел? Можно, но процессору проще с байтами работать, чем с битами, поэтому в ЭВМ и используются byte / word / dword. С битами будет менее читаемо и медленнее работать.
к сожалению, из того что я писал ты ничего не понял. Обрати внимание как ведут себя границы между байтами, где XOR а где OR. Первая процедура считает дискретно байтами, вторая непрерывно, хотя и подгружает тоже байтами.
AndreyMust19 подсказка: crc8byte это алгоритм из Вики, записанный на пасе, а crc8bit это якобы программно нереализуемый "аппаратный" вариант
.. в аппаратуре это про контроллеры штоль?.. хм я CRC16 табличный писал для ATmega162/PIC18/8051, вроде как то работает с байтами
