DAN0 - My proposed compression algorithm

[newcoleco]

Instead of taking time to talk in details here what is this algorithm, I've done a PDF file in my blog at the following link that includes technical details, source codes, real test results, and all in simple words :

 

http://newcoleco.dev-fr.org/p4198/2010-03-18-algorithme-de-compression-dan0.html

 

For our needs, a simple RLE is well enough, like the one proposed by Marcel de Kogel in his original Coleco library that I'm still using today in my personal Coleco development kit. However, a better compression gives us more space for encoding more stuff in our projects.

 

Yes, I did look at other solutions proposed from Commodore and MSX scenes, including PuCrunch and a few others. I did appreciate the smallest one named Bitbuster, and overall I was thinking that I should done my own algorithm because none of them put RLE on the front, but somehow gets the advantage by an happy consequence of dictionnary compression. Because RLE is the fastest one, I've decided to keep it and try to improve its result... even if it makes it a little bit slower.

 

Overall, the compression algorithm I'm suggesting here can offer an extra 2% of bytes saving compared to a straight RLE by trying to compress the data part of the RLE encoding with a fixed Huffman encoding table, all in a single pass routine. Because it's a fixed table, it's not the optimum encoding all the time, but better encoding is well enough considering that more nuances need more bytes to encode in the decompression routine.

 

And, I've done some progress during the last nights, while writing the documentation, for a tool based on this algorithm. If it works fine, and if I can find back the source code of my graphic tools made last year, I'll be able to include the new compression built-in the graphic tool to make it simple even more simple for you to use it.

 

! Warning ! : If you use this work for your own projects, please credits properly. Thanks!

[+retroclouds]

Even though I'm not a colecovision coder (yet), I have read your PDF with much interest

 

Cool stuff

[newcoleco]

* Erratum *

 

Someone said to me that, it was not a good practice to manipulate interruptions with di and ei instructions while dealing with VPD routines. Well, I did learn that by looking at the end of the ROM Destructor where the calls to VDP routines (in BIOS) are encapsulated with di and ei instructions. My guess is that they didn't want the steering wheel interruption to interfer with VDP calls, not necessary to avoid a bug, but to avoid making them slower than they should be and then causing potential video corruption while trying to change video ram outside the safe window of time. Anyway, I've decided to follow the advice and cut the di and ei instructions everywhere in my library and in the codes based on my compression algorithm DAN0. So, a new updated PDF file should be uploaded today.

 

* News about another compression algorithm for Coleco projects *

 

Someone is working on a simplified version of PuCrunch by not using the part of variable length encoding (Huffman, Gamma, etc.) but still use the idea of escape codes and dictionary compression (lz77, lz78). The author of this new algorithm confirms that the main objective is to get a strong compression without using much cpu time and ressources. His first version of the decompression routine is about only 160 bytes, which is bigger than DAN0, but he's trying to optimize the code as much as possible before releasing it. The estimated compression result is cutting up to half of the data normally needed for a simple RLE, like the one proposed by Marcel de Kogel in his Coleco library (1996-1997).

Edited March 20, 2010 by newcoleco

[newcoleco]

I've find back a version of my graphic tool... not sure if it's the good one... anyway, I'm still working on a routine to compress data based on my algorithm. And, I've released an updated version of my PDF documentation, based on a new routine source code (appendix 3) faster than the previous version. And yes, I did get rid of all the "di" and "ei" instructions.

 

And, I've got news about the other algorithm in development based on PuCrunch and apparently the tests are showing a gain around 5%-10% over DAN0 results. So, it's not a cut of 50% over RLE like expected, but it's still a much more powerful compression algorithm. I'm keeping an eye on this new algorithm in the hope of integrating it into my graphic tool.

[newcoleco]

I did try another algorithm based on dictionary compression instead of huffman encoding. Also, I've decided to be inspired by PuCrunch and try using an escape code instead of adding bytes everywhere to indicate the RAW parts. And to avoid the need of extra memory, the dictionary is the compressed data. It's not the maximum compression I'm trying to reach with this idea but to simply avoid a too complex routine with a big ram usage (256 bytes in RAM is big considering there is only 1KB inside the ColecoVision). I don't have results yet about this new algorithm but I can tell you that the decompression routine in its simpliest form is 6 bytes smaller than DAN0 and gives a faster execution too. I've called this new algorithm DAN1... to be added in my PDF file eventually.

 

 

Decompression routine size, from big to small : DAN0 (101 bytes), DAN1 (95 bytes), RLE (54 bytes).

 

Decompression routine speed, from slow to fast : DAN0, DAN1, RLE.

 

Compression ratio : DAN0 compress more than RLE. And (I suppose, not tested yet) DAN1 compress approximately as well as DAN0.

 

 

And if we want to compare with other algorithms like BitBuster, I can only compare the size of the routines I was able to convert myself (sort of) for ColecoVision projects, but you can already assume that all the other decompression routines are slower, bigger and need more memory (ram) than my proposed solutions.

 

 

Decompression routine size, from big to small : RNC2 (236 bytes), Pletter (221 bytes), BitBuster (173- bytes).

 

Decompression routine speed, from slow to fast : RNC2, Pletter, BitBuster.

Edited March 22, 2010 by newcoleco

[+GroovyBee]

How does your compression routine compare against the GIF and PCX algorithms for size/speed?

[newcoleco]

How does your compression routine compare against the GIF and PCX algorithms for size/speed?

 

I can't tell really there is actually no GIF or PCX format supported for the ColecoVision... well, that's not correct because one source of information told me that there was some efforts done, back in the late 80s or the 90s, to read other image formats for the Coleco ADAM computer like one to display a GIF picture with a lot of effort and tricks to be efficient enough to display the result as good as possible in a fair amount of time. You've have to consider that a format like GIF is not made to be efficient for ColecoVision pictures because it's not based on the kind of image format and resolution this system can handle. So, there are disadvantages of using a format not adapted. For example, the Miss Space Fury title screen you can see in my documentation (PDF format) is a 256x192 GIF file, around 4 KB size, and the same picture compressed to be displayed on ColecoVision is less than 3 KB.

 

As for the size and speed of decompression routines, I can't tell because I've no routine for GIF or PCX decoding runnable on Z80 cpus, but they are certainly a lot bigger in size and need a lot more memory to execute. I'll also argue that even if some parts can be estimated as having the same speed in theory, DAN0 is simple enough to be faster than the other ones.

 

But DAN0 is not an algorithm strickly for pictures, it's just that the large memory space available for the ColecoVision is the one in the video, but you can use DAN0 to encode text and other data that you may want in video memory, like my project GhostBlaster using part of video memory to store the current level data.

 

 

* Update *

 

And, I stop investigating DAN1 algorithm because the actual tests are showing results worst than DAN0 and sometimes worst than RLE (which is not acceptable).

[+GroovyBee]

Do you have any links giving information about the graphics data format on the ColecoVision?

[newcoleco]

Do you have any links giving information about the graphics data format on the ColecoVision?

Inside ColecoVision, and some other machines, the video chip is a Texas Instrument TMS9928. There are 4 different video mode, each one with its own properties.

 

I've done at least 2 videos concerning the video chip TMS9928.

 

The most used graphic mode is named Graphic Mode 2, which is the hi-resolution one : a nice and colored 256 x 192 pixels.

Bitmap screen in this mode is composed of only 12 KB of data : 6144 bytes for the PATTERN table, and 6144 bytes for the COLOR table.

 

There are technical details about this video chip, some by Texas Instruments.

[+retroclouds]

@GroovyBee: For the technical details on the 9918 VDP you can checkout this thread.

 

Look for "TECH MANUALS -> 3. Others -> VDP Programmer's guide"

 

**EDIT: Fixed broken URL**

Edited March 23, 2010 by retroclouds

[+retroclouds]

@newcoleco: Are you planning on creating a PC based packer utility like they have for bitbuster ?

[newcoleco]

@newcoleco: Are you planning on creating a PC based packer utility like they have for bitbuster ?

I'm just saying in this thread : "I've done some thinkings lately and I wanted to share it with you; it's another compression algorithm and this is the concept behind it. Use it for your projects if you want so, or even adapt the concept for your own needs."

 

Making a packer will impose to fix the format, it'll also somehow impose to use binary files into Coleco projects, which I don't want to do. But, even if I don't think I'll do one myself, I've no problem if someone else want to make one : the compression algorithm is documented and it can be used "as is" or not.

 

Why I think that I should not do a general purpose packer based on this format?

 

A first thing that bugs me about doing a general purpose packer like those done for BitBuster, RNC2, and many more is about generating binary files. Using binary files into a format that maybe will change or simply not survive the test of time is, in my opinion, not a good idea. A file written in a way to give the key for using these encoded data is more appealing to me than a binary file that doesn't say much except "I look like garbage because I need to be decoded". Also, it may sounds strange to you but the way I'm programming my games doesn't use binary files, but generated C and ASM listings made by tools like those to convert pictures and make charsets. Why? because after generating these listings, I can manipulate them and this work of precision cannot be achieved if the data I want to modify is inside a binary file.

 

A second thing that bugs me about doing a general purpose packer is the way DAN0 can be slightly optimized by packing multiple data tables. To do so, and keep track of every data tables, it'll need to manipulate a table of pointers to identify each part all mixed together into a single file, almost like for a ZIP format. By doing so, a generated DAN0 archive file cannot be included as is in a project, making the packed data bigger for no good reason. The generated archive will need a tool to be converted in a format that a programmer will be able to understand and use in his projects; like using the text and pointers informations for labeling tables in a structured ASM encoded file. Doing a conversion tool to get an ASM listing seems not to be a big deal, except that the ASM listing may not be in the appropriate format for the ASM compiler the programmer want to use. So, I prefer then to make a tools that fits my needs and share the results, instead of making a more general packer that may not be used much at all and need to be update constantly to keep being used.

 

With all that said, I did program to test the proposed algorithm by decoding and then reencoding data tables in Marcel de Kogel's RLE format. This is why I was able to give you the first interesting results based on the proposed algorithm and compare them with the original RLE encoded data. The program is written in Java and the tables are hard coded into the program, and it's also adapted for the pictures tables, so it's not useful at all except for testing and maybe for some conversions like the one I plan to try for fun later.

[newcoleco]

I've tried an extreme case, trying to compress 13 tables into DAN0 format. My compressor algorithm is trying all the 6227020800 possibilities of sequences to encode them, in the hope to find THE sequence (order) to compress these tables to save the most bytes by using the "stealing bytes" effect. Because it's a very long process, my test is still running after hours... well, I didn't say that I can do a compressor optimized. Anyway, by logic, this method will simply try to save up to 10 bytes for each compressed table excepted the first one. The experimentation is running actually... about an hour of calculation done and not half of the cases done yet, it will probably runs the entire night.

 

Of course, this kind of situation of encoding 13 tables in a Coleco project will be pretty rare, because the normal number of RLE encoded tables in a Coleco project are not much : bitmap picture (count for 2 tables), charset (count for 2 tables), and one or more screens (count for 1 table each), and sprites (1 table)... so, it's about 7 tables to compress... which don't take much time even with this not-optimized compressor I've done.

 

I can't give you the compressor because it's not well done, not commented, source code only, no interface, and you need to code your tables to compress inside the application, or encode your method to load files with it.

 

Anyway, I've news from the other guy and the compression is almost what he was expecting, which is somehow for the pictures between 1KB better and 1KB worst compared to DAN0, and a decompression routine size 50% bigger. His decompression routine speed is faster than DAN0, but not by much.

[newcoleco]

Test of DAN0 on a concret project :

 

Experimentation in a real Coleco project : GhostBlaster (PAL version)

 

- Before DAN0 (Using Marcel's RLE) : 32621 bytes

 

- After DAN0 (Removing all RLE) : 29732 bytes

 

- Saving : 2889 bytes, 2.8213KB = 8% of 32KB.

 

- Number of extra levels (average 700 bytes each) this version could handle : 4 more levels.

 

That's a concret usage of DAN0, and the decompression speed is good enough to not notice a difference between the RLE and DAN0 versions of this game project.

 

I'm happy!

Edited March 25, 2010 by newcoleco

[youki]

Of course, this kind of situation of encoding 13 tables in a Coleco project will be pretty rare

 

I have lot more table than that in my Ghost'n zombies .

If i remember well about 25 tables.

 

One thing to compress well in addition of a good compression algorithm , is to analyse the image before the compression and slightly modify the compression way according to the image.

For instance, if you consider RLE. Sometimes it is better to compress column by column instead of row by row.

And sometimes if you divide you image in a certain number of square , and for each of these squares find if it is better to compress by row or by column you can even save more space. And to store the information about what "kind" of decompression to do (row or columns) for each squares you can store that on one byte. Suppose you decide to divide your image in 8 squares maximum. Each bit of the byte can be used to determine if the decompression should be done vertically or horizontally.

 

So i guess if you use that idea coupled with your DAN0 , You could achieve very good result. I did some tests few time ago with RLE , and the results on certain type of image is really impressive , compared to the only "horizontal" RLE.

[newcoleco]

Of course, more you know about what you want to compress, more you'll try adapted solutions, based on the result you are looking for.

 

The way data are pushed to the video memory increments the address (pointer) automaticaly, so it's more likely to decompress data in order as a constant flow to avoid complexe manipulations, but it's possible to do what you said by constantly setting the pointer to video memory based on where you want the next data to be... it's more complexe and need more memory and time to do so, but it's totally possible.

 

Another example of algorithm, from CPC scene, is to read first a line of bits that represents a mask to tell which bytes need to be different from the previous line pof bytes. This kind of compression can be used, for example, to avoid encoding bytes that are simply "vertically" the same if you look at all the "lines of bytes", alligned one under the other, which occurs in graphics, like in the AtariAge logo if you consider each pixel as a byte.