Data Compression Benchmark - DAN, PLETTER, ZX7, EXOMIZER, PUCRUNCH, MEGALZ

[newcoleco]

From my presentation about my recent work on Coleco graphics tools; Coleco ADAM users annual convention ADAMCon 29, July 20-23, 2017, in Guelph, Ontario.

The following text is about data compression obtained by using popular LZ variants for 8-bit systems, including my own named Dan, applied on several bitmap pictures for 8-bit systems.

These pictures include formats Coleco .PC, MSX .SC2, and ZX Spectrum .SCR. The pictures are limited to PATTERN and COLOR tables only (no sprites allowed).

 

 

Table showing results with MIN, MAX, and AVERAGE for each cathebory.

 

Please note : Exomizer needs extra RAM prior to decompress data, and RLE (Run Length Encoding) is not a LZ variant.

• 3822.74 <- Exomizer
• 3930.13 <- Dan3
• 3931.65 <- Dan4
• 3939.92 <- Dan1
• 3940.85 <- Dan2
• 3944.20 <- PuCrunch
• 4044.70 <- MegaLZ
• 4059.60 <- Pletter , BitBuster
• 4063.13 <- ZX7
• 4077.10 <- ApLib aka APack
• 5899.67 <- RLE

Table 1 - Average compression in bytes obtained on 95 Graphic Mode 2 bitmap pictures of 12K bytes each.

 

• 4797.03 <- Exomizer
• 4928.53 <- Dan4
• 4930.37 <- PuCrunch
• 4940.84 <- Dan3
• 4958.74 <- MegaLZ
• 4961.80 <- Pletter , BitBuster
• 4963.39 <- ZX7
• 4986.14 <- ApLib aka APack
• 4992.42 <- Dan2
• 4996.06 <- Dan1
• 6059.89 <- RLE

Table 2 - Average compression in bytes on 1115 ZX Spectrum .SCR complex pixel art of 6912 bytes each.

 

• 2714.56 <- Exomizer
• 2828.22 <- Dan3
• 2832.77 <- Dan4
• 2863.85 <- Pletter , BitBuster
• 2865.63 <- MegaLZ
• 2866.14 <- PuCrunch
• 2867.64 <- ApLib aka APack
• 2867.65 <- ZX7
• 2875.06 <- Dan2
• 2890.77 <- Dan1
• 4264.42 <- RLE

Table 3 - Average compression in bytes on 615 ZX Spectrum .SCR simple pixel art of 6912 bytes each.

 

 

DAN3 and DAN4 data compression

DAN3 is a lossless data compression based on the idea to compress relevant data with some patterns more than optimizing patches of emptiness, using the best ideas of LZ77-LZSS variants DAN1 and DAN2 data compression, but changed how doublets ( size and relative index values ) are encoded; using Golomb Gamma instead of Elias Gamma, limited the size of sequences, and simplified the binary tree to decode offset values.

 

DAN4 is an attempt to improve DAN3. First, the modified k=1 Exp-Golomg values reads bytes instead of bits for large values which improves the decompression speed. Second, the two (2) supported modes, one optimized for simple data and one for complex data such as detailed pixel-arts and heavily dithered graphics.

Of course, DAN3 and DAN4 are not miracle solutions.

 

Because of its nature, DAN3 struggle to do better compression ratio results for pictures with lots of spaces like the following one.

And sometimes, DAN1 is better than DAN3 for bitmap with dithering like the following one by 66 bytes.



So how to decide which data compression to use for our projects? Trial and error? Perhaps, or simply use the data compression tools you are most comfortable with.

Samples with their data compression results:

NewColeco Presents ROM File Edition

• 837 < Exomizer
• 845 < Dan2
• 845 < Dan1
• 858 < Dan4
• 863 < PuCrunch
• 895 < ZX7
• 895 < ApLib
• 898 < Pletter
• 908 < Dan3
• 969 < MegaLZ
• 1478 < RLE

 

Smurf Challenge

• 1140 < Exomizer
• 1162 < Dan2
• 1164 < Dan1
• 1170 < PuCrunch
• 1185 < Dan4
• 1188 < Dan3
• 1229 < ApLib
• 1233 < Pletter
• 1237 < ZX7
• 1245 < MegaLZ
• 1705 < RLE

 

