Как посчитать crc массива байт

Как посчитать контрольную сумму CRC32, CRC16, CRC8

В интернете существует большое количество вариантов расчёта контрольной суммы CRC. Но что же собственно такое контрольная сумма и почему она рассчитывается именно так? Давайте разберёмся. А заодно напишем программу, которая будет рассчитывать CRC с заданными параметрами.

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

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

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

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

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

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

Вот ещё пример: (x 16 +) x 15 + x 2 + x 0 = (1)1000000000000101 = 0x8005 = 32773.

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

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

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

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

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

Схематичное представление вычисления CRC на примере деления на многочлен x 8 + x 2 + x 1 + x 0

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

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

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

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

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

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

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

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

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

Предлагаемая программа плохо масштабируема. То есть она работает хорошо при вычислении контрольной суммы 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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 Программа для расчёта контрольной суммы по алгоритмам CRC32, CRC16 и CRC8

Интерфейс программы для расчёта контрольной суммы по алгоритмам CRC32, CRC16 и CRC8

Программа позволяет рассчитывать CRC массива байтов (введённого в поле «Сообщение») или указанного файла. Все рассмотренные выше параметры контрольной суммы настраиваются через интерфейс программы.

Ну и напоследок выкладываю ссылки на архив, в архиве лежат: программа «Калькулятор CRC», оригинальная статья «A Painless Guide to CRC Error Detection Algorithms», класс RocksoftCrcModel() на Visual Basic.NET и на C#.

Содержимое архива «CRC calculator»

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

Источник

Простой расчет контрольной суммы

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

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

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

Причина помех на физическом уровне, при передаче данных.

Вот пример самого типичного алгоритма для микроконтроллера, ставшего, фактически, промышленным стандартом с 1979 года.

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

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

Бит четности (1-битная контрольная сумма)

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

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

8-битная контрольная сумма

Если контроля четности мало (а этого обычно мало), добавляется дополнительная контрольная сумма. Рассчитать контрольную сумму, можно как сумму ранее переданных байт, просто и логично

Естественно биты переполнения не учитываем, результат укладываем в выделенные под контрольную сумму 8 бит. Можно пропустить ошибку, если при случайном сбое один байт увеличится на некоторое значение, а другой байт уменьшится на то же значение. Контрольная сумма не изменится. Проведем эксперимент по передаче данных. Исходные данные такие:

.

,

на 256 отправленных телеграмм с ошибкой, одна пройдет проверку контрольной суммы. Смотрим статистику от виртуальной передачи данных, с помощью простой тестовой программы:

Или условный КПД=55%, от возможностей «идеальной» контрольной суммы. Такова плата за простоту алгоритма и скорость обработки данных. В целом, для многих применений, алгоритм работоспособен. Используется одна операция сложения и одна переменная 8-битовая. Нет возможности не корректной реализации. Поэтому алгоритм и применяется в контроллерах ADAMS, ICP, в составе протокола DCON (там дополнительно может быть включен бит четности, символы только ASCI, что так же способствует повышению надежности передачи данных и итоговая надежность несколько выше, так как часть ошибок выявляется по другим, дополнительным признакам, не связанных с контрольной суммой).

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

Для сравнения применим, вместо суммы, побитовое сложение XOR. Стало существенно хуже, вероятность обнаружения ошибки 1:67 или 26% от теоретического предела. Упрощенно, это можно объяснить тем, что XOR меняет при возникновении ошибке еще меньше бит в контрольной сумме, ниже отклик на единичный битовый сбой, и повторной ошибке более вероятно вернуть контрольную сумму в исходное состояние.

Так же можно утверждать, что контрольная сумма по XOR представляет из себя 8 независимых контрольных сумм из 1 бита. Вероятность того, что ошибка придется на один из 8 бит равна 1:8, вероятность двойного сбоя 1:64, что мы и наблюдаем, теоретическая величина совпала с экспериментальными данными.

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

Константа должна быть простой, и быть достаточно большой, для изменения большего числа бит после каждой операции, 211 вполне подходит, проверяем:

