Executable Code Golf: Making Tiny Binaries for Constrained Systems
Nathan Egge
https://2019.linux.conf.au/schedule/presentation/160/
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.
linux.conf.au is a conference about the Linux operating system, and all aspects of the thriving ecosystem of Free and Open Source Software that has grown up around it. Run since 1999, in a different Australian or New Zealand city each year, by a team of local volunteers, LCA invites more than 500 people to learn from the people who shape the future of Open Source. For more information on the conference see https://linux.conf.au/
#linux.conf.au #linux #foss #opensource
Видео Executable Code Golf: Making Tiny Binaries for Constrained Systems канала linux.conf.au
https://2019.linux.conf.au/schedule/presentation/160/
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.
linux.conf.au is a conference about the Linux operating system, and all aspects of the thriving ecosystem of Free and Open Source Software that has grown up around it. Run since 1999, in a different Australian or New Zealand city each year, by a team of local volunteers, LCA invites more than 500 people to learn from the people who shape the future of Open Source. For more information on the conference see https://linux.conf.au/
#linux.conf.au #linux #foss #opensource
Видео Executable Code Golf: Making Tiny Binaries for Constrained Systems канала linux.conf.au
Показать
Комментарии отсутствуют
Информация о видео
Другие видео канала
See what your computer is doing with Ftrace utilitiesCppCon 2018: Matt Godbolt “The Bits Between the Bits: How We Get to main()”SymbiFlow - The next generation FOSS FPGA toolchainUsing Static Binary Analysis To Find Vulnerabilities And Backdoors In FirmwareFPGA based mobile phone: Creating a truly open and trustable mobile communications deviceThe Linux File System...for humansA case study in incrementing a language's major version: PHPLinus Torvalds "Nothing better than C"But Mummy I don't want to use CUDA - Open source GPU compute"Behind the scenes of an ELK system" - Rafael Martinez Guerrero (LCA 2020)Firmware security, why it matters and how you can have itDonkey Car electronics designDe-mystifying interrupt balancing: irqbalanceRust for IOTFirst Exploit! Buffer Overflow with Shellcode - bin 0x0E"LumoSQL - updating SQLite for the modern age" - Dan Shearer (LCA 2020)Making C Less Dangerous in the Linux kernel"Privacy and Decentralisation with Multicast" - Brett Sheffield (LCA 2020)Preventing the IoT Dystopia with Copyleft