uni 0 Posted February 16, 2020 (edited) · Report post В 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, 2020 by uni Quote Ответить с цитированием Share this post Link to post Share on other sites
uni 0 Posted February 16, 2020 (edited) · Report post Надо добавить, что алгоритм не только полиномом отличаются между собой, но и порядком работы с битами. В результате чего могут применятся те же, но инвертированные полиномы (0xA001 <-> 0x8005. 0x1021 <-> 0x8408). Код на асме для avr в avrlibc не содержит переходов, насколько я вижу, поэтому это не двойной цикл. Теоретически он должен быть быстрее обсуждаемой в теме реализации, но не ясно почему он на стандартной строке показал другой результат. Edited February 16, 2020 by uni Quote Ответить с цитированием Share this post Link to post Share on other sites
uni 0 Posted February 16, 2020 (edited) · Report post Для полинома 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, 2020 by uni Quote Ответить с цитированием Share this post Link to post Share on other sites
uni 0 Posted February 16, 2020 (edited) · Report post В 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, 2020 by uni Quote Ответить с цитированием Share this post Link to post Share on other sites
demiurg_spb 0 Posted February 17, 2020 · Report post 16 hours ago, uni said: Т.е. алгоритм из библиотеки avrlibc действительно быстрее и самый близкий по времени к табличному методу расчёта. Этого я и ожидал) Спасибо! Quote Ответить с цитированием Share this post Link to post Share on other sites
AHTOXA 0 Posted February 17, 2020 · Report post Без данных по размеру кода в тестах эти результаты мало о чём говорят. А то может, этот Optim кода больше расходует, чем табличный метод :-) Quote Ответить с цитированием Share this post Link to post Share on other sites
uni 0 Posted February 18, 2020 · Report post Это очень просто прикинуть для avr8. Судя по картинке с кодом для этого метода там используется около 45 инструкций. Это 90 байт для этой архитектуры, что значительно меньше размера таблицы и обслуживающего его кода. Этот метод вполне может называться оптимальным для avr8. В avr почти все инструкции (опкоды) двухбайтовые, кроме некоторых исключений. Quote Ответить с цитированием Share this post Link to post Share on other sites
uni 0 Posted February 18, 2020 · Report post Функция Сrc16Optim(): 36 команд или 72 байта. Quote Ответить с цитированием Share this post Link to post Share on other sites
esaulenka 0 Posted June 4, 2020 · Report post Чуток не в тему. Господа, а есть ли способ посчитать CRC8 за несколько ксоров-сдвигов по аналогии с "Оптимизированный расчёт CRC-16 CCITT на языке Си, полином 0x8408 " из викибукс ? Quote Ответить с цитированием Share this post Link to post Share on other sites
Baser 0 Posted June 4, 2020 · Report post 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; } Но это не намного короче... Quote Ответить с цитированием Share this post Link to post Share on other sites
Сергей Борщ 0 Posted June 4, 2020 · Report post 7 часов назад, esaulenka сказал: CRC8 Который именно? Там же куча разных полиномов, два направления сдвига, может быть инверсия данных или результата... Вот тут есть решение для двух разных вариантов CRC8 и описание, как вывести для любого полинома любой разрядности. Quote Ответить с цитированием Share this post Link to post Share on other sites
esaulenka 0 Posted June 5, 2020 · Report post 21 hours ago, Baser said: if (i & 0x01) crc ^= 0x5e; Ага, спасибо, такой способ я освоил (собственно, его в этом топике и обсуждали). 16 hours ago, Сергей Борщ said: Вот тут есть решение Спасибо большое, надо будет покурить. Сходу непонятно. 16 hours ago, Сергей Борщ said: Который именно? Сразу не обозначил, извините. Мне для внутреннего хранилища настроек надо было, так что без разницы. Но что-то я посмотрел-посмотрел на это всё, и выкинул поле checksum из заголовка. Quote Ответить с цитированием Share this post Link to post Share on other sites