Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Calcul de checksum


Sujet :

Algorithmes et structures de données

  1. #1
    Futur Membre du Club
    Calcul de checksum
    Bonjour à tous,

    voilà je cherche comment calculer un checksum d'une trame d'octet du type:

    11 FF C5 00 0E 95 00 28 01 05 98 22 81 00 0E F7 FC FD

    dont le checksum devrait être : F9 C4

    Pour simple indication, on me dit: "somme de la trame complémentée + 1"

    Mais mes cours de réseaux sont bien loin, et j'ai beau essayer plusieurs solutions je ne retombe pas sur mes pattes...

    Si quelqu'un à une idée, çà m'enlèverai une sacré épine du pied =)

    Par avance: Merci !

    ps: pour info le langage cible est le C# avec un tableau de byte[] en entrée...

  2. #2
    Inactif  
    Moi, je trouve F921 en checksum... Ce qui me fait dire qu'il doit te manquer un octet, ou qu'il y a un problème de propagation de retenue qui n'est pas indiqué dans ta "formule". En pratique, j'ai l'impression plutôt que tu as des octets en trop... Il y a une différence de 0xA3 en trop pour retomber sur ses pattes.

    Mais la formule normale, c'est "NOT ( Somme(i=1..n)(Trame[i] ) + 1", le "not" étant le complément à un (ou négation binaire).

    Peux-tu nous dire de quel protocole exactement il s'agit ? Si c'est un protocole "connu", ça aidera pas mal à trouver le problème.
    Mac LAK.
    ___________________________________________________
    Ne prenez pas la vie trop au sérieux, de toutes façons, vous n'en sortirez pas vivant.

    Sources et composants Delphi sur mon site, L'antre du Lak.
    Pas de question technique par MP : posez-la dans un nouveau sujet, sur le forum adéquat.

    Rejoignez-nous sur : ► Serveur de fichiers [NAS] ► Le Tableau de bord projets ► Le groupe de travail ICMO

  3. #3
    Rédacteur

    Citation Envoyé par Mac LAK Voir le message
    Moi, je trouve F921 en checksum...
    pareil.

    Code java :Sélectionner tout -Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    int[] data ={
    	0x11 ,0xFF ,0xC5 ,0x00 ,0x0E ,0x95 ,0x00 ,0x28 ,0x01 ,0x05 ,0x98 ,0x22 ,0x81 ,0x00 ,0x0E ,0xF7 ,0xFC ,0xFD
    };
     
    int checksum=0;
    for(int i : data) checksum += i;
    checksum = (~checksum + 1) & 0xFFFF; 
     
    System.out.println(Integer.toHexString(checksum));
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  4. #4
    Membre expert
    le principe du checksum repose sur une division polynomiale

    le resultat de ton checksum va dépendre du polynome utilisé...

    http://www.cs.jhu.edu/~scheideler/co...4_S02/CRC.html
    bazar: http://www.improetcompagnie.com/publ...ctacles-6.html

    BÉPO la disposition de clavier francophone, ergonomique et libre: http://bepo.fr/wiki/Accueil

    Emacs Wiki: http://www.emacswiki.org/

    En attente de ce que produira: http://www.pushmid.com

  5. #5
    Inactif  
    Citation Envoyé par jabbounet Voir le message
    le principe du checksum repose sur une division polynomiale

    le resultat de ton checksum va dépendre du polynome utilisé...

    http://www.cs.jhu.edu/~scheideler/co...4_S02/CRC.html
    C'est vrai pour un CRC16, mais là, c'est une simple somme tout comme les checksums UDP et IP par exemple. Il n'y a pas de polynôme, mais plutôt des règles d'arithmétique binaire à connaître à l'avance.

    Notamment, il peut manquer des octets dans le tableau, ou l'algorithme peut sommer des octets en dehors de la trame utile : UDP, par exemple, ajoute les deux adresses IP (qui ne font pas partie de la zone UDP de la trame !!!) à son checksum.
    Mac LAK.
    ___________________________________________________
    Ne prenez pas la vie trop au sérieux, de toutes façons, vous n'en sortirez pas vivant.

    Sources et composants Delphi sur mon site, L'antre du Lak.
    Pas de question technique par MP : posez-la dans un nouveau sujet, sur le forum adéquat.

    Rejoignez-nous sur : ► Serveur de fichiers [NAS] ► Le Tableau de bord projets ► Le groupe de travail ICMO

  6. #6
    Futur Membre du Club
    Bonjour à tous et tout d'abord merci pour vos réponses.

    Le type de protocole utilisé, est un protocole propriétaire, et donc il ne s'agit pas de protocole "connu".

    Je vais vérifier de mon coté s'il ne s'agit tout simplement pas d'une erreur, dans l'exemple énoncé.

    Je vous tiens au courant...

  7. #7
    Membre expert
    Citation Envoyé par Mac LAK Voir le message
    C'est vrai pour un CRC16, mais là, c'est une simple somme tout comme les checksums UDP et IP par exemple. Il n'y a pas de polynôme, mais plutôt des règles d'arithmétique binaire à connaître à l'avance.

    Notamment, il peut manquer des octets dans le tableau, ou l'algorithme peut sommer des octets en dehors de la trame utile : UDP, par exemple, ajoute les deux adresses IP (qui ne font pas partie de la zone UDP de la trame !!!) à son checksum.
    ce n'est effectivement pas un polynome pour TCP/UDP,
    Mais on retrouve des polynômes dans pas mal d'endroit ailleurs (dans les couches plus basse) quelque soit la méthode il y'a toujours un concept mathématique derrière.




    En divergeant un peu
    quelques liens intéressant pour ceux qui veulent se cultiver sur le sujet
    http://ram-0000.developpez.com/tutor...e/?page=page_6
    http://en.wikipedia.org/wiki/Cyclic_...dundancy_check
    http://www.ross.net/crc/download/crc_v3.txt

    Et une source sur md4/5....
    http://www.faqs.org/rfcs/rfc1320.html
    http://www.faqs.org/rfcs/rfc1321.html

    http://www.opensource.apple.com/sour...bsum/sum-md5.c
    bazar: http://www.improetcompagnie.com/publ...ctacles-6.html

    BÉPO la disposition de clavier francophone, ergonomique et libre: http://bepo.fr/wiki/Accueil

    Emacs Wiki: http://www.emacswiki.org/

    En attente de ce que produira: http://www.pushmid.com

  8. #8
    Rédacteur

    Citation Envoyé par jabbounet Voir le message
    ce n'est effectivement pas un polynome pour TCP/UDP,
    Mais on le retrouve des polynômes dans pas mal d'endroit ailleurs (dans les couches plus basse) quelque soit la méthode il y'a toujours un concept mathématique derrière.
    J'ai testé la plupart des chercksum 16-bits usuels, et aucun ne se rapproche plus du résultat que celui qu'on a donné.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  9. #9
    Inactif  
    Je reste vraiment persuadé qu'il manque des données, ou qu'il y en a trop...

    L'énoncé de la méthode est clair, c'est proche du checksum BIOS (aussi appelé "sum16"), et le fait que l'on trouve une valeur très proche en l'appliquant plaide encore en la faveur de cet algo : avec un CRC, on aurait eu une dispersion bien plus élevée et on serait tombés sur un résultat très éloigné.
    Mac LAK.
    ___________________________________________________
    Ne prenez pas la vie trop au sérieux, de toutes façons, vous n'en sortirez pas vivant.

    Sources et composants Delphi sur mon site, L'antre du Lak.
    Pas de question technique par MP : posez-la dans un nouveau sujet, sur le forum adéquat.

    Rejoignez-nous sur : ► Serveur de fichiers [NAS] ► Le Tableau de bord projets ► Le groupe de travail ICMO

  10. #10
    Rédacteur

    Citation Envoyé par Mac LAK Voir le message
    L'énoncé de la méthode est clair, c'est proche du checksum BIOS (aussi appelé "sum16")
    Hum... y a un complément a 2 dans le "sum16" ?
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  11. #11
    Inactif  
    Citation Envoyé par pseudocode Voir le message
    Hum... y a un complément a 2 dans le "sum16" ?
    Tacitement, vu que la somme des données et du checksum doit être nulle... Donc, le checksum doit être le complément à deux de la somme afin d'arriver à zéro, bien entendu.



    Pour ceux qui ne comprennent pas de quoi on parle : Le complément à deux (égal au complément à un [ou NOT binaire] augmenté de un) est, justement, l'opposé binaire d'un nombre quelconque.
    Il y a propagation d'un bit au passage lorsque l'on additionne les deux, mais une fois remis à la plage d'origine sur N bits (16 ici), on obtient bien zéro.
    Mac LAK.
    ___________________________________________________
    Ne prenez pas la vie trop au sérieux, de toutes façons, vous n'en sortirez pas vivant.

    Sources et composants Delphi sur mon site, L'antre du Lak.
    Pas de question technique par MP : posez-la dans un nouveau sujet, sur le forum adéquat.

    Rejoignez-nous sur : ► Serveur de fichiers [NAS] ► Le Tableau de bord projets ► Le groupe de travail ICMO

  12. #12
    Rédacteur

    Citation Envoyé par Mac LAK Voir le message
    Tacitement, vu que la somme des données et du checksum doit être nulle...
    Vu comme ca effectivement.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  13. #13
    Futur Membre du Club
    Effectivement, il y avait tout simplement une erreur dans la trame d'exemple qui nous a été fournie... (merci le client ! °\o/°)

    L'algorithme a appliquer en C# est bien:

    Code :Sélectionner tout -Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
     
            public static byte[] CalculateCS(byte[] data)
            {
                  short cs = 0; 
                  foreach (byte b in data)  cs += b; //Somme des octets
                  cs = (short)((~cs) + 1); //Complément à 2 
                  return System.BitConverter.GetBytes(cs); 
            }


    Merci à vous en tout cas !

  14. #14
    Inactif  
    Citation Envoyé par Carlito78 Voir le message
    Effectivement, il y avait tout simplement une erreur dans la trame d'exemple qui nous a été fournie... (merci le client ! °\o/°)
    Pendons le dernier client avec les tripes du dernier commercial !!
    De rien, bonne continuation et merci pour le !
    Mac LAK.
    ___________________________________________________
    Ne prenez pas la vie trop au sérieux, de toutes façons, vous n'en sortirez pas vivant.

    Sources et composants Delphi sur mon site, L'antre du Lak.
    Pas de question technique par MP : posez-la dans un nouveau sujet, sur le forum adéquat.

    Rejoignez-nous sur : ► Serveur de fichiers [NAS] ► Le Tableau de bord projets ► Le groupe de travail ICMO