What is the best routine for graphics compression?

[alexeym]

Hi. I'm looking for a Mac or Windows tool to compress ZX Spectrum graphics (not only full screen .scr images but also sprites) and routine which would decompress the data and put the decompressed sprite (3x2 chars or 24x16 pixels) to x,y coordinates (1-32, 1-24). I wonder what is the best routine for that?

[djnzx48]

You could try these articles:

http://hype.retroscene.org/blog/dev/740.html
http://hype.retroscene.org/blog/933.html

[alexeym]

Awesome links. Thank you so much!

[Ralf]

If you ask me about drawing sprites, then the best compression is no compression at all

Any data compression will slow down your drawing routine. And speed is in most cases critical. Make your sprite drawing just a little bit slower
and you'll discover that everything doesn't fit into a frame, that your framerate drop from 25 fps to 17 fps for example, making your game 50% slower.

Both speed and memory are issues on Zx Spectrum but I would say speed is a bigger issue.

[alexeym]

The game is kind of static (no animation), so that's not a problem.

[Einar Saukas]

Even if performance is not a problem, compressing individual sprites won't provide very good results. Your sprites will compress better if you divide your sprites into small groups (preferably putting more similar sprites together in the same group), then compress each group. Later during the game, you would decompress one of the groups into a temporary area, before copying the required sprites to the screen. Notice it will take some experimentation to find out the best trade-off between group size and compression ratio that works best for you.

For compressing small blocks, you should get good results using ZX7. There are more sophisticated data compressors available for the Spectrum, but they are typically focused on compressing larger data blocks with several Kb each. In comparison, ZX7 is focused on compressing smaller blocks (although my suggestion above still applies!), also it decompresser faster, it doesn't require additional memory, and the decompressor size is smaller than others.

To compress full screen .scr images, I'm sure you will get the best results using RCS+ZX7 combined together. Moreover the "Smart" version of the decompressor can both decompress a full .SCR (compressed with RCS+ZX7) directly to screen, and also a block of sprites (compressed with ZX7) to the temporary area I mentioned.

[Einar Saukas]

You could try these articles:

http://hype.retroscene.org/blog/dev/740.html
http://hype.retroscene.org/blog/933.html

I remember reading the first article a couple years ago, but I didn't know there was a follow-up. These articles are awesome!!!

Both articles are very well thought, well researched, and well written. It was a real pleasure to read an in-depth analysis like this.

My only (constructive) criticism is that I don't think these scenarios are practical enough for the Spectrum. For instance, the first scenario consists of 8 files extracted from the "Calgary" test. However most of these are text files larger than 38Kb. It would never make sense to decompress such a large block of text into the Spectrum memory at once. Especially considering that there's not even enough room to fit both the compressed block and the decompressing memory area in 48Kb! Even in a very large text adventure for the Spectrum 128K, a text block to be compressed would never exceed 16Kb. As a matter of fact, in practice text blocks would be typically much smaller, because whenever a Spectrum program contains a lot of text, it's better to use simpler text compression strategies and avoid data block compression altogether...

However I'm not implying the articles are flawed. I'm just pointing out that the article is oriented towards compression of larger data blocks. The selected set of files in the article contains 77 files, with total size of 1,233,995 bytes, therefore an average of 16,026 bytes per file. But I believe the most typical usage of data compression in Spectrum programs is to compress relatively small data blocks, from a few hundred bytes to a few Kb. At least that's what I always needed in my own Spectrum programs, and that's ZX7 main strength. My point is, the article conclusions make sense, but they don't necessarily apply to compressing smaller blocks of data.

Another point is that data compression specifically for Spectrum screens, using RCS+ZX7, was not measured. The "Graphics" scenario from the article consists of 30 files, including 19 Spectrum screens. Using only ZX7, these 19 Spectrum screens compress to 93,969 bytes and the remaining 11 other files to 78,171 bytes, a total of 172,140 bytes (59.37%). But using RCS+ZX7 for these 19 Spectrum screens instead, they compress to 81,849 bytes, reducing the total to 160,020 bytes (55.19%). That's better than all other results in the article! Although I understand that including RCS was outside the scope of the articles, that's perfectly fine.

[Sokurah]

In Vallation I'm only storing enemies as 16x16 frames, then when you change screen it'll take a few of those and shift them into 24x16 images before the next screen is shown. This way I can pack in more enemies. But as mentioned before, actually compressing the spritedata doesn't seem like an option that would yield much space. And certainly not something you'd want to do for something drawn on the fly ... if you know what I mean.

[catmeows]

As a matter of fact, in practice text blocks would be typically much smaller, because whenever a Spectrum program contains a lot of text, it's better to use simpler text compression strategies and avoid data block compression altogether...

I agree. Typical text message would be just few lines of text long. No LZ method can compete dictionary in such case. I have really good experience with byte pair encoding that can achieve about 50% compression for english.

About ZX7 - I quite agree with the article. The match/literal flag bit is a mistake and elias encoding (probably) too. When you look ať modern byte based LZs like LZ4, LZ5, LZF they are much faster and not much worse or same as ZX7 and their offset size is tuned for rather big files. A modern "8bit" byte based LZ could probably offer more than ZX 7.

[Joefish]

This is the problem with data compression on systems with not a lot memory - you need to compress a large amount to get good efficiency, but also that you can't unpack bits of it at a time because it needs to be able to refer back through previously extracted data to point to repititions, which is where the savings come from.

One option you might consider is compressing up to 6K of data at a time. You can then unpack this to screen memory (with the attributes blanked out to hide it), copy out the sprite or level data you need, then wipe the screen again.

And as Sokurah says, if your sprite data is pre-shifted, undo the pre-shifting before you compress as this will lead to far more repeated bytes and better compression. Up to you whether that means your sprite frames shrink from 24x16 to 16x16, or whether you leave them as 24x16. But you will need an efficient re-shifter routine to set them back after they're extracted, or the saving won't be worth it.

And as Einar says, a routine to re-order screen data to line-by-line can improve screen compression, as it makes the repeated parts of a screen closer together in memory, so the compressor is then more efficient and picking up on repetitions.

[Joefish]

Another problem with compression - it's fine if you've got a ROM cartridge or disk to store your compressed data, but if you have to hold it in RAM and hold the expanded version in RAM then you have to decide if it's worth it.

For screens, you can uncompress them straight to the screen memory, so it's not a huge issue. But for game sprites, data, etc. you really need to be achieving 50% compression or it's just not worth it.

For example, if you have two levels in a game and each is 2K of data, that's 4K in total. If you compress it, you're still going to need 2K of unpacked live level data for your game. Now if you can pack your level data by 50% such that each level is now only 1K, then your 2K of live upacked data plus 2 x 1K of compressed data takes up the same space as before, 4K, so you've just broken even.

Now four levels would have taken up 8K, but now take up only 2K + 4 x 1K = 6K, so now you're saving memory. But if your compressed level data isn't shrinking by much, then it's not worth it.

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

I've been doing some experiments with Einar's code as I've now got it into my head to compress the title screen of Go-Go BunnyGun and use it as an attract mode even in the 48K game, and even though I'm already running short of memory!

Using the linear screen re-arrangement helps the compression, but an algorithm I wrote myself also helps. That works from the bottom of the screen up, XOR-ing each line with the one above. So where the line is the same as above, you just get empty pixels. It doesn't help on highly detailed screens, or ones with lots of stippling, but for a manga-style image like mine with vertical lines and big blocks of colour, it leaves large blank areas and shaves a few hundred bytes off the compressed screen. Which is now down to under 4K.

What I want to do is try some experiments to see if I can optimise the image itself for compression; maybe reducing the detail a bit as well, and see how significant that is in the compressed file size.

I'm also trying to work out if it's worth compressing the sprites individually or as a block. An 8-frame sprite animation is 720 bytes, and some have only minor changes between frames, so 50% compression is readily achievable. That improves a little if I concatenate several sprites in one block, but makes it more awkward to unpack and extract the ones I want for a level.

Of course, sprites common to all levels (explosions, weapon pod) shouldn't be compressed at all as that would just be a waste of memory.

[Joefish]

Hmm - I seem to have written a compression routine that actually runs on the Speccy itself and compresses my title screen even further, down to 3742 bytes. (The re-rodered ZX7 encoding gave 4247 bytes). Not sure how well it'll fare with other screens, but for the sort of thing people had drawn for the recent Hobbit update - lots of lines and large patches of colour - I suspect it could be pretty good. Though I need to verify it is doing everything reliably and I haven't made a big mistake somewhere. And that's still a big chunk of memory that wouldn't be available to the game!

I need to optimise the cack out of the post-processor stage and probably the decoder too. It's not massive, but I'm no expert and writing super-efficient code.

I want to see if I can do something more efficient for my sprite data too, though it (like my screen code) would take advantage of a bit of knowledge of the sprite format. I've got an idea for improving the encoding of back-referencing small sections of repeated runs in small blocks of data. The question then is whether using two or more custom encoding systems saves enough memory to have more than one decoder programmed in...

[Ast A. Moore]

I use RLE for the title and the award ribbon in Yankee. I simply count empty (zero) bytes in vertical rows and write down the number of consecutive empty bytes. The decompressor is very fast and it saves quite a few bytes in images that contain a lot of blank bytes. I do decompress them directly onto the screen, so it’s worth it.

You could, I suppose, apply compression to some level data. If you then always decompress it to the same pre-allocated portion of RAM, it seems like a viable option. Maybe you could also pre-populate that area with some graphics, if you’re going to regularly copy them onto the screen. Then again, sprite graphics usually don’t compress well.

[Joefish]

Well, I refined my earlier idea of XORing rows and added a function to calculate the row addresses in pixel order. So each pixel row is XORed with the one above. And similarly, the attributes sweep backwards one byte at a time, XORing with the previous byte in memory. The result of this is that repeated data gets turned into lots and lots of zeroes. Large blocks of pixels become just a line across the top and a few dots down the sides. Stipples become alternate solid and clear lines. I then use a 0 bit in the compressed data stream to encode a zero byte, so the more of those can be generated the better. Everything else is encoded with a 1 followed by further data, that is either literal bytes, or a limited dictionary of the most common values. I tried a full dictionary but it wasn't worth it - it took too many bits to identify an entry compared to just supplying a literal byte value. That might be a useful approach for text compression too, rather than encoding a full dictionary. And has the advantage that you could decode any part of the data at any time, since there are no back-references.

My earlier one for title graphics - you might like this - takes advantage of the fact that no-one ever uses the FLASH bit. For each character, the attribute comes first. If there's no FLASH bit then the next byte is an 8-bit mask. This tells you for which bytes in the 8 rows of the character there is data to come. Set bits in the mask use the next byte in the data stream for the pixel byte. Any blank bits in the mask result in a 0 byte being written. So a full character takes 10 bytes. But a half-character only 6. The trick is that if the FLASH bit is set, it's first stripped from the attribute, but then the pixel mask byte is re-used from the previous character. So it might encode the same pattern of bytes present in the character, or if the mask is 0, then another empty character is drawn. It simply eliminates all the blank bytes in an image. And it does it using whole bytes, rather than faffing around with an arbitrary stream of bits. I think I also had a set of bytes for each line where each bit meant 'copy the previous attribute and process accordingly'.

[Morkin]

My earlier one for title graphics - you might like this - takes advantage of the fact that no-one ever uses the FLASH bit. For each character, the attribute comes first. If there's no FLASH bit then the next byte is an 8-bit mask. This tells you for which bytes in the 8 rows of the character there is data to come. Set bits in the mask use the next byte in the data stream for the pixel byte. Any blank bits in the mask result in a 0 byte being written. So a full character takes 10 bytes. But a half-character only 6. The trick is that if the FLASH bit is set, it's first stripped from the attribute, but then the pixel mask byte is re-used from the previous character. So it might encode the same pattern of bytes present in the character, or if the mask is 0, then another empty character is drawn. It simply eliminates all the blank bytes in an image. And it does it using whole bytes, rather than faffing around with an arbitrary stream of bits. I think I also had a set of bytes for each line where each bit meant 'copy the previous attribute and process accordingly'.

That's quite good.

I guess depending on what you're printing, e.g. if it's static graphics, you could also use the BRIGHT bit for something as well? Not sure what.

[TomD]

I created a compression routine for exactly this purpose, being able to compress "cutouts" of the screen for titles or small blocks of graphics for intros but can be used for anything. You can read more about it here http://www.tomdalby.com/other/lzf.html

It has two modes for the "cutouts", static and moveable. If you need to move the "cutout" each time you paste to screen then moveable should be used and the only real difference is the decompressor is larger at 151bytes vs. the static version at 92bytes. Full screen is also in the utility.

Any questions let me know.

TomD

[TomD]

If you want to see an example of it working try this https://tomdalby.com/speccy/cobra_w.tap

[catmeows]

[Bedazzle]

What about megalz packer?

[catmeows]

What about megalz packer?

https://github.com/emmanuel-marty/lzsa/ ... /README.md

Here is quite handy chart showing compression/speed ratio.

[Joefish]

Generic byte packers aren't always the best at compressing graphics though. If you can take advantage of some knowledge of how graphics data is more likely to repeat, then you can optimise the compressor to pack that data. Einar's re-arranges a staggered Spectrum screen to line-by-line order to bring potential repetitions closer together, which makes them easier for an LZ77-type algorithm to compress. My alogrithm pre-processes the graphics to turn common repetitions into zeroes, which my packing routine can optimise above all other values, a bit like a RLE algorithm would do.

[Joefish]

Hmm. Just been meddling with a screen compressor that gives some really good results on the selection of screens I was using. It gets Einar's Cobra pic down to just 1945 bytes. But try it on that pack of Russian screens and it's not so good. It 'compresses' MAC's Phantis screen 'down' to only 7123 bytes! (that's more than it was originally, in case you didn't notice)

But on a couple of examples like that BatmanTheCapedCrusader I get 4957 bytes compared to 5457 (I think) for RCS + ZX7
It works best on patches of colour and lines - multiple levels of stipple and colour changes just make it worse. It might be good for something like that Hobbit update.

I should probably tweak the algorithm so it just stops trying when faced with too much changing data...

[catmeows]

How it works ?
Honestly - a decent benchmark suite of screens would really help. And I don't mean just full size screens but also in-game illustrations, for example from Case of missing swan and even smaler examples, something of size 6*6 chars like pictures from Rychle Sipy.

[Joefish]

Well, with smaller graphics there's the question of whether you're expecting to compress the data that makes up a small graphic, and what order the bytes for that are in, or whether you mean to paste the graphic onto an otherwise empty screen and compress the whole screen. As they're different tasks. A whole screen has a fixed format that you can exploit. Maybe known sized graphics have formats that are exploitable too. But arbitrary data of variable length is something different.

My 'MiniDict' technique is to XOR each attribute with the one before, which turns repetitions into zeros.

I then XOR each pixel line with the one above, which again reduces blocks of pixels to just lines and dots around the edges. (What it's not good at is stipples).

Then I do a frequency analysis of what's left, and pick out the 16 most commonly used bytes (other than 0). Again, this takes advantage of the dots that are left by the XOR process.

The encoding is a bitstream as follows:

16 x bytes - common byte mini-dictionary
0 bit -> 0 byte
1,0 bit -> read next four bits, look up byte in mini-dicitonary
1,1 bit -> read next 8 bits as literal byte

I've just added a refinement that after six 0 bits, it then either flags a 1 to continue otherwise it contains a binary number of how many more zero bytes to skip. This helps it skip over large blank areas of the screen. I can post some code later. But it actually runs on a Speccy. Or at least, in an emulator.

[Lethargeek]

To compress full screen .scr images, I'm sure you will get the best results using RCS+ZX7 combined together.

Nope. Let me remind you of this 3 years old wos thread:

https://www.worldofspectrum.org/forums/ ... compressor

ZX7 (RCS or not) like other Spectrum screen compression tools i'm aware of all have one fundamental flaw: they compress bytes (ie strips) instead of square chunks. In most cases squares have better correlation between the pixels, hence better possible compression ratio.

Also chunky methods are better for compressing small size pictures (ie sprites) - even separate ones. Me planned to write a sprite compressor as well using similar approach but got distracted by other projects and everyday problems.