CRC

CRC (англ. Cyclic Redundance Checksum) — контрольная сумма некоторых произвольных данных. Некоторая цифра в заголовке файла, получаемая в результате замысловатой операции со всеми её значащими байтами(обычно последовательным сложением с прокруткой на каждом цикле по основанию 2, то есть домножением результата на 2 и добавлением единицы при переполнении). Сама по себе никакого информационного смысла не имеет, но обладает примечательным свойством — изменяться при любом изменении любого байта файла. Причём в зависимости от того, какого конкретно из них — по разному. Что даёт право операционной системе простым сравнением вычисленного значения со значением в заголовке решать — считать файл успешно прочитанным, или залупиться на носитель, с которого читает, стандартной системной табличкой c одноимённой гогой и кнопочками «Нафиг-Нефиг-Пофиг». А любым коммуникационным компонентам — делать то же самое с передаваемой информацией, решая, принять пакет как правильный, или перезапросить.

Таким образом является важным фактором в процессе проверки целостности информации на всех стадиях её хранения и передачи, поэтому встроена во многие компоненты операционной системы чуть менее чем полностью.

Имеет разрядность традиционно вдвое большую чем цифирки, над которыми вычисление производится, просто тупо за счёт того, чтобы камушку вычислять её было быстрее и проще базовыми командами ядра, не подключая к процессу математический сопроцессор(ALU), страничный контроллер ПДП и другую «тяжёлую артиллерию». Из-за чего код её вычисления на Ассемблере(любой разрядности) занимает всего 8 байт. Поэтому по видам камушков подразделяется на несколько видов:

Собственно CRC

Стандартная (8-битная) контрольная сумма. Разрядность 16 бит(тип переменной Word). Считается последовательным сложением каждого байта блока с домножением результата на 2 (то есть f_n+1=(f_n+x)*2+Z, где x-значение байта, а Z — значение флага переполнения после сложения и умножения на тупо «встал-не встал». И так в цикле, пока значащие байты блока не кончатся. Таким образом логика проста: Сложить и прокрутить. Потому контрольную сумму, собственно и называют циклической. Могёт принимать значения от 0 до 65535 (FFFFh).

CRC32

В сути то же самое, только поскольку 32-разрядному камушку удобнее проглатывать байты по 2, то и суммировать их быстрее за одну операцию сдвоенными. Соответственно складывая 16-битные значения. Конечная разрядность получается понятное дело эти самые 32 бита. Тип переменной Cardinal. Значение от 0 до 4294967295(FFFF:FFFFh)

CRC64

С появлением 64-разрядных процессоров соответственно и контрольная сумма «ещё немного подросла». Да, тут всё пока точно так же, как и в предыдущем случае. Только проглот по 4 байта и соответственно значения 32-битные, а сумма 64-битная. Максимальное значение 2⁶⁴−1(Ну его нафиг, считайте сами. FFFF:FFFF:FFFF:FFFFh это). Тип переменной по логике Word64, хотя во многих языках и размерности то такой(в отличии от Int64) нету!

MD4,MD5(ака CRC128)

Когда файлы стали большими, начали исчисляться в гигабайтах и перестали влезать даже на DVDшные болванки, и затрещал по швам при этом даже FAT32, выяснилось, что простым наращиванием разрядности контрольной суммы тут для обеспечения достаточно педантичной проверки достоверности уже не обойтись. И даже значение вариантов 1/2⁶⁴ начало повторяться не там, где надо, и давать сбои. Поэтому пришлось не только самому контрольному значению до 128 бит подрасти и обозваться уже хэшем(ибо ни в одну переменную эта хрень уже тупо не помещается), но и существенно усложниться алгоритму его вычисления. Кому интересно, как её вычислять — идите вы…на Педивикию. Там и формулы есть…

ОбCRCруемые обьекты

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

• Общая контрольная сумма — в файловой системе хранится в кластере каталога, в котором лежит файл в его атрибутах. В архивном файле — тот же конь. В телекоммуникационных средах обычно передаётся последней перед завершением сеанса передачи файла.
• Кластерная(блочная) контрольная сумма — Контрольная сумма одного кластера файла(минимального элемента файловой системы. Да, даже файл размером в 1 байт занимает на диске полный кластер. Вот такой вот эффективный у неё КПД). Хранится в таблице размещения файлов про каждый кластер отдельная. При перманентном фэйле кластер отстреливается(вешается ему маркер «Бэд блок»), а его содержимое пересохраняется в другое место(уж как прочлось) с подправкой CRC. При передаче данных превращается в пакетную и передаётся в заголовке пакета(вначале или в конце, зависимо от протокола передачи). Именно её сверкой пакет и принимается или отбраковывается(перезапрашивается).
• Построчные контрольные суммы — В сути своей — пережиток дикого прошлого компьютеризации, когда иной раз возникали обстоятельства, когда двоичный код приходилось набивать ручками со здоровенных таблиц(дампов). Именно оттуда и пошло нынешнее народное название этим словом BSoD. Контрольная сумма 16 байт(одной строки дампа). Во многих HEX-редакторах до сих пор отображается справа от строк наравне с ASCII-представлением набранного. И иногда ж практически надобится. Олдфаги ещё помнят такие таблицы, печатавшиеся в 80-х годах в журналах Радио и приложении к Юному Технику для «народных умельцев», собиравших на коленке не менее народные поделки Микро-80, РК-86 и пр. интересные зверюги на слегка обработанном напильником по стыренным промасленным чертежам i8080, отечественном булыжнике КР580ВМ80А.
• Ну и Функциональные контрольные суммы — поскольку контрольную сумму можно вычислить для любого произвольного куска данных — в помехозащищённых их форматах (например RIFF) в заголовках для критичных параметров есть контрольные суммы их полей. А в потоковых форматах(JPeg, MPeg и т. п.), в сути своей представляющих из себя банальные непрерывные архивные файлы с динамическим ключом — там есть ещё контрольные суммы блоков данных, участвующие в проверке достоверности их распаковки в воспроизводящее устройство. Банально чтобы последнее от запихивания ему в буфер непонять чего случайно лапки не откинуло.