Autoblog de blog.rom1v.com

Ce site n'est pas le site officiel de ®om
C'est un blog automatisé qui réplique les articles de blog.rom1v.com

Exécuter un algorithme lors de la compilation (templates C++)

Fri, 27 Mar 2015 19:53:08 +0000 - (source)

hanoi

En général, pour résoudre un problème donné, nous écrivons un algorithme dans un langage source, puis nous le compilons (dans le cas d’un langage compilé). La compilation consiste à traduire le code source en un code exécutable par une machine cible. C’est lors de l’exécution de ce fichier que l’algorithme est déroulé.

Mais certains langages, en l’occurrence C++, proposent des mécanismes permettant un certain contrôle sur la phase de compilation, tellement expressifs qu’ils permettent la métaprogrammation. Nous pouvons alors faire exécuter un algorithme directement par le compilateur, qui se contente de produire un fichier exécutable affichant le résultat.

À titre d’exemple, je vais présenter dans ce billet comment résoudre le problème des tours de Hanoï (généralisé, c’est-à-dire quelque soit la position initiale des disques) lors de la phase de compilation.

Les programmes complets décrits dans ce billet sont gittés :

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

(ou sur github)

Problème des tours de Hanoï généralisé

La résolution naturelle du problème généralisé des tours de Hanoï est récursive.

Pour déplacer n disques vers la tour T, il faut:

En voici une implémentation classique en C++ (le compilateur va générer le code permettant d’exécuter l’algorithme) :

#include <iterator>
#include <iostream>
#include <vector>

class Hanoi {
    using tower = unsigned int;
    using size = unsigned int;

    std::vector<tower> state; // disk number i is on tower state[i]

public:
    Hanoi(std::initializer_list<tower> init) : state(init) {}

    void solve(tower target) {
        printState(); // initial state
        solveRec(state.size(), target);
    }

private:
    void solveRec(size disks, tower target) {
        if (disks == 0) {
            return;
        }
        // the tower of the largest disk at this depth of recursion
        tower &largest = state[state.size() - disks];
        if (largest == target) {
            // the largest disk is already on the target tower
            solveRec(disks - 1, target);
        } else {
            // move disks above the largest to the intermediate tower
            solveRec(disks - 1, other(largest, target));
            // move the largest disk to the target
            largest = target;
            printState();
            // move back the disks on the largest
            solveRec(disks - 1, target);
        }
    }

    void printState() {
        std::copy(state.cbegin(), state.cend(),
                  std::ostream_iterator<tower>(std::cout));
        std::cout << std::endl;
    }

    static inline tower other(tower t1, tower t2) {
        return 3 - t1 - t2;
    }

};

int main() {
    Hanoi{ 0, 0, 0, 0, 0 }.solve(2);
    return 0;
}

(sourcecommit – tag runtime)

À compiler avec :

g++ -std=c++11 hanoi.cpp -o hanoi

L’algorithme utilise un simple vecteur de positions des disques, indexés du plus grand au plus petit, pour stocker l’état courant.

Par exemple, l’état { 0, 0, 0, 0 } représente 4 disques sur la tour 0 :

state = { 0, 0, 0, 0 };

    0         1         2

    |         |         |
   -+-        |         |
  --+--       |         |
 ---+---      |         |
----+----     |         |

L’état { 1, 1, 0, 2 }, quant-à lui, représente ces positions:

state = { 1, 1, 2, 1 };

    0         1         2

    |         |         |
    |         |         |
    |        -+-        |
    |      ---+---      |
    |     ----+----   --+--

Dans cette version, pour déplacer le disque i, il suffit alors de changer la valeur de state[i].

Il serait possible d’utiliser une structure de données différente, comme un vecteur par tour stockant les numéros des disques présents, mais celle que j’ai choisie sera beaucoup plus adaptée pour la suite.

Étant données 2 tours T1 et T2, il est très facile d’en déduire la 3e : 3 – T1 – T2. Ce calcul est extrait dans la fonction inlinée other(…).

Le contexte étant présenté, essayons maintenant d’implémenter le même algorithme pour le faire exécuter par le compilateur.

Structure de données constante

std::vector est une structure de données utilisable uniquement à l’exécution : il n’est pas possible d’en créer ou d’en utiliser une instance lors de la compilation. Même l’utilisation d’un simple tableau d’entiers nous poserait des problèmes par la suite.

Nous allons donc grandement simplifier le stockage des positions des disques, en utilisant un seul entier. En effet, à chaque disque est associée une tour qui peut être 0, 1 ou 2. Par conséquent, un chiffre en base 3 (un trit) suffit pour stocker la position d’une tour.

Ainsi, nous pouvons représenter l’état { 1, 2, 1, 0, 2 } par l’entier 146 (1×81 + 2×27 + 1×9 + 0×3 + 2×1) :

+-----+-----+-----+-----+-----+
| 3^4 | 3^3 | 3^2 | 3^1 | 3^0 |
|  81 |  27 |   9 |   3 |   1 |
+-----+-----+-----+-----+-----+
|  1  |  2  |  1  |  0  |  2  |
+-----+-----+-----+-----+-----+

Au passage, voici comment convertir rapidement un nombre dans une autre base en shell (pratique pour débugger) :

$ echo 'ibase=3; 12102' | bc
146
$ echo 'obase=3; 146' | bc
12102

Nous allons utiliser le type entier le plus long, à savoir unsigned long long, stockant au minimum 64 bits, soit 64 digits en base 2. En base 3, cela représente 64 × ln(2)/ln(3) ≃ 40 digits : nous pouvons donc stocker la position de 40 disques dans un seul entier.

Pour cela, définissons un type state :

using state = unsigned long long;

Expressions constantes généralisées

Nous allons écrire une première ébauche n’utilisant que des expressions constantes, clairement indiquées et vérifiées depuis C++11 grâce au mot-clé constexpr. Une fonction constexpr doit, en gros, n’être composé que d’une instruction return.

C’est le cas à l’évidence pour notre fonction other(…) :

constexpr tower other(tower t1, tower t2) {
    return 3 - t1 - t2;
}

Grâce à l’opérateur ternaire et à la récursivité, nous pouvons cependant en écrire de plus complexes.

Dans notre programme classique, le déplacement d’un disque i se résumait à changer la valeur de state[i]. Maintenant que l’état du système est compacté dans un seul entier, l’opération est moins directe.

Soit l’état courant { 0, 1, 2, 0, 0 } (ou plus simplement 01200). Supposons que nous souhaitions déplacer le disque au sommet de la tour 2 vers la tour 1. Cela consiste, en fait, à remplacer le dernier 2 par un 1 (rappelez-vous, les disques sont indexés du plus grand au plus petit). Le résultat attendu est donc 01100.

Notez que ce déplacement n’est pas toujours autorisé. Par exemple, le disque au sommet de la tour 2 est plus grand (i.e. a un plus petit index) que celui au sommet de la tour 0, il n’est donc pas possible de le déplacer vers la tour 0. C’est à l’algorithme que revient la responsabilité de n’effectuer que des déplacements légaux.

Remplacer le dernier digit x de la représentation d’un nombre N (dans une base quelconque) par y peut s’implémenter récursivement :

Concrètement :

      N   N\d d    { x=2, y=1 }
  01200  0120 0    // d != x : remplacer x par y dans N\d
   0120   012 0    //   d != x : remplacer x par y dans N\d
    012    01 2    //     d == x : remplacer x par y
    011    01 1    //     d = y
   0110   011 0    //   recoller d au résultat
  01100  0110 0    // recoller d au résultat

Il reste à expliciter l’étape du remplacement du digit. De manière générale, remplacer par un chiffre d le dernier digit d’un nombre N exprimé dans une base b consiste à calculer, soit N / b * b + d, soit de manière équivalente N - N % b + d (/ représentant la division entière et % le modulo). Dans les deux cas, l’opération annule le dernier digit puis ajoute son remplaçant.

base10

Sur un exemple en base 10, c’est évident. Remplaçons le dernier chiffre de 125 par 7 selon les deux méthodes :

     N /  b *  b + v         N -   N %  b + d
   125 / 10 * 10 + 7       125 - 125 % 10 + 7
         12 * 10 + 7       125 -        5 + 7
             120 + 7                  120 + 7
                 127                      127

Arbitrairement, nous utiliserons la première méthode pour implémenter notre fonction constexpr move(…) :

constexpr state move(state s, tower src, tower target) {
    return s % 3 == src
        ? s / 3 * 3 + target
        : move(s / 3, src, target) * 3 + s % 3;
}

De la même manière, définissons une fonction getTower(s, i) qui retourne la tour sur laquelle se trouve le ième plus petit disque :

constexpr tower getTower(state s, size disk) {
    return disk == 1
        ? s % 3
        : getTower(s / 3, disk - 1);
}

Attaquons-nous maintenant à la conversion de la fonction solveRec(…). Elle contenait deux branchements (if) et plusieurs instructions séquentielles, que nous allons devoir transformer en une seule instruction return.

Pour cela, nous allons remplacer les branchements par des opérateurs ternaires :

if (C) {
    X = A;
} else {
    X = B;
}

devient :

X = C ? A : B;

Notez que contrairement à la version if/else, cela implique que les expressions retournent une valeur. Cela tombe bien, comme une fonction constexpr ne peut pas modifier une variable, notre fonction va retourner l’état résultant de la transformation.

Concernant les instructions séquentielles, remarquons qu’elles dépendent successivement les unes des autres. De manière générale, nous pouvons remplacer :

A = f();
B = g(A);
X = h(B);

par:

X = h(g(f()));

En combinant ces principes, la méthode solve(…) peut être écrite ainsi (afin de bien voir l’imbrication des appels, je ne la découpe volontairement pas en plusieurs méthodes) :

constexpr state solve(size disks, state s, tower target) {
    return disks == 0
        ? s
        : getTower(s, disks) == target
            ? solve(disks - 1, s, target)
            : solve(disks - 1,
                    move(solve(disks - 1,
                               s,
                               other(getTower(s, disks), target)),
                         getTower(s, disks),
                         target),
                    target);
}

Les appels les plus profonds sont effectués en premier.

Ajoutons une méthode d’affichage pour obtenir la représentation de l’état du système en base 3 :

std::ostream &print_state(std::ostream &os, size ndisks, state s) {
    return ndisks ? print_state(os, ndisks - 1, s / 3) << s % 3 : os;
}

(sourcecommit – tag constexpr)

Compilons et exécutons le programme :

$ g++ -std=c++11 metahanoi.cpp && ./metahanoi
22222

L’état 22222 (soit l’entier 242) est bien écrit en dur dans le binaire généré :

$ g++ -std=c++11 -S metahanoi.cpp && grep 242 metahanoi.s
        movq    $242, -16(%rbp)
        movl    $242, %edx

Le compilateur est donc bien parvenu à la solution.

Mais avouons que le résultat est un peu décevant : l’état final, nous le connaissions déjà ; ce qui nous intéresse, c’est le cheminement pour y parvenir. Nous souhaiterions donc qu’en plus, le compilateur nous indique, d’une manière ou d’une autre, les étapes intermédiaires décrivant la solution du problème.

Templates

Pour cela, nous allons utiliser les templates.

Pour comprendre comment les templates vont nous aider, commençons par quelques précisions.

Les classes template sont souvent utilisées avec des paramètres types. Par exemple, std::vector<int> définit un nouveau type paramétré par le type int. Mais il est également possible de passer des paramètres non-types, qui sont alors des valeurs "simples".

Une classe template ne définit pas un type, mais permet de générer des types selon les paramètres qui lui sont affectés. Concrètement, std::vector<int> et std::vector<double> sont des types totalement différents, comme s’ils étaient implémentés par deux classes écrites séparément.

Dit autrement, la classe est au template ce que l’objet est à la classe : une instance. Mais c’est une instance qui existe lors de la phase de compilation !

     +----------------+
     | CLASS TEMPLATE |
     +----------------+
          | template
          | instantiation
          v                     COMPILE TIME
     +----------------+
     |  CLASS / TYPE  |    -----------------------
     +----------------+
          | class                 RUNTIME
          | instantiation
          v
     +----------------+
     |     OBJECT     |
     +----------------+

