Ross n williams a painless guide to crc error detection algorithms перевод

Оглавление

Введение: обнаружение ошибок.

Основная идея, заложенная в алгоритме CRC .

Двоичная арифметика без учета переносов .

Полностью рабочий пример.

Прямая реализация CRC.

Реализация табличного алгоритма.

Слегка преобразованный табличный алгоритм.

«Зеркальный» табличный алгоритм .

Начальные и конечные значения.

Полное определение алгоритма .

Параметрическая модель CRC алгоритма .

Каталог параметров стандартных реализаций CRC алгоритма .

Реализация модельного алгоритма .

Создай собственную табличную реализацию.

Генерация таблицы просмотра.

C. Другие, обнаруженные мной, но не просмотренные ссылки.

Предисловие

Данная статья посвящена полному и точному описанию CRC (Cyclic Redundancy Codes – Циклические Избыточные Коды) и реализации табличных алгоритмов их вычисления. Большая часть литературы, касающаяся CRC вообще, и их табличным разновидностям особенно, достаточно сложна и запутанна (по крайней мере, мне так показалось). Статья была написана с целью дать простое и вместе с тем точное опи сание CRC, вникающее во все тонкости реализации его высокоскоростных вариан тов. Предложена параметрическая модель CRC алгоритма, названная «Rocksoft Model CRC Algorithm», которая может быть настроена таким образом, чтобы рабо тать подобно большинству стандартных реализаций алгоритмов расчета CRC, и ко торая, одновременно, является хорошим примером для демонстрации особенностей некоторых из них. Кроме того, приведен неоптимизированный пример на языке C, а также 2 варианта высокоскоростной табличной реализации, и программа генерации таблицы поиска для расчета CRC.

Элементарное руководство по CRC алгоритмам обнаружения ошибок

1. Введение: обнаружение ошибок

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

Сообщение с контрольной суммой

Сообщение после передачи

Как Вы видите, второй байт сообщения при передаче оказался измененным с 23 на 27. Приемник может обнаружить ошибку, сравнивая переданную контрольную сумму (33) с рассчитанной им самим: 6 + 27 + 4 = 37. Если при правильной пере даче сообщения окажется поврежденной сама контрольная сумма, то такое сооб щение будет неверно интерпретировано, как искаженное. Однако, это не самая плохая ситуация. Более опасно, одновременное повреждение сообщения и кон трольной суммы таким образом, что все сообщение можно посчитать достоверным. К сожалению, исключить такую ситуацию невозможно, и лучшее, чего можно до биться, это снизить вероятность ее появления, увеличивая количество информации в контрольной сумме (например, расширив ее с одного до 2 байт).

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

2. Требования сложности

В предыдущем разделе мы показали, что повреждение сообщения может быть обнаружено, используя в качестве алгоритма контроля простое суммирование бай тов сообщения по модулю 256:

Сообщение с контрольной суммой

Сообщение после передачи

Недостаток этого алгоритма в том, что он слишком прост. Если произойдет не сколько искажений, то в 1 случае из 256 мы не сможем их обнаружить. Например:

Сообщение с контрольной суммой

Сообщение после передачи

Для повышения надежности мы могли бы изменить размер регистра с 8 битного на 16 битный (то есть суммировать по модулю 65536 вместо модуля 256), что скорее

3. Основная идея, заложенная в алгоритме CRC

всего снизит вероятность ошибки с 1/256 до 1/65536. Хотя это и неплохая идея, од нако, она имеет тот недостаток, что применяемая формула расчета не «случайна» в должной степени — каждый суммируемый байт оказывает влияние лишь на один байт суммирующего регистра, при этом ширина самого регистра не имеет никакого значения. Например, во втором случае суммирующий регистр мог бы иметь ширину хоть мегабайт, однако ошибка все равно не была бы обнаружена. Проблема может быть решена лишь заменой простого суммирования более сложной функцией, чтобы каждый новый байт оказывал влияние на весь регистр контрольной суммы.

Таким образом, мы сформулировали 2 требования для формирования надежной контрольной суммы:

Ширина: Размер регистра для вычислений должен обеспечивать изна чальную низкую вероятность ошибки (например, 32 байтный ре гистр обеспечивает вероятность ошибки 1/2 32 ).

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

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

3. Основная идея, заложенная в алгоритме CRC

С чего нам следует начать в наших поисках алгоритмов более сложных, чем про стое суммирование? На ум приходят самые экзотичные схемы. Мы могли бы соста

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

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

Основная идея алгоритма CRC состоит в представлении сообщения виде огром ного двоичного числа, делении его на другое фиксированное двоичное число и ис пользовании остатка этого деления в качестве контрольной суммы. Получив сооб щение, приемник может выполнить аналогичное действие и сравнить полученный остаток с «контрольной суммой» (переданным остатком).

Приведу пример. Предположим, что сообщение состоит из 2 байт (6, 23), как в предыдущем примере. Их можно рассматривать, как шестнадцатеричное число 0167h, или как двоичное число 0000 0110 0001 0111. Предположим, что ширина реги стра контрольной суммы составляет 1 байт, а в качестве делителя используется 1001, тогда сама контрольная сумма будет равна остатку от деления 0000 0110 0001 0111 на 1001. Хотя в данной ситуации деление может быть выполнено с использованием стандартных 32 битных регистров, в общем случае это не верно. Поэтому воспользу емся делением «в столбик», которому нас учили в школе (вспомнили?). Только на этот раз, оно будет выполняться в двоичной системе счисления:

Элементарное руководство по CRC алгоритмам обнаружения ошибок

Источник

Williams R.N. A Painless Guide to CRC Error Detection Algorithms

This document explains CRCs (Cyclic Redundancy Codes) and their table-driven implementations in full, precise detail. Much of the literature on CRCs, and in particular on their table-driven implementations, is a little obscure. This document is an attempt to provide a clear and simple no-nonsense explanation of CRCs and to absolutely nail down every detail of the operation of their high-speed implementations. In addition to this, this document presents a parameterized model CRC algorithm called the «Rocksoft^tm Model CRC Algorithm». The model algorithm can be parameterized to behave like most of the CRC implementations around, and so acts as a good reference for describing particular algorithms. A low-speed implementation of the model CRC algorithm is provided in the C programming language. Lastly there is a section giving two forms of high-speed table driven implementations, and providing a program that generates CRC lookup tables.

Introduction: Error Detection
The Need For Complexity
The Basic Idea Behind CRC Algorithms
Polynomical Arithmetic
Binary Arithmetic with No Carries
A Fully Worked Example
Choosing A Poly
A Straightforward CRC Implementation
A Table-Driven Implementation
A Slightly Mangled Table-Driven Implementation
«Reflected» Table-Driven Implementations
«Reversed» Polys
Initial and Final Values
Defining Algorithms Absolutely
A Parameterized Model For CRC Algorithms
A Catalog of Parameter Sets for Standards
An Implementation of the Model Algorithm
Roll Your Own Table-Driven Implementation
Generating A Lookup Table
Summary
Corrections

Источник

Статья на тему: «CRC-алгоритмы обнаружения ошибок»

1.Обнаружение ошибок

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

В этом примере возникла ошибка во втором байте, и вместо числа 23 было передано число 27. Такую ошибку приемник может определить, вычислив контрольную сумму (37) и сравнив ее с полученной (33). Если бы сбой произошел в четвертом байте — в самой контрольной сумме, то верное сообщение было бы забраковано. Но главная опасность в том, что ошибка может произойти как в самом сообщении, так и в контрольной сумме, причем таким образом, что контрольная сумма от неверного сообщения совпадет с неверно переданной контрольной суммой. К сожалению, полностью избежать такой ситуации нельзя, можно лишь уменьшать вероятность ее возникновения, увеличивая длину контрольной суммы.

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

2. Необходимость использования сложных алгоритмов

Рассмотрим предыдущий пример в ситуации, когда ошибка не может быть обнаружена:

Вероятность возникновения такой ошибки — 1/256. Для улучшения детекции ошибок можно перейти от 8-битной контрольной суммы к 16-битной, т.е. суммируя по модулю 65536. Это, очевидно, уменьшит вероятность пропуска ошибки до 1/65536. Но в данном примере увеличение длины контрольной суммы не позволит отловить ошибку. Происходит это в результате того, что при использовании в качестве контрольной функции операции сложения, почти каждый байт исходного сообщения влияет только на один байт контрольной суммы, вне зависимости от ее длины. Поэтому, помимо длины контрольной суммы, обращают внимание на такой фактор как хаотичность: формула должна позволять любому байту сообщения изменять любое количество бит контрольной суммы.

3. Основная идея CRC-алгоритмов

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

4. Полиномиальная арифметика

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

В связи с алгоритмами CRC часто можно встретить термин «полиномиальный». Говорят, что данный CRC алгоритм использует некий полином, и.т.п. И, вообще, говорят, что CRC алгоритмы используют полиномиальную арифметику. Что же это такое?

Делимое, делитель, частное и остаток рассматриваются не как положительные целые, а как полиномы с двоичными коэффициентами. То есть число записывается в виде двоичной строки, биты которой служат коэффициентами полинома. Например числу 23 (010111b) отвечает полином:

1*x^4 + 0*x^3 + 1*x^2 + 1*x^1 + 1*x^0, или проще:

Мы можем осуществлять арифметические операции, понимая их как операции над полиномами. Например, умножим 13 (01101b) на 11 (01011b):

(x^3 + x^2 + x^0)(x^3 + x^1 + x^0) =

(x^6 + x^4 + x^3 + x^5 + x^3 + x^2 + x^3 + x^1 + x^0) =

x^6 + x^5 + x^4 + 3*x^3 + x^2 + x^1 + x^0

Для того, чтобы получить в ответе 143, мы должны в качестве x взять 2 и привести коэффициенты к двоичным, перенеся 1 из 3*x^3 в старшие разряды. Получаем:

x^7 + x^3 + x^2 + x^1 + x^0 , что соответствует 010001111b = 143

Это обычная арифметика, просто основание системы счисления здесь выписано явно. Суть в том, что если мы не знаем х, то мы не можем производить переносы. Мы не знаем, что 3*x^3 это то x^4+x^3, потому что мы не знаем, что х = 2. В полиномиальной арифметике отношения между коэффициентами не определены, и коэффициенты при разных степенях полностью изолированы.

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

(x^3 + x^2 + x^0)(x^3 + x^1 + x^0) =

(x^6 + x^4 + x^3 + x^5 + x^3 + x^2 + x^3 + x^1 + x^0) =

x^6 + x^5 + x^4 + 3*x^3 + x^2 + x^1 + x^0 =

x^6 + x^5 + x^4 + x^3 + x^2 + x^1 + x^0

В дальнейшем мы не будем упоминать полиномиальное представление, поскольку это может только усложнить изложение, и будем говорить об эквивалентной системе, назывемой «двоичная арифметика без переноса».

5. Двоичная арифметика без переноса

Как нетрудно заметить с отменой переноса исчезают и различия между сложением и вычитанием. Для каждой позиции есть 4 варианта:

0 + 0 = 0 — 0 = 0 0 + 1 = 0 — 1 = 1 1 + 0 = 1 — 0 = 1 1 + 1 = 1 — 1 = 0

То есть, фактически, сложение и вычитание в CRC-арифметике эквивалентны операции XOR, которая является обратной самой себе, и это очень удобно.

Объединение сложения и вычитания приводит также к исчезновению строгого отношения порядка. Действительно, то что 1010b больше чем 10b остается верным, но уже нет причин полагать, что 1010b больше чем 1001b. Поэтому вводится слабое отношение порядка: число X больше числа Y если номер позиции старшей 1-ы числа X больше номера позиции старшей 1-ы числа Y ( этот номер, отсчитываемый с 0, называется длиной числа ). Умножение и деление выполняются по обычным схемам с учетом новых операций сложения и вычитания.

Полезно ввести понятия кратности и делимости. Будем говорить, что число A кратно числу B ( или A делится на B) в смысле CRC-арифметики, если A можно получить складывая (XOR) результаты различных сдвигов ( влево) числа B. Например, 0111010110b кратно 011b:

Однако 0111010111b нельзя составить из сдвигов 011b, поэтому говорят, что 0111010111b не делится на 011b.

6. Пример вычисления CRC

Теперь, когда построена CRC-арифметика, мы можем интерпретировать вычисление CRC как взятие остатка от деления. В этом пункте мы обсудим некоторые детали и приведем пример.

Во первых, необходимо выбрать делитель. Его длина должна на один бит превосходить требуемую длину CRC. То есть, для получения CRC16 необходимо взять 17-битный делитель (в соответствии с данным выше определением его длина будет равна 16-и). Поскольку остаток должен быть меньше делителя (иначе можно выполнить деление еще раз), мы получим CRC требуемой длины.

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

Перед делением сообщение дополняют W нулями ( где W — длина делителя)

CRC дописывается в конец, так что передаваемое сообщение будет таким: 11010110111110. Приемник может либо:

• Отделить контрольную сумму от сообщения, добавить нули в конец сообщения, сосчитать CRC, и сравнить с полученным.
• Расчитать CRC всей переданной цепочки ( не добавляя нули ) и посмотреть получится ли ноль.

Далее мы будем использовать второй способ.

Итак операции которые необходимо произвести, при использовании CRC-алгоритмов:

