#116651 - ttursas - Sat Jan 27, 2007 10:45 pm
Hi!
I just released my implementations of deflate/inflate, the data compression/decompression
algorithms (LZ77 + dynamic Huffman trees). Grab the sources here: http://www.villehelin.com/nintendoDS.html
I didn't follow the RFC-1951 (DEFLATE) 100%, but what I did should be good enough. :)
Anyway, deflateTT is the commandline tool to compress stuff, and inflateTT-DS is what
you might want to integrate to your Nintendo DS homebrew project.
Note that inflateTT-DS doesn't need malloc() etc. dynamic memory manager, or libnds,
so you should be able to port it also to GBA (just use it the way it is, should work directly?).
Last edited by ttursas on Sat Apr 21, 2007 7:41 pm; edited 1 time in total
#116660 - Lick - Sat Jan 27, 2007 11:46 pm
Wow cool, have you done any tests with it? Is it any better than the BIOS functions?
_________________
http://licklick.wordpress.com
#116661 - tepples - Sat Jan 27, 2007 11:48 pm
| ttursas wrote: |
| I didn't follow the RFC-1951 (DEFLATE) 100%, but what I did should be good enough. :) |
Is it compatible with existing DEFLATE-based formats such as PKZIP and Gzip?
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.
#116685 - ttursas - Sun Jan 28, 2007 10:40 am
I haven't compared it to the BIOS stuff, only to gzip. Here's an example:
The texture that holds the HUD stuff, particles, etc. misc stuff in Wright Flight, 65536B RAW.
With gzip, 3605B. With deflateTT, 3828B.
This is because, I think, I don't store the Huffman trees as optimally as the RFC suggests.
Too lazy to do that. :) Anyway, deflateTT is pretty slow, but inflateTT-DS is fast enough so
that I can on demand, on the fly, decompress those 128x128 airplane textures. I.e., when
a new plane appears on the screen I allocate it room in the VRAM and uncompress its
texture there. Works pretty nicely... Start a network match where each player has his own
plane and see that it works ok. :)
And naturally, in the future, I'll write that inflateTT-DS in ARM. :) But more important things
first...
...
And nope, it's not compatible with PKZIP or Gzip, because I didn't do the header parts
according to the specs. The compressed data is stored the way RFC-1951
describes, so that should be PKZIP/Gzip compatibe, I guess...
Anyway, I just wanted to get about the same level of compression than in Gzip, and
here it is. I don't care about few bytes, needed just something better than my old
RLE packer (anyway, it was just waiting for the moment to be replaced)...
#116686 - ttursas - Sun Jan 28, 2007 10:50 am
If the DS BIOS does only LZ77 decompression, then DEFLATE is better, because
DEFLATE has two phases, first it compresses with LZ77, and then it compresses the LZ77
output with Huffman coding.
#116707 - ttursas - Sun Jan 28, 2007 5:37 pm
I have to add here that inflateTT-DS takes some heap (around 5KBs total) for the Huffman trees, and the
output writing could be more optimal, so if you want faster decompression with less
overhead, LZSS might be a better choice.
inflateTT-DS doesn't decompress to a buffer, but directly to the output, so that's a plus if you
consider memory usage. Also, if you have that 5KBs free elsewhere at the time of decompression,
feel free to modify inflateTT-DS sources to use that memory instead of its static buffers. :)
Plus I'll make the next version of deflateTT/inflateTT to store the Huffman trees according
to the RFC...
#126279 - ttursas - Sat Apr 21, 2007 7:44 pm
Ok, I just released v1.1 of inflateTT and deflateTT (and inflateTT-DS). Now the Huffman
code lengths are also RLE+Huffman compressed so you can expect to get ~200 bytes
smaller files with this release. It's still not 100% RFC-1951 compatible, but almost. :)
#127865 - ttursas - Sat May 05, 2007 11:11 pm
Just released v1.2... v1.1 was a bit buggy, it would choke on big files. Anyway, v1.2 can
also RLE compress the raw Huffman code lengths, just like RFC-1951 says, so v1.2
should be able to give a few bytes smaller archives than v1.1.
EDIT: v1.1 RLE'd zeroes in the Huffman code lengths, v1.2 can also RLE other values
(RLE'd zeroes have their own codes)...
#145918 - ttursas - Sun Nov 25, 2007 4:47 pm
Ok, released version 1.3 of inflateTT-MP. inflate() is now thread safe, has return values, and the header file is C++ compatible. Just started to work on a C++ project with lots of threads... :)
#145921 - knight0fdragon - Sun Nov 25, 2007 6:45 pm
couldnt you use the bios functions to make it faster? I believe the DS has support for both Huffman and LZ77
_________________
http://www.myspace.com/knight0fdragonds
MK DS FC: Dragon 330772 075464
AC WW FC: Anthony SamsClub 1933-3433-9458
MPFH: Dragon 0215 4231 1206
#145922 - tepples - Sun Nov 25, 2007 6:46 pm
BIOS LZ77 is limited in the match length and window size. Besides, BIOS does not compress.
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.
#145927 - knight0fdragon - Sun Nov 25, 2007 8:49 pm
well compressing is not a problem if you are compressing it PC side
_________________
http://www.myspace.com/knight0fdragonds
MK DS FC: Dragon 330772 075464
AC WW FC: Anthony SamsClub 1933-3433-9458
MPFH: Dragon 0215 4231 1206
#146249 - ttursas - Sat Dec 01, 2007 11:05 am
deflateTT/inflateTT are not the optimal tools for data compression, but just something that you can pretty easily plug in. :) I'm using them all over the place, in Nintendo DS, PSP and PC projects, and it's pretty nice to be able to use one simple function call to decompress data with minimal setups etc.
Just consider these as an alternative, ok? :D