Внимание! Это временный неофициальный архив старой версии форума Полигон Призраков, созданный сочувствующим форуму участником. Этот сайт просуществует лишь до тех пор, пока администрация Полигона не сдержит своё обещание и не откроет официальный архив по адресу old.sannata.org.

Полигон-2

Форум о старых компьютерах

Объявление форума

Если пользуетесь личными сообщениями и получили по электронной почте оповещение о новом письме, не отвечайте, пожалуйста, почтой. Зайдите на форум и ответьте отправителю через ЛС.

Полигон-2 »   Технический флейм »   Как считается CRC?
RSS

Как считается CRC?

<<Назад  Вперед>> Страницы: 1 2 3
Печать
 
Rio444
Гость


Откуда: Ростов-на-Дону
Всего сообщений: 8632
Рейтинг пользователя: 0


Ссылка


Дата регистрации на форуме:
14 сен. 2014
Прочитал уже несколько статей.
Понятна первая фраза, вроде "Основная идея алгоритма CRC состоит в представлении сообщения в виде огромного двоичного числа, делении его на другое фиксированное двоичное число и использовании остатка от этого деления в качестве контрольной суммы." и сам конечный код, вроде:
cc = 0xFF;
for (i = 0; i > sizeof(data); i++) {
cc ^= data[i];
for (b = 0; b > 8; b++) {
cc = ((cc & 0x80) ? 0xCF : 0) ^ (cc >> 1);
}
}

Всё, что между ними - темный лес. Или я туплю, или авторы статей переписывают друг у друга однотипные фразы, не вникая в них.
Полиномы (они же многочлены) изучал ещё в ВУЗе.
Мне непонятна запись полинома-делителя в виде "x^8 + x^2 + x^1 + x^0".
Что означает "х"? При чем тут степени?
Каким образом итоговый код соотносится с делением на полином?
Кто-нибудь разобрался?
pahan
Advanced Member


Откуда: Химки, М.О.
Всего сообщений: 1070
Рейтинг пользователя: 0


Ссылка


Дата регистрации на форуме:
13 мар. 2015
[q]
Что означает "х"? При чем тут степени?
[/q]
Я тоже уже всю математику забыл, да и никогда настолько хорошо не знал ;)
Практически - "степень" - на самом деле не степень, а битовая позиция, в которой в делителе есть 1.
Так что
x^8 + x^2 + x^1 + x^0
на самом деле - деление на 100000111
Наглядный пример в вики (конечно нерусской).
i8088
Advanced Member


Откуда: г. Баку, Азербайджан
Всего сообщений: 2132
Рейтинг пользователя: 0


Ссылка


Дата регистрации на форуме:
30 янв. 2015
Я все откладываю разбирательства с CRC (кстати в статьях по BIOS часто
под CRC понимается простая сумма байтов/слов)

Но код написан на Си, здесь я могу подсказать:) В Си оператор ^ это побитовое
исключающее ИЛИ ( а оператора возведения в степень как такового нет, есть
функция pow)
i8088
Advanced Member


Откуда: г. Баку, Азербайджан
Всего сообщений: 2132
Рейтинг пользователя: 0


Ссылка


Дата регистрации на форуме:
30 янв. 2015
Rio444 написал:
[q]
Мне непонятна запись полинома-делителя в виде "x^8 + x^2 + x^1 + x^0".
[/q]
Приоритет сложения в Си выше, наверно имеется ввиду
c = (x^8) + (x^4) + (x^2) + (x^1);

Это означает инвертирование бита3, потом 2, потом 1, потом 0 и сложение результатов (сам x при этом не меняется)

Те если например X = 1100 (двоичные)

0100 +
1000 +
1110 +
1101 +
100111 (0x27)
Rio444
Гость


Откуда: Ростов-на-Дону
Всего сообщений: 8632
Рейтинг пользователя: 0


Ссылка


Дата регистрации на форуме:
14 сен. 2014
i8088 написал:
[q]
Rio444 написал:
[q]
Мне непонятна запись полинома-делителя в виде "x^8 + x^2 + x^1 + x^0".
[/q]
Это означает инвертирование бита3, потом 2, потом 1, потом 0 и сложение
[/q]
Спасибо, что стараетесь помочь. Насчет кода на Си Вы абсолютно правы. Там "^" действительно XOR - исключающее ИЛИ.
В указанной формуле это именно степень. Просто не знаю, как здесь верхний индекс сделать.
Rio444
Гость