De la même manière qu’une variable d’instance existe pour chaque objet (instance de classe), une variable static existe pour chaque classe (instance de template).

Pour conserver les états successifs de la résolution du problème des tours de Hanoï, nous allons donc créer une classe par étape, dans laquelle nous allons pouvoir y stocker un état static. Nous voulons donc remplacer notre fonction solve(…) par des classes template.

Pour illustrer comment, commençons par un template simple effectuant la somme de deux entiers :

template <int I, int J>
struct Sum {
    static constexpr int result = I + J;
};

Sum<3, 4>::result est calculé à la compilation et vaut 7.

Prenons maintenant l’exemple d’un calcul récursif : la factorielle d’un entier. Il nous faut implémenter à la fois le cas général et la condition d’arrêt. Nous pourrions penser à utiliser l’opérateur ternaire ainsi :

template <int N>
struct Fact {
    // does not work!
    static constexpr int result = N == 0 ? 1 : N * Fact<N - 1>::result;
};

Malheureusement, ceci ne peut pas fonctionner, car pour calculer la valeur d’une expression, le compilateur doit d’abord calculer le type de chacun des opérandes. Par conséquent, Fact<N - 1> sera généré même si N == 0. La récursivité ne s’arrête donc jamais, provoquant une erreur à la compilation :

error: template instantiation depth exceeds maximum of 900

Comment faire alors ? La clé réside dans la spécialisation de templates, qui permet de sélectionner l’implémentation de la classe en fonction des paramètres :

template <int N>
struct Fact {
    static constexpr int result = N * Fact<N-1>::result;
};

template <>
struct Fact<0> {
    static constexpr int result = 1;
};

Lorsque Fact est instancié avec le paramètre 0, la classe est générée à partir du template spécialisé, stoppant ainsi la récursivité.

Appliquons ce principe à notre algorithme des tours de Hanoï. Nous allons définir une classe template Solver avec 3 paramètres de template, les mêmes que notre fonction solve(…) :

template <size DISKS, state S, tower TARGET>
struct SolverRec { … };

Puis nous allons en définir une spécialisation pour le cas où DISKS vaut 0 :

template <state S, tower TARGET>
struct SolverRec<0, S, TARGET> { … };

Nous avons ainsi implémenté le premier branchement sur la condition DISKS == 0.

Un second branchement reste à réaliser : le calcul à effectuer est différent selon si le plus grand disque parmi les DISKS derniers est déjà sur la tour cible ou non. Celui-ci est plus compliqué, car les paramètres de template présents ne permettent pas d’évaluer sa condition.

Nous allons donc devoir ajouter en paramètre la position du disque SRC afin de pouvoir sélectionner la bonne implémentation en fonction de la condition SRC == TARGET. Sa valeur étant déterminée par celle des autres paramètres, l’ajout de SRC ne va pas entraîner la création de nouveaux types. Par contre, il multiplie les cas à implémenter :

// cas général
template <size DISKS, state S, tower SRC, tower TARGET>
struct SolverRec { … };

// quand SRC == TARGET (le disque est déjà bien placé)
template <size DISKS, state S, tower TOWER>
struct SolverRec<DISKS, S, TOWER, TOWER> { … };

// quand il ne reste plus qu'un seul disque, mal placé
template <state S, tower SRC, tower TARGET>
struct SolverRec<1, S, SRC, TARGET> { … };

// quand il ne reste plus qu'un seul disque, déjà bien placé
template <state S, tower TOWER>
struct SolverRec<1, S, TOWER, TOWER> { … };

Les plus observateurs auront remarqué que désormais, la récursivité s’arrête à 1 disque, et non plus 0 comme précédemment. En effet, maintenant que le paramètre SRC est ajouté, il va falloir le calculer (grâce à getTower(…)) avant d’utiliser le type. Or, cela n’a pas de sens de récupérer la position d’un disque lorsque nous n’avons pas de disques. D’ailleurs, l’exécution de getTower(…) avec disk == 0 provoquerait une erreur… de compilation (vu que l’exécution se déroule à la compilation).

Nous avons maintenant 4 versions de la classe template SolverRec à écrire. Chacune devra contenir l’état final résultant du déplacement de DISKS disques de la tour SRC vers la tour TARGET à partir de l’état S. Cet état sera stocké dans une constante final_state, présente dans chacune des spécialisations.

Voici mon implémentation :

template <size DISKS, state S, tower SRC, tower TARGET>
struct SolverRec {
    static constexpr tower nextSrc = getTower(S, DISKS - 1);
    static constexpr tower inter = other(SRC, TARGET);
    using rec1 = SolverRec<DISKS - 1, S, nextSrc, inter>;
    static constexpr state value = move(rec1::final_state, SRC, TARGET);
    using rec2 = SolverRec<DISKS - 1, value, inter, TARGET>;
    static constexpr state final_state = rec2::final_state;
};

template <size DISKS, state S, tower TOWER>
struct SolverRec<DISKS, S, TOWER, TOWER> {
    static constexpr tower nextSrc = getTower(S, DISKS - 1);
    using rec = SolverRec<DISKS - 1, S, nextSrc, TOWER>;
    static constexpr state final_state = rec::final_state;
};

template <state S, tower SRC, tower TARGET>
struct SolverRec<1, S, SRC, TARGET> {
    static constexpr state final_state = move(S, SRC, TARGET);
};

template <state S, tower TOWER>
struct SolverRec<1, S, TOWER, TOWER> {
    static constexpr state final_state = S;
};

Le type (déterminé par les arguments des templates) correspondant aux appels récursifs dépend des valeurs constexpr calculées dans la classe. C’est à l’appelant de calculer la tour source pour renseigner la valeur du paramètre SRC.

Par commodité, nous pouvons aussi ajouter une classe template Solver, qui calcule elle-même la tour SRC du plus grand disque lors du démarrage.

template <size DISKS, state S, tower TARGET>
struct Solver {
    static constexpr tower src = getTower(S, DISKS);
    using start = SolverRec<DISKS, S, src, TARGET>;
    static constexpr state final_state = start::final_state;
};

(sourcecommit – tag templates)

De cette manière, pour calculer l’état résultant du déplacement de 5 disques à l’état 00000 (l’entier 0) vers la tour 2, il suffit de lire la variable :

Solver<5, 0, 2>::final_state;

Nous avons donc converti notre implementation d’une simple fonction constexpr en classes template. Fonctionnellement équivalente pour l’instant, cette nouvelle version met en place les fondations pour récupérer, à l’exécution, les étapes de la résolution du problème calculées à la compilation.

État initial

Mais avant cela, dotons-nous d’un outil pour décrire l’état initial facilement, qui pour l’instant doit être exprimé grâce à un state, c’est-à-dire un entier.

L’idée serait que l’état et le nombre de disques soit calculé automatiquement à la compilation à partir de la liste des positions des disques :

Disks<1, 2, 0, 1, 2>

Contrairement à précedemment, ici, nous avons besoin d’un nombre indéterminé de paramètres. Nous allons donc utiliser les variadic templates :

template <tower ...T>
struct Disks;

Remarquez que ce template est juste déclaré et non défini.

Pour parcourir les paramètres, nous avons besoin de deux spécialisations (une pour la récursion et une pour la condition d’arrêt) :

template <tower H, tower ...T>
struct Disks<H, T...> { … };

template <>
struct Disks<> { … };

Chacune des deux spécialisent le template déclaré, mais remarquez que l’une n’est pas une spécialisation de l’autre. C’est la raison pour laquelle nous avons besoin de déclarer un template (sans le définir) dont ces deux définitions sont une spécialisation.

Voici l’implémentation :

template <tower H, tower ...T>
struct Disks<H, T...> {
    static constexpr state count = 1 + sizeof...(T);
    static constexpr state pack(state tmp) {
        return Disks<T...>::pack(tmp * 3 + H);
    }
    static constexpr state packed = pack(0);
};

template <>
struct Disks<> {
    static constexpr state count = 0;
    static constexpr state pack(state tmp) { return tmp; };
    static constexpr state packed = 0;
};

Le nombre de disques est initialisé en comptant les paramètres grâce à l’opérateur sizeof....

L’état compacté est stocké dans la variable packed. Étant donné que les premiers paramètres traités seront les digits de poids fort, la multiplication devra être effectuée par les appels récursifs plus profonds. C’est la raison pour laquelle j’utilise une fonction temporaire qui permet d’initialiser packed.

Nous pouvons maintenant initialiser notre solver ainsi :

using disks = Disks<1, 2, 0, 1, 2>;
using solver = Solver<disks::count, disks::packed, 2>;

(sourcecommit – tag disks)

Affichage récursif

Attaquons-nous maintenant à l’affichage des états successifs.

Le plus simple consiste à implémenter une méthode print(…) dans chacune des classes SolverRec, affichant l’état associé et/ou appellant récursivement les méthodes print(…) sur les instances de SolverRec utilisées pour la résolution du problème.

Pour cela, nous devons auparavant déterminer, pour chaque template instancié, quel état afficher. Par exemple, pour les classes crées à partir de l’implémentation du template non spécialisé, il y a plusieurs états accessibles :

C’est en fait l’état value qu’il faut afficher :

Il est important de différencier, pour chaque SolverRec, l’état final, représentant l’état après l’application de tous les déplacements demandés, de l’état suivant le seul déplacement unitaire (s’il existe) associé à la classe. C’est ce dernier que nous voulons afficher.

Nous allons donc ajouter dans les 4 versions du template SolverRec une méthode :

static std::ostream &print(std::ostream &os, size ndisks);

Le paramètre std::ostream &os permet juste de préciser sur quel flux écrire (std::cout par exemple) ; il est retourné pour pouvoir le chaîner avec d’autres écritures (comme << std::endl).

Cette méthode a besoin de connaître le nombre total de disques, afin d’afficher le bon nombre de digits. Notez que cette valeur est différente du paramètre de template DISKS, qui correspond au nombre de disques à déplacer pour le niveau de récursivité courant.

template <size DISKS, state S, tower SRC, tower TARGET>
struct SolverRec {
    static constexpr tower nextSrc = getTower(S, DISKS - 1);
    static constexpr tower inter = other(SRC, TARGET);
    using rec1 = SolverRec<DISKS - 1, S, nextSrc, inter>;
    static constexpr state value = move(rec1::final_state, SRC, TARGET);
    using rec2 = SolverRec<DISKS - 1, value, inter, TARGET>;
    static constexpr state final_state = rec2::final_state;

    static std::ostream &print(std::ostream &os, size ndisks) {
        rec1::print(os, ndisks);
        print_state(os, ndisks, value) << std::endl;
        rec2::print(os, ndisks);
        return os;
    }
};

template <size DISKS, state S, tower TOWER>
struct SolverRec<DISKS, S, TOWER, TOWER> {
    static constexpr tower nextSrc = getTower(S, DISKS - 1);
    using rec = SolverRec<DISKS - 1, S, nextSrc, TOWER>;
    static constexpr state final_state = rec::final_state;

    static std::ostream &print(std::ostream &os, size ndisks) {
        rec::print(os, ndisks);
        return os;
    }
};

template <state S, tower SRC, tower TARGET>
struct SolverRec<1, S, SRC, TARGET> {
    static constexpr state value = move(S, SRC, TARGET);
    static constexpr state final_state = value;

    static std::ostream &print(std::ostream &os, size ndisks) {
        print_state(os, ndisks, value) << std::endl;
        return os;
    }
};

template <state S, tower TOWER>
struct SolverRec<1, S, TOWER, TOWER> {
    static constexpr state value = S;
    static constexpr state final_state = value;

    static std::ostream &print(std::ostream &os, size ndisks) {
        return os;
    }
};

Seules les versions du template pour lesquelles SRC != TARGET affichent un état. Les autres n’ont rien à afficher directement.

Ajoutons également, par commodité, une méthode similaire dans le template Solver (sans le paramètre ndisks, car ici il est toujours égal à DISKS) :

template <size DISKS, state S, tower TARGET>
struct Solver {
    static constexpr tower src = getTower(S, DISKS);
    using start = SolverRec<DISKS, S, src, TARGET>;
    static constexpr state final_state = start::final_state;

