A new data compressor called ZX0

The place for codemasters or beginners to talk about programming any language for the Spectrum.
User avatar
Einar Saukas
Bugaboo
Posts: 3145
Joined: Wed Nov 15, 2017 2:48 pm

Re: A new data compressor called ZX0

Post by Einar Saukas »

ZX0 and ZX1 are now available for assembly 8080 and PDP11:

https://gitlab.com/ivagor/dezx0
https://gitlab.com/ivagor/dezx1
roudoudou
Drutt
Posts: 2
Joined: Tue Feb 02, 2021 2:22 pm

Re: A new data compressor called ZX0

Post by roudoudou »

Hi

about the pareto graph, is there an official dataset to do it?

the graph miss some crunchers so...
User avatar
Einar Saukas
Bugaboo
Posts: 3145
Joined: Wed Nov 15, 2017 2:48 pm

Re: A new data compressor called ZX0

Post by Einar Saukas »

roudoudou wrote: Mon Feb 22, 2021 8:39 am about the pareto graph, is there an official dataset to do it?
I don't know. You will have to ask [mention]introspec[/mention].
introspec
Dizzy
Posts: 53
Joined: Wed Jan 02, 2019 2:26 pm
Location: London
Contact:

Re: A new data compressor called ZX0

Post by introspec »

roudoudou wrote: Mon Feb 22, 2021 8:39 am about the pareto graph, is there an official dataset to do it?
Well, it is the same dataset from my 2017 article, that Einar used for testing ZX0!!!

Einar, my apologies for disappearing from the face of Earth, I need to catch up with some real life responsibilities, and then I'll get back to optimizing. I am seeing that your ZX1 decompressors are already quite close to LZSA2 in terms of the speed; I do not know if I'd be able to speed them up much further, but I think that overall ZX0/ZX1 combination is a fantastic pair of compressors for many practical tasks.
User avatar
Einar Saukas
Bugaboo
Posts: 3145
Joined: Wed Nov 15, 2017 2:48 pm

Re: A new data compressor called ZX0

Post by Einar Saukas »

introspec wrote: Tue Mar 02, 2021 5:18 pm Einar, my apologies for disappearing from the face of Earth, I need to catch up with some real life responsibilities, and then I'll get back to optimizing.
No problem, it happens with me all the time :)

introspec wrote: Tue Mar 02, 2021 5:18 pm I am seeing that your ZX1 decompressors are already quite close to LZSA2 in terms of the speed;
Did you measure it yourself already? I have only tested a limited set, I'm counting on you to obtain the "official" results and provide an updated article and/or graph!

introspec wrote: Tue Mar 02, 2021 5:18 pm I do not know if I'd be able to speed them up much further, but I think that overall ZX0/ZX1 combination is a fantastic pair of compressors for many practical tasks.
You have already contributed a lot, thank you very much! I credited you in both ZX0 and ZX1 pages accordingly.

In the meantime, I'm about to release ZX2, which is a minimalist version of ZX1 focused on very small datasets (for instance to create 1K demos). There's nothing groundbreaking about it, I just think there's enough demand to justify it.
User avatar
Iapetus
Drutt
Posts: 5
Joined: Thu Mar 04, 2021 10:20 pm
Location: Portugal
Contact:

Re: A new data compressor called ZX0

Post by Iapetus »

I am new here in the forum. For ages I have been using Exomizer on all my games for different platforms (6502,z80,6809) but I will give ZX0 a try in my new TC2048 game project. thanks.
User avatar
Einar Saukas
Bugaboo
Posts: 3145
Joined: Wed Nov 15, 2017 2:48 pm

Re: A new data compressor called ZX0

Post by Einar Saukas »

Iapetus wrote: Sun Mar 07, 2021 4:22 pm I am new here in the forum. For ages I have been using Exomizer on all my games for different platforms (6502,z80,6809) but I will give ZX0 a try in my new TC2048 game project. thanks.
Thank you! :)
User avatar
Einar Saukas
Bugaboo
Posts: 3145
Joined: Wed Nov 15, 2017 2:48 pm

Re: A new data compressor called ZX0

Post by Einar Saukas »

The ZX0 decompressor is now available for 6502, ported by Bitbreaker (Tobias Bindhammer) from the C64 demoscene!
User avatar
utz
Microbot
Posts: 116
Joined: Wed Nov 15, 2017 9:04 am
Contact:

Re: A new data compressor called ZX0

Post by utz »

Am I understanding correctly that the 6502 depacker is not compatible with output from the original compressor?
User avatar
Einar Saukas
Bugaboo
Posts: 3145
Joined: Wed Nov 15, 2017 2:48 pm

Re: A new data compressor called ZX0

Post by Einar Saukas »

utz wrote: Sun Mar 14, 2021 8:10 pm Am I understanding correctly that the 6502 depacker is not compatible with output from the original compressor?
There are 2 types of ZX0 depacker for 6502:
  • dzx0.asm supports the standard ZX0 format
  • sfx.asm supports a modified ZX0 variant with C64 specific optimizations
User avatar
Einar Saukas
Bugaboo
Posts: 3145
Joined: Wed Nov 15, 2017 2:48 pm

Re: A new data compressor called ZX0

Post by Einar Saukas »

The ZX0 decompressor is now available for both Motorola 6809 and Hitachi 6309, ported by Doug Masten!
User avatar
Einar Saukas
Bugaboo
Posts: 3145
Joined: Wed Nov 15, 2017 2:48 pm

Re: A new data compressor called ZX0

Post by Einar Saukas »

Einar Saukas wrote: Tue Mar 02, 2021 8:11 pm In the meantime, I'm about to release ZX2, which is a minimalist version of ZX1 focused on very small datasets (for instance to create 1K demos).
ZX2 is finally available! You can read about it here:

https://github.com/einar-saukas/ZX2
Randomiserusr
Drutt
Posts: 11
Joined: Fri Mar 19, 2021 5:15 pm

Re: A new data compressor called ZX0

Post by Randomiserusr »

Hi, new to the forum and immediately this post caught my eye.
I am using ZX basic boriel and I am interested to know how to use ZX0 within basic?
I am writing a novel game with lots of text so wanted to compress the string arrays but struggling to see how to us this library

Any basic help or examples much appreciated
Thanks
User avatar
Einar Saukas
Bugaboo
Posts: 3145
Joined: Wed Nov 15, 2017 2:48 pm

Re: A new data compressor called ZX0

Post by Einar Saukas »

Randomiserusr wrote: Fri Mar 19, 2021 5:40 pm Hi, new to the forum and immediately this post caught my eye.
Welcome!

Randomiserusr wrote: Fri Mar 19, 2021 5:40 pm I am using ZX basic boriel and I am interested to know how to use ZX0 within basic?
There's a short explanation and a simple example here:

https://zxbasic.readthedocs.io/en/latest/library/zx0/

The ZX Basic version that includes ZX0 support was not released yet. However you can already use it in any other ZX Basic version, just download this file, copy it to the same folder as your program, and use this:

Code: Select all

#include "zx0.bas"
instead of this:

Code: Select all

#include <zx0.bas>
Randomiserusr wrote: Fri Mar 19, 2021 5:40 pm I am writing a novel game with lots of text so wanted to compress the string arrays but struggling to see how to us this library
What kind of game exactly?

The reason I'm asking is, this kind of block compression is not intended to compress short text sentences separately. You would need to group your text into larger blocks before compression. Later you would have to decompress an entire block in order to access a text sentence within this block.

Therefore this is not a good choice for typical text adventures, where you typically need to access individual sentences in arbitrary order. Those games usually use a much simpler compression, for instance storing each character in 6 bits instead of 8, or storing most common pairs of characters (see here) or most common words (for instance "the", "you", etc) as a single byte. These ideas are used in PAW for instance. It wouldn't compress as much as ZX0, but it allows decompressing small text sentences "on the fly".

