Z80 compressor

Paradigm Shifter

Is there one available?

Is it any good?

Peeps have been suggesting we should look into this, so here's a new thread!

I'd do the compressor on the PC.

I've done huffman before, pretty easy. But boring to code.

Mixing compression algorithms can be a win too, compress using various methods and compare results.

na_th_an

Exomizer, aplib and pucrunch are nice compressors, each with their own pros/cons. Some compress better, some are faster, some are smaller.

I've been using the aplib decompresor quite a bit lately, and it works great for full screen graphics.

Paradigm Shifter

Obviously I meant "decompressor" in the title ;)

Fikee

Paradigm Shifter wrote: »

Is there one available?

Is it any good?

There are many mature compressor, namely pucrunch and exomizer are good. pucrunch uses an innovative way how to mark literals and matches while exomizer do some magic with reducing offset length (basically statiscal compression of offsets). Both do some optimizing on stream but exomizer looks more advanced in this.

By far best is pmc by Paolo Ferraris, it is LZ backed by Huffman (well, i believe it is Shannon-Fano actually but i could be wrong). It was written for minigame compo and has amazing compression ratio and very compact decoder. Sadly its decompressor is very slow, it takes maybe 15 seconds to decompress 5 KB.

What is missing is some kind compressor which would use LZ (with some tweaks like optimizing, using index to few previously used offsets - 7zip does such things) and backed with full huffman and with quite fast (at least 1KB/sec) decompressor.

FrankT

MegaLZ is good. It has commandline app to compress binaries, and the z80 decompressor is very fast and fairly small. I hacked Splitting Images and was able to fit in many more level screens using MegaLZ.

For screens, Laser Compact 5.2 does the best compression i've seen. You can save the compressed screen with or without the decompressor included. Options to include the attributes or not, and different 1/3rds of the screen. Its TRDOS disk only though. Might be worth extracting the compressor code from the disk to make a tap for all speccies.

Paradigm Shifter

Can we do better if we pool our brainz though?

This is the development forum after all ;)

csmith

Paradigm Shifter wrote: »

Peeps have been suggesting we should look into this, so here's a new thread!

Damn, you beat me too it during the drive home!

csmith

I want to be able to unpack the sprites needed for a room during the screen flip. There is a load of painting to do, so unpack must be fast.

I was going to start with a really simple "factor out the common byte sequences and index to them" but then I realised that the index reference might nearly take up as much space as the factored out bytes. But I knew this in the back of my mind anyway, if I'm honest.

Compression of the room data would also be good - though I'd probably split the map into segments (being a bunch of rooms), and unpack the segment you're in when you move from one to the other. Saves doing it too often and improves the compression ratio as you're working on a bigger data set (unless I statistically analyse the entire room data, and the compress map segments against that).

So a balance between speed'n'complexity against compression ratio is good.

Paradigm Shifter

Statistical analysis of all the data, that's exactly what Huffman does.

Step 1:

Build histogram of data

Step 2:

Build tree and compress using frequency table from (1)

Step 3: Profit

I'm not saying huffman is the holy grail though ;) It's a good start.

csmith

Paradigm Shifter wrote: »

Statistical analysis of all the data, that's exactly what Huffman does.
.. cut ..
I'm not saying huffman is the holy grail though ;) It's a good start.

That's where I was coming from. I wrote an LZW (or was it just LZ?) compressor/decompressor a while back for a package installer. That was quite good, but I see that kind of decompressor needing just too much memory for a Z80 in-game decompressor.

I suppose we could frig it to create a single expansion table (or whatever it's called) for all the sprites, and then compress each (or groups) against that. Obviously we want to selectively decompress data, and thus we could do without the overhead that normally goes at the front of each compressed block.

Paradigm Shifter

Think of the all the data as one big long file, for a kickoff.

EDIT: And then go from there, a new table is gonna cost you memory.

EDIT2: Yes, I am Cptn Obvious ;)

csmith

Paradigm Shifter wrote: »

