Slashdot Mirror
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?'
It isn't amazing until its also palindromic!
The only good weather is bad weather.
I just heard the news on slashdot -- Frodo Baggins, the smallest elf, was just executed! No other details were available.
... wanting to execute the smallest possible elf. You Americans and your bloodsports. Barbarians.
If you guys go ahead with your cold-hearted plan to execute this elf, the Olsen twins better watch their backs next time they're in Ireland, if you catch my drift.
- SMJ - (It's not just a name: it's a bad aftertaste.)
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
Privacy is terrorism.
This makes my new 100-gig hard drive seem WAY too big.
Some of the old-time Demo groups (and warez groups) would put very nice VGA demos in 4k as well.
every single byte in this executable file can be accounted for and justified
The author's sanity, however, cannot.
moto411.com
I think there are quite a few. It's seen as a challenge, and does have practical uses. Have a look at Toms Rootboot disk - it includes a web server, a telnet server, a telnet client, an nfs client, wget, gzip, bzip2, vi, a whole load of network drivers, and a tonne of other stuff, all compressed down onto one floppy disk. Only I've never quite been able to find the source code for any of it despite spending a small amount of time looking - possibly someone would be able to put me right on that one.
There are also lots of interesting articles on linuxassembly.org.
Andrew
But I'd like to see them get a Breakout clone in 1K
None are more hopelessly enslaved than those who falsely believe they are free. Johann Wolfgang von Goethe.
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.
Soon I realized that smaller programs are not the end-all goal of programming. If a slightly bigger program is easier to understand for the next person who modifies/maintains it, then that is the new "Right Thing" for that application... and I realized the efficient progamming of the PDP days was a biproduct of necessity more than anything else. It's seldom needed with today's blazing hardware capabilities.
This isn't to say that many of today's programs are over-bloated, but just to reinforce the trade-off between small and easy to understand.
We really need more efficiant programming in OSes today. Look at the system requirements for OSes over the past few years. It's gone crazy. Check out the requirements for NT Workstation 4.0, Windows XP Pro and Windows 2000 Pro.
Doesn't something seem messed up? What have we really gained since 4.0 that causes 4x the memory, 3x the procecssor, and almost 15x the harddrive space? Is USB and Firewire support really that big? And have you ever tried to run XP on the min system? It doesn't work so well. I remember being able to tweak a system to run Windows 95 on a 386 with 5mb memory and a 45mb harddrive. It wasn't pretty but it could run. Today if you aren't going 1ghz+, then they want to leave you behind.
They are just using really fast hardware as an excuse for bloating the code.
Even Linux (redhat moreso) is guilty of this.
Remember when awesome games could fit on a handful of floppies? I think that could fly today if they tried. Look at the Demo scene. 64k can do alot of graphics. The most awesome games like Betrayal at Krondor were only a few floppies. Sure, if you have big hardware use it, but don't waste it. Programmers are just getting slack and including (literally) everything in the world, and not writing anything for themselves. They aren't looking to optimize stuff, just to kick it out and make money (obviously open source isn't guilty of the money or the fast kickout thing)...
Tibbon
tibbon.com
The current state of elf proccessors demands an astounding amount of system resources. When combined with dwarf co processor, it provides for unparalleled carnie access.
Looking through the comments here I see two main threads : (1) Squeezing out the last few overhead in a program leads to hard to understand / maintain program and thus is not worth the effort. (2) Whats the big deal anyway in this era of 100 GB disks and 2GHz processors?
While both these criticisms are valid, they miss the point. Firstly, it wasnt the objective of the author to squeeze the last few bytes out of that program to save resources. He was just putting his hard-earned knowledge to use. He was doing it because he could! This is the same motivation for people who climb mountains : because the mountain is there, and because they can climb it. Indeed, if the author were seriously looking into saving resources, he'd hardly be wasting his time on a trivial program, would he?
Secondly, one of the authors intentions was to demonstrate the limits to which austerity could be taken to. Certainly, this was a trivial program - but the same principles could be used to shrink larger non-trivial programs, and it those cases, the savings could possibly be larger. Of course, it those cases, the largest savings would come from a good optimizing compiler rather than crunching the headers together. More importantly, the author has exposed whole new ideas and lines of possibilities to programmers.
There is no such thing as luck. Luck is nothing but an absence of bad luck.
Beyond some point, the article is really just silliness, interesting or not. Below 512 bytes, your not going to save anything on any system. Ok, there are filesystems that compress things further for squeezing into flash memory and such, so maybe there are some marginally useful applications, but still the header overlapping is a bit much to be worth considering.
Some of the 4K demos I've seen written for ASM competitions completely blow my mind... check out this one, 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.
"Mind, as manifested by the capacity to make choices, is to some extent present in every electron." -Freeman Dyson
Maybe in theory. In practice, once your program gets too big to fit it all in your head at once, you're going to run out of the mental energy required to stay ahead of the C compiler (and remain bug-free).
If you've disassembled the output of a good optimizing compiler lately, you'd see that it usually produces pretty good code. Except for the inner loops of numerical algorithms, I doubt that anyone will consistently be able to produce code that is more than 25% faster than the C compiler.
The thing is, the compiler is able to spit out this code at thousands of lines per minute all day long. It doesn't get tired. The human programmer is going to get tired of the boredom, and will start creating higher level abstractions in assembly. He'll start using macros. He'll use a simplified parameter passing protocol so that he doesn't have to inline and hand-allocate the registers for every little subroutine call.
Before long, he's fallen behind, and the C code will run faster overall. And the C program will have taken less time to write, as well.
To be compared with the non-optimized gcc version at 3,998 bytes.
I wonder how small you can make a Windows EXE..
Beware: In C++, your friends can see your privates!
A dos .com file does not have a lower limit. .COM files are without headers, so having a realy tiny .com file is not very hard ;) It sais more about the crap turbo pascal puts in the .com file.. a .com file that returns correctly can just have one byte in it: 0xc3 (RET)
http://linuxassembly.org/asmutils.html
Check it out, download it and assemble it.
They create the smalles set of binaries for the basic linux tools that I have found and they employ a good portion of the stuff mentioned in this paper.
They make busybox look bloated by comparison.
Another neat trick is to use the ld options "-Wl, gc-sections" when linking a static binary -- it tries to weed out all the unused portions of the libraries it links against.
The last trick I usually use is to link against uClibc or dietlibc rather then glibc. Makes a noticeable difference. RedHat has been working on a program called "newlib" which is supposed to do the same thing as uClibc or dietlibc but better (for embedded stuff).
Just because a program or executable file is smaller, doesn't necessarily mean it's more efficient. For instance, some compiler optimizations actually produce larger executables. If you unroll a loop, it actually generates code for each iteration of the loop, but saves time because it's faster to keep going forward than to branch backwards to run through the code again.
Similarly, you can have inline functions that insert the inline function directly into the function calling it. Every function that calls an inline function would get a copy of it, which produces larger code, but saves a lot of time since it doesn't need to push the arguments on the stack, branch to the new function, and return with the value.
Finally, the biggest speed gains you can get are generally algorithmic in nature. You can do a bubble sort with just a few lines of code. It's a lot simpler code and smaller than the larger and more complicated quick sort or merge sort. I know which one I'd rather wait for with a million items to sort.
So remember, just because something is bigger, doesn't mean it's more bloated, and just because something is smaller doesn't mean it's faster or more efficient.
Looking for a computer support specialist for your small business? Check out
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.
42. Easy. What is 32 + 8 + 2?
You may say, yeah but how often will you printf more than 1024 bytes? Exactly,- practically never. Which is why this sort of crap is not showing up in testing and DOES show up when people are trying to crack it.