🧩 Vingt-neuf octets pour dire bonjour : golfer « Hello, World! » en SuperHack 🔗

Récit du défi « Super Small Hello World » de hacker.org : les solutions qui ont fonctionné, celles qui ont failli marcher et l’astuce qui a finalement permis d’atteindre 29.

📑 Table des Matières 🔗

🎯 Le défi 🔗

hacker.org propose un petit langage ésotérique appelé SuperHack. La tâche semble triviale : écrire un programme SuperHack qui affiche Hello, World!.

Le piège réside dans le calcul du score. Vous êtes évalué sur l’aire du rectangle englobant de votre code, et plus il est petit, mieux c’est. Le programme doit également se terminer proprement : en exécutant l’instruction ! (arrêt). Planter avec une exception de la machine virtuelle une fois le texte affiché ne compte pas, pas plus que l’affichage d’octets parasites.

Le score à battre était de 29.

🧭 Tour d’horizon de SuperHack en deux minutes 🔗

SuperHack est une machine à pile en 2D, similaire dans l’esprit à Befunge :

• Le code est une grille d’instructions d’un seul caractère. Le compteur ordinal (PC) démarre dans le coin supérieur gauche (ou sur un %) et se déplace vers la droite.
• Il y a une pile de données contenant des entiers, ainsi qu’une pile d’appels séparée qui stocke des positions.
• Instructions utilisées dans cet article :

Deux conséquences façonnent tout ce qui suit.

1. Les caractères sont des données. g lit le propre code du programme, de sorte que la chaîne Hello, World! peut simplement résider dans la grille et être lue caractère par caractère. La plupart de ses lettres (H e l o W r) sont des no-ops lorsqu’elles sont exécutées. Trois ne le sont pas : , empile 0, d divise et ! arrête le programme.
2. @ / $ forment des boucles, et le nombre d’itérations dépend de l’emplacement des @. $ reprend deux cellules après le @ auquel il retourne. Cela atterrit sur le @ suivant, qui s’empile à nouveau, de sorte que quelques @ peuvent rejouer le corps de la boucle un grand nombre de fois :
   • Des @@@@@ adjacents donnent des nombres de Fibonacci. Cinq d’entre eux exécutent le corps exactement 13 fois.
   • Des @ espacés de deux cellules donnent des puissances de deux. Quatre d’entre eux permettent 16 passages.

Treize caractères, treize passages. Gardez cela en tête.

L’aire est égale à la largeur multipliée par la hauteur, et 29 est un nombre premier. Un programme de 29 cellules doit donc tenir sur une seule ligne ou une seule colonne.

1️⃣ Solution 1 : la boucle directe (aire 32) 🔗

Hello, World!%0@s!@@@@@ 01^gP1+$

La première vraie solution place la charge utile (payload) au début et démarre l’exécution juste après :

Le gadget d’arrêt. Le premier @ place sa propre position tout en bas de la pile d’appels, et s saute par-dessus le !. La chaîne de Fibonacci effectue ensuite ses 13 passages. Lorsque la pile d’appels finit par se dérouler jusqu’à ce premier @, $ reprend deux cellules après lui, ce qui correspond exactement au !. Le programme s’arrête proprement, sans aucun test de fin de chaîne où que ce soit.

Le remplissage. Avec des @ adjacents, le retour depuis le dernier @ reprend deux cellules plus loin, ce qui saute la première cellule après la chaîne. Cette cellule doit donc être inoffensive : c’est un espace.

Résultat : Hello, World!, arrêt propre, aire 32. C’est correct mais spacieux : la charge utile est un poids mort, et le %, l’espace de remplissage et le 0 coûtent ensemble trois cellules.

2️⃣ Solution 2 : l’entrelacement (aire 28, mais invalide) 🔗

1H@e@l@l@o ,1 ^WgoPr2lsds!+$

L’idée suivante consiste à ne plus dépenser de cellules pour une charge utile séparée et à tisser la chaîne à travers le code. Les caractères de Hello, World! occupent les colonnes impaires (1, 3, …, 25), et le code remplit les colonnes paires intermédiaires :

