что такое crc код

Целостность данных, CRC

Контрольная сумма

И возвращать байт суммы. Создадим и заполним структуру данными и прогоним через эту функцию. В последний байт структуры запишем контрольную сумму:

Теперь можно передать структуру приёмнику! Пример “синтетический”, так как кому и каким способом передавать данные мы не рассматриваем. Хотя, можно отправить по Serial, например с одной Ардуины на другую, как в уроке по парсингу Serial:

Далее на приёмнике примем данные:

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

Если значение совпадёт с переданным rxData.hash – данные верны! Дополним предыдущий код:

И по условию можем выполнять какие-то действия, например применить полученные данные к устройству или проигнорировать их. Достоинства контрольной суммы:

Недостатки контрольной суммы:

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

Превратились в такой:

CRC (cyclic redundancy code) – циклический избыточный код. Алгоритм тоже выдаёт некое “число” при прохождении через него потока байтов, но учитывает все предыдущие данные при расчёте. Как работает данный алгоритм мы рассматривать не будем, об этом можно почитать на Википедии или здесь. Рассмотрим реализацию CRC 8 бит по стандарту Dallas, он используется в датчиках этой фирмы (например DS18b20 и домофонные ключи iButton). Данная реализация должна работать на всех платформах, так как это чисто C++ без привязки к архитектуре (компилятор сам разберётся):

Финальный пример. Передатчик:

Также коллега поделился реализацией данного алгоритма на ассемблере для AVR, она работает чуть быстрее и весит чуть легче, что может быть критично например для ATtiny:

Функция используется точно так же, как предыдущая.

Источник

CRC FAQ. Что, зачем и как

Глава 1. Что такое CRC и зачем он нужен

CRC (cyclic redundancy code) — циклический избыточный код, иногда называемый также контрольным кодом. По своей сути — это просто вычисленное на основе исходного передаваемого сообщения число (или можно сказать код), которое передаётся вместе с самим сообщением (дописывается в конец информационной части) и служит для контроля его безошибочной передачи.

Число это вычисляется по определённым правилам и всегда имеет строго определённое заранее количество разрядов. Очень удобно заранее знать, сколько разрядов занимает контрольное число, потому что иначе станет заранее неизвестной длина сообщения целиком, вместе с CRC, даже при условии, что мы точно знаем длину информационной части. Кроме того, это позволяет заранее выделить для вычисления CRC регистр нужного размера.

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

Глава 2. Базовая теория, необходимая для вычисления CRC

По большому счёту, вся теория нахождения CRC базируется на двух вещах.

Первое. Любое сообщение можно представить в виде одного большого двоичного числа и считать что значения разрядов этого числа кодируют коэффициенты некоторого полинома.

Например, возьмём сообщение «15». В шестнадцатиричном виде оно кодируется так: 0x31,0x35. Если перевести эту запись в двоичную форму и записать всё в одну строку, то получим: 00110001 00110101. Если считать, что каждый разряд полученного числа — это коэффициент полинома, то этот полином будет иметь вид:
0*x 15 +0*x 14 +1*x 13 +1*x 12 +0*x 11 +0*x 10 +0*x 9 + 1*x 8 +0*x 7 +0*x 6 +1*x 5 +1*x 4 +0*x 3 +1*x 2 + 0*x 1 +1*x 0
Кратко его можно записать так: x 13 +x 12 +x 8 +x 5 +x 4 +x 2 +1

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

Второе. Количество разрядов любого двоичного сообщения — это вполне конкретные, конечные числа. Соответственно, множества всех возможных N-разрядных сообщений (где N-любое целое положительное число), составленных по описанному выше способу, — это конечные множества. При использовании особой алгебры такие конечные множества можно считать конечными полями, являющимися расширением простого конечного поля GF(2). Соответственно, любые полиномы, коэффициенты которых составлены из значений разрядов двоичных чисел, можно рассматривать как многочлены над конечным полем.

Подробно многочлены над конечными полями изучаются в отдельном разделе математики, в который мы не будем сильно углубляться в рамках этой статьи. Если кто-то хочет узнать больше — вектор поисков для самостоятельного изучения, я считаю, вполне определён. Нам же интересно, что это за особая алгебра и как это связано с вычислением CRC.

Так вот, отличия этой алгебры от обычной заключаются в следующем:
— операции сложения и вычитания в ней тождественны и выполняются как сложение по модулю 2 (XOR),
— вместо понятий «меньше»/»больше» используются понятия «старше»/»младше». Старшим считается многочлен с большей степенью (наибольшая степень, у которой коэффициент при x равен единице). Например x 3 +1 старше, чем x 2 +x, потому что 3>2.

