Как посчитать контрольную сумму CRC32, CRC16, CRC8
В интернете существует большое количество вариантов расчёта контрольной суммы CRC. Но что же собственно такое контрольная сумма и почему она рассчитывается именно так? Давайте разберёмся. А заодно напишем программу, которая будет рассчитывать CRC с заданными параметрами.
1 Теория, лежащая в основе расчёта CRC
Но такой способ определения наличия ошибок – очень неинформативный и срабатывает не всегда, т.к. при искажении нескольких битов сообщения, чётность суммы может не измениться. Поэтому существует множество более «продвинутых» проверок, в том числе CRC.
По сути, CRC – это не сумма, а результат деления некого объёма информации (информационного сообщения) на константу, а точнее – остаток от деления сообщения на константу. Тем не менее, CRC исторически также называют «контрольная сумма». В значение CRC вносит вклад каждый бит сообщения. То есть, если хотя бы один бит исходного сообщения изменится при передаче, контрольная сумма тоже изменится, причём существенно. Это большой плюс такой проверки, так как он позволяет однозначно определить, исказилось исходное сообщение при передаче или нет.
Что такое исходное сообщение – понятно. Это непрерывная последовательность битов произвольной длины.
Что за константа, на которую мы должны делить исходное сообщение? Это некоторое число также любой длины, но обычно используются числа, кратные 1 байту – 8, 16 или 32 бита. Просто так легче считать, ведь компьютеры работают именно с байтами, а не с битами.
Константу-делитель обычно записывают в виде полинома (многочлена) вот таким образом: x 8 + x 2 + x 1 + x 0 . Здесь степень числа «x» означает позицию бита-единицы в числе, начиная с нулевой, а старший разряд указывает на степень полинома и отбрасывается при интерпретации числа. То есть записанное ранее число – это не что иное как 100000111 в двоичной системе счисления.
Обычно при записи многочлена старший разряд подразумевается, но не пишется. То есть вышеуказанный многочлен можно было бы записать в двоичной системе как (1)00000111. В скобках я указал подразумеваемый старший разряд числа. Поэтому говорят, что многочлен равен 7 в десятичной системе счисления (111b = 7d).
Вот ещё пример: (x 16 +) x 15 + x 2 + x 0 = (1)1000000000000101 = 0x8005 = 32773.
Обычно используются некие стандартные многочлены для разных типов CRC. Вот некоторые из них:
| Алгоритм CRC | Образующий многочлен |
|---|---|
| CRC-16 | 0x8005 |
| CRC-16-CCITT | 0x1021 |
| CRC-16-DNP | 0x3D65 |
| CRC-32-IEEE 802.3 | 0x04C11DB7 |
| CRC-32C | 0x1EDC6F41 |
| CRC-32K | 0x741B8CD7 |
В посвящённой расчёту CRC статье на Википедии есть большая таблица образующих полиномов.
Так как же считать контрольную сумму? Существует базовый метод – деление сообщения на полином «в лоб» – и его модификации в целях уменьшения количества вычислений и, соответственно, ускорения расчёта CRC. Для начала мы рассмотрим именно базовый метод.
В общем виде деление числа на многочлен выполняется по такому алгоритму. Алгоритм вычисления контрольной суммы CRC:
- Создаётся массив (регистр), заполненный нулями, равный по длине разрядности (степени) полинома.
- Исходное сообщение дополняется нулями в младших разрядах, в количестве, равном числу разрядов полинома.
- В младший разряд регистра заносится один старший бит сообщения, а из старшего разряда регистра выдвигается один бит.
- Если выдвинутый бит равен «1», то производится инверсия битов (операция XOR, исключающее ИЛИ) в тех разрядах регистра, которые соответствуют единицам в полиноме.
- Если в сообщении ещё есть биты, переходим к шагу 3).
- Когда все биты сообщения поступили в регистр и были обработаны этим алгоритмом, в регистре остаётся остаток от деления, который и является контрольной суммой CRC.
Назовём этот метод расчёта CRC метод побитового сдвига или простой метод.
Рисунок иллюстрирует деление исходной последовательности битов на число (1)00000111, или многочлен x 8 + x 2 + x 1 + x 0 .
Схематичное представление вычисления CRC на примере деления на многочлен x 8 + x 2 + x 1 + x 0
Кстати, проверить правильность расчёта 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
Как вы могли заметить, в данной реализации расчёта 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
Этот код полностью готов к использованию, можно брать и применять. Пользоваться данной программой так:
- создать экземпляр класса RocksoftCrcModel(), передав в конструктор параметры модели CRC;
- для расчёта контрольной суммы, вызвать метод данного объекта ComputeCrc() или ComputeCrcAsBytes(), передав в качестве параметра информационное сообщение, для которого необходимо посчитать контрольную сумму;
- если меняются параметры модели CRC, таблица автоматически пересчитывается, и новый экземпляр класса можно не создавать.
Приведу пример использования данного класса для алгоритма 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 . Внешний вид окна приведён на рисунке. Программа работает под ОС Windows и требует .NET версии 3.5 .
Интерфейс программы для расчёта контрольной суммы по алгоритмам 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 бит. Можно пропустить ошибку, если при случайном сбое один байт увеличится на некоторое значение, а другой байт уменьшится на то же значение. Контрольная сумма не изменится. Проведем эксперимент по передаче данных. Исходные данные такие:
- Блок данных 8 байт.
- Заполненность псевдослучайными данными Random($FF+1)
- Случайным образом меняем 1 бит в блоке данных операцией XOR со специально подготовленным байтом, у которого один единичный бит на случайной позиции.
- Повторяем предыдущий пункт 10 раз, при этом может получится от 0 до 10 сбойных бит (2 ошибки могут накладываться друг на друга восстанавливая данные), вариант с 0 сбойных бит игнорируем в дальнейшем как бесполезный для нас.
на 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. Приходим к еще более интенсивной модификации контрольной суммы, желательно с минимальным затратами ресурсов. Добавляем фокус из криптографических алгоритмов
- Промежуточная CRC для первого действия 16-битная (после вычислений обрезается до 8 бит) и в дальнейшем работаем как с 8-битной, если у нас 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 битных данных, и без умножения вообще.
Crc32 как посчитать контрольную сумму
Почему часто многие испытывают проблемы с CRC, и как это исправить (перевод [1]).
Насколько много разных способов, какими можно реализовать алгоритм проверки контрольной суммы (Cyclic Redundancy Check, CRC)? В частности, что такое вычисление CRC по 32-битному полиному, также известное как CRC32?
Давайте рассмотрим варианты вычисления CRC32. В общем случае алгоритм CRC может быть реализован одним из двух основных методов:
• На основе формулы.
• На основе таблицы.
Для каждого из этих методов существуют различные опции, которые можно выбрать. Во-первых, для каждого вычисления CRC мы можем использовать один из двух полиномов, отличаются они обратным порядком бит в полиноме:
• «Прямую» константу полинома.
• «Обратную» константу полинома.
Во-вторых, когда мы инициализируем таблицу, инициализацию можно делать сдвигом бит влево или вправо.
В третьих, когда мы вычисляем значение CRC, биты можно сдвигать влево или вправо. Об этих моментах Ross Williams рассказывает в своем руководстве «A PAINLESS GUIDE TO CRC ERROR DETECTION ALGORITHMS» (Безболезненное руководство по алгоритмам обнаружения ошибок):
«В сущности есть только 2 формы вычисления CRC: нормальная (normal) и отраженная (reflected). Нормальная форма со сдвигом влево охватывает случай алгоритмов с Refin=FALSE и Refot=FALSE. Отраженная делает сдвиг вправо, и относится к алгоритмам, у которых оба этих параметра true.»
Это дает 2 формулы, показанные ниже.
Примечание: в то время как последняя «отраженная» формула верна, первая «нормальная» формула неверна — необходимо обратить вспять обе формулы, т. е. биты данных и конечное значение CRC.
В результате получается 4 и 5 опций соответственно.
В четвертых — когда мы считываем каждый байт данных, мы не обязательно при вычислении CRC можем делать реверс бит в алгоритме CRC. В пятых — мы опционально можем делать реверс бит конечного значения CRC.
Таким образом, в зависимости от формы (нормальная или отраженная) и от константы полинома (прямая или обратная), наивный пользователь может получить как минимум 4 разных значения вычисления CRC! Два из них будут корректны, а два других нет.
• Нормальная форма (сдвиг влево) с прямым полиномом (корректна).
• Отраженная форма (сдвиг вправо) с прямым полиномом.
• Нормальная форма (сдвиг влево) с обратным полиномом.
• Отраженная форма (сдвиг вправо) с обратным полиномом (корректна).
[Контрольная сумма]
Ross также упоминает контрольную сумму, называя её «CHECK»:
«CHECK: . поле, содержащее контрольную сумму, полученную их строки ASCII «123456789». Эта строка прогоняется через указанный алгоритм, например 313233. (hex-форма).
Для CRC32 популярен прямой полином 0x04C11DB7. Реверсированием бит мы получаем полином 0xEDB88320.
| Полином | Двоичное представление полинома |
| 0x04C11DB7 | 00000100_11000001_00011101_10110111 |
| 0xEDB88320 | 11101101_10111000_10000011_00100000 |
Примечание: см. далее «CRC32 или CRC33?».
Эти полиномы (при корректном использовании) генерируют одинаковую контрольную сумму:
| Форма | Полином | CRC32 по контрольным данным ASCII «123456789» |
| Нормальная | 0x04C11DB7 | 0xCBF43926 |
| Отраженная | 0xEDB88320 | 0xCBF43926 |
Обратите внимание, что значение этих двух контрольных сумм одинаковое, несмотря на то, что их полиномы разные! Ниже будет показано, почему так происходит независимо от любого из 4 используемых методов вычисления CRC:
• По формуле.
• С помощью таблицы.
• То и другое с нормальным полиномом.
• То и другое с отраженным полиномом.
В реальной жизни используют не только полиномы CRC32. В Википедии есть таблица популярных полиномов CRC. См. также ссылки [2, 3, 4]. И конечно, разные алгоритмы вычислят CRC по-разному.
123456789 зашифрованное CRC32A, даст значение 181989fc
123456789 зашифрованное CRC32B, даст значение cbf43926
Первым CRC32A является алгоритм ITU I.363.5, популяризированный утилитой BZIP2. Следующий CRC32B это алгоритм ITU V.42, используемый в Ethernet, и он популяризирован PKZip.
Почему на одинаковом полиноме 0x04C11DB7, при одинаковых входных данных получается разные значения CRC32? Забегая вперед, обобщим вычисленные значения:
| Полином | Сдвиг | Реверс данных | Реверс CRC | CRC | Имя |
| 0x04C11DB7 | Влево | Нет | Нет | 0xFC891918 | crc32a |
| Да | Да | 0xCBF43926 | crc32b | ||
| 0xEDB88320 | Вправо | Нет | Нет | 0xCBF43926 | crc32b |
| Да | Да | 0xFC891918 | crc32a |
Подробности можно узнать в enum_crc32.cpp [1]. В этом документе основное внимание уделено CRC32B. На *nix машинах можно использовать штатную утилиту cksum. Например, команды:
Путем преобразования в hex с помощью Basic Calculator [5]:
Это соответствует ожидаемому значению контрольной суммы.
[Реализация CRC32]
Как мы можем действительно реализовать подсчет CRC32?
• Инициализируем значение CRC, часто нулем, но по соглашению обычно инвертируем эти биты, т. е. берем -1.
• Проходим через все байты, по которым хотим вычислить CRC. Для каждого байта делается операция исключающего ИЛИ (exclusive-or, XOR) с текущим CRC по одному биту за раз.
• По соглашению для конечной CRC мы инвертируем её биты.
Звучит просто, не так ли?
Необходимо учесть и другие не такие важные, но все-таки имеющие значения детали реализации:
• Когда мы делаем операцию XOR над байтом данных и текущим CRC, то начинаем с верхних или нижних бит?
• В каком направлении сдвигаем биты CRC?
• Как мы преобразуем эту формулу в таблицу, чтобы обрабатывать сразу 8 бит?
Начнем с версии, вычисляющей CRC по формуле.
[Вычисление CRC по формуле]
Если используется метод с формулой, то мы можем обобщить 4 варианта реализаций двумя алгоритмами:
a) «Нормальная» CRC32, вычисляемая по формуле:
• Здесь reverse это таблица байт, у которых значения бит реверсированы.
• Подобным образом reflect32() реверсирует 32-разрядное значение.
Здесь важны несколько ключевых моментов:
• «Нормальная» означает сдвиг влево.
• Мы реверсируем байты буфере перед их операцией XOR со значением CRC.
• Байты данных поступают в верхние 8 бит значения CRC.
• Мы проверяем верхний бит значения CRC.
• Мы инвертируем конечное значение CRC.
• Мы реверсируем конечное значение CRC.
Что произойдет, если не делать реверсирование никаких бит?
Если прогнать этот алгоритм по строке «123456789», то получим значение CRC32 0xFC891918. Обратите внимание, что это little endian форма значения big endian 0x181989FC, упомянутая выше! Т. е. здесь у нас получился вариант CRC32A.
b) «Отраженная» CRC32, вычисляемая по формуле. Если мы хотим убрать все эти реверсирования бит, то получим упрощенную версию алгоритма:
• «Отраженная» (reflected) означает сдвиг вправо.
• Байты данных поступают в нижние 8 бит значения CRC.
• Мы проверяем нижний бит значения CRC.
• Мы инвертируем конечное значение CRC.
Что произойдет, если у нас будет несоответствие между формой (нормальная/отраженная) и полиномом (0x04C11DB7/0xEDB88320)? На проверочной строке «123456789» получатся следующие результаты:
Нормальная форма (0x04C11DB7): 0xCBF43926
Отраженная форма (0x04C11DB7): 0xFC4F2BE9, что неправильно!
Нормальная форма (0xEDB88320): 0xFC4F2BE9, что неправильно!
Отраженная форма (0xEDB88320): 0xCBF43926
Теперь понятно, почему многие пользователи просят помощи в Интернете, когда используют значение 0x04C11DB7 (прямой полином) и получают некорректное вычисление CRC. Типовое решение проблемы, которое часто советуют — использовать другой (обратный) полином 0x0xEDB88320, и при этом обе стороны часто не понимают, что оба полинома правильные!
Реальная проблема заключается в НЕСООТВЕТСТВИИ между битовым сдвигом, используемым при инициализации таблицы CRC32, и вычислением CRC32.
[Вычисление CRC на основе таблицы]
У «формульного» алгоритма есть один большой, раздражающий недостаток: нам нужно проверять значение CRC по одному биту в цикле. Конечно, это занимает много процессорного времени.
Можно ли сразу проверять не один, а 8 бит? Да, это реально с помощью заранее подготовленной таблицы. Табличный алгоритм вычисления CRC разбивается на 2 шага:
• Инициализация таблицы.
• Вычисление CRC с использованием этой таблицы.
Как уже упоминалось в обсуждении «формульного» алгоритма, существует 4 разные варианта (пермутации) алгоритма вычисления CRC, два правильных и 2 неправильных:
• Нормальная форма (сдвиг влево) с прямым полиномом (корректна).
• Отраженная форма (сдвиг вправо) с прямым полиномом.
• Нормальная форма (сдвиг влево) с обратным полиномом.
• Отраженная форма (сдвиг вправо) с обратным полиномом (корректна).
Фаза вычисления по таблице добавляет 8 дополнительных пермутаций алгоритма.
| Фаза | Сколько вариаций (пермутаций) алгоритма |
| Инициализация | 2 2 = 4 |
| Вычисление CRC | 2 3 = 8 |
Итого получается 2 2 * 2 3 = 4 * 8 = 32 пермутации. Из этих 32 только 4 пермутации корректны, или можно так сказать, стандартизированы. Остальные 28 неправильные, и они встречаются иногда из-за того, что кто-то не понимает теорию и неправильно применяет её. Так что не удивляйтесь, что многие люди путаются с CRC32. Слишком просто здесь сделать ошибку.
Итак, как можно реализовать таблицу для вычисления CRC32 четырьмя разными способами?
| Форма | Проверяемый бит | Сдвиг | Полином | Правильно? | Функция |
| Нормальная | Старший | Влево | 0x04C11DB7 | Да | crc32_init_normal ( прямой полином ) |
| Отраженная | Младший | Вправо | Нет! | crc32_init_reflect ( прямой полином ) | |
| Нормальная | Старший | Влево | 0xEDB88320 | Нет! | crc32_init_normal ( обратный полином ) |
| Отраженная | Младший | Вправо | Да | crc32_init_reflect ( обратный полином ) |
Нормальная форма с полиномом 0x04C11DB7: & << 31 [1] = poly, [16] = poly << 8, правильная таблица.
Отраженная форма с полиномом 0x04C11DB7: &1 >> [1] = rev. poly, [30] = rev.poly << 8, неправильная таблица.
Нормальная форма с полиномом 0xEDB88320: & << 31 [128] = rev. poly, [120] = rev.poly >> 8, неправильная таблица.
Отраженная форма с полиномом 0xEDB88320: &1 >> [128] = poly, [8] = poly >> 8, правильная таблица.
Проверкой элементов table[1] и table[128] мы можем определить:
• Какая используется форма алгоритма (нормальная или отраженная).
• Какой используется полином.
• Какое направление сдвига следует использовать.
Как можно реализовать вычисление CRC восемью разными способами?
| Сдвиг CRC | Биты данных реверсированы | Конечная CRC реверсирована |
| Влево | Нет | Нет |
| Вправо | Да | Да |
Биты данных реверсируются в зависимости от используемой формы:
Конечное значение CRC реверсируется в зависимости от используемой формы:
Перечислим 8 пермутаций для вычислений:
| Сдвиг вправо | Реверс данных | Реверс CRC | Функция |
| 0 | 0 | 0 | crc32_000() |
| 0 | 0 | 1 | crc32_001() |
| 0 | 1 | 0 | crc32_010() |
| 0 | 1 | 1 | crc32_011() |
| 1 | 0 | 0 | crc32_100() |
| 1 | 0 | 1 | crc32_101() |
| 1 | 1 | 0 | crc32_110() |
| 1 | 1 | 1 | crc32_111() |
| Полином | Bit | Init | Shift CRC | Реверс данных | Реверс CRC | Функция | Допустимо |
| 0x04C11DB7 | 31 | crc32_init_normal | Влево | 0 | 0 | crc32_000() | crc32a |
| 31 | 0 | 1 | crc32_001() | нет | |||
| 31 | 1 | 0 | crc32_010() | нет | |||
| 31 | 1 | 1 | crc32_011() | crc32b | |||
| 31 | Вправо | 0 | 0 | crc32_100() | нет | ||
| 31 | 0 | 1 | crc32_101() | нет | |||
| 31 | 1 | 0 | crc32_110() | нет | |||
| 31 | 1 | 1 | crc32_111() | нет | |||
| 1 | crc32_init_reflect | Влево | 0 | 0 | crc32_000() | нет | |
| 1 | 0 | 1 | crc32_001() | нет | |||
| 1 | 1 | 0 | crc32_010() | нет | |||
| 1 | 1 | 1 | crc32_011() | нет | |||
| 1 | Вправо | 0 | 0 | crc32_100() | нет | ||
| 1 | 0 | 1 | crc32_101() | нет | |||
| 1 | 1 | 0 | crc32_110() | нет | |||
| 1 | 1 | 1 | crc32_111() | нет | |||
| 0xEDB88320 | 31 | crc32_init_normal | Влево | 0 | 0 | crc32_000() | нет |
| 31 | 0 | 1 | crc32_001() | нет | |||
| 31 | 1 | 0 | crc32_010() | нет | |||
| 31 | 1 | 1 | crc32_011() | нет | |||
| 31 | Вправо | 0 | 0 | crc32_100() | нет | ||
| 31 | 0 | 1 | crc32_101() | нет | |||
| 31 | 1 | 0 | crc32_110() | нет | |||
| 31 | 1 | 1 | crc32_111() | нет | |||
| 1 | crc32_init_reflect | Влево | 0 | 0 | crc32_000() | нет | |
| 1 | 0 | 1 | crc32_001() | нет | |||
| 1 | 1 | 0 | crc32_010() | нет | |||
| 1 | 1 | 1 | crc32_011() | нет | |||
| 1 | Вправо | 0 | 0 | crc32_000() | crc32b | ||
| 1 | 0 | 1 | crc32_001() | нет | |||
| 1 | 1 | 0 | crc32_010() | нет | |||
| 1 | 1 | 1 | crc32_011() | crc32a |
Bit: какой бит проверяется при инициализации таблицы.
Shift CRC: какое направление сдвига CRC во время вычисления. Обратите внимание, что это не зависит от того, в каком направлении используется сдвиг во время инициализации!
[CRC32, общие выводы]
В следующей таблице суммарно показаны 2 формы CRC32:
| Описание | Нормальная | Отраженная |
| Биты полинома реверсированы? | Нет | Да |
| Значение полинома | 0x04C11DB7 | 0xEDB88320 |
| Полиномиальная номенклатура | Прямая | Обратная |
| Инициализируемый бит таблицы | Старший | Младший |
| Проверяемый бит таблицы | 31 | 1 |
| Сдвиг бит таблицы инициализации | Влево | Вправо |
| Биты данных реверсированы? | Да | Нет |
| Сдвиг при вычислении CRC | Влево | Вправо |
| Конечная CRC реверсируется? | Да | Нет |
| Корректная функция инициализации | crc32_init_normal | crc32_init_reflect |
| Корректная функция вычисления CRC | crc32_011() | crc32_100() |
| CRC32 от строки «123456789» | 0xCBF43926 | |
Из-за того, что кто-то один совсем не понял CRC32, другие люди начинают думать, что CRC32 это плохой вариант вычисления хеша.
CRC32 никогда не предназначалась для использования в хеш-таблице. На самом деле нет никаких веских причин использовать CRC32 для этой цели, и автор [1] рекомендует избегать этого. Если Вы решите использовать CRC32, то важно использовать хеш-биты со стороны конца противоположного тому, в который подаются октеты ключа. Какой именно конец — зависит от специфической реализации CRC32. Не рассматривайте CRC32 как хеш-функцию «черного ящика», и не используйте её как хеш общего назначения. Обязательно проверяйте каждое приложение на пригодность к определенной ситуации.
Примечательно, что Bret Mulvey реализовал неправильную версию CRC32! Вот оригинальный код:
Оригинальная страничка Bret-а мертва (http://home.comcast.net/
bretm/hash/8.html), но к счастью есть зеркала (https://web.archive.org/web/20130420172816/http://home.comcast.net/
Замечание: у Bret-а есть новая страничка, но он ловко опускает CRC32 из-за своего непонимания CRC32 (http://papa.bretmulvey.com/post/124027987928/hash-functions).
Вот вопрос на Stack Overflow:
http://stackoverflow.com/questions/10953958/can-crc32-be-used-as-a-hash-function
Видно, что Bret не реализовал правильно CRC32, но никто на самом деле не говорит, в чем заключается его ошибка! Можно посмотреть соответствующий код и данные, что определить, где Bret допустил ошибки.
[Неправильный код]
1. Bret взял инициализацию таблицы, не совпадающую с вычислением CRC.
Напомню, что для CRC32 существует 2 полинома: прямой 0x04C11DB7 и реверсный 0xEDB88320. У реверсного порядок следования бит обратный. Алгоритм CRC существует в 2 формах: нормальная форма проверяет старший бит и делает сдвиг влево, отраженная форма проверяет младший бит и сдвигает вправо. Bret в функции Init() использует прямой полином, не соответствующий «отраженной» форме инициализации младшего бита.
2. Неправильное вычисление CRC. Bret в функции ComputeHash() делает сдвиг влево, но не делает реверсирование бит в как в данных, так и конечном значении CRC!
Если мы рассмотрим возможные способы, которыми кто-то мог бы инициализировать таблицу с прямым полиномом 0x04C11DB7, то обнаружем 8 значений CRC для текста «123456789». НИ ОДНО из них не будет корректным!
[Почему существуют 2 формы?]
Возможно Вам будет интересно, почему вообще существую 2 формы алгоритма. Давным-давно, когда CRC был только что разработан и реализован, разработчики аппаратуры сдвигали биты справа налево, используя так называемый barrel shifter (см. Википедию). Впоследствии, когда CRC был реализован программно, кое-кто заметил, что все эти реверсирования бит не нужны, если:
• Использовать реверсный полином.
• В обратном порядке опрашивать биты у байт.
• Реверсировать конечное значение CRC.
Если вывести трассировку, как вычисляется CRC32 при помощи таблиц (см. выше во врезке правильную таблицу для 0x04C11DB7 и правильную таблицу для 0xEDB88320), то получим:
[Неправильные данные]
Код Bret-а генерирует неправильную таблицу CRC:
В результате по этой неправильной таблице вычисляется неправильная контрольная сумма:
[Исправление кода Bret-а]
Можно исправить эту реализацию двумя способами, в зависимости от того, какой полином хотим использовать.
1. Исправление с обратным полиномом.
a) Инициализация таблицы должна использовать обратный полином:
b) При вычислении CRC поменяйте неправильный левый сдвиг сдвиг на правильный правый сдвиг:
2. Исправление с прямым полиномом.
a) Инициализация таблицы. Здесь нужно установить начальное значение CRC. Если старший бит установлен, то выполняется левый сдвиг и XOR с полиномом.
b) Вычисление CRC. У байт данных должны быть реверсированы биты. Изначальный код:
. надо исправить так:
Итого: не принимайте ничего на веру, проверяйте свой код и данные.
[CRC32 или CRC33?]
Технически 32-разрядная константа 0x04C11DB7 это на самом деле 33-разрядная константа 0x104C11DB7, которая классифицируется как IEEE-802 CRC (см. RFC 3385 [6]).
| Полином | Двоичное значение полинома |
| 0x04C11DB7 | 00000100_11000001_00011101_10110111 |
| 0x104C11DB7 | 1_00000100_11000001_00011101_10110111 |
Поскольку когда-то 64-разрядные вычисления были неоправданно дорогими, полином CRC33 был усечен до 32 бит без каких-либо значимых потерь, даже если вычисление дает несколько другие результаты, чем чистая 33-разрядная реализация:
Name already in use
If nothing happens, download GitHub Desktop and try again.
Launching GitHub Desktop
If nothing happens, download GitHub Desktop and try again.
Launching Xcode
If nothing happens, download Xcode and try again.
Launching Visual Studio Code
Your codespace will open once ready.
There was a problem preparing your codespace, please try again.
Latest commit
Git stats
Files
Failed to load latest commit information.
README.md
A.K.A. Why does almost everyone bugger up CRC32 and how to fix it.
Version 2, August 23, 2022 By Michaelangel007
Table of Contents
- Introduction
- Checksum
- CRC32 Implementation
- Formulaic CRC
- Table-Lookup CRC
- CRC32 Tables
- All CRC32 Permutations
- Bad Code
- Why two forms?
- Bad Data
How many different ways can one implement a Cyclic redundancy check algorithm? Specifically, where the polynomial is 32-bits, aka CRC32?
Let me count the ways.
The CRC algorithm can be implemented in one of two general methods:
- Formulaic
- Table-Lookup
For each of these methods there are various options we can choose from:
First, for each CRC we can use one of two polynomials:
- a «forward» polynomial constant, or
- a «reverse» polynomial constant, that is, the forward polynomial bit reversed.
Second, when we initialize the table we can shift bits to the left or right.
Third, when we calculate the CRC value we can shift bits to left or right. Ross Williams mentions in his guide: A PAINLESS GUIDE TO CRC ERROR DETECTION ALGORITHMS
«There are really only two forms: normal and reflected. Normal shifts to the left and covers the case of algorithms with Refin=FALSE and Refot=FALSE. Reflected shifts to the right and covers algorithms with both those parameters true.»
And gives these two formulas:
Note: that while the latter «reflected» formula is correct, the former «normal» formula is incorrect — one needs to reverse both the:
- data bits, and
- final CRC value.
That gives rise to the Forth and Fifth options, respectively. The fourth — as we read each byte of the data we are calculating the CRC for we optionally bit-reverse the the bytes as they get applied into the CRC algorithm.
The fifth — we optionally bit-reverse the final CRC value.
What this all means is that depending on:
- which form (Normal or Reflected) and
- which polynomial (Forward or Reverse)
is used a naive user won’t realize there at least a total of 4 different outcomes!
Two of them are correct; the other two are incorrect.
- Normal form (Shift Left) with Forward polynomial (valid)
- Reflected form (Shift Right) with Forward polynomial
- Normal form (Shift Left) with Reverse polynomial
- Reflected form (Shift Right) with Reverse polynomial (valid)
Ross also mentions a checksum called «CHECK»:
CHECK: . The field contains the checksum obtained when the ASCII string «123456789» is fed through the specified algorithm (i.e. 313233. (hexadecimal)).
For CRC32 a popular forward polynomial is 0x04C11DB7. Reversing the bits we get the reference polynomial of 0xEDB88320 .
Polynomial Binary 0x04C11DB7 00000100_11000001_00011101_10110111 0xEDB88320 11101101-10111000_10000011_00100000 (Note: See CRC32 vs CRC33)
They generate this checksum:
Form Polynomial CRC32 checksum Normal 0x04C11DB7 0xCBF43926 Reflected 0xEDB88320 0xCBF43926 Notice how the two checksum values are the same even though the polynomials are different! We’ll examine why that is in a bit (groan) but for now we can utilize this knowledge to verify that we have implemented the CRC32 algorithm correctly regardless if we are using:
- a formulaic method,
- a table-lookup method,
- a normal polynomial, or
- a reflected polynomial.
These are not the only CRC32 polynomials used. Wikipedia has a table of popular CRC polynomials For example, if you enter in «123456789» in password searching utilities:
NOTE: To prevent ambiguity I’ll call the former CRC32A .
The former CRC32A is the ITU I.363.5 algorithm popularised by BZIP2. The latter CRC32B is the ITU V.42 algorithm used in Ethernet and popularised by PKZip)
Why are two different values when both of these are generated with the same CRC32 polynomial 0x04C11DB7 on the same input? We’re getting ahead of ourselves but they can be summarize like this:
Polynomial Shift Reverse Data Reverse CRC Checksum Name 0x04C11DB7 Left No No 0xFC891918 crc32a 0x04C11DB7 Left Yes Yes 0xCBF43926 crc32b 0xEDB88320 Right No No 0xCBF43926 crc32b 0xEDB88320 Right Yes Yes 0xFC891918 crc32a You can see enum_crc32.cpp for more details.
For this document we will focus mainly on CRC32B.
On *nix machines we can use the built-in cksum utility.
Produces this output:
Which matches the expected checksum value.
So how do we actually implement CRC32?
- Initialize the CRC value, typically zero, but by convention we usually invert the bits, that is, -1.
- Iterate over each byte we wish to calculate the CRC checksum for
- For each byte we exclusive-or (XOR) it with the current CRC one bit at a time
Sounds simple, right?
It is, except for some minor, but important implementation details:
- When we XOR the data byte into the current CRC value do we start at the top or bottom bits?
- Which direction do we shift the CRC bits?
- How do we convert this formula into a table where we handle all 8-bits at once?
We’ll start with the formulaic version.
If we are using a formulaic method, we can generalize the 4 permutations with 2 algorithms:
- a) Formulaic «Normal» CRC32
- The reverse is a table of byte values bit-reversed.
- Likewise reflect32() bit reverses a 32-bit value.
There are few key things to note:
- Normal = Shift Left
- We reverse bytes in the buffer before XOR’ing them into the CRC value
- The data bytes are fed into the top 8 bits of the CRC value
- We test the top-bit of the CRC value
- We invert the final CRC value
- We bit reverse the final CRC value
What were to happen if we didn’t reverse any of the bits?
Running it on «123456789» produces the CRC32 value of 0xFC891918 — notice how this is the little endian form of the big endian value 0x181989FC mentioned above! We would have CRC32A .
b) Formulaic «Reflected» CRC32
If we want to remove all that bit-reversing shenanigans we end up the simpler version:
The areas to note are:
- Reflected = Shift Right
- The data bytes are fed into the bottom 8 bits of the CRC value
- We test the bottom-bit of the CRC value
- We invert the final CRC value
What would happen if we mis-matched the form and the polynomial? Using the check string this produces the formulaic output of:
We can now understand why often times you’ll find people posting on the internet that they are using a (forward polynomial) value of 0x04C11DB7 and are asking for help to understand why they aren’t getting the correct CRC calculation. The typical knee-jerk solution is someone tells the original parent to use the other (reverse) polynomial, 0x0xEDB88320 , without both parties understanding that both polynomials are correct!
The real problem is a MISMATCH of the bit shuffling used in the CRC32 table Initialization and CRC32 Calculation.
There is one big annoyance with the formulaic approach:
- We need to test the CRC one bit a time
Can we test 8 bits at once? Yes, by using a pre-computed table. The table lookup approach the CRC algorithm is broken down into two phases:
- Initialization of the table
- Calculation of crc using the table
As we saw in the formulaic discussion above there are 4 different permutions.
- Normal form (Shift Left) with Forward polynomial (valid)
- Reflected form (Shift Right) with Forward polynomial
- Normal form (Shift Left) with Reverse polynomial
- Reflected form (Shift Right) with Reverse polynomial (valid)
The calculation phase of table-lookup adds 8 more permutations.
Phase Permutations Initialization 2^2 Calculation 2^3 Thus there are a total of 2^2 * 2^3 = 4 * 8 = 32 permutations.
Of these 32 different permutations only 4 are correct, or should I say standardized. The other 28 are broken implementations due to someone not understanding the theory and incorrectly applying it.
No wonder most people are confused about CRC32! It is so easy to go wrong!!
Here are the details:
a) How can the table initialization be implemented in 4 different ways?
Form Bit Check Rotate Polynomial Valid Function Normal Top Bit Left 0x04C11DB7 Yes crc32_init_normal ( forward poly ) Reflected Bottom Bit Right 0x04C11DB7 no !! crc32_init_reflect( forward poly ) Normal Top Bit Left 0xEDB88320 no !! crc32_init_normal ( reverse poly ) Reflected Bottom Bit Right 0xEDB88320 Yes crc32_init_reflect( reverse poly ) Here are the 4 CRC32 tables:
- Normal 0x04C11DB7: &<<31 [ 1] = poly , [ 16] = poly << 8 VALID
- Reflected 0x04C11DB7: &1 >> [ 1] = rev. poly, [ 30] = rev.poly << 8 broken
- Normal 0xEDB88320: &<<31 [128] = rev. poly, [120] = rev.poly >> 8 broken
- Reflected 0xEDB88320: &1 >> [128] = poly , [ 8] = poly >> 8 VALID
Thus by inspecting table[1] and table[128] entries we can tell:
- Which form you used,
- Which polynomial you used, and
- Which shift direction you should be using.
b) How can the CRC calculation be implemented in 8 different ways?
Shift CRC Data Bits reversed? Final CRC Reversed? Left No No Right Yes Yes The data bits are reversed depending on which form we are in:
Form Data bits Normal crc32 = table[ (crc32 >> 24) ^ reverse[ *data ] ^ (crc << 8); Reflected crc32 = table[ (crc32 ) ^ *data ] ^ (crc >> 8); The final CRC value is reversed depending on which form we are in:
Enumerating the 8 calculation permutations:
Right Shift Reverse
DataReverse
CRCFunction 0 0 0 crc32_000() 0 0 1 crc32_001() 0 1 0 crc32_010() 0 1 1 crc32_011() 1 0 0 crc32_100() 1 0 1 crc32_101() 1 1 0 crc32_110() 1 1 1 crc32_111() All CRC32 Permutations
Enumerating all 32 initialization and calculation permutations:
- See enum_crc32.cpp
- Bit = Which bit is tested during table initialization
- Shift CRC = Which direction the CRC value is shifted during calculation. Note that this is independent of which shift direction was used during initialization!
TL:DR; CRC32 Summary
Here is a summary of the two forms of CRC32:
Description Normal Reflected Polynomial bits reversed? No Yes Polynomial value 0x04C11DB7 0xEDB88320 Polynomial nomenclature Forward Reverse Table initialization bit Top-bit Low-bit Table initialization bit test 31 1 Table initialization bit shift Left Right Data bits reversed? Yes No CRC calculation shift Left Right Final CRC bits reversed? Yes No Correct Initialization Function crc32_init_normal crc32_init_reflect Correct Calculation Function crc32_011() crc32_100() CRC32 Checksum «123456789» 0xCBF43926 CBF43926 CRC32 Hashing Confusion
Due to one person completely failing to understand CRC32 this misled other people to falsely conclude that CRC32 wouldn’t make a good hash.
CRC32 was never intended for hash table use. There is really no good reason to use it for this purpose, and I recommend that you avoid doing so. If you decide to use CRC32, it’s critical that you use the hash bits from the end opposite to that in which the key octets are fed in. Which end this is depends on the specific CRC32 implementation. Do not treat CRC32 as a «black box» hash function, and do not use it as a general purpose hash. Be sure to test each application of it for suitability.
Ironically, Bret Mulvey implemented a broken version of CRC32!
While Bret’s original hashing page is now dead .
. Fortunately there are mirrors available:
NOTE: Bret has a new page but he siliently omits CRC32 due to his misunderstanding of CRC32.
This Stack Overflow question:
mentions Bret didn’t implement CRC32 correctly, but no one actually says WHAT the bug(s) are!
We can inspect the:
- code
- data
to determine where Bret made his bugs.
Bret mismatched the table initialization with the CRC calculation.
- Incorrect table initialization.
Pardon the pun, but to re-hash:
CRC32 has two polynomials:
- The forward polynomial, 0x04C11DB7 ,
- The reverse polynomial, 0xEDB88320 , where the bits are reversed.
The CRC algorith comes in two forms:
- Normal initialization checks the top bit and shifts left,
- Reflected initialiation checks the bottom bit and shifts right.
Bret’s Init() used a forward polynomial mismatched with a ‘reflected’ bottom bit initialization.
- Incorrect CRC calculation
Bret’s ComputeHash() shifts left HOWEVER he didn’t reverse the bits in both the data and final CRC value!
If we enumerate the possible ways someone could initialize the table with the forward polynomial 0x04C11DB7 we discover there are 8 crc values on the text «123456789». NONE of these are correct!
You may be wondering why are there even two forms in the first place?
Back in the day when CRC was being first designed / implemented the hardware guys would shift bits out right-to-left using a barrel shifter.
When CRC was implemented in software someone noticed all this bit-reversal was unneccessary if they:
- reversed the polynomial
- reversed the reversed bytes
- reversed the reversed final CRC value
If we output a trace of how the crc32 is calculated using the tables .
- Proper table for 0x04C11DB7
- Proper table for 0xEDB88320
. we get this output:
Bret’s code generates this bogus CRC table:
Which generates this «bad checksum» using the bogus CRC table:
a) If he had actually followed his own advice .
Do not treat CRC32 as a «black box» hash function,
- the checksum, and
- the table
to verify they were correct he would have noticed that all the high nibbles were set to zero! This is dilluting the effectiveness of the CRC32 hash!
Compare and constrast when the tables are correctly initialized:
- CRC Polynomial 0x04C11DB7:
- CRC32 Polynomial 0xEDB88320:
Fixing Bret’s Code
There two ways we could fix this depending on which polynomial we want to use.
Fix using the reverse polynomial
a) Table Initialization
- Use the reverse polynomial
- Fix using the forward polynomial
Thus along with verifing the calculation was correct he would have come to a different conclusion about the validity of CRC32 as a hashing function.
TL:DR; Don’t assume! VERIFY your code + data.
Technically, the CRC 32-bit constant 0x04C11DB7 is really a 33-bit constant 0x104C11DB7 which is classified as an IEEE-802 CRC. See RFC 3385
Polynomial Binary 0x04C11DB7 00000100_11000001_00011101_10110111 0x104C11DB7 1_00000100_11000001_00011101_10110111 Since 64-bit computing was hideously expensive at the time of when the CRC33 polynomial got truncated down to 32-bits without any loss in generality even though this gives different results then a pure 33-bit implementation: