Data compression

Ask anything your want about Megadrive/Genesis programming.

Moderator: BigEvilCorporation

Post Reply
Shiru
Very interested
Posts: 786
Joined: Sat Apr 07, 2007 3:11 am
Location: Russia, Moscow
Contact:

Data compression

Post by Shiru » Sun Oct 21, 2007 4:55 am

Is there any data compressors with decompression routines for SMD which can be used in homebrew SMD projects? Mainly for graphic data compression.


I recently made C versions (don't get it wrong, there already was C++ versions for PC made by authors) of decompression routines of two popular ZX Spectrum and MSX compressors:

Hrust - one of best data compressors for ZX, after ZIP, RAR (yes, the famous archivers ported to ZX) and RIP (best native ZX compressor, without PC version unfortunately).

Bitbuster - popular data compressor on MSX scene, made by Team Bomba. Much less effective than Hrust, but with simpler and faster decompression.


Both of these decompressors take few seconds to decompress fullscreen image (35K). Of course, rewritting routines in M68K asm can make they faster to get more acceptable speed. But I currently don't want to rewrite that code (I need to found how to make C functions interface for assembly routines in SGCC first, or make asm version of testing framework). So, I offer this topic to discussion - maybe someone know other suitable compressors or already have complete solution.

Temporary link for my versions of decompression code is here (just headers with code, without testing framework; I tested it with SGCC).

Jorge Nuno
Very interested
Posts: 374
Joined: Mon Jun 11, 2007 3:09 am
Location: Azeitão, PT

Post by Jorge Nuno » Sun Oct 21, 2007 7:51 am

I'm using 2 methods of compressing/decompressing:

Run lenght encoding (RLE) for very repeated things like plain tiles and almost-empty tilemaps. (easy to do in ASM)

Hoffman for tiles that use few colors, like if you only use 3 colors, a pixel will ocupy 1 or 2 bits (I'm doing the compressor ATM)


RLE I have a Decompressor in ASM and a Win EXE comp.

Hoff I have a Dec in ASM and a partial comp in ASM too.

Fonzie
Genny lover
Posts: 323
Joined: Tue Aug 29, 2006 11:17 am
Contact:

Post by Fonzie » Sun Oct 21, 2007 12:35 pm

There was a guy here named Fdarkangel that ported a bunch of stuff to MD...
One of the ported thing (and that was used for tavern rpg until some point) was an LZSS decompressor.
It was pretty fast http://www.genny4ever.net/index.php?page=works (see MDSA benchmark) assuming that the data was compressed pretty nicely (a 32KB file of tiles was like 5KB compressed).

He did C & ASM version of it... and both had a bug on real hardware it seems (like static data randomly added to the result)... very strange... Was maybe a compilation problem.

I still have the sources & computer compressor if anybody want them :)
The main problem over the bug was slow speed (like 3 frames to decompress 160 tiles) and the need of decompression buffer (+dma in case of VRAM use).


I designed a little file system optimized for both megadrive & megacd (padded to 2KB, and very 68K seeking friendly) and Tulio Adriano did a windows software to pack a whole directory using Lzss to this filesystem.
This system is still used on tavern rpg, but without LZSS.
It is called MEGADRIVE SUPER ARCHIVER ^^

:D

------------
Pascal or Kaneda (i don't remember) messed with some nice tile compression routines, used in sonic, maybe?
The advantage of those routines is that they could be decompressed in VRAM immediately, and were pretty fast.

TmEE co.(TM)
Very interested
Posts: 2440
Joined: Tue Dec 05, 2006 1:37 pm
Location: Estonia, Rapla City
Contact:

Post by TmEE co.(TM) » Sun Oct 21, 2007 2:18 pm

I'd go for RLE... very easy to do, and works well if you use it on not too complex images. I need compression in my game too... GFX is taking too much space (PCM too, but you can't MP3 on MD :wink: or ADPCM with good results when the poor Z80 does music and sound effects).
Mida sa loed ? Nagunii aru ei saa ;)
http://www.tmeeco.eu
Files of all broken links and images of mine are found here : http://www.tmeeco.eu/FileDen

Shiru
Very interested
Posts: 786
Joined: Sat Apr 07, 2007 3:11 am
Location: Russia, Moscow
Contact:

Post by Shiru » Sun Oct 21, 2007 2:18 pm

Jorge Nuno wrote:Run lenght encoding (RLE) for very repeated things like plain tiles and almost-empty tilemaps. (easy to do in ASM)
RLE easy to do in anything, but it can be useful only in rare cases, usually it has very low compression rate. However, RLE has two advantages: it's very fast and doesn't require RAM buffer to depack (like LZ-based compressors requires). I even did sprite rendering routine with RLE decompression on fly (not for SMD, of course).
Fonzie wrote:assuming that the data was compressed pretty nicely (a 32KB file of tiles was like 5KB compressed)
That's not very objective measure. Tilesets can be very different, some can be well compressed even with RLE, some compresses bad with any compressors. To compare compression effectivity test must be done, so it will be good if you share at least PC compression utility.

I have such test results (done by Alone Coder in this year) for some ZX, MSX and PC compressors:

Code: Select all

           unpacker  file1   file2    file3   file4
unpacked        0     6376    11142    1652    1231
MS Pack       195     5352     8986    1349     983
Bitbuster*    112?    5281     9099    1319     989
Pletter*      112     5244     8954    1326     975
Hrum          119     5238     8956    1297     970
MegaLZ*       110     5195     8883    1293     969
Hrust2 (QC)   181     5195     8798    1304     976
Pucrunch*     255     5164     8797    1257   not comp.
Hrust1        225     5123     8740    1271     967
ZIP (zlib)*  none     5013     8627    1249     964
ZIP (7zip)*  none     4984     8552    1247     962
RAR 2.50*    1968     4976     8479    1258     977
RIP           244     4969     8443    1262     977
mRIP          220     4970     8457    1252     974
ZXRAR         385     4959     8449    1250     967
LZMA (7zip)* none     4952     8406    1201     960
Unpacker means size of unpacker routine for Z80 if exists. Test files were some programs and games for ZX Spectrum (both code, graphics, etc). They still available for further tests.

Fonzie wrote:Pascal or Kaneda (i don't remember) messed with some nice tile compression routines, used in sonic, maybe?
The advantage of those routines is that they could be decompressed in VRAM immediately, and were pretty fast.
I think, ROMhackers and hobbyist console games translators know many such routines and have (de)compressors for them. That good idea, decompression directly to VRAM is very good feature, but I think that achieved due to low compression rate.

tomaitheous
Very interested
Posts: 256
Joined: Tue Sep 11, 2007 9:10 pm

Post by tomaitheous » Mon Oct 22, 2007 1:18 am

Nice comparison list Shiru. I converted pucrunch decompressor for another platform - it's a pretty decent compressor.

I found quite a few LZSS compression schemes that use a circular buffer for mem->I/O (one that did I/O->I/O), avoiding the need to decompress large files before copying them to VRAM, etc. And one LZSS scheme that preloaded the LZ window (actually circular buffer) before decompression - that threw me off when I was writting the decompressor for the data :D.

KanedaFr
Administrateur
Posts: 1139
Joined: Tue Aug 29, 2006 10:56 am
Contact:

Post by KanedaFr » Mon Oct 22, 2007 7:18 am

Fonzie wrote: Pascal or Kaneda (i don't remember) messed with some nice tile compression routines, used in sonic, maybe?
The advantage of those routines is that they could be decompressed in VRAM immediately, and were pretty fast.
I used the RLE algo from Charles MacD ;)
it's full asm68k and write directly in VRAM

It's first use was in Bmp2Tile so...you can see i use it without problem for sooo long.
I optimized it with the help of former devega forum users some years ago.
I 'recently' mod the unpacker to return the number of tiles unpacked.

WayneK
Newbie
Posts: 7
Joined: Tue Apr 17, 2007 8:58 pm

Post by WayneK » Mon Oct 22, 2007 9:48 am

I used RNC (Rob Northen Compressor) which was a popular packer on many platforms during the MD's active years... you can find a cmdline PC exe packer for the data (mode1 - best pack/slow unpack, mode 2 - ok packing/fast unpack) and source for the 2 decrunchers on devrs.com (perhaps in the GB or GBA section I can't remember, but the archive includes source for unpacking on many platforms, 68000 included).

If I remember correctly, the game "Bubble + Squeak" on MD uses RNC Mode 1, and so the decruncher can be borrowed directly from there if you have any problems with the generic 68000 decrunch source :)

drx
Interested
Posts: 16
Joined: Mon Jul 02, 2007 8:45 pm

Post by drx » Fri Nov 16, 2007 3:52 pm

Sonic 3D uses both RNC1 and RNC2.

More on topic, there are a lot of different compression format for various uses in MD games. In Sonic games there are three - you can just grab a disassembly and steal it from there :P

Post Reply