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