Нахождение CRC заключается в делении с остатком информационного полинома (тот который составлен из информационного сообщения) на некоторый специальный полином. Делим мы как обычно — столбиком, но вместо операции «вычитания» используем «сложение по модулю 2» и продолжаем деление до тех пор, пока оставшийся в делимом полином не окажется младше полинома делителя. Полученный остаток — это и есть CRC.

Для примера разделим рассмотренный выше полином, составленный из сообщения «15», на полином x 4 +x+1, для чего сначала запишем последний полином со всеми коэффициентами в явном виде (1*x 4 +0*x 3 +0*x 2 +1*x 1 +1*x 0 ), а потом запишем эти коэффициенты в виде вектора (10011). Деление будет выглядеть так, как на рисунке справа.

Нули в самом начале делимого, как я и обещал, нам не пригодились, точно также, как они не пригодились бы нам и при обычном делении.

Идём далее. Что это за специальный полином, на который мы делим наше представленное в виде полинома сообщение?

А это как раз один из основных параметров CRC-алгоритма, называемый также порождающим многочленом или порождающим полиномом. В качестве порождающего многочлена обычно берут какой-либо неприводимый многочлен.

Деление с остатком на полином степени N позволяет получить 2 N различных остатков от деления, причем все эти остатки можно описать N-1 разрядными векторами.

Описанные выше действия — это то, что мы по сути всегда делаем при нахождении CRC. Такое описание алгоритма удобно теоретикам и неудобно инженерам. Поэтому теперь перейдём к частностям, которые приближают нас к практической действительности.

Глава 3. Модификация алгоритма для практического применения.

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

То есть теперь можно описать наш алгоритм так: побитно загружаем наше информационное сообщение в регистр нужного размера (на единицу меньше степени порождающего полинома), каждый раз сдвигая регистр влево и помещая новый бит в младший разряд. При этом, если вытесняемый из регистра старший бит равен единице, то выполняем XOR регистра со всеми битами порождающего полинома, кроме старшего. Значение регистра после обработки всего сообщения — это и есть CRC.

На картинке слева тот же самый пример, который мы рассматривали выше, но оформленный в соответствии с новым (инженерным) описанием алгоритма вычисления CRC (хотя по сути, это то же самое деление, что и выше).

Одно отличие в нашем инженерном алгоритме от рассматриваемого выше деления столбиком всё же есть. Отличие это заключается в начальном значении регистра. Мы инициализировали регистр нулями. В итоге наше сообщение стало несколько длиннее первоначального. Как мы знаем, нули в начале сообщения не влияют на результат вычислений, их там можно хоть сколько написать. Но ведь можно инициализировать регистр и не нулями.

Что изменится? Да особенно ничего, просто мы тогда будем искать CRC для несколько модифицированного исходного сообщения (с приписанными в начале битами). Если тот, кто будет определять правильность передачи сообщения, знает об этом и знает какое значение для инициализации регистра нужно выбирать, то он сможет правильно посчитать CRC. Надо сказать, что на практике чаще всего используется инициализация всего регистра нулями или инициализация всего регистра единицами.

Параметры, определяющие формирование битовой последовательности должны описывать:

Наличие последнего параметра связано с тем, что сообщения как правило передаются побайтно и при этом возможны два варианта передачи: старшим битом вперёд (в этом случае биты исходного сообщения располагаются в битовой последовательности, для которой вычисляется CRC, в нормальном порядке) или младшим битом вперёд (в этом случае биты исходного сообщения располагаются в битовой последовательности, для которой вычисляется CRC, в обратном порядке). Причём, иногда переворачивают не только биты в байтах, но и, например, байты в словах. Кстати говоря, во всех примерах, которые приводятся в этой статье, рассматривался только нормальный порядок бит (старшим битом вперёд).

Кроме того, иногда полученный в результате деления остаток дополнительно инвертируют и в качестве CRC используют не сам остаток, а это инвертированное значение.

Помимо описанного в этой статье прямого способа вычисления, существует, так называемый, табличный или быстрый способ расчёта CRC, но об этом как-нибудь в другой раз. А на сегодня, пожалуй, всё.

Источник

Циклический избыточный код

Содержание

Введение

Помехоустойчивое кодирование

Первые попытки создания кодов с избыточной информацией начались задолго до появление современных ПК. К примеру, ещё в шестидесятых годах прошлого века Ридом и Соломоном была разработана эффективная методика кодирования — Код Рида-Соломона. Использование её в те времена не представлялось возможным, так как произвести операцию декодирования за разумное время первыми алгоритмами не удавалось. Точку в этом вопросе поставила фундаментальная работа Берлекампа, опубликованная в 1968 году. Эта методика, на практическое применение которой указал через год Мэсси, и по сей день используется в цифровых устройствах, обеспечивающих прием RS-кодированных данных. Более того: данная система позволяет не только определять позиции, но и исправлять неверные кодовые символы (чаще всего октеты).

