Decodage de données binaires [Résolu]

[Darki03]

Bonjour, à tous !

Mes connaissances en programmation se limitant à ce que j'ai pu apprendre lors de ma scolarité, j'espère ne choquer personne avec mes questions ^^ !. J'éspère aussi poster au bon endroit !

Voila je vous explique mon problème, j'ai écrit un petit bout de code maladroit qui mélange C et C++ (cela doit être affreux pour un programmeur confirmé mais le résultat est fonctionnel) qui a mon gout prend beaucoup de temps pour s'exécuter.

Le but de ce programme est de lire un fichier binaire qui contient un enregistrement de la communication numérique (ARINC) d'un équipement aéronautique.

Pour lire le fichier binaire pas de soucis cela se fait assez rapidement, le problème se situe au niveau du décodage des trames ARINC enregistrées, opération qui prend le plus de temps dans mon code.

Le fichier binaire contient en fait des succession de paquets de 9 octets : 5 octets contenant une info temporelle et 4 octets contenant le mot ARINC reçu.

Pour ce faire je lis l'ensemble des paquets de 9 octets et je les stockent un à un dans une liste chainée que je parcours ensuite pour les décoder, le résultats du décodage est stocké a son tour dans une structure qui est elle même stockée dans une autre liste chainée de structure ().

Le decodage consiste pour les 4 octets du mot ARINC a decomposer les 32 bits en différente parties pour obtenir les informations qu'il contient.Pour ce qui est de l'info temporelle les 5 octects contiennent sous forme binaire Heures;Minutes;Secondes et Microsecondes (8 bits pour les H, 6 pour les minutes, 6 pour les secondes et 20 pour les µsecondes)

Pour l'instant je me débrouille avec des divisions et des soustractions pour extraire les parties désirées du mot ou de l'info temporelle. De plus j'ai besoins d'afficher l'info temporelle sous la forme seconde.µsecondes ( H*3600+60*M+S+(µS/1000000)), ce calcul doit etre gourmand en temps je pense.

Ce projet étant lié a mon travail, je ne peut pas tout le temps rentrer dans le détail. Ma question se limite au problème de temps de calcul pour décoder les mots, si quelqu'un à une idée je lui en serait très reconnaissant.

Je peut donner plus d'infos dans un message privé (surtout que tout cela doit vous paraitre brouillon mais j'ai du mal à tout expliquer de manière succincte) et même vous fournir mon code si cela peut aider.

D'avance merci .

[ram-0000]

Tu stockes tes enregistrements bruts de 9 octets dans une liste chainée ==> OK

Par contre, je ne vois pas l'intérêt de stocker le résultat du décodage dans une autre liste chainée.

Cela t'oblige à décoder tous tes enregistrements bruts (effectivement, si tu en as beaucoup, cela peut prendre du temps) et surtout à stocker en mémoire une intreprétation de ce que tu as déjà. De plus, même si tu n'est pas intéressé par les 100 premiers (ou derniers, peut importe) enregistrements, tu calcule quand même leur représentation et tu stockes cette représentation en mémoire, quel gachis (je trouve).

