If it's a separate fork on git, it should be feasible to see how far behind it is and if/what has changed in the original code base compared to the fork. It's a much better solution for the user (where the user in this case is inevitably a developer of some sort)Bedazzle wrote: ↑Fri Jul 23, 2021 11:01 pmI hardly imagine user that uses sourcesEinar Saukas wrote: ↑Mon Jul 19, 2021 5:06 pm If you were an Amstrad CPC user, what would you prefer?
And I'm not sure that different sources of data will be in sync when updated from time to time.
A new data compressor called ZX0
Re: A new data compressor called ZX0
Re: A new data compressor called ZX0
Yes, I didn't go through all the code in deep, I just took a quick look, but I agree with you that a CPC optimized version should be done by a CPC coder : )introspec wrote: ↑Mon Jul 19, 2021 4:32 pmAh, so you must be Rhino^BG? I now understand where you coming from (I've heard CPC people measuring execution time in NOPs, but never paid enough attention as to why). But it is an interesting question. The thing is, both turbo and fast decompressors are heavily optimized for speed under the assumption of standard Z80 timings. I run tests in a specially instrumented emulator and I can see differences in execution times even on the order of single t-states. Almost every structural decision in the decompressor was made with consideration of the resulting efficiency on several "average" files, which I selected from a corpus of mine. Thus, given how different your Z80 timings are, I think you would benefit from re-optimizing everything fully, not just patching a decompressor here and there.Rhino wrote: ↑Fri Jul 16, 2021 5:25 pmI forgot to mention that I am an Amstrad CPC user, where the memory snowing effect makes jp not faster than jr in any case, so that "jp" turbo version is not the most optimal for CPC.
Maybe it would be worthwhile to specify the platform from a constant in the code so that it fits better in each case?
I am not volunteering to do this because my work on decompressors is progressing very slowly at present, due to my other responsibilities. In addition, I do not have an emulator with CPC timings, and I do not have much immediate intuition with regard of what would and what would not well. This is probably a kind of the project that should be undertaken by someone with CPC background, like yourself.
Until that happens maybe a simple warning in the comments like "This code is not optimized for CPC", could be useful imo.
Regards
Re: A new data compressor called ZX0
Isn't that the default? I really don't see the point.
http://iki.fi/sol - my schtuphh
https://github.com/jarikomppa/speccy/ - 48k speccy dev
https://github.com/jarikomppa/specnext/ - specnext dev
https://github.com/jarikomppa/speccy/ - 48k speccy dev
https://github.com/jarikomppa/specnext/ - specnext dev
Re: A new data compressor called ZX0
Well, in my opinion it all depends on the audience you are targeting, if you want to target the general community of z80 coders you should keep in mind that a % of them are CPC users, and that for them, even the current data in the source comments about the speed of the code (comparing some versions with others) is probably not correct. I think a comment in that sense helps to put the code in context since a CPC programmer can get to this code from many different ways, and you can not assume that everyone will know in advance that it is not a code optimized for his machine.
On the other hand, that message might also help to find a CPC programmer who will make the optimized version.
Regards
Re: A new data compressor called ZX0
I'm thinking about integrating ZX0 into my toolchain. Most of my tooling is in Python. I could just call out from Python to the ZX0 binary but I'd like to have ZX0 as a Python module instead. This would be much cleaner - it would just output a Python array instead of me having to write my data to temporary file, compress that to another temporary file then read that back in to Python for further processing.. and finally clean up the temporary files. I might be able to do some fancy piping to avoid the temporary file shenanigans, but still..
Before I have a crack at doing this.. I'm just wondering if anyone else has done it or fancies doing it? You know.. just to save me some time/hassle
Edit: I would of course be happy for any code I write to be included in the main ZX0 repo. Does the license allow me to do this and still distribute the Python module with my toolchain?
Before I have a crack at doing this.. I'm just wondering if anyone else has done it or fancies doing it? You know.. just to save me some time/hassle
Edit: I would of course be happy for any code I write to be included in the main ZX0 repo. Does the license allow me to do this and still distribute the Python module with my toolchain?
- Einar Saukas
- Bugaboo
- Posts: 3215
- Joined: Wed Nov 15, 2017 2:48 pm
- Einar Saukas
- Bugaboo
- Posts: 3215
- Joined: Wed Nov 15, 2017 2:48 pm
Re: A new data compressor called ZX0
If you port it to Python, it will work better if you made it available on your own repository, then I will add a link to it from mine. This way, you can freely update your version whenever you want, and everyone else will easily find it anyway.
Re: A new data compressor called ZX0
Ok. I'll take a look at doing this.. and if it works out I'll host it somewhere and share a link back in here.
- Einar Saukas
- Bugaboo
- Posts: 3215
- Joined: Wed Nov 15, 2017 2:48 pm
Re: A new data compressor called ZX0
Hi Einar!
Congratulations on this new compressor, it's amazing!!
I took a look at the standard decompressors a couple of hours ago (very good both, especially forwards variant), and I haven't found any optimization, which indicates that the code is already very mature.
However, there's something I think can be done to gain three bytes (no time gain) at the "cost" of changing the order of the bits as long as it allows to maintain the deterministic of bit read system:
Congratulations on this new compressor, it's amazing!!
I took a look at the standard decompressors a couple of hours ago (very good both, especially forwards variant), and I haven't found any optimization, which indicates that the code is already very mature.
However, there's something I think can be done to gain three bytes (no time gain) at the "cost" of changing the order of the bits as long as it allows to maintain the deterministic of bit read system:
Code: Select all
; -----------------------------------------------------------------------------
; ZX0 decoder by Einar Saukas
; "Standard" version (66 bytes only)
; -----------------------------------------------------------------------------
; Parameters:
; HL: source address (compressed data)
; DE: destination address (decompressing)
; -----------------------------------------------------------------------------
dzx0_standard:
ld bc, $ffff ; preserve default offset 1
push bc
inc bc
ld a, $80
dzx0s_literals:
call dzx0s_elias ; obtain length
ldir ; copy literals
call dzx0s_elias ; obtain new offset or length for last offset
add a, a ; copy from last offset or new offset?
jr c, dzx0s_new_offset
dzx0s_copy:
......
......
dzx0s_new_offset:
ex af, af'
pop af ; discard last offset
xor a ; adjust for negative offset
sub c
ret z ; check end marker
ld b, a
ex af, af'
ld c, (hl) ; obtain offset LSB
inc hl
rr b ; last offset bit becomes first length bit
rr c
push bc ; preserve new offset
ld bc, 1 ; obtain length
call nc, dzx0s_elias_backtrack
inc bc
jr dzx0s_copy
Code: Select all
; -----------------------------------------------------------------------------
; ZX0 decoder by Einar Saukas
; "Standard" version (66 bytes only) - BACKWARDS VARIANT
; -----------------------------------------------------------------------------
; Parameters:
; HL last source address (compressed data)
; DE last destination address (decompressing)
; -----------------------------------------------------------------------------
dzx0_standard_back:
ld bc, 1 ; preserve default offset 1
push bc
dec c
ld a, &80
dzx0sb_literals:
call dzx0sb_elias ; obtain length
lddr ; copy literals
call dzx0sb_elias ; obtain new offset or length for last offset
add a, a ; copy from last offset or new offset?
jr c, dzx0sb_new_offset
dzx0sb_copy:
......
......
dzx0sb_new_offset:
inc sp ; discard last offset
inc sp
dec b
ret z ; check end marker
dec c ; adjust for positive offset
ld b, c
ld c, (hl) ; obtain offset LSB
dec hl
srl b ; last offset bit becomes first length bit
rr c
inc bc
push bc ; preserve new offset
ld bc, 1 ; obtain length
call c, dzx0sb_elias_backtrack
inc bc
jr dzx0sb_copy
Re: A new data compressor called ZX0
I can't edit my previous message so....
My mistake I've already realized that it does not work, but i'll keep looking for some optimization
Congratulations, again.
My mistake I've already realized that it does not work, but i'll keep looking for some optimization
Congratulations, again.
- Einar Saukas
- Bugaboo
- Posts: 3215
- Joined: Wed Nov 15, 2017 2:48 pm
Re: A new data compressor called ZX0
Thank you!!!
Thanks
I'm aware of your numerous contributions for other compressors (you were even mentioned in ZX7 credits), therefore I really appreciate your efforts trying to improve ZX0 too!
Re: A new data compressor called ZX0
Well… I spent a couple of hours mechanically porting the c code to Python, line by line. The resulting code looks pretty horrible. Then spent another few hours making it work, using very small test files and comparing results between the two versions.
Once that was working I tried a “proper” test with a 16k binary file of compiled Z80 code and data. The compiled c version took 14 seconds to compress, and the Python version took… 13 minutes! But at least two two results were identical!
So.. horrible code that runs embarrassingly slowly by about a factor of 60. It’s a good start but now comes the hard part of trying to improve on those two things. Still, at least the only way is up, baby!
Once that was working I tried a “proper” test with a 16k binary file of compiled Z80 code and data. The compiled c version took 14 seconds to compress, and the Python version took… 13 minutes! But at least two two results were identical!
So.. horrible code that runs embarrassingly slowly by about a factor of 60. It’s a good start but now comes the hard part of trying to improve on those two things. Still, at least the only way is up, baby!
Re: A new data compressor called ZX0
With all of you, an incredible optimization of..... 8 T-cycles (it seems that no more can be achieved )
Code: Select all
; -----------------------------------------------------------------------------
; ZX0 decoder by Einar Saukas
; "Standard" version (69 bytes only) - BACKWARDS VARIANT
; -----------------------------------------------------------------------------
; Parameters:
; HL last source address (compressed data)
; DE last destination address (decompressing)
; -----------------------------------------------------------------------------
dzx0_standard_back:
ld a, $80
ld bc, 1 ; preserve default offset 1
push bc
dzx0sb_literals:
call dzx0sb_elias ; obtain length
lddr ; copy literals
inc c
add a, a ; copy from last offset or new offset?
jr c, dzx0sb_new_offset
call dzx0sb_elias ; obtain length
dzx0sb_copy:
ex (sp), hl ; preserve source, restore offset
push hl ; preserve offset
add hl, de ; calculate destination - offset
lddr ; copy from offset
inc c
pop hl ; restore offset
ex (sp), hl ; preserve offset, restore source
add a, a ; copy from literals or new offset?
jr nc, dzx0sb_literals
dzx0sb_new_offset:
call dzx0sb_elias ; obtain offset MSB
inc sp ; discard last offset
inc sp
dec b
ret z ; check end marker
dec c ; adjust for positive offset
ld b, c
ld c, (hl) ; obtain offset LSB
dec hl
srl b ; last offset bit becomes first length bit
rr c
inc bc
push bc ; preserve new offset
ld bc, 1 ; obtain length
call c, dzx0sb_elias_backtrack
inc bc
jr dzx0sb_copy
dzx0sb_elias:
add a, a ; inverted interlaced Elias gamma coding
jr nz, dzx0sb_elias_skip
ld a, (hl) ; load another group of 8 bits
dec hl
rla
dzx0sb_elias_skip:
ret nc
dzx0sb_elias_backtrack:
add a, a
rl c
rl b
jr dzx0sb_elias
Re: A new data compressor called ZX0
Great work [mention]Einar Saukas[/mention] it's much appreciated!
FYI I"ve added support for ZX0 to Gfx2Next. It's a slightly modified version to support compression from a buffer.
FYI I"ve added support for ZX0 to Gfx2Next. It's a slightly modified version to support compression from a buffer.
Re: A new data compressor called ZX0
Not yet. I've improved it a lot (now 6 minutes instead of 13 for that 16k test file) but it's still too slow to be useful and the code still looks like a cat danced on my keyboard while I was typing.
If you want the code for evaluation purposes or because you are a Python optimisation guru and think you can improve it then DM me and I'll happily send you a copy. Otherwise.. I'll keep working on it until either I'm happy or I can't make any further improvements - then I'll release it.
If you want the code for evaluation purposes or because you are a Python optimisation guru and think you can improve it then DM me and I'll happily send you a copy. Otherwise.. I'll keep working on it until either I'm happy or I can't make any further improvements - then I'll release it.
- Einar Saukas
- Bugaboo
- Posts: 3215
- Joined: Wed Nov 15, 2017 2:48 pm
Re: A new data compressor called ZX0
I'm updating the ZX0 repository with this optimization now. Thank you!!!
- Einar Saukas
- Bugaboo
- Posts: 3215
- Joined: Wed Nov 15, 2017 2:48 pm
Re: A new data compressor called ZX0
Awesome, thank you!!!
- Einar Saukas
- Bugaboo
- Posts: 3215
- Joined: Wed Nov 15, 2017 2:48 pm
Re: A new data compressor called ZX0
Did you also convert "memory.c" to Python, or are you simply relying on Python GC? I believe native GC will be faster than explicit memory management in an interpreted language like Python.
I'm not a Python programmer, but I can take a look at your code if you want!
Re: A new data compressor called ZX0
I've ripped out all the c-like memory stuff and moved over to Python GC now, and implemented a cache of the elias-gamma bits (idea from [mention]Bedazzle[/mention]) along with a few other small tweaks and the time is roughly halved again. Not sure that I can see any more possible gains.. but someone else might do. It's just about useful for my purposes now, but I'd love to see it be faster stillEinar Saukas wrote: ↑Wed Aug 25, 2021 7:13 pm Did you also convert "memory.c" to Python, or are you simply relying on Python GC? I believe native GC will be faster than explicit memory management in an interpreted language like Python.
Sure! Let me tidy it up a little bit and I'll post it somewhere... maybe as a snippet on BitBucket so that others can take a look at it tooEinar Saukas wrote: ↑Wed Aug 25, 2021 7:13 pm I'm not a Python programmer, but I can take a look at your code if you want!
Re: A new data compressor called ZX0
Here's the code: https://bitbucket.org/evilpaul/workspac ... ets/gBnzKA
It's still a bit rough and ready. Eventually I'll wrap it up into a module, and include some command line options for when it's run as a stand-alone app.
If you put a 48.rom file in the right place then it'll compress it and check it against a known good md5 sum. This way you can make changes and check that you haven't broken anything.
I've only optimised and tided up the optimize() function - compress() is fast enough that it doesn't need any work.
If anyone can see any improvements (after having profiled them to make sure that they do actually improve things) then let me know.
It's still a bit rough and ready. Eventually I'll wrap it up into a module, and include some command line options for when it's run as a stand-alone app.
If you put a 48.rom file in the right place then it'll compress it and check it against a known good md5 sum. This way you can make changes and check that you haven't broken anything.
I've only optimised and tided up the optimize() function - compress() is fast enough that it doesn't need any work.
If anyone can see any improvements (after having profiled them to make sure that they do actually improve things) then let me know.
Re: A new data compressor called ZX0
This time I have achieved a more important speed optimization, around 2%
Code: Select all
; -----------------------------------------------------------------------------
; ZX0 decoder by Einar Saukas
; "Standard" version (69 bytes only) - BACKWARDS VARIANT
; -----------------------------------------------------------------------------
; Parameters:
; HL: last source address (compressed data)
; DE: last destination address (decompressing)
; -----------------------------------------------------------------------------
dzx0_standard_back:
ld bc, 1 ; preserve default offset 1
push bc
ld a, $80
dzx0sb_literals:
call dzx0sb_elias ; obtain length
lddr ; copy literals
inc c
add a, a ; copy from last offset or new offset?
jr c, dzx0sb_new_offset
call dzx0sb_elias ; obtain length
dzx0sb_copy:
ex (sp), hl ; preserve source, restore offset
push hl ; preserve offset
add hl, de ; calculate destination - offset
lddr ; copy from offset
inc c
pop hl ; restore offset
ex (sp), hl ; preserve offset, restore source
add a, a ; copy from literals or new offset?
jr nc, dzx0sb_literals
dzx0sb_new_offset:
inc sp ; discard last offset
inc sp
call dzx0sb_elias ; obtain offset MSB
dec b
ret z ; check end marker
dec c ; adjust for positive offset
ld b, c
ld c, (hl) ; obtain offset LSB
dec hl
srl b ; last offset bit becomes first length bit
rr c
inc bc
push bc ; preserve new offset
ld bc, 1 ; obtain length
call c, dzx0sb_elias_backtrack
inc bc
jr dzx0sb_copy
dzx0sb_elias_backtrack:
add a, a
rl c
rl b
dzx0sb_elias:
add a, a ; inverted interlaced Elias gamma coding
jr nz, dzx0sb_elias_skip
ld a, (hl) ; load another group of 8 bits
dec hl
rla
dzx0sb_elias_skip:
jr c, dzx0sb_elias_backtrack
ret
; -----------------------------------------------------------------------------
- rastersoft
- Microbot
- Posts: 151
- Joined: Mon Feb 22, 2021 3:55 pm
Re: A new data compressor called ZX0
Mmm... Does anybody have interest in my text compression/decompression routines from Escape from M.O.N.J.A.S.? The output is about the 59% size of the original, each string is individually addressable, and can be decompressed on-the-fly without needing any kind of buffer. If there is interest, I can extract it and put some instructions...
Re: A new data compressor called ZX0
I need to do something with text compression for my Zelda-lite game. I have a bunch of ideas, but I would be interested to hear your approach. Maybe open another thread?rastersoft wrote: ↑Thu Sep 02, 2021 7:50 am Mmm... Does anybody have interest in my text compression/decompression routines from Escape from M.O.N.J.A.S.? The output is about the 59% size of the original, each string is individually addressable, and can be decompressed on-the-fly without needing any kind of buffer. If there is interest, I can extract it and put some instructions...