Smallest Possible ELF Executable?

taviso writes "I recently stumbled across this paper (google cache), where the author investigates the smallest possible ELF executable on linux, some interesting stuff, and well worth a read. The author concludes, 'every single byte in this executable file can be accounted for and justified. How many executables have you created lately that you can say that about?'

No law on repeat articles?

[ebuck]

Last time I read this on slash dot was less than a year ago. I imagine in 4 or 5 months we'll see it again.

The article is great. It really is a good intro to refresh that assembly / understand ELF / do neat stuff. I still have the tiny assembler installed on my machine from the last go round.

I've heard of a guy who is trying to make the world's smallest 'cat' program. I wonder how many other utilities have been similiarly "optimized"

Turbo Pascal

[DNS-and-BIND]

I seem to remember making some damn small Turbo Pascal .COM files. Under 4096 bytes, IIRC.

Small virus catcher (for DOS)

[Fuzzums]

in assembly: RET

All this one byte program does is terminate execution. If it's infected by a virus you'll see soon enough if the size has increased.

ofcourse with todays macroviruses this doesn't work anymore :(

Correction

[ebuck]

Well, someone will point it out soon, so I might as well do it myself.

nasm is the name of the assembler, not tiny.

You can make a 45 byte version of the 'true' and 'false' utilities by changing the output to 1 or 0 respectively. Some shells implement these as builtin functions, but it does show a pratical (albeit odd) way to save a few bytes of disk space.

Re:Turbo Pascal

[compwizrd]

Some of the old-time Demo groups (and warez groups) would put very nice VGA demos in 4k as well.

Windows exe

[Sivar]

Cas, or StorageReview.com's forums, created a 324 bytes Windows 2000 PE executeable. It completely blew away all of mine, the smallest of which were about ~700 bytes.

Re:umm.... yeah?

[Leonel]

Did you bother to read it?

From the article, after the first try in asm:

Looks like we shaved off a measly twelve bytes. So much for all the extra overhead that C automatically incurs, eh?

Re:Turbo Pascal

[dknj]

They still do pack some nice effects into 40k windows binaries now.. I'm still amazed

-dk

Not bad...

[Captain Pedantic]

But I'd like to see them get a Breakout clone in 1K [demon.co.uk]

Even Shorter...

[MarvinMouse]

While the program would be completely useless.

You could make it even shorter by having it return absolutely nothing (Just having it execute and finish.)

It could be useful to catch when anything starts to modify programs on your computer, because if the "thing" just modifies programs, it will recognize it as a program, and increase the size notably.

I really like the 45 byte program though, too bad that after you passed 100 bytes, it became totally non-compliant.

No need to be smaller than 512 really...

[Anonymous Coward]

Harddrive sizes being what they are now, the smallest sector size I see is 512 bytes. If the file stored in that sector is smaller than 512, it still takes up 512 bytes. Very intersting article however.

3d Tube in 256 bytes

[timbong]

I think this [pouet.net] is more interesting and the source code (assembler) is included too.

112 bytes for mandlebrot

[Anonymous Coward]

I remember writing a 112 bytes executable (including headers) in 68000 assembly language that could draw mandlebrot fractals. I am pretty sure you can't get it smaller than that (at least on the 68000), I'd done the register coloring dependency graph by hand.
One of the smallest yet greatest thing I ever wrote.

Even smaller

[ggeens]

:
w

The colon on the first line is an older version of the #! line, but only works for sh. And of course, `w' is one character less than `ls'.

On systems that automatically use /bin/sh on unknown files, the smallest possible shell script is:

w

Yes, a single character.

32 byte run-length decompressor?

[Zaiff Urgulbunger]

I remember years ago writting a run-length decompressor in Z80 asm that was 32 bytes. I think the compressor was 50 something bytes!

I also recall adding up the clock cycles for all of this to try and find the fastest implementation!

I'm over it now though!

I'm just glad to forget those cassette-tape based, hand coded assembler days, but it is kind of a shame to see how bloated code has got. If only I'd had a macro-assembler on my Sinclair ZX Spectrum (Timex something or other in the US) in those days... oh the world could've been mine!!

