rotation de bits

**pierabobl** · 10/07/2006, 15h16

Bonjour a tous,
Est ce que quelqu'un sais si il est possible de faire une rotation de bits sur une valeur quelconque, en C.
Attention, je parle pas du decalage classique avec les operateurs << et >>, mais une rotation, cad qu'en plus de decaler, il faut reinjecter les bits sortant de l'autre cote, exemple:

0x0001 si rotation a droite, devient: 0x8000

Une instruction assembleur (le ROR/ROL) nous permet de faire ca, mais j'arrive pas a l'utiliser!!

(voir forum assembleur)

**fveysseire** · 10/07/2006, 15h23

Envoyé par pierabobl

0x0001 si rotation a droite, devient: 0x8000

Quand tu fais une rotation je ne vois pas comment tu peux faire pour passer de 0x0001 à 0x8000.

ce serais plus logique que 0x0001 devienne 0xF000.

La représentation la plus simple pour les rotations reste le binaire:

tu veux passer de :

00 00 01 01 à 10 00 00 10

le ROR et le ROL doivent avoir une correspondance en C j'investigue ...

**fveysseire** · 10/07/2006, 15h29

Je pense que pour la rotation vers la gauche tu devra te servir des décalages simple avec les retenues.

retenues ou overflow comme tu préfère (mais je ne me souviens plus trop du fopnctionnement de l'overflow et de sa mise en pratique

)

**fveysseire** · 10/07/2006, 15h34

Il faut bien faire attention aux mots que tu utilise . Dans ton intitulé tu parle de rotation de bits et dans ton exemple il est question d'hexadecimal....

**pierabobl** · 10/07/2006, 15h50

Ok, je vais essayer d'etre plus clair.

en binaire, la rotation droite d'un octet 0000 0001 donnerait:
1000 0000

en pratique j'aurais plutot besoin d'un mot de plusieurs octet c'est pour ca que je l'ai mit en hexa

**Jean-Marc.Bourguet** · 10/07/2006, 16h07

Envoyé par pierabobl

Est ce que quelqu'un sais si il est possible de faire une rotation de bits sur une valeur quelconque, en C.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
unsigned rotate_right(unsigned x, int count)
{
    // assume unsigned has no padding bits
    int const unsigned_bit_count = CHAR_BIT * sizeof unsigned;
    count %= unsigned_bit_count;
    if (count < 0)
        count += unsigned_bit_count;
    // but don't assume anything about << unsigned_bit_count
    if (count == 0)
        return x;
    else
        return (x >> count) | (x << unsigned_bit_count-count);
}

**fveysseire** · 10/07/2006, 16h08

A ce moment la si tu veux faire des rotation sur des octets utilise des word et fais comme indiqué ci dessus.

C'est à dire tu as un octet genre en Hexa 0xA5

Donc 0xA5 ca donne en binaire 1010 0101

Tu veux faire une rotation vers la gauche.
tu mets ton octet dans un word (initialisé à zero).

Ca donne 0000 0000 1010 0101.

Tu fais des décalages simples à gauche et si tu as quelque chose de la forme :

0000 0001 0100 1010 tu ajoute un cela te donne une rotation vers la gauche.

tu peux utiliser ce procédé pour les rotations à droite en mettant ton octet dans le poids fort d'un word

**fveysseire** · 10/07/2006, 16h08

Sorry Jean-Marc à poster avant, j'avais pas vu.

**pierabobl** · 10/07/2006, 16h17

Merci merci.

Je vais essayer ca.

Je suis tout de meme un peu decu

de pas pouvoir utiliser une seule instruction...

ca remet en cause tous l'interet du programme. (qui doit avant tout etre rapide)

pourquoi toujours + vite ...

**CGi** · 10/07/2006, 17h59

Si tu n'as pas de contraite de portabilité tu peux peut-être utiliser l'assembleur directement ça sera probablement plus rapide dans ce cas là.

Par exemple :
pour des unsigned char

Code :

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

1
2
3
4
5
6
7
8
9
 
unsigned char rotate_right(unsigned char x, size_t count)
{
    asm {
         MOV ECX,count
         MOV AL,x
         ROR AL,CL
     }
}

pour des unsigned int

Code :

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

1
2
3
4
5
6
7
8
9
 
unsigned rotate_right(unsigned x, size_t count)
{
    asm {
         MOV ECX,count
         MOV EAX,x
         ROR EAX,CL
       }
}

gl · 10/07/2006, 19h05

Envoyé par fveysseire

Quand tu fais une rotation je ne vois pas comment tu peux faire pour passer de 0x0001 à 0x8000.

ce serais plus logique que 0x0001 devienne 0xF000.

Et par quel miracle ?

**Pragmateek** · 10/07/2006, 19h15

Code :

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

return (x >> count) | (x << unsigned_bit_count-count);

Est-ce que le standard garantit que les opérandes de "|" sont complètement évalués avant l'opération "|", évitant des effets de bord gênant?

**rigobert** · 10/07/2006, 19h27

Envoyé par seriousme

