Search the Community
Showing results for tags 'compression'.
-
Hi! I made a modified version of the ZX0 compressor to make the decompressor smaller (and faster) in the 6502, by sacrificing about 0.5% compression ratio. The intended use is compressing data up to about 10kB, or where the decompressor size should be as small as possible. Current 6502 code is 130 bytes for the small decompressor (this includes the initialization) and 175 bytes for the fast version. Note that the compressor is only a slightly modified version of the original ZX0 compressor by Einar Saukas, but the decompressors (C and 6502 versions) are by me. Code and documentation is here: https://github.com/dmsc/zx02 , go to the releases to download the compiled compressor for linux and windows. EDIT: I added a third 6502 decompressor, with a trade off between size and speed, at 138 bytes it will probably be the best to use in most situations. Current stats in the "conan.gfx" file are: File Size (bytes) Speed (cycles/bytes) zx02-fast.asm 175 48.1 zx02-optim.asm 138 58.0 zx02-small.asm 130 72.6 Have Fun!
-
Hi everyone, A few of us (@Muddyfunster, @Synthpopalooza) were having a discussion about data compression and unpacking of data such as level maps and sound/tunes. I was doing a bit of study around the AA forum and came across some discussions here: https://atariage.com/forums/topic/316628-most-efficient-compression-for-atari/ https://atariage.com/forums/topic/291154-any-compressor-between-rle-and-lz4/ There appears to be a number of routines which might be useful some of which do have a 6502 conversion for other machines. I see the main feature having the ability to unpack stored data from ROM into RAM. For example both Millie & Molly and Exo have a huge amount of ROM set aside (eg. 1-2 banks!) for pokey music reducing our capacity to include more features etc. I see the process working as follows: Compress a binary data file using a command-line tool Convert compressed binary data in a data table To unpack - set the input (ROM) and output (RAM) pointers and process As an example I used the zx0 compressor to reduce 4096 bytes down to 680 bytes. Anyway, does anyone have any working examples which we could utilise in 7800basic? (assembly is fine for use in the backend) I feel this could be a really useful step for 7800 developers to have an ability to store compressed data. EXAMPLE CODE (currently LZ4, ZX0, ZX7) Thanks to @playsoft, @Eagle and @xxl for assisting with compression libraries and @RevEng for initial 7800basic compatibility 20220215.Compression.zip
-
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!
- 3 replies
-
- 2
-
- lossless
- compression
- (and 7 more)
-
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
- 5 replies
-
- 3
-
- lossless
- compression
-
(and 1 more)
Tagged with:
-
DAN2 Lossless Compression by Daniel Bienvenu aka NewColeco A variant of DAN1 Compression Format Based on LZ77 data compression, multiple offset sizes, unary code and elias gamma. The project started after Alekmaul remarks and test data during December 2016. Technical information Three (3) differences compared to DAN1: The set of 4 different sizes to encode offset values becomes { 1, 4, 8, max } where max value is set by the user. The capability to store sequences of literal bytes is removed. The END OF DATA code is 17 bits long instead of 18. The data format changed a little, making it incompatible with the original DAN1 format. The first bits is an unary code to set the maximum of bits for offset values ( 0 = 10 bits, 10 = 11 bits, 110 = 12 bits, etc.) The second byte is the first raw byte to copy as literal. The rest of the data format follows similar to DAN1 specifications, except there is no sequences of literals (RLE) and also the END code is shorter by 1 bit. Comparing DAN1 and DAN2 In term of speed, the compression and decompression are virtually the same speed as DAN1. In term of size, the decompression routine is slightly bigger than DAN1, +7 bytes according to my z80 data compression library. The expected improvement in compression ratio is only due to the possibility to adjust the maximum number of bits to encode offsets. Test samples from Exomizer test1.bin (audio wave file) Original: 202762 ZX7: 223933 DAN1: 204208 (sequences of raw bytes help to not blow up in size) DAN2 -m 16: 216898 Pletter: 221245 MegaLZ: 221136 Aplib aka APPACK: 219793 PUCrunch: N/A test2.bin (text file filled only with the letter q) Original: 196608 ZX7: 19 DAN1: 18 DAN2 -f -m 10: 18 Pletter: N/A *error during compression* MegaLZ: 2510 Aplib aka APPACK: 19 PUCrunch: N/A test3.bin (formatted text file with fields such as name and date) Original: 111261 ZX7: 52035 DAN1: 48103 DAN2 -m 16: 37048 Pletter: 44563 MegaLZ: 47052 Aplib aka APPACK: 37094 PUCrunch: N/A Test samples from Alekmaul Robee Blaster Title (Pattern, Color, and Name version) Original: 2024, 2024 and 768. Total 4816 ZX7: 970, 790 and 383. Total 2143 DAN1: 965, 793 and 385. Total 2143 DAN2 m -10: 947, 784 and 385. Total 2116 Pletter: 957, 787 and 385. Total 2129 MegaLZ: 972, 806 and 384. Total 2162 Aplib aka APPACK: 986, 806 and 384. Total 2176 PUCrunch -d -c0 -s: 940, 772 and 373. Total 2085 Robee Blaster Title (Pattern and Color only version) Original: 6144 and 6144. Total 12288 ZX7: 1257 and 793. Total 2049 DAN1: 1248 and 799. Total 2047 DAN2 -m 11: 1233 and 791. Total 2024 Pletter: 1259 and 795. Total 2054 MegaLZ: 1269 and 832. Total 2101 Aplib ka APPACK: 1273 and 825. Total 2098 PUCrunch -d -c0 -s: 1235 and 770. Total 2005 Test Sample Bitmap Graphic II Download DAN2 (EXE, SRC, ASM) version BETA-20170106 : dan2-beta-20170106.zip Change Log for version BETA-20170106: increased up to 16 bits max offset size value fixed bug with default max bits fixed bug occurring with test2.bin sample DAN2 (EXE, SRC, ASM) version BETA-20170101 : dan2-beta-20170101.zip * BUG FOUND , PLEASE DOWNLOAD NEWER VERSION *
-
I've been thinking about how to add efficient, fast compression of level data to Alex Kidd. Currently, the widest level possible (unpacked) due to memory constraints is 1280px wide (or, 160 characters, or 5 screens). The level in the current Alex Kidd demo fully exploits that space, and it is the smallest I have in my current designs. This takes slightly less than 4k of RAM (3840 bytes, to be exact). So, I need to come up with a form of compression of the levels that has a number of characteristics: Compress the data enough so that total memory consumption for a map of 3072px wide (the largest map I currently have designed) is less than the 3840 bytes currently available (and actually, I probably need to shoot for something around 3kb 'cause I need some memory back for other things, such as longer music tracks). Is extremely fast to unpack to VDP: I need to copy three to six rows (96 - 192 bytes) of unpacked data to the VDP every frame, depending on how fast Alex is running (he runs fast enough to need two-pixel scroll increments at times). Add to that the 128 bytes for the sprite table that need to be uploaded every frame, as well as the game logic even with the uncompressed map I'm close to the edge of the the machine can do with the current C code. Allow for dynamic modifications to the map. This is probably the most annoying requirement, but since Alex can destroy parts of the world (rocks get replace by nothing, boxes replaced by money bags or special items, specials items and money bags by nothing) I need to be able to take those out for as long as that part is potentially on screen. Because of that, simple RLE is out of the question. So I ruled out RLE. Besides that, the obvious one is to look at the way the levels are built up: every item on screen can be represented by a 16x16 meta-tile. Using the meta-tile approach, the map data itself of course compresses to 25% of it's original size, and the meta-tile dictionary will take up around 800 - 1024 bytes, depending on the complexity of the map. This puts the largest map at around 2k, so the compression result is excellent. However, uploading this to the VDP turns out to be slower than expected. In iterating over the metatiles, I need to see whether I'm uploading odd or even rows, and starting from odd or even columns and that code slows things down enough to push me over the limit of what I still have available in the time for one frame (well, when Alex is running at least, when he moves slowly, I only need to do this for three rows and that still seems to work fine). I can do a couple of things to remedy this (optimize the lookup code, unroll some loops, hand code it in assembly, ...), but I wanted to see of someone else can think of a super-duper way of compressing the data that is nearly free when it comes to turning it into something that I can upload to the VDP.
-
Has anyone written an assembly language LZ decompression routine for the TI? I'm thinking about compressing some game maps on the PC and decompressing them on the TI (to avoid in-game loading), so if it had a PC compression counterpart that would be great. The only utility I know about is Barry Boone's archiver, but I don't suppose that would be easy to integrate into a game?
-
It's not the first time we talk about data compression, particulary for graphics and because. For graphics, we want a way to decompress data directly into VRAM using near to zero extra RAM space. The common ways to compress data are Run Length Encoding, Huffman and Dictionary. Run Length Encoding (RLE) is the fastest one to encode and decode and can give a decent compression ratio. Huffman is basicaly an optimization by encoding with a small number of bits what occurs the most. Its decompression time is usually a bit longer than for other compression methods. Not a big deal normaly since it's during the initialiation of the graphics for a title screen or a grame screen. Dictionary compression is normaly the best one, but its main problem is usualy the need for extra memory space to create the dictionary while decompressing data which isn't the way to go for ColecoVision games because of the limited RAM space. I created my own data compression long ago which is basicaly an improved encoded RLE compression by using a fixed huffman to encode data. I called it DAN0 and I'm quite proud of myself for saving even more ROM space than with the RLE method I was using for years. Then I was curious to see the other data compressions and I saw that there are many many of them, some can decompress data directly into VRAM, and some of them are just simply better than the others. To help comparing the different data compressions out there, I decided to use a bitmap screen 256x192 with just enough complexity in it to see a difference in size for the different results of compression. LET'S COMPARE SOME OF THE DATA COMPRESSION WE MIGHT USE FOR TITLE SCREENS From my ColecoVision Strip Poker game project : strippokertitlescreen.zip RAW (no compression) : 12288 bytes RLE : 4528 DAN0 : 4143 Pucrunch : 4000 BitBuster or BitBuster Extreme : 3595 PLETTER : 3557 aPLib : 3543 MegaLZ : 3524 Exomizer v2 : 3337 Please note that the size of the program to decompress the data isn't included. Because the end result depends mostly on the original data, we can't say that Exomizer is the best, sometimes aPLib is better than Exomizer, it varies. But a few things are constant like DAN0 is always better than RLE, and Pletter is always better than BitBuster. Side note : SMS homebrew scene is very interesting for ColecoVision homebrewers because it imply Z80 assembly and the port number for VRAM is the same. Which makes links like this one from Maxim quite interesting. Feel free to comment, ask questions, and do your own tests with other data compression programs
- 41 replies
-
- data compression
- compression
-
(and 8 more)
Tagged with: