A new data compressor called ZX0

[AndyC]

If you were an Amstrad CPC user, what would you prefer?

I hardly imagine user that uses sources

And I'm not sure that different sources of data will be in sync when updated from time to time.

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)

[Rhino]

I 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?

Ah, 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.

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.

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 : )
Until that happens maybe a simple warning in the comments like "This code is not optimized for CPC", could be useful imo.

Regards

[Sol_HSA]

Until that happens maybe a simple warning in the comments like "This code is not optimized for CPC", could be useful imo.

Isn't that the default? I really don't see the point.

[Rhino]

Until that happens maybe a simple warning in the comments like "This code is not optimized for CPC", could be useful imo.

Isn't that the default? I really don't see the point.

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

[evilpaul]

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?

[Einar Saukas]

Does the license allow me to do this and still distribute the Python module with my toolchain?

Yes!

[Einar Saukas]

I would of course be happy for any code I write to be included in the main ZX0 repo.

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.

[evilpaul]

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]

Thank you!

[Urusergi]

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:

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

[Urusergi]

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.

[Einar Saukas]

Congratulations on this new compressor, it's amazing!!

Thank you!!!

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.

Thanks

I've already realized that it does not work, but i'll keep looking for some optimization

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!

[evilpaul]

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!

[Urusergi]

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

[headkaze]

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.

[Bedazzle]

Well… I spent a couple of hours mechanically porting the c code to Python, line by line.

Is it available somewhere?

[evilpaul]

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.

[Einar Saukas]

With all of you, an incredible optimization of..... 8 T-cycles (it seems that no more can be achieved )

I'm updating the ZX0 repository with this optimization now. Thank you!!!

[Einar Saukas]

Great work @Einar Saukas 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.

Awesome, thank you!!!

[Einar Saukas]

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

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!

[evilpaul]

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'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 still

I'm not a Python programmer, but I can take a look at your code if you want!

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 too

[evilpaul]

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.

[Urusergi]

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]

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...

[evilpaul]

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...

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?