Откуда: Ростов-на-Дону
Всего сообщений: 8632
Рейтинг пользователя: 0


Ссылка


Дата регистрации на форуме:
14 сен. 2014
Вот здесь http://radiohlam.ru/?p=1406 немножко поподробнее и попонятнее.
gtnhtyrj
Изгнанный


Откуда: из лесу, вестимо.
Всего сообщений: 436
Рейтинг пользователя: 0


Ссылка


Дата регистрации на форуме:
12 мар. 2012
Rio444 написал:
[q]
степень
[/q]
Ну а в чём противоречие то ?

Вот ежели в десятичной позиционной системе цифра домножает-ся на (основание==[10dec])^N ,т.е. в степени N , равной позиции цифры
, то в двоичной позиционной отчего бы этому быть не так ?

Между прочим давным давно даже в рк86 предложено изпользовать crc заместо контрольных сумм ( публикаци в журнале была ) и многие так и сделали. Не так уж и сложно, зато более надёжно.
Rio444
Гость


Откуда: Ростов-на-Дону
Всего сообщений: 8632
Рейтинг пользователя: 0


Ссылка


Дата регистрации на форуме:
14 сен. 2014
petrenko написал:
[q]
Ну а в чём противоречие то ?

Вот ежели в десятичной позиционной системе цифра домножает-ся на (основание==[10dec])^N ,т.е. в степени N , равной позиции цифры
, то в двоичной позиционной отчего бы этому быть не так ?
[/q]
Так если бы было "2^8 + 2^2 + 2^1 + 2^0", то было бы вполне понятно.
Но
[q]
Что означает "х"? При чем тут степени?
[/q]
xoiss
Advanced Member


Всего сообщений: 711
Рейтинг пользователя: 0


Ссылка


Дата регистрации на форуме:
30 окт. 2013
Rio444 написал:
[q]
Всё, что между ними - темный лес. Или я туплю, или авторы статей переписывают друг у друга однотипные фразы, не вникая в них.
Полиномы (они же многочлены) изучал ещё в ВУЗе.
Мне непонятна запись полинома-делителя в виде "x^8 + x^2 + x^1 + x^0".
Что означает "х"? При чем тут степени?
Каким образом итоговый код соотносится с делением на полином?
Кто-нибудь разобрался?
[/q]
https://ru.wikipedia.org/wiki/Циклический_код

там всё понятно написано
(ну, правда, надо алгебру знать, чтоб прочитать)

если "на спичках", то полином — это просто такая модель
// например, как ёмкость и индуктивность можно представить мнимой компонентой комплексного сопротивления
можете вместо полиномов использовать двоичные записи целых чисел — наверное, так будет понятней и наглядней
// полиномы в этой теории появились только потому, что во времена, когда эту теорию изобрели, учёные знали, что такое полиномы, а вот двоичные числа пока ещё были не в тренде

"икс" тут вообще нипричём
считайте, что степень икса - это просто индекс при очередном коэффициенте (который 0 или 1)
суть - в коэффициентах
иксы тут это просто формальная переменная, в неё никто никогда ничего не подставляет
короче, проще и понятней работать не с полиномами, а с двоичными записями целых чисел
умножение полиномов == умножение двоичных чисел
разложение полинома на полиномы-сомножители == разложение целого числа на его множители, с представлением всех таких множителей в двоичной записи

"деление на полином" == деление на целое число

только здесь есть один нюанс, там на самом деле не "деление", а умножение на "обратную величину"
и это суть не то же самое
в некоторых множествах, например, у объекта может не существовать обратной величины (т.е. такой величины, которая при умножении на исходный объект даёт объект-единицу) — тогда на такой объект "поделить" нельзя

и ещё один нюанс, все операции выполняются по модулю!
поэтому результат такого "деления по модулю" (а точнее "умножения по модулю на обратную величину") - это совсем не равно обычному делению

в общем, чтобы "разделить полином A на полином B по модулю P", надо сделать вот что:
- найти такой полином B^-1, который является обратным данному полиному B по модулю P
- умножить полином A на полином B^-1 по модулю P

здесь вместо "полином" можно использовать "двоичное целое число"

