🧩 Ventinove Byte per Dire Ciao: Code Golf di “Hello, World!” in SuperHack 🔗

Un resoconto della sfida “Super Small Hello World” di hacker.org: le soluzioni che hanno funzionato, quelle che ci sono andate vicino e il trucco che ha finalmente permesso di raggiungere quota 29.

📑 Indice 🔗

🎯 La sfida 🔗

hacker.org ospita un piccolo linguaggio esoterico chiamato SuperHack. Il compito sembra banale: scrivere un programma in SuperHack che stampi Hello, World!.

La difficoltà sta nel punteggio. Vieni valutato in base all’area del rettangolo di delimitazione (bounding box) del tuo codice, e più è piccola, meglio è. Inoltre, il programma deve terminare correttamente: eseguendo l’istruzione ! (halt). Andare in crash con un’eccezione della VM una volta stampato il testo non è valido, così come non è valido stampare byte spuri.

Il numero da battere era 29.

🧭 Un tour di due minuti di SuperHack 🔗

SuperHack è una macchina a stack bidimensionale, simile nello spirito a Befunge:

• Il codice è una griglia di istruzioni a singolo carattere. Il program counter (PC) parte dall’angolo in alto a sinistra (oppure da un %) e si muove verso destra.
• C’è uno stack dati di numeri interi, più un call stack separato che memorizza le posizioni.
• Istruzioni utilizzate in questo articolo:

Due conseguenze plasmano tutto ciò che segue.

1. I caratteri sono dati. g legge il codice stesso del programma, quindi la stringa Hello, World! può semplicemente risiedere nella griglia ed essere letta un carattere alla volta. La maggior parte delle sue lettere (H e l o W r) sono no-op quando vengono eseguite. Tre non lo sono: , inserisce 0, d divide e ! arresta il programma.
2. @ / $ creano cicli, e il numero di iterazioni dipende da dove si trovano le @. $ riprende due celle dopo la @ a cui ritorna. Questo la fa atterrare sulla @ successiva, che inserisce nuovamente se stessa nello stack, permettendo a poche @ di ripetere il corpo del ciclo molte volte:
   • @@@@@ adiacenti producono conteggi di Fibonacci. Cinque di esse eseguono il corpo esattamente 13 volte.
   • @ distanziate di due celle producono potenze di due. Quattro di esse consentono 16 passaggi.

Tredici caratteri, tredici passaggi. Tienilo a mente.

L’area è larghezza per altezza, e 29 è un numero primo. Pertanto, un programma di 29 celle deve essere una singola riga o una singola colonna.

1️⃣ Soluzione 1: il ciclo diretto (area 32) 🔗

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

La prima vera soluzione posiziona il payload all’inizio e avvia l’esecuzione subito dopo:

Il gadget di arresto. La prima @ mette la propria posizione in fondo al call stack, e s salta oltre il !. La catena di Fibonacci esegue quindi i suoi 13 passaggi. Quando il call stack finalmente si srotola fino a quella prima @, $ riprende due celle dopo di essa, ovvero esattamente sul !. Il programma si arresta in modo pulito e non c’è alcun test di fine stringa da nessuna parte.

Il padding. Con le @ adiacenti, il ritorno dall’ultima @ riprende due celle più avanti, il che salta la prima cella dopo la catena. Quella cella deve quindi contenere qualcosa di innocuo, motivo per cui è uno spazio.

Risultato: Hello, World!, arresto pulito, area 32. È corretto ma spazioso: il payload è peso morto, e il %, il padding e lo 0 costano complessivamente tre celle.

2️⃣ Soluzione 2: intrecciare dati e codice (area 28, ma non valida) 🔗

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

L’idea successiva è smettere di sprecare celle per un payload separato e intrecciare la stringa direttamente nel codice. I caratteri di Hello, World! occupano le colonne dispari (1, 3, …, 25), mentre il codice riempie le colonne pari intermedie:

