rotation de bits

Version imprimable

10/07/2006, 15h16
pierabobl

rotation de bits

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!!:oops: (voir forum assembleur)
10/07/2006, 15h23
fveysseire

Citation:

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 ...
10/07/2006, 15h29
fveysseire

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 :oops: )
10/07/2006, 15h34
fveysseire

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....;)
10/07/2006, 15h50
pierabobl

rotation de bits

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

Citation:

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:

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

10/07/2006, 16h08
fveysseire

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 :D
10/07/2006, 16h08
fveysseire

Sorry Jean-Marc à poster avant, j'avais pas vu.
10/07/2006, 16h17
pierabobl

rotation de Bits

Merci merci.

Je vais essayer ca.

Je suis tout de meme un peu decu :cry: 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 ... :roll:

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:

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:

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

10/07/2006, 19h05
gl

Citation:

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 ?
10/07/2006, 19h15
Pragmateek

Code:

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?
10/07/2006, 19h27
rigobert

Citation:

Envoyé par seriousme

Code:

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.
10/07/2006, 19h34
Jean-Marc.Bourguet

Citation:

Envoyé par seriousme

Code:

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.

Citation:

évitant des effets de bord gênant?

Quels effets de bord?
10/07/2006, 19h35
Jean-Marc.Bourguet

Citation:

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?
10/07/2006, 19h40
rigobert

Citation:

Envoyé par pierabobl

Merci merci.

Je vais essayer ca.

Je suis tout de meme un peu decu :cry: 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 ... :roll:

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

Citation:

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:

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:

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)

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

Code:

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:

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)"

10/07/2006, 21h24
mat.M

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..
10/07/2006, 22h02
Emmanuel Delahaye

Citation:

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...
10/07/2006, 22h04
Emmanuel Delahaye

Citation:

Envoyé par fveysseire

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

ben si...

Citation:

ce serais plus logique que 0x0001 devienne 0xF000.

ben non...
10/07/2006, 22h08
Emmanuel Delahaye
Citation:
Envoyé par Jean-Marc.Bourguet

Il ne faut quand même pas trops sous-estimer les compilateurs.<...>avec gcc 2.95 (la plus vieille version que j'ai) donne:

Code:

1 2 3 4 5 rotate_right: movl 8(%esp),%ecx movl 4(%esp),%eax rorl %cl,%eax ret
Excellent !
11/07/2006, 08h24
fveysseire

Citation:

Envoyé par Emmanuel Delahaye

ben si...

ben non...

Autant pour moi on passe bien de 0x0001 à 0x8000 en faisant une rotation à droite.

Désolé pour mon erreur.:oops:
11/07/2006, 11h31
pierabobl

Rotation de bits

Merci a tous

Je vais essayer de bidouiller quekchose, avec NASM, vu que l'assembleur AS de gcc commence a me :oops:

Code:

1
2
#define rotr(x,n)   (((x) >> ((int)(n))) | ((x) << (32 - (int)(n))))
#define rotl(x,n)   (((x) << ((int)(n))) | ((x) >> (32 - (int)(n))))

Que pensez-vous de ça ? Trouvé sur le net ;)

11/07/2006, 11h55
Jean-Marc.Bourguet
Citation:
Envoyé par KiLVaiDeN

Code:

1 2 #define rotr(x,n) (((x) >> ((int)(n))) | ((x) << (32 - (int)(n)))) #define rotl(x,n) (((x) << ((int)(n))) | ((x) >> (32 - (int)(n))))

Que pensez-vous de ça ? Trouvé sur le net ;)
Quelle est la difference avec ce que j'ai propose? A part bien sur les constantes magiques et l'utilisation de nombres signes pour des decalages, deux choses qui peuvent avoir des effets inattendus.

Et ce sont des macros evaluant deux fois leurs arguments. Autre source d'effets inattendus.
11/07/2006, 12h00
KiLVaiDeN

Ta version est plus propre c'est une certitude, mais si la personne doit faire énormément de rotations ( dans une boucle ) ça fera un appel de fonction à chaque fois ( enfin un call ) ?

La macro permet peut-être de gagner en vitesse non ?
11/07/2006, 12h07
pierabobl

rotation de bits

Merci beaucoup a tous!

Je crois que je vais utiliser la macro, c'est simple et ca marche

C'est pas que pour le plaisir des rotation, il y a aussi un alogorithme qui attend ...

Encore merci a vous tous:D
11/07/2006, 12h55
KiLVaiDeN
Citation:

Envoyé par pierabobl

Merci beaucoup a tous!

Je crois que je vais utiliser la macro, c'est simple et ca marche

C'est pas que pour le plaisir des rotation, il y a aussi un alogorithme qui attend ...

Encore merci a vous tous:D

La solution de Jean-Marc.Bourguet reste la plus propre cependant, et en la mettant "inline" tu auras des bonnes performances
Code:

1 2 3 4 5 6 7 8 9 10 #ifndef INLINE # if __GNUC__ # define INLINE extern inline # else # define INLINE inline # endif #endif INLINE int max(int a, int b) { return a > b ? a : b; }
Un exemple de fonction inline..
12/07/2006, 11h17
Menthe_a_l_eau

De toute manière , un appel propre un fichier ASM sera plus rapide !

La solution ideale est la compilation conditionelle en c et ASM des differents processeur utilisés ( #define x86, arm ... ).

Nota : Comme cité precedement, il faut prendre avec pincettes l'asm en ligne (pas forcement plus rapide du au problèmes cités). Le mieux restera d'analyser son code en mode desassemblé après compil pour optimiser tout cela :mouarf:

Fuseau horaire GMT +2. Il est actuellement 14h17.