Resoconto Free Exercise 11 giugno 2005

HACK YOUR MIND: resoconto sull'evento

-- by Unai Vivi --

Ringraziamenti

Innanzitutto grazie a tutti coloro che hanno partecipato. Siete stati tutti bravissimi!
Grazie poi a Matteo Generali per l'aiuto, per il suo grande carisma e per la sua capacità di gestire sempre in maniera efficace ed efficente situazioni impreviste ed avverse e nondimeno per l'aver messo a disposizione dell'evento la sua grande capacità logistico-organizzativa.
Infine grazie al gentile ingegnere [di cui purtroppo non ricordo il nome: se me lo dite, lo inserisco] che ha prestato il suo tempo facendo una grande cortesia all'associazione, permettendoci di accedere al dipartimento di Ingegneria ed usufruire della disponibilità del laboratorio InfoMec.

Complimentissimi ad entrambi! Siete stati davvero geniali!

Una particolare nota di riguardo va a Daniele Stanzani, che ha fatto subito presente che un file vuoto (0 byte) fatto in shell, una volta eseguito, non dà alcun output, e che quindi questo output nullo potrebbe considerarsi uguale al codice shell invertito del programma!

Consegna della gara

"Hack your mind" contest

Creare un programma che stampi a video il suo stesso codice sorgente, capovolto (dall'ultimo carattere al primo), senza accedere al filesystem.

È possibile partecipare individualmente o a squadre.

È consentito soltanto l'uso di documentazione offline e cartacea.

Inoltre a ciascun partecipante verrà consegnata una tabella ASCII.

I linguaggi fra cui scegliere sono:

• shell

• C

• Java

• php

IN PALIO PER IL VINCITORE: CHIAVETTA USB 256 MB

Dopo circa mezz'ora, ai concorrenti è stato dato il seguente suggerimento.

Primo suggerimento

Usando il linguaggio "italiano" e l'interprete "cervello umano", le istruzioni che risolvono il problema sono le seguenti.

Scrivi la frase seguente 2 volte, capovolta, la prima volta fra virgolette e preceduta da un punto: "Scrivi la frase seguente 2 volte, capovolta, la prima volta fra virgolette e preceduta da un punto:".

L'output generato da una persona che segua alla lettera le istruzioni soprastanti, sarà costituito esattamente dal testo soprastante, scritto alla rovescia, dall'ultimo carattere al primo.
Ora dovete trovare un modo di fare qualcosa di analogo con il linguaggio di programmazione che avete scelto.

Soluzioni - coded by Unai Vivi

C - soluzione compatta

main(){int i=0;char c;char s[]="main(){int i=0;char c;char s[]=c%s%c%;for(;i<strlen(s)/2;i++){c=*(s+i);*(s+i)=*(s+strlen(s)-1-i);*(s+strlen(s)-1-i)=c;}printf(s,0x22,s,0x22);}";for(;i<strlen(s)/2;i++){c=*(s+i);*(s+i)=*(s+strlen(s)-1-i);*(s+strlen(s)-1-i)=c;}printf(s,0x22,s,0x22);}

C - soluzione elegante e leggibile

(Quandanche compilato con "gcc -Wall", non genera alcun warning)

#include <stdio.h>
#include <string.h>
int main()
{
int ero;
char latano;
char s[]="#include <stdio.h>c%#include <string.h>c%int main()c%{c%c%int ero;c%c%char latano;c%c%char s[]=c%s%c%;c%c%for(ero=0;ero<strlen(s)/2;ero++)c%c%{c%c%c%latano=*(s+ero);c%c%c%*(s+ero)=*(s+strlen(s)-1-ero);c%c%c%*(s+strlen(s)-1-ero)=latano;c%c%}c%c%printf(s,0x0A,0x09,0x0A,0x09,0x0A,0x09,0x0A,0x09,0x09,0x0A,0x09,0x09,0x0A,0x09,0x09,0x0A,0x09,0x0A,0x09,0x0A,0x22,s,0x22,0x09,0x0A,0x09,0x0A,0x09,0x0A,0x0A,0x0A,0x0A);c%c%return 0;c%}";
for(ero=0;ero<strlen(s)/2;ero++)
{
latano=*(s+ero);
*(s+ero)=*(s+strlen(s)-1-ero);
*(s+strlen(s)-1-ero)=latano;
}
printf(s,0x0A,0x09,0x0A,0x09,0x0A,0x09,0x0A,0x09,0x09,0x0A,0x09,0x09,0x0A,0x09,0x09,0x0A,0x09,0x0A,0x09,0x0A,0x22,s,0x22,0x09,0x0A,0x09,0x0A,0x09,0x0A,0x0A,0x0A,0x0A);
return 0;
}

Shell

a="\x27";s='a="\x27";s=;echo `echo $s|head -c 11;echo -en $a;echo -n $s;echo -en $a;echo $s|tail -c 85`|rev';echo `echo $s|head -c 11;echo -en $a;echo -n $s;echo -en $a;echo $s|tail -c 85`|rev

Shell - alternativa con uso di funzioni

f(){ echo -en "$1";echo "f '$1'|rev";};f 'f(){ echo -en "$1";echo "f \x27$1\x27|rev";};'|rev

Java

public class Arversa{public static void main(String s[]){char v=34;String a="public class Arversa{public static void main(String s[]){char v=34;String a=;char[] b=(a.substring(0,76)+v+a+v+a.substring(76,a.length())).toCharArray();for(int i=0;i<b.length/2;i++){char x=b[i];b[i]=b[b.length-1-i];b[b.length-1-i]=x;}System.out.println(new String(b));}}";char[] b=(a.substring(0,76)+v+a+v+a.substring(76,a.length())).toCharArray();for(int i=0;i<b.length/2;i++){char x=b[i];b[i]=b[b.length-1-i];b[b.length-1-i]=x;}System.out.println(new String(b));}}

php

<?php $s='<?php $s=c%s%c%;$s=strrev($s);printf($s,0x27,addslashes($s),0x27)?>';$s=strrev($s);printf($s,0x27,addslashes($s),0x27)?>

Sono disonibili i sorgenti formattati e indentati.

Soluzioni - coded by winners

Vediamo ora i sorgenti dei nostri due formidabili vincitori, che nonostante la tensione della competizione sono riusciti a vincere in modo sorprentente! (Hanno entrambi scelto il C)

Marco Bonfatti

char* buff = "char* buff = ;int main(int argv, char **argc){int i=0;int dim=0;int b;while(buff[dim++] != 0);for(i=dim; i>0&& !(buff[i-1]==' ' && buff[i]==';');i--)putchar(buff[i-1]);b=i;putchar(34);for(i=dim; i>0;i--)putchar(buff[i-1]);putchar(34);for(i=b; i>0;i--)putchar(buff[i-1]);return 0;}";int main(int argv, char **argc){int i=0;int dim=0;int b;while(buff[dim++] != 0);for(i=dim; i>0 && !(buff[i-1]==' ' && buff[i]==';');i--)putchar(buff[i-1]);b=i;putchar(34);for(i=dim; i>0;i--)putchar(buff[i-1]);putchar(34);for(i=b; i>0;i--)putchar(buff[i-1]);return 0;}

Commenti:

La soluzione è eccellente!
Elegantissima la condizione relativa al primo ciclo for!

i>0 && !(buff[i-1]==' ' && buff[i]==';')

 Purtroppo, però, c'è una piccola svista: vegono stampati due null (cioè byte composti da 8 bit uguali a zero) di troppo: uno all'inizio e uno verso metà. Ecco l'output del programma (compilato da bonfatti.c):

NULL]};0 nruter;)]1-i[ffub(rahctup)--i ;0>i;b=i(rof;)43(rahctup;)]1-i[ffub(rahctup)--i ;0>i;mid=i(rof;)43(rahctup;i=b;)]1-i[ffub(rahctup)--i ;)';'==]i[ffub && ' '==]1-i[ffub(! && 0>i ;mid=i(rof;)0 =! ]++mid[ffub(elihw;b tni;0=mid tni;0=i tni{)cgra** rahc ,vgra tni(niam tni;"[NULL]};0 nruter;)]1-i[ffub(rahctup)--i ;0>i;b=i(rof;)43(rahctup;)]1-i[ffub(rahctup)--i ;0>i;mid=i(rof;)43(rahctup;i=b;)]1-i[ffub(rahctup)--i ;)';'==]i[ffub && ' '==]1-i[ffub(! && 0>i ;mid=i(rof;)0 =! ]++mid[ffub(elihw;b tni;0=mid tni;0=i tni{)cgra** rahc ,vgra tni(niam tni; = ffub *rahc" = ffub *rahc

In effetti il bug è difficile da tracciare, giacchè quei due byte errati non si vedono nella stampa a video (che stampa appunto solo i caratteri stampabili), infatti un byte ASCII 0 e un byte ASCII 32 (spazio) chiaramente non sono la stessa cosa. Il byte nullo in questione è visibile se ridirezioniamo l'output su un file, e apriamo il file con un editor di testo come Vim, che mostra tutti i caratteri ASCII, compresi queli non stampabili, possiamo vedere tali null, evidenziati con colore e simbolo speciali. Questi null peraltro impediscono a programmi come rev di GNU o allo scarabalter (scarabalter.c) di capovolgere la stringa passata in ingresso (l'output del programma della gara) giacchè durante il parsing incontrano dei terminatori di stringa (per i programmi codati in C, il byte nullo rappresenta il terminatore di stringa) inaspettati, e quindi non riescono a capovolgere la stringa di caratteri in input. Per risolvere il bug, bisogna fare la seguente piccola modifica al sorgente:

char* buff = "char* buff = ;int main(int argv, char **argc){int i=0;int dim=0;int b;while(buff[dim++] != 0);for(i=dim-1; i>0&& !(buff[i-1]==' ' && buff[i]==';');i--)putchar(buff[i-1]);b=i;putchar(34);for(i=dim-1; i>0;i--)putchar(buff[i-1]);putchar(34);for(i=b; i>0;i--)putchar(buff[i-1]);return 0;}";
int main(int argv, char **argc)
{
  int i=0;
  int dim=0;
  int b;
  while(buff[dim++] != 0);
  for(i=dim-1; i>0 && !(buff[i-1]==' ' && buff[i]==';'); i--)
    putchar(buff[i-1]);
  b=i;
  putchar(34);
  for(i=dim-1; i>0; i--)
    putchar(buff[i-1]);
  putchar(34);
  for(i=b; i>0; i--)
    putchar(buff[i-1]);
  return 0;
}

Alessandro Guido

char*s="};)'c'(rahctup;)'h'(rahctup;)'a'(rahctup;)'r'(rahctup;)'*'(rahctup;)'s'(rahctup;)'='(rahctup;)43(rahctup;)]i[s(rahctup)--i;0=>i;(rof;)43(rahctup;)';'(rahctup;)]i[s(rahctup)++i;0=!]i[s;0=i(rof ;i tni{)(niam diov";void main(){int i;for(i=0;s[i]!=0;i++)putchar(s[i]);putchar(';');putchar(34);for(;i>=0;i--)putchar(s[i]);putchar(34);putchar('=');putchar('s');putchar('*');putchar('r');putchar('a');putchar('h');putchar('c');}

Commenti:

Anche qui abbiamo una soluzione altrettanto eccellente!

Elegantissima la scansione della stringa, già capovolta, prima all'avanti (con conseguente determinazione della lunghezza della stringa) e poi all'indietro! Purtroppo, però, anche qui c'è la svista del null infiltrato: infatti l'output contiene un null verso la metà. Ecco l'output del programma (compilato da iro.c):

};)'c'(rahctup;)'h'(rahctup;)'a'(rahctup;)'r'(rahctup;)'*'(rahctup;)'s'(rahctup;)'='(rahctup;)43(rahctup;)]i[s(rahctup)--i;0=>i;(rof;)43(rahctup;)';'(rahctup;)]i[s(rahctup)++i;0=!]i[s;0=i(rof ;i tni{)(niam diov;"[NULL]void main(){int i;for(i=0;s[i]!=0;i++)putchar(s[i]);putchar(';');putchar(34);for(;i>=0;i--)putchar(s[i]);putchar(34);putchar('=');putchar('s');putchar('*');putchar('r');putchar('a');putchar('h');putchar('c');}"=s*rahc

Anche qui valgono le stesse considerazioni riguardo al null fatte sopra per bonfatti.c. Per risolvere il bug, bisogna fare la seguente piccola modifica al sorgente:

char*s="};)'c'(rahctup;)'h'(rahctup;)'a'(rahctup;)'r'(rahctup;)'*'(rahctup;)'s'(rahctup;)'='(rahctup;)43(rahctup;)]i[s(rahctup )--i;0=>i;--i(rof;)43(rahctup;)';'(rahctup;)]i[s(rahctup )++i;0=!]i[s;0=i(rof ;i tni{)(niam diov";
void main()
{
int i;
for(i=0;s[i]!=0;i++)
 putchar(s[i]);
putchar(';');
putchar(34);
for(i--;i>=0;i--)
 putchar(s[i]);
putchar(34);
putchar('=');
putchar('s');
putchar('*');
putchar('r');
putchar('a');
putchar('h');
putchar('c');
}

Programmi di correzione

Le correzioni dei testi dei concorrenti sono state fatte in automatico (a parte la manuale cancellazione dei null di troppo nell'output).

scarabalter.c

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
int main()
{
char *pc=(char*)malloc(sizeof(char));
unsigned int i=0,j;
char app;
while(read(0,pc+i++,1))
   pc=(char*)realloc(pc,(i+1)*sizeof(char));
i--;//Ora i rappresenta l'indice del terminatore di stringa
*(pc+i)='\0';
for(j=0;j<i/2;j++)
{
   app=*(pc+j);
   *(pc+j)=*(pc+i-1-j);
   *(pc+i-1-j)=app;
}
printf("%s",pc);
return 0;
}

 correggi-c.php

<?php
$sorgente="/home/nb/competition/arversa.c";
$output="/home/nb/competition/pippo";
$handle_s=fopen($sorgente,"r");
$handle_o=fopen($output,"r");
$str_sorg=trim(fread($handle_s,filesize($sorgente)),"\x00..\x20");
$str_out=trim(fread($handle_o,filesize($output)),"\x00..\x20");
$sfella=1;

if(strcmp($str_sorg,$str_out)==0)
   echo "Perfetto! 10 punti\n";
else if(strcasecmp($str_sorg,$str_out)==0)
   echo "Perfetto, ma non case sensitive! 9 punti\n";
else
{
   $tabu=array(" ","\n","\r","\t","\f","\v");
   $str_sorg=str_replace($tabu,"",$str_sorg);
   $str_out=str_replace($tabu,"",$str_out);
   if(strcmp($str_sorg,$str_out)==0)
      echo "Ok (ripulito da caratteri speciali). 8 punti!)\n";
   else if(strcasecmp($str_sorg,$str_out)==0)
      echo "Ok (ripulito da caratteri speciali), ma non C.S.. 7 punti!\n";
   else
   {
      $sfella=0;
      echo "L'output del programma è errato.\n";
   }
}
if($sfella)
   echo "(Togliere 5 punti se il programma stampava alla dritta)\n";
fclose($handle_s);
fclose($handle_o);
?>

Inoltre c'era uno script in shell (che non trovo più!) che accettava come parametro il nome del file del sorgente consegnato dal partecipante, e in automatico preparava tutto (facendo le opportune rinominazioni, ecc.), compilava, eseguiva e chiamava lo scarabalter e poi chiamava l'eseguibile di PHP e gli passava correggi-c.php.
Quindi ad esempio per correggere il sorgente di Pinco Pallino si lanciava "./correggi.sh pincopallino.c" e veniva stampato a video il punteggio relativo al sorgente del partecipante.
Siccome però è stato necessario intervenire manualmente per rimuovere dei null dagli ouput dei sorgenti dei due vincitori, è stata applicata una penalità di 0,5 punti. Questo non toglie nulla alla strabiliante bravura dei vincitori!