    static std::ostream &print(std::ostream &os) {
        print_state(std::cout, DISKS, S) << std::endl; // initial state
        return start::print(os, DISKS);
    }
};

(sourcecommit – tag print)

Cette nouvelle version affiche bien lors de l’exécution les états calculés lors de la compilation.

Cependant, les appels récursifs nécessaires à la résolution du problème ne sont pas supprimés : ils sont nécessaires à l’affichage des résultats. Il est dommage de résoudre le problème à la compilation si c’est pour que l’exécution repasse par chacune des étapes de la résolution pour l’affichage.

Liste chaînée

Pour éviter cela, nous allons générer à la compilation une liste chaînée des étapes qu’il ne restera plus qu’à parcourir à l’exécution. Chaque classe qui affichait un état va désormais stocker un nœud de la liste chainée, implémenté ainsi :

struct ResultNode {
    state value;
    ResultNode *next;
};

Le défi est maintenant d’initialiser les champs next de chacun des nœuds à l’adresse du nœud suivant dans l’ordre de résolution du problème des tours de Hanoï, et non dans l’ordre des appels récursifs, qui est différent. Par exemple, l’état (value) associé à une instance du template SolverRec non spécialisé (correspondant au cas général) devra succéder à tous les états générés par l’appel récursif rec1, pourtant appelé après.

Pour cela, chaque classe doit être capable d’indiquer à son appelant quel est le premier nœud qu’elle peut atteindre (first) et passer à chaque classe appelée le nœud qui devra suivre son nœud final (AFTER). Ces informations suffisent à déterminer dans tous les cas le nœud suivant d’une classe donnée, ce qui permet de constituer la liste chaînée complète en mémoire :

template <size DISKS, state S, tower SRC, tower TARGET, ResultNode *AFTER>
struct SolverRec {
    static ResultNode node;
    static constexpr tower nextSrc = getTower(S, DISKS - 1);
    static constexpr tower inter = other(SRC, TARGET);
    using rec1 = SolverRec<DISKS - 1, S, nextSrc, inter, &node>;
    static constexpr state value = move(rec1::final_state, SRC, TARGET);
    using rec2 = SolverRec<DISKS - 1, value, inter, TARGET, AFTER>;
    static constexpr state final_state = rec2::final_state;
    static constexpr ResultNode *first = rec1::first;
    static constexpr ResultNode *next = rec2::first;
};

template <size DISKS, state S, tower SRC, tower TARGET, ResultNode *AFTER>
ResultNode SolverRec<DISKS, S, SRC, TARGET, AFTER>::node = { value, next };

template <size DISKS, state S, tower TOWER, ResultNode *AFTER>
struct SolverRec<DISKS, S, TOWER, TOWER, AFTER> {
    static constexpr tower nextSrc = getTower(S, DISKS - 1);
    using rec = SolverRec<DISKS - 1, S, nextSrc, TOWER, AFTER>;
    static constexpr state final_state = rec::final_state;
    static constexpr ResultNode *first = rec::first;
};

template <state S, tower SRC, tower TARGET, ResultNode *AFTER>
struct SolverRec<1, S, SRC, TARGET, AFTER> {
    static ResultNode node;
    static constexpr state value = move(S, SRC, TARGET);
    static constexpr state final_state = value;
    static constexpr ResultNode *first = &node;
    static constexpr ResultNode *next = AFTER;
};

template <state S, tower SRC, tower TARGET, ResultNode *AFTER>
ResultNode SolverRec<1, S, SRC, TARGET, AFTER>::node = { value, next };

template <state S, tower TOWER, ResultNode *AFTER>
struct SolverRec<1, S, TOWER, TOWER, AFTER> {
    static constexpr state value = S;
    static constexpr state final_state = value;
    static constexpr ResultNode *first = AFTER;
};

template <size DISKS, state S, tower TARGET>
struct Solver {
    static ResultNode list;
    static constexpr tower src = getTower(S, DISKS);
    using start = SolverRec<DISKS, S, src, TARGET, nullptr>;
};

template <size DISKS, state S, tower TARGET>
ResultNode Solver<DISKS, S, TARGET>::list = { S, start::first };

La variable static node n’étant pas constexpr (elle doit être adressable à l’exécution pour former la liste chaînée), elle doit être initialisée en dehors de la classe.

Pour parcourir simplement la liste chaînée, rendons ResultNode itérable (j’implémente ici uniquement le strict minimum pour que l’iterator fonctionne) :

struct ResultNode {
    state value;
    ResultNode *next;

    class iterator {
        const ResultNode *current;
    public:
        iterator(const ResultNode *current) : current(current) {};
        iterator &operator++() { current = current->next; return *this; }
        state operator*() { return current->value; }
        bool operator==(const iterator &o) { return current == o.current; }
        bool operator!=(const iterator &o) { return !(*this == o); }
    };

    iterator begin() const { return iterator(this); }
    iterator end() const { return iterator(nullptr); }
};

La liste peut être parcourue ainsi :

using disks = Disks<0, 0, 0, 0, 0>;
using solver = Solver<disks::count, disks::packed, 2>; 
for (state s : solver::list) {
    print_state(std::cout, disks::count, s) << std::endl;
}

(sourcecommit – tag nodes)

En observant le binaire généré, la liste chaînée est directement visible (ici les octets sont en little endian) :

$ objdump -sj .data metahanoi

metahanoi:     file format elf64-x86-64

Contents of section .data:
 6012a0 00000000 00000000 00000000 00000000
 6012b0 00000000 00000000 00136000 00000000    n00: { 00000, &n05 }
 6012c0 ca000000 00000000 f0136000 00000000    n01: { 21111, &n20 }
 6012d0 35000000 00000000 70136000 00000000    n02: { 01222, &n12 }
 6012e0 16000000 00000000 30136000 00000000    n03: { 00211, &n08 }
 6012f0 05000000 00000000 10136000 00000000    n04: { 00012, &n06 }
 601300 02000000 00000000 f0126000 00000000    n05: { 00002, &n04 }
 601310 04000000 00000000 e0126000 00000000    n06: { 00011, &n03 }
 601320 18000000 00000000 40136000 00000000    n07: { 00220, &n09 }
 601330 15000000 00000000 20136000 00000000    n08: { 00210, &n07 }
 601340 1a000000 00000000 d0126000 00000000    n09: { 00222, &n02 }
 601350 24000000 00000000 a0136000 00000000    n10: { 01100, &n15 }
 601360 2e000000 00000000 80136000 00000000    n11: { 01201, &n13 }
 601370 34000000 00000000 60136000 00000000    n12: { 01221, &n11 }
 601380 2d000000 00000000 50136000 00000000    n13: { 01200, &n10 }
 601390 29000000 00000000 b0136000 00000000    n14: { 01112, &n16 }
 6013a0 26000000 00000000 90136000 00000000    n15: { 01102, &n14 }
 6013b0 28000000 00000000 c0126000 00000000    n16: { 01111, &n01 }
 6013c0 d8000000 00000000 60146000 00000000    n17: { 22000, &n27 }
 6013d0 c5000000 00000000 20146000 00000000    n18: { 21022, &n23 }
 6013e0 cc000000 00000000 00146000 00000000    n19: { 21120, &n21 }
 6013f0 c9000000 00000000 e0136000 00000000    n20: { 21110, &n19 }
 601400 ce000000 00000000 d0136000 00000000    n21: { 21122, &n18 }
 601410 be000000 00000000 30146000 00000000    n22: { 21001, &n24 }
 601420 c4000000 00000000 10146000 00000000    n23: { 21021, &n22 }
 601430 bd000000 00000000 c0136000 00000000    n24: { 21000, &n17 }
 601440 ee000000 00000000 90146000 00000000    n25: { 22211, &n30 }
 601450 dd000000 00000000 70146000 00000000    n26: { 22012, &n28 }
 601460 da000000 00000000 50146000 00000000    n27: { 22002, &n26 }
 601470 dc000000 00000000 40146000 00000000    n28: { 22011, &n25 }
 601480 f0000000 00000000 a0146000 00000000    n29: { 22220, &n31 }
 601490 ed000000 00000000 80146000 00000000    n30: { 22210, &n29 }
 6014a0 f2000000 00000000 00000000 00000000    n31: { 22222, nullptr }

La colonne de gauche correspond aux adresses des données. Les 4 colonnes suivantes contiennent des blocs de 4 octets, les deux premiers de chaque ligne représentant le champ value et les deux suivants le champ next de ResultNode, que j’ai réécrits de manière plus lisible à droite.

Possible ?

Cette représentation interpelle : pourquoi ne pas stocker plus simplement les différents états dans l’ordre, plutôt que d’utiliser des indirections pour former une liste chaînée ?

Malheureusement, je n’ai pas trouvé de solution pour stocker les états ordonnés dans un seul tableau d’entiers dès la compilation.

Si quelqu’un y parvient, ça m’intéresse !


Comportement indéfini et optimisation

Wed, 22 Oct 2014 00:41:59 +0000 - (source)

binary

Dans certains langages (typiquement C et C++), la sémantique de certaines opérations est indéfinie. Cela permet au compilateur de ne s’intéresser qu’aux cas qui sont définis (et donc de les optimiser) sans s’occuper des effets produits sur les cas indéfinis.

C’est un concept très précieux pour améliorer sensiblement les performances. Mais cela peut avoir des effets surprenants. Si le résultat de votre programme dépend d’un comportement indéfini (undefined behavior) particulier, alors votre programme complet n’a pas de sens, et le compilateur a le droit de faire ce qu’il veut. Et il ne s’en prive pas !

Programme indéfini

Par exemple, déréférencer un pointeur NULL est un comportement indéfini. En effet, contrairement à ce que beaucoup pensent, l’exécution du programme ne va pas forcément provoquer une erreur de segmentation.

J’ai écrit un petit programme tout simple (undefined.c) :

1
2
3
4
5
6
7
8
9
10
11
#include <stdio.h>
#include <malloc.h>

int main(int argc, char *argv[]) {
    int *i = argc == 1 ? NULL : malloc(sizeof(int));
    *i = 42;
    if (!i)
        return 1;
    printf("pwnd %d\n", *i);
    return 0;
}

Si argc vaut 1 (c’est-à-dire si nous appelons l’exécutable sans passer d’arguments de la ligne de commande), alors le pointeur i est NULL (ligne 5).

Cette ligne peut paraître étrange, mais elle permet de faire dépendre i d’une valeur connue uniquement à l’exécution (argc), ce qui évite au compilateur de savoir à l’avance que i est NULL.

La ligne 6 (*i = 42) est donc incorrecte : nous n’avons pas le droit de déréférencer un pointeur NULL. Nous nous attendons donc souvent à une erreur de segmentation.

Mais suite à ce que je viens de vous dire, admettons que ce ne soit pas le cas, et que nous arrivions quand même sur la ligne suivante (7). Ici, si i est NULL, la fonction se termine (en retournant 1, ligne 8).

Donc il n’y a donc aucun moyen d’afficher le contenu du printf ligne 9.

Et bien… en fait, si !

Exécution

Essayons (j’utilise gcc 4.7.2 packagé dans Debian Wheezy en amd64, les résultats peuvent différer avec un autre compilateur ou une autre version de gcc) :

$ gcc -Wall undefined.c
$ ./a.out          # argc == 1
Erreur de segmentation
$ ./a.out hello    # argc == 2
pwnd 42

Jusqu’ici, tout va bien. Maintenant, activons des optimisations de compilation :

$ gcc -Wall -O2 undefined.c
$ ./a.out
pwnd 42

Voilà, nous avons réussi à exécuter le printf alors que argc == 1.

Que s’est-il passé ?

Assembleur

Pour le comprendre, il faut regarder le code généré en assembleur, sans et avec optimisations.

Sans optimisation

Pour générer le résultat de la compilation sans assembler (et donc obtenir un fichier source assembleur undefined.s) :

gcc -S undefined.c

J’ai commenté les parties importantes :

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
    .file   "undefined.c"
    .section    .rodata
.LC0:
    .string "pwnd %d\n"
    .text
    .globl  main
    .type   main, @function
