Table of Contents

Les exemples pratiques utilisés dans cette démonstration proviennent de cette page.
Sur processeur AVR, une bibliothèque existe : Somme de contrôle CRC

DOW CRC (Dallas One Wire CRC)

Le code ci-dessous ne fonctionne pas. Mélange entre chaine de caractère et chaine normale

DOW CRC-8

Fonction

#include <stdio.h>
#include <string.h>
#define CRCPOLY8 0x18           //correspond au masque des XOR sur le polynôme x⁸+x⁵+x⁴+x⁰
 
void main(void)
{
        int crc = 0x00 , i = 0, bit_counter = 0, b = 0, feedback_bit = 0, length = 0;       //déclaration + initialisation des variables
        char string[]={"A200000001B81C02"};     //chaîne utilisée pour le calcul du crc
 
        length = strlen(string)-1;          //la longueur de la chaîne -1 (car tableau de caractères commence à 0)
        for (i=0; i<=length; i++)           //passage dans chaque cellules de la chaine string
        {                       
                b = string[length-i];         //nous travaillons de droite à gauche(length-i)
                bit_counter = 4;        //si le caractère a déjà été décomposé en hexadécimal => 4 bits par valeur
                while (bit_counter>0)   //passage dans la boucle 4 fois
                {                               
                        feedback_bit = (crc ^ b) & 0x01;                //vérification de la valeur du dernier bit
                        if (feedback_bit == 0x01) crc = crc ^ CRCPOLY8;    //si le dernier bit est un 1, XOR entre le CRC et le polynôme
                        crc = (crc >> 1) & 0x7F;                        //déplacement de crc de 1 sur la droite + vérification que le bit rajouter (celui de gauche) est bien un 0
                        if (feedback_bit == 0x01) crc = crc | 0x80;      //implantation du 1 du feedback_bit (1 au dernier bit) dans le crc en tant que premier bit (tout à gauche)
                        b = b>>1;         //déplacement de b de 1 sur la droite (car le dernier bit a déjà été utilisé)
                        bit_counter--;
                }
        }
        printf("%#x\n",crc);
}

Exemple de fonctionnement

1-Wire ROM: A2 00 00 00 01 B8 1C 02
CRCPOLY8 = 0x18
CRCinitial = 0x00

i=0

