2011-09-23 Le raid5 et le «ou» exclusif

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)

http://www.k1ka.be/pics/xor/Groucho.png http://www.k1ka.be/pics/xor/Chico.png http://www.k1ka.be/pics/xor/Harpo.png http://www.k1ka.be/pics/xor/Zeppo.png

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

http://www.k1ka.be/pics/xor/Groucho.pnghttp://www.k1ka.be/pics/xor/Chico.pnghttp://www.k1ka.be/pics/xor/Harpo.pnghttp://www.k1ka.be/pics/xor/Zeppo.png

= http://www.k1ka.be/pics/xor/xxx.png

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

http://www.k1ka.be/pics/xor/xxx.pnghttp://www.k1ka.be/pics/xor/Chico.pnghttp://www.k1ka.be/pics/xor/Harpo.pnghttp://www.k1ka.be/pics/xor/Zeppo.png

= http://www.k1ka.be/pics/xor/Groucho.png

Magique, non ?

Le script Perl

  #!/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;

Le programme Pascal

  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.

Footnotes:

1. Sous Linux, un ensemble d'utilitaires intitulé netpbm «inclue la conversion depuis/vers de nombreux formats différents. Il y a plus de 220 outils séparés dans ce paquet, incluant des convertisseurs pour plus de 80 formats graphiques.» http://packages.debian.org/lenny/netpbm.