Jump to content

    
Sign in to follow this  
uni

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

Recommended Posts

В 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;
}

2020-02-16_10-15-02.png

Edited by uni

Share this post


Link to post
Share on other sites

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

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

Edited by uni

Share this post


Link to post
Share on other sites

Для полинома 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 by uni

Share this post


Link to post
Share on other sites
В 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 by uni

Share this post


Link to post
Share on other sites
16 hours ago, uni said:

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

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

Спасибо!

Share this post


Link to post
Share on other sites

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

Share this post


Link to post
Share on other sites

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

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

Share this post


Link to post
Share on other sites

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

 

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

Share this post


Link to post
Share on other sites

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;
}

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

Share this post


Link to post
Share on other sites
7 часов назад, esaulenka сказал:

CRC8

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

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

Share this post


Link to post
Share on other sites
21 hours ago, Baser said:

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

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

 

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

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

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

 

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

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

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

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

Share this post


Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Sign in to follow this