Расчет Ethernet CRC32 - программное обеспечение против алгоритмического результата

Question

Я пытаюсь вычислить последовательность проверки кадра (FCS) байта пакета Ethernet.Полином является 0x104C11DB7.Я следовал алгоритму XOR-SHIFT, показанному здесь http://en.wikipedia.org/wiki/Cyclic_redundancy_check или здесь http://www.woodmann.com/fravia/crctut1.htm

Предположим, что информация, которая предположительно имеет CRC, составляет только один байт.Скажем, это 0x03.

1. шаг: pad с 32 битами вправо

   0x0300000000

2. выровнятьполином и данные с левой стороны с их первым битом, который не равен нулю, и xor их

   0x300000000 xor 0x209823B6E = 0x109823b6e

3. принимают выравнивание остатка и снова xor

   0x109823b6e xor 0x104C11DB7 = 0x0d4326d9

Поскольку больше не осталось битов, CRC32 0x03 должен быть 0x0d4326d9

К сожалению, все реализации программного обеспечения говорят мне, что янеправильно, но что я сделал не так или что они делают по-другому?

Python говорит мне:

 "0x%08x" % binascii.crc32(chr(0x03))
 0x4b0bbe37

Онлайн-инструмент здесь http://www.lammertbies.nl/comm/info/crc-calculation.html#intr получает тот же результат.В чем разница между моими ручными вычислениями и алгоритмом, который использует упомянутое программное обеспечение?

ОБНОВЛЕНИЕ:

Оказывается, подобный вопрос уже был о переполнении стека:

Вы найдете ответ здесь Python CRC-32 горе

Хотя это не очень интуитивно понятно.Если вы хотите более формальное описание того, как это делается для фреймов Ethernet, вы можете обратиться к Стандартному документу Ethernet 802.3 Часть 3 - Глава 3.2.9 Поле последовательности проверки фреймов

Давайте продолжимпример сверху:

1. Обратный порядок бит вашего сообщения.Это представляет способ, которым они будут входить в приемник по крупицам.

   0x03, следовательно, равно 0xC0

2. Дополнить первые 32 бита вашего сообщения.Обратите внимание, что мы дополняем 32-битный одиночный байт.

   0xC000000000 xor 0xFFFFFFFF = 0x3FFFFFFF00

3. Завершите метод Xor и Shift сверху.Примерно через 6 шагов вы получите:

   0x13822f2d

4. Затем приведенная выше последовательность битов дополняется.

   0x13822f2d xor 0xFFFFFFFF = 0xec7dd0d2

5. Помните, что мы изменили порядок битов, чтобы получить представление на проводе Ethernet на первом этапе.Теперь мы должны повернуть вспять этот шаг, и мы наконец выполним наш квест.

   0x4b0bbe37

Кто бы ни придумал этот способ сделать это, он должен быть ...

Очень часто вы действительно хотите знать, что полученное вами сообщение верное.Для этого вы принимаете полученное сообщение, включая FCS, и выполняете те же шаги с 1 по 5, что и выше.Результатом должно быть то, что они называют остатком.Который является константой для данного полинома.В этом случае это 0xC704DD7B.

Как mcdowella упоминает, что вы должны поиграться со своими битами, пока вы не сделаете это правильно, в зависимости от приложения, которое вы используете.

Answer 1

Этот фрагмент Python записывает правильный CRC для Ethernet:

# write payload
for byte in data:
    f.write('%02X\n' % ord(byte))
# write FCS
crc = zlib.crc32(data)&0xFFFFFFFF
for i in range(4):
    b = (crc >> (8*i)) & 0xFF
    f.write('%02X\n' % b)

Спас бы меня некоторое время, если бы я нашел это здесь.

Answer 2

В Интернете есть несколько мест, где вы прочтете, что порядок битов должен быть обращен до вычисления FCS, но спецификация 802.3 не является одной из них. Цитирование из версии 2008 спецификации:

3.2.9 Frame Check Sequence (FCS) field

A cyclic redundancy check (CRC) is used by the transmit and receive algorithms to
generate a CRC value for the FCS field. The FCS field contains a 4-octet (32-bit)
CRC value. This value is computed as a function of the contents of the protected
fields of the MAC frame: the Destination Address, Source Address, Length/ Type 
field, MAC Client Data, and Pad (that is, all fields except FCS). The encoding is
defined by the following generating polynomial.

  G(x) = x32 + x26 + x23 + x22 + x16 + x12 + x11 
             + x10 + x8 + x7 + x5 + x4 + x2 + x + 1

Mathematically, the CRC value corresponding to a given MAC frame is defined by 
the following procedure:

a) The first 32 bits of the frame are complemented.
b) The n bits of the protected fields are then considered to be the coefficients
   of a polynomial M(x) of degree n – 1. (The first bit of the Destination Address
   field corresponds to the x(n–1) term and the last bit of the MAC Client Data 
   field (or Pad field if present) corresponds to the x0 term.)
c) M(x) is multiplied by x32 and divided by G(x), producing a remainder R(x) of
   degree ≤ 31.
d) The coefficients of R(x) are considered to be a 32-bit sequence.
e) The bit sequence is complemented and the result is the CRC.

The 32 bits of the CRC value are placed in the FCS field so that the x31 term is
the left-most bit of the first octet, and the x0 term is the right most bit of the
last octet. (The bits of the CRC are thus transmitted in the order x31, x30,..., 
x1, x0.) See Hammond, et al. [B37].

Конечно, остальные биты в кадре передаются в обратном порядке, но это не включает FCS. Опять же из спецификации:

3.3 Order of bit transmission

Each octet of the MAC frame, with the exception of the FCS, is transmitted least
significant bit first.

Answer 3

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

Один из способов обойти это - посмотреть на источник программы, который понимает это правильно, такой как http://sourceforge.net/projects/crcmod/files/ (по крайней мере, он утверждает, что соответствует, и поставляется с модульным тестом для этого).

Другой способ - поиграть с реализацией. Например, если я использую калькулятор на http://www.lammertbies.nl/comm/info/crc-calculation.html#intr, я могу видеть, что при присвоении ему 00000000 получается CRC 0x2144DF1C, но при его значении FFFFFFFF получается FFFFFFFF - так что вы описываете не совсем полиномиальное деление, для которого 0 будет иметь контрольная сумма 0

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

Answer 4

http://en.wikipedia.org/wiki/Cyclic_redundancy_check

имеет все данные для Ethernet и множество важных деталей, например, есть (по крайней мере) 2 соглашения для кодирования полинома в 32-битное значение, самый большой член первый или самый маленький член первый.