Bejeweled Title Screen

• 1306 < Exomizer
• 1358 < Dan2
• 1359 < Dan1
• 1372 < Dan4
• 1376 < Dan3
• 1380 < PuCrunch
• 1424 < ApLib
• 1427 < Pletter
• 1427 < ZX7
• 1463 < MegaLZ
• 2711 < RLE

 

Robee Blaster

• 1937 < Exomizer
• 2005 < PuCrunch
• 2016 < Dan3
• 2023 < Dan4
• 2024 < Dan2
• 2047 < Dan1
• 2050 < ZX7
• 2054 < Pletter
• 2098 < ApLib
• 2101 < MegaLZ
• 8752 < RLE

 

Maze Maniac

• 2433 < Exomizer
• 2504 < PuCrunch
• 2522 < Dan3
• 2551 < Dan4
• 2554 < Dan2
• 2570 < Dan1
• 2620 < Pletter
• 2621 < ZX7
• 2650 < MegaLZ
• 2671 < ApLib
• 4609 < RLE

 

Anniversary Cake Demo

• 2947 < Exomizer
• 2993 < PuCrunch
• 3020 < Dan2
• 3025 < Dan3
• 3028 < Dan1
• 3058 < Dan4
• 3108 < ApLib
• 3123 < MegaLZ
• 3126 < ZX7
• 3130 < Pletter
• 4048 < RLE

 

F1SPP

• 3913 < Exomizer
• 4013 < Dan3
• 4028 < Dan2
• 4033 < Dan4
• 4045 < Dan1
• 4096 < PuCrunch
• 4107 < MegaLZ
• 4170 < Pletter
• 4170 < ZX7
• 4208 < ApLib
• 6770 < RLE

 

Lena aka Lenna (used a lot in papers about imaging)

• 8595 < Exomizer
• 8812 < Dan4
• 8840 < Dan3
• 8873 < Dan1
• 8897 < Dan2
• 8925 < PuCrunch
• 8962 < MegaLZ
• 9084 < ZX7
• 9085 < Pletter
• 9141 < ApLib
• 11958 < RLE

 

UPDATES : November 17, 2017. Added informations about DAN4 results developped during October-November 2017.

Edited November 18, 2017 by newcoleco

[newcoleco]

SPACE VERSUS SPEED

 

Especially for the 8-bits and 16-bits homebrew projects, optimization is a constant dilemma between space and speed.

 

The following table shows the results of DAN1, DAN3, PLETTER and ZX7, all running the same SlideShow demo, all decompressing directly to VRAM (which is very slow), with the size in bytes of each decompression routine, the size in bytes of the ROM file containing decompression routine with the pictures, and the time in seconds for the decompression of the 1st picture.

 

• DAN1: decompression routine 211 bytes, ROM file 27094 bytes, show 1st picture in 1.114 second
• DAN3: decompression routine 201 bytes, ROM file 27010 bytes, show 1st picture in 1.072 second
• PLETTER: decompression routine 209 bytes, ROM file 27740 bytes, show 1st picture in 0.877 second
• ZX7: decompression routine 132 bytes, ROM file 27665 bytes, show 1st picture in 0.876 second

 

 

APPENDIX - Questions and Answers

 

QUESTION :

 

WHY PLETTER AND ZX7 OFFER SIMILAR COMPRESSION RESULTS IN THIS BENCHMARK?

 

ANSWER :

 

ZX7 and PLETTER are both using two possible sizes to encode offset (relative index) values in their LZ77 encoding. The small size to encode offset values is 7 bits ( 128 ) long for both compressors while the big size is fixed to 11 bits ( 2048 ) long for ZX7 and variable for PLETTER from 9 bits ( 512 ) up to 13 bits ( 8192 ) long. After a first pass scanning data, PLETTER decides the ideal size to encode the big offset values. To get similar results, both PLETTER and ZX7 should use similar sizes to encode offsets, which is 11 bits long. And it happens that the bitmap pictures made of 6K bytes data tables ( PATTERN table for ZX Specatrum screens, PATTERN and COLOR tables for Graphic Mode 2 ) tend to get better results with big offsets encoded as 11 bits values. In sumary, if the data to compress do need 7 bits long offsets and/or 11 bits long offsets to get a good compression result, PLETTER and ZX7 should always give similar results, otherwise PLETTER do provide better compression with its flexibility of various ( from 9 to 13 bits long ) sizes to encode offsets.

 