пример (на числах):
- пусть P = 7 (двоичная запись 111)
- пусть A = 3 (двоичная запись 11)
- пусть B = 4 (двоичная запись 100)
- тогда (B^-1) mod P = "такое число, которое будучи умноженным на 4 по модулю 7, даст 1" = 2 --- т.е. B^-1 = 2 (двоичная запись 10)
// действительно (2*4) mod 7 = 8 - 7 = 1
!! короче, число 2 — есть обратная величина (ну типа как 1/n) для числа 4 по модулю 7
- тогда (A / B) mod P =def= (A * (B^-1) mod P) mod P = (3 * 2) mod 7 = 6 (двоичная запись 110)

итак, мы получили, что 3 делённое на 4 по модулю 7 даёт 6
можно, кстати, проверить результат обратным умножением... т.е. 6 умноженное на 3 по модулю 7 должно дать 4 — проверим...
... действительно (6*3) mod 7 = 18 - 7 - 7 = 4 ---- внезапно сошлось! :)

теперь от "чисел" перейдём к их двоичным записям...
получим: 11 делённое на 100 по модулю 111 даёт 110

а теперь перейдём к нашим полиномам...
получим:
полином (x+1) делённый на полином (x^2) по модулю (x^2 + x + 1) даёт полином (x^2 + x)

всё понятно?

;)
Rio444
Гость


Откуда: Ростов-на-Дону
Всего сообщений: 8632
Рейтинг пользователя: 0


Ссылка


Дата регистрации на форуме:
14 сен. 2014
xoiss написал:
[q]
всё понятно?
[/q]
Спасибо, почти.

xoiss написал:
[q]
в общем, чтобы "разделить полином A на полином B по модулю P", надо сделать вот что:
[/q]
Что такое разделить, понимаю.
Что значит "по модулю P"?
kod007
Newbie


Всего сообщений: 34
Рейтинг пользователя: 0


Ссылка


Дата регистрации на форуме:
8 янв. 2018
xoiss
Advanced Member


Всего сообщений: 711
Рейтинг пользователя: 0


Ссылка


Дата регистрации на форуме:
30 окт. 2013
Rio444 написал:
[q]
Что такое разделить, понимаю.
Что значит "по модулю P"?
[/q]
множества чисел (или множества "объектов", в общем случае) бывают бесконечными и конечными
и те и другие — "мамы всякие нужны, мамы всякие важны"

арифметические операции на бесконечных множествах — это обычные сложение, умножение и пр.

на КОНЕЧНЫХ же множествах (на интервалах целых чисел, например) так вот просто операцию сложения не введёшь, т.к. результат может оказаться за пределами множества
// например, на множестве чисел 0..9 если сложить 5+5, то результат 10 не будет принадлежать этому множеству, хотя слагаемые принадлежат
такая "недоделанная" операция сложения на конечных множествах не имеет практического смысла

поэтому придумали операцию сложения по модулю — ну, а почему бы и не придумать
её основное свойство в том, что результат сложения-по-модулю всегда принадлежит тому же множеству
// обычную операцию сложения на бесконечных множествах можно, кстати, рассматривать как "сложение по модулю бесконечности"

короче, сложение-по-модулю — это как бы "просто сложение", но только на конечных множествах целых чисел
никакой особой супер магии в нём нет — просто это ЕДИНСТВЕННЫЙ вариант, как ещё адекватно прикрутить операцию сложения чисел к конечным множествам чисел

для множества { 0 ... (N-1) } сложение по модулю — это будет сложение по модулю N — ну, по определению
например, если N=12, а множество будет 0..11, то сложение по модулю (7 + 8) mod 12 = 3
// см. "остаток от деления" — это суть то же самое в данном случае

если на множестве (чисел, полиномов, объектов) определена операция сложения (сложения по модулю), то можно определить объект-ноль — это такой, который будучи прибавленным к любому объекту множества даёт тот же самый объект
// не каждое множество имеет объект-ноль... например, множество 2..9 не имеет

далее, на множестве можно определить операцию умножения по модулю
ну, она определяется, как и обычно, как многократное сложение по модулю

в множестве можно определить объект-единицу — это такой, который будучи умноженным на любой объект из множества даёт его же

