- Malbolge
-
Malbolge est un langage de programmation du domaine public inventé par Ben Olmstead en 1998, nommé d'après le huitième cercle de l'enfer dans L'Enfer de Dante, le Malebolge.
La particularité de Malbolge est qu'il a été conçu pour être le pire (le plus difficile et exotique) langage de programmation possible. Toutefois, certaines des astuces utilisées pour rendre la compréhension difficile peuvent être simplifiées.
Sommaire
Programmer en Malbolge
Malbolge était si difficile à comprendre quand il est arrivé qu'il a fallu deux ans au premier programme Malbolge pour apparaître. Le programme n'a même pas été écrit par un être humain : il a été généré par un algorithme de recherche par faisceaux conçu par Andrew Cooke et implémenté en Lisp.
Le 24 août 2000, Anthony Youhas annonça sur son blog qu'il a "battu Malbolge avec un bâton et maîtrisé ses secrets", fournissant des preuves sous forme de trois programmes Malbolge qui affichent diverses phrases. Toutefois il ne révéla pas ses techniques.
Plus tard, Lou Scheffer posta une cryptanalyse de Malboge et fournit un programme pour copier son entrée vers sa sortie.
Olmstead croyait Malbolge Turing-complet, sauf pour de la mémoire infinie. Il y a eu une discussion intéressante visant à déterminer si l'on pouvait implémenter des boucles en Malbolge ; il a fallu de nombreuses années avant d'introduire la première boucle non-terminante.
Le 17 août 2004, Tomasz Wegrzanowski écrivit un générateur de programmes Malbolge affichant diverses chaines de caractères. D'après lui, l'astuce est d'oublier les sauts, de garder le registre D à des endroits bas de la mémoire, et d'effectuer aléatoirement des opérations NOP, ROT et Crazy jusqu'à ce que le registre A contienne ce dont on a besoin. Les programmes produits avec cette technique sont bien plus grands que ceux d'Anthony.
Hello world en Malbolge
(=<`:9876Z4321UT.-Q+*)M'&%$H"!~}|Bzy?=|{z]KwZY44Eq0/{mlk** hKs_dG5[m_BA{?-Y;;Vb'rR5431M}/.zHGwEDCBA@98\6543W10/.R,+O<Programmes simples en Malbolge
Malbolge est un langage machine pour une machine virtuelle trinaire, l'interpréteur Malbolge. Pour vous aider à écrire des programmes Malbolge qui tournent correctement, le mode de fonctionnement de l'interpréteur standard est décrit plus bas.
Notes
- L'interpréteur standard et la spécification officielle ne correspondent pas parfaitement.
- C'est une explication simplifiée du code source de l'interpréteur: elle évite le chiffrement inutile et les étapes de soustraction et introduit un langage assembleur.
- Avant de la corriger, assurez-vous qu'elle est bel et bien techniquement incorrecte et pas juste inhabituelle.
Registres
Malbolge possède trois registres, a, c, et d, qui sont comme des variables dans d'autres langages. Quand un programme démarre, la valeur de ces trois registres est zéro. c est spécial: c'est le compteur ordinal (i.e. il pointe sur l'instruction courante).
Notation des pointeurs
[d] signifie que la valeur de d est une adresse mémoire; [d] est la valeur stockée à cette adresse. [c] est similaire.
Mémoire
La machine virtuelle a 59049 emplacements mémoire qui peuvent chacun contenir un nombre trinaire à dix chiffres. Chaque emplacement mémoire a une adresse de 0 à 59048 et peut contenir une valeur de 0 à 59048. Une valeur qui atteint 59049 est remplacée par 0.
Avant qu'un programme Malbolge commence, la première partie de la mémoire est remplie avec le programme. Tous les blancs dans le programme sont ignorés et, pour rendre la programmation plus difficile, tout le reste dans le programme doit commencer en tant qu'une des instructions suivantes.
Le reste de la mémoire est rempli en utilisant l'opération Crazy (voir plus bas) sur les deux adresses précédentes ([m] = crz [m - 2], [m - 1]). La mémoire remplie ainsi se répète toutes les douze adresses (les chiffres ternaires individuels se répètent toutes les trois ou quatre adresses, donc un groupe de chiffres trinaires est garanti de se répéter toutes les douze adresses).
Instructions
Malbolge possède huit instructions. Malbolge trouve quelle instruction exécuter en prenant la valeur à [c], en lui ajoutant la valeur de c et en lui soustrayant 94 jusqu'à ce que le nombre soit inférieur à 94. Le résultat final dit à l'interpréteur ce qu'il doit faire :
Instructions Valeur de ([c] + c) % 94 Instruction représentée Explication 4 jmp [d] + 1 La valeur à [d], plus un, est là où Malbolge va sauter et commencer à exécuter des instructions. 5 out a Affiche la valeur de a, en tant que caractère ASCII, à l'écran. 23 in a Entre un caractère, en tant que code ASCII, dans a. Les retours à la ligne sont le code 10. Une condition de fin de fichier est le code 59048. 39 rotr [d]
mov a, [d]Fait tourner la valeur à [d] d'un nombre trinaire (0002111112 devient 2000211111). Stocke le résultat à la fois dans [d] et dans a. 40 mov d, [d] Copie la valeur à [d] dans d. 62 crz [d], a
mov a, [d]Effectue l'opération Crazy (voir plus bas) avec la valeur à [d] et la valeur de a. Stocke le résultat à la fois dans [d] et a. 68 nop Ne fait rien. 81 end Termine le programme. Toute autre valeur fait comme 68: rien. Ces valeurs ne sont pas permises dans un programme pendant qu'il est chargé, mais sont permises plus tard. Après que chaque instruction est exécutée, l'instruction en cours est chiffrée (voir plus bas) afin qu'elle ne fasse pas pareil la prochaine fois, à moins qu'un saut vienne d'arriver. Par contre, juste après un saut, Malbolge chiffre l'instruction juste avant celle sur laquelle il a sauté. Ensuite, les valeurs de c et d sont incrémentées de 1 et la prochaine instruction est exécutée.
L'opération Crazy
Pour chaque nombre trinaire des deux entrées, utilisez la table suivante pour obtenir un nombre trinaire du résultat. Par exemple, crz 0001112220, 0120120120 donne 1001022211.
opération Crazy crz Entrée 2 0 1 2 Entrée 1 0 1 0 0 1 1 0 2 2 2 2 1 Chiffrement
Après qu'une instruction sera exécutée, la valeur à [c] (sans rien ajouter) se verra soustraire 94 jusqu'à ce qu'elle soit inférieure à 94. Puis, le résultat est chiffré avec l'une des deux méthodes équivalentes suivantes.
Méthode 1
Trouver le résultat ci-dessous. Stocker le code ASCII du caractère plus bas à [c].
0000000000111111111122222222223333333333444444444455555555556666666666777777777788888888889999 0123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123 ---------------------------------------------------------------------------------------------- 9m<.TVac`uY*MK'X~xDl}REokN:#?G"i@5z]&gqtyfr$(we4{WP)H-Zn,[%\3dL+Q;>U!pJS72FhOA1CB6v^=I_0/8|jsbMéthode 2
Trouver le résultat ci-dessous. Stocker la version chiffrée à [c].
Table de chiffrement Résultat Chiffré Résultat Chiffré Résultat Chiffré Résultat Chiffré Résultat Chiffré 0 57 19 108 38 113 57 91 76 79 1 109 20 125 39 116 58 37 77 65 2 60 21 82 40 121 59 92 78 49 3 46 22 69 41 102 60 51 79 67 4 84 23 111 42 114 61 100 80 66 5 86 24 107 43 36 62 76 81 54 6 97 25 78 44 40 63 43 82 118 7 99 26 58 45 119 64 81 83 94 8 96 27 35 46 101 65 59 84 61 9 117 28 63 47 52 66 62 85 73 10 89 29 71 48 123 67 85 86 95 11 42 30 34 49 87 68 33 87 48 12 77 31 105 50 80 69 112 88 47 13 75 32 64 51 41 70 74 89 56 14 39 33 53 52 72 71 83 90 124 15 88 34 122 53 45 72 55 91 106 16 126 35 93 54 90 73 50 92 115 17 120 36 38 55 110 74 70 93 98 18 68 37 103 56 44 75 104 Cycles dans le chiffrement
La cryptanalyse de Malbolge par Lou Scheffer mentionne six cycles différents dans le chiffrement. Ils sont listés ici :
- 33 ⇒ 53 ⇒ 45 ⇒ 119 ⇒ 78 ⇒ 49 ⇒ 87 ⇒ 48 ⇒ 123 ⇒ 71 ⇒ 83 ⇒ 94 ⇒ 57 ⇒ 91 ⇒ 106 ⇒ 77 ⇒ 65 ⇒ 59 ⇒ 92 ⇒ 115 ⇒ 82 ⇒ 118 ⇒ 107 ⇒ 75 ⇒ 104 ⇒ 89 ⇒ 56 ⇒ 44 ⇒ 40 ⇒ 121 ⇒ 35 ⇒ 93 ⇒ 98 ⇒ 84 ⇒ 61 ⇒ 100 ⇒ 97 ⇒ 46 ⇒ 101 ⇒ 99 ⇒ 86 ⇒ 95 ⇒ 109 ⇒ 88 ⇒ 47 ⇒ 52 ⇒ 72 ⇒ 55 ⇒ 110 ⇒ 126 ⇒ 64 ⇒ 81 ⇒ 54 ⇒ 90 ⇒ 124 ⇒ 34 ⇒ 122 ⇒ 63 ⇒ 43 ⇒ 36 ⇒ 38 ⇒ 113 ⇒ 108 ⇒ 39 ⇒ 116 ⇒ 69 ⇒ 112 ⇒ 68 ⇒ 33 ...
- 37 ⇒ 103 ⇒ 117 ⇒ 111 ⇒ 120 ⇒ 58 ⇒ 37 ...
- 41 ⇒ 102 ⇒ 96 ⇒ 60 ⇒ 51 ⇒ 41 ...
- 42 ⇒ 114 ⇒ 125 ⇒ 105 ⇒ 42 ...
- 50 ⇒ 80 ⇒ 66 ⇒ 62 ⇒ 76 ⇒ 79 ⇒ 67 ⇒ 85 ⇒ 73 ⇒ 50 ...
- 70 ⇒ 74 ⇒ 70 ...
Ces cycles peuvent être utilisés pour créer des boucles qui font des choses différentes à chaque fois et qui deviennent finalement répétitives. Lou Scheffer a utilisé cette idée pour créer un programme Malbolge (inclus dans sa cryptanalyse sur laquelle un lien ci-dessous pointe) qui répète tout ce que l'utilisateur donne en entrée.
Liens externes
- Site officiel de Malbolge (archivé)
- spécification du langage Malbolge
- interpréteur Malbolge (code source C)
- description de l'algorithme d'Andrew Cooke pour créer le premier programme Malbolge
- cryptanalyse de Malbolge par Lou Scheffer
- papier sur comment écrire des programmes Malbolge; pousse l'analyse de Scheffer un peu plus loin
- annonce sur le blog d'Anthony Youhas
- version simpliste de "99 bottles" en Malbolge
Wikimedia Foundation. 2010.