CONCLUSION :

 

PLETTER is similar to ZX7 but provides better compression overall.

 

QUESTION :

 

Why DAN3 is better than DAN1 and DAN2 compression in this benchmark?

 

ANSWER :

 

In this benchmark, the bitmap pictures may get better compression by using 8 bits ( 256 ) instead of only 7 bits ( 128 ) for the small offset values. Why? Because of the way the graphics are encoded. If you look at ZX Spectrum .SCR bitmap pictures, bytes for the PATTERN table are interlace in a way that bytes 256 away from each others in the data table are one above the other on screen making them more likely to be the same. And Graphic Mode II bitmap pictures are in blocks of 256x8 pixels on screen which makes offsets of 256 bytes in the data tables more likely to find similar bytes than offsets of 128 bytes. Because of this, DAN1, DAN2 and DAN3 do have 8 bits offsets. However, DAN1 and DAN2 do worse than DAN3 to compress ZX Spectrum pictures simply because their smaller offset bit-size is only 4 bits ( 16 ) while it's 5 bits ( 32 ) for DAN3, and offset of 32 is very important: it's 32 bytes long for each line of 256 pixels on screen, and ZX Spectrum COLOR table are rows of 32 bytes. These differences explain the difference in the results. And also, it's 32 x 24 characters on screen for our beloved 8-bit systems (mostly), which again makes 32 a relevant offset value.

 

CONCLUSION :

 

Overall, DAN3 is using a better set of possible bit-sizes to encode offsets than DAN1 and DAN2 for graphics like title screens that we need in our projects. Also the 4 bits instead of 5 bits to encode smaller offsets do explain why DAN1 and DAN2 do worse than DAN3 with ZX Spectrum bitmap screens, because extra bits are used to identify in which small size is encoded each offset in the compressed data.

 

QUESTION :

 

Shouldn't a flexible set of bit-sizes for offsets be a better solution than making a format with fixed sizes?

 

ANSWER :

 

Yes, and that's exactly the reason why Exomizer out-perform all the others compressors. But to achieve this, a table of variable bit-size lengths to encode-decode offsets is needed. This table is encoded very efficiently into the first 52 bytes of the compressed data. The table needs to be decoded into RAM prior to the decompression. The space needed in RAM for this offsets table can be a deal breaker for some vintage systems, for some projects without enough extra memory space available.

 

CONCLUSION :

 

A flexible way to encode offsets, like the one used in Exomizer, do perform better than fixed sizes. To achieve this, extra memory space is used for a table of the possible offset sizes which can be significant enough on vintage 8bits computers and consoles like the ColecoVision to be a deal-breaker.

 

QUESTION :

 

Is Exomizer 2.0 the best data compression for vintage 8-bits systems?

 

ANSWER :

 

It depends what you mean by "best" data compression. For example, Subsizer 0.6 is a data compression tool for the Commodore 64 that gives slightly better results (a few bytes difference) than Exomizer 2.0. After some tests, Subsizer 0.6 crashes while trying to compress some files including 2 of the Graphic Mode II pictures from my benchmark test. Another tool from the Commodore 64 scene is named ALZ64 and uses arithmetic coding instead of Huffman coding to get even better compression at the cost of time and memory space, but it's a packer for Commodore 64 programs, not a data compression tool for raw files like picture, text, and audio files.

 

CONCLUSION :

 

There are many data compression tools and some do compress more than Exomizer 2.0.

 

 

*UPDATE : December 8, 2017 - Added section SPACE VERSUS SPEED

Edited December 9, 2017 by newcoleco

[newcoleco]

Updated this post with DAN4 data compression tests results.

 

DAN4 is an effort to make a slightly faster DAN3 with some optimizations here and there.

 

Backstory: At the ADAMCon banquet in 2017, Mister Luc M., aka pixelboy, asked if DAN3 is fast enough to decompress data "on the fly". Knowing that RLE is the only fast data compression algorithm that I know, with maybe DAN0 as a close second in my opinion, I couldn't reply since I had no idea of what amount and kind of data we were talking about. Mister Dale W. replied that essentialy this with a mention that DAN data compression should be fast enough for the project idea Luc was talking about. The banquet ended and this talk made me think with this eternal dilema of SIZE versus SPEED. I've searched for solutions and juggled with ideas of my own, and it's in October and November of 2017 that I've started to code a variant of DAN3 with ideas of allowing reading bytes instead of bits for large numbers, at the cost of a bigger decompression routine, to allow faster decompression time. Also, to fight the lost of compression ratio, the idea of using less bits for hard to compress data granted this newly made DAN4 to somehow get results good enough to even beat from time to time DAN3.

 

I will post DAN3 tools first before the end of 2017 since it's in average the useful version for our projects in general. DAN4 is more specific for special needs in time.

[+DZ-Jay]

Great stuff! Thanks for the effort put into this. I am in the process of devising a bespoke compression scheme for Intellivision graphics screens and your results certainly guides which algorithms to consider.

 

By the way, I just wanted to point out because of a comment that you made on the first post, that the picture "lenna" is a photo of Lenna Söderberg, a Playboy Centerfold Playmate 1972, which was scanned digitally sometime in the 1970s to make a demo of a digital image processor for a conference. From then on it became a tradition to use it in image processing as a test of color balance and texture rendering.

 

I just find that bit of computer history interesting.

 

For the really curious, here's the original centerfold picture, of which the "lenna" image is just a piece. Warning! Very much NSFW!!!

 

-dZ.

[newcoleco]

Great stuff! Thanks for the effort put into this. I am in the process of devising a bespoke compression scheme for Intellivision graphics screens and your results certainly guides which algorithms to consider.

 

{...Lenna in computer imaging history...}

 

-dZ.

 

Thanks for your comment.

 

I'm glad you find this useful.

 

This represents months of collecting data and working on my own tools on a large amount of fullscreen graphics that I believe to be the most memory consuming in our homebrew projects. I give freely my work, my tools, my knowledge, even my games. There is a lot of technical information in various PDF and forums posts that I've written and this is just one of them.

During that time, I've learned a lot about what works and what doesn't, making my own formats, experimenting with ideas and testing them. You can see the following text as more rambling about what I've learned.

 

LZ77 variants are dominating in popularity; GZIP is used in our daily internet communications. It's a very efficient lossless data compression that doesn't need extra memory to maintain a dictionary or any kind of dynamic data structure to help optimize the compression ratio. The main reasons why some tools give better compression than others are the algorithm used and the way the values are encoded in the compressed data format. Exomizer uses tables in order to minimize the number of bits to be encoded for each offset value; if the relative offset values are more likely to be in the same range, regardless if it's small or large values, the number of bits to encode them are simply the index value in a table, cutting bytes and bytes of data in a smart way.

 

Because Exomizer uses extra memory to compute its tables, I felt unease to use it in my ColecoVision projects simply because there is only 1K RAM in the game console. So I used a various bits sizes method to encode offsets, and the steps of 4 bits or so gave me the best compression ratio results, avoiding to encode into lots and lots of 0 bits offset values for nearby matching sequences. Of course, my DAN1, DAN2 and DAN3 formats can't reach the same optimization as Exomizer in that regard, but since Exomizer needs space for the data to compute the table needed to get this optimization, and the fact that Exomizer do not care about matches of a single byte which, I've seen a few times my formats getting better results than Exomizer but it's rare, it depends on the data. I see the compression of a match of a single byte somewhat like a local fixed Huffman encoding, and Huffman encoding is used in modern data archives with LZ data compression to improve the compression ratio, like ZIP.

 

During my search online for lossless data compression used for 8bit homebrew projects, I was surprised to see new tools using arithmetic data compression since it's based on floating point numbers, not integers. So, I've added the info in the APPENDIX section but I had not much time to experiment and couldn't be used for our projects, requiring just too much RAM memory to compute the necessary tables.

 

