Data Compression

[hotdog1234]

Where can I get information on basic data compression and decompression? I don't need code, just information on compression bit-level wise.

[Graphmastur]

Go to ticalc.org, and search ezcmp. It should be the first one on the list. Read how the method works. It can be used recursively, so you could take an entire 16384 byte app page, and turn it into 1/4 of a page. Since you know you are working with 16384 bytes, then you should be able to make it run, say, 50 times. You would not have to store the first 3 bytes it asks for. This is for SAD?

[hotdog1234]

[Mapar007]

You could ask Darkstone Knight, he's been developing a lz77/Huffman coding compression method for one of his games.

[cjgone]

Huffman compression is pretty easy compared to other methods and fairly optimal. It requires knowledge of how binary trees work; the steps to use it are fairly straightforward.


The idea is that by finding the frequencies of how often a letter appears in something, you can use these frequencies and a natural order (look this us, a priority queue) and make one binary tree that holds all the letters. You can make a binary code by adding a 1 to every left you take on the tree and a 0 for every right (i don't think it matters if left =0 and right =1).

So in the pic below:

h = 011

a = 01

every letter has a unique binary code and by putting it all together, you can use mutiple letters to make up one byte. So a = 01, thats like 2-bits, so four 'a's is one byte instead of 4 bytes.

more common words are higher up in the tree thru natural order, you have to look that up.


In the pic below is a tree of letter frequencies and the binary value 0 or 1 associated with each one. This is not the correct assemblage of a tree, the method to do so is defined a million times online tho.


It goes something like this tho:

You put a structure or node that contains the letter and its frequency for each character into something called a priorty queue, where thru ordering when you take out the nodes\structures they're in the "natural order". Now you take 2 nodes out, create a new tree combining them and you put it back into the queue and you continue to assemble all the nodes into one whole tree.

[Graphmastur]

Huffman kinda depends on the data being compressed. If you don't use 256 different bytes, huffman is the way to go. If there is just a little over 15 bytes, the one mentioned before is great. If you understand huffman, and think you can do it in asm, then go for it!!

[cjgone]

Meh, making a binary tree in assembler doesn't seem to bad other then having to like dynamically allocate memory for nodes.. You could pre define it all tho ;)

A general look would be

[hotdog1234]

Huffman is not my intention...I think I'll probably end up doing my own compression routine.

[cjgone]

^Your own compression routine? O_OOO_O_O

lol, stick with the already done routines bro, it'll be the most worthwhile time wise anyway.\


There's also another way that finds repeating phrases and searches thru teh data and replaces them with less data thru a table. Which has already been defined too, but it might be slow on a calc.

Write a decompressor on the calc and the compressor on ur comp. That's be the best way.

[cjgone]

You can be extremely cool and find an already written compressor that outputs the compressed data and a necessary lookup table, and then just write a simple decompressor on the calc that uses the lookup table to do the easy find and replace.

[hotdog1234]

[cjgone]

If you're just trying to compress ur home screen and big pics with all that black space, you can pretty eassily do that with find and repalce methods.

[hotdog1234]

[cjgone]

Archive run your game thru mirageos if memory is a big deal?

[hotdog1234]

[FloppusMaximus]

Try lots of different techniques. You may find that some of them work better than you expect.

Using (classical, non-adaptive) Huffman coding is easy to decompress, and gives a modest amount of compression for many different kinds of data, so don't be too quick to dismiss it. It's common to use some form of Huffman coding in *addition* to an LZ-like algorithm.

It's perfectly fine to try to invent your own algorithms - take advantage of the particular redundancies of your data set. But then try them out and see how they compare to the more established algorithms.

Remember, too, that the only things that should concern you are the compression ratio and the size and speed of the decompressor. If it takes an hour to compress the data on the PC, who cares?

[briandm03]

Im sure you've already found this file, but search for compression techniques at ticalc. This is how i learned the basics of compression, many thanks to the author!

[hotdog1234]

Briandm03, you hit the nail on the head! THANKS! That was JUST the file I needed, but couldn't find and no one else suggested. Now I don't have to come up with my own routines!

I just have to work out which routines to use now. I'm probably going to use SRLE for maps and Huffman for Campaign text, both of which have routines. As for sprites and full-sized pics, I'll have to experiment with different solutions I found.

EDIT: I'm looking at Levi Lansing's bmp2asm converter, which only works for full-sized ti-86 pictures. Since I like the compression ratio, and understand the concept, I'll probably use a modified verion of his decompressor and end up writing my own compressor using his technique.

[darkstone knight]

[Graphmastur]

Hmmm. Is Lz77 the same as zlib .zip compression? It looks like it works the same way.