• 1 initialise l’indice à la colonne 1 (le H).
• Quatre @ espacés de deux cellules (colonnes 2, 4, 6, 8) permettent jusqu’à 16 passages.
• La propre , de la charge utile (colonne 11) empile le 0 dont g a besoin comme numéro de ligne.
• 2+ fait avancer l’indice à la colonne impaire suivante.
• Les cellules s sautent par-dessus le d et le ! de la charge utile afin qu’ils ne soient pas exécutés comme du code.

Le problème est que 16 passages, c’est plus que 13. Après avoir affiché la chaîne, la boucle continue de lire au-delà de la fin et affiche $ ainsi que deux octets NUL. Ensuite, $ trouve la pile d’appels vide et la machine virtuelle plante :

output:  "Hello, World!$\0\0"
message: call stack underflow

C’est compact, mais ce n’est pas une solution. Cela introduit toutefois l’idée clé : les caractères de la charge utile qui se trouvent être des instructions utiles (,) jouent un double rôle de données et de code.

3️⃣ Solution 3 : passer à la verticale (aire 27, mais invalide) 🔗

\
2
H
@
e
@
l
@
l
@
o
x
,
g

P
W
2
o
+
r
$
l

d

!

(Un caractère par ligne. Les lignes vides sont des espaces simples, qui font partie des données.)

Basculer le programme sur le côté présente un avantage inattendu. Dans une colonne unique, g a besoin que la coordonnée x vaille 0 et que la ligne soit i. La , de la charge utile fournit ce 0 gratuitement, de sorte que la lecture se réduit à x , g : dupliquer i, empiler 0, lire. Le coût est d’un seul \ tout en haut pour orienter le PC vers le bas.

Elle souffre cependant du même défaut que la solution 2. La boucle dépasse la fin, affiche des octets NUL et se termine par un call stack underflow. Avec une aire de 27, c’est le plus petit programme de cet article, mais il n’est pas valide.

La leçon des solutions 2 et 3 est que s’arrêter proprement coûte des cellules. L’entrelacement rend la boucle économique, mais il vous impose 16 passages alors qu’il vous en faut exactement 13.

4️⃣ Solution 4 : payer pour la sortie (aire 30) 🔗

\
2
H
@
e
@
l
@
l
@
o
x
,
g
 
P
W
x
o
5
r
d
l
5
d
?
!
2
+
$

La solution 4 conserve l’entrelacement vertical de la solution 3 et ajoute un véritable test de fin de chaîne :

L’indice parcourt 2, 4, …, 26. floor(i/25) reste à 0 jusqu’au tout dernier caractère (i = 26), de sorte que le ? saute l’arrêt à chaque passage sauf au dernier. Lors du dernier passage, l’exécution tombe sur le ! de la charge utile, qui est simultanément le dernier caractère affiché et l’instruction qui arrête le programme.

C’est un superbe exemple de réutilisation : les caractères ,, d et ! de la charge utile servent tous de code. Mais le test coûte cinq cellules, et le total s’élève à 30.

🧱 Pourquoi 29 semblait impossible 🔗

À ce stade, mon compagnon IA a tenté de prouver que 30 était optimal. Chaque approche semblait se heurter au même mur :

• L’entrelacement bloque la boucle économique. Treize passages nécessitent cinq @ adjacents, et un entrelacement n’a aucune cellule de code adjacente. Vous êtes donc coincé avec 16 passages et un test coûteux.
• La parité bloque les sorties moins chères. Dans un entrelacement, ? ne peut jamais se trouver directement devant $. La cellule qui les sépare est toujours une cellule de données.
• Une charge utile contiguë bloque l’autre conception. Mettez la charge utile en un seul bloc et la boucle de Fibonacci rentre à nouveau. Mais alors la charge utile doit résider dans un endroit jamais exécuté (ce qui coûte un % ou un grand indice de départ), car exécuter ...d! comme du code fait planter ou arrête le programme.

Les recherches exhaustives par ordinateur sur des aires plus petites n’ont rien donné, et les recherches autour de l’agencement de la solution 4 pour une aire de 29 n’ont rien trouvé non plus. « 30 est le plancher » commençait à ressembler à un théorème.

Ce n’en était pas un.

🏆 Solution 5 : vingt-neuf (aire 29) 🔗

9@s!@@@@@Hello, Worlä¡1^gP1+$

La percée est venue d’une relecture du code source du juge. Deux lignes sont décisives :

case 'P':
  $output .= chr($this->Pop() & 0x7F); break;
