Отправлено Amateur 28 февраля 2003 г. 15:29 В ответ на: Коллеги! Я думаю многие знают алгоритм вычисления CRC. Вот сижу разбираюсь с чужой прогой(+) отправлено bialix 28 февраля 2003 г. 13:44

Для вычисления остатка от деления на полином (CRC) наиболее часто используются два алгоритма SIMPLE и TABLE, подробно описанные доктором Росс Н. Вильямсом (Dr Ross N. Williams) в статье “A PAINLESS GUIDE TO CRC ERROR DETECTION ALGORITHMS” на вебсайте http://www.ross.net/crc/. Недостатки этих алгоритма (для SIMPLE – большое время вычисления, для TABLE — большой объем памяти) особенно проявляются при выполнении вычислений с использованием микропроцессоров, имеющих существенные ограничения, как по объему памяти программ, так и по быстродействию. Ниже рассматривается еще один алгоритм вычисления CRC, условно называемый OPTIMAL. Для некоторых полином OPTIMAL обеспечивает быстродействие расчета больше, чем TABLE, при этом объем используемой памяти меньше, чем при использовании SIMPLE. Алгоритм OPTIMAL представляет собой оптимизированный для байтных вычислений алгоритм SIMPLE. Покажем применение этого алгоритма вычисления на примере вычисления CRC-16/CCITT.

1-й шаг: к старшему байту CRC добавляем очередной байт
I15 I14 I13 I12 I11 I10 I9 I8 I7 I6 I5 I4 I3 I2 I1 I0
D7 D6 D5 D4 D3 D2 D1 D0
I’15 I’14 I’13 I’12 I’11 I’10 I’9 I’8 I7 I6 I5 I4 I3 I2 I1 I0
2-й шаг: Дописываем справа нулевой байт
I’15 I’14 I’13 I’12 I’11 I’10 I’9 I’8 I7 I6 I5 I4 I3 I2 I1 I0 0 0 0 0 0 0 0 0
3-й шаг: сдвигам вправо на 1 бит полином. Проанализируем как будет выполняться деление. Если бит I’15 = 1, то выполняется вычитание полинома, если I’15 = 0, то вычитание не выполняется. Поскольку мы говорим об арифметике без переноса, то можно утверждать:
- для данного полинома разряды I’14-I’12, I’10-I5, I3-I0, 7-0 на этом шаге не изменятся;
- разряды I’15, I’11, I4, 7 не изменятся если I’15 = 0, и будут проинвертированы, если I’15 = 1. Это равносильно выполнению над этими битами операции сложения с битом I’15 (I’11 Е I’15; I4 Е I’15; 7 Е I’15).
7 6 5 4 3 2 1 0
I’15 I’14 I’13 I’12 I’11 I’10 I’9 I’8 I7 I6 I5 I4 I3 I2 I1 I0 0 0 0 0 0 0 0 0
1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 1
I’15 I’15 I’15 I’15
Выполняя сдвиг полинома вправо и выполняя аналогичные рассуждения получаем:
7 6 5 4 3 2 1 0
I’15 I’14 I’13 I’12 I’11 I’10 I’9 I’8 I7 I6 I5 I4 I3 I2 I1 I0 0 0 0 0 0 0 0 0
I’15 I’15 I’15
I’14 I’14 I’14
I’13 I’13 I’13
I’12 I’12 I’12
I’11 I’11 I’11
I’15 I’15 I’15
I’10 I’10 I’10
I’14 I’14 I’14
I’9 I’9 I’9
I’13 I’13 I’13
I’8 I’8 I’8
I’12 I’12 I’12

Выполняя группировку получаем:

1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 1
I’15 I’14 I’13 I’12 I’11 I’10 I’9 I’8 I7 I6 I5 I4 I3 I2 I1 I0 0 0 0 0 0 0 0 0
I’15 I’14 I’13 I’12 I’11 I’10 I’9 I’8
I’15 I’14 I’13 I’12
I’15 I’14 I’13 I’12 I’11 I’10 I’9 I’8
I’15 I’14 I’13 I’12
I’15 I’14 I’13 I’12 I’11 I’10 I’9 I’8
I’15 I’14 I’13 I’12
Если принять:
Е I’15 I’14 I’13 I’12 I’11 I’10 I’9 I’8
I’15 I’14 I’13 I’12
A7 A6 A5 A4 A3 A2 A1 A0
То получим:
I7 I6 I5 I4 I3 I2 I1 I0 0 0 0 0 0 0 0 0
A7 A6 A5 A4 A3 A2 A1 A0
A7 A6 A5 A4 A3 A2 A1 A0
A3 A2 A1 A0

void crc16_ccitt(unsigned char data, unsigned short & crc)
{
unsigned short a, d = crc;
d ^= (unsigned short)((data<<8) & 0xff00);
a = (unsigned short)((d^(d>>4)) & 0xff00);
crc = (unsigned short)(d<<8);
crc ^= (unsigned short)(a>>8);
crc ^= (unsigned short)(a>>3);
crc ^= (unsigned short)(a<<4);
}