Статьи Королевства Дельфи
Контрольные суммы и CRC.
| й Парунов, дата публикации 18 февраля 2003г. |
Недавно возникла у меня тут потребность в контроле блоков информации. В памяти сразу всплыла магическая фраза "CRC". Вроде эта CRC бывает и 16-, и 32-битной (да хоть 512-битной, но это, пожалуй, перебор). И есть понятие "контрольная сумма". Вот об этом и поговорим, не углубляясь в теорию, а упирая на практическое применение.
Вообще говоря, задача стоит так: нам из нашей информации (назовём её блоком) нужно получить число, которое однозначно идентифицирует эту информацию (назовём его хэшем). Так как блоки большие, а число маленькое, ясно, что блоков, в том числе и такой же длины, дающих то же число, очень много, гораздо больше, чем атомов в Галактике. Зачем же тогда нужно такое число? Целей может быть две:
- Нужно опознать блок. Опознавать его по образцу неэффективно и часто бессмысленно, а вот по маленькому числу… При этом, естественно, желательно, чтобы числа получались "послучайнее" - то есть были равномерно размазаны в диапазоне от нуля до максимума. Мы сможем узнать "свой" блок, до некоторой степени быть уверены в том, что он никак (умышленно или случайно) не изменён, вычислив его хэш и сравнив с образцом.
- Нужно найти блок - есть ли он у нас уже, и где? Ясно, что при тупом сравнении всех блоков с новым можно состариться. А вычислить хэш и сравнить его с известными хэшами имеющихся блоков можно быстро.
Речь пойдёт о первом вопросе. Второй гораздо сложнее и неоднозначнее; если хотите разобраться в нём - смотрите информацию по поиску при помощи хэш-таблиц. Кстати, в большинстве случаев это наибыстрейший вариант поиска информации.
Контроль данных - вопрос древний и проработанный. Есть два основных его варианта:
- Контрольная пломба… ой, сумма. Байты (слова, двойные слова…) просто складываются, складываются по модулю 2, вычитаются в различных комбинациях. Например, складываем все байты (а лучше слова или вообще двойные слова) блока и получаем хэш. Этот метод исторически первый и самый быстрый.
- CRC. Менее быстрый (раз в шесть в случае 32 бит на Intel32), но более хаотичный метод. "Хаотичный" он потому, что при его вычислении применяется не только сложение, но и сдвиги регистров, что даёт возможность данному биту блока повлиять не на один-два-три бита хэша, а на многие, и очень быстро, таким образом, что для предсказания этого не существует математического аппарата - можно только поставить эксперимент.