Think of the all the data as one big long file, for a kickoff.

Well, I am. But then most of us will want to decompress bits of it.
Edit: I'm only talking about one table/dictionary, that's my point.

The more I think about it, the more I like the idea of:
1. feed the compressor each sprite in turn (or each room data in turn). ie a chunk.
2. The compressor analyses each "chunk" and puts them to one side.
3. When all chunks analysed, the compressor writes out the dictionary (say for LZW)
4. It then compresses each chunk in turn, maintaining an index to each in the output stream.
4. Write out the chunk_number->stream_offset index.

To decompress, you call the decompressor with the chunk number, from which it finds the start/end of the compressed chunk. It then decompresses against the common shared dictionary.

Thus you only need one dictionary.

Something like that.

Paradigm Shifter

You need the data length in bits for a decompress, so you can do that with a list skip rather than storing offsets. Slow, but probably not too slow to cause headaches.

csmith

Paradigm Shifter wrote: »

You need the data length in bits for a decompress, so you can do that with a list skip rather than storing offsets. Slow, but probably not too slow to cause headaches.

Truuuuueeeee, but each sprite is going to be in a table anyway, as they will have a bunch of parameters associated with them. Most of this could be compressed, but as you have the table anyway and some data in it would need to be "plaintext" so to speak, you could store the index to the compressed sprite data there instead of the pointer to the sprite data (that you would have had _before_ you decided to compress), and pass that to the decomp.

Ok nasty from a reuse point of view, but great from a memory use point of view.

Alcoholics Anonymous

Paradigm Shifter wrote: »

I'm not saying huffman is the holy grail though ;) It's a good start.

Way back in 2003 (has it been that long already!?!) I wrote this huffman decoder masterpiece:

; Static Huffman Decoder
; Alvin Albrecht 03.2003
;

XLIB SPHuffDecode

; enter: hl = root of decoder tree
;        de = memory address of encoded message
;         c = next bit in de's byte to interpret (bit mask)
; exit :  a = next decoded symbol
;        de and c are updated for decoding the next symbol
; uses : af, c, de, hl

.nextcodebit
   srl c              ; move mask right one bit
   jp nc, SPHuffDecode
   inc de             ; move on to next byte
   ld c,$80

.SPHuffDecode
   inc hl
   inc hl
   inc hl             ; hl = root.left+1
   ld a,(hl)          ; if msb of left pointer = 0 then this is a leaf
   or a
   jp nz, notleaf
   dec hl             ; a leaf, decoded symbol is stored at root.left
   ld a,(hl)
   ret                ; return with a = decoded symbol, de = next address, c = next bit

.notleaf
   ld a,(de)          ; get current byte
   and c              ; mask off bit
   jr z, goleft       ; if code bit is 0, move left along tree

   inc hl
   ld a,(hl)
   inc hl
   ld h,(hl)
   ld l,a             ; hl = root.right
   jp nextcodebit

.goleft
   ld a,(hl)
   dec hl
   ld l,(hl)
   ld h,a             ; hl = root.left
   jp nextcodebit

That's it sans decoder tree.

The main bit of huffman compression code:

; Static Huffman Encoder
; Alvin Albrecht 03.2003
;

XLIB SPHuffEncode

; enter: hl = addr of encoder array (array indexed by symbols pointing at decoder tree leaves)
;         c = symbol to encode
;        de = memory address to write encoded symbol to
;         a = next bit in de to write to (bit mask)
; exit : hl = memory address to write next encoded symbol to
;         c = next bit in hl to write to (bit mask)
; uses : af, bc, de, hl, b', de', hl'

.SPHuffEncode
   ld b,0
   add hl,bc
   add hl,bc         ; hl = &encoder[c] contains pointer to symbol's leaf node
   ld c,a            ; c = next memory bit to write to
   ld a,(hl)
   inc hl
   ld h,(hl)
   ld l,a            ; hl = decoder tree leaf for symbol
   push hl
   exx
   pop hl            ; hl = decoder tree leaf for symbol
   ld b,0            ; b = # of encoded bits on stack