Но далеко не везде от кода требуется коррекция ошибок. Многие современные каналы связи обладают приемлемыми характеристиками, и зачастую достаточно лишь проверить, успешно ли прошла передача или возникли какие-нибудь сложности; структура же ошибок и конкретные позиции неверных символов совершенно не интересуют принимающую сторону. И в этих условиях очень удачным решением оказались алгоритмы, использующие контрольные суммы. CRC как нельзя лучше подходит для подобных задач: невысокие затраты ресурсов, простота реализации и уже сформированный математический аппарат из теории линейных циклических кодов обеспечили ей огромную популярность.

Контрольная сумма

В самом общем своем виде контрольная сумма представляет собой некоторое значение, построенное по определенной схеме на основе кодируемого сообщения. Проверочная информация при систематическом кодировании дописывается в конец сообщения — после полезных данных. На принимающей стороне абонент знает алгоритм вычисления контрольной суммы: соответственно, программа имеет возможность проверить корректность принятых данных.

При передаче пакетов по реальному каналу, разумеется, могут возникнуть искажения исходной информации вследствие разных внешних воздействий: электрических наводок, плохих погодных условий и многих других. Сущность методики в том, что при хороших характеристиках хэш-функции в подавляющем числе случаев ошибка в сообщении приведет к изменению вычисленного на приеме значения CRC. Если исходная и вычисленная суммы не равны между собой, принимается решение о недостоверности принятых данных, и можно запросить повторную передачу пакета.

Математическое описание

Алгоритм CRC базируется на свойствах деления с остатком двоичных многочленов, то есть многочленов над конечным полем . Значение CRC является по сути остатком от деления многочлена, соответствующего входным данным, на некий фиксированный порождающий многочлен.

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

Количество различных многочленов степени меньшей равно , что совпадает с числом всех двоичных последовательностей длины .

Значение контрольной суммы в алгоритме с порождающим многочленом G(x) степени N определяется как битовая последовательность длины N, представляющая многочлен R(x), получившийся в остатке при делении многочлена P(x), представляющего входной поток бит, на многочлен G(x):

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

Умножение осуществляется приписыванием нулевых битов к входной последовательности, что улучшает качество хеширования для коротких входных последовательностей.

При делении с остатком исходного многочлена на порождающий полином G(x) степени N можно получить 2 N различных остатков от деления. G(x) всегда является неприводимым многочленом. Обычно его подбирают в соответствии с требованиями к хэш-функции в контексте каждого конкретного применения.

Тем не менее, существует множество стандартизированных образующих многочленов, обладающих хорошими математическими и корреляционными свойствами (минимальное число коллизий, простота вычисления). В статье приведены некоторые из них, а также соответствующие реализации на языке Си.

Вычисление CRC

Параметры алгоритма

Говоря о формировании контрольной суммы CRC, в первую очередь нужно упомянуть о полиноме-генераторе. Существует огромное множество многочленов, участвующих в формировании cyclic reduntancy code; многие из них указаны в конце статьи.

Другим параметром конкретного алгоритма вычисления контрольной суммы является размер слова, или суммарное количество регистров — информационных ячеек, используемых для вычисления численного значения хэша. При этом обязательно учитывается то, что размер слова и степень образующего контрольную сумму полинома совпадают. На практике более всего распространены 8, 16 и 32 — битовые слова, что является следствием особенностей архитектуры современной вычислительной техники.

И последний параметр, важный при описании определенной методики — начальные состояния регистров (стартовое слово). Это последняя из трех значимых характеристик; зная их в совокупности, мы можем восстановить алгоритм вычисления CRC, если данная модификация методики не имеет специфических особенностей, таких, как обратный порядок обработки битов.

Описание процедуры

Из файла берется первое слово — это может быть битовый (CRC-1), байтовый (CRC-8) или любой другой элемент. Если старший бит в слове «1», то слово сдвигается влево на один разряд с последующим выполнением операции XOR. Соответственно, если старший бит в слове «0», то после сдвига операция XOR не выполняется. После сдвига теряется старый старший бит, а младший бит освобождается — его значение устанавливается равным нулю. На место младшего бита загружается очередной бит из файла, и операция повторяется до тех пор, пока не загрузится последний бит файла. После прохождения всего файла, в слове остается остаток, который и является контрольной суммой.

Наиболее используемые и стандартизованные полиномы

В то время, как циклические избыточные коды являются частью стандартов, у этого термина не существует общепринятого определения — трактовки различных авторов нередко противоречат друг другу. [1] [5]