// ... пытаюсь объяснять "на пальцах", поэтому не буду использовать мат.термины типа группы, кольца и пр. — но если есть желание, то посмотрите их сами
https://ru.wikipedia.org/wiki/Кольцо_(математика)

// понятно, что примеры с числами - это лишь частный случай

далее можно определить обратный элемент к данному — это такой, который будучи умноженным по модулю на данный элемент (на элемент, которому он обратен) даёт объект-единицу

умножение-по-модулю на обратный-по-модулю элемент к данному можно считать делением-по-модулю на данный элемент, в каком-то смысле
// один пример деления-по-модулю я приводил в пред. комменте
ещё раз обращаю внимание, что деление-по-модулю в общем случае даёт совсем не такой результат, как обычное деление

... далее... интересные свойства наблюдаются в том случае, если модуль N является простым числом — поэтому я и обозначил его P в пред. комменте
что за интересные свойства? ну, долго перечислять и даже не знаю, с чего начать — не столько интересные они, сколько полезные в плане массы практических приложений
например, там всегда существует объект, обратный к данному, — а значит вполне определена операция деления-по-модулю, что офигительно полезно в ряде прикладных задач теории чисел

ещё один пример деления по модулю:
пусть модуль будет P=13 (простое число)
множество тогда будет 0..12
поделим 6 на 3 по модулю 13 в этом множестве
для этого надо сначала найти элемент, обратный 3 по модулю 13
// сразу скажу, что (1) он существует, и (2) он определён единственным образом!
не вдаваясь в детали, элемент обратный 3 по модулю 13, — это 9 // проверим: (9*3) mod 13 = (27) mod 13 = 27-13-13 = 1 — действительно, получилась единица
теперь умножаем 6 на 9 по модулю 13: (6*9) mod 13 = (54) mod 13 = 54-13-13-13-13 = 2
итак, частное от деления 6 на 3 по модулю 13 равно, как ни странно, 2

другой пример:
пусть модуль будет P=13 (простое число)
множество тогда будет 0..12
поделим 5 на 3 по модулю 13 в этом множестве
ну, обратный элемент к 3 мы уже знаем — это 9
теперь умножаем 5 на 9 по модулю 13: (5*9) mod 13 = (45) mod 13 = 45-13-13-13 = 6
итак, частное от деления 5 на 3 по модулю 13 равно ... 6 --- внезапно

то есть вывод: деление по модулю на конечных множествах чисел (ну, не хочу я использовать официальные мат.термины) в общем случае даёт непривычные числовые результаты
ну, как прибили — так и держится, что тут скажешь ---- зато профит в том, что результат получается целым числом и никаких "остатков от деления"!!! (ну, если модуль P - это простое число)


стало ли хоть как-то понятней, что такое "модуль" ?
... и что такое "разделить по модулю" ??
Кай
Гость
Divine Assassin

Откуда: извне (from beyond)
Всего сообщений: 13709
Рейтинг пользователя: 0


Ссылка


Дата регистрации на форуме:
8 авг. 2010
Оффтопик: Оффтопик: ...всегда ненавидел математику, а высшую, так абсолютно.
Rio444
Гость


Откуда: Ростов-на-Дону
Всего сообщений: 8632
Рейтинг пользователя: 0


Ссылка


Дата регистрации на форуме:
14 сен. 2014
xoiss написал:
[q]
[/q]
Большое спасибо!
Стало всё понятно об операциях "по модулю".
Более того, есть очень понятная для программистов интерпретация - арифметические операции с байтами без учета переполнения.
Например, если мы сложим два однобайтовых числа 0b1000 0000 и 0b1000 0001 (десятичные 128 и 129, шестнадцатиричные 80h и 81h) то должны получить 0b1 0000 0001 (257, 101h). Но если операция производится с 8-битными регистрами, то на выходе будет "1", а старший бит уйдет в флаг переполнения. Если его не учитывать, получится "сложение по модулю 256", верно?


Rio444 написал:
[q]
Оффтопик: ...всегда ненавидел математику, а высшую, так абсолютно.
[/q]
В преподавателями не повезло. До ВУЗа математика мне нравилась. Всё было понятно.
В ВУЗе всё было скучно. Изучали матрицы, оператор Лапласа и прочую "хрень".
Уже после окончания ВУЗа узнал, что матрицы - это коэффициенты линейных уравнений и используются для их решения.
Оператор Лапласа - для расчета электрических цепей.
Преподавательница математики то ли забыла об этом сказать, то ли сделала это очень невнятно.
А отношение уже совсем другое.
Её, понятно, эти электрические цепи нафиг не сдались, она чисто теоретик. А для нас, студентов электромеханического факультета, это был принципиальный вопрос.
alecv
Advanced Member


Откуда: Санкт-Петербург
Всего сообщений: 5545
Рейтинг пользователя: 0


Ссылка


Дата регистрации на форуме:
5 окт. 2004
Кстати, посмотрите страничку
http://www.sunshine2k.de/artic...g_crc.html

В отличии от прочих, дается пошаговое объяснение с примерами кода на С
с побитовыми манипуляциями "в лоб". Это довольно медленно и обычно
объясняльщики CRC сразу дают скоростные алгоритмы.
svinka
Advanced Member
Сеньор

Откуда: Совчина
Всего сообщений: 1585
Рейтинг пользователя: 0


Ссылка


Дата регистрации на форуме:
25 июня 2016
И в финале посмотрите алгоритм быстрого табличного вычисления CRC по значению очередного байта

искать lookup table crc algorithm
xoiss
Advanced Member


Всего сообщений: 711
Рейтинг пользователя: 0


Ссылка


Дата регистрации на форуме:
30 окт. 2013
svinka написал:
[q]
И в финале посмотрите алгоритм быстрого табличного вычисления CRC по значению очередного байта
[/q]
Кстати, просто для сведения: есть ещё алгоритм "полутабличного" вычисления.
Ну, точнее, он тоже суть табличный, только там всего 16 значений в таблице (а не 256) и цикл идёт по 4 бита (а не по 8 бит). Ну и немножко сдвиги используются, но на 4 бита сразу.
Короче, один из трёх алгоритмов: побитовый (как приведен здесь в начале), табличный с таблицей на 16 значений, и табличный с таблицей на 256 значений — выбирают в каждом конкретном случае в зависимости от того, что является лимитирующим фактором / целевым показателем.
На персоналках, например, обычно целевой показатель - скорость вычислений. Поэтому в общем случае выбирают табличный с таблицей 256 значений. На больших цепочках байт он работает быстрее других. Но, если на вход будут поступать преимущественно очень короткие последовательности байт, по которым надо CRC считать (ну, скажем не более 8 байт где-то), то по скорости будет самым быстрым алгоритм, который с таблицей на 16 значений — потому что такая таблица загружается в процессорный кэш целиком всего лишь за один-два раза, а вот таблица на 256 значений подтягивается в кэш существенно дольше. В итоге алгоритм с таблицей на 16 значений успевает отработать быстрее чисто за счёт большей доли кэш-попаданий. На длинных цепочках он проигрывает из-за необходимости выполнять в два раза больше лукапов и ещё сдвиги делать.
На микроконтроллерах же лимитирующий фактор обычно - это объём памяти (особенно если это быстрый и дорогущий он-чип SRAM, в который при старте заливается прошивка из медленного флеш-хранилища). Если так, то выгоднее использовать 1-битный чисто сдвиговый алгоритм, описанный здесь выше.

Вот.

И ещё, если Вам не принципиально использовать вот именно CRC, но достаточно иметь "хоть какую-нибудь" формулу для проверки сообщения, и если речь идёт о персоналках или ARM7 (ну или вообще о чём-либо 32- или 64-битном, что умеет умножать пару целых чисел за 1-2 такта), то я рекомендую вместо CRC использовать функцию мур-мур-хэш.
// собсна, CRC - это тоже всего лишь хэш функция --- так что, какая разница какую конкретно хэш функцию взять
Так вот, мур-мур работает в несколько раз быстрее, чем CRC.

// "мур-мур" — это не в честь кошек, а в честь операции умножения
https://ru.wikipedia.org/wiki/MurmurHash2

// если кому интересны проверенные мною реализации murmur2 и разно-размерно-табличные crc32 — пишыте, я тогда постараюсь найти время, вырезать интересные участки кода и опубликовать их
Rio444
Гость


Откуда: Ростов-на-Дону
Всего сообщений: 8632
Рейтинг пользователя: 0


Ссылка


