On m'a appris que la fonction logique xor («ou» exclusif) était à la base du principe du RAID 5... Sans entrer dans le détail, il suffit de savoir que si on dispose par exemple de 4 disques A,B,C,D, on peut en utiliser un cinquième X qui sera le résultat de l'opération
A xor B xor C xor D -> X
Si on perd le disque A, on pourra le reconstituer en effectuant
X xor B xor C xor D -> A
Je trouve ça absolument magique... Pour m'en convaincre, j'ai voulu essayer avec un ensemble de données de taille (très) réduite.
Soit par exemple 4 chaînes de caractères de même longueur (on complète avec des espaces):
'C'est au travers de larges grilles' 'Que les femelles du canton ' 'Admiraient un puissant gorille ' 'Sans souci du quand dira-t-on '
Chaque caractère est encodé sous forme d'un octet représentant son code ASCII. Si on prend les 4 premières lettre de chaque chaîne et qu'on effectue l'opération sur leurs codes binaires, ça donne:
C 67 01000011 Q 81 01010001 A 65 01000001 S 83 01010011 ________ \0 0 00000000
L'opérateur 'xor' renvoie 0 lorsque les deux arguments sont différents, 1 dans le cas contraire. On peut donc l'interpréter comme «est différend de». D'un point de vue typographique, il est souvent représenté par ⊕ [1], bien que l'unicode spécifie un caractère ⊻ [2] explicitement dénommé XOR, mais je ne l'ai rencontré nulle part.
Lorsqu'on opère avec plus de deux arguments, on peut aussi considérer que le résultat est celui de l'addition binaire, mais sans effectuer de report. Dans le cas qui précède, le résultat est par hasard le caractère NULL, le premier de la table ASCII.
Si on effectue l'opération inverse, on retrouve bien le caractère manquant:
\0 0 00000000 C 67 01000011 Q 81 01010001 A 65 01000001 ________ 01010011 -> S
Si on effectue cette opération lettre à lettre pour les 4 phrases, on en obtient une cinquième qu'il n'est pas intéressant d'afficher parce que les caractères qui en résultent sont souvent non imprimables. Le petit programme pascal listé plus bas effectue cette combinaison des quatre lignes en une cinquième, puis l'opération inverse en combinant 5⊕2⊕3⊕4, 1⊕5⊕3⊕4, 1⊕2⊕5⊕4 et 1⊕2⊕3⊕5, ce qui restitue bien les 4 lignes d'origine.
On explique sur Wikipédia qu'un procédé de chiffrement à clé unique fonctionne de la même manière:
Mais ce qui précède n'est pas transcendant comme exemple. Un peu plus amusant, on peut effectuer l'opération avec des images. J'ai utilisé le format pgm[3] parce qu'il s'agit d'un format extrêmement simple sans compression; dans le cas d'un fichier monochrome de moins de 255 valeurs, chaque pixel est représenté par un seul octet. Le flux d'octets est simplement précédé d'un en-tête ASCII spécifiant le type de fichier, sa largeur et sa hauteur, enfin le nombre maximal de couleurs1
$ head -3 Groucho.pgm P5 90 120 255
J'ai donc au départ 4 images de taille identique, Groucho.pgm, Chico.pgm, Harpo.pgm et Zeppo.pgm (comme il n'y a pas de compression, les fichiers ont exactement la même taille également)
et j'en produit une cinquième au moyen du script qui suit. Encore une fois, on effectue un xor octet à octet de toutes les images. Il faut juste «sauter» ceux correspondant aux caractères de l'en-tête, ce qui permet que le fichier résultant soit toujours conforme à la spécification, et puisse être affiché comme une image (je ne me suis pas cassé la tête, j'ai compté à la main le nombre de caractères de cet en-tête... Il ne faut cependant pas oublier les sauts de lignes).
On passe le nom des 4 fichiers comme arguments, suivi du nom du fichier qui sera créé:
$ ./xor.pl Groucho.pgm Chico.pgm Harpo.pgm Zeppo.pgm xxx.pgm
⊕ ⊕ ⊕
=
Et on se sert de cette curieuse créature pour recréer une image manquante:
$ ./xor.pl xxx.pgm Chico.pgm Harpo.pgm Zeppo.pgm Groucho2.pgm
⊕ ⊕ ⊕
=
Magique, non ?
#!/usr/bin/perl -w use strict; use POSIX qw(:errno_h :fcntl_h); sysopen (F ,$ARGV[0],O_RDONLY) or die "$!"; sysopen (G ,$ARGV[1],O_RDONLY) or die "$!"; sysopen (H ,$ARGV[2],O_RDONLY) or die "$!"; sysopen (I ,$ARGV[3],O_RDONLY) or die "$!"; my $output=$ARGV[4]; open X,">$output"; sysopen (X ,$output,O_WRONLY) or die "$!"; my @byte; my $header; sysread (F,$header,15); # 15: à adapter selon l'en-tête syswrite(X,$header); sysseek(G,15,0); sysseek(H,15,0); sysseek(I,15,0); while (sysread (F, $byte[0],1) ){ sysread(G, $byte[1],1); sysread(H, $byte[2],1); sysread(I, $byte[3],1); my $x = $byte[0] ^ $byte[1] ^ $byte[2] ^ $byte[3]; syswrite(X,$x); } close F; close G; close H; close I; close X;
Program raid5; Type TabPhrases = array [1..5] of string; Var phrases: TabPhrases; i,j,k,l,x: integer; Begin phrases[1] := 'C''est au travers de larges grilles'; phrases[2] := 'Que les femelles du canton '; phrases[3] := 'Admiraient un puissant gorille '; phrases[4] := 'Sans souci du quand dira-t-on '; l := length(phrases[1]); for i := 1 to l do begin // pour chaque position de la ligne... x := ord(phrases[1][i]) // on exécute un xor entre les valeurs xor ord(phrases[2][i]) // de chaque caractère situé à cette xor ord(phrases[3][i]) // position xor ord(phrases[4][i]); phrases[5][i] := chr(x) // le résultat est enregistré dans une end; // 5ème ligne à la position correspodante writeln; //for i := 1 to l do write(phrases[5][i],' '); // affichage éventuel //writeln; // de 5 for k := 1 to 4 do begin // pour chaque ligne... for i := 1 to l do begin // pour chaque position de la ligne... x := 0; for j := 1 to 4 do begin if j <> k then // on fait un xor entre chaque caractère à cette position x := x xor ord(phrases[j][i]) else // SAUF CELUI DE LA LIGNE EN COURS, qu'on remplace par // celui de la ligne 5 x := x xor ord(phrases[5][i]) end; write(chr(x)) end; writeln; end end.