The Shrine

I am actually implementing a small and rather limited but still commercially usable PNG decoder. This might be the first truly hard task I've ever undertaken (especially since I started around 10PM last night, it's 6AM now, and I'm trying to finish in in about another 8 hours or so, though it's not a hard-and-fast requirement).

We're only supporting 16- and 256- color, paletted, non-interlaced images right now, and ignoring all non-crucial blocks (like gamma correction), which is almost a microscopic subset of all possible PNG images. PNG is a very flexible and in my opinion pretty bad-ass format. Still, writing a decoder is tough - I'm having to learn about LZ77 compression on the fly, and I still have the defiltering step afterwards. PNG data achieves the great compression it does partially because before compressing its pixel data, it rearranges each scanline (a scanline is a horizontal line in the image) according to one of a few predictable algorithms that improve the compressibility of the data. However, after it's uncompressed, it has to be defiltered as well, by applying the algorithm that was originally applied to the scanline in reverse, and this can be different for each scanline. (Though, actually, it seems like compared to LZ77 compression/decompression, the filtering/defiltering steps are cake.)

Anyway, for anyone who doesn't care about this kind of thing (quite possibly most of you), the thing I really wanted to convey is that I actually finally feel like I'm earning the wings for my "serious programmer" credential, so to speak.

As for why I'm not using one of the existing decoder libraries, I'd rather not waste code space implementing a complete decoder given mobile phone requirements, and I have no guarantee that any we'd use wouldn't be unusable due to a static or global variable of some kind (illegal in BREW) anyway. We actually need a decoder that only supports this limited subset of PNG, and I don't know of any decoder that would fit.

What's great is that I'm quite excited, and am starting to be pretty happy to be becoming the kind of geek that is thrilled to be pulling an all-nighter doing this. I suppose that makes me rather different, but really, who gives a pair of rat's asses...just wanted to share some exuberance with you all.

I love PNG's file format, especially the data chunks. It was very well designed. The title of each chunk has capital or lowercase letters as a set of "bits" pertaining to the block.

Have you ever written a decoder? I could use an assist, the compression part of it is pretty tricky.

Nope. I researched it when I was planning on using a variant of the file format for graphics with my game, but never really coded. Nowadays, I try to stay away from low-level stuff.

Yeah, compression is pretty tricky, so it would pay off to read up on the LZ77 format in detail. Compression algorithms rival cryptography algorithms in complexity. (In some cases, they are almost the same thing.) I'm surprised that you're planning on finishing this in one day.

Yes, well, that plan is not working out, but I am at least making progress.

I have the RFC (Request For Comments) for both LZ77 and DEFLATE (the Hoffman/LZ77 combination used by PNG), which are good overviews. I tried reading the original LZ77 paper too, but it includes all the formal math to back up the algorithm and it would likely take me days to really understand it in depth, and I think I can probably do the decoder faster without it.

I find the whitepapers a little confusing, actually, and I can't find supplemental information on it that's any better. The thing is that they use all sorts of nutty tricks to really squish the file (which is what we need on something like a phone), like compressing the two Hoffman trees they use with another Hoffman tree. Also, I'm slightly confused by the decoding algorithm, which says to "backtrack and copy bytes" if you find a LZ77 backwards-length/value pair, but does that mean insert or overwrite?

Anyway, I have no doubt that I'll get it with some time, and I think that a lightweight PNG decoder for a phone might be a fairly hot technology actually for phone space. None of the external developer projects I was working on at JAMDAT had one; some had their own tools, but a reader for a very efficient and non-proprietary format like PNG that nearly all major graphics programs support I think might be really useful. There may be some companies out there that have them, but I'm guessing they're keeping them to themselves if so.

Very cool accomplishment, but I find it hard to believe there's no available LZ77 algorithms implemented out there. One I know of, 7-zip is something I looked at for an old company.

On the one hand, doing something like this is a nice test of your coding skills and something you can learn from. On the other, something this complicated takes a while to get exactly right and it's better to use implementations that have already been tested.

Still, implementing LZ77 is no joke.

I don't have to implement an encoder, just a decoder. There are public-license implementations of DEFLATE (PNG actually uses a combination of compression techniques by this name - LZ77 and Huffman trees), but all the ones I've seen are part of a full-featured encoder/decoder, and I'm really not sure it wouldn't be just as much work to try to pull the decoding part out and just use that. Even if I did, it would be likely to be a lot bigger in code size than we want, because even if it were the best, tightest, smallest, fastest code in the world, it still contains functionality to deflate all types of PNG files, whereas I'm only doing enough to support paletted images. Size of the code itself is really quite an issue on phones, and I don't want to bloat our MOD by 10K (or however much a full-featured decoder would end up adding to code size).

Also, there's the learning thing you'd mentioned, which has been good too - I had to really get my bitwise/bitshift operators down, because DEFLATE packs bits, and these were easily my weakest operators in C++.

isnt that an oxymoron? Badass of programming?....

Actually, I'd say anyone who'd believe that is somewhat of an oxymoron himself.

Still working on it, somebody shoot me, my world is pain.

Heh, you got the love the juxtaposition of the start and end of this thread. I suppose your next hat trick is to code a Chess AI in 8 hours.

Any particular reason for the sudden condescencion and baiting? I suppose I did give you a lot of shit when you steered Barret wrong on his broadband setup...

Relax. I'm only giving you a friendly ribbing. Seriously, I hope you get it done, but at least you now know how hard it is to write a compression/decompression routine from stratch.