При этом многие широко используемые полиномы не являются наиболее эффективными из всех возможных. В 1993—2004 годах группа ученых занималась исследованием порождающих многочленов разрядности до 16, [1] 24 и 32 бит, [6] [7] и нашла полиномы, дающие лучшую, нежели стандартизированные многочлены, производительность в смысле кодового расстояния. [7] Один из результатов этого исследования уже нашёл своё применение в протоколе iSCSI.

Ниже в таблице перечислены наиболее распространенные многочлены — генераторы CRC.На практике вычисление CRC может включать пре- и пост-инверсию, а также обратный порядок обработки битов. В проприетарных реализациях CRC для усложнения анализа кода применяют ненулевые начальные значения регистров.

Существующие стандарты CRC-128 (IEEE) и CRC-256 (IEEE) в настоящее время вытеснены криптографическими хеш-функциями.

Попытки описания алгоритмов CRC

Примеры спецификаций некоторых алгоритмов CRC

Примеры программ для вычисления CRC на языке C

Источник

CRC: как защитить программу

Всем нам свойственно ошибаться, но иногда мы вовремя обнаруживаем свои ошибки. Пусть ты не сможешь умножить в уме 790 г. колбасы на 134 рубля 50 копеек, но если продавщица говорит: «115 рублей, молодой человек», то ты можешь прикинуть (около 120 рублей умножить на 1/4 килограмма будет 30 рублей, 130 минус 30 — сто рублей) и понять, что эта добрая тетя пытается тебя обдурить, присвоив себе десятку.
Компьютеры тоже ошибаются. Сбоит память, на винчестерах появляются бэдблоки, мыши в колодцах грызут телефонные кабели. Так в информацию вносятся ошибки, которые нужно обнаруживать и по возможности исправлять.

Чтобы найти ошибку, к сообщению добавляют контрольную сумму (checksum). В самом простом случае это сумма всех байтов сообщения. Например:

Сообщение: 12 34 56
Контрольная сумма: 12+34+56=102

После передачи в это сообщение могут быть внесены помехи, например, так:

Искаженное сообщение: 12 36 56, контрольная сумма 102

Если теперь сложить байты сообщения, результат не совпадет с контрольной суммой. Так программа может сделать вывод, что данные были повреждены, и принять меры (например, еще раз запросить пакет TCP/IP или выдать сообщение, что архив поврежден).

CRC, или циклический избыточный код, — это улучшенный (и усложненный) вариант контрольной суммы. В этой статье будет рассказано об алгоритме CRC32, который применяется в протоколе TCP/IP, архиваторах Zip и Rar. Затем я расскажу тебе, как защитить свою программу от модификаций, проверяя ее
CRC.

Чем плоха контрольная сумма

Во-первых, если просто складывать байты, то старшие биты будут изменяться реже, чем младшие. То есть, если мы складываем

12 34 56, контрольная сумма 102
12 34 56 23, контрольная сумма 125
12 34 56 23 45, контрольная сумма 170

результат останется в пределах двух сотен. Если контрольная сумма записана в 32-разрядное или 64-разрядное слово, старшие байты будут содержать нули. Это не есть хорошо, так как все биты контрольной суммы должны быть равноценными.

Во-вторых, сообщения с переставленными байтами будут иметь одну и ту же сумму:

12 34 56, контрольная сумма 102
56 12 34, контрольная сумма 102

Несмотря на все эти недостатки, разные варианты контрольной суммы используются довольно широко, например, в штрих-кодах (barcode). У меня в руках банка консервированной кукурузы, на которой написан такой штрих-код:

Это код EAN-13 (тринадцать цифр). Правило для его проверки такое: сложи цифры на четных позициях, умножь сумму на три и добавь цифры на нечетных позициях. Должно получиться число, которое делится на десять:

9 + 8 + 8+ 7 + 0 + 2 = 34
5 + 9 + 4 + 3 + 1 + 1 + 5 = 28
34 * 3 + 28 = 130, делится на 10

А чтобы это условие выполнялось, последнюю цифру, 5, делают контрольной суммой. То есть складывают по этим правилам все остальные цифры, а последнюю цифру вычисляют как 10 минус последняя цифра суммы. Контрольная сумма нужна затем, чтобы сканер в супермаркете не считывал неправильный код если упаковка грязная или продавщица случайно закрыла код рукой. Если интересно, можешь проверить по этому правилу штрих-коды на любых упаковках пищевых продуктов (но не книг — у них другой код, ISBN).

Есть очень простой, короткий и быстрый (примерно в 10 раз быстрее CRC) способ подсчета контрольной суммы. Берем по 4 байта из файла, и делаем с ними логическую операцию XOR. То, что получится в результате, — контрольная сумма.