• Выбрать длину W и делитель G ( длиной W ).
• Добавить W нулей к исходному сообщению М. ( Полученное обозначим M’ )
• Разделить M’ на G используя CRC-арифметику. Остаток — контрольная сумма.

7. Выбор делителя

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

Во-первых отметим, что передаваемое сообщение Т кратно делителю. Действительно, последние W бит сообщения T — остаток от деления сообщения M’ на делитель. То есть Т=М’+CRC ( + означает сложение, а не добавление в конец ), а поскольку сложение одновременно является вычитанием, то оно «уменьшает» M’ до ближайшего кратного G.

Теперь предположим, что сообщение пришло с ошибками. Это можно записать так T+E, где E — вектор ошибки. Приемник делит T+E на G. Поскольку T mod G = 0, то (T+E) mod G = E mod G. Поэтому способность метода отлавливать специфические ошибки будет определяться количеством E кратных G, поскольку такие помехи не могут быть обнаружены.

Перечислим некоторые типы ошибок, которые мы в первую очередь можем ожидать при передаче.

• Ошибка в одном бите. E = 100. 000. Такие ошибки можно отловить если в G не менее 2-х битов установлено в 1. Как бы мы ни складывали сдвиги таких G, всегда получим строку в которой по крайней мере 2 еденичных бита, значит E не может быть кратно G.
• Ошибка в двух битах. Надо подобрать G для которых не служат кратными числа типа 011, 0101, 01001, и.т.д. О таких G см. Tanenbaum A.S. «Computer Networks».
• Ошибка в нечетном количестве бит. Такие ошибки можно отловить, взяв G, в котором количество бит четно. Это следует из того,что:
  • CRC-умножение это просто XOR константы в аккумулятор с разными сдвигами.
  • XOR — поразрядная операция, инвертирующая те биты аккумулятора, напротив которых в прибавляемой строке стоит 1.
  • Если сделать XOR значения с четным числом едениц, то в аккумуляторе инвертируется четное количество едениц, в результате чего четность количества едениц аккумулятора сохранится.
• Ошибка пакета. E = 000. 000111. 111000. 000. То есть ошибка локализована в непрерывном пакете внутри сообщения. Такое E можно представить в виде произведения: E=(1000. 00)*(111111111), где в первой скобке Z нулей, а во второй — N едениц. Если в G младший бит — 1, то левый множитель не может быть делителем G, тогда, если G длиннее правого множителя, то ошибка будет отловлена.

Приводим ниже наиболее известные делители ( в скобках номера единичных битов ):

8. Особенности различных алгоритмов

Основная задача данного обзора — дать полную спецификацию CRC-16. Этот вариант — один из наиболее простых из класса CRC. Он полностью укладывается в теоретическую модель, описанную выше. Однако тема связанная с алгоритмами CRC этим далеко не исчерпывается. Например, реализация этих алгоритмов составляет отдельный вопрос, не менее, а, скорее, и более сложный чем теоретические основы. На первый взгляд с реализацией не может возникнуть никаких вопросов, поскольку операции XOR и SHL включены в систему команд любого процессора, что позволяет создать простую и эффективную реализацию на машинном языке. Однако в последнее время стали популярными сложные алгоритмы, далеко отстоящие от обычной чхемы деления. В первую очередь это так называемая табличная реализация и ее модификации, цель которых в переходе от цикла по всем битам к циклу по большим порциям данных — байтам, словам, и.т.д. Особенности различных реализаций привели к новым модификациям самого алгоритма. Появились такие понятия как начальное и конечное значения.

Начальное ( стартовое ) значение записывается в аккумулятор перед началом генерации CRC. Алгоритм CRC16 в инициализирует аккумулятор нулем, выполняя обыкновенную схему деления. Однако выбор нулевого стартового значения не самый удачный. Нетрудно видеть, что нули в начале сообщения являются «слепым пятном» алгоритма ( т. е. их число не повлияет на значение контрольной суммы ), и, в то же время, такие сообщения достаточно часто встречаются. Введение начального значения, которое с точки зрения схемы деления эквивалентно дописыванию в начало сообщения ненулевого значения позволяет обойти эту проблему.

Конечное значение просто складывается (XOR) с остатком деления.

Модификация CRC16/CITT использует стартовое значение FFFFh. Алгоритм CRC32 использует FFFFFFFFh в качестве начального и конечного значений.

Источник

1Теория, лежащая в основе расчёта CRC

Для начала давайте немного разберёмся в теории. Итак, что же такое CRC? Если кратко, это одна из разновидностей подсчёта контрольной суммы. Контрольная сумма – это метод проверки целостности принятой информации на стороне приёмника при передаче по каналам связи. Например, одна из простейших проверок – использование бита чётности. Это когда суммируются все биты передаваемого сообщения, и если сумма оказывается чётной, то в конец сообщения добавляется 0, если нечётной – то 1. При приёме также подсчитывается сумма битов сообщения, и сравнивается с принятым битом чётности. Если они отличаются, значит при передаче возникли ошибки, и передаваемая информация была искажена.

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

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

Что такое исходное сообщение – понятно. Это непрерывная последовательность битов произвольной длины.

Что за константа, на которую мы должны делить исходное сообщение? Это некоторое число также любой длины, но обычно используются числа, кратные 1 байту – 8, 16 или 32 бита. Просто так легче считать, ведь компьютеры работают именно с байтами, а не с битами.

Константу-делитель обычно записывают в виде полинома (многочлена) вот таким образом: x⁸ + x² + x¹ + x⁰. Здесь степень числа «x» означает позицию бита-единицы в числе, начиная с нулевой, а старший разряд указывает на степень полинома и отбрасывается при интерпретации числа. То есть записанное ранее число – это не что иное как 100000111 в двоичной системе счисления.

Обычно при записи многочлена старший разряд подразумевается, но не пишется. То есть вышеуказанный многочлен можно было бы записать в двоичной системе как (1)00000111. В скобках я указал подразумеваемый старший разряд числа. Поэтому говорят, что многочлен равен 7 в десятичной системе счисления (111b = 7d).

Вот ещё пример: (x¹⁶ +) x¹⁵ + x² + x⁰ = (1)1000000000000101 = 0x8005 = 32773.

Обычно используются некие стандартные многочлены для разных типов CRC. Вот некоторые из них:

В посвящённой расчёту CRC статье на Википедии есть большая таблица образующих полиномов.

Так как же считать контрольную сумму? Существует базовый метод – деление сообщения на полином «в лоб» – и его модификации в целях уменьшения количества вычислений и, соответственно, ускорения расчёта CRC. Для начала мы рассмотрим именно базовый метод.

В общем виде деление числа на многочлен выполняется по такому алгоритму. Алгоритм вычисления контрольной суммы CRC:

