Quoi qu'il en soit, calculer un CRC revient a calculer le reste d'une division de polynome binaire (i.e dans le corps Z/2Z). Dans ce corps, la multiplication par "x" est un décalage de 1 bit. L'addition et la soustraction est un "ou exclusif" (XOR).
Par exemple, calculer le CRC 32bits sur le message "0xFF" revient à effectuer le calcul suivant:
CRC( 0xFF (hexa) )
= CRC( 11111111 (binaire) )
= CRC( 1.x^7 + 1.x^6 + 1.x^5 + 1.x^4 + 1.x^3 + 1.x^2 + 1.x^1 + 1.x^0 )
= (x^7+x^6+x^5+x^4+x^3+x^2+x^1+x^0) * x^32 modulo POLYCRC(x)
= (x^39+x^38+x^37+x^36+x^35+x^34+x^33+x^32) modulo POLYCRC(x)
avec le polynome CRC32 habituel POLYCRC(x) = x^32+x^26+x^23+x^22+x^16+x^12+x^11+x^10+x^8+x^7+x^5+x^4+x^2+x^+1
on obtient:
CRC( 0xFF (hexa) )
= x^31+x^29+x^28+x^24+x^23+x^22+x^21+x^20+x^18+x^17+x^16+x^14+x^7+x^5+x^4+x^2
= 10110001111101110100000010110100 (binaire)
= B1F740B4 (hexa)
En pratique, on ne fait pas la division sur le polynome complet du message. On met à jour le CRC a chaque bit du message.
1 2 3 4
| CRC(x)=0
Pour chaque bit "b" du message
CRC(x) = (CRC(x) * x^1 + b*x^32) modulo POLYCRC(x)
Fin pour |
ATTENTION: Pour le calcul du "vrai" CRC32, on initialise le CRC avec des bits à "1", et au final on inverse tous les bits. Cette modification permet de prendre en compte les "zeros" en début/fin de message.
1 2 3 4 5
| CRC(x) = x^31 + ... + x^1 + x^0
Pour chaque bit "b" du message
CRC(x) = (CRC(x) * x^1 + b*x^32) modulo POLYCRC(x)
Fin pour
CRC(x) = CRC(x) - (x^31 + ... + x^1 + x^0) |
Partager