I've studied computer science at University, with computer imaging in mind. I saw Lenna picture over and over in various papers, her picture became a reference, a standard of many pictures used to test and compare various results of algorithms such as edges detection, textures, and also data compression including lossy compression using DCT and wavelets. I firmly believe that her picture, her face, became a meme among computer scientists before memes were invented.

 

PS: I've added a tiny section about SPACE VS SPEED just before the APPENDIX. It doesn't show all formats, but it gives an idea of what to expect.

[+DZ-Jay]

Thanks for the additional detail. You are right that the Lenna photo was indeed a "meme" among computer imagery scientists, way before that was invented. Lots of people claim that it's a great sample for detecting edges, shadows, color balance, etc. However, the most likely reason is probably because it's a photo of a hot chick posing naked.

 

As for compression, I was actually considering looking into Exomizer. My main concern is with decompression, not compression. I am working on a game development framework for the Intellivision, and I am looking to devise an efficient packing/compression format for background graphical scenes. These background scenes are composed of 16-bit words (well, actually 13-bit words), and the ROM is 16-bits wide.

 

My expectation is that the compression will be done "out of band" by a compiler as a pre-processing step prior to assemblage. Therefore, the use of extra resources for optimization during compression is not really a concern.

 

Moreover, the particular use-case I am looking to address is the initialization of levels or the generation of title and other static screens, which are not in the critical path of game-play. Therefore, the speed of decompression is also not a major concern.

 

What is a major concern is the complexity of implementation, and the size and efficiency of the decompression scheme. While it doesn't need to be fast, it needs to be compact enough to not take too much precious memory either in ROM or RAM. Simplicity of the algorithm is also desired, mostly because I am not really that good at programming or maths, and I don't want to burn my brain implementing it.

 

I'll take a look at your DAN1, DAN2, DAN3 algorithms to get a bit more context on them. Thanks again!

 

-dZ.

[newcoleco]

As for compression, I was actually considering looking into Exomizer. My main concern is with decompression, not compression. I am working on a game development framework for the Intellivision, and I am looking to devise an efficient packing/compression format for background graphical scenes. These background scenes are composed of 16-bit words (well, actually 13-bit words), and the ROM is 16-bits wide.

Your concerns are surely shared with homebrewers like me dealing with limited ROM and RAM memory space. It's the main reason why I've spent so much time into this, getting results without sacrificing memory space.

 

My expectation is that the compression will be done "out of band" by a compiler as a pre-processing step prior to assemblage. Therefore, the use of extra resources for optimization during compression is not really a concern.

Same with ColecoVision homebrew games, the data compression time is not a concern because it's not the part gamers do experience while playing our games.

 

Moreover, the particular use-case I am looking to address is the initialization of levels or the generation of title and other static screens, which are not in the critical path of game-play. Therefore, the speed of decompression is also not a major concern.

Same situation with ColecoVision homebrew games, the majority of the graphics are usually not rendered "on-the-fly" risking the fluidity of the game or even glitches. Graphics are initialized first then shown on screen with minor changes, usually tiles and sprites movement manipulations, based on what it's supposed to be going on screen.

 

What is a major concern is the complexity of implementation, and the size and efficiency of the decompression scheme. While it doesn't need to be fast, it needs to be compact enough to not take too much precious memory either in ROM or RAM. Simplicity of the algorithm is also desired, mostly because I am not really that good at programming or maths, and I don't want to burn my brain implementing it.

I'm glad I've burn my brain for the greater good.

 

I'll take a look at your DAN1, DAN2, DAN3 algorithms to get a bit more context on them. Thanks again!

 

-dZ.

Ask your questions. Since I'm actually working on data compression, it's a hot topic for me these days.

 

And if you want a collaboration, just provide me lots of raw data samples corresponding to Intellivision homebrew projects (real or fictional) to be compressed. I can take a look, analyze them, and come up with a LZ77 variant algorithm based on my work that should suit your needs, getting your expertise on Intellivision into consideration. If it needs to be a special format instead of the ones I've already come up with, I can make the adapted compression tool in C and the decompression routine in Z80 asm easily. Make it your own solution afterward, make the 6502 ASM routine, tweak it, adapt it, integrate it in your toolbox. And if you're having trouble coding, I'm sure enthusiasts will be happy to help.

 

