Search the Community

DOWNLOAD ColecoVision SlideShow Sample in 5 formats: SLIDESHOW SAMPLE.ZIP README.TXT Hello everyone, My name is NewColeco and I'm gonna tell you what I've been worked on during the last 3 years. Not everyone is aware that graphics are very difficult to add in our beloved homebrew games, especially within the standard 32K cartridge size. To make things worse, some graphics cannot be compressed at all to keep the action fluid and fast. In order to add great looking bitmap screens and tilesets into our projects, we use data compression. I've been working very hard on lossless data compression for our graphics data. My new compressed formats are named DAN1, DAN2, and DAN3; they work especially well for big graphics like charset and bitmap screens. They are, technically speaking, LZ77 variants and developed based on our graphics need. The ZIP file in the download section contains 5 files of the exact same slideshow sample, the only difference is the data compression format used in each one of them. Information about the Slideshow ROM files: in Pletter - ROM size 27730 bytes. in ZX7 - ROM size 27665 bytes. in DAN1 - ROM size 27094 bytes. in DAN1 without RLE support - ROM size 27078 bytes. in DAN3 - ROM size 26999 bytes. For this slideshow sample, saving about 700 bytes is a big deal; should be enough to add an extra picture without going over 32K. Now you know what I've been working on lately. Question? Thanks for reading!