unsigned long XORCount(void* data, size_t bytesread)
// data — сообщение, size_t — его длина
<
*(long*)(data + bytesread) = 0; // Подписать 4 нулевых байта
bytesread /= sizeof(long);
while(bytesread—)
sum ^= *(long*)data, data+=sizeof(long);
// Первые 4 байта XOR вторые 4 байта XOR третьи.
return sum;
>

В этой контрольной сумме все байты используются полностью, среди них нет более значимых или менее значимых. Теоретическая вероятность того, что контрольная сумма окажется правильной для испорченного файла — 1 шанс на 2 ^ 32. Но операция XOR обладает таким свойством, что A XOR A = 0. Поэтому для сообщений

12 34 A6 7B 91 92 93 94 91 92 93 94
12 34 A6 7B 12 34 56 78 12 34 56 78
12 34 A6 7B 00 00 00 00 00 00 00 00

контрольная сумма будет одинаковой, как и для любых других, содержащих четное число одинаковых четверок байт (или же просто 8, 16, 24 или 32 одинаковых байт). И если вместо NOP’ов записать в исполнимый файл нули или любые другие байты (но число байт обязательно кратно 8), то программа этого не обнаружит. Все это плохо, но не смертельно, поэтому этим алгоритмом вполне можно пользоваться, если нужна высокая скорость проверки.

Что такое CRC

Запомни простую формулу: CRC = сообщение % полином

То есть все сообщение (файл, архив) делим по модулю на некоторую константу (ее называют полиномом). Остаток от деления и есть CRC. О том, как весь файл можно разделить на число, я скажу чуть ниже, а пока — урок арифметики. Но не обычной арифметики, а полиномиальной.
Что же это за арифметика такая? Это двоичная арифметика без переносов и заемов. Если сложить 1+1 в обычной двоичной арифметике, получится 10 (переносим единицу). Если вычесть 10–1, получится 1 (занимаем единицу).

В полиномиальной арифметике:

0+0 = 0 0–0=0
0+1 = 1 0–1=1 (не занимаем!)
1+0 = 1 1–0=1
1+1 = 0 (не переносим!) 1–1=0

Видно, что сложение в полиномиальной арифметике — это то же, что и вычитание. И если тебя мучили таблицами истинности на уроках информатики, ты сразу вспомнишь, что это операция XOR. В учебниках по дискретной математике ее обозначают кружком с косым крестиком внутри. Я буду обозначать эту операцию крышкой ^, как в Си.
В полиномиальной арифметике 100 плюс 110 равно 10, но 100 минус 110 тоже равно 10. Нет ни знака, ни определенного порядка битов. Все биты равнозначны, и это очень важное свойство для CRC. Если переставить несколько битов в обоих слагаемых, те же биты будут переставлены в сумме:

1010 ^ 1100=01 10, поменяем местами первые два и последние два бита:
1010 ^ 0011=10 01 (а теперь сравни 19+34=53 и 91+43=134, а не 35).

Биты можно представить как коэффициенты многочлена (полинома). Поэтому арифметику называют полиномиальной, а делитель в алгоритмах CRC — полиномом. В общем, все это математические заморочки, но знать будет не лишнее.

Умножение в полиномиальной арифметике нам не понадобится, а вот о делении нужно сказать подробнее. Делим, как во втором классе, уголком, но вместо вычитания используем операцию XOR:
Сообщение: 1101010
Полином: 101

1101010
^101
====
111010
^101
===
10010
^101
===== получили 0, сдвигаемся на 2 бита
110
^101
===
11

Именно так считают CRC. Заметь, что в каждом столбике мы вычитаем старшие биты 1–1=0. В следующих битах могут быть любые числа. Один раз мы получили ноль в старшем бите, и нам пришлось сдвинуться вправо на 2 бита, а не на один. Итак, можно записать такой алгоритм (это не рабочий код, он только показывает алгоритм):

В столбиках мы сдвигали полином 101 вправо, каждый раз вычитая его из сообщения. В этом алгоритме полином остается на месте, но мы «двигаем» делимое влево. Если старший бит r равен нулю, мы сдвигаемся еще на один бит, не вычитая POLY. Константа POLY равна полиному без старшей единицы, то есть 01. Обрати на это внимание: первую единицу писать незачем, так как двоичное число всегда начинается с единицы.
Как работает этот код, легче понять на примере. Возьмем то же сообщение 1101010 и тот же полином 101 (сравни со столбиком выше):

Шаг 1. r = 1 // Отделили первый бит
data = 101010 // r=1, поэтому делаем XOR
^01
======
111010
Шаг 2. r = 1
data = 11010
^01
=====
10010
Шаг 3. r = 1
data = 0010
^01
====
0110
Шаг 4. r = 0 // XOR не делаем
data = 110
Шаг 5. r = 1
data = 10
^01
==
11