Have a nice weekend!

Edited December 9, 2017 by newcoleco

[+nanochess]

OMG! First time I see the complete picture of Lena. Perfection everywhere.

[+DZ-Jay]

Ask your questions. Since I'm actually working on data compression, it's a hot topic for me these days.

 

And if you want a collaboration, just provide me lots of raw data samples corresponding to Intellivision homebrew projects (real or fictional) to be compressed. I can take a look, analyze them, and come up with a LZ77 variant algorithm based on my work that should suit your needs, getting your expertise on Intellivision into consideration. If it needs to be a special format instead of the ones I've already come up with, I can make the adapted compression tool in C and the decompression routine in Z80 asm easily. Make it your own solution afterward, make the 6502 ASM routine, tweak it, adapt it, integrate it in your toolbox. And if you're having trouble coding, I'm sure enthusiasts will be happy to help.

 

Have a nice weekend!

 

Wow! Thanks for all the attention! I'm sure I'll be asking lots of questions eventually.

 

-dZ.

[+DZ-Jay]

Here's my first question.

The Intellivision is not really an 8-bit system. It has a 16-bit CPU with 16-bit registers which can address 8-bit or 16-bit RAM and 10-bit or 16-bit ROM (this is due to historical reasons). Home-brews typically use 16-bit ROM. Screen graphics are tile-based, with a Background Table (BACKTAB) in 16-bit RAM that stores a word that defines each of 240 tiles (20 columns x 12 rows) on the screen.

Each 16-bit word (actually, they only use 13-bits) in the BACKTAB contains the index of a graphics "card" to use (either from the built-in Graphics ROM, or the user-defined Graphics RAM), and various meta-data bits describing color and other properties.

I was thinking that both the "card" and "other" data parts could repeat at different rates, so they could compress at varying ratios.

I then thought that as an initial step, the encoder could split these two parts out of the word (shifting the bits around to align them) and compress them each as an individual 8-bit byte. The decoder could then re-build the word as necessary after decompressing each part.

My question is, do you think this could be a good idea? For full context, below is the 16-bit word definition of BACKTAB cells for each of the two screen modes of the Intellivision:

Color Stack Mode:
                               Color/Other Data
           ___________________________|___________________________
   _______/______                                          _______\______
  /              \                                        /              \
    13   12    11   10    9    8    7    6    5    4    3    2    1    0   
  +----+-----+----+----+----+----+----+----+----+----+----+----+----+----+ 
  |Adv.|FG   |GRAM|           GRAM/GROM Card #            |   FG Color   | 
  |col |Bit3/|GROM|    (0-255 for GROM, 0-63 for GRAM)    |   Bits 0-2   | 
  |stck|     |    |                                       |              | 
  +----+-----+----+----+----+----+----+----+----+----+----+----+----+----+ 
                  \_______________________________________/
                                  Card Data




Foreground/Background Mode:
                               Color/Other Data
                _______________________|_________________________
   ____________/__________                                _______\______
  /                       \                              /              \
    13   12   11   10    9    8    7    6    5    4    3    2    1    0   
  +----+----+----+----+----+----+----+----+----+----+----+----+----+----+ 
  |BG  |BG  |GRAM|BG  |BG  |      GRAM/GROM Card #       |   FG Color   | 
  |Bit2|Bit3|GROM|Bit1|Bit0|          (0 - 63)           |   Bits 0-2   | 
  +----+----+----+----+----+----+----+----+----+----+----+----+----+----+ 
                           \_____________________________/
                                       Card Data

My idea is to shift the lower 3 bits out of the word, and add them back at the top, and split the "card" and "other" into two bytes.

[newcoleco]

Here's my first question.

 

The Intellivision is not really an 8-bit system. It has a 16-bit CPU with 16-bit registers which can address 8-bit or 16-bit RAM and 10-bit or 16-bit ROM (this is due to historical reasons). Home-brews typically use 16-bit ROM. Screen graphics are tile-based, with a Background Table (BACKTAB) in 16-bit RAM that stores a word that defines each of 240 tiles (20 columns x 12 rows) on the screen.

 

