Rotation de 4 bits

Version imprimable

15/06/2007, 11h42
ozyamdias

Rotation de 4 bits

Bonjour à tous,

Voilà j'ai un petit soucis dans mon code.
Dans l'éxecution de mon programme (en C) je dois effectuer une rotation
par quartets d'une chaine de caractères.
Voilà l'exemple :
1er carac 2eme carac 3eme carac
aaaa bbbb | cccc dddd | eeee ffff

Une fois la rotation effectuée la chaine à cette tête là :
1er carac 2eme carac 3eme carac
ffff aaaa | bbbb cccc | dddd eeee

et là j'avoue que je sêche un peu... auriez vous quelques idées ?

Merci beaucoup
Romain
15/06/2007, 11h48
Nemerle

Citation:

Envoyé par ozyamdias

Bonjour à tous,

Voilà j'ai un petit soucis dans mon code.
Dans l'éxecution de mon programme (en C) je dois effectuer une rotation
par quartets d'une chaine de caractères.
Voilà l'exemple :
1er carac 2eme carac 3eme carac
aaaa bbbb | cccc dddd | eeee ffff

Une fois la rotation effectuée la chaine à cette tête là :
1er carac 2eme carac 3eme carac
ffff aaaa | bbbb cccc | dddd eeee

et là j'avoue que je sêche un peu... auriez vous quelques idées ?

Merci beaucoup
Romain

bourrin: x= (20<<x)+((4<<x)>>8)
15/06/2007, 11h51
ozyamdias

Citation:

Envoyé par Nemerle

bourrin: x= (20<<x)+((4<<x)>>8)

