Je constate avec joie que mon petit jeu a eu du succès...
Certains ont remarqué que je n'avais pas spécifié le langage à utiliser.
C'était fait exprès. Le problème était rédigé de façon à faire penser au
C, mais sans le spécifier explicitement, pour voir si certains pensaient
à autre chose. Du coup je peux maintenant faire des catégories.
Scripts
=======
Vainqueur dans la catégorie script, et aussi toutes catégories
confondues, Jérôme Kieffer, avec un script bash de 29 octets (il a
oublié la virgule après Hello, mais c'est compensé par l'espace qu'il a
mis en trop avant ! et qui est un gallicisme).
Cependant on peut faire mieux. Voici un script de 28 octets (soit un de
moins) qui fait la même chose :
#!/bin/sed 1d
Hello, World!
En trichant un peu, 19 octets :
echo Hello, World!
C'est de la triche car ça ne marche que si c'est lancé par le shell : ça
ne marche pas avec execl() par exemple. La raison est que c'est le shell
(et non le noyau linux) qui interprète ça comme un script (du shell
considéré).
En trichant encore plus (là j'abuse), 11 octets :
$ echo -n '#!/bin/echo' > ^H^HHello,\ World\!
$ ./^H^HHello,\ World\! && echo ni!
Hello, World!
ni!
Il faut remplacer les ^H par des Control-H (taper Control-V Control-H).
On peut rajouter des Control-H si on veut pouvoir appeler le script avec
un chemin plus long.
Langages compilés (C en fait)
=============================
Ici c'est Lucas Nussbaum qui remporte la palme avec un exécutable de 716
octets compilé avec diet. Cependant, à lire la description dans le site
web en question, il n'est pas clair si son Hello, World! est lié
statiquement ou dynamiquement. Est-ce que tu pourrais me l'envoyer, pour
voir ?
> Alors, je gagne quoi ? :)
Si c'est statique, une bière à la prochaine bouffe Guilde, car je suis
content d'avoir appris l'existemnce de diet. Si c'est du dynamique, rien
du tout, car sur la plupart des Linux il ne tournera pas.
Je voudrais quand-même commenter la proposition de Pierre Pronchery,
surtout parce que j'étais au départ parti sur la même idée :
int main() { write(1, "Hello, world!\n", 14); return 0; }
L'idée est bonne : se passer de la libc et utiliser directement les
appels système linux. Cependant telle quelle elle ne marche pas. En
compilant et en stripant ça, j'obtiens un exécutable de 3308 octets.
Pierre obtient 2784 octets car on n'a pas les mêmes gcc et libc.
Finalement on ne gagne pas grand chose sur le Hello, World! de base.
La raison pour laquelle ça ne marche pas est qu'on est quand-même en
train d'utiliser la libc sans s'en rendre compte : pratiquement tous les
appels système sont wrappés par la libc et le compilateur linke toujours
avec celle-ci, même si on ne le lui demande pas (essayez gcc -v pour
voir). C'est d'ailleurs un fichier de la libc (crt1.o) lié statiquement
à l'exécutable qui se charge d'appeler main(). Le vrai point d'entrée du
programme s'appelle _start(). Si on veut vraiment se passer de la libc,
il faut déclarer soi même les appels système avec les macros _syscall*()
et faire l'édition de liens explicitement avec ld :
$ cat hello.c
#include <linux/unistd.h>
int errno;
static inline _syscall3(int, write,
int, fd, const void *, buf, int, count);
static inline _syscall1(int, exit, int, status);
void _start(void) { write(1, "Hello, World!\n", 14); exit(0); }
$ gcc -w -O -c hello.c
$ ld hello.o -o hello
$ strip hello
$ wc -c hello
916 hello
$ ./hello && echo ni!
Hello, World!
ni!
Les macros _syscall*() font en fait de l'assembleur en ligne. Elles
utilisent la variable externe errno (normalement de la libc), mais on
peut raccourcir le programme en supprimant la gestion de errno :
$ cat hello.c
#include <linux/unistd.h>
#undef __syscall_return
#define __syscall_return(type, res) return (type) (res)
static inline _syscall3(int, write,
int, fd, const void *, buf, int, count);
static inline _syscall1(int, exit, int, status);
void _start(void) { write(1, "Hello, World!\n", 14); exit(0); }
ce qui me donne un exécutable de 884 octets. On n'est pas loin des
performances de diet sans outils particulier.
Mais bon, vu que les macros c'est de l'assembleur inline caché, on est
presque dans la catégorie suivante.
Assembleur
==========
Ici j'aurais envie de déclarer vainqueur Pierre Pronchery. Jean-Noel
Avila, qui trafique les en-têtes ELF, est renvoyé dans la catégorie
héxa.
Voici ma version, un peu moins bonne (544 octets). Comme je ne sais pas
programmer en assembleur, j'ai pris l'assembleur généré par gcc -O et
j'ai simplifié ce que j'ai pu :
.globl _start
_start:
movl $4, %eax # write(
movl $1, %ebx # 1,
movl $message, %ecx # message,
movl $14, %edx # 14
int $0x80 # );
movl $1, %eax # exit(
movl $0, %ebx # 0
int $0x80 # );
message:
.string "Hello, World!\n"
Je compile avec
as -o hello.o hello.s
ld --gc-sections hello.o -o hello
strip hello
C'est pratiquement le même code que ce que donne Lucas. Je suppose que
la différence tient aux outils d'assemblage (nasm vs. gas). Je précise
que je peux réduire ce programme de 544 à 196 octets simplement avec
head -1 :
mv hello hello.orig
head -1 hello.orig > hello
chmod a+x hello
(oui, c'est brutal, mais le programme marche toujours). Seulement
trafiquer ainsi le fichier nous fait entrer dans la catégorie suivante.
Héxadécimal
===========
(où, ce qui revient au même, tout moyen de trafiquer la structure ELF du
fichier)
Alors là, je suis complètement bluffé par le code de Brian Raiter, posté
par Jean-Noel Avila. 59 octets pour un binaire ELF ! Chapeau.
Voici toujours ma solution en 132 octets. Je me suis inspiré du
programme précédent et de la description du format ELF dans
http://www.linuxjournal.com/article.php?sid=1060 et
/usr/src/linux/include/linux/elf.h. J'ai enlevé les en-têtes de
sections, l'espace inutilisé ainsi que les sections inutiles. Voici ce
qui reste :
# En-tête fichier ELF (52 octets, incompressible) :
000000: 7f 45 4c 46 01 01 01 00 00 00 00 00 00 00 00 00 # signature
000010: 02 00 # type = exécutable
000012: 03 00 # machine = i386
000014: 01 00 00 00 # version ELF
000018: 54 80 04 08 # début prog en mémoire
00001c: 34 00 00 00 # début des en-têtes programme
000020: 00 00 00 00 # début des en-têtes sections
000024: 00 00 00 00 # drapeaux
000028: 34 00 # taille en-tête ELF
00002a: 20 00 # taille en-têtes programme
00002c: 01 00 # nombre d'en-têtes programme
00002e: 28 00 # taille en-têtes sections
000030: 00 00 # nombre d'en-têtes section
000032: 00 00 # numéro de la section .shstrtab
# En-tête programme (32 octets, incompressible) :
000034: 01 00 00 00 # type = « loadable »
000038: 00 00 00 00 # offset dans le fichier
00003c: 00 80 04 08 # adresse virtuelle
000040: 00 80 04 08 # adresse physique
000044: 84 00 00 00 # taille dans le fichier
000048: 84 00 00 00 # taille en mémoire
00004c: 05 00 00 00 # protection mémoire 05 = r-x
000050: 00 10 00 00 # alignement = 4 ko
# Code (34 octets) :
000054: b8 04 00 00 00 # movl $4, %eax
000059: bb 01 00 00 00 # movl $1, %ebx
00005e: b9 76 80 04 08 # movl $message, %ecx
000063: ba 0e 00 00 00 # movl $14, %edx
000068: cd 80 # int $0x80
00006a: b8 01 00 00 00 # movl $1, %eax
00006f: bb 00 00 00 00 # movl $0, %ebx
000074: cd 80 # int $0x80
# Données (14 octets, incompressible) :
000076: 48 65 6c 6c 6f 2c 20 57 6f 72 6c 64 21 0a # "Hello, Wolrd!\n"
000084
Soit 84 octets dans deux en-têtes ELF, 34 de code et 14 de données. On
peut encore réduire un peu la taille du code en utilisant le fait que
Linux initialise les registres à zéro. Du coup il suffit de manipuler
uniquement les octets de poids faible (registres al à dl) :
# Code réduit (16 octets, difficilement compressible)
000054: b0 04 # mov $0x4,%al
000056: b3 01 # mov $0x1,%bl
000058: b1 10 # mov $0x10,%cl
00005a: b2 0e # mov $0xe,%dl
00005c: cd 80 # int $0x80
00005e: b0 01 # mov $0x1,%al
000060: b3 00 # mov $0x0,%bl
000062: cd 80 # int $0x80
Mais il faut alors charger le programme à l'adresse 0 (remplacer les 80
04 08 par 00 00 00 dans les en-têtes). On est à 114 octets. Je pense que
c'est le plus petit qu'on puisse avoir pour un ELF propre. On voit que
si on veut gagner encore, il faut réduire la place des en-têtes. Par
exemple, l'ent-ête a.out suivante :
# En-tête a.out (32 octets, incompressible) :
000000: 07 01 64 00 # signature (OMAGIC)
000004: 30 00 00 00 # taille segment texte
000008: 00 00 00 00 # taille segment données
00000c: 00 00 00 00 # taille segment données non initialisées
000010: 00 00 00 00 # taille table des symboles
000014: 00 00 00 00 # début du programme en mémoire
000018: 00 00 00 00 # taille des « relocations » du texte
00001c: 00 00 00 00 # taille des « relocations » des données
peut remplacer les deux en-têtes ELF, mais le chargeur a.out du noyau ne
semble pas mettre à zéro les registres. On se retrouve à 80 octets.
Seulement le format a.out n'est plus très supporté ou demande
l'installation d'un module.
La solution de Brian Raiter consiste en fait à repérer les champs
inutilisés des en-têtes ELF et en profiter pour écrire les deux en-têtes
et le programme *les uns par dessus les autres* :
En-tête fichier ELF : 52 octets (octets 1 à 52)
en-tête programme : 32 octets (octets 4 à 36)
code : 22 octets (octets 21 à 42)
données : 13 octets (octets 47 à 59, pas de !)
----------------------------------------------------------
Total : 59 octets
En fait il y a même des champs utilisés qui sont ainsi recyclés.
Tout ça est très acrobatique et me conduit à la conclusion que le format
ELF, avec ses 84 octets d'en-tête, n'est pas bien adapté aux petits
programmes.
Edgar.
--
Edgar Bonet Tél : 04 76 88 10 96
Laboratoire Louis Néel -- CNRS Mobile : 06 77 19 79 39
25 av. des Martyrs, BP 166 Fax : 04 76 88 11 91
38042 Grenoble cedex 9, France e-mail : guilde@???
