Les sommes de contrôle

10 + 1 = 11, 1 + 1 = 1

Image d'entête

par skywodd | | Licence (voir pied de page)

Catégories : Cours Tutoriels Arduino | Mots clefs : Arduino Genuino Mémoire EEPROM Checksum CRC

Cet article a été modifié pour la dernière fois le


Dans un précédent article, nous avions vu ensemble comment utiliser la mémoire EEPROM interne d'une carte Arduino / Genuino. Cependant, une question subsiste : comment être sûr que les données lues d'une mémoire (ou reçues d'une quelconque façon) sont justes ? Comment être sûr que celles-ci n'ont pas été altérées en chemin ? C'est justement le sujet de l'article d'aujourd'hui !

Sommaire

Bonjour à toutes et à tous !

Dans un précédent article, nous avions vu ensemble comment utiliser la mémoire EEPROM interne d'une carte Arduino / Genuino pour stocker des données utilisateur, de calibration ou autre. Cependant, il manquait un petit quelque chose que certains n'ont pas manqué de remarquer : la détection d'erreur d'écriture et de lecture.

Photographie puce EPROM UV

La puce d'une UV-EPROM amd27c512

Une mémoire EEPROM (ou tout autre type de mémoire) n'est pas infaillible. Les écritures peuvent échouer (mémoire en fin de vie) ou s'altérer avec le temps (mémoire laissée trop longtemps sans alimentation ou défectueuse). De la même façon, lors d'une communication entre deux périphériques (avec ou sans fil), des erreurs peuvent se glisser dans le flux de données reçues. Dans les deux cas de figure, on s'expose à un potentiellement gros soucis : les données lues / reçues sont différentes des données d'origine. Aie !

Se pose donc LA question : comment détecter un problème de lecture ou de transmission de données ? La réponse tient en trois mots : "Sommes de contrôle".

PS Il est plus juste de dire "une réponse", car il existe bien d'autres façons de détecter, voir même corriger une erreur de lecture ou de transmission. Le code de Hamming est un bon exemple de solution alternative.

Les sommes de contrôle

Les sommes de contrôle ont pour but de détecter des erreurs de transmission / lecture de données.

Illustration du processus de vérification par checksum

Illustration du processus de vérification par checksum

Le principe de fonctionnement des sommes de contrôle est relativement simple :

  • Avant l'écriture / envoi, on calcule une somme de contrôle à partir des données binaires.

  • On écrit / transmets ensuite les données.

  • À la lecture / réception des données, on recalcule la même somme de contrôle, mais avec les données lues / reçues cette fois-ci.

  • Si les sommes sont égales, les données sont identiques. Si les sommes sont différentes, c'est qu'il y a une erreur.

Il existe de nombreuses façons de générer une somme de contrôle. Une simple addition modulo N peut faire office de sommes de contrôle. L'important est qu'au final on doit obtenir un nombre de taille fixe qui change en fonction des données en entrée. Une toute petite modification des données en entrée doit résulter dans un changement important en sortie.

PS La qualité d'une somme de contrôle est liée à sa robustesse. Si un grand nombre de séries de données peuvent générer la même somme de contrôle, c'est qu'elle n'est pas très robuste.

En informatique, les deux algorithmes de "hashage" (génération de somme) les plus utilisés sont MD5 et SHA-2. Si vous avez déjà téléchargé un fichier sur internet, vous avez surement déjà dû voir ce genre de chose en dessous du lien de téléchargement : "md5sum 501d97ae902c40a459c5d97150018c92". Ce grand nombre hexadécimal est la somme de contrôle du fichier.

En électronique et en télécommunication, on préfère les sommes de contrôle courtes et faciles à calculer. Elles sont certes moins robustes, mais plus rapides à calculer. Les algorithmes MD5 et SHA2 sont relativement simples à mettre en oeuvre sur un PC de bureau, mais sur un microcontrôleur, une somme de contrôle de 256 bits (32 octets) n'est vraiment pas envisageable ! En radiocommunication basse consommation, un message fait entre 32 et 256 octets en général. Une somme de contrôle de 32 octets n'a donc pas sa place dans le message. Il en va de même avec les mémoires EEPROM qui font en général quelques Kilo Octets, voir moins. 32 octets dans une mémoire EEPROM de 1Ko représentent plus de 3% de la mémoire totale, ça fait beaucoup !

Nos chers ingénieurs ont donc trouvé une solution un poil moins efficace, mais beaucoup plus simple et légère : les sommes de contrôle cycliques, plus simplement appelées "CRC" ou "Checksum".

Sans entrer dans le détail mathématique, les Checksum sont tous basés sur le calcul d'un polynôme constitué de puissances de deux, exemple : x^16 + x^12 + x^5 + 1. Cela peut paraître compliqué, mais dans les faits, l'implémentation de ce genre de calcul se résume à une boucle avec un OU exclusive et un test. Vous le verrez dans le chapitre suivant, l'implémentation n'est vraiment pas compliquée.

PS Pour les amateurs de formules mathématiques, la page Wikipedia anglaise sur le sujet explique étape par étape le calcul et donne quelques exemples de polynômes standards.

PS Pour ceux qui voudraient tester leur propre implémentation, cette page permet de calculer plusieurs checksum standards et cette page explique de nombreuses "subtilités" d'implémentations de certains checksum standard, en particulier l'inversion des bits en entrée et en sortie de checksum.

Implémentation en C/C++

Dans ce chapitre, je vais vous présenter plusieurs façons relativement standard de faire un CRC.

N.B. Si vous avez besoin d'implémenter un calcul de CRC pour communiquer avec un capteur ou un module, lisez bien la documentation du constructeur de votre capteur / module ;)

Il n'existe pas d'implémentation standard unique d'un CRC.

L'aspect mathématique est le même pour tous les CRC, mais le calcul diffère en fonction des fabricants. Certains fabricants oublient même l'objectif premier d'un CRC et choisissent des implémentations complètement fantaisistes pour éviter aux concurrents de faire des modules compatibles avec leur produit (les fabricants de stations météo et d'horloges avec capteur de température adorent faire ça).