main:
.LFB0:
    .cfi_startproc
    pushq   %rbp
    .cfi_def_cfa_offset 16
    .cfi_offset 6, -16
    movq    %rsp, %rbp
    .cfi_def_cfa_register 6
    subq    $32, %rsp
    movl    %edi, -20(%rbp)
    movq    %rsi, -32(%rbp)
    cmpl    $1, -20(%rbp)     ; if (argc == 1)
    je  .L2                   ;     goto .L2
    movl    $4, %edi          ; arg0 = 4  // sizeof(int)
    call    malloc            ; tmp = malloc(4)
    jmp .L3                   ; goto .L3
.L2:
    movl    $0, %eax
.L3:
    movq    %rax, -8(%rbp)    ; i = tmp
    movq    -8(%rbp), %rax
    movl    $42, (%rax)       ; *i = 42
    cmpq    $0, -8(%rbp)      ; if (!i)
    jne .L4                   ;    goto .L4
    movl    $1, %eax          ; ret = 1
    jmp .L5
.L4:
    movq    -8(%rbp), %rax
    movl    (%rax), %eax
    movl    %eax, %esi        ; arg1 = *i
    movl    $.LC0, %edi       ; arg0 points to "pwnd %d\n"
    movl    $0, %eax
    call    printf            ; printf("pwnd %d\n", *i)
    movl    $0, %eax          ; ret = 0
.L5:
    leave
    .cfi_def_cfa 7, 8
    ret                       ; return ret
    .cfi_endproc
.LFE0:
    .size   main, .-main
    .ident  "GCC: (Debian 4.7.2-5) 4.7.2"
    .section    .note.GNU-stack,"",@progbits

Le code généré est très fidèle au code source C.

Avec gcc -O

Maintenant, activons certaines optimisations :

gcc -O -S undefined.c

Ce qui donne :

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
34
35
36
37
38
39
40
41
42
    .file   "undefined.c"
    .section    .rodata.str1.1,"aMS",@progbits,1
.LC0:
    .string "pwnd %d\n"
    .text
    .globl  main
    .type   main, @function
main:
.LFB11:
    .cfi_startproc
    cmpl    $1, %edi          ; if (argc == 1)
    je  .L2                   ;    goto .L2
    subq    $8, %rsp
    .cfi_def_cfa_offset 16
    movl    $4, %edi          ; arg0 = 4  // sizeof(int)
    call    malloc            ; tmp = malloc(4)
    movq    %rax, %rdx        ; i = tmp
    movl    $42, (%rax)       ; *i = 42
    movl    $1, %eax          ; ret = 1
    testq   %rdx, %rdx        ; if (!i)
    je  .L5                   ;    goto .L5
    movl    $42, %esi         ; arg1 = 42
    movl    $.LC0, %edi       ; arg0 points to "pwnd %d\n"
    movl    $0, %eax
    call    printf            ; printf("pwnd %d\n", 42)
    movl    $0, %eax          ; ret = 0
    jmp .L5                   ; goto .L5
.L2:
    .cfi_def_cfa_offset 8
    movl    $42, 0            ; segfault (dereference addr 0)
    movl    $1, %eax          ; ret = 1
    ret
.L5:
    .cfi_def_cfa_offset 16
    addq    $8, %rsp
    .cfi_def_cfa_offset 8
    ret                       ; return ret
    .cfi_endproc
.LFE11:
    .size   main, .-main
    .ident  "GCC: (Debian 4.7.2-5) 4.7.2"
    .section    .note.GNU-stack,"",@progbits

Là, le compilateur a réorganisé le code. Si je devais le retraduire en C, j’écrirais ceci :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <stdio.h>
#include <malloc.h>

int main(int argc, char *argv[]) {
    if (argc == 1)
        *((int *) NULL) = 42;
    int *i = malloc(sizeof(int));
    *i = 42;
    if (!i)
        return 1;
    printf("pwnd %d\n", 42);
    return 0;
}

Ce qui est amusant, c’est qu’il alloue de la mémoire pour stocker i, il lui affecte la valeur 42… mais ne la lit jamais. En effet, il a décidé de recoder en dur 42 pour le paramètre du printf.

Mais avec ce résultat, impossible d’atteindre le printf si argc == 1.

Avec gcc -O2

Optimisons davantage :

gcc -O2 -S undefined.c

Ou, plus précisément (avec gcc 4.9.1 par exemple, l’option -O2 ne suffit pas) :

gcc -O -ftree-vrp -fdelete-null-pointer-checks -S undefined.c

(les options d’optimisation sont décrites dans la doc).

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
    .file   "undefined.c"
    .section    .rodata.str1.1,"aMS",@progbits,1
.LC0:
    .string "pwnd %d\n"
    .section    .text.startup,"ax",@progbits
    .p2align 4,,15
    .globl  main
    .type   main, @function
main:
.LFB11:
    .cfi_startproc
    subq    $8, %rsp
    .cfi_def_cfa_offset 16
    movl    $42, %esi         ; arg1 = 42
    movl    $.LC0, %edi       ; arg2 points to "pwnd %d\n"
    xorl    %eax, %eax
    call    printf            ; printf("pwnd %d\n", 42)
    xorl    %eax, %eax        ; ret = 0
    addq    $8, %rsp
    .cfi_def_cfa_offset 8
    ret                       ; return ret
    .cfi_endproc
.LFE11:
    .size   main, .-main
    .ident  "GCC: (Debian 4.7.2-5) 4.7.2"
    .section    .note.GNU-stack,"",@progbits

Là, l’optimisation donne un résultat beaucoup plus direct :

#include <stdio.h>

int main(int argc, char *argv[]) {
    printf("pwnd %d\n", 42);
    return 0;
}

Quel raisonnement a-t-il pu suivre pour obtenir ce résultat ? Par exemple le suivant.

Lorsqu’il rencontre la ligne 6 de undefined.c, soit i est NULL, soit i n’est pas NULL. Le compilateur sait que déréférencer un pointeur NULL est indéfini. Il n’a donc pas à gérer ce cas. Il considère donc que i est forcément non-NULL.

Mais alors, à quoi bon tester si i est non-NULL ligne 7 ? Le test ne sert à rien. Donc il le supprime.

Ce raisonnement permet de transformer le code ainsi :

#include <stdio.h>
#include <malloc.h>

int main(int argc, char *argv[]) {
    int *i = argc == 1 ? NULL : malloc(sizeof(int));
    *i = 42;
    printf("pwnd %d\n", *i);
    return 0;
}

Mais ce n’est pas tout. Le compilateur sait que i n’est pas NULL, donc il peut considérer que le malloc a lieu. Et allouer un entier en mémoire, écrire 42 dedans, puis lire la valeur cet entier plus tard, ça se simplifie beaucoup : juste lire 42, sans allouer de mémoire.

Ce qu’il simplifie en :

    printf("pwnd %d\n", 42);

CQFD

Avec clang -02

Il est intéressant d’observer ce que produit un autre compilateur : Clang.

clang -O2 -S undefined.c

Voici le résultat :

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
    .file   "undefined.c"
    .text
    .globl  main
    .align  16, 0x90
    .type   main,@function
main:                                   # @main
.Ltmp2:
    .cfi_startproc
# BB#0:
    pushq   %rbp
.Ltmp3:
    .cfi_def_cfa_offset 16
.Ltmp4:
    .cfi_offset %rbp, -16
    movq    %rsp, %rbp
.Ltmp5:
    .cfi_def_cfa_register %rbp
    cmpl    $1, %edi          ; if (argc == 1)
    je  .LBB0_4               ;     goto .LBB0_4
# BB#1:
    movl    $4, %edi          ; arg0 = 4  //sizeof(int)
    callq   malloc            ; tmp = malloc(4)
    movq    %rax, %rcx        ; i = tmp
    movl    $42, (%rcx)       ; *i = 42
    movl    $1, %eax          ; ret = 1
    testq   %rcx, %rcx        ; if (!i)
    je  .LBB0_3               ;     goto .LBB0_3
# BB#2:
    movl    $.L.str, %edi     ; arg0 points to "pwnd %d\n"
    movl    $42, %esi         ; arg1 = 42
    xorb    %al, %al
    callq   printf            ; printf("pwnd %d\n", *i)
    xorl    %eax, %eax        ; ret = 0
.LBB0_3:
    popq    %rbp
    ret                       ; return ret
.LBB0_4:                                # %.thread
    ud2                       ; undefined instruction
.Ltmp6:
    .size   main, .Ltmp6-main
.Ltmp7:
    .cfi_endproc
.Leh_func_end0:

    .type   .L.str,@object          # @.str
    .section    .rodata.str1.1,"aMS",@progbits,1
.L.str:
    .asciz   "pwnd %d\n"
    .size   .L.str, 9


    .section    ".note.GNU-stack","",@progbits

Il réalise les mêmes optimisations que gcc -O, sauf qu’il génère une erreur explicite grâce à l’instruction machine ud2.

#include <stdio.h>
#include <malloc.h>

int main(int argc, char *argv[]) {
    if (argc == 1)
        ud2(); /* hardware undefined instruction */
    int *i = malloc(sizeof(int));
    *i = 42;
    if (!i)
        return 1;
    printf("pwnd %d\n", 42);
    return 0;
}

Étonnamment, Clang ne prend jamais la décision de supprimer le malloc.

Par contre, avec une version suffisamment récente (ça marche avec Clang 3.5.0), il est possible d’ajouter des vérifications lors de l’exécution :

$ clang -fsanitize=null undefined.c && ./a.out
undefined.c:6:5: runtime error: store to null pointer of type 'int'
Erreur de segmentation

Ça peut être pratique pour détecter des problèmes. Et puis des NullPointerExceptions en C, ça fait rêver, non ?

À retenir

Si un programme contient un comportement indéfini, alors son comportement est indéfini. Pas juste la ligne en question. Pas juste les lignes qui suivent la ligne en question. Le programme. Même s’il fonctionne maintenant sur votre machine avec votre version de compilateur.

Somebody once told me that in basketball you can’t hold the ball and run. I got a basketball and tried it and it worked just fine. He obviously didn’t understand basketball.

(source)

Pour aller plus loin et étudier d’autres exemples, je vous recommande la lecture des articles suivants (en anglais) :

Optimisations multi-threadées

Les comportements indéfinis font partie intégrante du C et du C++. Mais même dans des langages de plus haut niveau, il existe des comportements indéfinis (pas de même nature, je vous l’accorde), notamment lorsque plusieurs threads s’exécutent en parallèle.

Pour garantir certains comportements, il faut utiliser des mécanismes de synchronisation. Dans une vie antérieure, j’avais présenté certains de ces mécanismes en Java.

Mais une erreur courante est de penser que la synchronisation ne fait que garantir l’atomicité avec des sections critiques. En réalité, c’est plus complexe que cela. D’une part, elle ajoute des barrières mémoire empêchant certaines réorganisations des instructions (ce qui explique pourquoi le double-checked locking pour écrire des singletons est faux). D’autre part, elle permet de synchroniser les caches locaux des threads, sans quoi l’exemple suivant (inspiré d’ici) est incorrect :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class VisibilityTest extends Thread {

    boolean keepRunning = true;

    public static void main(String... args) throws Exception {
        VisibilityTest thread = new VisibilityTest();
        thread.start();
        Thread.sleep(1000);
        thread.keepRunning = false;
        System.out.println(System.currentTimeMillis() +
                           ": keepRunning false");
    }

    @Override
    public void run() {
        System.out.println(System.currentTimeMillis() + ": start");
        while (keepRunning);
        System.out.println(System.currentTimeMillis() + ": end");
    }

}

Pour le compiler et l’exécuter :

javac VisibilityTest.java && java VisibilityTest

Sans synchronisation, il est très fort probable que le thread démarré ne se termine jamais, voyant toujours keepRunning à true, même si le thread principal lui a donné la valeur false.

Là encore, c’est une optimisation (la mise en cache d’une variable) qui provoque ce comportement « inattendu » sans synchronisation.

Déclarer keepRunning volatile suffit à résoudre le problème.

Conclusion

La notion de comportement indéfini est très importante pour améliorer la performance des programmes. Mais elle est source de bugs parfois difficiles à
Erreur de segmentation


AImageView (composant Android)

Mon, 20 Oct 2014 18:48:34 +0000 - (source)

android

Pour afficher une image sur Android, le SDK contient un composant ImageView.

Cependant, son mécanisme de configuration du redimensionnement de l’image (ScaleType) me semble déficient :

J’ai donc écrit un composant AImageView (qui hérite d’ImageView) avec un mécanisme alternatif au scale type.

Principes

AImageView propose 4 paramètres :

Actuellement, il préserve toujours le format d’image (aspect ratio).

Exemple d’utilisation

    <com.rom1v.aimageview.AImageView
        android:layout_width="match_parent"
        android:layout_height="match_parent"
        android:src="@drawable/myimage"
        app:xWeight="0.5"
        app:yWeight="0.5"
        app:fit="inside"
        app:scale="downscale|upscale" />

Ici, l’image va s’adapter à l’intérieur (inside) du composant (des marges seront ajoutées si nécessaires), exactement (l’image peut être réduite – downscale – ou agrandie – upscale – pour s’adapter) et sera centrée (0.5, 0.5).

Équivalences des scale types

Les constantes de ScaleType du composant standard ImageView correspondent en fait à des valeurs particulières de ces paramètres. Comme vous pourrez le constater, elles ne couvrent pas toutes les combinaisons, et ne sont pas toujours explicites…

ScaleType.CENTER

  app:xWeight="0.5"
  app:yWeight="0.5"
  app:scale="disabled"
  // app:fit ne fait rien quand scale vaut "disabled"

ScaleType.CENTER_CROP

  app:xWeight="0.5"
  app:yWeight="0.5"
  app:fit="outside"
  app:scale="downscale|upscale"

ScaleType.CENTER_INSIDE

  app:xWeight="0.5"
  app:yWeight="0.5"
  app:fit="inside"
  app:scale="downscale"

ScaleType.FIT_CENTER

  app:xWeight="0.5"
  app:yWeight="0.5"
  app:fit="inside"
  app:scale="downscale|upscale"

ScaleType.FIT_END

  app:xWeight="1"
  app:yWeight="1"
  app:fit="inside"
  app:scale="downscale|upscale"

ScaleType.FIT_START

  app:xWeight="0"
  app:yWeight="0"
  app:fit="inside"
  app:scale="downscale|upscale"

ScaleType.FIT_XY

Cette configuration ne peut pas être reproduite en utilisant les paramètres d’AImageView, car ce composant préserve toujours l’aspect ratio.

ScaleType.MATRIX

AImageView hérite d’ImageView et force le scaleType à ScaleType.MATRIX (pour redimensionner et déplacer l’image). Par conséquent, il n’y a pas d’équivalent, AImageView est basé dessus.

Composant

Le composant est disponible sous la forme d’un project library (sous licence GNU/LGPLv3 (plus maintenant) MIT):

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

(miroir sur github)

Vous pouvez le compiler en fichier `.aar` grâce à la commande :

cd AImageView
./gradlew assembleRelease

Il sera généré dans library/build/outputs/aar/aimageview.aar.

J’ai aussi écrit une application de démo l’utilisant (avec tous les fichiers Gradle qui-vont-bien) :

git clone --recursive http://git.rom1v.com/AImageViewSample.git

(miroir sur github)

AImageViewSample

Pour compiler un apk de debug (par exemple) :

cd AImageViewSample
./gradlew assembleDebug

Pour ceux que le code intéresse, la classe principale est AImageView. Pour l’utiliser, la partie importante est dans activity_main.xml.

N’hésitez pas à critiquer ou à remonter des bugs.


Chiffrer un disque dur externe (ou une clé USB) avec LUKS

Sun, 20 Jul 2014 21:03:33 +0000 - (source)

crypto
Un disque dur externe contenant vos données n’a pas de raisons de ne pas être chiffré. Voici quelques commandes utiles pour l’utilisation de LUKS.

Prérequis

Le paquet cryptsetup doit être installé :

sudo apt-get install cryptsetup

Initialisation

Trouver le disque

Tout d’abord, il faut déterminer l’emplacement du disque dur dans /dev. Pour cela, avant de le brancher, exécuter la commande :

sudo tail -f /var/log/messages

Lors du branchement du disque, plusieurs lignes similaires à celles-ci doivent apparaître :

Jul 20 21:25:29 pc kernel: [  678.139988] sd 7:0:0:0: [sdb] 976754645 4096-byte logical blocks: (4.00 TB/3.63 TiB)

Ici, [sdb] signifie que l’emplacement est /dev/sdb. Dans la suite, je noterai cet emplacement /dev/XXX.

Il est très important de ne pas se tromper d’emplacement, afin de ne pas formater un autre disque…

Effacer le disque

Si des données étaient présentes sur ce disque, il est plus sûr de tout supprimer physiquement :

sudo dd if=/dev/zero of=/dev/XXX bs=4K

Cette commande peut prendre beaucoup de temps, puisqu’elle consiste à réécrire physiquement tous les octets du disque dur.

Créer la partition chiffrée

Pour initialiser la partition chiffrée :

sudo cryptsetup luksFormat -h sha256 /dev/XXX

La passphrase de déchiffrement sera demandée.

Maintenant que nous avons une partition chiffrée, ouvrons-la :

sudo cryptsetup luksOpen /dev/XXX lenomquevousvoulez

Cette commande crée un nouveau device dans /dev/mapper/lenomquevousvoulez, contenant la version déchiffrée (en direct).

Formater

Pour formater cette partition en ext4 :

sudo mkfs.ext4 /dev/mapper/lenomquevousvoulez

Pour l’initialisation, c’est fini, nous pouvons fermer la vue déchiffrée :

cryptsetup luksClose lenomquevousvoulez

Montage manuel

Il est possible de déchiffrer et monter la partition manuellement en ligne de commande :

sudo cryptsetup luksOpen /dev/XXX lenomquevousvoulez
sudo mkdir -p /media/mydisk
sudo mount -t ext4 /dev/mapper/lenomquevousvoulez /media/mydisk

Le contenu est alors accessible dans /media/mydisk.

Pour démonter et fermer, c’est le contraire :

sudo umount /media/mydisk
sudo cryptsetup luksClose /dev/XXX lenomquevousvoulez

Mais c’est un peu fastidieux. Et je n’ai pas trouvé de solution pour permettre le luksOpen par un utilisateur (non-root) en ligne de commande.

Montage semi-automatique

Les environnement de bureau permettent parfois de monter un disque dur chiffré simplement, avec la demande de la passphrase lors de l’ouverture du disque. Voici ce que j’obtiens avec XFCE :
luksOpen

Mais par défaut, le nom du point de montage est peu pratique : /media/rom/ae74bc79-9efe-4325-8b4d-63d1506fa928. Heureusement, il est possible de le changer. Pour cela, il faut déterminer le nom de la partition déchiffrée :

$ ls /dev/mapper/luks-*
/dev/mapper/luks-8b927433-4d4f-4636-8a76-06d18c09723e

Le nom très long correspond en fait à l’UUID du disque, qui peut aussi être récupéré grâce à :

sudo cryptsetup luksUUID /dev/XXX

ou encore :

sudo blkid /dev/XXX

L’emplacement désiré, ainsi que les options qui-vont-bien, doivent être rajoutés dans /etc/fstab :

/dev/mapper/luks-8b927433-4d4f-4636-8a76-06d18c09723e /media/mydisk ext4 user,noauto

Ainsi, le disque sera désormais monté dans /media/mydisk.

Si en plus, nous souhaitons spécifier un nom user-friendly pour la partition déchiffrée (celui dans /dev/mapper/), il faut ajouter une ligne dans /etc/crypttab (en adaptant l’UUID) :

mydisk UUID=8b927433-4d4f-4636-8a76-06d18c09723e none luks,noauto

Et utiliser celle-ci à la place dans /etc/fstab :

/dev/mapper/mydisk /media/mydisk ext4 user,noauto

Gestion des passphrases

Il est possible d’utiliser plusieurs passphrases (jusqu’à 8) pour déchiffrer le même disque.

Pour en ajouter une :

sudo cryptsetup luksAddKey /dev/XXX

Pour en supprimer une :

sudo cryptsetup luksRemoveKey /dev/XXX

Pour changer une unique passphrase, il suffit d’en ajouter une nouvelle puis de supprimer l’ancienne.

Ou alors d’utiliser :

sudo cryptsetup luksChangeKey /dev/XXX

mais man cryptsetup dit qu’il y a un risque.

État

Pour consulter l’état d’une partition LUKS :

sudo cryptsetup luksDump /dev/XXX

Gestion de l’en-tête

L’en-tête LUKS est écrit au début du disque. L’écraser empêche définivement le déchiffrement de la partition.

Il est possible d’en faire une sauvegarde dans un fichier :

cryptsetup luksHeaderBackup /dev/XXX --header-backup-file fichier

Et de les restaurer :

cryptsetup luksHeaderRestore /dev/XXX --header-backup-file fichier

Pour supprimer l’en-tête (et donc rendre les données définitivement inaccessibles s’il n’y a pas de backup) :

cryptsetup luksErase /dev/XXX

Conclusion

Une fois configuré la première fois, et après les quelques modifications pénibles pour choisir les noms pour le déchiffrement et le montage, l’utilisation au quotidien est vraiment très simple : il suffit de rentrer la passphrase directement à partir du navigateur de fichiers.


SSHFS inversé (rsshfs)

Sun, 15 Jun 2014 13:30:27 +0000 - (source)

sshfs

SSHFS permet de monter un répertoire d’une machine distance dans l’arborescence locale en utilisant SSH :

sshfs serveur:/répertoire/distant /répertoire/local

Mais comment monter un répertoire local sur une machine distante ?

Une solution simple serait de se connecter en SSH sur la machine distante et d’exécuter la commande sshfs classique.

Mais d’abord, ce n’est pas toujours directement possible : la machine locale peut ne pas être accessible (non adressable) depuis la machine distante. Ça se contourne en créant un tunnel SSH utilisant la redirection de port distante (option -R).

Et surtout, ce n’est pas toujours souhaitable : cela nécessite que la clé privée autorisée sur la machine locale soit connue de la machine distante. Or, dans certains cas, nous ne voulons pas qu’une machine esclave puisse se connecter à notre machine maître.

Reverse SSHFS

En me basant sur la commande donnée en exemple, j’ai donc écrit un petit script Bash (rsshfs, licence GPLv3) qui permet le reverse SSHFS :

(disponible également sur github)

git clone http://git.rom1v.com/rsshfs.git
cd rsshfs
sudo install rsshfs /usr/local/bin

Les paquets sshfs et fuse doivent être installés sur la machine distante (et l’utilisateur doit appartenir au groupe fuse). Le paquet openssh-sftp-server doit être installé sur la machine locale ainsi que vde2 (pour la commande dpipe) (plus maintenant).

Son utilisation se veut similaire à celle de sshfs :

rsshfs /répertoire/local serveur:/répertoire/distant

Comme avec sshfs, /répertoire/distant doit exister sur serveur et doit être vide.

Il est également possible de monter le répertoire en lecture seule :

rsshfs /répertoire/local serveur:/répertoire/distant -o ro

Attention. L’option « lecture seule » est demandée à la machine distante, par un paramètre sshfs. Par conséquent, une version modifiée de sshfs pourrait ignorer la demande de lecture seule. Vous devez donc faire confiance à la machine distante. (plus maintenant)

Contrairement à sshfs, étant donné que rsshfs agit comme un serveur, cette commande ne retourne pas tant que le répertoire distant n’est pas démonté.

Pour démonter, dans un autre terminal :

rsshfs -u serveur:/répertoire/distant

Ou plus simplement (depuis le commit 440a357) en pressant Ctrl+C dans le terminal de la commande de montage.

TODO

J’ai choisi la facilité en écrivant un script indépendant qui appelle la commande qui-va-bien.

L’idéal serait d’ajouter cette fonctionnalité à sshfs directement.


Compiler un exécutable pour Android

Tue, 18 Mar 2014 23:39:52 +0000 - (source)

android

Je vais présenter dans ce billet comment compiler un exécutable ARM pour Android, l’intégrer à un APK et l’utiliser dans une application.

À titre d’exemple, nous allons intégrer un programme natif, udpxy, dans une application minimale de lecture vidéo.

Contexte