its not executable size that matters

[Capt. Beyond]

Its not so much the executable size that really matters (when talking about bloat), its the memory consumption of the program that really matters.I could write a very small program size wise that would drain your memory and crash your system, or make it slow down to a crawl.

MenuetOS

[jaaron]

On a similar topic, MenuetOS [menuetos.org] is a full OS written in assembly and fits on a floppy. Yeah, lots of OS's used to fit on floppies, but it's still cool. It's amazing what all you can fit into a small space if you're careful.

256b...

[Skiboo]

www.256b.com [256b.com] is a site full of little 256 byte windows programs. It's amazing what they can do in that tiny amount of space. All assembler, all with source code, it's worth checking out.

It's kind of a contest to see who can come up with the best 256 byte program.

4K Demos

[Wraithlyn]

Some of the 4K demos I've seen written for ASM competitions completely blow my mind... check out this one [sanction.de], it's basically a flythrough of the first level of Descent, with texture mapping, source lighting, animated lava and recharger field, a MIDI soundtrack, etc... all in 4095 bytes!!!

Here is Sanction's home page, it contains a couple more very impressive 4K demos.

What about the Visual Studio .NET compiler?

[Jugalator]

Stand-alone console EXE (Release Build):

#include "stdafx.h"

int _tmain(int argc, _TCHAR* argv[])
{
return 42;
}

Size: 20,992 bytes

To be compared with the non-optimized gcc version at 3,998 bytes. :-)

I wonder how small you can make a Windows EXE..

Re:Turbo Pascal

[irc.goatse.cx troll]

40k? luxury!
try 256 bytes ;) [256b.com]

A great site concerning this theme

[cvore]

www.linuxassembly.org/ - Go there, its free and fun :-)

Re:What about the Visual Studio .NET compiler?

[Jugalator]

Hm... I stripped the code from stdio.h, replaced _TCHAR* with char* so the stdafx.h doesn't really do much at all. Then turned on size optimizations and turned off boundary checks etc in the compiler. Still exactly 20992 bytes. Huh?? Browsed the exe and there's full text messages like "ooh something corrupted the state of this program and it cannot safely continue". Which is actually a great addition by Microsoft, but can't you remove such things? :-)

But I guess the .NET compiler has its lower limits where bloat get called feature, just surprising that it seems to compile at the minimum size by default... Or perhaps it use some kind of silly padding so even if there's less code, the physical size isn't reduced.

smallest executable: cero bytes

[Anonymous Coward]

Yes, if in Linux (maybe other *nix) you create a file with cero bytes (touch foo) and give it the execution permissions, you can execute it without error nor warning. It is not an elf executable and
after executing it you obtain: nothing (as you guess), but it is a funny completness property of system (null operator).

I saw this in one of the first
[ioccc.org]
International Obfuscated C Code Contests.

Re:112 bytes for mandlebrot

[Anonymous Coward]

The record for mandelbrot on DOS is 69 bytes, and 175 bytes for Linux (by me, framebuffer). See linuxassemly.org -> asmutils

Re:4K Demos

[Wraithlyn]

Do you remember Future Crew? And the legendary Second Reality demo of '93? (Available here [mbhs.edu], but can be hard to run properly on modern systems) Apparently many of those guys are now working at Remedy... which may explain why Max Payne is such a graphically beautiful game... I wouldn't be surprised in the slightest if the Max FX engine employs some nice ASM routines. Also, check out their Final Reality benchmark [instantnetworks.net], the final "cityscape flythrough" is a homage to a nearly identical (albeit flat shaded) sequence in Second Reality. Cool shit.

Re:Excellent troll!

[rplacd]

> Would you really want to try to repair a broken system without ls?

I've had to -- echo * works well enough, sometimes. Some Linux install disks give you a shell, but few utilities other than mount, mknod, cat, etc. Now, if they gave us ed I wouldn't have to "cat >> /mnt/etc/fstab" and the like.

If you search the FreeBSD freebsd-hackers mailing list, you'll even find a "more" command implemented with shell builtins (at least, I don't remember it using cat). It's too long to remember, though.