b = string [15] <=> '2' [0000'0010]

bit_counter = 4
 feedback_bit = (crc ^ b) & 0x01;
crc XOR b
crc 0000'0000
b 0000'0010
Résultat 0000'0010
(crc XOR b) & 0x01
crc XOR b 0000'0010
0x01 0000'0001
Résultat 0000'0000

⇒ feedback_bit = 0x00

 crc = (crc >> 1) & 0x7F; 
crc»1
crc 0000'0000
crc»1 0000'0000
(crc»1) & 0x7F
crc»1 0000'0000
0x7F 0111'1111
Résultat 0000'0000

⇒ crc = 0x00

 b = b>>1; 
b»1
b 0000'0010
b»1 0000'0001

⇒ b = 0x01

bit_counter = 3
 feedback_bit = (crc ^ b) & 0x01;
crc XOR b
crc 0000'0000
b 0000'0001
Résultat 0000'0001
(crc XOR b) & 0x01
crc XOR b 0000'0001
0x01 0000'0001
Résultat 0000'0001

⇒ feedback_bit = 0x01

 if (feedback_bit == 0x01) crc = crc ^ CRCPOLY8; 
crc XOR CRCPOLY8
crc 0000'0000
CRCPOLY8 0001'1000
Résultat 0001'1000

⇒ crc = 0x18

 crc = (crc >> 1) & 0x7F; 
crc»1
crc 0001'1000
crc»1 0000'1100
(crc»1) & 0x7F
crc»1 0000'1100
0x7F 0111'1111
Résultat 0000'1100

⇒ crc = 0x0C

 if (feedback_bit == 0x01) crc = crc | 0x80; 
crc OR 0x80
crc 0000'1100
0x80 1000'0000
Résultat 1000'1100

⇒ crc = 0x8C

 b = b>>1; 
b»1
b 0000'0001
b»1 0000'0000

⇒ b = 0x00

bit_counter = 2
 feedback_bit = (crc ^ b) & 0x01;
crc XOR b
crc 1000'1100
b 0000'0000
Résultat 1000'1100
(crc XOR b) & 0x01
crc XOR b 1000'1110
0x01 0000'0001
Résultat 0000'0000

⇒ feedback_bit = 0x00

 crc = (crc >> 1) & 0x7F; 
crc»1
crc 1000'1100
crc»1 0100'0110
(crc»1) & 0x7F
crc»1 0100'0110
0x7F 0111'1111
Résultat 0100'0110

⇒ crc = 0x46

 b = b>>1; 
b»1
b 0000'0000
b»1 0000'0000

⇒ b = 0x00

bit_counter = 1
 feedback_bit = (crc ^ b) & 0x01;
crc XOR b
crc 0100'0110
b 0000'0000
Résultat 0100'0110
(crc XOR b) & 0x01
crc XOR b 0100'0110
0x01 0000'0001
Résultat 0000'0000

⇒ feedback_bit = 0x00

 crc = (crc >> 1) & 0x7F; 
crc»1
crc 0100'0110
crc»1 0010'0011
(crc»1) & 0x7F
crc»1 0010'0011
0x7F 0111'1111
Résultat 0010'0011

⇒ crc = 0x23

 b = b>>1; 
b»1
b 0000'0000
b»1 0000'0000

⇒ b = 0x00

i=1

b = string [14] <=> '0' [0000'0000]

bit_counter = 4
 feedback_bit = (crc ^ b) & 0x01;
crc XOR b
crc 0010'0011
b 0000'0000
Résultat 0010'0011
(crc XOR b) & 0x01
crc XOR b 0010'0011
0x01 0000'0001
Résultat 0000'0001

⇒ feedback_bit = 0x01

 if (feedback_bit == 0x01) crc = crc ^ CRCPOLY8; 
crc XOR CRCPOLY8
crc 0010'0011
CRCPOLY8 0001'1000
Résultat 0011'1011

⇒ crc = 0x3B

 crc = (crc >> 1) & 0x7F; 
crc»1
crc 0011'1011
crc»1 0001'1101
(crc»1) & 0x7F
crc»1 0001'1101
0x7F 0111'1111
Résultat 0001'1101

⇒ crc = 0x1D

 if (feedback_bit == 0x01) crc = crc | 0x80; 
crc OR 0x80
crc 0001'1101
0x80 1000'0000
Résultat 1001'1101

⇒ crc = 0x9D

 b = b>>1; 
b»1
b 0000'0000
b»1 0000'0000

⇒ b = 0x00

bit_counter = 3
 feedback_bit = (crc ^ b) & 0x01;
crc XOR b
crc 1001'1101
b 0000'0000
Résultat 1001'1101
(crc XOR b) & 0x01
crc XOR b 1001'1101
0x01 0000'0001
Résultat 0000'0001

⇒ feedback_bit = 0x01

 if (feedback_bit == 0x01) crc = crc ^ CRCPOLY8; 
crc XOR CRCPOLY8
crc 1001'1101
CRCPOLY8 0001'1000
Résultat 1000'0101

⇒ crc = 0x85

 crc = (crc >> 1) & 0x7F; 
crc»1
crc 1000'0101
crc»1 0100'0010
(crc»1) & 0x7F
crc»1 0100'0010
0x7F 0111'1111
Résultat 0100'0010

⇒ crc = 0x42

 if (feedback_bit == 0x01) crc = crc | 0x80; 
crc OR 0x80
crc 0100'0010
0x80 1000'0000
Résultat 1100'0010

⇒ crc = 0xC2

 b = b>>1; 
b»1
b 0000'0000
b»1 0000'0000

⇒ b = 0x00

bit_counter = 2
 feedback_bit = (crc ^ b) & 0x01;
crc XOR b
crc 1100'0010
b 0000'0000
Résultat 1100'0010
(crc XOR b) & 0x01
crc XOR b 1100'0010
0x01 0000'0001
Résultat 0000'0000

⇒ feedback_bit = 0x00

 crc = (crc >> 1) & 0x7F; 
crc»1
crc 1100'0010
crc»1 0110'0001
(crc»1) & 0x7F
crc»1 0110'0001
0x7F 0111'1111
Résultat 0110'0001

⇒ crc = 0x61

 b = b>>1; 
b»1
b 0000'0000
b»1 0000'0000

⇒ b = 0x00

bit_counter = 1
 feedback_bit = (crc ^ b) & 0x01;
crc XOR b
crc 0110'0001
b 0000'0000
Résultat 0110'0001
(crc XOR b) & 0x01
crc XOR b 0110'0001
0x01 0000'0001
Résultat 0000'0001

⇒ feedback_bit = 0x01

 if (feedback_bit == 0x01) crc = crc ^ CRCPOLY8; 
crc XOR CRCPOLY8
crc 0110'0001
CRCPOLY8 0001'1000
Résultat 0111'1001

⇒ crc = 0x79

 crc = (crc >> 1) & 0x7F; 
crc»1
crc 0111'1001
crc»1 0011'1100
(crc»1) & 0x7F
crc»1 0011'1100
0x7F 0111'1111
Résultat 0011'1100

⇒ crc = 0x3C

 if (feedback_bit == 0x01) crc = crc | 0x80; 
crc OR 0x80
crc 0011'1100
0x80 1000'0000
Résultat 1011'1100

⇒ crc = 0xBC

 b = b>>1; 
b»1
b 0000'0000
b»1 0000'0000

⇒ b = 0x00

i=2

b = string [13] <=> 'C' [0000'1100]

.
.
.

i=13

b = string [2] <=> '0' [0000'0000]

.
.
.

bit_counter = 1
 feedback_bit = (crc ^ b) & 0x01;
crc XOR b
crc 0101'1101
b 0000'0000
Résultat 0101'1101
(crc XOR b) & 0x01
crc XOR b 0101'1101
0x01 0000'0001
Résultat 0000'0001

⇒ feedback_bit = 0x01

 if (feedback_bit == 0x01) crc = crc ^ CRCPOLY8; 
crc XOR CRCPOLY8
crc 0101'1101
CRCPOLY8 0001'1000
Résultat 0100'0101

⇒ crc = 0x45

 crc = (crc >> 1) & 0x7F; 
crc»1
crc 0100'0101
crc»1 0010'0010
(crc»1) & 0x7F
crc»1 0010'0010
0x7F 0111'1111
Résultat 0010'0010

⇒ crc = 0x22

 if (feedback_bit == 0x01) crc = crc | 0x80; 
crc OR 0x80
crc 0010'0010
0x80 1000'0000
Résultat 1010'0010

⇒ crc = 0xA2 {C'est la valeur du CRC pour [00000001B81C (Numéro de série) + 02 (Family Code)], s'il est ajouté à la suite du numéro de série, le CRC final sera de 0x00!}

.
.
.

i=14

b = string [1] <=> '2' [0000'0010]

.
.
.

i=15

b = string [0] <=> 'A' [0000'1010]

.
.
.

bit_counter = 1

.
.
.

⇒ crc = 0x00 {Nous avons au final un 0x00, 0xA2 est bel et bien le CRC de [00000001B81C02]}

DOW CRC-16

Fonction

#include <stdio.h>
#include <string.h>
#define CRCPOLY16 0x4002           //correspond au masque des XOR sur le polynôme x^16+x^15+x^2+x^0
 
void main(void)
{
        int crc = 0x0000 , i = 0, bit_counter = 0, b = 0, feedback_bit = 0, length = 0;       //déclaration + initialisation des variables
        char string[]={"75"};     //chaîne utilisée pour le calcul du crc
 
        length = strlen(string)-1;          //la longueur de la chaîne -1 (car tableau de caractères commence à 0)
        for (i=0; i<=length; i++)           //passage dans chaque cellules de la chaine string
        {                       
                b = string[length-i];         //nous travaillons de droite à gauche(length-i)
                bit_counter = 4;        //si le caractère a déjà été décomposé en hexadécimal => 4 bits par valeur
                while (bit_counter>0)   //passage dans la boucle 4 fois
                {                               
                        feedback_bit = (crc ^ b) & 0x0001;                //vérification de la valeur du dernier bit
                        if (feedback_bit == 0x0001) crc = crc ^ CRCPOLY16;    //si le dernier bit est un 1, XOR entre le CRC et le polynôme
                        crc = (crc >> 1) & 0x7FFF;                        //déplacement de crc de 1 sur la droite + vérification que le bit rajouter (celui de gauche) est bien un 0
                        if (feedback_bit == 0x0001) crc = crc | 0x8000;      //implantation du 1 du feedback_bit (1 au dernier bit) dans le crc en tant que premier bit (tout à gauche)
                        b = b>>1;         //déplacement de b de 1 sur la droite (car le dernier bit a déjà été utilisé)
                        bit_counter--;
                }
        }
        printf("%#x\n",crc);
}

Exemple de fonctionnement

1-Wire ROM: 75
CRCPOLY16 = 0x4002
CRCinitial = 0x90F1

i=0

b = string [1] <=> '5' [0000'0000'0000'0101]

bit_counter = 4
 feedback_bit = (crc ^ b) & 0x0001;
crc XOR b
crc 1001'0000'1111'0001
b 0000'0000'0000'0101
Résultat 1001'0000'1111'0100
(crc XOR b) & 0x0001
crc XOR b 1001'0000'1111'0100
0x0001 0000'0000'0000'0001
Résultat 0000'0000'0000'0000

⇒ feedback_bit = 0x0000

 crc = (crc >> 1) & 0x7FFF; 
crc»1
crc 1001'0000'1111'0001
crc»1 0100'1000'0111'1000
(crc»1) & 0x7FFF
crc»1 0100'1000'0111'1000
0x7FFF 0111'1111'1111'1111
Résultat 0100'1000'0111'1000

⇒ crc = 0x4878

 b = b>>1; 
b»1
b 0000'0000'0000'0101
b»1 0000'0000'0000'0010

⇒ b = 0x0002

bit_counter = 3
 feedback_bit = (crc ^ b) & 0x0001;
crc XOR b
crc 0100'1000'0111'1000
b 0000'0000'0000'0010
Résultat 0100'1000'0111'1010
(crc XOR b) & 0x0001
crc XOR b 0100'1000'0111'1010
0x0001 0000'0000'0000'0001
Résultat 0000'0000'0000'0000

⇒ feedback_bit = 0x0000

 crc = (crc >> 1) & 0x7FFF; 
crc»1
crc 0100'1000'0111'1000
crc»1 0010'0100'0011'1100
(crc»1) & 0x7FFF
crc»1 0010'0100'0011'1100
0x7FFF 0111'1111'1111'1111
Résultat 0010'0100'0011'1100

⇒ crc = 0x243C

 b = b>>1; 
b»1
b 0000'0000'0000'0010
b»1 0000'0000'0000'0001

⇒ b = 0x0001

bit_counter = 2
 feedback_bit = (crc ^ b) & 0x0001;
crc XOR b
crc 0010'0100'0011'1100
b 0000'0000'0000'0001
Résultat 0010'0100'0011'1101
(crc XOR b) & 0x0001
crc XOR b 0010'0100'0011'1101
0x0001 0000'0000'0000'0001
Résultat 0000'0000'0000'0001

⇒ feedback_bit = 0x0001

 if (feedback_bit == 0x0001) crc = crc ^ CRCPOLY16; 
crc XOR CRCPOLY8
crc 0010'0100'0011'1100
CRCPOLY16 0100'0000'0000'0010
Résultat 0110'0100'0011'1110

⇒ crc = 0x643E

 crc = (crc >> 1) & 0x7FFF; 
crc»1
crc 0110'0100'0011'1110
crc»1 0011'0010'0001'1111
(crc»1) & 0x7FFF
crc»1 0011'0010'0001'1111
0x7FFF 0111'1111'1111'1111
Résultat 0011'0010'0001'1111

⇒ crc = 0x321F

 if (feedback_bit == 0x0001) crc = crc | 0x80; 
crc OR 0x8000
crc 0011'0010'0001'1111
0x8000 1000'0000'0000'0000
Résultat 1011'0010'0001'1111

⇒ crc = 0xB21F

 b = b>>1; 
b»1
b 0000'0000'0000'0001
b»1 0000'0000'0000'0000

⇒ b = 0x0000

bit_counter = 1
 feedback_bit = (crc ^ b) & 0x0001;
crc XOR b
crc 1011'0010'0001'1111
b 0000'0000'0000'0000
Résultat 1011'0010'0001'1111
(crc XOR b) & 0x0001
crc XOR b 1011'0010'0001'1111
0x0001 0000'0000'0000'0001
Résultat 0000'0000'0000'0001

⇒ feedback_bit = 0x0001

 if (feedback_bit == 0x0001) crc = crc ^ CRCPOLY16; 
crc XOR CRCPOLY8
crc 1011'0010'0001'1111
CRCPOLY16 0100'0000'0000'0010
Résultat 1111'0010'0001'1101

⇒ crc = 0xF21D

 crc = (crc >> 1) & 0x7FFF; 
crc»1
crc 1111'0010'0001'1101
crc»1 0111'1001'0000'1110
(crc»1) & 0x7FFF
crc»1 0111'1001'0000'1110
0x7FFF 0111'1111'1111'1111
Résultat 0111'1001'0000'1110

⇒ crc = 0x790E

 if (feedback_bit == 0x0001) crc = crc | 0x80; 
crc OR 0x8000
crc 0111'1001'0000'1110
0x8000 1000'0000'0000'0000
Résultat 1111'1001'0000'1110

⇒ crc = 0xF90E

 b = b>>1; 
b»1
b 0000'0000'0000'0000
b»1 0000'0000'0000'0000

⇒ b = 0x0000

i= 1

b = string [0] <=> '7' [0000'0000'0000'0111]

bit_counter = 4
 feedback_bit = (crc ^ b) & 0x0001;
crc XOR b
crc 1111'1001'0000'1110
b 0000'0000'0000'0111
Résultat 1111'1001'0000'1001
(crc XOR b) & 0x0001
crc XOR b 1111'1001'0000'1001
0x0001 0000'0000'0000'0001
Résultat 0000'0000'0000'0001

⇒ feedback_bit = 0x0001

 if (feedback_bit == 0x0001) crc = crc ^ CRCPOLY16; 
crc XOR CRCPOLY8
crc 1111'1001'0000'1110
CRCPOLY16 0100'0000'0000'0010
Résultat 1011'1001'0000'1100

⇒ crc = 0xB90C

 crc = (crc >> 1) & 0x7FFF; 
crc»1
crc 1011'1001'0000'1100
crc»1 0101'1100'1000'0110
(crc»1) & 0x7FFF
crc»1 0101'1100'1000'0110
0x7FFF 0111'1111'1111'1111
Résultat 0101'1100'1000'0110

⇒ crc = 0x5C86

 if (feedback_bit == 0x0001) crc = crc | 0x80; 
crc OR 0x8000
crc 0101'1100'1000'0110
0x8000 1000'0000'0000'0000
Résultat 1101'1100'1000'0110

⇒ crc = 0xDC86

 b = b>>1; 
b»1
b 0000'0000'0000'0111
b»1 0000'0000'0000'0011

⇒ b = 0x0003

bit_counter = 3
 feedback_bit = (crc ^ b) & 0x0001;
crc XOR b
crc 1101'1100'1000'0110
b 0000'0000'0000'0011
Résultat 1101'1100'1000'0101
(crc XOR b) & 0x0001
crc XOR b 1101'1100'1000'0101
0x0001 0000'0000'0000'0001
Résultat 0000'0000'0000'0001

⇒ feedback_bit = 0x0001

 if (feedback_bit == 0x0001) crc = crc ^ CRCPOLY16; 
crc XOR CRCPOLY8
crc 1101'1100'1000'0110
CRCPOLY16 0100'0000'0000'0010
Résultat 1001'1100'1000'0100

⇒ crc = 0x9C84

 crc = (crc >> 1) & 0x7FFF; 
crc»1
crc 1001'1100'1000'0100
crc»1 0100'1110'0100'0010
(crc»1) & 0x7FFF
crc»1 0100'1110'0100'0010
0x7FFF 0111'1111'1111'1111
Résultat 0100'1110'0100'0010

⇒ crc = 0x4E42

 if (feedback_bit == 0x0001) crc = crc | 0x80; 
crc OR 0x8000
crc 0100'1110'0100'0010
0x8000 1000'0000'0000'0000
Résultat 1100'1110'0100'0010

⇒ crc = 0xCE42

 b = b>>1; 
b»1
b 0000'0000'0000'0011
b»1 0000'0000'0000'0001

⇒ b = 0x0001

bit_counter = 2
 feedback_bit = (crc ^ b) & 0x0001;
crc XOR b
crc 1100'1110'0100'0010
b 0000'0000'0000'0001
Résultat 1100'1110'0100'0011
(crc XOR b) & 0x0001
crc XOR b 1100'1110'0100'0011
0x0001 0000'0000'0000'0001
Résultat 0000'0000'0000'0001

⇒ feedback_bit = 0x0001

 if (feedback_bit == 0x0001) crc = crc ^ CRCPOLY16; 
crc XOR CRCPOLY8
crc 1100'1110'0100'0010
CRCPOLY16 0100'0000'0000'0010
Résultat 1000'1110'0100'0000

⇒ crc = 0x8E40

 crc = (crc >> 1) & 0x7FFF; 
crc»1
crc 1000'1110'0100'0000
crc»1 0100'0111'0010'0000
(crc»1) & 0x7FFF
crc»1 0100'0111'0010'0000
0x7FFF 0111'1111'1111'1111
Résultat 0100'0111'0010'0000

⇒ crc = 0x4720

 if (feedback_bit == 0x0001) crc = crc | 0x80; 
crc OR 0x8000
crc 0100'0111'0010'0000
0x8000 1000'0000'0000'0000
Résultat 1100'0111'0010'0000

⇒ crc = 0xC720

 b = b>>1; 
b»1
b 0000'0000'0000'0001
b»1 0000'0000'0000'0000

⇒ b = 0x0000

bit_counter = 1
 feedback_bit = (crc ^ b) & 0x0001;
crc XOR b
crc 1100'0111'0010'0000
b 0000'0000'0000'0000
Résultat 1100'0111'0010'0000
(crc XOR b) & 0x0001
crc XOR b 1100'0111'0010'0000
0x0001 0000'0000'0000'0001
Résultat 0000'0000'0000'0000

⇒ feedback_bit = 0x0000

 crc = (crc >> 1) & 0x7FFF; 
crc»1
crc 1100'0111'0010'0000
crc»1 0110'0011'1001'0000
(crc»1) & 0x7FFF
crc»1 0110'0011'1001'0000
0x7FFF 0111'1111'1111'1111
Résultat 0110'0011'1001'0000

⇒ crc = 0x6390