veyepar: Executable Code Golf: Making Tiny Binaries for Constrained Systems

Author(s):	Nathan Egge
Location	C2
Date	jan Thu 24	Days Raw Files
Start	16:45	First Raw Start	16:25
Duration	0:45:0	Offset	0:19:46
End	17:30	Last Raw End	17:29
Chapters	00:00 0:09:34 0:39:33
Total cuts_time	41 min.

https://2019.linux.conf.au/schedule/presentation/160/
raw-playlist raw-mp4-playlist encoded-files-playlist host public tweet mp4 svg png

assets release.pdf Executable_Code_Golf_Making_Tiny_Binaries_for_Constrained_Systems.json
logs
Admin: episode episode list cut list raw files day marks day marks day image_files

State:

Locked:

clear this to unlock

Locked by:

user/process that locked.

Start:

initially scheduled time from master, adjusted to match reality

Duration:

length in hh:mm:ss

Name:

Video Title (shows in video search results)

Emails:

email(s) of the presenter(s)

Released:

has someone authorised pubication

Normalise:

Channelcopy:

m=mono, 01=copy left to right, 10=right to left, 00=ignore.

Thumbnail:

filename.png

Description:

markdown

Ever had to rewrite an algorithm or data structure to keep your binary within a certain size?  Then you've played executable code golf!

For whole programs, a common practice is to use an executable packer like UPX.  However as your binary size gets smaller, the overhead of the decoding stub becomes significant and the compression efficiency of the LZ-based algorithms go down.  Better compression can be had using a compressing linker like Crinkler, but this closed source project only supports 32-bit Windows targets.  For Linux targets or 64-bit / non-x86 / obsolete hardware there is no good alternative.

The XLINK project is an open-source compressing linker implementing a PAQ-based compression algorithm similar to that in Crinkler.  It currently targets older DOS embedded platforms where both disk space and memory are limited and the notoriously long decode times of Crinkler are unacceptable.  An experimental 32-bit ELF target is in progress which will bring the same executable compression tools to Linux for use in embedded or IOT applications.

This talk will describe the PAQ compression algorithm in detail and give a short overview of the assembly code for decompression.  It will provide an overview of how XLINK works and is able to trade-off start-up time for compression by varying the decoder algorithm, including the use of multiple entropy segments and an alternate lower complexity hashing function.  You will learn why applying compression while linking outperforms even the best post-link-stage executable compressors and what extra size-optimization tricks are available at link-time.  Finally, we will look at the open research problems in executable compression and other future work like individual function compression for patching existing binaries.

Comment:

production notes