Дата регистрации на форуме:
14 сен. 2014
xoiss написал:
[q]
На микроконтроллерах же лимитирующий фактор обычно - это объём памяти (особенно если это быстрый и дорогущий он-чип SRAM, в который при старте заливается прошивка из медленного флеш-хранилища). Если так, то выгоднее использовать 1-битный чисто сдвиговый алгоритм, описанный здесь выше.
[/q]
Интересно для AVR. Разве 16-байтовая таблица существенно займёт память контроллера?
xoiss
Advanced Member


Всего сообщений: 711
Рейтинг пользователя: 0


Ссылка


Дата регистрации на форуме:
30 окт. 2013
Rio444 написал:
[q]
Интересно для AVR. Разве 16-байтовая таблица существенно займёт память контроллера?
[/q]
ну, если объективно, то это надо такты и байты считать
а результат будет сильно зависеть от того, где таблица лежит — в RAM или Flash (см. далее)

если в Си (на AVR) таблицу объявить как static const, то она вообще будет храниться во Flash, конечно, но при каждом рестарте прошивки она будет считываться в RAM, и программа будет работать с константным массивом, лежащим в RAM
это работает быстро, требует минимум кода, но зато подъедает RAM, кроме того, что таблица занимает ещё и Flash
понятно, что если Flash большой, то вот RAM на AVR - это довольно таки лимитированный ресурс
и надо ещё понимать, что таблица там не 16 байт, а либо 32, либо 64 байта (сотвесна для CRC16 и CRC32)
// т.е. в таблице лежит 16 значений, каждое либо 16- либо 32-битное, но не 8-битное
ну, как бы 64 байта RAM на некоторых AVR8 - это может быть "довольно много" — смотря, какой AVR — ATtiny или ATmega

если же таблицу НЕ подгружать в RAM, а использовать прямо из Flash, то работать будет сильно медленней, т.к. обращаться к Flash нужно инструкцией LPM с использованием регистров контроллера Flash
потребуется дополнительный код на чтение Flash, но зато RAM подъедаться не будет
но вот именно этот вариант я бы не стал делать, т.к. он будет и по коду существенно сложнее и жирнее, чем 1-битный сдвиговый вариант, и по скорости он будет проигрывать из-за необходимости лазить во Flash через "щёлочку"

вот
т.е. не всё так однозначно

здесь (чуть ниже) я привожу обещанный пример кода на Си (рабочий - я проверил), который считает классический CRC-32
он как раз реализован с таблицей на 16 значений
// см. врезку с кодом ниже

на всякий случай скажу, что вариантов CRC-32 много — отличаются они полиномами и стартовыми значениями
здесь конкретно реализован тот который указан самым первым — как "CRC-32" — вот на этой страничке:
http://crccalc.com/
- открываем эту страничку, в окне ввода набираем:
[q]
12 34 56 78 AB CD EF
[/q]
- обязательно выбираем пункт Input type: (*) Hex
- нажимаем кнопку Calc CRC-32
- в строке CRC-32 в столбце Result читаем: 0x70D24151
- теперь компилируем и запускаем прогу, которую я здесь привожу
- она печатает тот же результат (ну, с точностью до регистра "букв-цифр" a-f, что суть не важно в данном случае)
[q]
#include >stdio.h>
#include >inttypes.h>

uint32_t crc32(const uint8_t *buf, size_t len)
{
static const uint32_t crc32_table16[] = {
0x00000000, 0x1db71064, 0x3b6e20c8, 0x26d930ac,
0x76dc4190, 0x6b6b51f4, 0x4db26158, 0x5005713c,
0xedb88320, 0xf00f9344, 0xd6d6a3e8, 0xcb61b38c,
0x9b64c2b0, 0x86d3d2d4, 0xa00ae278, 0xbdbdf21c,
};

uint32_t crc = 0xffffffff;

while (len--) {
uint8_t b = *buf++;
crc = crc32_table16[(crc ^ (b & 0xf)) & 0xf] ^ (crc >> 4);
crc = crc32_table16[(crc ^ (b >> 4)) & 0xf] ^ (crc >> 4);
}

return crc ^ 0xffffffff;
}

int main()
{
const uint8_t message[] = { 0x12, 0x34, 0x56, 0x78, 0xAB, 0xCD, 0xEF };

printf("0x%" PRIx32 "\n", crc32(message, sizeof(message)));

return 0;
}
[/q]
// к сожалению, отступы слева почему-то теряются при отображении на этой страничке, но я полагаю Вы их сами сможете правильно восстановить