1. Создаётся массив (регистр), заполненный нулями, равный по длине разрядности (степени) полинома.
2. Исходное сообщение дополняется нулями в младших разрядах, в количестве, равном числу разрядов полинома.
3. В младший разряд регистра заносится один старший бит сообщения, а из старшего разряда регистра выдвигается один бит.
4. Если выдвинутый бит равен «1», то производится инверсия битов (операция XOR, исключающее ИЛИ) в тех разрядах регистра, которые соответствуют единицам в полиноме.
5. Если в сообщении ещё есть биты, переходим к шагу 3).
6. Когда все биты сообщения поступили в регистр и были обработаны этим алгоритмом, в регистре остаётся остаток от деления, который и является контрольной суммой CRC.

Назовём этот метод расчёта CRC метод побитового сдвига или простой метод.

Рисунок иллюстрирует деление исходной последовательности битов на число (1)00000111, или многочлен x⁸ + x² + x¹ + x⁰.

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

Осталась ещё пара моментов, о которых стоит сказать. Как вы могли заметить, сообщение можно разделить на любое число. Как его выбрать? Существует ряд стандартных полиномов, которые используются при вычислении CRC. Например, для CRC32 это может быть число 0x04C11DB7, а для CRC16 это может быть 0x8005.

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

Также при расчётах непосредственно перед выдачей финальную контрольную сумму CRC можно поделить на какое-то другое число.

И последнее. Байты сообщения при записи в регистр могут помещаться как старшим битом «вперёд», так и наоборот, младшим. И результирующая CRC также может выдаваться, начиная со старшего бита или с младшего.

Изменение порядка битов в байте на обратный назовём «обращение», «реверс» или «отзеркаливание» байта.

Итого имеются 6 параметров, которые влияют на значение контрольной суммы:

• порядок CRC;
• образующий многочлен (его иногда называют «генераторный полином», переводя с английского буквально);
• начальное содержимое регистра;
• значение, с которым производится финальное XOR;
• реверс байтов информационного сообщения;
• реверс байтов CRC перед финальным XOR.

2Расчёт контрольной суммы CRC методом побитового сдвига

На основании всего вышеизложенного, давайте напишем функцию на языке Visual Basic .NET, которая будет рассчитывать контрольную сумму CRC, принимая ряд параметров, которые я описал выше, и возвращая значение CRC в виде 32-разрядного беззнакового числа.

Код расчёта CRC методом побитового сдвига на языке VB.NET

''' <summary>
''' Возвращает контрольную сумму типа CRC, рассчитанную методом побитового сдвига.
''' </summary>
''' <param name="bytes">Входная последовательность байтов (исходное сообщение).</param>
''' <param name="poly">Образующий многочлен разрядности <paramref name="width">width</paramref>.</param>
''' <param name="width">Порядок CRC в битах, 8/16/32.</param>
Public Shared Function GetCrc_Simple(ByVal bytes As Byte(), ByVal poly As UInteger, Optional ByVal width As Integer = 32, Optional ByVal initReg As UInteger = &HFFFFFFFFUI, Optional ByVal finalXor As UInteger = &HFFFFFFFFUI, Optional ByVal reverseBytes As Boolean = True, Optional ByVal reverseCrc As Boolean = True) As UInteger

  Dim widthInBytes As Integer = width  8
  
  'Дополняем сообщение width нулями (расчёт в байтах):
  ReDim Preserve bytes(bytes.Length - 1 + widthInBytes)
  
  'Создаём очередь битов из сообщения:
  Dim msgFifo As New Queue(Of Boolean)(bytes.Count * 8 - 1)
  For Each b As Byte In bytes
    Dim ba As New BitArray({b})
    If reverseBytes Then
      For i As Integer = 0 To 7
          msgFifo.Enqueue(ba(i))
      Next
    Else
      For i As Integer = 7 To 0 Step -1
          msgFifo.Enqueue(ba(i))
      Next
    End If
  Next
  
  'Создаём очередь из битов начального заполнения регистра:
  Dim initBytes As Byte() = BitConverter.GetBytes(initReg)
  Dim initBytesReversed As IEnumerable(Of Byte) = (From b As Byte In initBytes Take widthInBytes).Reverse
  Dim initFifo As New Queue(Of Boolean)(width - 1)
  For Each b As Byte In initBytesReversed
    Dim ba As New BitArray({b})
    If Not reverseBytes Then
       For i As Integer = 0 To 7
           initFifo.Enqueue(ba(i))
       Next
    Else
      For i As Integer = 7 To 0 Step -1
          initFifo.Enqueue(ba(i))
      Next
    End If
  Next
  
  'Сдвиг и XOR:
  Dim register As UInteger = 0 'заполняем width-разрядный регистр нулями.
  Do While msgFifo.Count > 0
    
    Dim poppedBit As Integer = CInt(register >> (width - 1)) And 1 'определить перед сдвигом регистра.
    
    Dim shiftedBit As Byte = Convert.ToByte(msgFifo.Dequeue)
    If initFifo.Count > 0 Then
      Dim b As Byte = Convert.ToByte(initFifo.Dequeue)
      shiftedBit = shiftedBit Xor b
    End If
    
    register = register << 1
    register = register Or shiftedBit
    
    If poppedBit = 1 Then
      register = register Xor poly
    End If
  Loop
  
  'Финальные преобразования:
  Dim crc As UInteger = register 'Регистр содержит остаток от деления - контрольную сумму.
  If reverseCrc Then
    crc = reflect(crc, width)
  End If
  crc = crc Xor finalXor
  crc = crc And (&HFFFFFFFFUI >> (32 - width)) 'маскируем младшие разряды.
  
  Return crc

End Function

''' <summary>
''' Обращает заданное число младших битов переданного числа.
''' </summary>
''' <param name="inpValue">Число, которое требуется «отзеркалить».</param>
''' <param name="bitsToReflect">Сколько младших битов обратить, 0..32.</param>
''' <returns></returns>
''' <remarks>Например: reflect(&H3E23, 3) == &H3E26.</remarks>
Private Shared Function reflect(ByVal inpValue As UInteger, Optional ByVal bitsToReflect As Integer = 32) As UInteger
    Dim t As UInteger = inpValue
    Dim reflected As UInteger = inpValue
    For i As Integer = 0 To bitsToReflect - 1
        Dim bm As UInteger = bitMask(bitsToReflect - 1 - i)
        If (t And 1) = 1 Then
            reflected = reflected Or bm
        Else
            reflected = reflected And Not bm
        End If
        t >>= 1
    Next
    Return reflected
End Function

''' <summary>
''' Возвращает наибольший разряд числа.
''' </summary>
''' <param name="number">Число, разрядность которого следует определить.</param>
''' <returns></returns>
Private Shared Function bitMask(ByVal number As Integer) As UInteger
    Dim res As UInteger = (1UI << number)
    Return res
