+mksmith Posted June 5, 2021 Share Posted June 5, 2021 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 5 Quote Link to comment https://forums.atariage.com/topic/321346-unpacking-compressed-data-from-rom-to-ram/ Share on other sites More sharing options...
Eagle Posted June 5, 2021 Share Posted June 5, 2021 The main problem is that the A7800 only has 4kb of ram I've always used RLE for level maps. https://github.com/tebe6502/Mad-Assembler/tree/master/examples/compression 4 Quote Link to comment https://forums.atariage.com/topic/321346-unpacking-compressed-data-from-rom-to-ram/#findComment-4837498 Share on other sites More sharing options...
TailChao Posted June 5, 2021 Share Posted June 5, 2021 (edited) I've been using puCrunch to compress graphics, stage maps, and scripts for awhile. Its performance (in terms of packing the data) is quite good and the license is fairly lenient for closed-source games (WXWindows Library License). Unfortunately, none of the below is for 7800basic - but can likely be adapted for it. Asterisks in the procedure come with which type of data you're compressing and what it's dependent upon. In my case... Graphics are run through the compressor as-is. Maps and scripts have the possibility of referencing uncompressed data or calling out to code (or may - in my case they do), so they're run through a "mini-assembler" first using a DASM symbol table and then compressed. The only restriction here is that compressed data can't reference assets within other compressed data. Both are unpacked to EXRAM as needed, since this takes awhile you may want to consider implementing this as a background task (so it can run asynchronously for several frames). I didn't do this on the 7800 but have on other hardware, basically so you don't have to stall the game while the depacker does its thing. Unpacking addresses are fixed, but that's not a huge problem here. That's basically it. Addendum : Nope, it's not. I also recommend the usual sacrilege of looking at how some NES games handle compressed resources, as it's extremely common there. Edited June 5, 2021 by TailChao 5 Quote Link to comment https://forums.atariage.com/topic/321346-unpacking-compressed-data-from-rom-to-ram/#findComment-4837539 Share on other sites More sharing options...
Synthpopalooza Posted June 5, 2021 Share Posted June 5, 2021 There's LZSS, which is currently being used in an Atari 8 project I am working on. Will investigate. 2 Quote Link to comment https://forums.atariage.com/topic/321346-unpacking-compressed-data-from-rom-to-ram/#findComment-4837543 Share on other sites More sharing options...
+playsoft Posted June 5, 2021 Share Posted June 5, 2021 For general compression I tend to use LZ4 on the A8/5200 and have made a quick 7800basic test. I'm not that familiar with 7800basic so I probably haven't interfaced to it in the best way. Basically you need to set 3 variables; the LZ4 data source address, the destination address and the destination end address then call lz4_decode. The lz4_decode routine needs 6 bytes in ZP for pointers, plus some other variables which can go anywhere (these are all temporary and only needed for the duration of the lz4_decode call). The my_lz4.exe command line program is the standard LZ4 code with the header information removed, just run this with the file you want to compress (e.g. my_lz4 graphics\image.dat). test.zip 3 Quote Link to comment https://forums.atariage.com/topic/321346-unpacking-compressed-data-from-rom-to-ram/#findComment-4837652 Share on other sites More sharing options...
Synthpopalooza Posted June 5, 2021 Share Posted June 5, 2021 (edited) 8 hours ago, Eagle said: The main problem is that the A7800 only has 4kb of ram There are other setups that allow extra RAM, including the 512k bankram, and the XM 128K RAM setup which I believe is accessible on Dragonfly. Edited June 5, 2021 by Synthpopalooza 1 Quote Link to comment https://forums.atariage.com/topic/321346-unpacking-compressed-data-from-rom-to-ram/#findComment-4837721 Share on other sites More sharing options...
+mksmith Posted June 6, 2021 Author Share Posted June 6, 2021 Thanks everyone for your thoughts and contributions! I thought this might be a really good discussion point! 13 hours ago, TailChao said: I've been using puCrunch to compress graphics, stage maps, and scripts for awhile. Its performance (in terms of packing the data) is quite good and the license is fairly lenient for closed-source games (WXWindows Library License). Unfortunately, none of the below is for 7800basic - but can likely be adapted for it. Asterisks in the procedure come with which type of data you're compressing and what it's dependent upon. In my case... Graphics are run through the compressor as-is. Maps and scripts have the possibility of referencing uncompressed data or calling out to code (or may - in my case they do), so they're run through a "mini-assembler" first using a DASM symbol table and then compressed. The only restriction here is that compressed data can't reference assets within other compressed data. Both are unpacked to EXRAM as needed, since this takes awhile you may want to consider implementing this as a background task (so it can run asynchronously for several frames). I didn't do this on the 7800 but have on other hardware, basically so you don't have to stall the game while the depacker does its thing. Unpacking addresses are fixed, but that's not a huge problem here. That's basically it. Addendum : Nope, it's not. I also recommend the usual sacrilege of looking at how some NES games handle compressed resources, as it's extremely common there. Thanks TC - will check that out and see what I can read up on ? 8 hours ago, playsoft said: For general compression I tend to use LZ4 on the A8/5200 and have made a quick 7800basic test. I'm not that familiar with 7800basic so I probably haven't interfaced to it in the best way. Basically you need to set 3 variables; the LZ4 data source address, the destination address and the destination end address then call lz4_decode. The lz4_decode routine needs 6 bytes in ZP for pointers, plus some other variables which can go anywhere (these are all temporary and only needed for the duration of the lz4_decode call). The my_lz4.exe command line program is the standard LZ4 code with the header information removed, just run this with the file you want to compress (e.g. my_lz4 graphics\image.dat). test.zip 401.09 kB · 2 downloads Brilliant to see a great working example thanks Paul. Always takes me a bit to get around integration of asm libraries initially so this is very helpful ? 2 Quote Link to comment https://forums.atariage.com/topic/321346-unpacking-compressed-data-from-rom-to-ram/#findComment-4837903 Share on other sites More sharing options...
+mksmith Posted June 6, 2021 Author Share Posted June 6, 2021 15 hours ago, Eagle said: The main problem is that the A7800 only has 4kb of ram I've always used RLE for level maps. https://github.com/tebe6502/Mad-Assembler/tree/master/examples/compression Thank Eagle! Will check that out. I generally use 128KRam carts for my games as I find having access to $4000-$7fff very useful. In Millie & Molly I used 4k for the DL, around 9k for the rewind buffer and the remaining for playing the pokey out of RAM for the in-game tunes. 1 Quote Link to comment https://forums.atariage.com/topic/321346-unpacking-compressed-data-from-rom-to-ram/#findComment-4837904 Share on other sites More sharing options...
Eagle Posted November 22, 2021 Share Posted November 22, 2021 https://github.com/bbbradsmith/huffmunch Quote Huffmunch is directly inspired by the DEFLATE algorithm widely known for its use in the ZIP file format, but with an interest in making something suitable for the NES. Goals: Provides serial decompression of a stream of data, one byte at a time. Uses an extremely small amount of RAM. Takes advantage of random access to ROM for the compressed data. Has reasonable performance on the low-powered 6502 CPU. At a high level, DEFLATE uses two major compression techniques in tandem: An LZ algorithm builds a dictionary of commonly repeated substrings of symbols as the data is decompressed, and allows further repetitions of these dictionary entries to be replaced by a much smaller reference symbol. A Huffman tree uses distribution of symbol frequency to find an optimal way to store the stream of symbols and references. The main problem with LZ techniques here is that they require the decompressor to build up a dictionary out of the decompressed data, meaning it the decompressed data has to be stored in RAM so that it can be accessed. Huffmunch takes a similar approach: A Huffman tree is used to encode symbols optimally according to frequency. Each symbol may represent a single byte, or a longer string. A symbol may additionally reference another symbol as a suffix. Here the dictionary is stored directly in the Huffman tree structure, and the suffix ability allows longer symbols to combine their data with shorter ones for some added efficiency. Because the tree structure explicitly contains all the symbols to be decoded, it can reside in ROM, and only a trivial amount of RAM is needed to traverse the tree. The compression algorithm itself is currently a fairly naïve hill climbing method: Assign every byte in the stream a symbol in the huffman tree/dictionary. Look for any short substrings that are repeated and prioritize them by frequency/length. Try replacing the best repeating substring with a new symbol, and add it to the dictionary. If the resulting compressed data (tree + bitstream) is smaller, keep the new symbol and return to 2. Otherwise try the next most likely substring, until one that successfully shrinks the data is found (return to 2), or after enough attempts end the search. Longer repeated strings will gradually be built up from shorter ones that can combine. Eventually the tree will grow large enough that adding a new symbol requires more tree data than can be saved by that symbol's repetition; at that point compression will cease. There may be more optimal ways to do this, but this was relatively simple to implement, and seems to perform well enough on data sets that are a reasonable size for the NES. I'm open to suggestions for improvement here. 4 Quote Link to comment https://forums.atariage.com/topic/321346-unpacking-compressed-data-from-rom-to-ram/#findComment-4952108 Share on other sites More sharing options...
+mksmith Posted November 23, 2021 Author Share Posted November 23, 2021 @Eagle Thanks mate for listing another potential option!! I have been using the one @playsoft (thanks Paul ?) provided in a number of projects recently and it's been working great. With PETSCII robots i've managed to squeeze in all 10 levels into 2 banks with a 1k or so spare in each and it unpacks nice and quick too. I need to put up an example project to show this off soon. Gotta love our community here!! 7 Quote Link to comment https://forums.atariage.com/topic/321346-unpacking-compressed-data-from-rom-to-ram/#findComment-4952643 Share on other sites More sharing options...
+mksmith Posted February 6, 2022 Author Share Posted February 6, 2022 Hi all, Please find attached an example compression and scrolling map (created in Tiled) displaying the first half of the GnG Level 1 map. Thanks go to @playsoft for the LZ4 routine and @RevEng for checking over a few things when integrating into 7800basic. Please note a few limitations with this method: Max 256 tiles wide 3 colors only for the backgrounds all tile gfx must existing in the same gfx block (including text) so I think it's 256 (4x8) or 128 (8x8) compressionandscrollingmap.zip I really think going forward compression is going to play a big part in 7800 games much like it does on the c64. As noted above with PETSCII 7800 we have included all the maps (now 13 across 3 banks) - would never have been possible otherwise. 3 1 Quote Link to comment https://forums.atariage.com/topic/321346-unpacking-compressed-data-from-rom-to-ram/#findComment-4999290 Share on other sites More sharing options...
+Muddyfunster Posted February 6, 2022 Share Posted February 6, 2022 Thanks for the updated example Matt! 1 Quote Link to comment https://forums.atariage.com/topic/321346-unpacking-compressed-data-from-rom-to-ram/#findComment-4999465 Share on other sites More sharing options...
+mksmith Posted February 6, 2022 Author Share Posted February 6, 2022 26 minutes ago, Muddyfunster said: Thanks for the updated example Matt! No probs mate! Been sitting on for too long! Quote Link to comment https://forums.atariage.com/topic/321346-unpacking-compressed-data-from-rom-to-ram/#findComment-4999477 Share on other sites More sharing options...
Eagle Posted February 6, 2022 Share Posted February 6, 2022 (edited) I did some tests with other compressors for comparison Level11Map.lz4.binary - 900 bytes I tested Level11Map.binary Exomizer - 634 bytes ZX0 - 682 bytes Deflate - 698 bytes Pucrunch - 707 bytes http://xxl.atari.pl/zx0-decompressor/ http://github.com/tebe6502/Mad-Assembler/tree/master/examples/compression Unfortunately I have no clue about 7800Basic ;( Level11Map.binary.exo Level11Map.binary.deflate Level11Map.binary.pck Level11Map.binary.zx0 Edited February 6, 2022 by Eagle 1 Quote Link to comment https://forums.atariage.com/topic/321346-unpacking-compressed-data-from-rom-to-ram/#findComment-4999530 Share on other sites More sharing options...
+mksmith Posted February 6, 2022 Author Share Posted February 6, 2022 Good comparison and some nice savings there! Getting the code working in 7800basic just involves inlining the 6502 generally.but sometimes requires updating references to some of 7800basics zeropage layout. I'm starting to get better at 6502 after working PETSCII so might take a look at some stage. The LZ4 one has proven a great comprise so far between size and speed. Be nice to eventually have a few to use for the community. 2 Quote Link to comment https://forums.atariage.com/topic/321346-unpacking-compressed-data-from-rom-to-ram/#findComment-4999679 Share on other sites More sharing options...
Eagle Posted February 6, 2022 Share Posted February 6, 2022 (edited) BTW Shrinkler the best again 620 bytes Very slow unpack (~4,5kB/s) https://github.com/atari8xxl/unShrinkler Level11Map.binary.shr Edited February 6, 2022 by Eagle 3 Quote Link to comment https://forums.atariage.com/topic/321346-unpacking-compressed-data-from-rom-to-ram/#findComment-4999706 Share on other sites More sharing options...
+mksmith Posted February 6, 2022 Author Share Posted February 6, 2022 Interesting table thanks @Eagle ☺️ Quote Link to comment https://forums.atariage.com/topic/321346-unpacking-compressed-data-from-rom-to-ram/#findComment-4999891 Share on other sites More sharing options...
Eagle Posted February 7, 2022 Share Posted February 7, 2022 (edited) ZX7 packer - 734 bytes Unpack for Level11Map - 10 frames I tried my best Hope it works. @mksmith let me know so I can try another one https://xxl.atari.pl/zx7-decompressor/ 7800BASIC Quote rem unpack compressed data asm SET_POINTER ZX7_INPUT,Level11CompressedMapData SET_POINTER ZX7_OUTPUT,MAPSCREENRAM jsr unZX7 end ASM Quote token = a ;$F0 lenL = token+1 offsL = lenL+1 copysrc = offsL+1 ZX7_INPUT = copysrc+2 ZX7_OUTPUT = ZX7_INPUT+2 unZX7 ldy #$00 lda #$80 sta token copyby jsr GET_BYTE jsr PUT_BYTE mainlo jsr getbits bcc copyby lda #$01 sta lenL lenval jsr getbits rol lenL bcs _ret ; koniec jsr getbits bcc lenval jsr GET_BYTE sta offsL lda ZX7_OUTPUT clc ; !!!! C=0 sbc offsL sta copysrc lda ZX7_OUTPUT+1 sbc #$00 sta copysrc+1 cop0 lda (copysrc),y inc copysrc bne skip_copy_inc inc copysrc+1 skip_copy_inc jsr PUT_BYTE dec lenL bne cop0 jmp mainlo getbits asl token ; bez c bne _ret jsr GET_BYTE rol @ ; c sta token _ret rts GET_BYTE lda (zx7_input),y inc zx7_input bne g_b1 inc zx7_input+1 g_b1 rts PUT_BYTE sta (zx7_output),y inc zx7_output bne p_b1 inc zx7_output+1 p_b1 rts download packer https://github.com/antoniovillena/zx7mini Level11Map.binary.zx7 Edited February 7, 2022 by Eagle 1 Quote Link to comment https://forums.atariage.com/topic/321346-unpacking-compressed-data-from-rom-to-ram/#findComment-5000401 Share on other sites More sharing options...
+mksmith Posted February 7, 2022 Author Share Posted February 7, 2022 @Eagle Awesome mate! Will give it a try shortly!! 2 Quote Link to comment https://forums.atariage.com/topic/321346-unpacking-compressed-data-from-rom-to-ram/#findComment-5000606 Share on other sites More sharing options...
Eagle Posted February 8, 2022 Share Posted February 8, 2022 I’m 100% sure about Asm part, it’s working fine. No idea about 7800 basic. token = a ;$F0 should be on zero page (e.g. $F0) but looks like basic works different so I used “a” like in your example. Hope you figure it out. 2 Quote Link to comment https://forums.atariage.com/topic/321346-unpacking-compressed-data-from-rom-to-ram/#findComment-5000627 Share on other sites More sharing options...
+mksmith Posted February 8, 2022 Author Share Posted February 8, 2022 In 7800basic a-z are zero page variables so when using things like pointers back to assembly it's easiest to reference those vars. 2 Quote Link to comment https://forums.atariage.com/topic/321346-unpacking-compressed-data-from-rom-to-ram/#findComment-5000630 Share on other sites More sharing options...
+mksmith Posted February 8, 2022 Author Share Posted February 8, 2022 @Eagle Fantastic job mate - worked first time! scrollingmap_ZX7.zip 2 1 Quote Link to comment https://forums.atariage.com/topic/321346-unpacking-compressed-data-from-rom-to-ram/#findComment-5000658 Share on other sites More sharing options...
+mksmith Posted February 8, 2022 Author Share Posted February 8, 2022 One question - what did you use to pack the data? OS availability? Quote Link to comment https://forums.atariage.com/topic/321346-unpacking-compressed-data-from-rom-to-ram/#findComment-5000694 Share on other sites More sharing options...
Eagle Posted February 8, 2022 Share Posted February 8, 2022 (edited) Thanks. I will try next one I used zx7mini.exe from https://github.com/antoniovillena/zx7mini I’m afraid this only Windows. However, the source code is available. Edited February 8, 2022 by Eagle Quote Link to comment https://forums.atariage.com/topic/321346-unpacking-compressed-data-from-rom-to-ram/#findComment-5000862 Share on other sites More sharing options...
+mksmith Posted February 8, 2022 Author Share Posted February 8, 2022 Ah ok thanks ? Quote Link to comment https://forums.atariage.com/topic/321346-unpacking-compressed-data-from-rom-to-ram/#findComment-5000869 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.