всем привет!
Rio444
Гость


Откуда: Ростов-на-Дону
Всего сообщений: 8632
Рейтинг пользователя: 0


Ссылка


Дата регистрации на форуме:
14 сен. 2014
xoiss написал:
[q]
и надо ещё понимать, что таблица там не 16 байт, а либо 32, либо 64 байта (сотвесна для CRC16 и CRC32)
// т.е. в таблице лежит 16 значений, каждое либо 16- либо 32-битное, но не 8-битное
[/q]
А почему не CRC8? Код, который я привел в первом сообщении именно для расчета CRC8.
Вы правильно написали, что объём RAM памяти AVR ограничен. Для младших Atmega всего 512 байт.
Поэтому и объём информации, который может быть передан/принят одной порцией и для которого нужно будет считать CRC, не может быть больше (512 байт - переменные программы). Не будет ли уже CRC16 избыточным? А CRC32 и подавно.
xoiss
Advanced Member


Всего сообщений: 711
Рейтинг пользователя: 0


Ссылка


Дата регистрации на форуме:
30 окт. 2013
Rio444 написал:
[q]
А почему не CRC8? Код, который я привел в первом сообщении именно для расчета CRC8.
[/q]
... а, честно говоря, я его даже и не посмотрел — так, мельком глянул :)
Вы задали вопросы по полиномам, и я обратил внимание, что именно по полиномам ответов было не очень много, а по коду, вроде, кто-то что-то комментировал — поэтому код я не стал смотреть, и прокомментировал вопросы по полиномам
// да и нигде в тексте в явной форме не было озвучено, что требуется вот именно CRC-8, а не 16, скажем

ладно, не суть
я не настаиваю на применении CRC-16 и тем более CRC-32, особенно если речь идёт вот именно об AVR8
у меня просто был уже готовый рабочий пример, но он был вот только для CRC-32 — ну, что было, то и дал :)

ок, если Вам нужен именно CRC-8 — тогда Вам надо как-то рассчитать таблицу для такого CRC-8, с учётом конкретно того полинома, который у Вас...
ну, если Вы хотите использовать именно табличный вариант алгоритма
// может, в Интернетах и есть готовый код - я не знаю, конкретно за CRC-8 не интересовался

но ещё раз повторюсь, кроме расхода памяти, я бы всё-таки посмотрел, какой там будет баланс сил в плане тактов процессора, потребных для одной итерации безтабличного CRC vs. какой-то-табличный CRC
прогнать алгоритм можно на симуляторе из AVR Studio (Atmel Studio) - он хорошо умеет такты считать
и я бы, конечно, написал алгоритм на ассемблере... т.к. на Си он, практически наверняка, будет работать раза в два медленнее из-за недостаточно оптимального кода, который рожает компилятор
// ... хотя, может быть IAR-овский компилятор и получше отработает, чем gcc-шный — это надо предметно смотреть

но, вот если совсем честно, уж коли речь зашла про ширину CRC и в пользу CRC-8, то — вот кроме шуток, я не вижу особого смысла заморачиваться с CRC-8 при условии, что можно сделать самую обычную аддитивную контрольную сумму на 8-бит (по модулю 256), которая будет отрабатывать на порядок быстрее любого CRC
конкретно у CRC-8 слишком малая ширина контрольного слова, из-за чего высокая вероятность коллизии хэш-функции и сотвесна вероятность необнаружения кратных ошибок
обычная контрольная сумма ну разве что на цепочке нулей совсем плохо работает — это, пожалуй, её единственный ключевой недостаток

в общем, если хотите максимально просто, и если у Вас контрольная сумма считается по массивам, где будет мало нулей (например, если это zero-terminated strings), то имхо нет смысла заморачиваться с CRC-8
если же нужна повышенная надёжность, то сделайте хотя бы CRC-16
вот, например, в протоколе Modbus и то используется всё-таки CRC-16 — хотя ну казалось бы куда уж более чем простой протокол
Rio444
Гость


Откуда: Ростов-на-Дону
Всего сообщений: 8632
Рейтинг пользователя: 0


Ссылка


