Portabilité de mes opérations sur les bits : critiques

**roh01** · 08/04/2009, 18h12

Bonjour,

Je travaille actuellement sur une librairie destinée à compacter / décompacter des entiers signés, codés sur 32 bits. Le but est de les coder sur 24, 16 ou 8 bits selon le cas pour les transmettre sur un canal de communication puis d’être capable d’effectuer la bijection inverse chez le récepteur.

J’ai utilisé deux techniques différentes pour réaliser ces fonctions. Je manque toutefois de recul (et d’expérience) pour porter un regard critique sur mon travail. C’est pourquoi je sollicite humblement votre avis :p

Première approche (la plus intuitive pour moi) :

J’ai utilisé une union pour mapper sur l’entier un tableau d’octet

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
union BufferInt32_u
{
   int32_t entier;
   char_t octets[C_NB_OCTETS_32BITS];
};
typedef union BufferInt32_u bufferint32_t;

Par cette technique, je suis capable d’accéder et de travailler sur les différents octets qui composent l’entier. Je test l’octet qui contient le bit de signe (qui correspond au MSB). Cette méthode n’est pas portable car je dois émettre une hypothèse sur sa position dans le tableau de char.

Voici, en exemple, la fonction qui réalise la conversion entier signé 32 -> 24 bits

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
int32_t RecadrerInt32Int24(int32_t Entier32bits, char_t p_EntierCompresse[C_NB_OCTETS_24BITS])
{
   bufferint32_t BufferInt32;
   size_t i;
   int32_t CompteRendu;
   char_t BufferResultat[C_NB_OCTETS_24BITS];
 
   //Controler que l'entier rentre bien dans la taille mémoire finale spécifiée
   if ((Entier32bits >= C_MIN_INT_24BITS) && (Entier32bits <= C_MAX_INT_24BITS))
   {
 
      //Recopie de l'entier a compresser dans une variable locale pour modification
      BufferInt32.entier = Entier32bits;
 
      //Replacer le bit de poids fort qui contient le signe
      BufferResultat[C_POS_OCTET_POIDS_FORT_24BITS]
               = (BufferInt32.octets[C_POS_OCTET_POIDS_FORT_32BITS])
                        & C_MASQUE_POIDS_FORT_OCTET;
 
      //Reconstruire l'octet de poids fort
      BufferResultat[C_POS_OCTET_POIDS_FORT_24BITS]
               |= BufferInt32.octets[C_POS_OCTET_POIDS_FORT_24BITS];
 
      //Replacer les autres bits
      for (i = C_POSITION_OCTET_POIDS_FAIBLE; i < C_POS_OCTET_POIDS_FORT_24BITS; ++i)
      {
         BufferResultat[i] = BufferInt32.octets[i];
      }
      CompteRendu = EXIT_SUCCESS;
   }
   else
   {
      //Positionner les bits à une valeur par defaut
      for (i = C_ZERO; i < C_NB_OCTETS_24BITS; ++i)
      {
         BufferResultat[i] = C_INT8_DEFAUT;
      }
      CompteRendu = EXIT_FAILURE;
   }
 
   //Assigner à la sortie la valeur du buffer
   for (i = C_ZERO; i < C_NB_OCTETS_24BITS; ++i)
   {
      p_EntierCompresse[i] = BufferResultat[i];
   }
 
   return CompteRendu;
}

Et, voici la fonction qui réalise l’opération inverse :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
int32_t ReformerInt24Int32(char_t EntierCompresse24Bits[C_NB_OCTETS_24BITS], int32_t * p_Entier32bits)
{
   bufferint32_t BufferInt32;
   int32_t CompteRendu;
   size_t i;
 
   //Initialisation du buffer
   BufferInt32.entier = C_ZERO;
 
   //Recopie de l'entier a compresser dans une variable locale pour modification
   for (i = C_ZERO; i < C_NB_OCTETS_24BITS; ++i)
   {
      BufferInt32.octets[i] = EntierCompresse24Bits[i];
   }
 
   //Test du signe de l'entier a reformer
   if (EntierCompresse24Bits[C_POS_OCTET_POIDS_FORT_24BITS] >= C_ZERO)
   {
      //On complete l'entier avec des zeros
      BufferInt32.entier &= C_MASQUE_POSITIF_24_VERS_32BITS;
   }
   else
   {
      //On complete avec des uns
      BufferInt32.entier |= C_MASQUE_NEGATIF_24_VERS_32BITS;
   }
 
   CompteRendu = EXIT_SUCCESS;
 
   //Assigner à la sortie la valeur du buffer
   *p_Entier32bits = BufferInt32.entier;
 
   return CompteRendu;
}

