Inversion de bits d'un octets

Version imprimable

29/04/2008, 13h58
agentchico

Inversion de bits d'un octets

Bonjour,
Je cherche depuis un moment un algo pour faire une inversion des 8 bits d'un unsigned char.

J'ai un unsigned char : b7 b6 b5 b4 b3 b2 b1 b0
Et je veux qu'il devienne : b0 b1 b2 B3 b4 b5 b6 b7

Donc : 0110 0011 => 1100 0110

Si vous pouviez m'aider, je perd la tête avec tout mes masques :lol:

merci
29/04/2008, 14h10
dapounet

Je ferais comme ça : permuter les moitiés de chaque octet, puis les moitiés de chaque quadruplet, etc.

7 6 5 4 3 2 1 0

3 2 1 0 7 6 5 4

1 0 3 2 5 4 7 6

0 1 2 3 4 5 6 7
29/04/2008, 14h25
agentchico
hum, oui je vais essayer :D
Code:

1 2 3 4 5 6 7 8 unsigned char rot(unsigned char octet) { unsigned char temp=octet<<4; temp=temp|(octet>>4); return temp; }
bon j'ai la première permutation .. maintenant faut que je réfléchisse pour la suite :aie:
29/04/2008, 14h37
nicodn02

tu as vu les mask avec les bits ?
29/04/2008, 14h40
souviron34

et surtout les structures 'champ de bit" (ou bitfield) :mrgreen:
29/04/2008, 14h45
agentchico

Les masques oui, bitfield jamais entendu. Je vais voir ce que c'est.

Sinon avec les permutations,il me manque la dernière permutation et c'est bon.

Mais si il y a une autre solution, je veux bien aussi.

merci

il y a en effet plus simple:
Code:

1 2 3 4 5 6 7 8 9 10 11 unsigned char swich(unsigned char c){ unsigned char d = 0; int i; for(i=0; i<8; i++){ if(c&(1<<i)) d = d|(1<<(7-i)); } return d; }
Algo:
boucle balayant les 8bits du unsigned char c
lecture de droite a gauche
si le bit lu est un 1, alors on le place dans d à la bonne position

Remarque: on ne peut effectuer que 7 decalages dans un unsigned char ou sinon on "sort" du unsigned char

proposition

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
unsigned char rotation(unsigned char r) {
    int i;
    unsigned char masque1=1, masque2=1, t=0;
 
    masque2 = masque2 << 7;
    for (i=1;i<=8;i++) {
        if ( r & masque1 ) {
            t = t | masque2;
        }
        masque1 = masque1 << 1;
        masque2 = masque2 >> 1;
    }
 
    return t;
}

29/04/2008, 15h07
valefor

Pour les manips de bits j'aime bien cette page
29/04/2008, 15h09
agentchico

effectivement c'est l'algo que je cherche depuis le début, je tournai autour sans le trouver exactement et la méthode permutation est un peu trop "barbare" après l'avoir fait :lol:

edit: pour la proposition je vais l'analyser et la page va me servir vu que je bosse sur des automates, les bits je vais en manger :)

merci!

Citation:

Envoyé par agentchico

Je cherche depuis un moment un algo pour faire une "demi rotation" des 8 bits d'un unsigned char.

J'ai un unsigned char : b7 b6 b5 b4 b3 b2 b1 b0
Et je veux qu'il devienne : b0 b1 b2 B3 b4 b5 b6 b7

Donc : 0110 0011 => 1100 0110

Je ne sais pas ce que tu appelles demi-rotation, mais ce que tu montres est une inversion de bits.

Il suffit de lire la donnée bit a bit et de l'écrire au bon endroit ensuite. Il y a plusieurs méthodes qu'il va falloir comparer en efficacité, parce que quoiqu'il arrive, elles sont lentes. L'interface pourrait être :

Code:

1
2
3
4
 
unsigned bit_reverse8 (unsigned data)
{
}

Voila un canevas d'essais

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
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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
 
/* delahaye.emmanuel@free.fr/clib/ */
#include "ed/inc/chro.h"
#include "ed/inc/sys.h"
 
#include <stdio.h>
#include <assert.h>
 
/* user's define
 
Device Under Test (DUT)
*/
typedef unsigned dut_f (unsigned data);
 
unsigned bit_reverse8_a (unsigned data)
{
   unsigned rev = 0;
   unsigned char a[8];
   int i = 0;
   unsigned m = 1;
 
   /* expansion */
   for (i = 0; i < 8; i++)
   {
      a[i] = !!(data & m);
      m <<= 1u;
   }
 
   /* reduction */
   for (i = 0; i < 8; i++)
   {
      m >>= 1u;
      if (a[i] == 1)
      {
         rev |= m;
      }
   }
 
   return rev;
}
 
unsigned bit_reverse8_b (unsigned data)
{
   unsigned rev = 0;
   int i = 0;
   unsigned ms = 1;
   unsigned md = 1 << 8;
 
   /* expansion */
   for (i = 0; i < 8; i++)
   {
      unsigned bit = !!(data & ms);
 
      ms <<= 1u;
 
      md >>= 1u;
 
      if (bit == 1)
      {
         rev |= md;
      }
   }
 
   return rev;
}
 
unsigned bit_reverse8_c (unsigned data)
{
   return (((data * 0x80200802ULL) & 0x0884422110ULL) *
           0x0101010101ULL >> 32) & 0xFF;
}
 
unsigned bit_reverse8_d (unsigned data)
{
   int i;
   unsigned masque1 = 1;
   unsigned masque2 = 1 << 7;
   unsigned t = 0;
 
   for (i = 0; i < 8; i++)
   {
      if (data & masque1)
      {
         t |= masque2;
      }
      masque1 <<= 1;
      masque2 >>= 1;
   }
   return t;
}
 
unsigned bit_reverse8_e (unsigned n)
{
   n = (n << 4) | (n >> 4);
   n = ((n << 2) & 0xCC) | ((n >> 2) & 0x33);
   n = ((n << 1) & 0xAA) | ((n >> 1) & 0x55);
 
   return n;
}
 
unsigned bit_reverse8_f (unsigned n)
{
 
   unsigned d = 0;
   int i;
   for (i = 0; i < 8; i++)
   {
      if (n & (1 << i))
         d = d | (1 << (7 - i));
   }
   return d;
}
 
#ifdef  TEST
#define NB_TRY 10000000ul
 
struct test
{
   dut_f *pf_dut;
   char const *s_ver;
   double temps;
};
 
static int compare (void const *pa, void const *pb)
{
   struct test const *ta = pa;
   struct test const *tb = pb;
   return (int) (ta->temps - tb->temps);
}
 
static void results (struct test *a_test, size_t n)
{
   qsort (a_test, n, sizeof *a_test, compare);
 
   printf ("\nHall of fame (average)\n\n");
   {
      size_t i;
 
      for (i = 0; i < n; i++)
      {
         struct test const *p = a_test + i;
         printf ("%2d - %.1f ns (%s)\n", i + 1, p->temps, p->s_ver);
      }
   }
}
 
int main (void)
{
   chro_s *chrono = chro_create ();
 
   if (chrono != NULL)
   {
      struct test a_test[] = {
         {bit_reverse8_a, "a by -ed-", 0},
         {bit_reverse8_b, "b by -ed-", 0},
         {bit_reverse8_c, "c by valfor", 0},
         {bit_reverse8_d, "d by Corentin59", 0},
         {bit_reverse8_e, "e by dapounet", 0},
         {bit_reverse8_f, "f by nicodn02", 0},
      };
      size_t i;
      for (i = 0; i < NELEM (a_test); i++)
      {
         struct test const *p = a_test + i;
         unsigned long try;
         int err = 0;
 
         chro_init (chrono);
         chro_start (chrono);
 
         for (try = 0; !err && try < NB_TRY; try++)
         {
            /* D.U.T */
            unsigned data = p->pf_dut (0x80);
 
            if (data != 0x01)
            {
               printf ("erreur (%s) data = %02X\n", p->s_ver, data);
               err = 1;
            }
         }
 
         chro_stop (chrono);
 
         /* get time and store the average */
         if (!err)
         {
            unsigned long ms;
            chro_elapsed (chrono, &ms);
            a_test[i].temps = (1000000 * ms) / (double) NB_TRY;
            printf ("done in %.1f ns (%s)\n", a_test[i].temps, p->s_ver);
         }
      }
 
      results (a_test, NELEM (a_test));
 
      chro_delete (chrono), chrono = NULL;
   }
   assert (chrono == NULL);
 
   return 0;
}
#endif