Même en restant sur une implémentation standard, la taille du CRC peut varier, le polynôme peut varier, les données en entrée peuvent être inversées (et pas juste une inversion 0 / 1, une vraie inversion bit de poids fort -> bit de poids faible), le CRC en sortie peut être inversé, voire même mixé avec une valeur fixe. La valeur de départ peut elle aussi varier et il existe même deux façons différentes d'implémenter le polynôme (avec le bit de faible toujours à 1 ou le bit de poids fort).

Bref, en théorie comme en pratique, il existe des centaines de façons possibles de calculer un CRC.

CRC-16 ANSI / IBM

Il s'agit d'un des deux CRC 16 bits les plus utilisés en électronique.

Il est un poil compliqué à cause de l'inversion de bits. La version CCITT présentée plus bas est plus simple. Si vous avez le choix, utiliser la version du chapitre suivant.

Caractéristiques techniques (pour les curieux) :

  • CRC 16 bits

  • Polynôme 0x8005

  • Valeur initiale 0x0000

  • Inversion de l'entrée et de la sortie

  • Pas de XOR final

Le code :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <stdint.h>


uint16_t bit_reflect(uint16_t data, unsigned char nbits) {
    uint16_t output = 0;
    for (unsigned char i = 0; i < nbits; ++i) {
        if (data & 1) 
            output |= 1 << ((nbits - 1) - i);
        data >>= 1;
    }
    return output;
}


uint16_t crc16_ibm(char* data, unsigned int data_len) {
    uint16_t crc = 0;

    if (data_len == 0)
        return 0;

    for (unsigned int i = 0; i < data_len; ++i) {
        uint16_t dbyte = bit_reflect(data[i], 8);
        crc ^= dbyte << 8;
        
        for (unsigned char j = 0; j < 8; ++j) {
            uint16_t mix = crc & 0x8000;
            crc = (crc << 1);
            if (mix)
                crc = crc ^ 0x8005;
        }
    }

    return bit_reflect(crc, 16);
}

L'extrait de code ci-dessus est disponible en téléchargement sur cette page.

Utilisation :

1
uint16_t résultat = crc16_ibm(données, taille_des_données);

La valeur de retour est un nombre entier sur 16 bits non signé (uint16_t).

CRC-16 CCITT (0xFFFF)

Il s'agit d'un des deux CRC 16 bits les plus utilisés en électronique.

C'est le calcul de CRC que j'utilise dans mes programmes.

Caractéristiques techniques :

  • CRC 16 bits

  • Polynôme 0x1021

  • Valeur initiale 0xFFFF

  • Pas d'inversion d'entrée ou de sortie

  • Pas de XOR final

Le code :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <stdint.h>


uint16_t crc16_ccitt(char* data, unsigned int data_len) {
    uint16_t crc = 0xFFFF;

    if (data_len == 0)
        return 0;

    for (unsigned int i = 0; i < data_len; ++i) {
        uint16_t dbyte = data[i];
        crc ^= dbyte << 8;
        
        for (unsigned char j = 0; j < 8; ++j) {
            uint16_t mix = crc & 0x8000;
            crc = (crc << 1);
            if (mix)
                crc = crc ^ 0x1021;
        }
    }

    return crc;
}

