Smallest Possible ELF Executable? 460
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?'
Not good enough (Score:5, Funny)
Re:Not good enough (Score:5, Funny)
Re:Not good enough (Score:5, Funny)
Weird... I read that as "aibophobia", and thought it was the fear of electronic pets.
smallest elf execution (Score:5, Funny)
Re: smallest elf execution (Score:5, Funny)
> I just heard the news on slashdot -- Frodo Baggins, the smallest elf, was just executed! No other details were available.
In my own research I have discovered that the average Hobbit executable is barely half the size of the average Elf executable.
They're faster to run in a tight spot, too!
Re:smallest elf execution (Score:5, Funny)
Unfortunately, the article was incorrect then. Frodo is a hobbit. Furthermore, he is far from the smallest hobbit.
However, he was executed. By two elves. By way of trampling.
Does that mean we can assume that ELF binaries run on Hobbits [microprocessor.sscc.ru]?
(Sorry, I couldn't resist.)
auuugh! (Score:3, Funny)
Re:smallest elf execution (Score:5, Funny)
No. Trolls are completely different creatures from hobbits and elves.
Yes, yes. We all know Frodo was a hobbit. . . (Score:3, Funny)
Rumors of his being a fairy persist, however.
KFG
No law on repeat articles? (Score:4, Interesting)
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"
Correction (Score:3, Interesting)
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.
It doesn't save any disk space (Score:5, Insightful)
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.
Re:It doesn't save any disk space (Score:5, Informative)
Optimized Executables (Score:5, Informative)
There are also lots of interesting articles [linuxassembly.org] on linuxassembly.org [linuxassembly.org].
Andrew
Re:Optimized Executables (Score:5, Informative)
Re:Optimized Executables (Score:5, Informative)
Re:No law on repeat articles (An apology) (Score:2)
I read this article months ago, but it was not a Slashdot link. It was a link from another tech news source.
Turbo Pascal (Score:2, Interesting)
Re:Turbo Pascal (Score:5, Interesting)
Re:Turbo Pascal (Score:3, Interesting)
-dk
Re:Turbo Pascal (Score:3, Interesting)
try 256 bytes
Re:Turbo Pascal (Score:3, Funny)
4 bytes. Hmph.
Re:Turbo Pascal (Score:5, Informative)
Re:Turbo Pascal (Score:3, Informative)
The Amiga E language (sort of a Pascal+C+whatever like beast) compiler stuffed a hello world program in 80 bytes or so. Pure executable, no external libraries needed.
The author's list [fov120.com] of self-designed languages is definitely worth a look.
You disgust me... (Score:5, Funny)
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.
Re:You disgust me... (Score:3, Funny)
Small virus catcher (for DOS) (Score:5, Interesting)
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
Re:Small virus catcher (for DOS) (Score:2, Funny)
Of course this AV avoidance didn't work, as evidenced by the fact that viruses are now extinct and a footnote in the history of computer security.
Re:Small virus catcher (for DOS) (Score:4, Insightful)
Therefore, this file wouldn't be infected by like 99% of all COM infecting virii...
Re:Small virus catcher (for DOS) (Score:2)
good, bloat sucks (Score:3, Funny)
Re:good, bloat sucks (Score:3, Funny)
So don't expect me to do anything about it.
Excellent troll! (Score:4, Insightful)
Re:Excellent troll! (Score:5, Informative)
Re:Excellent troll! (Score:3, Funny)
Re:Excellent troll! (Score:3, Interesting)
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].
I feel guilty (Score:5, Funny)
Re:I feel guilty (Score:3, Funny)
Re:I feel guilty (Score:3, Funny)
Glibc is the thief! (Score:2, Informative)
Interesting topic... (Score:2)
Re:Interesting topic... (Score:3, Interesting)
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>
Re:Interesting topic... (Score:4, Insightful)
umm.... yeah? (Score:2, Insightful)
I remember this trick wehn I was learning x86 assembly. I wrote a hello world program in assembly. Assembled, it came to something like 35 bytes. In C++, it took over 10K.
Now, also see the statement that he is abandoning portability, because he's using linux-specific system calls. So, in a nutchell, C++ makes big code that's portable, assembly makes tiny code that's static.
Did I miss something or was this a long winded article about why assembly is better than C++?
Re:umm.... yeah? (Score:4, Interesting)
From the article, after the first try in asm:
Re:umm.... yeah? (Score:2)
Re:umm.... yeah? (Score:2, Troll)
Obviously you weren't using the ELF format then:
There is no getting around the fact that the 45th byte in the file, which specifies the number of entries in the program header table, needs to be non-zero, needs to be present, and needs to be in the 45th position from the start of the ELF header.
Maybe ELF is just too inefficient.
Smallest Posible Post (Score:5, Funny)
Re:Smallest Posible Post (Score:5, Funny)
ii (Score:2, Funny)
Bloat...now a worldwide concept! (Score:4, Funny)
67% of Americans are overweight. They can't account for most of the bites they use. By developing software that is just as bloated, the users feel good about themselves.
This kind of skinny programming is very insensitive to the fatass society we Americans live in! Hopefully the U.S. Congress hears of this soon, so that they may legislate this kind of software right off the face of the earth.
Masque, head of the Sensitive Programming Foundation*
[*A division of Maxtor Corporation; come check out our new 320GB drives, featuring room for tomorrow's applications...today.]
Windows exe (Score:4, Interesting)
Re:Windows exe (Score:2)
justification (Score:5, Funny)
The author's sanity, however, cannot.
Not bad... (Score:5, Interesting)
Even Shorter... (Score:3, Interesting)
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.
Re:Even Shorter... (Score:3, Informative)
No need to be smaller than 512 really... (Score:5, Interesting)
Re:No need to be smaller than 512 really... (Score:3, Informative)
Unless, of course, you're using ReiserFS with tail packing turned on.
Re:No need to be smaller than 512 really... (Score:5, Funny)
This should really be added to the Linux Gay Conspiracy.
Bigger is Sometimes Better (Score:5, Informative)
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.
Microsoft. Yes, Microsoft (Score:4, Insightful)
Finally found a web archive of the page I wanted: http://web.archive.org/web/20011031094552/www.rjh
A real pity that standards have slipped so much since then.
(I refuse to post anonymously even though I have mentioned Microsoft in a thread about Small Exes. So there
Efficiancy in OS programming needed (Score:5, Insightful)
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)...
Re:Efficiancy in OS programming needed (Score:2, Insightful)
Re:Efficiancy in OS programming needed (Score:5, Insightful)
Unfortunately my take on this situation is a bit more sinister. Your post mentions that NT 5.0 (Windows 2000 Pro) requires 64M of RAM, yet NT 5.1 (Windows XP) requires 128M of RAM. Why the twofold increase for a minor upgrade? Well, consider two things:
1. Windows XP was released during one of the slowest hardware sales slumps in PC history. All the big players were hoping to see XP spur sales. Not coincidentally, for many people XP required a new PC.
2. Microsoft can only stand to benefit from these PC sales in the form of OEM licenses.
Yes I'm cynical but I've always been of the belief that the bloat in XP is engineered, not the simple result of bad programming. To think that the project managers and marketing don't talk about these sorts of things is naive
Re:Efficiancy in OS programming needed (Score:4, Insightful)
Part of it also lies on the shoulders of developers. A lot of developers today are simply programmers that learned C in high school. They have little understanding of machine languages, assembly, or the CPU architectures they're coding for. They know just what the high-level languages look like and one or two ways of accomplishing their goal. What they need to know is how their software design decisions actually get implemented by the assembler and executed by the architecture. Memory efficiency never even crosses their mind. Who wants to pay for programmers that actually know their shit when they can just claim their product is so advanced it now requires four times the resources?
Perhaps this is another area in which OpenSource software can shine some day...
Embedded systems need efficiency (Score:4, Interesting)
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).
Several things (Score:3, Informative)
2) The increase in OS requirements is mainly due to an increase in software requirements as a whole. An OS is worthless if you can't run anything on it, so you need to set your requirements with software in mind. MS made this mistake with Windows 95. Yes, technically IT would run with 4MB of ram, but that wasn't enough to load anything else. XP's stated minimum isn't the actual minimum, but a practical one wheny ou account for applications.
3) As others have mentioned, compact code comes at the price of maintainability. Sure, I can write a program in 100% assembly, and then if I'm realyl good tweak the machine code to make sure it is as efficient as possable. Now try and maintain that. This is hard enough if it's a tiny app, but if it is something large like, say, Mozilla even the orignal programmer would find matenence very difficult and anyone else would find it almost impossable.
4) Along those line, portability requires that you code in a higher level language, and often that you make some changes that increase your code size. If you do everything in optimised assembly, well it's a one platform thing. I can gaurentee that you have to do a massive rewrite of an assembly Windows app if you want to make it run on x86 Linux just because of the API differences. If you are talking another hardware platform, then it's a total and complete rewrite.
5) Your 64k demo thing I'm assuming is refering to the now infamous Farbrausch demos. It is simply stunning what they can get done in 64k BUT it comes at a huge price. First there is the memory usage, look at your task manager sometime when one of those is running, they use like 80MB. Because of their tiny disk usage they can to decompress to memory. Second their compatibility is horrable, their newer one FR22 works properly on my sytstem at work, but not at home, the only big difference being at home a have a geForce 4 at work I have a GeForce 3. Finally, these thigns are only made possable by the "bloated" Windows framework with things like DirectX to simplfy low level access.
6) Most people see little point in trying to make things run well on a 386 when you can get an entire system running at over 1ghz for about $500.
3d Tube in 256 bytes (Score:5, Interesting)
256b... (Score:5, Interesting)
It's kind of a contest to see who can come up with the best 256 byte program.
That goes to show those C bigots (Score:2, Insightful)
Hand-tuned assembler is always faster/smaller/better than C code, except when it comes to portability.
And this just goes to show that fact again!
Re:That goes to show those C bigots (Score:5, Insightful)
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.
26 bytes (Score:4, Funny)
$ cat >a.pl
./a.pl
#!/usr/bin/perl
exit(42);
$ chmod +x a.pl
$
$ echo $?
42
$ ls -l a.pl
-rwxr-xr-x 1 bcrowell bcrowell 26 Oct 19 12:41 a.pl
Only takes up 26 bytes on my hard disk!
Smallest possible size (Score:2)
Re:Smallest possible size (Score:2)
nasm (Score:3, Informative)
32 byte run-length decompressor? (Score:2, Interesting)
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!!
Of course shortly thereafter... (Score:3, Funny)
linuxdoc.org
Chapter 11
Verse 35
proccessing in today's world (Score:5, Funny)
its not executable size that matters (Score:2, Interesting)
MenuetOS (Score:4, Interesting)
On bloatnesses (Score:4, Insightful)
However, using assembler this way is not the most optimal resource. Frankly this piece of code is only useful if you need some real tiny program and you are running out of space and speed. But, today, 99.99...% of tasks don't need it. The optimal way to use such tricks is to concentrate in tasks that really need "the best and fastest code ever". These are drivers and situations where speed's price costs gold. Usually this is done by injecting the necessary asm directives into C or any other language. Writing everything in pure Assembler is unpractical and the result may become harder to understand than the Rosetta Stone.
However the article is making a point - how unoptimised are the present compilers. For example, GCC is mostly C in C. It makes it highly portable, but, if anyone decided to repeat Turbo Pascal feat (most of its base code was Assembler), I know that binary code would shrink to the impossible. Right now we may not be feeling this drawback as bloatness still doesn't clog everything. In the future this situation may change if speed and reliability turn to higher priorities.
Some note for the bloat FUDders: This is not a reason for Linux distros being bloat. First learn to be rational on your needs and don't install everything in one box. Second, learn a little bit of administration, maybe some programming and kick that (mega_kernel) + (some_highly_featured_libs) + (several_unuseful_apps) out of your box. Then you will know that Linux can help fry eggs on your processor with lightning speed. Till then, keep the flame for yourself and read "Why I switched from Mac to Windows".
i love this (Score:2, Insightful)
while that isn't practical anymore these days, a LOT of code has become very sloppy. More than once have i stumbled over some college kids c app that was supposed to demonstrate linked lists, and instead, it was using one class with an array.
programming is an art, like acting. many try and are good enough for some purposes, but only a selected few are masters. sounds pretty damn philosophical, don't read too much into it
Could be used to make "true" smaller. (Score:3, Funny)
$ wc -c
9752
That's thousands of extra bytes - eek.
People are missing the point (Score:5, Insightful)
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.
4K Demos (Score:5, Interesting)
Here is Sanction's home page, it contains a couple more very impressive 4K demos.
Re:4K Demos (Score:3, Informative)
I wonder the speed and the effects some Doom III would have if it was written mainly in Asm...
Re:4K Demos (Score:3, Interesting)
What about the Visual Studio .NET compiler? (Score:5, Interesting)
To be compared with the non-optimized gcc version at 3,998 bytes.
I wonder how small you can make a Windows EXE..
Re:What about the Visual Studio .NET compiler? (Score:5, Interesting)
But I guess the
OT: Re:What about the Visual Studio .NET compiler? (Score:5, Informative)
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.
Any program can be written using one less byte (Score:3, Funny)
In fact, just apply this fact iteratively and you'll find that any program can be written in zero bytes!
asmutils does a good portion of this (Score:5, Informative)
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).
Small size != More efficient (Score:5, Insightful)
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.
Kids don't try this at home :-) (Score:5, Interesting)
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.
What about emacs executables ? (Score:3, Funny)
Re:Largest? (Score:2)
GW6SP2M.EXE 302.10MB
Favorite_ISO.zip.exe 700MB
Even smaller (Score:3, Interesting)
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:
wYes, a single character.
Re:Even smaller (Score:3, Funny)
w
Yes, a single character.
Actually, a zero-byte file will work as well. Granted, it doesn't do much. But at least it is guaranteed to be bug-free.
Re:I ask out of total ignorance... (Score:3, Informative)