End Function

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

Предлагаемая программа плохо масштабируема. То есть она работает хорошо при вычислении контрольной суммы CRC для коротких сообщений, длиной до нескольких десятков килобайтов. Я писал её с целью только продемонстрировать работу простого алгоритма, и не занимался оптимизацией. При расчёте CRC для длинного сообщения, размером десятки или сотни мегабайтов, программа будет сильно загружать процессор и память, т.к. всё сообщение целиком загружается в очередь. Этому способствует метод преобразования числа в битовую последовательность, используя Queue(Of Boolean). Для работы с такими большими сообщениями желательно реализовать промежуточный буфер, который будет передавать сообщение в программу небольшими порциями.

Зато у этой программы есть одно преимущество: она может быть использована для расчёта CRC любого порядка, не обязательно 8, 16 или 32. Это может быть CRC5 или CRC49. Только для чисел больше 32-х разрядов нужно изменить соответствующим образом входные параметры – допустим, poly передавать не как UInteger, а как ULong, или передавать его в виде битового массива (тогда теоретически порядок CRC вообще будет неограничен).

3Расчёт контрольной суммы CRC табличным методом

Для сокращения числа вычислений из предыдущего метода – метода побитового сдвига – придуманы некоторые оптимизации.

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

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

Я не буду здесь вдаваться в теорию, она довольно сложна и много раз описана в других статьях. В частности, очень хорошее и подробное описание бинарной арифметики, лежащей в основе расчёта CRC, и описание табличного метода, даётся в статье Ross N. Williams: «A Painless Guide to CRC Error Detection Algorithms». Рекомендую к прочтению обязательно! Оригинальный текст – в приложении к статье, а русский перевод легко найти в интернете.

Ну что же, пришло время для самой программы. Она будет несколько длиннее предыдущей. По сути, это реализация алгоритма из указанной статьи в стиле объектно-ориентированного программирования. Опять же будем писать программу на моём любимом языке программирования VB.NET. Я назвал этот класс RocksoftCrcModel, по названию компании, в которой работал автор указанной статьи.

Код расчёта CRC табличным методом на языке VB.NET

    ''' <summary>
    ''' Реализует алгоритм расчёта CRC методом Rocksoft^tm Model CRC.
    ''' </summary>
    Public Class RocksoftCrcModel

#Region "PROPS AND FIELDS"

        ''' <summary>
        ''' Таблица предвычисленных значений для расчёта контрольной суммы.
        ''' </summary>
        Public ReadOnly CrcLookupTable(255) As UInteger

        ''' <summary>
        ''' Порядок CRC, в битах (строго 8, 16 или 32).
        ''' Изменение этого свойства ведёт к пересчёту таблицы.
        ''' </summary>
        Public Property CrcWidth As Integer
            Get
                Return _CrcWidth
            End Get
            Set(value As Integer)
                If _CrcWidth <> value Then
                    _CrcWidth = value
                    _TopBit = getBitMask(_CrcWidth - 1)
                    _WidMask = (((1UI << (_CrcWidth - 1)) - 1UI) << 1) Or 1UI
                    generateLookupTable()
                End If
            End Set
        End Property
        Private _CrcWidth As Integer = 32

        ''' <summary>
        ''' Образующий многочлен.
        ''' Изменение этого свойства ведёт к пересчёту таблицы.
        ''' </summary>
        Public Property Polynom As UInteger
            Get
                Return _Polynom
            End Get
            Set(value As UInteger)
                If _Polynom <> value Then
                    _Polynom = value
                    generateLookupTable()
                End If
            End Set
        End Property
        Private _Polynom As UInteger = &H4C11DB7

        ''' <summary>
        ''' Обращать ли байты сообщения?
        ''' Изменение этого свойства ведёт к пересчёту таблицы.
        ''' </summary>
        Public Property ReflectIn As Boolean
            Get
                Return _ReflectIn
            End Get
            Set(value As Boolean)
                If _ReflectIn <> value Then
                    _ReflectIn = value
                    generateLookupTable()
                End If
            End Set
        End Property
        Private _ReflectIn As Boolean = True

        ''' <summary>
        ''' Начальное содержимое регистра.
        ''' </summary>
        Public Property InitRegister As UInteger
            Get
                Return _InitRegister
            End Get
            Set(value As UInteger)
                If _InitRegister <> value Then
                    _InitRegister = value
                End If
            End Set
        End Property
        Private _InitRegister As UInteger = &HFFFFFFFFUI

        ''' <summary>
        ''' Обращать выходное значение CRC?
        ''' </summary>
        Public Property ReflectOut As Boolean
            Get
                Return _ReflectOut
            End Get
            Set(value As Boolean)
                If _ReflectOut <> value Then
                    _ReflectOut = value
                End If
            End Set
        End Property
        Private _ReflectOut As Boolean = True

        ''' <summary>
        ''' Значение, с которым XOR-ится выходное значение CRC.
        ''' </summary>
        Public Property XorOut As UInteger
            Get
                Return _XorOut
            End Get
            Set(value As UInteger)
                If _XorOut <> value Then
                    _XorOut = value
                End If
            End Set
        End Property
        Private _XorOut As UInteger = &HFFFFFFFFUI

#End Region '/PROPS AND FIELDS

#Region "READ-ONLY PROPS"

        ''' <summary>
        ''' Возвращает старший разряд полинома.
        ''' </summary>
        ReadOnly Property TopBit As UInteger
            Get
                Return _TopBit
            End Get
        End Property
        Private _TopBit As UInteger = getBitMask(CrcWidth - 1)

        ''' <summary>
        ''' Возвращает длинное слово со значением (2^width)-1.
        ''' </summary>
        Private ReadOnly Property WidMask As UInteger
            Get
                Return _WidMask
            End Get
        End Property
        Private _WidMask As UInteger = (((1UI << (CrcWidth - 1)) - 1UI) << 1) Or 1UI

#End Region '/READ-ONLY PROPS

#Region "CTOR"

        ''' <summary>
        ''' Конструктор, инициализированный параметрами по умолчанию для алгоритма CRC32.
        ''' </summary>
        Public Sub New()
            generateLookupTable()
        End Sub

        ''' <summary>
        ''' Инициализирует новый экземпляр параметрической модели CRC с настраиваемыми параметрами.
        ''' </summary>
        ''' <param name="width">Разрядность контрольной суммы в битах.</param>
        ''' <param name="poly">Полином.</param>
        ''' <param name="initReg">начальное содержимое регистра.</param>
        ''' <param name="isReflectIn">Обращать ли входящие байты сообщения?</param>
        ''' <param name="isReflectOut">Обратить ли CRC перед финальным XOR.</param>
        ''' <param name="xorOut">Конечное значение XOR.</param>
        Public Sub New(ByVal width As Integer, ByVal poly As UInteger, Optional ByVal initReg As UInteger = &HFFFFFFFFUI, Optional ByVal isReflectIn As Boolean = True, Optional ByVal isReflectOut As Boolean = True, Optional ByVal xorOut As UInteger = &HFFFFFFFFUI)
            Me.CrcWidth = width
            Me.Polynom = poly
            Me.InitRegister = initReg
            Me.ReflectIn = isReflectIn
            Me.ReflectOut = isReflectOut
            Me.XorOut = xorOut
            generateLookupTable()
        End Sub

#End Region '/CTOR

#Region "ВЫЧИСЛЕНИЕ CRC"

        ''' <summary>
        ''' Вычисляет значение контрольной суммы переданного сообщения.
        ''' </summary>
        ''' <param name="message">Исходное сообщение, для которого нужно посчитать контрольную сумму.</param>
       Public Function ComputeCrc(ByRef message As Byte()) As UInteger
            Dim registerContent As UInteger = InitRegister 'Содержимое регистра в процессе пересчёта CRC.
            For Each b As Byte In message
                registerContent = getNextRegisterContent(registerContent, b)
            Next
            Dim finalCrc As UInteger = getFinalCrc(registerContent)
            Return finalCrc
        End Function

        ''' <summary>
        ''' Вычисляет значение контрольной суммы переданного сообщения и возвращает его в виде массива байтов.
        ''' </summary>
        ''' <param name="message">Исходное сообщение, для которого нужно посчитать контрольную сумму.</param>
        Public Function ComputeCrcAsBytes(ByRef message As Byte()) As Byte()
            Dim crc As UInteger = ComputeCrc(message)
            Dim crcBytes As Byte() = BitConverter.GetBytes(crc)
            Dim crcBytesOrdered(crcBytes.Length - 1) As Byte
            For i As Integer = 0 To crcBytes.Length - 1
                crcBytesOrdered(i) = crcBytes(crcBytes.Length - 1 - i)
            Next
            Return crcBytesOrdered
        End Function

        ''' <summary>
        ''' Обрабатывает один байт сообщения (0..255).
        ''' </summary>
        ''' <param name="prevRegContent">Содержимое регистра на предыдущем шаге.</param>
        ''' <param name="value">Значение очередного байта из сообщения.</param>
        Private Function getNextRegisterContent(ByVal prevRegContent As UInteger, ByVal value As Byte) As UInteger
            Dim uValue As UInteger = value
            If ReflectIn Then
                uValue = reflect(uValue, 8)
            End If
            Dim reg As UInteger = prevRegContent
            reg = reg Xor (uValue << (CrcWidth - 8))
            For i As Integer = 0 To 7
                If (reg And TopBit) = TopBit Then
                    reg = (reg << 1) Xor Polynom
                Else
                    reg <<= 1
                End If
                reg = reg And WidMask()
            Next
            Return reg
        End Function

        ''' <summary>
        ''' Возвращает значение CRC для обработанного сообщения.
        ''' </summary>
        ''' <param name="regContent">Значение регистра до финального обращения и XORа.</param>
        Private Function getFinalCrc(ByVal regContent As UInteger) As UInteger
            If ReflectOut Then
                Dim res As UInteger = XorOut Xor reflect(regContent, CrcWidth)
                Return res
            Else
                Dim res As UInteger = XorOut Xor regContent
                Return res
            End If
        End Function

