Checksum simple sur 32 bits ? Fermé

Question

Checksum simple sur 32 bits ?

Bonjour,

Je suis à la recherche d'un algorithme simple pour générer un checksum de 32 bits. Pourquoi 32 bits ? Parce que je travaille sur une puce dont les données sont en 32 bits, je stockerais donc ce code dans une seule variable type INT. Et je n'ai pas besoin de sécurité extrême, donc plus de 32 bits, ca me parait surdimensionné.

Le but est simplement de vérifier que je lis correctement une mémoire externe (Flash) embarquée. Lors de la génération des fichiers à flasher, je calculerais ce checksum, l'écrirais en flash avec les données, puis le recalculerais lors de la lecture.

Il n'y a pas vraiment de sécurité en jeu, il s'agit plutôt d'un contrôle de bon fonctionnement du programme et du hardware.

J'ai cherché un peu, mais je n'ai trouvé que des codes style MD5, donnant 128 bits ou plus. De plus, j'ai des contraintes de temps réel, donc j'aimerais un calcul (relativement) simple.

Evidemment, il y a la solution d'une somme bête et méchante, mais j'aimerais si possible un algorithme un peu plus évolué, qui pourrait m'assurer un peu plus qu'en cas  d'égalité des checksum, les données de départs sont bien identiques. Notamment, si cet algorithme pouvait tenir compte de l'emplacement des données (la chaine "abc" générerait un code différent de la chaine "bca"), ca serait un plus considérable.

Merci :)

blux · Answer

Salut,

un CRC32 devrait te suffire, non ?

control

sebsauvage · Answer

La CRC32 est assez répandue.
On trouve assez facilement le code sur internet (chercher CRC32 sur google)

Note qu'une CRC 32 est bien pour vérifier l'intégrité des donnés, mais pas assez fiable pour une authentification (pour laquelle il est indispensable de passer par MD5 ou SHA1).

kilian · Answer

Salut,

Regarde par là:
https://en.wikipedia.org/wiki/List_of_checksum_algorithms

EDIT: Désolé, avait pas vu les messages des autres.

Richard · Answer

Le CRC-32 permet de vérifier une donnée 32 bits, ca n'est pas mon but (ou alors ai-je mail compris son application)

Je précise :

Je stocke en Flash externe des paquets de données, environ 1500 valeurs 32 bits, pour fixer les idées. je voudrais associer un checksum à chaque paquet, pas à chaque valeur de 32 bit (ca pendrait trop de temps et trop d'espace mémoire en flash). La taille des paquets sera fixe (x valeurs 32 bits, j'ia cité 1500 pour exemple au dessus, ca n'est pas totalement fixé encore dans mon programme).

Mon programme génère un offset pour la lecture en flash. Il se rend à cet offset, et lit x valeurs successives. L'idée est donc de pouvoir vérifier deux choses :
* Que j'aie bien récupéré le bon paquet : ni celui d'a coté, ni un mélange entre deux paquets successif. Ca revient à détecter une erreur dans la génération de mon offset.
* Que les données ne sont pas corrompues : par un parasite sur le bus, par une mauvaise écriture à la base, que sais-je...

Je souhaite donc générer à partir de x valeurs 32 bits une (x+1) ième valeur, 32 bits également.

Je viens de lire une astuce, qui consiste à calculer un checksum genre MD5, et à n'en garder que 32 bits sur les 128. Mais ca me fera faire des calculs pour rien, et comme je suis tendu niveau ressources processeurs...

Richard · Answer

Il semblerait en fait que ce que je cherche soit une fonction de hachage (hash function), et non pas un checksum.

Je fouille Wikipedia, mais rien en dessous de 128 bits, apparemment... :(
https://en.wikipedia.org/wiki/Cryptographic_hash_function

sebsauvage · Answer

CRC32 est une fonction de hashage, mais elle ne doit pas être utilisée à des fins cryptographiques.

Richard · Answer

Je comprend pas comment un CRC peut être calculé sur 1500 valeurs 32 bits, alors que les définitions que j'ai (ici ou sur wikipedia) parlent de division bit à bit. De plus, la notion de division m'ennuie, c'est pas l'opération la plus rapide...

J'ai trouvé ca par contre, qui me semble pas mal : Adler-32 

https://en.wikipedia.org/wiki/Adler-32

sebsauvage · Answer

Tu te prend la tête: il y a des librairies CRC32 prêtes à l'emploi dans pratiquement tous les langages.
Tu peux leur passer une chaîne de taille arbitraire, en une fois ou plusieurs fois sans problème.

Google est ton ami.

En C: http://www.netrino.com/Connecting/2000-01/crc.zip
En C++: https://www.boost.org/doc/libs/1_72_0/libs/crc/crc.html

etc.

Richard · Answer

En effet, je me prend la tête. Mais c'est pas pour rien, je bosse sur de l'embarqué, et mes contraintes temps réel (et d'espace mémoire) sont importantes. Je ne peux pas me permettre de laisser partir des ressources dans des tâches que je ne maitrise pas. Vu le fonctionnement du CRC, avec de la division, il y a fort à parier que ca prendra un temps fou.

En plus, mais ca c'est plus personnel et subjectif, j'aime comprendre ce que je code, donc j'aime bien faire moi-même mes fonctions. Au moins la 1ere fois, ensuite evidemment si y'a moyen de gagner du temps de développement ou du temps processeur avec des packages déjà près... Je sais, oui, que c'est se prendre la tête. mais c'est assumé :)

Sinon, pour précision, je code en C, avec parfois des bouts d'assembleur.

sebsauvage · Answer

Je t'encourage à regarder les sources avant de les jeter: Il n'y a pas de division utilisée, mais des décalage de bits.

En l'occurence, la source C du CRC dont j'ai donné la référence ne fait que 200 lignes.

Utilisateur anonyme · Answer

Bonjour,

En 84 lorsque j'ai commencé à codé en assembleur, les contraintes d'espace et de temps était
toujours les priorités. Ceci dit, j'ai personnellement codé tout un "BIOS" pour le processeur
MC6809 et il y avait une partie communication RS232.

Or j'ai codé tout une série de commande ainsi qu'un protocol de communication sur 8 bits. Ceci dit, je trouve que votre dileme ressemble un peu à ces préoccupations de mon passé.

Suggestion :

Comme "checksum" ( somme de vérification ) et ce même sur 32 bits, vous pouvez coder
16 bits pour l'offset, et 16 bits pour le data. Vous pourriez aussi coder 4 conditions sur huit
bits. Bien qu'une somme soit banal, elle n'en demeure pas moins efficace. En assembleur
c'est le bit d'overflow qui vous fournira le (x+1) ième valeur.

Penser toujours en fonction du fait que en regroupant le binaire par 4 bits, vous passer du binaire
à l'hexadécimal instantannément !

32 bits

1010 1010 1010 1010 1010 1010 1010 1010 (2)
A A A A A A A A (16)

si vous avez à construire un [ checksum ] de vérification, commencer par quelque chose de simple.
la rigeur de l'assembleur rendra la fonction efficace. Enfin ce sont là quelques idées.

Cordialement

Lupin

Checksum simple sur 32 bits ?

11 réponses

Discussions similaires