Итак, алгоритм в целом понятен: делим нацело data на POLY, получаем crc. И при делении 0–1=1, 1+1=0 без переноса.

Сложность состоит в том, что сообщение может весить пару мегабайт. Как же разделить его на полином? Заметь, что при каждом проходе цикла у нас меняются только 2 первых бита data. Значит, можно проходить по
всему сообщению, читая в каждый момент времени небольшую порцию данных (в нашем случае — первые два бита).

Как работает табличная реализация

Но у этого алгоритма есть еще один недостаток: он обрабатывает по одному биту сообщения. Например, для мегабайтного файла он сделает 8 миллионов проходов цикла, и каждый раз будет извлекать отдельные биты. Согласись, это никуда не годится!
Есть общепринятый трюк, который ускоряет подсчет CRC чуть ли не в десятки раз. Идея такова: будем обрабатывать по байту за один проход цикла. Когда мы делим байт на полином, у нас в остатке получается некоторое число, причем оно не зависит от других байтов сообщения. Вот это число мы можем хранить в таблице для каждого делимого байта. Имея такую таблицу, будем получать CRC для каждого байта за один проход.
Сейчас я расскажу, как построить такую таблицу и что конкретно в ней будет находиться. Чтобы не маяться с длинными таблицами, возьмем байт, равный 3 битам, и короткий полином 111. Пусть сообщение состоит из 5 бит, назовем их abcde. Пройдем наш старый алгоритм по шагам:

Шаг 1. if(a) // Запись условная, это не рабочий код
bc ^= 11;
Шаг 2. if(b)
cd ^= 11; // Полином 110 без первой единицы
Шаг 3. if(c)
de ^= 11;

Когда мы подсчитали bcd и перешли на второй шаг, бит a уже не нужен, и на дальнейшие подсчеты он никак не влияет. Когда дошли до последнего шага, оказались ненужными биты a и b. А после третьего шага сыграл свою роль бит c, который теперь сходит со сцены.
То, что поменялись биты abc, уже не важно, потому что на четвертом, пятом и так далее шаге они не будут использоваться. Но на этих трех шагах как-то изменились биты de. И изменились они в зависимости от битов abc. Давай переберем все значения abc, начиная с 000 и до 111.

000 (a=0, b=0, c=0) — ни одно из условий не выполняется, поэтому биты def не изменились.
001 (a=0, b=0, c=1) — условие if(c) выполнилось. Я запишу это так:
abc
001def
^11
010 — условие if(b) выполнилось, но после добавления единицы к c выполнилось также if(c). Запишем под чертой результат операции XOR над двумя соответствующими числами в битах de:
abc
010de
^11
^11
==
01
011 — выполнилось условие if(b), но бит c был при этом обнулен, поэтому if(c) не сработало:
abc
011de
^11
==
10
100 — сработало условие if(a), которое вызвало if(b). В результате бит d будет подвергнут операции XOR с единицей (далее будем говорить проще, XOR’ится с единицей):
abc
100de
^11
^11
==
10
101 — аналогично, но бит c обнулился, и результат — нулевой:
abc
101de
^11
==
00

То же самое ты можешь написать для 110 и 111. Довольно муторное дело, но в нем нет ничего сложного. Сделаем массив T с индексами от 000 до 111, в котором будем хранить результаты наших вычислений:

индекс значение
000 00
001 11
010 01
011 10
100 10
101 00
110 11
111 00

Теперь рассчитать CRC можно, что называется, в два притопа, три прихлопа. Смотри:

de ^= t[abc]; // Код условный, не рабочий.
gh ^= t[def]; // t — массив, abc def ghi — сообщение
crc = ghi;

Если вынести текущий изменяемый байт в отдельную переменную, расширить байт до 8 бит и взять 32-битный полином, получим почти готовый код для расчета
CRC:

static const long t[256] = <
0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, 0x076dc419,
0x706af48f, 0xe963a535, 0x9e6495a3, 0x0edb8832, 0x79dcb8a4,
0xe0d5e91e, 0x97d2d988, 0x09b64c2b, 0x7eb17cbd,
// И так далее, все 256 элементов смотри в коде к статье
>