Unless you can split your text adventure into multiple "areas", compressing together all location descriptions in each area. Or if your game is more like a Choose Your Own Adventure where each text sentence is quite large, filling an entire page.

Randomiserusr wrote: Fri Mar 19, 2021 5:40 pm Any basic help or examples much appreciated
If you can describe what you need, we may be able to put you in the right track :)
Randomiserusr
Drutt
Posts: 11
Joined: Fri Mar 19, 2021 5:15 pm

Re: A new data compressor called ZX0

Post by Randomiserusr »

Oh thank you for your quick and verbose response.

Yes the string array will hold a long description of the "Chapter" and so needs to be retrievable quickly.

Looks like my best bet is some sort of digraph or trigraph routine to store the "Dictionary"
I guess this way I can do all my "compressing and dictionary building" external to ZX Basic and build the data in DATA statements against a DICTIONARY Array indexed by the "Key".

Unless there is a nicer and better/easy way?

thanks
:-)
catmeows
Manic Miner
Posts: 718
Joined: Tue May 28, 2019 12:02 pm
Location: Prague

Re: A new data compressor called ZX0

Post by catmeows »

Randomiserusr wrote: Sat Mar 20, 2021 9:49 am Looks like my best bet is some sort of digraph or trigraph routine to store the "Dictionary"
Unless there is a nicer and better/easy way?
You want this: https://en.wikipedia.org/wiki/Byte_pair_encoding
I haved tried it with text of Pirates! game and result was little less than 50% of original size.
Proud owner of Didaktik M
Randomiserusr
Drutt
Posts: 11
Joined: Fri Mar 19, 2021 5:15 pm

Re: A new data compressor called ZX0

Post by Randomiserusr »

Thanks for the reply :-)

Yes, I was looking at this amongst many others so will try this if the current simple word dictionary is not yielding good compression results.

Any ZX BASIC (Or BASIC ) suggested sites? Else I will check this out a bit later

Thanks again
User avatar
Einar Saukas
Bugaboo
Posts: 3145
Joined: Wed Nov 15, 2017 2:48 pm

Re: A new data compressor called ZX0

Post by Einar Saukas »

Randomiserusr wrote: Sat Mar 20, 2021 9:49 am Yes the string array will hold a long description of the "Chapter" and so needs to be retrievable quickly.
If each string contains long descriptions, it should work for ZX0.

Basically your choices are:
  • A PAW-like text compression based on digraphs and common words. It will give you the same compression regardless of the text size, saving up to 50% of space depending on how you implement it. In this case, you will need a custom routine to decompress it "on the fly" while printing.
  • A generic block compressor like ZX0. It will give you better compression for larger texts, saving up to 70% of space if the text is large enough (perhaps using a few common words in a prefix area to help compression). In this case, you will need to decompress each description into a temporary area, before quickly printing it as usual.
I suggest you run a quick test, compressing each of your text descriptions using ZX0 just to see if they are long enough to achieve a good compression. If they do, then problem solved. Otherwise you can take the other option.
Randomiserusr
Drutt
Posts: 11
Joined: Fri Mar 19, 2021 5:15 pm

Re: A new data compressor called ZX0

Post by Randomiserusr »

Einar Saukas wrote: Sun Mar 21, 2021 5:13 am
Randomiserusr wrote: Sat Mar 20, 2021 9:49 am Yes the string array will hold a long description of the "Chapter" and so needs to be retrievable quickly.
If each string contains long descriptions, it should work for ZX0.

Basically your choices are:
  • A PAW-like text compression based on digraphs and common words. It will give you the same compression regardless of the text size, saving up to 50% of space depending on how you implement it. In this case, you will need a custom routine to decompress it "on the fly" while printing.
  • A generic block compressor like ZX0. It will give you better compression for larger texts, saving up to 70% of space if the text is large enough (perhaps using a few common words in a prefix area to help compression). In this case, you will need to decompress each description into a temporary area, before quickly printing it as usual.
