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

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

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

шаг: колодка с 32 битами вправо

0x0300000000

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

0x300000000 xor 0x209823B6E = 0x109823b6e

взять остаток выровнять и снова 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 Поле последовательности проверки кадра

Продолжим пример сверху:

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

0x03 поэтому0xC0

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

0xC000000000 xor 0xFFFFFFFF = 0x3FFFFFFF00

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

0x13822f2d

Вышеуказанная последовательность битов затем дополняется.

0x13822f2d xor 0xFFFFFFFF = 0xec7dd0d2

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

0x4b0bbe37

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

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

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

 cp.engr24 янв. 2017 г., 20:29
@sebs, как меняли?
 sebs15 февр. 2012 г., 21:56
0x209823B6E - это сдвинутая версия полинома для выравнивания его с данными
 sebs27 нояб. 2018 г., 18:38
@ cp.engr сдвинут на один бит влево.(0x104C11DB7 << 1)
 grieve15 февр. 2012 г., 06:31
Откуда берется 0x209823B6E?
 grieve15 февр. 2012 г., 06:48
Также вы установили начальный остаток на 0xFFFFFFFF

Ответы на вопрос(4)

# 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)

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

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

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

для согласования вычислений 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, чтобы выяснить, где первые отличаются и фиксируют различия один за другим.

где вы прочтете, что порядок битов должен быть обращен до вычисления 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.
 hobbs06 мар. 2015 г., 18:37
Просто подразумевается, что «первый бит» и «последний бит» относятся к порядку передачи - онине по этой причине сказать «старший значащий бит» или «наименее значимый бит» :)

Ваш ответ на вопрос