Permuter les bits d'une chaîne de caractere

Version imprimable

13/09/2006, 10h37
Menontona

Permuter les bits d'une chaîne de caractere

Bonjour,

Je cherche a permutter certains bits d'une chaîne de caracteres. Comment acceder a un bits spécifique d'une chaîne en c ?
Il me faudrait l'equivalent du type "bit" mais je ne vois pas comment partir.

Merci d'avance :mouarf:

Menontona
13/09/2006, 10h53
Médinoc

Généralement, on accède aux bits avec les opérateurs bit-à-bit :

Code:

& | ^ << >>
13/09/2006, 11h36
Menontona

Je cherche en fait a permutter ,par exemple, le 1er bit d'une chaîne de caractère avec le 32ème. Je ne sais pas si c'est possible, et je ne vois pas du tout comment m'y prendre. Si qq peut m'éclairer

Merci d'avance
Menontona
13/09/2006, 11h42
Médinoc

Je peux te donner un exemple, si tu me dis ce que tu appelles "premier bit" : Sans doute un bit du premier octet, mais est-ce celui de poids fort ou de poids faible?
13/09/2006, 11h51
Menontona

Je cherche a faire une fonction qui applique l'algorithme de cryptage DES.
En gros on decoupe un texte en bloc de 64 bits.

Chaque bloc subit une transposition initiale suivant la table suivante :
Table de transpositions initiales

58 50 42 34 26 18 10 2
60 52 44 36 28 20 12 4
62 54 46 38 30 22 14 6
64 56 48 40 32 24 16 8
57 49 41 33 25 17 9 1
59 51 43 35 27 19 11 3
61 53 45 37 29 21 13 5
63 55 47 39 31 23 15 7

Nous sommes toujours en possession d'un bloc de 64 bits, mais dont les éléments ont changé de place (par exemple, le bit 1 se retrouve à la place du bit 40, le bit 40 se retrouve à la place du bit 28, etc.).

cf
http://www.gaudry.be/crypto-des.html#steps
13/09/2006, 11h57
Médinoc

ça ne me dit pas dans quel ordre sont numérotés les bits...
13/09/2006, 13h23
Menontona

un bonne exemple vos toujours mieux que des explications farfelues.

Il me semble que "abcd" donne (table ascii) :
01100001 01100010 01100011 01100100

Je doît trouver une technique pour que sa donne:
00100001 01100010 01100011 01100101
(inversé le second bit avec le dernier)

OK, donc, le premier bit est le bit de poids fort du premier octet.

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
/*
 >> est l'opérateur de décalage à droite ( x >> n divise par 2^n )
 << est l'opérateur de décalage à gauche ( x << n multiplie par 2^n )
 1<<n équivaut à 2^n, c'est-à-dire le bit n (en partant du poids faible)
 1<<(7-n) équivaut au bit n en partant du poids fort.
 
 Note: Ici, les bits sont numérotés à partir de zéro (0), pas de un (1)
 */
 
//Note: Tu peux sûrement changer cela en macros,
// ou même en fonctions inline si ton compilo le supporte,
// pour aller plus vite.
 
void SetBitTo1(unsigned char *bits, size_t num)
{
//Equivaut a bits[num/8] = bits[num/8] OR (1 << (7-(num % 8)))
// c'est-à-dire          = bits[num/8] OR (bit num%8 en partant du poids fort)
bits[num >> 3] |= (1 << (7-(num & 0x07)));
}
 
void SetBitTo0(unsigned char *bits, size_t num)
{
//Equivaut a bits[num/8] = bits[num/8] AND NOT (1 << (7-(num % 8)))
// c'est-à-dire          = bits[num/8] AND NOT (bit num%8 en partant du poids fort)
bits[num >> 3] &= ~(1 << (7-(num & 0x07)));
}
 
int GetBit(unsigned char const *bits, size_t num)
{
//Equivaut a bits[num/8] AND (1 << (7-(num % 8)))
// c'est-à-dire          = bits[num/8] AND (bit num%8 en partant du poids fort)
return ( bits[num >> 3] & (1 << (7-(num & 0x07))) != 0);
}

Note : Je n'ai pas testé, mais ça doit être ça.
Ainsi, pour inverser les bits "2" et "32":

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void InverserBits(unsigned char *bits, a, b)
{
int bitA = GetBit(bits, a-1);
int bitB = GetBit(bits, b-1);
 
if(bitA)
    SetBitTo1(bits, b-1);
else
    SetBitTo0(bits, b-1);
 
if(bitB)
    SetBitTo1(bits, a-1);
else
    SetBitTo0(bits, a-1);
}
 
void main()
{
unsigned char bits[] = { 0x61, 0x62, 0x63, 0x64 };
InverserBits(bits, 2, 32);
}

Un truc qui peut être plus simple, avec l'opérateur XOR (dit "OU Exclusif").

a XOR 1 = NOT a
a XOR 0 = a

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void ChangeBit(unsigned char *bits, size_t num)
{
//Equivaut a bits[num/8] = bits[num/8] XOR (1 << (7-(num % 8)))
// c'est-à-dire          = bits[num/8] XOR (bit num%8 en partant du poids fort)
bits[num >> 3] ^= (1 << (7-(num & 0x07)));
}
 
void InverserBits(unsigned char *bits, a, b)
{
int bitA = GetBit(bits, a-1);
int bitB = GetBit(bits, b-1);
 
//Si les deux bits sont identiques, inutile de modifier quoi que ce soit
//S'ils sont différents, on les change tous les deux:
if(bitA != bitB)
	{
	ChangeBit(bits, a-1);
	ChangeBit(bits, b-1);
	}
}

13/09/2006, 14h02
Menontona

Merci je vais etudier sa 8O 8O
13/09/2006, 14h24
Menontona

Mouarf, je capte pas :
bits[num >> 3]
& (1 << (7-(num & 0x07)))
!= 0);

Si tu pouvais me commenter un peu plus sa m'aiderait :roll:

bits[num >> 3]
Fais un decalage sur l'index (num)? ou qq chose d'autre
13/09/2006, 15h01
fearyourself
Citation:

Envoyé par Menontona

Mouarf, je capte pas :
bits[num >> 3]
& (1 << (7-(num & 0x07)))
!= 0);

Si tu pouvais me commenter un peu plus sa m'aiderait :roll:

bits[num >> 3]
Fais un decalage sur l'index (num)? ou qq chose d'autre

Il en a mis :
Code:

1 2 3 //Equivaut a bits[num/8] = bits[num/8] XOR (1 << (7-(num % 8))) // c'est-à-dire = bits[num/8] XOR (bit num%8 en partant du poids fort)
Jc
13/09/2006, 15h12
Menontona

..
13/09/2006, 15h13
Menontona

Citation:

Envoyé par fearyourself

Il en a mis :
Jc

Oui c'est pour sa:

Citation:

Envoyé par Menontona

Si tu pouvais commenter un peu plus sa m'aiderait :roll:

Mais sinon merci, je pense que j'arriverais a m'en sortir. (ds cb de temps :aie: )
13/09/2006, 15h30
Médinoc

num >> 3 signifie "num décalé à droite de 3 bits", donc "num divisé trois fois par 2" (num divisé par 2³)
---> Donc, cela équivaut à num/8.

Et je divise num par 8 car sous pas mal d'architectures, il y a 8 bits dans un unsigned char.
Et pour le bit correspondant dans l'octet, je prends le reste de la division par 8...