Finalement, sauf erreur de ma part, ça va vite...

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
done in 68.7 ns (a by -ed-)
done in 68.8 ns (b by -ed-)
done in 45.3 ns (c by valfor)
done in 48.4 ns (d by Corentin59)
done in 28.1 ns (e by dapounet)
done in 51.6 ns (f by nicodn02)
 
Hall of fame (average)
 
 1 - 28.1 ns (e by dapounet)
 2 - 45.3 ns (c by valfor)
 3 - 48.4 ns (d by Corentin59)
 4 - 51.6 ns (f by nicodn02)
 5 - 68.8 ns (b by -ed-)
 6 - 68.7 ns (a by -ed-)
 
Press ENTER to continue.

29/04/2008, 15h26
agentchico

Ok je ne savais pas que comment ca s'appeler.
Inversion je pensais plutôt à 0011 0011 => 1100 1100.

Soit, je change.

J'aime bien cette solution :

Code:

1
2
3
4
5
 
unsigned char bit_reverse8 (unsigned char b)
{
return ((b * 0x80200802ULL) & 0x0884422110ULL) * 0x0101010101ULL >> 32;
}

Citation:
Envoyé par valefor
J'aime bien cette solution :
Code:

1 2 3 4 5 unsigned char bit_reverse8 (unsigned char b) { return ((b * 0x80200802ULL) & 0x0884422110ULL) * 0x0101010101ULL >> 32; }
Après légère mise au point, OK.

Citation:

Envoyé par corentin59

proposition

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
unsigned char rotation(unsigned char r) {
    int i;
    unsigned char masque1=1, masque2=1, t=0;
 
    masque2 = masque2 << 7;
    for (i=1;i<=8;i++) {
        if ( r & masque1 ) {
            t = t | masque2;
        }
        masque1 = masque1 << 1;
        masque2 = masque2 >> 1;
    }
 
    return t;
}

OK. C'est une version légèrement optimisée de ma proposition b. Après légère optimisation du codage, elle se classe après valfor.

Citation:

Envoyé par Emmanuel Delahaye

Après légère mise au point, OK. Meilleur classement sur ma machine pour le moment.

Et avec l'algorithme que j'ai donné au début ?
Code:

1 2 3 4 5 6 7 8 unsigned char rot (unsigned char n) { n = (n << 4) | (n >> 4); n = ((n << 2) & 0xCC) | ((n >> 2) & 0x33); n = ((n << 1) & 0xAA) | ((n >> 1) & 0x55); return n; }

29/04/2008, 23h04
Emmanuel Delahaye

Citation:

Envoyé par dapounet

Et avec l'algorithme que j'ai donné au début ?

Tu bas tout le monde !
29/04/2008, 23h32
Emmanuel Delahaye

Citation:

Envoyé par agentchico

vu que je bosse sur des automates, les bits je vais en manger :)

C'est ta vie !
30/04/2008, 08h40
valefor

Citation:

elle se classe après valfor.

Oulala, attention, ce n'est pas de moi hein !

Ceci dit je ne sais pas combien d'instructions vont êtres générées pour la solution de dapounet.

Si quelqu'un peut donner le code généré pour les différentes solutions, on aurait éventuellement un aperçut de leur performances...