With ever increasing sizes of various programs (video games being notorious for this), the question of size optimization comes up more and more often. [Nathan Otterness] shows us how it’s done by minifying a Linux “Hello, World!” program to the extreme.
A naive attempt at a minimal hello world in C might land you somewhere about 12-15Kb, but [Nathan] can do much better. He starts by writing everything in assembly, using Linux system calls. This initial version without optimization is 383 bytes. The first major thing to go is the section headers; they are not needed to actually run the program. Now he’s down to 173 bytes. And this is without any shenanigans!
The first shenanigans are extreme code size optimizations: by selecting instructions carefully (and in a way a C compiler never would), he shaves another 16 bytes off. But the real shenanigans begin when he starts looking for spaces in the ELF header that he can clobber while the program is still accepted by Linux: now he can move his already tiny x86_64 code into these “vacant” spaces in the ELF and program headers for a final tiny ELF file weighing in at just 120 bytes.
P.S.: We know it is possible to make this smaller, but leave this as an exercise to the viewer.
How does this compare to using a.out?
That was my first thought as well. I can’t seem to get nasm to produce a 64-bit a.out that will actually execute, though; is a.out even supported on x64 Linux?
I at least think it’s still the native output format for single-file GCC. If you don’t use -o you still get a file named a.out at least.
https://www.phoronix.com/news/Linux-Remove-a.out
64 bytes for elf ident and header
There will always be minimum 2 program headers, 1 for elf header, 2nd for text section
Then 2 section header, 1 for string tab maybe, another for text section
You can remove unnecessary space then change the offset
Coming from the RTEMS* crowd, I expected an attempt at making a tiny Linux kernel. Instead it’s just a tiny “hello world”. Meh.
* Real-Time Executive for Multiprocessor Systems
Same here
Pretty sure the title for that would be “How small can a Linux kernel be?” . Who would write this and use the word executable? That would be weird.
I was inspired by the very first sentence of the article.
After reading this sentence, my first thought was that the article is going to be about bloat of modern Linux kernel and how it was optimized. When I understood that someone simply abused the elf loader to display a “hello world” message, it was “meh.”
Also, I think Windows also uses the word “Executive” when referring to core parts of its NT kernel.
To the point of bloat in Linux, my understanding is staying rooted in C/Rust they are able to avoid bloat. The other factor is contributions to the kernel must be of a certain quality, problem code doesnt get in.
I run Linux so when I execute something I made in C I get the best performance. I also use Windows since hardware drivers plug and play so much better
Linux has virtual memory, which keeps tasks (processes) from clobbering each other. I’m fond of RTEMS, FreeRTOS, etc. but this is a different class of OS. (Don’t mention VxWorks — I’ve just had dinner…)
This reminds me of the mainframe program IEFBR14, which was one instruction long. I used it often.
Missed the “World’s smallest elf” pun
The smallest DOS program I ever encountered was around 10 bytes while still doing something useful. It waits for a keypress, and then set the error level with the key’s code. Intended use is to make choices in batch files. In DOS, the .com files were loaded directly into memory, and then execution started from the start. The OS didn’t do any sort of initialization as it does for .exe files. I don’t know if Linux has something like that.
With DOS it is easy because .com files don’t have any header. The first byte is the start of the first instruction.
Yeah. I also want to know. I once wrote an app as a .com, that copied a command line over its own PSP and then called int21 to run dos programs and inspect the exit codes. Fitted into around 256 bytes of ram, half of that was the environment block, so it really was around 128 bytes. The binary however was a lot bigger and did all the code moves, back in the day when code segments were not enforced, in the .com executable format.
Back in the 8086 days, I wrote a small “Hello World” that used BIOS calls (int 10).
With all the modern anti-BIOS security shenanigans, I’m not sure it would even run now.
Maybe in a WINE emulator?
There’s an old gag about “real programmers use ‘copy con foo.exe'” [or, as mentioned, foo.com] … but this is dang close.
There’s an article from 1999 detailing a 45 byte ELF binary that linux will load (even though it violates the spec): https://www.muppetlabs.com/~breadbox/software/tiny/teensy.html
Someone was doing size optimisations on android app’s .apk sizes. The final thought was, “an application does not need an activity, so let’s remove it.”
Unfortunately an android app without an activity and without a service, is just an icon in your apps list. So essentially it did nothing. But it was a valid .apk in a couple hundered bytes.
No.
Okay, this are now the possible extremum for the masters. But what can we do to push the average programer to generate code that is 10 times smaller and 10 times faster? Do we need a new special developing enviroment with a lash, pillory and glowing pliers?
If you’re thinking that there’s a lot of wasted space in compiler-produced assembly, there’s apparently much less than there used to be. The actual method to get programmers to produce software that is smaller and faster is to rethink whatever it is that they’re designing.
If your hypothetical program only needs a small part of a much larger library, maybe you can toss that function into the code you’re writing. This is bad, and dumb, but statically linked functions can improve speed. If you’re very sure that other software will already have a function available – lean heavily into whatever tools are already there rather than calling up a library. (As an example, .kkrieger has held the title for the world’s smallest FPS at <97Kb. It leans very heavily on DirectX calls to do pretty much everything, meaning that in practical terms the game is a 33Mb download since that was roughly the size of the DirectX 9.0 installer.)
The other place to look is in what functions the software presents to the user. Code that does one thing, and that thing only, can be very small as long as its features are limited. Compare the 40Kb of the linux 𝚌𝚊𝚝 command to the multi-megabyte size of 𝚟𝚒𝚖.
Let me give you a bad example. If you buy a multimeter you expect you can switch it on and it measure a voltage. Now, if you by the new Rigol DM858 Multimeter it boot Android. That took at every startup the same time than your cellphone needs when you switched it on the first time. Is that okay? What is the reason for this compared to multimeter?
In the past I switched on my car stereo and it worked instantanly. Now with new and shiny DAB reciever it tooks 10s for something nobody knows.
A few weeks a ago my Sony TV (with Android) recieved an unwanted (ARGH!) update of the operating system. Now I switch it on and I have to wait 5-10s before it possible to open the channel select screen. Before that is work with 1s wait time.
If you search for it you can easy find thousand and thousands of devices that become more shitty than in the past.
The world slows down because programer become to lazy to do there job right!
The world slows down because tasks got so complex, that programmer would have to work for at least 5 years to deliver a product, which would then already be obsolete at the time of its release.
Blaming the ordinary programmers for that is like blaming civilians who were the victims of a war crime. You can either have a job and be able to put food on the table, or you can work on efficient software for an indefinite amount of time while feeding on your own toenails like Stallman.
Don’t worry, I have you covered. Just ship it to me and I’ll ship you back a plain old multimeter with no OS in exchange. Instant on! Do you prefer digital or analog? Reply back and let me know!
Make developers use a Pentium-100, 16GB of RAM and text terminals for both editing source code and test running the programs. Parkinson’s law applies to programming to.
What’s the point in making anything smaller than a sector on the disk? ÂŻ(°_o)/ÂŻ
So you can pack gazillions (instead of millions) of them in a zip.
Before refactoring:
s.o: file format elf64-x86-64
Disassembly of section .text:
0000000000000000 :
0: 48 31 c0 xor %rax,%rax
3: 48 31 ff xor %rdi,%rdi
6: 48 ff c0 inc %rax
9: 48 ff c7 inc %rdi
c: 48 c7 c6 00 00 00 00 mov $0x0,%rsi
13: 83 c2 0c add $0xc,%edx
16: 0f 05 syscall
18: 48 c7 c0 3c 00 00 00 mov $0x3c,%rax
1f: 48 31 ff xor %rdi,%rdi
22: 0f 05 syscall
0x23/ 35 bytes text section and Hello world in data section
after refactoring:
0000000000000000 :
0: b0 01 mov $0x1,%al
2: 40 b7 01 mov $0x1,%dil
5: 48 c7 c6 00 00 00 00 mov $0x0,%rsi
c: 83 c2 0c add $0xc,%edx
f: 0f 05 syscall
11: b0 3c mov $0x3c,%al
13: 31 ff xor %edi,%edi
15: 0f 05 syscall
0x16/23 bytes
update
file offset of text section must be atleast 0x1000 and for data section 0x2000
Some bloke back in 1999-2001 Hugi assembly Compo days crafted an executable that ran on both Linux ELF and Windows command line MZ executable. Forget how big it was, perhaps 200 bytes, and did nothing, but it was crafter so that the single exe ran on both platforms successfully.
https://en.wikipedia.org/wiki/Fat_binary
Reminds me of the DOS+OS/2 “Family API” (FAPI).
https://virtuallyfun.com/2021/05/16/all-in-the-family/
But where does he save that program? On a disk with block size = 1 bit ?
C programs can be made smaller if K&R C coding style is used and if stdio.h is being left out.
For simple text mode applications that can be enough.