Faster 6502 decompressor & suggestions for possible format changes. about lzsa

[emmanuel-marty]

Thank you so much again for the kind words!

I quickly adapted your LZSA2 decompressor for the ACME assembler syntax and checked it in as decompress_faster_v2.asm, hopefully that's fine. A ~30% speed gain is HUGE and will be of interest to everyone, as it would let LZSA2 be used for tasks where only LZSA1 or LZ4 was usable before, such as real-time decompression of precalc data in demos.

I don't think the ~2% further gain is worth breaking compatibility, however, I have a couple of other changes (that provide a free, small ratio increase) that would also break compatibility, as well as more involved changes (not free in decompression time, but would provide a bigger ratio increase) that might all be all worth rolling into one incompatible format extension or new format altogether. In the meantime, I'm happy for you to use LZSA2 in HuC and you should definitely apply these changes locally, as you will control both ends. I don't have changes queued to shrink_block_v2.c and if I do, I'll be happy to be mindful of your local changes so that they merge cleanly.

I am however also happy to provide a window option to LZSA (once we worked that out with apultra, I'll know what you expect) as that would most likely result in a much larger speed boost and won't break anything for other CPUs.

Are you 'the' John Brandwood of Gryzor/Renegade/Ocean fame? If so, it's a big honor :-)

[jbrandwood]

Hi, I've continued to work on the LZSA2 decompressor, and have removed another 11 bytes of code at only a minimal cost in speed (it is still 30+% faster that Peter Ferrie's FAST code, but now it is only 3 bytes longer). The SMALL version is also smaller, now smaller than the current SMALL 6502 code, but it is still 25% faster than the FAST 6502 code.

I have also written an LZSA1 decompressor that helps to restore the difference between LZSA1 and LZSA2. ;-)

lzsa1 test with current SMALL code ... 172 bytes long, takes 2,909,491 cycles.
lzsa1 test with current FAST code ... 307 bytes long, takes 2,728,523 cycles.
lzsa1 test with new SMALL code ... 168 bytes long, takes 2,159,229 cycles.
lzsa1 test with new FAST code ... 205 bytes long, takes 1,545,259 cycles.

lzsa2 test with new FAST code ... 256 bytes long, takes 2,248,796 cycles.

I'm attaching both of the latest decompressors to this message.

Happy New Year!

P.S. Yes, I am "that" John Brandwood ... it's really nice that so many people still have fond memories of the work that I did so very, very long ago now! :-)

lzsa-6502-2019-12-31.zip

[emmanuel-marty]

Wow, thank you, that's fantastic work! I checked in the updated, smaller LZSA2 depacker and your new LZSA1 decompressor as well, quickly converted to ACME syntax. They work great on C64 as well, this should hopefully be useful to many.

Happy New Year as well!