Code :

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

return (x >> count) | (x << unsigned_bit_count-count);

Est-ce que le standard garantit que les opérandes de "|" sont complètement évalués avant l'opération "|", évitant des effets de bord gênant?

Je ne suis pas sûr de comprendre la question, mais il y aura problème si les décalages demandés sont négatifs, supérieurs à 31 sur une architecture 32-bit ou supérieurs à 63 sur une architecture 64-bit. Dans ces cas, les résultats des décalages sont à priori indéterminés.

**Jean-Marc.Bourguet** · 10/07/2006, 19h34

Envoyé par seriousme

Code :

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

return (x >> count) | (x << unsigned_bit_count-count);

Est-ce que le standard garantit que les opérandes de "|" sont complètement évalués avant l'opération "|",

Oui.

évitant des effets de bord gênant?

Quels effets de bord?

**Jean-Marc.Bourguet** · 10/07/2006, 19h35

Envoyé par rigobert

Je ne suis pas sûr de comprendre la question, mais il y aura problème si les décalages demandés sont négatifs, supérieurs à 31 sur une architecture 32-bit ou supérieurs à 63 sur une architecture 64-bit. Dans ces cas, les résultats des décalages sont à priori indéterminés.

Et comment veux-tu avoir de tels decalages avec la maniere dont je les calcule?

**rigobert** · 10/07/2006, 19h40

Envoyé par pierabobl

Merci merci.

Je vais essayer ca.

Je suis tout de meme un peu decu

de pas pouvoir utiliser une seule instruction...

ca remet en cause tous l'interet du programme. (qui doit avant tout etre rapide)

pourquoi toujours + vite ...

C'est en effet une petite lacune du C, alors que la plupart des processeurs implémentent le ROR et le ROL depuis bien longtemps (déjà à l'époque des cpu 8-bit...).
Il n'y a hélas pas de solution idéale pour pallier à ce manque si on veut à la fois un code rapide et portable.
Et même si la portabilité n'est pas cruciale, attention: l'assembleur en ligne n'est pas toujours plus rapide que du code compilé (problème de la discontinuité de l'environnement de l'optimiseur).

**CGi** · 10/07/2006, 20h23

Envoyé par rigobert

attention: l'assembleur en ligne n'est pas toujours plus rapide que du code compilé (problème de la discontinuité de l'environnement de l'optimiseur).

Effectivement, mais dans ce cas il y en a une.
Je viens de tester sur une boucle executé 10000000 de fois

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
unsigned rotate_right_2(unsigned x, int count)
{
    // assume unsigned has no padding bits
    int const unsigned_bit_count = CHAR_BIT * sizeof(unsigned);
    count %= unsigned_bit_count;
    if (count < 0)
        count += unsigned_bit_count;
    // but don't assume anything about << unsigned_bit_count
    if (count == 0)
        return x;
    else
        return (x >> count) | (x << unsigned_bit_count-count);
}

temps = 400ms

Code :

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

1
2
3
4
5
6
7
8
unsigned rotate_right(unsigned x, size_t count)
{
    asm {
         MOV ECX,count
         MOV EAX,x
         ROR EAX,CL
       }
}

temps = 70ms

(Sur un P4 2GHz)

**Jean-Marc.Bourguet** · 10/07/2006, 20h59

Il ne faut quand même pas trops sous-estimer les compilateurs. Si on admet un comportement non spécifié, compiler ceci:

Code :

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

1
2
3
4
5
unsigned rotate_right(unsigned x, size_t count)
{
  int const unsigned_bit_count = CHAR_BIT * sizeof(unsigned);
  return (x >> count) | (x << unsigned_bit_count-count);
}

avec gcc 2.95 (la plus vieille version que j'ai) 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
	.file	"rot.c"
	.version	"01.01"
gcc2_compiled.:
.text
	.align 16
.globl rotate_right
	.type	 rotate_right,@function
rotate_right:
	movl 8(%esp),%ecx
	movl 4(%esp),%eax
	rorl %cl,%eax
	ret
.Lfe1:
	.size	 rotate_right,.Lfe1-rotate_right
	.ident	"GCC: (GNU) 2.95.4 20011002 (Debian prerelease)"

mat.M · 10/07/2006, 21h24

Excepté la solution de CGI je ne vois pas autrement; peut- être avec des champs de bit...

Mais il faut faire tout un traitement avec des champs de bits..

**Emmanuel Delahaye** · 10/07/2006, 22h02

Envoyé par pierabobl

Est ce que quelqu'un sais si il est possible de faire une rotation de bits sur une valeur quelconque, en C.

Oui, mais pas directement. Il faut sauvegarder le bit qui va être ejecté faire le décalage et le réintroduire à la main...

OK, c'est pas terrible, mais en version portable, y'a pas mieux (peut être qu'un compilateur très malin detecterait la manoeuvre et mettra un ROL ou ROR...).

Evidemment, tu peux mettre de l'assembleur en ligne, mais je n'ai rien dit...

rotation de bits

C

Discussions similaires

Partager

Partager