A new data compressor called ZX0

[Einar Saukas]

I think you really found sweetpot.

Thanks!

[Einar Saukas]

Current "mega" decompressor is very wasteful. Here is 158/163 byte decompressor that is 10%/15% faster:

Good work!

There's only one problem I noticed: you cannot use "sra b" instead of "scf/rr b", because this will break matches with offset > 16K.

I know you mentioned that you tried to avoid self-modifying code, but 5% on top of everything else is not small.

Good point! The difference is high enough to deserve a separate SMC version.

The rest of performance improvements are coming from processing the first bit of Elias gamma inline

Good idea!

[introspec]

It didn't seem to be faster than dzx0_mega, although I didn't have time to test it extensively.

Well, 3-5% improvement in speed MAY be hard to notice to a naked eye. This is why we use a selection of testcases, and emulators with precise time measurement! Did you at least notice that it is also about 30 bytes shorter?

More seriously, I tried to let you know of this work, and I posted another version of the same decompressor in the "ZX7" thread on WoS: https://worldofspectrum.org/forums/disc ... ent_920979
However, you never replied, so I just assumed that you might have lost interest in further improvements to ZX7. The reason I was trying to flag it to you was mainly to replace "mega" decompressor with much shorter (and faster) one, because for my applications I was always mainly interested in fast decompression and because "mega" was just too bulky. Also, I implemented there several unusual speed optimizations, which I do not believe were used anywhere else at the time (nowadays I wrote many other decompressors using similar ideas so they are much more widespread).

Is this the unpublished ZX7 decompressor that you mentioned, or is there another even faster?

No, I actually wrote another, very different decompressor when I was trying to see what is the largest speed I can squeeze out of ZX7 without resorting to using LUTs and other horrible optimizations. What I came up with is 194 bytes long (50 bytes shorter than "mega" decompressor), and 9% faster:

Code: Select all

;
;  Speed-optimized ZX7 decompressor by spke (v.2 06-27/08/2019, 194 bytes)
;
;  Original ZX7 decompressors were written by Einar Saukas, Antonio Villena & Metalbrain
;
;  This decompressor was written from scratch and optimized for speed by spke
;  (it is 106 bytes longer and 17% faster than the 88 byte "Turbo" decompressor
;  and is 50 bytes shorter and 9% faster than the 244 byte "Mega" decompressor)
;
;  The decompression is done in the standard way:
;
;  ld hl,CompressedData
;  ld de,WhereToDecompress
;  call DecompressZX7
;
;  The decompressor only modifies AF, BC, DE and HL
;
;  Drop me an email if you have any comments/ideas/suggestions: [email protected]
;

		MACRO	GET_BIT
			add a : call z,ReloadByte
		ENDM

		MACRO	FASTER_GET_BIT
			add a : jp nz,1f : ld a,(hl) : inc hl : rla
1
		ENDM

@DecompressZX7:		ld a,#80 : jr CopyLiteral

ReloadByte0		ld a,(hl) : inc hl : rla : jr c,SetupMatch
			DUP 4
			ldi : add a : jr c,SetupMatch
			EDUP
			jr CopyLiteral

ReloadByte1		ld a,(hl) : inc hl : rla : jr c,EliasCode1
			add a : jr c,EliasCode01
			add a : jr c,EliasCode001
			add a : jr nc,LongerGamma

EliasCode0001		GET_BIT : rl c
EliasCode001		GET_BIT : rl c
EliasCode01		FASTER_GET_BIT : rl c
EliasCode1		; 1 is already in C
			inc c

ReadOffset:		ld e,(hl) : inc hl
			bit 7,e : jr z,CopyMatchC

LongOffset		DUP 3
			FASTER_GET_BIT : rl d
			EDUP
			GET_BIT : jp nc,CopyMatchC		; if C, then low bit of D would overflow and be zero. if NC, nothing needs to be done
			inc d : res 7,e

CopyMatchC		scf

CopyMatch		ex (sp),hl
	 		push hl : sbc hl,de : pop de		; 11+15+10=36t
			ldi : ldir : pop hl

MainLoop:		add a : jr z,ReloadByte0 : jr c,SetupMatch
CopyLiteral		ldi
			add a : jr z,ReloadByte0 : jr nc,CopyLiteral


