Durant ces dernières semaines chez Genymobile, j’ai développé un outil de reverse tethering pour Android, permettant aux téléphones (et aux tablettes) d’utiliser la connexion internet de l’ordinateur sur lequel ils sont branchés, sans accès root (ni sur le téléphone, ni sur le PC). Il fonctionne sur GNU/Linux, Windows et Mac OS.
Nous avons décidé de le publier en open source, sous le nom de gnirehtet.
Oui, c’est un nom bizarre, jusqu’à ce qu’on réalise qu’il s’agit du résultat de la commande bash :
rev <<< tethering
Il suffit de télécharger la dernière release, de l’extraire, et d’exécuter la commande suivante sur le PC :
./gnirehtet rt
Une fois activé, un logo en forme de clé apparaît dans la barre de statut du téléphone :
Lisez le fichier README pour plus de détails.
Le projet est composé de deux parties :
Le client s’enregistre en tant que VPN, de manière à intercepter tout le trafic
réseau du téléphone, sous la forme de byte[]
de paquets IPv4 bruts, qu’il
transmet alors vers le serveur relais sur une connexion TCP (établie
par-dessus adb).
Le serveur relais analyse les en-têtes des paquets, ouvre des connexions à partir du PC vers les adresses de destinations demandées, et relaie le contenu dans les deux sens en suivant les protocoles UDP et TCP. Il crée et renvoie des paquets de réponse vers le client Android, qui les écrit sur l’interface VPN.
D’une certaine manière, le serveur relais se comporte comme un NAT, en cela qu’il ouvre des connexions pour le compte d’autres machines qui n’ont pas accès au réseau. Cependant, il diffère des NAT standards dans la manière dont il communique avec les clients, en utilisant un protocole spécifique (très simple) sur une connexion TCP.
Pour plus de détails, lisez la page développeurs.
Une fois que l’application est capable d’intercepter l’intégralité du traffic réseau du téléphone, différentes approches sont possibles. Voici celles que j’ai considérées.
TL;DR: J’ai d’abord étudié l’utilisation d’un “TUN device” sur le PC, mais ça ne répondait pas à nos besoins. J’ai ensuite voulu utiliser SOCKS pour bénéficier des serveurs existants, mais des contraintes nous empêchaient de relayer le trafic UDP. Alors j’ai implémenté gnirehtet.
Lors de mes recherches pour savoir comment implémenter le reverse tethering,
j’ai d’abord trouvé des projets créant un TUN device sur l’ordinateur
(vpn-reverse-tether
and SimpleRT
).
Cette conception fonctionne très bien, et a plusieurs avantages :
Cependant :
Il se peut néanmoins que ces applications répondent davantage à vos besoins.
Afin d’éviter d’avoir à développer un serveur relais spécifique, ma première
idée était d’écrire un client qui parlait le protocole SOCKS (suivant le RFC
1928). Ainsi, il serait possible d’utiliser n’importe quel serveur SOCKS
existant, par exemple celui fourni par ssh -D
.
Vous l’avez probablement déjà utilisé pour éviter le filtrage des pare-feux en entreprise. Pour cela, démarrez le tunnel :
ssh mon_serveur -ND1080
Puis configurez votre navigateur pour utiliser le proxy SOCKS localhost:1080
.
N’oubliez pas d’activer la résolution DNS distante pour résoudre les noms de
domaine à partir de mon_serveur
(dans Firefox, activez
network.proxy.socks_remote_dns
dans about:config
).
Malheureusement, l’implémentation d’OpenSSH ne supporte pas UDP, même si le protocole SOCKS5 lui-même le supporte. Et nous avons besoin d’UDP, au moins pour les requêtes DNS (ainsi que pour NTP).
Si vous avez lu attentivement les deux paragraphes précédents, vous devriez vous demander :
Comment Firefox peut-il résoudre les noms de domaine à distance alors que le proxy SOCKS d’OpenSSH ne supporte même pas UDP ?
La réponse se trouve dans la section 4 du RFC : l’adresse de destination demandée peut être une IPv4, une IPv6 ou un nom de domaine. Par contre, pour utiliser cette fonctionnalité, le client (par exemple Firefox) doit savoir qu’il passe par un proxy (puisqu’il doit explicitement passer le nom de domaine au lieu de le résoudre localement), alors que notre reverse tethering doit être transparent.
Mais tout n’est pas perdu. Certes, OpenSSH ne supporte pas UDP, mais ce n’est
qu’une implémentation spécifique, nous pourrions en utiliser une autre.
Malheureusement, SOCKS5 relaie UDP sur UDP, et les téléphones
et l’ordinateur communiquent sur adb (grâce à adb reverse
), qui ne supporte
pas non plus la redirection de ports UDP.
Peut-être que nous pourrions au moins relayer les requêtes DNS en les forçant à utiliser TCP, comme le fait tsocks :
tsocks will normally not be able to send DNS queries through a SOCKS server since SOCKS V4 works on TCP and DNS normally uses UDP. Version 1.5 and up do however provide a method to force DNS lookups to use TCP, which then makes them proxyable.
Mais finalement, SOCKS n’est plus une solution aussi attirante pour implémenter le reverse tethering.
Par conséquent, j’ai développé à la fois le client et le serveur relais manuellement.
Ce billet de blog et différents projets open source (SimpleRT
,
vpn-reverse-tether
, LocalVPN
et ToyVpn
) m’ont beaucoup aidé à comprendre
comment implémenter cette solution de reverse tethering.
Gnirehtet permet aux téléphones et tablettes Android d’utiliser facilement la connection internet d’un ordinateur par USB, sans accès root. C’est très utile quand vous ne pouvez pas accéder au réseau par un point d’accès WiFi.
J’espère qu’il pourra être utile à certains d’entre vous.
L’objectif de ce billet est de parvenir à nous connecter à un serveur a priori inaccessible derrière un NAT.
De nos jours, TCP est toujours utilisé en mode client-serveur :
Une fois la connexion établie, cependant, le client et le serveur jouent exactement le même rôle au niveau de la communication. Par contre, très souvent, leur rôle applicatif dépend directement de celui qui a initié la connexion :
Ce fonctionnement paraît tellement naturel que “client” désigne bien souvent à la fois celui qui initie la connexion et celui qui effectue des requêtes (au serveur), alors que “serveur” désigne aussi bien la partie en écoute que celle qui répondra aux requêtes (des clients).
Avec la pénurie d’adresses IPv4, le NAT s’est généralisé. Bien souvent, un accès internet ne fournit qu’une seule adresse IPv4. Les différents ordinateurs partageant la même connexion ne sont alors pas accessibles directement depuis l’extérieur (il est nécessaire d’ouvrir des ports).
Ainsi, derrière un NAT sans ports ouverts, un serveur ne sera pas accessible publiquement. Par contre, un client pourra continuer à se connecter à n’importe quel serveur public.
Il existe des situations pour lesquelles nous souhaitons qu’un logiciel joue le rôle de serveur au niveau applicatif, afin de répondre aux requêtes des clients, mais client au niveau de la communication, afin de passer les NATs sans difficultés.
Par exemple, nous pouvons vouloir accéder, grâce à VNC ou SSH, à un ordinateur se trouvant derrière un NAT sur lequel, par hypothèse, nous n’avons pas la main. Dans ce cas, seul le serveur (au sens applicatif) aura la capacité d’ouvrir une connexion vers le client.
Il est possible d’utiliser un logiciel spécialement conçu pour gérer cette inversion des rôles. C’est le cas par exemple de gitso, qui inverse le protocole VNC afin de simplifier l’aide de novices à distance.
Cette solution a cependant l’inconvénient d’être très spécifique, nécessitant un développement supplémentaire pour chaque protocole.
SSH permet d’ouvrir un tunnel pour rediriger un port d’une machine distance vers une adresse quelconque.
Par exemple, après avoir démarré la redirection :
ssh un_serveur_public -NR2222:localhost:22
toutes les connexions arrivant sur un_serveur_public:2222
seront redirigées de
manière transparente vers localhost:22
(sur la machine ayant initié le tunnel,
donc).
(Cela nécessite d’activer GatewayPorts yes
dans /etc/ssh/sshd_config
sur
un_serveur_public
.)
De cette manière, un serveur SSH inaccessible derrière un NAT est rendu
accessible à travers un tunnel en passant par une machine publique
(un_serveur_public
). Ainsi, il est possible de s’y connecter avec la
commande :
ssh un_serveur_public -p2222
Cette stratégie fonctionne bien, mais elle nécessite que la machine qui souhaite
exposer un serveur grâce à un tunnel possède un accès SSH sur
un_serveur_public
.
Si l’on souhaite aider quelqu’un grâce à la prise de contrôle de sa machine à distance, il y a toutes les chances que cette personne n’ait pas d’accès SSH vers une machine publiquement accessible. Il est alors possible de lui créer un compte restreint dédié sur un serveur que l’on contrôle, mais c’est très intrusif, et il faut s’assurer de ne pas réduire la sécurité.
Mais en fait, cette contrainte est superflue.
La redirection de port distant nécessite des permissions car, outre le fait qu’elle est implémentée sur SSH, il serait déraisonnable d’autoriser n’importe qui à ouvrir une socket en écoute sur un port arbitraire d’une machine distante.
Pour éviter ce problème, nous pouvons décomposer la redirection de port distant fourni par SSH en deux parties :
un_serveur_public
, redirigée vers
l’adresse localhost:22
dans l’exemple précédent ;2222
) de la machine
distante, redirigée vers la première connexion.L’idée est de mettre en place le premier demi-tunnel sur la machine serveur, et le second demi-tunnel, nécessitant des permissions, sur la machine publique, contrôlée par le client.
Pour cela, nous allons utiliser l’outil socat
, qui permet de relayer les
données entre deux sockets, quelque soit le rôle qu’elles aient joué lors de
l’initialisation.
Pour comprendre son utilisation, nous allons ouvrir grâce à netcat (nc
) une
socket TCP en écoute sur le port 5000
et nous y connecter :
Toute entrée validée par un retour à la ligne dans le terminal 1 s’affichera dans le terminal 2 (et vice-versa).
Démarrons maintenant dans deux terminaux différents une socket en écoute sur les
ports 1111
et 2222
:
Pour les mettre en communication avec socat
, dans un 3e terminal :
socat tcp:localhost:1111 tcp:localhost:2222
Inversement, il est possible de mettre en communication deux sockets actives (sans compter sur leur synchronisation). Pour cela, commençons par ouvrir le serveur relai :
socat tcp-listen:1111 tcp-listen:2222
Puis connectons-y deux sockets :
Nous sommes maintenant prêts pour créer l’équivalent d’une redirection de port
distant SSH grâce à deux socat
s, qui vont permettre d’inverser la connexion
uniquement sur la portion qui permet de traverser le NAT :
Le 23 février, une équipe de chercheurs a annoncé avoir cassé SHA-1 en pratique, en générant une collision.
À partir de leur travail, il est possible de produire de nouvelles paires de fichiers PDF arbitrairement différents qui auront la même signature SHA-1. Par exemple :
$ sha1sum shadow1.pdf shadow2.pdf
fffe36a1d6f0a76a585af4f3838a4a46b6714f0c shadow1.pdf
fffe36a1d6f0a76a585af4f3838a4a46b6714f0c shadow2.pdf
$ sha256sum shadow1.pdf shadow2.pdf
502ccf8ecee10176d891fa4aeab295edec22b95141c2ae16d85f13b39879e37e shadow1.pdf
2546d272df653c5a99ef0914fa6ed43b336f309758ea873448154ebde90cdfe1 shadow2.pdf
J’explique dans ce billet le principe, et je fournis un outil qui produit, à partir de deux images JPEG, deux fichiers PDF différents de même SHA-1.
En fabriquant leur collision, les auteurs ont pris soin de la rendre réutilisable :
Furthermore, the prefix of the colliding messages was carefully chosen so that they allow an attacker to forge two PDF documents with the same SHA-1 hash yet that display arbitrarily-chosen distinct visual content.
Aujourd’hui, nous allons jouer aux attaquants.
La réutilisation de la collision repose sur le fait qu’avec SHA-1, ajouter un suffixe identique à une collision existante produit encore une collision :
SHA1(A) == SHA1(B) ==> SHA1(A|X) == SHA1(B|X)
(où X|Y
est la concaténation de X
et de Y
)
Autrement dit, vous prenez les fichiers qui produisent une collision, vous ajoutez les mêmes octets aux deux, vous obtenez le même SHA-1 :
$ { cat shattered-1.pdf; echo bonjour; } | sha1sum
4bfd4b804da3aa207b29d6f1300dde507988dc4b -
$ { cat shattered-2.pdf; echo bonjour; } | sha1sum
4bfd4b804da3aa207b29d6f1300dde507988dc4b -
Il est donc trivial de créer de nouvelles collisions.
Mais pour qu’elles aient un intérêt, encore faut-il :
Les différences entre shattered-1.pdf
et shattered-2.pdf
se situent entre
les adresses 0xc0
et 0x13f
:
Nous devrons donc, quoi qu’il arrive, conserver les 0x140
(320) premiers
octets : il s’agira forcément d’un fichier PDF.
Pour analyser la structure sur un exemple minimal, je vous conseille l’exemple
fourni à la dernière page du papier (good.pdf
et bad.pdf
) :
<< -- base64 -d | tar xj
QlpoOTFBWSZTWbL5V5MABl///////9Pv///v////+/////HDdK739/677r+W3/75rUNr4Aa/AAAAAAA
CgEVTRtQDQAaA0AAyGmjTQGmgAAANGgAaMIAYgGgAABo0AAAAAADQAIAGQ0MgDIGmjQA0DRk0AaMQ0D
QAGIANGgAAGRoNGQMRpo0GIGgBoGQAAIAGQ0MgDIGmjQA0DRk0AaMQ0DQAGIANGgAAGRoNGQMRpo0GI
GgBoGQAAIAGQ0MgDIGmjQA0DRk0AaMQ0DQAGIANGgAAGRoNGQMRpo0GIGgBoGQAAIAGQ0MgDIGmjQA0
DRk0AaMQ0DQAGIANGgAAGRoNGQMRpo0GIGgBoGQAABVTUExEZATTICnkxNR+p6E09JppoyamjGhkm0a
mmIyaekbUejU9JiGnqZqaaDxJ6m0JkZMQ2oaYmJ6gxqMyE2TUzJqfItligtJQJfYbl9Zy9QjQuB5mHQ
RdSSXCCTHMgmSDYmdOoOmLTBJWiCpOhMQYpQlOYpJjn+wQUJSTCEpOMekaFaaNB6glCC0hKEJdHr6Bm
UIHeph7YxS8WJYyGwgWnMTFJBDFSxSCCYljiEk7HZgJzJVDHJxMgY6tCEIIWgsKSlSZ0S8GckoIIF+5
51Ro4RCw260VCEpWJSlpWx/PMrLyVoyhWMAneDilBcUIeZ1j6NCkus0qUCWnahhk5KT4GpWMh3vm2nJ
WjTL9Qg+84iExBJhNKpbV9tvEN265t3fu/TKkt4rXFTsV+NcupJXhOhOhJMQQktrqt4K8mSh9M2DAO2
X7uXGVL9YQxUtzQmS7uBndL7M6R7vX869VxqPurenSuHYNq1yTXOfNWLwgvKlRlFYqLCs6OChDp0HuT
zCWscmGudLyqUuwVGG75nmyZhKpJyOE/pOZyHyrZxGM51DYIN+Jc8yVJgAykxKCEtW55MlfudLg3KG6
TtozalunXrroSxUpVLStWrWLFihMnVpkyZOrQnUrE6xq1CGtJlbAb5ShMbV1CZgqlKC0wCFCpMmUKSE
kvFLaZC8wHOCVAlvzaJQ/T+XLb5Dh5TNM67p6KZ4e4ZSGyVENx2O27LzrTIteAreTkMZpW95GS0CEJY
hMc4nToTJ0wQhKEyddaLb/rTqmgJSlkpnALxMhlNmuKEpkEkqhKUoEq3SoKUpIQcDgWlC0rYahMmLuP
Q0fHqZaF4v2W8IoJ2EhMhYmSw7qql27WJS+G4rUplToFi2rSv0NSrVvDUpltQ8Lv6F8pXyxmFBSxiLS
xglNC4uvXVKmAtusXy4YXGX1ixedEvXF1aX6t8adYnYCpC6rW1ZzdZYlCCxKEv8vpbqdSsXl8v1jCQv
0KEPxPTa/5rtWSF1dSgg4z4KjfIMNtgwWoWLEsRhKxsSA9ji7V5LRPwtumeQ8V57UtFSPIUmtQdOQfs
eI2Ly1DMtk4Jl8n927w34zrWG6Pi4jzC82js/46Rt2IZoadWxOtMInS2xYmcu8mOw9PLYxQ4bdfFw3Z
Pf/g2pzSwZDhGrZAl9lqky0W+yeanadC037xk496t0Dq3ctfmqmjgie8ln9k6Q0K1krb3dK9el4Xsu4
4LpGcenr2eQZ1s1IhOhnE56WnXf0BLWn9Xz15fMkzi4kpVxiTKGEpffErEEMvEeMZhUl6yD1SdeJYbx
zGNM3ak2TAaglLZlDCVnoM6wV5DRrycwF8Zh/fRsdmhkMfAO1duwknrsFwrzePWeMwl107DWzymxdQw
iSXx/lncnn75jL9mUzw2bUDqj20LTgtawxK2SlQg1CCZDQMgSpEqLjRMsykM9zbSIUqil0zNk7Nu+b5
J0DKZlhl9CtpGKgX5uyp0idoJ3we9bSrY7PupnUL5eWiDpV5mmnNUhOnYi8xyClkLbNmAXyoWk7GaVr
M2umkbpqHDzDymiKjetgzTocWNsJ2E0zPcfht46J4ipaXGCfF7fuO0a70c82bvqo3HceIcRlshgu73s
eO8BqlLIap2z5jTOY+T2ucCnBtAtva3aHdchJg9AJ5YdKHz7LoA3VKmeqxAlFyEnQLBxB2PAhAZ8Kvm
uR6ELXws1Qr13Nd1i4nsp189jqvaNzt+0nEnIaniuP1+/UOZdyfoZh57ku8sYHKdvfW/jYSUks+0rK+
qtte+py8jWL9cOJ0fV8rrH/t+85/p1z2N67p/ZsZ3JmdyliL7lrNxZUlx0MVIl6PxXOUuGOeArW3vuE
vJ2beoh7SGyZKHKbR2bBWO1d49JDIcVM6lQtu9UO8ec8pOnXmkcponBPLNM2CwZ9kNC/4ct6rQkPkQH
McV/8XckU4UJCy+VeTA==
--
Notre objectif est que les quelques octets différents entre les deux fichiers PDF déterminent l’image à afficher.
Il serait en théorie possible d’appliquer cet aiguillage au niveau de la structure du PDF, mais c’est en fait au niveau du JPEG qu’il sera implémenté :
PDFs with the same MD5 hash have previously been constructed by Gebhardt et al. [12] by exploiting so-called Indexed Color Tables and Color Transformation functions. However, this method is not effective for many common PDF viewers that lack support for these functionalities. Our PDFs rely on distinct parsings of JPEG images, similar to Gebhardt et al.’s TIFF technique [12] and Albertini et al.’s JPEG technique [1].
Voici le strict nécessaire à savoir sur le format JPEG pour notre besoin.
Une image est stockée entre les marqueurs 0xffd8
(Start Of Image) et
0xffd9
(End Of Image).
Il est possible d’insérer autant de commentaires que l’on veut, grâce au
marqueur 0xfffe
suivi de sa taille sur 2 octets (en big-endian). La taille
compte le header de taille, mais pas le marqueur initial.
Par exemple, si je veux insérer le commentaire “Hello” au tout début, mon fichier JPEG ressemblera à ceci :
ff d8 ff fe 00 07 48 65 6c 6c 6f … ff d9
[SOI] [EOI]
[[COM] [LEN] H e l l o]
<------------------->
7
Et c’est à peu près tout ce qu’il y a à savoir.
Mettons en évidence la première différence entre les fichiers en collision.
Dans le fichier 1 :
000000b0 -- -- -- -- -- -- -- -- -- -- -- -- -- ff fe 01
000000c0 73 -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
Dans le fichier 2 :
000000b0 -- -- -- -- -- -- -- -- -- -- -- -- -- ff fe 01
000000c0 7f -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
Chacun définit un bloc de commentaires, mais pas de mêmes tailles. Dans le
fichier 1, le début du prochain bloc sera à l’adresse 0x232
(0xbf + 0x173
),
alors que dans le fichier 2 il sera à l’adresse 0x23e
(0xbf + 0x17f
).
Nous avons donc trouvé notre aiguillage ; nous allons maintenant utiliser des commentaires JPEG pour cacher soit la première image, soit la seconde.
Pour l’exploiter jusqu’au bout, il suffit de disposer les commentaires astucieusement pour que les deux versions représentent des images parfaitement valides.
Nous allons donc commencer en 0x232
un bloc de commentaires, ayant une taille
permettant de recouvrir l’intégralité de l’image que nous allons stocker en
0x23e
. Et inversement, nous devons démarrer un commentaire à la fin de l’image
stockée en 0x23e
pour cacher la deuxième image.
Comparons sur le résultat ce qu’observe un parseur qui parcourt chacun des fichiers.
(GG
et HH
sont les deux images à stocker. J1
et J2
sont les longueurs
des sauts pour enjamber chacune des images.)
Le fichier 1 est parsé ainsi :
00000090 -- -- -- -- -- ff d8 -- -- -- -- -- -- -- -- --
…
000000b0 -- -- -- -- -- -- -- -- -- -- -- -- -- ff fe 01
000000c0 73 -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
…
00000230 -- -- ff fe J1 J1 -- -- -- -- -- -- -- -- GG GG
00000240 GG GG GG GG GG GG GG GG GG GG GG GG GG GG GG GG
…
i GG GG GG GG GG GG ff fe J2 J2 HH HH HH HH HH HH
i+0x10 HH HH HH HH HH HH HH HH HH HH HH HH HH HH HH HH
…
j HH HH ff d9 -- -- -- -- -- -- -- -- -- -- -- --
Le fichier 2 est parsé différemment :
00000090 -- -- -- -- -- ff d8 -- -- -- -- -- -- -- -- --
…
000000b0 -- -- -- -- -- -- -- -- -- -- -- -- -- ff fe 01
000000c0 7f -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
…
00000230 -- -- ff fe J1 J1 -- -- -- -- -- -- -- -- GG GG
00000240 GG GG GG GG GG GG GG GG GG GG GG GG GG GG GG GG
…
i GG GG GG GG GG GG ff fe J2 J2 HH HH HH HH HH HH
i+0x10 HH HH HH HH HH HH HH HH HH HH HH HH HH HH HH HH
…
j HH HH ff d9 -- -- -- -- -- -- -- -- -- -- -- --
Les structures JPEG sont donc valides dans les deux fichiers. L’image affichée
dépendra de l’octet stocké à l’adresse 0xc0
, valant soit 0x73
, soit 0x7f
.
Maintenant, il nous reste à rendre notre PDF valide.
Le header participant à la collision SHA-1 (donc figé) définit des configurations dans des sections séparées (donc non figées) :
00000000 25 50 44 46 2d 31 2e 33 0a 25 e2 e3 cf d3 0a 0a |%PDF-1.3.%......|
00000010 0a 31 20 30 20 6f 62 6a 0a 3c 3c 2f 57 69 64 74 |.1 0 obj.<</Widt|
00000020 68 20 32 20 30 20 52 2f 48 65 69 67 68 74 20 33 |h 2 0 R/Height 3|
00000030 20 30 20 52 2f 54 79 70 65 20 34 20 30 20 52 2f | 0 R/Type 4 0 R/|
00000040 53 75 62 74 79 70 65 20 35 20 30 20 52 2f 46 69 |Subtype 5 0 R/Fi|
00000050 6c 74 65 72 20 36 20 30 20 52 2f 43 6f 6c 6f 72 |lter 6 0 R/Color|
00000060 53 70 61 63 65 20 37 20 30 20 52 2f 4c 65 6e 67 |Space 7 0 R/Leng|
00000070 74 68 20 38 20 30 20 52 2f 42 69 74 73 50 65 72 |th 8 0 R/BitsPer|
00000080 43 6f 6d 70 6f 6e 65 6e 74 20 38 3e 3e 0a 73 74 |Component 8>>.st|
Ainsi, la largeur (Width
) est définie dans l’objet 2
, la hauteur (Height
)
dans l’objet 3
, etc.
Ces objets sont à définir à la suite des fichiers JPEG embarqués. Pour
comprendre leur format, le plus simple est de lire le fichier good.pdf
que je
recommandais plus haut :
On y trouve la définition des objets (entre autres les dimensions de l’image) :
2 0 obj
8
endobj
3 0 obj
8
endobj
4 0 obj
/XObject
endobj
5 0 obj
/Image
endobj
6 0 obj
/DCTDecode
endobj
7 0 obj
/DeviceRGB
endobj
8 0 obj
1693
endobj
9 0 obj
<<
/Type /Catalog
/Pages 10 0 R
>>
endobj
10 0 obj
<<
/Type /Pages
/Count 1
/Kids [11 0 R]
>>
endobj
11 0 obj
<<
/Type /Page
/Parent 10 0 R
/MediaBox [0 0 8 8]
/CropBox [0 0 8 8]
/Contents 12 0 R
/Resources
<<
/XObject <</Im0 1 0 R>>
>>
>>
endobj
12 0 obj
<</Length 30>>
stream
q
8 0 0 8 0 0 cm
/Im0 Do
Q
endstream
endobj
Ensuite vient la table de références croisées ; elle indique l’offset de chacun des objets définis, dans l’ordre :
xref
0 13
0000000000 65535 f
0000000017 00000 n
0000001861 00000 n
0000001879 00000 n
0000001897 00000 n
0000001922 00000 n
0000001945 00000 n
0000001972 00000 n
0000001999 00000 n
0000002020 00000 n
0000002076 00000 n
0000002142 00000 n
0000002309 00000 n
À chaque ajout ou suppression de caractères dans la définition des objets, cette table doit être mise à jour.
Le fichier se termine par un trailer, contenant l’offset de la table de références :
trailer << /Root 9 0 R /Size 13>>
startxref
2391
%%EOF
Ces offsets sont un peu fastidieux à modifier à la main, mais ça fonctionne.
J’ai donc écrit un petit outil qui applique toutes ces opérations automatiquement: SHAdow.
Il prend en entrée deux images JPEG (de moins de 64K, puisque la taille d’un commentaire est codé sur 2 octets), ainsi que leurs dimensions (afin d’éviter d’utiliser des dépendances pour les extraire) :
./shadow.py img1.jpg img2.jpg 200 200
Il génère deux fichiers dans le répertoire courant, shadow1.pdf
et
shadow2.pdf
.
Il ne reste qu’à vérifier qu’ils ont bien le même SHA-1 :
sha1sum shadow1.pdf shadow2.pdf
Les pointeurs sont utilisés plus souvent que nécessaire en C++.
Je voudrais présenter ici comment caractériser les utilisations abusives et par quoi les remplacer.
La décision d’utiliser des pointeurs dépend en grande partie de l’API des objets utilisés.
API est à comprendre dans un sens très large : je considère que des classes utilisées dans une autre partie d’une même application exposent une API.
L’objectif est donc de concevoir des API de manière à ce que leur utilisation ne nécessite pas de manipuler de pointeurs, ni même si possible de smart pointers.
Cela peut paraître surprenant, mais c’est en fait ainsi que vous utilisez les classes de la STL ou de Qt : vos méthodes ne retournent jamais un raw pointer ni un smart pointer vers une string nouvellement créée.
De manière générale, vous n’écririez pas ceci :
ni ceci :
À la place, vous écririez sûrement :
Notre objectif est d’écrire des classes qui s’utiliseront de la même manière.
Il faut distinguer deux types de raw pointers :
Le plus simple est de les comparer sur un exemple.
Ici, nous avons la responsabilité de supprimer info
au bon moment.
C’est ce type de pointeurs dont nous voulons nous débarrasser.
Ici, le pointeur permet juste de passer l’adresse de l’objet, mais la méthode
writeDataTo(…)
ne doit pas gérer sa durée de vie : elle ne le détient donc
pas.
Cet usage est tout-à-fait légitime, nous souhaitons le conserver.
Pour savoir si un pointeur est owning ou non, il suffit de se poser la
question suivante : est-ce que lui affecter nullptr
provoquerait une fuite
mémoire ?
Voici quelques exemples illustrant pourquoi nous voulons éviter les owning raw pointers.
Il est facile d’oublier de supprimer un pointeur dans des cas particuliers.
Par exemple :
Ici, si l’ouverture du fichier a échoué, parser
ne sera jamais libéré.
L’exemple suivant est encore plus significatif :
Appeler une méthode sans s’occuper du résultat peut provoquer des fuites mémoires.
Il est également possible, par inattention, de supprimer plusieurs fois le même pointeur (ce qui entraîne un undefined behavior).
Par exemple, si device
fait partie de la liste devices
, ce code le supprime
deux fois :
L’utilisation d’un pointeur après sa suppression est également indéfinie.
Je vais prendre un exemple réel en Qt.
Supposons qu’une classe DeviceMonitor
surveille le branchement de
périphériques, et crée pour chacun un objet Device
.
Lorsqu’un périphérique est débranché, un signal Qt provoque
l’exécution du slot DeviceMonitor::onDeviceLeft(Device *)
. Nous voulons
alors signaler au reste de l’application que le device est parti (signal
DeviceMonitor::deviceLeft(Device *)
), puis supprimer l’object device
correspondant :
Mais c’est loin d’être trivial.
Si nous le supprimons immédiatement comme ceci, et qu’un slot est branché à
DeviceMonitor::deviceLeft(Device *)
en
Qt::QueuedConnection
, alors il est possible que le pointeur
soit déjà supprimé quand ce slot sera exécuté.
Un proverbe dit que quand ça crashe avec un delete
, “il faut appeller
deleteLater()
pour corriger le problème” :
Mais malheureusement, ici, c’est faux : si le slot branché au signal
DeviceMonitor::deviceLeft(Device *)
est associé à un QObject
vivant dans un autre thread, rien ne garantit que son
exécution aura lieu avant la suppression du pointeur.
L’utilisation des owning raw pointers n’est donc pas seulement vulnérable aux erreurs d’inattention (comme dans les exemples précédents) : dans des cas plus complexes, il devient difficile de déterminer quand supprimer le pointeur.
De manière plus générale, lorsque nous avons un pointeur, nous ne savons pas forcément qui a la responsabilité de le supprimer, ni comment le supprimer :
Qt fournit un mécanisme pour supprimer automatiquement les QObject *
quand
leur parent est détruit. Cependant, cette fonctionnalité ne s’applique qu’aux
relations de composition.
Résumons les inconvénients des owning raw pointeurs :
Laissons de côté les pointeurs quelques instants pour observer ce qu’il se passe avec de simples valeurs (des objets plutôt que des pointeurs vers des objets) :
C’est plus simple : la gestion mémoire est automatique, et le code est plus sûr. Par exemple, les fuites mémoire et les double suppressions sont impossibles.
Ce sont des avantages dont nous souhaiterions bénéficier également pour les pointeurs.
Dans les cas où les pointeurs sont utilisés uniquement pour éviter de retourner des copies (et non pour partager des objets), il est préférable de retourner les objets par valeur à la place.
Par exemple, si vous avez une classe :
Évitez :
Préférez :
Certes, dans certains cas, il est moins efficace de passer un objet par valeur qu’à travers un pointeur (car il faut le copier).
Mais cette inefficacité est à relativiser.
D’abord parce que dans certains cas (quand l’objet est copié à partir d’une
rvalue reference), la copie sera remplacée par un move. Le move
d’un vector
par exemple n’entraîne aucune copie (ni move) de ses
éléments.
Ensuite parce que les compilateurs optimisent le retour par valeur
(RVO), ce qui fait qu’en réalité dans les exemples ci-dessus, aucun Result
ni Vector
n’est jamais copié ni mové : ils sont directement créés à
l’endroit où ils sont affectés (sauf si vous compilez avec le paramètre
-fno-elide-constructors
).
Mais évidemment, il y a des cas où nous ne pouvons pas simplement remplacer un pointeur par une valeur, par exemple quand un même objet doit être partagé entre différentes parties d’un programme.
Nous voudrions les avantages des valeurs également pour ces cas-là. C’est l’objectif de la suite du billet.
Pour y parvenir, nous avons besoin de faire un détour par quelques idiomes couramment utilisés en C++.
Ils ont souvent un nom étrange. Par exemple :
Nous allons étudier les deux premiers.
Prenons un exemple simple :
Nous souhaitons rendre cette méthode thread-safe grâce à un mutex
(std::mutex
en STL ou QMutex
en Qt).
Supposons que validate()
et something()
puissent lever une exception.
Le mutex doit être déverrouillé à la fin de l’exécution de la méthode. Le problème, c’est que cela peut se produire à différents endroits, donc nous devons gérer tous les cas :
Le code est beaucoup plus complexe et propice aux erreurs.
Avec des classes utilisant RAII (std::lock_guard
en STL ou
QMutexLocker
en Qt), c’est beaucoup plus simple :
En ajoutant une seule ligne, la méthode est devenue thread-safe.
Cette technique consiste à utiliser le cycle de vie d’un objet pour acquérir une ressource dans le constructeur (ici verrouiller le mutex) et la relâcher dans le destructeur (ici le déverrouiller).
Voici une implémentation simplifiée possible de QMutexLocker
:
Comme l’objet est détruit lors de la sortie du scope de la méthode (que ce
soit par un return
ou par une exception survenue n’importe où), le mutex
sera toujours déverrouillé.
Au passage, dans l’exemple ci-dessus, nous remarquons que la variable locker
n’est jamais utilisée. RAII complexifie donc la détection des variables
inutilisées, car le compilateur doit détecter les effets de bords. Mais il s’en
sort bien : ici, il n’émet pas de warning.
Les smart pointers utilisent RAII pour gérer automatiquement la durée de vie des pointeurs. Il en existe plusieurs.
Dans la STL :
std::unique_ptr
std::shared_ptr
std::weak_ptr
std::auto_ptr
(à bannir)Dans Qt :
QSharedPointer
(équivalent de std::shared_ptr
)QWeakPointer
(équivalent de std::weak_ptr
)QScopedPointer
(ersatz de std::unique_ptr
)QScopedArrayPointer
QPointer
QSharedDataPointer
QExplicitlySharedDataPointer
Le smart pointer le plus simple est le scoped pointer. L’idée est vraiment
la même que QMutexLocker
, sauf qu’au lieu de vérouiller et
déverrouiller un mutex, il stocke un raw pointer et le supprime.
En plus de cela, comme tous les smart pointers, il redéfinit certains opérateurs pour pouvoir être utilisé comme un raw pointer.
Par exemple, voici une implémentation simplifiée possible de
QScopedPointer
:
Et un exemple d’utilisation :
Les shared pointers permettent de partager l’ownership (la responsabilité de suppression) d’une ressource.
Ils contiennent un compteur de références, indiquant le nombre d’instances partageant le même pointeur. Lorsque ce compteur tombe à 0, le pointeur est supprimé (il faut donc éviter les cycles).
En pratique, voici ce à quoi ressemblerait une liste de Device
s partagés par
des QSharedPointer
s :
Le partage d’un pointeur découle toujours de la copie d’un shared pointer.
C’est la raison pour laquelle getDevice(…)
et add(…)
manipulent un
QSharedPointer
.
Le piège à éviter est de créér plusieurs smart pointers indépendants sur le même raw pointer. Dans ce cas, il y aurait deux refcounts à 1 plutôt qu’un refcount à 2, et le pointeur serait supprimé dès la destruction du premier shared pointer, laissant l’autre pendouillant.
Petite parenthèse : la signature des méthodes add
et remove
sont
différentes car une suppression ne nécessite pas de manipuler la durée de
vie du Device
passé en paramètre.
Refcounted smart pointers are about managing te owned object’s lifetime.
Copy/assign one only when you intend to manipulate the owned object’s lifetime.
Au passage, si en Qt vous passez vos objets de la couche C++ à la couche QML, il faut aussi passer les shared pointers afin de ne pas casser le partage, ce qui implique d’enregistrer le type :
Listons donc les avantages des shared pointers :
Cependant, si la gestion mémoire est automatique, elle n’est pas
transparente : elle nécessite de manipuler explicitement des
QSharedPointer
, ce qui est verbeux.
Il est certes possible d’utiliser un alias (typedef) pour atténuer la verbosité :
Mais quoi qu’il en soit, cela reste plus complexe que des valeurs.
Pour aller plus loin, nous allons devoir faire un détour inattendu, par un idiome qui n’a a priori rien à voir.
PImpl sert à réduire les dépendances de compilation.
Opaque pointers are a way to hide the implementation details of an interface from ordinary clients, so that the implementation may be changed without the need to recompile the modules using it.
Prenons la classe Person
suivante (person.h
) :
Elle contient juste un nom et un âge. Elle définit par ailleurs une méthode
privée, countYears(…)
, qu’on imagine appelée dans getAge()
.
Chaque classe désirant utiliser la classe Person
devra l’inclure :
Par conséquent, à chaque modification de ces parties privées (qui sont pourtant
que des détails d’implémentation), toutes les classes incluant person.h
devront être recompilées.
C’est ce que PImpl permet d’éviter, en séparant la classe en deux :
Concrètement, la classe Person
précédente est la partie privée. Renommons-la :
Créons la partie publique, définissant l’interface souhaitée :
Elle contient un pointeur vers PersonPrivate
, et lui délègue tous les appels.
Évidemment, Person
ne doit pas inclure PersonPrivate
, sinon nous aurions les
mêmes dépendances de compilation, et nous n’aurions rien résolu. Il faut
utiliser à la place une forward declaration.
Voici son implémentation :
Le pointeur vers la classe privée est souvent nommé d
car il s’agit d’un
d-pointer.
Donc comme prévu, tout cela n’a rien à voir avec notre objectif d’éviter d’utiliser des pointeurs.
Mais en fait, si. PImpl permet de séparer les classes manipulées explicitement de l’objet réellement modifié :
Il y a une relation 1-1 entre la classe publique et la classe privée correspondante. Mais nous pouvons imaginer d’autres cardinalités.
Par exemple, Qt partage implicitement les parties privées d’un grand nombre de classes. Il ne les copie que lors d’une écriture (CoW) :
Par exemple, lorsqu’une QString
est copiée, la même zone mémoire
sera utilisée pour les différentes instances, jusqu’à ce qu’une modification
survienne.
Cependant, il ne s’agit que d’un détail d’implémentation utilisé pour améliorer les performances. Du point de vue utilisateur, tout se passe comme si les données étaient réellement copiées :
En d’autres termes, les classes publiques ci-dessus ont une sémantique de valeur.
À la place, nous pouvons décider de partager inconditionnellement la partie privée, y compris après une écriture :
Dans ce cas, la classe publique a sémantique d’entité. Elle est qualifiée de resource handle.
C’est bien sûr le cas des smart pointers :
Mais aussi d’autres classes, comme l’API Dom de Qt :
Tout-à-l’heure, j’ai présenté PImpl en utilisant un owning raw pointer :
Mais en fait, à chaque type de relation correspond un type de smart pointer directement utilisable pour PImpl.
Pour une relation 1-1 classique :
Pour une relation 1-N à sémantique de valeur (CoW) :
Pour une relation 1-N à sémantique d’entité :
Par exemple, donnons à notre classe Person
une sémantique d’entité :
Person
se comporte maintenant comme un pointeur.
p1
et p2
sont alors des resource handles vers PersonPrivate
:
Évidemment, ce n’est pas approprié pour la classe Person
, car le comportement
est trop inattendu.
Mais je vais présenter un cas réel où ce design est approprié.
Pour l’entreprise dans laquelle je suis salarié, j’ai implémenté une fonctionnalité permettant d’utiliser une souris USB branchée sur un PC pour contrôler un téléphone Android connecté en USB.
Concrètement, cela consiste à tranférer (grâce à libusb
), à partir
du PC, les événements HID reçus de la souris vers le téléphone Android.
J’ai donc (entre autres) créé des resources handles UsbDevice
et
UsbDeviceHandle
qui wrappent les structures C libusb_device
et libusb_device_handle
, suivant les principes
détaillés dans ce billet.
Leur utilisation illustre bien, d’après moi, les bénéfices d’une telle conception.
UsbDevice
peut être retourné par valeur, et passé en paramètre d’un signal
par const reference (exactement comme nous le ferions avec un
QString
).
Si une souris est trouvée dans la liste, on la retourne simplement ; sinon, on
retourne un UsbDevice
“null”.
La gestion mémoire est totalement automatique et transparente. Les problèmes présentés sont résolus.
UsbDevice
peut naviguer entre la couche C++ et QML.
Grâce à RAII, les connexions (UsbDeviceHandle
) sont fermées automatiquement.
En particulier, si la connexion à la souris échoue, la connexion au téléphone Android est automatiquement fermée.
Dans ces différents exemples, new
et delete
ne sont jamais utilisés, et
par construction, la mémoire sera correctement gérée. Ou plus précisément,
si un problème de gestion mémoire existe, il se situera dans l’implémentation de
la classe elle-même, et non partout où elle est utilisée.
Ainsi, nous manipulons des handles se comportant comme des pointeurs, ayant les mêmes avantages que les valeurs :
Ils peuvent par contre présenter quelques limitations.
Par exemple, ils sont incompatibles avec QObject
. En effet,
techniquement, la classe d’un resource handle doit pouvoir être copiée (pour
supporter le passage par valeur), alors qu’un QObject
n’est pas
copiable :
QObject
s are identities, not values.
Très concrètement, cela implique que UsbDevice
ne pourrait pas supporter de
signaux (en tout cas, pas directement). C’est d’ailleurs le cas de beaucoup de
classes de Qt : par exemple QString
et QList
n’héritent
pas de QObject
.
C’est juste une heuristique…
En suivant ces principes, nous pouvons nous débarrasser des owning
raw pointers et des new
et delete
“nus”. Cela contribue à rendre le code
plus simple et plus robuste.
Ce sont d’ailleurs des objectifs qui guident les évolutions du langage C++ :
return 0;
Pour ce blog, j’ai abandonné Wordpress pour Jekyll, un moteur de blog statique.
Ainsi, j’écris mes articles en markdown dans mon éditeur favori, je les commite dans un dépôt git, et je génère le blog avec :
jekyll build
Le contenu hébergé étant statique, les pages ainsi générées à partir des sources sont renvoyées telles quelles.
Ce fonctionnement a beaucoup d’avantages :
git clone
, pas de base de données).L’inconvénient, c’est qu’un contenu statique est difficilement conciliable avec le support des commentaires (il faut bien d’une manière ou d’une autre exécuter du code lors de la réception d’un commentaire).
Il y a plusieurs manières de contourner le problème.
Il est par exemple possible d’en déporter la gestion (sur un service en ligne comme Disqus ou un équivalent libre – isso – à héberger soi-même). Ainsi, les commentaires peuvent être chargés séparément par le client en Javascript.
Au lieu de cela, j’ai choisi d’intégrer les commentaires aux sources du blog. Voici comment.
L’objectif est d’une part de pouvoir stocker et afficher les commentaires existants, et d’autre part de fournir aux lecteurs la possibilité d’en soumettre de nouveaux, qui me seront envoyés par e-mail.
Je me suis principalement inspiré du contenu de Jekyll::StaticComments, même si, comme nous allons le voir, je n’utilise pas le plug-in lui-même.
L’idée est de stocker les commentaires quelque part dans les sources du site au format YAML.
Le plugin Jekyll::StaticComments nécessite de stocker un fichier par
commentaire dans un dossier spécial (_comments
) parsé par un
script à insérer dans le répertoire _plugins
.
Personnellement, je préfère avoir tous les commentaires d’un même post regroupés
au sein d’un même fichier. Et pour cela, pas besoin de plug-in : nous pouvons
faire correspondre à chaque post dans _posts
une liste de
commentaires dans _data
(un répertoire géré nativement par Jekyll).
Par exemple, ce billet est stocké dans :
_posts/2017-01-09-commentaires-statiques-avec-jekyll.md
Dans l’idéal, je voudrais que les commentaires associés soient stockés dans :
_data/comments-2017-01-09-commentaires-statiques-avec-jekyll.yaml
En pratique, pour des raisons techniques (Jekyll ne donne pas accès au nom du fichier), le nom du fichier ne contient pas le numéro du jour :
_data/comments-2017-01-commentaires-statiques-avec-jekyll.yaml
Il suffit alors de stocker dans ces fichiers les commentaires sous cette forme :
Pour des exemples réels, voir les sources des commentaires de ce blog.
Maintenant que nous avons les données des commentaires, nous devons les afficher.
Il faut d’abord trouver la liste des commentaires associée à la page courante.
Comme nous ne pouvons pas récupérer directement le nom du fichier d’une page,
nous devons reconstruire la chaîne à partir de la variable page.id
, qui
ici vaut :
/2017/01/commentaires-statiques-avec-jekyll
Cette ligne de Liquid :
donne la valeur :
comments-2017-01-commentaires-statiques-avec-jekyll
Nous avons donc tout ce dont nous avons besoin pour créer le template de
commentaires (à stocker dans _include/comments.html
) :
Il suffit alors d’inclure cette page à l’endroit où vous souhaitez insérer les
commentaires (typiquement dans _layout/post.html
) :
Pour proposer aux utilisateurs de poster de nouveaux commentaires, il nous faut un formulaire.
À titre d’exemple, voici le mien (intégré à
_include/comments.html
) :
Ce formulaire est affiché sous les commentaires existants.
L’action
du formulaire précédent pointait sur
comments/submit.php
. Il nous reste donc à écrire dans ce fichier
le code à exécuter lorsqu’un utilisateur envoie un commentaire au serveur.
Ce sera la seule partie “dynamique” du site.
Voici les parties importantes de comments/submit.php
(basé sur
la version de Jekyll::StaticComments) :
Quand un commentaire est envoyé avec succès, la page
comments/sent.html
est affichée à l’utilisateur.
Ainsi, lorsqu’un commentaire est posté, je reçois un mail :
post_id: /2017/01/commentaires-statiques-avec-jekyll
email: my@email
---
- id: ?
author: ®om
author-url: http://blog.rom1v.com
date: 2017-01-09 19:27:10+01:00
contents: |
Ceci est un test.
J’ai d’ailleurs ajouté une règle procmail pour que ces mails arrivent dans un dossier dédié.
Je peux alors copier le contenu dans le .yaml
correspondant, formatter le
commentaire (entre autres l’indenter de 4 espaces, ce qu’on pourrait
automatiser), et le commiter.
Une fois mis en place, vous devriez donc avoir les fichiers suivants :
_data/comments-*.yaml
_include/comments.html
comments/submit.php
comments/sent.html
Je souhaitais depuis longtemps migrer vers un moteur de blog statique, qui correspond davantage à ma façon d’écrire des articles, et offre beaucoup d’avantages (légèreté, sécurité, maintenance…).
Je suis très content d’y être parvenu sans perdre les commentaires ni la possibilité d’en poster de nouveaux.
Certes, la validation est très manuelle, mais c’est le prix à payer pour avoir des commentaires statiques. Pour un blog avec une fréquence de commentaires assez faible, je pense que ce n’est pas très gênant.
Un collègue m’a envoyé récemment le lien vers ce challenge, utilisé pour recruter chez NERD (que je ne connais pas).
Je vous le partage car je l’ai trouvé très intéressant. Le but est de trouver un input qui donne l’output attendu.
Pour info, entre le moment où j’ai eu connaissance du problème et le moment où je l’ai résolu, il s’est écoulé 6 jours. Je n’ai pas travaillé dessus à plein temps, mais ne comptez pas le résoudre en 20 minutes
Je ne publie ni ma réponse au résultat attendu, ni les explications (ce serait incorrect vis-à-vis des auteurs du challenge). Je fournis par contre à la fin l’input qui donne comme output mon e-mail, ce qui suffit à prouver que j’ai résolu le problème.
Amusez-vous bien !
#include <string.h>
typedef unsigned char u8;
typedef unsigned int u32;
u8 confusion[512]={
0xac,0xd1,0x25,0x94,0x1f,0xb3,0x33,0x28,0x7c,0x2b,0x17,0xbc,0xf6,0xb0,0x55,0x5d,
0x8f,0xd2,0x48,0xd4,0xd3,0x78,0x62,0x1a,0x02,0xf2,0x01,0xc9,0xaa,0xf0,0x83,0x71,
0x72,0x4b,0x6a,0xe8,0xe9,0x42,0xc0,0x53,0x63,0x66,0x13,0x4a,0xc1,0x85,0xcf,0x0c,
0x24,0x76,0xa5,0x6e,0xd7,0xa1,0xec,0xc6,0x04,0xc2,0xa2,0x5c,0x81,0x92,0x6c,0xda,
0xc6,0x86,0xba,0x4d,0x39,0xa0,0x0e,0x8c,0x8a,0xd0,0xfe,0x59,0x96,0x49,0xe6,0xea,
0x69,0x30,0x52,0x1c,0xe0,0xb2,0x05,0x9b,0x10,0x03,0xa8,0x64,0x51,0x97,0x02,0x09,
0x8e,0xad,0xf7,0x36,0x47,0xab,0xce,0x7f,0x56,0xca,0x00,0xe3,0xed,0xf1,0x38,0xd8,
0x26,0x1c,0xdc,0x35,0x91,0x43,0x2c,0x74,0xb4,0x61,0x9d,0x5e,0xe9,0x4c,0xbf,0x77,
0x16,0x1e,0x21,0x1d,0x2d,0xa9,0x95,0xb8,0xc3,0x8d,0xf8,0xdb,0x34,0xe1,0x84,0xd6,
0x0b,0x23,0x4e,0xff,0x3c,0x54,0xa7,0x78,0xa4,0x89,0x33,0x6d,0xfb,0x79,0x27,0xc4,
0xf9,0x40,0x41,0xdf,0xc5,0x82,0x93,0xdd,0xa6,0xef,0xcd,0x8d,0xa3,0xae,0x7a,0xb6,
0x2f,0xfd,0xbd,0xe5,0x98,0x66,0xf3,0x4f,0x57,0x88,0x90,0x9c,0x0a,0x50,0xe7,0x15,
0x7b,0x58,0xbc,0x07,0x68,0x3a,0x5f,0xee,0x32,0x9f,0xeb,0xcc,0x18,0x8b,0xe2,0x57,
0xb7,0x49,0x37,0xde,0xf5,0x99,0x67,0x5b,0x3b,0xbb,0x3d,0xb5,0x2d,0x19,0x2e,0x0d,
0x93,0xfc,0x7e,0x06,0x08,0xbe,0x3f,0xd9,0x2a,0x70,0x9a,0xc8,0x7d,0xd8,0x46,0x65,
0x22,0xf4,0xb9,0xa2,0x6f,0x12,0x1b,0x14,0x45,0xc7,0x87,0x31,0x60,0x29,0xf7,0x73,
0x2c,0x97,0x72,0xcd,0x89,0xa6,0x88,0x4c,0xe8,0x83,0xeb,0x59,0xca,0x50,0x3f,0x27,
0x4e,0xae,0x43,0xd5,0x6e,0xd0,0x99,0x7b,0x7c,0x40,0x0c,0x52,0x86,0xc1,0x46,0x12,
0x5a,0x28,0xa8,0xbb,0xcb,0xf0,0x11,0x95,0x26,0x0d,0x34,0x66,0x22,0x18,0x6f,0x51,
0x9b,0x3b,0xda,0xec,0x5e,0x00,0x2a,0xf5,0x8f,0x61,0xba,0x96,0xb3,0xd1,0x30,0xdc,
0x33,0x75,0xe9,0x6d,0xc8,0xa1,0x3a,0x3e,0x5f,0x9d,0xfd,0xa9,0x31,0x9f,0xaa,0x85,
0x2f,0x92,0xaf,0x67,0x78,0xa5,0xab,0x03,0x21,0x4f,0xb9,0xad,0xfe,0xf3,0x42,0xfc,
0x17,0xd7,0xee,0xa3,0xd8,0x80,0x14,0x2e,0xa0,0x47,0x55,0xc4,0xff,0xe5,0x13,0x3f,
0x81,0xb6,0x7a,0x94,0xd0,0xb5,0x54,0xbf,0x91,0xa7,0x37,0xf1,0x6b,0xc9,0x1b,0xb1,
0x3c,0xb6,0xd9,0x32,0x24,0x8d,0xf2,0x82,0xb4,0xf9,0xdb,0x7d,0x44,0xfb,0x1e,0xd4,
0xea,0x5d,0x35,0x69,0x23,0x71,0x57,0x01,0x06,0xe4,0x55,0x9a,0xa4,0x58,0x56,0xc7,
0x4a,0x8c,0x8a,0xd6,0x6a,0x49,0x70,0xc5,0x8e,0x0a,0x62,0xdc,0x29,0x4b,0x42,0x41,
0xcb,0x2b,0xb7,0xce,0x08,0xa1,0x76,0x1d,0x1a,0xb8,0xe3,0xcc,0x7e,0x48,0x20,0xe6,
0xf8,0x45,0x93,0xde,0xc3,0x63,0x0f,0xb0,0xac,0x5c,0xba,0xdf,0x07,0x77,0xe7,0x4e,
0x1f,0x28,0x10,0x6c,0x59,0xd3,0xdd,0x2d,0x65,0x39,0xb2,0x74,0x84,0x3d,0xf4,0xbd,
0xc7,0x79,0x60,0x0b,0x4d,0x33,0x36,0x25,0xbc,0xe0,0x09,0xcf,0x5b,0xe2,0x38,0x9e,
0xc0,0xef,0xd2,0x16,0x05,0xbe,0x53,0xf7,0xc2,0xc6,0xa2,0x24,0x98,0x1c,0xad,0x04};
u32 diffusion[32]={
0xf26cb481,0x16a5dc92,0x3c5ba924,0x79b65248,0x2fc64b18,0x615acd29,0xc3b59a42,0x976b2584,
0x6cf281b4,0xa51692dc,0x5b3c24a9,0xb6794852,0xc62f184b,0x5a6129cd,0xb5c3429a,0x6b978425,
0xb481f26c,0xdc9216a5,0xa9243c5b,0x524879b6,0x4b182fc6,0xcd29615a,0x9a42c3b5,0x2584976b,
0x81b46cf2,0x92dca516,0x24a95b3c,0x4852b679,0x184bc62f,0x29cd5a61,0x429ab5c3,0x84256b97};
u8 input[32]={
//change only this :
0x66,0xd5,0x4e,0x28,0x5f,0xff,0x6b,0x53,0xac,0x3b,0x34,0x14,0xb5,0x3c,0xb2,0xc6,
0xa4,0x85,0x1e,0x0d,0x86,0xc7,0x4f,0xba,0x75,0x5e,0xcb,0xc3,0x6e,0x48,0x79,0x8f
//
};
void Forward(u8 c[32],u8 d[32],u8 s[512],u32 p[32])
{
for(u32 i=0;i<256;i++)
{
for(u8 j=0;j<32;j++)
{
d[j]=s[c[j]];
c[j]=0;
}
for(u8 j=0;j<32;j++)
for(u8 k=0;k<32;k++)
c[j]^=d[k]*((p[j]>>k)&1);
}
for(u8 i=0;i<16;i++)
d[i]=s[c[i*2]]^s[c[i*2+1]+256];
}
int main(int argc, char* argv[])
{
u8 target[]="Hire me!!!!!!!!";
u8 output[32];
Forward(input,output,confusion,diffusion);
return memcmp(output,target,16); // => contact jobs(at)nerd.nintendo.com
}
Ma preuve de solution :
diff --git a/HireMe.cpp b/HireMe.cpp
index ca94719..8374683 100644
--- a/HireMe.cpp
+++ b/HireMe.cpp
@@ -45,8 +45,8 @@ u32 diffusion[32]={
u8 input[32]={
//change only this :
-0x66,0xd5,0x4e,0x28,0x5f,0xff,0x6b,0x53,0xac,0x3b,0x34,0x14,0xb5,0x3c,0xb2,0xc6,
-0xa4,0x85,0x1e,0x0d,0x86,0xc7,0x4f,0xba,0x75,0x5e,0xcb,0xc3,0x6e,0x48,0x79,0x8f
+0x82,0x69,0xd7,0x3c,0xd7,0x58,0xd7,0x0d,0x22,0x46,0x58,0x22,0x22,0x69,0x22,0x77,
+0x77,0xd7,0x77,0xe6,0xf8,0x22,0xd7,0x58,0x9c,0x58,0x3c,0xf8,0xf8,0x22,0x58,0x13
//
};
@@ -70,7 +70,7 @@ void Forward(u8 c[32],u8 d[32],u8 s[512],u32 p[32])
int main(int argc, char* argv[])
{
- u8 target[]="Hire me!!!!!!!!";
+ u8 target[]="[rom@rom1v.com]";
u8 output[32];
Forward(input,output,confusion,diffusion);
Un collègue m’a envoyé récemment le lien vers ce challenge, utilisé pour recruter chez NERD (que je ne connais pas).
Je vous le partage car je l’ai trouvé très intéressant. Le but est de trouver un input qui donne l’output attendu.
Pour info, entre le moment où j’ai eu connaissance du problème et le moment où je l’ai résolu, il s’est écoulé 6 jours. Je n’ai pas travaillé dessus à plein temps, mais ne comptez pas le résoudre en 20 minutes ;-)
Je ne publie ni ma réponse au résultat attendu, ni les explications (ce serait incorrect vis-à-vis des auteurs du challenge). Je fournis par contre à la fin l’input qui donne comme output mon e-mail, ce qui suffit à prouver que j’ai résolu le problème.
Amusez-vous bien !
Ma preuve de solution :
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)
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;
}
(source – commit – 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.
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;
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.
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;
}
(source – commit – 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.
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;
};
(source – commit – 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.
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>;
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 :
S
) ;rec1::final_state
) ;value
) ;final_state
).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);
}
};
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.
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;
}
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.
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 !
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)
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) :
(source – commit – tag runtime
)
À compiler avec :
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.
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) :
34 | 33 | 32 | 31 | 30 |
---|---|---|---|---|
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
:
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(…)
:
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.
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(…)
:
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 :
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 :
devient :
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 :
par:
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) :
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 :
(source – commit – 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.
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 :
Ainsi, l’expression :
est calculée à 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 :
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 :
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(…)
:
Puis nous allons en définir une spécialisation pour le cas où DISKS
vaut 0 :
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 :
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 :
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.
(source – commit – 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 :
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.
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 :
Contrairement à précedemment, ici, nous avons besoin d’un nombre indéterminé de paramètres. Nous allons donc utiliser les variadic templates :
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) :
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 :
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 :
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 :
S
) ;rec1::final_state
) ;value
) ;final_state
).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 :
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.
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
) :
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.
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 :
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 :
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) :
La liste peut être parcourue ainsi :
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.
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 !
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 !
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 |
|
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 !
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é ?
Pour le comprendre, il faut regarder le code généré en assembleur, sans et avec optimisations.
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 |
|
Le code généré est très fidèle au code source C.
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 |
|
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 |
|
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
.
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 |
|
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
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 |
|
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 NullPointerException
s en C, ça fait rêver, non ?
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) :
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 |
|
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.
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