[C TOTW 6] Xor tricks

[ark]

Ploplation!

J'ai pas trop trop de temps en ce moment, je viens de reprendre les cours, toussa... Du coup je vais quand même essayer de maintenir la fréquence de mes Tip of the week, mais je vous garantie rien. Par ailleurs, avant de commencer, si certains d'entre vous ont des idées de sujets intéressants qu'ils souhaiteraient que j'aborde, faites le moi savoir sur IRC ou sur le forum en MP. ;)

Bref, trêve de bavardage, on va s'attaquer un peu a l’opérateur bit a bit XOR.

Commençons par la base, c'est quoi cet opérateur ? Tout d'abord, XOR, c'est pour signifier "eXclusive OR". Soit "OU exclusif" en Français. C'est un opérateur, qui va prendre en entrée deux valeurs, et sortir une 3 eme en sortie.

Voici sa table de vérité :

Code :

A   | B   | S
--------------
0   | 0   | 0
0   | 1   | 1
1   | 0   | 1
1   | 1   | 0
--------------
0 = FALSE
1 = TRUE

Dans cette table, A et B sont les entrées, S la sortie.
A savoir egalement, cet operateur est commutatif et associatif.
Bref, mais je ne vais pas détailler plus ici, go wikipedia pour plus d'infos.

Alors, a quoi cette chose peut bien nous servir en C, nous allons le voir tout de suite !

Il faut s'avoir qu'il s'agit d'un operateur bit a bit en C, il va donc s'appliquer sur chaque bits, et non chaque octets, gardez bien ca en tete !

Donc cet operateur, peut nous permettre de reinitialiser une variable a 0, en faisant :

Code C :

a ^= a;

Alors oui, ca a pas l'air tres utiles, mais il faut savoir que ca peut etre pratique dans des systemes embarques, ou sur des architectures avec des processeurs qui font des trucs étranges pour arriver a leurs fin. Mais c'est pas spécialement le tricks que je voulais vous montrer.

Ce que je voulais vous montrer principalement, c'est comment swap deux variables sans variables temporaire.

Je voulais vous faire une démonstration un peu plus mathématique ici, mais il s'avere que ca risque de vous embrouiller plus qu'autre chose, voici donc le code :p

Code C :


#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

void swap(int *a, int *b) {
  if (a == b)
    return;
  *a ^= *b;
  *b ^= *a;
  *a ^= *b;
}

int main(char argc, char *argv[]) {

  int a, b;

  if (argc != 3) {
    fprintf(stderr, "Usage: %s nb1 nb2\n", *argv);
    return 1;
  }
  a = atoi(argv[1]);
  b = atoi(argv[2]);
  fprintf(stdout, "a = %d, b = %d\n", a, b);
  swap(&a, &b);
  fprintf(stdout, "a = %d, b = %d\n", a, b);
  return 0;
}

Le main est la juste pour le plaisir!

/!\ Dans le cas ou a est egal a b, c'est a dire que les deux pointent au meme endroit, dans l'exemple donne dans ce code, on ne va pas pouvoir effectuer la permutation, l'operation XOR va mettre les valeurs pointes par a et par consequent b a 0, ce qui aura pour effet de reset tout a 0.

En detaillant, avec des valeurs, on obtiendrait ceci :

a = 42
b = 1337

Premiere ligne :
a = a ^ b;
<=> a = 42 ^ 1337;

Deuxieme ligne :
b = b ^ a;
<=> b = 1337 ^ (42 ^ 1337)

Mais comme l'operateur XOR est associatif et commutatif, on peut ecrire :
b = 1337 ^ 1337 ^ 42

Et selon la table de verite, 1337 ^ 1337 = 0, soit :
b = 42 ^ 0 = 42

Et troisieme ligne :

a = a ^ b;
<=> a = (42 ^ 1337) ^ 42;
<=> a = 42 ^ 42 ^ 1337;
<=> a = 1337;

