Discussion :

[agentchico]

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

merci

[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

[agentchico]

hum, oui je vais essayer

Code :

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

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

[nicodn02]

tu as vu les mask avec les bits ?

[souviron34]

et surtout les structures 'champ de bit" (ou bitfield)

[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

[nicodn02]

il y a en effet plus simple:

Code :

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

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

[corentin59]

proposition

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
 
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;
}

[Emmanuel Delahaye]

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 :

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

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

Voila un canevas d'essais

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
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 :

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
 
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.

[agentchico]

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

Soit, je change.

[valefor]

J'aime bien cette solution :

Code :

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

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

[Emmanuel Delahaye]

J'aime bien cette solution :

Code :

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

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.

[dapounet]

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 :

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

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;
}

[Emmanuel Delahaye]

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

Tu bas tout le monde !