#End Region '/ВЫЧИСЛЕНИЕ CRC

#Region "РАСЧЁТ ТАБЛИЦЫ"

        ''' <summary>
        ''' Вычисляет таблицу предвычисленных значений для расчёта контрольной суммы.
        ''' </summary>
        Private Sub generateLookupTable()
            For i As Integer = 0 To 255
                CrcLookupTable(i) = generateTableItem(i)
            Next
        End Sub

        ''' <summary>
        ''' Рассчитывает один байт таблицы значений для расчёта контрольной суммы
        ''' по алгоритму Rocksoft^tm Model CRC Algorithm.
        ''' </summary>
        ''' <param name="index">Индекс записи в таблице, 0..255.</param>
        Private Function generateTableItem(ByVal index As Integer) As UInteger

            Dim inbyte As UInteger = CUInt(index)

            If ReflectIn Then
                inbyte = reflect(inbyte, 8)
            End If

            Dim reg As UInteger = inbyte << (CrcWidth - 8)

            For i As Integer = 0 To 7
                If (reg And TopBit) = TopBit Then
                    reg = (reg << 1) Xor Polynom
                Else
                    reg <<= 1
                End If
            Next

            If ReflectIn Then
                reg = reflect(reg, CrcWidth)
            End If

            Dim res As UInteger = reg And WidMask
            Return res

        End Function

#End Region '/РАСЧЁТ ТАБЛИЦЫ

#Region "ВСПОМОГАТЕЛЬНЫЕ"

        ''' <summary>
        ''' Возвращает наибольший разряд числа.
        ''' </summary>
        ''' <param name="number">Число, разрядность которого следует определить, степень двойки.</param>
        Private Function getBitMask(ByVal number As Integer) As UInteger
            Dim res As UInteger = 1UI << number
            Return res
        End Function

        ''' <summary>
        ''' Обращает заданное число младших битов переданного числа.
        ''' </summary>
        ''' <param name="value">Число, которое требуется обратить («отзеркалить»).</param>
        ''' <param name="bitsToReflect">Сколько младших битов числа обратить, 0..32.</param>
        ''' <remarks>Например: reflect(0x3E23, 3) == 0x3E26.</remarks>
        Private Function reflect(ByVal value As UInteger, Optional ByVal bitsToReflect As Integer = 32) As UInteger
            Dim t As UInteger = value
            Dim reflected As UInteger = value
            For i As Integer = 0 To bitsToReflect - 1
                Dim bm As UInteger = getBitMask(bitsToReflect - 1 - i)
                If (t And 1) = 1 Then
                    reflected = reflected Or bm
                Else
                    reflected = reflected And Not bm
                End If
                t >>= 1
            Next
            Return reflected
        End Function

#End Region '/ВСПОМОГАТЕЛЬНЫЕ

    End Class 

Этот код полностью готов к использованию, можно брать и применять. Пользоваться данной программой так:

• создать экземпляр класса RocksoftCrcModel(), передав в конструктор параметры модели CRC;
• для расчёта контрольной суммы, вызвать метод данного объекта ComputeCrc() или ComputeCrcAsBytes(), передав в качестве параметра информационное сообщение, для которого необходимо посчитать контрольную сумму;
• если меняются параметры модели CRC, таблица автоматически пересчитывается, и новый экземпляр класса можно не создавать.