Et voila, une façon efficace de conserver un peu de mémoire (oui, 4 bytes c'est pas beaucoup) sur votre machine! :p

Aussi, quand j'aurais plus de temps, je comptes m'attaquer a une autre utilisation de l'operateur XOR, un peu plus touchy cette fois ! :D

[Kiwazaru]

Et voila, une façon efficace de conserver un peu de mémoire (oui, 4 bytes c'est pas beaucoup) sur votre machine! :p

Ce qui est cool c'est qu'on peut économiser beaucoup plus que 4 bytes en mémoire en fait
Prenons l'exemple où nous voulons échanger deux chaînes données par l'utilisateur, alors 2 cas extrêmes s'offrent à nous:

1er Cas: L'utilisateur entre une chaîne de 1000 octets qui prend donc théoriquement 1000+1 octets (null byte) en mémoire. Il entre ensuite une seconde variable de 4 octets (beaucoup plus petite), alors le programme devra créer une variable de 1001 octets pour la première variable, et de 1001 octets pour la deuxième. En effet, même si la valeur que l'on veut coder se code facilement sur un octet, la permutation futur provoquera un overflow si on essaye d'y coder 1001 octets. Une dernière variable, celle-ci temporaire utilisée pour la permutation sera crée avec une taille de 5 octets pour y stocker la plus petite chaîne c'est-à-dire la deuxième chaîne entrée. Ainsi, le programme devra réserver 1001+1001+5 octets en mémoire soit 2007 octets en mémoire.

2ème Cas: L'utilisateur entre une chaîne de 1000 octets qui prend donc théoriquement 1000+1 octets (null byte) en mémoire. Il entre ensuite une seconde variable de 999 octets (aussi grande à 1 octet près), alors le programme devra créer une variable de 1001 octets pour la première variable, et de 1001 octets pour la deuxième. En effet, même si la valeur que l'on veut coder se code sur 1000 octets, la permutation futur provoquera un overflow si on essaye d'y coder 1001 octets. Une dernière variable, celle-ci temporaire utilisée pour la permutation sera crée avec une taille de 1000 octets pour y stocker la plus petite chaîne c'est-à-dire la deuxième chaîne entrée. Ainsi, le programme devra réserver 1001+1001+1000 octets en mémoire soit 3002 octets en mémoire.

Ici on voit bien que dans un certains cas, on augmente pas mal la demande de place mémoire de l'algorithme ( +995 octets en l’occurrence ).
La formule du nombre d'octets en mémoire demandé pour cet algorithme de permutation est donc: 2*(MAX_LEN_VAR+1)+(TMP_LEN_VAR+1);
La formule du nombre d'octets économisé avec la variable temporaire est donc: (MAX_LEN_VAR+1)-(TMP_LEN_VAR+1);

Ici on a donc: 2*(MAX_LEN_VAR+1)+(MIN_LEN_VAR+1) == 2*(1000+1)+(999+1) == 3002 pour le nombre d'octets utilisés en mémoire.
Puis on a: (MAX_LEN_VAR+1)-(TMP+_LEN_VAR+1) == 1001-1000 == 1 pour le nombre d'octets économisés avec la variable temporaire.
Bon, dans ce cas là, avec la simple permutation on économise 1 octet, c'est naze, du coup le XOR permet d'économiser (TMP_LEN_VAR+1)-4 octets (on verra pourquoi -4).

Prenons le code suivant qui ne fonctionne que si c1 et c2 sont de même taille et pour chaque bytes > 0 (sinon ça fait un null byte donc strlen() fuck et renvoit une longueur < à la vraie si il y a une suite):

Code C :


#include <stdio.h>
#include <string.h>

int main( void )
{
   char c1[] = "Bonjour je suis la première chaine.";
   char c2[] = "Bonjour je suis la deuxième chaine.";
   unsigned int len = (strlen(c1) == strlen(c2)) ? strlen(c1) : 0;
    while (len--) {
       c1[len] ^= c2[len];
       c2[len] ^= c1[len];
       c1[len] ^= c2[len];
   }
   printf("Première chaîne: %s\nDeuxième chaîne: %s", c1, c2);
}
 

Output:

Code :

Première chaîne: Bonjour je suis la deuxième chaine.
Deuxième chaîne: Bonjour je suis la première chaine.

Pour les 4 octets non économisés c'est tout simplement le fait que cette solution demande une boucle, qui demande elle-même une variable de type unsigned int, un unsigned char suffisant seulement pour les chaînes de moins de 256+1 caractères alors qu'avec un unsigned int on peut permuter des chaînes allant jusqu'à 2^32+1 caractères.
Bon bien évidemment tout cela n'est que théorique, une chaîne de 2^32 caractère, ça vient un peu d'une autre planète (quoiqu'il doit sûrement y avoir des exemples utiles :')), mais ça reste important.
Du coup, ici on peut économiser au maximum 2^32+1 octets avec une boucle qui admet un unsigned int comme compteur de chaque octets.

Dans l'algorithme ci-dessus, on a bien le même effet que la permutation simple, et que la permutation via XOR sur les entiers.
La longueur des 2 chaînes vaut 36 (et non 35, 'è' est codé différemment), on peut donc appliquer notre formule: 2*(MAX_LEN_VAR+1)+(TMP_LEN_VAR+1); soit 2*(36+1)+(0) == 74, l'algorithme demande donc 74 octets en mémoire.
L'économie par rapport à l'algorithme de permutation basique est donc de: (MAX_LEN_VAR+1)-(TMP_LEN_VAR+1) = (36+1)-(0) soit 37 octets économisés en mémoire.

Un exemple plus concret de l'économie est le suivant: Prenons deux chaîne de 2^32+1 octets en mémoire (cas extrême), appliquons donc l'algorithme de permutation par variable temporaire nous avons alors:
2*(MAX_LEN_VAR+1)+(TMP_LEN_VAR+1) == 2*(2^32+1)+(2^32+1) == 12 884 901 891 soit 12.8849019 gigabytes en mémoire, rien que ça !
(MAX_LEN_VAR+1)-(TMP_LEN_VAR+1) = (2^32+1)-(2^32+1) == 0 octets économisés par la variable temporaire.

Prenons maintenant ce cas, avec la solution de permutation par XOR.
2*(MAX_LEN_VAR+1)+(TMP_LEN_VAR+1) == 2*(2^32+1)+(0) == 8 589 934 594 soit 8.58993459 gigabytes !
((MAX_LEN_VAR+1)-(TMP_LEN_VAR+1))-4 = (2^32+1)-(0) == 4 294 967 297 - 4 == 4 294 967 293 octets, soit 4.29496729 gigabytes économisés par la variable temporaire !
Dans ce cas extrême, la solution du XOR nous économise 4gb de mémoire vive, par rapport à 0 pour la solution de permutation simple.

Le problème est en fait une confrontation: Temps d'exécution VS Demande de mémoire.
Faire l'algorithme:
x -> z
x -> y
z -> y
est bien moins long que fait une boucle pour permuter tous les octets des deux chaînes, alors la question est, quand est-il plus rentable d'utiliser 2^32+1 octets en mémoire pour permuter deux chaînes que de mettre plus de temps pour le faire ?

Il faut bien comprendre, que plus la seconde variable (prenons la seconde variable comme variable universellement plus petite) sera petite, moins l'algorithme de permutation xorée sera rentable. En effet, le rapport temps d'exécution et consommation de mémoire s'égalisera à 4 près lorsque la seconde variable vaudra 4 (3 octets + null byte) et le XOR ne deviendra plus du tout rentable dans l'intervalle [2,3] octets dû à l'utilisation de notre variable unsigned in de 4 octets , ce qui veut dire que pour un certains seuil, la solution de permutation par variable temporaire restera rentable, à partir du moment où le seul sera atteint, il sera donc plus rentable au niveau de la consommation de la mémoire d'effectuer une permutation xorée, en conséquence le temps d'exécution ne fera qu'augmenter contrairement à l'algorithme de permutation par variable temporaire qui se stabilisera mais qui prendra de plus en plus de mémoire.

La solution est donc relative à l'équipement sur laquelle elle est utilisée, et le type de cette solution en découlera.
Prenons un exemple, sur un PC moderne disposant d'une quantité de mémoire vive plus que respectable, le problème sera principalement le temps d'exécution, aujourd'hui le problème n'est plus le même qu'avant, c'est-à-dire la consommation mémoire, mais plus généralement le temps d'exécution. Qui ne s'est jamais énervé devant un programme qui met du temps à faire ce qu'il doit faire sans même se soucier de voir si il y avait une conséquence sur sa taille en mémoire ?
Le second exemple le plus probable, à mon sens, est celui des systèmes embarqués, qui embarquent moins de mémoire vive, et qui en sont donc plus dépendante.

Cordialement,

[gruik]

j'avoue ne pas avoir tout compris, le cas 2 ressemble étrangement au cas 1 qui plus est, le propos c'est de ré-implémenter strncpy()/memcpy() ?

[ark]

C'est bien beau ton histoire Kiwazaru, mais comme l'a bien dit gruik, si tu veux swap des strings, tu swap les pointeurs, ca sert a rien de recopier l’intégralité des strings.

De plus, dans ton exemple, tu peux éviter d'utiliser les 4 octets qui te servent a parcourir ta string, tout simplement en utilisant les pointeurs.

[Kiwazaru]

Mon exemple est pas assez général, et en effet il suffit d'inverser les pointeurs, mais si on prend l'exemple d'une permutation dans un tableau plus complexe (à plusieurs dimensions par exemple), la permutation des pointeurs ne suffisent plus.
L'exemple que j'ai en tête étant d'inverser une image bitmap: On swap les x octets représentants les y premiers pixels de l'image en haut, avec les x octets représentants les y premiers octets de l'image en bas, et ainsi de suite.

[gruik]

si on prend l'exemple d'une permutation dans un tableau plus complexe (à plusieurs dimensions par exemple), la permutation des pointeurs ne suffisent plus.

tu peux développer ? parce que perso je vois toujours pas le problème

L'exemple que j'ai en tête étant d'inverser une image bitmap: On swap les x octets représentants les y premiers pixels de l'image en haut, avec les x octets représentants les y premiers octets de l'image en bas, et ainsi de suite.

ben dans ces cas là on prépare l'image tranquillement dans un coin et une fois qu'elle est prête on l'affiche, on utilise un buffer pour copier une ligne, on déplace l'autre, on copie la première à l'endroit de la dernière, c'est plus efficace, et si ça l'était pas ça serait de toutes façons bien plus lisible niveau code, quant à l'optimisation d'un effet graphique aussi simple... ça se serait peut-être justifié au début des années 90' (et encore) mais aujourd'hui c'est totalement improbable, si on est limité en mémoire on va bufferiser la copie intermédiaire pour swapper les contenus

[b0fh]

Hello World,

Un truc que je n'ai vu encore mentionné nulle part dans la discussion: les CPU modernes sont superscalaires, ou au moins pipelinés. çad que la lecture des registres en entrée, l'exécution de l'arithmétique, les accès mémoires, et l'écriture du registre de destination, n'ont pas forcément lieu pendant le même cycle.

Sur une telle architecture, le xor swap c'est de la merde: le CPU est forcé d'exécuter les 3 instructions séquentiellement, puisque à chaque étape l'input dépend de l'output d'avant. Avec des mov et un registre intermédiaire, les opérations peuvent (presque) avoir lieu en parallèle.

[Commodor]

Hello World,

Un truc que je n'ai vu encore mentionné nulle part dans la discussion: les CPU modernes sont superscalaires, ou au moins pipelinés. çad que la lecture des registres en entrée, l'exécution de l'arithmétique, les accès mémoires, et l'écriture du registre de destination, n'ont pas forcément lieu pendant le même cycle.

Sur une telle architecture, le xor swap c'est de la merde: le CPU est forcé d'exécuter les 3 instructions séquentiellement, puisque à chaque étape l'input dépend de l'output d'avant. Avec des mov et un registre intermédiaire, les opérations peuvent (presque) avoir lieu en parallèle.

Tu es sûr ? Le pipeline d'instructions permet justement de régler ce genre de problème. Dans un pipeline tu as plusieurs registres (différents de ceux du processeurs) du coup chaque étape de l'instruction est enregistrée dans un registre propre ce qui permet de "court-circuiter" et d'envoyer le contenu du registre en sortie de l'ALU (unité de calcul) vers l'entrée du calcul suivant avant le write back en mémoire (si l'instruction suivante utilisait un registre(variable) de l'instruction précédente).

Du coup passer par une variable temporaire ou directement avec un xor ne devrait pas faire de différence. Le pire pour le pipeline c'est les sauts dans la mémoire (conditions/boucles/jmp/etc) qui rendent invalide les étages inférieurs du pipeline et oblige le proc à mettre un ou plusieurs étages en attentes voir même de tout reprendre (le pipeline arrive quand même à déduire si un saut mémoire va être pris ou pas, jusqu’à un certain pourcentage)

Bon après, utiliser le xor ou une variable tmp, en fonction du compilo et de ses options d'optimisation, y aura pas vraiment de différence