Calcolo Ethernet CRC32 - software vs risultato algoritmico

Question

Sto provando a calcolare il Frame Check Sequence (FCS) di un pacchetto Ethernet byte per byte. Il polinomio è 0x104C11DB7. ho seguito l'algoritmo XOR-SHIFT visto qui http://en.wikipedia.org/wiki/Cyclic_redundancy_check o qui http://www.woodmann.com/fravia/crctut1.htm

assuma le informazioni che si suppone hanno un CRC è un solo byte. Diciamo che è 0x03.

1. passo: pad con 32 bit verso destra

   0x0300000000

2. allineare il polinomio e consistenza a sinistra con il primo bit che non è zero e XOR loro

   0x300000000 xor 0x209823B6E = 0x109823b6e

3. take restante allineare e xor nuovamente

   0x109823b6e xor 0x104C11DB7 = 0x0d4326d9

Dato che non ci sono più po 'lasciato il CRC32 di 0x03 dovrebbe essere 0x0d4326d9

Purtroppo tutte le implementazioni software mi dicono che sbaglio, ma che cosa ho fatto di sbagliato o che cosa stanno facendo diversamente?

Python mi dice:

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

Lo strumento on-line qui http://www.lammertbies.nl/comm/info/crc-calculation.html#intr ottiene lo stesso risultato. Qual è la differenza tra il mio calcolo manuale e l'algoritmo utilizzato dal software menzionato?

UPDATE:

Abbiamo scoperto che c'era una domanda simile già in stack overflow:

Potete trovare una risposta qui Python CRC-32 woes

Anche se questo non è molto intuitivo. Se si desidera una descrizione più formale su come è fatto per Ethernet cornici si può guardare il Ethernet Standard document 802.3 Parte 3 - Capitolo 3.2.9 Frame Check Sequence campo

Consente continuare l'esempio dall'alto:

1. Invertire l'ordine dei bit del tuo messaggio. Questo rappresenta il modo in cui sarebbero entrati nel ricevitore a poco a poco.

   0x03 è quindi 0xC0

2. complemento del primo 32 bit del messaggio. Si noti che il singolo byte viene ripetuto con 32 bit nuovamente.

   0xC000000000 xor 0xFFFFFFFF = 0x3FFFFFFF00

3. Completa il Xor e metodo di spostamento dall'alto di nuovo. Dopo circa 6 passo si ottiene:

   0x13822f2d

4. Il bit sequense sopra viene poi completato.

   0x13822f2d xor 0xFFFFFFFF = 0xec7dd0d2

5. Ricordate che abbiamo invertito l'ordine po 'per ottenere la rappresentazione sul filo Ethernet al punto uno. Ora dobbiamo invertire questo passo e alla fine completiamo la nostra ricerca.

   0x4b0bbe37

Chi si avvicinò con questo modo di fare che dovrebbe essere ...

Un sacco di volte si vuole realmente sapere che il messaggio ricevuto è corretto. Per raggiungere questo obiettivo, si prende il messaggio ricevuto, incluso FCS, e si esegue lo stesso passaggio da 1 a 5 come sopra. Il risultato dovrebbe essere quello che chiamano il residuo. Che è una costante per un dato polinomio. In questo caso è 0xC704DD7B.

Come mcdowella menzioni devi giocare con i tuoi bit fino a quando non lo fai, a seconda dell'applicazione che si sta utilizzando.

Answer 1

Generalmente, è necessario un po 'di tentativi ed errori per far coincidere i calcoli del CRC, perché non si finisce mai di leggere esattamente ciò che deve essere fatto. A volte è necessario reindirizzare i byte di input o il polinomio, a volte è necessario iniziare con un valore diverso da zero e così via.

Un modo per aggirare questo è guardare all'origine di un programma che lo fa correttamente, come ad esempio http://sourceforge.net/projects/crcmod/files/ (almeno afferma di corrispondere, e viene fornito con un test di unità per questo).

Un altro è giocare con un'implementazione. Per esempio, se uso la calcolatrice a http://www.lammertbies.nl/comm/info/crc-calculation.html#intr posso vedere che dandogli 00000000 produce un CRC di 0x2144DF1C, ma dandogli FFFFFFFF produce FFFFFFFF - quindi non è esattamente la divisione polinomiale che lei descrive, per cui 0 avrebbe checksum 0

Da una rapida occhiata al codice sorgente e questi risultati penso che sia necessario iniziare con un CRC di 0xFFFFFFFF - ma potrei sbagliarmi e si potrebbe finire per eseguire il debugging del codice fianco a fianco dell'implementazione, usando printfs corrispondenti per scoprirlo dove il primo differisce e fissa le differenze una per una.

Answer 2

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

ha tutti i dati per ethernet e la ricchezza di dettagli importanti, ad esempio, ci sono (almeno) 2 convenzioni per codificare polinomio in un valore a 32 bit, il più grande primo termine o più piccolo termine prima.

Answer 3

Ci sono diversi posti su Internet in cui si legge che l'ordine dei bit deve essere invertito prima di calcolare FCS, ma la specifica 802.3 non è una di queste.Citando dalla versione 2008 della specifica:

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]. 

Certamente il resto dei bit nel frame sono trasmessi in ordine inverso, ma che non include l'FCS. Anche in questo caso, dalla specifica:

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 4

Questo frammento di Python scrive il corretto CRC per 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) 

mi avrebbe risparmiato un po 'di tempo, se ho trovato qui.