Приведу пример использования данного класса для алгоритма CRC16. В качестве сообщения message будем использовать массив байтов, который представляет собой строку «123456789» в коде ASCII, которая используется во многих онлайн-калькуляторах CRC:

Dim crcModel As New RocksoftCrcModel(16, &H8005, 0, True, True, 0)
Dim message as Byte() = {&H31, &H32, &H33, &H34, &H35, &H36, &H37, &H38, &H39}
Dim crc As UInteger = crcModel.ComputeCrc(message)

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

Для любителей C# перепишем данный класс таким образом:

Код расчёта CRC табличным методом на языке C# (разворачивается)

using System;

namespace CRC
{
  /// <summary>Реализует алгоритм расчёта CRC методом Rocksoft^tm Model CRC.</summary>
  public class RocksoftCrcModel
  {
    /// <summary>Таблица предвычисленных значений для расчёта контрольной суммы.</summary>
    public readonly uint[] CrcLookupTable;
    private int _CrcWidth;
    private uint _Polynom;
    private bool _ReflectIn;
    private uint _InitRegister;
    private bool _ReflectOut;
    private uint _XorOut;
    private uint _TopBit;
    private uint _WidMask;

    /// <summary>
    /// Порядок CRC, в битах (8/16/32).
    /// Изменение этого свойства ведёт к пересчёту таблицы.
    /// </summary>
    public int CrcWidth
    {
      get
      {
        return this._CrcWidth;
      }
      set
      {
        if (this._CrcWidth == value)
          return;
        this._CrcWidth = value;
        this._TopBit = this.getBitMask(checked (this._CrcWidth - 1));
        this._WidMask = (uint) ((int) checked (unchecked ((uint) (1 << checked (this._CrcWidth - 1))) - 1U) << 1 | 1);
        this.generateLookupTable();
      }
    }

    /// <summary>
    /// Образующий многочлен.
    /// Изменение этого свойства ведёт к пересчёту таблицы.
    /// </summary>
    public uint Polynom
    {
      get
      {
        return this._Polynom;
      }
      set
      {
        if ((int) this._Polynom == (int) value)
          return;
        this._Polynom = value;
        this.generateLookupTable();
      }
    }

    /// <summary>
    /// Обращать байты сообщения?
    /// Изменение этого свойства ведёт к пересчёту таблицы.
    /// </summary>
    public bool ReflectIn
    {
      get
      {
        return this._ReflectIn;
      }
      set
      {
        if (this._ReflectIn == value)
          return;
        this._ReflectIn = value;
        this.generateLookupTable();
      }
    }

    /// <summary>Начальное содержимое регистра.</summary>
    public uint InitRegister
    {
      get
      {
        return this._InitRegister;
      }
      set
      {
        if ((int) this._InitRegister == (int) value)
          return;
        this._InitRegister = value;
      }
    }

    /// <summary>Обращать выходное значение CRC?</summary>
    public bool ReflectOut
    {
      get
      {
        return this._ReflectOut;
      }
      set
      {
        if (this._ReflectOut == value)
          return;
        this._ReflectOut = value;
      }
    }

    /// <summary>Значение, с которым XOR-ится выходное значение CRC.</summary>
    public uint XorOut
    {
      get
      {
        return this._XorOut;
      }
      set
      {
        if ((int) this._XorOut == (int) value)
          return;
        this._XorOut = value;
      }
    }

    /// <summary>Возвращает старший разряд полинома.</summary>
    public uint TopBit
    {
      get
      {
        return this._TopBit;
      }
    }

    /// <summary>Возвращает длинное слово со значением (2^width)-1.</summary>
    /// <returns></returns>
    /// <remarks></remarks>
    private uint WidMask
    {
      get
      {
        return this._WidMask;
      }
    }

    /// <summary>
    /// Конструктор, инициализированный параметрами по умолчанию для алгоритма CRC32.
    /// </summary>
    public RocksoftCrcModel()
    {
      base..ctor();
      this.CrcLookupTable = new uint[256];
      this._CrcWidth = 32;
      this._Polynom = 79764919U;
      this._ReflectIn = true;
      this._InitRegister = uint.MaxValue;
      this._ReflectOut = true;
      this._XorOut = uint.MaxValue;
      this._TopBit = this.getBitMask(checked (this.CrcWidth - 1));
      this._WidMask = (uint) ((int) checked (unchecked ((uint) (1 << checked (this.CrcWidth - 1))) - 1U) << 1 | 1);
      this.generateLookupTable();
    }

    /// <summary>
    /// Инициализирует новый экземпляр параметрической модели CRC с настраиваемыми параметрами.
    /// </summary>
    /// <param name="width">Разрядность контрольной суммы в битах.</param>
    /// <param name="poly">Полином.</param>
    /// <param name="initReg">начальное содержимое регистра.</param>
    /// <param name="isReflectIn">Обращать ли входящие байты сообщения?</param>
    /// <param name="isReflectOut">Обратить ли CRC перед финальным XOR.</param>
    /// <param name="xorOut">Конечное значение XOR.</param>
    public RocksoftCrcModel(int width, uint poly, uint initReg = 4294967295, bool isReflectIn = true, bool isReflectOut = true, uint xorOut = 4294967295)
    {
      base..ctor();
      this.CrcLookupTable = new uint[256];
      this._CrcWidth = 32;
      this._Polynom = 79764919U;
      this._ReflectIn = true;
      this._InitRegister = uint.MaxValue;
      this._ReflectOut = true;
      this._XorOut = uint.MaxValue;
      this._TopBit = this.getBitMask(checked (this.CrcWidth - 1));
      this._WidMask = (uint) ((int) checked (unchecked ((uint) (1 << checked (this.CrcWidth - 1))) - 1U) << 1 | 1);
      this.CrcWidth = width;
      this.Polynom = poly;
      this.InitRegister = initReg;
      this.ReflectIn = isReflectIn;
      this.ReflectOut = isReflectOut;
      this.XorOut = xorOut;
      this.generateLookupTable();
    }

    /// <summary>Вычисляет значение контрольной суммы переданного сообщения.</summary>
    /// <param name="message">Исходное сообщение, для которого нужно посчитать контрольную сумму.</param>
    /// <returns></returns>
    public uint ComputeCrc(ref byte[] message)
    {
      uint num1 = this.InitRegister;
      byte[] numArray = message;
      int index = 0;
      while (index < numArray.Length)
      {
        byte num2 = numArray[index];
        num1 = this.getNextRegisterContent(num1, num2);
        checked { ++index; }
      }
      return this.getFinalCrc(num1);
    }

