well, the main problem here is that most options for compressing on-calc(especially if there's lots of features/fancy GUI, etc.) take up a lot of space, most of the time more than is saved by the compression of the program

it might make more sense to compress it off-calc.
that would require computer access for every user though :\
I don't know...

I suggest looking up the DEFLATE standard, which is open and specified in an RFC, unlike RAR.

Would you perhaps be so kind as to write me a routine that compresses and decompresses a file? Or perhaps psuedocode it.

isn't that just asking for him to write the entire thing for you?
also, i was under the impression that more complex compression formats like this were compressed off-calc because the calculators have too little RAM to handle it. (see Iambian's pucrunch programs).

Quote from: ACagliano on February 23, 2012, 02:32:17 pm

Would you perhaps be so kind as to write me a routine that compresses and decompresses a file? Or perhaps psuedocode it.

isn't that just asking for him to write the entire thing for you?
also, i was under the impression that more complex compression formats like this were compressed off-calc because the calculators have too little RAM to handle it. (see Iambian's pucrunch programs).

I think Iambian made a pucrunch compressor as an Axiom (or something similar to that).


For ACagliano, there are a couple different methods you could use, but RLE is definitely not the right choice. There are two main reasons you wouldn't use RLE. The first is that most programs on calc do not have long strips of the byte and the second is that if a program did have long amounts of the same number, the programmer would either compress it themselves or render that on the fly. What this means is that I would assume that RLE would make most programs larger

So, for a better alternative, so far in my life I've used LZ77 and DEFLATE. LZ77 is what's called a floating window where you search the past X bytes to see if you can find a match for the data your are currently looking at. X can be whatever you want, but for this project, since you probably won't be compressing stuff that won't fit in ram, you can just search the whole program for a match. DEFLATE uses the exact same principle as LZ77 except it also compresses the "data" used to tell the decompressor where to search for a byte.

What I would suggest is that first you take a look at LZ77 and get that running. Once you're happy with how that works (even if you're still increasing size when you compress), you can then make a few slight modifications and you'll be using DEFLATE, at which point you'll probably get some nice ratios.


If you want some source examples, I've done LZ77 and DEFLATE compression on the computer and I've decompressed them both on the calculator. (Though DEFLATE was done in TruVid so the code is rather scary (and runs at $F000)). The only problem with my code is that I made up my own data format to fit my needs.

And for information on these two, the LZ77 Wikipedia page is probably enough to get you going. For DEFLATE this is the page I used. (You can't make up DEFLATE like you can LZ77)

LZ77 is good for really big amounts of data, and it gets rid of byte boundaries, but here's a small example.

First of all, since you'll be working with sizes no bigger than calculator ram, you should probably make your sliding window just big enough to include the whole program, (2,048, 4,096, 8,192, 16,384). So, for this example, I'll go with 2,048 (11 bits). Also, for max match size, I'll use 7 bits.

Also, 0 will mean uncompressed and will be followed by the number of uncompressed bytes (7 bits) and 1 will mean compressed and will be followed by search distance then size.

Key:
(1 bit)
8 bits
[11 bits]
{7 bits}

00 01 02 03 04 05 06 07 08 09 00 00 06 07 08 09 00 00 06 02 03 04 05 06 08 09 04 03 06 06 06 06 06 06 06 06 06 06 04 04 05 08 09 09 01 01 01 02 03 04 05

(0) {12} 00 01 02 03 04 05 06 07 08 09 00 00 (1) [6] {7} (1) [17] {5} (0) {5} 08 09 04 03 06 (1) [01] {9} (0) {8} 04 04 05 08 09 09 01 (1) [45] {5}

That wasn't easy. In this small example, even though we didn't fully make use of all the bits we had in the size fields, and this data was super short, we still went from 408 bits to 292 bits.

Also, if you manage to follow what happened there, you'll see that this method actually encompasses RLE

in his compressed data, if a bit is a 0, it will tell the decompressor that the next section of bytes in the compressed stream is a string of uncompressed bytes. the next 7 bits in that same byte indicate the number of uncompressed bytes that will follow. the first uncompressed section in his code is this:
(0) {12} 00 01 02 03 04 05 06 07 08 09 00 00
with a 0 bit indicating that it's uncompressed, and the next 7 holding the number 12, indicating 12 bytes of uncompressed data will follow.

after that, the decompressor checks for a 0 or 1 in the next bit again. if it sees a 1, it knows that the next session is compressed, in that, rather than storing uncompressed data, it checks the number stored in the next 11 bits to find the point in the data that is being pointed to. it then checks the 7 bits after that, which hold the number of bytes to be copied from that spot in the data.

in his example, the first compressed section is this:
(1) [6] {7}
firstly, i'm fairly certain that this should be
(1) [7] {6}
instead, which says, move into the compressed data 7 bytes, and copy the next 6 bytes to that point in the uncompressed data.
he's taking advantage that this section:
06 07 08 09 00 00 06 07 08 09 00 00
has the same string of bytes occur twice in a row to have it only occur once in the compressed data, and just refer back to it for the second one.

i hope that helps a bit. =)