Le framework multimédia d’Android ne supporte pas nativement la lecture de flux UDP multicast (1, 2).

Il est possible, pour y parvenir, d’utiliser des lecteurs alternatifs, par exemple basés sur ffmpeg/libav (l’un est un fork de l’autre), tel que libvlc.

Il existe par ailleurs un outil natif, sous licence GPLv3, relayant du trafic UDP multicast vers du HTTP : udpxy. N’importe quel client supportant HTTP (comme le lecteur natif d’Android) peut alors s’y connecter. C’est cet outil que nous allons utiliser ici.

udpxy

Compilation classique

Avant de l’intégrer, comprenons son utilisation en le faisant tourner sur un ordinateur classique (Debian Wheezy 64 bits pour moi).

Il faut d’abord le télécharger les sources, les extraire et compiler :

wget http://www.udpxy.com/download/1_23/udpxy.1.0.23-9-prod.tar.gz
tar xf udpxy.1.0.23-9-prod.tar.gz
cd udpxy-1.0.23-9/
make

Si tout se passe bien, nous obtenons (entre autres) un binaire udpxy.

Test de diffusion

Pour tester, nous avons besoin d’une source UDP multicast. Ça tombe bien, VLC peut la fournir. Pour obtenir le résultat attendu par udpxy, nous devons diffuser vers une adresse multicast (ici 239.0.0.1). Par exemple, à partir d’un fichier MKV :

cvlc video.mkv ':sout=#udp{dst=239.0.0.1:1234}'

En parallèle, démarrons une instance d’udpxy, que nous venons de compiler :

./udpxy -p 8379

Cette commande va démarrer un proxy relayant de l’UDP multicast vers de l’HTTP, écoutant sur le port 8379.

Dans un autre terminal, nous pouvons faire pointer VLC sur le flux ainsi proxifié :

vlc http://localhost:8379/udp/239.0.0.1:1234/

Normalement, le flux doit être lu correctement.

Remarquez qu’udpxy pourrait très bien être démarré sur une autre machine (il suffirait alors de remplacer localhost par son IP). Mais pour la suite, nous souhaiterons justement exécuter udpxy localement sur Android.

Bien sûr, avec VLC, nous n’aurions pas besoin d’udpxy. Le flux est lisible directement avec la commande :

vlc udp://@239.0.0.1:1234/

Android

Notez que certains devices Android ne supportent pas le multicast, la réception de flux multicast ne fonctionnera donc pas.

Maintenant que nous avons vu comment fonctionne udpxy, portons-le sur Android.

Notre but est de le contrôler à partir d’une application et le faire utiliser par le lecteur vidéo natif.

Pour cela, plusieurs étapes sont nécessaires :

  1. obtenir un binaire ARM exécutable pour Android ;
  2. le packager avec une application ;
  3. l’extraire ;
  4. l’exécuter.

Exécutable ARM

Pré-compilé

Pour obtenir un binaire ARM exécutable, le plus simple, c’est évidemment de le récupérer déjà compilé, s’il est disponible (c’est le cas pour udpxy). Dans ce cas, il n’y a rien à faire.

Pour le tester, transférons-le sur le téléphone et exécutons-le :

adb push udpxy /data/local/tmp
adb shell /data/local/tmp/udpxy -p 8379

Si tout se passe bien, cette commande ne produit en apparence rien : elle attend qu’un client se connecte. Pour valider le fonctionnement, si le téléphone est sur le même réseau que votre ordinateur, vous pouvez utiliser cette instance (ARM) d’udpxy comme proxy entre la source multicast et un lecteur VLC local :

vlc http://<ip_device>:8379/udp/239.0.0.1:1234/

Pour obtenir l’ip du téléphone :

adb shell netcfg | grep UP
Compilation ponctuelle

S’il n’est pas disponible, il va falloir le compiler soi-même à partir des sources, ce qui nécessite le NDK Android, fournissant des chaînes de compilation pré-compilées.

Il suffit alors d’initialiser la variable d’environnement CC pour pointer sur la bonne chaîne de compilation (adaptez les chemins et l’architecture selon votre configuration) :

export NDK=~/android/ndk
export SYSROOT="$NDK/platforms/android-19/arch-arm"
export CC="$NDK/toolchains/arm-linux-androideabi-4.8/prebuilt/linux-x86_64/bin/arm-linux-androideabi-gcc --sysroot=$SYSROOT"
make

Bravo, vous venez de générer un binaire udpxy pour l’architecture ARM.

Compilation intégrée

La compilation telle que réalisée ci-dessus est bien adaptée à la génération d’un exécutable une fois de temps en temps, mais s’intègre mal dans un système de build automatisé. En particulier, un utilisateur avec une architecture différente devra adapter les commandes à exécuter.

Heureusement, le NDK permet une compilation plus générique.

Pour cela, il faut créer un répertoire jni dans un projet Android (ou n’importe où d’ailleurs, mais en pratique c’est là qu’il est censé être), y mettre les sources et écrire des Makefiles.

Créons donc un répertoire jni contenant les sources. Vu que nous les avons déjà extraites, copions-les à la racine de jni/ :

cp -rp udpxy-1.0.23-9/ jni/
cd jni/

Créons un Makefile nommé Android.mk :

LOCAL_PATH := $(call my-dir)

include $(CLEAR_VARS)

LOCAL_MODULE    := udpxy
LOCAL_SRC_FILES := udpxy.c sloop.c rparse.c util.c prbuf.c ifaddr.c ctx.c mkpg.c \
                   rtp.c uopt.c dpkt.c netop.c extrn.c main.c

include $(BUILD_EXECUTABLE)

Puis compilons :

ndk-build

ndk-build se trouve à la racine du NDK.

Le binaire sera généré dans libs/armeabi/udpxy.

Afin d’organiser les projets plus proprement, il vaut mieux mettre les sources d’udpxy et son Android.mk dans un sous-répertoire spécifique au projet (dans jni/udpxy/). Dans ce cas, il faut rajouter un fichier jni/Android.mk contenant :

include $(call all-subdir-makefiles)

Packager avec l’application

Je suppose ici que vous savez déjà créer une application Android.

Nous devons maintenant intégrer le binaire dans l’APK. Pour cela, il y a principalement deux solutions :

Vu que les projets library ne gèrent pas les assets, nous allons utiliser une ressource raw.

Il faut donc copier le binaire dans res/raw/, à chaque fois qu’il est généré (à automatiser donc).

Extraire l’exécutable

L’exécutable est bien packagé avec l’application, et comme toutes les ressources, nous pouvons facilement obtenir un InputStream (le fonctionnement est similaire pour les assets).

Mais pour l’exécuter en natif, le binaire doit être présent sur le système de fichiers. Il faut donc le copier et lui donner les droits d’exécution. Sans la gestion des exceptions, cela donne :

// "/data/data/<package>/files/udpxy"
File target = new File(getFilesDir(), "udpxy")
InputStream in = getResources().openRawResource(R.raw.udpxy);
OutputStream out = new FileOutputStream(target);
// copy from R.raw.udpxy to /data/data/<package>/files/udpxy
FileUtils.copy(in, out);
// make the file executable
FileUtils.chmod(target, 0755);

Et les parties intéressantes de FileUtils :

public static void copy(InputStream in, OutputStream os) throws IOException {
    byte[] buf = new byte[4096];
    int read;
    while ((read = (in.read(buf))) != -1) {
        os.write(buf, 0, read);
    }
}

public static boolean chmod(File file, int mode) throws IOException {
    String sMode = String.format("%03o", mode); // to string octal value
    String path = file.getAbsolutePath();
    String[] argv = { "chmod", sMode, path };
    try {
        return Runtime.getRuntime().exec(argv).waitFor() == 0;
    } catch (InterruptedException e) {
        throw new IOException(e);
    }
}

Exécuter le programme natif

Maintenant que le binaire est disponible sur le système de fichiers, il suffit de l’exécuter :

String[] command = { udpxyBin.getAbsolutePath(), "-p", "8379" };
udpxyProcess = Runtime.getRuntime().exec(command);

Le lecteur vidéo pourra alors utiliser l’URI proxifié comme source de données :

String src = UdpxyService.proxify("239.0.0.1:1234");

Projets

andudpxy

Je mets à disposition sous licence GPLv3 le projet library andudpxy, qui met en œuvre ce que j’ai expliqué ici :

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

(ou sur github)

Pour l’utiliser dans votre application, n’oubliez pas de référencer la library et de déclarer le service UdpxyService dans votre AndroidManifest.xml :

<service android:name="com.rom1v.andudpxy.UdpxyService" />

Pour démarrer le démon :

UdpxyService.startUdpxy(context);

et pour l’arrêter :

UdpxyService.stopUdpxy(context);

andudpxy-sample

J’ai également écrit une application minimale de lecture vidéo qui utilise cette library :

git clone http://git.rom1v.com/andudpxy-sample.git

(ou sur github)

C’est toujours utile d’avoir une application d’exemple censée fonctionner 😉

L’adresse du flux UDP multicast à lire est écrite en dur dans MainActivity (et le flux doit fonctionner lors du démarrage de l’activité) :

private static final String ADDR = "239.0.0.1:1234";

Compilation

Après avoir cloné les 2 projets dans un même répertoire parent, renommez les local.properties.sample en local.properties, éditez-les pour indiquer le chemin du SDK et du NDK.

Ensuite, allez dans le répertoire andudpxy-sample, puis exécutez :

ant clean debug

Vous devriez obtenir bin/andudpxy-sample-debug.apk.

Bien sûr, vous pouvez aussi les importer dans Eclipse (ou un autre IDE) et les compiler selon vos habitudes.

Conclusion

Nous avons réussi à compiler et exécuter un binaire ARM sur Android, packagé dans une application.

Ceci peut être utile pour exécuter du code déjà implémenté nativement pour d’autres plates-formes, pour faire tourner un démon natif… Par exemple, le projet Serval (sur lequel j’ai un peu travaillé) utilise un démon servald, qui tourne également sur d’autres architectures.

Ce n’est cependant pas la seule manière d’exécuter du code natif dans une application : la plus courante est d’appeler des fonctions natives (et non un exécutable) directement à partir de Java, en utilisant JNI. L’une et l’autre répondent à des besoins différents.


Des slides Beamer en Markdown

Sat, 15 Feb 2014 18:29:14 +0000 - (source)

Pour produire des slides propres pour une présentation, j’aime beaucoup Beamer (basé sur LaTeX). Mais la syntaxe est un peu lourde et la configuration est parfois inutilement compliquée (fonts, encodage, compilation multipasse…).

Est-il possible d’avoir les avantages de Beamer sans ses inconvénients ? La réponse est oui, grâce à pandoc et son Markdown étendu.

Beamer

Voici le code d’un exemple très simple de présentation Beamer :

\documentclass[hyperref={pdfpagelabels=false}]{beamer}
\usepackage[utf8]{inputenc}
\usepackage{lmodern}

\title{Exemple}
\author{Romain Vimont}
\date{15 février 2014}

\begin{document}

\begin{frame}
\titlepage
\end{frame}

\section{Ma section}

\begin{frame}{Ma première frame}
\begin{itemize}
 \item c'est bien
 \item mais c'est verbeux
\end{itemize}
\end{frame}

\end{document}

Le code source est, il faut bien l’avouer, assez rebutant, et le rapport signal/bruit assez faible.

Une fois les paquets pdflatex, textlive-latex-base et latex-beamer installés (sous Debian), vous pouvez le compiler avec :

pdflatex fichier.tex

Markdown

Voici maintenant l’équivalent en Pandoc-Markdown :

% Exemple
% Romain Vimont
% 15 février 2014

# Ma section

## Ma première frame

 - c'est bien
 - et en plus ce n'est pas verbeux

Indiscutablement, c’est beaucoup plus lisible !

Avec le paquet pandoc (en plus des paquets latex déjà installés), vous pouvez le compiler avec :

pandoc -st beamer fichier.md -o fichier.pdf

Notez que le résultat n’est pas strictement identique, la version compilée avec pandoc ajoute une frame de section, mais il ne s’agit que d’une différence de template par défaut.

Démo

J’ai créé une présentation d’exemple avec un thème personnalisé.

