Почему часто многие испытывают проблемы с 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."
Примечание: в то время как последняя "отраженная" формула верна, первая "нормальная" формула неверна - необходимо обратить вспять обе формулы, т. е. биты данных и конечное значение 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]:
echo "obase=16; 3421780262;" | bc
CBF43926
Это соответствует ожидаемому значению контрольной суммы.
[Реализация CRC32]
Как мы можем действительно реализовать подсчет CRC32?
• Инициализируем значение CRC, часто нулем, но по соглашению обычно инвертируем эти биты, т. е. берем -1. • Проходим через все байты, по которым хотим вычислить CRC. Для каждого байта делается операция исключающего ИЛИ (exclusive-or, XOR) с текущим CRC по одному биту за раз. • По соглашению для конечной CRC мы инвертируем её биты.
Звучит просто, не так ли?
Необходимо учесть и другие не такие важные, но все-таки имеющие значения детали реализации:
• Когда мы делаем операцию XOR над байтом данных и текущим CRC, то начинаем с верхних или нижних бит? • В каком направлении сдвигаем биты CRC? • Как мы преобразуем эту формулу в таблицу, чтобы обрабатывать сразу 8 бит?
Начнем с версии, вычисляющей CRC по формуле.
[Вычисление CRC по формуле]
Если используется метод с формулой, то мы можем обобщить 4 варианта реализаций двумя алгоритмами:
{
uint8_t result =0;
uint8_t maskSRC =0x01;
uint8_t maskDST =0x80;
for (int i=0; i < 8; i++)
{
if (val8 & maskSRC)
result |= maskDST;
maskSRC << =1;
maskDST >> =1;
}
return result;
}
uint32_treflect32 (uint32_t val32)
{
uint32_t result =0;
uint32_t maskSRC =0x00000001;
uint32_t maskDST =0x80000000;
for (int i=0; i < 32; i++)
{
if (val32 & maskSRC)
result |= maskDST;
maskSRC << =1;
maskDST >> =1;
}
return result;
}
Здесь важны несколько ключевых моментов:
• "Нормальная" означает сдвиг влево. • Мы реверсируем байты буфере перед их операцией 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 дополнительных пермутаций алгоритма.
Фаза
Сколько вариаций (пермутаций) алгоритма
Инициализация
22 = 4
Вычисление CRC
23 = 8
Итого получается 22 * 23 = 4 * 8 = 32 пермутации. Из этих 32 только 4 пермутации корректны, или можно так сказать, стандартизированы. Остальные 28 неправильные, и они встречаются иногда из-за того, что кто-то не понимает теорию и неправильно применяет её. Так что не удивляйтесь, что многие люди путаются с CRC32. Слишком просто здесь сделать ошибку.
Итак, как можно реализовать таблицу для вычисления CRC32 четырьмя разными способами?
Bit: какой бит проверяется при инициализации таблицы. Shift CRC: какое направление сдвига CRC во время вычисления. Обратите внимание, что это не зависит от того, в каком направлении используется сдвиг во время инициализации!
[CRC32, общие выводы]
В следующей таблице суммарно показаны 2 формы CRC32:
Из-за того, что кто-то один совсем не понял CRC32, другие люди начинают думать, что CRC32 это плохой вариант вычисления хеша.
CRC32 никогда не предназначалась для использования в хеш-таблице. На самом деле нет никаких веских причин использовать CRC32 для этой цели, и автор [1] рекомендует избегать этого. Если Вы решите использовать CRC32, то важно использовать хеш-биты со стороны конца противоположного тому, в который подаются октеты ключа. Какой именно конец - зависит от специфической реализации CRC32. Не рассматривайте CRC32 как хеш-функцию "черного ящика", и не используйте её как хеш общего назначения. Обязательно проверяйте каждое приложение на пригодность к определенной ситуации.
Примечательно, что Bret Mulvey реализовал неправильную версию CRC32! Вот оригинальный код:
public class CRC32 : HashFunction
{
uint[] tab;
public CRC32()
{
Init(0x04c11db7);
}
public CRC32(uint poly)
{
Init(poly);
}
voidInit(uint poly)
{
tab = new uint[256];
for (uint i=0; i <256; i++)
{
uint t = i;
for (int j=0; j <8; j++)
if ((t &1) ==0)
t >>=1;
else
t = (t >>1) ^ poly;
tab[i] = t;
}
}
public override uint ComputeHash(byte[] data)
{
uint hash =0xFFFFFFFF;
foreach (byte b in data)
hash = (hash <<8) ^ tab[b ^ (hash >>24)];
return~hash;
}
}
Оригинальная страничка Bret-а мертва (http://home.comcast.net/~bretm/hash/8.html), но к счастью есть зеркала (https://web.archive.org/web/20130420172816/http://home.comcast.net/~bretm/hash/8.html).
Замечание: у 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". НИ ОДНО из них не будет корректным!
Reflected 0x04C11DB7: &1 >> [ 1] = rev. poly, [ 30] = rev.poly << 8 broken
Shift: Left , Rev. Data: 0, Rev. CRC: 0, 0xC9A0B7E5 no
Shift: Left , Rev. Data: 0, Rev. CRC: 1, 0xA7ED0593 no
Shift: Left , Rev. Data: 1, Rev. CRC: 0, 0x9D594C04 no
Shift: Left , Rev. Data: 1, Rev. CRC: 1, 0x20329AB9 no
Shift: Right, Rev. Data: 0, Rev. CRC: 0, 0xFC4F2BE9 no
Shift: Right, Rev. Data: 0, Rev. CRC: 1, 0x97D4F23F no
Shift: Right, Rev. Data: 1, Rev. CRC: 0, 0xFDEFB72E no
Shift: Right, Rev. Data: 1, Rev. CRC: 1, 0x74EDF7BF no
Почему так?
[Почему существуют 2 формы?]
Возможно Вам будет интересно, почему вообще существую 2 формы алгоритма. Давным-давно, когда CRC был только что разработан и реализован, разработчики аппаратуры сдвигали биты справа налево, используя так называемый barrel shifter (см. Википедию). Впоследствии, когда CRC был реализован программно, кое-кто заметил, что все эти реверсирования бит не нужны, если:
• Использовать реверсный полином. • В обратном порядке опрашивать биты у байт. • Реверсировать конечное значение CRC.
Если вывести трассировку, как вычисляется CRC32 при помощи таблиц (см. выше во врезке правильную таблицу для 0x04C11DB7 и правильную таблицу для 0xEDB88320), то получим:
Итого: не принимайте ничего на веру, проверяйте свой код и данные.
[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-разрядная реализация:
Полином
64-bit reversed
33-bit reversed
0x104C11DB7
0xEDB8832080000000
0x1DB710641
[Ссылки]
1. CRC32 Demystified site:github.com. 2. Enter the passphrase to be encrypted site:decryptpassword.com. 3. What are the different hash algorithm outputs for 123,456,789 site:integers.co. 4. hash_file — Generate a hash value using the contents of a given file site:php.net. 5. Bc (programming language\) site:wikipedia.org. 6. Request for Comments: 3385 site:tools.ietf.org. 7. Reversing CRC – Theory and Practice site:stigge.org. 8. Calculating 32-bit CRCs (CRC-32) site:mdfs.net. 9. Which hashing algorithm is best for uniqueness and speed? site:softwareengineering.stackexchange.com. 10. Calculate a 32-bit CRC lookup table in C/C++ site:stackoverflow.com. 11. Can CRC32 be used as a hash function? site:stackoverflow.com. 12. CRC32 site:wiki.osdev.org. 13. Программная реализация CRC-алгоритма STM32.