I suggest you run a quick test, compressing each of your text descriptions using ZX0 just to see if they are long enough to achieve a good compression. If they do, then problem solved. Otherwise you can take the other option.
Thanks for this. I have created a packing routine outside of ZX Basic which translates the sentences into "tokens" which are then added to DATA statements. A "Dictionary" is added a quick look up to output the words and it seems to be on different in speed as just plain text. So instead of lots of STRINGS and STRING Arrays there is on String array and several number arrays which seem to take up less memory.

That said the original question I posted was to understand how to implement ZX0 in ZXBasic.
Whilst technically sound I am not a Z80 assembler by trade (Though I did some in the mid 80's) but just need the stepping stones to kick start the usage of ZX0 in ZXBASIC

The kind of thing I am looking for is:-

1. Compress using
zx0 -q intro.scr.rcs.zx0
2. Then add inline asm code to compressed file

Code: Select all

introscr:
    asm
        incbin "intro.scr.rcs.zx0"
    end asm

#include "zx0.bas"

dzx0AgileRCS(@introscr, 16384)
3, This is where it starts to fall down for me.

Q1. The compressed file intro.scr.rcs.zx0 was generated from a file called intro.scr.rcs but what is in this file or should I say what should I add in this file?
How is it formatted?

Q2. Assuming Q1. Answered then how do I use this after call

Code: Select all

 dzx0AgileRCS(@introscr, 16384)
in ZXBASIC
in terms of loading the uncompressed Text in this file into memory and more importantly into variables that I can access afterwards?

Lastly is there actual working examples you could send to me please?
thank you
User avatar
Einar Saukas
Bugaboo
Posts: 3145
Joined: Wed Nov 15, 2017 2:48 pm

Re: A new data compressor called ZX0

Post by Einar Saukas »

Randomiserusr wrote: Sun Mar 21, 2021 10:02 am Lastly is there actual working examples you could send to me please?
Let's start with a simpler example:

1. Choose any ZX Spectrum image in SCR format. It can be anything. For instance right click on this link and save it as "Cobra.scr".

2. Compress this image using ZX0, typing "zx0 Cobra.scr". You should see something like this:

Code: Select all

>zx0 Cobra.scr
ZX0 v1.5: Optimal data compressor by Einar Saukas
[...............................................]
File compressed from 6912 to 2196 bytes! (delta 2)
3. Since there's no Boriel ZX Basic version that includes ZX0 yet, then right click on this link and save it as "zx0.bas".

4. Type this program below, then save it as "prog1.bas":

Code: Select all

#include "zx0.bas"

10 dzx0Standard(@introscr, 16384)
20 GOTO 20

introscr:
    asm
        incbin "Cobra.scr.zx0"
    end asm
5. Put all these files in the same directory, then compile this program using "zxb -t -a -B prog1.bas". It will generate a file called "prog1.tap".

6. Load "prog1.tap" using your favorite emulator. You will see this image getting decompressed directly to the screen.

7. Try making some changes to this program. For instance compress 2 different images, include both compressed images into your program, then change your program to decompress one screen, wait for a pressed key, then decompress another screen.

8. Now change it again, but this time try to compress 2 text files instead of 2 images. You should make your program decompress the first text to address 50000, then print it from address 50000 to screen, wait for a pressed key, clear the screen, decompress the second text to address 50000, then print it from address 50000 to screen.
introspec
Dizzy
Posts: 53
Joined: Wed Jan 02, 2019 2:26 pm
Location: London
Contact:

Re: A new data compressor called ZX0

Post by introspec »

Hi Einar, I just created a somewhat clumsy pull request on the GitHub. The final version of the "unzx0_fast.asm" is about as fast as "dzx0_mega.asm" (the 412 byte version), but is only 191 bytes long. Of course, because their speeds are quite similar, I've seen files where "dzx0_mega.asm" is a bit faster, and I've seen files where "unzx0_fast.asm" is faster. Both are within 1% of each other, so I do not think you can be more specific than this.

I am attaching the new decompressor here as well, just for convenience.

Code: Select all

;
;  Speed-optimized ZX0 decompressor by spke (191 bytes)
;
;  ver.00 by spke (27/01-23/03/2021, 191 bytes)
;
;  Original ZX0 decompressors were written by Einar Saukas
;
;  This decompressor was written on the basis of "Standard" decompressor by
;  Einar Saukas and optimized for speed by spke. This decompressor is
;  about 5% faster than the "Turbo" decompressor, which is 128 bytes long.
;  It has about the same speed as the "Mega" decompressor, which occupies 412 bytes.
;  
;  The decompressor uses AF, AF', BC, DE, HL and IX and relies upon self-modified code.
;
;  The decompression is done in the standard way:
;
;  ld hl,FirstByteOfCompressedData
;  ld de,FirstByteOfMemoryForDecompressedData
;  call DecompressZX0
;
;  Of course, ZX0 compression algorithms are (c) 2021 Einar Saukas,
;  see https://github.com/einar-saukas/ZX0 for more information
;
;  Drop me an email if you have any comments/ideas/suggestions: [email protected]
;
;  This software is provided 'as-is', without any express or implied
;  warranty.  In no event will the authors be held liable for any damages
;  arising from the use of this software.
;
;  Permission is granted to anyone to use this software for any purpose,
;  including commercial applications, and to alter it and redistribute it
;  freely, subject to the following restrictions:
;
;  1. The origin of this software must not be misrepresented; you must not
;     claim that you wrote the original software. If you use this software
;     in a product, an acknowledgment in the product documentation would be
;     appreciated but is not required.
;  2. Altered source versions must be plainly marked as such, and must not be
;     misrepresented as being the original software.
;  3. This notice may not be removed or altered from any source distribution.

		MACRO	RELOAD_BITS
			ld a,(hl) : inc hl : rla
		ENDM

		MACRO	INLINE_READ_GAMMA
.ReadGammaBits		add a : rl c : add a : jr nc,.ReadGammaBits
		ENDM

@DecompressZX0:		ld ix,CopyMatch1
			ld bc,#FFFF : ld (PrevOffset),bc				; default offset is -1
			inc bc : ld a,#80 : jr RunOfLiterals				; BC is assumed to contains 0 most of the time
			
ShorterOffsets			; 7-bit offsets allow additional optimizations,
				; based on the facts that C==0 and AF' has C ON!
				ld (ix+PrevOffset+1-CopyMatch1),#FF			; the top byte of the offset is always #FF
				exa : ld a,(hl) : inc hl
				rra : ld (PrevOffset),a					; note that AF' always has flag C ON

			jr nc,LongerMatch

CopyMatch2			; the case of matches with len=2
				exa : ld c,2

CopyMatch1			; the faster match copying code
				push hl							; preserve source
PrevOffset			EQU $+1 : ld hl,#FFFF					; restore offset (default offset is -1)
				add hl,de						; HL = dest - offset
				ldir
				pop hl							; restore source

			; after a match you can have either
			; 0 + <elias length> = run of literals, or
			; 1 + <elias offset msb> + [7-bits of offset lsb + 1-bit of length] + <elias length> = another match
AfterMatch1		add a : jr nc,RunOfLiterals

UsualMatch:			; this is the case of usual match+offset
				add a : jr nc,LongerOffets : jr nz,ShorterOffsets	; NZ after NC == "confirmed C"
					RELOAD_BITS : jr c,ShorterOffsets

LongerOffets			inc c : INLINE_READ_GAMMA				; reading gamma requires C=1
				call z,ReloadReadGamma

ProcessOffset			exa : xor a : sub c
				ret z							; end-of-data marker (only checked for longer offsets)

				rra : ld (PrevOffset+1),a
				ld a,(hl) : inc hl
				rra : ld (PrevOffset),a

			; lowest bit is the first bit of the gamma code for length
			jr c,CopyMatch2

				; this wastes 1 t-state for longer matches far away,
				; but saves 4 t-states for longer nearby (seems to pay off in testing)
				ld c,b
LongerMatch			inc c
				; doing SCF here ensures that AF' has flag C ON and costs
				; cheaper than doing SCF in the ShortestOffsets branch
				scf : exa

				INLINE_READ_GAMMA
				call z,ReloadReadGamma
				inc bc

CopyMatch3			push hl						; preserve source
				ld hl,(PrevOffset)				; restore offset
				add hl,de					; HL = dest - offset
				; because BC>=3, we can do 2 x LDI safely
				ldi : ldi : ldir
				pop hl						; restore source

			; after a match you can have either
			; 0 + <elias length> = run of literals, or
			; 1 + <elias offset msb> + [7-bits of offset lsb + 1-bit of length] + <elias length> = another match
AfterMatch3		add a : jr c,UsualMatch

RunOfLiterals:			inc c : add a : jr nc,LongerRun : jr nz,CopyLiteral	; NZ after NC == "confirmed C"
					RELOAD_BITS : jr c,CopyLiteral

LongerRun			INLINE_READ_GAMMA : jr nz,CopyLiterals
					RELOAD_BITS
				call nc,ReadGammaAligned

CopyLiterals			ldi
CopyLiteral			ldir

			; after a literal run you can have either
			; 0 + <elias length> = match using a repeated offset, or
			; 1 + <elias offset msb> + [7-bits of offset lsb + 1-bit of length] + <elias length> = another match
			add a : jr c,UsualMatch

RepMatch:			inc c : add a : jr nc,LongerRepMatch : jr nz,CopyMatch1	; NZ after NC == "confirmed C"
					RELOAD_BITS : jr c,CopyMatch1

LongerRepMatch			INLINE_READ_GAMMA
				jp nz,CopyMatch1

				; this is a crafty equivalent of
				; CALL ReloadReadGamma : JP CopyMatch1
				push ix

;
;  the subroutine for reading the remainder of the partly read Elias gamma code.
;  it has two entry points: ReloadReadGamma first refills the bit reservoir in A,
;  while ReadGammaAligned assumes that the bit reservoir has just been refilled.

ReloadReadGamma:	RELOAD_BITS

ReadGammaAligned:	; this loop can be unrolled for a very minor increase in decompression speed
			; (we are talking about +0.2% for +8 bytes, i.e. not really recommended)

		;DEFINE	UNROLL_ME
		IFNDEF	UNROLL_ME
				DUP 2
				ret c
				add a : rl c
				add a
				EDUP
				jr nz,ReadGammaAligned
		ELSE
				DUP 4
				ret c
				add a : rl c
				add a
				EDUP
		ENDIF

ReloadBits		RELOAD_BITS

ReadingLongGamma		; this loop does not need unrolling,
				; as it does not get much use anyway
				ret c
				add a : rl c : rl b
				add a :	jr nz,ReadingLongGamma

			jr ReloadBits

User avatar
Einar Saukas
Bugaboo
Posts: 3145
Joined: Wed Nov 15, 2017 2:48 pm

Re: A new data compressor called ZX0

Post by Einar Saukas »

Good work!!!

I approved your pull request, so it's now available here:

https://github.com/einar-saukas/ZX0/blo ... 0_fast.asm

My only concern is that your code uses a compiler specific syntax, so many users won't be able to use it. In particular, all compilers I have refused to compile it :)

Do you mind if I update it to a more generic assembly syntax? Here's exactly the same listing, with all compiler specific details removed:

Code: Select all

;
;  Speed-optimized ZX0 decompressor by spke (191 bytes)
;
;  ver.00 by spke (27/01-23/03/2021, 191 bytes)
;
;  Original ZX0 decompressors were written by Einar Saukas
;
;  This decompressor was written on the basis of "Standard" decompressor by
;  Einar Saukas and optimized for speed by spke. This decompressor is
;  about 5% faster than the "Turbo" decompressor, which is 128 bytes long.
;  It has about the same speed as the "Mega" decompressor, which occupies 412 bytes.
;  
;  The decompressor uses AF, AF', BC, DE, HL and IX and relies upon self-modified code.
;
;  The decompression is done in the standard way:
;
;  ld hl,FirstByteOfCompressedData
;  ld de,FirstByteOfMemoryForDecompressedData
;  call DecompressZX0
;
;  Of course, ZX0 compression algorithms are (c) 2021 Einar Saukas,
;  see https://github.com/einar-saukas/ZX0 for more information
;
;  Drop me an email if you have any comments/ideas/suggestions: [email protected]
;
;  This software is provided 'as-is', without any express or implied
;  warranty.  In no event will the authors be held liable for any damages
;  arising from the use of this software.
;
;  Permission is granted to anyone to use this software for any purpose,
;  including commercial applications, and to alter it and redistribute it
;  freely, subject to the following restrictions:
;
;  1. The origin of this software must not be misrepresented; you must not
;     claim that you wrote the original software. If you use this software
;     in a product, an acknowledgment in the product documentation would be
;     appreciated but is not required.
;  2. Altered source versions must be plainly marked as such, and must not be
;     misrepresented as being the original software.
;  3. This notice may not be removed or altered from any source distribution.

DecompressZX0:
        ld      ix, CopyMatch1
        ld      bc, $ffff
        ld      (PrevOffset+1), bc      ; default offset is -1
        inc     bc
        ld      a, $80
        jr      RunOfLiterals           ; BC is assumed to contains 0 most of the time

        ; 7-bit offsets allow additional optimizations, based on the facts that C==0 and AF' has C ON!
ShorterOffsets:
        ld      (ix+PrevOffset+2-CopyMatch1), $ff  ; the top byte of the offset is always $FF
        ex      af, af'
        ld      a, (hl)
        inc     hl
        rra
        ld      (PrevOffset+1), a       ; note that AF' always has flag C ON
        jr      nc, LongerMatch

CopyMatch2:                             ; the case of matches with len=2
        ex      af, af'
        ld      c, 2

        ; the faster match copying code
CopyMatch1:
        push    hl                      ; preserve source

PrevOffset:
        ld      hl, $ffff               ; restore offset (default offset is -1)
        add     hl, de                  ; HL = dest - offset
        ldir
        pop     hl                      ; restore source

        ; after a match you can have either
        ; 0 + <elias length> = run of literals, or
        ; 1 + <elias offset msb> + [7-bits of offset lsb + 1-bit of length] + <elias length> = another match
AfterMatch1:
        add     a, a
        jr      nc, RunOfLiterals

UsualMatch:                             ; this is the case of usual match+offset
        add     a, a
        jr      nc, LongerOffets
        jr      nz, ShorterOffsets      ; NZ after NC == "confirmed C"
        
        ld      a, (hl)                 ; reload bits
        inc     hl
        rla

        jr      c, ShorterOffsets

LongerOffets:
        inc     c

        add     a, a                    ; inline read gamma
        rl      c
        add     a, a
        jr      nc, $-4

        call    z, ReloadReadGamma

ProcessOffset:
        ex      af, af'
        xor     a
        sub     c
        ret     z                       ; end-of-data marker (only checked for longer offsets)
        rra
        ld      (PrevOffset+2),a
        ld      a, (hl)
        inc     hl
        rra
        ld      (PrevOffset+1), a

        ; lowest bit is the first bit of the gamma code for length
        jr      c, CopyMatch2

        ; this wastes 1 t-state for longer matches far away,
        ; but saves 4 t-states for longer nearby (seems to pay off in testing)
        ld      c, b
LongerMatch:
        inc     c
        ; doing SCF here ensures that AF' has flag C ON and costs
        ; cheaper than doing SCF in the ShortestOffsets branch
        scf
        ex      af, af'

        add     a, a                    ; inline read gamma
        rl      c
        add     a, a
        jr      nc, $-4

        call    z,ReloadReadGamma
        inc     bc

CopyMatch3:
        push    hl                      ; preserve source
        ld      hl, (PrevOffset+1)      ; restore offset
        add     hl, de                  ; HL = dest - offset

        ; because BC>=3, we can do 2 x LDI safely
        ldi
        ldi
        ldir
        pop     hl                      ; restore source

        ; after a match you can have either
        ; 0 + <elias length> = run of literals, or
        ; 1 + <elias offset msb> + [7-bits of offset lsb + 1-bit of length] + <elias length> = another match
AfterMatch3:
        add     a, a
        jr      c, UsualMatch

RunOfLiterals:
        inc     c
        add     a, a
        jr      nc, LongerRun
        jr      nz, CopyLiteral         ; NZ after NC == "confirmed C"
        
        ld      a, (hl)                 ; reload bits
        inc     hl
        rla

        jr      c, CopyLiteral

LongerRun:
        add     a, a                    ; inline read gamma
        rl      c
        add     a, a
        jr      nc, $-4

        jr      nz, CopyLiterals
        
        ld      a, (hl)                 ; reload bits
        inc     hl
        rla

        call    nc, ReadGammaAligned

CopyLiterals:
        ldi

CopyLiteral:
        ldir

        ; after a literal run you can have either
        ; 0 + <elias length> = match using a repeated offset, or
        ; 1 + <elias offset msb> + [7-bits of offset lsb + 1-bit of length] + <elias length> = another match
        add     a, a
        jr      c, UsualMatch

RepMatch:
        inc     c
        add     a, a
        jr      nc, LongerRepMatch
        jr      nz, CopyMatch1          ; NZ after NC == "confirmed C"
        
        ld      a, (hl)                 ; reload bits
        inc     hl
        rla

        jr      c, CopyMatch1

LongerRepMatch:
        add     a, a                    ; inline read gamma
        rl      c
        add     a, a
        jr      nc, $-4

        jp      nz, CopyMatch1

        ; this is a crafty equivalent of CALL ReloadReadGamma : JP CopyMatch1
        push    ix

        ;  the subroutine for reading the remainder of the partly read Elias gamma code.
        ;  it has two entry points: ReloadReadGamma first refills the bit reservoir in A,
        ;  while ReadGammaAligned assumes that the bit reservoir has just been refilled.
ReloadReadGamma:
        ld      a, (hl)                 ; reload bits
        inc     hl
        rla

ReadGammaAligned:
        ret     c
        add     a, a
        rl      c
        add     a, a
        ret     c
        add     a, a
        rl      c
        add     a, a
        jr      nz, ReadGammaAligned

ReloadBits:
        ld      a, (hl)                 ; reload bits
        inc     hl
        rla

ReadingLongGamma:                       ; this loop does not need unrolling, as it does not get much use anyway
        ret     c
        add     a, a
        rl      c
        rl      b
        add     a, a
        jr      nz, ReadingLongGamma
        jr      ReloadBits
introspec
Dizzy
Posts: 53
Joined: Wed Jan 02, 2019 2:26 pm
Location: London
Contact:

Re: A new data compressor called ZX0

Post by introspec »

No worries, of course. I do think it is much easier to read with macros and indenting, but people can make their own choice and I am guessing it is best to use the most compatible syntax possible in your main repo.

And of course I cannot complain about removing EXAs and other shorthand.
User avatar
Einar Saukas
Bugaboo
Posts: 3145
Joined: Wed Nov 15, 2017 2:48 pm

Re: A new data compressor called ZX0

Post by Einar Saukas »

Done!

I will run a few tests, then update the documentation accordingly. Thanks again!!!
User avatar
Einar Saukas
Bugaboo
Posts: 3145
Joined: Wed Nov 15, 2017 2:48 pm

Re: A new data compressor called ZX0

Post by Einar Saukas »

Houston, we have a problem!

When I decompress LedZeppelin.scr directly to the screen, it produces a wrong image.

Perhaps I made a mistake when converting your version to a generic syntax, but I double-checked everything twice and it seems fine. Can you please test it using your original version?
Post Reply