Each 16-bit word (actually, they only use 13-bits) in the BACKTAB contains the index of a graphics "card" to use (either from the built-in Graphics ROM, or the user-defined Graphics RAM), and various meta-data bits describing color and other properties.

 

I was thinking that both the "card" and "other" data parts could repeat at different rates, so they could compress at varying ratios.

 

I then thought that as an initial step, the encoder could split these two parts out of the word (shifting the bits around to align them) and compress them each as an individual 8-bit byte. The decoder could then re-build the word as necessary after decompressing each part.

 

My question is, do you think this could be a good idea? For full context, below is the 16-bit word definition of BACKTAB cells for each of the two screen modes of the Intellivision:

Color Stack Mode:
                               Color/Other Data
           ___________________________|___________________________
   _______/______                                          _______\______
  /              \                                        /              \
    13   12    11   10    9    8    7    6    5    4    3    2    1    0   
  +----+-----+----+----+----+----+----+----+----+----+----+----+----+----+ 
  |Adv.|FG   |GRAM|           GRAM/GROM Card #            |   FG Color   | 
  |col |Bit3/|GROM|    (0-255 for GROM, 0-63 for GRAM)    |   Bits 0-2   | 
  |stck|     |    |                                       |              | 
  +----+-----+----+----+----+----+----+----+----+----+----+----+----+----+ 
                  \_______________________________________/
                                  Card Data




Foreground/Background Mode:
                               Color/Other Data
                _______________________|_________________________
   ____________/__________                                _______\______
  /                       \                              /              \
    13   12   11   10    9    8    7    6    5    4    3    2    1    0   
  +----+----+----+----+----+----+----+----+----+----+----+----+----+----+ 
  |BG  |BG  |GRAM|BG  |BG  |      GRAM/GROM Card #       |   FG Color   | 
  |Bit2|Bit3|GROM|Bit1|Bit0|          (0 - 63)           |   Bits 0-2   | 
  +----+----+----+----+----+----+----+----+----+----+----+----+----+----+ 
                           \_____________________________/
                                       Card Data

My idea is to shift the lower 3 bits out of the word, and add them back at the top, and split the "card" and "other" into two bytes.

 

Since it's very technical and new to me, I trust your judgement on the matter. My question is: is it possible to let the data decompress into the memory at once before doing the bitshifting correction to get back valid data? If it's possible, then we can focus on analyzing your data bitshifted through my tools and see its effect on the results.

 

What I can say is that splitting bytes into distinct groups helps the compression ratio. Many modern data compression technics use a "reset" code to change the encoding at any point (usually split into blocks) when the data seems to have a different need, to switch from one kind to another. As you know, text data don't look like graphics, graphics don't look like codes, etc. and sometimes a file can integrate multiple kinds of data in it, such as our graphics are usually split into tables of colors, patterns and tiles.

[+DZ-Jay]

My question is: is it possible to let the data decompress into the memory at once before doing the bitshifting correction to get back valid data?

 

I'm not sure I understand. Are you asking if we can decompress the entire stream first into RAM and then do the bitshifting? I guess this is certainly possible, but I would prefer not having to commit that memory first. That's 240 words of RAM, which is considerable on the Intellivision.

 

I may have misunderstood your question, though.

 

-dZ.

[newcoleco]

I'm not sure I understand. Are you asking if we can decompress the entire stream first into RAM and then do the bitshifting? I guess this is certainly possible, but I would prefer not having to commit that memory first. That's 240 words of RAM, which is considerable on the Intellivision.

 

I may have misunderstood your question, though.

 

-dZ.

Surely I'm not understanding all that technical information.

 

I was thinking that both the "card" and "other" data parts could repeat at different rates, so they could compress at varying ratios.

That is a correct assumption.

 

I then thought that as an initial step, the encoder could split these two parts out of the word (shifting the bits around to align them) and compress them each as an individual 8-bit byte. The decoder could then re-build the word as necessary after decompressing each part.

