CRC-алгоритм решает задачу обнаружения ошибок, возникающих при передаче сообщения. CRC-алгоритм вычисляет и добавляет в конец сообщения так называемую контрольную сумму (КС).
При 2-байтовой длине регистра, хранящего КС, мы имеем дело с алгоритмом CRC-16, при 4-байтовой - с алгоритмом CRC-32.
Порядок обработки сообщения следующий:
Очевидно, что это не всегда так:
Отсюда два вывода:
В качестве КС можно взять, например, n-битовый остаток от деления n-битового представления сообщения на n-битовое значение (n = 8, 16, 32 ...). Битовое представление сообщения получается путем замены каждого его символа на его битовое значение. Так, 8-битовое представление строки abcd будет следующим:
01100001 01100010 01100011 01100100
Его можно получить, употребив следующий написанный на Фортране код:
character(*), parameter :: st = 'abcd'
integer(2) i
do i = 1, len(st)
print '(b8)', ichar(st(i:i))
end do
end
В do-цикле берется числовой код символа и выводится его битовое представление.
Если в качестве делителя взять число
p = 00110001 (p = 31 в системе счислений по основанию 16; p = 49 в системе счислений по основанию 10), то 1-байтовый остаток от деления сообщения на p будет равен
00000101.
Результат можно получить, употребив функцию Mod, на стандартном Windows-калькуляторе, имеющем вид Программист.
Однако приведенный способ вычисления КС не вполне надежен [1], поскольку вероятность получения поврежденного сообщения с той же КС, что и в исходном сообщении, весьма ощутима.
В CRC-алгоритме реализуется двоичная арифметика без переносов, которая иллюстрируется следующими примерами:
а)
10011011
+
11001010
01010001
б)
10011011
-
11001010
01010001
При сложении битов употребляются следующие правила:
0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 0 (без переноса)
а при вычитании - следующие:
0 - 0 = 0
0 - 1 = 1 (зацикливание)
1 - 0 = 1
1 - 1 = 0
В программировании подобные правила реализуются битовой операцией Исключающее ИЛИ (в Фортране IEOR).
Иные детали CRC-арифметики можно посмотреть, опять же, в [1].
Алгоритм CRC-16 вычисляет 2-байтовую КС сообщения, определяя ее как 2-байтовый остаток от деления сообщения на заданную величину. Деление выполняется по правилам двоичной арифметики без переносов.
Алгоритм CRC-16:
Входные данные:
сообщение st.
Параметры алгоритма (задаются в системе счисления по основанию 16):
делитель p = #1021;
исходное заполнение 2-байтового CRC-регистра (iCrc = #ffff), хранящего остаток от деления st на p.
Выходные данные:
iCrc - остаток от деления st на p.
Для осмысление алгоритма достаточно выполнить в столбик деление двоичного представления st на p, используя правила двоичной арифметики без переносов (см. снова [1]), и проанализировать порядок выполнения этой операции.
Далее приводятся Фортран и 1С-реализации CRC-алгоритма
Фортран-реализацию приведенного выше алгоритма запишем более компактно, не вводя некоторые промежуточные переменные:
character(*), parameter :: st = 'Test CRC-message'
integer(2), parameter :: p = #1021
integer(2) iCrc, ic, i
logical b
lenSt = len(st)
iCrc = #ffff
do i = 1, lenSt
iCrc = ieor(iCrc, isha(ichar(st(i:i)), 8))
do j = 0, 7
b = btest(iCrc, 15)
iCrc = isha(iCrc, 1)
if(b) iCrc = ieor(iCrc, p)
end do
end do
print '(a7, z4)', 'iCrc = ', iCrc
print '(a7, i4)', 'iCrc = ', iCrc
end
При st = 'Test CRC-message' имеем следующий результат:
iCrc = 625 (основание системы счисления 16)
iCrc = 1573 (основание системы счисления 10)
В 1С:Предприятие 8 на момент создания примера нет битовых операций. Кроме того, при преобразовании символа в код (функция кодСимвола) используется Unicode-кодировка, а не ASCII, как в Фортране (функция iChar).
Эти особенности учтены в нижеприводимом 1С-коде.
функция срс16(сб)
// Полином (делитель)
п = "0001000000100001";
// Инициализация СРС
срс = "1111111111111111";
д = стрДлина(сб);
для к = 1 по д цикл
с = сред(сб, к, 1);
б = символБиты(с);
если пустаяСтрока(б) тогда возврат б конецЕсли;
срс = и_или(срс, б);
для м = 1 по 8 цикл
т = лев(срс, 1) = "1";
срс = сред(срс, 2) + "0";
если т тогда срс = и_или(срс, п) конецЕсли;
конецЦикла;
конецЦикла;
// Возвращаем СРС как число в системе счисления по основанию 10
возврат битыЧисло10(срс);
конецФункции
// Преобразование символа в битовую строку
функция символБиты(с)
// Unicode-код символа
кс = кодСимвола(с);
б = "";
если кс > 255 и кс < 1040 тогда
сообщить("Плохой символ");
иначе
// Перевод кодов русских букв из Unicode в ASCII
если кс >= 1040 тогда кс = кс - 848 конецЕсли;
пока кс > 0 цикл
б = строка(кс % 2) + б;
кс = цел(кс / 2);
конецЦикла;
для к = 1 по 8 - стрДлина(б) цикл б = "0" + б конецЦикла;
// Получаем из 8-битового представления символа его 16-битовое представление
б = б + "00000000";
конецЕсли;
возврат б;
конецФункции
// Исключающее ИЛИ. А и Б - битовые строки одной длины
функция и_или(А, Б)
р = "";
д = стрДлина(А);
для к = 1 по д цикл р = р + ?(сред(А, к, 1) = сред(Б, к, 1), "0", "1") конецЦикла;
возврат р;
конецФункции
// Преобразование битовой строки в число в системе счисления по основанию 10
Функция битыЧисло10(стр)
ч10 = 0;
д = стрДлина(стр);
для к = 1 по д цикл ч10 = ч10 + ?(сред(стр, к, 1) = "1", pow(2, д - к), 0) конецЦикла;
возврат ч10;
КонецФункции
процедура кнопкаВыполнитьНажатие(кнопка)
очиститьСообщения();
сб = "Test CRC-message";
сообщить(срс16(сб));
// Напечатает
// 1573
конецПроцедуры
Для ускорения вычислений КС используются табличные реализации CRC-алгоритма. Кроме того, CRC-алгоритмы могут отличаться и другими параметрами, такими, как значение делителя, начальное значение CRC-регистра и пр. При выборе рабочего варианта CRC-алгоритма следует учитывать его быстродействие и качество (надежность).
1. Ross N. Williams. A painless guide to CRC error detection algorithms. Rocksoft™ Pty Ltd