Здесь на каждом шаге мы выбираем элемент из таблицы T по значению старшего байта (crc >> 24) и XOR’им его с очередным байтом. Этот байт у нас каждый раз сдвигается влево, а на его место приходит новый из сообщения (*buff++). Все эти сдвиги нужны для того, чтобы использовать длинный 32-битный полином, который XOR’ится с четырьмя соседними байтами сразу.
В последних четырех строчках мы проводим через серию XOR’ов и сдвигаем влево оставшийся в младшем байте crc последний байт файла. По правилам вычисления CRC все символы должны «уйти» влево, за пределы переменной. На этом заканчивается вычисление CRC — остатка от деления сообщения на полином в полиномиальной арифметике.
Итак, в таблице хранятся сдвинутые и проXORенные значения полинома. Конкретные сдвиги зависят от индекса массива, который есть предыдущий байт (abc или crc >> 24), а значение следующего байта (def или (crc crc = CRCINIT;
while (bufflen—)
crc = t[(crc >> 24 ^ *buff++) & 0xFF] ^ (crc

Это позволяет избавиться от четырех последних строчек, хотя не делает алгоритм ни проще, ни быстрее. Кстати, скобки вокруг (crc while(bufflen—)
crc = t[(crc ^ *buff++) & 0xFF] ^ (crc >> 8);

Такой код будет давать перевернутый CRC, и именно его ты скорее всего найдешь на сайтах для программистов и в различных FAQ по CRC. Еще раз повторюсь, что именно так считают CRC большинство программ.

Из-за путаницы с перевернутыми алгоритмами можно найти описание алгоритма с полиномом 0x04C11DB7 и другого алгоритма с полиномом 0xEDB88320. На самом деле это одно и то же, только авторы первого алгоритма переворачивали байты при каждом проходе цикла, а во втором алгоритме переделали сдвиг (crc > 8), выделили младший байт вместо старшего и записали задом наперед полином:

EDB88320 = 11101101101110001000001100100000
04C11DB7 = 00000100110000010001110110110111

После вычисления CRC32 его обычно инвертируют (заменяют единицы нулями, а нули единицами). Это записывается либо как crc ^= 0xFFFF FFFF, либо crc =

crc. Второй вариант быстрее и короче, поэтому мы будем пользоваться им.

Ищем оптимальный алгоритм

Табличная реализация CRC совсем непохожа на деление в полиномиальной арифметике. Еще более забавные вещи начнутся, когда мы будем оптимизировать этот алгоритм.
Массив t[], конечно, можно рассчитывать заранее и записывать в константы, как показано выше. Но есть более оптимальный путь — генерировать этот массив при запуске программы. На это уходят буквально доли секунды, а программа становится на килобайт (256 элементов умножить на 4 байт) короче:

static unsigned long t[256]; // Таблица для подсчета CRC
void CRCInit()
<
for (int i = 0; i 0; j—) // Для каждого бита
if(t[i] & 1) // Если младший бит
t[i] = (t[i]>>1) ^ CRCPOLY;
else
t[i] >>= 1;
>
>

Особых пояснений этот алгоритм не требует, потому что он делает то же, что мы делали вручную, когда рассчитывали таблицу t[]: проходит по всем битам abcdefhi, и если бит равен единице, XOR’ит следующие биты с полиномом. Длина байта здесь равна 8 символам, а полином 32-битный. Алгоритм перевернутый. В «прямом» алгоритме будет отличаться только вложенный цикл:

t[i] = i 0; j—) // Для каждого бита
if(t[i] & 0x80000000) // Если старший бит
t[i] = (t[i]

Оба алгоритма можно очень хорошо разогнать, если развернуть вложенный цикл и убрать условие. Я напишу «турбореактивную» версию перевернутого алгоритма, так как почти всегда ты будешь пользоваться именно им:

for (int i = 0; i > 1) ^ CRCPOLY, иначе
// x = (x >> 1) ^ 0 = x >> 1;
x = (x>>1) ^ (CRCPOLY & (-(signed long)(x & 1)));
x = (x>>1) ^ (CRCPOLY & (-(signed long)(x & 1)));
x = (x>>1) ^ (CRCPOLY & (-(signed long)(x & 1)));

Эта программа выполняется на Duron-800 за 12 микросекунд, тогда как исходная версия — за 35 мксек. Ускорение просто невероятное, но толку от него немного, потому что инициализация таблицы занимает очень небольшую часть от общего времени работы алгоритма. Проще говоря, 12 микросекунд не отличишь на глаз от тридцати пяти (одна микросекунда — миллионная доля секунды).
Затем я попробовал частично развернуть цикл подсчета
CRC:

crc = CRCINIT;
bufflen /= 4; // bufflen должно быть кратно 4. Для хвостов
while(bufflen—) // следует использовать обычный алгоритм
< x = *(long*)buff;
crc = t[(crc ^ x) & 0xFF] ^ (crc >> 8);
crc = t[(crc ^ x >> 8) & 0xFF] ^ (crc >> 8);
crc = t[(crc ^ x >> 16) & 0xFF] ^ (crc >> 8);
crc = t[(crc ^ x >> 24) & 0xFF] ^ (crc >> 8);
buff += 4;
>
crc =

crc; // Инвертировать CRC

Это дает некоторый прирост скорости, но этот прирост невелик (не больше 5%). Так или иначе, конечная версия моей программы для подсчета CRC использует именно этот алгоритм и динамическую генерацию таблицы
t[].

Как защитить свою программу от взлома

Ты можешь подсчитать CRC своего exe’шника, сравнить его с CRC, хранящимся в том же exe’шнике, и убедиться, что программа не была повреждена / взломана. Идея не нова, и она используется, в частности, в Total Commander (на проверке CRC прокололись многие крэкеры, написавшие патчи к
TC). В exe’шниках DOS и Windows уже предусмотрены поля для контрольной суммы (16-битной по смещению 0x12..0x13 от начала файла и 32-битной по смещению 0x8-0xB от начала PE-заголовка). Самым простым вариантом будет использовать их. В компоновщике Link для MSVC++ предусмотрена опция /RELEASE, которая заставляет пересчитывать контрольную сумму после каждой компиляции программы. А Win32 API имеет функцию MapFileAndCheckSum для проверки этой суммы. Если нужно защитить программу от повреждений и вирусов, это действительно лучший вариант — всего-то пара строчек кода.
Но такая «защита» не остановит ни одного крэкера. Придется придумать что-нибудь получше, а именно считать CRC самостоятельно. В заголовке exe’шника есть куча неиспользуемых и зарезервированных полей, в которые можно записать CRC. Я выбрал поле 0x2C из заголовка MS-DOS. Чтобы не получилось так, что CRC файла изменился из-за того, что мы вписали в этот же файл CRC, будем считать CRC начиная со смещения 0x40 (пропускаем заголовок MS-DOS). Получаем имя данного exe’шника функцией GetModuleFileName, открываем его, подсчитываем CRC и сравниваем с хранящимся в файле:

#define QUANT 1024 // Читать по 1024 байт файла
#define CRCPOLY 0xEDB88320
#define CRCINIT 0xFFFFFFFF
int CRCCheckThisExe()
< // Проверить целостность exe (возвращает 1,
// если программа была изменена)
char FileName[MAX_PATH]; HANDLE hFile; DWORD bytesread;
char data[QUANT], *p; unsigned long crc, x;

Как показывает опыт, на скорость расчета CRC сильно влияет размер считываемого куска QUANT. Я получал хорошие результаты при QUANT = 1024 и QUANT = 2048. Ты можешь подобрать другие значения. По идее, они должны быть кратны размеру сектора диска (512 байт), но можно еще попробовать учесть, что мы считываем файл не с начала, а со смещения 0x40.

Считает и записывает CRC в exe’шник отдельная программа, CRCMaker. Ее можно прописать в свойства проекта (Post-build step), чтобы после каждой компиляции CRC пересчитывался автоматически.
Чтобы усилить защиту, нужно «размазать» вычисление CRC по всей твоей программе. При запуске программы вызови GetModuleFileName и сохрани путь в глобальной переменной. Затем где-то в другом месте открой файл и начни подсчет CRC. Хороших результатов можно добиться, если подсчитывать CRC при простое программы (когда пользователь не работает с клавиатурой и мышью или когда переключился в другую программу). Два значения CRC — рассчитанное и взятое из файла — нужно записать в глобальные переменные и в нескольких точках программы сверять между собой. Лучше не выдавать никаких предупреждающих сообщений, а сразу выходить из программы. Все это более или менее обезопасит твою прогу от цепких лап любителей
SoftIce.

Что еще почитать на тему CRC

Ross Williams. A painless guide to CRC error detection algorithms. — ftp://www.internode.net.au/clients/rocksoft/papers/crc_v3.txt
(русский перевод см. http://www.rsdn.ru/article/files/classes/SelfCheck/crcguide.pdf). Очень подробное описание принципа подсчета CRC, но не слишком оптимальные алгоритмы. Можно почитать, если ты хочешь разобраться в математических подробностях.

FAQ по CRC. — http://faqs.org.ru/progr/common/crc_faq.rar. Самые короткие и вразумительные алгоритмы вычисления CRC из всех, что я встречал. На Си, Паскале, ассемблере. Там же — как взломать CRC (подобрать сообщение под заданный
CRC).

Алексей Кирюшкин. Защита исполняемых файлов от искажений. —
http://www.rsdn.ru/article/files/classes/selfcheck.xml. Автор предлагает хранить CRC в разделе данных и находить его по некоторой сигнатуре. Неплохой способ, хотя он немного сложнее, чем хранение CRC в заголовках exe’шника.

Скачать пример программы можно отсюда. Программа XakepCRC проверяет CRC файлов, но она также защищает себя от взлома с помощью CRC. Заголовочные файлы из каталога CRClib ты можешь использовать в своих программах.

Источник