Всего 72% от теоретического предела, небольшое улучшение перед простой суммой. Алгоритм в таком виде не имеет смысла. В данном случае теряется важная информация из отбрасываемых старших 8..16 бит, а их необходимо учитывать. Проще всего, смешать функцией XOR с младшими битами 1..8. Приходим к еще более интенсивной модификации контрольной суммы, желательно с минимальным затратами ресурсов. Добавляем фокус из криптографических алгоритмов

Результат 91% от теоретического предела. Вполне годится для применения.

Если в микроконтроллере нет блока умножения, можно имитировать умножение операций сложения, смещения и XOR. Суть процесса такая же, модифицированный ошибкой бит, равномерно «распределяется» по остальным битам контрольной суммы.

На удивление хороший результат. Среднее значение 254,5 или 99% от теоретического предела, операций немного больше, но все они простые и не используется умножение.

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

Что соответствует 100.6% от теоретического предела, вполне хороший результат для такого простого алгоритма из одной строчки:

Используется полноценное 16-битное умножение. Опять же не обошлось без магического числа 44111 (выбрано из общих соображений без перебора всего подмножества чисел). Более точно, константу имеет смысл подбирать, только определившись с предполагаемым типом ошибок в линии передачи данных.

Столь высокий результат объясняется тем, что 2 цикла умножения подряд, полностью перемешивают биты, что нам и требовалось. Исключением, похоже, является последний байт телеграммы, особенно его старшие биты, они не полностью замешиваются в контрольную сумму, но и вероятность того, что ошибка придется на них невелика, примерно 4%. Эта особенность практически ни как не проявляется статистически, по крайней мере на моем наборе тестовых данных и ошибке ограниченной 10 сбойными битами. Для исключения этой особенности можно делать N+1 итераций, добавив виртуальный байт в дополнение к имеющимся в тестовом блоке данных (но это усложнение алгоритма).

Вариант без умножения с аналогичным результатом. Переменная CRC 16-битная, данные 8-битные, результат работы алгоритма — младшие 8 бит найденной контрольной суммы:

Результат 100.6% от теоретического предела.

Вариант без умножения более простой, оставлен самый минимум функций, всего 3 математических операции:

Результат 86% от теоретического предела.

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

Небольшое улучшение в некоторых случаях дает так же:

16-битная контрольная сумма

Далее, предположим что нам мало 8 бит для формирования контрольной суммы.

Следующий вариант 16 бит, и теоретическая вероятность ошибки переданных данных 1:65536, что намного лучше. Надежность растет по экспоненте. Но, как побочный эффект, растет количество вспомогательных данных, на примере нашей телеграммы, к 8 байтам полезной информации добавляется 2 байта контрольной суммы.

Простые алгоритмы суммы и XOR, применительно к 16-битной и последующим CRC не рассматриваем вообще, они практически не улучают качество работы, по сравнению с 8-битным вариантов.

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

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

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

32-битная контрольная сумма

Перейдем к варианту 32-битной контрольной суммы. Появляется проблема со временем отводимым для анализа статистических данных, так как число переданных телеграмм уже сравнимо с 2^32. Алгоритм такой же, магические числа меняются в сторону увеличения

За 10 млн. итераций ошибка не обнаружена. Чтобы ускорить сбор статистики обрезал CRC до 24 бит:

Результат, из 10 млн. итераций ошибка обнаружена 3 раза

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

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

Вариант без умножения:

Сбоя для полноценной контрольной суммы дождаться не получилось. Контрольная сумма урезанная до 24 бит показывает примерно такие же результаты, 8 ошибок на 100 млн. итераций. Промежуточная переменная CRC 64-битная.

64-битная контрольная сумма

Ну и напоследок 64-битная контрольная сумма, максимальная контрольная сумма, которая имеет смысл при передачи данных на нижнем уровне:

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

Метод аналогичный тому, какой применили для CRC32 показал аналогичные результаты. Больше бит оставляем, выше надежность в полном соответствии с теоретическим пределом. Проверял на младших 20 и 24 битах, этого кажется вполне достаточным, для оценки качества работы алгоритма.

Так же можно применить для 128-битных чисел (и еще больших), главное подобрать корректно 128-битные магические константы. Но это уже явно не для микроконтроллеров, такие числа и компилятор не поддерживает.

Комментарии

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

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

Мой проект по исследованию CRC на гитхаб.

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

Источник