La 2e technique est censée rendre la fonction portable en privilégiant les opérations de décalage de bits. Du coup, l’utilisation de l’union n’est plus justifiée.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
int32_t Test(int32_t Entier32bits, char_t p_EntierCompresse[C_NB_OCTETS_24BITS])
{
 
   size_t CompteurOctets;
 
   for (CompteurOctets = C_ZERO; CompteurOctets < C_NB_OCTETS_24BITS; ++CompteurOctets)
   {
      p_EntierCompresse[CompteurOctets] = (char_t) ((Entier32bits >> (C_NB_BITS_OCTET * CompteurOctets)) & 0x000000FF);
   }
 
 
   if(Entier32bits >> (C_NB_BITS_OCTET * C_NB_OCTETS_32BITS - C_UN))
   {
      //Le nombre est negatif
      p_EntierCompresse[C_NB_OCTETS_24BITS - C_UN]|= 0x80;
 
   }
   else
   {
      //Le nombre est positif
      p_EntierCompresse[C_NB_OCTETS_24BITS - C_UN]&= 0x7F;
   }
 
   return EXIT_SUCCESS;
}

Ce code fonctionne également mais la norme C99 (chapitre 6.5.7) précise que le décalage de bits sur des entiers signés est dangeureux. J’ai modifié la fonction pour travailler sur des entiers non signés :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
int32_t Test(int32_t Entier32bits, char_t p_EntierCompresse[C_NB_OCTETS_24BITS])
{
 
   size_t CompteurOctets;
   uint32_t EntierNonSigne = (uint32_t) Entier32bits;
 
   for (CompteurOctets = C_ZERO; CompteurOctets < C_NB_OCTETS_24BITS; ++CompteurOctets)
   {
      p_EntierCompresse[CompteurOctets] = (char_t) ((EntierNonSigne >> (C_NB_BITS_OCTET * CompteurOctets)) & 0x000000FF);
   }
 
 
   if(EntierNonSigne >> (C_NB_BITS_OCTET * C_NB_OCTETS_32BITS - C_UN))
   {
      //Le nombre est negatif
      p_EntierCompresse[C_NB_OCTETS_24BITS - C_UN]|= 0x80;
 
   }
   else
   {
      //Le nombre est positif
      p_EntierCompresse[C_NB_OCTETS_24BITS - C_UN]&= 0x7F;
   }
 
   return EXIT_SUCCESS;
}

Mes questions :

dans la mesure où je n’utilise pas la valeur de l’entier « décalé », est-il vraiment nécessaire de passer par l’entier non signé pour obtenir un code portable ?
autre technique :
- créer deux jeux de fonctions, chacun supposant le bit de signe en début ou fin du tableau d’octets
- créer deux jeux de fonctions, chacun supposant le bit de signe en début ou fin du tableau d’octets
- tester la position du bits de signe dans le tableau d’octets et affecter à la bonne fonction l’alias RecadrerInt32IntXX
Qu’en pensez-vous ?

Merci d'avance,

Les headers :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
 #define C_DECALAGE_UN_BIT 1
#define C_NB_BITS_OCTET 8
#define C_NB_OCTETS_32BITS 4
#define C_NB_OCTETS_24BITS 3
#define C_NB_OCTETS_16BITS 2
#define C_NB_OCTETS_8BITS 1
 
//Constantes des tableaux de bits
#define C_POS_BIT_POIDS_FORT_OCTET (C_NB_BITS_OCTET - 1 + C_PREMIER_INDICE)
#define C_POS_BIT_POIDS_FAIBLE_OCTET C_PREMIER_INDICE
 
//Constantes des tableaux d'octets
#define C_POSITION_OCTET_POIDS_FAIBLE C_PREMIER_INDICE
#define C_POS_OCTET_POIDS_FORT_32BITS (C_NB_OCTETS_32BITS - 1 + C_PREMIER_INDICE)
#define C_POS_OCTET_POIDS_FORT_24BITS (C_NB_OCTETS_24BITS - 1 + C_PREMIER_INDICE)
 
//Constantes des masques de conversion
#define C_MASQUE_POIDS_FAIBLE_OCTET 0x01
#define C_MASQUE_POIDS_FORT_OCTET 0x80
#define C_MASQUE_POSITIF_24_VERS_32BITS 0x00FFFFFF
#define C_MASQUE_NEGATIF_24_VERS_32BITS 0xFF000000
 
#define C_MIN_INT_24BITS -8388608
#define C_MAX_INT_24BITS -C_MIN_INT_24BITS-1
 
//Valeurs par defaut
#define C_INT8_DEFAUT 0
#define C_INT32_DEFAUT 0

**diogene** · 08/04/2009, 18h49

Ce n'est pas facile parce que :
- l'utilisation d'une union n'est pas portable, d'abord parce que mettre une valeur dans un champ et la relire dans un autre n'est pas portable.
- le codage des entiers signés n'est pas portable : il existe 3 façons légales de coder un entier signé
- Comme tu le signales, il y a problème à décaler des entiers signés si la valeur est négative