Le résultat est disponible ici, mais c’est surtout la source (raw) qui est intéressante. Pour récupérer le projet et générer le pdf :

git clone http://git.rom1v.com/mdbeamer.git
cd mdbeamer
make

Il est également disponible sur github.

Ce projet a vocation à être utilisé comme base pour mes futures présentations (et les vôtres si vous le désirez). Chacune d’entre elles sera sur une branche git et sur un remote différents.

Injection de version

Pour pouvoir distinguer rapidement différentes versions d’une même présentation, j’ai également ajouté au Makefile une commande pour injecter un identifiant de version à côté de la date (donc à la fin de la 3e ligne du code source). Il s’agit du résultat de git describe (contenant le nom du dernier tag annoté) ou à défaut simplement le numéro de commit actuel.

Pour l’utiliser :

make withversion

Un format pivot

J’utilise ici le Pandoc-Markdown pour écrire du Beamer plus simplement.

Mais son intérêt est beaucoup plus général : il s’agit d’un véritable format pivot, compilable vers de nombreux formats.

Pour de la documentation par exemple, il suffit de l’écrire en Pandoc-Markdown et de la compiler, grâce à pandoc, en :

C’est d’ailleurs très pratique quand quelqu’un vous demande une documentation dans un format totalement inadapté (type docx), à rédiger de manière collaborative : il suffit alors d’utiliser Pandoc-Markdown, git et un Makefile.

Pour les slides, pandoc supporte, en plus de Beamer, la compilation vers des slides HTML :

Cette généricité a bien sûr des limites : l’utilisation de code spécifique à un format particulier (tel que j’en utilise dans mon exemple) empêche de le compiler correctement vers d’autres formats.

Conclusion

Le language Markdown (étendu par pandoc) permet de combiner la généricité, la simplicité et la gitabilité pour écrire des documents ou des slides, ce qui en fait un outil absolument indispensable.


Lecture différée de la webcam d’un Rasberry Pi

Mon, 20 Jan 2014 10:20:40 +0000 - (source)

raspi

L’objectif de ce billet est de parvenir à lire le flux provenant de la caméra d’un Raspberry Pi avec un décalage de quelques secondes (plutôt qu’en direct), avec les outils dédiés que sont raspivid et omxplayer.

Contexte

Là où je travaille, il y a un babyfoot. Nous avons récemment décidé de l’informatiser un peu pour avoir la détection et le ralenti des buts. Entre autres, un Raspberry Pi a été installé avec sa caméra au-dessus du terrain de manière à fournir une vue aérienne.

raspivid permet d’afficher en direct ce que la caméra filme. Mais l’intérêt est faible dans notre cas : le direct, nous l’avons déjà sous les yeux.

Il est bien plus utile d’avoir un "direct" différé de quelques secondes : lors d’un but ou d’une action litigieuse, il suffit de tourner la tête pour revoir ce qu’il vient de se passer (à vitesse réelle).

Je me suis intéressé à faire fonctionner ce cas d’usage. Je vais détailler ici les principes et les problèmes rencontrés.

Un simple tube

La première idée fut de brancher le flux H.264 que produit raspivid sur l’entrée de omxplayer, qui serait démarré quelques secondes plus tard.

Premier problème, omxplayer ne semblait pas savoir lire sur son entrée standard. Ce n’est pas très gênant, il suffit d’utiliser un tube nommé grâce à mkfifo. En effet :

printf 'a\nb\nc\n' | grep b

peut être remplacé par :

# terminal 1
mkfifo /tmp/fifo
printf 'a\nb\nc\n' > /tmp/fifo
# terminal 2
< /tmp/fifo grep b

Mais en fait, il y a plus direct : omxplayer n’est qu’un script wrapper pour le vrai omxplayer.bin, c’est lui qui empêchait la lecture sur l’entrée standard. Il suffit juste d’exporter la variable qui-va-bien et d’appeler omxplayer.bin directement :

export LD_LIBRARY_PATH="/opt/vc/lib:/usr/lib/omxplayer"
omxplayer.bin 

Cependant, contrairement à ce que proposent beaucoup de commandes shell, omxplayer.bin ne prévoit pas explicitement de lire sur son entrée standard, il attend obligatoirement un fichier en paramètre. Donnons-lui donc comme fichier /dev/stdin !

raspivid -t 0 -w 1280 -h 720 -fps 25 -n -o - | omxplayer.bin /dev/stdin

Vu la durée de démarrage d’omxplayer.bin, pas besoin de retarder son lancement, la vidéo sera bien décalée de quelques secondes.

Le problème, c’est que le buffer lié au tube est très limité (man 7 pipe) : il sera très vite plein, bloquant totalement l’enregistrement et la lecture de la vidéo.

Avec un buffer

Nous avons besoin d’un buffer plus important. Pour cela, nous pouvons utiliser mbuffer, ici avec une taille de 10Mo :

raspivid  | mbuffer -m 10m | omxplayer.bin /dev/stdin

Et là, cela semble fonctionner.

Pour décaler un peu plus la lecture par omxplayer.bin, il est possible d’utiliser les commandes groupées (man bash) pour ajouter un appel à sleep avant le démarrage :

raspivid  | mbuffer -m 10m | { sleep 3; omxplayer.bin /dev/stdin; }

raspivid est censé enregistrer à 25 fps (-fps 25) et omxplayer nous indique dans la console qu’il lit à 25 fps.

Cependant, en réalité, le décalage n’est pas constant : il augmente petit à petit au fil des minutes, et le buffer se remplit légèrement plus vite qu’il ne se vide. La lecture consomme moins d’images que n’en produit l’enregistrement, comme si le débit d’images de l’enregistrement était supérieur à celui de lecture.

Il y a donc un manque d’exactitude (à ne pas confondre avec un manque de précision) dans le nombre d’images enregistrées et/ou lues par seconde.

Si nous tentons d’enregistrer à un débit légèrement inférieur (24 fps), c’est le contraire : le retard est rattrapé progressivement jusqu’à fournir une lecture en direct.

Comme le débit d’images est la seule information temporelle disponible et qu’elle est inexacte, il semble impossible de contrecarrer cette variation de délai.

Information temporelle

Mais en réalité, ce n’est pas la seule information temporelle dont nous disposons : nous savons que le flux est en direct.

Comment exploiter cette information ? Pour le comprendre, il suffit d’enregistrer à un débit d’images très faible (-fps 5) et de le lire toujours à 25 fps.

Si la lecture provient d’un fichier, alors la vidéo passe en accéléré. Par contre, si la lecture sort de la webcam en direct, alors la vidéo passe à vitesse normale mais à 5 fps : le lecteur a beau vouloir lire 25 images par seconde, s’il n’en reçoit que 5 chaque seconde, il n’a pas d’autre choix que de lire à 5 fps.

Ainsi, sans même connaître sa valeur réelle exacte, nous parvenons à obtenir le même débit d’images à l’enregistrement qu’à la lecture.

Mais comme nous l’avons vu, avec un débit d’images d’enregistrement inférieur, le délai introduit se réduira inexorablement (le retard sera rattrapé). Ce que nous voulons éviter : nous voulons un délai constant.

Delay

Nous avons cependant avancé, car maintenant, si nous disposions d’une commande qui retarde ce qui sort de raspivid pour le donner à omxplayer x secondes plus tard, et que nous enregistrons à un débit d’images légèrement inférieur à celui de la lecture, alors omxplayer rattrapera le retard pour parvenir au direct… décalé de x secondes. Exactement ce que nous voulons !

J’ai donc demandé sur stackoverflow si une telle commande existait, ce qui ne semblait pas être le cas.

Je l’ai donc implémentée (sous licence GPLv3) :

git clone http://git.rom1v.com/delay.git
cd delay
make && sudo make install

(ou sur github)

Elle permet de décaler tout ce qui arrive sur stdin d’un délai constant pour le sortir sur stdout :

delay [-b <dtbufsize>] <delay>

Elle est donc très générique, et n’a aucun lien avec le fait que le flux soit une vidéo.

Elle fonctionne aussi très bien pour différer la lecture de la webcam dans VLC sur un pc classique :

ffmpeg -an -s 320x240 -f video4linux2 -i /dev/video0 -f mpeg2video -b 1M - |
  delay 2s | vlc -

Nous pourrions penser qu’il suffit de faire la même chose avec raspivid et omxplayer, avec un débit d’images légèrement inférieur pour l’enregistrement (24 fps) :

raspivid -t 0 -w 1280 -h 720 -fps 24 -n -o - |
  delay -b10m 4s |
  omxplayer.bin /dev/stdin

Malheureusement, avec omxplayer, ce n’est pas si simple.

Initialisation immédiate

En effet, l’initialisation d’omxplayer pour une lecture vidéo est très longue (plusieurs secondes), et surtout, elle ne débute que lorsque une partie suffisamment importante de la vidéo à lire est reçue (les headers ne suffisent pas). Décaler la vidéo de x secondes décale également l’initialisation de x secondes, ajoutant d’autant plus de décalage.

Certes, le retard supplémentaire sera rattrapé progressivement, mais cela prendra du temps (environ 1 image chaque seconde, soit 1 seconde toutes les 25 secondes). Pour obtenir le délai désiré dès le départ, ce problème doit être évité.

Une solution de contournement consiste à passer les premiers (méga-)octets sortis de raspivid directement à omxplayer.bin, et de ne différer que le reste avec delay. De cette manière, les premières images seront lues immédiatement, permettant au lecteur de s’initialiser, alors que la suite sera différée.

Grâce aux commandes groupées de bash (encore elles), c’est très simple :

raspivid -t 0 -w 1280 -h 720 -fps 24 -n -o - |
  { head -c10M; delay -b10m 4s; } |
  omxplayer.bin /dev/stdin

La commande head va passer immédiatement les 10 premiers méga-octets à omxplayer.bin, puis la commande delay prendra le relai. Ainsi, l’initialisation aura déjà eu lieu quand les premiers octets sortiront de delay.

À part les premières secondes un peu chaotiques, le flux vidéo sera alors bien diffusé en différé avec un délai constant (testé sur 24 heures).

Conclusion

Nous avons donc bricolé une solution qui permet un replay différé en continu sur un Raspberry Pi.


Duplicity : des backups incrémentaux chiffrés

Wed, 14 Aug 2013 14:59:42 +0000 - (source)

backup

Quiconque s’auto-héberge doit maintenir un système de sauvegarde de son serveur, permettant de tout remettre en place dans le cas d’un crash de disque dur, d’un piratage ou d’un cambriolage.

Objectifs

Il est nécessaire de sauvegarder à la fois des fichiers (les mails, les services hébergés, les fichiers de config…) et le contenu de bases de données (associées aux services hébergés).

Le système de sauvegarde doit conserver les archives durant un certain temps (par exemple 2 mois). En effet, un piratage ou une erreur de manipulation peuvent n’être détectés que quelques jours plus tard : il est important de pouvoir restaurer un état antérieur.

La sauvegarde doit être régulière (par exemple quotidienne).

Seule une infime partie des données étant modifiées d’un jour à l’autre, la sauvegarde a tout intérêt à être incrémentale.

Pour résister aux cambriolages, une sauvegarde doit être réalisée sur (au moins) une machine distante. Il est donc préférable que ces données soient chiffrées.

Duplicity

Vous l’aurez compris, duplicity répond à tous ces besoins.

Je ne vais pas expliquer tout ce qu’il sait faire, mais plutôt comment je l’utilise et pourquoi.

Mes choix d’utilisation

Sauvegarde locale

Personnellement, je n’effectue qu’une sauvegarde locale dans une tâche cron, c’est-à-dire que les fichiers de backups sont stockés sur le serveur lui-même.

En effet, une sauvegarde automatique vers un serveur distant, par SSH par exemple, nécessiterait une clé privée en clair sur le serveur. Cette configuration ne résisterait pas à certains piratages : une intrusion sur le serveur donnerait également accès aux sauvegardes, permettant à un pirate d’effacer à la fois les données et les backups.

C’est donc une autre machine, à l’initiative de la connexion, qui rapatrie les backups. Évidemment, elle ne doit pas synchroniser localement les backups supprimés du serveur (elle serait vulnérable à la suppression des backups par un pirate), mais doit plutôt supprimer les anciennes sauvegardes de sa propre initiative.