.encode
   ld e,(hl)
   inc hl
   ld a,(hl)
   or a
   jp nz, notdone    ; if parent of this node is NULL (msb), done encoding!
   ld a,b            ; a = # of encoded bits on stack
   exx
   ex de,hl          ; hl = memory address to write symbol to
   or a
   ret z             ; if no encoded bits, return done

   ld b,a
.writeloop
   pop af
   ld a,c
   jr nz, encoderight
   cpl               ; encode a left movement in tree by writing a 0 bit
   and (hl)
   ld (hl),a
   jp cont
.encoderight
   or (hl)           ; encode a right movement in tree by writing a 1 bit
   ld (hl),a
.cont
   srl c             ; move to next bit in memory
   jp nc, cont2      ; if byte still not filled
   inc hl            ; move on to next memory byte
   ld c,$80          ; start with first bit in byte
.cont2
   djnz writeloop
   ret

.notdone
   ld d,a            ; de = parent node
   inc de
   inc de            ; de = parent.left
   dec hl            ; hl = child
   ld a,(de)         ; find out if hl is a left child or right child
   cp l
   inc de            ; de = parent.left+1
   jr nz, foundchild
   ld a,(de)
   cp h
.foundchild
   push af           ; save: nz = right child, z = left child
   inc b             ; one more encoded bit on stack
   ld hl,-3
   add hl,de         ; hl = parent
   jp encode         ; on to the next encoded bit

with the statistical stuff written in C. Of course I don't know how it all works anymore or if it even works (it was never really tested but I tend to write bugfree code too ;-P ).

The point is it'snot hard and it's not big in asm (not including the tree). I never even considered dictionary compressions since I didn't think it would work too well if you wanted random access to individual bits of data on the go.

I was not the only one to implement such a thing here, I remember a coupl eof others taking about their z80 implementations over the years.

csmith

Alcoholics Anonymous wrote: »

Of course I don't know how it all works anymore or if it even works (it was never really tested but I tend to write bugfree code too ;-P ).

Isn't that always the way ;-)

I was not the only one to implement such a thing here, I remember a coupl eof others taking about their z80 implementations over the years.

Well, we should start an archive. This kind of thing is really useful and does not come up that often for people to remember what's good and what's not, or have working examples to hand.... Unlike sprite code and stuff which is _always_ discussed ;-)

csmith

Just dug out some LZW code (in C) that I could probably Z80 asm pretty easily... Will give it a go when my brain melts from all this writing...

Paradigm Shifter

Agree about the sprite code.

We always have gamedev.net as backup, I was thinking of asking them if they would do a retro forum, but I have only just logged on today after several years ;)

EDIT: http://www.gamedev.net/community/forums/topic.asp?topic_id=563232

joefish

My scheme for a generic Speccy compressor, that I thought about on the way home tonight. Apologies if any of it seems too generic or too obvious, but please chip in wth other suggestions as I know sod all about compression; just what could be useful for games. It's intended to be a fairly comprehensive spec. I can see I was thinking along the same lines as csmith.

Decompressor.

A1. I think it would help to settle on one algorithm that gives good compression and a fast, compact Z80 decompressor.

A2. It should be able to decompress distinct chunks from a single compressed data block, using a single common encoding tree / dictionary.

A3. It should also be easy to adapt the decompressor to work linearly and incrementally, so we can run it until we get X bytes (or just over) from a given chunk, then save its state and come back to it later for more. (I don't mean just decoding lots of little chunks here - I mean the ability to stop mid-stream).

GUI/Script

B1. The compressor should come with a PC GUI, to prepare a config script to gather the files for compressing.

B2. The actual compression should be done by passing this script file to a command-line executable. The GUI can then invoke this command-line executable. That makes it all a bit more versatile and portable.

B3. In the GUI, you select one or more files that you want compressing together. The order of the files is remembered, and can be manipulated up/down. Each file is intended to be compressed as a distinct chunk of data, but with a common decompression tree. You can also specify further sub-divisions of each file into smaller distinct chunks.

B4. Each file is one of three (initially) basic types; ASCII text, binary data and indexed binary data. Plain text is just ASCII to be compressed (although \r\n will be replaced by CHR$(13) in the compressed data). Binary data is just raw bytes.

B5. 'Indexed binary' files have the following form:
1 byte = number of chunks n
2 x n bytes = offset from start of file to start of each chunk. Length of chunk is inferred from the offset to the next chunk, or the end of the file.
Remaining bytes = chunked binary data.
This is for, for example, sprites of varying sizes, or individual maps of different areas. Each sprite or map is one 'chunk'.

B6. For each text file, you can also specifiy an optional separator character. The text will be split up into chunks based on this separator character. The actual separator character (and any \r\n immediately before it) does not appear in the resultant compressed data.

B7. Similarly for binary files, you can specify an optional fixed 'chunk size', e.g. '32' for 16x16 pixel-only sprites. The compressor will then treat the entire binary file as a series of chunks of this size. (There is no optional setting for the 'indexed binary' file type).

B8. Or if you don't want to use chunks, you can set a global option that ignores all these extra settings, concatenates all your files into one stream and compresses that.

B9. You then specify an output file, an optional report text file, and set two options, if you want the number of chunks, and the chunk offset table, to appear at the start of the file (as per the 'Indexed Binary' file format, above).

Compressor

C1. When run, the compressor should pool all the files together and create a single optimised tree for all the files and chunks.

C2. It should then compress each file, or each defined chunk of each file, into separate and distinct streams of bytes. These are all then concatenated, in order, into a single binary file. (I know this will waste bits as padding at the end of each chunk, but byte-aligning will make accessing them a lot faster. If you don't want to use chunks like this, you could just specify a single stream).

C3. The number of chunks (optional), the offset to the start of each chunk (optional), and the decoding tree are added to the start of the data block, then all is saved as a single binary.

C4. If required, a report of progress (including the file/chunk before/after sizes and indexing data) is produced as a text output file.

C5. The decompressor can then be given the address of the decoding tree/dictionary and the address of a compressed chunk, and it will decode that chunk.

More than one tree

On this, I thought if you wanted a separate tree, you could build a separate file. Or the GUI could let you add a numeric field to each file, to tell it to use tree 1, 2, 3 etc. Or the GUI could have a tree control, and you group like files under a top-level heading which denotes the tree.

Winston

Actually, what I'm after is a decompressor that does ZIP so I can decompress zipped TAP files on the Speccy... memory shouldn't be too much of a problem for my application as I have some extra :-)

Paradigm Shifter

Re: gamedev - moved to ideas and suggestions, but some encouragement.

jamorski

Where would we be able to find details of pmc by Paolo Ferraris?

Fikee

jamorski wrote: »

Where would we be able to find details of pmc by Paolo Ferraris?

http://starbase.globalpc.net/~wyndex/mini03/index.main.html

download ZDBlast, check sources. in 2004 it was used to pack 4K RACE too.
for some details check 2003, 2004 minigame bbs, paolo describes algorithm he used in some thread. dont remember where it was, you have to dig it.

joefish

Paradigm Shifter wrote: »

You need the data length in bits for a decompress, so you can do that with a list skip rather than storing offsets. Slow, but probably not too slow to cause headaches.

How about a compromise where you put all the sprites for a character in a single chunk, then index to that chunk with a byte address and decompress it all? For example, for something like Gauntlet you may have 8 directions, 2 frames walking, one frame shooting, and 8 directions for the shot. That's 32 sprites at 32 bytes each so 1K per character. Then you make it so that the character data is stored in 1K chunks compressed individually.

If you want to do incremental extractions, would you also need a limit on the maximum size of a word in the data dictionary, so you know how big a rolling buffer you need to leave to work with?

Tom-Cat

A very nice compressor :

http://retrospec.sgn.net/users/tomcat/yu/ZX/Utils/Html/FileCompressor.php

does a good job at compression, decompression is VERY fast and it does auto-reloc of the decompressor, etc.

Dr BEEP

I was wondering why you want to compres.

As for MiniGames, well that's obvious.

For really large games I would say compress all levels/screens and only decompress the level/screen you are at.

If it's for loading only and you decompress all data after loading, I fail to see the emergency of compressing. OK it saves some time, but on an emulator you don't really notice this. As for size, OK so it saves some space on a disk/tape or whatever.

But back to compressors:
I myself never use a predefined compressor, but make my own (de)compressor per game by selecting the right routine needed for my program.

Some examples:
123Maze (1K) holds 26 puzzles from 10x10. Compression is done by storing 4 fields in a byte and unpacking this (4 values possible)

Lingo (1K) holds 300 5 letter words by using Huffmann.

Worldbar (2K and 4K with AI) holds a screen that is built from all kinds of repeating strings (i.e INK 7, PAPER 8, " " or INK 6, PAPER 2," ") which are numbered and called with a printroutine to print the nth string.

SOKOB-ONE (1K) holds 26 levels of Sokoban differently sized.
In 1 byte up to 4 positions with 8 possible values can be stored (8 values = 3 bits, 4th bit used as valuerepeater)

In Stratego (now working on) I have compressed and uncompressed graphics. The compressed graphics decompress AFTER the uncompressed graphics so I only need to set UDG or CHARS once.

So I would like to see WHAT you want compressed and think a special compressingroutine over for it.

csmith

Dr BEEP wrote: »

So I would like to see WHAT you want compressed and think a special compressingroutine over for it.

Graphics mainly, and room data (which will already have been optimised to use as little space as possible).

The general theory (well as joefish and I have declared) is to compress everything as one stream to improve the compression ratio (theoretically), but to chunk the actual compression stream to allow individual sprites and screens (or groupings of) to be cherry picked and decompressed when needed.

No one is planning to compress in-game. Only decompress.

Using the same compression for all the chunks allows you to have one dictionary, or similar, depending on the compression algorithm used.

Edit: You have to think of the data you're compressing as being arbitrarily random, and assume that it has been optimised, which it should have if you're worth your salt.
(By random I mean not data that you can spot patterns in by eye. Compressors will be able to of couse, as that is how they work ;-) Real random data will compress terribly!)

csmith

With regards to compressing, can we have tools written in C that will run on the command line?
The guts could be a library that a GUI can use as well as the command line tool.

Not everyone has a computer that runs windows, so a windows GUI app is not so useful ;-)

Plus the compression could then be built into Makefiles as part of the development environment.

evilpaul

This is sounding like the optimisation thread.....

In my currently-shelved-but-at-the-fully-working-prototype-stage Speccy platformer game, I compress each level's graphics in one chunk, and then each individual room in it's own chunk. I could go crazy and figure out a custom compression scheme that would no doubt save me bytes but.. well.. what I've got works well enough that I no longer have memory issues and the decompression speed is not a worry either. For me it's much more important to get things working before I worry too much about the size or the speed of the tech.

So remember:

1) Don't optimise
2) Don't optimise - yet
3) Only optimise something that you know is slow (preferably, only optimise something that a profiler has told you is slow).

Just replace "slow" with "taking too much memory".

Paradigm Shifter

Yeah I agree compression shouldn't be done for giggles only ;)

I think a command line program is best option for compressor since you can whack a GUI on top if you want to.

Paradigm Shifter

csmith wrote: »

With regards to compressing, can we have tools written in C that will run on the command line?
The guts could be a library that a GUI can use as well as the command line tool.

Not everyone has a computer that runs windows, so a windows GUI app is not so useful ;-)

Plus the compression could then be built into Makefiles as part of the development environment.

No PC that runs windows? I hope you have Wine or whatever it is called.

Otherwise how can you play Civ IV? :-o