Идентификация исходной битовой последовательности
Вычисление контрольных сумм. В отличие от рассмотренных выше методов для метода контрольных сумм нет четкого определения алгоритма. Каждый разработчик трактует понятие контрольной суммы по-своему. В простейшем виде контрольная сумма – это арифметическая сумма двоичных значений контролируемого блока символов. Но этот метод обладает практически теми же недостатками, что и предыдущие, самый главный из которых – нечувствительность контрольной суммы к четному числу ошибок в одной колонке и самому порядку следования символов в блоке.
Контроль циклически избыточным кодом – CRC (Cyclical Redundancy Check). Это гораздо более мощный и широко используемый метод обнаружения ошибок передачи информации. Он обеспечивает обнаружение ошибок с вероятностью до 99%. Кроме того, этот метод обладает рядом других полезных моментов, которые могут найти свое воплощение в практических задачах. Рассмотрению этого метода и будет посвящено дальнейшее изложение.
Сама по себе аббревиатура "CRC" знакома многом пользователям компьютера, особенно тем, кому приходится часто переносить свои архивные файлы посредством дискеты. В один прекрасный день попытка распаковки архивного файла наверняка приводила к выводу на экран сообщения о том, что у этого файла какое-то неправильное значение CRC. Что же представляет собой это загадочное значение CRC, какую пользу можно извлечь из знаний о нем? В данном разделе мы постараемся с этим разобраться, тем более, что данная задача является хорошей возможностью очередной раз продемонстрировать возможности и преимущества ассемблера по обработке данных на уровне битов, строк битов, последовательности байт (в том числе и неопределенной длины).
CRC (Cyclic Redundancy Code) – последовательность бит, полученная по определенному алгоритму на основании другой (исходной) битовой последовательности. Главная особенность (и практическая значимость) значения CRC состоит в том, что оно однозначно идентифицирует исходную битовую последовательность и поэтому используется в различных протоколах связи, таких, как HDLC и ZMODEM, а также для проверки целостности блоков данных, передаваемых различными устройствами. В силу этих свойств алгоритм вычисления CRC часто реализуется на аппаратном уровне.
Если взять пример с архиватором, то его работа в общем случае заключается в следующем: архиватор упаковывает файлы в соответствии с некоторым алгоритмом архивации, вычисляя для каждого упаковываемого файла значение CRC. После этого заархивированные файлы могут множество раз копироваться, пересылаться по сети, в том числе с использованием электронной почты, и т. д. В процессе своих путешествий файл может столкнуться с различными неприятными воздействиями внешней среды, например, с неисправным дисководом, искажением его внутреннего содержимого во время передачи по сети и т. п.
Эти изменения не обязательно должны быть глобальными, они могут касаться всего одного бита. Когда приходит время, пользователь распаковывает архив, при этом архиватор в первую очередь проверяет целостность файлов в нем. Для этого архиватор опять по содержимому файла вычисляет его CRC и сравнивает полученное значение с тем значением CRC, которое было вычислено при упаковке файла. Если они равны, то считается, что целостность файла не была нарушена, и он распаковывается, в обратном случае, если новое и старое значения CRC не совпадают, то считается, что архивный файл поврежден, и процесс его распаковки завершается.
Необходимо отметить, что CRC не обязательно вычислять для больших массивов данных, каким является файл. Его можно вычислять и для отдельных строк текста и даже слов с целью организации простейшего контроля целостности и отождествления символьных (числовых) последовательностей. Более того, из рассмотрения ниже вы увидите, что алгоритм вычисления CRC, по сути, является еще одним методом хэширования, которые мы подробно рассматривали в разделе "Таблицы с вычисляемыми входами" главы 2. Таким образом, алгоритм вычисления CRC имеет много достоинств, которые могут найти применение в самых различных практических задачах.
Основная идея вычисления CRC заключается в следующем. Исходная последовательность байтов, которой могут быть и огромный файл, и текст размером несколько слов и даже символов, представляется единой последовательностью битов. Эта последовательность делится на некоторое фиксированное двоичное число. Интерес представляет остаток от этого деления, который и является значением CRC. Все, что теперь требуется, – это некоторым образом запомнить его и передать вместе с исходной последовательностью.
Приемник данной информации всегда может таким же образом выполнить деление и сравнить его остаток с исходным значением CRC. Если они равны, то считается, что исходное сообщение не повреждено, и т. д. Но этот лишь общая схема. Реальный алгоритм вычисления CRC использует особые правила арифметики, в соответствии с которыми производятся все вычисления, назовем их правилами CRC-арифметики. В силу принципиальной важности этих правил для нашего изложения коротко рассмотрим их отличия от правил обычной двоичной арифметики.