Unpacking compressed data from ROM to RAM

[+mksmith]

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

 

[Eagle]

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

 

[TailChao]

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

[Synthpopalooza]

There's LZSS, which is currently being used in an Atari 8 project I am working on.  Will investigate.

[+playsoft]

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

[Synthpopalooza]

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

[+mksmith]

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 ?

 

[+mksmith]

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.

[Eagle]

 

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:

1. Assign every byte in the stream a symbol in the huffman tree/dictionary.
2. Look for any short substrings that are repeated and prioritize them by frequency/length.
3. Try replacing the best repeating substring with a new symbol, and add it to the dictionary.
4. If the resulting compressed data (tree + bitstream) is smaller, keep the new symbol and return to 2.
5. 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.

 

[+mksmith]

@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!!

[+mksmith]

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.

[+Muddyfunster]

Thanks for the updated example Matt!

[+mksmith]

26 minutes ago, Muddyfunster said:

Thanks for the updated example Matt!

No probs mate! Been sitting on for too long!

[Eagle]

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

[+mksmith]

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.

[Eagle]

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

[+mksmith]

Interesting table thanks @Eagle ☺️

[Eagle]

 

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

[+mksmith]

@Eagle Awesome mate! Will give it a try shortly!!

[Eagle]

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. 

[+mksmith]

In 7800basic a-z are zero page variables so when using things like pointers back to assembly it's easiest to reference those vars.  

[+mksmith]

@Eagle Fantastic job mate - worked first time!

 

 scrollingmap_ZX7.zip

[+mksmith]

One question - what did you use to pack the data? OS availability?

 

 

[Eagle]

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

[+mksmith]

Ah ok thanks ?