Is this a good compression format?

[dragonboy]

It's a long thread, and it may sound comfusing at first, but once you get to the end you'll figure out what I'm talking about. I'm not going to use this in any project I'll be doing now (until I manage to figure out how to use a Command Prompt) but I just want to share my idea with the Sega-16 community.

there are two parts/steps of the compression format. Step 1, is like LSZZ compression, and is used to eliminate reocurring patterns in colors. Step 2, is like RLE and is there to expand every color to their correct legnth. It's that way because I noticed that the colors always repeat themselves in the same order, but the amount of times every individual color repeats itself always changes.

There are three different threads/lists of bits in this:

compressed list- thread of compressed data

semidecompressed list- data that has been decoded through the LSZZ part but not the RLE part

decompressed list- the final decompressed sprite

the first step:

take the next bit in the compressed list:

if 0:
the next four bits in the compressed list are the next pixel/color in semidecompressed list

if 1:
the next eight bits in the compressed list are in this format
SSSSSLLL
S-source
L-legnth

it subtracts S from the current position in the semidecompressed list, and copies every pixel from there to the front of the semidecompressed list for the legnth of L.

repeat this step until you reached the last pixel in the semidecompressed list

the second step

take the first pixel/color in the semidecompressed list, and move it into decompressed list.

take the next bit in the compressed list:

if 0: repeat last pixel/color in the decompressed list

if 1: move next pixel/color from the semidecompressed list into the decompressed list

grab the next bit in the compressed list and do the same until you reach the last pixel in the decompressed list

[Joe Redifer]

I think Zip files are pretty neat!!

[tomaitheous]

One optimization you can do it add 2 to value of LLL copy length. Given if this was for a 4bit linear format, the LZ operand is the length of two raw pixels so it should have a minimum of 2 pixels hence the addition of 2. Gives you more length for your buck

Also, since you're layering two compression schemes, you're increasing 2bits to every 4bit chunk that doesn't get compression (1bit in the LZ scheme and 1 bit on the RLE scheme). It can compressed file to less than worth while gain or even worst bloat it to more than the original size (depends on the source file). There are two ways around that.

First method is to have the LZ operation take care of the RLE and set the bitmap flag to every 2 pixels cutting down the overhead of raw pixels from 2bits to 1/2bit (and since you don't need it for one pixel because the operand for RLE will cost about 2 pixels canceling out the savings). To setup RLE on a LZ window, write the first byte as raw to the destination pointer, then set the LZ history windows to -1... one place behind the pointer The length (LLL+2) becomes the length of RLE. It's also custom to have the control bits in a group, usually in a byte (group of 8 bitmap flags) and the decompression knows when to grab the next byte as the mask(bitmap flag). Makes decoding faster too since you have less bit shifting and logic.

The other method is to use variable length control flags. A binary tree. If D0 = 0, then raw, if D0 = 1 then check D1. If D1 = 0 then RLE, else (D1=1) LZ windows+offset, etc. With this method you *do* have to bit pack the data unlike the above method, but you can have longer than RLE lengths (whatever you decide on). Since a single raw pixel (or two as appropriate) is assigned to D0 as 0, it only has 1bit overhead. I've done this for multiple type RLE control codes: nibble, byte, word, 3 byte, and 4 byte RLE patterns.

The best thing is not to try and use one compression scheme for everything. Have different variants that focus more on one thing over another and have a single byte header so the decompression routine know why decompression algorithm to use. Of course figure out the best compression scheme would have to be done externally from an app you write yourself.

[evildragon]

I think Zip files are pretty neat!!

This is graphics compression on the Genesis.

I don't think Zip files are blast processing compatible.

[Joe Redifer]

I like RAR, too, but it seems perhaps maybe just a bit elitist sometimes, I dunno. GZip is pretty fun. SIT used to be cool but none of the cool kids use SIT files any more. So I guess ZIP files are the neatest of the bunch.

[evildragon]

Those are FILE compression formats!

Whats in discussion is graphics compression formats for use on the Genesis.

Joe, your ignorance is showing.

[playgen]

I think your inability to tell when someone is joking on the internet is showing!

[TmEE]

file compression, gfx compression... no difference, unless one is lossy which doesn't work well for data files...

[evildragon]

I think your inability to tell when someone is joking on the internet is showing!

I can't tell in real life. Having aspergers is hard when it comes to social skills.

[dragonboy]

First method is to have the LZ operation take care of the RLE and set the bitmap flag to every 2 pixels cutting down the overhead of raw pixels from 2bits to 1/2bit (and since you don't need it for one pixel because the operand for RLE will cost about 2 pixels canceling out the savings). To setup RLE on a LZ window, write the first byte as raw to the destination pointer, then set the LZ history windows to -1... one place behind the pointer The length (LLL+2) becomes the length of RLE. It's also custom to have the control bits in a group, usually in a byte (group of 8 bitmap flags) and the decompression knows when to grab the next byte as the mask(bitmap flag). Makes decoding faster too since you have less bit shifting and logic.

There are not supposed to be very many raw pixels anyway.
1) there are a ton of consecutive pixels with the same color in every sprite.
2) with taking out the all the same consecutive pixels, LZSS will occur a lot more often, since everything doesn't have to be exactly the same, because you can have the same colors but with different legnths.

Example:

red, red, red, green, green, blue, green, green

can later appear as:

red, green, green, green, green, blue, blue, green

because the lengths of the colors can be different, even when LZSS is applied.

[tomaitheous]

There are not supposed to be very many raw pixels anyway.

True. With your method of a 1bit repeat it's definitely optimized for 2,3,4 sequenced pixels runs. But that method's less efficient for longer run of pixels. I'd still do a multi compression scheme system with a single byte identifier for the header.

Btw what does your avatar compress to? With with the file set to 4bit, pucrunch compresses it down from 6000 bytes to 830 bytes.

[dragonboy]

I'll compress my avatar, but it will take me a while since I have to do it manually.


I've make some improvements: I'll have the RLE part start with two bytes: LLLLLLLL LLBBBTTT

L: legnth of specific area in the unit of "legnths for individual colors"
B: amount of bits for the legnth of anycolor except color-0
T: amount of bits for the legnth of color-0

for every legnth size, legnth-0 signifies the legnth of a color will be longer than the maximum legnth; when the legnth is #0 it will be followed by another legnth, of the same legnth size, that is added to the highest possible legnth for that legnth size.

at the end of every specific area, there will be another 2 bytes that do the same.

The reason why I gave another legnth size for color-0, also known as transparency color, is because I notice in many sprites color-0 has much a wider area of covering than the rest of colors.