    /// <summary>
    /// Вычисляет значение контрольной суммы переданного сообщения и возвращает его в виде массива байтов.
    /// </summary>
    /// <param name="message">Исходное сообщение, для которого нужно посчитать контрольную сумму.</param>
    /// <returns></returns>
    public byte[] ComputeCrcAsBytes(byte[] message)
    {
      byte[] bytes = BitConverter.GetBytes(this.ComputeCrc(ref message));
      byte[] numArray = new byte[checked (bytes.Length - 1 + 1)];
      int num1 = 0;
      int num2 = checked (bytes.Length - 1);
      int index = num1;
      while (index <= num2)
      {
        numArray[index] = bytes[checked (bytes.Length - 1 - index)];
        checked { ++index; }
      }
      return numArray;
    }

    /// <summary>Обрабатывает один байт сообщения (0..255).</summary>
    /// <param name="prevRegContent">Содержимое регистра на предыдущем шаге.</param>
    /// <param name="value">Значение очередного байта из сообщения.</param>
    private uint getNextRegisterContent(uint prevRegContent, byte value)
    {
      uint num1 = (uint) value;
      if (this.ReflectIn)
        num1 = this.reflect(num1, 8);
      uint num2 = prevRegContent ^ num1 << checked (this.CrcWidth - 8);
      int num3 = 0;
      do
      {
        num2 = (((int) num2 & (int) this.TopBit) != (int) this.TopBit ? num2 << 1 : num2 << 1 ^ this.Polynom) & this.WidMask;
        checked { ++num3; }
      }
      while (num3 <= 7);
      return num2;
    }

    /// <summary>Возвращает значение CRC для обработанного сообщения.</summary>
    /// <param name="regContent">Значение регистра до финального обращения и XORа.</param>
    /// <returns></returns>
    private uint getFinalCrc(uint regContent)
    {
      if (this.ReflectOut)
        return this.XorOut ^ this.reflect(regContent, this.CrcWidth);
      return this.XorOut ^ regContent;
    }

    /// <summary>Вычисляет таблицу предвычисленных значений для расчёта контрольной суммы.</summary>
    private void generateLookupTable()
    {
      int index = 0;
      do
      {
        this.CrcLookupTable[index] = this.generateTableItem(index);
        checked { ++index; }
      }
      while (index <= (int) byte.MaxValue);
    }

    /// <summary>
    /// Рассчитывает один байт таблицы значений для расчёта контрольной суммы
    /// по алгоритму Rocksoft^tm Model CRC Algorithm.
    /// </summary>
    /// <param name="index">Индекс записи в таблице, 0..255.</param>
    private uint generateTableItem(int index)
    {
      uint num1 = checked ((uint) index);
      if (this.ReflectIn)
        num1 = this.reflect(num1, 8);
      uint num2 = num1 << checked (this.CrcWidth - 8);
      int num3 = 0;
      do
      {
        if (((int) num2 & (int) this.TopBit) == (int) this.TopBit)
          num2 = num2 << 1 ^ this.Polynom;
        else
          num2 <<= 1;
        checked { ++num3; }
      }
      while (num3 <= 7);
      if (this.ReflectIn)
        num2 = this.reflect(num2, this.CrcWidth);
      return num2 & this.WidMask;
    }

    /// <summary>Возвращает наибольший разряд числа.</summary>
    /// <param name="number">Число, разрядность которого следует определить, степень двойки.</param>
    /// <returns></returns>
    private uint getBitMask(int number)
    {
      return (uint) (1 << number);
    }

    /// <summary>Обращает заданное число младших битов переданного числа.</summary>
    /// <param name="value">Число, которое требуется обратить ("отзеркалить").</param>
    /// <param name="bitsToReflect">Сколько младших битов числа обратить, 0..32.</param>
    /// <returns></returns>
    /// <remarks>Например: reflect(0x3E23, 3) == 0x3E26.</remarks>
    private uint reflect(uint value, int bitsToReflect = 32)
    {
      uint num1 = value;
      uint num2 = value;
      int num3 = 0;
      int num4 = checked (bitsToReflect - 1);
      int num5 = num3;
      while (num5 <= num4)
      {
        uint bitMask = this.getBitMask(checked (bitsToReflect - 1 - num5));
        if (((long) num1 & 1L) == 1L)
          num2 |= bitMask;
        else
          num2 &= ~bitMask;
        num1 >>= 1;
        checked { ++num5; }
      }
      return num2;
    }
  }
}

Данная программа на C# не тестировалась мной, в отличие от предыдущей, написанной на VB.NET. Этот код получен через декомпиляцию предыдущего. Если в нём обнаружатся какие-то ошибки, то пишите в комментариях или мне на почту, исправлю.

Прикладываю к статье полностью рабочий и готовый к использованию файл RocksoftCrcModel.vb с реализацией расчёта контрольной суммы CRC, который мы тут рассмотрели, а также RocksoftCrcModel.cs на C#.

Полную и самую последнюю версию кода можно скачать с репозитория на GitHub.

4«Взлом» контрольной суммы CRC32 и CRC16

Кратко затронем вопрос «взлома» CRC32. И прежде всего давайте определимся с понятием «взлом» применительно к данному вопросу.

Если задача определения контрольной суммы некоторого массива данных – прямая задача, то «взлом» – это обратная задача, а именно: подгонка контрольной суммы под определённый массив данных.

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

Для начала нужно посчитать обычным образом контрольную сумму CRC32, CRC16 или любую другую, какая вам нужна, для этого изменённого файла. Пусть это будет C1. Теперь нужно добавить такое же число нулевых байтов в конец файла, которое содержится в контрольной сумме (для CRC32 – 4 байта, для CRC16 – 2 байта, и т.д.). Можно простым перебором подобрать такое число C2, которое мы и запишем в эти нулевые байты. Ведь понятно, что полный диапазон всех допустимых значений CRC32 укладывается в 2³² ~ 4,295 млрд. То есть за 4 с небольшим миллиарда итераций расчёта контрольной суммы с начальным содержимым регистра, равным С1, мы брутфорсом («в лоб», методом грубой силы) подберём нужное значение. При современных вычислительных мощностях это не составит проблемы. А уж «взломать» с помощью перебора CRC16 вообще дело нескольких секунд.

Можно ли разместить нулевые байты в середине или начале файла? Можно. К операции XOR применим сочетательный закон: a XOR (b XOR c) = (a XOR b) XOR c, поэтому можно с успехом разбить файл на 3 части: до вставки, после вставки, и сама вставка. Посчитать CRC для первых двух частей (C1 и C2 на иллюстрации), объединить их операцией XOR, заполнить этим числом начальное содержимое регистра, а затем «сбрутфорсить» CRC оставшейся третьей части X.

+-----------------+-----+---------+
|        c1       |  x  |   c2    |
+-----------------+-----+---------+

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

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