Personnellement, je m'orienterai vers un format d'émission/ réception (puisque tu sembles avoir la maîtrise de la fonction de réception) d'un unsigned + le signe + l'information concernant l'endian de l'émission ou avec un endian défini. On doit alors pouvoir reconstituer la valeur dans le format de la machine réceptrice.

**Emmanuel Delahaye** · 09/04/2009, 09h55

Envoyé par diogene

Personnellement, je m'orienterai vers un format d'émission/ réception (puisque tu sembles avoir la maîtrise de la fonction de réception) d'un unsigned + le signe + l'information concernant l'endian de l'émission ou avec un endian défini. On doit alors pouvoir reconstituer la valeur dans le format de la machine réceptrice.

on a pas besoin de connaitre l'endianness si on utilise un format indépendant de la machine, comme le format réseau (MSB en tête). Ensuite, on peut définir un format sur 1, 2 3 ou 4 octets, mais il faut nécessairement une information pour savoir de quoi on parle, ce qui veut dire par exemple :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
[0] 1
[1] donnee

ou

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
[0] 2
[1] MSB
[2] LSB

ou

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
[0] 3
[1] MSB
[2] ...
[3] LSB

ou

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
[0] 4
[1] MSB
[2] ...
[3] ...
[4] LSB

etc.

Pas sûr qu'on gagne vraiment de la place...

**sopsag** · 09/04/2009, 11h44