• 1 fa partire l’indice dalla colonna 1 (la H).
• Quattro @ distanziate di due celle (colonne 2, 4, 6, 8) consentono fino a 16 passaggi.
• La , stessa del payload (colonna 11) inserisce lo 0 che serve a g come riga.
• 2+ fa avanzare l’indice alla colonna dispari successiva.
• Le celle s saltano oltre la d e il ! del payload, evitando che vengano eseguiti come codice.

Il problema è che 16 passaggi sono più di 13. Dopo aver stampato la stringa, il ciclo continua a leggere oltre la fine e stampa $ e due byte NUL. Poi $ trova il call stack vuoto e la VM muore:

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

È piccolo, ma non è una soluzione. Introduce però l’idea chiave: i caratteri del payload che sono anche istruzioni utili (,) svolgono un doppio lavoro come dati e come codice.

3️⃣ Soluzione 3: andare in verticale (area 27, ma non valida) 🔗

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

P
W
2
o
+
r
$
l

d

!

(Un carattere per riga. Le righe vuote sono singoli spazi, che fanno parte dei dati.)

Ruotare il programma in verticale offre un vantaggio inaspettato. In una singola colonna, g ha bisogno che la coordinata x sia 0 e la riga sia i. La , del payload fornisce quello 0 gratuitamente, quindi la lettura si riduce a x , g: duplica i, inserisci 0, leggi. Il costo è un singolo \ in cima per deviare il PC verso il basso.

Ha però lo stesso difetto della soluzione 2. Il ciclo va oltre il limite, stampa byte NUL e termina con call stack underflow. Con un’area di 27 è il programma più piccolo di questo articolo, ma non è valido.

La lezione delle soluzioni 2 e 3 è che fermarsi in modo pulito costa celle. L’intreccio rende economico il ciclo, ma ti dà 16 passaggi quando te ne servono esattamente 13.

4️⃣ Soluzione 4: pagare il prezzo dell’uscita (area 30) 🔗

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

La soluzione 4 mantiene l’intreccio verticale della soluzione 3 e aggiunge un vero test di fine stringa:

L’indice assume i valori 2, 4, …, 26. floor(i/25) rimane 0 fino all’ultimissimo carattere (i = 26), quindi il ? salta l’arresto a ogni passaggio tranne l’ultimo. All’ultimo passaggio, l’esecuzione cade sul ! del payload, che è contemporaneamente l’ultimo carattere stampato e l’istruzione che ferma il programma.

È un bellissimo esempio di riutilizzo: i caratteri ,, d e ! del payload fungono tutti da codice. Ma il test costa cinque celle, e il totale è 30.

🧱 Perché 29 sembrava impossibile 🔗

A questo punto il mio assistente IA ha provato a dimostrare che 30 fosse il minimo assoluto. Ogni approccio sembrava scontrarsi con lo stesso muro:

• L’intreccio impedisce il ciclo economico. Tredici passaggi richiedono cinque @ adiacenti, e in un layout intrecciato non ci sono celle di codice adiacenti. Quindi sei costretto a usare 16 passaggi e un test a pagamento.
• La parità blocca uscite più economiche. In un intreccio, ? non può mai trovarsi direttamente davanti a $. La cella tra di loro è sempre una cella del payload.
• Un payload contiguo blocca l’altro design. Metti il payload in un unico blocco e il ciclo di Fibonacci torna a entrare. Ma a quel punto il payload deve trovarsi in una zona mai eseguita (costando un % o un indice iniziale grande), perché eseguire ...d! come codice provoca un crash o un arresto immediato.

Le ricerche esaustive al computer su aree più piccole non hanno trovato nulla, e anche le ricerche attorno allo schema della soluzione 4 ad area 29 non hanno dato frutti. “30 è il limite inferiore” iniziava a sembrare un teorema.

Non lo era.

🏆 Soluzione 5: ventinove (area 29) 🔗

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

La svolta è arrivata rileggendo il codice sorgente del giudice di gara. Due righe fanno la differenza:

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

• P stampa solo i 7 bit meno significativi. Un byte con il bit più alto impostato a 1, c + 128, viene stampato esattamente come c.
• Un byte compreso tra 128 e 255 non è un’istruzione, quindi viene eseguito come no-op.
• Le stringhe PHP sono sequenze di byte, quindi un byte del genere occupa una singola cella come qualsiasi altro.

Ogni carattere del payload ha quindi due possibili codifiche. Quella standard può fare qualcosa quando viene eseguita. Quella con c | 0x80 è garantita inerte. Ecco la “formula per i dati”: memorizza i caratteri pericolosi come c + 128, e lascia che P rimuova il bit alto gratuitamente.

Solo due caratteri del payload sono pericolosi: d diventa ä (0xE4) e ! diventa ¡ (0xA1). Modificando questi due, l’intero payload può essere eseguito. Questo rimuove l’ostacolo descritto nel terzo punto elenco qui sopra.

Ora prendi la soluzione 1 e sposta il payload all’interno del ciclo:

Seguiamo un passaggio passo dopo passo:

1. Il PC atterra da qualche parte nella catena di @ e attraversa tutto il payload. H e l l o, lo spazio e W o r l non fanno nulla. La , del payload inserisce lo 0 che serve a g come riga. ä e ¡ non fanno nulla.
2. 1^ copia i sopra quello 0, e g legge la colonna i.
3. P la stampa. Per gli ultimi due caratteri stampa 0xE4 & 0x7F = 'd' e 0xA1 & 0x7F = '!'.
4. 1+ fa avanzare i, e $ ritorna nella catena.

Rispetto alla soluzione 1, spariscono tre celle:

• %: il payload non ha più bisogno di essere protetto dall’esecuzione.
• Lo spazio di padding: la cella che viene saltata dopo la catena è ora la H del payload, che è una no-op.
• Lo 0 prima di 1^g: la , del payload lo fornisce a ogni passaggio.

32 − 3 = 29. Dopo il tredicesimo passaggio, il call stack si srotola fino al gadget e il programma si ferma sul ! alla colonna 3.

Output Hello, World!, nessun messaggio dalla VM, 271 cicli, area 29.

🌐 L’ultimo ostacolo: inviare i byte giusti al giudice 🔗

Il primo invio è tornato indietro con got: 'Hello, WorlC$' e un punteggio di 31. Il modulo web aveva inviato i dati in UTF-8, trasformando ciascun carattere speciale in due byte (ä → C3 A4, ¡ → C2 A1). Mascherati a 7 bit, 0xC3 viene stampato come C e 0xA4 come $.

La soluzione consiste nel far inviare al browser la codifica Latin-1, in cui ciascuno di quei caratteri occupa un solo byte. Sulla pagina della sfida, ho dovuto aprire la console dei DevTools ed eseguire:

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

Poi basta premere il normale pulsante di invio. Il giudice stampa Hello, World!, e il punteggio da battere (King of the Hill) diventa 29.

📊 Tabella dei Punteggi 🔗

💡 Lezioni Apprese 🔗

• I dati sono anche codice. Ogni passo vincente è nato dal lasciare che le stesse celle servissero a entrambi gli scopi: la , del payload come push 0 gratuito, il suo ! come istruzione di arresto, e infine l’intero payload come corpo del ciclo.
• Una dimostrazione di impossibilità vale solo quanto le sue premesse. “30 è il limite inferiore” era vero per layout intrecciati e limitati ai caratteri ASCII stampabili. Nessuna di queste due restrizioni era nelle regole.
• Leggi il codice sorgente reale. La ricerca brute-force all’interno di uno spazio di progettazione fisso non può trovare una risposta che si trova al di fuori di esso. Due righe del codice PHP del giudice (& 0x7F e default: break) hanno ottenuto ciò che ore di ricerca automatica non avevano potuto fare.
• Fai attenzione al trasporto. Un programma corretto può comunque fallire quando il modulo web modifica i suoi byte lungo il tragitto verso il giudice.