Explore executable code golf techniques for creating tiny binaries in constrained systems during this 42-minute conference talk from linux.conf.au. Dive into the challenges of rewriting algorithms and data structures to minimize binary size, and learn about alternatives to common executable packers like UPX. Discover the XLINK project, an open-source compressing linker implementing PAQ-based compression for older DOS embedded platforms and experimental 32-bit ELF targets. Gain insights into the PAQ compression algorithm, assembly code for decompression, and the advantages of applying compression during linking. Examine size-optimization tricks available at link-time, open research problems in executable compression, and potential future developments like individual function compression for patching existing binaries. Ideal for developers working on embedded or IoT applications with limited disk space and memory.
Overview
Syllabus
Intro
What is Code Golf?
But What is Executable Code Golf?
Example: Paint in 16 bytes
My Hobby: Making 256B Animations
Many Different Categories
State of the Art 1kB to 8kB (Windows v. Linux)
XLINK project (1) • Goal: Produce an open source link-time compressor non-Windows platforms
PAQ Compression Algorithm
Arithmetic Range Coding Properties
Context Modeling and Context Mixing
Sparse n-gram Context Modeling . For each bit to decode
Complete Decoder Specification • Entropy Segment data structure that describes decoder problem
Why does this work better than LZ based compression?
Anatomy of an Object / Library File
XLINK Implementation • Linux linker has many implementation concerns
Programming in MS-DOS
Cannot access enough memory for hash table
Need 32-bit registers for more accurate EC
Hash function too slow for use on 386
i386 PAQ Decompression Stub (255 bytes)
Why should I care about binary compression in 2019?
Future Directions
Taught by
linux.conf.au
