next »

[Pineapple]

Well, I've got this compiler & interpreter I'm writing for the heck of it. So far I've written 4 compression methods for its sprite data; the data conversion program chooses the smallest compression result and makes usable data out of it that will be read by the interpreter's sprite drawing command.

Each pixel is comprised of 4 bits, which will be colors on a pallet at some point. At the moment, the valid RGB values are 0,0,0 64,64,64 128,128,128 and 256,256,256 - anything else is automatically counted by the interpreter as 0.

Note that the fourth compression method (which searches for 12 simple patterns 4096 pixels ahead, for each pixel) can take quite a while to process.

Please see if you can find any specific image characteristics that are ineffectively compressed by all methods. Also notify me of bugs, if you please.



Download it here

It'll ask for the image path (just put it in the same directory and type the image's filename, extension included) and frame size. This will be used for spritesheets, not individual sprites, so that's merely how many pixels large each tile will be.



TECHNICAL ASPECTS:
The random data test is an image generated by spraying the MS spraycan tool all over the place to where all colors made up appx. 25% of the image. The compressor is not intended to be compressing truly random data.

Mode 0 is an uncompressed bitmap storing each pixel in 2 bits.

Mode 1 is RLE compression that stores each 2 bit color value as a byte and how many, up to 256, of the same color follow it. Strength: small images
Random data test: 145% expansion

Mode 2 is similar to the above, except the RLE data is stored in 1 byte. 6 bits are for the number following and 2 bits are for the color. Strength: typical pixel art imagery
Random data test: 73% compression

Mode 3 stores the RLE compressed data for 2 pixel data in 1 byte. 2 bits are for each quantity and 2 bits are for each color. Strength: Unpatterned data
Random data test: 36% compression

Mode 4 scans for 12 simple patterns: 4096 consecutive zeros, 1024 consecutive zeros, 256 consecutive zeros, 64 consecutive zeros, four consecutive of every color, and three consecutive of every color. 4 values are reserved for single colors that are part of none of these patterns. The data for 2 patterns is stored in 1 byte. Strength: Images with generous amounts of empty space
Random data test: 44% compression

I am still looking into additional compression methods that won't be too difficult to implement.

[Pineapple]

Oh-my-effing-garshness

That mode 3 compressor is the shiz. It just compressed its own output by almost a third.

Going for a third pass now, will report back soon.


REPORT:
Wow. I must have some sort of an error someplace. The random-ish image file first started at a compression size of appx. 6,000 bytes. That went down to about 2,100 bytes. The third pass is down to 710 bytes. I've almost broken Shannon's Law. Going for a fourth pass. If it succeeds, I'll make a decompressor and see whether I can come back up with the original data.

[Pineapple]

Bah, it must be a mistake. The compression can store pixels in up to a 5:4 pixel to bit ratio at the absolute maximum, and uncompressed is 1:2. It's been reducing sizes by much more than 50%, so something's screwy.

That said, I still think it may still be effective at compressing random data.

[Overkill]

Why reinvent the wheel? Just use an existing lossless compression library like zlib (which uses the DEFLATE algorithm, which is used in libpng and gzip). Since you're looking for easy to implement, why not just use something that's already been implemented, heavily tested, and used in tons of software already! :D

I mean, making byte-packing compression algorithms can be fun. But it concerns me that you haven't written a decompressor yet, which means there may be large oversights in how the compression will be reversed effectively.

Though I guess you're going for a "runtime" decompression that happens on every draw, which means zlib might not be suitable. But, you may want to decompress the images when they're first loaded instead of when the draw command kicks in, so the compression algorithms don't cause any render slowdown. In this case, zlib can become suitable, and your program can just copy raw pixel data and have to not worry about compression mode settings EVERY iteration.

[Pineapple]

I do know what I'm doing, I've written bit-level image compression algorithms more than once for games I just never finished. I like the nostalgia of 2-bit graphics, and whenever I do them I just have to make them really be that way.

Anyway, I'll come back to this at some other point, but I know for sure that something screwy is going on with that compression.

[Triplefox]

I recall investigating this line of thinking myself. I think it's gonna be really, really hard to outcompress palettized PNG once you break through the fixed cost of the header. And then once you have it loaded you have to go through another translation layer to get the final RGB output(this latter part is the part I focused on more in my experiments). And when drawing the graphics you'll probably want custom tools of some kind to see all the colors. It really is just a huge pain to do a complete emulation of older graphics hardware, even if it's technically beautiful.

But if you just want the small size, PNG is where it's at.

[Evan Balster]

Old-school graphics systems didn't use compression per se.  A byte would correspond to four 2-bit pixels.  That's a 75% (or 94.75%, if a pixel is four bytes to begin with) compression every time, without complication.

If you want something more solid, go with zlib or PNG like the last chap said.