1. Прямой табличный алгоритм crc16

Необходимость дополнения исходной строки завершающими нулевыми байтами представляет большое неудобство при реализации общей схемы табличного алгоритма. Поэтому на практике используют другую схему вычисления CRC, не требующую завершения исходного сообщения нулевыми байтами. В этой схеме очередной байт исходной строки объединяется операцией XOR со старшим байтом регистра, выдвинутым с левой стороны этого регистра.

Полученное в результате объединения значение используется в качестве индекса для доступа к CRC-таблице. Извлекаемое из CRC-таблицы значение объединяется операцией XOR с содержимым регистра. Описанный алгоритм называют прямым табличным алгоритмом.

Рис. 12.6. Схема вычислений CRC с использованием прямого табличного алгоритма

На схеме вычислений CRC с использованием прямого табличного алгоритма цифрами обозначена последовательность шагов вычисления CRC.

1. Выдвижение старшего байта регистра АХ в байтовую ячейку.

2. Выполнение операции XOR над выдвинутым на шаге 1 в байтовую ячейку старшим байтом регистра АХ и очередным байтом исходной строки.

3. Полученное на шаге 2 значение используется в качестве индекса для доступа к элементу CRC-таблицы.

4. Извлеченное из CRC-таблицы значение объединяется по XOR со значением в регистре АХ.

5. Результат выполнения на шаге 4 операции XOR помещается обратно в регистр АХ.

После обработки последнего байта исходной строки регистр АХ содержит значение CRC.

Все существующие алгоритмы вычисления CRC являются, по сути, различными модификациями описанного выше табличного алгоритма. Эти модификации преследуют разные цели, перечислим некоторые из них:

• переход от цикла по всем битам к циклу по большим порциям данных – байтам, словам и т. д.;

• повышение разрядности порождающего полинома;

• отражение особенностей функционирования аппаратуры передачи данных (наличие этой цели обусловлено тем, что микросхемы, поддерживающие работу последовательного порта компьютера, передачу байта начинают с его младших битов, поэтому описанные ниже алгоритмы расчета CRC, учитывающие эту особенность, называются зеркальными).

Алгоритмы вычисления CRC получили свое закрепление в некоторых стандартах. Перечислим отличительные особенности основных алгоритмов вычисления CRC. Итак, основные алгоритмы вычисления CRC различаются:

• по значению и степени порождающего полинома, при этом значение полинома обычно указывается без ведущей единицы в старшем разряде;

• по начальному содержимому регистра, в котором формируется значение CRC;

• по тому, производится ли обращение битов каждого байта перед его обработкой;

• по способу прохода байтов через регистр – способ может быть косвенным или прямым;

• по тому, производится ли обращение конечного результата;

• по конечному значению, с которым производится объединение по XOR результата вычисления CRC.

После появления 32-разрядных микропроцессоров наибольшей популярностью стали пользоваться 32-разрядные алгоритмы вычисления CRC. В различных источниках рассматривают два типа таких алгоритмов – прямой и зеркальный. Рассмотрим их конкретные реализации, рекомендуемые стандартами.

Как и любой табличный алгоритм, табличный алгоритм вычисления CRC32 требует задания CRC-таблицы. Ее можно задать в программе статически, явно прописав значения элементов таблицы в сегменте кода, или динамически, вычислив значения элементов таблицы перед началом расчета CRC.

В заключение обсудим "зеркальный" вариант табличного алгоритма – алгоритм CRC32 (V.42 МККТТ). Этот вариант вычисления CRC обязан своим возникновением существованию последовательного интерфейса, который посылает биты, начиная с наименее значимого (бит 0) и заканчивая самым старшим (бит 7), то есть в обратном порядке. В "зеркальном" регистре все биты отражены относительно центра. Например, 10111011001 есть отражение значения 10011011101.

Вместо того чтобы менять местами биты перед их обработкой, можно зеркально отразить все значения и действия, участвующие в прямом алгоритме. При этом направление расчетов поменяется – байты теперь будут сдвигаться вправо, полином 04clldb7h зеркально отразится относительно его центра, в результате получится значение 0edb88320h. СRС32-таблица будет зеркальным отражением аналогичной таблицы для прямого алгоритма (рис. 12.7).

Рис. 12.7. Схема "Зеркального" табличного алгоритма

Для зеркального алгоритма вычисления CRC32 процесс вычисления такой же, за исключением порядка – сдвиги и заполнение регистра осуществляются вправо.

Этот вариант работы алгоритма вычисления CRC32 удобен тем, что не нужно знать длину собственно исходной последовательности (без значения CRC). Достаточно просто обработать весь входной поток, не различая в строке завершающую ее подстроку с CRC. Далее необходимо сравнить содержимое регистра ЕАХ с 6b202ca2h. Если эти значения равны, значит, исходная последовательность нарушена не была. Для получения собственно строки достаточно отбросить последние 4 байта сообщения, полученного приемником.