Discussion :

[antonny]

Au cours d'une de mes lectures de cours C, je suis tombé sur ce bout de code qui permet d'optimiser une inversion de bits dans un entier par une référence à une table de correspondance :

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
 Reverse bits in word by lookup table : 
 
static const unsigned char BitReverseTable256[256] = 
{
#   define R2(n)     n,     n + 2*64,     n + 1*64,     n + 3*64
#   define R4(n) R2(n), R2(n + 2*16), R2(n + 1*16), R2(n + 3*16)
#   define R6(n) R4(n), R4(n + 2*4 ), R4(n + 1*4 ), R4(n + 3*4 )
    R6(0), R6(2), R6(1), R6(3)
};
 
unsigned int v; // reverse 32-bit value, 8 bits at time
unsigned int c; // c will get v reversed
 
// Option 1:
c = (BitReverseTable256[v & 0xff] << 24) | 
    (BitReverseTable256[(v >> 8) & 0xff] << 16) | 
    (BitReverseTable256[(v >> 16) & 0xff] << 8) |
    (BitReverseTable256[(v >> 24) & 0xff]);

Je manque d’expérience en C et je ne comprends pas la syntaxe de cette partie notamment :

Code :

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

1
2
3
4
5
6
7
 static const unsigned char BitReverseTable256[256] = 
{
#   define R2(n)     n,     n + 2*64,     n + 1*64,     n + 3*64
#   define R4(n) R2(n), R2(n + 2*16), R2(n + 1*16), R2(n + 3*16)
#   define R6(n) R4(n), R4(n + 2*4 ), R4(n + 1*4 ), R4(n + 3*4 )
    R6(0), R6(2), R6(1), R6(3)
};

Comment je dois lire ça ? Un tableau dans lequel il y a des macros définies ? Mais combien d'éléments constituent le tableau ici à sa déclaration ?
(Je n'avais jamais vu des macros placées comme ça dans un tableau). Bref, je suis perdu au niveau de la syntaxe.
Si vous pouviez m'éclairer
Merci,
salutations.

[picodev]

Bonjour,

Peu importe où se situent les définitions des macros, seules leurs expansions se retrouvent dans le code qui sera compilé. Le code suivant revient au même, il ne s'agit que d'un choix esthétique facilitant la compréhension, a priori.

Code :

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

1
2
3
4
5
6
7
8
#   define R2(n)     n,     n + 2*64,     n + 1*64,     n + 3*64
#   define R4(n) R2(n), R2(n + 2*16), R2(n + 1*16), R2(n + 3*16)
#   define R6(n) R4(n), R4(n + 2*4 ), R4(n + 1*4 ), R4(n + 3*4 )
 
static const unsigned char BitReverseTable256[256] = 
{
    R6(0), R6(2), R6(1), R6(3)
};

Si tu sauves ce morceau de code dans un fichier macro.c et que tu lances la commande gcc -E macro.c tu verras la sortie du préprocesseur avec les macros expansées :

Code :

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

1
2
3
4
5
6
7
static const unsigned char BitReverseTable256[256] =
{
 
 
 
    0, 0 + 2*64, 0 + 1*64, 0 + 3*64, 0 + 2*16, 0 + 2*16 + 2*64, 0 + 2*16 + 1*64, 0 + 2*16 + 3*64, 0 + 1*16, 0 + 1*16 + 2*64, 0 + 1*16 + 1*64, 0 + 1*16 + 3*64, 0 + 3*16, 0 + 3*16 + 2*64, 0 + 3*16 + 1*64, 0 + 3*16 + 3*64, 0 + 2*4, 0 + 2*4 + 2*64, 0 + 2*4 + 1*64, 0 + 2*4 + 3*64, 0 + 2*4 + 2*16, 0 + 2*4 + 2*16 + 2*64,
......

Sinon pour le nombre d'éléments c'est relativement simple. La macro R6 utilise 4 fois R4, R4 utilise 4 fois R2 et R2 produit 4 éléments. Au total nous avons donc 4*4*4=64 éléments par expansion de macro R6. Le tableau est rempli avec 4 appels à cette macro donc il aura 4*64=256 éléments.
Au final ce tableau contient à l'indice i un octet avec les bits de i renversés.

[antonny]

Merci Picodev, c'est très clair maintenant.