...
default:
  break;   // every unknown character is a no-op

• P n’affiche que les 7 bits de poids faible. Un octet dont le bit de poids fort est activé, c + 128, s’affiche exactement comme c.
• Un octet compris entre 128 et 255 n’est pas une instruction, il s’exécute donc comme un no-op.
• Les chaînes PHP sont des tableaux d’octets, un tel octet occupe donc une seule cellule comme n’importe quel autre.

Chaque caractère de la charge utile possède par conséquent deux encodages. L’encodage standard peut faire quelque chose lorsqu’il est exécuté. L’encodage c | 0x80 est garanti inerte. C’est la « formule magique pour les données » : stocker les caractères dangereux sous la forme c + 128, et laisser P retirer gratuitement le bit de poids fort.

Seuls deux caractères de la charge utile sont dangereux : d devient ä (0xE4) et ! devient ¡ (0xA1). Une fois ces deux caractères modifiés, l’intégralité de la charge utile peut être exécutée. Cela élimine l’obstacle du troisième point ci-dessus.

Reprenons maintenant la solution 1 et déplaçons la charge utile à l’intérieur de la boucle :

Déroulons un passage :

1. Le PC atterrit quelque part dans la chaîne de @ et traverse la charge utile. H e l l o, l’espace et W o r l ne font rien. La , de la charge utile empile le 0 dont g a besoin comme numéro de ligne. ä et ¡ ne font rien.
2. 1^ copie i au-dessus de ce 0, et g lit la colonne i.
3. P l’affiche. Pour les deux derniers caractères, il affiche 0xE4 & 0x7F = 'd' et 0xA1 & 0x7F = '!'.
4. 1+ fait avancer i, et $ retourne dans la chaîne.

Par rapport à la solution 1, trois cellules disparaissent :

• % : la charge utile n’a plus besoin d’être protégée contre l’exécution.
• L’espace de remplissage : la cellule sautée après la chaîne est désormais le H de la charge utile, qui est un no-op.
• Le 0 avant 1^g : la , de la charge utile le fournit à chaque passage.

32 − 3 = 29. Après le 13e passage, la pile d’appels se déroule jusqu’au gadget et le programme s’arrête sur le ! à la colonne 3.

Sortie Hello, World!, aucun message de la VM, 271 cycles, aire 29.

🌐 Le dernier obstacle : envoyer les octets au juge 🔗

La première soumission est revenue avec got: 'Hello, WorlC$' et un score de 31. Le formulaire web avait envoyé les données en UTF-8, transformant chaque caractère spécial en deux octets (ä → C3 A4, ¡ → C2 A1). Masqués sur 7 bits, 0xC3 s’affiche comme C et 0xA4 comme $.

La solution consiste à forcer le navigateur à envoyer du Latin-1, où chacun de ces caractères tient sur un seul octet. Sur la page du défi, j’ai dû ouvrir la console DevTools et exécuter :

document.querySelectorAll('form').forEach(
  f => f.acceptCharset = 'ISO-8859-1');
document.querySelector('textarea').value =
  "9@s!@@@@@Hello, Worl\u00e4\u00a11^gP1+$";

Il suffit ensuite d’appuyer sur le bouton de soumission normal. Le juge affiche Hello, World!, et le score au classement général est de 29.

📊 Tableau des scores 🔗

💡 Ce qu’il faut retenir 🔗

• Les données sont aussi du code. Chaque étape décisive est venue du fait de laisser les mêmes cellules servir aux deux : la , de la charge utile comme push 0 gratuit, son ! comme arrêt, et finalement toute la charge utile comme corps de la boucle.
• Une preuve d’impossibilité ne vaut que ce que valent ses hypothèses. « 30 est le plancher » était vrai pour les dispositions entrelacées en ASCII imprimable. Aucune de ces deux restrictions ne figurait dans les règles.
• Lisez le vrai code source. Une recherche par force brute dans un espace de conception figé ne peut pas trouver une réponse qui se situe en dehors de cet espace. Deux lignes du code PHP du juge (& 0x7F et default: break) ont accompli ce que des heures de recherche automatique n’avaient pas pu faire.
• Attention au transport. Un programme correct peut tout de même échouer lorsque le formulaire web modifie ses octets en chemin vers le juge.