Как рассчитывается контрольная сумма CRC32?
Может быть, я просто не вижу этого, но CRC32 кажется либо слишком сложным, либо недостаточно объясненным, где бы я ни находился в Интернете.
Я понимаю, что это остаток от арифметического деления значения сообщения, не основанного на переносе, деленного на полином (генератор), но фактическая реализация этого ускользает от меня.
Я прочитал "Безболезненное руководство по алгоритмам обнаружения ошибок CRC", и должен сказать, что он не был безболезненным. Она довольно хорошо подходит к теории, но автор никогда не доходит до простого "вот оно". Он говорит, что это за параметры для стандартного алгоритма CRC32, но он пренебрегает, чтобы четко изложить, как вы к нему подходите.
Часть, которая получает меня, - это когда он говорит "это все", а затем добавляет: "О, кстати, это может быть изменено или может начинаться с других начальных условий", и не дает четкого ответа о том, каков окончательный путь. вычисления контрольной суммы CRC32 с учетом всех изменений, которые он только что добавил.
- Есть ли более простое объяснение того, как рассчитывается CRC32?
Я попытался кодировать в C, как таблица формируется:
for (i = 0; i < 256; i++)
{
temp = i;
for (j = 0; j < 8; j++)
{
if (temp & 1)
{
temp >>= 1;
temp ^= 0xEDB88320;
}
else {temp >>= 1;}
}
testcrc[i] = temp;
}
но это, кажется, генерирует значения, несовместимые со значениями, которые я нашел в других местах в Интернете. Я мог бы использовать значения, которые я нашел в Интернете, но я хочу понять, как они были созданы.
Любая помощь в выяснении этих невероятно запутанных чисел была бы очень признательна.
Ответы
Ответ 1
Полином для CRC32:
х 32 + х 26 + х 23 + х 22 + х 16 + х 12 + х 11 + х 10 + х 8 + х 7 + х 5 + х 4 + х 2 + х + 1
Или в шестнадцатеричном и двоичном виде:
0x 01 04 C1 1D B7
1 0000 0100 1100 0001 0001 1101 1011 0111
Наибольший член (x 32) обычно не записывается явно, поэтому он может быть представлен в шестнадцатеричном виде так же, как
0x 04 C1 1D B7
Не стесняйтесь считать 1 и 0, но вы обнаружите, что они совпадают с полиномом, где 1 - это бит 0 (или первый бит), а x - это бит 1 (или второй бит).
Почему этот полином? Потому что должен быть стандарт, заданный полином, и стандарт был установлен IEEE 802.3. Также чрезвычайно трудно найти многочлен, который эффективно обнаруживает различные битовые ошибки.
Вы можете думать о CRC-32 как о серии "Бинарная арифметика без переносов" или в основном "XOR и операции сдвига". Это технически называется полиномиальной арифметикой.
Чтобы лучше понять это, подумайте об этом умножении:
(x^3 + x^2 + x^0)(x^3 + x^1 + x^0)
= (x^6 + x^4 + x^3
+ x^5 + x^3 + x^2
+ x^3 + x^1 + x^0)
= x^6 + x^5 + x^4 + 3*x^3 + x^2 + x^1 + x^0
Если мы предположим, что x является основанием 2, то получим:
x^7 + x^3 + x^2 + x^1 + x^0
Зачем? Поскольку 3x ^ 3 - это 11x ^ 11 (но нам нужно только 1 или 0 предварительных цифр), поэтому мы переносим:
=1x^110 + 1x^101 + 1x^100 + 11x^11 + 1x^10 + 1x^1 + x^0
=1x^110 + 1x^101 + 1x^100 + 1x^100 + 1x^11 + 1x^10 + 1x^1 + x^0
=1x^110 + 1x^101 + 1x^101 + 1x^11 + 1x^10 + 1x^1 + x^0
=1x^110 + 1x^110 + 1x^11 + 1x^10 + 1x^1 + x^0
=1x^111 + 1x^11 + 1x^10 + 1x^1 + x^0
Но математики изменили правила так, что это мод 2. Таким образом, любой двоичный полиномиальный мод 2 - это просто сложение без переноса или XOR. Итак, наше оригинальное уравнение выглядит так:
=( 1x^110 + 1x^101 + 1x^100 + 11x^11 + 1x^10 + 1x^1 + x^0 ) MOD 2
=( 1x^110 + 1x^101 + 1x^100 + 1x^11 + 1x^10 + 1x^1 + x^0 )
= x^6 + x^5 + x^4 + 3*x^3 + x^2 + x^1 + x^0 (or that original number we had)
Я знаю, что это прыжок веры, но это за пределами моей способности линейного программиста. Если вы опытный студент CS или инженер, я бросаю вызов, чтобы сломать это. Каждый выиграет от этого анализа.
Итак, чтобы проработать полный пример:
Original message : 1101011011
Polynomial of (W)idth 4 : 10011
Message after appending W zeros : 11010110110000
Теперь мы разделим расширенное сообщение на Poly, используя арифметику CRC. Это то же разделение, что и раньше:
1100001010 = Quotient (nobody cares about the quotient)
_______________
10011 ) 11010110110000 = Augmented message (1101011011 + 0000)
=Poly 10011,,.,,....
-----,,.,,....
10011,.,,....
10011,.,,....
-----,.,,....
00001.,,....
00000.,,....
-----.,,....
00010,,....
00000,,....
-----,,....
00101,....
00000,....
-----,....
01011....
00000....
-----....
10110...
10011...
-----...
01010..
00000..
-----..
10100.
10011.
-----.
01110
00000
-----
1110 = Remainder = THE CHECKSUM!!!!
Деление дает частное, которое мы отбрасываем, и остаток, который является вычисленной контрольной суммой. На этом заканчивается расчет. Обычно контрольная сумма затем добавляется к сообщению и результат передается. В этом случае передача будет: 11010110111110.
В качестве делителя используйте только 32-разрядное число, а в качестве дивиденда - весь поток. Выбросьте частное и оставьте остаток. Прикрепите остаток в конце вашего сообщения, и у вас будет CRC32.
Средний обзор парня:
QUOTIENT
----------
DIVISOR ) DIVIDEND
= REMAINDER
- Возьмите первые 32 бита.
- Биты сдвига
- Если 32 бита меньше, чем DIVISOR, перейдите к шагу 2.
- XOR 32 бита от DIVISOR. Переходите к шагу 2.
(Обратите внимание, что поток должен делиться на 32 бита, или он должен быть дополнен. Например, 8-битный поток ANSI должен быть дополнен. Также в конце потока разделение останавливается.)
Ответ 2
CRC довольно прост; вы берете многочлен, представляемый как биты и данные, и делите полином на данные (или вы представляете данные как многочлен и делаете то же самое). Остаток, который находится между 0 и многочленом, является CRC. Ваш код немного сложно понять, отчасти потому, что он неполный: temp и testcrc не объявлены, поэтому неясно, что индексируется, и сколько данных выполняется через алгоритм.
Способ понимания CRC состоит в том, чтобы попытаться вычислить несколько, используя короткую часть данных (16 бит или около того) с коротким многочленом - по 4 бита. Если вы практикуете этот путь, вы действительно поймете, как вы можете его кодировать.
Если вы часто это делаете, CRC довольно медленно вычисляет в программном обеспечении. Аппаратное вычисление намного более эффективно и требует всего нескольких ворот.
Ответ 3
Для IEEE802.3, CRC-32. Подумайте обо всем сообщении в виде последовательного потока бит, добавьте 32 нулей в конец сообщения. Затем вы ДОЛЖНЫ развернуть биты КАЖДОГО байта сообщения и сделать 1 дополнение первых 32 бит. Теперь разделим на многочлен CRC-32, 0x104C11DB7. Наконец, вы должны 1 дополнить 32-битный остаток этого деления бит-реверсировать каждый из 4 байтов остатка. Это становится 32-разрядным CRC, который добавляется к концу сообщения.
Причиной этой странной процедуры является то, что первые реализации Ethernet будут сериализовать сообщение по одному байту за раз и сначала передать младший значащий бит каждого байта. Последовательный бит-поток затем прошел последовательный CRC-32 сдвиговый регистр, который был просто дополнен и отправлен на провод после того, как сообщение было завершено. Причина для дополнения первых 32 бит сообщения заключается в том, что вы не получаете нулевой CRC, даже если сообщение было нулевым.
Ответ 4
В дополнение к Википедии Циклическая проверка избыточности и Вычисление CRC, я нашел статью под названием Реверсивный CRC - теория и практика * чтобы быть хорошей ссылкой.
Существуют три подхода к вычислению CRC: алгебраический подход, битоориентированный подход и подход, основанный на таблицах. В Реверсивный CRC - теория и практика * каждый из этих трех алгоритмов/подходов объясняется в теории, сопровождаемой в ПРИЛОЖЕНИИ реализацией для CRC32 на языке программирования C.
* Ссылка в формате PDF
Реверсирование CRC - теория и практика.
HU Berlin Public Report
SAR-PR-2006-05
Май 2006
Авторы:
Мартин Стигг, Хенрик Плёц, Волк Мюллер, Йенс-Питер Редлих
Ответ 5
Я потратил некоторое время, пытаясь раскрыть ответ на этот вопрос, и наконец опубликовал учебник по CRC-32:
учебник хэша CRC-32 - Сообщество AutoHotkey
В этом примере из него я продемонстрирую, как вычислить хэш CRC-32 для строки ASCII 'abc':
calculate the CRC-32 hash for the ASCII string 'abc':
inputs:
dividend: binary for 'abc': 0b011000010110001001100011 = 0x616263
polynomial: 0b100000100110000010001110110110111 = 0x104C11DB7
011000010110001001100011
reverse bits in each byte:
100001100100011011000110
append 32 0 bits:
10000110010001101100011000000000000000000000000000000000
XOR the first 4 bytes with 0xFFFFFFFF:
01111001101110010011100111111111000000000000000000000000
'CRC division':
01111001101110010011100111111111000000000000000000000000
100000100110000010001110110110111
---------------------------------
111000100010010111111010010010110
100000100110000010001110110110111
---------------------------------
110000001000101011101001001000010
100000100110000010001110110110111
---------------------------------
100001011101010011001111111101010
100000100110000010001110110110111
---------------------------------
111101101000100000100101110100000
100000100110000010001110110110111
---------------------------------
111010011101000101010110000101110
100000100110000010001110110110111
---------------------------------
110101110110001110110001100110010
100000100110000010001110110110111
---------------------------------
101010100000011001111110100001010
100000100110000010001110110110111
---------------------------------
101000011001101111000001011110100
100000100110000010001110110110111
---------------------------------
100011111110110100111110100001100
100000100110000010001110110110111
---------------------------------
110110001101101100000101110110000
100000100110000010001110110110111
---------------------------------
101101010111011100010110000001110
100000100110000010001110110110111
---------------------------------
110111000101111001100011011100100
100000100110000010001110110110111
---------------------------------
10111100011111011101101101010011
remainder: 0b10111100011111011101101101010011 = 0xBC7DDB53
XOR the remainder with 0xFFFFFFFF:
0b01000011100000100010010010101100 = 0x438224AC
reverse bits:
0b00110101001001000100000111000010 = 0x352441C2
thus the CRC-32 hash for the ASCII string 'abc' is 0x352441C2