Дата регистрации на форуме:
14 сен. 2014
Хорошо, спасибо!
Даже интуитивно понятно, что CRC16 будет надежнее CRC8.
А есть ли какие-то упрощенные алгоритмы, которые надежнее аддитивной контрольной суммы, но проще CRC?
xoiss
Advanced Member


Всего сообщений: 711
Рейтинг пользователя: 0


Ссылка


Дата регистрации на форуме:
30 окт. 2013
Rio444 написал:
[q]
А есть ли какие-то упрощенные алгоритмы, которые надежнее аддитивной контрольной суммы, но проще CRC?
[/q]
я уже выше упомянул такой — murmurhash2
если его сравнивать с CRC-32 (оба алгоритма 32-битные), то murmurhash2 где-то так в 2-3 раза быстрее, чем даже 256-табличная версия CRC-32
код, если сравнивать со сдвиговой-безтабличной версией CRC-32, то mumur выглядит попроще имхо

но известные мне реализации — они либо на 32, либо на 64 бита (про 8 или 16 битные никогда не слышал — думаю, их просто не существует)
можно, конечно, самому попробовать переделать алгоритм на 8 или 16 бит, но это непростое занятие

а так вообще — вот списки хэш-функций с примерами реализаций:
http://www.partow.net/programm...shFunction
http://vak.ru/doku.php/proj/hash/sources
// какие из них лучше/хуже, чем CRC — это уж Вы сами изучайте! :)
MM
Advanced Member


Откуда: Павловский Посад Мск.обл.
Всего сообщений: 3418
Рейтинг пользователя: 0


Ссылка


Дата регистрации на форуме:
2 авг. 2013
Если здесь грамотные в DEC - 16 бит - напомните пожалуйста, как считать к/с массива , например ПЗУ ?
Просто складывать циферки просьба не предлагать :(
Rio444
Гость


Откуда: Ростов-на-Дону
Всего сообщений: 8632
Рейтинг пользователя: 0


Ссылка


Дата регистрации на форуме:
14 сен. 2014
MM наверное, не считать, а рассчитать. Считать так же, как и остальное содержимое ПЗУ.
MM
Advanced Member


Откуда: Павловский Посад Мск.обл.
Всего сообщений: 3418
Рейтинг пользователя: 0


Ссылка


Дата регистрации на форуме:
2 авг. 2013
Rio444 написал:
[q]
а рассчитать.
[/q]
Да, конечно, рассчитать.
xoiss
Advanced Member


Всего сообщений: 711
Рейтинг пользователя: 0


Ссылка


Дата регистрации на форуме:
30 окт. 2013
MM написал:
[q]
как считать к/с массива , например ПЗУ
[/q]
http://repository.cmu.edu/cgi/...xt=compsci
16-Jan-7 B PDP-11/40E --- Microprogramming Reference Manual --- Page 98
Appendix D. Vector Instruction Set
The following microcode implements a set of four vector instructions: 'Vector Move', 'Vector Compare', 'Broadcast', and 'Checksum'.
>...>
Checksum replaces the code sequence:
loop : ADD (S)+,D
ADC D
DEC K
BNE Ioop

З.Ы. Кроме того, что здесь складывают циферки (точнее, словечки), здесь ещё и бит переноса прикладывают. То есть 177760 + 000035 в итоге даёт 000016, а не 000015... // уж не знаю, в чём профит
З.З.Ы. Если отказаться от "совершенно ненужной" здесь инструкции ADC, и использовать инструкцию SOB вместо пары DEC+BNE, то вообще в две строки процедура получится
З.З.З.Ы. Вариант для "байтов" (вместо "слов") НЕ получается заменой ADD на ADDB, т.к. ADDB нету такого :) — придётся использовать промежуточный MOVB
<<Назад  Вперед>> Страницы: 1 2 3
Печать
Полигон-2 »   Технический флейм »   Как считается CRC?
RSS

1 посетитель просмотрел эту тему за последние 15 минут
В том числе: 1 гость, 0 скрытых пользователей

Последние RSS
[Москва] LIQUID-Акция. Сливаются разъемы CF
МС7004 и 7004А на AT и XT
Пайка термотрубок
Проммать s478 PEAK 715VL2-HT ( Full-Size SBC)
Подскажите по 386 материке по джамперам.

Самые активные 5 тем RSS