Dans le monde des codec video (et peut être ailleurs) on trouve le format SDL qui permet de coder un entier sur le moins d'octets possible.
Le truc est simple :
Chaque octet du resultat est interprété comme ça :
les 7 bits de poids faible contiennent une partie de l'entier à encoder.
le bit de poids fort indique qu'il faut continuer à décoder l'octet suivant.
(le bit de poids fort à zero signifie qu'on a fini)

Ce qui donne :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
typedef unsigned long long uint_to_encode ;

int encode_to_SDL ( uint_to_encode size , unsigned char * ouput )
    {
    int n ;
    for ( n = 0 ; size > 0 ; size >>= 7 , ++n , ++ouput )
        {
        *ouput = (unsigned char)( size & 0x7F ) ;
        if (size > 0x7F) *ouput |= 0x80 ;
        }
    return( n ) ;
    }

uint_to_encode decode_SDL ( const unsigned char * input , int * nb_byte_used )
    {
    uint_to_encode res = 0 ;
    int n,pow ;

    for ( n = 1 , pow = 0 ;; pow += 7 , ++n , ++input )
        {
        res += (*input & 0x7F) << pow ;
        if ((*input & 0x80) == 0) break ;
        }
    if (nb_byte_used != NULL) *nb_byte_used = n ;
    return( res ) ;
    }

A toi de redéfinir le type uint_to_encode en fonction de tes besoins.
Dans certain cas bien sûr, tu peut avoir besoin de 5 octets pour coder un int mais c'est rare et inévitable...
(de même que certains fichiers sont plus gros une fois zippés)

**Emmanuel Delahaye** · 09/04/2009, 11h50

Envoyé par sopsag

Dans le monde des codec video (et peut être ailleurs) on trouve le format SDL qui permet de coder un entier sur le moins d'octets possible.
Le truc est simple :
Chaque octet du resultat est interprété comme ça :
les 7 bits de poids faible contiennent une partie de l'entier à encoder.
le bit de poids fort indique qu'il faut continuer à décoder l'octet suivant.
(le bit de poids fort à zero signifie qu'on a fini)

Ca ressemble au format BER utilisé en SNMP ...

C'est assez complexe...

**sopsag** · 09/04/2009, 14h01

boarpfl !
ce n'est pas si compliqué... regarde le code : quelques lignes de C pour encoder et décoder.

**roh01** · 09/04/2009, 18h05

Merci beaucoup pour toutes vos réponses.

Je n'ai pas beaucoup de temps à moi ces temps-ci, mais des que j'aurais digéré vos réponses, je ne manquerais pas de poster mes remarques/questions/remerciements.

**roh01** · 13/05/2009, 10h18

Bonjour,

Le volume des données à traiter par mon application étant modéré (embarqué temps réel) donc je préfère me limiter à des fonctions simples et claires. En effet, même si le format SDL semble puissant (merci pour l'information), je pense que dans mon cas précis, le gain serait restreint.

Comme suggéré, j'ai choisi de définir mon propre format de données *intermédiaire* pour les données signées :

MSB = bit de signe
Reste des bits = bits de données

Voilà le code que j'ai écris pour la conversion d'un entier 16 bits :

Compactage

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
int32_t RecadrerInt32Int16(int32_t Entier32bits,
         uchar_t p_EntierCompresse[C_NB_OCTETS_16BITS])
{
   uchar_t BufferConversionEntier[C_NB_OCTETS_16BITS];
   int32_t CompteRendu;
   size_t Compteur;
   uint32_t EntierNonSigne;
 
   //Initialisation de la sortie et des variables locales
   memset(p_EntierCompresse, C_ZERO, C_NB_OCTETS_16BITS);
   memset(BufferConversionEntier, C_ZERO, C_NB_OCTETS_16BITS * sizeof(uchar_t));
   EntierNonSigne = C_ZERO;
 
   //Controler que l'entier rentre bien dans la taille mémoire finale spécifiée
   if ((Entier32bits >= C_MIN_INT_16BITS) && (Entier32bits <= C_MAX_INT_16BITS))
   {
      if (Entier32bits >= C_ZERO)
      {
         //Le nombre a traiter est positif
         BufferConversionEntier[C_ZERO + C_PREMIER_INDICE] = C_SIGNE_POSITIF;
         EntierNonSigne = (uint32_t) Entier32bits;
      }
      else
      {
         //Le nombre a traiter est negatif
         BufferConversionEntier[C_ZERO + C_PREMIER_INDICE] = C_SIGNE_NEGATIF;
         EntierNonSigne = (uint32_t) (-Entier32bits);
      }
 
      //Sauvegarde de l'octet de poid fort decale pour etre positionne en octet de poid faible
      //Le MSB, contenant le bit de signe peut etre neutralise car deja traite
      BufferConversionEntier[C_ZERO + C_PREMIER_INDICE]
               |= (uchar_t) ((EntierNonSigne >> C_DECALAGE_2E_OCTET)
                        & C_MASQUE_7BITS_POID_FAIBLE);
 
      //Decomposition dans le buffer des octets restants
      for (Compteur = C_UN; Compteur < C_NB_OCTETS_16BITS; ++Compteur)
      {
         BufferConversionEntier[Compteur + C_PREMIER_INDICE]
                  = (uchar_t) (C_MASQUE_OCTET_POID_FAIBLE
                           & (EntierNonSigne >> (C_DECALAGE_2E_OCTET - Compteur
                                    * C_NB_BITS_OCTET)));
      }
 
      //Affectation de la sortie et du compte rendu d'execution
      memcpy(p_EntierCompresse, BufferConversionEntier, C_NB_OCTETS_16BITS
               * sizeof(uchar_t));
      CompteRendu = EXIT_SUCCESS;
   }
   else
   {
      //Positionnement des sorties a des valeurs par defaut
      memset(p_EntierCompresse, C_INT8_DEFAUT, C_NB_OCTETS_16BITS);
      CompteRendu = EXIT_FAILURE;
   }
 
   return CompteRendu;
}

Decompactage :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
int32_t ReformerInt16Int32(uchar_t EntierCompresse16Bits[C_NB_OCTETS_16BITS],
         int32_t * p_Entier32bits)
{
   uchar_t BufferConversionEntier[C_NB_OCTETS_16BITS];
   uint32_t Accumulateur;
   size_t Compteur;
 
   //Initialisation des sorties
   *p_Entier32bits = C_ZERO;
 
   //Recopie des octets a traiter dans le buffer
   memcpy(BufferConversionEntier, EntierCompresse16Bits, C_NB_OCTETS_16BITS
            * sizeof(uchar_t));
 
   //Initialisation de l'accumulateur a la valeur du MSB (moins le bit de signe)
   Accumulateur = (uint32_t) BufferConversionEntier[C_ZERO + C_PREMIER_INDICE]
            & C_MASQUE_7BITS_POID_FAIBLE;
 
   //Recopie des octets suivant dans l'accumulateur décalé
   for (Compteur = C_UN; Compteur < C_NB_OCTETS_16BITS; ++Compteur)
   {
      Accumulateur = (Accumulateur << C_NB_BITS_OCTET) | BufferConversionEntier[C_PREMIER_INDICE
               + Compteur];
   }
 
   //Recopie du signe de l'entier a decompresser
   if ((EntierCompresse16Bits[C_POSITION_MSB] & C_MASQUE_POIDS_FORT_OCTET)
            == C_SIGNE_POSITIF)
   {
      *p_Entier32bits = (int32_t) Accumulateur;
   }
   else
   {
      *p_Entier32bits = (int32_t) (-Accumulateur);
   }
 
   return EXIT_SUCCESS;
}

Je me suis forcé à utiliser exclusivement les opérations de décalage de bits, de comparaison de signes et/ou de masquage pour assurer le maximum de portabilité.
Je n'utilise plus d'unions.
Enfin, les seules hypothèses que j'émet sur la position des octets ne devrait concerner que le format intermédiaire (ou compacté) que j'ai défini.

Qu'en pensez-vous ?

Merci d'avance

Portabilité de mes opérations sur les bits : critiques

C

Discussions similaires

Partager

Partager