Re:3d Tube in 256 bytes

[archen]

Something else to check out for those interested in tight code: the .product, by Farb-rausch consulting.

http://www.theproduct.de/

Kids don't try this at home :-)

[Antity]

The first few examples are quite noteworthy, but when the author starts to put code inside the ELF header, it gets really ugly..

Saying that these bytes are "only padding anyway for future extensions" doesn't feel that good. :-)

This remembers me of early attempts on AmigaOS to shorten and fasten executables where people could be sure that all available Amigas would only use the lower 24 bits of 32 bit address registers since the machines could only address 24 bits physically. So they put application data into the upper 8 bits of registers. Worked fine.

Then came newer machines which really used the full set of 32 address lines and all those dirty programs crashed without obvious reason..

The author says "if we leave compatibility behind.." but what he's doing is not only leaving inter-OS compatibility behind - what he creates isn't even an ELF executable anymore. It's just something that happens to work with this special Linux version.

So since this isn't even an ELF executable any more, there's no reason not just to write "exit 42" in bash (which would be an amazing 8 bytes in size *g*).

Don't misunderstand me, I really like those hacks. But I myself will never, ever again code something that is prone to break in the future just because I didn't follow standards.

One could say that this is what programming is about. :-) No offence meant.

Re:Interesting topic...

[Blkdeath]

But given that, in most cases, disk space is vast, and memory is plentiful, there isn't much in the way of usefulness. Maybe in some niche' applications running on tight hardware... but running Linux.

Consider for a moment what the GNU world would be like if every byte, primarily of our base system, was accounted for. Imagine a Linux distribution on the shelf with a "Zero Overhead" label on it - and be able to mean it!

Consider Linux 2.4.x running on a 486 with 16MB of RAM - and having 14 of it free for applications even with init and Bash running.

Now expand the concept to GUI applications, XFree86, etc. and think of how blazingly FAST the entire Linux experience would be, even on the most mediocre hardware. People would get a CPU upgrade and their systems would boot to KDM as if it was already loaded.

Considering too the fact that every (assuming based on my own HDDs and limited knowledge of IDE transfer code) 8KB of program code requires a separate disk read operation to load to cache. Every 8KB that's shaved off an application's startup routines is one less disk read, which means those dusty old ATA33 hard drives would suddenly seem a lot more worthwhile to keep around (not to mention they'd be big enough, what with reduced size constraints) - an especially Good Thing<TM> considering recent changes in manufacturer policy [slashdot.org] where new drives are concerned.

The excuse that CPU/RAM/HDD is inexpensive is a lousy one at best. It's cheap because bloated programs and operating systems have driven up demand, which has caused a surge in supply, which has dropped the prices. Imagine a world though where it was only the Windows weenies who had to trundle out to their resident computer store [highfield.ca] every other month to accomodate their latest cabre of software updates? We'd be able to laugh at them, knowing full-well that our K62-400s were smoking their brand-new P4-3.0GHz super-screamer systems.

</RANT>

Embedded systems need efficiency

[yerricde]

CPU is cheap, hard disk is cheap.

Maybe on PCs, but not on embedded systems, handheld systems, or game consoles. The Game Boy Advance, for instance, has only 384 KB of RAM, and all but 32 KB are 16-bit bus width with muchos wait states. Many microcontrollers inside such things as microwave ovens are as powerful as an Atari 2600 VCS, with 128 bytes of RAM and about 12 bytes of VRAM (if that).

Small demos aht the like...

[the_arrow]

I remember in the "good old days" (tm) on the Amiga, when some (well, quite a lot actually :) people managed to make small intros with sine-scrolling multi-colored text in less than 512 bytes, all done in the bootblock which also had a loader for whatever game/demo was on the disk.

Re:Excellent troll!

[Tet]

I've had to -- echo * works well enough, sometimes. Some Linux install disks give you a shell, but few utilities other than mount, mknod, cat, etc. Now, if they gave us ed I wouldn't have to "cat >> /mnt/etc/fstab" and the like.

For probably the ultimate description of recovering from a screwed system without access to the normal tools, see Al Viro's inhuman heroics here [google.com].