SetupMatch:		push de : ld bc,1 : ld d,b

			add a : jr z,ReloadByte1 : jr c,EliasCode1
			FASTER_GET_BIT : jr c,EliasCode01
			GET_BIT : jr c,EliasCode001
			GET_BIT : jr c,EliasCode0001

LongerGamma		ld d,4-1
ReadExponent		inc d : GET_BIT : jr nc,ReadExponent

ReadGammaCode		GET_BIT : rl c : rl b : jr c,EndOfData
			dec d : jr nz,ReadGammaCode
			inc bc : jr ReadOffset

EndOfData:		pop de ; : ret				; RET is not needed, as ReloadBytes follows

;
;  pretty usual getbit for mixed datastreams

ReloadByte:		ld a,(hl) : inc hl
			rla : ret

In fact, the idea of partly unrolled Elias gamma processing was first conceived in this decompressor. I felt a little bad that such a beauty goes to waste, as ZX7 is getting very dated, so I am very happy to see that the same idea now works in ZX0, and does really well too.

[introspec]

There's only one problem I noticed: you cannot use "sra b" instead of "scf/rr b", because this will break matches with offset > 16K.

Arrgh, it kind of passed my mind, but I still tried and because it worked on the small subset of testcases, I just accepted it. Sorry.

I'll think some more about this decompressor, it still has several places which annoy me, so I am guessing there is a little bit of optimization still left in it. But all the major improvements should be in place now.

[Einar Saukas]

It didn't seem to be faster than dzx0_mega, although I didn't have time to test it extensively.

Well, 3-5% improvement in speed MAY be hard to notice to a naked eye. This is why we use a selection of testcases, and emulators with precise time measurement! Did you at least notice that it is also about 30 bytes shorter?

This is not what I meant!

I noticed that "dzx7_lom_v1" (from this page) was smaller and faster than "dzx7_mega". But "dzx7_lom_v1" didn't seem to be faster than "dzx0_mega".

More seriously, I tried to let you know of this work, and I posted another version of the same decompressor in the "ZX7" thread on WoS: https://worldofspectrum.org/forums/disc ... ent_920979
However, you never replied, so I just assumed that you might have lost interest in further improvements to ZX7.

I didn't notice your post, sorry! At this time I wasn't paying much attention to WoS forum anymore, then afterwards my forum notifications were blocked so I couldn't keep track of posts anymore.

I will update ZX7 with your new version. Do you prefer to be credited as "introspec", "spke", or something else?

[introspec]

I noticed that "dzx7_lom_v1" (from this page) was smaller and faster than "dzx7_mega". But "dzx7_lom_v1" didn't seem to be faster than "dzx0_mega".

Sorry, yes, that may well be the case.

I didn't notice your post, sorry! At this time I wasn't paying much attention to WoS forum anymore, then afterwards my forum notifications were blocked so I couldn't keep track of posts anymore.

Yes, I kind of missed most of the drama at WoS because I hated the new forum engine and did not trust the management. So I did not visit them often, but I read about your battle about ZXDB very recently and understand you very well.

I will update ZX7 with your new version. Do you prefer to be credited as "introspec", "spke", or something else?

Ideally, I would prefer to have my comments kept intact (and they say "spke"). Of course, you are welcome to add any additional comments there. I usually release my ZX Spectrum sources under ZLIB license, but if you feel strongly about it, we can agree on something else.

In fact, since this decompressor has been written over a year ago, there may be few recent tricks that are not implemented in it. Give me a few days and I'll go through it again, to save you some future updating.

[bobs]

Does the ZX0 decompressor (I’m testing the ‘mega’ version at the moment) provide a register-pair or address which can be read to find the number of bytes that have been written during the decompression, or alternatively the final address written to?

[Einar Saukas]

Does the ZX0 decompressor (I’m testing the ‘mega’ version at the moment) provide a register-pair or address which can be read to find the number of bytes that have been written during the decompression, or alternatively the final address written to?

After execution, use DEC DE to get the final address written to. Also use DEC HL to get the final address read from.

This will work for all 3 ZX1 decompressors (standard, mega, turbo).

[bobs]

Does the ZX0 decompressor (I’m testing the ‘mega’ version at the moment) provide a register-pair or address which can be read to find the number of bytes that have been written during the decompression, or alternatively the final address written to?

After execution, use DEC DE to get the final address written to. Also use DEC HL to get the final address read from.

