Ещё один метод расчёта CRC16

[uni 0]

В 14.02.2020 в 19:05, demiurg_spb сказал:

Интересно было бы сравнить с Вашим решением по скорости и по объёму кода.

К сожалению, результат не совпал с табличным вариантом и с предыдущим моим двойным циклом с полиномом 0xA001. В любом случае этот алгоритм гораздо медленнее приведённого мной варианта, т.к. также использует двойной цикл, судя по эквивалентным с-кодам, приведённым в документации. Сам асм-код не разбирал.

Цитата

Optimized CRC-16 calculation.

Polynomial: x^16 + x^15 + x^2 + 1 (0xa001)<br>
Initial value: 0xffff

This CRC is normally used in disk-drive controllers.

The following is the equivalent functionality written in C.

 

Optimized CRC-16 calculation.

Polynomial: x^16 + x^15 + x^2 + 1 (0xa001)<br>
Initial value: 0xffff

This CRC is normally used in disk-drive controllers.

The following is the equivalent functionality written in C.

\code
uint16_t
crc16_update(uint16_t crc, uint8_t a)
{
int i;

crc ^= a;
for (i = 0; i < 8; ++i)
{
    if (crc & 1)
    crc = (crc >> 1) ^ 0xA001;
    else
    crc = (crc >> 1);
}

return crc;
}

Edited February 16 by uni

[uni 0]

Надо добавить, что алгоритм не только полиномом отличаются между собой, но и порядком работы с битами. В результате чего могут применятся те же, но инвертированные полиномы (0xA001 <-> 0x8005. 0x1021 <-> 0x8408).

Код на асме для avr в avrlibc не содержит переходов, насколько я вижу, поэтому это не двойной цикл. Теоретически он должен быть быстрее обсуждаемой в теме реализации, но не ясно почему он на стандартной строке показал другой результат.

Edited February 16 by uni

[uni 0]

Для полинома 0x1021 теперь уже 4 варианта: https://godbolt.org/z/ja9Lwq

Для проверки используется строка "123456789", которая имеет crc = 0x29B1.

Для avr8 чуда не произошло, но алгоритм GetCrc16Optim() оказался быстрее моего самого первого варианта и быстрее двойного цикла:

Table - 13.9 мкс (таблица 512 байт)
Optim - 22.9 мкс (без таблицы)
Simple - 24.6 мкс (без таблицы)
Cycle - 51.3 мкс (без таблицы)

Edited February 16 by uni

[uni 0]

В 14.02.2020 в 19:05, demiurg_spb сказал:

Интересно было бы сравнить с Вашим решением по скорости и по объёму кода.

Попробовал ещё раз. Видимо что-то не так сделал в первый и был не внимателен. Теперь всё сошлось, код прилагаю.

Итак, полином 0xA001, CRC16/MODBUS, результат для строки "123456789" равен 0#4B37. Для ATmega16 @ 16 МГц имеем:

Table - 12.9 мкс (таблица 512 байт)
Optim - 17.3 мкс (без таблицы)
Simple - 20.0 мкс (без таблицы)
Cycle - 52.4 мкс (без таблицы)

Т.е. алгоритм из библиотеки avrlibc действительно быстрее и самый близкий по времени к табличному методу расчёта.

crc16-modbus.pdf

Edited February 16 by uni

[demiurg_spb 0]

16 hours ago, uni said:

Т.е. алгоритм из библиотеки avrlibc действительно быстрее и самый близкий по времени к табличному методу расчёта.

Этого я и ожидал)

Спасибо!

[AHTOXA 0]

Без данных по размеру кода в тестах эти результаты мало о чём говорят. А то может, этот Optim кода больше расходует, чем табличный метод :-)

[uni 0]

Это очень просто прикинуть для avr8. Судя по картинке с кодом для этого метода там используется около 45 инструкций. Это 90 байт для этой архитектуры, что значительно меньше размера таблицы и обслуживающего его кода. Этот метод вполне может называться оптимальным для avr8.

В avr почти все инструкции (опкоды) двухбайтовые, кроме некоторых исключений.

[uni 0]

Функция Сrc16Optim(): 36 команд или 72 байта.

[esaulenka 0]

Чуток не в тему.

 

Господа, а есть ли способ посчитать CRC8 за несколько ксоров-сдвигов по аналогии с "Оптимизированный расчёт CRC-16 CCITT на языке Си, полином 0x8408 " из викибукс ?

[Baser 0]

CRC Polynomial a^8 + a^5 + a^4 + 1

uint8_t CRC8 (uint8_t data, uint8_t crc)
{
uint8_t i = data ^ crc;
crc = 0;
if (i & 0x01) crc ^= 0x5e;
if (i & 0x02) crc ^= 0xbc;
if (i & 0x04) crc ^= 0x61;
if (i & 0x08) crc ^= 0xc2;
if (i & 0x10) crc ^= 0x9d;
if (i & 0x20) crc ^= 0x23;
if (i & 0x40) crc ^= 0x46;
if (i & 0x80) crc ^= 0x8c;
return crc;
}

Но это не намного короче...

[Сергей Борщ 0]

7 часов назад, esaulenka сказал:

CRC8

Который именно? Там же куча разных полиномов, два направления сдвига, может быть инверсия данных или результата...

Вот тут есть решение для двух разных вариантов CRC8 и описание, как вывести для любого полинома любой разрядности.

[esaulenka 0]

21 hours ago, Baser said:

if (i & 0x01) crc ^= 0x5e;

Ага, спасибо, такой способ я освоил (собственно, его в этом топике и обсуждали).

 

16 hours ago, Сергей Борщ said:

Вот тут есть решение

Спасибо большое, надо будет покурить. Сходу непонятно.

 

16 hours ago, Сергей Борщ said:

Который именно?

Сразу не обозначил, извините. Мне для внутреннего хранилища настроек надо было, так что без разницы.

Но что-то я посмотрел-посмотрел на это всё, и выкинул поле checksum из заголовка.