Полигон-2

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

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