Chiffrement

Duplicity utilise GPG pour le chiffrement, permettant :

Le premier choix nécessite à la fois quelque chose que je possède (la clé, de forte entropie) et quelque chose que je connais (la passphrase, de plus faible entropie). Le second ne nécessite que la passphrase à retenir.

L’utilisation d’une clé privée autorise donc une meilleure sécurité, notamment si vous souhaitez envoyer vos backups sur un serveur américain.

Néanmoins, les backups sont surtout utiles lors de la perte de données, notamment dans le cas d’un cambriolage, où la clé GPG a potentiellement également disparu. Et les sauvegardes distantes ne seront d’aucune utilité sans la clé…
Il peut donc être moins risqué d’opter, comme je l’ai fait, pour une simple passphrase.

À vous de placer le curseur entre la protection de vos données et le risque de ne plus pouvoir les récupérer.

Installation

Sur une Debian :

sudo apt-get install duplicity

Fonctionnement

Duplicity effectue des sauvegardes complètes et incrémentales. Les sauvegardes incrémentales nécessitent toutes les sauvegardes depuis la dernière complète pour être restaurées.
Personnellement, j’effectue une sauvegarde complète tous les mois, et une incrémentale tous les jours.

Pour choisir le mode :

Exemple (à exécuter en root pour avoir accès à tous les fichiers) :

duplicity / file:///var/backups/duplicity/ --include-globbing-filelist filelist.txt --exclude '**'

Duplicity va sauvegarder à partir de la racine ("/") tous les fichiers selon les règles d’inclusion et d’exclusion définies dans filelist.txt. Ce fichier contient simplement la liste des fichiers et répertoires à sauvegarder, ainsi que ceux à exclure. Par exemple :

/usr/local/bin/
/home/rom/Maildir/
/home/rom/.procmailrc
- /var/www/blog/wp-content/cache/
/var/www/blog/

Attention : les fichiers et répertoires à exclure doivent apparaître avant l’inclusion d’un répertoire parent. En effet, duplicity s’arrête à la première règle qui matche un chemin donné pour déterminer s’il doit l’inclure ou l’exclure.

Pour restaurer :

duplicity restore file:///var/backups/duplicity/ /any/directory/

(utiliser l’option -t pour restaurer à une date particulière)

Pour supprimer les anciennes sauvegardes (ici de plus de 2 mois) :

duplicity remove-older-than 2M file:///var/backups/duplicity/ --force

Bases de données

Tout comme pour les fichiers, il est préférable de sauvegarder incrémentalement les bases de données (seule une toute petite partie des données change d’un jour à l’autre).

Une première solution serait d’utiliser la fonctionnalité-qui-va-bien de votre SGBD.

Mais si le contenu de vos bases de données ne dépasse pas quelques Go (ce qui est très probable pour de l’auto-hébergement), duplicity permet de faire beaucoup plus simple.

Il suffit en effet de générer un dump complet des bases de données vers des fichiers .sql et d’inclure leur chemin dans la liste des fichiers à sauvegarder. Et là, c’est magique, duplicity va ne sauvegarder que les parties de ces (gros) fichiers qui ont changées, grâce à rsync et à son algorithme qui utilise des rolling checksums.

Bien sûr, il ne faut pas compresser ces fichiers avant de les donner à manger à duplicity (sinon l’intégralité du fichier risque de changer) ; c’est lui qui va s’en charger. De même, il vaut mieux éviter d’inclure dans les fichies SQL des informations liées au dump, comme sa date de génération.

Pour exporter une base de données MySQL par exemple :

mysql -uroot -ppassword --skip-comments -ql my_database > my_database.sql

Script

Il reste donc à écrire un script qui exporte les bases de données et qui appelle duplicity avec la liste de ce qu’il y a à sauvegarder.

Voici un prototype, à sauvegarder dans /usr/local/bin/backup :

#!/bin/bash
BACKUP_HOME=/var/backups
TMP_DBDIR="$BACKUP_HOME/dbdump"
BACKUP_DIR="$BACKUP_HOME/duplicity"
MYSQLPW=mon_password_mysql
PASSPHRASE=ma_passphrase_de_chiffrement_des_backups
DATABASES='blog autre_base'
FILELIST="/usr/local/bin/
/home/rom/Maildir/
/home/rom/.procmailrc
- /var/www/blog/wp-content/cache/
/var/www/blog/
$TMP_DBDIR/"

# databases
mkdir -p "$TMP_DBDIR"
for dbname in $DATABASES
do
  printf "## Dump database $dbname...\n"
  mysqldump -uroot -p"$MYSQLPW" --skip-comments -ql "$dbname" \
    > "$TMP_DBDIR/$dbname.sql"
done

# duplicity
printf '## Backup using duplicity...\n'
unset mode
[ "$1" = full ] && mode=full && printf '(force full backup)\n'
mkdir -p "$BACKUP_DIR"
export PASSPHRASE
duplicity $mode / file://"$BACKUP_DIR"/ \
  --include-globbing-filelist <(echo "$FILELIST") --exclude '**'

printf '## Delete old backups\n'
duplicity remove-older-than 2M file://"$BACKUP_DIR"/ --force

# backups are encrypted, we can make them accessible
chmod +r "$BACKUP_DIR"/*.gpg

# remove temp files
rm "$TMP_DBDIR"/*.sql

Une fois configuré, ne pas oublier de tester : exécuter le script et restaurer les données dans un répertoire de test, puis vérifier que tout est OK. Cette vérification doit être effectuée de temps en temps : il serait dommage de s’apercevoir, lorsqu’on en a besoin, que les backups sont inutilisables ou qu’un répertoire important a été oublié.

Cron

Pour démarrer automatiquement une sauvegarde complète le premier jour du mois et une incrémentale tous les autres jours, cron est notre ami :

sudo crontab -e

Ajouter les lignes :

0 1 1    * * /usr/local/bin/backup full
0 1 2-31 * * /usr/local/bin/backup

La première colonne correspond aux minutes, la deuxième aux heures : le script sera donc exécuté à 1h du matin. La 3e correspond au numéro du jour dans le mois. Les deux suivantes sont le numéro du mois dans l’année et le jour de la semaine.

Il peut être préférable d’exécuter le script en priorité basse :

0 1 1    * * nice -15 ionice -c2 /usr/local/bin/backup full
0 1 2-31 * * nice -15 ionice -c2 /usr/local/bin/backup

Copies

Il ne reste plus qu’à effectuer des copies des fichiers de backups ailleurs.

À partir d’une autre machine, le plus simple est d’utiliser rsync (sans l’option --delete !) :

rsync -rvP --partial-dir=/my/local/tmpbackup --ignore-existing --stats -h server:/var/backups/duplicity/ /my/local/backup/

--ignore-existing évite de récupérer des modifications malicieuses des backups sur le serveur (ils ne sont pas censés être modifiés). Du coup, il faut aussi faire attention à sauvegarder les transferts partiels ailleurs (--partial-dir), sans quoi ils ne se termineront jamais.

Pour supprimer les anciens backups sur cette machine, c’est la même commande que sur le serveur :

duplicity remove-older-than 2M file:///my/local/backup/ --force

Conclusion

La génération de sauvegardes à la fois incrémentales et chiffrées, y compris pour les bases de données, font de duplicity une solution de backup idéale pour l’auto-hébergement.

Je l’utilise depuis plusieurs mois, et j’en suis très satisfait (même si je n’ai pas encore eu besoin de restaurer les backups en situation réelle).

À vos backups !


Anti-AdBlock et Hadopi, même combat ?

Thu, 13 Jun 2013 15:47:38 +0000 - (source)

abp

La presse s’inquiète de plus en plus de l’impact des bloqueurs de publicités sur leurs sources de revenus et condamne, plus ou moins ouvertement, leur utilisation par les internautes.

Le débat se polarise alors entre :

La seconde catégorie avance un argument simple et de bon sens : le contenu produit nécessite du travail, et leurs auteurs ont évidemment besoin de se loger, de se nourrir, et bien d’autres choses encore… Ce qui implique, dans notre société, d’avoir de l’argent. Ce que rapporte un peu la publicité.

Les autres sont des pirates sans conscience désirant tout gratuitement, à qui il faut expliquer qu’une attitude responsable consiste à ne pas bloquer les publicités. À moins que…

Hadopi

Des auteurs qui proposent du « contenu » difficilement vendable à un public qui y accède sans le payer, ça ne vous rappelle rien ?

L’un des fondements de l’idéologie répressive d’Hadopi est qu’il faut éduquer et contraindre les utilisateurs, sans quoi les « créateurs » ne pourront plus « vivre de leur travail », et donc ne pourront plus « créer ».

Faut-il établir un cadre psychologique incitant à accepter l’intrusion de publicités afin que les journalistes puissent « gagner leur vie » ?

De la même manière qu’il faut dépasser l’opposition entre le partage de la culture et son financement par la vente de copies, je pense qu’il faut dépasser celle entre la liberté de (non) réception (appliquée au web) et le financement par la publicité.

Les discussions portant sur la négociation d’un compromis entre les deux positions, comme l’acceptation de publicités moins intrusives, paraissent vaines.

Valeur et financement

Ne pas pouvoir vendre un contenu ne signifie pas qu’il n’a pas de valeur : un article rendu accessible à tous n’a pas moins de valeur que le même article restreint par un accès payant.

Par contre, y ajouter de la publicité diminue la valeur que leur attribuent les lecteurs, mais aussi les auteurs eux-mêmes : tous préféreraient ne pas la subir. La publicité agit donc comme un parasite.

Et pour les journalistes, ce parasite engendre une dépendance financière pouvant influencer le fond du discours. D’une manière générale, les sources de financement ont souvent tendance à réduire l’indépendance, pierre angulaire du journalisme.

C’est la raison pour laquelle certains essaient de ne dépendre que de leurs lecteurs. Mais, pour la plupart d’entre eux (pas tous), cela signifie limiter le contenu aux seuls abonnés. En effet, si tout est déjà accessible, pourquoi payer ?

Cependant, en pratique, seuls quelques gros sites peuvent se permettre cette restriction (les internautes ne vont pas s’abonner aux milliers de sites qu’ils visitent). Et au fond, est-ce bien le web que nous voulons, cloisonné par des barrières à péages ?

Du côté des lecteurs, la publicité ralentit la navigation, impose une pollution visuelle et collecte certaines données personnelles ; pas étonnant qu’ils cherchent à s’en prémunir !

Monnaie, revenu et travail

Dans le monde de la rareté, l’échange monétaire provient de la rencontre de l’offre et de la demande. Dans le monde de l’immatériel, l’offre et la demande se rencontrent déjà parfaitement sans monnaie, qui ne joue alors plus le rôle de facilitateur d’échange, mais au contraire d’obstacle : il est nécessaire de restreindre ou dégrader le résultat du travail pour pouvoir « gagner sa vie ».

Le métier de certains journalistes, dont personne ne conteste l’utilité, est menacé, car nous avons intégré le fait que le revenu devait provenir exclusivement du travail. Mais si ce travail ne génère pas d’argent, doit-il disparaître ?

La publicité est omniprésente car il faut absolument gagner de l’argent autrement, l’information en elle-même n’en rapportant pas. Pourtant, les internautes vont bien sur les sites de presse pour l’information, pas pour la publicité !

Revenu de base

Et si une partie du revenu était indépendante du travail ? Dissocier le revenu et l’emploi n’améliorerait-il pas la situation, pour tout le monde et en particulier pour les journalistes ?

Le revenu de base augmente la possibilité d’activités non rentables, sans ajouter de dépendances (car inconditionnel).

La rentabilité ayant tendance à entraver et dénaturer le journalisme, ne devrions-nous envisager sérieusement cette proposition dans les débats sur le financement de la presse, et plus généralement sur les productions potentiellement non-marchandes ?

Le revenu de base n’interdirait bien sûr pas les autres sources de financement : il s’y ajouterait. Simplement, il augmenterait la capacité à refuser des financements contraignants, tels que ceux provenant de la publicité…


Powered by VroumVroumBlog 0.1.32 - RSS Feed
Download config articles