Show HN: Micro LZMA decoder (x86 assembly code golf) | Hacker News Reader

Show HN: Micro LZMA decoder (x86 assembly code golf)

github.com

56 pointsjpegqs10 comments

Cool! I like tiny encoders. I teach assembly programming at a university where one of the final assignments in the course is making a decoder for something similar to LZ77 in Cortex M3 (thumb 2) assembly. Best I could do is 15 instructions / 40 bytes found here: https://gist.github.com/ManDeJan/fd1c625e3540faa41d03736eb94... .

Impressive!

I love these tiny decoders, even if their use cases are limited. To me this is as much art as it is programming.

For Javascript I ran into these two recently:

Tiny LZW(ish) encoder/decoder. The decoder is 141 bytes: https://gist.github.com/mr5z/d3b653ae9b82bb8c4c2501a06f3931c...

RegPack, a non-standard encoding, but an awesome approach for small chunks (1-4KByte is optimal) of self contained compressed code, using regular expressions for decoding: https://github.com/Siorki/RegPack

Crinkler [1] is a popular compressor-linker for 1--8 KB demos and its decompressor (partially overlapping with a PE header) is probably around 1--200 bytes. Later efforts like oneKpaq [2] also have a comparable decompressor size.

If you don't mind a shameless plug and a slightly larger decompressor (about 500 bytes in JS) for better compression, my Roadroller [3] might fit the bill as well.

[1] https://github.com/runestubbe/Crinkler

[2] https://github.com/temisu/oneKpaq

[3] https://lifthrasiir.github.io/roadroller/

You can also find size-optimized LZSS decoders in 30+ different assembly languages here: http://www.deater.net/weave/vmwprod/asm/ll/ll.html

I wonder how this compares to the one in UPX.

The compression method in UPX is much simpler (therefore smaller and faster), but the last time I saw it was over 10 years ago, something may have changed. But LZMA should provide better compression.

I want to make the decoder small enough to be used in compressed executables. Where decompression performance doesn't matter because LZMA is far from fast decompression, and small code without inlining makes it worse (but bearable).

I looked at the latest version of UPX, they began to use LZMA, if this is considered an LZMA decoder:

https://github.com/upx/upx/blob/devel/src/stub/src/arch/amd6...

Then it takes ~2500 bytes, mine is ~500 (static version). But the decompression speed for larger code should be higher, as I noticed.

I have suggested them to look at my version, but I think UPX not much hardcore for that. Because I'm guessing decompression speed is more important to UPX than the extra 2kb.

I guess it would be a nice option, if I was trying to compress something that was already small, so the extra 2kb was significant.

Reply on news.ycombinator.com