CRC-5 обнаружил в проекте cgminer в ужасной реализации. Вычисления производятся по битам и далеко не самым оптимальным образом. Решил разобраться, почему и что это вообще за CRC такой. Из кода выяснил, что алгоритм похоже использует полином x^5+x^2+1(0x05). В таблицах нашел алгоритм CRC-5/USB с полиномом 0x05. Это тот же полином, только не ясно, как сделать алгоритм одинаково эффективно работающий с байтами и битами. В коде встречаются варианты применения алгоритма как к битовым строкам так и байтам. Решение такое: расчитать таблицу умножения для полинома и использовать табличные подстановки. Чтобы "подобрать" алгоритм для CRC5 сначала реализовал расчет CRC-5/USB, потому что для него есть точное определение в базе и прверочные числа.
- CRC-5/USB
- width=5 poly=0x05 init=0x1f refin=true refout=true xorout=0x1F check=0x19 name="CRC-5/USB"
- CRC-5/BITMAIN
- width=5 poly=0x05 init=0x1f refin=false refout=false xorout=0x0 check=0x0F name="CRC-5/BITMAIN"
Формат записи характеристик алгоритма: разрядность, полином, маска инициализации, отражение бит на входе и выходе алгоритма, маска инверсии на выходе и контрольная сумма от строки "123456789". Данных по CRC-5/BITMAIN не было, я даже не был уверен что это возможно.
Сразу не получилось подобрать алгоритм, потому что неясно было, как выполнять выравнивание данных при пяти битах. Я начал с реализации табличного алгоритма для CRC-5/USB.
Сделал алгоритм с табицей 16 элементов (умножение на 4 бита).
Таблица подстановки для CRC-5/USB
0x00, 0x16, 0x05, 0x13,
0x0A, 0x1C, 0x0F, 0x19,
0x14, 0x02, 0x11, 0x07,
0x1E, 0x08, 0x1B, 0x0D,
Структура алгоритма точно такая же, как и для CRC-8.
uint8_t CRC5USB_update(uint8_t crc, uint8_t data)
{
crc = crc ^ data;
crc = (crc>>4) CRC5USB_Lookup4[crc&0xF];
crc = (crc>>4) CRC5USB_Lookup4[crc&0xF];
return crc&0x1F;
}
Если таблица имеет размер 256 элементов, алгоритм еще упроститься
uint8_t CRC5USB_update(uint8_t crc, uint8_t data)
{
crc = crc ^ data;
crc = CRC5USB_Lookup[crc];
return crc;
}
Для CRC-5/BITMAIN сгенерировал таблицу умножения 256 элементов (умножение на 8 бит). В таблице и в алгоритме число 5 бит выравниывается по старшему разряду.
Алгоритм работает над байтами,
uint8_t CRC5_update(uint8_t crc, uint8_t data)
{
crc = (crc<<3) ^ data;
crc = CRC5_Lookup[crc];
return (crc>>3);
}
Для реализации в микроконтроллере мы обычно используем маленькие табицы по 16 элементов
uint8_t CRC5_update(uint8_t crc, uint8_t data)
{
crc = (crc<<3) ^ data;
crc = (crc<<4) ^ CRC5_Lookup[crc>>4];
crc = (crc<<4) ^ CRC5_Lookup[crc>>4];
return (crc>>3);
}
Алгоритм CRC можно дробить на любое число бит 1...8.
// шаг алгоритма для 1..8 бит
crc = crc ^ data;
crc = (crc << bits) ^ CRC5_Lookup[crc>>(8-bits)];
Таким образом можно посчитать CRC5, если число бит в битовой строке не кратно восьми. Данные при этом должны выравниваться по старшему биту.
Таблица подстановки для CRC5
0x00, 0x28, 0x50, 0x78, 0xA0, 0x88, 0xF0, 0xD8,
0x68, 0x40, 0x38, 0x10, 0xC8, 0xE0, 0x98, 0xB0,
0xD0, 0xF8, 0x80, 0xA8, 0x70, 0x58, 0x20, 0x08,
0xB8, 0x90, 0xE8, 0xC0, 0x18, 0x30, 0x48, 0x60,
0x88, 0xA0, 0xD8, 0xF0, 0x28, 0x00, 0x78, 0x50,
0xE0, 0xC8, 0xB0, 0x98, 0x40, 0x68, 0x10, 0x38,
0x58, 0x70, 0x08, 0x20, 0xF8, 0xD0, 0xA8, 0x80,
0x30, 0x18, 0x60, 0x48, 0x90, 0xB8, 0xC0, 0xE8,
0x38, 0x10, 0x68, 0x40, 0x98, 0xB0, 0xC8, 0xE0,
0x50, 0x78, 0x00, 0x28, 0xF0, 0xD8, 0xA0, 0x88,
0xE8, 0xC0, 0xB8, 0x90, 0x48, 0x60, 0x18, 0x30,
0x80, 0xA8, 0xD0, 0xF8, 0x20, 0x08, 0x70, 0x58,
0xB0, 0x98, 0xE0, 0xC8, 0x10, 0x38, 0x40, 0x68,
0xD8, 0xF0, 0x88, 0xA0, 0x78, 0x50, 0x28, 0x00,
0x60, 0x48, 0x30, 0x18, 0xC0, 0xE8, 0x90, 0xB8,
0x08, 0x20, 0x58, 0x70, 0xA8, 0x80, 0xF8, 0xD0,
0x70, 0x58, 0x20, 0x08, 0xD0, 0xF8, 0x80, 0xA8,
0x18, 0x30, 0x48, 0x60, 0xB8, 0x90, 0xE8, 0xC0,
0xA0, 0x88, 0xF0, 0xD8, 0x00, 0x28, 0x50, 0x78,
0xC8, 0xE0, 0x98, 0xB0, 0x68, 0x40, 0x38, 0x10,
0xF8, 0xD0, 0xA8, 0x80, 0x58, 0x70, 0x08, 0x20,
0x90, 0xB8, 0xC0, 0xE8, 0x30, 0x18, 0x60, 0x48,
0x28, 0x00, 0x78, 0x50, 0x88, 0xA0, 0xD8, 0xF0,
0x40, 0x68, 0x10, 0x38, 0xE0, 0xC8, 0xB0, 0x98,
0x48, 0x60, 0x18, 0x30, 0xE8, 0xC0, 0xB8, 0x90,
0x20, 0x08, 0x70, 0x58, 0x80, 0xA8, 0xD0, 0xF8,
0x98, 0xB0, 0xC8, 0xE0, 0x38, 0x10, 0x68, 0x40,
0xF0, 0xD8, 0xA0, 0x88, 0x50, 0x78, 0x00, 0x28,
0xC0, 0xE8, 0x90, 0xB8, 0x60, 0x48, 0x30, 0x18,
0xA8, 0x80, 0xF8, 0xD0, 0x08, 0x20, 0x58, 0x70,
0x10, 0x38, 0x40, 0x68, 0xB0, 0x98, 0xE0, 0xC8,
0x78, 0x50, 0x28, 0x00, 0xD8, 0xF0, 0x88, 0xA0,
