newcoleco Posted July 27, 2017 Share Posted July 27, 2017 (edited) 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 6 Quote Link to comment Share on other sites More sharing options...
newcoleco Posted July 30, 2017 Author Share Posted July 30, 2017 (edited) 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 Quote Link to comment Share on other sites More sharing options...
newcoleco Posted November 18, 2017 Author Share Posted November 18, 2017 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. 2 Quote Link to comment Share on other sites More sharing options...
+DZ-Jay Posted December 8, 2017 Share Posted December 8, 2017 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. 1 Quote Link to comment Share on other sites More sharing options...
newcoleco Posted December 9, 2017 Author Share Posted December 9, 2017 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. Quote Link to comment Share on other sites More sharing options...
+DZ-Jay Posted December 9, 2017 Share Posted December 9, 2017 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. Quote Link to comment Share on other sites More sharing options...
newcoleco Posted December 9, 2017 Author Share Posted December 9, 2017 (edited) 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 Quote Link to comment Share on other sites More sharing options...
+nanochess Posted December 9, 2017 Share Posted December 9, 2017 OMG! First time I see the complete picture of Lena. Perfection everywhere. Quote Link to comment Share on other sites More sharing options...
+DZ-Jay Posted December 9, 2017 Share Posted December 9, 2017 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. Quote Link to comment Share on other sites More sharing options...
+DZ-Jay Posted December 9, 2017 Share Posted December 9, 2017 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. Quote Link to comment Share on other sites More sharing options...
newcoleco Posted December 9, 2017 Author Share Posted December 9, 2017 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. Quote Link to comment Share on other sites More sharing options...
+DZ-Jay Posted December 9, 2017 Share Posted December 9, 2017 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. Quote Link to comment Share on other sites More sharing options...
newcoleco Posted December 9, 2017 Author Share Posted December 9, 2017 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. Quote Link to comment Share on other sites More sharing options...
+DZ-Jay Posted December 10, 2017 Share Posted December 10, 2017 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. Quote Link to comment Share on other sites More sharing options...
newcoleco Posted December 10, 2017 Author Share Posted December 10, 2017 (edited) 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 Quote Link to comment Share on other sites More sharing options...
newcoleco Posted December 25, 2017 Author Share Posted December 25, 2017 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). Quote Link to comment Share on other sites More sharing options...
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.
Note: Your post will require moderator approval before it will be visible.