Pourquoi ne pas calculer l'interprétation de ces résultats bruts que lorsque tu en as réellement besoin et ce n'est même pas la peine de la sauvegarder car d'après ce que tu montres, le temps de recalcul semble très rapide. Dans le calcul que tu as décrit, il n'y a rien de long (sauf si c'est répété quelques milliers de fois pour rien )

[Darki03]

En fait je n'ai pas tout dit ! je stocke les informations décodées dans une liste car d'autres opérations sont réalisées ensuite ! en effet je dois faire des tests sur les infos décodées, par exemple pour l'ARINC chaque donnée est identifiée par un numéro de label (en octal sur 8 bits) et une transmission est une succession de labels qui doivent arriver dans un certain ordre et je teste cet ordre pour voire si on a pas perdus des billes en cours de route !. Au final je crée aussi un fichier csv qui contient les infos décodées, ce fichier n'est ni plus ni moins que les élément de ma liste chainée mis bout a bout (et donc dans l'ordre de récéption).

Je me sert aussi de la STL pour avoir des outil de comparaison entre listes pour faire les tests.

Certes le calcul cité ne doit pas être long mais pour certain enregistrements le nombre de mots reçu est important, par exemple pour 5 minutes on peut atteindre 900000 mots !

J'ai aussi essayé la méthode lecture->décodage->stockage dans une même boucle mais le résultats est identique au niveau timing .

[Nogane]

Bonsoir,
La lecture du fichier peut être longue si tu fait des lectures successive de 9 octets par 9 octets, sans buffer.
Si c'est ce que tu fait, essai avec un filebuf, sinon ben j'ai pas d'autre idée...

[Darki03]

La lecture du fichier est deja "bufferisée" et est deja très rapide ! c'est l'enchainement des décodages qui est la plus longue (peut etre n'existe t il pas de solution )

[3DArchi]

Bonjour,
As-tu fais un bench pour voir exactement quelles étaient les étapes les plus gourmandes ? Sinon toute recherche d'optimisation peut te faire aller dans des directions peu rentables ou contre-productives...
Dans ce que je comprend de ton exposé :
1/ Lecture du fichier: OK
2/ Pour tout mes enregistrement :
2.1 Decoder Enregistrement
2.1.1 Decoder Temps
2.1.2 Decoder Mot
2.2 Ajouter à la liste des Enregistrements décodées.

Qu'est-ce qui est gourmand : 2.1.1, 2.1.2 ou 2.2 ou tous ?

Envoyé par Darki03

Pour l'instant je me débrouille avec des divisions et des soustractions pour extraire les parties désirées du mot ou de l'info temporelle.

Des masques et des décalages ?

Envoyé par Darki03

De plus j'ai besoins d'afficher l'info temporelle sous la forme seconde.µsecondes ( H*3600+60*M+S+(µS/1000000)), ce calcul doit etre gourmand en temps je pense.

Le calcul n'est pas forcément ce qui te prendra plus le temps. La question peut plutôt se poser en ces termes : A l'affichage, tu ne vas probablement afficher qu'un faible nombre d'enregistrement sur l'écran (le nombre de ligne d'un écran étant limité). Peut-être ne faut-il faire cette transformation qu'à ce moment (d'autant si tu as un composant d'affichage 'intelligent' type liste virtuelle).

[Darki03]

Envoyé par 3DArchi

Bonjour,
As-tu fais un bench pour voir exactement quelles étaient les étapes les plus gourmandes ? Sinon toute recherche d'optimisation peut te faire aller dans des directions peu rentables ou contre-productives...
Dans ce que je comprend de ton exposé :
1/ Lecture du fichier: OK
2/ Pour tout mes enregistrement :
2.1 Decoder Enregistrement
2.1.1 Decoder Temps
2.1.2 Decoder Mot
2.2 Ajouter à la liste des Enregistrements décodées.

Qu'est-ce qui est gourmand : 2.1.1, 2.1.2 ou 2.2 ou tous ?

En fait je ne suis pas rentré dans le détail de la boucle de décodage, j'ai juste constaté que c'était l'opération la plus longue de mon programme.

Envoyé par 3DArchi

Des masques et des décalages ?

Des décalages, par exemple pour le calcul des minutes et des secondes qui sont codées sur 6 bits et donc deux octets:
Les 6 bits de poids fort de l'o1 représentent les minutes, les deux bits de poids faible de l'o1 et les 4 bits de poids fort de l'o2 représentent les secondes.

Les calcul est le suivant:
minutes=o1>>2;
secondes=o2>>4;
secondes=secondes+(o1-4*minutes)*16;

Envoyé par 3DArchi

Le calcul n'est pas forcément ce qui te prendra plus le temps. La question peut plutôt se poser en ces termes : A l'affichage, tu ne vas probablement afficher qu'un faible nombre d'enregistrement sur l'écran (le nombre de ligne d'un écran étant limité). Peut-être ne faut-il faire cette transformation qu'à ce moment (d'autant si tu as un composant d'affichage 'intelligent' type liste virtuelle).

En fait je n'affiche rien à l'écran, tout les résultats sont inscrits dans un fichier texte en sortie de programme (1 ligne par mot et données séparées par un ; ). De plus je construit aussi un petit fichier rapport qui contient des infos sur le décodage (nottament la liste des labels érronées).

[3DArchi]

Envoyé par Darki03

En fait je ne suis pas rentré dans le détail de la boucle de décodage, j'ai juste constaté que c'était l'opération la plus longue de mon programme.

Peux-tu poster juste ce bout de code ?

[Darki03]

A priori pas de soucis pour présenter cette partie de mon code (voir en piece jointe, attention les yeux ^^ !)

Pardonnez aussi mon impolitesse mais j'ai oubliè de vous remercier pour vos réponses et votre réactivité< !

[3DArchi]

La première remarque qui me saute aux yeux - l'impact en perf n'est peut-être pas significatif mais.. - : pourquoi allouer sur le tas x et word et non pas les définir sur la pile ? A moins qu'il n'y a récursion ou que info soit très très grosse (et à ce moment que pour x), je ne vois pas l'intérêt.
Peux-tu fournir la définition de info ?

[Darki03]

Voici la structure info:

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
typedef struct 
{
        int label; 
        int parite;
		int sec;
		int misec;
		int sdi;
		int ssm;
		bool test_par;
		string binaire;
		int error;
		int emit;
		int emit1;
} info;

[3DArchi]

puiss(256,2) == 256*256 ?

[Darki03]

Envoyé par 3DArchi

puiss(256,2) == 256*256 ?

Oui, de meme que puiss(256,1)= 256 >< (je l'avait pas vu celle la Oo !)

[3DArchi]

Tes variables ont des noms affreux
En revanche, tu utilises la STL ; ca fera - de question à se poser.

Passons au cœur des choses :
En préambule, je ne te garantie pas que tout va améliorer la chose, mais à tester pour voir les impacts.
1/ Enlever les allocations dynamiques :

Code :

1
2
3
4
5
6
 
for(list<mot>::iterator k(read.begin()); k!= read.end();++k)
     {
             info x;
             unsigned char word[9];
     }

2/ Decoded : faire un resize puisque tu as l'ensemble des éléments, puis avoir un iterateur d'insertion :

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
size_t nbr_elts(0);
while(posu<last_octet) // Tant que l'on a pas atteint le dernier octect
{
   //lecture ...
   read.push_back(w); //On ajoute w a la liste read
   nbr_elts++;
}

Decoded.resize(nbr_elts);
type<Decoded>::iterator it_courant(Decoded.begin());
for(list<mot>::iterator k(read.begin()); k!= read.end();++k)
{
   info x;
  // ... decodage
  *it_courant = x;
   ++it_courant;
}

3/ Que fait wordcopy_2 ?

4/ Je crois que les stringstream ne sont pas très performant. On va remplacer ça :

Code :

1
2
3
4
5
 
               std::ostringstream label;//,c1,c2,c3,c4,c5;    //
               label<<std::oct<<static_cast<int>(word[0]); //Conversion du label en octal
				   std::istringstream l1(label.str());         //
				   l1>>(*x).label; //On affecte la valeur du label a la variable label  de la structure x

Qui si j'ai bien compris transforme un entier en octal et relit cet octal comme un entier. J'en comprend pas bien l'intérêt mais bon...
On va se servir du compilateur pour nous générer une transformation bien plus efficace en utilisant les principes de la méta-programmation (on aurait peut être pu utiliser boost, mais je ne sais pas si tu l'utilises):
On commence par définir une méta-fonction qui nous fait tout le calcul (j'ai pas réfléchie au pb LSB/MSB, je te laisse le soin de vérifier) :
(tu as besoin d'inclure #include <climits> pour CHAR_BIT)

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
template<int Loop, long long dix = 1>
struct dec2oct2dc
{
   inline static long long DoIt(int word_)
   {
      return ((word_&0x07))*dix +
         dec2oct2dc<(Loop-3>0?Loop-3:0), dix*10>::DoIt(word_>>3);
   }
};
 
template<long long dix>
struct dec2oct2dc<0,dix>
{   
   inline static long long DoIt(int)
   {
      return 0;
   }
};

Ensuite on remplace les lignes de codes avec les stream par :

Code :

1
2
 
x.label = dec2oct2dc<sizeof(int)*CHAR_BIT>::DoIt(static_cast<int>(word[0]));

Toujours dans le même ordre d'idée, on va changer ça :

Code :

1
2
3
4
5
6
7
8
9
10
11
 
std::bitset<8> b1(word[0]);      //
std::bitset<8> b2(word[1]);      //
std::bitset<8> b3(word[2]);      //
std::bitset<8> b4(word[3]);      //
std::ostringstream a1,a2,a3,a4;  //Conversion en binaire des 4 octet du mot ARINC
a1<<b1;                          // 
a2<<b2;                          // 
a3<<b3;                          // 
a4<<b4;                          // 
(*x).binaire=a4.str()+a3.str()+a2.str()+a1.str(); //x.bianaire = les 32 bit du mot arinc a la suite (MSB --- LSB)

Par ... horreur ... des macros :

Code :

1
2
3
4
5
6
7
8
9
10
 
#define TOBIT_0(c_,pc) (*(pc) = ((c_)&0x01)?'1':'0');
#define TOBIT_1(c_,pc) (*(pc) = ((c_))&0x01)?'1':'0');TOBIT_0((c_)>>1,(pc)-1)
#define TOBIT_2(c_,pc) (*(pc) = ((c_)&0x01)?'1':'0');TOBIT_1((c_)>>1,(pc)-1)
#define TOBIT_3(c_,pc) (*(pc) = ((c_)&0x01)?'1':'0');TOBIT_2((c_)>>1,(pc)-1)
#define TOBIT_4(c_,pc) (*(pc) = ((c_)&0x01)?'1':'0');TOBIT_3((c_)>>1,(pc)-1)
#define TOBIT_5(c_,pc) (*(pc) = ((c_)&0x01)?'1':'0');TOBIT_4((c_)>>1,(pc)-1)
#define TOBIT_6(c_,pc) (*(pc) = ((c_)&0x01)?'1':'0');TOBIT_5((c_)>>1,(pc)-1)
#define TOBIT_7(c_,pc) (*(pc) = ((c_)&0x01)?'1':'0');TOBIT_6((c_)>>1,(pc)-1)
#define TOBIT(c_,pc) TOBIT_7(c_,pc)

Et le code devient :

Code :

1
2
3
4
5
6
7
8
 
   char str_bit[33];
   str_bit[32]=0;
   TOBIT(word[0],&str_bit[31]);
   TOBIT(word[1],&str_bit[23]);
   TOBIT(word[2],&str_bit[15]);
   TOBIT(word[3],&str_bit[7]);
   x.binaire = str_bit;

5/ (ligne à peu de valeur ajoutée ?)
On remplace

Code :

usec=(word[6]-16*sec)*puiss(256,2)+word[5]*puiss(256,1)+word[4]; // Calcul des µsec

par

Code :

usec=(word[6]&0x0F)*256*256+word[5]*256)+word[4]; // Calcul des µsec

Hypothèse = puiss(256,2)==256*256 et puiss(256,1)=256...

6/ De la même façon, on peut remplacer

Code :

sec=sec+(word[7]-4*m)*16; //Calcul des secondes

par

Code :

sec=sec+(word[7]&0x03)*16; //Calcul des secondes

7/ Dernier point : que fait test_parite ? En fait, prend-il beaucoup de temps ?

[EDIT] ci-joint ton fichier remanié. Il te reste encore un peu de boulot pour vérifier le tout

[Darki03]

merci pour toutes ces réponses, je vais étudier ça ce soir à la maison (au boulot je suis pas mal pris par d'autres choses et je me débrouille avec mon programme tel quel).

Pour les deux fonctions wordcopy_2 et test_par en voici le détail:

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
//Fonction pour copier le mot a2 dans le mot a1
void wordcopy(unsigned char a1[9], unsigned char a2[9])
{ 
     int i=0;
     for(i=0;i<=9;i++)
         {
             a1[i]=a2[i];
         }
}
 
//Fonction pour copier le mot a2 dans le mot a1
void wordcopy_2(unsigned char * const a1, unsigned char a2[9])
{ 
     int i=0;
	 unsigned char *pi;
	 pi=a1;
     for(i=0;i<=9;i++)
         {
             *pi=a2[i];
			 pi++;
         }
}

en fait j'ai fait wordcopy_2 a cause de l'allocation dynamique mais comme tu me conseille plutot de l'enlever, wordcopy suffit !

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
 
//Calcul du nombre de bit a 1 dans un char
int nb_bit_1(char n)
{
 int count=0;
 while(n){
          count++;
          n &= n-1;
          }
  return count;   
}
 
//Test de la parité d'un mot ARINC  (si n1 est pair alors par=1, si n1 est impair par=0)
bool test_parite( unsigned char a[9],int par)
{
     bool k=0;
     int nb1=0;
     int last=0;
     last=a[3]>>7;       //
     last=a[3]-128*last; //On retire le bit de parité dans le mot d'entrée
     nb1 = nb_bit_1(last)+nb_bit_1(a[2])+nb_bit_1(a[1])+nb_bit_1(a[0]); //Nb de bit a 1 dans les 31 bits restants
     if ( ( ( nb1 & 1 ) && ( par==0 ) ) || ( !( nb1 & 1 ) && ( par==1 ) ) ) //Si nb1 est impair et par=0 ou Si nb1 est pair et par=1 alors le test est True
	 {
         k=1;
	 }
     else 
	 {
	     k=0; //Sinon le test est False
	 }
	 return k;
}

Cette fonction réalise un test de parité sur le mot ARINC. Elle compare le bit de parité à la valeur qui devrait etre envoyée en fonction du nombre de bits à 1 dans les 31 bits restants.

Derniere question, si j'ai bien compris [word[3]-128*par] est équivalent à [word[3]&0x7F] ?

[3DArchi]

Envoyé par Darki03

Pour les deux fonctions wordcopy_2 et test_par en voici le détail:

Sauf erreur de recopie, tu as un bug dans tes fonctions wordcopy : i va jusqu'à 9 inclus alors que le tableau est de taille 9 (donc dernier adressable est [8]). Jamais eu de plantage inexpliqué ?

Envoyé par Darki03

en fait j'ai fait wordcopy_2 a cause de l'allocation dynamique mais comme tu me conseille plutot de l'enlever, wordcopy suffit !

Sinon, si tu l'as, utilises memcpy. En général, il est optimisé pour être plus efficace que ta fonction.

Envoyé par Darki03

Code :

Cette fonction réalise un test de parité sur le mot ARINC. Elle compare le bit de parité à la valeur qui devrait etre envoyée en fonction du nombre de bits à 1 dans les 31 bits restants.

Je jette un coup d'oeil.

Envoyé par Darki03

Derniere question, si j'ai bien compris [word[3]-128*par] est équivalent à [word[3]&0x7F] ?

(il m'avait échappé).

[3DArchi]

Code :

1
2
3
 
     last=a[3]>>7;       //
     last=a[3]-128*last; //On retire le bit de parité dans le mot d'entrée

Peut juste être simplifié :

Code :

1
2
 
last=a[3]&0x7f; //Tu connais maintenant !

Ton code ressemble furieusement à du code C qui aurait été porté en C++, non ?

[Darki03]

Envoyé par 3DArchi

Sauf erreur de recopie, tu as un bug dans tes fonctions wordcopy : i va jusqu'à 9 inclus alors que le tableau est de taille 9 (donc dernier adressable est [8]). Jamais eu de plantage inexpliqué ?

Oo je sais pas pourquoi j'ai fait ça mais y'a bel et bien un soucis. A priori cela n'engendre pas de plantage ! je vais quand meme corriger cela tout de suite !

[3DArchi]

Envoyé par Darki03

A priori cela n'engendre pas de plantage !

Tu as eu de la chance (probablement que l'octet est un octet de padding pour de l'alignement et non significatif).

[Darki03]

Envoyé par 3DArchi

Code :

Peut juste être simplifié :

Code :

Ton code ressemble furieusement à du code C qui aurait été porté en C++, non ?

En fait j'ai écrit des partie de code avec mes souvenirs de cours de C (parce qu'on retient les choses plus facilement après le C++ avec les classes, héritage et encapsulation et autres bizzareries je ne me rappelle plus grand chose !)

Les parties en C++ ont été faite a partir de toutes mes recherches sur internet !