L'extrait de code ci-dessus est disponible en téléchargement sur cette page.

Utilisation :

1
uint16_t résultat = crc16_ccitt(données, taille_des_données);

La valeur de retour est un nombre entier sur 16 bits non signé (uint16_t).

CRC-32 (Ethernet)

Un grand classique de l'informatique !

Ce CRC est utilisé partout en communication réseau. Son utilisation la plus connue est dans les trames Ethernet, mais il est aussi utilisé pour les communications SATA (disques durs), les archives compressées (Zip, Gzip, Bzip), certains formats d'encodage vidéos (Mpeg), etc.

Caractéristiques techniques :

  • CRC 32 bits

  • Polynôme 0x04C11DB7

  • Valeur initiale 0xFFFFFFFF

  • Inversion de l'entrée et de la sortie

  • XOR final 0xFFFFFFFF

Le code :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <stdint.h>


uint32_t bit_reflect(uint32_t data, unsigned char nbits) {
    uint32_t output = 0;
    for (unsigned char i = 0; i < nbits; ++i) {
        if (data & 1) 
            output |= 1 << ((nbits - 1) - i);
        data >>= 1;
    }
    return output;
}


uint32_t crc32_ethernet(char* data, unsigned int data_len) {
    uint32_t crc = 0xFFFFFFFF;

    if (data_len == 0)
        return 0;

    for (unsigned int i = 0; i < data_len; ++i) {
        uint32_t dbyte = bit_reflect(data[i], 8);
        crc ^= dbyte << 24;
        
        for (unsigned char j = 0; j < 8; ++j) {
            uint32_t mix = crc & 0x80000000;
            crc = (crc << 1);
            if (mix)
                crc = crc ^ 0x04C11DB7;
        }
    }

    return bit_reflect(crc, 32) ^ 0xFFFFFFFF;
}

L'extrait de code ci-dessus est disponible en téléchargement sur cette page.

Utilisation :

1
uint32_t résultat = crc32_ethernet(données, taille_des_données);

La valeur de retour est un nombre entier sur 32 bits non signé (uint32_t).

Bonus : Implémentation générique (base des implémentations précédentes)

En bonus, voici une implémentation générique, capable de calculer à peut près n'importe quel CRC standard.

Il suffit de lui passer en paramètres les informations concernant le CRC désiré et la fonction fait le calcul de polynôme.

Le code (avec un exemple d'utilisation pour PC) :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <stdint.h>


typedef uint32_t CRC; // Cette déclaration de type peut être ajustée pour supporter des CRC 64 bits


CRC bit_reflect(CRC data, unsigned char nbits) {
    CRC output = 0;
    for (unsigned char i = 0; i < nbits; ++i) {
        if (data & 1) 
            output |= 1 << ((nbits - 1) - i);
        data >>= 1;
    }
    return output;
}


CRC crc_generic(char* data, unsigned int data_len, 
                unsigned char nbits, CRC polynôme, CRC initial_value,
                char reflect_input, char reflect_output, CRC final_xor_value) {

    CRC bitmask = (1ULL << nbits) - 1;
    CRC msb_mask = 1 << (nbits - 1);
    CRC crc = initial_value;

    if (data_len == 0)
        return 0;

    for (unsigned int i = 0; i < data_len; ++i) {
        CRC dbyte = data[i];

        if (reflect_input)
            dbyte = bit_reflect(dbyte, 8);
        
        crc ^= dbyte << (nbits - 8);
        
        for (unsigned char j = 0; j < 8; ++j) {
            CRC mix = crc & msb_mask;
            crc = ((crc << 1) & bitmask);
            if (mix)
                crc = crc ^ polynôme;
        }
    }
    
    if (reflect_output)
        crc = bit_reflect(crc, nbits);

    return (crc ^ final_xor_value) & bitmask;
}


// ----- Exemple pour PC


#include <stdio.h>

int main(void) {
    
    printf("CRC-16: %lX\n", crc_generic("123456789", 9, 16, 0x8005, 0, 1, 1, 0)); // 0xBB3D
    printf("CRC-16 CCITT (0xFFFF): %lX\n", crc_generic("123456789", 9, 16, 0x1021, 0xffff, 0, 0, 0)); // 0x29B1
    printf("CRC-16 CCITT (0x1D0F): %lX\n", crc_generic("123456789", 9, 16, 0x1021, 0x1D0F, 0, 0, 0)); // 0xE5CC
    printf("CRC-32: %lX\n", crc_generic("123456789", 9, 32, 0x04C11DB7, 0xFFFFFFFF, 1, 1, 0xFFFFFFFF)); // 0xCBF43926
    
    return 0;
}

L'extrait de code ci-dessus est disponible en téléchargement sur cette page.

N.B. Ce code a servi de base pour les codes précédents ;)