Merci de ta réponse,
mais je dois dire que je ne comprend pas beaucoup :(
x correspond au caractère courant ? et les nombres 20, 4 et 8...
15/06/2007, 12h00
pseudocode

Citation:

Envoyé par Nemerle

bourrin: x= (20<<x)+((4<<x)>>8)

20<<X 8O

ca serait pas plutot x<<20 ??
15/06/2007, 12h02
ozyamdias

Citation:

Envoyé par pseudocode

20<<X 8O

ca serait pas plutot x<<20 ??

Oui voila je ne comprend pas bien, et d'ailleurs pourquoi 20 ?
(l'algo à toujours été ma faiblesse en programmation :roll: )
15/06/2007, 13h16
droggo

Jia,

Là, j'ai un sérieux doute sur toutes les réponses.

En effet

Citation:

Envoyé par ozyamdias

Dans l'éxecution de mon programme (en C) je dois effectuer une rotation par quartets d'une chaine de caractères.

Et si on peut faire la rotation d'une chaîne de caractères comme le font toutes les réponses, alors je suis probablement le pape. :mouarf:

Mais bon, d'un autre côté le titre du sujet

Citation:

Envoyé par ozyamdias

Rotation de 4 bits

ne correspond pas a priori à un décalage d'une chaîne. :D
15/06/2007, 14h12
Senyk

Si je comprends bien on a 3 char (x,y,z).

Dans ce cas, j'utiliserai des masques et faire l'ensemble doucement pas à pas

par exemple le "aaaa" de ton exemple correspond aux 4 bits de poids forts du premier char donc

Code:

char aaaa = (0xf0 & x) >> 4;

tu peux faire le reste de la même manière...

ensuite tu reconstruit tes char, le premier char x deviendra par exemple :

Code:

x = (ffff << 4) | aaaa
15/06/2007, 14h24
ozyamdias

En faite je vais préciser un peu.
Je me suis mal exprimer, l'exemple que je donnais était là pour montrer juste ce que je voudrai faire.
J'ai une chaine de caractère, de longueur variable.
Ce que j'aimerais faire (et là ou je bloque :? ), c'est décaler de 4 bits toute la chaine et que les derniers 4 bits viennent à la places des premiers :
je reprend l'exemple que j'ai donné plus haut, la chaine :
aaaa bbbb . cccc dddd . eeee ffff . gggg hhhh . iiii jjjj ....
devienne :
jjjj aaaa . bbbb cccc . dddd eeee . ffff gggg . hhhh iiii
(j'ai groupé la chaine 4 bits par 4 bits pour que ce soit plus explicite)

je bosse dessus depuis un petit moment et c'est vrai que je bloque pas mal.
15/06/2007, 14h28
droggo

Dio,

Citation:

Envoyé par ozyamdias

En faite je vais préciser un peu.
Je me suis mal exprimer, l'exemple que je donnais était là pour montrer juste ce que je voudrai faire.
J'ai une chaine de caractère, de longueur variable.
Ce que j'aimerais faire (et là ou je bloque :? ), c'est décaler de 4 bits toute la chaine et que les derniers 4 bits viennent à la places des premiers :
je reprend l'exemple que j'ai donné plus haut, la chaine :
aaaa bbbb . cccc dddd . eeee ffff . gggg hhhh . iiii jjjj ....
devienne :
jjjj aaaa . bbbb cccc . dddd eeee . ffff gggg . hhhh iiii
(j'ai groupé la chaine 4 bits par 4 bits pour que ce soit plus explicite)

je bosse dessus depuis un petit moment et c'est vrai que je bloque pas mal.

Ouais, c'est bien ce qu'il me semblait, il fallait préciser un peu.
15/06/2007, 14h46
ozyamdias

Citation:

Envoyé par droggo

Dio,

Ouais, c'est bien ce qu'il me semblait, il fallait préciser un peu.

Effectivement désolé, autant pour ma precision :sm:

Voilà comment j'ai fait avec l'aide d'un ami :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void RotationQuartet(char *Chaine, int TailleChaine)
{
	int		iIndex = 0;
	char	*ChaineDecalee = NULL;
 
	// Allocation de la mémoire pour la chaine "rotationnée"	
	ChaineDecalee = (char *)malloc(TailleChaine*sizeof(char)+1);
 
	// Rotation quarter par quartet vers la droite
	// On sauvegarde les quatres derniers bits que l'on place au début de la nouvelle chaine
	for(iIndex=0; iIndex<4; iIndex++)
		ChaineDecalee[iIndex] = Chaine[TailleChaine-4+iIndex];	
 
	// Maintenant on décale tous les autres bits de la chaine à envoyée
	strncat(ChaineDecalee, Chaine, TailleChaine-4);
 
	// On fait pointer la nouvelle chaine sur l'ancienne tout en libérant la mémoire occupée
	Chaine = NULL;
	Chaine = ChaineDecalee;
	free(ChaineDecalee);
}

Fie,
Citation:
Envoyé par ozyamdias
Voilà comment j'ai fait avec l'aide d'un ami :
Code:

1 2 3 4 5 6 7 void RotationQuartet(char *Chaine, int TailleChaine) {... // On fait pointer la nouvelle chaine sur l'ancienne tout en libérant la mémoire occupée Chaine = NULL; Chaine = ChaineDecalee; free(ChaineDecalee); }
Là, tu as un problème.

Quid de l'ancienne mémoire de Chaine ?
Puis comme Chaine == ChaineDecalee, le
free(ChaineDecalee);
fait que Chaine n'est plus valide non plus.

De plus, même sans ces problèmes, le fait d'affecter une nouvelle valeur au pointeur Chaine ne change pas sa valeur dans le programme appelant (il faudrait passer l'adresse du pointeur, pas le pointeur).

15/06/2007, 16h08
Nemerle

Citation:

Envoyé par pseudocode

20<<X 8O

ca serait pas plutot x<<20 ??

oui, (20<<x)+((4<<x)>>8) est déconnant, zut j'ai écris trop vite!

Son objet est représenté par 24 bits:

décalage à gauche de x de 20 bits: (20<<x) donne ffff 0000 ... 0000
puis on reprend x:
décalage de x à droite de 4 bits: 0000 aaaa ... eeee

Et on additionne le tout: (20<<x)+(x>>4)
15/06/2007, 16h28
ozyamdias

Citation:

Envoyé par droggo

Fie,

Là, tu as un problème.

Quid de l'ancienne mémoire de Chaine ?
Puis comme Chaine == ChaineDecalee, le
free(ChaineDecalee);
fait que Chaine n'est plus valide non plus.

De plus, même sans ces problèmes, le fait d'affecter une nouvelle valeur au pointeur Chaine ne change pas sa valeur dans le programme appelant (il faudrait passer l'adresse du pointeur, pas le pointeur).

Tu as raison mais l'ancienne chaine je n'en ai pas besoin en faite.
Mais de toute facon je vois un gros probleme, tres tres bete :aie:
En faite je faire un décalage sur 4 bits et moi j'ai pas fait ce
mouarfff :help:

Bonjour,

je propose ça, qui a l'air de fonctionner :

Deux tests :

Citation:

75 6E 20 73 69 6D 70 6C 65 20 74 65 73 74 un simple test
47 56 E2 07 36 96 D7 06 C6 52 07 46 57 37 GVâ6–×ÆRFW7

75 6E 20 73 69 6D 70 6C 65 20 74 65 73 74 21 un simple test!
17 56 E2 07 36 96 D7 06 C6 52 07 46 57 37 42 Vâ6–×ÆRFW7B

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
 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
char* RotateStringByNibble(char* string, char* shiftedString);
 
int main(void)
{
    char test[] = "un simple test!";
    char* newstring = NULL;
 
    newstring = malloc(sizeof(test));
 
    RotateStringByNibble(test, newstring);
 
    free(newstring);
 
    return 0;
 
}
/* attention le \0 de la chaîne originale n'est pas préservé dans la chaîne en sortie */
char* RotateStringByNibble(char* string, char* shiftedString)
{
    size_t lenstr;
    unsigned int i;
    char a, b, c;
 
    lenstr = strlen(string);
 
    for (i = 0; i < lenstr - 1; i++)
    {
        a = string[i];
        b = string[i+1];
 
        a = (a & 0x0F) << 4;
        b = (b & 0xF0) >> 4;
 
        c = a | b;
 
        shiftedString[i+1] = c;
 
    }
 
    a = string[0];
    b = string[lenstr-1];
 
    a = (a & 0xF0) >> 4;
    b = (b & 0x0F) << 4;
 
    c = a | b;
 
    shiftedString[0] = c;
 
    return shiftedString;
 
}

Merci, j'en étais arrivé à ce code ci, qui je pense ressemble fort au tient :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
void RotateString(char *psSrc, unsigned int uiSize, char *psDst)
{
   int iIndex = 0;
 
   for(iIndex = 0; iIndex<(uiSize -1); iIndex++)
   {
       if(iIndex == 0)
          psDst[iIndex] = (psSrc[uiSize-4+iIndex]&0x0F) + ((psSrc[iIndex]&0xF0)>>4);
       else
          psDst[iIndex] = (psSrc[iIndex-1]&0x0F) + ((psSrc[iIndex]&0xF0)>>4);
 
   }
   // On ajout ou non le caractère de fin de chaine
}

voilà je pense que ca doit faire la meme chose que ton code, a verifier :)
merci

Rom

15/06/2007, 17h41
droggo

Hia,

Citation:

Envoyé par ozyamdias

Tu as raison mais l'ancienne chaine je n'en ai pas besoin en faite.

Relis quand même ce que j'ai écrit :
- tu provoques une fuite mémoire
- le programme appelant ne reçoit pas la nouvelle chaîne, que de toute manière tu invalides en libérant la mémoire.

On peut aussi organiser la chaîne en file circulaire (c'est une structure de données FIFO classique en algo ça traîne dans tous les manuels).
Il suffit alors de 'consommer' à chaque fois 4 caractères en déplaçant la tête de file de 4 positions.
Pour avoir la chaîne permutée il suffit à chaque fois de lister la file.

Voici un exemple en C avec des entiers, il n'y a qu'à changer les int en char et écrire une fonction rotation correspondant à 4 appels de retrieve

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
 
typedef struct
{ int taille;
  int index;
  int contenu;
  int* base;
}FileCirc;
 
 
void InitCirc ( FileCirc * pfc, int S)
{ pfc->taille=S;
  pfc->index=0 ;
  pfc->contenu=0;
  pfc->base= (int *)malloc(S*sizeof(int));
}
 
void Destruct (FileCirc * pfc)
{free (pfc->base);}
 
 
void Store(FileCirc * pfc, int n)
{ int storindex;
	if(pfc->contenu==pfc->taille) {printf ("Impossible: File pleine"); return;}
 else
	{storindex= (pfc->index + pfc->contenu)%pfc->taille;
     *(pfc->base+storindex)=n;
	 pfc->contenu++;
	}
 
}
 
int Retrieve (FileCirc * pfc)
{ 	int result;
	if(pfc->contenu==0) {printf("Impossible: Pile vide"); return 0;}
  else
  { result=*(pfc->base+pfc->index);
    pfc->contenu--;
    pfc->index ++;
	if (pfc->index==pfc->taille) pfc->index=0;
  }
  return result;
}
 
 
void ListeTout (FileCirc * pfc)
{ int indexcourant= pfc->index;
   int i;
   for (i=0; i<pfc->contenu; i++)
   { printf("\n%d", *(pfc->base+indexcourant));
     indexcourant++;
	 if (indexcourant== pfc->taille) indexcourant=0;
   }
}

15/06/2007, 21h01
ozyamdias

Merci pour vos réponse :)
Je vais voir pour ma fuite de mémoire et étudier le système de buffer tournant.
:merci: