Haxxoring the elf format for 1k/4k stuff

category: code [glöplog]
alrj: that sounds nice. tell us when it's done - so I can announce that properly :)
added on the 2009-05-29 16:22:27 by las las
@parapete/leblane/las: great work! i've dusted off my asm skills during the last few days and re-implemented your technique in order to better understand it. now, i've got one question: why are you recalculating the hashes and doing a linear search instead of using the bucket list? is it because otherwise you would still need the full symbol name?

thx, floe
added on the 2009-06-19 09:31:05 by floe floe
floe, yep that's right. the hash used in the elf format produces lots of collisions in the table even for a small amount of symbols, whereas the one we're using doesn't have the same problem in my experience.
actually now that i think about it there might have been other reasons for doing that too, i really don't remember as i haven't touched this code in a while. let us know if you come up with something more efficient!
Done !

Feel free to test The Byte Optimized Linker, for linux/x86_64.

This first release doesn't support much, not even archives files (.a).
Porting to 32bit x86 will require a lot of tedious work I really don't want to do because I don't have any x86 where I could test and use it.

Flow2 included :)
added on the 2009-08-08 21:16:57 by alrj alrj
Nice! It would be easy to make 7.2 completely integrated into the linker though:

objdump -t $TARGETOBJ | awk ' /\*UND\*/{print $4}' > symbollist

dumps the names of unresolved symbols in an .o file.

The rest of my stuff is here : http://parapete.untergrund.net/bdle/ if you fancied a look. It completely automates the process, however your tool has much better potential to crunch bytes since you can reorder sections and such.

Now go and write an intro!
It would be interresting to compare the respective sizes of the (compressed) binaries made using each technique: one with my --aligned --ccall, and one with the functions pointers.

It might be worth it for a 1k, but maybe not for a 4k. Lzma just loves repeating chunks :)
added on the 2009-08-08 23:30:19 by alrj alrj
like any compression technique ?
added on the 2009-08-09 11:22:21 by MsK` MsK`
@alrj: Thanks! I'm trying to link my latest linux 4k with your linker in order to compare sizes with the original version, but I'm having some trouble: uninitialized global variables (which should end in .bss in the final executable) become common symbols (SHN_COMMON) in the object files, and bold crashes when it finds them.

I made some small changes to the linker and now simple helloworld-ish examples work, and the intro links, but segfaults when I run it. I'm not familiar with the internals of the linking process, so I'm not sure if my modifications are anywhere near correct, but I can send a patch or setup a public git repository with my changes if you (or anyone else) want to review them :)
added on the 2009-08-13 20:13:29 by slack slack
@slack: Yup, I've recently discovered the SHN_COMMON bug when playing with C sources. The compiler puts uninitialized global variables into the SHN_COMMON pseudo-section instead of .bss, so that if another source file declares it, the linker should merge them. It means that the linker itself has to reserve additionnal room in .bss.

Some hackish temporary workaround would be to declare the global variables as "static" if they are only used in one file (→ no need for it to be COMMON), or assign it a value (→ goes to .data instead of .bss/COMMON).

I'll try to implement the support for SHN_COMMON this weekend.

Could you send your patch to amand.tihon@alrj.org ?
added on the 2009-08-15 08:57:33 by alrj alrj
On Mac OS X the smallest binary is 165 bytes according to: Crafting a Tiny Mach-O Executable by Amit Singh
added on the 2009-08-15 12:29:42 by neoneye neoneye
hi, bad news?, the .hash section seems to be osbolete.. Binutils patched his old .hash section few years ago (http://sourceware.org/ml/binutils/2006-06/msg00418.html) to get a more efficient structure, now most of linux distribution build their lib with this patched version of binutils. Binutils replaced .hash to .gnu.hash section and there is no element containing the number of symbols. I'm currentrly trying to get flow2 working on my archlinux 2.6.36
added on the 2010-12-23 17:04:54 by stfsux stfsux
Are you sure? This still works for me (The 45B one):
With up to date archlinux 2.6.36 kernel as well.
added on the 2010-12-23 21:43:22 by joooo joooo
I'm talking about parapete/atomicdeathwolf2's trick, loading a dynamic symbol via GOT/PLT.
added on the 2010-12-23 22:23:50 by stfsux stfsux
Oh it changed? Great :'( I don't really use linux any more except for embedded stuff so I probably won't do any more work on this, sorry.
erf... :[
Well, I found a way to get number of symbols, but sincerly It's a bit hard to patch flow2 with all technical contrains (registers,stack,etc.). Here is the tricks in C:
Code: if ( dyn->d_tag == DT_GNU_HASH ) { unsigned int *ptr = dyn->d_un.d_ptr; unsigned int *buckets = NULL; unsigned int *chains = NULL; unsigned int nbuckets , symidx , nsyms = 0, bitmsk; nbuckets = (unsigned int)*ptr; symidx = (unsigned int)ptr[1]; bitmsk = (unsigned int)ptr[2]; buckets = &ptr[4+bitmsk]; chains = &ptr[nbuckets+4+bitmsk]; unsigned int i; for ( i = 0; i < nbuckets ; i++ ) { if ( buckets[i] != 0 ) { unsigned int length = 1; unsigned int off; for ( off = buckets[i]-symidx; (chains[off]&1)==0; ++off ) ++length; nsyms += length; } } nsyms += symidx; }
added on the 2010-12-28 02:34:51 by stfsux stfsux
Damn it.... The cherry on the cake... OpenGL library (with last nvidia driver) isn't compiled with the new .gnu.hash... :')
SDL has .gnu.hash and OpenGL hasn't... We need to check the both section for each library... Nothing better for reduce executable size.
added on the 2010-12-29 06:12:37 by stfsux stfsux
@kernel_error: archlinux breaking compatibility once again. Why am I not even surprised?

Linking with --hash-style=gnu by default instead of --hash-style=both is pretty stupid, if you ask me.
added on the 2011-01-06 19:25:04 by alrj alrj
Currently I am packing my elf file and putting a execution on top of it to pipe it into gzip to /tmp and run it.
Are there any different compressions used i'm currently at work(no ssh) so no source here :(
Would like to see some other methods.
That's a classical packing usually used on linux, it's not really efficient for 1k. BTW lzma done a better compression than gzip.
added on the 2011-01-07 18:13:52 by stfsux stfsux
Dunno if this has been mentioned already but:

45 bytes ELF executable
More tiny ELF executables
added on the 2011-07-31 20:49:55 by p01 p01
Oh yes it has :p
added on the 2011-07-31 21:04:27 by p01 p01
Currently I am packing my elf file and putting a execution on top of it to pipe it into gzip to /tmp and run it.

Note that on some distributions /tmp is mounted with the noexec flag, so after uncompression you will not be able to start your main executable. Better use a different location like ~/

added on the 2011-07-31 22:32:49 by torus torus
And unpacking in ~/ saves you a few (4 if I can count) bytes ;)
added on the 2011-08-01 16:02:09 by flure flure