Tiny 64-bit ELF executables

NASM 64-bit ELF headerSeveral years ago I read an excellent guide to ELF executables called “A Whirlwind Tutorial on Creating Really Teensy ELF Executables for Linux.” It outlines some of the factors that contribute to overhead in ELF executables, and goes to great lengths to make the smallest-possible ELF program. Unfortunately, the tutorial only covers 32-bit ELF executables. By hand-coding the ELF and program headers and compiling them with NASM, it’s also possible to create very small 64-bit ELF programs.

For instance, a 64-bit “Hello World!” program written in C and compiled with gcc takes up 8.2 kilobytes on my system. When the same program is written in assembly and compiled using the techniques outlined by Raiter, it only takes up 152 bytes. Further improvements are possible, but they entail some compatibility-compromising hacks that may reduce portability between different systems and versions of Linux.

tl;dr: Download the zip file containing the sources and makefile here, or get the 32-bit and 64-bit sources and compile them individually (here are the fully optimized 32-bit and 64-bit sources). To compile all of the examples, extract the files from the archive and type “make” or compile them yourself with
$ nasm -f bin [filename]
.

Teensy 64-bit ELF Executables

The original guide to teensy ELF executables shows that you can cut most of the fat from a compiled program by creating an executable that provides an ELF header, a program header, a main routine and nothing else. A program that doesn’t link to external libraries or rely on other resources doesn’t need anything else, but regular compilers don’t bother cutting out the unnecessary sections. The techniques in the Teensy Elf guide can be applied almost directly to the 64-bit ELF format with a few key adjustments.

The 64-bit ELF Header

The ELF specification defines the 64-bit ELF header with the following struct:

The 64-bit ELF header is exactly like the 32-bit ELF header except for the size of its address and offset entries. While the word and halfword entries are consistent between 32 and 64-bit architectures, Elf64_Off and Elf64_Addr entries are 8 bytes long (64 bits) and Elf32_Off and Elf32_Addr entries each take up four bytes (32 bits).

The 64-bit ELF Program Header

The 64-bit ELF program header is similar to the 32-bit phdr except that in addition to the different address and offset widths, the segment’s flag values are in a new location:

Creating a Tiny 64-bit ELF Header in NASM

Porting the data from the ELF spec into NASM allows us to create a 64-bit NASM ELF template. This is a 64-bit version of the Teensy ELF proposed in the original tutorial. The main routine is taken from the “64-bit NASM Hello World” tutorial:

Compiling and running

Download the package containing the source files here, or get the 32-bit and 64-bit sources and compile them individually.To compile all of the examples, extract the files and type “make” or
$ nasm -f bin [filename]
.

wc shows the dramatic difference in the compiled program sizes:

The NASM programs are 40-60 times smaller than the program compiled by gcc with default settings.

Assembly Optimizations

By carefully choosing instructions, a few bytes can be shaved from each executable. For instance, as François-Renaud Escriva pointed out in the comments, instead of using 64-bit register instructions, specifying 32 or even 16-bit registers can make the instructions smaller and save a few bytes. Also, as olsner pointed out on r/osdev, the CDQ instruction will sign-extend eax into edx, effectively doing the same thing as xor edx, edx in less bytes since eax contains a positive value. The optimized 64-bit program looks like this:

Using the optimized routine shaves 66 bytes from the 64-bit executable, resulting in a 152 byte ELF. Similar optimization shaves only 7 bytes from the 32-bit ELF.

The original Teensy ELF tutorial provides additional improvements by overlapping the ELF and program headers, but the resulting executables may not work consistently across different systems and versions. If you want an even smaller ELF, playing with the headers is your next step.

Further Reading

System V Application Binary Interface - ELF Header and Program Header specs

A Whirlwind Tutorial on Creating Really Teensy ELF Executables for Linux (again)

Incoming search terms:

One thought on “Tiny 64-bit ELF executables