And so I asked my question about bit-shifting after decompression because it seems to be what you were already implying here but I wasn't sure.

 

So, let me try to explain what I think you were saying and you tell me if I'm wrong.

 

Let's consider the data already split into 2 sets ( cards and others ) as you propose and use LZ compression on each set of bytes.

 

Then the result is used in a project with the LZ decompression routine and an extra routine to reverse the bit-shifting effect after decompression is done.

 

Is that what you are talking about or it's more gymnastic with things getting done at the same time?

 

Since I've never coded for the Intellivision, I'm quite in the dark about what's possible and what isn't.

 

We should probably have a talk in another thread. Let me free up a bit my mailbox here.

[+DZ-Jay]

Surely I'm not understanding all that technical information.

 

 

That is a correct assumption.

 

 

And so I asked my question about bit-shifting after decompression because it seems to be what you were already implying here but I wasn't sure.

 

So, let me try to explain what I think you were saying and you tell me if I'm wrong.

 

Let's consider the data already split into 2 sets ( cards and others ) as you propose and use LZ compression on each set of bytes.

 

Then the result is used in a project with the LZ decompression routine and an extra routine to reverse the bit-shifting effect after decompression is done.

 

Is that what you are talking about or it's more gymnastic with things getting done at the same time?

 

Since I've never coded for the Intellivision, I'm quite in the dark about what's possible and what isn't.

 

We should probably have a talk in another thread. Let me free up a bit my mailbox here.

 

Sorry about all the confusion, I am not that knowledgeable about compression so I was kind of making it up, and I see I managed to take you down my confused path.

 

I thought more like doing something fancy at the same time, so that as both bytes were being unpacked, they could be re-shited/joined on the fly. I don't even know if this is practical.

 

However, it may be much more clever than is needed. At this point, even RLE would be an improvement since on the Intellivision, most home-brews just store the raw data.

 

-dZ.

[newcoleco]

Sorry about all the confusion, I am not that knowledgeable about compression so I was kind of making it up, and I see I managed to take you down my confused path.

 

I thought more like doing something fancy at the same time, so that as both bytes were being unpacked, they could be re-shited/joined on the fly. I don't even know if this is practical.

 

However, it may be much more clever than is needed. At this point, even RLE would be an improvement since on the Intellivision, most home-brews just store the raw data.

 

-dZ.

Yes, you should try to use RLE compression first. There are a lot of RLE listings and once you get one that works for you, you can be creative and modify it.

 

What can be interesting for your needs, since you were thinking of doing a fancy "on-the-fly", is to implement something like this, which is not a decompression but more a decoder of compressed data used (called) in a routine with the bit-shifting applied "on-the-fly":

 

Initialize the necessary addresses and variables

START LOOP

*Get next "other"

If byte "other" is an invalid value, END LOOP

*Get next "card"

Bit-shifting accordingly

Load into memory

END LOOP

*Get next: Provide the next byte according to the compression method used. Should be an external routine to avoid repeating codes.

 

Once you make this pseudo-code works with RAW data as a default compression method, you can improve with other compression methods. I don't think LZ77 method can work in this way, but some RLE and Huffman methods surely can.

 

Enjoy!

Edited December 10, 2017 by newcoleco

[newcoleco]

Intellivision Graphics Compression with DZ-Jay

After some talk with DZ-Jay, we figured out that bytes modifications "on the fly" were needed, and so it was better to do either a basic RLE data compression or, considering the particular graphics data structure and size, something like a fixed dictionary of 16-bits words in it that can be shared between multiple screens and referenced by simply 8-bits values (a byte).

 

Pletter versus ZX7 (more...)

I've done some more experiments with Pletter lately and I've noticed a lack of efficiency. The offset value is encoded in such a way that Pletter needs an extra bit for relative offsets larger than 127; ZX7 avoids this need. However, ZX7 lacks an adjustable size for big offset values which favors Pletter over ZX7 when the number of bits needed fixed in ZX7 is not already the best possible option. Also, I've tried to code a more aggressive Pletter data compression tool and the results only save like a bit which is insignificant (really, a bit isn't even enough to save a byte in most cases).