DAN3 Lossless Data Compression Programmed by Daniel Bienvenu, 2017. What is DAN3? DAN3 is a LZ77/LZSS variant using unary encoding, k=1 Exp-Golomb and various sizes relative offsets without the need for extra memory prios to decompress data. Details below. Ask questions, post comments, share experiences. Download DAN3 build 20180126 (de)compression tool final? (BIN + SRC) : dan3_20180126.zip DAN3 build 20180123 (de)compression tool *BUG* (BIN + SRC) : dan3_20180123.zip DAN3 build 20180118 (de)compression tool *BUG* (BIN + SRC) : dan3_20180118.zip (previous version) DAN3 compression tool *BUG* only experimental beta (BIN) : dan3beta.zip ColecoVision Slide Show Sample (SRC, BIN) : SLIDESHOWDAN3.zip Technical Information DAN3 is a LZ77/LZSS variant developed based on DAN1 and DAN2, which explains their similarities. The format starts, like in DAN2, with defining what's the size in bits for the large offset values used to identify a match with the following table with a unary code (sequence of bits that looks like this): 0 : 9 bits long <- 512 bytes (characters on a screen). 10 : 10 bits long <- 1K (character set, some bitmap screens) 110 : 11 bits long <- 2K (most bitmap screens) 1110 : 12 bits long <- 4K (dithered bitmap screens) 11110 : 13 bits long <- 8K (my decompression routine limit as-is) 111110 : 14 bits long <- 16K 1111110 : 15 bits long <- 32K 11111110 : 16 bits long <- 64K (only good for 32bits/64bits PC files at this point) ... (no limit in theory) Then, like in DAN2, the first byte of the uncompressed data is stored as is. Afterward, things are a little different, which makes DAN3 different than the others; offering a better compression on average but not always. For each match, the size and the relative offset values are encoded. While DAN1 and DAN2 are using Elias Gamma to encode the size value, DAN3 is using a k=1 Exp-Golomb encoding instead, which somehow helps to optimize a little bit both in term of space and time to decode. As for the relative offset values, DAN3 is using a completely different set of possible bit-size offsets; using {5, 8, max} instead of {1, 4, 8, max} bits to encode offsets. As for the special case of a nearby single byte being the same as the current byte to encode, DAN3 limits to the first 3 nearest bytes, instead of the 18 nearest bytes, which limits its potential to find a match and save space, but since the big impact is with sequences of more than 2 bytes, this change has no impact besides offering a better compression than Pletter and the others that do not support sequences of a single byte, acting if you like as a local fixed Huffman encoding. Here's a comparison side by side of Elias Gamma and k=1 Exp-Golomb to show you what I mean by size and speed possible gain in DAN3 since reading fewer bits means taking less time to decode. Elias Gamma (DAN1 and DAN2) versus k=1 Exp-Golomb (DAN3) 1 : 10 = size 1 010 : 11 = size 2 011 : 0100 = size 3 00100 : 0101 = size 4 00101 : 0110 = size 5 00110 : 0111 = size 6 00111 : 001000 = size 7 0001000 : 001001 = size 8 0001001 : 001010 = size 9 0001010 : 001011 = size 10 0001011 : 001100 = size 11 0001100 : 001101 = size 12 0001101 : 001110 = size 13 0001110 : 001111 = size 14 0001111 : 00010000 = size 15 000010000 : 00010001 = size 16 ... 000000011111110 : 00000011111111 = size 254 In DAN3, the support of Exp-Golomb stops at 00000011111111 = size 254. There are 3 reasons for that: It allows an optimization of decoding only into a single byte instead of supporting to carry the bits into a 16 bits register pair. In Z80 opcodes, that simplifies the decoding routine, making it faster and smaller. It makes the specials markers for END OF DATA and RLE about a byte smaller and faster to read. Very large sequences of nothingness sadly will need more than one match of size 254 each but since we're talking about compressing our elaborated graphics which are mostly not that empty, the limitation should be barely an issue and satisfy plenty our needs. Special Markers 00000001 + byte : RLE - Copy raw the next (byte value + 1) bytes 00000000 : END OF DATA Relative Offset For a size of 1 byte, the relative offset is either 0 (the byte just before), 1, or 2 encoded respectively as 0, 10, and 11. For sizes of 2 or more, the offset is encoded as follow: 10 + 5 bits = 5-bits Offset 0 + byte = 8-bits Offset = byte + 32 11 + N bits + byte = large Offset = (N bits and byte together as a 9 or more bits value) + 288 Listing Decompression to VRAM Routine for Z80, using BE and BF ports (ColecoVision) Written in SDCC style, to be added to your compression toolbox. DAN3 decompression routine is only 14 bytes bigger than DAN1 decompression. ; dan3.s ; DAN3 Lossless Data Compression Format by Daniel Bienvenu ; DAN3 Decompression to VRAM ; 6 December, 2017 ; Size: 201 bytes ; HL = SOURCE ; DE = DESTINATION ; global from this code ;================ .globl _dan3 ; void dan3 (void *data, unsigned vram_offset); .globl dan3 ; HL = ADDR. TO COMPRESSED DATA , DE = DESTINATION IN VRAM ; Wrapper to get values from parameters (register pairs) _dan3: pop bc pop de pop hl push hl push de push bc ; HL = SOURCE ; DE = DESTINATION dan3: ; Set Write in VRAM at DE ld c,#0xbf out (c),e set 6,d out (c),d res 6,d ; Set A for reading a bit routine ld a,#0x80 ; Important to save the IX register push ix ld ix, #get_bit_e+3 dan3_offsetsize_loop: dec ix dec ix dec ix call get_bit ; check next bit jr c, dan3_offsetsize_loop ; Copy literal byte dan3_copy_byte: ld b,#0x01 dan3_literal2main: ld c,#0xbe dan3_literals_loop: outi inc de jr nz, dan3_literals_loop ; Main loop dan3_main_loop: call get_bit ; check next bit jr c,dan3_copy_byte ; Decode Exp-Golomb + Special Marker push de ld de, #0x0001 ld b,e dan3_expgolomb_0: inc b call get_bit ; check next bit jr c, dan3_expgolomb_value bit 3,b jr z, dan3_expgolomb_0 ; Special Marker pop de call get_bit ; check next bit jr c, dan3_literals pop ix ret ; EXIT dan3_literals: ld b, (hl) ; load counter value (8 bits) inc hl inc b jr dan3_literal2main dan3_expgolomb_value: dec b dan3_expgolomb_value_loop: call get_bit_e ; check next bit -> DE djnz dan3_expgolomb_value_loop dec e push de pop bc jr z, dan3_offset1 ; D = 0, E = ??, BC = LENGTH ; Decode Offset value ld e,d ; e = 0 call get_bit ; check next bit jr nc, dan3_offset3 call get_bit jr nc, dan3_offset2 call get_highbits_e ; read some bits -> E inc e ld d,e ; D = E + 1 dan3_offset3: ld e, (hl) ; load offset offset value (8 bits) inc hl ex af, af' ld a,e add a,#0x20 ; Skip the short offsets covered by 5 bits ones ld e,a jr nc, dan3_offset_nocarry inc d dan3_offset_nocarry: ex af, af' jr dan3_copy_from_offset dan3_offset2: call get_5bits_e ; read 5 bits -> E jr dan3_copy_from_offset dan3_offset1: call get_bit ; check next bit jr nc, dan3_copy_from_offset call get_bit_e inc e ; Copy previously seen bytes dan3_copy_from_offset: ex (sp), hl ; store source, restore destination push hl ; store destination scf sbc hl, de ; HL = source = destination - offset - 1 pop de ; DE = destination ; BC = count ; COPY BYTES ex af,af' set 6,d dan3_copybytes_loop: push bc ld c,#0xbf out (c),l nop out (c),h inc hl nop nop in a,(#0xbe) nop nop nop out (c),e nop out (c),d inc de nop nop out (#0xbe),a pop bc dec bc ld a,b or c jr nz, dan3_copybytes_loop res 6,d ex af,af' pop hl ; restore source address (compressed data) jp dan3_main_loop get_highbits_e: jp (ix) ; COVER 16K ; call get_bit_e ; get next bit -> E ; COVER 8K get_5bits_e: call get_bit_e ; get next bit -> E call get_bit_e ; get next bit -> E call get_bit_e ; get next bit -> E call get_bit_e ; get next bit -> E get_bit_e: call get_bit ; get next bit rl e ; push bit into E ret ; get a bit get_bit: add a,a ret nz ld a,(hl) inc hl rla ret Comparison with DAN1 DAN3 to VRAM decompression routine is only 14 bytes more than the one for DAN1 to VRAM. As for the compression ratio, it really depends on the data. For example, here's a table showing the size obtained with DAN1 and DAN3 for each picture in the SlideShow sample. awb1p: DAN1 3677+2298, DAN3 3689+2328 f1spp: DAN1 2366+1679, DAN3 2349+1664 h6exp: DAN1 3412+2313, DAN3 3398+2297 mgfap: DAN1 3554+1935, DAN3 3551+1928 sotbp: DAN1+ 3394+1956, DAN3 3381+1921 Updates * Dec 5, 2017 - Added Offset encoding details. * Dec 6, 2017 - Bug-Fixed and optimized ASM decompression routine. Added comparison with DAN1 for the SlideShow sample. * Jan 18, 2018 - Updated (de)compression tool * Jan 23, 2018 - Fixed fast compression method "-f" to be closer to perfect compression optimization * Jan 26, 2018 - Fixed RLE compression, now provides the expected results for hard to compress data

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.