Liv писал(а):А для CRC-8 это тоже выгоднее?
Прошу прощения за задержку с ответом, закрутило.
Увы, нет. По крайней мере, для 1-Wire
CRC8 содержит в полиноме столько же единичек, сколько и 16-битная CRC от xmodem, но ведь сама CRC вдвое короче и при прокручивании для такого быстрого способа набор сдвигов и xor-ов становится ну слишком большим. Так навскидку, развёрнутый канонический цикл займёт меньше места и будет выполняться быстрее.
Но есть ещё один способ, занимающий промежуточное положение между каноническим циклом и табличным вычислением и по скорости, и по месту. Используется две таблицы по шестнадцать вхождений и CRC вычисляется таблично для каждого полубайта отдельно.
Если обычную таблицу для байтового алгоритма таблицу из 256 вхождений записать "квадратно", 16*16, то можно заметить, что все значения в таблице есть xor соответствующего значения по вертикали из первой строки и по горизонтали из первого столбца.
Соответсвтенно, для того же далласа, берём две таблицы, в одной из которых сдублирована первая строка, в другой — первый столбец (если я нигде не ошибся в перебивании чисел из таблички в далласовской апноте).
Код: Выделить всё
uint8_t crctable_1w_lo[] = {
0, 94, 188, 226, 97, 63, 221, 131, 194, 156, 126, 32, 163, 253, 31, 65
};
uint8_t crctable_1w_hi[] = {
0, 157, 35, 190, 70, 219, 101, 248, 140, 17, 175, 50, 202, 233, 116
};
И обновление CRC для одного байта будет выглядеть так
Код: Выделить всё
uint8_t crc_1w_table_4(uint8_t crc, uint8_t data)
{
uint8_t index = crc ^ data;
return crctable_1w_lo[ index & 0x0F] ^ crctable_1w_hi[ index >> 4];
}
Будет оно ближе по скорости к циклу или к привычной табличке для целых байтов — зависит от архитектуры контроллера, разрядности его самого и CRC. Так навскидку для AVR при аккуратнов выписывании на асме (с выровненными на границу 16 байт полутаблицами) это будет раза в полтора быстрее, чем развёрнутый в линеечку цикл. А места займёт ощутимо меньше, чем полноразмерная таблица.
Может, когда-то разрожусь на статеечку на эту тему, а может и нет — в сети, вообще говоря, довольно много информации, а писатель статей из меня не такой хороший, как Вы.Лень в виде мании величия: «ты гений, зачем стараться?». В виде комплекса: «всё равно не выйдет, зачем упираться?». Как логика: «если достаточно, зачем знать и уметь больше?». Цель одна: остановить. Не любит тепло работающих мышц и шум работающего мозга.