This will work for all 3 ZX1 decompressors (standard, mega, turbo).

Many thanks

[Einar Saukas]

Yes, I kind of missed most of the drama at WoS because I hated the new forum engine and did not trust the management. So I did not visit them often, but I read about your battle about ZXDB very recently and understand you very well.

Curiously WoS is still using ZXDB

Ideally, I would prefer to have my comments kept intact (and they say "spke"). Of course, you are welcome to add any additional comments there. I usually release my ZX Spectrum sources under ZLIB license, but if you feel strongly about it, we can agree on something else.

I usually release Spectrum sources (including ZX1 decompressors) under an informal "please give proper credit" license. It's essentially the same, but apparently too many people don't understand formal licenses and are afraid of them.

However I use formal licenses (usually BSD3 or Apache2) in modern platform tools (including the ZX1 compressor) because the possibility of abuse is much higher in these cases.

In fact, since this decompressor has been written over a year ago, there may be few recent tricks that are not implemented in it. Give me a few days and I'll go through it again, to save you some future updating.

Thanks!

In the meantime, I'm finishing ZX1. Then I will need your help to improve it too

[introspec]

I usually release my ZX Spectrum sources under ZLIB license, but if you feel strongly about it, we can agree on something else.

I usually release Spectrum sources (including ZX1 decompressors) under an informal "please give proper credit" license. It's essentially the same, but apparently too many people don't understand formal licenses and are afraid of them.

However I use formal licenses (usually BSD3 or Apache2) in modern platform tools (including the ZX1 compressor) because the possibility of abuse is much higher in these cases.

I used to have no explicit licenses, but then I discovered that having no license also puts quite a few people off. Some of them even explained to me why they do so and I found their arguments compelling. So these days I include a reasonably "big name" license, so that anti-license people can understand what is going on and pro-license people are also satisfied.

As for "attribution", well, I am in two minds about it. Personally, I tend to write fairly detailed summaries about all tools and libraries that I used in my software. However, when someone makes me do it (like you do in your licenses), I tend to feel a bit put off (because it seems I am being forced to do what I'd do anyway). At the same time, most people just not care. Suppose I use license with an attribution clause and someone does not honour it. Frankly, I am not very likely to chase it, so it will just make me feel annoyed. Instead, I tend to go for non-attribution licenses, as with them I do not build up any substantial expectations and any attribution I get feels like a nice bonus.

In the meantime, I'm finishing ZX1. Then I will need your help to improve it too

I will be glad, I think decompression of the interlaced gamma can be done much more elegantly. This means ~ZX7-size size-optimized decompressor and a potential for further improvement in decompression speed. I understand your point about the extra byte, but I am sure you will save more with the decompressor size (even if you assume that there are 10 files to decompress instead of one).

[introspec]

In the meantime, I'm finishing ZX1. Then I will need your help to improve it too

BTW, could you please consider using "inverted" interlaced Elias code in ZX1?
I.e. instead of codes of the form 1, 0x1, 0x0x1, etc, use codes of the form 0, 1x0, 1x1x0, etc

I believe such code can be decompressed slightly faster (and I don't think it would affect size-optimized version, right?)

[Einar Saukas]

I understand your point about the extra byte, but I am sure you will save more with the decompressor size (even if you assume that there are 10 files to decompress instead of one).

Good point!

My idea was getting maximum compression in ZX0 without any concessions, then making ZX1 as a simplified version that would sacrifice some compression to make it much smaller and faster (interlaced Elias gamma, different offsets, etc). But you are right, it's not worth it to have 2 different versions when the main difference is interlaced Elias gamma that only costs 1 byte.

OK, I will apply to ZX0 the same interlaced Elias gamma changes that I made for ZX1. This will be ZX0 version 1.1

I'm still going to publish ZX1 later, but now it won't be so much different from ZX0 anymore.

[Einar Saukas]

OK, I just released ZX0 version 1.1. This change costs 1 extra byte per compressed file, but the new decompressor routine is now much smaller and faster. So it was worth it!

These are the updated results:

Code: Select all

              ZX7       ZX0-q   Exomizer3    ZX0

Calgary      117658    116693     95997    100001
Canterbury    32268     30730     26365     26342
Graphics     172140    164722    163915    163677
Music         66692     61947     58586     58412
Misc         265121    249648    245434    244262

TOTAL:       653879    623663    590297    592694

As you can see, ZX0 total compressed size increased a little but the difference is negligible. This didn't change any of the previous conclusions.

This change breaks compatibility with the previous version. Thus don't forget to download all programs and assembly routines again!

Many thanks to [mention]introspec[/mention] for insisting to use interlaced Elias Gamma Code in ZX0, instead of (just) ZX1 as I originally intended. I have also incorporated some of his previous otimization ideas into the new "turbo" and "mega" versions, so he's now credited in these routines and in the documentation.

[Einar Saukas]

[mention]introspec[/mention]: My apologies, but I was already finishing the new ZX0 format (with your suggested changes) when you sent your Pull Request for a faster decompressor in the old format a couple hours ago. Therefore it doesn't fit anymore. Could you please update your Pull Request? Thanks!

Some tech notes about the latest release:

Both "standard" and "turbo" versions look OK now. The "standard" version is only 70 bytes (same size as ZX7 standard, same speed as ZX7 mega). The "turbo" version is 130 bytes and 20% faster, so that's a good tradeoff.

However ZX0 definitely needs a better "mega" version. My current implementation is terrible! The only idea I had was to I used a "brute force" approach to unroll all routines. The result I got was 562 bytes and only 25% faster than "standard". It was not worth it. If [mention]introspec[/mention] can provide a better version, I will gladly replace it! I won't even bother about alternate registers or self-modifying code anymore.

[introspec]

@introspec: My apologies, but I was already finishing the new ZX0 format (with your suggested changes) when you sent your Pull Request for a faster decompressor in the old format a couple hours ago. Therefore it doesn't fit anymore. Could you please update your Pull Request? Thanks!

Some tech notes about the latest release:

Both "standard" and "turbo" versions look OK now. The "standard" version is only 70 bytes (same size as ZX7 standard, same speed as ZX7 mega). The "turbo" version is 130 bytes and 20% faster, so that's a good tradeoff.

However ZX0 definitely needs a better "mega" version. My current implementation is terrible! The only idea I had was to I used a "brute force" approach to unroll all routines. The result I got was 562 bytes and only 25% faster than "standard". It was not worth it. If @introspec can provide a better version, I will gladly replace it! I won't even bother about alternate registers or self-modifying code anymore.

No worries, I'll do it once I find a bit of time. I need ZX0 with a fast decompressor for my own work, so there can be no better motivation. And I am 100% sure 500 bytes are not needed

Have you considered using reversed bits in the gamma code? It can speed up the decompression quite noticeably, although I cannot say immediately if you will still be able to fit decompressor into 70 bytes.

[Einar Saukas]

Have you considered using reversed bits in the gamma code? It can speed up the decompression quite noticeably, although I cannot say immediately if you will still be able to fit decompressor into 70 bytes.

This is a great idea for ZX1! I will change it ASAP.

Although this change doesn't work so well in ZX0, because it has an instruction "rr b" that needs flag C set. If we invert Elias Gamma Code, this will make the "standard" version a little bit slower and larger. Also if you unroll the code like I did in the "mega" version (although my implementation was overkill) then this change will also make it slightly slower and larger.

However the "backwards" variant of ZX0 that doesn't depend on flag C, so it doesn't have this disadvantage. Therefore that's a good idea for ZX0 backwards only. We are already storing offsets differently between forward and backward versions, so there's already precedent for differences between them

I will release ZX0 version 1.2 later today. Thanks again!!!

[introspec]

Have you considered using reversed bits in the gamma code? It can speed up the decompression quite noticeably, although I cannot say immediately if you will still be able to fit decompressor into 70 bytes.

This is a great idea for ZX1! I will change it ASAP.

Although this change doesn't work so well in ZX0, because it has an instruction "rr b" that needs flag C set. If we invert Elias Gamma Code, this will make the "standard" version a little bit slower and larger. Also if you unroll the code like I did in the "mega" version (although my implementation was overkill) then this change will also make it slightly slower and larger.

Einas, can you maybe build a private version of ZX1 with the reversed bits in the gamma code for the forward compressor? My current fast decompressor does not depend on the flag C in the same way as the standard decompressor, but the gamma reader seems like it would benefit from the reverse bits convention. However, my case for is purely statistical, i.e. I know it'll work faster, but I do not know how much faster (and am not sure if it would be enough to justify slowing the standard decompressor down). With such an experimental compressor build I can test my idea and report whether it's worth it.

I currently have a draft version of the decompressor that is 2.5-3% faster than "turbo" and is 156 bytes long. I don't see any size-efficient ways of speeding it up at the moment, but I'll sit on it for a few more days, maybe I will see something I am not seeing now. I don't think it can be made faster than "mega" this time around ...but it may still be a decent compromize for many situations.

[Einar Saukas]

can you maybe build a private version of ZX1 with the reversed bits in the gamma code for the forward compressor?

I uploaded a pre-release version here:

https://github.com/einar-saukas/ZX1

It's basically the same as ZX0, except offsets don't use Elias Gamma Coding. This change reduced compression by about 3% but made it about 15% faster.

I had originally planned ZX1 to be a much smaller faster version of ZX0. However, after [mention]introspec[/mention] convinced me to use interlaced Elias Gamma Code in ZX0 too, there isn't so much difference between ZX0 and ZX1 anymore...

I have considered other simplifications for ZX1 but they are simply not worth it. In particular, limiting offset and/or length to a single byte sacrifices compression too much, without making much difference in decompressor size or speed. If anyone has other suggestions to be considered, they are welcome!

[introspec]

can you maybe build a private version of ZX1 with the reversed bits in the gamma code for the forward compressor?

I uploaded a pre-release version here:

https://github.com/einar-saukas/ZX1

Sorry, I made a misprint, I meant ZX0 with the inverted bits. It is just much quicker for you to build it, rather than for me to fiddle with the compiler setup. I'll do ZX1 decompressor too, of course, as I promised, but I want to finalize ZX0 decompressors first.

[Joefish]

I still think you'll get savings if you can save and re-use one (or two, depending on encoding) previous back-reference after using a new back-reference; not just recovering the last one after using a literal.
You could also experiment with re-proportioning the Elias-Gamma encoding so that it has more data bits to each extension bit.

I suppose in reality you have to trade-off savings of a few bits here and there in the packed data against the extra bytes of the decoder program itself...

[Einar Saukas]

Sorry, I made a misprint, I meant ZX0 with the inverted bits.

No problem, it's here.

[introspec]

No problem, it's here.

Thank you very much. I had a quick go at it, and it seems that while it helps in some ways, it also makes things harder in other ways. Specifically, dzx0_standard.asm becomes 1 byte larger, and a bit slower, but the slowdown is so small (fractions of a percent) that you can just ignore it.
dzx0_turbo.asm benefits the most - it can be made 10 bytes shorter and simultaneously 1-2% faster.
My speed-optimized decompressor at the moment is about the same as it was before, so no clear benefits.
Overall, inverting the bits does not help as much as I hoped it would (except for the "turbo" decompressor, where it really makes things better).

[Einar Saukas]

I still think you'll get savings if you can save and re-use one (or two, depending on encoding) previous back-reference after using a new back-reference; not just recovering the last one after using a literal.

I vaguely remember reading about a Spectrum compressor that worked exactly as you described. Does anybody know which one?

I may try it later, but this will require implementing a fairly different compressor and decompressor. This is not an easy change.

You could also experiment with re-proportioning the Elias-Gamma encoding so that it has more data bits to each extension bit.

I had already tried this idea. It didn't help.

It's not worth it to spend more bits to represent smaller more frequent values, in order to save bits when representing larger less frequent values.

I suppose in reality you have to trade-off savings of a few bits here and there in the packed data against the extra bytes of the decoder program itself...

Exactly.

[Einar Saukas]

No problem, it's here.

Thank you very much. I had a quick go at it, and it seems that while it helps in some ways, it also makes things harder in other ways. Specifically, dzx0_standard.asm becomes 1 byte larger, and a bit slower, but the slowdown is so small (fractions of a percent) that you can just ignore it.
dzx0_turbo.asm benefits the most - it can be made 10 bytes shorter and simultaneously 1-2% faster.
My speed-optimized decompressor at the moment is about the same as it was before, so no clear benefits.
Overall, inverting the bits does not help as much as I hoped it would (except for the "turbo" decompressor, where it really makes things better).

Agreed! This was exactly my conclusion.

Although inverted Elias Gamma Code was perfect for ZX1, that doesn't have these disadvantages.