Discussion :

[Menontona]

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


Menontona

[Médinoc]

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

Code :

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

& | ^ << >>

[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

[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?

[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

[Médinoc]

ça ne me dit pas dans quel ordre sont numérotés les bits...

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

[Médinoc]

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

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

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

[Médinoc]

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 :

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

[Menontona]

Merci je vais etudier sa

[Menontona]

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

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


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

[fearyourself]

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

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


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

Il en a mis :

Code :

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

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

[Menontona]

..

[Menontona]

Il en a mis :
Jc

Oui c'est pour sa:

Si tu pouvais commenter un peu plus sa m'aiderait

Mais sinon merci, je pense que j'arriverais a m'en sortir. (ds cb de temps )

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