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