Вычисление CRC-кода

CRC-8

Для вычисления CRC-8 используются первые 7 байт (56 бит). Основу составляет полином:

CRC-8 = X8+X5+X4+1

Блок-схема алгоритма вычисления CRC-8.

Алгоритм использует операции сдвига и «исключающего или».

Пример первый: ассемблер MCS-51. Подпрограмма расчета CRC.
Эта подпрограмма использует одну ячейку памяти CRC для хранения результата. Перед первым вызовом эту ячейку необходимо обнулить. В аккумуляторе - очередной принятый или передаваемый байт. После того, как все байты переданы/приняты в ячейке CRC получится контрольная сумма. Подпрограмма не портит никаких регистров, кроме регистра состояния.

DO_CRC:
PUSH ACC ; сохраняем аккумулятор
PUSH B ; сохраняем регистр В
PUSH ACC ; сохраняем байт данных
MOV B, #8 ; кол-во битов (счетчик циклов)
CRC_LOOP: 
XRL A, CRC ; XOR с предыдущим значением контрольной суммы
RRC A ; сдвиг вправо через флаг переноса
MOV A, CRC ; берем последнее значение CRC
JNC ZERO ; переход, если не было переноса
XRL A, #18H ; обновляем значение CRC путем XOR с константой
ZERO: 
RRC A ; снова сдвигаем CRC
MOV CRC, A ; сохраняем новое значение CRC
POP ACC ; восстанавливаем байт данных
RR A ; циклически сдвигаем вправо
PUSH ACC ; снова сохраняем значение
DJNZ B, CRC_LOOP ; повторяем цикл 8 раз (для каждого бита)
POP ACC ; очищаем стек
POP B ; восстанавливаем прежние значения регистров из стека
POP ACC 
RET ; завершение процедуры

Пример второй: процедура на языке Pascal с использованием табличных вычисле-ний CRC. Как и предыдущая, эта процедура должны быть вызвана для каждого передаваемого/принимаемого байта, а перед первым использованием переменная CRC должна быть обнулена.

Var
 CRC : Byte; {переменная-результат расчета контрольной суммы}

Procedure Do_CRC(X: Byte);
{Эта процедура вычисляет контрольную сумму по стандартному алгоритму для устройств 1-Wire и накапливает результат в глобальной переменной CRC}

Const
{Нижеследующая таблица содержит заранее вычисленные сигнатуры, используемые для быстрого расчета CRC}

Table : Array[0..255] of Byte = ( 0, 94, 188, 226, 97, 63, 221, 131, 194, 156, 126, 32, 163, 253, 31, 65,
157, 195, 33, 127, 252, 162, 64, 30, 95, 1, 227, 189, 62, 96, 130, 220,
35, 125, 159, 193, 66, 28, 254, 160, 225, 191, 93, 3, 128, 222, 60, 98,
190, 224, 2, 92, 223, 129, 99, 61, 124, 34, 192, 158, 29, 67, 161, 255,
70, 24, 250, 164, 39, 121, 155, 197, 132, 218, 56, 102, 229, 187, 89, 7,
219, 133, 103, 57, 186, 228, 6, 88, 25, 71, 165, 251, 120, 38, 196, 154,
101, 59, 217, 135, 4, 90, 184, 230, 167, 249, 27, 69, 198, 152, 122, 36,
248, 166, 68, 26, 153, 199, 37, 123, 58, 100, 134, 216, 91, 5, 231, 185,
140, 210, 48, 110, 237, 179, 81, 15, 78, 16, 242, 172, 47, 113, 147,205,
17, 79, 173, 243, 112, 46, 204, 146, 211, 141, 111, 49, 178, 236, 14, 80,
175, 241, 19, 77, 206, 144, 114, 44, 109, 51, 209, 143, 12, 82, 176, 238,
50, 108, 142, 208, 83, 13, 239, 177, 240, 174, 76, 18, 145, 207, 45, 115,
202, 148, 118, 40, 171, 245, 23, 73, 8, 86, 180, 234, 105, 55, 213, 139,
87, 9, 235, 181, 54, 104, 138, 212, 149, 203, 41, 119, 244, 170, 72, 22,
233, 183, 85, 11, 136, 214, 52, 106, 43, 117, 151, 201, 74, 20, 246, 168,
116, 42, 200, 150, 21, 75, 169, 247, 182, 232, 10, 84, 215, 137, 107, 53);

Begin
 CRC := Table[CRC xor X];
{Расчет заключается в простом извлечении результата из таблицы}
End;

.def wiretemp = r22 ; регистр под нужды 1-wire 
.def wireres = r2 ; обязательно из числа r0...r15 

;********************************************************************* 
crc8:
; выполняет подсчет CRC по алгоритму 1-Wire
; вход: r0 - считанный байт
; выход: CRC - содержит подсчитанную сумму
; портит: регистр Z
; примечание: перед первым вызовом CRC необходимо обнулить

 push r0
 ldi wiretemp, 8
 mov wireres,wiretemp
r1w_loop_crc:
 lds wiretemp, CRC
 eor r0, wiretemp
 ror r0
 mov r0, wiretemp
 brcc zero
 ldi wiretemp, 0x18
 eor r0, wiretemp
zero:
 ror r0
 sts CRC, r0
 pop r0
 ; 4 следующие команды делают циклический сдвиг r0
 push r0
 ror r0
 pop r0
 ror r0
 ; сдвиг закончен - очень удобно, не правда ли?!
 push r0
 dec wireres
 brne r1w_loop_crc
 pop r0
 lds r0, CRC

 ret

...
 .dseg
CRC: .byte 1 ; расчитываемая контр.сумма

Описанный ниже алгоритм используется для вычисления двух разных CRC-кодов.

Результатом вычисления CRC может быть значение 0 или “seed”.

Последовательность вычислений следующая:
Нахождение логического исключающего ИЛИ между младшим битом CRC и младшим битом данных.
Если результат равен 0, то:
a. Сдвиг вправо CRC.
Если результат равен 1:
a. Поиск нового значения CRC путем вычисления логического исключающего ИЛИ между CRC и полиномом CRC.
b. Сдвиг вправо CRC.
c. Установка старшего бита CRC к 1.
Сдвиг вправо данных.
Повтор данной последовательности 8 раз.

Данный алгоритм может использоваться для вычисления, как CRC8, так и CRC16. Отличие состоит только в разрядности сдвигового регистра (8 разрядов для CRC8, 16 разрядов для CRC16) и значении полинома. Данное значение моделируется схемой из логических элементов исключающее ИЛИ. Значение полинома равно 18h для CRC8 и 4002h для CRC16.

Алгоритмы реализованы для поиска значения CRC для одного байта при однократном выполнении, но CRC “seed” размещается в качестве аргумента в процедуры CRC. Таким образом, результат одной операции CRC может быть указан в следующий раз вместе со следующим байтом и в результате вычисляется CRC от произвольного количества байт.

Проверка CRC для 64-разрядного идентификатора реализуется OWI_CheckRomCRC. Она вычисляет значение CRC8 первых 56 бит, а затем сравнивает его с последними 8 битами идентификатора.