Bonus : mise en oeuvre avec la mémoire EEPROM d'une carte Arduino / Genuino

Dans mon précédent article sur les mémoires EEPROM, je vous avais présenté un programme d'exemple supportant diverses fonctionnalités, comme la détection de première utilisation et la mise à jour de la structure de données.

Je vous propose donc aujourd'hui une version modifiée intégrant la vérification de checksum, en plus de tout le reste.

Le code complet avec commentaires :

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
/**
 * Exemple d'utilisation de structure avec EEPROM.put().
 * Variante avec versionnage et détection de première utilisation.
 * Utilise une somme de contrôle 16 bits pour détecter les erreurs de lecture.
 */

#include <EEPROM.h>

/** Le nombre magique et le numéro de version actuelle */
static const unsigned long STRUCT_MAGIC = 123456789;
static const byte STRUCT_VERSION = 2;

/** La structure qui contient les données */
struct MaStructure {
  unsigned long magic;
  byte struct_version;
  uint16_t checksum;

  int valeur_1; // Depuis la struct_version = 0
  float valeur_2; // Depuis la struct_version = 1
  char valeur_3[16]; // Depuis la struct_version = 2
};

/** L'instance de la structure, globale car utilisé dans plusieurs endroits du programme */
MaStructure ms;

void setup() {
  Serial.begin(9600);

  // Charge le contenu de la mémoire
  chargeEEPROM();

  // Affiche les données dans la structure
  Serial.print("Valeur 1 = ");
  Serial.println(ms.valeur_1);

  Serial.print("Valeur 2 = ");
  Serial.println(ms.valeur_2);

  Serial.print("Valeur 3 = ");
  Serial.println(ms.valeur_3);
}

void loop() {
} 

/** Sauvegarde en mémoire EEPROM le contenu actuel de la structure */
void sauvegardeEEPROM() {
  // Met à jour le nombre magic, le numéro de version et la checksum avant l'écriture
  ms.magic = STRUCT_MAGIC;
  ms.struct_version =  STRUCT_VERSION;
  ms.checksum = 0; // Calcul la checksum sans prendre en compte la valeur actuelle
  ms.checksum = crc16_ccitt((byte*) &ms, sizeof(ms));
  EEPROM.put(0, ms);
}

/** Charge le contenu de la mémoire EEPROM dans la structure */
void chargeEEPROM() {

  // Lit la mémoire EEPROM
  EEPROM.get(0, ms);
  
  // Calcul de la checksum
  uint16_t current_checksum = ms.checksum;
  ms.checksum = 0; // Calcul la checksum sans prendre en compte la valeur actuelle
  uint16_t real_checksum = crc16_ccitt((byte*) &ms, sizeof(ms));
  
  // Détection d'une mémoire non initialisée ou corrompue
  byte erreur = ms.magic != STRUCT_MAGIC || current_checksum != real_checksum;
  
  // Valeurs par défaut struct_version == 0
  if (erreur) {

    // Valeurs par défaut pour les variables de la version 0
    ms.valeur_1 = 42;
  }
  
  // Valeurs par défaut struct_version == 1
  if (ms.struct_version < 1 || erreur) {

    // Valeurs par défaut pour les variables de la version 1
    ms.valeur_2 = 13.37;
  }

  // Valeurs par défaut pour struct_version == 2
  if (ms.struct_version < 2 || erreur) {

    // Valeurs par défaut pour les variables de la version 2
    strcpy(ms.valeur_3, "Hello World!");
  }

  // Sauvegarde les nouvelles données
  sauvegardeEEPROM();
}

/** Fonction de calcul d'une somme de contrôle CRC-16 CCITT 0xFFFF */
uint16_t crc16_ccitt(unsigned char* data, unsigned int data_len) {
  uint16_t crc = 0xFFFF;

  if (data_len == 0)
    return 0;

  for (unsigned int i = 0; i < data_len; ++i) {
    uint16_t dbyte = data[i];
    crc ^= dbyte << 8;

    for (unsigned char j = 0; j < 8; ++j) {
      uint16_t mix = crc & 0x8000;
      crc = (crc << 1);
      if (mix)
        crc = crc ^ 0x1021;
    }
  }

  return crc;
}

L'extrait de code ci-dessus est disponible en téléchargement sur cette page (le lien de téléchargement en .zip contient le projet Arduino prêt à l'emploi).

Conclusion

Ce tutoriel / cours est désormais terminé.

Si ce tutoriel / cours vous a plu, n'hésitez pas à le commenter sur le forum, à le diffuser sur les réseaux sociaux et à soutenir le site si cela vous fait plaisir.