Полигон-2

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 написал:

[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 написал:

[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 написал:

[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 наверное, не считать, а рассчитать. Считать так же, как и остальное содержимое ПЗУ.